* [PATCH bpf-next v3 1/6] bpf: Update is_range_tree_set to work for consecutive ranges
2026-09-23 19:11 [PATCH bpf-next v3 0/6] bpf: Fix arena memory incoherence Emil Tsalapatis
@ 2026-09-23 19:11 ` Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 2/6] bpf: Track availability information for ranges in range tree Emil Tsalapatis
` (4 subsequent siblings)
5 siblings, 0 replies; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-23 19:11 UTC (permalink / raw)
To: bpf; +Cc: ast, andrii, eddyz87, memxor, daniel, Emil Tsalapatis
The arena range tree currently does not handle consecutive
ranges present in the tree. This is by design: Consecutive
ranges get merged into one by default. However, this design
only lets us track a single bit's worth of state for each
address range, encoded by whether the range is present in
the tree or not (i.e., is it allocated).
We require more fine-grained state tracking for each range.
This means possibly having in the tree consecutive ranges
that cannot be merged because they have different states.
However, existing code implicitly assumes that this scenario
is not possible in its logic.
Expand the logic of is_range_tree_set to handle consecutive
ranges in the tree. The logic change does not affect existing
users and amounts to a defensive check until we enable unmergeable
consecutive ranges in subsequent patches.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
kernel/bpf/range_tree.c | 20 +++++++++++++++-----
1 file changed, 15 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index 2f28886f3ff7..fdf7ba7aefe0 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -180,12 +180,22 @@ int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
int is_range_tree_set(struct range_tree *rt, u32 start, u32 len)
{
u32 last = start + len - 1;
- struct range_node *left;
+ struct range_node *rn;
- /* Is this whole range set ? */
- left = range_it_iter_first(rt, start, last);
- if (left && left->rn_start <= start && left->rn_last >= last)
- return 0;
+ for ((rn = range_it_iter_first(rt, start, last)); rn != NULL;
+ rn = __range_it_iter_next(rn, start, last)) {
+ /* Make sure the range covers the start */
+ if (rn->rn_start > start)
+ return -ESRCH;
+
+ /* If it covers the entire range we're done. */
+ if (rn->rn_last >= last)
+ return 0;
+
+ start = rn->rn_last + 1;
+ }
+
+ /* No range to cover [start, last] */
return -ESRCH;
}
--
2.52.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next v3 2/6] bpf: Track availability information for ranges in range tree
2026-09-23 19:11 [PATCH bpf-next v3 0/6] bpf: Fix arena memory incoherence Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 1/6] bpf: Update is_range_tree_set to work for consecutive ranges Emil Tsalapatis
@ 2026-09-23 19:11 ` Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 3/6] bpf: Fix arena race between page free and alloc leading to incoherency Emil Tsalapatis
` (3 subsequent siblings)
5 siblings, 0 replies; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-23 19:11 UTC (permalink / raw)
To: bpf; +Cc: ast, andrii, eddyz87, memxor, daniel, Emil Tsalapatis
Arena address ranges are currently encoded in a range tree: Ranges
present in the tree are free and available for allocation, while
absent ranges are allocated. However, this opens up the arena code to
subtle races between page table updates, range tree updates, and
concurrent allocations that can cause permanent inconsistencies.
Avoiding such races involves distinguishing between memory ranges that
are free and ready to be allocated, and ranges that are being freed but
should not be reused yet. Such tracking is cleanly possible through the
arena's range tree. The range tree is only consumed by arena and has no
additional future consumers, so it can be tailored towards tracking more
state. Alternatives such as deferring range freeing require more
asynchrony and per-range state tracking in the main arena code, and can
introduce additional race conditions.
Expand the tree to track whether a range present in the tree is
available for allocation. For now, all ranges are available: We add
the option to add back a range in an unavailable state, and to move
already present ranges from unavailable to available. We do not
implement other transitions, since they are not required to support
BPF arenas.
The patch adds two operations: Adding a range as unavailable, and
turning a range from unavailable to available. Unavailable ranges are
not mergable, and will be imminently be turned available by the ongoing
arena free() operation that created them. Turning ranges from
unavailable to available is a simple flag change on the range with an
optional merge with adjacent available ranges.
This diff adds -EAGAIN as a possible return value for range_tree_clear().
This is triggered by code in subsequent diffs, when there is an attempt
to use a range that has not been completely freed yet.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
kernel/bpf/arena.c | 10 +--
kernel/bpf/range_tree.c | 177 ++++++++++++++++++++++++++++++++++------
kernel/bpf/range_tree.h | 4 +-
3 files changed, 158 insertions(+), 33 deletions(-)
diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index c6369ea5e208..197ac3df68c7 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -317,7 +317,7 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
goto err_free_arena;
range_tree_init(&arena->rt);
- err = range_tree_set(&arena->rt, 0, attr->max_entries);
+ err = range_tree_set_avail(&arena->rt, 0, attr->max_entries);
if (err)
goto err_free_scratch;
mutex_init(&arena->lock);
@@ -561,7 +561,7 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
ret = apply_to_page_range(&init_mm, kaddr, PAGE_SIZE, apply_range_set_cb, &data);
if (ret) {
- range_tree_set(&arena->rt, vmf->pgoff, 1);
+ range_tree_set_avail(&arena->rt, vmf->pgoff, 1);
fault_ret = VM_FAULT_SIGBUS;
goto out_err_locked_memcg;
}
@@ -809,7 +809,7 @@ 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);
+ range_tree_set_avail(&arena->rt, 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);
@@ -924,7 +924,7 @@ 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);
+ range_tree_set_avail(&arena->rt, pgoff, page_cnt);
init_llist_head(&free_pages);
cdata.arena = arena;
@@ -1051,7 +1051,7 @@ static void arena_free_worker(struct work_struct *work)
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);
+ range_tree_set_avail(&arena->rt, pgoff, page_cnt);
}
raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index fdf7ba7aefe0..456db58650bd 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -39,8 +39,15 @@ struct range_node {
u32 rn_start;
u32 rn_last; /* inclusive */
u32 __rn_subtree_last;
+ bool available; /* range is available for allocating. */
};
+/* Is the range available for merging? */
+static inline bool range_available(struct range_node *rn)
+{
+ return rn && rn->available;
+}
+
static struct range_node *rb_to_range_node(struct rb_node *rb)
{
return rb_entry(rb, struct range_node, rb_range_size);
@@ -55,20 +62,30 @@ static u32 rn_size(struct range_node *rn)
static inline struct range_node *__find_range(struct range_tree *rt, u32 len)
{
struct rb_node *rb = rt->range_size_root.rb_root.rb_node;
- struct range_node *best = NULL;
+ struct rb_node *best = NULL;
+ struct range_node *rn;
while (rb) {
- struct range_node *rn = rb_to_range_node(rb);
+ rn = rb_to_range_node(rb);
if (len <= rn_size(rn)) {
- best = rn;
+ best = rb;
rb = rb->rb_right;
} else {
rb = rb->rb_left;
}
}
- return best;
+ /* Filter unavailable ranges. */
+ while (best) {
+ rn = rb_to_range_node(best);
+ if (range_available(rn))
+ return rn;
+
+ best = rb_prev(best);
+ }
+
+ return NULL;
}
s64 range_tree_find(struct range_tree *rt, u32 len)
@@ -135,10 +152,19 @@ range_it_iter_first(struct range_tree *rt, u32 start, u32 last)
/* Clear the range in this range tree */
int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
{
+ u32 first = start;
u32 last = start + len - 1;
struct range_node *new_rn;
struct range_node *rn;
+ /* Scan for unavailable ranges and try again if so. */
+ while ((rn = range_it_iter_first(rt, first, last))) {
+ if (!range_available(rn))
+ return -EAGAIN;
+
+ first = rn->rn_last + 1;
+ }
+
while ((rn = range_it_iter_first(rt, start, last))) {
if (rn->rn_start < start && rn->rn_last > last) {
u32 old_last = rn->rn_last;
@@ -153,6 +179,7 @@ int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
NUMA_NO_NODE);
if (!new_rn)
return -ENOMEM;
+ new_rn->available = rn->available;
new_rn->rn_start = last + 1;
new_rn->rn_last = old_last;
range_it_insert(new_rn, rt);
@@ -199,23 +226,12 @@ int is_range_tree_set(struct range_tree *rt, u32 start, u32 len)
return -ESRCH;
}
-/* Set the range in this range tree */
-int range_tree_set(struct range_tree *rt, u32 start, u32 len)
+/* Do we have adjacent ranges (and do not overlap with them)? */
+static int range_get_adjacent(struct range_tree *rt, u32 start, u32 last,
+ struct range_node **leftp, struct range_node **rightp)
{
- u32 last = start + len - 1;
struct range_node *right;
struct range_node *left;
- int err;
-
- /* Is this whole range already set ? */
- left = range_it_iter_first(rt, start, last);
- if (left && left->rn_start <= start && left->rn_last >= last)
- return 0;
-
- /* Clear out everything in the range we want to set. */
- err = range_tree_clear(rt, start, len);
- if (err)
- return err;
/* Do we have a left-adjacent range ? */
left = range_it_iter_first(rt, start - 1, start - 1);
@@ -227,34 +243,141 @@ int range_tree_set(struct range_tree *rt, u32 start, u32 len)
if (right && right->rn_start != last + 1)
return -EFAULT;
- if (left && right) {
+ *leftp = left;
+ *rightp = right;
+
+ return 0;
+}
+
+/*
+ * Merge with adjacent available ranges if possible. The new [start, last]
+ * has already been confirmed to be adjacent with left/right by the caller.
+ */
+static int range_tree_merge(struct range_tree *rt, u32 start, u32 last,
+ struct range_node *left, struct range_node *right)
+{
+ if (range_available(left) && range_available(right)) {
/* Combine left and right adjacent ranges */
range_it_remove(left, rt);
range_it_remove(right, rt);
left->rn_last = right->rn_last;
range_it_insert(left, rt);
kfree_nolock(right);
- } else if (left) {
+ } else if (range_available(left)) {
/* Combine with the left range */
range_it_remove(left, rt);
left->rn_last = last;
range_it_insert(left, rt);
- } else if (right) {
+ } else if (range_available(right)) {
/* Combine with the right range */
range_it_remove(right, rt);
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 merge available. */
+ return -ENOENT;
}
+
return 0;
}
+/* Make a range available, possibly merging. */
+int range_tree_make_avail(struct range_tree *rt, u32 start, u32 len)
+{
+ u32 last = start + len - 1;
+ struct range_node *rn;
+ struct range_node *right;
+ struct range_node *left;
+ int err;
+
+ /*
+ * Confirm the range exists is unavailable,
+ * and fits the requested range exactly.
+ */
+ rn = range_it_iter_first(rt, start, last);
+ if (!rn || rn->available)
+ return -EINVAL;
+
+ if (rn->rn_start != start || rn->rn_last != last)
+ return -EINVAL;
+
+ err = range_get_adjacent(rt, start, last, &left, &right);
+ if (err)
+ return err;
+
+ /* If no merging required, just make available. */
+ if (!range_available(left) && !range_available(right)) {
+ rn->available = true;
+ return 0;
+ }
+
+ /* Can merge, remove the range already. */
+ start = rn->rn_start;
+ last = rn->rn_last;
+ range_it_remove(rn, rt);
+ kfree_nolock(rn);
+
+ return range_tree_merge(rt, start, last, left, right);
+}
+
+/* Set the range in this range tree */
+static int range_tree_set(struct range_tree *rt, u32 start, u32 len, bool available)
+{
+ u32 last = start + len - 1;
+ struct range_node *right;
+ struct range_node *left;
+ int err;
+
+ /* Is this whole range already set ? */
+ left = range_it_iter_first(rt, start, last);
+ if (left && left->rn_start <= start && left->rn_last >= last &&
+ range_available(left) && available)
+ return 0;
+
+ /* Clear out everything in the range we want to set. */
+ err = range_tree_clear(rt, start, len);
+ if (err)
+ return err;
+
+ /* Get adjacent ranges and check for overlaps. */
+ err = range_get_adjacent(rt, start, last, &left, &right);
+ if (err)
+ return err;
+
+ /*
+ * If the range is not available for allocation, don't merge.
+ * Unavailable ranges are in the process of being freed and should
+ * be imminently marked available, so merging them with other
+ * unavailable ranges will just lead to splitting the range back
+ * almost immediately.
+ */
+ if (available) {
+ err = range_tree_merge(rt, start, last, left, right);
+ if (!err)
+ return 0;
+ }
+
+ left = kmalloc_nolock(sizeof(struct range_node), __GFP_ACCOUNT, NUMA_NO_NODE);
+ if (!left)
+ return -ENOMEM;
+ left->available = available;
+ left->rn_start = start;
+ left->rn_last = last;
+ range_it_insert(left, rt);
+
+ return 0;
+}
+
+int range_tree_set_avail(struct range_tree *rt, u32 start, u32 len)
+{
+ return range_tree_set(rt, start, len, true);
+}
+
+int range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len)
+{
+ return range_tree_set(rt, start, len, false);
+}
+
void range_tree_destroy(struct range_tree *rt)
{
struct range_node *rn;
diff --git a/kernel/bpf/range_tree.h b/kernel/bpf/range_tree.h
index ff0b9110eb71..aa27edf451bc 100644
--- a/kernel/bpf/range_tree.h
+++ b/kernel/bpf/range_tree.h
@@ -14,7 +14,9 @@ void range_tree_init(struct range_tree *rt);
void range_tree_destroy(struct range_tree *rt);
int range_tree_clear(struct range_tree *rt, u32 start, u32 len);
-int range_tree_set(struct range_tree *rt, u32 start, u32 len);
+int range_tree_set_avail(struct range_tree *rt, u32 start, u32 len);
+int range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len);
+int range_tree_make_avail(struct range_tree *rt, u32 start, u32 len);
int is_range_tree_set(struct range_tree *rt, u32 start, u32 len);
s64 range_tree_find(struct range_tree *rt, u32 len);
--
2.52.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next v3 3/6] bpf: Fix arena race between page free and alloc leading to incoherency
2026-09-23 19:11 [PATCH bpf-next v3 0/6] bpf: Fix arena memory incoherence Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 1/6] bpf: Update is_range_tree_set to work for consecutive ranges Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 2/6] bpf: Track availability information for ranges in range tree Emil Tsalapatis
@ 2026-09-23 19:11 ` Emil Tsalapatis
2026-09-23 22:42 ` Alexei Starovoitov
2026-09-23 19:11 ` [PATCH bpf-next v3 4/6] bpf: Add explicit state machine for arena free spans Emil Tsalapatis
` (2 subsequent siblings)
5 siblings, 1 reply; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-23 19:11 UTC (permalink / raw)
To: bpf; +Cc: ast, andrii, eddyz87, memxor, daniel, Emil Tsalapatis,
Mykola Lysenko
Existing arena kfunc code has an underlying race condition
that can lead to writes being lost from the BPF program's
point of view:
a) A memory range gets freed by operation (1), and its range
is added back to the arena range tree.
b) A concurrent allocation (2) reallocates the range, and does
writes to it. Writes from that CPU may follow the stale TLB
entries into the pages that are about to be freed.
c) (1) invalidates the TLB. The old pages, and any writes done
to them, are now inaccessible. zap_pages() similarly removes the
mappings for userspace threads.
This can be triggered by particularly demanding BPF arena data
structures that constantly allocate and deallocate memory, like
hash table allocations.
Solve this ABA problem by preventing range reallocation until
TLB invalidation/unmapping is complete. First, mark the range
freed but unavailable. Afterwards, drop the spinlock and
flush the kernel TLB and zap user page tables. Then pick up
the lock again and mark the ranges as available once again,
completing the free operation.
Reported-by: Mykola Lysenko <nickolay.lysenko@gmail.com>
Fixes: b8467290edab ("bpf: arena: make arena kfuncs any context safe")
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
kernel/bpf/arena.c | 156 ++++++++++++++++++++++++++++++++++++----
kernel/bpf/range_tree.c | 36 ++++++++--
kernel/bpf/range_tree.h | 5 +-
3 files changed, 176 insertions(+), 21 deletions(-)
diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 197ac3df68c7..9df4c74ff171 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -76,6 +76,7 @@ struct arena_free_span {
struct llist_node node;
unsigned long uaddr;
u32 page_cnt;
+ bool release_only;
};
u64 bpf_arena_get_kern_vm_start(struct bpf_arena *arena)
@@ -551,7 +552,11 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
}
ret = range_tree_clear(&arena->rt, vmf->pgoff, 1);
- if (ret) {
+ /* If a range is unavailable, try again. */
+ if (ret == -EAGAIN) {
+ raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+ goto retry;
+ } else if (ret) {
fault_ret = VM_FAULT_SIGBUS;
goto out_err_locked_memcg;
}
@@ -585,6 +590,19 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
if (new_page)
free_pages_nolock(new_page, 0);
return fault_ret;
+
+retry:
+ bpf_map_memcg_exit(old_memcg, new_memcg);
+ if (new_page)
+ free_pages_nolock(new_page, 0);
+
+ if (!(vmf->flags & FAULT_FLAG_ALLOW_RETRY))
+ return VM_FAULT_SIGBUS;
+
+ if (!(vmf->flags & FAULT_FLAG_RETRY_NOWAIT))
+ release_fault_lock(vmf);
+
+ return VM_FAULT_RETRY;
}
static const struct vm_operations_struct arena_vm_ops = {
@@ -890,6 +908,7 @@ static void zap_pages(struct bpf_arena *arena, long uaddr, long page_cnt)
static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt, bool sleepable)
{
struct mem_cgroup *new_memcg, *old_memcg;
+ struct range_node *unavail_node = NULL;
u64 full_uaddr, uaddr_end;
long kaddr, pgoff;
struct page *page;
@@ -898,6 +917,7 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
struct arena_free_span *s;
struct clear_range_data cdata;
unsigned long flags;
+ bool release_only = false;
int ret = 0;
/* only aligned lower 32-bit are relevant */
@@ -924,7 +944,20 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
if (ret)
goto defer;
- range_tree_set_avail(&arena->rt, pgoff, page_cnt);
+ unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
+ if (IS_ERR(unavail_node)) {
+ ret = PTR_ERR(unavail_node);
+ raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+ /*
+ * For -EAGAIN: An overlapping fault reserves
+ * the range before installing its PTE.
+ */
+ if (ret == -ENOMEM || ret == -EAGAIN)
+ goto defer;
+ WARN_ON_ONCE(ret);
+ bpf_map_memcg_exit(old_memcg, new_memcg);
+ return;
+ }
init_llist_head(&free_pages);
cdata.arena = arena;
@@ -954,6 +987,16 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
zap_pages(arena, full_uaddr, 1);
__free_page(page);
}
+
+ ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags);
+ if (ret) {
+ release_only = true;
+ goto defer;
+ }
+
+ ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
+ raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+ WARN_ON_ONCE(ret);
bpf_map_memcg_exit(old_memcg, new_memcg);
return;
@@ -961,16 +1004,33 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
defer:
s = kmalloc_nolock(sizeof(struct arena_free_span), __GFP_ACCOUNT, -1);
bpf_map_memcg_exit(old_memcg, new_memcg);
- if (!s)
+ if (!s) {
/*
- * If allocation fails in non-sleepable context, pages are intentionally left
- * inaccessible (leaked) until the arena is destroyed. Cleanup or retries are not
- * possible here, so we intentionally omit them for safety.
+ * Directly mark the region available. Unavailable regions must
+ * always be transient, and a permanent one breaks the assumptions
+ * made in the allocation/faulting code. The operation is safe because
+ * unavailable nodes are not modified by the range tree code without a reference
+ * to the node. The modification from unavailable to available also does
+ * not require touching anything in the tree apart from the node itself,
+ * so it can be done locklessly. The downside is fragmentation in the tree,
+ * since we cannot merge with neighbors, but this is a) safe and b) better
+ * than leaking the range.
*/
+ if (release_only)
+ range_node_mark_available(unavail_node);
+
+ /*
+ * If we haven't even zapped the pages, intentionally leave them
+ * inaccessible (leaked) until the arena is destroyed. Cleanup or
+ * retries are not possible here, so we intentionally omit them for safety.
+ */
+
return;
+ }
s->page_cnt = page_cnt;
s->uaddr = uaddr;
+ s->release_only = release_only;
llist_add(&s->node, &arena->free_spans);
irq_work_queue(&arena->free_irq);
}
@@ -1019,13 +1079,16 @@ static void arena_free_worker(struct work_struct *work)
struct mem_cgroup *new_memcg, *old_memcg;
struct llist_node *list, *pos, *t;
struct arena_free_span *s;
+ struct range_node *unavail_node;
u64 arena_vm_start, user_vm_start;
- struct llist_head free_pages;
+ struct llist_head free_pages, teardown_spans;
struct clear_range_data cdata;
struct page *page;
unsigned long full_uaddr;
long kaddr, page_cnt, pgoff;
unsigned long flags;
+ bool retry = false;
+ int ret;
if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
schedule_work(work);
@@ -1035,28 +1098,58 @@ static void arena_free_worker(struct work_struct *work)
bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
init_llist_head(&free_pages);
+ init_llist_head(&teardown_spans);
cdata.arena = arena;
cdata.free_pages = &free_pages;
arena_vm_start = bpf_arena_get_kern_vm_start(arena);
user_vm_start = bpf_arena_get_user_vm_start(arena);
list = llist_del_all(&arena->free_spans);
- llist_for_each(pos, list) {
+ llist_for_each_safe(pos, t, list) {
s = llist_entry(pos, struct arena_free_span, node);
page_cnt = s->page_cnt;
- kaddr = arena_vm_start + s->uaddr;
pgoff = compute_pgoff(arena, s->uaddr);
+ if (s->release_only) {
+ ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
+ WARN_ON_ONCE(ret);
+ kfree_nolock(s);
+ continue;
+ }
+
+ kaddr = arena_vm_start + s->uaddr;
+
+ unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
+ if (IS_ERR(unavail_node)) {
+ ret = PTR_ERR(unavail_node);
+ /* Kick off another attempt at the end of this call. */
+ if (ret == -EAGAIN) {
+ llist_add(pos, &arena->free_spans);
+ retry = true;
+ continue;
+ }
+
+ /*
+ * An -ENOMEM failure is the same failure mode as in
+ * the defer: path of arena_free_pages(). Do not treat
+ * the leak as a bug.
+ */
+ if (ret != -ENOMEM)
+ WARN_ON_ONCE(ret);
+
+ kfree_nolock(s);
+ 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_avail(&arena->rt, pgoff, page_cnt);
+ __llist_add(pos, &teardown_spans);
}
raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
- /* Iterate the list again without holding spinlock to do the tlb flush and zap_pages */
- llist_for_each_safe(pos, t, list) {
+ /* Keep ranges unavailable until their stale translations are gone. */
+ llist_for_each_safe(pos, t, READ_ONCE(teardown_spans.first)) {
s = llist_entry(pos, struct arena_free_span, node);
page_cnt = s->page_cnt;
full_uaddr = clear_lo32(user_vm_start) + s->uaddr;
@@ -1067,8 +1160,6 @@ static void arena_free_worker(struct work_struct *work)
/* remove pages from user vmas */
zap_pages(arena, full_uaddr, page_cnt);
-
- kfree_nolock(s);
}
/* free all pages collected by apply_to_existing_page_range() in the first loop */
@@ -1077,7 +1168,42 @@ static void arena_free_worker(struct work_struct *work)
__free_page(page);
}
+ if (!llist_empty(&teardown_spans)) {
+ if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
+ llist_for_each_safe(pos, t, __llist_del_all(&teardown_spans)) {
+ s = llist_entry(pos, struct arena_free_span, node);
+ s->release_only = true;
+ llist_add(pos, &arena->free_spans);
+ }
+
+ schedule_work(work);
+ bpf_map_memcg_exit(old_memcg, new_memcg);
+ return;
+ }
+
+ llist_for_each_safe(pos, t, __llist_del_all(&teardown_spans)) {
+ s = llist_entry(pos, struct arena_free_span, node);
+ page_cnt = s->page_cnt;
+ pgoff = compute_pgoff(arena, s->uaddr);
+ /*
+ * This range tree operation does not allocate memory,
+ * and so should never fail regardless of contention
+ * or memory pressure. This is in contrast to regular
+ * inserts that _can_ fail under memory pressure and
+ * force us to defer the free.
+ */
+ ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
+ WARN_ON_ONCE(ret);
+ kfree_nolock(s);
+ }
+ raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+ }
+
bpf_map_memcg_exit(old_memcg, new_memcg);
+
+ /* Retry if any region was unavailable for free. */
+ if (retry)
+ schedule_work(work);
}
static void arena_free_irq(struct irq_work *iw)
diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index 456db58650bd..9472cf1bc26d 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -3,6 +3,7 @@
#include <linux/interval_tree_generic.h>
#include <linux/slab.h>
#include <linux/bpf.h>
+#include <linux/err.h>
#include "range_tree.h"
/*
@@ -45,7 +46,21 @@ struct range_node {
/* Is the range available for merging? */
static inline bool range_available(struct range_node *rn)
{
- return rn && rn->available;
+ /* Pairs with smp_store_release() in range_node_mark_available(). */
+ return rn && smp_load_acquire(&rn->available);
+}
+
+/*
+ * Mark a node as available. Designed to be used locklessly
+ * as a last-ditch effort to avoid leaking unavailable range
+ * tree nodes when all attempts to directly or indirectly
+ * free an arena region has failed. See arena_free_pages()
+ * for more info.
+ */
+void range_node_mark_available(struct range_node *rn)
+{
+ /* Pairs with smp_load_acquire() in range_available(). */
+ smp_store_release(&rn->available, true);
}
static struct range_node *rb_to_range_node(struct rb_node *rb)
@@ -321,7 +336,8 @@ int range_tree_make_avail(struct range_tree *rt, u32 start, u32 len)
}
/* Set the range in this range tree */
-static int range_tree_set(struct range_tree *rt, u32 start, u32 len, bool available)
+static int range_tree_set(struct range_tree *rt, u32 start, u32 len, bool available,
+ struct range_node **new_rn)
{
u32 last = start + len - 1;
struct range_node *right;
@@ -364,18 +380,28 @@ static int range_tree_set(struct range_tree *rt, u32 start, u32 len, bool availa
left->rn_start = start;
left->rn_last = last;
range_it_insert(left, rt);
+ if (new_rn)
+ *new_rn = left;
return 0;
}
int range_tree_set_avail(struct range_tree *rt, u32 start, u32 len)
{
- return range_tree_set(rt, start, len, true);
+ return range_tree_set(rt, start, len, true, NULL);
}
-int range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len)
+struct range_node *range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len)
{
- return range_tree_set(rt, start, len, false);
+ struct range_node *rn = NULL;
+ int err;
+
+ err = range_tree_set(rt, start, len, false, &rn);
+ if (err)
+ return ERR_PTR(err);
+ if (WARN_ON_ONCE(!rn))
+ return ERR_PTR(-EINVAL);
+ return rn;
}
void range_tree_destroy(struct range_tree *rt)
diff --git a/kernel/bpf/range_tree.h b/kernel/bpf/range_tree.h
index aa27edf451bc..4f9ea2acea29 100644
--- a/kernel/bpf/range_tree.h
+++ b/kernel/bpf/range_tree.h
@@ -10,12 +10,15 @@ struct range_tree {
struct rb_root_cached range_size_root;
};
+struct range_node;
+
void range_tree_init(struct range_tree *rt);
void range_tree_destroy(struct range_tree *rt);
int range_tree_clear(struct range_tree *rt, u32 start, u32 len);
int range_tree_set_avail(struct range_tree *rt, u32 start, u32 len);
-int range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len);
+struct range_node *range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len);
+void range_node_mark_available(struct range_node *rn);
int range_tree_make_avail(struct range_tree *rt, u32 start, u32 len);
int is_range_tree_set(struct range_tree *rt, u32 start, u32 len);
s64 range_tree_find(struct range_tree *rt, u32 len);
--
2.52.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next v3 3/6] bpf: Fix arena race between page free and alloc leading to incoherency
2026-09-23 19:11 ` [PATCH bpf-next v3 3/6] bpf: Fix arena race between page free and alloc leading to incoherency Emil Tsalapatis
@ 2026-09-23 22:42 ` Alexei Starovoitov
2026-09-24 19:08 ` Emil Tsalapatis
0 siblings, 1 reply; 13+ messages in thread
From: Alexei Starovoitov @ 2026-09-23 22:42 UTC (permalink / raw)
To: Emil Tsalapatis, bpf; +Cc: andrii, eddyz87, memxor, daniel, Mykola Lysenko
On Wed, Sep 23, 2026 at 07:11 PM Emil Tsalapatis <emil@etsalapatis.com> wrote:
> Solve this ABA problem by preventing range reallocation until
> TLB invalidation/unmapping is complete. First, mark the range
> freed but unavailable. Afterwards, drop the spinlock and
> flush the kernel TLB and zap user page tables. Then pick up
> the lock again and mark the ranges as available once again,
> completing the free operation.
The range is allocated in the range tree before the free.
can we keep it allocated until flush_tlb_kernel_range() and
zap_pages() are done and call range_tree_set() only after that ?
bpf_arena_reserve_pages() creates the same 'allocated without pages'
state. arena_vm_fault() shouldn't populate such range, I think.
Then there is no need for the 3rd state in the range tree.
[...]
> + unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
> + if (IS_ERR(unavail_node)) {
> + ret = PTR_ERR(unavail_node);
> + /* Kick off another attempt at the end of this call. */
> + if (ret == -EAGAIN) {
> + llist_add(pos, &arena->free_spans);
> + retry = true;
> + continue;
> + }
> +
> + /*
> + * An -ENOMEM failure is the same failure mode as in
> + * the defer: path of arena_free_pages(). Do not treat
> + * the leak as a bug.
> + */
> + if (ret != -ENOMEM)
> + WARN_ON_ONCE(ret);
> +
> + kfree_nolock(s);
> + continue;
> + }
This makes it worse.
Unavailable ranges don't merge, so range_tree_set_unavail() always
allocates a node. When kmalloc_nolock() fails the span is dropped
before the ptes are cleared and the pages stay mapped until map free.
Today the worker unmaps and frees the pages and range_tree_set()
failure costs only the address range.
pw-bot: cr
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next v3 3/6] bpf: Fix arena race between page free and alloc leading to incoherency
2026-09-23 22:42 ` Alexei Starovoitov
@ 2026-09-24 19:08 ` Emil Tsalapatis
0 siblings, 0 replies; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-24 19:08 UTC (permalink / raw)
To: Alexei Starovoitov; +Cc: bpf, andrii, eddyz87, memxor, daniel, Mykola Lysenko
On Wed, Sep 23, 2026 at 10:42 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Wed, Sep 23, 2026 at 07:11 PM Emil Tsalapatis <emil@etsalapatis.com> wrote:
> > Solve this ABA problem by preventing range reallocation until
> > TLB invalidation/unmapping is complete. First, mark the range
> > freed but unavailable. Afterwards, drop the spinlock and
> > flush the kernel TLB and zap user page tables. Then pick up
> > the lock again and mark the ranges as available once again,
> > completing the free operation.
>
> The range is allocated in the range tree before the free.
> can we keep it allocated until flush_tlb_kernel_range() and
> zap_pages() are done and call range_tree_set() only after that ?
> bpf_arena_reserve_pages() creates the same 'allocated without pages'
> state. arena_vm_fault() shouldn't populate such range, I think.
> Then there is no need for the 3rd state in the range tree.
>
arena_vm_fault does populate reserved ranges, we designed the reserve
to just touch the range tree without preventing the range from being populated.
If we did prevent arena_vm_fault() from doing so, afaict we'd need a marker very
similar to the 3rd state we're introducing in this patch.
More generally, a lot of the complexity stems exactly from the fact we
are allowing
the page-fault based and kfunc-based population of arenas, even though
doing both
at the same time would be weird. If we disabled bpf_arena_alloc/free_pages() on
arenas without BPF_F_SEGV_ON_FAULT we could treat each API separately and avoid
half these races. Right now we're doing the equivalent of populating a
file with mmap()
and read()/write() at the same time.
> [...]
> > + unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
> > + if (IS_ERR(unavail_node)) {
> > + ret = PTR_ERR(unavail_node);
> > + /* Kick off another attempt at the end of this call. */
> > + if (ret == -EAGAIN) {
> > + llist_add(pos, &arena->free_spans);
> > + retry = true;
> > + continue;
> > + }
> > +
> > + /*
> > + * An -ENOMEM failure is the same failure mode as in
> > + * the defer: path of arena_free_pages(). Do not treat
> > + * the leak as a bug.
> > + */
> > + if (ret != -ENOMEM)
> > + WARN_ON_ONCE(ret);
> > +
> > + kfree_nolock(s);
> > + continue;
> > + }
>
> This makes it worse.
> Unavailable ranges don't merge, so range_tree_set_unavail() always
> allocates a node. When kmalloc_nolock() fails the span is dropped
> before the ptes are cleared and the pages stay mapped until map free.
> Today the worker unmaps and frees the pages and range_tree_set()
> failure costs only the address range.
>
The kfree_nolock(s) path is only if we fail to somehow grab the range we are
freeing from the range tree. We can still go ahead with apply_range_clear_cb,
but it is not clear at that point what we are unmapping because this case
should not happen during regular execution (unlike -EAGAIN and -ENOMEM).
> pw-bot: cr
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH bpf-next v3 4/6] bpf: Add explicit state machine for arena free spans
2026-09-23 19:11 [PATCH bpf-next v3 0/6] bpf: Fix arena memory incoherence Emil Tsalapatis
` (2 preceding siblings ...)
2026-09-23 19:11 ` [PATCH bpf-next v3 3/6] bpf: Fix arena race between page free and alloc leading to incoherency Emil Tsalapatis
@ 2026-09-23 19:11 ` Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler Emil Tsalapatis
2026-09-23 19:11 ` [PATCH bpf-next v3 6/6] selftests/bpf: Add arena allocation race tests Emil Tsalapatis
5 siblings, 0 replies; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-23 19:11 UTC (permalink / raw)
To: bpf; +Cc: ast, andrii, eddyz87, memxor, daniel, Emil Tsalapatis,
Puranjay Mohan
The arena_free_worker() call currently tracks the status
of each arena_free_span by placing it into a separate
list. This requires multiple list manipulation calls
during the freeing operation, complicating the code for
no reason.
Add an explicit state machine for span state. This
avoids encoding the states within temporary list membership,
and also allows for safely reschedulign freeing work for each
span separately.
Suggested-by: Puranjay Mohan <puranjay@kernel.org>
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
kernel/bpf/arena.c | 108 +++++++++++++++++++++++++++------------------
1 file changed, 65 insertions(+), 43 deletions(-)
diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 9df4c74ff171..69c8924f4c30 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -72,11 +72,18 @@ struct bpf_arena {
static void arena_free_worker(struct work_struct *work);
static void arena_free_irq(struct irq_work *iw);
+enum arena_free_span_state {
+ ARENA_FREE_SPAN_NOT_STARTED, /* Freeing not started */
+ ARENA_FREE_SPAN_UNAVAIL, /* Region cleared & unavailable */
+ ARENA_FREE_SPAN_ZAPPED, /* Region zapped and cleared */
+ ARENA_FREE_SPAN_FAILED, /* Freeing operation cannot continue */
+};
+
struct arena_free_span {
struct llist_node node;
unsigned long uaddr;
u32 page_cnt;
- bool release_only;
+ enum arena_free_span_state state;
};
u64 bpf_arena_get_kern_vm_start(struct bpf_arena *arena)
@@ -1030,7 +1037,7 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
s->page_cnt = page_cnt;
s->uaddr = uaddr;
- s->release_only = release_only;
+ s->state = release_only ? ARENA_FREE_SPAN_ZAPPED : ARENA_FREE_SPAN_NOT_STARTED;
llist_add(&s->node, &arena->free_spans);
irq_work_queue(&arena->free_irq);
}
@@ -1081,7 +1088,7 @@ static void arena_free_worker(struct work_struct *work)
struct arena_free_span *s;
struct range_node *unavail_node;
u64 arena_vm_start, user_vm_start;
- struct llist_head free_pages, teardown_spans;
+ struct llist_head free_pages;
struct clear_range_data cdata;
struct page *page;
unsigned long full_uaddr;
@@ -1098,7 +1105,6 @@ static void arena_free_worker(struct work_struct *work)
bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
init_llist_head(&free_pages);
- init_llist_head(&teardown_spans);
cdata.arena = arena;
cdata.free_pages = &free_pages;
arena_vm_start = bpf_arena_get_kern_vm_start(arena);
@@ -1107,27 +1113,19 @@ static void arena_free_worker(struct work_struct *work)
list = llist_del_all(&arena->free_spans);
llist_for_each_safe(pos, t, list) {
s = llist_entry(pos, struct arena_free_span, node);
- page_cnt = s->page_cnt;
- pgoff = compute_pgoff(arena, s->uaddr);
-
- if (s->release_only) {
- ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
- WARN_ON_ONCE(ret);
- kfree_nolock(s);
+ if (s->state != ARENA_FREE_SPAN_NOT_STARTED)
continue;
- }
+ page_cnt = s->page_cnt;
+ pgoff = compute_pgoff(arena, s->uaddr);
kaddr = arena_vm_start + s->uaddr;
unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
if (IS_ERR(unavail_node)) {
ret = PTR_ERR(unavail_node);
/* Kick off another attempt at the end of this call. */
- if (ret == -EAGAIN) {
- llist_add(pos, &arena->free_spans);
- retry = true;
+ if (ret == -EAGAIN)
continue;
- }
/*
* An -ENOMEM failure is the same failure mode as in
@@ -1137,20 +1135,24 @@ static void arena_free_worker(struct work_struct *work)
if (ret != -ENOMEM)
WARN_ON_ONCE(ret);
- kfree_nolock(s);
+ s->state = ARENA_FREE_SPAN_FAILED;
continue;
}
+ s->state = ARENA_FREE_SPAN_UNAVAIL;
+
/* 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);
- __llist_add(pos, &teardown_spans);
}
raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
/* Keep ranges unavailable until their stale translations are gone. */
- llist_for_each_safe(pos, t, READ_ONCE(teardown_spans.first)) {
+ llist_for_each_safe(pos, t, list) {
s = llist_entry(pos, struct arena_free_span, node);
+ if (s->state != ARENA_FREE_SPAN_UNAVAIL)
+ continue;
+
page_cnt = s->page_cnt;
full_uaddr = clear_lo32(user_vm_start) + s->uaddr;
kaddr = arena_vm_start + s->uaddr;
@@ -1160,6 +1162,12 @@ static void arena_free_worker(struct work_struct *work)
/* remove pages from user vmas */
zap_pages(arena, full_uaddr, page_cnt);
+
+ /*
+ * Used to avoid zapping twice if we fail the lock acquisition
+ * below and rerun the span through this function.
+ */
+ s->state = ARENA_FREE_SPAN_ZAPPED;
}
/* free all pages collected by apply_to_existing_page_range() in the first loop */
@@ -1168,40 +1176,54 @@ static void arena_free_worker(struct work_struct *work)
__free_page(page);
}
- if (!llist_empty(&teardown_spans)) {
- if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
- llist_for_each_safe(pos, t, __llist_del_all(&teardown_spans)) {
- s = llist_entry(pos, struct arena_free_span, node);
- s->release_only = true;
- llist_add(pos, &arena->free_spans);
+ if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
+ llist_for_each_safe(pos, t, list) {
+ s = llist_entry(pos, struct arena_free_span, node);
+
+ if (s->state == ARENA_FREE_SPAN_FAILED) {
+ kfree_nolock(s);
+ continue;
}
- schedule_work(work);
- bpf_map_memcg_exit(old_memcg, new_memcg);
- return;
+ llist_add(pos, &arena->free_spans);
+ retry = true;
}
+ goto done;
+ }
- llist_for_each_safe(pos, t, __llist_del_all(&teardown_spans)) {
- s = llist_entry(pos, struct arena_free_span, node);
- page_cnt = s->page_cnt;
- pgoff = compute_pgoff(arena, s->uaddr);
- /*
- * This range tree operation does not allocate memory,
- * and so should never fail regardless of contention
- * or memory pressure. This is in contrast to regular
- * inserts that _can_ fail under memory pressure and
- * force us to defer the free.
- */
- ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
- WARN_ON_ONCE(ret);
+ llist_for_each_safe(pos, t, list) {
+ s = llist_entry(pos, struct arena_free_span, node);
+
+ /* Remove the spans of failed allocations. */
+ if (s->state == ARENA_FREE_SPAN_FAILED) {
kfree_nolock(s);
+ continue;
}
- raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+
+ if (s->state == ARENA_FREE_SPAN_NOT_STARTED) {
+ llist_add(pos, &arena->free_spans);
+ retry = true;
+ continue;
+ }
+
+ page_cnt = s->page_cnt;
+ pgoff = compute_pgoff(arena, s->uaddr);
+ /*
+ * This range tree operation does not allocate memory,
+ * and so should never fail regardless of contention
+ * or memory pressure. This is in contrast to regular
+ * inserts that _can_ fail under memory pressure and
+ * force us to defer the free.
+ */
+ ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
+ WARN_ON_ONCE(ret);
+ kfree_nolock(s);
}
+ raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+done:
bpf_map_memcg_exit(old_memcg, new_memcg);
- /* Retry if any region was unavailable for free. */
if (retry)
schedule_work(work);
}
--
2.52.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler
2026-09-23 19:11 [PATCH bpf-next v3 0/6] bpf: Fix arena memory incoherence Emil Tsalapatis
` (3 preceding siblings ...)
2026-09-23 19:11 ` [PATCH bpf-next v3 4/6] bpf: Add explicit state machine for arena free spans Emil Tsalapatis
@ 2026-09-23 19:11 ` Emil Tsalapatis
2026-09-23 19:28 ` sashiko-bot
` (2 more replies)
2026-09-23 19:11 ` [PATCH bpf-next v3 6/6] selftests/bpf: Add arena allocation race tests Emil Tsalapatis
5 siblings, 3 replies; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-23 19:11 UTC (permalink / raw)
To: bpf; +Cc: ast, andrii, eddyz87, memxor, daniel, Emil Tsalapatis
The arena allocation code currently has a race in the fault handler
that can cause userspace threads to write to the wrong arena page.
a) The fault handler removes a range from the range tree to mark the
addresses as allocated, then installs a page A into the kernel page
tables.
b) A concurrent free/reallocation removes A and installs a page B.
c) The fault handler still goes ahead with installing page A in the
page table. The kernel sees page B, while userspace sees page A.
There is no way to protect the PTE installation and the range tree
modification simultaneously, because we cannot nest the synchronization
primitives for their respective critical sections. PTE allocation
may require allocations due to PTE reclamation, and its spinlock
becomes sleepable under PREEMPT_RT. Thus we cannot do this operation
while holding the range tree spinlock. There is no public API for
manually taking this spinlock, so we nest the range tree operation
inside it.
Solve this issue by adjusting the range tree in two steps. First,
mark the address of the page being allocated as unavailable. Then
drop the range spinlock, insert the PTE, take the range spinlock
again, and fully remove it from the range tree. Concurrent free
operations get serialized to before the fault handler, while
it is not possible to allocate the page once it has been reserved.
Concurrent page fault handler calls retry until the page is fully
allocated by the original call.
Also return VM_FAULT_RETRY for transient allocation failures. These
are a) faulting on pages that are temporarily marked unavailable in
the range tree and b) rqspinlock acquisition failures.
Fixes: 317460317a02 ("bpf: Introduce bpf_arena.")
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
kernel/bpf/arena.c | 66 ++++++++++++++++++++++++++++++-----------
kernel/bpf/range_tree.c | 14 +++++++++
kernel/bpf/range_tree.h | 1 +
3 files changed, 64 insertions(+), 17 deletions(-)
diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 69c8924f4c30..5438b68d269a 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -489,8 +489,9 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
struct bpf_map *map = vmf->vma->vm_file->private_data;
struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
struct mem_cgroup *new_memcg, *old_memcg;
- struct page *page, *new_page = NULL;
vm_fault_t fault_ret;
+ struct range_node *unavail_node;
+ struct page *page, *new_page = NULL;
long kbase, kaddr;
unsigned long flags;
int ret;
@@ -512,15 +513,17 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
bpf_map_memcg_exit(old_memcg, new_memcg);
}
- if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
- /*
- * A failed lock means a possible deadlock was detected. Don't
- * return VM_FAULT_RETRY: this handler never took mmap_lock, but
- * the fault path would re-take it on retry and deadlock. Fail.
- */
- if (new_page)
- free_pages_nolock(new_page, 0);
- return VM_FAULT_SIGBUS;
+ ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags);
+ if (ret) {
+ /* If we are deadlocking somehow, no way to ensure forward progress. */
+ if (ret == -EDEADLK) {
+ if (new_page)
+ free_pages_nolock(new_page, 0);
+ return VM_FAULT_SIGBUS;
+ }
+
+ if (ret)
+ goto retry;
}
page = vmalloc_to_page((void *)kaddr);
@@ -562,7 +565,7 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
/* If a range is unavailable, try again. */
if (ret == -EAGAIN) {
raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
- goto retry;
+ goto retry_memcg;
} else if (ret) {
fault_ret = VM_FAULT_SIGBUS;
goto out_err_locked_memcg;
@@ -583,12 +586,40 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
page = new_page;
new_page = NULL;
out:
- page_ref_add(page, 1);
+ /* Reserve the page while installing its user PTE without the arena lock. */
+ bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
+ unavail_node = range_tree_set_unavail(&arena->rt, vmf->pgoff, 1);
+ bpf_map_memcg_exit(old_memcg, new_memcg);
raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
- if (new_page)
+
+ if (new_page) {
free_pages_nolock(new_page, 0);
- vmf->page = page;
- return 0;
+ new_page = NULL;
+ }
+
+ /* If we couldn't mark the page unavailable, retry. */
+ if (IS_ERR(unavail_node)) {
+ ret = PTR_ERR(unavail_node);
+ if (ret == -EAGAIN)
+ goto retry;
+ return VM_FAULT_SIGBUS;
+ }
+
+ fault_ret = vmf_insert_page(vmf->vma, vmf->address, page);
+ while ((ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags))) {
+ /* If we somehow deadlocked stop trying to take the lock. */
+ if (ret == -EDEADLK) {
+ range_node_mark_available(unavail_node);
+ return VM_FAULT_SIGBUS;
+ }
+
+ cond_resched();
+ }
+
+ ret = range_tree_remove_unavail(&arena->rt, vmf->pgoff, 1);
+ raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+ WARN_ON_ONCE(ret);
+ return fault_ret;
out_err_locked_memcg:
bpf_map_memcg_exit(old_memcg, new_memcg);
@@ -598,8 +629,9 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
free_pages_nolock(new_page, 0);
return fault_ret;
-retry:
+retry_memcg:
bpf_map_memcg_exit(old_memcg, new_memcg);
+retry:
if (new_page)
free_pages_nolock(new_page, 0);
@@ -689,7 +721,7 @@ static int arena_map_mmap(struct bpf_map *map, struct vm_area_struct *vma)
* of user_vm_start. Set VM_DONTCOPY to prevent arena VMA from
* being copied into the child process on fork.
*/
- vm_flags_set(vma, VM_DONTEXPAND | VM_DONTCOPY);
+ vm_flags_set(vma, VM_DONTEXPAND | VM_DONTCOPY | VM_MIXEDMAP);
vma->vm_ops = &arena_vm_ops;
return 0;
}
diff --git a/kernel/bpf/range_tree.c b/kernel/bpf/range_tree.c
index 9472cf1bc26d..62ebf4df51cb 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -404,6 +404,20 @@ struct range_node *range_tree_set_unavail(struct range_tree *rt, u32 start, u32
return rn;
}
+int range_tree_remove_unavail(struct range_tree *rt, u32 start, u32 len)
+{
+ u32 last = start + len - 1;
+ struct range_node *rn;
+
+ rn = range_it_iter_first(rt, start, last);
+ if (!rn || rn->available || rn->rn_start != start || rn->rn_last != last)
+ return -EINVAL;
+
+ range_it_remove(rn, rt);
+ kfree_nolock(rn);
+ return 0;
+}
+
void range_tree_destroy(struct range_tree *rt)
{
struct range_node *rn;
diff --git a/kernel/bpf/range_tree.h b/kernel/bpf/range_tree.h
index 4f9ea2acea29..79295abe3684 100644
--- a/kernel/bpf/range_tree.h
+++ b/kernel/bpf/range_tree.h
@@ -19,6 +19,7 @@ int range_tree_clear(struct range_tree *rt, u32 start, u32 len);
int range_tree_set_avail(struct range_tree *rt, u32 start, u32 len);
struct range_node *range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len);
void range_node_mark_available(struct range_node *rn);
+int range_tree_remove_unavail(struct range_tree *rt, u32 start, u32 len);
int range_tree_make_avail(struct range_tree *rt, u32 start, u32 len);
int is_range_tree_set(struct range_tree *rt, u32 start, u32 len);
s64 range_tree_find(struct range_tree *rt, u32 len);
--
2.52.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler
2026-09-23 19:11 ` [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler Emil Tsalapatis
@ 2026-09-23 19:28 ` sashiko-bot
2026-09-23 20:11 ` bot+bpf-ci
2026-09-23 22:42 ` Alexei Starovoitov
2 siblings, 0 replies; 13+ messages in thread
From: sashiko-bot @ 2026-09-23 19:28 UTC (permalink / raw)
To: Emil Tsalapatis; +Cc: bpf
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Critical] bpf: memory isolation breach on arena spinlock -EDEADLK
- [Medium] bpf: spurious VM_FAULT_SIGBUS on concurrent arena page faults
--
commit a5d5ccfbb2dd50c63d33c5a9de680c3dad099509
Author: Emil Tsalapatis <emil@etsalapatis.com>
bpf: Atomically update PTE and range tree in arena VM fault handler
This commit modifies the arena VM fault handler to atomically adjust the
range tree and insert PTEs, avoiding deadlocks with the range tree spinlock
under PREEMPT_RT. It does this by marking the range as unavailable, dropping
the lock to insert the PTE, then re-acquiring the lock to fully remove the
range.
> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> index 69c8924f4c306..5438b68d269a8 100644
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c
> @@ -562,7 +565,7 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
> /* If a range is unavailable, try again. */
> if (ret == -EAGAIN) {
> raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
> - goto retry;
> + goto retry_memcg;
> } else if (ret) {
[ ... ]
> @@ -583,12 +586,40 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
[ ... ]
> + fault_ret = vmf_insert_page(vmf->vma, vmf->address, page);
> + while ((ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags))) {
> + /* If we somehow deadlocked stop trying to take the lock. */
> + if (ret == -EDEADLK) {
> + range_node_mark_available(unavail_node);
> + return VM_FAULT_SIGBUS;
> + }
[Severity: Critical]
Does this error path leave memory isolation broken? By calling
range_node_mark_available(), it marks the range as free in the arena's range
tree allocator.
However, the page was already mapped into the kernel vmap via
apply_to_page_range() and the user page tables via vmf_insert_page().
If the lock returns -EDEADLK, subsequent allocations might hand out this same
page to other BPF programs or userspace, potentially causing two independent
users to share and corrupt the same memory. Should this path unmap the page
before returning?
> +
> + cond_resched();
> + }
[ ... ]
> @@ -598,8 +629,9 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
[ ... ]
> -retry:
> +retry_memcg:
> bpf_map_memcg_exit(old_memcg, new_memcg);
> +retry:
> if (new_page)
> free_pages_nolock(new_page, 0);
>
> if (!(vmf->flags & FAULT_FLAG_ALLOW_RETRY))
> return VM_FAULT_SIGBUS;
[Severity: Medium]
Will this lead to spurious process crashes for concurrent faults? When two
threads concurrently page-fault on the same arena page, the first thread marks
the range as unavailable and drops the spinlock to call vmf_insert_page().
The second thread sees the unavailable range via range_tree_clear(), which
returns -EAGAIN. This sends the second thread to retry_memcg and it returns
VM_FAULT_RETRY.
When the kernel fault handler drops the mmap lock and retries the fault, it
clears FAULT_FLAG_ALLOW_RETRY. If the first thread hasn't removed the
unavailable node yet, the second thread hits -EAGAIN again, fails this flag
check, and returns VM_FAULT_SIGBUS instead of waiting.
--
Sashiko AI review · https://sashiko.dev/#/patchset/20260923191125.5311-1-emil@etsalapatis.com?part=5
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler
2026-09-23 19:11 ` [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler Emil Tsalapatis
2026-09-23 19:28 ` sashiko-bot
@ 2026-09-23 20:11 ` bot+bpf-ci
2026-09-23 22:42 ` Alexei Starovoitov
2 siblings, 0 replies; 13+ messages in thread
From: bot+bpf-ci @ 2026-09-23 20:11 UTC (permalink / raw)
To: emil, bpf
Cc: ast, andrii, eddyz87, memxor, daniel, emil, ast, andrii, daniel,
martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 4185 bytes --]
> Fixes: 317460317a02 ("bpf: Introduce bpf_arena.")
Should the Fixes: tag point to commit b795379757eb ("bpf: Introduce
range_tree data structure and use it in bpf arena") instead? The commit
being fixed here uses a range tree, not the maple tree from
317460317a02. The range tree was introduced in b795379757eb (November
2024), and that commit contains the vulnerable pattern: clearing the
range from the tree and allocating a page under lock, but releasing the
lock before userspace PTE installation.
> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> index 69c8924f4c306..5438b68d269a8 100644
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c
[ ... ]
> page = vmalloc_to_page((void *)kaddr);
> @@ -562,7 +565,7 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
> /* If a range is unavailable, try again. */
> if (ret == -EAGAIN) {
> raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
> - goto retry;
> + goto retry_memcg;
> } else if (ret) {
> fault_ret = VM_FAULT_SIGBUS;
> goto out_err_locked_memcg;
> @@ -583,12 +586,40 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
> page = new_page;
> new_page = NULL;
> out:
> - page_ref_add(page, 1);
> + /* Reserve the page while installing its user PTE without the arena lock. */
> + bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
> + unavail_node = range_tree_set_unavail(&arena->rt, vmf->pgoff, 1);
> + bpf_map_memcg_exit(old_memcg, new_memcg);
> raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
> - if (new_page)
> +
> + if (new_page) {
> free_pages_nolock(new_page, 0);
> - vmf->page = page;
> - return 0;
> + new_page = NULL;
> + }
> +
> + /* If we couldn't mark the page unavailable, retry. */
> + if (IS_ERR(unavail_node)) {
> + ret = PTR_ERR(unavail_node);
> + if (ret == -EAGAIN)
> + goto retry;
> + return VM_FAULT_SIGBUS;
> + }
Can faults on already-allocated pages now fail at memory.max? The
already-allocated case goes straight to out: after finding the page:
page = vmalloc_to_page((void *)kaddr);
if (page) {
...
/* already have a page vmap-ed */
goto out;
}
Before this patch, out: only did page_ref_add() and returned 0. Now out:
calls range_tree_set_unavail(), which goes through range_tree_set().
An allocated page has no node in the range tree, so range_tree_clear()
finds nothing, no merge happens for unavailable ranges, and the function
always reaches this allocation:
left = kmalloc_nolock(sizeof(struct range_node),
__GFP_ACCOUNT, NUMA_NO_NODE);
if (!left)
return -ENOMEM;
This runs under bpf_map_memcg_enter(), so it is charged to the arena
map's memcg. kmalloc_nolock() cannot block, so try_charge_memcg()
cannot reclaim. Once the memcg is at memory.max, it returns -ENOMEM
unless __GFP_HIGH or __GFP_NOFAIL is set. range_tree_set_unavail()
returns ERR_PTR(-ENOMEM), and the code returns VM_FAULT_SIGBUS.
This means a process accessing a page the BPF program already allocated
gets killed with SIGBUS when memcg is at memory.max. Hitting memory.max
is routine (e.g. page cache from reading a file), so this would affect
ordinary workloads. Before this patch, the already-allocated case needed
no allocation at all.
Commit c7cd8be3d72f ("bpf: arena: Allocate the fault-in page outside
the lock") fixed this failure mode: "Once the memcg is at memory.max
that allocation just fails ... and the process gets a SIGSEGV on a
perfectly valid arena address. Hitting memory.max is routine, so this
kills innocent processes over memory that reclaim could have freed."
That commit also ensured "A lockless probe skips that preallocation when
a page is already mapped, so the common case wastes no allocation."
Could the range_node be allocated before arena->spinlock is taken, with
a reclaim-capable GFP_KERNEL_ACCOUNT allocation like the page
preallocation? This would keep a routine memcg limit from turning into a
SIGBUS on valid arena memory.
[ ... ]
---
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/35908471084
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler
2026-09-23 19:11 ` [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler Emil Tsalapatis
2026-09-23 19:28 ` sashiko-bot
2026-09-23 20:11 ` bot+bpf-ci
@ 2026-09-23 22:42 ` Alexei Starovoitov
2 siblings, 0 replies; 13+ messages in thread
From: Alexei Starovoitov @ 2026-09-23 22:42 UTC (permalink / raw)
To: Emil Tsalapatis, bpf; +Cc: andrii, eddyz87, memxor, daniel
On Wed, Sep 23, 2026 at 07:11 PM Emil Tsalapatis <emil@etsalapatis.com> wrote:
> There is no way to protect the PTE installation and the range tree
> modification simultaneously, because we cannot nest the synchronization
> primitives for their respective critical sections. PTE allocation
> may require allocations due to PTE reclamation, and its spinlock
> becomes sleepable under PREEMPT_RT. Thus we cannot do this operation
> while holding the range tree spinlock. There is no public API for
> manually taking this spinlock, so we nest the range tree operation
> inside it.
__do_fault() locks the page returned by ->fault() before finish_fault()
installs the pte. That's how filemap_fault() is synchronized with
truncate.
can arena_vm_fault() lock the page, recheck vmalloc_to_page() and
return VM_FAULT_LOCKED, and the free path do
lock_page(); unlock_page(); before zap_pages() ?
[...]
> out:
> - page_ref_add(page, 1);
> + /* Reserve the page while installing its user PTE without the arena lock. */
> + bpf_map_memcg_enter(&arena->map, &old_memcg, &new_memcg);
> + unavail_node = range_tree_set_unavail(&arena->rt, vmf->pgoff, 1);
> + bpf_map_memcg_exit(old_memcg, new_memcg);
> raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
> - if (new_page)
> +
> + if (new_page) {
> free_pages_nolock(new_page, 0);
> - vmf->page = page;
> - return 0;
> + new_page = NULL;
> + }
> +
> + /* If we couldn't mark the page unavailable, retry. */
> + if (IS_ERR(unavail_node)) {
> + ret = PTR_ERR(unavail_node);
> + if (ret == -EAGAIN)
> + goto retry;
> + return VM_FAULT_SIGBUS;
> + }
The race needs user space to access the page while bpf prog is
freeing it.
With this patch every user fault, including the one on a page that
bpf prog already allocated, does kmalloc_nolock() of a range node.
It cannot reclaim, so at memory.max the process gets SIGBUS on
a valid page. That's what commit c7cd8be3d72f fixed.
Two threads touching the same page for the first time: the 2nd one
gets -EAGAIN and spins in VM_FAULT_RETRY until the 1st is done.
^ permalink raw reply [flat|nested] 13+ messages in thread
* [PATCH bpf-next v3 6/6] selftests/bpf: Add arena allocation race tests
2026-09-23 19:11 [PATCH bpf-next v3 0/6] bpf: Fix arena memory incoherence Emil Tsalapatis
` (4 preceding siblings ...)
2026-09-23 19:11 ` [PATCH bpf-next v3 5/6] bpf: Atomically update PTE and range tree in arena VM fault handler Emil Tsalapatis
@ 2026-09-23 19:11 ` Emil Tsalapatis
2026-09-23 20:12 ` bot+bpf-ci
5 siblings, 1 reply; 13+ messages in thread
From: Emil Tsalapatis @ 2026-09-23 19:11 UTC (permalink / raw)
To: bpf; +Cc: ast, andrii, eddyz87, memxor, daniel, Emil Tsalapatis
Add selftests to handle arena page allocation-related races.
Ensure that concurrent frees and nonsleepable/sleepable page
allocations, as well as allocations from userspace, do not
lead to inconsistent or lost data.
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
.../selftests/bpf/prog_tests/arena_race.c | 270 ++++++++++++++++++
.../testing/selftests/bpf/progs/arena_race.c | 159 +++++++++++
2 files changed, 429 insertions(+)
create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_race.c
create mode 100644 tools/testing/selftests/bpf/progs/arena_race.c
diff --git a/tools/testing/selftests/bpf/prog_tests/arena_race.c b/tools/testing/selftests/bpf/prog_tests/arena_race.c
new file mode 100644
index 000000000000..c2da611421f3
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/arena_race.c
@@ -0,0 +1,270 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#define _GNU_SOURCE
+#include <sched.h>
+#include <sys/syscall.h>
+#include <test_progs.h>
+
+#include "arena_race.skel.h"
+
+struct free_thread_ctx {
+ struct arena_race *skel;
+ int err;
+ __u32 retval;
+};
+
+struct fault_thread_ctx {
+ __u64 *addr;
+ int stop;
+};
+
+static int run_prog(struct bpf_program *prog, const char *name)
+{
+ LIBBPF_OPTS(bpf_test_run_opts, opts);
+ int err;
+
+ err = bpf_prog_test_run_opts(bpf_program__fd(prog), &opts);
+ return ASSERT_OK(err, name) && ASSERT_OK(opts.retval, name) ? 0 : -1;
+}
+
+/* Trigger the sleepable free page path. */
+static void *run_free_thread(void *arg)
+{
+ LIBBPF_OPTS(bpf_test_run_opts, opts);
+ struct free_thread_ctx *ctx = arg;
+
+ ctx->skel->bss->target_tid = sys_gettid();
+ ctx->err = bpf_prog_test_run_opts(
+ bpf_program__fd(ctx->skel->progs.free_page), &opts);
+ ctx->retval = opts.retval;
+ return NULL;
+}
+
+/* Continuously fault in the address. */
+static void *fault_reader_thread(void *arg)
+{
+ struct fault_thread_ctx *ctx = arg;
+
+ while (!READ_ONCE(ctx->stop))
+ (void)READ_ONCE(*ctx->addr);
+ return NULL;
+}
+
+static int wait_for(int *p)
+{
+ __u64 deadline = get_time_ns() + 5ULL * 1000 * 1000 * 1000;
+
+ while (!READ_ONCE(*p)) {
+ if (get_time_ns() > deadline)
+ return -ETIMEDOUT;
+ }
+ return 0;
+}
+
+static struct arena_race *setup_arena(__u64 **addr, bool trace_flush)
+{
+ struct arena_race *skel;
+ size_t arena_sz;
+ char *base;
+ int err;
+
+ skel = arena_race__open();
+ if (!ASSERT_OK_PTR(skel, "open"))
+ return NULL;
+ err = bpf_program__set_autoload(skel->progs.trace_flush, trace_flush);
+ if (!ASSERT_OK(err, "trace_flush_autoload"))
+ goto err_out;
+
+ err = arena_race__load(skel);
+ if (!ASSERT_OK(err, "load"))
+ goto err_out;
+ err = arena_race__attach(skel);
+ if (!ASSERT_OK(err, "attach"))
+ goto err_out;
+
+ if (run_prog(skel->progs.alloc_old, "alloc_old"))
+ goto err_out;
+ if (skel->bss->skip) {
+ test__skip();
+ goto err_out;
+ }
+
+ base = bpf_map__initial_value(skel->maps.arena, &arena_sz);
+ if (!ASSERT_OK_PTR(base, "arena_base"))
+ goto err_out;
+ *addr = (__u64 *)(base + getpagesize());
+ if (!ASSERT_EQ((unsigned long)skel->bss->ptr, (unsigned long)*addr,
+ "arena_ptr"))
+ goto err_out;
+ return skel;
+
+err_out:
+ arena_race__destroy(skel);
+ return NULL;
+}
+
+static void test_free_before_flush(bool deferred)
+{
+ struct free_thread_ctx ctx = {};
+ struct arena_race *skel;
+ pthread_t thread;
+ __u64 *addr;
+ bool thread_created = false, flush_seen = false, completed = false;
+ int err;
+
+ if (libbpf_find_vmlinux_btf_id("flush_tlb_kernel_range",
+ BPF_TRACE_FENTRY) <= 0) {
+ printf("%s:SKIP: flush_tlb_kernel_range is not an fentry target\n",
+ __func__);
+ test__skip();
+ return;
+ }
+
+ skel = setup_arena(&addr, true);
+ if (!skel)
+ return;
+
+ /* Pause during a TLB flush to widen the race window. */
+ skel->bss->pause_on_flush = 1;
+
+ if (deferred) {
+ /*
+ * Test the nonsleepable free path that gets
+ * deferred to a worker in the kernel. We do
+ * so by triggering the arena operation from
+ * a nonsleepable tracepoint context.
+ */
+ skel->bss->trigger_pid_tgid =
+ ((__u64)getpid() << 32) | (__u32)sys_gettid();
+ skel->bss->trigger_syscall = SYS_getpgid;
+ skel->bss->deferred_free = 1;
+ if (!ASSERT_GE(syscall(SYS_getpgid, 0), 0, "deferred_free"))
+ goto release;
+ } else {
+ /*
+ * Test the sleepable arena free path through a
+ * syscall test prog.
+ */
+ ctx.skel = skel;
+ err = pthread_create(&thread, NULL, run_free_thread, &ctx);
+ if (!ASSERT_OK(err, "pthread_create")) {
+ skel->bss->release = 1;
+ goto out;
+ }
+ thread_created = true;
+ }
+
+ /* Wait until the worker thread triggers a flush. */
+ err = wait_for(&skel->bss->flush_entered);
+ if (!ASSERT_OK(err, "flush_entered"))
+ goto release;
+
+ flush_seen = true;
+
+ /* Force a reallocation during the flush. */
+ run_prog(skel->progs.try_realloc, "realloc_before_flush");
+ ASSERT_NULL(skel->bss->realloc_ptr, "realloc_before_flush");
+
+release:
+ skel->bss->release = 1;
+ if (thread_created) {
+ ASSERT_OK(pthread_join(thread, NULL), "pthread_join");
+ thread_created = false;
+ completed = ASSERT_OK(ctx.err, "free_run") &&
+ ASSERT_OK(ctx.retval, "free_retval");
+ } else if (skel->bss->target_tid) {
+ err = wait_for(&skel->bss->worker_exited);
+ completed = ASSERT_OK(err, "worker_exited");
+ }
+ ASSERT_FALSE(skel->bss->timed_out, "flush_timed_out");
+
+ if (flush_seen && completed &&
+ !run_prog(skel->progs.try_realloc, "realloc_after_flush")) {
+ ASSERT_EQ((unsigned long)skel->bss->realloc_ptr,
+ (unsigned long)addr, "realloc_after_flush");
+ ASSERT_EQ(*addr, skel->rodata->new_marker, "new_marker");
+ }
+out:
+ arena_race__destroy(skel);
+}
+
+/*
+ * Force a race between a faulting thread in userspace and a
+ * free operation on the arena.
+ */
+static void test_fault_free_realloc(void)
+{
+ struct fault_thread_ctx fault = {};
+ struct arena_race *skel;
+ pthread_t fault_thread;
+ bool fault_created = false;
+ __u64 *addr;
+ __u64 expected, value;
+ int err, i;
+
+ skel = setup_arena(&addr, false);
+ if (!skel)
+ return;
+
+ skel->bss->realloc_after_free = 1;
+
+ fault.addr = addr;
+ err = pthread_create(&fault_thread, NULL, fault_reader_thread, &fault);
+ if (!ASSERT_OK(err, "pthread_create_fault"))
+ goto out;
+ fault_created = true;
+
+ for (i = 0; i < 1000; i++) {
+ LIBBPF_OPTS(bpf_test_run_opts, opts);
+
+ err = bpf_prog_test_run_opts(bpf_program__fd(skel->progs.free_page),
+ &opts);
+ if (err) {
+ ASSERT_OK(err, "free_realloc");
+ break;
+ }
+ if (opts.retval) {
+ ASSERT_OK(opts.retval, "free_realloc");
+ break;
+ }
+ value = *addr;
+ expected = skel->bss->current_marker;
+ if (value != expected) {
+ ASSERT_EQ(value, expected, "marker_after_realloc");
+ break;
+ }
+ }
+
+ WRITE_ONCE(fault.stop, 1);
+ if (fault_created) {
+ ASSERT_OK(pthread_join(fault_thread, NULL), "pthread_join_fault");
+ fault_created = false;
+ }
+out:
+ WRITE_ONCE(fault.stop, 1);
+ if (fault_created)
+ pthread_join(fault_thread, NULL);
+ arena_race__destroy(skel);
+}
+
+void serial_test_arena_race(void)
+{
+ cpu_set_t cpuset;
+ int err;
+
+ err = sched_getaffinity(0, sizeof(cpuset), &cpuset);
+ if (!ASSERT_OK(err, "sched_getaffinity"))
+ return;
+ if (CPU_COUNT(&cpuset) < 2) {
+ printf("%s:SKIP: at least two runnable CPUs are required\n", __func__);
+ test__skip();
+ return;
+ }
+
+ if (test__start_subtest("free_before_flush"))
+ test_free_before_flush(false);
+ if (test__start_subtest("deferred_free_before_flush"))
+ test_free_before_flush(true);
+ if (test__start_subtest("fault_free_realloc"))
+ test_fault_free_realloc();
+}
diff --git a/tools/testing/selftests/bpf/progs/arena_race.c b/tools/testing/selftests/bpf/progs/arena_race.c
new file mode 100644
index 000000000000..56ebfd727324
--- /dev/null
+++ b/tools/testing/selftests/bpf/progs/arena_race.c
@@ -0,0 +1,159 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#define BPF_NO_KFUNC_PROTOTYPES
+#include <vmlinux.h>
+#include <bpf/bpf_helpers.h>
+#include <bpf/bpf_tracing.h>
+#include "bpf_experimental.h"
+#include <bpf_arena_common.h>
+
+const volatile __u64 old_marker = 0x1111222233334444ULL;
+const volatile __u64 new_marker = 0x5555666677778888ULL;
+
+struct {
+ __uint(type, BPF_MAP_TYPE_ARENA);
+ __uint(map_flags, BPF_F_MMAPABLE);
+ __uint(max_entries, 4);
+#ifdef __TARGET_ARCH_arm64
+ __ulong(map_extra, 0x1ull << 32);
+#else
+ __ulong(map_extra, 0x1ull << 44);
+#endif
+} arena SEC(".maps");
+
+bool skip;
+
+void __arena *ptr;
+void __arena *realloc_ptr;
+bool realloc_after_free;
+__u64 current_marker;
+__u64 marker_seq;
+
+int target_tid;
+int pause_on_flush;
+int flush_entered;
+int release;
+int timed_out;
+
+__u64 trigger_pid_tgid;
+long trigger_syscall;
+int deferred_free;
+int worker_armed;
+int worker_exited;
+
+static __always_inline void wait_for_release(void)
+{
+ while (!*(volatile int *)&release && can_loop)
+ ;
+ if (!*(volatile int *)&release)
+ timed_out = 1;
+}
+
+SEC("syscall")
+int alloc_old(void *ctx)
+{
+#if defined(__BPF_FEATURE_ADDR_SPACE_CAST) || defined(BPF_ARENA_FORCE_ASM)
+ __u64 __arena *p;
+ char __arena *base = arena_base(&arena);
+
+ realloc_ptr = NULL;
+ ptr = bpf_arena_alloc_pages(&arena, base + __PAGE_SIZE, 1,
+ NUMA_NO_NODE, 0);
+ if (!ptr)
+ return 1;
+ p = (__u64 __arena *)ptr;
+ *p = old_marker;
+ current_marker = old_marker;
+#else
+ skip = true;
+#endif
+ return 0;
+}
+
+SEC("syscall")
+int free_page(void *ctx)
+{
+#if defined(__BPF_FEATURE_ADDR_SPACE_CAST) || defined(BPF_ARENA_FORCE_ASM)
+ __u64 __arena *p;
+ __u64 marker;
+
+ if (!ptr)
+ return 1;
+ bpf_arena_free_pages(&arena, ptr, 1);
+ if (!realloc_after_free)
+ return 0;
+
+ marker = new_marker + ++marker_seq;
+ realloc_ptr = bpf_arena_alloc_pages(&arena, ptr, 1, NUMA_NO_NODE, 0);
+ if (realloc_ptr)
+ ptr = realloc_ptr;
+ else
+ realloc_ptr = ptr;
+ p = (__u64 __arena *)ptr;
+ *p = marker;
+ current_marker = marker;
+#endif
+ return 0;
+}
+
+SEC("syscall")
+int try_realloc(void *ctx)
+{
+#if defined(__BPF_FEATURE_ADDR_SPACE_CAST) || defined(BPF_ARENA_FORCE_ASM)
+ __u64 __arena *p;
+
+ realloc_ptr = bpf_arena_alloc_pages(&arena, ptr, 1, NUMA_NO_NODE, 0);
+ if (realloc_ptr) {
+ ptr = realloc_ptr;
+ p = (__u64 __arena *)realloc_ptr;
+ *p = new_marker;
+ current_marker = new_marker;
+ }
+#endif
+ return 0;
+}
+
+SEC("tp_btf/sys_enter")
+int BPF_PROG(deferred_free_prog, struct pt_regs *regs, long id)
+{
+#if defined(__BPF_FEATURE_ADDR_SPACE_CAST) || defined(BPF_ARENA_FORCE_ASM)
+ if (!deferred_free || bpf_get_current_pid_tgid() != trigger_pid_tgid ||
+ id != trigger_syscall)
+ return 0;
+
+ deferred_free = 0;
+ /* The worker can run on another CPU before the kfunc returns. */
+ worker_armed = 1;
+ bpf_arena_free_pages(&arena, ptr, 1);
+#endif
+ return 0;
+}
+
+SEC("fentry/arena_free_worker")
+int BPF_PROG(trace_free_worker, struct work_struct *work)
+{
+ if (worker_armed && !target_tid)
+ target_tid = (__u32)bpf_get_current_pid_tgid();
+ return 0;
+}
+
+SEC("fexit/arena_free_worker")
+int BPF_PROG(trace_free_worker_ret, struct work_struct *work)
+{
+ if ((__u32)bpf_get_current_pid_tgid() == target_tid)
+ worker_exited = 1;
+ return 0;
+}
+
+SEC("?fentry/flush_tlb_kernel_range")
+int BPF_PROG(trace_flush, unsigned long start, unsigned long end)
+{
+ if (!pause_on_flush ||
+ (__u32)bpf_get_current_pid_tgid() != target_tid)
+ return 0;
+ flush_entered = 1;
+ wait_for_release();
+ return 0;
+}
+
+char _license[] SEC("license") = "GPL";
--
2.52.0
^ permalink raw reply related [flat|nested] 13+ messages in thread* Re: [PATCH bpf-next v3 6/6] selftests/bpf: Add arena allocation race tests
2026-09-23 19:11 ` [PATCH bpf-next v3 6/6] selftests/bpf: Add arena allocation race tests Emil Tsalapatis
@ 2026-09-23 20:12 ` bot+bpf-ci
0 siblings, 0 replies; 13+ messages in thread
From: bot+bpf-ci @ 2026-09-23 20:12 UTC (permalink / raw)
To: emil, bpf
Cc: ast, andrii, eddyz87, memxor, daniel, emil, ast, andrii, daniel,
martin.lau, eddyz87, yonghong.song, mason, ihor.solodrai
[-- Attachment #1: Type: text/plain, Size: 5684 bytes --]
> diff --git a/tools/testing/selftests/bpf/prog_tests/arena_race.c b/tools/testing/selftests/bpf/prog_tests/arena_race.c
> new file mode 100644
> index 0000000000000..c2da611421f3a
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/prog_tests/arena_race.c
[ ... ]
> @@ -0,0 +1,270 @@
[ ... ]
> +static struct arena_race *setup_arena(__u64 **addr, bool trace_flush)
> +{
> + struct arena_race *skel;
> + size_t arena_sz;
> + char *base;
> + int err;
> +
> + skel = arena_race__open();
> + if (!ASSERT_OK_PTR(skel, "open"))
> + return NULL;
> + err = bpf_program__set_autoload(skel->progs.trace_flush, trace_flush);
> + if (!ASSERT_OK(err, "trace_flush_autoload"))
> + goto err_out;
> +
> + err = arena_race__load(skel);
> + if (!ASSERT_OK(err, "load"))
> + goto err_out;
> + err = arena_race__attach(skel);
> + if (!ASSERT_OK(err, "attach"))
> + goto err_out;
> +
> + if (run_prog(skel->progs.alloc_old, "alloc_old"))
> + goto err_out;
> + if (skel->bss->skip) {
> + test__skip();
> + goto err_out;
> + }
A subsystem pattern flags this as potentially concerning: when the BPF
object was built without arena address-space-cast support, alloc_old
in progs/arena_race.c sets `skip = true`. setup_arena() then calls
test__skip() without printing why.
Both subtests go through setup_arena(), so on such a toolchain every
subtest is marked SKIP with no explanation. The neighbouring arena
tests print a reason before skipping for the same condition. For
example, prog_tests/arena_list.c prints:
printf("%s:SKIP:compiler doesn't support arena_cast\n", __func__);
test__skip();
The other skip in this file (in test_free_before_flush) already prints
"flush_tlb_kernel_range is not an fentry target". Should this skip
include a similar reason?
> +
> + base = bpf_map__initial_value(skel->maps.arena, &arena_sz);
> + if (!ASSERT_OK_PTR(base, "arena_base"))
> + goto err_out;
> + *addr = (__u64 *)(base + getpagesize());
> + if (!ASSERT_EQ((unsigned long)skel->bss->ptr, (unsigned long)*addr,
> + "arena_ptr"))
> + goto err_out;
> + return skel;
> +
> +err_out:
> + arena_race__destroy(skel);
> + return NULL;
> +}
[ ... ]
> diff --git a/tools/testing/selftests/bpf/progs/arena_race.c b/tools/testing/selftests/bpf/progs/arena_race.c
> new file mode 100644
> index 0000000000000..56ebfd7273247
> --- /dev/null
> +++ b/tools/testing/selftests/bpf/progs/arena_race.c
[ ... ]
> +SEC("syscall")
> +int free_page(void *ctx)
> +{
> +#if defined(__BPF_FEATURE_ADDR_SPACE_CAST) || defined(BPF_ARENA_FORCE_ASM)
> + __u64 __arena *p;
> + __u64 marker;
> +
> + if (!ptr)
> + return 1;
> + bpf_arena_free_pages(&arena, ptr, 1);
> + if (!realloc_after_free)
> + return 0;
> +
> + marker = new_marker + ++marker_seq;
> + realloc_ptr = bpf_arena_alloc_pages(&arena, ptr, 1, NUMA_NO_NODE, 0);
> + if (realloc_ptr)
> + ptr = realloc_ptr;
> + else
> + realloc_ptr = ptr;
> + p = (__u64 __arena *)ptr;
> + *p = marker;
> + current_marker = marker;
Can the write to *p cause spurious test failures when the realloc
fails?
When bpf_arena_alloc_pages() fails, the code falls through to write the
marker through the old ptr. That only works if the failure means
fault_reader_thread already faulted the page back in.
However, there is a second way to reach the failed realloc: the free
itself can be deferred. The reader thread's fault reserves the range
for a short time while it installs the user PTE. In arena_vm_fault()
it calls range_tree_set_unavail() before vmf_insert_page() and
range_tree_remove_unavail() after it.
If the next iteration's bpf_arena_free_pages() starts inside that
window, arena_free_pages() gets -EAGAIN and defers the free:
kernel/bpf/arena.c:arena_free_pages() {
unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
if (IS_ERR(unavail_node)) {
...
/*
* For -EAGAIN: An overlapping fault reserves
* the range before installing its PTE.
*/
if (ret == -ENOMEM || ret == -EAGAIN)
goto defer;
The page is still allocated at that point, so the realloc fails:
is_range_tree_set() returns -ESRCH, or range_tree_clear() returns
-EAGAIN. The program then writes the marker into the old page and sets
current_marker.
Then arena_free_worker(), queued via irq_work and schedule_work on the
same CPU, clears the kernel PTE, zaps the user PTE and frees that page.
When the userspace loop reads *addr afterwards, arena_vm_fault() maps
a fresh zeroed page because the range is available again, so
ASSERT_EQ(value, expected, "marker_after_realloc")
in test_fault_free_realloc() sees 0 instead of the marker.
A variant: if the deferred span runs only after the next iteration's
synchronous free and successful realloc at the same address, the worker
tears down the newly reallocated page, and the same assertion fails.
The kernel is doing what it is designed to do here; the program is
writing to a page it just freed. The test's assumption that a failed
realloc always means the page was faulted back in does not hold, so
the 1000-iteration loop can fail spuriously in CI, most easily on VMs
where the reader thread's vCPU can be delayed between vmf_insert_page()
and range_tree_remove_unavail().
Possible fixes: have free_page return a distinct retval or flag when
the realloc fails and the page may be pending release, or make
userspace retry or skip the marker check in that case.
> +#endif
> + return 0;
> +}
[ ... ]
---
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/35908471084
^ permalink raw reply [flat|nested] 13+ messages in thread