From 33a154a96e71a34a1bcca9f40da343dbbf7b38b4 Mon Sep 17 00:00:00 2001 From: Alexei Starovoitov Date: Thu, 1 Oct 2026 14:52:55 +0000 Subject: selftests/bpf: Test packet range of pointers sharing an id Add tests where two packet pointers share an id and tightening one pointer's umax from its var_off would put it less than their constant distance from the other's umax: with an index & 0x38 capped at 50, the base pointer keeps umax 50, so the pointer 8 bytes further on must keep umax 58, even though its known bits allow at most 56. These refused a valid program or accepted an out-of-bounds access before the fix: - check the advanced copy, load through the base: valid, was refused; - check the base, load the byte at base + 1 through a copy advanced by 8: was accepted; - check base + 4, load 4 bytes at base + 2 through base + 8: reads two bytes past the checked range, was accepted; - the same as the second with data_meta pointers checked against data: was accepted. These pass with and without the fix and cover nearby paths: - subtract an unknown scalar from a checked pointer and load below it (the range is kept across a new id); - reach a load through two paths whose checks cover 8 and 7 bytes after the loaded pointer; the second path must not be pruned by the first; - spill a copy of a pointer, check the pointer, fill the copy and load one byte past the checked range: the load is refused, and the copy has the range of the check. Signed-off-by: Alexei Starovoitov Link: https://lore.kernel.org/bpf/20261001145255.855630-2-alexei.starovoitov@gmail.com Signed-off-by: Kumar Kartikeya Dwivedi --- lib/lwq.c | 158 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 158 insertions(+) create mode 100644 lib/lwq.c (limited to 'lib/lwq.c') diff --git a/lib/lwq.c b/lib/lwq.c new file mode 100644 index 000000000..c1e11ba6f --- /dev/null +++ b/lib/lwq.c @@ -0,0 +1,158 @@ +// SPDX-License-Identifier: GPL-2.0-only +/* + * Light-weight single-linked queue. + * + * Entries are enqueued to the head of an llist, with no blocking. + * This can happen in any context. + * + * Entries are dequeued using a spinlock to protect against multiple + * access. The llist is staged in reverse order, and refreshed + * from the llist when it exhausts. + * + * This is particularly suitable when work items are queued in BH or + * IRQ context, and where work items are handled one at a time by + * dedicated threads. + */ +#include +#include + +struct llist_node *__lwq_dequeue(struct lwq *q) +{ + struct llist_node *this; + + if (lwq_empty(q)) + return NULL; + spin_lock(&q->lock); + this = q->ready; + if (!this && !llist_empty(&q->new)) { + /* ensure queue doesn't appear transiently lwq_empty */ + smp_store_release(&q->ready, (void *)1); + this = llist_reverse_order(llist_del_all(&q->new)); + if (!this) + q->ready = NULL; + } + if (this) + q->ready = llist_next(this); + spin_unlock(&q->lock); + return this; +} +EXPORT_SYMBOL_GPL(__lwq_dequeue); + +/** + * lwq_dequeue_all - dequeue all currently enqueued objects + * @q: the queue to dequeue from + * + * Remove and return a linked list of llist_nodes of all the objects that were + * in the queue. The first on the list will be the object that was least + * recently enqueued. + */ +struct llist_node *lwq_dequeue_all(struct lwq *q) +{ + struct llist_node *r, *t, **ep; + + if (lwq_empty(q)) + return NULL; + + spin_lock(&q->lock); + r = q->ready; + q->ready = NULL; + t = llist_del_all(&q->new); + spin_unlock(&q->lock); + ep = &r; + while (*ep) + ep = &(*ep)->next; + *ep = llist_reverse_order(t); + return r; +} +EXPORT_SYMBOL_GPL(lwq_dequeue_all); + +#if IS_ENABLED(CONFIG_LWQ_TEST) + +#include +#include +#include +#include +#include +struct tnode { + struct lwq_node n; + int i; + int c; +}; + +static int lwq_exercise(void *qv) +{ + struct lwq *q = qv; + int cnt; + struct tnode *t; + + for (cnt = 0; cnt < 10000; cnt++) { + wait_var_event(q, (t = lwq_dequeue(q, struct tnode, n)) != NULL); + t->c++; + if (lwq_enqueue(&t->n, q)) + wake_up_var(q); + } + while (!kthread_should_stop()) + schedule_timeout_idle(1); + return 0; +} + +static int lwq_test(void) +{ + int i; + struct lwq q; + struct llist_node *l, **t1, *t2; + struct tnode *t; + struct task_struct *threads[8]; + + printk(KERN_INFO "testing lwq....\n"); + lwq_init(&q); + printk(KERN_INFO " lwq: run some threads\n"); + for (i = 0; i < ARRAY_SIZE(threads); i++) + threads[i] = kthread_run(lwq_exercise, &q, "lwq-test-%d", i); + for (i = 0; i < 100; i++) { + t = kmalloc_obj(*t); + if (!t) + break; + t->i = i; + t->c = 0; + if (lwq_enqueue(&t->n, &q)) + wake_up_var(&q); + } + /* wait for threads to exit */ + for (i = 0; i < ARRAY_SIZE(threads); i++) + if (!IS_ERR_OR_NULL(threads[i])) + kthread_stop(threads[i]); + printk(KERN_INFO " lwq: dequeue first 50:"); + for (i = 0; i < 50 ; i++) { + if (i && (i % 10) == 0) { + printk(KERN_CONT "\n"); + printk(KERN_INFO " lwq: ... "); + } + t = lwq_dequeue(&q, struct tnode, n); + if (t) + printk(KERN_CONT " %d(%d)", t->i, t->c); + kfree(t); + } + printk(KERN_CONT "\n"); + l = lwq_dequeue_all(&q); + printk(KERN_INFO " lwq: delete the multiples of 3 (test lwq_for_each_safe())\n"); + lwq_for_each_safe(t, t1, t2, &l, n) { + if ((t->i % 3) == 0) { + t->i = -1; + kfree(t); + t = NULL; + } + } + if (l) + lwq_enqueue_batch(l, &q); + printk(KERN_INFO " lwq: dequeue remaining:"); + while ((t = lwq_dequeue(&q, struct tnode, n)) != NULL) { + printk(KERN_CONT " %d", t->i); + kfree(t); + } + printk(KERN_CONT "\n"); + return 0; +} + +module_init(lwq_test); +#endif /* CONFIG_LWQ_TEST*/ -- cgit v1.3.1