[PATCH bpf-next v3 0/3] bpf, arena: fix range_tree consistency on allocation failure

[PATCH bpf-next v3 0/3] bpf, arena: fix range_tree consistency on allocation failure

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

The arena range tree can be left inconsistent when kmalloc_nolock()
fails mid-operation. Patch 1 fixes range_tree_clear(), patch 2 fixes
range_tree_set(), patch 3 makes the arena free paths handle
range_tree_set() failures and checks the return value in
arena_alloc_pages()'"'"'s partial-allocation error path.

Changes in v3:
  - Check range_tree_set() return value in arena_alloc_pages()'"'"'s error
    path, which restores the unpopulated tail of a partially allocated
    range (previously ignored), as pointed out in review.

Changes in v2:
  - Fix multi-line comment style in patches 1 and 3 (opening /* on its
    own line), as pointed out in review.

Note: arena_vm_fault()'s two recovery paths (restoring the range to the
free tree after allocation/mapping failure) also call range_tree_set()
without checking the return value; that is addressed in a separate
series.

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      | 22 ++++++++++++---
 kernel/bpf/range_tree.c | 61 ++++++++++++++++++++++++++++++-----------
 2 files changed, 63 insertions(+), 20 deletions(-)

-- 
2.54.0

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

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

range_tree_clear() pre-allocates the right-half node before modifying
the tree, so an allocation failure returns -ENOMEM without altering the
range tree.

Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>
---
 kernel/bpf/range_tree.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index 2f28886f3ff7..15b588377a76 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -143,16 +143,22 @@ 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 v3 1/3] bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock failure

[sashiko-bot]

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

Pre-existing issues:
- [High] range_tree_set() modifies the interval tree before attempting a fallible allocation, leaving the tree in a corrupted state on OOM, similar to the bug fixed in range_tree_clear().
- [High] Transient NOWAIT allocation failure in range_tree_clear() causes arena_vm_fault() to trigger a fatal SIGSEGV.
--

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

bpf, arena: fix range_tree_clear inconsistency on kmalloc_nolock failure

range_tree_clear() pre-allocates the right-half node before modifying
the tree, so an allocation failure returns -ENOMEM without altering the
range tree.

> diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
> index 2f28886f3ff75..15b588377a769 100644
> --- a/kernel/bpf/range_tree.c
> +++ b/kernel/bpf/range_tree.c
> @@ -143,16 +143,22 @@ 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;

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

Looking at range_tree_set() in kernel/bpf/range_tree.c:

	range_tree_clear(rt, start, len);
	...
	left = kmalloc_nolock(sizeof(struct range_node),
			      __GFP_ACCOUNT, NUMA_NO_NODE);
	if (!left)
		return -ENOMEM;

It modifies the tree by calling range_tree_clear() first, and then can fail
its allocation. If arena_free_pages() calls range_tree_set() to return slots
and it fails here, the slots seem to be silently and permanently leaked since
the return value is ignored.

Could we apply this same pre-allocation pattern to range_tree_set() as well?

[Severity: High]
This is another pre-existing issue, but does returning -ENOMEM from here
cause unexpected crashes in user space?

Looking at arena_vm_fault() in kernel/bpf/arena.c:

	ret = range_tree_clear(&arena->rt, vmf->pgoff, 1);
	if (ret)
		goto out_sigsegv_memcg;

Since arena_vm_fault() handles page faults under a raw spinlock with IRQs
disabled, this kmalloc_nolock() acts as a GFP_NOWAIT allocation. If it fails
under memory pressure, it returns -ENOMEM, which arena_vm_fault() then
translates into VM_FAULT_SIGSEGV.

This causes the faulting user application to be randomly killed with a
segmentation fault rather than retrying or returning OOM.

Could this error handling be improved to avoid crashing the task?

[ ... ]

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

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

[chenyuan_fl]

From: Yuan Chen <chenyuan@kylinos.cn>

range_tree_set() pre-allocates the node needed for a brand-new range
before calling range_tree_clear(), so an allocation failure returns
-ENOMEM without having modified the tree (previously the overlapping
nodes were already removed by range_tree_clear() before the allocation
was attempted, permanently losing the cleared sub-ranges).

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 15b588377a76..54055b1fe541 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -199,6 +199,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;
@@ -208,20 +209,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 */
@@ -241,14 +262,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

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

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1668 bytes --]

> commit d5e05189cced9c98030a06e9001b3384079ee0ac
> Author: Yuan Chen <chenyuan@kylinos.cn>
> Date:   Mon Aug 10 21:47:59 2026 +0800
>
>     bpf, arena: fix range_tree_set inconsistency on kmalloc_nolock failure
>
>     range_tree_set() pre-allocates the node needed for a brand-new range
>     before calling range_tree_clear(), so an allocation failure returns
>     -ENOMEM without having modified the tree (previously the overlapping
>     nodes were already removed by range_tree_clear() before the allocation
>     was attempted, permanently losing the cleared sub-ranges).
>
>     Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>

This looks like a bug fix, should it include a Fixes tag?  The
allocate-after-clear ordering has been present since range_tree_set()
was introduced in b795379757eb ("bpf: Introduce range_tree data
structure and use it in bpf arena"), which already had:

kernel/bpf/range_tree.c:range_tree_set() {
    ...
    err = range_tree_clear(rt, start, len);
    if (err)
            return err;
    ...
    } else {
            left = bpf_mem_alloc(&bpf_global_ma, sizeof(struct range_node));
            if (!left)
                    return -ENOMEM;
    ...

so the tree was already mutated by the time the allocation failure was
returned.  A Fixes tag also matters here for backport scope, since the
allocator changed from bpf_mem_alloc() to kmalloc_nolock() partway
through the affected history.


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/31396076224

[PATCH bpf-next v3 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() now handle range_tree_set()
errors. arena_free_pages() aborts the free on error, and
arena_free_worker() moves range_tree_set() before PTE clearing so that a
failed tree update leaves the PTEs intact instead of freeing pages that
the arena free tree does not track.

Also check the range_tree_set() return value in arena_alloc_pages()'s
error path, which restores the unpopulated tail of a partially allocated
range; log a warning instead of silently leaking the virtual range when
the tree update fails.

Signed-off-by: Yuan Chen <chenyuan@kylinos.cn>
---
 kernel/bpf/arena.c | 22 ++++++++++++++++++----
 1 file changed, 18 insertions(+), 4 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 555ee2531ef9..d57a0b617525 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -766,7 +766,9 @@ static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt
 	bpf_map_memcg_exit(old_memcg, new_memcg);
 	return clear_lo32(arena->user_vm_start) + uaddr32;
 out:
-	range_tree_set(&arena->rt, pgoff + mapped, page_cnt - mapped);
+	if (range_tree_set(&arena->rt, pgoff + mapped, page_cnt - mapped))
+		pr_warn_ratelimited("bpf_arena: failed to restore free range %ld+%ld after partial alloc\n",
+				    pgoff + mapped, page_cnt - mapped);
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 	if (mapped) {
 		flush_vmap_cache(kern_vm_start + uaddr32, mapped << PAGE_SHIFT);
@@ -881,7 +883,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 +1011,18 @@ 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 v3 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 1 potential issue(s) to consider:
- [High] Physical memory leak in the BPF arena allocation rollback and deferred free paths when `range_tree_set()` fails.
--

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

bpf, arena: check range_tree_set return in arena_free_pages and arena_free_worker

This commit adds error checking for range_tree_set() in the BPF arena
allocation rollback and free paths. If the tree update fails, it aborts
the page free operation or skips clearing PTEs to prevent untracked pages.

> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> index 7b6847200b431..1e519c3c229ca 100644
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c

[ ... ]

> @@ -881,7 +883,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]
Does this early return cause a physical memory leak bounded by the lifetime
of the BPF map?

If arena_alloc_pages() fails midway due to memory limits, it attempts to
roll back the partially allocated physical pages by calling
arena_free_pages(). Under memory pressure, the range_tree_set() call is
highly likely to fail due to its internal kmalloc_nolock() allocation.

Aborting here leaves the physical pages mapped in the kernel VMA and
completely orphaned. Exchanging a virtual address space leak for a physical
memory leak on an error path under OOM conditions worsens memory pressure.

The pre-patch behavior of freeing pages and clearing PTEs appeared safe,
since bpf_arena_fault_handler() handles unmapped PTEs by mapping the
scratch_page.

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

[ ... ]

> @@ -1004,11 +1011,18 @@ 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;
> +

[Severity: High]
Can this continue statement permanently leak the physical pages from the
free system?

When this skips PTE clearing and page collection, the subsequent loop in
arena_free_worker():

arena_free_worker() {
    ...
    llist_for_each_safe(pos, t, list) {
        s = llist_entry(pos, struct arena_free_span, node);
        ...
        kfree_nolock(s);
    }
    ...
}

unconditionally destroys the tracking span 's'. This abandons the pages,
leaving them orphaned rather than avoiding an unrecoverable state.

>  		/* 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/20260810134800.2875487-1-chenyuan_fl@163.com?part=3