Skip to contentSkip to conversation

bpf: Support bpf_rcu_head in hash and LRU hash maps

PATCH In review Puranjay Mohan 4 participants 7 messages Sep 24 – Sep 25

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover bpf: Support bpf_rcu_head in hash and LRU hash maps

bpf_call_rcu() currently only takes a bpf_rcu_head in an array, because an array element is never freed while the map is alive. Hash elements are recycled, and an RCU callback cannot be cancelled, so a delete racing a queued callback would hand the element back to the allocator underneath it.

This keeps the element alive until the callback has run. The map claims the head before releasing an element; if a callback is queued or running, the element is unlinked but not returned to the allocator, and the callback returns it through a new map_release_elem(). Patch 1 also covers the two places a hash recycles an element without freeing it: the per-CPU spare a preallocated htab uses on update, and LRU eviction.

Patch 2 adds tests for the delete, replace, recycle and eviction paths. Each was checked against a kernel with the corresponding hunk reverted.

Puranjay Mohan (2):
bpf: Support bpf_rcu_head in hash and LRU hash maps selftests/bpf: Add bpf_call_rcu tests for hash and LRU hash maps

 include/linux/bpf.h                           |   5 +
 kernel/bpf/hashtab.c                          | 104 ++++++-
 kernel/bpf/helpers.c                          | 117 +++++++-
 kernel/bpf/syscall.c                          |  14 +-
 .../selftests/bpf/prog_tests/call_rcu.c       | 254 +++++++++++++++-
 tools/testing/selftests/bpf/progs/call_rcu.c  | 274 ++++++++++++++++++
 6 files changed, 740 insertions(+), 28 deletions(-)

base-commit: 4f3a5eae895b9995e93425a75235d8f1f3268caa

Signature · 1 line
2.53.0-Meta
#1 lore raw

PATCH 1/2 bpf: Support bpf_rcu_head in hash and LRU hash maps

bpf_call_rcu() is restricted to arrays because an array element is never freed while the map is alive. Hash elements are recycled, and an RCU callback cannot be cancelled, so a delete racing a queued callback would hand the element back to the allocator underneath it.

Keep the element alive until the callback has run. Before releasing an element the map calls bpf_rcu_head_claim(), which marks the head dead and reports whether a callback is queued or running. If one is, the element is unlinked but not returned to the allocator; the callback does that through a new map_release_elem(), since only the map knows whether that is a freelist push or bpf_mem_cache_free(). The dead bit stops it being armed again, so there is a definite last callback. Timers and friends in the same value are still cancelled on delete.

The head and the element are busy for different spans: RCU dequeues a head before invoking it, so it can be re-armed from inside the callback, while the element has to live until the callback returns. ARMED covers the head, RUNNING the element, and whoever clears the last of the two releases a dead element. RUNNING is dropped under the read locks, so only one callback runs on a head at a time.

The dead bit lives in the element, so alloc_htab_elem() and prealloc_lru_pop() reset the head when they hand one out.

A preallocated htab stashes the old element in a per-CPU spare on update rather than freeing it, which cannot be done to one with a queued callback, so maps carrying a head take the freelist path instead.

For LRU the eviction path asks bpf_rcu_head_busy() and declines, leaving the element in the map.

---
 include/linux/bpf.h  |   5 ++
 kernel/bpf/hashtab.c | 104 +++++++++++++++++++++++++++++++++-----
 kernel/bpf/helpers.c | 117 ++++++++++++++++++++++++++++++++++++++-----
 kernel/bpf/syscall.c |  14 +++++-
 4 files changed, 214 insertions(+), 26 deletions(-)
include/linux/bpf.h +5 -0
index 1e1ce2afe2ed8..91eee1d066a32 100644
@@ -111,6 +111,8 @@ struct bpf_map_ops {
 	void *(*map_lookup_elem)(struct bpf_map *map, void *key);
 	long (*map_update_elem)(struct bpf_map *map, void *key, void *value, u64 flags);
 	long (*map_delete_elem)(struct bpf_map *map, void *key);
+	/* Release an element a bpf_rcu_head callback was holding. */
+	void (*map_release_elem)(struct bpf_map *map, void *value);
 	long (*map_push_elem)(struct bpf_map *map, void *value, u64 flags);
 	long (*map_pop_elem)(struct bpf_map *map, void *value);
 	long (*map_peek_elem)(struct bpf_map *map, void *value);
@@ -665,6 +667,9 @@ void copy_map_value_locked(struct bpf_map *map, void *dst, void *src,
 void bpf_timer_cancel_and_free(void *timer);
 void bpf_wq_cancel_and_free(void *timer);
 void bpf_task_work_cancel_and_free(void *timer);
+bool bpf_rcu_head_claim(struct bpf_map *map, void *value);
+bool bpf_rcu_head_busy(struct bpf_map *map, void *value);
+void bpf_rcu_head_reset(struct bpf_map *map, void *value);
 void bpf_list_head_free(const struct btf_field *field, void *list_head,
 			struct bpf_spin_lock *spin_lock);
 void bpf_rb_root_free(const struct btf_field *field, void *rb_root,
kernel/bpf/hashtab.c +92 -12

202 lines not on this page · raw message

kernel/bpf/helpers.c +104 -13

175 lines not on this page · raw message

kernel/bpf/syscall.c +13 -1
index 74496fd716d3b..10c6575c53cee 100644
@@ -1326,7 +1326,19 @@ static int map_check_btf(struct bpf_map *map, struct bpf_token *token,
 				}
 				break;
 			case BPF_RCU_HEAD:
-				if (map->map_type != BPF_MAP_TYPE_ARRAY) {
+				if (map->map_type != BPF_MAP_TYPE_HASH &&
+				    map->map_type != BPF_MAP_TYPE_LRU_HASH &&
+				    map->map_type != BPF_MAP_TYPE_ARRAY) {
+					ret = -EOPNOTSUPP;
+					goto free_map_tab;
+				}
+				/*
+				 * Array elements are never released, so they are never
+				 * claimed either. Any other map has to be able to take
+				 * one back from a callback.
+				 */
+				if (map->map_type != BPF_MAP_TYPE_ARRAY &&
+				    !map->ops->map_release_elem) {
 					ret = -EOPNOTSUPP;
 					goto free_map_tab;
 				}
Signature · 1 line
2.53.0-Meta
#2 lore raw
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [High] bpf: preallocated hash map loses per-cpu spare causing update failure - [Medium] bpf: LRU eviction…

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] bpf: preallocated hash map loses per-cpu spare causing update failure
- [Medium] bpf: LRU eviction fails to cancel timers immediately for RCU claimed elements --

commit 48e7d59b1040d1c559a2c8cba927c93eb44f710e
Author: Puranjay Mohan <[email protected]>

bpf: Support bpf_rcu_head in hash and LRU hash maps

This commit introduces bpf_rcu_head support for hash and LRU hash maps, allowing map elements with RCU callbacks to be handled appropriately on deletion. Elements are kept alive until the callback completes, with the dead bit stopping further arming.

Quoted 16 lines
kernel/bpf/hashtab.c +0 -3
index f744a42bb8139..5e2f4cbe9d0f2 100644
@@ -914,15 +925,24 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
 	hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
 		if (l == tgt_l) {
 			hlist_nulls_del_rcu(&l->hash_node);
-			bpf_map_dec_elem_count(&htab->map);
 			break;
 		}
 
 	htab_unlock_bucket(b, flags);
 
-	if (l == tgt_l)
-		check_and_cancel_fields(htab, l);

kernel/bpf/hashtab.c static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node) · line 941

Quoted 10 lines
kernel/bpf/hashtab.c +9 -1
-	return l == tgt_l;
+	if (l != tgt_l)
+		return false;
+
+	/*
+	 * An arm can land after the check above. The element is already unlinked
+	 * by now, so map_release_elem() finishes the handoff to the free list.
+	 */
+	if (bpf_rcu_head_claim(&htab->map, htab_elem_value(l, htab->map.key_size)))
+		return false;

[Severity: Medium]
When an element is claimed by an RCU callback, htab_lru_map_delete_node() returns early and skips check_and_cancel_fields(). Does this leave timers and other special fields active after logical deletion?

The commit message mentions that timers and friends in the same value are still cancelled on delete, but they appear to remain active here and could fire during the RCU grace period.

Quoted 5 lines
kernel/bpf/hashtab.c +4 -0
+
+	bpf_map_dec_elem_count(&htab->map);
+	check_and_cancel_fields(htab, l);
+	return true;
 }

[ ... ]

Quoted 8 lines
kernel/bpf/hashtab.c +1 -3
@@ -1129,9 +1179,18 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 			struct pcpu_freelist_node *l;
 
 			l = __pcpu_freelist_pop(&htab->freelist);
-			if (!l)
-				return ERR_PTR(-E2BIG);
-			l_new = container_of(l, struct htab_elem, fnode);
+			if (l) {

kernel/bpf/hashtab.c static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, · line 1192

Quoted 10 lines
kernel/bpf/hashtab.c +10 -0
+				l_new = container_of(l, struct htab_elem, fnode);
+			} else {
+				/* Spend the spare; freeing old_elem refills the freelist. */
+				if (!old_elem)
+					return ERR_PTR(-E2BIG);
+				pl_new = this_cpu_ptr(htab->extra_elems);
+				l_new = *pl_new;
+				if (!l_new)
+					return ERR_PTR(-E2BIG);
+				*pl_new = NULL;

[Severity: High]
By setting the per-CPU spare *pl_new = NULL and later pushing the replaced element into the global freelist, is the per-CPU spare permanently lost?

Once all CPUs lose their spares and the map is full, could updating an existing element fail with -E2BIG?

Quoted 4 lines
kernel/bpf/hashtab.c +1 -0
+			}
 			bpf_map_inc_elem_count(&htab->map);
 		}
 	} else {
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
#3 lore raw
In reply to Puranjay Mohan
When htab_lru_map_delete_node() returns false for a busy element, can the LRU force-shrink loop scan the whole list with IRQs disabled?
Quoted 13 lines
include/linux/bpf.h +2 -0
index 8594c8aff745..afdf22cf5a7a 100644
@@ -111,6 +111,8 @@ struct bpf_map_ops {
 	void *(*map_lookup_elem)(struct bpf_map *map, void *key);
 	long (*map_update_elem)(struct bpf_map *map, void *key, void *value, u64 flags);
 	long (*map_delete_elem)(struct bpf_map *map, void *key);
+	/* Release an element a bpf_rcu_head callback was holding. */
+	void (*map_release_elem)(struct bpf_map *map, void *value);
 	long (*map_push_elem)(struct bpf_map *map, void *value, u64 flags);
 	long (*map_pop_elem)(struct bpf_map *map, void *value);
 	long (*map_peek_elem)(struct bpf_map *map, void *value);

[ ... ]

Quoted 4 lines
kernel/bpf/hashtab.c +0 -0
index 53c99fe4f176..b5555b43147d 100644

[ ... ]

Quoted 29 lines
kernel/bpf/hashtab.c +9 -4
@@ -904,6 +910,11 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
 	int ret;
 
 	tgt_l = container_of(node, struct htab_elem, lru_node);
+
+	/* An element a callback still needs cannot be evicted. */
+	if (bpf_rcu_head_busy(&htab->map, htab_elem_value(tgt_l, htab->map.key_size)))
+		return false;
+
 	b = __select_bucket(htab, tgt_l->hash);
 	head = &b->head;
 
@@ -914,15 +925,24 @@ static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node)
 	hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
 		if (l == tgt_l) {
 			hlist_nulls_del_rcu(&l->hash_node);
-			bpf_map_dec_elem_count(&htab->map);
 			break;
 		}
 
 	htab_unlock_bucket(b, flags);
 
-	if (l == tgt_l)
-		check_and_cancel_fields(htab, l);
-	return l == tgt_l;
+	if (l != tgt_l)
+		return false;
+
+	/*

kernel/bpf/hashtab.c static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node) · line 946

Quoted 10 lines
kernel/bpf/hashtab.c +9 -0
+	 * An arm can land after the check above. The element is already unlinked
+	 * by now, so map_release_elem() finishes the handoff to the free list.
+	 */
+	if (bpf_rcu_head_claim(&htab->map, htab_elem_value(l, htab->map.key_size)))
+		return false;
+
+	bpf_map_dec_elem_count(&htab->map);
+	check_and_cancel_fields(htab, l);
+	return true;
 }

When htab_lru_map_delete_node() returns false for a busy element, can the LRU force-shrink loop scan the whole list with IRQs disabled?

Looking at __bpf_lru_list_shrink() in kernel/bpf/bpf_lru_list.c, the force_shrink_list walk is not bounded by nr_scans:

    list_for_each_entry_safe_reverse(node, tmp_node, force_shrink_list,
                                     list) {
            if (READ_ONCE(node->pending_free) ||
                lru->del_from_htab(lru->del_arg, node)) {
                    __bpf_lru_node_move_to_free(l, node, free_list,
                                                tgt_free_type);
                    return 1;
            }
    }

It runs under raw_res_spin_lock_irqsave(&l->lock), which is either the global LRU list lock in bpf_lru_list_pop_free_to_local() or the per-CPU list lock in bpf_percpu_lru_pop_free().

Before this patch, del_from_htab() almost always succeeded on the first node. Now every busy element returns false and the loop moves on.

The commit message says a callback can be re-armed from inside itself, so elements can stay ARMED or RUNNING indefinitely. If most of the inactive list (or the active list when inactive is empty) is busy, then every LRU insert that needs a free node walks the entire list with IRQs off, up to max_entries nodes.

For large maps, wouldn't this create IRQs-off latency of milliseconds per update from any program context, with waiters potentially hitting rqspinlock timeouts?

[ ... ]

Quoted 39 lines
kernel/bpf/hashtab.c +17 -4
@@ -1110,6 +1149,17 @@ static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab)
 	return is_fd_htab(htab) && BITS_PER_LONG == 64;
 }
 
+/*
+ * On update a preallocated htab stashes the old element in this CPU's spare
+ * instead of freeing it. An element with a queued callback cannot be reused
+ * that way, so those maps release it through free_htab_elem() instead.
+ */
+static bool htab_stashes_old_elem(const struct bpf_htab *htab)
+{
+	return htab_is_prealloc(htab) &&
+	       !btf_record_has_field(htab->map.record, BPF_RCU_HEAD);
+}
+
 static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 					 void *value, u32 key_size, u32 hash,
 					 bool percpu, bool onallcpus,
@@ -1121,7 +1171,7 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 	void __percpu *pptr;
 
 	if (prealloc) {
-		if (old_elem) {
+		if (old_elem && htab_stashes_old_elem(htab)) {
 			/* if we're updating the existing element,
 			 * use per-cpu extra elems to avoid freelist_pop/push
 			 */
@@ -1132,9 +1182,18 @@ static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key,
 			struct pcpu_freelist_node *l;
 
 			l = __pcpu_freelist_pop(&htab->freelist);
-			if (!l)
-				return ERR_PTR(-E2BIG);
-			l_new = container_of(l, struct htab_elem, fnode);
+			if (l) {
+				l_new = container_of(l, struct htab_elem, fnode);
+			} else {
+				/* Spend the spare; freeing old_elem refills the freelist. */
+				if (!old_elem)

kernel/bpf/hashtab.c static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, · line 1199

Quoted 10 lines
kernel/bpf/hashtab.c +7 -0
+					return ERR_PTR(-E2BIG);
+				pl_new = this_cpu_ptr(htab->extra_elems);
+				l_new = *pl_new;
+				if (!l_new)
+					return ERR_PTR(-E2BIG);
+				*pl_new = NULL;
+			}
 			bpf_map_inc_elem_count(&htab->map);
 		}
 	} else {

For preallocated htabs that carry a bpf_rcu_head, once the per-CPU spare is spent, is it ever refilled?

These maps get extra_elems because htab_has_extra_elems() only excludes percpu, LRU and fd maps. prealloc_init() allocates max_entries + num_possible_cpus() elements, and alloc_extra_elems() moves num_possible_cpus() of them into the per-CPU spares, so the freelist holds exactly max_entries.

Before this patch the stash path swapped old_elem with the spare, so the two pools stayed separate and the map never held more than max_entries elements.

With htab_stashes_old_elem() false, the new branch handles the full-map case like this:

1. The map holds max_entries elements and the freelist is empty. An update of an existing key on CPU0 takes the spare (*pl_new = NULL).

2. htab_map_update_elem() calls free_htab_elem(htab, l_old) after unlocking the bucket:

free_htab_elem() -> bpf_rcu_head_claim() -> __free_htab_elem() -> pcpu_freelist_push()

The freelist now has one element, but the spare is still NULL. Nothing refills htab->extra_elems for these maps, since the stash path is the only writer.

3. An insert of a new key pops that freelist element, so the map now holds max_entries + 1 elements. bpf_map_inc_elem_count() counts it as well.

4. Repeating this on every CPU lets the map hold max_entries + num_possible_cpus() live entries.

5. After that, with the freelist empty and this CPU's spare NULL, every BPF_EXIST/BPF_ANY update of an existing key returns -E2BIG. A normal preallocated hash map never fails this way when it is full.

The comment "freeing old_elem refills the freelist" is only half true. It refills the freelist rather than the spare, and when bpf_rcu_head_claim() reports a queued callback it refills nothing until that callback finishes.

Doesn't this violate max_entries, and break replace-in-place once the map is full?

[ ... ]

Quoted 4 lines
kernel/bpf/helpers.c +0 -0
index a284f20c97d5..2b5a5bc98233 100644

[ ... ]

Quoted 28 lines
kernel/bpf/helpers.c +14 -2
@@ -4823,26 +4838,96 @@ static void bpf_rcu_run_callback(struct rcu_head *rcu)
 	struct bpf_prog *prog = rh->prog;
 	struct bpf_map *map = rh->map;
 	void *value, *key;
+	int old, state;
 	u32 idx;
 
 	value = (void *)rh - map->record->rcu_head_off;
 	key = map_key_from_value(map, value, &idx);
 
-	/* Pairs with the arming cmpxchg(): rh may be re-armed as soon as this store lands. */
-	smp_store_release(&rh->armed, 0);
+	/*
+	 * Take RUNNING first, so a claim racing this always sees one of the two.
+	 * rh may be re-armed, and its fields overwritten, once ARMED is dropped.
+	 */
+	old = atomic_fetch_or(RCU_HEAD_RUNNING, &rh->state);
+	WARN_ON_ONCE(old & RCU_HEAD_RUNNING);
+	atomic_andnot(RCU_HEAD_ARMED, &rh->state);
 
+	/*
+	 * Drop RUNNING under the read locks, or a re-arm could be invoked while
+	 * this callback is still on the element. The callback picks the flavour,
+	 * so both locks are needed.
+	 */
+	rcu_read_lock_trace();
 	rcu_read_lock_dont_migrate();
 	callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)value, 0, 0);

kernel/bpf/helpers.c static void bpf_rcu_run_callback(struct rcu_head *rcu) · line 4872

Quoted 10 lines
kernel/bpf/helpers.c +6 -0
+	state = atomic_fetch_andnot(RCU_HEAD_RUNNING, &rh->state) & ~RCU_HEAD_RUNNING;
 	rcu_read_unlock_migrate();
+	rcu_read_unlock_trace();
+
+	/* A live element is never dead, so this only fires after a claim. */
+	if (!(state & RCU_HEAD_BUSY) && (state & RCU_HEAD_DEAD))
+		map->ops->map_release_elem(map, value);
 
 	bpf_prog_put(prog);
 }

A subsystem pattern flags this as potentially concerning:

Hash and LRU hash maps can now carry a bpf_rcu_head. So __bpf_call_rcu() queues call_rcu() / call_rcu_tasks_trace() on an rcu_head embedded in an htab element that is still linked into its bucket's RCU-protected hlist_nulls.

If that element is then deleted while the callback is queued, bpf_rcu_head_claim() sees ARMED and the delete path leaves the release to the callback. bpf_rcu_run_callback() then returns the element to the allocator through map->ops->map_release_elem(map, value).

The grace period it waited for began when the head was armed, which is before the hlist_nulls_del_rcu() in the delete path. A BPF reader that looked the element up after the call_rcu() and before the unlink is therefore not covered by that grace period.

The RCU guide's remove-before-reclaim rule says to call call_rcu() or kfree_rcu() after removing an object from an RCU-protected data structure, not before.

Is the grace period starting before the unlink acceptable under htab's existing element-reuse semantics, or should the deferred release wait for a grace period that starts after the unlink?

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

#4 lore raw
In reply to Puranjay Mohan
Quoted 44 lines · Puranjay Mohan

bpf_call_rcu() is restricted to arrays because an array element is never freed while the map is alive. Hash elements are recycled, and an RCU callback cannot be cancelled, so a delete racing a queued callback would hand the element back to the allocator underneath it.

Keep the element alive until the callback has run. Before releasing an element the map calls bpf_rcu_head_claim(), which marks the head dead and reports whether a callback is queued or running. If one is, the element is unlinked but not returned to the allocator; the callback does that through a new map_release_elem(), since only the map knows whether that is a freelist push or bpf_mem_cache_free(). The dead bit stops it being armed again, so there is a definite last callback. Timers and friends in the same value are still cancelled on delete.

The head and the element are busy for different spans: RCU dequeues a head before invoking it, so it can be re-armed from inside the callback, while the element has to live until the callback returns. ARMED covers the head, RUNNING the element, and whoever clears the last of the two releases a dead element. RUNNING is dropped under the read locks, so only one callback runs on a head at a time.

The dead bit lives in the element, so alloc_htab_elem() and prealloc_lru_pop() reset the head when they hand one out.

A preallocated htab stashes the old element in a per-CPU spare on update rather than freeing it, which cannot be done to one with a queued callback, so maps carrying a head take the freelist path instead.

For LRU the eviction path asks bpf_rcu_head_busy() and declines, leaving the element in the map.

---
 include/linux/bpf.h  |   5 ++
 kernel/bpf/hashtab.c | 104 +++++++++++++++++++++++++++++++++-----
 kernel/bpf/helpers.c | 117 ++++++++++++++++++++++++++++++++++++++-----
 kernel/bpf/syscall.c |  14 +++++-
 4 files changed, 214 insertions(+), 26 deletions(-)
include/linux/bpf.h +0 -0
index 1e1ce2afe2ed8..91eee1d066a32 100644

include/linux/bpf.h struct bpf_map_ops { · line 115

Quoted 5 lines
include/linux/bpf.h +2 -0
@@ -111,6 +111,8 @@ struct bpf_map_ops {
 	void *(*map_lookup_elem)(struct bpf_map *map, void *key);
 	long (*map_update_elem)(struct bpf_map *map, void *key, void *value, u64 flags);
 	long (*map_delete_elem)(struct bpf_map *map, void *key);
+	/* Release an element a bpf_rcu_head callback was holding. */
+	void (*map_release_elem)(struct bpf_map *map, void *value);

This is quite heavy. As you can see both bots poked plenty of holes. I feel this will be nightmarish to support moving forward.

I'd like to hear from Tejun whether he thinks that call_rcu_only_in_array_map is a limitation for what he wanted to do or not.

Instead of supporting in hash map we can support them in bpf_mem_alloced objects instead. Same flexibility. A lot less pain.

pw-bot: cr

#5 lore raw

PATCH 2/2 selftests/bpf: Add bpf_call_rcu tests for hash and LRU hash maps

In reply to Puranjay Mohan

Each of these checks the element a callback was armed on is still the one it runs on, by the value it sees.

hash_delete arms, deletes, then inserts another key, which would be handed the freed element straight back off the freelist. hash_np does the same on a BPF_F_NO_PREALLOC map, which frees to bpf_mem_alloc instead. hash_replace replaces the key twice, which is how a preallocated map recycles through its per-CPU spare. reuse arms an element that has already been deleted and recycled. lru_evict floods a two-entry map and checks the armed element was not evicted. hash_chain checks a re-arm from the callback of a deleted element is refused.

stress hammers arm and delete on overlapping keys from several CPUs and checks every arm ran.

---
 .../selftests/bpf/prog_tests/call_rcu.c       | 254 +++++++++++++++-
 tools/testing/selftests/bpf/progs/call_rcu.c  | 274 ++++++++++++++++++
 2 files changed, 526 insertions(+), 2 deletions(-)
tools/testing/selftests/bpf/prog_tests/call_rcu.c +252 -2
index e4d271d43d878..b60220cdf318c 100644
@@ -1,6 +1,7 @@
 // SPDX-License-Identifier: GPL-2.0
 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
 #include <test_progs.h>
+#include <pthread.h>
 #include "call_rcu.skel.h"
 #include "call_rcu_fail.skel.h"
 
@@ -163,6 +164,158 @@ static void test_call_rcu_teardown(void)
 	call_rcu__destroy(skel);
 }
 
+/*
+ * A hash element armed and then deleted: the element must stay alive until the
+ * callback has run, and the callback must still see its value.
+ */
+static void test_call_rcu_hash_delete(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	struct call_rcu *skel;
+	int i;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arm_hash_then_delete),
+					      &opts), "test_run"))
+		goto out;
+	if (!ASSERT_EQ(opts.retval, 0, "retval") ||
+	    !ASSERT_EQ(skel->bss->arm_err, 0, "arm_err"))
+		goto out;
+
+	kern_sync_rcu();
+	for (i = 0; i < 3000; i++) {
+		if (__atomic_load_n(&skel->bss->hash_callbacks, __ATOMIC_ACQUIRE) >= 1)
+			break;
+		usleep(10000);
+	}
+
+	ASSERT_EQ(skel->bss->hash_callbacks, 1, "hash_callbacks");
+	ASSERT_EQ(skel->bss->hash_cb_val, 0xbadc0de, "hash_cb_val");
+out:
+	call_rcu__destroy(skel);
+}
+
+/* A hash callback which re-arms, with the element deleted mid-chain. */
+static void test_call_rcu_hash_chain(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	struct call_rcu *skel;
+	int i;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	skel->bss->hash_chain = 3;
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arm_hash_then_delete),
+					      &opts), "test_run") ||
+	    !ASSERT_EQ(opts.retval, 0, "retval"))
+		goto out;
+
+	kern_sync_rcu();
+	for (i = 0; i < 3000; i++) {
+		if (__atomic_load_n(&skel->bss->hash_callbacks, __ATOMIC_ACQUIRE) >= 1)
+			break;
+		usleep(10000);
+	}
+
+	/*
+	 * The delete lands before the first callback, so the chain is cut:
+	 * re-arming a dead head fails and the element is released once.
+	 */
+	ASSERT_EQ(skel->bss->hash_chain_err, -EBUSY, "chain_refused");
+
+	/* A re-arm that slipped through would land within a grace period. */
+	kern_sync_rcu();
+	usleep(100000);
+	ASSERT_EQ(skel->bss->hash_callbacks, 1, "hash_callbacks");
+out:
+	call_rcu__destroy(skel);
+}
+
+/* An LRU element evicted under pressure while its callback is queued. */
+static void test_call_rcu_lru_evict(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	struct call_rcu *skel;
+	int i;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arm_lru_then_evict),
+					      &opts), "test_run") ||
+	    !ASSERT_EQ(opts.retval, 0, "retval") ||
+	    !ASSERT_EQ(skel->bss->arm_err, 0, "arm_err"))
+		goto out;
+
+	kern_sync_rcu();
+	for (i = 0; i < 3000; i++) {
+		if (__atomic_load_n(&skel->bss->lru_callbacks, __ATOMIC_ACQUIRE) >= 1)
+			break;
+		usleep(10000);
+	}
+
+	ASSERT_EQ(skel->bss->lru_still_present, 1, "lru_still_present");
+	ASSERT_EQ(skel->bss->lru_callbacks, 1, "lru_callbacks");
+	ASSERT_EQ(skel->bss->lru_cb_val, 0xfeedface, "lru_cb_val");
+out:
+	call_rcu__destroy(skel);
+}
+
+static void *stress_thread(void *arg)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	int i, err, prog_fd = *(int *)arg;
+
+	for (i = 0; i < 200; i++) {
+		err = bpf_prog_test_run_opts(prog_fd, &opts);
+		if (!ASSERT_OK(err, "test_run"))
+			break;
+	}
+
+	return NULL;
+}
+
+/* Concurrent arm and delete on overlapping keys from several CPUs. */
+static void test_call_rcu_stress(void)
+{
+	pthread_t thread[8];
+	struct call_rcu *skel;
+	int i, err, prog_fd;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel_open_and_load"))
+		return;
+
+	prog_fd = bpf_program__fd(skel->progs.stress_hash);
+	for (i = 0; i < ARRAY_SIZE(thread); i++) {
+		err = pthread_create(&thread[i], NULL, stress_thread, &prog_fd);
+		if (!ASSERT_OK(err, "pthread_create"))
+			break;
+	}
+	while (i--)
+		pthread_join(thread[i], NULL);
+
+	for (i = 0; i < 3000; i++) {
+		if (__atomic_load_n(&skel->bss->stress_callbacks, __ATOMIC_ACQUIRE) >=
+		    skel->bss->stress_arms)
+			break;
+		kern_sync_rcu();
+		usleep(10000);
+	}
+
+	/* Every arm must have run, and the run must not have stalled early. */
+	ASSERT_GT(skel->bss->stress_arms, 1000, "stress_arms");
+	ASSERT_EQ(skel->bss->stress_callbacks, skel->bss->stress_arms, "stress_callbacks");
+
+	call_rcu__destroy(skel);
+}
+
 static void test_call_rcu_bad_map(void)
 {
 	LIBBPF_OPTS(bpf_map_create_opts, opts);
@@ -177,9 +330,9 @@ static void test_call_rcu_bad_map(void)
 	opts.btf_key_type_id = bpf_map__btf_key_type_id(skel->maps.arr);
 	opts.btf_value_type_id = bpf_map__btf_value_type_id(skel->maps.arr);
 
-	fd = bpf_map_create(BPF_MAP_TYPE_HASH, "rcu_hash", sizeof(__u32),
+	fd = bpf_map_create(BPF_MAP_TYPE_PERCPU_HASH, "rcu_pcpu", sizeof(__u32),
 			    bpf_map__value_size(skel->maps.arr), 1, &opts);
-	ASSERT_EQ(fd, -EOPNOTSUPP, "hash_rejected");
+	ASSERT_EQ(fd, -EOPNOTSUPP, "percpu_hash_rejected");
 	if (fd >= 0)
 		close(fd);
 
@@ -253,6 +406,89 @@ static void test_call_rcu_two_heads(void)
 	call_rcu__destroy(skel);
 }
 
+static void test_call_rcu_hash_replace(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	struct call_rcu *skel;
+	int i;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel"))
+		return;
+
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arm_then_replace),
+					      &opts), "run"))
+		goto out;
+	if (!ASSERT_EQ(opts.retval, 0, "retval"))
+		goto out;
+	ASSERT_OK(skel->bss->arm_err, "arm_err");
+
+	kern_sync_rcu();
+	for (i = 0; i < 3000; i++) {
+		if (__atomic_load_n(&skel->bss->hash_callbacks, __ATOMIC_ACQUIRE) >= 1)
+			break;
+		usleep(10000);
+	}
+	if (!ASSERT_EQ(skel->bss->hash_callbacks, 1, "hash_callbacks"))
+		goto out;
+
+	/*
+	 * The value the callback saw tells us which element it ran on: the one
+	 * that was armed, not one handed back out to a later update.
+	 */
+	ASSERT_EQ(skel->bss->hash_cb_val, 0xbadc0de, "hash_cb_val");
+out:
+	call_rcu__destroy(skel);
+}
+
+static void test_call_rcu_reuse(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	struct call_rcu *skel;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel"))
+		return;
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arm_after_reuse), &opts),
+		       "run"))
+		goto out;
+	ASSERT_EQ(opts.retval, 0, "retval");
+	ASSERT_OK(skel->bss->reuse_arm2, "arm_after_reuse");
+out:
+	call_rcu__destroy(skel);
+}
+
+static void test_call_rcu_hash_np(void)
+{
+	LIBBPF_OPTS(bpf_test_run_opts, opts);
+	struct call_rcu *skel;
+	int i;
+
+	skel = call_rcu__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "skel"))
+		return;
+
+	if (!ASSERT_OK(bpf_prog_test_run_opts(bpf_program__fd(skel->progs.arm_delete_reinsert),
+					      &opts), "run"))
+		goto out;
+	if (!ASSERT_EQ(opts.retval, 0, "retval"))
+		goto out;
+	ASSERT_OK(skel->bss->arm_err, "arm_err");
+
+	kern_sync_rcu();
+	for (i = 0; i < 3000; i++) {
+		if (__atomic_load_n(&skel->bss->hash_callbacks, __ATOMIC_ACQUIRE) >= 1)
+			break;
+		usleep(10000);
+	}
+	if (!ASSERT_EQ(skel->bss->hash_callbacks, 1, "hash_callbacks"))
+		goto out;
+
+	ASSERT_EQ(skel->bss->hash_cb_val, 0xbadc0de, "hash_cb_val");
+out:
+	call_rcu__destroy(skel);
+}
+
 void test_call_rcu(void)
 {
 	if (test__start_subtest("run"))
@@ -265,6 +501,20 @@ void test_call_rcu(void)
 		test_call_rcu_two_heads();
 	if (test__start_subtest("teardown"))
 		test_call_rcu_teardown();
+	if (test__start_subtest("hash_delete"))
+		test_call_rcu_hash_delete();
+	if (test__start_subtest("hash_chain"))
+		test_call_rcu_hash_chain();
+	if (test__start_subtest("lru_evict"))
+		test_call_rcu_lru_evict();
+	if (test__start_subtest("hash_replace"))
+		test_call_rcu_hash_replace();
+	if (test__start_subtest("hash_np"))
+		test_call_rcu_hash_np();
+	if (test__start_subtest("reuse"))
+		test_call_rcu_reuse();
+	if (test__start_subtest("stress"))
+		test_call_rcu_stress();
 	if (test__start_subtest("bad_map"))
 		test_call_rcu_bad_map();
 	if (test__start_subtest("iter"))
tools/testing/selftests/bpf/progs/call_rcu.c +274 -0

286 lines not on this page · raw message

Signature · 1 line
2.53.0-Meta
#6 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Add bpf_call_rcu tests for hash and LRU hash maps

Does the opening sentence accurately describe all the tests listed? The claim "Each of these checks the element a callback was armed on is still the one it runs on, by the value it sees" holds for…
Quoted 5 lines

selftests/bpf: Add bpf_call_rcu tests for hash and LRU hash maps

Each of these checks the element a callback was armed on is still the one it runs on, by the value it sees.

Quoted 8 lines

hash_delete arms, deletes, then inserts another key, which would be handed the freed element straight back off the freelist. hash_np does the same on a BPF_F_NO_PREALLOC map, which frees to bpf_mem_alloc instead. hash_replace replaces the key twice, which is how a preallocated map recycles through its per-CPU spare. reuse arms an element that has already been deleted and recycled. lru_evict floods a two-entry map and checks the armed element was not evicted. hash_chain checks a re-arm from the callback of a deleted element is refused.

Does the opening sentence accurately describe all the tests listed? The claim "Each of these checks the element a callback was armed on is still the one it runs on, by the value it sees" holds for hash_delete, hash_np, hash_replace, and lru_evict, which assert the callback value matches the armed value (hash_cb_val == 0xbadc0de or lru_cb_val == 0xfeedface).

However, test_call_rcu_reuse() only checks that the arm succeeds (ASSERT_OK(skel->bss->reuse_arm2)), and reuse_cb() is just return 0; with no value check.

test_call_rcu_hash_chain() asserts hash_chain_err == -EBUSY and hash_callbacks == 1, but never checks hash_cb_val.

The stress test (stress_reclaim) only counts callbacks and never looks at the value either.

Could the opening sentence be narrowed to the four tests it actually describes (hash_delete, hash_np, hash_replace, lru_evict)?

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/progs/call_rcu.c +0 -0
index 505008647fd6..f3ad92729800 100644

[ ... ]

Quoted 12 lines
tools/testing/selftests/bpf/progs/call_rcu.c +12 -0
+/* Arm a hash element, then delete it before the callback can run. */
+SEC("syscall")
+int arm_hash_then_delete(void *ctx)
+{
+	struct elem init = {};
+	__u32 key = 7;
+	struct elem *e;
+
+	init.val = 0xbadc0de;
+	if (bpf_map_update_elem(&hash, &key, &init, BPF_ANY))
+		return 1;
+

tools/testing/selftests/bpf/progs/call_rcu.c int arm_trace(void *ctx) · line 336

Quoted 10 lines
tools/testing/selftests/bpf/progs/call_rcu.c +10 -0
+	e = bpf_map_lookup_elem(&hash, &key);
+	if (!e)
+		return 2;
+
+	arm_err = bpf_call_rcu(&e->rh, &hash, hash_reclaim);
+	if (arm_err)
+		return 3;
+
+	if (bpf_map_delete_elem(&hash, &key))
+		return 4;

Can a grace period elapse between the arm and the delete? The program is SEC("syscall"), which runs from bpf_prog_test_run_syscall() under rcu_read_lock_trace() and bpf_prog_run_pin_on_cpu(). That only disables migration, not preemption.

With CONFIG_PREEMPT=y (set in tools/testing/selftests/bpf/config.x86_64), the task can be preempted between the bpf_call_rcu() and the bpf_map_delete_elem(). If the grace period completes in that gap, hash_reclaim() runs on a live element. Its re-arm succeeds, hash_chain_err becomes 0, and hash_callbacks goes to 2. The delete then claims the re-armed element. The second callback runs and only then gets -EBUSY.

The test would then fail when it checks:

prog_tests/call_rcu.c:test_call_rcu_hash_chain():

    ASSERT_EQ(skel->bss->hash_chain_err, -EBUSY, "chain_refused");
    ...
    ASSERT_EQ(skel->bss->hash_callbacks, 1, "hash_callbacks");

The same window affects arm_lru_then_evict(). If lru_reclaim() completes before or during the bpf_for() flood, the element is no longer busy. htab_lru_map_delete_node() evicts it, lru_still_present becomes 0, and the assertion fails:

    ASSERT_EQ(skel->bss->lru_still_present, 1, "lru_still_present");

The existing arm() program in this file already guards against this:

progs/call_rcu.c:arm():

    e->val = 0xdeadbeef;
    /* Keep a grace period from elapsing between the two arms. */
    bpf_rcu_read_lock();
    arm_err = bpf_call_rcu(&e->rh, &arr, reclaim);
    ...
    bpf_rcu_read_unlock();

Should arm_hash_then_delete() and arm_lru_then_evict() hold bpf_rcu_read_lock() from the arm through the delete or the eviction loop, so the tests are deterministic rather than timing-dependent?

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