selftests/bpf: libarena: Add initial data structures
Subsystems (3)
Emil Tsalapatis
reviewerv4 cover selftests/bpf: libarena: Add initial data structures
Add two new data structures to libarena. These data structures initially resided in the sched-ext repo (https://github.com/sched-ext/scx) and have been adapted to the internal libarena build system. The data structures are:
- Red black tree: Fundamental tree data structure that can also serve as a base for more domain-specific data structures.
- Lev-Chase deque: Queue data structure that allows efficient work stealing, useful in scheduling scenarios.
The data structures are accompanied by selftests that are automatically discovered by the existing libarena test_progs selftest and incorporated in the CI.
CHANGELOG
=========
v3 -> v4 (https://lore.kernel.org/bpf/[email protected]/)
- Turn off load_acquire/store_relesase - dependent selftests for s390 (CI)
- Various style/non-functional nits (AI)
v2 -> v3 (https://lore.kernel.org/bpf/[email protected]/)
- Add workaround to handle LLVM 21 and GCC 15 assignment-to-memset promotions that are causing verification failures for arena programs (CI)
- Incorporate Sashiko feedback for cleanup edge cases (Sashiko)
- Simplify some of the ordering semantics in spmc
v1 -> v2 (https://lore.kernel.org/bpf/[email protected]/):
- Rename tests from st_ to test_ (Alexei)
- Removed the freelist caches from the rbtrees, previously used to defer freeing (Alexei)
- Moved the type and function definitions to use the __arena identifier
- Removed the typecasts during function return and directly return __arena pointers (Alexei)
- Renamed queues to spmc queues to abstract away the algorithm (Alexei)
- Adjusted the memory barriers in the spmc queue
- Added multithreaded testing harness for libarena programs (Alexei)
- Added parallel selftest for queues (Alexei)
- Split least upper bound and exact find operations back into separate functions to prevent RB_DUPLICATE-related bug (AI)
Emil Tsalapatis (3):
selftests/bpf: libarena: Add rbtree data structure selftests/bpf: libarena: Add spmc queue data structure selftests/bpf: libarena: parallel test harness and spmc parallel
selftest
.../bpf/libarena/include/libarena/rbtree.h | 83 ++ .../bpf/libarena/include/libarena/spmc.h | 27 + .../bpf/libarena/include/libarena/userspace.h | 6 + .../selftests/test_parallel_spmc.bpf.c | 673 +++++++++++ .../bpf/libarena/selftests/test_rbtree.bpf.c | 968 +++++++++++++++ .../bpf/libarena/selftests/test_spmc.bpf.c | 194 +++ .../selftests/bpf/libarena/src/rbtree.bpf.c | 1047 +++++++++++++++++ .../selftests/bpf/libarena/src/spmc.bpf.c | 234 ++++ .../selftests/bpf/prog_tests/libarena.c | 187 +++ 9 files changed, 3419 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/spmc.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_spmc.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/spmc.bpf.c
Signature · 1 line
2.54.0
Emil Tsalapatis
reviewerPATCH v4 1/3 selftests/bpf: libarena: Add rbtree data structure
Add a native red-black tree data structure to libarena. The data structure supports multiple APIs (key-value based, node based) with which users can query and modify it. The tree uses the libarena memory allocator to manage its data.
--- .../bpf/libarena/include/libarena/rbtree.h | 83 ++ .../bpf/libarena/selftests/test_rbtree.bpf.c | 968 +++++++++++++++ .../selftests/bpf/libarena/src/rbtree.bpf.c | 1047 +++++++++++++++++ 3 files changed, 2098 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c
tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h new file +83 -0
@@ -0,0 +1,83 @@ +/* SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause */ + +#pragma once + +#define RB_MAXLVL_PRINT (16) + +struct rbnode ; + +struct rbnode { + struct rbnode __arena *parent; +union { +struct { + struct rbnode __arena *left; + struct rbnode __arena *right; + }; + + struct rbnode __arena *child[2]; + }; +uint64_t key; +/* Used as a linked list or to store KV pairs. */ +union { + struct rbnode __arena *next; +uint64_t value; + }; +bool is_red; +}; + +/* +* Does the rbtree allocate its own nodes, or do they get +* allocated by the caller? +*/ +enum rbtree_alloc { +RB_ALLOC , +RB_NOALLOC , +}; + +/* +* Specify the behavior of rbtree insertions when the key is +* already present in the tree. +* +* RB_DEFAULT: Default behavior, reject the new insert. +* +* RB_UPDATE: Update the existing value in the rbtree. +* This updates the node itself, not just the value in +* the existing node. +* +* RB_DUPLICATE: Allow nodes with identical keys in the rbtree. +* Finding/popping/removing a key acts on any of the nodes +* with the appropriate key - there is no ordering by time +* of insertion. +*/ +enum rbtree_insert_mode { +RB_DEFAULT , +RB_UPDATE , +RB_DUPLICATE , +}; + +struct rbtree { + struct rbnode __arena *root; +enum rbtree_alloc alloc; +enum rbtree_insert_mode insert; +}; + +#ifdef __BPF__ +struct rbtree __arena *rb_create(enum rbtree_alloc alloc, enum rbtree_insert_mode insert); + +int rb_destroy(struct rbtree __arena *rbtree); +int rb_insert(struct rbtree __arena *rbtree, u64 key, u64 value); +int rb_remove(struct rbtree __arena *rbtree, u64 key); +int rb_find(struct rbtree __arena *rbtree, u64 key, u64 *value); +int rb_print(struct rbtree __arena *rbtree); +int rb_least(struct rbtree __arena *rbtree, u64 *key, u64 *value); +int rb_pop(struct rbtree __arena *rbtree, u64 *key, u64 *value); + +int rb_insert_node(struct rbtree __arena *rbtree, struct rbnode __arena *node); +int rb_remove_node(struct rbtree __arena *rbtree, struct rbnode __arena *node); + +struct rbnode __arena *rb_node_alloc(u64 key, u64 value); +void rb_node_free(struct rbnode __arena *rbnode); + +int rb_integrity_check(struct rbtree __arena *rbtree); + +#endif /* __BPF__ */
tools/testing/selftests/bpf/libarena/selftests/test_rbtree.bpf.c new file +968 -0
968 lines not on this page · raw message
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +1047 -0
1,047 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH bpf-next v4 1/3] selftests/bpf: libarena: Add rbtree data structure
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] Failure to check `can_loop` termination leads to severe tree corruption, memory leaks, and NULL…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Failure to check can_loop termination leads to severe tree corruption, memory leaks, and NULL pointer dereferences. --
commit 090a58da31563cb07c7562cdaaf67470a54e90c0
Author: Emil Tsalapatis <[email protected]>
selftests/bpf: libarena: Add rbtree data structure
This commit adds a native red-black tree data structure to libarena. It supports multiple APIs for querying and modifying the tree, and uses the libarena memory allocator to manage its data.
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0
[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+__weak +int rb_destroy(struct rbtree __arena *rbtree) +{ +int ret =0 ; + +arena_subprog_init (); + +if (unlikely (!rbtree)) +return -EINVAL ;
[ ... ]
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 80
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +8
-0+while (rbtree->root && can_loop) { + ret =rb_remove (rbtree, rbtree->root->key); +if (ret) +break ; + } + +out: +arena_free (rbtree);
[Severity: High]
Does this code leak memory if the loop exits early due to the can_loop limit being reached? If the loop aborts early, the rbtree container is freed even though the remaining nodes have not been removed.
Quoted 2 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +2
-0+return ret; +}
[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+static +struct rbnode __arena *rbnode_least_upper_bound(struct rbnode __arena *subtree, uint64_t key) +{ + struct rbnode __arena *node = subtree; +int dir; + +if (!subtree) +return NULL ; +
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 182
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+while (can_loop) { + dir = (key <= node->key) ?0 :1 ; + +if (!node->child[dir]) +break ; + + node = node->child[dir]; + } + +return node;
[Severity: High]
If this loop terminates early because can_loop evaluates to false, will it return an internal tree node rather than a leaf node?
Quoted 1 line
+}
[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+static +int rb_node_insert(struct rbtree __arena *rbtree, + struct rbnode __arena *node) +{ + struct rbnode __arena *grandparent, *parent = rbtree->root; +u64 key = node->key; + struct rbnode __arena *uncle; +int dir; +int ret;
[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +4
-0+if (rbtree->insert !=RB_DUPLICATE ) + parent =rbnode_find (parent, key); +else + parent =rbnode_least_upper_bound (parent, key);
[ ... ]
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 283
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +4
-0+ node->parent = parent; +/* Also works if key == parent->key. */ +if (key <= parent->key) + parent->left = node;
[Severity: High]
If rbnode_find() or rbnode_least_upper_bound() returns an internal node due to a can_loop timeout, does unconditionally overwriting parent->left or parent->right here permanently detach and leak the existing subtree?
Quoted 2 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +2
-0+else + parent->right = node;
[ ... ]
Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +7
-0+static +int rb_node_remove(struct rbtree __arena *rbtree, + struct rbnode __arena *node) +{ + struct rbnode __arena *parent, *sibling, *close_nephew, *distant_nephew; +bool free = (rbtree->alloc ==RB_ALLOC ); + struct rbnode __arena *replace, *initial;
[ ... ]
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +5
-0+while (can_loop) { + +/* Balancing reached the root, there can be no imbalance. */ +if (!parent) +return 0 ;
[ ... ]
Quoted 22 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +22
-0+ sibling->is_red = true; + node = parent; + parent = node->parent; + dir =rbnode_dir (node); + } + +if (node != initial) { + dir =rbnode_dir (node); + parent = node->parent; + sibling = parent->child[1 -dir]; + } +/* +* Almost there. We know between the parent, sibling, +* and nephews only one or two of the nephews are red. If +* it is the close one, rotate it to the sibling position, +* paint it black, and paint the previous sibling red. +*/ + + close_nephew = sibling->child[dir]; + distant_nephew = sibling->child[1 - dir]; + +/*
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 743
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+* If the distant red nephew is not red, rotate +* and repaint. We need the distant nephew +* to be red. We know the close nephew is red +* because at least one of them are, so the +* distant one is black if it exists. +*/ +if (!distant_nephew || !distant_nephew->is_red) { +rbnode_rotate (rbtree, sibling,1 - dir); + sibling->is_red = true; + close_nephew->is_red = false;
[Severity: High]
Can this cause a NULL pointer dereference if the rebalancing loop above exits early due to can_loop?
An early exit bypasses the guarantee that the sibling has red children, which means both nephews, including close_nephew, might be NULL here.
Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +3
-0+ distant_nephew = sibling; + sibling = close_nephew; + }
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Emil Tsalapatis
reviewerRe: [PATCH bpf-next v4 1/3] selftests/bpf: libarena: Add rbtree data structure
Quoted 169 lines · sashiko-bot
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Failure to checkcan_looptermination leads to severe tree corruption, memory leaks, and NULL pointer dereferences. --commit
090a58da31563cb07c7562cdaaf67470a54e90c0
Author: Emil Tsalapatis <[email protected]>selftests/bpf: libarena: Add rbtree data structure
This commit adds a native red-black tree data structure to libarena. It supports multiple APIs for querying and modifying the tree, and uses the libarena memory allocator to manage its data.
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+__weak +int rb_destroy(struct rbtree __arena *rbtree) +{ +int ret =0 ; + +arena_subprog_init (); + +if (unlikely (!rbtree)) +return -EINVAL ;[ ... ]
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 80
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +8
-0+while (rbtree->root && can_loop) { + ret =rb_remove (rbtree, rbtree->root->key); +if (ret) +break ; + } + +out: +arena_free (rbtree);[Severity: High]
Does this code leak memory if the loop exits early due to thecan_looplimit being reached? If the loop aborts early, the rbtree container is freed even though the remaining nodes have not been removed.Quoted 2 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +2
-0+return ret; +}[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+static +struct rbnode __arena *rbnode_least_upper_bound(struct rbnode __arena *subtree, uint64_t key) +{ + struct rbnode __arena *node = subtree; +int dir; + +if (!subtree) +return NULL ; +tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 182
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+while (can_loop) { + dir = (key <= node->key) ?0 :1 ; + +if (!node->child[dir]) +break ; + + node = node->child[dir]; + } + +return node;[Severity: High]
If this loop terminates early becausecan_loopevaluates to false, will it return an internal tree node rather than a leaf node?Quoted 1 line
+}
[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+static +int rb_node_insert(struct rbtree __arena *rbtree, + struct rbnode __arena *node) +{ + struct rbnode __arena *grandparent, *parent = rbtree->root; +u64 key = node->key; + struct rbnode __arena *uncle; +int dir; +int ret;[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +4
-0+if (rbtree->insert !=RB_DUPLICATE ) + parent =rbnode_find (parent, key); +else + parent =rbnode_least_upper_bound (parent, key);[ ... ]
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 283
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +4
-0+ node->parent = parent; +/* Also works if key == parent->key. */ +if (key <= parent->key) + parent->left = node;[Severity: High]
Ifrbnode_find()orrbnode_least_upper_bound()returns an internal node due to acan_looptimeout, does unconditionally overwritingparent->leftorparent->righthere permanently detach and leak the existing subtree?Quoted 2 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +2
-0+else + parent->right = node;[ ... ]
Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +7
-0+static +int rb_node_remove(struct rbtree __arena *rbtree, + struct rbnode __arena *node) +{ + struct rbnode __arena *parent, *sibling, *close_nephew, *distant_nephew; +bool free = (rbtree->alloc ==RB_ALLOC ); + struct rbnode __arena *replace, *initial;[ ... ]
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +5
-0+while (can_loop) { + +/* Balancing reached the root, there can be no imbalance. */ +if (!parent) +return 0 ;[ ... ]
Quoted 22 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +22
-0+ sibling->is_red = true; + node = parent; + parent = node->parent; + dir =rbnode_dir (node); + } + +if (node != initial) { + dir =rbnode_dir (node); + parent = node->parent; + sibling = parent->child[1 -dir]; + } +/* +* Almost there. We know between the parent, sibling, +* and nephews only one or two of the nephews are red. If +* it is the close one, rotate it to the sibling position, +* paint it black, and paint the previous sibling red. +*/ + + close_nephew = sibling->child[dir]; + distant_nephew = sibling->child[1 - dir]; + +/* tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 743
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+* If the distant red nephew is not red, rotate +* and repaint. We need the distant nephew +* to be red. We know the close nephew is red +* because at least one of them are, so the +* distant one is black if it exists. +*/ +if (!distant_nephew || !distant_nephew->is_red) { +rbnode_rotate (rbtree, sibling,1 - dir); + sibling->is_red = true; + close_nephew->is_red = false;[Severity: High]
Can this cause a NULL pointer dereference if the rebalancing loop above exits early due tocan_loop?
Quoted 2 lines
An early exit bypasses the guarantee that the sibling has red children, which means both nephews, including
close_nephew, might be NULL here.
No. We don't care what happens if can_loop triggers. Same for the rest of the bot feedback. The only outstanding actionable nit is imo the mismatch between the function names in the patch description and the actual code for spmc, for which I can send another version if necessary.
Quoted 4 lines
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +3
-0+ distant_nephew = sibling; + sibling = close_nephew; + }
[email protected]
AI reviewRe: [PATCH bpf-next v4 1/3] selftests/bpf: libarena: Add rbtree data structure
In reply to Emil TsalapatisDoes this code leak memory if the loop exits early due to the can_loop limit being reached?
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0
[ ... ]
Quoted 27 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +27
-0+__weak +int rb_destroy(struct rbtree __arena *rbtree) +{ +int ret =0 ; + +arena_subprog_init (); + +if (unlikely (!rbtree)) +return -EINVAL ; + +if (rbtree->alloc ==RB_NOALLOC ) { +/* +* We cannot do anything about RB_NOALLOC nodes. The whole +* point of RB_NOALLOC is that the nodes are directly owned +* by the caller that allocates and inserts them. We could +* unilaterally grab all nodes and free them anyway, but that +* would almost certainly cause UAF as the callers keep accessing +* the now freed nodes. Throw an error instead. +*/ +if (rbtree->root) { +arena_stderr ("WARNING: Destroying RB_NOALLOC tree with > 0 nodes" ); +return -EBUSY ; + } + + goto out; + } +
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 82
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+while (rbtree->root && can_loop) { + ret =rb_remove (rbtree, rbtree->root->key); +if (ret) +break ; + } + +out: +arena_free (rbtree); +return ret; +}
Does this code leak memory if the loop exits early due to the can_loop limit being reached?
If the loop aborts early, the rbtree container is freed even though the remaining nodes have not been removed.
This was flagged in the v4 review by sashiko-bot:
https://lore.kernel.org/bpf/[email protected]/
[ ... ]
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+static +struct rbnode __arena *rbnode_least_upper_bound(struct rbnode __arena *subtree, uint64_t key) +{ + struct rbnode __arena *node = subtree; +int dir; + +if (!subtree) +return NULL ; + +while (can_loop) {
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 183
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+ dir = (key <= node->key) ?0 :1 ; + +if (!node->child[dir]) +break ; + + node = node->child[dir]; + } + +return node; +}
If this loop terminates early because can_loop evaluates to false, will it return an internal tree node rather than a leaf node?
This was flagged in the v4 review by sashiko-bot:
https://lore.kernel.org/bpf/[email protected]/
[ ... ]
Quoted 39 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +39
-0+static +int rb_node_insert(struct rbtree __arena *rbtree, + struct rbnode __arena *node) +{ + struct rbnode __arena *grandparent, *parent = rbtree->root; +u64 key = node->key; + struct rbnode __arena *uncle; +int dir; +int ret; + +if (unlikely (!rbtree)) +return -EINVAL ; + +if (!parent) { + rbtree->root = node; +return 0 ; + } + +if (rbtree->insert !=RB_DUPLICATE ) + parent =rbnode_find (parent, key); +else + parent =rbnode_least_upper_bound (parent, key); + +if (key == parent->key && rbtree->insert !=RB_DUPLICATE ) { +if (rbtree->insert ==RB_UPDATE ) { +/* +* Replace the old node with the new one. +* Free up the old node. +*/ + ret =rbnode_replace (rbtree, parent, node); +if (ret) +return ret; + +if (rbtree->alloc ==RB_ALLOC ) +rb_node_free (parent); + +return 0 ; + } +
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 285
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+/* Otherwise it's RB_DEFAULT. */ +return -EALREADY ; + } + + node->parent = parent; +/* Also works if key == parent->key. */ +if (key <= parent->key) + parent->left = node; +else + parent->right = node;
If rbnode_find() or rbnode_least_upper_bound() returns an internal node due to a can_loop timeout, does unconditionally overwriting parent->left or parent->right here permanently detach and leak the existing subtree?
This was flagged in the v4 review by sashiko-bot:
https://lore.kernel.org/bpf/[email protected]/
[ ... ]
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +9
-0+static +int rb_node_remove(struct rbtree __arena *rbtree, + struct rbnode __arena *node) +{ + struct rbnode __arena *parent, *sibling, *close_nephew, *distant_nephew; +bool free = (rbtree->alloc ==RB_ALLOC ); + struct rbnode __arena *replace, *initial; +bool is_red; +int dir;
[ ... ]
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +5
-0+while (can_loop) { + +/* Balancing reached the root, there can be no imbalance. */ +if (!parent) +return 0 ;
[ ... ]
Quoted 70 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +70
-0+/* Sibling is red, turn it into the grandparent. */ +if (sibling->is_red) { +/* +* Sibling is red. Transform the tree to turn +* the sibling into the parent's position, and +* repaint them. This does not balance the tree +* but makes it so we know the sibling is black +* and so can use the transformations to balance. +*/ +rbnode_rotate (rbtree, parent, dir); + parent->is_red = true; + sibling->is_red = false; + +/* Our new sibling is now the close nephew. */ + sibling = parent->child[1 - dir]; +/* If sibling has any red siblings, break out. */ +if (rbnode_has_red_children (sibling)) +break ; + +/* We can repaint the sibling and parent, we're done. */ + sibling->is_red = true; + parent->is_red = false; + +return 0 ; + } + +/* Sibling guaranteed to be black. If it has red children, break out. */ +if (rbnode_has_red_children (sibling)) +break ; + +/* +* Both sibling and children are black. If parent is red, swap +* colors with the sibling. Otherwise +*/ +if (parent->is_red) { + parent->is_red = false; + sibling->is_red = true; +return 0 ; + } + +/* +* Parent, sibling, and all its children are black. Repaint the sibling. +* This shortens the paths through it, so pop up a level in the +* tree and repeat the balancing. +*/ + sibling->is_red = true; + node = parent; + parent = node->parent; + dir =rbnode_dir (node); + } + +if (node != initial) { + dir =rbnode_dir (node); + parent = node->parent; + sibling = parent->child[1 -dir]; + } +/* +* Almost there. We know between the parent, sibling, +* and nephews only one or two of the nephews are red. If +* it is the close one, rotate it to the sibling position, +* paint it black, and paint the previous sibling red. +*/ + + close_nephew = sibling->child[dir]; + distant_nephew = sibling->child[1 - dir]; + +/* +* If the distant red nephew is not red, rotate +* and repaint. We need the distant nephew +* to be red. We know the close nephew is red
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 746
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+* because at least one of them are, so the +* distant one is black if it exists. +*/ +if (!distant_nephew || !distant_nephew->is_red) { +rbnode_rotate (rbtree, sibling,1 - dir); + sibling->is_red = true; + close_nephew->is_red = false; + distant_nephew = sibling; + sibling = close_nephew; + }
Can this cause a NULL pointer dereference if the rebalancing loop exits early due to can_loop?
An early exit bypasses the guarantee that the sibling has red children, which means both nephews, including close_nephew, might be NULL here.
This was flagged in the v4 review by sashiko-bot:
https://lore.kernel.org/bpf/[email protected]/
---
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/27043406243
Emil Tsalapatis
reviewerPATCH v4 2/3 selftests/bpf: libarena: Add spmc queue data structure
In reply to Emil TsalapatisExpand libarena with a single producer multiple consumer deque data structure. This is a single producer, multiple consumer lockless structure that permits efficient work stealing. The structure is a Lev-Chase queue, so it is lock-free and wait-free.
The data structure exposes three main calls. two of them are available to the thread owning the queue and one available to all threads in the program:
spmc_owner_push(): Push an item to the top of the queue. spmc_owner_pop(): Pop an item from the top of the queue. spmc_steal(): Steal a thread from the bottom of the queue from any thread.
Note that the queue is not really FIFO for all consumers, since non-owners of the queue can only work steal from the bottom.
--- .../bpf/libarena/include/libarena/spmc.h | 27 ++ .../bpf/libarena/selftests/test_spmc.bpf.c | 194 +++++++++++++++ .../selftests/bpf/libarena/src/spmc.bpf.c | 234 ++++++++++++++++++ 3 files changed, 455 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/spmc.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_spmc.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/spmc.bpf.c
tools/testing/selftests/bpf/libarena/include/libarena/spmc.h new file +27 -0
@@ -0,0 +1,27 @@ +/* SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause */ + +#pragma once + +struct spmc_arr ; + +#define SPMC_ARR_BASESZ 128 +#define SPMC_ARR_ORDERS 10 + +struct spmc_arr { + u64 __arena *data; +u64 order; +}; + +struct spmc { + volatile struct spmc_arr __arena *cur; +volatile u64 top; +volatile u64 bottom; +struct spmc_arr arr[SPMC_ARR_ORDERS ]; +}; + +int spmc_owned_add(struct spmc __arena *spmc, u64 val); +int spmc_owned_remove(struct spmc __arena *spmc, u64 *val); +int spmc_steal(struct spmc __arena *spmc, u64 *val); + +struct spmc __arena *spmc_create(void); +int spmc_destroy(struct spmc __arena *spmc);
tools/testing/selftests/bpf/libarena/selftests/test_spmc.bpf.c new file +194 -0
194 lines not on this page · raw message
tools/testing/selftests/bpf/libarena/src/spmc.bpf.c new file +234 -0
234 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH bpf-next v4 2/3] selftests/bpf: libarena: Add spmc queue data structure
The commit message describes an API that doesn't match the implementation.
Quoted 7 lines
selftests/bpf: libarena: Add spmc queue data structure
Expand libarena with a single producer multiple consumer deque data structure. This is a single producer, multiple consumer lockless structure that permits efficient work stealing. The structure is a Lev-Chase queue, so it is lock-free and wait-free.
Quoted 7 lines
The data structure exposes three main calls. two of them are available to the thread owning the queue and one available to all threads in the program:
spmc_owner_push(): Push an item to the top of the queue.spmc_owner_pop(): Pop an item from the top of the queue.spmc_steal(): Steal a thread from the bottom of the queue from any thread.
The commit message describes an API that doesn't match the implementation.
The message refers to spmc_owner_push() and spmc_owner_pop(), but the actual functions declared in libarena/spmc.h and defined in spmc.bpf.c are spmc_owned_add() and spmc_owned_remove():
tools/testing/selftests/bpf/libarena/include/libarena/spmc.h:
int spmc_owned_add(struct spmc __arena *spmc, u64 val);
int spmc_owned_remove(struct spmc __arena *spmc, u64 *val);
int spmc_steal(struct spmc __arena *spmc, u64 *val);Additionally, the descriptions are inverted. The message says the owner operates on the 'top' and stealers steal from the 'bottom', whereas the code has the owner operate on 'bottom' and stealers operate on 'top':
tools/testing/selftests/bpf/libarena/src/spmc.bpf.c:spmc_owned_add() {
b = smp_load_acquire(&spmc->bottom);
...
spmc_arr_put(arr, b, val);
smp_store_release(&spmc->bottom, b + 1);
}tools/testing/selftests/bpf/libarena/src/spmc.bpf.c:spmc_owned_remove() {
b = READ_ONCE(spmc->bottom) - 1;
...
value = spmc_arr_get(arr, b);
}tools/testing/selftests/bpf/libarena/src/spmc.bpf.c:spmc_steal() {
t = smp_load_acquire(&spmc->top);
...
value = spmc_arr_get(arr, t);
...
if (cmpxchg(&spmc->top, t, t + 1) != t)
}Finally, the message says spmc_steal() steals "a thread" rather than an item or value.
Should the commit message be updated to match the actual API and implementation?
---
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/27043406243
Emil Tsalapatis
reviewerPATCH v4 3/3 selftests/bpf: libarena: parallel test harness and spmc parallel selftest
In reply to Emil TsalapatisAdd a parallel test for the SPMC Lev-Chase workstealing queue. The queue is built to be wait-free even when there are multiple consumers, and the parallel selftest provides a signal on whether the queue behaves correctly when stress tested.
To support the test, this patch includes a test harness for parallel selftests. The spmc selftest acts as an example of the naming and other conventions expected by the harness.
--- .../bpf/libarena/include/libarena/userspace.h | 6 + .../selftests/test_parallel_spmc.bpf.c | 673 ++++++++++++++++++ .../selftests/bpf/prog_tests/libarena.c | 187 +++++ 3 files changed, 866 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c
tools/testing/selftests/bpf/libarena/include/libarena/userspace.h +6 -0
@@ -32,6 +32,12 @@ static inline bool libarena_is_asan_test_prog(const char *name)return strstr (name,"asan_test" ) == name; } +static inline bool libarena_is_parallel_test_prog (const char *name) +{ +return strstr (name,"parallel_test" ) == name; +} + +static inline int libarena_run_prog_args (int prog_fd,void *args,size_t argsize) {LIBBPF_OPTS (bpf_test_run_opts, opts);
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +673 -0
673 lines not on this page · raw message
tools/testing/selftests/bpf/prog_tests/libarena.c +187 -0
199 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [PATCH bpf-next v4 3/3] selftests/bpf: libarena: parallel test harness and spmc parallel selftest
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] Missing file descriptor (FD) validation after manual program lookups. --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Missing file descriptor (FD) validation after manual program lookups. --
commit f9cb27c914dcd0d4f6eca457c86b2aac266e34a4
Author: Emil Tsalapatis <[email protected]>
selftests/bpf: libarena: parallel test harness and spmc parallel selftest
Add a parallel test for the SPMC Lev-Chase workstealing queue. The queue is built to be wait-free even when there are multiple consumers, and the parallel selftest provides a signal on whether the queue behaves correctly when stress tested.
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 34
Quoted 13 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +5
-0@@ -27,6 +27,177 @@ static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, } +static void *run_libarena_parallel_prog (void *arg) +{ +struct bpf_program *prog = arg; + +return (void *)(long )libarena_run_prog (bpf_program__fd (prog));
[Severity: Medium]
Should we validate the file descriptor returned by bpf_program__fd here?
The program is manually looked up via bpf_object__find_program_by_name in run_libarena_parallel_test_workers before being passed to this thread worker. When using manual lookups instead of auto-generated skeleton fields, the program pointer could be valid while the underlying program is invalid, resulting in a negative FD.
An ASSERT_GE check for the file descriptor could prevent unexpected behavior.
Quoted 13 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +13
-0+} + +/* Max suffix is ceil((lg 2^32) / (lg 10)) + sizeof("__") = 10 + 2 = 12. */ +#define MAX_PARTEST_SUFFIX (12) +#define MAX_PARTEST_NAME (1024) +#define MAX_PARTEST_PREFIX (MAX_PARTEST_NAME - MAX_PARTEST_SUFFIX) + +static int run_libarena_parallel_fini (struct libarena *skel,const char *name, +size_t prefixlen) +{ +char tdname[MAX_PARTEST_NAME ]; +struct bpf_program *fini_prog; +int ret;
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 57
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +10
-0+ + ret =snprintf (tdname,sizeof (tdname),"%.*s__fini" , (int )prefixlen, name); +if (!ASSERT_LT (ret,sizeof (tdname),"partest fini name" )) +return -ENAMETOOLONG ; + + fini_prog =bpf_object__find_program_by_name (skel->obj, tdname); +if (!ASSERT_TRUE (fini_prog,"partest fini prog" )) +return -ENOENT ; + + ret =libarena_run_prog (bpf_program__fd (fini_prog));
[Severity: Medium]
Does this missing file descriptor check risk passing a negative FD to libarena_run_prog?
Similar to the above, we manually look up fini_prog. Checking the return value of bpf_program__fd with ASSERT_GE before using it would align with the BPF selftest guidelines for manual lookups.
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +4
-0+ASSERT_OK (ret, tdname); + +return ret; +}
[ ... ]
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +8
-0+static bool libarena_parallel_test_enabled (struct libarena *skel, +const char *prefix, +size_t prefixlen) +{ +struct bpf_program *prog; +char progname[MAX_PARTEST_NAME ]; +int ret; +
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 142
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +10
-0+ ret =snprintf (progname,sizeof (progname),"%.*s__enabled" , (int )prefixlen, + prefix); +if (!ASSERT_LT (ret,sizeof (progname),"partest enabled name" )) +return false; + + prog =bpf_object__find_program_by_name (skel->obj, progname); +if (!prog) +return true; + + ret =libarena_run_prog (bpf_program__fd (prog));
[Severity: Medium]
Should we verify that the FD returned by bpf_program__fd is non-negative before executing it?
Because progname is dynamically constructed and manually looked up, we do not have the same FD validity guarantees as we do for auto-generated skeleton fields.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
[email protected]
AI reviewRe: [PATCH bpf-next v4 3/3] selftests/bpf: libarena: parallel test harness and spmc parallel selftest
In reply to Emil TsalapatisShould the file descriptor returned by bpf_program__fd be validated here?
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +0
-0
[ ... ]
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 35
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +6
-0@@ -27,6 +27,177 @@ static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, } +static void *run_libarena_parallel_prog (void *arg) +{ +struct bpf_program *prog = arg; + +return (void *)(long )libarena_run_prog (bpf_program__fd (prog)); +}
Should the file descriptor returned by bpf_program__fd be validated here?
Reviewers in v2, v3, and v4 noted that because prog is manually looked up via bpf_object__find_program_by_name in run_libarena_parallel_test_workers before being passed to this thread worker, the program pointer could be valid while the underlying program is invalid, resulting in a negative FD. An ASSERT_GE check for the file descriptor could prevent unexpected behavior.
Quoted 13 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +13
-0+ +/* Max suffix is ceil((lg 2^32) / (lg 10)) + sizeof("__") = 10 + 2 = 12. */ +#define MAX_PARTEST_SUFFIX (12) +#define MAX_PARTEST_NAME (1024) +#define MAX_PARTEST_PREFIX (MAX_PARTEST_NAME - MAX_PARTEST_SUFFIX) + +static int run_libarena_parallel_fini (struct libarena *skel,const char *name, +size_t prefixlen) +{ +char tdname[MAX_PARTEST_NAME ]; +struct bpf_program *fini_prog; +int ret; +
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 58
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +10
-0+ ret =snprintf (tdname,sizeof (tdname),"%.*s__fini" , (int )prefixlen, name); +if (!ASSERT_LT (ret,sizeof (tdname),"partest fini name" )) +return -ENAMETOOLONG ; + + fini_prog =bpf_object__find_program_by_name (skel->obj, tdname); +if (!ASSERT_TRUE (fini_prog,"partest fini prog" )) +return -ENOENT ; + + ret =libarena_run_prog (bpf_program__fd (fini_prog)); +ASSERT_OK (ret, tdname);
Does this risk passing a negative FD to libarena_run_prog?
Reviewers in v2, v3, and v4 raised concerns about passing an unverified file descriptor. Because fini_prog is manually looked up via bpf_object__find_program_by_name, the manual lookup API can return a valid bpf_program pointer even if the program failed to load, which results in a negative FD. An explicit file descriptor validation such as ASSERT_GE should be added before using the FD.
Quoted 3 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +3
-0+ +return ret; +}
[ ... ]
Quoted 8 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +8
-0+static bool libarena_parallel_test_enabled (struct libarena *skel, +const char *prefix, +size_t prefixlen) +{ +struct bpf_program *prog; +char progname[MAX_PARTEST_NAME ]; +int ret; +
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 142
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +10
-0+ ret =snprintf (progname,sizeof (progname),"%.*s__enabled" , (int )prefixlen, + prefix); +if (!ASSERT_LT (ret,sizeof (progname),"partest enabled name" )) +return false; + + prog =bpf_object__find_program_by_name (skel->obj, progname); +if (!prog) +return true; + + ret =libarena_run_prog (bpf_program__fd (prog));
Should the FD returned by bpf_program__fd be verified as non-negative before executing it?
The reviewer noted in v4 that because progname is dynamically constructed and manually looked up via bpf_object__find_program_by_name, it does not have the same FD validity guarantees as auto-generated skeleton fields. FD validation should be added to prevent passing a negative FD.
tools/testing/selftests/bpf/prog_tests/libarena.c static void run_libarena_test(struct libarena *skel, struct bpf_program *prog, · line 148
Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +6
-0+if (ret == -EOPNOTSUPP ) +return false; +if (!ASSERT_OK (ret, progname)) +return false; +return true; +}
---
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/27043406243
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Fri, 5 Jun 2026 18:20:17 -0400 you wrote:
Add two new data structures to libarena. These data structures initially resided in the sched-ext repo (https://github.com/sched-ext/scx) and have been adapted to the internal libarena build system. The data structures are:
- Red black tree: Fundamental tree data structure that can also serve as a base for more domain-specific data structures.
[...]
Here is the summary with links:
- [bpf-next,v4,1/3] selftests/bpf: libarena: Add rbtree data structure
https://git.kernel.org/bpf/bpf-next/c/6c3e8a4d4765 - [bpf-next,v4,2/3] selftests/bpf: libarena: Add spmc queue data structure https://git.kernel.org/bpf/bpf-next/c/57c6ace8395d - [bpf-next,v4,3/3] selftests/bpf: libarena: parallel test harness and spmc parallel selftest https://git.kernel.org/bpf/bpf-next/c/42998f819256
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html