bpf: Extend the bpf_list family of APIs
Subsystems (4)
v6 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.
Four 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_node_is_edge: check if a node is the first or last in the listbpf_list_empty: check if the list is empty
refactor kfunc checks to table-driven approach, and add test cases for the aforementioned kfuncs.
Changes in v6:
- Merge [patch v5 (2,4,6)/6] into [patch v6 4/5]
- If list_head was 0-initialized, init it
- refactor kfunc checks to table-driven approach
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 v5:
https://lore.kernel.org/all/[email protected]/
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 (5):
bpf: Introduce the bpf_list_del kfunc.
bpf: Add bpf_list_add_impl to insert node after a given list node
bpf: Add bpf_list_is_edge/empty kfuncs
selftests/bpf: Add test cases for bpf_list_del/add/is_edge/empty bpf/verifier: refactor kfunc checks to table-driven approach
kernel/bpf/helpers.c | 98 ++++++++++ kernel/bpf/verifier.c | 103 +++++++--- .../testing/selftests/bpf/bpf_experimental.h | 39 ++++ .../selftests/bpf/progs/refcounted_kptr.c | 182 ++++++++++++++++++ 4 files changed, 398 insertions(+), 24 deletions(-)
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v6 1/5 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.
We have added an additional parameter bpf_list_head *head to bpf_list_del, as the verifier requires the head parameter to check whether the lock is being held.
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 | 27 +++++++++++++++++++++++++++ kernel/bpf/verifier.c | 6 +++++- 2 files changed, 32 insertions(+), 1 deletion(-)
kernel/bpf/helpers.c +27 -0
@@ -2459,6 +2459,32 @@ __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 list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ +if (unlikely (!h->next)) { +INIT_LIST_HEAD (h); +return NULL ; + } + +if (unlikely (!knode)) +return NULL ; + +if (WARN_ON_ONCE (READ_ONCE (knode->owner) != head)) +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 +4571,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 v6 1/5] bpf: Introduce the bpf_list_del kfunc.
Quoted 11 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.
We have added an additional parameter
bpf_list_head*head tobpf_list_del, as the verifier requires the head parameter to check whether the lock is being held.
Quoted 6 lines
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]>---
Quoted 1 line
[...]
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v6 1/5] bpf: Introduce the bpf_list_del kfunc.
In reply to ChengkaitaoQuoted 32 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.
We have added an additional parameter
bpf_list_head*head tobpf_list_del, as the verifier requires the head parameter to check whether the lock is being held.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 | 27 +++++++++++++++++++++++++++ kernel/bpf/verifier.c | 6 +++++- 2 files changed, 32 insertions(+), 1 deletion(-)kernel/bpf/helpers.c +3
-0@@ -2459,6 +2459,32 @@ __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) +{
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2474
Quoted 10 lines
kernel/bpf/helpers.c +10
-0+struct bpf_list_node_kern *knode = (struct bpf_list_node_kern *)node; +struct list_head *h = (void *)head; + +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ +if (unlikely (!h->next)) { +INIT_LIST_HEAD (h); +return NULL ; + }
nit: I would avoid doing this here, just for symmetry. If we are part of the list after the owner checks, this should be initialized correctly anyway.
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2477
Quoted 3 lines
kernel/bpf/helpers.c +3
-0+ +if (unlikely (!knode)) +return NULL ;
nit: It seems like node can't (shouldn't) be NULL, so we can lose this check.
Quoted 63 lines
kernel/bpf/helpers.c +11
-0+ +if (WARN_ON_ONCE (READ_ONCE (knode->owner) != head)) +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 +4571,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
-2@@ -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] || --2.50.1 (Apple Git-155)
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v6 1/5] bpf: Introduce the bpf_list_del kfunc.
Quoted 40 lines · Kumar Kartikeya Dwivedi
Quoted 38 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.
We have added an additional parameter
bpf_list_head*head tobpf_list_del, as the verifier requires the head parameter to check whether the lock is being held.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 | 27 +++++++++++++++++++++++++++ kernel/bpf/verifier.c | 6 +++++- 2 files changed, 32 insertions(+), 1 deletion(-)kernel/bpf/helpers.c +9
-0@@ -2459,6 +2459,32 @@ __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 list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/
Quoted 8 lines
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2474
Quoted 4 lines
kernel/bpf/helpers.c +4
-0+if (unlikely (!h->next)) { +INIT_LIST_HEAD (h); +return NULL ; + }nit: I would avoid doing this here, just for symmetry. If we are part of the list after the owner checks, this should be initialized correctly anyway.
Hmm, looks like I should take my ack back (just in principle, there's no bug here).
I see you copied the comment and check from __bpf_list_del. I was looking at rbtree_remove to see whether it did RB_CLEAR_NODE(n).
I think it's fine to keep this init, but let's try not repeating the same logic twice.
I would make all 3 (pop_front, pop_back, list_del) use __bpf_list_del. Just pass h->next, h->prev, or node depending on which one is being called.
Quoted 70 lines
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2477
Quoted 4 lines
kernel/bpf/helpers.c +3
-0+ +if (unlikely (!knode)) +return NULL ;nit: It seems like node can't (shouldn't) be NULL, so we can lose this check.
Quoted 63 lines
kernel/bpf/helpers.c +11
-0+ +if (WARN_ON_ONCE (READ_ONCE (knode->owner) != head)) +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 +4571,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
-2@@ -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] || --2.50.1 (Apple Git-155)
PATCH v6 2/5 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 | 34 ++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 17 +++++++++++++---- 2 files changed, 47 insertions(+), 4 deletions(-)
kernel/bpf/helpers.c +34 -0
@@ -2505,6 +2505,39 @@ __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; +struct list_head *h = (void *)head; + +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ +if (unlikely (!h->next)) { +INIT_LIST_HEAD (h); + goto fail; + } + +if (WARN_ON_ONCE (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) {
@@ -4574,6 +4607,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 +13 -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,17 @@ 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]) { +/* list/rbtree_add_impl have an extra arg (prev/less), +* so args-to-fixup are in different 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)
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v6 2/5] bpf: Add bpf_list_add_impl to insert node after a given list node
Quoted 28 lines · Chengkaitao
From: 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. frombpf_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 tobpf_list_add_impl, as the verifier requires the head parameter to check whether the lock is being held.Returns 0 on success,
-EINVALif '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.Signed-off-by Kaitao Cheng <[email protected]>--- kernel/bpf/helpers.c | 34 ++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 17 +++++++++++++---- 2 files changed, 47 insertions(+), 4 deletions(-)kernel/bpf/helpers.c +0
-0
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_back(struct bpf_list_head *head) · line 2511
Quoted 7 lines
kernel/bpf/helpers.c +4
-0@@ -2505,6 +2505,39 @@ __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)
I have pretty much the same comment here, there is a lot of duplication between this and __bpf_list_add.
We can write list_add_tail in terms of __list_add, and then unify all of this.
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_back(struct bpf_list_head *head) · line 2523
Quoted 12 lines
kernel/bpf/helpers.c +12
-0+{ +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; +struct list_head *h = (void *)head; + +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ +if (unlikely (!h->next)) { +INIT_LIST_HEAD (h); + goto fail;
Not clear to me why we should fail here; why can't we continue adding after initializing the list head?
E.g. __bpf_list_add isn't doing it.
Quoted 100 lines
kernel/bpf/helpers.c +18
-0+ } + +if (WARN_ON_ONCE (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) {@@ -4574,6 +4607,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 +13
-5@@ -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,17 @@ 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]) { +/* list/rbtree_add_impl have an extra arg (prev/less), +* so args-to-fixup are in different 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 ; } --2.50.1 (Apple Git-155)
PATCH v6 3/5 bpf: Add bpf_list_is_edge/empty kfuncs
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Add three kfuncs for BPF linked list queries:
- bpf_list_node_is_edge(head, node, is_first): true if node is the first (when is_first is true) or the last (when is_first is false) 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_edge/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 | 37 +++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 11 +++++++++-- 2 files changed, 46 insertions(+), 2 deletions(-)
kernel/bpf/helpers.c +37 -0
@@ -2538,6 +2538,41 @@ __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head,return -EINVAL ; } +__bpf_kfunc bool bpf_list_node_is_edge(struct bpf_list_head *head, +struct bpf_list_node *node,bool is_first) +{ +struct list_head *h = (struct list_head *)head, *edge; +struct bpf_list_node_kern *n = (struct bpf_list_node_kern *)node; + +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ +if (unlikely (!h->next)) +INIT_LIST_HEAD (h); + +if (list_empty (h)) +return false; + +if (READ_ONCE (n->owner) != head) +return false; + + edge = is_first ? h->next : h->prev; +return edge == &n->list_head; +} + +__bpf_kfunc bool bpf_list_empty(struct bpf_list_head *head) +{ +struct list_head *h = (struct list_head *)head; + +/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't +* called on its fields, so init here +*/ +if (unlikely (!h->next)) +INIT_LIST_HEAD (h); + +return list_empty (h); +} + __bpf_kfunc struct bpf_rb_node *bpf_rbtree_remove(struct bpf_rb_root *root,struct bpf_rb_node *node) {
@@ -4608,6 +4643,8 @@ 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_node_is_edge) +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 +9 -2
@@ -12465,6 +12465,8 @@ enum special_kfunc_type { KF_bpf_list_front, KF_bpf_list_back, KF_bpf_list_add_impl, + KF_bpf_list_node_is_edge, + KF_bpf_list_empty, KF_bpf_cast_to_kern_ctx, KF_bpf_rdonly_cast, KF_bpf_rcu_read_lock,
@@ -12527,6 +12529,8 @@ 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_node_is_edge) +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 +13007,9 @@ 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_node_is_edge] || + btf_id == special_kfunc_list[KF_bpf_list_empty]; }static bool is_bpf_rbtree_api_kfunc (u32 btf_id)
@@ -13126,7 +13132,8 @@ 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_node_is_edge]);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)
[email protected]
AI reviewRe: [PATCH v6 3/5] bpf: Add bpf_list_is_edge/empty kfuncs
The commit message says "three kfuncs" but the description lists two and the patch adds two (bpf_list_node_is_edge and bpf_list_empty). It looks like this is a leftover from v5 where there were…
Quoted 4 lines
Add three kfuncs for BPF linked list queries:
-bpf_list_node_is_edge(head, node, is_first): true if node is the first (whenis_firstis true) or the last (whenis_firstis false) in the list.
-bpf_list_empty(head): true if the list has no entries.
The commit message says "three kfuncs" but the description lists two and the patch adds two (bpf_list_node_is_edge and bpf_list_empty). It looks like this is a leftover from v5 where there were three separate functions (bpf_list_is_first, bpf_list_is_last, bpf_list_empty) before they were consolidated into two. Should this say "two kfuncs"?
---
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/22674350640
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v6 3/5] bpf: Add bpf_list_is_edge/empty kfuncs
Quoted 6 lines · On Wed, 4 Mar 2026 at 16:34, <[email protected]> wrote:
Quoted 5 lines
Add three kfuncs for BPF linked list queries:
-bpf_list_node_is_edge(head, node, is_first): true if node is the first (whenis_firstis true) or the last (whenis_firstis false) in the list.
-bpf_list_empty(head): true if the list has no entries.
Quoted 7 lines
The commit message says "three kfuncs" but the description lists two and the patch adds two (
bpf_list_node_is_edgeandbpf_list_empty). It looks like this is a leftover from v5 where there were three separate functions (bpf_list_is_first,bpf_list_is_last,bpf_list_empty) before they were consolidated into two. Should this say "two kfuncs"?
I have no idea why you decided to combine this, there isn't any indication in the changelog, but it looked fine in previous versions. It pairs well with bpf_list_{first,last}. I would prefer going with separate kfuncs (is_first, is_last). Please also don't skip addressing feedback from previous versions.
E.g. https://lore.kernel.org/all/[email protected] suggested using list_is_first/list_is_last.
Quoted 6 lines
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/22674350640
PATCH v6 4/5 selftests/bpf: Add test cases for bpf_list_del/add/is_edge/empty
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Extend the refcounted_kptr test: add a node to both an rbtree and a list, retrieve the node from the rbtree to obtain the node pointer, then add a new node after the first in the list, and finally use bpf_list_del to remove both nodes.
The test asserts that the list is non-empty after insert, asserts the first and last nodes after bpf_list_add, and asserts that the list is empty after removing both nodes.
To verify the validity of bpf_list_del/add, the test also expects the verifier to reject calls to bpf_list_del/add made without holding the spin_lock.
--- .../testing/selftests/bpf/bpf_experimental.h | 39 ++++ .../selftests/bpf/progs/refcounted_kptr.c | 182 ++++++++++++++++++ 2 files changed, 221 insertions(+)
tools/testing/selftests/bpf/bpf_experimental.h +39 -0
@@ -99,6 +99,45 @@ 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 +* 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 +* Return true if 'node' is the first (when 'is_first' is true) or the last +* (when 'is_first' is false) node in the list with head 'head'. +*/ +extern bool bpf_list_node_is_edge(struct bpf_list_head *head, + struct bpf_list_node *node, bool is_first) __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 +182 -0
188 lines not on this page · raw message
Signature · 1 line
2.50.1 (Apple Git-155)
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH v6 4/5] selftests/bpf: Add test cases for bpf_list_del/add/is_edge/empty
Quoted 12 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
Extend the
refcounted_kptrtest: add a node to both an rbtree and a list, retrieve the node from the rbtree to obtain the node pointer, then add a new node after the first in the list, and finally usebpf_list_delto remove both nodes.The test asserts that the list is non-empty after insert, asserts the first and last nodes after
bpf_list_add, and asserts that the list is empty after removing both nodes.
Quoted 6 lines
To verify the validity of bpf_list_del/add, the test also expects the verifier to reject calls to bpf_list_del/add made without holding the
spin_lock.Signed-off-by Kaitao Cheng <[email protected]>---
No reply to or feedback addressed from
https://lore.kernel.org/all/[email protected].
Please don't respin without acting on it, or explaining why you chose to skip it.
Quoted 41 lines
.../testing/selftests/bpf/bpf_experimental.h | 39 ++++ .../selftests/bpf/progs/refcounted_kptr.c | 182 ++++++++++++++++++ 2 files changed, 221 insertions(+)tools/testing/selftests/bpf/bpf_experimental.h +29
-0@@ -99,6 +99,45 @@ 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 +* 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 +* Return true if 'node' is the first (when 'is_first' is true) or the last
tools/testing/selftests/bpf/bpf_experimental.h extern struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head) __ks · line 140
Quoted 10 lines
tools/testing/selftests/bpf/bpf_experimental.h +10
-0+* (when 'is_first' is false) node in the list with head 'head'. +*/ +extern bool bpf_list_node_is_edge(struct bpf_list_head *head, + struct bpf_list_node *node, bool is_first) __ksym; + +/* Description +* Return true if the list with head 'head' has no entries. +*/ +extern bool bpf_list_empty(struct bpf_list_head *head) __ksym; +
Except the macro, the rest can come from vmlinux.h.
Quoted 8 lines
tools/testing/selftests/bpf/bpf_experimental.h +0
-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 373
Quoted 7 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +4
-0@@ -367,6 +367,188 @@ 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 with bpf_list_add, check bpf_list_node_is_edge/empty, then +* remove both nodes from list via bpf_list_del. +*/
Incorrect comment style.
Quoted 2 lines
tools/testing/selftests/bpf/progs/refcounted_kptr.c +1
-0+[...]
PATCH v6 5/5 bpf/verifier: refactor kfunc checks to table-driven approach
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Replace per-kfunc btf_id chains in list/rbtree/res_lock and graph node checks with btf_id_in_kfunc_table() and static kfunc tables for easier maintenance.
--- kernel/bpf/verifier.c | 93 +++++++++++++++++++++++++++++-------------- 1 file changed, 64 insertions(+), 29 deletions(-)
kernel/bpf/verifier.c +64 -29
@@ -12600,6 +12600,60 @@ BTF_ID(func, bpf_session_is_return) BTF_ID(func, bpf_stream_vprintk) BTF_ID(func, bpf_stream_print_stack) +static const enum special_kfunc_type bpf_list_api_kfuncs[] = { + KF_bpf_list_push_front_impl, + 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_list_add_impl, + KF_bpf_list_node_is_edge, + KF_bpf_list_empty, +}; + +/* Kfuncs that take a list node argument (bpf_list_node *). */ +static const enum special_kfunc_type bpf_list_node_api_kfuncs[] = { + KF_bpf_list_push_front_impl, + KF_bpf_list_push_back_impl, + KF_bpf_list_del, + KF_bpf_list_add_impl, + KF_bpf_list_node_is_edge, +}; + +/* Kfuncs that take an rbtree node argument (bpf_rb_node *). */ +static const enum special_kfunc_type bpf_rbtree_node_api_kfuncs[] = { + KF_bpf_rbtree_remove, + KF_bpf_rbtree_add_impl, + KF_bpf_rbtree_left, + KF_bpf_rbtree_right, +}; + +static const enum special_kfunc_type bpf_rbtree_api_kfuncs[] = { + KF_bpf_rbtree_add_impl, + KF_bpf_rbtree_remove, + KF_bpf_rbtree_first, + KF_bpf_rbtree_root, + KF_bpf_rbtree_left, + KF_bpf_rbtree_right, +}; + +static const enum special_kfunc_type bpf_res_spin_lock_kfuncs[] = { + KF_bpf_res_spin_lock, + KF_bpf_res_spin_unlock, + KF_bpf_res_spin_lock_irqsave, + KF_bpf_res_spin_unlock_irqrestore, +}; + +static bool btf_id_in_kfunc_table (u32 btf_id,const enum special_kfunc_type *kfuncs,int n) +{ +for (int i =0 ; i < n; i++) +if (btf_id == special_kfunc_list[kfuncs[i]]) +return true; +return false; +} +static bool is_task_work_add_kfunc (u32 func_id) { return func_id == special_kfunc_list[KF_bpf_task_work_schedule_signal] ||
@@ -13000,26 +13054,14 @@ static int check_reg_allocation_locked(struct bpf_verifier_env *env, struct bpf_static bool is_bpf_list_api_kfunc (u32 btf_id) { -return btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || - 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] || - btf_id == special_kfunc_list[KF_bpf_list_add_impl] || - btf_id == special_kfunc_list[KF_bpf_list_node_is_edge] || - btf_id == special_kfunc_list[KF_bpf_list_empty]; +return btf_id_in_kfunc_table (btf_id, bpf_list_api_kfuncs, +ARRAY_SIZE (bpf_list_api_kfuncs)); }static bool is_bpf_rbtree_api_kfunc (u32 btf_id) { -return btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl] || - btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || - btf_id == special_kfunc_list[KF_bpf_rbtree_first] || - btf_id == special_kfunc_list[KF_bpf_rbtree_root] || - btf_id == special_kfunc_list[KF_bpf_rbtree_left] || - btf_id == special_kfunc_list[KF_bpf_rbtree_right]; +return btf_id_in_kfunc_table (btf_id, bpf_rbtree_api_kfuncs, +ARRAY_SIZE (bpf_rbtree_api_kfuncs)); }static bool is_bpf_iter_num_api_kfunc (u32 btf_id)
@@ -13037,10 +13079,8 @@ static bool is_bpf_graph_api_kfunc(u32 btf_id)static bool is_bpf_res_spin_lock_kfunc (u32 btf_id) { -return btf_id == special_kfunc_list[KF_bpf_res_spin_lock] || - btf_id == special_kfunc_list[KF_bpf_res_spin_unlock] || - btf_id == special_kfunc_list[KF_bpf_res_spin_lock_irqsave] || - btf_id == special_kfunc_list[KF_bpf_res_spin_unlock_irqrestore]; +return btf_id_in_kfunc_table (btf_id, bpf_res_spin_lock_kfuncs, +ARRAY_SIZE (bpf_res_spin_lock_kfuncs)); }static bool is_bpf_arena_kfunc (u32 btf_id)
@@ -13129,17 +13169,12 @@ 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_del] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_node_is_edge]); + ret =btf_id_in_kfunc_table (kfunc_btf_id, bpf_list_node_api_kfuncs, +ARRAY_SIZE (bpf_list_node_api_kfuncs));break ;case BPF_RB_NODE : - ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || - kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_left] || - kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_right]); + ret =btf_id_in_kfunc_table (kfunc_btf_id, bpf_rbtree_node_api_kfuncs, +ARRAY_SIZE (bpf_rbtree_node_api_kfuncs));break ;default : verbose(env, "verifier internal error: unexpected graph node argument type %s\n",
Signature · 1 line
2.50.1 (Apple Git-155)
[email protected]
AI reviewRe: [PATCH v6 5/5] bpf/verifier: refactor kfunc checks to table-driven approach
The continuation line here has one fewer space than the other three call sites (is_bpf_list_api_kfunc, is_bpf_rbtree_api_kfunc, and check_kfunc_is_graph_node_api), so ARRAY_SIZE doesn't align to the…
Quoted 3 lines
kernel/bpf/verifier.c +0
-0
[ ... ]
kernel/bpf/verifier.c static bool is_bpf_graph_api_kfunc(u32 btf_id) · line 13084
Quoted 5 lines
static bool
is_bpf_res_spin_lock_kfunc(u32 btf_id){kernel/bpf/verifier.c +2
-0+return btf_id_in_kfunc_table (btf_id, bpf_res_spin_lock_kfuncs, +ARRAY_SIZE (bpf_res_spin_lock_kfuncs)); }
The continuation line here has one fewer space than the other three call sites (is_bpf_list_api_kfunc, is_bpf_rbtree_api_kfunc, and check_kfunc_is_graph_node_api), so ARRAY_SIZE doesn't align to the opening parenthesis of btf_id_in_kfunc_table(). Should this be aligned to match the others?
---
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/22674350640
Re: [PATCH v6 5/5] bpf/verifier: refactor kfunc checks to table-driven approach
In reply to ChengkaitaoNIT on the subject prefix: instead of bpf/verifier, it should be one of bpf, libbpf, selftests/bpf, bpftool, and "bpf, x86/arm64".
So, the subject can be "bpf: refactor kfunc checks using table-driven approach in verifier".
Thanks,
Leon
Quoted 142 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
Replace per-kfunc
btf_idchains in list/rbtree/res_lock and graph node checks withbtf_id_in_kfunc_table()and static kfunc tables for easier maintenance.Signed-off-by Kaitao Cheng <[email protected]>--- kernel/bpf/verifier.c | 93 +++++++++++++++++++++++++++++-------------- 1 file changed, 64 insertions(+), 29 deletions(-)kernel/bpf/verifier.c +64
-29@@ -12600,6 +12600,60 @@ BTF_ID(func, bpf_session_is_return) BTF_ID(func, bpf_stream_vprintk) BTF_ID(func, bpf_stream_print_stack) +static const enum special_kfunc_type bpf_list_api_kfuncs[] = { + KF_bpf_list_push_front_impl, + 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_list_add_impl, + KF_bpf_list_node_is_edge, + KF_bpf_list_empty, +}; + +/* Kfuncs that take a list node argument (bpf_list_node *). */ +static const enum special_kfunc_type bpf_list_node_api_kfuncs[] = { + KF_bpf_list_push_front_impl, + KF_bpf_list_push_back_impl, + KF_bpf_list_del, + KF_bpf_list_add_impl, + KF_bpf_list_node_is_edge, +}; + +/* Kfuncs that take an rbtree node argument (bpf_rb_node *). */ +static const enum special_kfunc_type bpf_rbtree_node_api_kfuncs[] = { + KF_bpf_rbtree_remove, + KF_bpf_rbtree_add_impl, + KF_bpf_rbtree_left, + KF_bpf_rbtree_right, +}; + +static const enum special_kfunc_type bpf_rbtree_api_kfuncs[] = { + KF_bpf_rbtree_add_impl, + KF_bpf_rbtree_remove, + KF_bpf_rbtree_first, + KF_bpf_rbtree_root, + KF_bpf_rbtree_left, + KF_bpf_rbtree_right, +}; + +static const enum special_kfunc_type bpf_res_spin_lock_kfuncs[] = { + KF_bpf_res_spin_lock, + KF_bpf_res_spin_unlock, + KF_bpf_res_spin_lock_irqsave, + KF_bpf_res_spin_unlock_irqrestore, +}; + +static bool btf_id_in_kfunc_table (u32 btf_id,const enum special_kfunc_type *kfuncs,int n) +{ +for (int i =0 ; i < n; i++) +if (btf_id == special_kfunc_list[kfuncs[i]]) +return true; +return false; +} +static bool is_task_work_add_kfunc (u32 func_id) { return func_id == special_kfunc_list[KF_bpf_task_work_schedule_signal] ||@@ -13000,26 +13054,14 @@ static int check_reg_allocation_locked(struct bpf_verifier_env *env, struct bpf_static bool is_bpf_list_api_kfunc (u32 btf_id) { -return btf_id == special_kfunc_list[KF_bpf_list_push_front_impl] || - 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] || - btf_id == special_kfunc_list[KF_bpf_list_add_impl] || - btf_id == special_kfunc_list[KF_bpf_list_node_is_edge] || - btf_id == special_kfunc_list[KF_bpf_list_empty]; +return btf_id_in_kfunc_table (btf_id, bpf_list_api_kfuncs, +ARRAY_SIZE (bpf_list_api_kfuncs)); }static bool is_bpf_rbtree_api_kfunc (u32 btf_id) { -return btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl] || - btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || - btf_id == special_kfunc_list[KF_bpf_rbtree_first] || - btf_id == special_kfunc_list[KF_bpf_rbtree_root] || - btf_id == special_kfunc_list[KF_bpf_rbtree_left] || - btf_id == special_kfunc_list[KF_bpf_rbtree_right]; +return btf_id_in_kfunc_table (btf_id, bpf_rbtree_api_kfuncs, +ARRAY_SIZE (bpf_rbtree_api_kfuncs)); }static bool is_bpf_iter_num_api_kfunc (u32 btf_id)@@ -13037,10 +13079,8 @@ static bool is_bpf_graph_api_kfunc(u32 btf_id)static bool is_bpf_res_spin_lock_kfunc (u32 btf_id) { -return btf_id == special_kfunc_list[KF_bpf_res_spin_lock] || - btf_id == special_kfunc_list[KF_bpf_res_spin_unlock] || - btf_id == special_kfunc_list[KF_bpf_res_spin_lock_irqsave] || - btf_id == special_kfunc_list[KF_bpf_res_spin_unlock_irqrestore]; +return btf_id_in_kfunc_table (btf_id, bpf_res_spin_lock_kfuncs, +ARRAY_SIZE (bpf_res_spin_lock_kfuncs)); }static bool is_bpf_arena_kfunc (u32 btf_id)@@ -13129,17 +13169,12 @@ 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_del] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_add_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_list_node_is_edge]); + ret =btf_id_in_kfunc_table (kfunc_btf_id, bpf_list_node_api_kfuncs, +ARRAY_SIZE (bpf_list_node_api_kfuncs));break ;case BPF_RB_NODE : - ret = (kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_remove] || - kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl] || - kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_left] || - kfunc_btf_id == special_kfunc_list[KF_bpf_rbtree_right]); + ret =btf_id_in_kfunc_table (kfunc_btf_id, bpf_rbtree_node_api_kfuncs, +ARRAY_SIZE (bpf_rbtree_node_api_kfuncs));break ;default : verbose(env, "verifier internal error: unexpected graph node argument type %s\n",
Hi Kaitao,
I think you should wait for some comments before sending the next revision.
The patch target is missing in subject: [PATCH bpf-next v6 ...
Thanks,
Leon
Quoted 66 lines · Chengkaitao
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.
Four 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_node_is_edge: check if a node is the first or last in the listbpf_list_empty: check if the list is emptyrefactor kfunc checks to table-driven approach, and add test cases for the aforementioned kfuncs.
Changes in v6:
- Merge [patch v5 (2,4,6)/6] into [patch v6 4/5]
- Iflist_headwas 0-initialized, init it
- refactor kfunc checks to table-driven approachChanges in v5:
- Fixbpf_objleak onbpf_list_add_implerrorChanges in v4:
- [patch v3 1/6] Revert to version v1
- Change the parameters ofbpf_list_add_implto (head, new, prev, ...)Changes in v3:
- Add a newlock_recmember to structbpf_reference_statefor lock holding detection.
- Add test cases to verify that the verifier correctly restricts calls tobpf_list_delwhen thespin_lockis not held.Changes in v2:
- Remove the head parameter frombpf_list_del
- Add bpf_list_add/is_first/is_last/empty to API and test casesLink to v5:
https://lore.kernel.org/all/[email protected]/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 (5):
bpf: Introduce thebpf_list_delkfunc.
bpf: Addbpf_list_add_implto insert node after a given list node
bpf: Add bpf_list_is_edge/empty kfuncs
selftests/bpf: Add test cases for bpf_list_del/add/is_edge/empty bpf/verifier: refactor kfunc checks to table-driven approachkernel/bpf/helpers.c | 98 ++++++++++ kernel/bpf/verifier.c | 103 +++++++--- .../testing/selftests/bpf/bpf_experimental.h | 39 ++++ .../selftests/bpf/progs/refcounted_kptr.c | 182 ++++++++++++++++++ 4 files changed, 398 insertions(+), 24 deletions(-)