uma: Use a hand-rolled bitset implementation

[markj]

Summary

Using bitset.h means that each bitset word has size 8 on 64-bit
platforms, which complicates the problem of embedding a slab header in
struct vm_page. Stop using bitset.h and instead make each word an int.
This requires more code, but not a prohibitive amount.

[dougm]

Could you shrink uma_slab at still use BITSET?

1. In slab_sizeof, replace sizeof(struct uma_slab) with __offsetof(struct uma_slab, us_free[1])
2. In uma_core.c, define

long *slab_bits(uma_slab_t slab)
{ return ((long *)&slab->us_free[1]); }

and replace &slab-us_free with slab_bits(slab) in several places.

sys/vm/uma_core.c

161

ffsl ->ffs

162

When is bit == 0?

[markj]

In D50640#1156315, @dougm wrote:

Could you shrink uma_slab at still use BITSET?

1. In slab_sizeof, replace sizeof(struct uma_slab) with __offsetof(struct uma_slab, us_free[1])
2. In uma_core.c, define

long *slab_bits(uma_slab_t slab)
{ return ((long *)&slab->us_free[1]); }

and replace &slab-us_free with slab_bits(slab) in several places.

Do you mean that slab->us_free should still have type int *? Then, is the idea that BIT_* would only access the low 32 bits of each bitset (us_free and slab_dbg_bits()), so it's okay to let them overlap from the perspective of BIT_*?

To describe the final result more concretely, when a uma_slab is embedded in the page header, the slab header layout effectively becomes:

struct uma_slab {
    LIST_ENTRY(uma_slab) us_link;
    uint16_t us_freecount;
    uint8_t us_flags;
    uint8_t us_domain;
    int us_free[3];
};

In a non-INVARIANTS kernel, this permits a set size of up to 96, and in an INVARIANTS kernel the maximum set size is 32.

[dougm]

In D50640#1156361, @markj wrote:

Do you mean that slab->us_free should still have type int *? Then, is the idea that BIT_* would only access the low 32 bits of each bitset (us_free and slab_dbg_bits()), so it's okay to let them overlap from the perspective of BIT_*?

I mean that slab->us_free should have type int[], as it does with your proposed change, which is not a pointer, but just a name that marks the end of the struct. Because it is an int[] and not a long[], it does not add padding when it is embedded in a page struct.
The idea is that, with this change, (long *)&slab->us_free[1] has the same behavior as &slab->us_free does now - it is an offset where an array of longs begins.

[markj]

In D50640#1156376, @dougm wrote:

In D50640#1156361, @markj wrote:

Do you mean that slab->us_free should still have type int *? Then, is the idea that BIT_* would only access the low 32 bits of each bitset (us_free and slab_dbg_bits()), so it's okay to let them overlap from the perspective of BIT_*?

I mean that slab->us_free should have type int[], as it does with your proposed change, which is not a pointer, but just a name that marks the end of the struct. Because it is an int[] and not a long[], it does not add padding when it is embedded in a page struct.
The idea is that, with this change, (long *)&slab->us_free[1] has the same behavior as &slab->us_free does now - it is an offset where an array of longs begins.

Sorry, I don't quite follow--with that scheme there is indeed no padding, but the 4 bytes between us_domain and us_free[1] are still unused. The reason for using int[] is to be able to fit two bitmaps into 12 bytes. The BIT_* macros want each bitmap to be at least 8 bytes in size (on 64-bit platforms, where sizeof(long) == 8).

[markj]

Fix issues in slab_bitset_ffs().