implement searchable bitfields

[andrewboie]

Is your enhancement proposal related to a problem? Please describe. This is related to #28900 and will be used to improve management of pages in the virtual address space, which currently can be allocated but not freed. We want to manage the address space using a searchable bitfield instead.

Describe the solution you'd like For a bitfield defined with something resembling:

static Z_BITFIELD_DECLARE(bitfield, num_bits);

which expands to (roughly):

static long bitfield[num_bits / sizeof(long)];

We want an allocation function, something like:

/**
 * Reserve contiguous bits in the bitfield
 *
 * If a contiguous region is found, it will be marked as in-use.
 *
 * @param bitfield Bitfield to examine
 * @param bitfield_size Number of bits in the bitfield
 * @param region_size Number of bits to allocate
 * @param offset Output parameter indicating offset (in bits) within the bitfield containing sufficient space
 * @retval 0 Success
 * @retval -1 No free space in the bitfield for the requested allocation
 *
int z_bitfield_alloc(void *bitfield, size_t bitfield_size, size_t region_size, size_t *offset);

and a release function, something like:

/**
 * Release in-use bits in a bitfield
 *
 * A 'region_size' number of bits starting at bit position 'offset' will be marked as
 * not being in use any more.
 * @param bitfield Bitfield to manipulate
 * @param region_size Number of bits to mark as not in use
 * @param offset Starting bit position to mark as not in use
 */
void z_bitfield_free(void *bitfield, size_t region_size, size_t offset);

We'll need some tests to show that this works. Put the implementation in lib/os in its own C file. The tests probably in tesks/kernel/common/src/bitfield.c.

It may be better to use a 1 for free bits as that will allow functions like __builtin_ffsl() to be used to help search it. Many CPUs have native instructions for things like __builtin_ffsl() which is why I suggest long as the array data type.

If the initial state of the bitfield is not all 0, we'll need a way to initialize it, preferably at build time in the Z_BITFIELD_DECLARE macro. GCC lets you do this with designated initilizers, e.g. int num[5]={ [0 . . . 4 ] = 3 }; // num = { 3, 3, 3, 3, 3}

Use every clever bit-twiddling hack you can think of to optimize the searching part, this is just a rough guide. But I expect this will be essentially something between O(n) and O(n^2) worst-case.

There's no limit on the region size, it may span multiple array elements.

No need to implement any kind of locking, that's an exercise for users of this API.

If you can find some existing Apache (or compatible) licensed code that already does what we need here, we can talk about possibly bringing it in instead of rolling our own.

The above API definitions are sketches and not graven in stone. #28900 and #28899 have detail about usage.

[dcpleung]

Done in #34686