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

["Emil Tsalapatis" <emil@etsalapatis.com>]

On Tue Jun 30, 2026 at 5:44 PM EDT, Ihor Solodrai wrote:
> 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?
>
>

How about keeping the check here and removing the unaligned bit handling
below? We don't test for it either, and I can't currently think of any
good use cases for it. So we can make sure here that the caller knows
the bit size should be word aligned.

>> +
>> +	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?
>

Yes, set/clear are not atomic and we are missing test and set. I can add
those.

> 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?
>

Yeah let's do that. AFAIK we only have cmpxchg for atomics so I'll use
it for the logic. It's expensive, but I don't think we can generate
anything like x86's btsl.

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

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