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
Signature · 1 line
2.54.0
Emil Tsalapatis
reviewerPATCH 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: [PATCH bpf-next 1/2] selftests/bpf: libarena: Add rbtree data structure
Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider: - [Critical] ABA vulnerability in lock-free freelist operations leads to memory corruption - [High]…
Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [Critical] ABA vulnerability in lock-free freelist operations leads to memory corruption
- [High] Inserting duplicate keys in RB_DUPLICATE mode silently overwrites subtrees and leaks memory
- [High] Unchecked early loop termination (can_loop) corrupts the tree structure and causes massive memory leaks
- [Medium] Missing build system integration renders new tests as dead code
--
commit 3a9a1af9570223a1c9cf74c5f2e9d724407fddac
Author: Emil Tsalapatis <[email protected]>
selftests/bpf: libarena: Add rbtree data structure
This commit adds a native red-black tree data structure to libarena. The data structure supports key-value and node-based APIs, and uses the libarena memory allocator to manage its data.
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c line 3
Quoted 9 lines
tools/testing/selftests/bpf/libarena/selftests/st_rbtree.bpf.c new file +3
-0@@ -0,0 +1,974 @@ +// SPDX-License-Identifier: LGPL-2.1 OR BSD-2-Clause + +#include <libarena/common.h>
These new test files are added to the selftests directory, but they do not appear to be integrated into the build system. Per the selftests subsystem guidelines, files not explicitly added to variables like TEST_PROGS or TEST_GEN_FILES in the Makefile won't be compiled or executed during normal runs. Should these be added to the Makefile?
[ ... ]
Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0
-0
[ ... ]
Quoted 25 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +25
-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
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 180
Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10
-0+* stop searching once we find the rightmost key. +*/ +if (node->key == key && node->child[dir]->key != key) +break ; + + node = node->child[dir]; + } + +return node; +}
When mode is RBN_FIND_LUB, this loop can break early and return an internal node that has a valid, non-NULL child. Back in rb_node_insert(), the new node is unconditionally assigned to parent->left (since key <= parent->key) which could silently overwrite the existing child pointer and leak the existing subtree. Does this correctly handle duplicate key insertions without detaching subtrees?
[ ... ]
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 lockless cmpxchg sequence suffer from the ABA problem?
If a thread is preempted after evaluating rbnode->parent but before executing cmpxchg, another thread could pop rbnode, allocate it, and free it back to the freelist with a completely different parent pointer. When the original thread resumes, the cmpxchg succeeds but erroneously sets the freelist head to the stale parent pointer. This could link an actively used tree node back into the freelist and lead to memory corruption.
[ ... ]
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 259
Quoted 12 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +12
-0+__weak +int rb_node_free(rbtree_t *rbtree __arg_arena, rbnode_t *rbnode __arg_arena) +{ +rbnode_t *old; + +do { + old = rbtree->freelist; + rbnode->parent = old; + }while (cmpxchg (&rbtree->freelist, old, rbnode) != old && can_loop); + +return 0 ; +}
Similarly, could this free implementation also be vulnerable to the ABA problem if the freelist head is rapidly popped and pushed concurrently?
[ ... ]
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 403
Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +7
-0+static inline rbnode_t *rbnode_least (rbnode_t *subtree) +{ +while (subtree->left && can_loop) + subtree = subtree->left; + +return subtree; +}
If the loop limit is reached and can_loop terminates early, could this return a node that still has a left child?
During node removal, this node would be swapped with the target node, leaving the target node with both left and potentially right children. The removal logic evaluates if (!node->left != !node->right) which would then bypass the single-child handler and fall through to the zero-child path, setting the parent's child pointer to NULL and leaking both subtrees. Are early loop terminations via can_loop safely handled without leaving the tree structure corrupted?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Emil Tsalapatis
reviewerPATCH 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: [PATCH bpf-next 2/2] selftests/bpf: libarena: Add Lev-Chase queue data structure
Thank you for your contribution! Sashiko AI review found 7 potential issue(s) to consider: - [High] Missing acquire memory barrier in `lvq_steal` allows speculative execution to read stale or…
Thank you for your contribution! Sashiko AI review found 7 potential issue(s) to consider:
- [High] Missing acquire memory barrier in lvq_steal allows speculative execution to read stale or uninitialized queue elements.
- [High] lvq_destroy unconditionally calls free() on NULL pointers, which corrupts the selftest memory allocator state.
- [High] The use of the test-specific can_loop macro in library data structure logic risks silent data loss and incomplete initialization.
- [Medium] Implicit signed-to-unsigned type promotion in deque resize logic could trigger erroneous array expansions.
- [Medium] The commit message incorrectly documents the data structure's push/pop semantics.
- [Low] Pointer arithmetic is performed on a potentially NULL pointer in lvq_order_init.
- [Low] Memory leaks in selftest error paths upon assertion failures.
--
commit c550e5013d289b25ae7b41bfdffc6d59d1302758
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.
Quoted 4 lines
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 code appears to implement standard Chase-Lev deque semantics where the owner operates at the bottom and stealers operate at the top.
Is the push and pop direction described in the commit message accurate?
Quoted 5 lines
tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c new file +0
-0
[ ... ]
Quoted 8 lines
tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c new file +7
-0@@ -0,0 +1,194 @@ +SEC("syscall") +int test_lvqueue_steal_one (void ) +{ +u64 val, newval; +int ret, i; + +lv_queue_t *lvq =lvq_create ();
tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c line 17
Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/st_lvqueue.bpf.c new file +10
-0+ +if (!lvq) +return 1 ; + +for (i =0 ; i <10 && can_loop; i++) { + val = i; + + ret =lvq_owner_push (lvq, val); +if (ret) +return 1 ;
Does this error path leak the queue's arena memory by returning without calling lvq_destroy(lvq)?
[ ... ]
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 8
Quoted 9 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +8
-0@@ -0,0 +1,241 @@ +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++) +lv_arr_put (dst, i,lv_arr_get (src, i)); +}
If the instruction budget is exhausted during a queue resize, the loop will terminate prematurely.
The caller lvq_owner_push() will then accept the partially copied array and replace the active queue, permanently dropping the uncopied elements without returning an error.
Can the use of the test-specific can_loop macro here cause silent data loss?
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 49
Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +7
-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 ;
Compilers might deduce that lvq cannot be NULL after pointer arithmetic and optimize away the subsequent if (!lvq) check entirely.
Does performing pointer arithmetic (&lvq->arr[order]) before checking if lvq is NULL result in undefined behavior?
[ ... ]
Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +3
-0+__weak +int lvq_owner_push(lv_queue_t *lvq __arg_arena, u64 val) +{
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 89
Quoted 2 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +2
-0+ sz = b - t; +if (sz >=lv_arr_size (arr) -1 ) {
Here sz is ssize_t (signed), but lv_arr_size() returns a u64 (unsigned). C type promotion rules will implicitly convert sz to an unsigned 64-bit integer.
If sz is ever negative, the unsigned promotion transforms it into a massive positive value, erroneously evaluating as greater than the array size.
Can this logic trigger an erroneous array expansion?
[ ... ]
Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +3
-0+__weak +int lvq_steal(lv_queue_t *lvq __arg_arena, u64 *val) +{
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 182
Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +8
-0+ b =READ_ONCE (lvq->bottom); + arr =READ_ONCE (lvq->cur); + + sz = b - t; +if (sz <=0 ) +return -ENOENT ; + + value =lv_arr_get (arr, t);
READ_ONCE() does not provide an acquire barrier, and control dependencies (like if (sz <= 0)) do not order read-to-read operations.
If a concurrent push occurs, the stealer could speculatively load the array element before loading the updated bottom index.
Does reading lvq->bottom with READ_ONCE() allow speculative execution to read stale or uninitialized queue elements on weakly-ordered architectures? Should lvq->bottom be read using smp_load_acquire() instead?
[ ... ]
Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +3
-0+__weak +u64 lvq_create_internal (void ) +{
[ ... ]
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c line 214
Quoted 4 lines
tools/testing/selftests/bpf/libarena/src/lvqueue.bpf.c new file +4
-0+for (i =0 ; i <LV_ARR_ORDERS && can_loop; i++) { + lvq->arr[i].data =NULL ; + lvq->arr[i].order = i; + }
Can an early termination of this loop due to can_loop leave array pointers uninitialized, leading to undefined behavior later?
[ ... ]
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);
The selftest free() implementation in mm.h does not check for NULL pointers and unconditionally decrements malloc_count:
MALLOC_VISIBLE void free(void *where)
{
malloc_count--;
if (!malloc_count)
malloc_ptr = free_mem_ptr;
}Since arrays are allocated lazily, higher-order array pointers will be NULL. Calling free() on these unallocated slots will drive malloc_count negative and permanently prevent the allocator from resetting the memory arena.
Can calling free() unconditionally on potentially NULL pointers corrupt the selftest memory allocator state?
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