[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

[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

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

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

[Emil Tsalapatis]

On Mon Aug 10, 2026 at 9:47 AM EDT, chenyuan_fl wrote:
> 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>

Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>

> ---
>  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);

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

[Emil Tsalapatis]

On Mon Aug 10, 2026 at 9:47 AM EDT, chenyuan_fl wrote:
> 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>

Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>

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

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

[Emil Tsalapatis]

On Mon Aug 10, 2026 at 9:48 AM EDT, chenyuan_fl wrote:
> 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>

Reviewed-by: Emil Tsalapatis <emil@etsalapatis.com>

The fact we can fail to free a page because of an allocation failure is
...not great. Especially considering the failure is silent (we can't
turn this into a warning ofc bc it would be triggerable by user error).
Imo this is very close to a silent memory leak, but the only mitigation
I can think of is some kind of retry, and going down that route would get
really messy really fast.

> ---
>  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);
>