bpf: Extend the bpf_list family of APIs
Subsystems (4)
v5 cover bpf: Extend the bpf_list family of APIs
From: Kaitao Cheng <[email protected]>
In BPF, a list can only be used to implement a stack structure. Due to an incomplete API set, only FIFO or LIFO operations are supported. The patches enhance the BPF list API, making it more list-like.
Five new kfuncs have been added:bpf_list_del: remove a node from the listbpf_list_add_impl: insert a node after a given list nodebpf_list_is_first: check if a node is the first in the listbpf_list_is_last: check if a node is the last in the listbpf_list_empty: check if the list is empty
Changes in v5:
- Fix bpf_obj leak on bpf_list_add_impl error
Changes in v4:
- [patch v3 1/6] Revert to version v1
- Change the parameters of bpf_list_add_impl to (head, new, prev, ...)
Changes in v3:
- Add a new lock_rec member to struct bpf_reference_state for lock holding detection.
- Add test cases to verify that the verifier correctly restricts calls to bpf_list_del when the spin_lock is not held.
Changes in v2:
- Remove the head parameter from bpf_list_del
- Add bpf_list_add/is_first/is_last/empty to API and test cases
Link to v4:
https://lore.kernel.org/all/[email protected]/
Link to v3:
https://lore.kernel.org/all/[email protected]/
Link to v2:
https://lore.kernel.org/all/[email protected]/
Link to v1:
https://lore.kernel.org/all/[email protected]/
Kaitao Cheng (6):
bpf: Introduce the bpf_list_del kfunc.
selftests/bpf: Add test cases for bpf_list_del
bpf: add bpf_list_add_impl to insert node after a given list node selftests/bpf: Add test case for bpf_list_add_impl
bpf: add bpf_list_is_first/last/empty kfuncs selftests/bpf: Add test cases for bpf_list_is_first/is_last/empty
kernel/bpf/helpers.c | 85 ++++++++ kernel/bpf/verifier.c | 30 ++- .../testing/selftests/bpf/bpf_experimental.h | 42 ++++ .../selftests/bpf/progs/refcounted_kptr.c | 182 ++++++++++++++++++ 4 files changed, 335 insertions(+), 4 deletions(-)
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v5 1/6 bpf: Introduce the bpf_list_del kfunc.
From: Kaitao Cheng <[email protected]>
If a user holds ownership of a node in the middle of a list, they can directly remove it from the list without strictly adhering to deletion rules from the head or tail.
This is typically paired with bpf_refcount. After calling bpf_list_del, it is generally necessary to drop the reference to the list node twice to prevent reference count leaks.
--- kernel/bpf/helpers.c | 19 +++++++++++++++++++ kernel/bpf/verifier.c | 6 +++++- 2 files changed, 24 insertions(+), 1 deletion(-)
kernel/bpf/helpers.c +19 -0
@@ -2459,6 +2459,24 @@ __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)return __bpf_list_del (head, true); } +__bpf_kfunc struct bpf_list_node *bpf_list_del(struct bpf_list_head *head, +struct bpf_list_node *node) +{ +struct bpf_list_node_kern *knode = (struct bpf_list_node_kern *)node; +struct list_head *h = (void *)head; + +if (unlikely (!knode)) +return NULL ; + +if (WARN_ON_ONCE (READ_ONCE (knode->owner) != h)) +return NULL ; + +list_del_init (&knode->list_head); +WRITE_ONCE (knode->owner,NULL ); + +return node; +} + __bpf_kfunc struct bpf_list_node *bpf_list_front(struct bpf_list_head *head) {struct list_head *h = (struct list_head *)head;
@@ -4545,6 +4563,7 @@ BTF_ID_FLAGS(func, bpf_list_push_front_impl) BTF_ID_FLAGS(func, bpf_list_push_back_impl) BTF_ID_FLAGS(func, bpf_list_pop_front, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_pop_back, KF_ACQUIRE | KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_list_del, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_front, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_back, KF_RET_NULL)BTF_ID_FLAGS (func, bpf_task_acquire,KF_ACQUIRE |KF_RCU |KF_RET_NULL )
kernel/bpf/verifier.c +5 -1
@@ -12461,6 +12461,7 @@ enum special_kfunc_type { KF_bpf_list_push_back_impl, KF_bpf_list_pop_front, KF_bpf_list_pop_back, + KF_bpf_list_del, KF_bpf_list_front, KF_bpf_list_back, KF_bpf_cast_to_kern_ctx,
@@ -12521,6 +12522,7 @@ BTF_ID(func, bpf_list_push_front_impl) BTF_ID(func, bpf_list_push_back_impl) BTF_ID(func, bpf_list_pop_front) BTF_ID(func, bpf_list_pop_back) +BTF_ID(func, bpf_list_del) BTF_ID(func, bpf_list_front) BTF_ID(func, bpf_list_back)BTF_ID (func, bpf_cast_to_kern_ctx)
@@ -12996,6 +12998,7 @@ static bool is_bpf_list_api_kfunc(u32 btf_id) btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || btf_id == special_kfunc_list[KF_bpf_list_pop_front] || btf_id == special_kfunc_list[KF_bpf_list_pop_back] || + btf_id == special_kfunc_list[KF_bpf_list_del] || btf_id == special_kfunc_list[KF_bpf_list_front] || btf_id == special_kfunc_list[KF_bpf_list_back]; }
@@ -13118,7 +13121,8 @@ static bool check_kfunc_is_graph_node_api(struct bpf_verifier_env *env,switch (node_field_type) {case BPF_LIST_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl]); + kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_del]);break ;case BPF_RB_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] ||
Signature · 1 line
2.50.1 (Apple Git-155)
Re: [PATCH v5 1/6] bpf: Introduce the bpf_list_del kfunc.
Quoted 21 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
If a user holds ownership of a node in the middle of a list, they can directly remove it from the list without strictly adhering to deletion rules from the head or tail.
This is typically paired with
bpf_refcount. After callingbpf_list_del, it is generally necessary to drop the reference to the list node twice to prevent reference count leaks.Signed-off-by Kaitao Cheng <[email protected]>--- kernel/bpf/helpers.c | 19 +++++++++++++++++++ kernel/bpf/verifier.c | 6 +++++- 2 files changed, 24 insertions(+), 1 deletion(-)kernel/bpf/helpers.c +0
-0
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2468
Quoted 10 lines
kernel/bpf/helpers.c +7
-0@@ -2459,6 +2459,24 @@ __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)return __bpf_list_del (head, true); } +__bpf_kfunc struct bpf_list_node *bpf_list_del(struct bpf_list_head *head, +struct bpf_list_node *node) +{ +struct bpf_list_node_kern *knode = (struct bpf_list_node_kern *)node; +struct list_head *h = (void *)head; + +if (unlikely (!knode))
Can you pass knode==NULL to this kfunc?
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2471
Quoted 3 lines
kernel/bpf/helpers.c +3
-0+return NULL ; + +if (WARN_ON_ONCE (READ_ONCE (knode->owner) != h))
it looks like you can just do READ_ONCE(knode->owner) != head. owner is void*, what's the point of defining struct list_head *h?
Quoted 59 lines
kernel/bpf/helpers.c +9
-0+return NULL ; + +list_del_init (&knode->list_head); +WRITE_ONCE (knode->owner,NULL ); + +return node; +} + __bpf_kfunc struct bpf_list_node *bpf_list_front(struct bpf_list_head *head) {struct list_head *h = (struct list_head *)head;@@ -4545,6 +4563,7 @@ BTF_ID_FLAGS(func, bpf_list_push_front_impl) BTF_ID_FLAGS(func, bpf_list_push_back_impl) BTF_ID_FLAGS(func, bpf_list_pop_front, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_pop_back, KF_ACQUIRE | KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_list_del, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_front, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_back, KF_RET_NULL)BTF_ID_FLAGS (func, bpf_task_acquire,KF_ACQUIRE |KF_RCU |KF_RET_NULL )kernel/bpf/verifier.c +5
-1@@ -12461,6 +12461,7 @@ enum special_kfunc_type { KF_bpf_list_push_back_impl, KF_bpf_list_pop_front, KF_bpf_list_pop_back, + KF_bpf_list_del, KF_bpf_list_front, KF_bpf_list_back, KF_bpf_cast_to_kern_ctx,@@ -12521,6 +12522,7 @@ BTF_ID(func, bpf_list_push_front_impl) BTF_ID(func, bpf_list_push_back_impl) BTF_ID(func, bpf_list_pop_front) BTF_ID(func, bpf_list_pop_back) +BTF_ID(func, bpf_list_del) BTF_ID(func, bpf_list_front) BTF_ID(func, bpf_list_back)BTF_ID (func, bpf_cast_to_kern_ctx)@@ -12996,6 +12998,7 @@ static bool is_bpf_list_api_kfunc(u32 btf_id) btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || btf_id == special_kfunc_list[KF_bpf_list_pop_front] || btf_id == special_kfunc_list[KF_bpf_list_pop_back] || + btf_id == special_kfunc_list[KF_bpf_list_del] || btf_id == special_kfunc_list[KF_bpf_list_front] || btf_id == special_kfunc_list[KF_bpf_list_back]; }@@ -13118,7 +13121,8 @@ static bool check_kfunc_is_graph_node_api(struct bpf_verifier_env *env,switch (node_field_type) {case BPF_LIST_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl]); + kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_del]);break ;case BPF_RB_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] ||Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v5 2/6 selftests/bpf: Add test cases for bpf_list_del
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Add a node to both an rbtree and a list, retrieve the node from the rbtree, use the obtained node pointer to remove it from the list, and finally free the node.
To verify the validity of bpf_list_del, also expect the verifier to reject calls to bpf_list_del made without holding the spin_lock.
--- .../testing/selftests/bpf/bpf_experimental.h | 11 +++ .../selftests/bpf/progs/refcounted_kptr.c | 71 +++++++++++++++++++ 2 files changed, 82 insertions(+)
tools/testing/selftests/bpf/bpf_experimental.h +11 -0
@@ -99,6 +99,17 @@ extern struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) __ks*/ extern struct bpf_list_node *bpf_list_pop_back (struct bpf_list_head *head) __ksym; +/* Description +* Remove 'node' from the BPF linked list with head 'head'. +* The node must be in the list. Caller receives ownership of the +* removed node and must release it with bpf_obj_drop. +* Returns +* Pointer to the removed bpf_list_node, or NULL if 'node' is NULL +* or not in the list. +*/ +extern struct bpf_list_node *bpf_list_del (struct bpf_list_head *head, +struct bpf_list_node *node) __ksym; +/* Description * Remove 'node' from rbtree with root 'root' * Returns
tools/testing/selftests/bpf/progs/refcounted_kptr.c +71 -0
77 lines not on this page · raw message
Signature · 1 line
2.50.1 (Apple Git-155)
Re: [PATCH v5 2/6] selftests/bpf: Add test cases for bpf_list_del
Quoted 89 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
Add a node to both an rbtree and a list, retrieve the node from the rbtree, use the obtained node pointer to remove it from the list, and finally free the node.
To verify the validity of
bpf_list_del, also expect the verifier to reject calls tobpf_list_delmade without holding thespin_lock.Signed-off-by Kaitao Cheng <[email protected]>--- .../testing/selftests/bpf/bpf_experimental.h | 11 +++ .../selftests/bpf/progs/refcounted_kptr.c | 71 +++++++++++++++++++ 2 files changed, 82 insertions(+)tools/testing/selftests/bpf/bpf_experimental.h +11
-0@@ -99,6 +99,17 @@ extern struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) __ks*/ extern struct bpf_list_node *bpf_list_pop_back (struct bpf_list_head *head) __ksym; +/* Description +* Remove 'node' from the BPF linked list with head 'head'. +* The node must be in the list. Caller receives ownership of the +* removed node and must release it with bpf_obj_drop. +* Returns +* Pointer to the removed bpf_list_node, or NULL if 'node' is NULL +* or not in the list. +*/ +extern struct bpf_list_node *bpf_list_del (struct bpf_list_head *head, +struct bpf_list_node *node) __ksym; +/* Description * Remove 'node' from rbtree with root 'root' * Returns tools/testing/selftests/bpf/progs/refcounted_kptr.c +44
-0@@ -367,6 +367,77 @@ long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \INSERT_STASH_READ (true,"insert_stash_read: remove from tree" );INSERT_STASH_READ (false,"insert_stash_read: don't remove from tree" ); +/* Insert node_data into both rbtree and list, remove from tree, then remove +* from list via bpf_list_del using the node obtained from the tree. +*/ +SEC("tc") +__description("test_bpf_list_del: remove an arbitrary node from the list") +__success __retval(0) +long test_bpf_list_del(void *ctx) +{ +long err; +struct bpf_rb_node *rb; +struct bpf_list_node *l; +struct node_data *n; + + err =__insert_in_tree_and_list (&head, &root, &lock); +if (err) +return err; + +bpf_spin_lock (&lock); + rb =bpf_rbtree_first (&root); +if (!rb) { +bpf_spin_unlock (&lock); +return -4 ; + } + + rb =bpf_rbtree_remove (&root, rb); +if (!rb) { +bpf_spin_unlock (&lock); +return -5 ; + } + + n = container_of(rb, struct node_data, r); + l =bpf_list_del (&head, &n->l); +bpf_spin_unlock (&lock); +bpf_obj_drop (n); +if (!l) +return -6 ; + +bpf_obj_drop (container_of(l ,struct node_data ,l )); +return 0 ; +} + +SEC("?tc") +__failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") +long list_del_without_lock_fail(void *ctx)
tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 423
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +10
-0+{ +struct bpf_rb_node *rb; +struct bpf_list_node *l; +struct node_data *n; + +bpf_spin_lock (&lock); + rb =bpf_rbtree_first (&root); +if (!rb) { +bpf_spin_unlock (&lock); +return -4 ;
Do we need to craft those error return codes in the program that is supposed to be rejected by verifier. Can we implement a minimal code that triggers the verifier error without all unnecessary noise.
Quoted 22 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +17
-0+ } + + rb =bpf_rbtree_remove (&root, rb); +bpf_spin_unlock (&lock); +if (!rb) +return -5 ; + + n = container_of(rb, struct node_data, r); + l =bpf_list_del (&head, &n->l); +bpf_obj_drop (n); +if (!l) +return -6 ; + +bpf_obj_drop (container_of(l ,struct node_data ,l )); +return 0 ; +} + SEC("tc")__success long rbtree_refcounted_node_ref_escapes (void *ctx)Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v5 3/6 bpf: add bpf_list_add_impl to insert node after a given list node
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Add a new kfunc bpf_list_add_impl(head, new, prev, meta, off) that inserts 'new' after 'prev' in the BPF linked list. Both must be in the same list; 'prev' must already be in the list. The new node must be an owning reference (e.g. from bpf_obj_new); the kfunc consumes that reference and the node becomes non-owning once inserted.
We have added an additional parameter bpf_list_head *head to bpf_list_add_impl, as the verifier requires the head parameter to check whether the lock is being held.
Returns 0 on success, -EINVAL if 'prev' is not in a list or 'new' is already in a list (or duplicate insertion). On failure, the kernel drops the passed-in node.
--- kernel/bpf/helpers.c | 25 +++++++++++++++++++++++++ kernel/bpf/verifier.c | 15 +++++++++++---- 2 files changed, 36 insertions(+), 4 deletions(-)
kernel/bpf/helpers.c +25 -0
@@ -2497,6 +2497,30 @@ __bpf_kfunc struct bpf_list_node *bpf_list_back(struct bpf_list_head *head)return (struct bpf_list_node *)h->prev; } +__bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head, +struct bpf_list_node *new, +struct bpf_list_node *prev, +void *meta__ign,u64 off) +{ +struct bpf_list_node_kern *kn = (void *)new, *kp = (void *)prev; +struct btf_struct_meta *meta = meta__ign; +struct list_head *n = &kn->list_head, *p = &kp->list_head; + +if (unlikely (!head ||READ_ONCE (kp->owner) != head)) + goto fail; + +if (cmpxchg (&kn->owner,NULL ,BPF_PTR_POISON )) + goto fail; + +list_add (n, p); +WRITE_ONCE (kn->owner, head); +return 0 ; + +fail: +__bpf_obj_drop_impl ((void *)n - off, meta ? meta->record :NULL , false); +return -EINVAL ; +} + __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,struct bpf_rb_node *node) {
@@ -4566,6 +4590,7 @@ BTF_ID_FLAGS(func, bpf_list_pop_back, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_del, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_front, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_back, KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_list_add_impl) BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_RCU | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_release, KF_RELEASE)BTF_ID_FLAGS (func, bpf_rbtree_remove,KF_ACQUIRE |KF_RET_NULL )
kernel/bpf/verifier.c +11 -4
@@ -12464,6 +12464,7 @@ enum special_kfunc_type { KF_bpf_list_del, KF_bpf_list_front, KF_bpf_list_back, + KF_bpf_list_add_impl, KF_bpf_cast_to_kern_ctx, KF_bpf_rdonly_cast, KF_bpf_rcu_read_lock,
@@ -12525,6 +12526,7 @@ BTF_ID(func, bpf_list_pop_back) BTF_ID(func, bpf_list_del) BTF_ID(func, bpf_list_front) BTF_ID(func, bpf_list_back) +BTF_ID(func, bpf_list_add_impl) BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast)BTF_ID (func, bpf_rcu_read_lock)
@@ -13000,7 +13002,8 @@ static bool is_bpf_list_api_kfunc(u32 btf_id) btf_id == special_kfunc_list[KF_bpf_list_pop_back] || btf_id == special_kfunc_list[KF_bpf_list_del] || btf_id == special_kfunc_list[KF_bpf_list_front] || - btf_id == special_kfunc_list[KF_bpf_list_back]; + btf_id == special_kfunc_list[KF_bpf_list_back] || + btf_id == special_kfunc_list[KF_bpf_list_add_impl]; }static bool is_bpf_rbtree_api_kfunc (u32 btf_id)
@@ -13122,7 +13125,8 @@ static bool check_kfunc_is_graph_node_api(struct bpf_verifier_env *env,case BPF_LIST_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_del]); + kfunc_btf_id == special_kfunc_list[KF_bpf_list_del] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl]);break ;case BPF_RB_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] ||
@@ -14264,6 +14268,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,if (meta.func_id == special_kfunc_list[KF_bpf_list_push_front_impl] || meta.func_id == special_kfunc_list[KF_bpf_list_push_back_impl] || + meta.func_id == special_kfunc_list[KF_bpf_list_add_impl] || meta.func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) { release_ref_obj_id = regs[BPF_REG_2 ].ref_obj_id; insn_aux->insert_off = regs[BPF_REG_2 ].off;
@@ -23230,13 +23235,15 @@ static int fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, *cnt =3 ; }else if (desc->func_id == special_kfunc_list[KF_bpf_list_push_back_impl] || desc->func_id == special_kfunc_list[KF_bpf_list_push_front_impl] || + desc->func_id == special_kfunc_list[KF_bpf_list_add_impl] || desc->func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {struct btf_struct_meta *kptr_struct_meta = env->insn_aux_data[insn_idx].kptr_struct_meta;int struct_meta_reg =BPF_REG_3 ;int node_offset_reg =BPF_REG_4 ; -/* rbtree_add has extra 'less' arg, so args-to-fixup are in diff regs */ -if (desc->func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) { +/* They has extra arg, so args-to-fixup are in diff regs */ +if (desc->func_id == special_kfunc_list[KF_bpf_list_add_impl] || + desc->func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) { struct_meta_reg =BPF_REG_4 ; node_offset_reg =BPF_REG_5 ; }
Signature · 1 line
2.50.1 (Apple Git-155)
[email protected]
AI reviewRe: [PATCH v5 3/6] bpf: add bpf_list_add_impl to insert node after a given list node
"Both must be in the same list" reads as though new and prev are both already present in the list, but the code requires new to have owner == NULL (via the cmpxchg check), meaning new must not be in…
Quoted 3 lines
Add a new kfunc
bpf_list_add_impl(head, new, prev, meta, off)that inserts 'new' after 'prev' in the BPF linked list. Both must be in the same list; 'prev' must already be in the list.
"Both must be in the same list" reads as though new and prev are both already present in the list, but the code requires new to have owner == NULL (via the cmpxchg check), meaning new must not be in any list. Would something like "prev must already be in the list headed by head" be clearer here?
Quoted 3 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
kernel/bpf/verifier.c struct bpf_insn addr[2] = { BPF_LD_IMM64(BPF_REG_2, (long)kptr_struct_meta) }; · line 23209
Quoted 13 lines
kernel/bpf/verifier.c +2
-2@@ -23195,13 +23200,15 @@ struct bpf_insn addr[2] = { BPF_LD_IMM64(BPF_REG_2, (long)kptr_struct_meta) }; *cnt =3 ; }else if (desc->func_id == special_kfunc_list[KF_bpf_list_push_back_impl] || desc->func_id == special_kfunc_list[KF_bpf_list_push_front_impl] || + desc->func_id == special_kfunc_list[KF_bpf_list_add_impl] || desc->func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) {struct btf_struct_meta *kptr_struct_meta = env->insn_aux_data[insn_idx].kptr_struct_meta;int struct_meta_reg =BPF_REG_3 ;int node_offset_reg =BPF_REG_4 ; -/* rbtree_add has extra 'less' arg, so args-to-fixup are in diff regs */ -if (desc->func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) { +/* They has extra arg, so args-to-fixup are in diff regs */
^^^^^^^^
"They has" should be "They have" or "These have".
The original comment also explained why the extra arg exists (rbtree_add has a 'less' callback). Could this be updated to mention both cases, e.g. "list_add_impl and rbtree_add_impl have an extra arg (prev / less), so args-to-fixup are in different regs"?
kernel/bpf/verifier.c static int fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, · line 23249
Quoted 5 lines
kernel/bpf/verifier.c +2
-0+if (desc->func_id == special_kfunc_list[KF_bpf_list_add_impl] || + desc->func_id == special_kfunc_list[KF_bpf_rbtree_add_impl]) { struct_meta_reg =BPF_REG_4 ; node_offset_reg =BPF_REG_5 ; }
---
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/22653666378
PATCH v5 4/6 selftests/bpf: Add test case for bpf_list_add_impl
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Extend refcounted_kptr test to exercise bpf_list_add:
add a second node after the first, then bpf_list_del both nodes.
To verify the validity of bpf_list_add, also expect the verifier to reject calls to bpf_list_add made without holding the spin_lock.
--- .../testing/selftests/bpf/bpf_experimental.h | 16 +++ .../selftests/bpf/progs/refcounted_kptr.c | 122 ++++++++++++++++-- 2 files changed, 124 insertions(+), 14 deletions(-)
tools/testing/selftests/bpf/bpf_experimental.h +16 -0
@@ -110,6 +110,22 @@ extern struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) __ksyextern struct bpf_list_node *bpf_list_del (struct bpf_list_head *head,struct bpf_list_node *node) __ksym; +/* Description +* Insert 'new' after 'prev' in the BPF linked list with head 'head'. +* The bpf_spin_lock protecting the list must be held. 'prev' must already +* be in that list; 'new' must not be in any list. The 'meta' and 'off' +* parameters are rewritten by the verifier, no need for BPF programs to +* set them. +* Returns +* 0 on success, -EINVAL if head is NULL, prev is not in the list with head, +* or new is already in a list. +*/ +extern int bpf_list_add_impl(struct bpf_list_head *head, struct bpf_list_node *new, + struct bpf_list_node *prev, void *meta, __u64 off) __ksym; + +/* Convenience macro to wrap over bpf_list_add_impl */ +#define bpf_list_add (head, new, prev) bpf_list_add_impl(head, new, prev, NULL, 0) +/* Description * Remove 'node' from rbtree with root 'root' * Returns
tools/testing/selftests/bpf/progs/refcounted_kptr.c +108 -14
152 lines not on this page · raw message
Signature · 1 line
2.50.1 (Apple Git-155)
Re: [PATCH v5 4/6] selftests/bpf: Add test case for bpf_list_add_impl
Quoted 19 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
Extend
refcounted_kptrtest to exercisebpf_list_add:
add a second node after the first, thenbpf_list_delboth nodes.To verify the validity of
bpf_list_add, also expect the verifier to reject calls tobpf_list_addmade without holding thespin_lock.Signed-off-by Kaitao Cheng <[email protected]>--- .../testing/selftests/bpf/bpf_experimental.h | 16 +++ .../selftests/bpf/progs/refcounted_kptr.c | 122 ++++++++++++++++-- 2 files changed, 124 insertions(+), 14 deletions(-)tools/testing/selftests/bpf/bpf_experimental.h +0
-0
tools/testing/selftests/bpf/bpf_experimental.h extern struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) __ksy · line 111
Quoted 2 lines
tools/testing/selftests/bpf/bpf_experimental.h +0
-0@@ -110,6 +110,22 @@ extern struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) __ksyextern struct bpf_list_node *bpf_list_del (struct bpf_list_head *head,struct bpf_list_node *node) __ksym;
should this be available from vmlinux.h?
Quoted 25 lines
tools/testing/selftests/bpf/bpf_experimental.h +16
-0+/* Description +* Insert 'new' after 'prev' in the BPF linked list with head 'head'. +* The bpf_spin_lock protecting the list must be held. 'prev' must already +* be in that list; 'new' must not be in any list. The 'meta' and 'off' +* parameters are rewritten by the verifier, no need for BPF programs to +* set them. +* Returns +* 0 on success, -EINVAL if head is NULL, prev is not in the list with head, +* or new is already in a list. +*/ +extern int bpf_list_add_impl(struct bpf_list_head *head, struct bpf_list_node *new, + struct bpf_list_node *prev, void *meta, __u64 off) __ksym; + +/* Convenience macro to wrap over bpf_list_add_impl */ +#define bpf_list_add (head, new, prev) bpf_list_add_impl(head, new, prev, NULL, 0) +/* Description * Remove 'node' from rbtree with root 'root' * Returns tools/testing/selftests/bpf/progs/refcounted_kptr.c +0
-0
tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 370
Quoted 6 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-2@@ -367,18 +367,19 @@ long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \INSERT_STASH_READ (true,"insert_stash_read: remove from tree" );INSERT_STASH_READ (false,"insert_stash_read: don't remove from tree" ); -/* Insert node_data into both rbtree and list, remove from tree, then remove -* from list via bpf_list_del using the node obtained from the tree. +/* Insert one node in tree and list, remove it from tree, add a second
Use kernel comment style: first line is just "/*" then text starts from the next one.
tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 373
Quoted 3 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +2
-0+* node after it in list with bpf_list_add, then remove both nodes from +* list via bpf_list_del. */
It sounds like the new test is quite different from the previous, why not add a separate test running new codepaths instead of retrofitting into the existing test?
Quoted 4 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-1SEC("tc") -__description("test_bpf_list_del: remove an arbitrary node from the list") +__description("test_list_add_del: test bpf_list_add/del") __success __retval(0)
tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 382
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +4
-4-long test_bpf_list_del (void *ctx) +long test_list_add_del (void *ctx) { -long err; +long err =0 ;struct bpf_rb_node *rb; -struct bpf_list_node *l; -struct node_data *n; +struct bpf_list_node *l, *l_1; +struct node_data *n, *n_1, *m_1;
nit: The naming scheme is a little bit confusing.
Quoted 36 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +22
-3err =__insert_in_tree_and_list (&head, &root, &lock);if (err)@@ -392,20 +393,48 @@ long test_bpf_list_del(void *ctx) } rb =bpf_rbtree_remove (&root, rb); -if (!rb) { -bpf_spin_unlock (&lock); +bpf_spin_unlock (&lock); +if (!rb)return -5 ; - } n = container_of(rb, struct node_data, r); + n_1 =bpf_obj_new (typeof (*n_1)); +if (!n_1) { +bpf_obj_drop (n); +return -1 ; + } + m_1 =bpf_refcount_acquire (n_1); +if (!m_1) { +bpf_obj_drop (n); +bpf_obj_drop (n_1); +return -1 ; + } + +bpf_spin_lock (&lock); +if (bpf_list_add (&head, &n_1->l, &n->l)) { +bpf_spin_unlock (&lock); +bpf_obj_drop (n); +bpf_obj_drop (m_1); +return -8 ; + } + l =bpf_list_del (&head, &n->l);
tools/testing/selftests/bpf/progs/refcounted_kptr.c long test_bpf_list_del(void *ctx) · line 427
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +3
-4+ l_1 =bpf_list_del (&head, &m_1->l);bpf_spin_unlock (&lock);bpf_obj_drop (n); -if (!l) -return -6 ; +bpf_obj_drop (m_1); -bpf_obj_drop (container_of(l ,struct node_data ,l )); -return 0 ; +if (l)
Can we do early returns, like
if (!l)
return -6;bpf_obj_drop(l);
if (!l_1)
return -7;bpf_obj_drop(l_1);
The point of returning different errors per each error path is to make it easy to understand where your test errored out by just looking at err.
Quoted 71 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +64
-0+bpf_obj_drop (container_of(l ,struct node_data ,l )); + else + err =-6 ; + +if (l_1) + bpf_obj_drop(container_of(l_1, struct node_data, l)); +else + err =-6 ; + +return err; }SEC ("?tc" )@@ -438,6 +467,71 @@ long list_del_without_lock_fail(void *ctx)return 0 ; } +SEC("?tc") +__failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") +long list_add_without_lock_fail(void *ctx) +{ +long err =0 ; +struct bpf_rb_node *rb; +struct bpf_list_node *l, *l_1; +struct node_data *n, *n_1, *m_1; + + err =__insert_in_tree_and_list (&head, &root, &lock); +if (err) +return err; + +bpf_spin_lock (&lock); + rb =bpf_rbtree_first (&root); +if (!rb) { +bpf_spin_unlock (&lock); +return -4 ; + } + + rb =bpf_rbtree_remove (&root, rb); +bpf_spin_unlock (&lock); +if (!rb) +return -5 ; + + n = container_of(rb, struct node_data, r); + n_1 =bpf_obj_new (typeof (*n_1)); +if (!n_1) { +bpf_obj_drop (n); +return -1 ; + } + m_1 =bpf_refcount_acquire (n_1); +if (!m_1) { +bpf_obj_drop (n); +bpf_obj_drop (n_1); +return -1 ; + } + +/* Intentionally no lock: verifier should reject bpf_list_add without lock */ +if (bpf_list_add (&head, &n_1->l, &n->l)) { +bpf_obj_drop (n); +bpf_obj_drop (m_1); +return -8 ; + } + +bpf_spin_lock (&lock); + l =bpf_list_del (&head, &n->l); + l_1 =bpf_list_del (&head, &m_1->l); +bpf_spin_unlock (&lock); +bpf_obj_drop (n); +bpf_obj_drop (m_1); + +if (l) + bpf_obj_drop(container_of(l, struct node_data, l));
tools/testing/selftests/bpf/progs/refcounted_kptr.c long list_del_without_lock_fail(void *ctx) · line 533
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +10
-0+else + err =-6 ; + +if (l_1) + bpf_obj_drop(container_of(l_1, struct node_data, l)); +else + err =-6 ; + +return err; +}
Do we need this big test just to trigger that verifier error?
Quoted 6 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-0+ SEC("tc")__success long rbtree_refcounted_node_ref_escapes (void *ctx)Signature · 1 line
2.50.1 (Apple Git-155)
Re: [PATCH v5 4/6] selftests/bpf: Add test case for bpf_list_add_impl
Quoted 17 lines · Mykyta Yatsenko
Quoted 14 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
Extend
refcounted_kptrtest to exercisebpf_list_add:
add a second node after the first, thenbpf_list_delboth nodes.To verify the validity of
bpf_list_add, also expect the verifier to reject calls tobpf_list_addmade without holding thespin_lock.Signed-off-by Kaitao Cheng <[email protected]>--- .../testing/selftests/bpf/bpf_experimental.h | 16 +++ .../selftests/bpf/progs/refcounted_kptr.c | 122 ++++++++++++++++-- 2 files changed, 124 insertions(+), 14 deletions(-)
Quoted 8 lines
tools/testing/selftests/bpf/bpf_experimental.h extern struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) __ksy · line 111
Quoted 7 lines
tools/testing/selftests/bpf/bpf_experimental.h +0
-0@@ -110,6 +110,22 @@ extern struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) __ksyextern struct bpf_list_node *bpf_list_del (struct bpf_list_head *head,struct bpf_list_node *node) __ksym;should this be available from
vmlinux.h?
In v7, I removed most of the function declarations and kept only the bpf_list_add macro.
https://lore.kernel.org/all/[email protected]/
I have a question: bpf_experimental.h already has many similar declarations for other kfuncs—are those redundant too, should we remove them as well? or is there a historical reason for keeping them? I would appreciate your clarification on this.
Quoted 32 lines
Quoted 24 lines
tools/testing/selftests/bpf/bpf_experimental.h +16
-0+/* Description +* Insert 'new' after 'prev' in the BPF linked list with head 'head'. +* The bpf_spin_lock protecting the list must be held. 'prev' must already +* be in that list; 'new' must not be in any list. The 'meta' and 'off' +* parameters are rewritten by the verifier, no need for BPF programs to +* set them. +* Returns +* 0 on success, -EINVAL if head is NULL, prev is not in the list with head, +* or new is already in a list. +*/ +extern int bpf_list_add_impl(struct bpf_list_head *head, struct bpf_list_node *new, + struct bpf_list_node *prev, void *meta, __u64 off) __ksym; + +/* Convenience macro to wrap over bpf_list_add_impl */ +#define bpf_list_add (head, new, prev) bpf_list_add_impl(head, new, prev, NULL, 0) +/* Description * Remove 'node' from rbtree with root 'root' * Returns tools/testing/selftests/bpf/progs/refcounted_kptr.c +0
-0tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 370
Quoted 6 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-2@@ -367,18 +367,19 @@ long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \INSERT_STASH_READ (true,"insert_stash_read: remove from tree" );INSERT_STASH_READ (false,"insert_stash_read: don't remove from tree" ); -/* Insert node_data into both rbtree and list, remove from tree, then remove -* from list via bpf_list_del using the node obtained from the tree. +/* Insert one node in tree and list, remove it from tree, add a second Use kernel comment style: first line is just "/*" then text starts from the next one.
Quoted 6 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 373
Quoted 3 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +2
-0+* node after it in list with bpf_list_add, then remove both nodes from +* list via bpf_list_del. */ It sounds like the new test is quite different from the previous, why not add a separate test running new codepaths instead of retrofitting into the existing test?
I merged the three test-case patches into one; they still share a common function, as some logic can be reused. I added some log output for readability.
Quoted 58 lines
Quoted 4 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-1SEC("tc") -__description("test_bpf_list_del: remove an arbitrary node from the list") +__description("test_list_add_del: test bpf_list_add/del") __success __retval(0)tools/testing/selftests/bpf/progs/refcounted_kptr.c long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ · line 382
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +4
-4-long test_bpf_list_del (void *ctx) +long test_list_add_del (void *ctx) { -long err; +long err =0 ;struct bpf_rb_node *rb; -struct bpf_list_node *l; -struct node_data *n; +struct bpf_list_node *l, *l_1; +struct node_data *n, *n_1, *m_1;nit: The naming scheme is a little bit confusing.
Quoted 43 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +24
-5err =__insert_in_tree_and_list (&head, &root, &lock);if (err)@@ -392,20 +393,48 @@ long test_bpf_list_del(void *ctx) } rb =bpf_rbtree_remove (&root, rb); -if (!rb) { -bpf_spin_unlock (&lock); +bpf_spin_unlock (&lock); +if (!rb)return -5 ; - } n = container_of(rb, struct node_data, r); + n_1 =bpf_obj_new (typeof (*n_1)); +if (!n_1) { +bpf_obj_drop (n); +return -1 ; + } + m_1 =bpf_refcount_acquire (n_1); +if (!m_1) { +bpf_obj_drop (n); +bpf_obj_drop (n_1); +return -1 ; + } + +bpf_spin_lock (&lock); +if (bpf_list_add (&head, &n_1->l, &n->l)) { +bpf_spin_unlock (&lock); +bpf_obj_drop (n); +bpf_obj_drop (m_1); +return -8 ; + } + l =bpf_list_del (&head, &n->l); + l_1 =bpf_list_del (&head, &m_1->l);bpf_spin_unlock (&lock);bpf_obj_drop (n); -if (!l) -return -6 ; +bpf_obj_drop (m_1);
Quoted 10 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c long test_bpf_list_del(void *ctx) · line 427
Quoted 3 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-2-bpf_obj_drop (container_of(l ,struct node_data ,l )); -return 0 ; +if (l)Can we do early returns, like
if (!l)
return -6;bpf_obj_drop(l);
if (!l_1)
return -7;bpf_obj_drop(l_1);
This change results in runtime errors, and the error log is provided below.
********************
117: (85) call bpf_list_del#101493 ;
R0=ptr_or_null_node_data(id=13,ref_obj_id=13,off=48) refs=6,9,11,13
118: (bf) r9 = r0 ;
R0=ptr_or_null_node_data(id=13,ref_obj_id=13,off=48) R9=ptr_or_null_node_data(id=13,ref_obj_id=13,off=48) refs=6,9,11,13 ; bpf_spin_unlock(&lock); @ refcounted_kptr.c:441
119: (18) r1 = 0xffff00006957bf50 ;
R1=map_value(map=.bss.A,ks=4,vs=36,off=32) refs=6,9,11,13
121: (85) call bpf_spin_unlock#94 ; refs=6,9,11,13
; bpf_obj_drop(n_rb); @ refcounted_kptr.c:442
122: (bf) r1 = r6 ; R1=ptr_node_data(ref_obj_id=6)
R6=ptr_node_data(ref_obj_id=6) refs=6,9,11,13
123: (b7) r2 = 0 ; R2=0 refs=6,9,11,13
124: (85) call bpf_obj_drop_impl#102200 ; refs=9,11,13
; bpf_obj_drop(n_new_ref); @ refcounted_kptr.c:443
125: (bf) r1 = r7 ; R1=ptr_node_data(ref_obj_id=9)
R7=ptr_node_data(ref_obj_id=9) refs=9,11,13
126: (b7) r2 = 0 ; R2=0 refs=9,11,13
127: (85) call bpf_obj_drop_impl#102200 ; refs=11,13
128: (b7) r0 = -11 ; R0=-11 refs=11,13
; if (!l_node) @ refcounted_kptr.c:445
129: (15) if r8 == 0x0 goto pc-22 108: R0=-11 R6=scalar() R7=scalar() R8=0 R9=ptr_or_null_node_data(id=13,ref_obj_id=13,off=48) R10=fp0 refs=13
; } @ refcounted_kptr.c:459
108: (95) exit
Unreleased reference id=13 alloc_insn=117BPF_EXIT instruction in main prog would lead to reference leak processed 194 insns (limit 1000000) max_states_per_insn 1 total_states 20 peak_states 20 mark_read 0
*******************
Quoted 77 lines
The point of returning different errors per each error path is to make it easy to understand where your test errored out by just looking at err.
Quoted 74 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +67
-0+bpf_obj_drop (container_of(l ,struct node_data ,l )); + else + err =-6 ; + +if (l_1) + bpf_obj_drop(container_of(l_1, struct node_data, l)); +else + err =-6 ; + +return err; }SEC ("?tc" )@@ -438,6 +467,71 @@ long list_del_without_lock_fail(void *ctx)return 0 ; } +SEC("?tc") +__failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") +long list_add_without_lock_fail(void *ctx) +{ +long err =0 ; +struct bpf_rb_node *rb; +struct bpf_list_node *l, *l_1; +struct node_data *n, *n_1, *m_1; + + err =__insert_in_tree_and_list (&head, &root, &lock); +if (err) +return err; + +bpf_spin_lock (&lock); + rb =bpf_rbtree_first (&root); +if (!rb) { +bpf_spin_unlock (&lock); +return -4 ; + } + + rb =bpf_rbtree_remove (&root, rb); +bpf_spin_unlock (&lock); +if (!rb) +return -5 ; + + n = container_of(rb, struct node_data, r); + n_1 =bpf_obj_new (typeof (*n_1)); +if (!n_1) { +bpf_obj_drop (n); +return -1 ; + } + m_1 =bpf_refcount_acquire (n_1); +if (!m_1) { +bpf_obj_drop (n); +bpf_obj_drop (n_1); +return -1 ; + } + +/* Intentionally no lock: verifier should reject bpf_list_add without lock */ +if (bpf_list_add (&head, &n_1->l, &n->l)) { +bpf_obj_drop (n); +bpf_obj_drop (m_1); +return -8 ; + } + +bpf_spin_lock (&lock); + l =bpf_list_del (&head, &n->l); + l_1 =bpf_list_del (&head, &m_1->l); +bpf_spin_unlock (&lock); +bpf_obj_drop (n); +bpf_obj_drop (m_1); + +if (l) + bpf_obj_drop(container_of(l, struct node_data, l)); +else + err =-6 ; +
Quoted 8 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c long list_del_without_lock_fail(void *ctx) · line 533
Quoted 7 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +7
-0+if (l_1) + bpf_obj_drop(container_of(l_1, struct node_data, l)); +else + err =-6 ; + +return err; +}Do we need this big test just to trigger that verifier error?
I simplified the "list_del/add_without_lock_fail" test cases, I'm unsure if this aligns with community expectations. An alternative would be to remove "list_del/add_without_lock_fail" test cases entirely. If you have a better approach, please let me know. Thank you.
Quoted 6 lines
Quoted 6 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-1+ SEC("tc")__success long rbtree_refcounted_node_ref_escapes (void *ctx) --2.50.1 (Apple Git-155)
I’ve also made the corresponding fixes based on the other suggestions. Please help review them again,thanks.
Signature · 2 lines
Yours, Chengkaitao
PATCH v5 5/6 bpf: add bpf_list_is_first/last/empty kfuncs
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Add three kfuncs for BPF linked list queries:
- bpf_list_is_first(head, node): true if node is the first in the list.
- bpf_list_is_last(head, node): true if node is the last in the list.
- bpf_list_empty(head): true if the list has no entries.
In previous versions, to implement the above functionality, it was necessary to first call bpf_list_pop_front/back to retrieve the first or last node before checking whether the passed-in node was the first or last one. After the check, the node had to be pushed back into the list using bpf_list_push_front/back, which was very inefficient.
Now, with the bpf_list_is_first/last/empty kfuncs, we can directly check whether a node is the first, last, or whether the list is empty, without having to first retrieve the node.
--- kernel/bpf/helpers.c | 41 +++++++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 15 +++++++++++++-- 2 files changed, 54 insertions(+), 2 deletions(-)
kernel/bpf/helpers.c +41 -0
@@ -2521,6 +2521,44 @@ __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head,return -EINVAL ; } +__bpf_kfunc bool bpf_list_is_first(struct bpf_list_head *head, struct bpf_list_node *node) +{ +struct list_head *h = (struct list_head *)head; +struct bpf_list_node_kern *n = (struct bpf_list_node_kern *)node; + +if (unlikely (!h->next) ||list_empty (h)) +return false; + +if (READ_ONCE (n->owner) != head) +return false; + +return h->next == &n->list_head; +} + +__bpf_kfunc bool bpf_list_is_last(struct bpf_list_head *head, struct bpf_list_node *node) +{ +struct list_head *h = (struct list_head *)head; +struct bpf_list_node_kern *n = (struct bpf_list_node_kern *)node; + +if (unlikely (!h->next) ||list_empty (h)) +return false; + +if (READ_ONCE (n->owner) != head) +return false; + +return h->prev == &n->list_head; +} + +__bpf_kfunc bool bpf_list_empty(struct bpf_list_head *head) +{ +struct list_head *h = (struct list_head *)head; + +if (unlikely (!h->next)) +return true; + +return list_empty (h); +} + __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,struct bpf_rb_node *node) {
@@ -4591,6 +4629,9 @@ BTF_ID_FLAGS(func, bpf_list_del, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_front, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_back, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_add_impl) +BTF_ID_FLAGS(func, bpf_list_is_first) +BTF_ID_FLAGS(func, bpf_list_is_last) +BTF_ID_FLAGS(func, bpf_list_empty) BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_RCU | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_release, KF_RELEASE)BTF_ID_FLAGS (func, bpf_rbtree_remove,KF_ACQUIRE |KF_RET_NULL )
kernel/bpf/verifier.c +13 -2
@@ -12465,6 +12465,9 @@ enum special_kfunc_type { KF_bpf_list_front, KF_bpf_list_back, KF_bpf_list_add_impl, + KF_bpf_list_is_first, + KF_bpf_list_is_last, + KF_bpf_list_empty, KF_bpf_cast_to_kern_ctx, KF_bpf_rdonly_cast, KF_bpf_rcu_read_lock,
@@ -12527,6 +12530,9 @@ BTF_ID(func, bpf_list_del) BTF_ID(func, bpf_list_front) BTF_ID(func, bpf_list_back) BTF_ID(func, bpf_list_add_impl) +BTF_ID(func, bpf_list_is_first) +BTF_ID(func, bpf_list_is_last) +BTF_ID(func, bpf_list_empty) BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast)BTF_ID (func, bpf_rcu_read_lock)
@@ -13003,7 +13009,10 @@ static bool is_bpf_list_api_kfunc(u32 btf_id) btf_id == special_kfunc_list[KF_bpf_list_del] || btf_id == special_kfunc_list[KF_bpf_list_front] || btf_id == special_kfunc_list[KF_bpf_list_back] || - btf_id == special_kfunc_list[KF_bpf_list_add_impl]; + btf_id == special_kfunc_list[KF_bpf_list_add_impl] || + btf_id == special_kfunc_list[KF_bpf_list_is_first] || + btf_id == special_kfunc_list[KF_bpf_list_is_last] || + btf_id == special_kfunc_list[KF_bpf_list_empty]; }static bool is_bpf_rbtree_api_kfunc (u32 btf_id)
@@ -13126,7 +13135,9 @@ static bool check_kfunc_is_graph_node_api(struct bpf_verifier_env *env, ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || kfunc_btf_id == special_kfunc_list[KF_bpf_list_del] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl]); + kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_is_first] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_is_last]);break ;case BPF_RB_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] ||
Signature · 1 line
2.50.1 (Apple Git-155)
Re: [PATCH v5 5/6] bpf: add bpf_list_is_first/last/empty kfuncs
Quoted 28 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
Add three kfuncs for BPF linked list queries:
-bpf_list_is_first(head, node): true if node is the first in the list.
-bpf_list_is_last(head, node): true if node is the last in the list.
-bpf_list_empty(head): true if the list has no entries.In previous versions, to implement the above functionality, it was necessary to first call bpf_list_pop_front/back to retrieve the first or last node before checking whether the passed-in node was the first or last one. After the check, the node had to be pushed back into the list using bpf_list_push_front/back, which was very inefficient.
Now, with the bpf_list_is_first/last/empty kfuncs, we can directly check whether a node is the first, last, or whether the list is empty, without having to first retrieve the node.
Signed-off-by Kaitao Cheng <[email protected]>--- kernel/bpf/helpers.c | 41 +++++++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 15 +++++++++++++-- 2 files changed, 54 insertions(+), 2 deletions(-)kernel/bpf/helpers.c +0
-0
kernel/bpf/helpers.c __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head, · line 2530
Quoted 10 lines
kernel/bpf/helpers.c +7
-0@@ -2521,6 +2521,44 @@ __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head,return -EINVAL ; } +__bpf_kfunc bool bpf_list_is_first(struct bpf_list_head *head, struct bpf_list_node *node) +{ +struct list_head *h = (struct list_head *)head; +struct bpf_list_node_kern *n = (struct bpf_list_node_kern *)node; + +if (unlikely (!h->next) ||list_empty (h)) +return false;
Do we need this block?
It sounds like a problem if we end up in the situation where node->owner points to the uninitialized head - the list is corrupted.
kernel/bpf/helpers.c __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head, · line 2535
Quoted 5 lines
kernel/bpf/helpers.c +5
-0+ +if (READ_ONCE (n->owner) != head) +return false; + +return h->next == &n->list_head;
Can we reuse list_is_first() here for simplicity?
Quoted 4 lines
kernel/bpf/helpers.c +4
-0+} + +__bpf_kfunc bool bpf_list_is_last(struct bpf_list_head *head, struct bpf_list_node *node) +{
kernel/bpf/helpers.c __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head, · line 2549
Quoted 10 lines
kernel/bpf/helpers.c +10
-0+struct list_head *h = (struct list_head *)head; +struct bpf_list_node_kern *n = (struct bpf_list_node_kern *)node; + +if (unlikely (!h->next) ||list_empty (h)) +return false; + +if (READ_ONCE (n->owner) != head) +return false; + +return h->prev == &n->list_head;
Here maybe list_is_last() going to work as well?
Quoted 74 lines
kernel/bpf/helpers.c +15
-0+} + +__bpf_kfunc bool bpf_list_empty(struct bpf_list_head *head) +{ +struct list_head *h = (struct list_head *)head; + +if (unlikely (!h->next)) +return true; + +return list_empty (h); +} + __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,struct bpf_rb_node *node) {@@ -4591,6 +4629,9 @@ BTF_ID_FLAGS(func, bpf_list_del, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_front, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_back, KF_RET_NULL) BTF_ID_FLAGS(func, bpf_list_add_impl) +BTF_ID_FLAGS(func, bpf_list_is_first) +BTF_ID_FLAGS(func, bpf_list_is_last) +BTF_ID_FLAGS(func, bpf_list_empty) BTF_ID_FLAGS(func, bpf_task_acquire, KF_ACQUIRE | KF_RCU | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_task_release, KF_RELEASE)BTF_ID_FLAGS (func, bpf_rbtree_remove,KF_ACQUIRE |KF_RET_NULL )kernel/bpf/verifier.c +13
-2@@ -12465,6 +12465,9 @@ enum special_kfunc_type { KF_bpf_list_front, KF_bpf_list_back, KF_bpf_list_add_impl, + KF_bpf_list_is_first, + KF_bpf_list_is_last, + KF_bpf_list_empty, KF_bpf_cast_to_kern_ctx, KF_bpf_rdonly_cast, KF_bpf_rcu_read_lock,@@ -12527,6 +12530,9 @@ BTF_ID(func, bpf_list_del) BTF_ID(func, bpf_list_front) BTF_ID(func, bpf_list_back) BTF_ID(func, bpf_list_add_impl) +BTF_ID(func, bpf_list_is_first) +BTF_ID(func, bpf_list_is_last) +BTF_ID(func, bpf_list_empty) BTF_ID(func, bpf_cast_to_kern_ctx) BTF_ID(func, bpf_rdonly_cast)BTF_ID (func, bpf_rcu_read_lock)@@ -13003,7 +13009,10 @@ static bool is_bpf_list_api_kfunc(u32 btf_id) btf_id == special_kfunc_list[KF_bpf_list_del] || btf_id == special_kfunc_list[KF_bpf_list_front] || btf_id == special_kfunc_list[KF_bpf_list_back] || - btf_id == special_kfunc_list[KF_bpf_list_add_impl]; + btf_id == special_kfunc_list[KF_bpf_list_add_impl] || + btf_id == special_kfunc_list[KF_bpf_list_is_first] || + btf_id == special_kfunc_list[KF_bpf_list_is_last] || + btf_id == special_kfunc_list[KF_bpf_list_empty]; }static bool is_bpf_rbtree_api_kfunc (u32 btf_id)@@ -13126,7 +13135,9 @@ static bool check_kfunc_is_graph_node_api(struct bpf_verifier_env *env, ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || kfunc_btf_id == special_kfunc_list[KF_bpf_list_push_back_impl] || kfunc_btf_id == special_kfunc_list[KF_bpf_list_del] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl]); + kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_is_first] || + kfunc_btf_id == special_kfunc_list[KF_bpf_list_is_last]);break ;case BPF_RB_NODE : ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] ||Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v5 6/6 selftests/bpf: Add test cases for bpf_list_is_first/is_last/empty
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Rename test_list_add_del to list_add_del_and_check and extend it to cover the new kfuncs: assert list non-empty after insert, assert is_first(n) and is_last(m_1) after bpf_list_add, and assert list empty after removing both nodes.
--- .../testing/selftests/bpf/bpf_experimental.h | 15 +++++++++++ .../selftests/bpf/progs/refcounted_kptr.c | 27 +++++++++++++++---- 2 files changed, 37 insertions(+), 5 deletions(-)
tools/testing/selftests/bpf/bpf_experimental.h +15 -0
@@ -126,6 +126,21 @@ extern int bpf_list_add_impl(struct bpf_list_head *head, struct bpf_list_node *n/* Convenience macro to wrap over bpf_list_add_impl */ #define bpf_list_add (head, new, prev) bpf_list_add_impl(head, new, prev, NULL, 0) +/* Description +* Return true if 'node' is the first node in the list with head 'head'. +*/ +extern bool bpf_list_is_first(struct bpf_list_head *head, struct bpf_list_node *node) __ksym; + +/* Description +* Return true if 'node' is the last node in the list with head 'head'. +*/ +extern bool bpf_list_is_last(struct bpf_list_head *head, struct bpf_list_node *node) __ksym; + +/* Description +* Return true if the list with head 'head' has no entries. +*/ +extern bool bpf_list_empty(struct bpf_list_head *head) __ksym; +/* Description * Remove 'node' from rbtree with root 'root' * Returns
tools/testing/selftests/bpf/progs/refcounted_kptr.c +22 -5
@@ -367,14 +367,14 @@ long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \INSERT_STASH_READ (true,"insert_stash_read: remove from tree" );INSERT_STASH_READ (false,"insert_stash_read: don't remove from tree" ); -/* Insert one node in tree and list, remove it from tree, add a second -* node after it in list with bpf_list_add, then remove both nodes from -* list via bpf_list_del. +/* Insert one node in tree and list, remove it from tree, add a second node +* after it with bpf_list_add, check bpf_list_is_first/is_last/empty, then +* remove both nodes from list via bpf_list_del. */ SEC("tc") -__description("test_list_add_del: test bpf_list_add/del") +__description("list_add_del_and_check: test bpf_list_add/del/is_first/is_last/empty") __success __retval(0) -long test_list_add_del(void *ctx) +long list_add_del_and_check(void *ctx) {long err =0 ;struct bpf_rb_node *rb;
@@ -386,6 +386,11 @@ long test_list_add_del(void *ctx)return err;bpf_spin_lock (&lock); +if (bpf_list_empty (&head)) { +bpf_spin_unlock (&lock); +return -7 ; + } + rb =bpf_rbtree_first (&root);if (!rb) {bpf_spin_unlock (&lock);
@@ -418,6 +423,14 @@ long test_list_add_del(void *ctx)return -8 ; } +if (!bpf_list_is_first (&head, &n->l) || + !bpf_list_is_last (&head, &m_1->l)) { +bpf_spin_unlock (&lock); +bpf_obj_drop (n); +bpf_obj_drop (m_1); +return -9 ; + } + l =bpf_list_del (&head, &n->l); l_1 =bpf_list_del (&head, &m_1->l);bpf_spin_unlock (&lock);
@@ -434,6 +447,10 @@ long test_list_add_del(void *ctx)else err =-6 ; +bpf_spin_lock (&lock); +if (!bpf_list_empty (&head)) + err =-7 ; +bpf_spin_unlock (&lock);return err; }
Signature · 1 line
2.50.1 (Apple Git-155)