Re: [PATCH bpf-next 4/5] selftests/bpf: Add arena-based bitmap data structure

[Ihor Solodrai <ihor.solodrai@linux.dev>]

On 6/18/26 1:56 AM, Emil Tsalapatis wrote:
> Add an arena-based word-aligned bitmap data struture. The
> structure is useful as a building block, e.g., sched-ext
> uses it to represent cpumask structures.
> 
> Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
> ---
>  .../bpf/libarena/include/libarena/bitmap.h    |  31 +++
>  .../selftests/bpf/libarena/src/bitmap.bpf.c   | 191 ++++++++++++++++++
>  2 files changed, 222 insertions(+)
>  create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
>  create mode 100644 tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
> 
> diff --git a/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
> new file mode 100644
> index 000000000000..11623a82e66a
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/include/libarena/bitmap.h
> @@ -0,0 +1,31 @@
> +#pragma once
> +
> +#define BITS_PER_BYTE		8
> +#define BYTES_TO_BITS(nb)	((nb) * BITS_PER_BYTE)
> +
> +#define BITS_PER_LONG		(sizeof(long) * BITS_PER_BYTE)
> +#define BITS_TO_LONGS(nr)	(((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG)
> +#define BIT_MASK(nr)		(1UL << ((nr) % BITS_PER_LONG))
> +#define BIT_WORD(nr)		((nr) / BITS_PER_LONG)
> +
> +struct bitmap {
> +	u64 bits[0];
> +};
> +
> +struct bitmap __arena *bmp_alloc(size_t bits);
> +void bmp_free(struct bitmap __arena *bmp);
> +
> +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp);
> +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp);
> +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp);
> +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp);
> +
> +void bmp_clear(size_t bits, struct bitmap __arena *bmp);
> +void bmp_and(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2);
> +void bmp_or(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src1, struct bitmap __arena *src2);
> +bool bmp_empty(size_t bits, struct bitmap __arena *bmp);
> +void bmp_copy(size_t bits, struct bitmap __arena *dst, struct bitmap __arena *src);
> +
> +bool bmp_intersects(size_t bits, struct bitmap __arena *arg1, struct bitmap __arena *arg2);
> +bool bmp_subset(size_t bits, struct bitmap __arena *big, struct bitmap __arena *small);
> +void bmp_print(size_t bits, struct bitmap __arena *bmp);
> diff --git a/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
> new file mode 100644
> index 000000000000..a8ca814aa0c8
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/libarena/src/bitmap.bpf.c
> @@ -0,0 +1,191 @@
> +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause
> +/*
> + * Copyright (c) 2025-2026 Meta Platforms, Inc. and affiliates.
> + * Copyright (c) 2025-2026 Emil Tsalapatis <emil@etsalapatis.com>
> + */
> +
> +#include <libarena/common.h>
> +
> +#include <libarena/asan.h>
> +#include <libarena/bitmap.h>
> +
> +__weak
> +struct bitmap __arena *bmp_alloc(size_t bits)
> +{
> +	struct bitmap __arena *bmp;
> +	size_t size = BITS_TO_LONGS(bits) * sizeof(bmp->bits[0]);
> +
> +	/* Assume long-aligned masks. */
> +	if (bits % BITS_PER_LONG)
> +		return NULL;

I think this check may be dropped.

There is code below to handle non-aligned bits (bmp_last_word_mask
etc), but here we forbid them, so masking doesn't run.

And you mentioned in the cover that this is supposed to be used as
cpumask, but nr_cpu_ids is unlikely to be a multiple of 64, right?


> +
> +	bmp = (struct bitmap __arena *)arena_malloc(size);
> +	if (!bmp)
> +		return NULL;
> +
> +	bmp_clear(bits, bmp);
> +
> +	return bmp;
> +}
> +
> +__weak
> +void bmp_free(struct bitmap __arena *bmp)
> +{
> +	arena_free(bmp);
> +}
> +
> +__weak
> +void bmp_set_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	bmp->bits[BIT_WORD(bit)] |= BIT_MASK(bit);
> +}
> +
> +__weak
> +void bmp_clear_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	bmp->bits[BIT_WORD(bit)] &= ~BIT_MASK(bit);
> +}
> +
> +__weak
> +bool bmp_test_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	return bmp->bits[BIT_WORD(bit)] & BIT_MASK(bit);
> +}
> +
> +__weak
> +bool bmp_test_and_clear_bit(u32 bit, struct bitmap __arena *bmp)
> +{
> +	u64 val = BIT_MASK(bit);
> +	u32 idx = BIT_WORD(bit);
> +	u64 actual;
> +
> +	do {
> +		u64 old = bmp->bits[idx];
> +
> +		if (!(old & val))
> +			return false;
> +
> +		u64 new = old & ~val;
> +		actual = cmpxchg(&bmp->bits[idx], old, new);

bmp_test_and_clear_bit() is atomic, but bmp_set_bit() and
bmp_clear_bit() aren't.

So the concurrent set/clear on the same word can lose updates (last
writer wins), right?  Only test_and_clear seems to be safe
cross-CPU. Are we missing test_and_set?

There is a doc on atomic bitops [1], and apparently in the kernel
there is a convention to have a non-atomic variant for each RMW atomic
operation, prefixed with '__', for example: test_and_clear_bit() and
__test_and_clear_bit().

Maybe libarena should follow the same convention?

[1] https://docs.kernel.org/core-api/wrappers/atomic_bitops.html


> +
> +		if (actual == old)
> +			return true;
> +
> +	} while (can_loop);
> +
> +	return false;
> +}
> +
> [...]