Re: [PATCH bpf-next v1 3/7] selftests/bpf: libarena: Add buddy per-CPU caches

[sashiko-bot@kernel.org]

Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [Medium] selftests/bpf: missing cache validity and NULL checks in buddy.bpf.c
- [Medium] selftests/bpf: missing pointer validation in buddy_cache_free()
- [Medium] selftests/bpf: out-of-bounds write in buddy_cache_state_destroy()
--

commit 8dee6e0e331ae6f1872b723dff5e251350292c90
Author: Emil Tsalapatis <emil@etsalapatis.com>

selftests/bpf: libarena: Add buddy per-CPU caches

This commit introduces per-CPU LIFO array caches in struct buddy for the
eight smallest allocation orders so small allocations and frees can bypass
the central buddy allocator lock on the fast path.

> diff --git a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> index 72b9ea3ac7d53..ce05e3e58ebae 100644
> --- a/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c
> +++ b/tools/testing/selftests/bpf/libarena/src/buddy.bpf.c

[ ... ]

> @@ -38,18 +42,116 @@
>   * and their allocation state. It also includes the freelist
>   * heads for the allocation itself.
>   */

[ ... ]

> +static __always_inline void __arena *
> +buddy_cache_pop(struct buddy_cache __arena *cache, int order)
> +{
> +	struct buddy_cache_order __arena *slots;
> +	void __arena *addr;
> +	u32 elems;
> +
> +	slots = &cache->orders[order];
> +	elems = READ_ONCE(slots->elems);
> +	if (!elems)
> +		return NULL;
> +
> +	addr = READ_ONCE(slots->objects[elems - 1]);
> +	WRITE_ONCE(slots->elems, elems - 1);
> +
> +	return addr;
> +}
> +
> +static __always_inline int buddy_cache_push(struct buddy_cache __arena *cache,
> +					    int order, void __arena *obj)
> +{
> +	struct buddy_cache_order __arena *slots;
> +	u32 elems;
> +
> +	slots = &cache->orders[order];
> +	elems = READ_ONCE(slots->elems);
> +	if (elems >= BUDDY_CACHE_CAPACITY)
> +		return -ENOMEM;
> +
> +	WRITE_ONCE(slots->objects[elems], obj);
> +	WRITE_ONCE(slots->elems, elems + 1);
> +
> +	return 0;
> +}
> +
> +void __arena *buddy_cache_alloc(struct buddy __arena *buddy, size_t order)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	struct buddy_cache __arena *cache;
> +	unsigned int cpu;
> +
> +	DISABLE_CACHE_IF_ASAN(NULL);
> +
> +	if (order >= BUDDY_CACHE_NUM_ORDERS)
> +		return NULL;
> +
> +	cpu = bpf_get_smp_processor_id();
> +	cache = state->percpu[cpu];
> +
> +	return buddy_cache_pop(cache, order);
> +}

[Severity: Medium]
Should buddy_cache_alloc() and buddy_cache_free() check that buddy is
non-NULL, that READ_ONCE(state->valid) is true, and that cache is non-NULL
before calling buddy_cache_pop() or buddy_cache_push()?

In buddy_alloc(), buddy_cache_alloc(buddy, order) is now called before
buddy_alloc_memory() checks if (!buddy):

buddy_alloc()
    order = size_to_order(size);
    address = buddy_cache_alloc(buddy, order);
    if (address)
        return address;
    return buddy_alloc_memory(buddy, size, order, 0);

Calling buddy_alloc(NULL, size) for a cached order (order <
BUDDY_CACHE_NUM_ORDERS) will therefore dereference &buddy->cache_state in
buddy_cache_alloc().

In addition, buddy_cache_state_init() and buddy_cache_state_destroy()
maintain state->valid with WRITE_ONCE(), but neither this commit nor the
follow-up commits in the series check state->valid or cache != NULL in
buddy.bpf.c. If buddy_alloc() or buddy_free() is called while cache_state is
uninitialized or destroyed (where state->valid is false and
state->percpu[cpu] is NULL), buddy_cache_pop() and buddy_cache_push() will
dereference NULL at arena address 0. Because BPF exception handling on
reserved page 0 zeroes loads and ignores stores, buddy_cache_push() will
read elems as 0, ignore the stores, and return 0, causing buddy_free() to
silently drop the freed block instead of returning it to the central buddy
allocator.

> +
> +/* Retrieve the order of an allocation from the address. */
> +static int buddy_cache_get_order(void __arena *addr)
> +{
> +	struct buddy_chunk __arena *chunk;
> +	u64 idx;
> +
> +	chunk = (void __arena *)((u64)addr & ~BUDDY_CHUNK_OFFSET_MASK);
> +	idx = ((u64)addr & BUDDY_CHUNK_OFFSET_MASK) / BUDDY_MIN_ALLOC_BYTES;
> +
> +	return idx_get_order(chunk, idx);
> +}
> +
> +int buddy_cache_free(struct buddy __arena *buddy, void __arena *addr)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	struct buddy_cache __arena *cache;
> +	unsigned int cpu;
> +	int order;
> +
> +	DISABLE_CACHE_IF_ASAN(-EINVAL);
> +
> +	order = buddy_cache_get_order(addr);
> +	if (order >= BUDDY_CACHE_NUM_ORDERS)
> +		return -EINVAL;
> +
> +	cpu = bpf_get_smp_processor_id();
> +	cache = state->percpu[cpu];
>  
> +	return buddy_cache_push(cache, order, addr);
> +}

[Severity: Medium]
What prevents buddy_cache_free() from accepting unaligned, interior, or
unallocated pointers before buddy_free_unlocked() can validate them?

In buddy_free(), buddy_cache_free() is invoked prior to
buddy_free_unlocked():

buddy_free()
    ret = buddy_cache_free(buddy, addr);
    if (!ret)
        return 0;
    ...
    ret = buddy_free_unlocked(buddy, (u64)addr);

While buddy_free_unlocked() checks that addr is aligned to
BUDDY_MIN_ALLOC_BYTES and verifies that idx is marked allocated via
idx_set_allocated(chunk, idx, false), buddy_cache_get_order() divides by
BUDDY_MIN_ALLOC_BYTES and reads idx_get_order(chunk, idx) without checking
either alignment or chunk->allocated.

When a chunk is initialized in buddy_chunk_get(), chunk->orders is
zero-initialized, and buddy_chunk_alloc() only sets the order and allocated
bit at the head index idx of each allocated block (advancing by idx += 1U <<
order_req), leaving interior sub-block indices with allocated == 0 and
order == 0.

If a caller passes an interior pointer such as
(u8 __arena *)alloc_path_test.bulk[i] + BUDDY_MIN_ALLOC_BYTES (as tested by
test_buddy_cache_paths() in the follow-up commit "selftests/bpf: libarena:
Cover buddy cache fast paths"), buddy_cache_get_order() reads order 0 at
idx + 1, and buddy_cache_free() pushes the interior pointer into the order-0
per-CPU cache and returns 0 instead of failing with -EINVAL. Likewise, an
unaligned pointer inside an allocated cached-order block has its low bits
truncated by the division in buddy_cache_get_order() and is pushed unaligned
into the per-CPU cache, corrupting subsequent buddy_alloc() returns.

[ ... ]

> @@ -557,6 +659,46 @@ static struct buddy_chunk __arena *buddy_chunk_get(struct buddy __arena *buddy)
>  	return chunk;
>  }
>  
> +static int buddy_cache_state_init(struct buddy __arena *buddy)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	struct buddy_cache __arena *cache;
> +	unsigned int cpu, order;
> +	int ret;
> +
> +	DISABLE_CACHE_IF_ASAN(0);
> +
> +	if (CONFIG_NR_CPUS > BUDDY_CACHE_MAX_CPUS)
> +		return -E2BIG;
> +
> +	WRITE_ONCE(state->valid, false);
> +
> +	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++) {
> +		ret = buddy_alloc_bulk(buddy, sizeof(*cache), 0,
> +				       (void __arena * __arena *)&state->percpu[cpu]);
> +		if (ret)
> +			return ret;
> +
> +		cache = state->percpu[cpu];
> +		for (order = zero; order < BUDDY_CACHE_NUM_ORDERS && can_loop; order++)
> +			WRITE_ONCE(cache->orders[order].elems, 0);
> +	}
> +
> +	WRITE_ONCE(state->valid, true);
> +
> +	return 0;
> +}
> +
> +static void buddy_cache_state_destroy(struct buddy __arena *buddy)
> +{
> +	struct buddy_cache_state __arena *state = &buddy->cache_state;
> +	unsigned int cpu;
> +
> +	WRITE_ONCE(state->valid, false);
> +	for (cpu = zero; cpu < CONFIG_NR_CPUS && can_loop; cpu++)
> +		WRITE_ONCE(state->percpu[cpu], NULL);
> +}

[Severity: Medium]
Can buddy_cache_state_destroy() overflow state->percpu[] when CONFIG_NR_CPUS
is greater than BUDDY_CACHE_MAX_CPUS (1024)?

While buddy_cache_state_init() checks if (CONFIG_NR_CPUS >
BUDDY_CACHE_MAX_CPUS) and returns -E2BIG, buddy_init() handles that failure
by calling buddy_destroy() -> buddy_cache_state_destroy():

buddy_init()
    ret = buddy_cache_state_init(buddy);
    if (ret) {
        buddy_destroy(buddy);
        return ret;
    }

In addition, arena_buddy_destroy() and arena_buddy_reset() in common.bpf.c
call buddy_destroy() directly before buddy_init(). Since
buddy_cache_state_destroy() loops up to CONFIG_NR_CPUS without bounding
against BUDDY_CACHE_MAX_CPUS, won't it write past the end of
state->percpu[BUDDY_CACHE_MAX_CPUS] and clobber adjacent arena memory on
kernels built with CONFIG_NR_CPUS > 1024?

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261020181900.6755-1-emil@etsalapatis.com?part=3