bpf: Introduce the bpf_list_del API
Subsystems (4)
cover bpf: Introduce the bpf_list_del API
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.
We propose introducing the bpf_list_del API, which allows users to directly remove a node from the list if the node pointer is obtained beforehand. This patch enhances the BPF list API, making it more list-like.
Kaitao Cheng (2):
bpf: Introduce the bpf_list_del kfunc.
selftests/bpf: Add test cases for bpf_list_del
kernel/bpf/helpers.c | 19 +++++++++ kernel/bpf/verifier.c | 6 ++- .../testing/selftests/bpf/bpf_experimental.h | 11 +++++ .../selftests/bpf/progs/refcounted_kptr.c | 41 +++++++++++++++++++ 4 files changed, 76 insertions(+), 1 deletion(-)
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH 1/2 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
@@ -2388,6 +2388,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;
@@ -4404,6 +4422,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
@@ -12345,6 +12345,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,
@@ -12399,6 +12400,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)
@@ -12862,6 +12864,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]; }
@@ -12970,7 +12973,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 1/2] bpf: Introduce the bpf_list_del kfunc.
Quoted 26 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 +1
-0@@ -2388,6 +2388,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,
kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2401
Quoted 10 lines
kernel/bpf/helpers.c +10
-0+ 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 ;
Existing __bpf_list_del() is actually using 'head', but here... passing 'head' just to warn on it ? Seems overkill.
Pass 'node' only. Then it will be more list-like.
Any other apis are missing?
pw-bot: cr
PATCH 2/2 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.
--- .../testing/selftests/bpf/bpf_experimental.h | 11 +++++ .../selftests/bpf/progs/refcounted_kptr.c | 41 +++++++++++++++++++ 2 files changed, 52 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 +41 -0
47 lines not on this page · raw message
Signature · 1 line
2.50.1 (Apple Git-155)