Skip to contentSkip to conversation

bpf: Extend the bpf_list family of APIs

PATCH Superseded Chengkaitao 4 participants 19 messages Mar 16 – Mar 22

Subsystems (4)

v8 of 9 Superseded Latest is v9 →

lore
Share & tools
lore
#0 lore raw

v8 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 list
bpf_list_add_impl: insert a node after a given list node
bpf_list_is_first: check if a node is the first in the list
bpf_list_is_last: check if a node is the last in the list
bpf_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 v8:
- Use [patch v7 5/5] as the start of the patch series
- Introduce double pointer prev_ptr in __bpf_list_del
- Extract refactored __bpf_list_del/add into separate patches
- Allow bpf_list_front/back result as the prev argument of bpf_list_add
- Split test cases

Changes in v7:
- Replace bpf_list_node_is_edge with bpf_list_is_first/is_last
- Reimplement __bpf_list_del and __bpf_list_add
- Simplify test cases

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 v7:
https://lore.kernel.org/all/[email protected]/

Link to v6:
https://lore.kernel.org/all/[email protected]/

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 (8):
bpf: refactor kfunc checks using table-driven approach in verifier
bpf: refactor __bpf_list_del to take list node pointer
bpf: Introduce the bpf_list_del kfunc.
bpf: refactor __bpf_list_add to take insertion point via **prev_ptr
bpf: Add bpf_list_add_impl to insert node after a given list node
bpf: allow bpf_list_front/back result as the prev argument of
bpf_list_add_impl
bpf: add bpf_list_is_first/last/empty kfuncs selftests/bpf: Add test cases for
bpf_list_del/add/is_first/is_last/empty

 kernel/bpf/helpers.c                          | 121 +++++--
 kernel/bpf/verifier.c                         | 116 +++++--
 .../testing/selftests/bpf/bpf_experimental.h  |  16 +
 .../selftests/bpf/progs/refcounted_kptr.c     | 311 ++++++++++++++++++
 4 files changed, 519 insertions(+), 45 deletions(-)
Signature · 1 line
2.50.1 (Apple Git-155)
#1 lore raw

PATCH v8 1/8 bpf: refactor kfunc checks using table-driven approach in verifier

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

Prepare for future extensions to the bpf_list API family.

---
 kernel/bpf/verifier.c | 79 +++++++++++++++++++++++++++++++------------
 1 file changed, 57 insertions(+), 22 deletions(-)
kernel/bpf/verifier.c +57 -22
index 4fbacd2149cd..64c1f8343dfa 100644
@@ -12639,6 +12639,53 @@ 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_front,
+	KF_bpf_list_back,
+};
+
+/* 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,
+};
+
+/* 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] ||
@@ -13038,22 +13085,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_front] ||
-	       btf_id == special_kfunc_list[KF_bpf_list_back];
+	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)
@@ -13071,10 +13110,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)
@@ -13163,14 +13200,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]);
+		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)
reviewer Reviewed-by on v8 1/8
#2 lore raw

Re: [PATCH bpf-next v8 1/8] bpf: refactor kfunc checks using table-driven approach in verifier

Quoted 9 lines · Chengkaitao

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

Prepare for future extensions to the bpf_list API family.

The change is valid, can you see if you can remove some of the is_bpf_*api_kfunc calls areound line 13000 and replace them with btf_id_in_kfunc_table calls?

And can you also do this refactoring for the other kfunc families? That way we replace all functions that match on the btf_id into a single call that takes in the array we are scanning for a match.

Quoted 12 lines
---
 kernel/bpf/verifier.c | 79 +++++++++++++++++++++++++++++++------------
 1 file changed, 57 insertions(+), 22 deletions(-)
kernel/bpf/verifier.c +0 -0
index 4fbacd2149cd..64c1f8343dfa 100644
@@ -12639,6 +12639,53 @@ BTF_ID(func, bpf_session_is_return)
 BTF_ID(func, bpf_stream_vprintk)
 BTF_ID(func, bpf_stream_print_stack)
 

kernel/bpf/verifier.c BTF_ID(func, bpf_session_is_return) · line 12651

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+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_front,
+	KF_bpf_list_back,
+};
+
+/* Kfuncs that take a list node argument (bpf_list_node *). */

Nit: Why add a description on just this and bpf_rbtree_node_api_kfuncs? I think a small comment on top of each if fine if a bit wordy because it's easy to spot when scanning for a specific kfunc family.

Quoted 99 lines
kernel/bpf/verifier.c +47 -22
+static const enum special_kfunc_type bpf_list_node_api_kfuncs[] = {
+	KF_bpf_list_push_front_impl,
+	KF_bpf_list_push_back_impl,
+};
+
+/* 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] ||
@@ -13038,22 +13085,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_front] ||
-	       btf_id == special_kfunc_list[KF_bpf_list_back];
+	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)
@@ -13071,10 +13110,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)
@@ -13163,14 +13200,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]);
+		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",
#3 lore raw

PATCH v8 2/8 bpf: refactor __bpf_list_del to take list node pointer

In reply to Chengkaitao

From: Kaitao Cheng <[email protected]>

Refactor __bpf_list_del to accept (head, struct list_head *n) instead of (head, bool tail). The caller now passes the specific node to remove:
bpf_list_pop_front passes h->next, bpf_list_pop_back passes h->prev.

Prepares for introducing bpf_list_del(head, node) kfunc to remove an arbitrary node when the user holds ownership.

---
 kernel/bpf/helpers.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)
kernel/bpf/helpers.c +9 -5
index cb6d242bd093..e87b263c5fe6 100644
@@ -2426,9 +2426,10 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 	return __bpf_list_add(n, head, true, meta ? meta->record : NULL, off);
 }
 
-static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tail)
+static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
+					    struct list_head *n)
 {
-	struct list_head *n, *h = (void *)head;
+	struct list_head *h = (void *)head;
 	struct bpf_list_node_kern *node;
 
 	/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't
@@ -2439,7 +2440,6 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai
 	if (list_empty(h))
 		return NULL;
 
-	n = tail ? h->prev : h->next;
 	node = container_of(n, struct bpf_list_node_kern, list_head);
 	if (WARN_ON_ONCE(READ_ONCE(node->owner) != head))
 		return NULL;
@@ -2451,12 +2451,16 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai
 
 __bpf_kfunc struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head)
 {
-	return __bpf_list_del(head, false);
+	struct list_head *h = (void *)head;
+
+	return __bpf_list_del(head, h->next);
 }
 
 __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)
 {
-	return __bpf_list_del(head, true);
+	struct list_head *h = (void *)head;
+
+	return __bpf_list_del(head, h->prev);
 }
 
 __bpf_kfunc struct bpf_list_node *bpf_list_front(struct bpf_list_head *head)
Signature · 1 line
2.50.1 (Apple Git-155)
#4 lore raw

Re: [PATCH bpf-next v8 2/8] bpf: refactor __bpf_list_del to take list node pointer

Quoted 19 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Refactor __bpf_list_del to accept (head, struct list_head *n) instead of (head, bool tail). The caller now passes the specific node to remove:
bpf_list_pop_front passes h->next, bpf_list_pop_back passes h->prev.

Prepares for introducing bpf_list_del(head, node) kfunc to remove an arbitrary node when the user holds ownership.

---
 kernel/bpf/helpers.c | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)
kernel/bpf/helpers.c +0 -0
index cb6d242bd093..e87b263c5fe6 100644

kernel/bpf/helpers.c __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head, · line 2432

Quoted 9 lines
kernel/bpf/helpers.c +3 -2
@@ -2426,9 +2426,10 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 	return __bpf_list_add(n, head, true, meta ? meta->record : NULL, off);
 }
 
-static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tail)
+static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
+					    struct list_head *n)
 {
-	struct list_head *n, *h = (void *)head;
+	struct list_head *h = (void *)head;

Note: The cast to void then back to list_head is necessary to avoid an "incompatible pointer types" error.

kernel/bpf/helpers.c static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai · line 2442

Quoted 8 lines
kernel/bpf/helpers.c +0 -1
 	struct bpf_list_node_kern *node;
 
 	/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't
@@ -2439,7 +2440,6 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai
 	if (list_empty(h))
 		return NULL;
 
-	n = tail ? h->prev : h->next;

The new code reads n _before_ we check if the list is initialized. So the n we are passing from the caller may well be NULL. However, __bpf_list_del() will in that case now a) call INIT_LIST_HEAD(() to properly set up prev/next, b) call list_empty() on the newly initialized list and exit without ever reading the NULL passed by the caller.

This is kind of counterintuitive: We are passing essentially a garbage value to __bpf_list_del that we thankfully end upi ignoring. Can you move the init check logic into the top-level kfuncs to make sure the list_head we're passing to __bpf_list_del is always valid? You can also just init the list and return NULL in that case - we know it's empty.

Quoted 22 lines
kernel/bpf/helpers.c +6 -2
 	node = container_of(n, struct bpf_list_node_kern, list_head);
 	if (WARN_ON_ONCE(READ_ONCE(node->owner) != head))
 		return NULL;
@@ -2451,12 +2451,16 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, bool tai
 
 __bpf_kfunc struct bpf_list_node *bpf_list_pop_front(struct bpf_list_head *head)
 {
-	return __bpf_list_del(head, false);
+	struct list_head *h = (void *)head;
+
+	return __bpf_list_del(head, h->next);
 }
 
 __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)
 {
-	return __bpf_list_del(head, true);
+	struct list_head *h = (void *)head;
+
+	return __bpf_list_del(head, h->prev);
 }
 
 __bpf_kfunc struct bpf_list_node *bpf_list_front(struct bpf_list_head *head)
#5 lore raw

PATCH v8 3/8 bpf: Introduce the bpf_list_del kfunc.

In reply to 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 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  | 11 +++++++++++
 kernel/bpf/verifier.c |  4 ++++
 2 files changed, 15 insertions(+)
kernel/bpf/helpers.c +11 -0
index e87b263c5fe6..dac346eb1e2f 100644
@@ -2437,6 +2437,8 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
 	 */
 	if (unlikely(!h->next))
 		INIT_LIST_HEAD(h);
+
+	/* verifier to guarantee n is a list node rather than the head */
 	if (list_empty(h))
 		return NULL;
 
@@ -2463,6 +2465,14 @@ __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)
 	return __bpf_list_del(head, h->prev);
 }
 
+__bpf_kfunc struct bpf_list_node *bpf_list_del(struct bpf_list_head *head,
+					       struct bpf_list_node *node)
+{
+	struct bpf_list_node_kern *kn = (void *)node;
+
+	return __bpf_list_del(head, &kn->list_head);
+}
+
 __bpf_kfunc struct bpf_list_node *bpf_list_front(struct bpf_list_head *head)
 {
 	struct list_head *h = (struct list_head *)head;
@@ -4549,6 +4559,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 +4 -0
index 64c1f8343dfa..e928ad4290c7 100644
@@ -12508,6 +12508,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,
@@ -12568,6 +12569,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)
@@ -12644,6 +12646,7 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 	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,
 };
@@ -12652,6 +12655,7 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 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,
 };
 
 /* Kfuncs that take an rbtree node argument (bpf_rb_node *). */
Signature · 1 line
2.50.1 (Apple Git-155)
#6 lore raw

Re: [PATCH bpf-next v8 3/8] bpf: Introduce the bpf_list_del kfunc.

Is this comment accurate for all callers of __bpf_list_del()?

kernel/bpf/helpers.c static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, · line 2443

Quoted 12 lines
kernel/bpf/helpers.c +2 -0
index e87b263c5fe6..dac346eb1e2f 100644
@@ -2437,6 +2437,8 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
 	 */
 	if (unlikely(!h->next))
 		INIT_LIST_HEAD(h);
+
+	/* verifier to guarantee n is a list node rather than the head */
 	if (list_empty(h))
 		return NULL;

Is this comment accurate for all callers of __bpf_list_del()?

For bpf_list_pop_front() and bpf_list_pop_back(), n is derived from h->next or h->prev. When the list is empty, h->next == h, so n is the head itself:

kernel/bpf/helpers.c:bpf_list_pop_front() {
    struct list_head *h = (void *)head;
    return __bpf_list_del(head, h->next);
                                ^^^^^^^ h when list is empty
}

In that case, the list_empty() check is the runtime defense against n == h, not the verifier. The verifier type guarantee only applies to the new bpf_list_del() path where node is a separate bpf_list_node argument.

Since __bpf_list_del() is shared by all three callers, this comment could mislead a future reader into thinking the list_empty() check is redundant, when it is actually essential for the pop paths.

Would it be better to move this comment into bpf_list_del() itself, or to qualify it as applying only to the bpf_list_del path?

[ ... ]

---
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/23141914395

#7 lore raw

Re: [PATCH bpf-next v8 3/8] bpf: Introduce the bpf_list_del kfunc.

In reply to Chengkaitao
Quoted 6 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.

Not sure what you mean by this, would saying "remove any node from a linked list" work:

Quoted 8 lines

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.

This is pretty confusing as a convention, and it's obvious in patch 8/8. Is it possible to hide this complexity from the user?

Quoted 11 lines
---
 kernel/bpf/helpers.c  | 11 +++++++++++
 kernel/bpf/verifier.c |  4 ++++
 2 files changed, 15 insertions(+)
kernel/bpf/helpers.c +0 -0
index e87b263c5fe6..dac346eb1e2f 100644

kernel/bpf/helpers.c static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head, · line 2441

Quoted 5 lines
kernel/bpf/helpers.c +2 -0
@@ -2437,6 +2437,8 @@ static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
 	 */
 	if (unlikely(!h->next))
 		INIT_LIST_HEAD(h);
+
+	/* verifier to guarantee n is a list node rather than the head */

Why add this comment here? At the very least you'd need to add this in the previous patch, but I think it's not particularly useful in general. It definitely doesn't work here because it's for existing code.

kernel/bpf/helpers.c __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head) · line 2473

Quoted 13 lines
kernel/bpf/helpers.c +6 -0
 	if (list_empty(h))
 		return NULL;
 
@@ -2463,6 +2465,14 @@ __bpf_kfunc struct bpf_list_node *bpf_list_pop_back(struct bpf_list_head *head)
 	return __bpf_list_del(head, h->prev);
 }
 
+__bpf_kfunc struct bpf_list_node *bpf_list_del(struct bpf_list_head *head,
+					       struct bpf_list_node *node)
+{
+	struct bpf_list_node_kern *kn = (void *)node;
+
+	return __bpf_list_del(head, &kn->list_head);

See the Sashiko review: https://sashiko.dev/#/patchset/20260316112843.78657-1-pilgrimtao%40gmail.com

1) The WARN_ON() issue is real, you'd need to adjust the warning.
2) The more important problem is the reuse bug. You need to make sure any elements in a list that don't get freed by during bpf_list_head_free() have NULL'ed left/right and owner fields.

Quoted 49 lines
kernel/bpf/helpers.c +3 -0
+}
+
 __bpf_kfunc struct bpf_list_node *bpf_list_front(struct bpf_list_head *head)
 {
 	struct list_head *h = (struct list_head *)head;
@@ -4549,6 +4559,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 +4 -0
index 64c1f8343dfa..e928ad4290c7 100644
@@ -12508,6 +12508,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,
@@ -12568,6 +12569,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)
@@ -12644,6 +12646,7 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 	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,
 };
@@ -12652,6 +12655,7 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 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,
 };
 
 /* Kfuncs that take an rbtree node argument (bpf_rb_node *). */
#8 lore raw

PATCH v8 4/8 bpf: refactor __bpf_list_add to take insertion point via **prev_ptr

In reply to Chengkaitao

From: Kaitao Cheng <[email protected]>

Refactor __bpf_list_add to accept (new, head, struct list_head **prev_ptr, ..) instead of (node, head, bool tail, ..). Load prev from *prev_ptr after INIT_LIST_HEAD(h), so we never dereference an uninitialized h->prev when head was 0-initialized (e.g. push_back passes &h->prev).

When prev is not the list head, validate that prev is in the list via its owner.

Prepares for bpf_list_add_impl(head, new, prev, ..) to insert after a given list node.

---
 kernel/bpf/helpers.c | 44 ++++++++++++++++++++++++++++----------------
 1 file changed, 28 insertions(+), 16 deletions(-)
kernel/bpf/helpers.c +28 -16
index dac346eb1e2f..a9665f97b3bc 100644
@@ -2379,11 +2379,13 @@ __bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *meta
 	return (void *)p__refcounted_kptr;
 }
 
-static int __bpf_list_add(struct bpf_list_node_kern *node,
+static int __bpf_list_add(struct bpf_list_node_kern *new,
 			  struct bpf_list_head *head,
-			  bool tail, struct btf_record *rec, u64 off)
+			  struct list_head **prev_ptr,
+			  struct btf_record *rec, u64 off)
 {
-	struct list_head *n = &node->list_head, *h = (void *)head;
+	struct list_head *n = &new->list_head, *h = (void *)head;
+	struct list_head *prev;
 
 	/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't
 	 * called on its fields, so init here
@@ -2391,39 +2393,49 @@ static int __bpf_list_add(struct bpf_list_node_kern *node,
 	if (unlikely(!h->next))
 		INIT_LIST_HEAD(h);
 
-	/* node->owner != NULL implies !list_empty(n), no need to separately
+	prev = *prev_ptr;
+
+	/* When prev is not the list head, it must be a node in this list. */
+	if (prev != h && WARN_ON_ONCE(READ_ONCE(container_of(
+	    prev, struct bpf_list_node_kern, list_head)->owner) != head))
+		goto fail;
+
+	/* new->owner != NULL implies !list_empty(n), no need to separately
 	 * check the latter
 	 */
-	if (cmpxchg(&node->owner, NULL, BPF_PTR_POISON)) {
-		/* Only called from BPF prog, no need to migrate_disable */
-		__bpf_obj_drop_impl((void *)n - off, rec, false);
-		return -EINVAL;
-	}
-
-	tail ? list_add_tail(n, h) : list_add(n, h);
-	WRITE_ONCE(node->owner, head);
+	if (cmpxchg(&new->owner, NULL, BPF_PTR_POISON))
+		goto fail;
 
+	list_add(n, prev);
+	WRITE_ONCE(new->owner, head);
 	return 0;
+
+fail:
+	/* Only called from BPF prog, no need to migrate_disable */
+	__bpf_obj_drop_impl((void *)n - off, rec, false);
+	return -EINVAL;
 }
 
 __bpf_kfunc int bpf_list_push_front_impl(struct bpf_list_head *head,
 					 struct bpf_list_node *node,
 					 void *meta__ign, u64 off)
 {
-	struct bpf_list_node_kern *n = (void *)node;
+	struct bpf_list_node_kern *new = (void *)node;
 	struct btf_struct_meta *meta = meta__ign;
+	struct list_head *h = (void *)head;
 
-	return __bpf_list_add(n, head, false, meta ? meta->record : NULL, off);
+	return __bpf_list_add(new, head, &h, meta ? meta->record : NULL, off);
 }
 
 __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 					struct bpf_list_node *node,
 					void *meta__ign, u64 off)
 {
-	struct bpf_list_node_kern *n = (void *)node;
+	struct bpf_list_node_kern *new = (void *)node;
 	struct btf_struct_meta *meta = meta__ign;
+	struct list_head *h = (void *)head;
 
-	return __bpf_list_add(n, head, true, meta ? meta->record : NULL, off);
+	return __bpf_list_add(new, head, &h->prev, meta ? meta->record : NULL, off);
 }
 
 static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
Signature · 1 line
2.50.1 (Apple Git-155)
#9 lore raw

Re: [PATCH bpf-next v8 4/8] bpf: refactor __bpf_list_add to take insertion point via **prev_ptr

Quoted 41 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Refactor __bpf_list_add to accept (new, head, struct list_head **prev_ptr, ..) instead of (node, head, bool tail, ..). Load prev from *prev_ptr after INIT_LIST_HEAD(h), so we never dereference an uninitialized h->prev when head was 0-initialized (e.g. push_back passes &h->prev).

When prev is not the list head, validate that prev is in the list via its owner.

Prepares for bpf_list_add_impl(head, new, prev, ..) to insert after a given list node.

---
 kernel/bpf/helpers.c | 44 ++++++++++++++++++++++++++++----------------
 1 file changed, 28 insertions(+), 16 deletions(-)
kernel/bpf/helpers.c +5 -3
index dac346eb1e2f..a9665f97b3bc 100644
@@ -2379,11 +2379,13 @@ __bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *meta
 	return (void *)p__refcounted_kptr;
 }
 
-static int __bpf_list_add(struct bpf_list_node_kern *node,
+static int __bpf_list_add(struct bpf_list_node_kern *new,
 			  struct bpf_list_head *head,
-			  bool tail, struct btf_record *rec, u64 off)
+			  struct list_head **prev_ptr,
+			  struct btf_record *rec, u64 off)
 {
-	struct list_head *n = &node->list_head, *h = (void *)head;
+	struct list_head *n = &new->list_head, *h = (void *)head;
+	struct list_head *prev;
 
 	/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't
 	 * called on its fields, so init here
@@ -2391,39 +2393,49 @@ static int __bpf_list_add(struct bpf_list_node_kern *node,
 	if (unlikely(!h->next))

kernel/bpf/helpers.c static int __bpf_list_add(struct bpf_list_node_kern *node, · line 2402

Quoted 10 lines
kernel/bpf/helpers.c +7 -1
 		INIT_LIST_HEAD(h);
 
-	/* node->owner != NULL implies !list_empty(n), no need to separately
+	prev = *prev_ptr;
+
+	/* When prev is not the list head, it must be a node in this list. */
+	if (prev != h && WARN_ON_ONCE(READ_ONCE(container_of(
+	    prev, struct bpf_list_node_kern, list_head)->owner) != head))
+		goto fail;
+

This is pretty difficult to read, can you clean this up?

Quoted 20 lines
kernel/bpf/helpers.c +8 -8
+	/* new->owner != NULL implies !list_empty(n), no need to separately
 	 * check the latter
 	 */
-	if (cmpxchg(&node->owner, NULL, BPF_PTR_POISON)) {
-		/* Only called from BPF prog, no need to migrate_disable */
-		__bpf_obj_drop_impl((void *)n - off, rec, false);
-		return -EINVAL;
-	}
-
-	tail ? list_add_tail(n, h) : list_add(n, h);
-	WRITE_ONCE(node->owner, head);
+	if (cmpxchg(&new->owner, NULL, BPF_PTR_POISON))
+		goto fail;
 
+	list_add(n, prev);
+	WRITE_ONCE(new->owner, head);
 	return 0;
+
+fail:
+	/* Only called from BPF prog, no need to migrate_disable */

kernel/bpf/helpers.c static int __bpf_list_add(struct bpf_list_node_kern *node, · line 2423

Quoted 10 lines
kernel/bpf/helpers.c +3 -1
+	__bpf_obj_drop_impl((void *)n - off, rec, false);
+	return -EINVAL;
 }
 
 __bpf_kfunc int bpf_list_push_front_impl(struct bpf_list_head *head,
 					 struct bpf_list_node *node,
 					 void *meta__ign, u64 off)
 {
-	struct bpf_list_node_kern *n = (void *)node;
+	struct bpf_list_node_kern *new = (void *)node;

I don't think this rename or the one in __bpf_list_add are useful, they also kind of obfuscate the point of the patch by accident imo.

Quoted 21 lines
kernel/bpf/helpers.c +5 -3
 	struct btf_struct_meta *meta = meta__ign;
+	struct list_head *h = (void *)head;
 
-	return __bpf_list_add(n, head, false, meta ? meta->record : NULL, off);
+	return __bpf_list_add(new, head, &h, meta ? meta->record : NULL, off);
 }
 
 __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 					struct bpf_list_node *node,
 					void *meta__ign, u64 off)
 {
-	struct bpf_list_node_kern *n = (void *)node;
+	struct bpf_list_node_kern *new = (void *)node;
 	struct btf_struct_meta *meta = meta__ign;
+	struct list_head *h = (void *)head;
 
-	return __bpf_list_add(n, head, true, meta ? meta->record : NULL, off);
+	return __bpf_list_add(new, head, &h->prev, meta ? meta->record : NULL, off);
 }
 
 static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
#10 lore raw

PATCH v8 5/8 bpf: Add bpf_list_add_impl to insert node after a given list node

In reply to 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. 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  | 14 ++++++++++++++
 kernel/bpf/verifier.c | 13 +++++++++++--
 2 files changed, 25 insertions(+), 2 deletions(-)
kernel/bpf/helpers.c +14 -0
index a9665f97b3bc..dc4f8b4eec01 100644
@@ -2438,6 +2438,19 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 	return __bpf_list_add(new, head, &h->prev, meta ? meta->record : NULL, off);
 }
 
+__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 *prev_ptr = &kp->list_head;
+
+	return __bpf_list_add(kn, head, &prev_ptr,
+			      meta ? meta->record : NULL, off);
+}
+
 static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
 					    struct list_head *n)
 {
@@ -4574,6 +4587,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 -2
index e928ad4290c7..98ddb370feb5 100644
@@ -12506,6 +12506,7 @@ enum special_kfunc_type {
 	KF_bpf_refcount_acquire_impl,
 	KF_bpf_list_push_front_impl,
 	KF_bpf_list_push_back_impl,
+	KF_bpf_list_add_impl,
 	KF_bpf_list_pop_front,
 	KF_bpf_list_pop_back,
 	KF_bpf_list_del,
@@ -12567,6 +12568,7 @@ BTF_ID(func, bpf_obj_drop_impl)
 BTF_ID(func, bpf_refcount_acquire_impl)
 BTF_ID(func, bpf_list_push_front_impl)
 BTF_ID(func, bpf_list_push_back_impl)
+BTF_ID(func, bpf_list_add_impl)
 BTF_ID(func, bpf_list_pop_front)
 BTF_ID(func, bpf_list_pop_back)
 BTF_ID(func, bpf_list_del)
@@ -12644,6 +12646,7 @@ 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_add_impl,
 	KF_bpf_list_pop_front,
 	KF_bpf_list_pop_back,
 	KF_bpf_list_del,
@@ -12655,6 +12658,7 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 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_add_impl,
 	KF_bpf_list_del,
 };
 
@@ -14345,6 +14349,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].var_off.value;
@@ -23357,13 +23362,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)
#11 lore raw

Re: [PATCH bpf-next v8 5/8] bpf: Add bpf_list_add_impl to insert node after a given list node

Quoted 29 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. 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  | 14 ++++++++++++++
 kernel/bpf/verifier.c | 13 +++++++++++--
 2 files changed, 25 insertions(+), 2 deletions(-)
kernel/bpf/helpers.c +0 -0
index a9665f97b3bc..dc4f8b4eec01 100644
@@ -2438,6 +2438,19 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 	return __bpf_list_add(new, head, &h->prev, meta ? meta->record : NULL, off);
 }

kernel/bpf/helpers.c __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head, · line 2449

Quoted 10 lines
kernel/bpf/helpers.c +9 -0
 
+__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 *prev_ptr = &kp->list_head;
+

You need to add a version of the check you added on patch 4 here to make sure the node owners are sane. The check was a WARN_ON because before the callers to __bpf_list_add didn't take a separate head and node argument from the program, so any inconsistency was a bug. With this helper this is no longer the case.

Also check the comment in Sashiko. Can you either add a test that ensures the use-after-free is described is not the case, or otherwise change the error handling/verifier behavior to avoid it? I suspect it's an actual issue.

In general your code is conflating two different issues in its error
handling: 1) A node is being inserted into two different lists at the same time, 2) the user has made a programming error and is supplying an invalid head/prev combination. These are two very different issues, and 2) is only possible with this new kfunc. Can you add error handling for it directly in bpf_list_add_impl, and assume the head/prev combination is alsways valid in __bpf_list_add?

Quoted 52 lines
kernel/bpf/helpers.c +5 -0
+	return __bpf_list_add(kn, head, &prev_ptr,
+			      meta ? meta->record : NULL, off);
+}
+
 static struct bpf_list_node *__bpf_list_del(struct bpf_list_head *head,
 					    struct list_head *n)
 {
@@ -4574,6 +4587,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 +4 -0
index e928ad4290c7..98ddb370feb5 100644
@@ -12506,6 +12506,7 @@ enum special_kfunc_type {
 	KF_bpf_refcount_acquire_impl,
 	KF_bpf_list_push_front_impl,
 	KF_bpf_list_push_back_impl,
+	KF_bpf_list_add_impl,
 	KF_bpf_list_pop_front,
 	KF_bpf_list_pop_back,
 	KF_bpf_list_del,
@@ -12567,6 +12568,7 @@ BTF_ID(func, bpf_obj_drop_impl)
 BTF_ID(func, bpf_refcount_acquire_impl)
 BTF_ID(func, bpf_list_push_front_impl)
 BTF_ID(func, bpf_list_push_back_impl)
+BTF_ID(func, bpf_list_add_impl)
 BTF_ID(func, bpf_list_pop_front)
 BTF_ID(func, bpf_list_pop_back)
 BTF_ID(func, bpf_list_del)
@@ -12644,6 +12646,7 @@ 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_add_impl,
 	KF_bpf_list_pop_front,
 	KF_bpf_list_pop_back,
 	KF_bpf_list_del,
@@ -12655,6 +12658,7 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 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_add_impl,
 	KF_bpf_list_del,
 };
 

kernel/bpf/verifier.c static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, · line 14353

Quoted 5 lines
kernel/bpf/verifier.c +1 -0
@@ -14345,6 +14349,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]) {

Can you use the macros you defined on patch one to replace this list and the one below?

Quoted 22 lines
kernel/bpf/verifier.c +6 -2
 		release_ref_obj_id = regs[BPF_REG_2].ref_obj_id;
 		insn_aux->insert_off = regs[BPF_REG_2].var_off.value;
@@ -23357,13 +23362,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;
 		}
#12 lore raw

PATCH v8 6/8 bpf: allow bpf_list_front/back result as the prev argument of bpf_list_add_impl

In reply to Chengkaitao

From: Kaitao Cheng <[email protected]>

KF_ARG_PTR_TO_LIST_NODE normally requires an owning reference (PTR_TO_BTF_ID | MEM_ALLOC and ref_obj_id). For bpf_list_add_impl's third argument (prev), allow a non-owning reference with ref_obj_id==0 so that the result of bpf_list_front() or bpf_list_back() can be passed as the insertion point. When prev is such a non-owning ref, skip the MEM_ALLOC/ref_obj_id checks and jump to the shared list-node processing. Owning refs (e.g. from pop + refcount_acquire) still pass the existing checks and reach the same label.

---
 kernel/bpf/verifier.c | 9 +++++++++
 1 file changed, 9 insertions(+)
kernel/bpf/verifier.c +9 -0
index 98ddb370feb5..0a6f2e6a5d28 100644
@@ -13737,6 +13737,14 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 				return ret;
 			break;
 		case KF_ARG_PTR_TO_LIST_NODE:
+			if (meta->func_id == special_kfunc_list[KF_bpf_list_add_impl]
+			    && i == 2 && type_is_non_owning_ref(reg->type)
+			    && !reg->ref_obj_id) {
+				/* Allow bpf_list_front/back return value as
+				 * list_add_impl's third arg (R3).
+				 */
+				goto check_ok;
+			}
 			if (reg->type != (PTR_TO_BTF_ID | MEM_ALLOC)) {
 				verbose(env, "arg#%d expected pointer to allocated object\n", i);
 				return -EINVAL;
@@ -13745,6 +13753,7 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 				verbose(env, "allocated object must be referenced\n");
 				return -EINVAL;
 			}
+check_ok:
 			ret = process_kf_arg_ptr_to_list_node(env, reg, regno, meta);
 			if (ret < 0)
 				return ret;
Signature · 1 line
2.50.1 (Apple Git-155)
#13 lore raw

Re: [PATCH bpf-next v8 6/8] bpf: allow bpf_list_front/back result as the prev argument of bpf_list_add_impl

Quoted 23 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

KF_ARG_PTR_TO_LIST_NODE normally requires an owning reference (PTR_TO_BTF_ID | MEM_ALLOC and ref_obj_id). For bpf_list_add_impl's third argument (prev), allow a non-owning reference with ref_obj_id==0 so that the result of bpf_list_front() or bpf_list_back() can be passed as the insertion point. When prev is such a non-owning ref, skip the MEM_ALLOC/ref_obj_id checks and jump to the shared list-node processing. Owning refs (e.g. from pop + refcount_acquire) still pass the existing checks and reach the same label.

---
 kernel/bpf/verifier.c | 9 +++++++++
 1 file changed, 9 insertions(+)
kernel/bpf/verifier.c +0 -0
index 98ddb370feb5..0a6f2e6a5d28 100644
@@ -13737,6 +13737,14 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
                                return ret;

kernel/bpf/verifier.c static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_ · line 13747

Quoted 10 lines
kernel/bpf/verifier.c +8 -0
                        break;
                case KF_ARG_PTR_TO_LIST_NODE:
+                       if (meta->func_id == special_kfunc_list[KF_bpf_list_add_impl]
+                           && i == 2 && type_is_non_owning_ref(reg->type)
+                           && !reg->ref_obj_id) {
+                               /* Allow bpf_list_front/back return value as
+                                * list_add_impl's third arg (R3).
+                                */
+                               goto check_ok;
+                       }

This is too specific and non scalable.
Another kfunc with similar requirements would need a separate 'if' with func_id == new_kfunc and potentially different 'i == N'. Let's introduce a new double underscore suffix for this or some other way.

pw-bot: cr

#14 lore raw

PATCH v8 7/8 bpf: add bpf_list_is_first/last/empty kfuncs

In reply to 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.

Currently, without these kfuncs, to implement the above functionality it is 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  | 38 ++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c | 11 +++++++++++
 2 files changed, 49 insertions(+)
kernel/bpf/helpers.c +38 -0
index dc4f8b4eec01..da70dcff4ba8 100644
@@ -2518,6 +2518,41 @@ __bpf_kfunc struct bpf_list_node *bpf_list_back(struct bpf_list_head *head)
 	return (struct bpf_list_node *)h->prev;
 }
 
+__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 *kn = (struct bpf_list_node_kern *)node;
+
+	if (READ_ONCE(kn->owner) != head)
+		return false;
+
+	return list_is_first(&kn->list_head, h);
+}
+
+__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 *kn = (struct bpf_list_node_kern *)node;
+
+	if (READ_ONCE(kn->owner) != head)
+		return false;
+
+	return list_is_last(&kn->list_head, h);
+}
+
+__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)
 {
@@ -4588,6 +4623,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 +11 -0
index 0a6f2e6a5d28..c2cc622bb3a1 100644
@@ -12512,6 +12512,9 @@ enum special_kfunc_type {
 	KF_bpf_list_del,
 	KF_bpf_list_front,
 	KF_bpf_list_back,
+	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,
@@ -12574,6 +12577,9 @@ 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_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)
@@ -12652,6 +12658,9 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 	KF_bpf_list_del,
 	KF_bpf_list_front,
 	KF_bpf_list_back,
+	KF_bpf_list_is_first,
+	KF_bpf_list_is_last,
+	KF_bpf_list_empty,
 };
 
 /* Kfuncs that take a list node argument (bpf_list_node *). */
@@ -12660,6 +12669,8 @@ static const enum special_kfunc_type bpf_list_node_api_kfuncs[] = {
 	KF_bpf_list_push_back_impl,
 	KF_bpf_list_add_impl,
 	KF_bpf_list_del,
+	KF_bpf_list_is_first,
+	KF_bpf_list_is_last,
 };
 
 /* Kfuncs that take an rbtree node argument (bpf_rb_node *). */
Signature · 1 line
2.50.1 (Apple Git-155)
#15 lore raw

Re: [PATCH bpf-next v8 7/8] bpf: add bpf_list_is_first/last/empty kfuncs

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

Currently, without these kfuncs, to implement the above functionality it is 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.

Quoted 3 lines

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.

Do you need to expand the exceptions you added in patch 5 for non-owning reference arguments to also hold for this? Checking the selftests, we don't have one where either bpf_list_is_last or bpf_list_is_first return true, can you add one?

Quoted 106 lines
---
 kernel/bpf/helpers.c  | 38 ++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c | 11 +++++++++++
 2 files changed, 49 insertions(+)
kernel/bpf/helpers.c +38 -0
index dc4f8b4eec01..da70dcff4ba8 100644
@@ -2518,6 +2518,41 @@ __bpf_kfunc struct bpf_list_node *bpf_list_back(struct bpf_list_head *head)
 	return (struct bpf_list_node *)h->prev;
 }
 
+__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 *kn = (struct bpf_list_node_kern *)node;
+
+	if (READ_ONCE(kn->owner) != head)
+		return false;
+
+	return list_is_first(&kn->list_head, h);
+}
+
+__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 *kn = (struct bpf_list_node_kern *)node;
+
+	if (READ_ONCE(kn->owner) != head)
+		return false;
+
+	return list_is_last(&kn->list_head, h);
+}
+
+__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)
 {
@@ -4588,6 +4623,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 +11 -0
index 0a6f2e6a5d28..c2cc622bb3a1 100644
@@ -12512,6 +12512,9 @@ enum special_kfunc_type {
 	KF_bpf_list_del,
 	KF_bpf_list_front,
 	KF_bpf_list_back,
+	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,
@@ -12574,6 +12577,9 @@ 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_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)
@@ -12652,6 +12658,9 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 	KF_bpf_list_del,
 	KF_bpf_list_front,
 	KF_bpf_list_back,
+	KF_bpf_list_is_first,
+	KF_bpf_list_is_last,
+	KF_bpf_list_empty,
 };
 
 /* Kfuncs that take a list node argument (bpf_list_node *). */
@@ -12660,6 +12669,8 @@ static const enum special_kfunc_type bpf_list_node_api_kfuncs[] = {
 	KF_bpf_list_push_back_impl,
 	KF_bpf_list_add_impl,
 	KF_bpf_list_del,
+	KF_bpf_list_is_first,
+	KF_bpf_list_is_last,
 };
 
 /* Kfuncs that take an rbtree node argument (bpf_rb_node *). */
reviewer Reviewed-by
#16 lore raw

Re: [PATCH bpf-next v8 7/8] bpf: add bpf_list_is_first/last/empty kfuncs

Quoted 14 lines · Emil Tsalapatis
Quoted 13 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.

Currently, without these kfuncs, to implement the above functionality it is 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.

Quoted 9 lines
Quoted 3 lines

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.

Do you need to expand the exceptions you added in patch 5 for non-owning reference arguments to also hold for this? Checking the selftests, we don't have one where either bpf_list_is_last or bpf_list_is_first return true, can you add one?

I misread the selftests, my bad. The tests pass fine, and we just have to keep an owning reference of the nodes around to pass to the helpers.

Quoted 106 lines
Quoted 106 lines
---
 kernel/bpf/helpers.c  | 38 ++++++++++++++++++++++++++++++++++++++
 kernel/bpf/verifier.c | 11 +++++++++++
 2 files changed, 49 insertions(+)
kernel/bpf/helpers.c +38 -0
index dc4f8b4eec01..da70dcff4ba8 100644
@@ -2518,6 +2518,41 @@ __bpf_kfunc struct bpf_list_node *bpf_list_back(struct bpf_list_head *head)
 	return (struct bpf_list_node *)h->prev;
 }
 
+__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 *kn = (struct bpf_list_node_kern *)node;
+
+	if (READ_ONCE(kn->owner) != head)
+		return false;
+
+	return list_is_first(&kn->list_head, h);
+}
+
+__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 *kn = (struct bpf_list_node_kern *)node;
+
+	if (READ_ONCE(kn->owner) != head)
+		return false;
+
+	return list_is_last(&kn->list_head, h);
+}
+
+__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)
 {
@@ -4588,6 +4623,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 +11 -0
index 0a6f2e6a5d28..c2cc622bb3a1 100644
@@ -12512,6 +12512,9 @@ enum special_kfunc_type {
 	KF_bpf_list_del,
 	KF_bpf_list_front,
 	KF_bpf_list_back,
+	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,
@@ -12574,6 +12577,9 @@ 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_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)
@@ -12652,6 +12658,9 @@ static const enum special_kfunc_type bpf_list_api_kfuncs[] = {
 	KF_bpf_list_del,
 	KF_bpf_list_front,
 	KF_bpf_list_back,
+	KF_bpf_list_is_first,
+	KF_bpf_list_is_last,
+	KF_bpf_list_empty,
 };
 
 /* Kfuncs that take a list node argument (bpf_list_node *). */
@@ -12660,6 +12669,8 @@ static const enum special_kfunc_type bpf_list_node_api_kfuncs[] = {
 	KF_bpf_list_push_back_impl,
 	KF_bpf_list_add_impl,
 	KF_bpf_list_del,
+	KF_bpf_list_is_first,
+	KF_bpf_list_is_last,
 };
 
 /* Kfuncs that take an rbtree node argument (bpf_rb_node *). */
#17 lore raw

PATCH v8 8/8 selftests/bpf: Add test cases for bpf_list_del/add/is_first/is_last/empty

In reply to Chengkaitao

From: Kaitao Cheng <[email protected]>

Extend refcounted_kptr with tests for bpf_list_add (including prev from bpf_list_front and bpf_refcount_acquire), bpf_list_del (including node from bpf_rbtree_remove and bpf_refcount_acquire), bpf_list_empty, bpf_list_is_first/last, and push_back on uninit head.

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  |  16 +
 .../selftests/bpf/progs/refcounted_kptr.c     | 311 ++++++++++++++++++
 2 files changed, 327 insertions(+)
tools/testing/selftests/bpf/bpf_experimental.h +16 -0
index 44466acf8083..5821f0000e1f 100644
@@ -85,6 +85,22 @@ extern int bpf_list_push_back_impl(struct bpf_list_head *head,
 /* Convenience macro to wrap over bpf_list_push_back_impl */
 #define bpf_list_push_back(head, node) bpf_list_push_back_impl(head, node, NULL, 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 the entry at the beginning of the BPF linked list.
  * Returns
tools/testing/selftests/bpf/progs/refcounted_kptr.c +311 -0

317 lines not on this page · raw message

Signature · 1 line
2.50.1 (Apple Git-155)
#18 lore raw
In reply to Chengkaitao
Quoted 14 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.

Five new kfuncs have been added:
bpf_list_del: remove a node from the list
bpf_list_add_impl: insert a node after a given list node
bpf_list_is_first: check if a node is the first in the list
bpf_list_is_last: check if a node is the last in the list
bpf_list_empty: check if the list is empty

Quoted 3 lines

refactor kfunc checks to table-driven approach, and add test cases for the aforementioned kfuncs.

By the way,
https://sashiko.dev/#/message/20260316112843.78657-1-pilgrimtao%40gmail.com
has some additional feedback apart from those of the list bot.

Quoted 72 lines

Changes in v8:
- Use [patch v7 5/5] as the start of the patch series
- Introduce double pointer prev_ptr in __bpf_list_del
- Extract refactored __bpf_list_del/add into separate patches
- Allow bpf_list_front/back result as the prev argument of bpf_list_add
- Split test cases

Changes in v7:
- Replace bpf_list_node_is_edge with bpf_list_is_first/is_last
- Reimplement __bpf_list_del and __bpf_list_add
- Simplify test cases

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 v7:
https://lore.kernel.org/all/[email protected]/

Link to v6:
https://lore.kernel.org/all/[email protected]/

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 (8):
bpf: refactor kfunc checks using table-driven approach in verifier
bpf: refactor __bpf_list_del to take list node pointer
bpf: Introduce the bpf_list_del kfunc.
bpf: refactor __bpf_list_add to take insertion point via **prev_ptr
bpf: Add bpf_list_add_impl to insert node after a given list node
bpf: allow bpf_list_front/back result as the prev argument of
bpf_list_add_impl
bpf: add bpf_list_is_first/last/empty kfuncs selftests/bpf: Add test cases for
bpf_list_del/add/is_first/is_last/empty

 kernel/bpf/helpers.c                          | 121 +++++--
 kernel/bpf/verifier.c                         | 116 +++++--
 .../testing/selftests/bpf/bpf_experimental.h  |  16 +
 .../selftests/bpf/progs/refcounted_kptr.c     | 311 ++++++++++++++++++
 4 files changed, 519 insertions(+), 45 deletions(-)