selftests/bpf: libarena: Add initial data structures
Subsystems (3)
Emil Tsalapatis
reviewercover 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.
Emil Tsalapatis (2):
selftests/bpf: libarena: Add rbtree data structure selftests/bpf: libarena: Add Lev-Chase queue data structure
.../bpf/libarena/include/libarena/lvqueue.h | 33 + .../bpf/libarena/include/libarena/rbtree.h | 89 ++ .../bpf/libarena/selftests/st_lvqueue.bpf.c | 194 ++++ .../bpf/libarena/selftests/st_rbtree.bpf.c | 974 ++++++++++++++++ .../selftests/bpf/libarena/src/lvqueue.bpf.c | 241 ++++ .../selftests/bpf/libarena/src/rbtree.bpf.c | 1032 +++++++++++++++++ 6 files changed, 2563 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c
---
Resending this because I typo'ed Matt's email _again_, sorry about that.
Signature · 1 line
2.54.0
Emil Tsalapatis
reviewerPATCH RESEND 1/2 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 | 89 ++ .../bpf/libarena/selftests/st_rbtree.bpf.c | 974 ++++++++++++++++ .../selftests/bpf/libarena/src/rbtree.bpf.c | 1032 +++++++++++++++++ 3 files changed, 2095 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/rbtree.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/st_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 +89 -0
@@ -0,0 +1,89 @@ +/* SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause */ + +#pragma once + +#define RB_MAXLVL_PRINT (16) + +struct rbnode ; + +typedef struct rbnode __arena rbnode_t; + +struct rbnode { +rbnode_t *parent; +union { +struct { +rbnode_t *left; +rbnode_t *right; + }; + +rbnode_t *child[2 ]; + }; +uint64_t key; +/* Used as a linked list or to store KV pairs. */ +union { +rbnode_t *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 { +rbnode_t *root; +rbnode_t *freelist; +enum rbtree_alloc alloc; +enum rbtree_insert_mode insert; +}; + +typedef struct rbtree __arena rbtree_t; + +#ifdef __BPF__ +u64 rb_create_internal (enum rbtree_alloc alloc,enum rbtree_insert_mode insert); +#define rb_create (alloc, insert) ((rbtree_t *)rb_create_internal((alloc), (insert))) + +int rb_destroy(rbtree_t *rbtree __arg_arena); +int rb_insert (rbtree_t *rbtree,u64 key,u64 value); +int rb_remove (rbtree_t *rbtree,u64 key); +int rb_find (rbtree_t *rbtree,u64 key,u64 *value); +int rb_print (rbtree_t *rbtree); +int rb_least (rbtree_t *rbtree,u64 *key,u64 *value); +int rb_pop (rbtree_t *rbtree,u64 *key,u64 *value); + +int rb_insert_node (rbtree_t *rbtree,rbnode_t *node); +int rb_remove_node (rbtree_t *rbtree,rbnode_t *node); +u64 rb_node_alloc_internal (rbtree_t *rbtree,u64 key,u64 value); +#define rb_node_alloc (rbtree, key, value) ((rbnode_t *)rb_node_alloc_internal((rbtree), (key), (value))) +int rb_node_free (rbtree_t *rbtree,rbnode_t *rbnode); + +int rb_integrity_check (rbtree_t *rbtree); + +#endif /* __BPF__ */
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +974 -0
974 lines not on this page · raw message
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +1032 -0
1,032 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [RESEND PATCH bpf-next 1/2] selftests/bpf: libarena: Add rbtree data structure
The comment says rb_find should return -EINVAL when looking for a non-existent key in an empty tree, but looking at rb_find in rbtree.bpf.c:
Quoted 6 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +0
-0@@ -0,0 +1,974 @@
[ ... ]
Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +10
-0+SEC("syscall") +__weak int test_rbtree_find_nonexistent (void ) +{ +u64 key =0xdeadbeef ; +u64 value =0 ; +int ret; + +rbtree_t *rbtree; + + rbtree =rb_create (RB_ALLOC ,RB_DEFAULT );
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c line 65
Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +10
-0+if (!rbtree) +return 1 ; + +/* Should return -EINVAL */ + ret =rb_find (rbtree, key, &value); +if (!ret) +return 2 ; + +return rb_destroy (rbtree); +}
The comment says rb_find should return -EINVAL when looking for a non-existent key in an empty tree, but looking at rb_find in rbtree.bpf.c:
int rb_find(rbtree_t *rbtree, u64 key, u64 *value)
{
rbnode_t *node;
if (unlikely(!rbtree))
return -EINVAL;
if (unlikely(!value))
return -EINVAL;
node = rbnode_find(rbtree->root, key, RBN_FIND_DFL);
if (!node || node->key != key)
return -ENOENT;
^^^^rb_find returns -EINVAL only when rbtree or value is NULL. For a valid rbtree with no matching node, rbnode_find returns NULL and rb_find returns -ENOENT. Should the comment say "Should return -ENOENT" instead?
[ ... ]
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0@@ -0,0 +1,1032 @@
[ ... ]
Quoted 35 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +35
-0+static +rbnode_t *rbnode_find (rbnode_t *subtree,u64 key,enum rbnode_find_mode mode) +{ +rbnode_t *node = subtree; +int dir; + +if (!subtree) +return NULL ; + +while (can_loop) { +/* +* If we are not looking for the least upper bound, +* we have found the only key. Otherwise keep going +* until we find the "leftmost" instance of the key. +*/ +if (mode ==RBN_FIND_DFL && node->key == key) +break ; + + dir = (key <= node->key) ?0 :1 ; + +if (!node->child[dir]) +break ; + +/* +* For least upper bound lookups, ensure that we +* stop searching once we find the rightmost key. +*/ +if (node->key == key && node->child[dir]->key != key) +break ; + + node = node->child[dir]; + } + +return node; +}
[ ... ]
Quoted 40 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +40
-0+static +int rb_node_insert(rbtree_t *rbtree __arg_arena, rbnode_t *node __arg_arena) +{ +rbnode_t *grandparent, *parent = rbtree->root; +enum rbnode_find_mode mode; +u64 key = node->key; +rbnode_t *uncle; +int dir; +int ret; + +if (unlikely (!rbtree)) +return -EINVAL ; + +if (!parent) { + rbtree->root = node; +return 0 ; + } + + mode =RBN_FIND_DFL ; +/* Always find the first node with the key when allowing duplicates. */ +if (rbtree->insert ==RB_DUPLICATE ) + mode =RBN_FIND_LUB ; + parent =rbnode_find (parent, key, mode); + +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 (rbtree, parent); + +return 0 ; + } +
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 310
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;
Can this overwrite an existing left subtree in RB_DUPLICATE mode?
When rbnode_find is called with RBN_FIND_LUB mode, it has a third break condition that stops the search when it finds a node with a matching key whose next-direction child has a different key:
rbnode_find() {
...
if (node->key == key && node->child[dir]->key != key)
break;
...
}With key == node->key, dir is computed as (key <= node->key) ? 0 : 1 = 0. The search stops at a matching node that has a non-NULL left child with a smaller key.
Back in rb_node_insert, the code skips the RB_DEFAULT check when rbtree->insert == RB_DUPLICATE, and falls through to:
node->parent = parent;
/* Also works if key == parent->key. */
if (key <= parent->key)
parent->left = node;Since key == parent->key, the condition is true and parent->left is overwritten with the new node. But parent->left already points to an existing subtree (the smaller node that triggered the third break condition). That existing left child is overwritten, orphaning its entire subtree.
Reproduction:
1) rb_insert(rbtree, 5, v1) in RB_DUPLICATE mode -> tree: {5}
2) rb_insert(rbtree, 3, v2) -> tree: {5->left = 3}
3) rb_insert(rbtree, 5, v3)
In step 3, rbnode_find returns the root node 5 via the third break condition (because child 3 has key != 5). Then rb_node_insert sets parent->left = new_node, overwriting the pointer to node 3. Node 3 is now orphaned and leaked.
The comment claims "Also works if key == parent->key", but this only holds when rbnode_find returns a node with an empty left slot, as in the typical duplicate-chain case where all keys are identical. As soon as a duplicate insertion meets a matching node that has a pre-existing smaller left child, the assignment corrupts the tree.
The tree integrity check in rb_integrity_check walks only nodes reachable from the root, so it does not detect orphaned nodes. The existing test test_rbtree_duplicate uses a single key value for all insertions, so it never exercises the interleaved case where a smaller key exists between duplicates.
---
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/25699461713
Emil Tsalapatis
reviewerRe: [RESEND PATCH bpf-next 1/2] selftests/bpf: libarena: Add rbtree data structure
Quoted 49 lines · bot+bpf-ci
Quoted 6 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +0
-0@@ -0,0 +1,974 @@[ ... ]
Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +10
-0+SEC("syscall") +__weak int test_rbtree_find_nonexistent (void ) +{ +u64 key =0xdeadbeef ; +u64 value =0 ; +int ret; + +rbtree_t *rbtree; + + rbtree =rb_create (RB_ALLOC ,RB_DEFAULT );tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c line 65
Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +10
-0+if (!rbtree) +return 1 ; + +/* Should return -EINVAL */ + ret =rb_find (rbtree, key, &value); +if (!ret) +return 2 ; + +return rb_destroy (rbtree); +}The comment says
rb_findshould return-EINVALwhen looking for a non-existent key in an empty tree, but looking atrb_findinrbtree.bpf.c:int
rb_find(rbtree_t *rbtree, u64 key, u64 *value){ rbnode_t *node; if (unlikely(!rbtree)) return -EINVAL; if (unlikely(!value)) return -EINVAL; node = rbnode_find(rbtree->root, key, RBN_FIND_DFL); if (!node || node->key != key) return -ENOENT; ^^^^
Quoted 4 lines
rb_findreturns-EINVALonly when rbtree or value is NULL. For a valid rbtree with no matching node,rbnode_findreturns NULL andrb_findreturns-ENOENT. Should the comment say "Should return-ENOENT" instead?
Ack.
Quoted 147 lines
[ ... ]
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0@@ -0,0 +1,1032 @@[ ... ]
Quoted 35 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +35
-0+static +rbnode_t *rbnode_find (rbnode_t *subtree,u64 key,enum rbnode_find_mode mode) +{ +rbnode_t *node = subtree; +int dir; + +if (!subtree) +return NULL ; + +while (can_loop) { +/* +* If we are not looking for the least upper bound, +* we have found the only key. Otherwise keep going +* until we find the "leftmost" instance of the key. +*/ +if (mode ==RBN_FIND_DFL && node->key == key) +break ; + + dir = (key <= node->key) ?0 :1 ; + +if (!node->child[dir]) +break ; + +/* +* For least upper bound lookups, ensure that we +* stop searching once we find the rightmost key. +*/ +if (node->key == key && node->child[dir]->key != key) +break ; + + node = node->child[dir]; + } + +return node; +}[ ... ]
Quoted 40 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +40
-0+static +int rb_node_insert(rbtree_t *rbtree __arg_arena, rbnode_t *node __arg_arena) +{ +rbnode_t *grandparent, *parent = rbtree->root; +enum rbnode_find_mode mode; +u64 key = node->key; +rbnode_t *uncle; +int dir; +int ret; + +if (unlikely (!rbtree)) +return -EINVAL ; + +if (!parent) { + rbtree->root = node; +return 0 ; + } + + mode =RBN_FIND_DFL ; +/* Always find the first node with the key when allowing duplicates. */ +if (rbtree->insert ==RB_DUPLICATE ) + mode =RBN_FIND_LUB ; + parent =rbnode_find (parent, key, mode); + +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 (rbtree, parent); + +return 0 ; + } +tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 310
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;Can this overwrite an existing left subtree in
RB_DUPLICATEmode?When
rbnode_findis called withRBN_FIND_LUBmode, it has a third break condition that stops the search when it finds a node with a matching key whose next-direction child has a different key:rbnode_find() { ... if (node->key == key && node->child[dir]->key != key) break; ... }With key ==
node->key, dir is computed as (key <=node->key) ? 0 : 1 = 0. The search stops at a matching node that has a non-NULL left child with a smaller key.Back in
rb_node_insert, the code skips theRB_DEFAULTcheck whenrbtree->insert==RB_DUPLICATE, and falls through to:node->parent = parent; /* Also works if key == parent->key. */ if (key <= parent->key) parent->left = node;Since key ==
parent->key, the condition is true andparent->leftis overwritten with the new node. Butparent->leftalready points to an existing subtree (the smaller node that triggered the third break condition). That existing left child is overwritten, orphaning its entire subtree.Reproduction:
1)rb_insert(rbtree, 5, v1)inRB_DUPLICATEmode -> tree: {5}
2)rb_insert(rbtree, 3, v2)-> tree: {5->left = 3}
3)rb_insert(rbtree, 5, v3)In step 3,
rbnode_findreturns the root node 5 via the third break condition (because child 3 has key != 5). Thenrb_node_insertsetsparent->left=new_node, overwriting the pointer to node 3. Node 3 is now orphaned and leaked.The comment claims "Also works if key ==
parent->key", but this only holds whenrbnode_findreturns a node with an empty left slot, as in the typical duplicate-chain case where all keys are identical. As soon as a duplicate insertion meets a matching node that has a pre-existing smaller left child, the assignment corrupts the tree.
Quoted 6 lines
The tree integrity check in
rb_integrity_checkwalks only nodes reachable from the root, so it does not detect orphaned nodes. The existing testtest_rbtree_duplicateuses a single key value for all insertions, so it never exercises the interleaved case where a smaller key exists between duplicates.
This is accurate. This is a bug introduced when refactoring the least_upper_bound() and find() internal methods that were almost identical. Will fix in the next iteration.
Quoted 6 lines
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/25699461713
[email protected]
AI reviewRe: [RESEND PATCH bpf-next 1/2] selftests/bpf: libarena: Add rbtree data structure
In reply to Emil TsalapatisThank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [High] Inserting duplicate keys into an `RB_DUPLICATE` rbtree overwrites existing subtrees, causing data…
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [High] Inserting duplicate keys into an RB_DUPLICATE rbtree overwrites existing subtrees, causing data loss and memory leaks.
- [High] The lock-free node freelist implementation is vulnerable to the ABA problem, leading to tree corruption. --
commit 1c2293fc665383e2481f9d7ee15173fb46b0ea76
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 (key-value based, node based) and uses the libarena memory allocator to manage its data.
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0@@ -0,0 +1,1032 @@
[ ... ]
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +4
-0+static inline rbnode_t *rb_node_alloc_common(rbtree_t *rbtree __arg_arena, u64 key, u64 value) +{ +rbnode_t *rbnode =NULL ; +
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 215
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+if (unlikely (!rbtree)) +return NULL ; + +/* Use the built-in node cache for the rbtree to avoid going to the allocator. */ +do { + rbnode = rbtree->freelist; +if (!rbnode) +break ; + + }while (cmpxchg (&rbtree->freelist, rbnode, rbnode->parent) != rbnode && can_loop);
Could this lock-free freelist implementation be vulnerable to the ABA problem in concurrent environments?
If Thread A reads rbtree->freelist and evaluates rbnode->parent, and is then delayed, Thread B could allocate rbnode, allocate its parent, and then free rbnode back to the freelist. When Thread A resumes, the cmpxchg would succeed because the freelist head is still rbnode, but it would erroneously set the freelist head to the stale rbnode->parent. This could cause the allocator to hand out an in-use tree node, leading to multiple concurrent uses of the same memory and tree corruption.
[ ... ]
Quoted 40 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +40
-0+static +int rb_node_insert(rbtree_t *rbtree __arg_arena, rbnode_t *node __arg_arena) +{ +rbnode_t *grandparent, *parent = rbtree->root; +enum rbnode_find_mode mode; +u64 key = node->key; +rbnode_t *uncle; +int dir; +int ret; + +if (unlikely (!rbtree)) +return -EINVAL ; + +if (!parent) { + rbtree->root = node; +return 0 ; + } + + mode =RBN_FIND_DFL ; +/* Always find the first node with the key when allowing duplicates. */ +if (rbtree->insert ==RB_DUPLICATE ) + mode =RBN_FIND_LUB ; + parent =rbnode_find (parent, key, mode); + +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 (rbtree, parent); + +return 0 ; + } +
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 310
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;
Does this code overwrite existing subtrees when inserting duplicate keys into an RB_DUPLICATE rbtree?
When rbnode_find() is called with RBN_FIND_LUB, it can break early when it finds the target key whose child in the search direction has a different key:
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c:rbnode_find() {
...
/*
* For least upper bound lookups, ensure that we
* stop searching once we find the rightmost key.
*/
if (node->key == key && node->child[dir]->key != key)
break;
...
}This causes it to return an internal node where node->child[dir] is explicitly not NULL. Back in rb_node_insert(), the new node is unconditionally assigned to parent->left or parent->right. This blindly overwrites the existing child pointer, permanently detaching and leaking the previous subtree.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Re: [RESEND PATCH bpf-next 1/2] selftests/bpf: libarena: Add rbtree data structure
In reply to Emil TsalapatisQuoted 9 lines · Emil Tsalapatis
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.
Signed-off-by Emil Tsalapatis <[email protected]>--- .../bpf/libarena/include/libarena/rbtree.h | 89 ++ .../bpf/libarena/selftests/st_rbtree.bpf.c | 974 ++++++++++++++++
st_ is too obscure. Use test_ ?
Review
Quoted 2 lines
(quoted diff) +2
-0+SEC("syscall") +__weak int test_rbtree_insert_one(void)
None of these tests check parallel operations, right? Let's add them and add the lock.
Not sure what's the point of lockless rbtree->freelist when the whole thing still needs to be locked?
imo there is no point in single threaded primitives. Only syscall prog can be single threaded. The rest run in parallel.
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 238
Quoted 2 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +2
-0+arena_stderr ("WARNING: Attempting to allocate a node " +"for a NULL rbtree\n" );
Don't split strings, since it's harder to grep for them. It's ok that they're long and go over 80 or ever 100 chars.
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 873
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+__weak +int rb_print_pop_up (rbnode_t **rbnode,u8 *depthp,enum rb_print_state (*stack)[RB_MAXLVL_PRINT ],enum rb_print_state *state) +{ +volatile u8 depth; +int j; + +if (unlikely (!rbnode || !depthp || !stack || !state)) +return -EINVAL ; + +WRITE_ONCE (depth, *depthp);
WRITE_ONCE? what for?
Emil Tsalapatis
reviewerPATCH RESEND 2/2 selftests/bpf: libarena: Add Lev-Chase queue data structure
In reply to Emil TsalapatisExpand libarena with a Lev-Chase deque data structure. This is a single producer, multiple consumer lockless queue that permits efficient work stealing. The structure is lock-free and wait-free to minimize overhead.
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:
lvqueue_owner_push(): Push an item to the top of the lvqueue. lvqueue_owner_pop(): Pop an item from the top of the lvqueue. lvqueue_steal(): Steal a thread from the bottom of the lvqueue from any thread.
--- .../bpf/libarena/include/libarena/lvqueue.h | 33 +++ .../bpf/libarena/selftests/st_lvqueue.bpf.c | 194 ++++++++++++++ .../selftests/bpf/libarena/src/lvqueue.bpf.c | 241 ++++++++++++++++++ 3 files changed, 468 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h new file +33 -0
@@ -0,0 +1,33 @@ +/* SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause */ + +#pragma once + +struct lv_arr ; + +#define LV_ARR_BASESZ 128 +#define LV_ARR_ORDERS 10 + +struct lv_arr { + u64 __arena *data; +u64 order; +}; + +typedef volatile struct lv_arr __arena lv_arr_t; + +struct lv_queue { +lv_arr_t *cur; +volatile u64 top; +volatile u64 bottom; +struct lv_arr arr[LV_ARR_ORDERS ]; +}; + +typedef struct lv_queue __arena lv_queue_t; + +int lvq_owner_push (lv_queue_t *lvq,u64 val); +int lvq_owner_pop (lv_queue_t *lvq,u64 *val); +int lvq_steal (lv_queue_t *lvq,u64 *val); + +u64 lvq_create_internal (void ); +#define lvq_create () ((lv_queue_t *)lvq_create_internal()) + +int lvq_destroy (lv_queue_t *lvq);
tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c new file +194 -0
194 lines not on this page · raw message
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +241 -0
241 lines not on this page · raw message
Signature · 1 line
2.54.0
[email protected]
AI reviewRe: [RESEND PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure
The API names in the commit message don't match the actual functions. Looking at tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h:
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:
lvqueue_owner_push(): Push an item to the top of the lvqueue.lvqueue_owner_pop(): Pop an item from the top of the lvqueue.lvqueue_steal(): Steal a thread from the bottom of the lvqueue from any thread.
The API names in the commit message don't match the actual functions. Looking at tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h:
int lvq_owner_push(lv_queue_t *lvq, u64 val);
int lvq_owner_pop(lv_queue_t *lvq, u64 *val);
int lvq_steal(lv_queue_t *lvq, u64 *val);The functions use 'lvq_' prefix, not 'lvqueue_'.
Also, the commit message describes push/pop as operating on the 'top' and steal as operating on the 'bottom', while the code follows the standard Chase-Lev convention where the owner operates at 'bottom' and stealers at 'top'. In lvq_owner_push():
b = smp_load_acquire(&lvq->bottom);
...
lv_arr_put(lvq->cur, b, val);
smp_store_release(&lvq->bottom, b + 1);And in lvq_steal():
t = smp_load_acquire(&lvq->top);
...
if (cmpxchg(&lvq->top, t, t + 1) != t)Could the commit message use the correct API names and clarify the terminology to match the variable names in the code?
[ ... ]
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +0
-0@@ -0,0 +1,241 @@
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 52
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +10
-0+static inline +int lvq_order_init(lv_queue_t *lvq __arg_arena, int order) +{ +lv_arr_t *arr = &lvq->arr[order]; + +if (unlikely (!lvq)) +return -EINVAL ; + +if (order >=LV_ARR_ORDERS ) +return -E2BIG ;
The pointer 'arr' is computed from '&lvq->arr[order]' before both the NULL check and the bounds check. Although this pointer is never dereferenced on the failure paths, forming a pointer more than one past the end of an array is undefined behavior per C17 6.5.6p8.
This can occur when lvq_owner_push() calls lvq_order_init(lvq, arr->order + 1) with arr->order + 1 == LV_ARR_ORDERS.
Since this function is marked '__arg_arena' and invoked by BPF programs, the verifier may reject the out-of-bounds pointer arithmetic. Should the 'arr' assignment be moved after both checks?
[ ... ]
---
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/25699461713
Emil Tsalapatis
reviewerRe: [RESEND PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure
Quoted 27 lines · bot+bpf-ci
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:
lvqueue_owner_push(): Push an item to the top of the lvqueue.lvqueue_owner_pop(): Pop an item from the top of the lvqueue.lvqueue_steal(): Steal a thread from the bottom of the lvqueue from any thread.The API names in the commit message don't match the actual functions. Looking at
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h:int lvq_owner_push(lv_queue_t *lvq, u64 val); int lvq_owner_pop(lv_queue_t *lvq, u64 *val); int lvq_steal(lv_queue_t *lvq, u64 *val);The functions use '
lvq_' prefix, not 'lvqueue_'.Also, the commit message describes push/pop as operating on the 'top' and steal as operating on the 'bottom', while the code follows the standard Chase-Lev convention where the owner operates at 'bottom' and stealers at 'top'. In
lvq_owner_push():b = smp_load_acquire(&lvq->bottom); ... lv_arr_put(lvq->cur, b, val); smp_store_release(&lvq->bottom, b + 1);
Quoted 8 lines
And in
lvq_steal():t = smp_load_acquire(&lvq->top); ... if (cmpxchg(&lvq->top, t, t + 1) != t)Could the commit message use the correct API names and clarify the terminology to match the variable names in the code?
Ack, will clean up.
Quoted 28 lines
[ ... ]
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +0
-0@@ -0,0 +1,241 @@[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 52
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +10
-0+static inline +int lvq_order_init(lv_queue_t *lvq __arg_arena, int order) +{ +lv_arr_t *arr = &lvq->arr[order]; + +if (unlikely (!lvq)) +return -EINVAL ; + +if (order >=LV_ARR_ORDERS ) +return -E2BIG ;The pointer 'arr' is computed from '&lvq->arr[order]' before both the NULL check and the bounds check. Although this pointer is never dereferenced on the failure paths, forming a pointer more than one past the end of an array is undefined behavior per C17 6.5.6p8.
Quoted 7 lines
This can occur when
lvq_owner_push()callslvq_order_init(lvq, arr->order + 1)witharr->order+ 1 ==LV_ARR_ORDERS.Since this function is marked '
__arg_arena' and invoked by BPF programs, the verifier may reject the out-of-bounds pointer arithmetic. Should the 'arr' assignment be moved after both checks?
Will move the pointer calculation to its proper place, thought the bit about verifier failures is completely extrapolated - this is an arena, of course we can do any pointer arithmetic we like.
Quoted 8 lines
[ ... ]
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/25699461713
[email protected]
AI reviewRe: [RESEND PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure
In reply to Emil TsalapatisThank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider: - [High] Use of undefined `malloc()` and `free()` instead of `arena_malloc()` and `arena_free()` - [High]…
Thank you for your contribution! Sashiko AI review found 3 potential issue(s) to consider:
- [High] Use of undefined malloc() and free() instead of arena_malloc() and arena_free()
- [High] Missing acquire memory barrier when reading lvq->bottom in lvq_steal() leads to stealing uninitialized data
- [High] Early loop termination via can_loop causes silent data corruption and wild pointer frees --
commit f362e0549cb75d0f854b07e362d4f47abea9daf9
Author: Emil Tsalapatis <[email protected]>
selftests/bpf: libarena: Add Lev-Chase queue data structure
Expand libarena with a Lev-Chase deque data structure. This is a single producer, multiple consumer lockless queue that permits efficient work stealing. The structure is lock-free and wait-free to minimize overhead.
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +0
-0
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 39
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +6
-0+static inline +void lv_arr_copy (lv_arr_t *dst,lv_arr_t *src,u64 b,u64 t) +{ +u64 i; + +for (i = t; i < b && can_loop; i++)
If can_loop breaks early, won't this array expansion silently abort without copying all queue items?
lvq_owner_push() doesn't seem to have error handling for this, which might lead to published, partially empty arrays and permanent queue data loss.
Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +6
-0+lv_arr_put (dst, i,lv_arr_get (src, i)); +} + +static inline +int lvq_order_init(lv_queue_t *lvq __arg_arena, int order) +{
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 58
Quoted 1 line
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +1
-0+ arr->data = (u64 __arena *)malloc((LV_ARR_BASESZ << order) * sizeof(*arr->data));
Should this be arena_malloc() instead?
Standard C library functions are typically not available during BPF target compilation, which could cause build or linker errors due to undefined symbols.
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +5
-0+if (!arr->data) +return -ENOMEM ; + +return 0 ; +}
[ ... ]
Quoted 12 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +12
-0+__weak +int lvq_steal(lv_queue_t *lvq __arg_arena, u64 *val) +{ +volatile u64 b, t; +lv_arr_t *arr; +ssize_t sz; +u64 value; + +if (unlikely (!lvq || !val)) +return -EINVAL ; + + t =smp_load_acquire (&lvq->top);
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 175
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +10
-0+ +/* +* It is important that t is read before b for +* stealers to avoid racing with the owner. +* Races between stealers are dealt with using +* CAS to increment the top value below. +*/ +smp_rmb (); + + b =READ_ONCE (lvq->bottom);
Could reading lvq->bottom without smp_load_acquire() (or a following smp_rmb()) cause the stealer to read uninitialized data?
In lvq_owner_push(), the array is updated before lvq->bottom is updated via smp_store_release(). On weakly ordered CPUs like ARM64, the control dependency (sz <= 0) below does not guarantee read-to-read ordering.
Could the CPU speculatively execute lv_arr_get(arr, t) before fetching the updated lvq->bottom, resulting in a successful steal of garbage data?
Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +7
-0+ arr =READ_ONCE (lvq->cur); + + sz = b - t; +if (sz <=0 ) +return -ENOENT ; + + value =lv_arr_get (arr, t);
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 204
Quoted 12 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +12
-0+__weak +u64 lvq_create_internal (void ) +{ +/* +* Marked as volatile because otherwise the array +* reference in the internal loop gets demoted to +* scalar and the program fails verification. +*/ +volatile lv_queue_t *lvq; +int ret, i; + + lvq =malloc (sizeof (*lvq));
Is it possible this should be arena_malloc() as well?
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 211
Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +7
-0+if (!lvq) +return (u64 )NULL ; + +WRITE_ONCE (lvq->bottom,0 ); +WRITE_ONCE (lvq->top,0 ); + +for (i =0 ; i <LV_ARR_ORDERS && can_loop; i++) {
If this initialization loop terminates early due to can_loop, will the remaining lvq->arr[i].data pointers retain uninitialized memory from the allocation?
If so, could the subsequent iteration in lvq_destroy() call free() on those wild pointers, causing memory corruption?
Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +3
-0+ lvq->arr[i].data =NULL ; + lvq->arr[i].order = i; + }
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 236
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +10
-0+__weak +int lvq_destroy(lv_queue_t *lvq __arg_arena) +{ +int i; + +if (unlikely (!lvq)) +return -EINVAL ; + +for (i =0 ; i <LV_ARR_ORDERS && can_loop; i++) +free (lvq->arr[i].data);
Should these be arena_free() calls?
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +5
-0+ +free (lvq); + +return 0 ; +}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Re: [RESEND PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure
In reply to Emil TsalapatisQuoted 6 lines · Emil Tsalapatis
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h new file +6
-0+ +struct lv_queue { +lv_arr_t *cur; +volatile u64 top; +volatile u64 bottom; +struct lv_arr arr[LV_ARR_ORDERS ];
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h line 31
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h new file +10
-0+}; + +typedef struct lv_queue __arena lv_queue_t; + +int lvq_owner_push (lv_queue_t *lvq,u64 val); +int lvq_owner_pop (lv_queue_t *lvq,u64 *val); +int lvq_steal (lv_queue_t *lvq,u64 *val); + +u64 lvq_create_internal (void ); +#define lvq_create () ((lv_queue_t *)lvq_create_internal())
workaround for some verifier issue?
Quoted 5 lines
+/*
+ * NOTE: These selftests only test for the single-threaded use case, which for
+ * Lev-Chase queues is obviously the simplest one. Still, it is important to
+ * exercise the API to ensure it passes verification and basic checks.
+ */
and multi-thread test pls :)
Re: [RESEND PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure
In reply to Emil TsalapatisQuoted 47 lines · Emil Tsalapatis
Expand libarena with a Lev-Chase deque data structure. This is a single producer, multiple consumer lockless queue that permits efficient work stealing. The structure is lock-free and wait-free to minimize overhead.
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:
lvqueue_owner_push(): Push an item to the top of the lvqueue.lvqueue_owner_pop(): Pop an item from the top of the lvqueue.lvqueue_steal(): Steal a thread from the bottom of the lvqueue from any thread.Signed-off-by Emil Tsalapatis <[email protected]>--- .../bpf/libarena/include/libarena/lvqueue.h | 33 +++ .../bpf/libarena/selftests/st_lvqueue.bpf.c | 194 ++++++++++++++ .../selftests/bpf/libarena/src/lvqueue.bpf.c | 241 ++++++++++++++++++ 3 files changed, 468 insertions(+) create mode 100644 tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h create mode 100644 tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c create mode 100644 tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.ctools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h new file +18
-0@@ -0,0 +1,33 @@ +/* SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause */ + +#pragma once + +struct lv_arr ; + +#define LV_ARR_BASESZ 128 +#define LV_ARR_ORDERS 10 + +struct lv_arr { + u64 __arena *data; +u64 order; +}; + +typedef volatile struct lv_arr __arena lv_arr_t; + +struct lv_queue { +lv_arr_t *cur;
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h line 28
Quoted 10 lines
tools/testing/selftests/bpf/libarena/include/libarena/lvqueue.h new file +10
-0+volatile u64 top; +volatile u64 bottom; +struct lv_arr arr[LV_ARR_ORDERS ]; +}; + +typedef struct lv_queue __arena lv_queue_t; + +int lvq_owner_push (lv_queue_t *lvq,u64 val); +int lvq_owner_pop (lv_queue_t *lvq,u64 *val); +int lvq_steal (lv_queue_t *lvq,u64 *val);
One more thing.
I feel the actual alogrithm name doesn't need to be in the name. Maybespmc_queue_push()spmc_queue_pop()
?