Skip to contentSkip to conversation

selftests/bpf: libarena: Add initial data structures

PATCH Superseded Emil Tsalapatis 3 participants 11 messages Jun 3 – Jun 5

Subsystems (3)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Emil Tsalapatis

author reviewer
#0 lore raw

v2 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
=========

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        |  659 +++++++++++
 .../bpf/libarena/selftests/test_rbtree.bpf.c  |  968 ++++++++++++++++
 .../bpf/libarena/selftests/test_spmc.bpf.c    |  194 ++++
 .../selftests/bpf/libarena/src/rbtree.bpf.c   | 1015 +++++++++++++++++
 .../selftests/bpf/libarena/src/spmc.bpf.c     |  232 ++++
 .../selftests/bpf/prog_tests/libarena.c       |  157 +++
 9 files changed, 3341 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
author reviewer
#1 lore raw

PATCH v2 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   | 1015 +++++++++++++++++
 3 files changed, 2066 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
new file mode 100644
index 000000000000..486428911d96
@@ -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 +1015 -0

1,015 lines not on this page · raw message

Signature · 1 line
2.54.0
#2 lore raw

Re: [PATCH bpf-next v2 1/3] selftests/bpf: libarena: Add rbtree data structure

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider: - [Medium] rb_print() causes a NULL pointer dereference when called on an empty tree. - [Medium]…

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
- [Medium] rb_print() causes a NULL pointer dereference when called on an empty tree.
- [Medium] rb_destroy() leaks the rbtree structure if node removal fails. --

commit 02f60ec9e8c02b47259587dc8e3bbe9137e1e4ed
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 to query and modify the tree, using the libarena memory allocator to manage its data.

Quoted 5 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +0 -0
new file mode 100644
index 0000000000000..7379eba6570af

[ ... ]

Quoted 8 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +8 -0
+__weak
+int rb_destroy(struct rbtree __arena *rbtree)
+{
+	int ret;
+
+	arena_subprog_init();
+
+	if (rbtree->alloc == RB_NOALLOC) {

[ ... ]

tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 74

Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +7 -0
+		goto out;
+	}
+
+	while (rbtree->root && can_loop) {
+		ret = rb_remove(rbtree, rbtree->root->key);
+		if (ret)
+			return ret;

[Severity: Medium]
Does this leak the rbtree structure if rb_remove() fails?

If rb_remove() encounters an error (for example, due to tree corruption), it returns early here. This skips the arena_free(rbtree) call at the out label, potentially leaking the rbtree structure and any remaining nodes.

Quoted 6 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +6 -0
+	}
+
+out:
+	arena_free(rbtree);
+	return 0;
+}

[ ... ]

Quoted 13 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +13 -0
+__weak
+int rb_print(struct rbtree __arena *rbtree)
+{
+	enum rb_print_state stack[RB_MAXLVL_PRINT];
+	struct rbnode __arena *rbnode = rbtree->root;
+	enum rb_print_state state;
+	struct rbnode __arena *next;
+	u64 next_addr;
+	u8 depth;
+	int ret;
+
+	if (unlikely(!rbtree))
+		return -EINVAL;

tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c line 893

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +10 -0
+
+	depth = 0;
+	state = RB_NONE_VISITED;
+
+	arena_stderr("=== RB TREE START ===\n");
+
+	/* Even with can_loop, the verifier doesn't like infinite loops. */
+	while (can_loop) {
+		if (state == RB_NONE_VISITED)
+			rbnode_print(depth, rbnode);

[Severity: Medium]
Does this cause a NULL pointer dereference if the tree is empty?

If a user calls rb_print() on an empty tree, rbtree->root is NULL. The loop is entered and rb_print() passes the NULL rbnode to rbnode_print().

Looking at rbnode_print(), it unconditionally dereferences the node:

inline void rbnode_print(size_t depth, struct rbnode __arena *rbn)

{
        arena_stderr("[DEPTH %d] %p (%s)\n PARENT %p", depth, rbn,
                     rbn->is_red ? "red" : "black", rbn->parent);
        ...
}

Could this lead to a crash when calling rb_print() on an empty tree?

Quoted 3 lines
tools/testing/selftests/bpf/libarena/src/rbtree.bpf.c new file +3 -0
+
+		/* Find which child to traverse next. */
+		state = rb_print_next_state(rbnode, state, &next_addr);
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
author reviewer
#3 lore raw

PATCH v2 2/3 selftests/bpf: libarena: Add spmc queue data structure

In reply to Emil Tsalapatis

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.

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     | 232 ++++++++++++++++++
 3 files changed, 453 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
new file mode 100644
index 000000000000..75611276ce13
@@ -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 +232 -0

232 lines not on this page · raw message

Signature · 1 line
2.54.0
#4 lore raw

Re: [PATCH bpf-next v2 2/3] selftests/bpf: libarena: Add spmc queue data structure

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] Duplicate pops occur in spmc_owned_remove. --

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] Duplicate pops occur in spmc_owned_remove.
--

commit 32e23022b6cf8e4bb5da76036f824fc171bf9e71
Author: Emil Tsalapatis <[email protected]>

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 5 lines
tools/testing/selftests/bpf/libarena/src/spmc.bpf.c new file +0 -0
new file mode 100644
index 0000000000000..7fd7b18a03732

[ ... ]

Quoted 7 lines
tools/testing/selftests/bpf/libarena/src/spmc.bpf.c new file +7 -0
+__weak
+int spmc_owned_remove(struct spmc __arena *spmc, u64 *val)
+{
+	volatile struct spmc_arr __arena *arr;
+	int ret = 0;
+	ssize_t sz;
+	u64 value;

tools/testing/selftests/bpf/libarena/src/spmc.bpf.c line 121

Quoted 10 lines
tools/testing/selftests/bpf/libarena/src/spmc.bpf.c new file +10 -0
+	u64 b, t;
+
+	if (unlikely(!spmc || !val))
+		return -EINVAL;
+
+	b = smp_load_acquire(&spmc->bottom) - 1;
+	t = smp_load_acquire(&spmc->top);
+	arr = READ_ONCE(spmc->cur);
+
+	smp_store_release(&spmc->bottom, b);

[Severity: Medium]
Could this ordering result in duplicate pops?

Because top is read before bottom is updated here, could stealers erroneously consume the same item as the owner? In a standard Chase-Lev queue, storing bottom before evaluating top, separated by a full memory barrier, is required to avoid this race.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
author reviewer
#5 lore raw

PATCH v2 3/3 selftests/bpf: libarena: parallel test harness and spmc parallel selftest

In reply to Emil Tsalapatis

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.

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        | 659 ++++++++++++++++++
 .../selftests/bpf/prog_tests/libarena.c       | 157 +++++
 3 files changed, 822 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
index 88b68ac73cca..fc27a4bcf5d7 100644
@@ -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 +659 -0

659 lines not on this page · raw message

tools/testing/selftests/bpf/prog_tests/libarena.c +157 -0

169 lines not on this page · raw message

Signature · 1 line
2.54.0
#6 lore raw

Re: [PATCH bpf-next v2 3/3] selftests/bpf: libarena: parallel test harness and spmc parallel selftest

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider: - [High] Worker threads can spin indefinitely without checking `test_abort`, causing a soft lockup.…

Thank you for your contribution! Sashiko AI review found 4 potential issue(s) to consider:
- [High] Worker threads can spin indefinitely without checking test_abort, causing a soft lockup.
- [Medium] Missing BPF FD Validation after manual program lookup.
- [Medium] Thread synchronization loops use a spin limit that is too low, causing flakiness.
- [Low] Returning a boolean flag as an error code.
--

commit 4565a6a5313dffad1dda425572fe86afb75dd583
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.

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.

Quoted 6 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +0 -0
new file mode 100644
index 0000000000000..3d9fe3f579c87
@@ -0,0 +1,659 @@

[ ... ]

tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c line 20

Quoted 8 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +8 -0
+/*
+ * The test requires the stealers/owners to sometimes quiesce
+ * before continuing the benchmark. Normally we'd use something
+ * like a condition variable, but since the benchmark is short-lived
+ * and operations are wait-free we just spin around the quiescence
+ * point instead. If we time out, we just fail the benchmark.
+ */
+#define TEST_SPMC_SYNC_SPINS (1U << 18)

[Severity: Medium]
Is this iteration limit sufficient for thread synchronization here?

Since a simple read loop of this size takes a fraction of a millisecond in kernel space, if the OS delays scheduling the worker threads, could this loop time out prematurely and incorrectly fail the test with -ETIMEDOUT?

[ ... ]

Quoted 7 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +7 -0
+static int spmc_resize_stealer(void)
+{
+	u64 val;
+	int ret;
+
+	arena_subprog_init();
+

tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c line 486

Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +10 -0
+	ret = spmc_quiesce_on_owner(1);
+	if (ret)
+		return ret;
+
+	__sync_fetch_and_add(&stealers_started, 1);
+
+	while (can_loop) {
+		spmc_waste_time();
+
+		ret = spmc_steal(spmc, &val);

[Severity: High]
If the owner thread fails and sets test_abort = true, could this loop spin indefinitely because it doesn't check test_abort?

Quoted 6 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +6 -0
+		if (!ret) {
+			ret = spmc_update_stats(val, false);
+			if (ret)
+				return ret;
+			continue;
+		}

[ ... ]

tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c line 535

Quoted 9 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +9 -0
+static int spmc_wait_for_round_steals(u64 target)
+{
+	u64 i;
+
+	arena_subprog_init();
+
+	bpf_for(i, 0, TEST_SPMC_SYNC_SPINS) {
+		if (test_abort)
+			return test_abort;

[Severity: Low]
Does this unintentionally return 1 instead of a negative error code like -EINTR?

Quoted 3 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +3 -0
+		if (round_steals >= target)
+			return 0;
+	}

[ ... ]

Quoted 9 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +9 -0
+static int spmc_burst_stealer(void)
+{
+	u64 round, val, active_epoch;
+	int ret;
+
+	arena_subprog_init();
+
+	for (round = zero; round < TEST_SPMC_BURST_ROUNDS && can_loop; round++) {
+		active_epoch = round * 2 + 1;

tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c line 637

Quoted 10 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +10 -0
+
+		/*
+		 * Wait till the owner prefills the queue then
+		 * start stealing.
+		 */
+		ret = spmc_quiesce_on_owner(active_epoch);
+		if (ret)
+			return ret;
+
+		while (owner_epoch == active_epoch && can_loop) {

[Severity: High]
Could this loop also hang indefinitely if the owner thread fails and sets test_abort = true without updating the epoch?

Quoted 3 lines
tools/testing/selftests/bpf/libarena/selftests/test_parallel_spmc.bpf.c new file +3 -0
+			ret = spmc_steal(spmc, &val);
+			if (!ret) {
+				ret = spmc_update_stats(val, false);

[ ... ]

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
index 81bdb084c2715..a42c1935eaf6e 100644
@@ -27,6 +27,147 @@ 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 the file descriptor from bpf_program__fd() be validated here before being passed to libarena_run_prog()?

Since run_libarena_parallel_test_workers() finds tdprog via a manual lookup (bpf_object__find_program_by_name), it doesn't have the same guarantees as skeleton fields. Could we use ASSERT_GE(fd, 0) to ensure we don't pass an invalid FD?

Quoted 2 lines
tools/testing/selftests/bpf/prog_tests/libarena.c +2 -0
+}
+
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=3
#7 lore raw
In reply to Emil Tsalapatis
Quoted 9 lines · Emil Tsalapatis

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.

Quoted 6 lines

- 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.

bpf CI says libarena tests are failing.

author reviewer
#8 lore raw
Quoted 10 lines · Alexei Starovoitov
Quoted 9 lines · Emil Tsalapatis

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.

Quoted 8 lines
Quoted 6 lines

- 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.

bpf CI says libarena tests are failing.

Looking into it, the issue is not manifesting with LLVM 22 so trying to see why. In the CI, the compiler is generating code that is doing the address space translation then still dereferencing the scalar instead of the PTR_TO_ARENA like so:

r0 = (scalar)
r1 = addr_space_cast(r0, 0, 1)
r2 = *(r0 + 16)

In my opinion if it's not a programming error we should prevent this kind of code sequence from happening.

#9 lore raw
Quoted 26 lines · Emil Tsalapatis
Quoted 10 lines · Alexei Starovoitov
Quoted 9 lines · Emil Tsalapatis

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.

Quoted 8 lines
Quoted 6 lines

- 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.

bpf CI says libarena tests are failing.

Looking into it, the issue is not manifesting with LLVM 22 so trying to see why. In the CI, the compiler is generating code that is doing the address space translation then still dereferencing the scalar instead of the PTR_TO_ARENA like so:

Quoted 6 lines

r0 = (scalar)
r1 = addr_space_cast(r0, 0, 1)
r2 = *(r0 + 16)

In my opinion if it's not a programming error we should prevent this kind of code sequence from happening.

That sounds like a llvm bug.
Pls craft a small reproducer and pass it to Yonghong.

author reviewer
#10 lore raw
Quoted 31 lines · Alexei Starovoitov
Quoted 30 lines · Emil Tsalapatis
Quoted 10 lines · Alexei Starovoitov
Quoted 9 lines · Emil Tsalapatis

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.

Quoted 8 lines
Quoted 6 lines

- 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.

bpf CI says libarena tests are failing.

Looking into it, the issue is not manifesting with LLVM 22 so trying to see why. In the CI, the compiler is generating code that is doing the address space translation then still dereferencing the scalar instead of the PTR_TO_ARENA like so:

r0 = (scalar)
r1 = addr_space_cast(r0, 0, 1)
r2 = *(r0 + 16)

Quoted 5 lines
Quoted 2 lines

In my opinion if it's not a programming error we should prevent this kind of code sequence from happening.

That sounds like a llvm bug.
Pls craft a small reproducer and pass it to Yonghong.

I fixed the issue for v3, but ftr this was a bug that was fixed in LLVM 22.1 (commit 94290f). I pinged Vineet because GCC was also failing with the exact same symptoms.