[PATCH bpf-next v1 0/3] bpf, arena: keep range tree consistent on kmalloc_nolock failure

[PATCH bpf-next v1 0/3] bpf, arena: keep range tree consistent on kmalloc_nolock failure

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

The arena range tree tracks free arena ranges.  range_tree_clear() and
range_tree_set() can fail when kmalloc_nolock() cannot allocate a node,
but both functions modified the tree before that allocation.  On
failure they returned -ENOMEM with part of the affected range already
removed from the tree, permanently losing those arena slots: they could
neither be allocated nor freed again.

Patch 1 pre-allocates the split node in range_tree_clear() so a failure
leaves the tree unmodified.  Patch 2 does the same for range_tree_set(),
allocating the new node only when the range has no adjacent free range
on either side.  Patch 3 makes arena_free_pages() and
arena_free_worker() check the range_tree_set() return value and skip
the free when the tree update fails, instead of unmapping and freeing
pages the tree still considers allocated.

The failure path requires kmalloc_nolock() to fail under memory
pressure, which is not feasible to trigger deterministically in a
selftest, so no regression test is included.

Yuan Chen (3):
  bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock
    failure
  bpf, arena: fix range_tree_set inconsistency on kmalloc_nolock failure
  bpf, arena: check range_tree_set return in arena_free_pages and
    arena_free_worker

 kernel/bpf/arena.c      | 17 +++++++++---
 kernel/bpf/range_tree.c | 60 ++++++++++++++++++++++++++++++-----------
 2 files changed, 58 insertions(+), 19 deletions(-)


base-commit: 11c1e836710dcba03e50454a4eedfdbaf8d3050e
-- 
2.54.0

[PATCH bpf-next v1 1/3] bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock failure

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

range_tree_clear() modifies the range tree before allocating the node
needed to split a range.  If the allocation fails, the function returns
-ENOMEM with part of the range already removed from the tree, leaving
those arena slots permanently unavailable.

Pre-allocate the node before modifying the tree so a failure leaves it
unmodified.

Fixes: b795379757eb ("bpf: Introduce range_tree data structure and use it in bpf arena")
Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>
---
 kernel/bpf/range_tree.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index 2f28886f3ff7..24fa32d4356b 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -143,16 +143,21 @@ int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
 		if (rn->rn_start < start && rn->rn_last > last) {
 			u32 old_last = rn->rn_last;
 
+			/* Pre-allocate the right-half node before modifying
+			 * the tree. If allocation fails we return -ENOMEM
+			 * without altering the range tree.
+			 */
+			new_rn = kmalloc_nolock(sizeof(struct range_node),
+						__GFP_ACCOUNT, NUMA_NO_NODE);
+			if (!new_rn)
+				return -ENOMEM;
+
 			/* Overlaps with the entire clearing range */
 			range_it_remove(rn, rt);
 			rn->rn_last = start - 1;
 			range_it_insert(rn, rt);
 
-			/* Add a range */
-			new_rn = kmalloc_nolock(sizeof(struct range_node), __GFP_ACCOUNT,
-						NUMA_NO_NODE);
-			if (!new_rn)
-				return -ENOMEM;
+			/* Add right-half range */
 			new_rn->rn_start = last + 1;
 			new_rn->rn_last = old_last;
 			range_it_insert(new_rn, rt);
-- 
2.54.0

Re: [PATCH bpf-next v1 1/3] bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock failure

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:

Pre-existing issues:
- [High] `range_tree_set()` suffers from the exact same partial-modification flaw that the patch fixes in `range_tree_clear()`, leading to permanent arena slot leaks.
--

--- Patch [1]: [PATCH bpf-next v1 1/3] bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock failure ---
commit 8092890527e00050d54d5c7b5deedf81e64396d7
Author: Yuan Chen <chenyuan@kylinos.cn>

bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock failure

This patch addresses an inconsistency in range_tree_clear() where memory
allocation failures could leave the range tree partially modified. It fixes
this by pre-allocating the required node before altering the tree structure.

> diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
> index 2f28886f3ff75..24fa32d4356bb 100644
> --- a/kernel/bpf/range_tree.c
> +++ b/kernel/bpf/range_tree.c
> @@ -143,16 +143,21 @@ int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
>  		if (rn->rn_start < start && rn->rn_last > last) {
>  			u32 old_last = rn->rn_last;
>  
> +			/* Pre-allocate the right-half node before modifying
> +			 * the tree. If allocation fails we return -ENOMEM
> +			 * without altering the range tree.
> +			 */
> +			new_rn = kmalloc_nolock(sizeof(struct range_node),
> +						__GFP_ACCOUNT, NUMA_NO_NODE);
> +			if (!new_rn)
> +				return -ENOMEM;
> +
>  			/* Overlaps with the entire clearing range */
>  			range_it_remove(rn, rt);

[Severity: High]
This isn't a bug introduced by this patch, but does range_tree_set()
suffer from the exact same partial-modification flaw?

Looking at range_tree_set() in kernel/bpf/range_tree.c, it also modifies the
tree before attempting an allocation:

	/* Clear out everything in the range we want to set. */
	err = range_tree_clear(rt, start, len);
	if (err)
		return err;
...
	} else {
		left = kmalloc_nolock(sizeof(struct range_node), __GFP_ACCOUNT, NUMA_NO_NODE);
		if (!left)
			return -ENOMEM;

If kmalloc_nolock() fails here, the function returns -ENOMEM but leaves the
tree with the overlapping nodes already deleted by range_tree_clear(). Any
previously free sub-ranges that were cleared could be permanently lost.

Furthermore, in kernel/bpf/arena.c, arena_free_pages() appears to ignore the
return value entirely:

	range_tree_set(&arena->rt, pgoff, page_cnt);

Could an allocation failure here result in a silent, permanent leak of arena
virtual address space?

[ ... ]

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260806030359.299480-1-chenyuan_fl@163.com?part=1

[PATCH bpf-next v1 2/3] bpf, arena: fix range_tree_set inconsistency on kmalloc_nolock failure

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

range_tree_set() clears overlapping ranges before allocating the node
for the new range.  If the allocation fails, the function returns
-ENOMEM with the cleared range already removed from the tree, leaving
those arena slots permanently unavailable.

Allocate only when the range has no adjacent free range on either side;
this is known before the clear, since any range covering start - 1 or
last + 1 survives it as an adjacent piece.  A failure therefore still
leaves the tree unmodified.

Fixes: b795379757eb ("bpf: Introduce range_tree data structure and use it in bpf arena")
Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>
---
 kernel/bpf/range_tree.c | 45 +++++++++++++++++++++++++++++++----------
 1 file changed, 34 insertions(+), 11 deletions(-)

diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index 24fa32d4356b..45560e9f0d07 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -198,6 +198,7 @@ int is_range_tree_set(struct range_tree *rt, u32 start, u32 len)
 int range_tree_set(struct range_tree *rt, u32 start, u32 len)
 {
 	u32 last = start + len - 1;
+	struct range_node *new_rn = NULL;
 	struct range_node *right;
 	struct range_node *left;
 	int err;
@@ -207,20 +208,40 @@ int range_tree_set(struct range_tree *rt, u32 start, u32 len)
 	if (left && left->rn_start <= start && left->rn_last >= last)
 		return 0;
 
+	/*
+	 * A new node is needed only when the range has no adjacent free
+	 * range on either side.  This is known before clearing: any range
+	 * covering start - 1 or last + 1 survives the clear as an adjacent
+	 * piece.  Allocate only in that case, before modifying the tree, so
+	 * a failure leaves the range tree unmodified
+	 */
+	left = range_it_iter_first(rt, start - 1, start - 1);
+	right = range_it_iter_first(rt, last + 1, last + 1);
+	if (!left && !right) {
+		new_rn = kmalloc_nolock(sizeof(struct range_node),
+					__GFP_ACCOUNT, NUMA_NO_NODE);
+		if (!new_rn)
+			return -ENOMEM;
+	}
+
 	/* Clear out everything in the range we want to set. */
 	err = range_tree_clear(rt, start, len);
 	if (err)
-		return err;
+		goto out_free_new;
 
 	/* Do we have a left-adjacent range ? */
 	left = range_it_iter_first(rt, start - 1, start - 1);
-	if (left && left->rn_last + 1 != start)
-		return -EFAULT;
+	if (left && left->rn_last + 1 != start) {
+		err = -EFAULT;
+		goto out_free_new;
+	}
 
 	/* Do we have a right-adjacent range ? */
 	right = range_it_iter_first(rt, last + 1, last + 1);
-	if (right && right->rn_start != last + 1)
-		return -EFAULT;
+	if (right && right->rn_start != last + 1) {
+		err = -EFAULT;
+		goto out_free_new;
+	}
 
 	if (left && right) {
 		/* Combine left and right adjacent ranges */
@@ -240,14 +261,16 @@ int range_tree_set(struct range_tree *rt, u32 start, u32 len)
 		right->rn_start = start;
 		range_it_insert(right, rt);
 	} else {
-		left = kmalloc_nolock(sizeof(struct range_node), __GFP_ACCOUNT, NUMA_NO_NODE);
-		if (!left)
-			return -ENOMEM;
-		left->rn_start = start;
-		left->rn_last = last;
-		range_it_insert(left, rt);
+		/* No adjacent ranges; use the pre-allocated node */
+		new_rn->rn_start = start;
+		new_rn->rn_last = last;
+		range_it_insert(new_rn, rt);
 	}
 	return 0;
+
+out_free_new:
+	kfree_nolock(new_rn);
+	return err;
 }
 
 void range_tree_destroy(struct range_tree *rt)
-- 
2.54.0

[PATCH bpf-next v1 3/3] bpf, arena: check range_tree_set return in arena_free_pages and arena_free_worker

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

arena_free_pages() and arena_free_worker() ignore range_tree_set()
errors and proceed to clear PTEs and free pages, even though the range
tree still considers the range allocated.  The range then becomes
permanently unavailable.

Check the return value: in arena_free_pages() abort the free on error;
in arena_free_worker() move range_tree_set() before PTE clearing and
skip the span on error.

Fixes: b795379757eb ("bpf: Introduce range_tree data structure and use it in bpf arena")
Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>
---
 kernel/bpf/arena.c | 17 ++++++++++++++---
 1 file changed, 14 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 555ee2531ef9..30745da9277b 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -881,7 +881,12 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 	if (ret)
 		goto defer;
 
-	range_tree_set(&arena->rt, pgoff, page_cnt);
+	ret = range_tree_set(&arena->rt, pgoff, page_cnt);
+	if (ret) {
+		raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+		bpf_map_memcg_exit(old_memcg, new_memcg);
+		return;
+	}
 
 	init_llist_head(&free_pages);
 	cdata.arena = arena;
@@ -1004,11 +1009,17 @@ static void arena_free_worker(struct work_struct *work)
 		kaddr = arena_vm_start + s->uaddr;
 		pgoff = compute_pgoff(arena, s->uaddr);
 
+		/* Mark the range as free before clearing PTEs so that
+		 * if the range tree update fails we leave the PTEs
+		 * intact, avoiding an unrecoverable state where pages
+		 * are freed but the arena free tree does not track them.
+		 */
+		if (range_tree_set(&arena->rt, pgoff, page_cnt))
+			continue;
+
 		/* clear ptes and collect pages in free_pages llist */
 		apply_to_existing_page_range(&init_mm, kaddr, page_cnt << PAGE_SHIFT,
 					     apply_range_clear_cb, &cdata);
-
-		range_tree_set(&arena->rt, pgoff, page_cnt);
 	}
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 
-- 
2.54.0

Re: [PATCH bpf-next v1 3/3] bpf, arena: check range_tree_set return in arena_free_pages and arena_free_worker

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:

New issues:
- [Low] The newly introduced multi-line comment in `arena_free_worker` does not follow the required BPF subsystem comment style (the opening `/*` is not on its own line).

Pre-existing issues:
- [High] TLB flush race in BPF arena free path allows BPF data corruption and leaking data to the page allocator.
--

--- Patch [3]: [PATCH bpf-next v1 3/3] bpf, arena: check range_tree_set return in arena_free_pages and arena_free_worker ---
commit e8687a8aed3ed0a8e5127b69fdd0e533b6129491
Author: Yuan Chen <chenyuan@kylinos.cn>

bpf, arena: check range_tree_set return in arena_free_pages and arena_free_worker

This commit updates arena_free_pages() and arena_free_worker() to handle
range_tree_set() errors. In arena_free_pages(), it aborts the free on
error, and in arena_free_worker(), it moves range_tree_set() before PTE
clearing.

> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> index 555ee2531ef98..30745da9277b0 100644
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c
> @@ -881,7 +881,12 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
>  	if (ret)
>  		goto defer;
>  
> -	range_tree_set(&arena->rt, pgoff, page_cnt);
> +	ret = range_tree_set(&arena->rt, pgoff, page_cnt);
> +	if (ret) {
> +		raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
> +		bpf_map_memcg_exit(old_memcg, new_memcg);
> +		return;
> +	}

[Severity: High]
This is a pre-existing issue, but does updating the free range tree under
arena->spinlock and then dropping the lock before flushing the TLB create a
race condition?

In both arena_free_pages() and arena_free_worker(), the spinlock is dropped
before flush_tlb_kernel_range() is called. 

If another thread concurrently allocates this same virtual address, maps new
physical pages into the PTE, and returns to the BPF program, could the new
program write to the old physical page due to stale TLB entries on that CPU?

When the first thread resumes, it would execute the TLB flush and free the
old physical page to the buddy allocator, which might cause data corruption
or leak data to the page allocator.

>  	init_llist_head(&free_pages);
>  	cdata.arena = arena;

[ ... ]

> @@ -1004,11 +1009,17 @@ static void arena_free_worker(struct work_struct *work)
>  		kaddr = arena_vm_start + s->uaddr;
>  		pgoff = compute_pgoff(arena, s->uaddr);
>  
> +		/* Mark the range as free before clearing PTEs so that
> +		 * if the range tree update fails we leave the PTEs
> +		 * intact, avoiding an unrecoverable state where pages
> +		 * are freed but the arena free tree does not track them.
> +		 */

[Severity: Low]
Does this multi-line comment follow the BPF subsystem style? 

The BPF subsystem guidelines require the opening /* to be on its own line:

/*
 * Mark the range as free before clearing PTEs so that
 ...

> +		if (range_tree_set(&arena->rt, pgoff, page_cnt))
> +			continue;
> +
>  		/* clear ptes and collect pages in free_pages llist */
>  		apply_to_existing_page_range(&init_mm, kaddr, page_cnt << PAGE_SHIFT,
>  					     apply_range_clear_cb, &cdata);
> -
> -		range_tree_set(&arena->rt, pgoff, page_cnt);
>  	}
>  	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
>

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260806030359.299480-1-chenyuan_fl@163.com?part=3