[PATCH bpf-next v4 0/8] bpf: Fix arena memory incoherence

[PATCH bpf-next v4 0/8] bpf: Fix arena memory incoherence

[Emil Tsalapatis]

Setting up arena memory for a task currently requires two operations:
Adjusting its range tree, used for tracking which memory is allocated;
and adjusting its page tables/flushing its TLB state. These operations
cannot happen atomically because their critical sections do not nest.
This lack of atomicity is the source of two bugs that can lead to
incoherence between different users of the same arena, wherein they
observe different pages for the same address.

Address the problem by more finely tracking the state of each address.
Expand the range tree used for address state tracking with a third
state, used to denote whether an address range is unavailable, either
because it is being freed or because it is being populated by a VM
fault. Use this extra state in the arena page freeing/fault logic
to ensure that operations on a single address properly serialize.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
Cc: Puranjay Mohan <puranjay@kernel.org>

v3 -> v4 (https://lore.kernel.org/bpf/20260923191125.5311-1-emil@etsalapatis.com/)

- Add per-arena anonymous mappings and associate pages with them
- Return VM_FAULT_LOCKED and let generic MM install user PTEs; wait
  for locked fault pages before TLB flushing and zapping (Alexei).
- Add mutual exclusion between arena free and fault operations to
  prevent incoherency.
- Return VM_FAULT_NOPAGE for non-retryable GUP faults when progress is
  impossible.
- Stop and drain self-requeueing deferred frees before map teardown.
- Track ownership of unavailable ranges independently of free progress
  and retry worker reservations on -ENOMEM without starting teardown.
- Make arena free span state machine explicit.

v2 -> v3 (https://lore.kernel.org/bpf/20260923061425.7045-1-emil@etsalapatis.com/)

- Rebase on bpf-next and resolve conflicts
- Fold in the atomic mark_available range tree operation into initial
  fix patches

v1 -> v2 (https://lore.kernel.org/bpf/20260902070239.16968-1-emil@etsalapatis.com/)

- Use __range_iter_next() in is_range_tree_set() (bot-ci)
- Move -EAGAIN handling to the patch where the errno is introduced (bot-ci)
- Add refactoring patch for (Puranjay)
- Avoid leaking unavailable range tree nodes with atomic mark_available
  operation()
- Avoid retries on res spinlock locking for -EDEADLK (Puranjay)


Emil Tsalapatis (8):
  bpf: Use mapping tree to zap arena VMAs
  bpf: Associate arena pages with their mapping
  bpf: arena: Stop deferred frees before map teardown
  bpf: Update is_range_tree_set to work for consecutive ranges
  bpf: Track availability information for ranges in range tree
  bpf: Fix arena race between page free and alloc leading to incoherency
  bpf: Synchronize arena page faults with page freeing
  selftests/bpf: Add arena allocation race tests

 include/linux/bpf.h                           |   1 +
 kernel/bpf/arena.c                            | 452 ++++++++++++++----
 kernel/bpf/range_tree.c                       | 240 ++++++++--
 kernel/bpf/range_tree.h                       |   7 +-
 kernel/bpf/syscall.c                          |   2 +
 .../selftests/bpf/prog_tests/arena_race.c     | 285 +++++++++++
 .../testing/selftests/bpf/progs/arena_race.c  | 159 ++++++
 7 files changed, 1013 insertions(+), 133 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/arena_race.c
 create mode 100644 tools/testing/selftests/bpf/progs/arena_race.c

-- 
2.52.0

[PATCH bpf-next v4 1/8] bpf: Use mapping tree to zap arena VMAs

[Emil Tsalapatis]

Walk the arena's mapping tree under i_mmap_lock_read() instead of dropping
arena->lock and acquiring mmap_lock for each VMA. Remove the need for MM
pins, address revalidation, visitation generations and zap seialization
Give each arena a private anonymous inode through an arena-owned backing
file.

This refactoring is necessary to avoid deadlocks between arena_vm_fault
and page zapping in subsequent patches.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 include/linux/bpf.h  |  1 +
 kernel/bpf/arena.c   | 97 ++++++++++++++++++--------------------------
 kernel/bpf/syscall.c |  2 +
 3 files changed, 43 insertions(+), 57 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 54144372281c..fd2986686d62 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -89,6 +89,7 @@ struct bpf_map_ops {
 	/* funcs callable from userspace (via syscall) */
 	int (*map_alloc_check)(union bpf_attr *attr);
 	struct bpf_map *(*map_alloc)(union bpf_attr *attr);
+	struct file *(*map_get_file)(struct bpf_map *map, int flags);
 	void (*map_release)(struct bpf_map *map, struct file *map_file);
 	void (*map_free)(struct bpf_map *map);
 	void (*map_free_pre_rcu)(struct bpf_map *map);
diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 0ff707707da0..b95ffdb14417 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -1,9 +1,11 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
+#include <linux/anon_inodes.h>
 #include <linux/bpf.h>
 #include <linux/btf.h>
 #include <linux/cacheflush.h>
 #include <linux/err.h>
+#include <linux/fs.h>
 #include <linux/irq_work.h>
 #include "linux/filter.h"
 #include <linux/llist.h>
@@ -53,6 +55,7 @@ struct bpf_arena {
 	u64 user_vm_start;
 	u64 user_vm_end;
 	struct vm_struct *kern_vm;
+	struct file *file;
 	struct page *scratch_page;
 	struct range_tree rt;
 	/* protects rt and nr_pages */
@@ -62,8 +65,6 @@ struct bpf_arena {
 	struct list_head vma_list;
 	/* protects vma_list */
 	struct mutex lock;
-	u64 zap_gen;
-	struct mutex zap_mutex;
 	struct irq_work     free_irq;
 	struct work_struct  free_work;
 	struct llist_head   free_spans;
@@ -268,6 +269,9 @@ static int populate_pgtable_except_pte(struct bpf_arena *arena)
 				   SZ_4G + GUARD_SZ / 2, apply_range_set_cb, NULL);
 }
 
+/* The backing file must not hold a map reference. */
+static const struct file_operations arena_backing_fops = {};
+
 static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
 {
 	struct vm_struct *kern_vm;
@@ -326,12 +330,18 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
 	if (err)
 		goto err_free_scratch;
 	mutex_init(&arena->lock);
-	mutex_init(&arena->zap_mutex);
 	raw_res_spin_lock_init(&arena->spinlock);
 	err = populate_pgtable_except_pte(arena);
 	if (err)
 		goto err_destroy_rt;
 
+	arena->file = anon_inode_create_getfile("bpf-map", &arena_backing_fops,
+						NULL, O_RDWR, NULL);
+	if (IS_ERR(arena->file)) {
+		err = PTR_ERR(arena->file);
+		goto err_destroy_rt;
+	}
+
 	return &arena->map;
 
 err_destroy_rt:
@@ -400,6 +410,7 @@ static void arena_map_free(struct bpf_map *map)
 	free_vm_area(arena->kern_vm);
 	range_tree_destroy(&arena->rt);
 	__free_page(arena->scratch_page);
+	fput(arena->file);
 	bpf_map_area_free(arena);
 }
 
@@ -428,10 +439,8 @@ static u64 arena_map_mem_usage(const struct bpf_map *map)
 }
 
 struct vma_list {
-	struct vm_area_struct *vma;
 	struct list_head head;
 	refcount_t mmap_count;
-	u64 zap_gen;
 };
 
 static int remember_vma(struct bpf_arena *arena, struct vm_area_struct *vma)
@@ -443,8 +452,6 @@ static int remember_vma(struct bpf_arena *arena, struct vm_area_struct *vma)
 		return -ENOMEM;
 	refcount_set(&vml->mmap_count, 1);
 	vma->vm_private_data = vml;
-	vml->vma = vma;
-	vml->zap_gen = 0;
 	list_add(&vml->head, &arena->vma_list);
 	return 0;
 }
@@ -638,6 +645,20 @@ static unsigned long arena_get_unmapped_area(struct file *filp, unsigned long ad
 	return round_up(ret, SZ_4G);
 }
 
+static struct file *arena_map_get_file(struct bpf_map *map, int flags)
+{
+	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
+	struct file *file;
+
+	file = alloc_file_clone(arena->file, flags & (O_ACCMODE | O_NONBLOCK),
+				&bpf_map_fops);
+	if (!IS_ERR(file)) {
+		file->private_data = map;
+		file_set_fsnotify_mode(file, FMODE_NONOTIFY);
+	}
+	return file;
+}
+
 static int arena_map_mmap(struct bpf_map *map, struct vm_area_struct *vma)
 {
 	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
@@ -692,6 +713,7 @@ BTF_ID_LIST_SINGLE(bpf_arena_map_btf_ids, struct, bpf_arena)
 const struct bpf_map_ops arena_map_ops = {
 	.map_meta_equal = bpf_map_meta_equal,
 	.map_alloc = arena_map_alloc,
+	.map_get_file = arena_map_get_file,
 	.map_free = arena_map_free,
 	.map_direct_value_addr = arena_map_direct_value_addr,
 	.map_mmap = arena_map_mmap,
@@ -835,60 +857,21 @@ static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt
  */
 static void zap_pages(struct bpf_arena *arena, long uaddr, long page_cnt)
 {
+	struct address_space *mapping = arena->file->f_mapping;
 	unsigned long size = (unsigned long)page_cnt << PAGE_SHIFT;
+	pgoff_t first = compute_pgoff(arena, uaddr);
+	pgoff_t last = first + page_cnt - 1;
 	struct vm_area_struct *vma;
-	struct mm_struct *mm;
-	struct vma_list *vml;
-	unsigned long vm_start;
-	u64 my_gen;
-
-	/*
-	 * Taking mmap_read_lock() under arena->lock would deadlock against
-	 * arena_vm_close(), which runs with mmap_write_lock held and then
-	 * acquires arena->lock. Drop arena->lock for mmap_read_lock().
-	 *
-	 * Use per-call my_gen, recorded in vml->zap_gen, to remember which
-	 * vmls this invocation has already processed across the lock drop.
-	 * Hold zap_mutex around the whole walk so concurrent zap_pages()
-	 * callers cannot overwrite each other's marks on shared vmls --
-	 * otherwise call B's mark would make call A skip a vml that A has
-	 * not yet zapped for A's uaddr range.
-	 */
-	mutex_lock(&arena->zap_mutex);
-	mutex_lock(&arena->lock);
-	my_gen = ++arena->zap_gen;
-	for (;;) {
-		mm = NULL;
-		list_for_each_entry(vml, &arena->vma_list, head) {
-			if (vml->zap_gen >= my_gen)
-				continue;
-			vml->zap_gen = my_gen;
-			if (!mmget_not_zero(vml->vma->vm_mm))
-				continue;
-			mm = vml->vma->vm_mm;
-			vm_start = vml->vma->vm_start;
-			break;
-		}
-		if (!mm)
-			break;
-		mutex_unlock(&arena->lock);
 
-		mmap_read_lock(mm);
-		/*
-		 * Re-resolve: while we waited the VMA could have been unmapped
-		 * and a different mapping installed at the same address.
-		 */
-		vma = find_vma(mm, vm_start);
-		if (vma && vma->vm_start == vm_start &&
-		    vma->vm_file && vma->vm_file->private_data == &arena->map)
-			zap_vma_range(vma, uaddr, size);
-		mmap_read_unlock(mm);
-		mmput(mm);
-
-		mutex_lock(&arena->lock);
+	/* The mapping lock keeps VMAs stable without taking mmap_lock. */
+	i_mmap_lock_read(mapping);
+	mapping_rmap_tree_foreach(vma, mapping, first, last) {
+		if (vma->vm_ops != &arena_vm_ops ||
+		    vma->vm_file->private_data != &arena->map)
+			continue;
+		zap_vma_range(vma, uaddr, size);
 	}
-	mutex_unlock(&arena->lock);
-	mutex_unlock(&arena->zap_mutex);
+	i_mmap_unlock_read(mapping);
 }
 
 static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt, bool sleepable)
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index 654f896af265..1a1cc305dabb 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -1209,6 +1209,8 @@ int bpf_map_new_fd(struct bpf_map *map, int flags)
 	if (ret < 0)
 		return ret;
 
+	if (map->ops->map_get_file)
+		return FD_ADD(flags | O_CLOEXEC, map->ops->map_get_file(map, flags));
 	return anon_inode_getfd("bpf-map", &bpf_map_fops, map,
 				flags | O_CLOEXEC);
 }
-- 
2.52.0

Re: [PATCH bpf-next v4 1/8] bpf: Use mapping tree to zap arena VMAs

[bot+bpf-ci]

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

> bpf: Use mapping tree to zap arena VMAs

TL;DR: Per-arena anon inode is no longer S_PRIVATE, so under SELinux arena
creation, mmap and fd passing may now be denied for existing policies. Was
this intended? Commit message doesn't mention it.

> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c

[ ... ]

> @@ -326,12 +330,18 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
>  	if (err)
>  		goto err_free_scratch;
>  	mutex_init(&arena->lock);
> -	mutex_init(&arena->zap_mutex);
>  	raw_res_spin_lock_init(&arena->spinlock);
>  	err = populate_pgtable_except_pte(arena);
>  	if (err)
>  		goto err_destroy_rt;
>
> +	arena->file = anon_inode_create_getfile("bpf-map", &arena_backing_fops,
> +						NULL, O_RDWR, NULL);
> +	if (IS_ERR(arena->file)) {
> +		err = PTR_ERR(arena->file);
> +		goto err_destroy_rt;
> +	}
> +
>  	return &arena->map;

Does switching arena fds from the shared S_PRIVATE anon inode to a
per-arena inode from anon_inode_create_getfile() change LSM behavior in a way
the commit message doesn't mention?

anon_inode_create_getfile() creates a !S_PRIVATE inode and calls the
inode_init_security_anon() hook:

    inode = alloc_anon_inode(sb);
    inode->i_flags &= ~S_PRIVATE;
    ...
    error = security_inode_init_security_anon(inode, &QSTR(name), context_inode);

Under SELinux this looks like it has two new effects for
BPF_MAP_TYPE_ARENA.

First, map creation now runs the anon inode create check:

    map_create() -> map_create_alloc() -> arena_map_alloc()
      -> anon_inode_create_getfile()
        -> selinux_inode_init_security_anon()

    return avc_has_perm(sid, isec->sid, isec->sclass, FILE__CREATE, &ad);

A policy that doesn't grant the caller's domain anon_inode { create } on the
transitioned "bpf-map" type would now fail arena creation with -EACCES,
which the PTR_ERR() above returns to userspace.

Second, every arena fd built by arena_map_get_file() via alloc_file_clone()
of arena->file has an inode without S_PRIVATE.  Previously
inode_sid_has_perm() returned early for the shared anon inode:

    if (unlikely(IS_PRIVATE(inode)))
        return 0;

That early return no longer applies.  mmap() of the arena
(selinux_mmap_file() -> file_map_prot_check() -> __file_has_perm() ->
inode_has_perm()) and passing the fd over SCM_RIGHTS or binder
(selinux_file_receive() -> file_has_perm()) would now need anon_inode
{ read write map } permission on that label, including in the receiving
domain.

Other map types keep the old unlabeled behavior because they still use
anon_inode_getfd(), so only arena fds get these checks.  Existing
SELinux-enforcing setups whose policy was written for the old behavior, such
as a loader daemon that creates maps and hands the fds to confined
applications, could start seeing denials on arena creation or mmap.  The
later patches in this series still call anon_inode_create_getfile(), so this
isn't changed there.

Was the new LSM labeling intended?  If the goal is only a unique inode and
mapping, could the old S_PRIVATE, unlabeled semantics be kept instead, or
could the commit message at least document the new policy requirements?


---
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/38657686181

[PATCH bpf-next v4 2/8] bpf: Associate arena pages with their mapping

[Emil Tsalapatis]

Associate arena backing pages with the arena's private mapping and set
their page offsets. This allows the fault handler to delegate user PTE
installation to generic MM code, which is itself useful for avoiding
races with kfunc-related arena operations.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 kernel/bpf/arena.c | 30 +++++++++++++++++++++++++++---
 1 file changed, 27 insertions(+), 3 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index b95ffdb14417..650baa09fcb5 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -202,6 +202,9 @@ static int apply_range_set_cb(pte_t *pte, unsigned long addr, void *data)
 		return -EBUSY;
 	set_pte_at(&init_mm, addr, pte, pteval);
 #endif
+	page_folio(page)->index = compute_pgoff(d->arena,
+						addr - bpf_arena_get_kern_vm_start(d->arena));
+	page->mapping = d->arena->file->f_mapping;
 	WARN_ON_ONCE(llist_del_first(d->pages) != node);
 	d->i++;
 	WRITE_ONCE(d->arena->nr_pages, d->arena->nr_pages + 1);
@@ -272,6 +275,17 @@ static int populate_pgtable_except_pte(struct bpf_arena *arena)
 /* The backing file must not hold a map reference. */
 static const struct file_operations arena_backing_fops = {};
 
+/* Arena pages are not page-cache entries and must not be evicted by MM. */
+static bool arena_release_folio(struct folio *folio, gfp_t gfp)
+{
+	return false;
+}
+
+static const struct address_space_operations arena_aops = {
+	.dirty_folio = noop_dirty_folio,
+	.release_folio = arena_release_folio,
+};
+
 static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
 {
 	struct vm_struct *kern_vm;
@@ -341,6 +355,8 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
 		err = PTR_ERR(arena->file);
 		goto err_destroy_rt;
 	}
+	arena->file->f_mapping->a_ops = &arena_aops;
+	mapping_set_release_always(arena->file->f_mapping);
 
 	return &arena->map;
 
@@ -355,6 +371,14 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
 	return ERR_PTR(err);
 }
 
+static void arena_put_page(struct page *page)
+{
+	lock_page(page);
+	page->mapping = NULL;
+	unlock_page(page);
+	__free_page(page);
+}
+
 static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data)
 {
 	struct bpf_arena *arena = data;
@@ -378,7 +402,7 @@ static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data)
 	 * the TLB entries can stick around and continue to permit access to
 	 * the freed page. So it all relies on 1.
 	 */
-	__free_page(page);
+	arena_put_page(page);
 	return 0;
 }
 
@@ -939,7 +963,7 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 			 * page_cnt is big it's faster to do the batched zap.
 			 */
 			zap_pages(arena, full_uaddr, 1);
-		__free_page(page);
+		arena_put_page(page);
 	}
 	bpf_map_memcg_exit(old_memcg, new_memcg);
 
@@ -1061,7 +1085,7 @@ static void arena_free_worker(struct work_struct *work)
 	/* free all pages collected by apply_to_existing_page_range() in the first loop */
 	llist_for_each_safe(pos, t, __llist_del_all(&free_pages)) {
 		page = llist_entry(pos, struct page, pcp_llist);
-		__free_page(page);
+		arena_put_page(page);
 	}
 
 	bpf_map_memcg_exit(old_memcg, new_memcg);
-- 
2.52.0

Re: [PATCH bpf-next v4 2/8] bpf: Associate arena pages with their mapping

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: sleeping lock_page() called under PTL spinlock in existing_page_cb()
--

commit 06bc77555d3cf904ccf154edab307819785c3c2b
Author: Emil Tsalapatis <emil@etsalapatis.com>
Subject: bpf: Associate arena pages with their mapping

This commit associates arena backing pages with the arena's private mapping
and sets their page offsets. This allows the fault handler to delegate user
PTE installation to generic MM code, helping avoid races with kfunc-related
arena operations.

> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> index b95ffdb14417a..650baa09fcb5a 100644
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c
[ ... ]
> @@ -355,6 +371,14 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
>  	return ERR_PTR(err);
>  }
>  
> +static void arena_put_page(struct page *page)
> +{
> +	lock_page(page);
> +	page->mapping = NULL;
> +	unlock_page(page);
> +	__free_page(page);
> +}
> +
>  static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data)
>  {
>  	struct bpf_arena *arena = data;
> @@ -378,7 +402,7 @@ static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data)
>  	 * the TLB entries can stick around and continue to permit access to
>  	 * the freed page. So it all relies on 1.
>  	 */
> -	__free_page(page);
> +	arena_put_page(page);

[Severity: High]
Does this code call a sleepable function under a spinlock?

existing_page_cb() is passed as a callback to apply_to_existing_page_range()
during map destruction. The MM core function apply_to_pte_range() acquires
the Page Table Lock (PTL) spinlock via pte_offset_map_lock() before
iterating over PTEs and invoking the callback.

The new arena_put_page() function calls lock_page(), which contains a
might_sleep() check and waits on a bitlock that can sleep.

Sleeping while holding the PTL spinlock will lead to a 'scheduling while
atomic' panic or deadlock.

>  	return 0;
>  }

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

[PATCH bpf-next v4 3/8] bpf: arena: Stop deferred frees before map teardown

[Emil Tsalapatis]

arena_free_worker() requeues itself when acquiring the arena spinlock
fails. arena_map_free() uses flush_work(), which only waits for the
queueing instance being flushed. If the worker requeues itself during
the flush, a later invocation can access the arena after it is freed.

No external callers remain at map teardown. Synchronize the IRQ work
first, then disable and synchronously cancel the worker. This waits for
a running callback to finish and prevents it from queueing another
invocation.

Fixes: b8467290edab ("bpf: arena: make arena kfuncs any context safe")
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 kernel/bpf/arena.c | 15 +++++++++++++--
 1 file changed, 13 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 650baa09fcb5..64a9001ecd68 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -409,6 +409,8 @@ static int existing_page_cb(pte_t *ptep, unsigned long addr, void *data)
 static void arena_map_free(struct bpf_map *map)
 {
 	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
+	struct llist_node *pos, *next;
+	struct arena_free_span *s;
 
 	/*
 	 * Check that user vma-s are not around when bpf map is freed.
@@ -419,9 +421,18 @@ static void arena_map_free(struct bpf_map *map)
 	if (WARN_ON_ONCE(!list_empty(&arena->vma_list)))
 		return;
 
-	/* Ensure no pending deferred frees */
+	/*
+	 * No callers remain. Drain the IRQ callback, then stop the worker,
+	 * including any attempts to requeue itself during teardown.
+	 */
 	irq_work_sync(&arena->free_irq);
-	flush_work(&arena->free_work);
+	disable_work_sync(&arena->free_work);
+
+	/* Remaining mapped pages are reclaimed by the page-table walk below. */
+	llist_for_each_safe(pos, next, llist_del_all(&arena->free_spans)) {
+		s = llist_entry(pos, struct arena_free_span, node);
+		kfree_nolock(s);
+	}
 
 	/*
 	 * free_vm_area() calls remove_vm_area() that calls free_unmap_vmap_area().
-- 
2.52.0

[PATCH bpf-next v4 4/8] bpf: Update is_range_tree_set to work for consecutive ranges

[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 2460e78d6a55..46e2dd01a353 100644
--- a/kernel/bpf/range_tree.c
+++ b/kernel/bpf/range_tree.c
@@ -186,12 +186,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

[PATCH bpf-next v4 5/8] bpf: Track availability information for ranges in range tree

[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 | 220 ++++++++++++++++++++++++++++++++++------
 kernel/bpf/range_tree.h |   7 +-
 3 files changed, 199 insertions(+), 38 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 64a9001ecd68..83106eed99f3 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -340,7 +340,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);
@@ -612,7 +612,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) {
 		llist_del_first(&pages);
-		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;
 	}
@@ -870,7 +870,7 @@ static long arena_alloc_pages(struct bpf_arena *arena, long uaddr, long page_cnt
 out_unmap:
 	/* Error handling: Undo partial mappings. */
 	flush_vmap_cache(kern_vm_start + uaddr32, mapped << PAGE_SHIFT);
-	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)
 		arena_free_pages(arena, uaddr32, mapped, sleepable);
@@ -946,7 +946,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;
@@ -1073,7 +1073,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 46e2dd01a353..e46f3467c3a2 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"
 
 /*
@@ -39,8 +40,29 @@ 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)
+{
+	/* 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)
 {
 	return rb_entry(rb, struct range_node, rb_range_size);
@@ -55,20 +77,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 +167,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;
@@ -159,6 +200,7 @@ int range_tree_clear(struct range_tree *rt, u32 start, u32 len)
 			range_it_insert(rn, rt);
 
 			/* Add right-half range */
+			new_rn->available = rn->available;
 			new_rn->rn_start = last + 1;
 			new_rn->rn_last = old_last;
 			range_it_insert(new_rn, rt);
@@ -205,57 +247,153 @@ 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 *new_rn = NULL;
 	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;
+	/* Do we have a left-adjacent range ? */
+	left = start ? range_it_iter_first(rt, start - 1, start - 1) : NULL;
+	if (left && left->rn_last != start - 1)
+		return -EFAULT;
 
-	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;
-	}
+	/* Do we have a right-adjacent range ? */
+	right = last != U32_MAX ? range_it_iter_first(rt, last + 1, last + 1) : NULL;
+	if (right && right->rn_start != last + 1)
+		return -EFAULT;
 
-	/* Clear out everything in the range we want to set. */
-	err = range_tree_clear(rt, start, len);
-	if (err)
-		goto out_free_new;
+	*leftp = left;
+	*rightp = right;
+
+	return 0;
+}
 
-	if (left && right) {
+/*
+ * 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 {
-		/* No adjacent ranges; use the pre-allocated node */
-		new_rn->rn_start = start;
-		new_rn->rn_last = last;
-		range_it_insert(new_rn, 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, struct range_node **new_rnp)
+{
+	u32 last = start + len - 1;
+	struct range_node *new_rn = NULL;
+	struct range_node *right;
+	struct range_node *left;
+	int err;
+
+	/* Already available: nothing to change. */
+	left = range_it_iter_first(rt, start, last);
+	if (available && range_available(left) &&
+	    left->rn_start <= start && left->rn_last >= last)
+		return 0;
+
+	/* Predict whether insertion needs a new node before clearing. */
+	left = start ? range_it_iter_first(rt, start - 1, start - 1) : NULL;
+	right = last != U32_MAX ? range_it_iter_first(rt, last + 1, last + 1) : NULL;
+
+	/* Unavailable ranges cannot merge. Allocate before changing the tree. */
+	if (!available ||
+	    (!range_available(left) && !range_available(right))) {
+		new_rn = kmalloc_nolock(sizeof(*new_rn), __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)
+		goto out_free_new;
+
+	/* Recompute adjacency: clearing may have trimmed or split nodes. */
+	err = range_get_adjacent(rt, start, last, &left, &right);
+	if (err)
+		goto out_free_new;
+
+	if (available &&
+	    (range_available(left) || range_available(right))) {
+		err = range_tree_merge(rt, start, last, left, right);
+		goto out_free_new;
+	}
+
+	/* No merge possible; transfer the reserved node to the tree. */
+	new_rn->available = available;
+	new_rn->rn_start = start;
+	new_rn->rn_last = last;
+	range_it_insert(new_rn, rt);
+	if (new_rnp)
+		*new_rnp = new_rn;
+
 	return 0;
 
 out_free_new:
@@ -263,6 +401,24 @@ int range_tree_set(struct range_tree *rt, u32 start, u32 len)
 	return err;
 }
 
+int range_tree_set_avail(struct range_tree *rt, u32 start, u32 len)
+{
+	return range_tree_set(rt, start, len, true, NULL);
+}
+
+struct range_node *range_tree_set_unavail(struct range_tree *rt, u32 start, u32 len)
+{
+	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)
 {
 	struct range_node *rn;
diff --git a/kernel/bpf/range_tree.h b/kernel/bpf/range_tree.h
index ff0b9110eb71..4f9ea2acea29 100644
--- a/kernel/bpf/range_tree.h
+++ b/kernel/bpf/range_tree.h
@@ -10,11 +10,16 @@ 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(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_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

[PATCH bpf-next v4 6/8] bpf: Fix arena race between page free and alloc leading to incoherency

[Emil Tsalapatis]

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.

For faults without FAULT_FLAG_ALLOW_RETRY, return VM_FAULT_NOPAGE
on an unavailable range so GUP can recheck the PTE while retaining
mmap_lock.

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 | 189 +++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 176 insertions(+), 13 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 83106eed99f3..07e19f406ceb 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
 #include <linux/anon_inodes.h>
+#include <linux/bits.h>
 #include <linux/bpf.h>
 #include <linux/btf.h>
 #include <linux/cacheflush.h>
@@ -73,10 +74,25 @@ struct bpf_arena {
 static void arena_free_worker(struct work_struct *work);
 static void arena_free_irq(struct irq_work *iw);
 
+/*
+ * Zero flags denote an unstarted free. ZAPPED implies CLEARED, and FAILED
+ * is a terminal pre-clear failure set alone. RESERVED tracks ownership
+ * independently of cleanup progress.
+ * Each span has a single owner until it is published on free_spans, so flag
+ * updates do not need atomic bit operations.
+ */
+enum arena_free_span_flags {
+	ARENA_FREE_SPAN_CLEARED = BIT(0),	/* Kernel PTEs cleared */
+	ARENA_FREE_SPAN_ZAPPED = BIT(1),	/* Kernel TLB flushed and user mappings zapped */
+	ARENA_FREE_SPAN_RESERVED = BIT(2),	/* Owns an unavailable range */
+	ARENA_FREE_SPAN_FAILED = BIT(3),	/* Freeing operation cannot continue */
+};
+
 struct arena_free_span {
 	struct llist_node node;
 	unsigned long uaddr;
 	u32 page_cnt;
+	unsigned int flags;
 };
 
 u64 bpf_arena_get_kern_vm_start(struct bpf_arena *arena)
@@ -600,7 +616,16 @@ 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) {
+		/* Non-retryable GUP callers recheck the PTE on NOPAGE. */
+		if (!(vmf->flags & FAULT_FLAG_ALLOW_RETRY)) {
+			fault_ret = VM_FAULT_NOPAGE;
+			goto out_err_locked_memcg;
+		}
+		raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+		goto retry;
+	} else if (ret) {
 		fault_ret = VM_FAULT_SIGBUS;
 		goto out_err_locked_memcg;
 	}
@@ -636,6 +661,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 = {
@@ -912,6 +950,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;
@@ -920,6 +959,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 */
@@ -946,7 +986,18 @@ 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)) {
+		raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+
+		/* If overlapping free in progress or out of memory, defer. */
+		ret = PTR_ERR(unavail_node);
+		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;
@@ -976,6 +1027,16 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 			zap_pages(arena, full_uaddr, 1);
 		arena_put_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;
@@ -983,16 +1044,36 @@ 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.
+		 *
+		 * Directly marking the node avialable is safe because unavailable nodes
+		 * are not modified by the range tree code without a reference to the node.
+		 * The unavailable -> available op does not touch anything in the tree apart
+		 * from the node so no need to take the lock.
+		 *
+		 * The downside is fragmentation in the tree, 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.
+		 */
+
 		return;
+	}
 
 	s->page_cnt = page_cnt;
 	s->uaddr = uaddr;
+	s->flags = release_only ? (ARENA_FREE_SPAN_CLEARED |
+				   ARENA_FREE_SPAN_ZAPPED |
+				   ARENA_FREE_SPAN_RESERVED) : 0;
 	llist_add(&s->node, &arena->free_spans);
 	irq_work_queue(&arena->free_irq);
 }
@@ -1041,6 +1122,7 @@ 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 clear_range_data cdata;
@@ -1048,6 +1130,8 @@ static void arena_free_worker(struct work_struct *work)
 	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);
@@ -1063,23 +1147,51 @@ static void arena_free_worker(struct work_struct *work)
 	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);
+		if (s->flags)
+			continue;
+
 		page_cnt = s->page_cnt;
-		kaddr = arena_vm_start + s->uaddr;
 		pgoff = compute_pgoff(arena, s->uaddr);
+		kaddr = arena_vm_start + s->uaddr;
+
+		/*
+		 * Marking the range tree unavailable is required to avoid
+		 * reallocations through, e.g., minor page faults.
+		 */
+		unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
+		if (!IS_ERR(unavail_node)) {
+			s->flags |= ARENA_FREE_SPAN_RESERVED;
+			goto clear_ptes;
+		}
+
+		ret = PTR_ERR(unavail_node);
+		/* Retry without starting teardown. */
+		if (ret == -EAGAIN || ret == -ENOMEM)
+			continue;
+
+		/* Unexpected failures leave pages for map teardown. */
+		WARN_ON_ONCE(ret);
+
+		s->flags = ARENA_FREE_SPAN_FAILED;
+		continue;
 
-		/* clear ptes and collect pages in free_pages llist */
+clear_ptes:
+		/* clear ptes and mark the span as cleared. */
 		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);
+		s->flags |= ARENA_FREE_SPAN_CLEARED;
 	}
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 
-	/* Iterate the list again without holding spinlock to do the tlb flush and zap_pages */
+	/* Remove stale translations before freeing the collected pages. */
 	llist_for_each_safe(pos, t, list) {
 		s = llist_entry(pos, struct arena_free_span, node);
+		if (!(s->flags & ARENA_FREE_SPAN_CLEARED) ||
+		    (s->flags & ARENA_FREE_SPAN_ZAPPED))
+			continue;
+
 		page_cnt = s->page_cnt;
 		full_uaddr = clear_lo32(user_vm_start) + s->uaddr;
 		kaddr = arena_vm_start + s->uaddr;
@@ -1090,7 +1202,11 @@ static void arena_free_worker(struct work_struct *work)
 		/* remove pages from user vmas */
 		zap_pages(arena, full_uaddr, page_cnt);
 
-		kfree_nolock(s);
+		/*
+		 * Used to avoid zapping twice if we fail the lock acquisition
+		 * below and rerun the span through this function.
+		 */
+		s->flags |= ARENA_FREE_SPAN_ZAPPED;
 	}
 
 	/* free all pages collected by apply_to_existing_page_range() in the first loop */
@@ -1099,7 +1215,54 @@ static void arena_free_worker(struct work_struct *work)
 		arena_put_page(page);
 	}
 
+	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);
+
+			/* Only unstarted frees and reserved ranges need a retry. */
+			if (!s->flags || (s->flags & ARENA_FREE_SPAN_RESERVED)) {
+				llist_add(pos, &arena->free_spans);
+				retry = true;
+			} else {
+				kfree_nolock(s);
+			}
+		}
+		goto done;
+	}
+
+	llist_for_each_safe(pos, t, list) {
+		s = llist_entry(pos, struct arena_free_span, node);
+
+		if (s->flags & ARENA_FREE_SPAN_FAILED) {
+			kfree_nolock(s);
+			continue;
+		}
+
+		if (!(s->flags & ARENA_FREE_SPAN_CLEARED)) {
+			llist_add(pos, &arena->free_spans);
+			retry = true;
+			continue;
+		}
+
+		if (s->flags & ARENA_FREE_SPAN_RESERVED) {
+			page_cnt = s->page_cnt;
+			pgoff = compute_pgoff(arena, s->uaddr);
+			/*
+			 * This range tree operation does not allocate memory,
+			 * so failures are actual bugs.
+			 */
+			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);
+
+	if (retry)
+		schedule_work(work);
 }
 
 static void arena_free_irq(struct irq_work *iw)
-- 
2.52.0

[PATCH bpf-next v4 7/8] bpf: Synchronize arena page faults with page freeing

[Emil Tsalapatis]

A fault can obtain page A, then a free/reallocation can replace it with
page B before the fault installs A in the user page table. Userspace
then sees A while BPF sees B. This also affects faults on existing pages.

Prevent the arena VM fault handler from running in parallel with arena free
operations. This is similar to the policy for file-backed mappings. Use a
per-arena reference counter to exclude faults from synchronous and deferred
page teardown, and vice versa. Faults and frees can each run concurrently
with operations of the same type.

Fixes: 317460317a02 ("bpf: Introduce bpf_arena.")
Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 kernel/bpf/arena.c | 123 +++++++++++++++++++++++++++++++++++++--------
 1 file changed, 102 insertions(+), 21 deletions(-)

diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
index 07e19f406ceb..899ad275ac7f 100644
--- a/kernel/bpf/arena.c
+++ b/kernel/bpf/arena.c
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0-only
 /* Copyright (c) 2024 Meta Platforms, Inc. and affiliates. */
 #include <linux/anon_inodes.h>
+#include <linux/atomic.h>
 #include <linux/bits.h>
 #include <linux/bpf.h>
 #include <linux/btf.h>
@@ -13,6 +14,7 @@
 #include <linux/btf_ids.h>
 #include <linux/vmalloc.h>
 #include <linux/pagemap.h>
+#include <linux/wait.h>
 #include <asm/tlbflush.h>
 #include "range_tree.h"
 
@@ -61,6 +63,8 @@ struct bpf_arena {
 	struct range_tree rt;
 	/* protects rt and nr_pages */
 	rqspinlock_t spinlock;
+	atomic_t opref;
+	wait_queue_head_t opwait;
 	/* number of pages currently populated in the arena */
 	u64 nr_pages;
 	struct list_head vma_list;
@@ -74,6 +78,29 @@ struct bpf_arena {
 static void arena_free_worker(struct work_struct *work);
 static void arena_free_irq(struct irq_work *iw);
 
+/* Positive references admit frees, negative references admit faults. */
+enum arena_opref {
+	ARENA_OPREF_FREE = 1,
+	ARENA_OPREF_FAULT = -1,
+};
+
+static bool arena_opref_get(struct bpf_arena *arena, enum arena_opref ref)
+{
+	int users = atomic_read(&arena->opref);
+
+	do {
+		if (users && (users ^ ref) < 0)
+			return false;
+	} while (!atomic_try_cmpxchg_acquire(&arena->opref, &users, users + ref));
+	return true;
+}
+
+static void arena_opref_put(struct bpf_arena *arena, enum arena_opref ref)
+{
+	if (atomic_fetch_sub_release(ref, &arena->opref) == ref)
+		wake_up_all(&arena->opwait);
+}
+
 /*
  * Zero flags denote an unstarted free. ZAPPED implies CLEARED, and FAILED
  * is a terminal pre-clear failure set alone. RESERVED tracks ownership
@@ -361,6 +388,8 @@ static struct bpf_map *arena_map_alloc(union bpf_attr *attr)
 		goto err_free_scratch;
 	mutex_init(&arena->lock);
 	raw_res_spin_lock_init(&arena->spinlock);
+	atomic_set(&arena->opref, 0);
+	init_waitqueue_head(&arena->opwait);
 	err = populate_pgtable_except_pte(arena);
 	if (err)
 		goto err_destroy_rt;
@@ -545,13 +574,22 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
 	struct bpf_arena *arena = container_of(map, struct bpf_arena, map);
 	struct mem_cgroup *new_memcg, *old_memcg;
 	LLIST_HEAD(pages);
-	struct page *page, *new_page = NULL;
 	struct apply_range_data data;
 	vm_fault_t fault_ret;
+	struct page *page, *new_page = NULL;
 	long kbase, kaddr;
 	unsigned long flags;
 	int ret;
 
+	if (!arena_opref_get(arena, ARENA_OPREF_FAULT)) {
+		if (vmf->flags & FAULT_FLAG_ALLOW_RETRY)
+			goto retry;
+		/* zap_pages() does not need the fault caller's mmap_lock. */
+		wait_event(arena->opwait, arena_opref_get(arena, ARENA_OPREF_FAULT));
+	}
+	/* folio_lock_or_retry() may drop the VMA lock before we release opref. */
+	bpf_map_inc(map);
+
 	kbase = bpf_arena_get_kern_vm_start(arena);
 	kaddr = kbase + (u32)(vmf->address);
 
@@ -569,15 +607,15 @@ 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) {
+			fault_ret = VM_FAULT_SIGBUS;
+			goto out_err;
+		}
+
+		goto retry_admitted;
 	}
 
 	page = vmalloc_to_page((void *)kaddr);
@@ -605,8 +643,8 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
 
 	if (!new_page) {
 		/*
-		 * The probed page was freed meanwhile or preallocation failed;
-		 * try the non-blocking allocator, we cannot sleep here.
+		 * Preallocation failed; try the non-blocking allocator since
+		 * we cannot sleep here.
 		 */
 		new_page = bpf_alloc_page(map->numa_node, false);
 		if (!new_page) {
@@ -624,7 +662,7 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
 			goto out_err_locked_memcg;
 		}
 		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;
@@ -647,23 +685,42 @@ static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
 	page = new_page;
 	new_page = NULL;
 out:
-	page_ref_add(page, 1);
+	/* Hand fault admission over to the folio lock before returning to MM. */
+	get_page(page);
 	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;
+	}
+
+	fault_ret = folio_lock_or_retry(page_folio(page), vmf);
+	if (fault_ret) {
+		put_page(page);
+	} else {
+		vmf->page = page;
+		fault_ret = VM_FAULT_LOCKED;
+	}
+	goto out_put;
 
 out_err_locked_memcg:
 	bpf_map_memcg_exit(old_memcg, new_memcg);
 out_err_locked:
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
+out_err:
 	if (new_page)
 		free_pages_nolock(new_page, 0);
+out_put:
+	arena_opref_put(arena, ARENA_OPREF_FAULT);
+	bpf_map_put(map);
 	return fault_ret;
 
-retry:
+retry_memcg:
 	bpf_map_memcg_exit(old_memcg, new_memcg);
+retry_admitted:
+	arena_opref_put(arena, ARENA_OPREF_FAULT);
+	bpf_map_put(map);
+retry:
 	if (new_page)
 		free_pages_nolock(new_page, 0);
 
@@ -947,6 +1004,14 @@ static void zap_pages(struct bpf_arena *arena, long uaddr, long page_cnt)
 	i_mmap_unlock_read(mapping);
 }
 
+static void wait_for_faults(struct llist_head *pages)
+{
+	struct page *page;
+
+	llist_for_each_entry(page, pages->first, pcp_llist)
+		folio_wait_locked(page_folio(page));
+}
+
 static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt, bool sleepable)
 {
 	struct mem_cgroup *new_memcg, *old_memcg;
@@ -979,12 +1044,14 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 
 	if (!sleepable)
 		goto defer;
+	if (!arena_opref_get(arena, ARENA_OPREF_FREE))
+		goto defer;
 
 	ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags);
 
 	/* Can't proceed without holding the spinlock so defer the free */
 	if (ret)
-		goto defer;
+		goto defer_admitted;
 
 	unavail_node = range_tree_set_unavail(&arena->rt, pgoff, page_cnt);
 	if (IS_ERR(unavail_node)) {
@@ -993,8 +1060,9 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 		/* If overlapping free in progress or out of memory, defer. */
 		ret = PTR_ERR(unavail_node);
 		if (ret == -ENOMEM || ret == -EAGAIN)
-			goto defer;
+			goto defer_admitted;
 		WARN_ON_ONCE(ret);
+		arena_opref_put(arena, ARENA_OPREF_FREE);
 		bpf_map_memcg_exit(old_memcg, new_memcg);
 		return;
 	}
@@ -1009,6 +1077,8 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 	/* drop the lock to do the tlb flush and zap pages */
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 
+	wait_for_faults(&free_pages);
+
 	/* ensure no stale TLB entries */
 	flush_tlb_kernel_range(kaddr, kaddr + (page_cnt * PAGE_SIZE));
 
@@ -1031,16 +1101,19 @@ static void arena_free_pages(struct bpf_arena *arena, long uaddr, long page_cnt,
 	ret = raw_res_spin_lock_irqsave(&arena->spinlock, flags);
 	if (ret) {
 		release_only = true;
-		goto defer;
+		goto defer_admitted;
 	}
 
 	ret = range_tree_make_avail(&arena->rt, pgoff, page_cnt);
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 	WARN_ON_ONCE(ret);
+	arena_opref_put(arena, ARENA_OPREF_FREE);
 	bpf_map_memcg_exit(old_memcg, new_memcg);
 
 	return;
 
+defer_admitted:
+	arena_opref_put(arena, ARENA_OPREF_FREE);
 defer:
 	s = kmalloc_nolock(sizeof(struct arena_free_span), __GFP_ACCOUNT, -1);
 	bpf_map_memcg_exit(old_memcg, new_memcg);
@@ -1133,7 +1206,12 @@ static void arena_free_worker(struct work_struct *work)
 	bool retry = false;
 	int ret;
 
+	if (!arena_opref_get(arena, ARENA_OPREF_FREE)) {
+		schedule_work(work);
+		return;
+	}
 	if (raw_res_spin_lock_irqsave(&arena->spinlock, flags)) {
+		arena_opref_put(arena, ARENA_OPREF_FREE);
 		schedule_work(work);
 		return;
 	}
@@ -1185,6 +1263,8 @@ static void arena_free_worker(struct work_struct *work)
 	}
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 
+	wait_for_faults(&free_pages);
+
 	/* Remove stale translations before freeing the collected pages. */
 	llist_for_each_safe(pos, t, list) {
 		s = llist_entry(pos, struct arena_free_span, node);
@@ -1259,6 +1339,7 @@ static void arena_free_worker(struct work_struct *work)
 	raw_res_spin_unlock_irqrestore(&arena->spinlock, flags);
 
 done:
+	arena_opref_put(arena, ARENA_OPREF_FREE);
 	bpf_map_memcg_exit(old_memcg, new_memcg);
 
 	if (retry)
-- 
2.52.0

Re: [PATCH bpf-next v4 7/8] bpf: Synchronize arena page faults with page freeing

[bot+bpf-ci]

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

> bpf: Synchronize arena page faults with page freeing

TL;DR:
- Arena faults may busy-loop on VM_FAULT_RETRY while any free runs
- Free worker may requeue itself in a CPU spin while a fault is in flight
- Deferred frees may be dropped if kmalloc_nolock() fails

> diff --git a/kernel/bpf/arena.c b/kernel/bpf/arena.c
> --- a/kernel/bpf/arena.c
> +++ b/kernel/bpf/arena.c

[ ... ]

> +static bool arena_opref_get(struct bpf_arena *arena, enum arena_opref ref)
> +{
> +	int users = atomic_read(&arena->opref);
> +
> +	do {
> +		if (users && (users ^ ref) < 0)
> +			return false;
> +	} while (!atomic_try_cmpxchg_acquire(&arena->opref, &users, users + ref));
> +	return true;
> +}
> +
> +static void arena_opref_put(struct bpf_arena *arena, enum arena_opref ref)
> +{
> +	if (atomic_fetch_sub_release(ref, &arena->opref) == ref)
> +		wake_up_all(&arena->opwait);
> +}

[ ... ]

> @@ -542,19 +571,28 @@ static void arena_vm_close(struct vm_area_struct *vma)
>  static vm_fault_t arena_vm_fault(struct vm_fault *vmf)
>  {
[ ... ]
> +	if (!arena_opref_get(arena, ARENA_OPREF_FAULT)) {
> +		if (vmf->flags & FAULT_FLAG_ALLOW_RETRY)
> +			goto retry;
> +		/* zap_pages() does not need the fault caller's mmap_lock. */
> +		wait_event(arena->opwait, arena_opref_get(arena, ARENA_OPREF_FAULT));
> +	}

When a free currently holds ARENA_OPREF_FREE and FAULT_FLAG_ALLOW_RETRY is
set, this jumps to retry: which calls release_fault_lock() and returns
VM_FAULT_RETRY without waiting for the free to finish.  Can this turn into
a busy loop in the faulting thread?

The test is on FAULT_FLAG_ALLOW_RETRY rather than
fault_flag_allow_retry_first(), and the arch fault handlers keep
FAULT_FLAG_ALLOW_RETRY set when they add FAULT_FLAG_TRIED.  On x86,
do_user_addr_fault() does:

    if (unlikely(fault & VM_FAULT_RETRY)) {
        flags |= FAULT_FLAG_TRIED;
        goto retry;
    }

so the retried attempt reaches the same check, fails arena_opref_get()
again, and returns VM_FAULT_RETRY again:

    lock_mm_and_find_vma()
      handle_mm_fault()
        __do_fault()    (also allocates and frees a prealloc PTE page
                         when the PMD is empty)
          arena_vm_fault()
            mmap_read_unlock()
            goto retry

The thread spins in kernel mode for as long as a free holds
ARENA_OPREF_FREE.  A free can hold it across work that sleeps or runs long:

    wait_for_faults() -> folio_wait_locked()
    zap_pages() -> i_mmap_lock_read() and zap_vma_range(), over up to the
                   whole 4 GiB arena
    arena_put_page() -> lock_page(), for every freed page

Before this patch a fault only took the busy -EAGAIN path when it hit a page
inside the range being freed.  With this patch, a fault anywhere in the
arena spins while any free is running.  Every arch with arena JIT support
selects PREEMPT_LAZY, so tick preemption bounds the spin and it is not a
permanent hang, but it is still an unbounded busy wait.

The usual MM convention (see __folio_lock_or_retry()) is to drop the fault
lock, sleep until the condition can be met, and then return VM_FAULT_RETRY
on the first attempt, blocking on the FAULT_FLAG_TRIED attempt.  The opwait
waitqueue added here would allow that, for example:

    release_fault_lock(vmf);
    wait_event(arena->opwait, atomic_read(&arena->opref) <= 0);
    return VM_FAULT_RETRY;

with the existing wait_event() kept for the !fault_flag_allow_retry_first()
case.  Would something like that work?

The existing non-retry wait_event() is also TASK_UNINTERRUPTIBLE with
mmap_read_lock held, and it is woken only when the count returns to exactly
0.  If frees keep overlapping, can the waiter be held off indefinitely?

[ ... ]

> @@ -1130,13 +1203,18 @@ static void arena_free_worker(struct work_struct *work)
[ ... ]
> +	if (!arena_opref_get(arena, ARENA_OPREF_FREE)) {
> +		schedule_work(work);
> +		return;
> +	}

The same busy polling happens in the other direction here.  When a fault
holds ARENA_OPREF_FAULT, arena_free_worker() requeues itself immediately.
The work item clears its pending bit before running, so schedule_work()
always succeeds and the kworker re-runs back to back until the fault count
drops to zero.

Faults can hold that reference for a long time.  arena_vm_fault() takes it
before the preallocation:

    if (!arena_opref_get(arena, ARENA_OPREF_FAULT)) { ... }
    ...
    new_page = alloc_pages_node(map->numa_node,
                                GFP_KERNEL | __GFP_ZERO |
                                __GFP_ACCOUNT | __GFP_NOWARN |
                                __GFP_RETRY_MAYFAIL, 0);

and holds it until after folio_lock_or_retry(), which may sleep in
__folio_lock_or_retry() -> folio_wait_locked{,_killable}().  The
GFP_KERNEL | __GFP_ACCOUNT allocation can enter direct or memcg reclaim, and
when the cgroup is over memory.high, try_charge_memcg() can call
__mem_cgroup_handle_over_high(), which sleeps for up to
MEMCG_MAX_HIGH_DELAY_JIFFIES (2*HZ) in schedule_timeout_killable().  For
that whole time the free worker polls at full CPU on a system_wq worker.

All non-sleepable frees take this path:

    bpf_arena_free_pages_non_sleepable()
      arena_free_pages(..., false)
        irq_work -> arena_free_irq() -> schedule_work()

and so does every sleepable free that sees a fault in flight, because of
this check in arena_free_pages():

    if (!arena_opref_get(arena, ARENA_OPREF_FREE))
            goto defer;

So under memory pressure, when releasing arena memory matters most, are
frees postponed while a CPU spins?  Before this patch the worker requeued
only on an rqspinlock failure or when a range overlapped another free.

A related side effect: sleepable frees that used to complete synchronously
now go to the defer path whenever any fault is in flight.  If
kmalloc_nolock() fails there, does the free get silently dropped, leaving the
pages allocated until the arena is destroyed?

arena_opref_put() already calls wake_up_all(&arena->opwait) when the fault
count goes from -1 to 0, but no free-side path waits on opwait, so that
wakeup has no consumer.  Could the worker, which already sleeps in
wait_for_faults(), zap_pages() and lock_page(), instead do:

    wait_event(arena->opwait, arena_opref_get(arena, ARENA_OPREF_FREE));

Alternatively, could the fault take its admission only after the sleeping
preallocation?


---
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/38657686181

[PATCH bpf-next v4 8/8] selftests/bpf: Add arena allocation race tests

[Emil Tsalapatis]

Add selftests for arena allocation, teardown and fault races.

Cover unavailable ranges and kernel/user mapping coherence during
synchronous and deferred frees and concurrent faults.

Signed-off-by: Emil Tsalapatis <emil@etsalapatis.com>
---
 .../selftests/bpf/prog_tests/arena_race.c     | 285 ++++++++++++++++++
 .../testing/selftests/bpf/progs/arena_race.c  | 159 ++++++++++
 2 files changed, 444 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..301f4dff28f9
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/arena_race.c
@@ -0,0 +1,285 @@
+// 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;
+	__u64 *addr;
+
+	while (!READ_ONCE(ctx->stop)) {
+		addr = __atomic_load_n(&ctx->addr, __ATOMIC_ACQUIRE);
+		(void)READ_ONCE(*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);
+
+		/* Keep deferred frees from earlier iterations on separate slots. */
+		if (i) {
+			skel->bss->page_idx = i;
+			if (run_prog(skel->progs.alloc_old, "alloc_next"))
+				goto out;
+			addr = (__u64 *)(unsigned long)skel->bss->ptr;
+			__atomic_store_n(&fault.addr, addr, __ATOMIC_RELEASE);
+		}
+
+		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;
+		}
+		/* The reader may populate the slot first, or free may defer. */
+		if (!skel->bss->realloc_ptr)
+			continue;
+		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..6d1675ba2395
--- /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, 1024);
+#ifdef __TARGET_ARCH_arm64
+	__ulong(map_extra, 0x1ull << 32);
+#else
+	__ulong(map_extra, 0x1ull << 44);
+#endif
+} arena SEC(".maps");
+
+bool skip;
+int page_idx;
+
+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_idx + 1) * __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)
+		return 0;
+	ptr = realloc_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

Re: [PATCH bpf-next v4 8/8] selftests/bpf: Add arena allocation race tests

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Critical] bpf: bpf_alloc_page() leaks uninitialized kernel memory to user space
--

commit 367216c19f195164e634a02e469d1a5439a1941c
Author: Emil Tsalapatis <emil@etsalapatis.com>

    selftests/bpf: Add arena allocation race tests
    
    Add selftests for arena allocation, teardown and fault races.

>     Cover unavailable ranges and kernel/user mapping coherence during
>     synchronous and deferred frees and concurrent faults.

[Severity: Critical]
While testing concurrent faults, does the allocation fallback path leak
uninitialized kernel memory to user space?

Looking at kernel/bpf/syscall.c:bpf_alloc_page(), it omits the __GFP_ZERO flag
on the fallback path:

	if (!sleepable || !can_alloc_pages())
		return alloc_pages_nolock(__GFP_ACCOUNT, nid, 0);

When preallocation fails in kernel/bpf/arena.c:arena_vm_fault(), the fault
handler falls back to the non-sleepable allocator:

	new_page = bpf_alloc_page(map->numa_node, false);

When sleepable preallocation fails due to memory pressure, or when a
non-sleepable BPF program allocates arena pages, the non-sleepable allocator
returns an uninitialized page.

Since the BPF arena is memory-mapped into user space, this allows
unprivileged users to read stale physical memory contents. Furthermore, on
PREEMPT_RT kernels, can_alloc_pages() is always false, so every arena
allocation unconditionally leaks uninitialized memory.

Also, regarding the behavior of concurrent faults, transiently missing pages
appear to correctly return VM_FAULT_NOPAGE or trigger a retry rather than
causing a fatal signal. In kernel/bpf/arena.c:arena_vm_fault():

	if (ret == -EAGAIN) {
		/* Non-retryable GUP callers recheck the PTE on NOPAGE. */
		if (!(vmf->flags & FAULT_FLAG_ALLOW_RETRY)) {
			fault_ret = VM_FAULT_NOPAGE;
			goto out_err_locked_memcg;
		}

Is the premise that concurrent faults cause a SIGBUS crash inaccurate?

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