Skip to contentSkip to conversation

bpf: Extend the bpf_list family of APIs

PATCH In review Chengkaitao 5 participants 19 messages Mar 29 – Apr 23

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

v9 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 v9:
- Expand table-driven approach coverage
- Clear list node owner and unlink before drop
- Remove warnings caused by WARN_ON_ONCE()
- Introduce the __nonown_allowed suffix

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

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 (9):
bpf: refactor kfunc checks using table-driven approach in verifier
bpf: refactor __bpf_list_del to take list node pointer
bpf: clear list node owner and unlink before drop
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

 Documentation/bpf/kfuncs.rst                  |  20 +-
 kernel/bpf/helpers.c                          | 126 ++++++-
 kernel/bpf/verifier.c                         | 301 ++++++++++-------
 .../testing/selftests/bpf/bpf_experimental.h  |  16 +
 .../selftests/bpf/progs/refcounted_kptr.c     | 311 ++++++++++++++++++
 5 files changed, 636 insertions(+), 138 deletions(-)
Signature · 1 line
2.50.1 (Apple Git-155)
#1 lore raw

PATCH v9 1/9 bpf: refactor kfunc checks using table-driven approach in verifier

From: Kaitao Cheng <[email protected]>

Replace per-kfunc btf_id chains check 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 | 261 +++++++++++++++++++++++-------------------
 1 file changed, 144 insertions(+), 117 deletions(-)
kernel/bpf/verifier.c +144 -117
index 4fbacd2149cd..f2d9863bb290 100644
@@ -544,9 +544,6 @@ static bool is_async_callback_calling_kfunc(u32 btf_id);
 static bool is_callback_calling_kfunc(u32 btf_id);
 static bool is_bpf_throw_kfunc(struct bpf_insn *insn);
 
-static bool is_bpf_wq_set_callback_kfunc(u32 btf_id);
-static bool is_task_work_add_kfunc(u32 func_id);
-
 static bool is_sync_callback_calling_function(enum bpf_func_id func_id)
 {
 	return func_id == BPF_FUNC_for_each_map_elem ||
@@ -586,7 +583,7 @@ static bool is_async_cb_sleepable(struct bpf_verifier_env *env, struct bpf_insn
 
 	/* bpf_wq and bpf_task_work callbacks are always sleepable. */
 	if (bpf_pseudo_kfunc_call(insn) && insn->off == 0 &&
-	    (is_bpf_wq_set_callback_kfunc(insn->imm) || is_task_work_add_kfunc(insn->imm)))
+	    is_async_callback_calling_kfunc(insn->imm))
 		return true;
 
 	verifier_bug(env, "unhandled async callback in is_async_cb_sleepable");
@@ -11203,31 +11200,6 @@ static int set_task_work_schedule_callback_state(struct bpf_verifier_env *env,
 	return 0;
 }
 
-static bool is_rbtree_lock_required_kfunc(u32 btf_id);
-
-/* Are we currently verifying the callback for a rbtree helper that must
- * be called with lock held? If so, no need to complain about unreleased
- * lock
- */
-static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
-{
-	struct bpf_verifier_state *state = env->cur_state;
-	struct bpf_insn *insn = env->prog->insnsi;
-	struct bpf_func_state *callee;
-	int kfunc_btf_id;
-
-	if (!state->curframe)
-		return false;
-
-	callee = state->frame[state->curframe];
-
-	if (!callee->in_callback_fn)
-		return false;
-
-	kfunc_btf_id = insn[callee->callsite].imm;
-	return is_rbtree_lock_required_kfunc(kfunc_btf_id);
-}
-
 static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
 {
 	if (range.return_32bit)
@@ -12639,11 +12611,103 @@ BTF_ID(func, bpf_session_is_return)
 BTF_ID(func, bpf_stream_vprintk)
 BTF_ID(func, bpf_stream_print_stack)
 
-static bool is_task_work_add_kfunc(u32 func_id)
-{
-	return func_id == special_kfunc_list[KF_bpf_task_work_schedule_signal] ||
-	       func_id == special_kfunc_list[KF_bpf_task_work_schedule_resume];
-}
+/* Kfunc family related to list. */
+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,
+};
+
+/* Kfunc family related to rbtree. */
+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,
+};
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
+	KF_bpf_res_spin_lock,
+	KF_bpf_res_spin_unlock,
+	KF_bpf_res_spin_lock_irqsave,
+	KF_bpf_res_spin_unlock_irqrestore,
+};
+
+/* Kfunc family related to iter_num. */
+static const enum special_kfunc_type bpf_iter_num_api_kfuncs[] = {
+	KF_bpf_iter_num_new,
+	KF_bpf_iter_num_next,
+	KF_bpf_iter_num_destroy,
+};
+
+/* Kfunc family related to arena. */
+static const enum special_kfunc_type bpf_arena_api_kfuncs[] = {
+	KF_bpf_arena_alloc_pages,
+	KF_bpf_arena_free_pages,
+	KF_bpf_arena_reserve_pages,
+};
+
+/* Kfunc family related to stream. */
+static const enum special_kfunc_type bpf_stream_api_kfuncs[] = {
+	KF_bpf_stream_vprintk,
+	KF_bpf_stream_print_stack,
+};
+
+/* Kfuncs that must be called when inserting a node in list/rbtree. */
+static const enum special_kfunc_type bpf_collection_insert_kfuncs[] = {
+	KF_bpf_list_push_front_impl,
+	KF_bpf_list_push_back_impl,
+	KF_bpf_rbtree_add_impl,
+};
+
+/* KF_ACQUIRE kfuncs whose vmlinux BTF return type is void* */
+static const enum special_kfunc_type bpf_obj_acquire_ptr_kfuncs[] = {
+	KF_bpf_obj_new_impl,
+	KF_bpf_percpu_obj_new_impl,
+	KF_bpf_refcount_acquire_impl,
+};
+
+/* Kfunc family related to task_work. */
+static const enum special_kfunc_type bpf_task_work_api_kfuncs[] = {
+	KF_bpf_task_work_schedule_signal,
+	KF_bpf_task_work_schedule_resume,
+};
+
+/* __kfuncs must be an array identifier (not a pointer), for ARRAY_SIZE. */
+#define btf_id_in_kfunc_table(__btf_id, __kfuncs)				\
+	({									\
+		u32 ___id = (__btf_id);						\
+		unsigned int ___i;						\
+		bool ___found = false;						\
+										\
+		for (___i = 0; ___i < ARRAY_SIZE(__kfuncs); ___i++) {		\
+			if (___id == special_kfunc_list[(__kfuncs)[___i]]) {	\
+				___found = true;				\
+				break;						\
+			}							\
+		}								\
+		___found;							\
+	})
 
 static bool is_kfunc_ret_null(struct bpf_kfunc_call_arg_meta *meta)
 {
@@ -12680,6 +12744,29 @@ static bool is_kfunc_pkt_changing(struct bpf_kfunc_call_arg_meta *meta)
 	return meta->func_id == special_kfunc_list[KF_bpf_xdp_pull_data];
 }
 
+/* Are we currently verifying the callback for a rbtree helper that must
+ * be called with lock held? If so, no need to complain about unreleased
+ * lock
+ */
+static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
+{
+	struct bpf_verifier_state *state = env->cur_state;
+	struct bpf_insn *insn = env->prog->insnsi;
+	struct bpf_func_state *callee;
+	int kfunc_btf_id;
+
+	if (!state->curframe)
+		return false;
+
+	callee = state->frame[state->curframe];
+
+	if (!callee->in_callback_fn)
+		return false;
+
+	kfunc_btf_id = insn[callee->callsite].imm;
+	return btf_id_in_kfunc_table(kfunc_btf_id, bpf_rbtree_api_kfuncs);
+}
+
 static enum kfunc_ptr_arg_type
 get_kfunc_ptr_arg_type(struct bpf_verifier_env *env,
 		       struct bpf_kfunc_call_arg_meta *meta,
@@ -13036,65 +13123,20 @@ static int check_reg_allocation_locked(struct bpf_verifier_env *env, struct bpf_
 	return 0;
 }
 
-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];
-}
-
-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];
-}
-
-static bool is_bpf_iter_num_api_kfunc(u32 btf_id)
-{
-	return btf_id == special_kfunc_list[KF_bpf_iter_num_new] ||
-	       btf_id == special_kfunc_list[KF_bpf_iter_num_next] ||
-	       btf_id == special_kfunc_list[KF_bpf_iter_num_destroy];
-}
-
 static bool is_bpf_graph_api_kfunc(u32 btf_id)
 {
-	return is_bpf_list_api_kfunc(btf_id) || is_bpf_rbtree_api_kfunc(btf_id) ||
+	return btf_id_in_kfunc_table(btf_id, bpf_list_api_kfuncs) ||
+	       btf_id_in_kfunc_table(btf_id, bpf_rbtree_api_kfuncs) ||
 	       btf_id == special_kfunc_list[KF_bpf_refcount_acquire_impl];
 }
 
-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];
-}
-
-static bool is_bpf_arena_kfunc(u32 btf_id)
-{
-	return btf_id == special_kfunc_list[KF_bpf_arena_alloc_pages] ||
-	       btf_id == special_kfunc_list[KF_bpf_arena_free_pages] ||
-	       btf_id == special_kfunc_list[KF_bpf_arena_reserve_pages];
-}
-
-static bool is_bpf_stream_kfunc(u32 btf_id)
-{
-	return btf_id == special_kfunc_list[KF_bpf_stream_vprintk] ||
-	       btf_id == special_kfunc_list[KF_bpf_stream_print_stack];
-}
-
 static bool kfunc_spin_allowed(u32 btf_id)
 {
-	return is_bpf_graph_api_kfunc(btf_id) || is_bpf_iter_num_api_kfunc(btf_id) ||
-	       is_bpf_res_spin_lock_kfunc(btf_id) || is_bpf_arena_kfunc(btf_id) ||
-	       is_bpf_stream_kfunc(btf_id);
+	return is_bpf_graph_api_kfunc(btf_id) ||
+	       btf_id_in_kfunc_table(btf_id, bpf_iter_num_api_kfuncs) ||
+	       btf_id_in_kfunc_table(btf_id, bpf_res_spin_lock_api_kfuncs) ||
+	       btf_id_in_kfunc_table(btf_id, bpf_arena_api_kfuncs) ||
+	       btf_id_in_kfunc_table(btf_id, bpf_stream_api_kfuncs);
 }
 
 static bool is_sync_callback_calling_kfunc(u32 btf_id)
@@ -13102,12 +13144,6 @@ static bool is_sync_callback_calling_kfunc(u32 btf_id)
 	return btf_id == special_kfunc_list[KF_bpf_rbtree_add_impl];
 }
 
-static bool is_async_callback_calling_kfunc(u32 btf_id)
-{
-	return is_bpf_wq_set_callback_kfunc(btf_id) ||
-	       is_task_work_add_kfunc(btf_id);
-}
-
 static bool is_bpf_throw_kfunc(struct bpf_insn *insn)
 {
 	return bpf_pseudo_kfunc_call(insn) && insn->off == 0 &&
@@ -13119,15 +13155,16 @@ static bool is_bpf_wq_set_callback_kfunc(u32 btf_id)
 	return btf_id == special_kfunc_list[KF_bpf_wq_set_callback];
 }
 
-static bool is_callback_calling_kfunc(u32 btf_id)
+static bool is_async_callback_calling_kfunc(u32 btf_id)
 {
-	return is_sync_callback_calling_kfunc(btf_id) ||
-	       is_async_callback_calling_kfunc(btf_id);
+	return is_bpf_wq_set_callback_kfunc(btf_id) ||
+	       btf_id_in_kfunc_table(btf_id, bpf_task_work_api_kfuncs);
 }
 
-static bool is_rbtree_lock_required_kfunc(u32 btf_id)
+static bool is_callback_calling_kfunc(u32 btf_id)
 {
-	return is_bpf_rbtree_api_kfunc(btf_id);
+	return is_sync_callback_calling_kfunc(btf_id) ||
+	       is_async_callback_calling_kfunc(btf_id);
 }
 
 static bool check_kfunc_is_graph_root_api(struct bpf_verifier_env *env,
@@ -13138,10 +13175,10 @@ static bool check_kfunc_is_graph_root_api(struct bpf_verifier_env *env,
 
 	switch (head_field_type) {
 	case BPF_LIST_HEAD:
-		ret = is_bpf_list_api_kfunc(kfunc_btf_id);
+		ret = btf_id_in_kfunc_table(kfunc_btf_id, bpf_list_api_kfuncs);
 		break;
 	case BPF_RB_ROOT:
-		ret = is_bpf_rbtree_api_kfunc(kfunc_btf_id);
+		ret = btf_id_in_kfunc_table(kfunc_btf_id, bpf_rbtree_api_kfuncs);
 		break;
 	default:
 		verbose(env, "verifier internal error: unexpected graph root argument type %s\n",
@@ -13163,14 +13200,10 @@ 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);
 		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);
 		break;
 	default:
 		verbose(env, "verifier internal error: unexpected graph node argument type %s\n",
@@ -13878,7 +13911,7 @@ static int check_kfunc_args(struct bpf_verifier_env *env, struct bpf_kfunc_call_
 				return -EINVAL;
 			}
 
-			if (!is_bpf_res_spin_lock_kfunc(meta->func_id))
+			if (!btf_id_in_kfunc_table(meta->func_id, bpf_res_spin_lock_api_kfuncs))
 				return -EFAULT;
 			if (meta->func_id == special_kfunc_list[KF_bpf_res_spin_lock] ||
 			    meta->func_id == special_kfunc_list[KF_bpf_res_spin_lock_irqsave])
@@ -14215,7 +14248,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		}
 	}
 
-	if (is_task_work_add_kfunc(meta.func_id)) {
+	if (btf_id_in_kfunc_table(meta.func_id, bpf_task_work_api_kfuncs)) {
 		err = push_callback_call(env, insn, insn_idx, meta.subprogno,
 					 set_task_work_schedule_callback_state);
 		if (err) {
@@ -14304,9 +14337,7 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 			return err;
 	}
 
-	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_rbtree_add_impl]) {
+	if (btf_id_in_kfunc_table(meta.func_id, bpf_collection_insert_kfuncs)) {
 		release_ref_obj_id = regs[BPF_REG_2].ref_obj_id;
 		insn_aux->insert_off = regs[BPF_REG_2].var_off.value;
 		insn_aux->kptr_struct_meta = btf_find_struct_meta(meta.arg_btf, meta.arg_btf_id);
@@ -14354,11 +14385,9 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 	t = btf_type_skip_modifiers(desc_btf, meta.func_proto->type, NULL);
 
 	if (is_kfunc_acquire(&meta) && !btf_type_is_struct_ptr(meta.btf, t)) {
-		/* Only exception is bpf_obj_new_impl */
+		/* Only exception is bpf_obj_acquire_ptr_kfuncs */
 		if (meta.btf != btf_vmlinux ||
-		    (meta.func_id != special_kfunc_list[KF_bpf_obj_new_impl] &&
-		     meta.func_id != special_kfunc_list[KF_bpf_percpu_obj_new_impl] &&
-		     meta.func_id != special_kfunc_list[KF_bpf_refcount_acquire_impl])) {
+		    !btf_id_in_kfunc_table(meta.func_id, bpf_obj_acquire_ptr_kfuncs)) {
 			verbose(env, "acquire kernel function does not return PTR_TO_BTF_ID\n");
 			return -EINVAL;
 		}
@@ -23316,9 +23345,7 @@ static int fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		insn_buf[1] = addr[1];
 		insn_buf[2] = *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_rbtree_add_impl]) {
+	} else if (btf_id_in_kfunc_table(desc->func_id, bpf_collection_insert_kfuncs)) {
 		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;
Signature · 1 line
2.50.1 (Apple Git-155)
#2 lore raw

Re: [PATCH bpf-next v9 1/9] 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 check with btf_id_in_kfunc_table() and static kfunc tables for easier maintenance.

Prepare for future extensions to the bpf_list API family.

---

I think old is_bpf_rbtree_api_kfunc(kfunc_btf_id) is more readable than new btf_id_in_kfunc_table(kfunc_btf_id, bpf_rbtree_api_kfuncs);
Not sure if this change should be bundled with this series, it looks quite orthogonal.

Quoted 33 lines
 kernel/bpf/verifier.c | 261 +++++++++++++++++++++++-------------------
 1 file changed, 144 insertions(+), 117 deletions(-)
kernel/bpf/verifier.c +1 -4
index 4fbacd2149cd..f2d9863bb290 100644
@@ -544,9 +544,6 @@ static bool is_async_callback_calling_kfunc(u32 btf_id);
 static bool is_callback_calling_kfunc(u32 btf_id);
 static bool is_bpf_throw_kfunc(struct bpf_insn *insn);
 
-static bool is_bpf_wq_set_callback_kfunc(u32 btf_id);
-static bool is_task_work_add_kfunc(u32 func_id);
-
 static bool is_sync_callback_calling_function(enum bpf_func_id func_id)
 {
 	return func_id == BPF_FUNC_for_each_map_elem ||
@@ -586,7 +583,7 @@ static bool is_async_cb_sleepable(struct bpf_verifier_env *env, struct bpf_insn
 
 	/* bpf_wq and bpf_task_work callbacks are always sleepable. */
 	if (bpf_pseudo_kfunc_call(insn) && insn->off == 0 &&
-	    (is_bpf_wq_set_callback_kfunc(insn->imm) || is_task_work_add_kfunc(insn->imm)))
+	    is_async_callback_calling_kfunc(insn->imm))
 		return true;
 
 	verifier_bug(env, "unhandled async callback in is_async_cb_sleepable");
@@ -11203,31 +11200,6 @@ static int set_task_work_schedule_callback_state(struct bpf_verifier_env *env,
 	return 0;
 }
 
...
Signature · 1 line
2.50.1 (Apple Git-155)
#3 lore raw

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

In reply to Chengkaitao
Quoted 108 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Replace per-kfunc btf_id chains check 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 | 261 +++++++++++++++++++++++-------------------
 1 file changed, 144 insertions(+), 117 deletions(-)
kernel/bpf/verifier.c +32 -34
index 4fbacd2149cd..f2d9863bb290 100644
@@ -544,9 +544,6 @@ static bool is_async_callback_calling_kfunc(u32 btf_id);
 static bool is_callback_calling_kfunc(u32 btf_id);
 static bool is_bpf_throw_kfunc(struct bpf_insn *insn);
 
-static bool is_bpf_wq_set_callback_kfunc(u32 btf_id);
-static bool is_task_work_add_kfunc(u32 func_id);
-
 static bool is_sync_callback_calling_function(enum bpf_func_id func_id)
 {
        return func_id == BPF_FUNC_for_each_map_elem ||
@@ -586,7 +583,7 @@ static bool is_async_cb_sleepable(struct bpf_verifier_env *env, struct bpf_insn
 
        /* bpf_wq and bpf_task_work callbacks are always sleepable. */
        if (bpf_pseudo_kfunc_call(insn) && insn->off == 0 &&
-           (is_bpf_wq_set_callback_kfunc(insn->imm) || is_task_work_add_kfunc(insn->imm)))
+           is_async_callback_calling_kfunc(insn->imm))
                return true;
 
        verifier_bug(env, "unhandled async callback in is_async_cb_sleepable");
@@ -11203,31 +11200,6 @@ static int set_task_work_schedule_callback_state(struct bpf_verifier_env *env,
        return 0;
 }
 
-static bool is_rbtree_lock_required_kfunc(u32 btf_id);
-
-/* Are we currently verifying the callback for a rbtree helper that must
- * be called with lock held? If so, no need to complain about unreleased
- * lock
- */
-static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
-{
-       struct bpf_verifier_state *state = env->cur_state;
-       struct bpf_insn *insn = env->prog->insnsi;
-       struct bpf_func_state *callee;
-       int kfunc_btf_id;
-
-       if (!state->curframe)
-               return false;
-
-       callee = state->frame[state->curframe];
-
-       if (!callee->in_callback_fn)
-               return false;
-
-       kfunc_btf_id = insn[callee->callsite].imm;
-       return is_rbtree_lock_required_kfunc(kfunc_btf_id);
-}
-
 static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
 {
        if (range.return_32bit)
@@ -12639,11 +12611,103 @@ BTF_ID(func, bpf_session_is_return)
 BTF_ID(func, bpf_stream_vprintk)
 BTF_ID(func, bpf_stream_print_stack)
 
-static bool is_task_work_add_kfunc(u32 func_id)
-{
-       return func_id == special_kfunc_list[KF_bpf_task_work_schedule_signal] ||
-              func_id == special_kfunc_list[KF_bpf_task_work_schedule_resume];
-}
+/* Kfunc family related to list. */
+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,
+};
+
+/* Kfunc family related to rbtree. */
+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,

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

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+       KF_bpf_rbtree_right,
+};
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
+       KF_bpf_res_spin_lock,
+       KF_bpf_res_spin_unlock,
+       KF_bpf_res_spin_lock_irqsave,
+       KF_bpf_res_spin_unlock_irqrestore,
+};

I think it's a step in the wrong direction.
I'd wait for Ihor's BTF_ID_NAMED cleanup.

Kaitao Cheng,

also please start your part of code reviews.
Your patches are not going to be landing if you don't code review.

https://lore.kernel.org/bpf/CAADnVQ+TKKptnNB25V3=bcdybh5G6c2DyW2sYtXvyRaVnPN8MA@mail.gmail.com/

pw-bot: cr

#4 lore raw

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

Quoted 115 lines · Alexei Starovoitov
Quoted 113 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Replace per-kfunc btf_id chains check 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 | 261 +++++++++++++++++++++++-------------------
 1 file changed, 144 insertions(+), 117 deletions(-)
kernel/bpf/verifier.c +37 -34
index 4fbacd2149cd..f2d9863bb290 100644
@@ -544,9 +544,6 @@ static bool is_async_callback_calling_kfunc(u32 btf_id);
 static bool is_callback_calling_kfunc(u32 btf_id);
 static bool is_bpf_throw_kfunc(struct bpf_insn *insn);
 
-static bool is_bpf_wq_set_callback_kfunc(u32 btf_id);
-static bool is_task_work_add_kfunc(u32 func_id);
-
 static bool is_sync_callback_calling_function(enum bpf_func_id func_id)
 {
        return func_id == BPF_FUNC_for_each_map_elem ||
@@ -586,7 +583,7 @@ static bool is_async_cb_sleepable(struct bpf_verifier_env *env, struct bpf_insn
 
        /* bpf_wq and bpf_task_work callbacks are always sleepable. */
        if (bpf_pseudo_kfunc_call(insn) && insn->off == 0 &&
-           (is_bpf_wq_set_callback_kfunc(insn->imm) || is_task_work_add_kfunc(insn->imm)))
+           is_async_callback_calling_kfunc(insn->imm))
                return true;
 
        verifier_bug(env, "unhandled async callback in is_async_cb_sleepable");
@@ -11203,31 +11200,6 @@ static int set_task_work_schedule_callback_state(struct bpf_verifier_env *env,
        return 0;
 }
 
-static bool is_rbtree_lock_required_kfunc(u32 btf_id);
-
-/* Are we currently verifying the callback for a rbtree helper that must
- * be called with lock held? If so, no need to complain about unreleased
- * lock
- */
-static bool in_rbtree_lock_required_cb(struct bpf_verifier_env *env)
-{
-       struct bpf_verifier_state *state = env->cur_state;
-       struct bpf_insn *insn = env->prog->insnsi;
-       struct bpf_func_state *callee;
-       int kfunc_btf_id;
-
-       if (!state->curframe)
-               return false;
-
-       callee = state->frame[state->curframe];
-
-       if (!callee->in_callback_fn)
-               return false;
-
-       kfunc_btf_id = insn[callee->callsite].imm;
-       return is_rbtree_lock_required_kfunc(kfunc_btf_id);
-}
-
 static bool retval_range_within(struct bpf_retval_range range, const struct bpf_reg_state *reg)
 {
        if (range.return_32bit)
@@ -12639,11 +12611,103 @@ BTF_ID(func, bpf_session_is_return)
 BTF_ID(func, bpf_stream_vprintk)
 BTF_ID(func, bpf_stream_print_stack)
 
-static bool is_task_work_add_kfunc(u32 func_id)
-{
-       return func_id == special_kfunc_list[KF_bpf_task_work_schedule_signal] ||
-              func_id == special_kfunc_list[KF_bpf_task_work_schedule_resume];
-}
+/* Kfunc family related to list. */
+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,
+};
+
+/* Kfunc family related to rbtree. */
+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,
+};
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
Quoted 8 lines

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

Quoted 5 lines
kernel/bpf/verifier.c +5 -0
+       KF_bpf_res_spin_lock,
+       KF_bpf_res_spin_unlock,
+       KF_bpf_res_spin_lock_irqsave,
+       KF_bpf_res_spin_unlock_irqrestore,
+};

I think it's a step in the wrong direction.
I'd wait for Ihor's BTF_ID_NAMED cleanup.

After reading Ihor's messages on the list, if I understand correctly, our two approaches seem to target different problems. What Ihor's work appears to achieve is the ability to remove the entire enum special_kfunc_type. My goal, on the other hand, is to replace many scattered func_id == special_kfunc_list[...] comparisons with a table-driven approach.

That said, once Ihor's solution lands, my approach would no longer be applicable as-is. So I have been thinking about an alternative, please see the patch linked below for details:
https://lore.kernel.org/bpf/[email protected]/

Quoted 6 lines

Kaitao Cheng,

also please start your part of code reviews.
Your patches are not going to be landing if you don't code review.

https://lore.kernel.org/bpf/CAADnVQ+TKKptnNB25V3=bcdybh5G6c2DyW2sYtXvyRaVnPN8MA@mail.gmail.com/

I will do my best to carry this forward.

Signature · 2 lines
Yours,
Chengkaitao
reviewer
#5 lore raw

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

Quoted 20 lines · Chengkaitao
Quoted 5 lines · Alexei Starovoitov
Quoted 3 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Quoted 12 lines

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

Quoted 9 lines

[...]

kernel/bpf/verifier.c +8 -0
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
+       KF_bpf_res_spin_lock,
+       KF_bpf_res_spin_unlock,
+       KF_bpf_res_spin_lock_irqsave,
+       KF_bpf_res_spin_unlock_irqrestore,
+};

I think it's a step in the wrong direction.
I'd wait for Ihor's BTF_ID_NAMED cleanup.

Quoted 6 lines

After reading Ihor's messages on the list, if I understand correctly, our two approaches seem to target different problems. What Ihor's work appears to achieve is the ability to remove the entire enum special_kfunc_type. My goal, on the other hand, is to replace many scattered func_id == special_kfunc_list[...] comparisons with a table-driven approach.

Hi Kaitao,

I appreciate your efforts, however after a quick pass over the changes you propose (both here and in the new series) with respect to BTF_ID macros and special_kfuncs_list, I don't understand what problem you're trying to solve.

The inherent complexity is in the fact that the verifier must know when a particular BTF id identifies a specific kfunc, or whether it belongs to some pre-defined set of ids. This is why special_kfuncs_list and other BTF_ID_SET/LIST-s exist.

And so there is no way around defining those ids and sets *somewhere*, and so far BTF_ID_* macros did a fine job of that, all things considered.

AFAICT your changes simply move around the same definitions from functions with if statements to constant arrays with a runtime search on them (which is slower by the way). What is the benefit of that vs the current implementation? We still have to maintain those arrays in the same way we have to maintain the is_foo_kfunc helpers.

Your newer proposal [1] takes the same idea to the next level, by introducing an entire new BTF kind, new ELF sections and a bunch of macros that are no less complicated than existing. And all of that just moves the same arrays "upstream" to the .BTF_ids section. Again, I fail to see any benefits to that complexity. Having differentiation between LIST and SET, and having to mark START and END is not a problem that needs solving IMO.

The work I was discussing with Alexei [2] is targeted: get rid of constant enums that mirror existing kfunc symbols by making BTF_ID internals a bit smarter. And the benefit is clear and simple.

If you could explain what exact issue you're trying to address with your BTF_ID refactoring patches, maybe we can try converging on a reasonable approach to it.

Thanks!

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

Quoted 15 lines

That said, once Ihor's solution lands, my approach would no longer be applicable as-is. So I have been thinking about an alternative, please see the patch linked below for details:
https://lore.kernel.org/bpf/[email protected]/

Quoted 6 lines

Kaitao Cheng,

also please start your part of code reviews.
Your patches are not going to be landing if you don't code review.

https://lore.kernel.org/bpf/CAADnVQ+TKKptnNB25V3=bcdybh5G6c2DyW2sYtXvyRaVnPN8MA@mail.gmail.com/

I will do my best to carry this forward.

#6 lore raw

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

Quoted 53 lines · Ihor Solodrai
Quoted 20 lines · Chengkaitao
Quoted 5 lines · Alexei Starovoitov
Quoted 3 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Quoted 12 lines

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

Quoted 9 lines

[...]

kernel/bpf/verifier.c +8 -0
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
+       KF_bpf_res_spin_lock,
+       KF_bpf_res_spin_unlock,
+       KF_bpf_res_spin_lock_irqsave,
+       KF_bpf_res_spin_unlock_irqrestore,
+};

I think it's a step in the wrong direction.
I'd wait for Ihor's BTF_ID_NAMED cleanup.

Quoted 6 lines

After reading Ihor's messages on the list, if I understand correctly, our two approaches seem to target different problems. What Ihor's work appears to achieve is the ability to remove the entire enum special_kfunc_type. My goal, on the other hand, is to replace many scattered func_id == special_kfunc_list[...] comparisons with a table-driven approach.

Hi Kaitao,

I appreciate your efforts, however after a quick pass over the changes you propose (both here and in the new series) with respect to BTF_ID macros and special_kfuncs_list, I don't understand what problem you're trying to solve.

The inherent complexity is in the fact that the verifier must know when a particular BTF id identifies a specific kfunc, or whether it belongs to some pre-defined set of ids. This is why special_kfuncs_list and other BTF_ID_SET/LIST-s exist.

And so there is no way around defining those ids and sets *somewhere*, and so far BTF_ID_* macros did a fine job of that, all things considered.

AFAICT your changes simply move around the same definitions from functions with if statements to constant arrays with a runtime search on them (which is slower by the way). What is the benefit of that vs the current implementation? We still have to maintain those arrays in the same way we have to maintain the is_foo_kfunc helpers.

Quoted 7 lines

Your newer proposal [1] takes the same idea to the next level, by introducing an entire new BTF kind, new ELF sections and a bunch of macros that are no less complicated than existing. And all of that just moves the same arrays "upstream" to the .BTF_ids section. Again, I fail to see any benefits to that complexity. Having differentiation between LIST and SET, and having to mark START and END is not a problem that needs solving IMO.

Your analysis of the code implementation for the new proposal is correct. Let me elaborate on the purpose behind my approach.

****** Purpose 1 ******

As described in this patch:
https://lore.kernel.org/bpf/[email protected]/

If we want to add a new kfunc, bpf_list_add_impl, we would today have to add "btf_id == special_kfunc_list[KF_bpf_list_back]" (or similar) five times in verifier.c. Under the newer proposal, that is no longer
necessary: defining the kfunc and its verifier metadata in one place is enough, for example:

__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)
{
/* kfunc implementation */
.......
}
BPF_VERIF_KFUNC_DEF(bpf_list_add_impl, list_api, graph_node_api, ... )

If BPF_VERIF_KFUNC_DEF is extended further, BTF_ID(func, bpf_list_add_impl) and BTF_ID_FLAGS(func, bpf_list_add_impl) might also become unnecessary, so the snippet above could eventually be close to all the code required to add a new kfunc.

****** Purpose 2 ******

The kernel no longer needs enum special_kfunc_type to list every KF_bpf_* entry. That information is folded into the .BTF_ids.##sfx section instead, so kfunc authors do not have to touch or think about special_kfunc_type.

****** Purpose 3 ******

As described in this patch:
https://lore.kernel.org/bpf/[email protected]/

In is_bpf_list_api_kfunc(u32 btf_id) there are on the order of eleven "btf_id == special_kfunc_list[*]" comparisons. As more kfuncs are added, every is_bpf_* helper will only grow longer and the verifier will get more repetitive. With the new design, those is_bpf_* helpers can be removed entirely, including the awkward scattered "btf_id == *" checks.

****** Purpose 4 ******

It pushes us to untangle messy verifier safety cases and make them modular, so they can be expressed as parameters to BPF_VERIF_KFUNC_DEF

Quoted 28 lines

The work I was discussing with Alexei [2] is targeted: get rid of constant enums that mirror existing kfunc symbols by making BTF_ID internals a bit smarter. And the benefit is clear and simple.

If you could explain what exact issue you're trying to address with your BTF_ID refactoring patches, maybe we can try converging on a reasonable approach to it.

Thanks!

[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/

Quoted 14 lines

That said, once Ihor's solution lands, my approach would no longer be applicable as-is. So I have been thinking about an alternative, please see the patch linked below for details:
https://lore.kernel.org/bpf/[email protected]/

Quoted 6 lines

Kaitao Cheng,

also please start your part of code reviews.
Your patches are not going to be landing if you don't code review.

https://lore.kernel.org/bpf/CAADnVQ+TKKptnNB25V3=bcdybh5G6c2DyW2sYtXvyRaVnPN8MA@mail.gmail.com/

I will do my best to carry this forward.

Signature · 2 lines
Yours,
Chengkaitao
reviewer
#7 lore raw

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

Quoted 62 lines · Chengkaitao
Quoted 50 lines · Ihor Solodrai
Quoted 20 lines · Chengkaitao
Quoted 5 lines · Alexei Starovoitov
Quoted 3 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Quoted 12 lines

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

Quoted 9 lines

[...]

kernel/bpf/verifier.c +8 -0
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
+       KF_bpf_res_spin_lock,
+       KF_bpf_res_spin_unlock,
+       KF_bpf_res_spin_lock_irqsave,
+       KF_bpf_res_spin_unlock_irqrestore,
+};

I think it's a step in the wrong direction.
I'd wait for Ihor's BTF_ID_NAMED cleanup.

Quoted 6 lines

After reading Ihor's messages on the list, if I understand correctly, our two approaches seem to target different problems. What Ihor's work appears to achieve is the ability to remove the entire enum special_kfunc_type. My goal, on the other hand, is to replace many scattered func_id == special_kfunc_list[...] comparisons with a table-driven approach.

Hi Kaitao,

I appreciate your efforts, however after a quick pass over the changes you propose (both here and in the new series) with respect to BTF_ID macros and special_kfuncs_list, I don't understand what problem you're trying to solve.

The inherent complexity is in the fact that the verifier must know when a particular BTF id identifies a specific kfunc, or whether it belongs to some pre-defined set of ids. This is why special_kfuncs_list and other BTF_ID_SET/LIST-s exist.

And so there is no way around defining those ids and sets *somewhere*, and so far BTF_ID_* macros did a fine job of that, all things considered.

AFAICT your changes simply move around the same definitions from functions with if statements to constant arrays with a runtime search on them (which is slower by the way). What is the benefit of that vs the current implementation? We still have to maintain those arrays in the same way we have to maintain the is_foo_kfunc helpers.

Quoted 7 lines

Your newer proposal [1] takes the same idea to the next level, by introducing an entire new BTF kind, new ELF sections and a bunch of macros that are no less complicated than existing. And all of that just moves the same arrays "upstream" to the .BTF_ids section. Again, I fail to see any benefits to that complexity. Having differentiation between LIST and SET, and having to mark START and END is not a problem that needs solving IMO.

Your analysis of the code implementation for the new proposal is correct. Let me elaborate on the purpose behind my approach.

Quoted 8 lines

****** Purpose 1 ******

As described in this patch:
https://lore.kernel.org/bpf/[email protected]/

If we want to add a new kfunc, bpf_list_add_impl, we would today have to add "btf_id == special_kfunc_list[KF_bpf_list_back]" (or similar) five times in verifier.c. ...

Kaitao,

I think the maintainability pain in the current verifier-side kfunc handling is clear, I don't think anyone would argue that it's not a problem. Your bpf_list_* work is a good demonstration of that. I agree it can be improved.

That said, I don't think extending .BTF_ids and/or BTF is the right way to solve it.

Quoted 14 lines

... Under the newer proposal, that is no longer
necessary: defining the kfunc and its verifier metadata in one place is enough, for example:

__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)
{
/* kfunc implementation */
.......
}
BPF_VERIF_KFUNC_DEF(bpf_list_add_impl, list_api, graph_node_api, ... )

Quoted 4 lines

If BPF_VERIF_KFUNC_DEF is extended further, BTF_ID(func, bpf_list_add_impl) and BTF_ID_FLAGS(func, bpf_list_add_impl) might also become unnecessary, so the snippet above could eventually be close to all the code required to add a new kfunc.

Defining a kfunc metadata in one place is a reasonable direction in principle, I agree.

Where I disagree is the mechanism. The complexity does not disappear, it just moves into .BTF_ids, new macros and resolve_btfids. The primary consumer of this metadata is the verifier, and I think it is better to keep that metadata in verifier-local C definitions instead of encoding it into .BTF_ids. Adding more indirection to this will only hurt maintainability IMO.

Quoted 6 lines

****** Purpose 2 ******

The kernel no longer needs enum special_kfunc_type to list every KF_bpf_* entry. That information is folded into the .BTF_ids.##sfx section instead, so kfunc authors do not have to touch or think about special_kfunc_type.

This is not an argument for the .BTF_ids extension. Removing special_kfunc_type mirroring is useful, but that will be addressed directly by the targeted cleanup already under discussion.

Quoted 11 lines

****** Purpose 3 ******

As described in this patch:
https://lore.kernel.org/bpf/[email protected]/

In is_bpf_list_api_kfunc(u32 btf_id) there are on the order of eleven "btf_id == special_kfunc_list[*]" comparisons. As more kfuncs are added, every is_bpf_* helper will only grow longer and the verifier will get more repetitive. With the new design, those is_bpf_* helpers can be removed entirely, including the awkward scattered "btf_id == *" checks.

The repetition is real. But removing is_bpf_*() helpers is not automatically a simplification if the same information is now encoded indirectly through section layout or local const arrays.

The same metadata is being maintained somewhere else, with more indirection than before. The complexity just moved around, and was not reduced.

The scattered "btf_id == *" will remain as long as it is necessary for the verifier to do certain checks or other work depending on the kfunc. Whether it's an array lookup, helper call or anything else in the condition, the condition must be there. Refactoring can't reduce this complexity, without changes in the verifier control flow.

Quoted 5 lines

****** Purpose 4 ******

It pushes us to untangle messy verifier safety cases and make them modular, so they can be expressed as parameters to BPF_VERIF_KFUNC_DEF

Again, I agree with the premise that verifier safety checks could become more modular where possible. But I think we should first separate two questions:

1. What kfunc properties should be declared centrally?
2. Where that declaration should live?

While I'd like to answer (1) with "all of them", I am not convinced the answer to (2) is .BTF_ids or BTF. A better C side declarative representation would give us most of the benefit here without making the BTF tooling more complex.

Here is how I think we should move forward:

1. Your bpf_list_* work is orthogonal to BTF_ID refactoring, so it's reasonable to first focus on landing it without changes to generic kfunc handling.

2. I plan to send patches (soon) for resolve_btfids, and then for BTF_ID macrology to eliminate the enum + array pattern. You are welcome to join the discussion and review / test the patches.

3. After all of the above lands, we can come back to the general BTF_ID / kfunc handling discussion. If you are interested in developing this further, I suggest to re-think the approach and come up with a "single kfunc metadata definition" that doesn't require significant changes in .BTF_ids section layout.

A slightly off-topic comment: the usage of _impl pattern for kfuncs should be considered deprecated. Any new kfuncs that work with verifier-supplied arguments should use KF_IMPLICIT_ARGS mechanism. So the bpf_list_add_impl in your seires should only have one version:
bpf_list_add marked with KF_IMPLICIT_ARGS flag.

Thanks,
Ihor

Quoted 3 lines
Quoted 2 lines

[...]

#8 lore raw

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

Quoted 38 lines · Ihor Solodrai
Quoted 21 lines · Chengkaitao
Quoted 8 lines · Ihor Solodrai
Quoted 7 lines · Chengkaitao
Quoted 5 lines · Alexei Starovoitov
Quoted 3 lines · Chengkaitao

From: Kaitao Cheng <[email protected]>

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

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

Quoted 9 lines

[...]

kernel/bpf/verifier.c +8 -0
+
+/* Kfunc family related to spin_lock. */
+static const enum special_kfunc_type bpf_res_spin_lock_api_kfuncs[] = {
+       KF_bpf_res_spin_lock,
+       KF_bpf_res_spin_unlock,
+       KF_bpf_res_spin_lock_irqsave,
+       KF_bpf_res_spin_unlock_irqrestore,
+};

****** Purpose 4 ******

Quoted 2 lines

It pushes us to untangle messy verifier safety cases and make them modular, so they can be expressed as parameters to BPF_VERIF_KFUNC_DEF

Again, I agree with the premise that verifier safety checks could become more modular where possible. But I think we should first separate two questions:

1. What kfunc properties should be declared centrally?
2. Where that declaration should live?

While I'd like to answer (1) with "all of them", I am not convinced the answer to (2) is .BTF_ids or BTF. A better C side declarative representation would give us most of the benefit here without making the BTF tooling more complex.

Quoted 5 lines

Here is how I think we should move forward:

1. Your bpf_list_* work is orthogonal to BTF_ID refactoring, so it's reasonable to first focus on landing it without changes to generic kfunc handling.

There is no consensus on whether the patch below should exist at all. [PATCH bpf-next v9 1/9] bpf: refactor kfunc checks using table-driven ...

Should we drop it entirely, or limit its scope to the is_bpf_* helpers that contain a large number of btf_id == special_kfunc_list[*]-style checks—for example by reverting to v8 or an earlier revision?
https://lore.kernel.org/all/[email protected]/

cc: Alexei Starovoitov, Emil Tsalapatis, Leon Hwang, Mykyta Yatsenko,
Kumar Kartikeya Dwivedi

Quoted 15 lines

2. I plan to send patches (soon) for resolve_btfids, and then for BTF_ID macrology to eliminate the enum + array pattern. You are welcome to join the discussion and review / test the patches.

3. After all of the above lands, we can come back to the general BTF_ID / kfunc handling discussion. If you are interested in developing this further, I suggest to re-think the approach and come up with a "single kfunc metadata definition" that doesn't require significant changes in .BTF_ids section layout.

A slightly off-topic comment: the usage of _impl pattern for kfuncs should be considered deprecated. Any new kfuncs that work with verifier-supplied arguments should use KF_IMPLICIT_ARGS mechanism. So the bpf_list_add_impl in your seires should only have one version:
bpf_list_add marked with KF_IMPLICIT_ARGS flag.

Signature · 2 lines
Yours,
Chengkaitao
reviewer
#9 lore raw

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

Quoted 19 lines · Chengkaitao
Quoted 18 lines · Ihor Solodrai
Quoted 3 lines · Chengkaitao

It pushes us to untangle messy verifier safety cases and make them modular, so they can be expressed as parameters to BPF_VERIF_KFUNC_DEF

Again, I agree with the premise that verifier safety checks could become more modular where possible. But I think we should first separate two questions:

1. What kfunc properties should be declared centrally?
2. Where that declaration should live?

While I'd like to answer (1) with "all of them", I am not convinced the answer to (2) is .BTF_ids or BTF. A better C side declarative representation would give us most of the benefit here without making the BTF tooling more complex.

Quoted 8 lines
Quoted 5 lines

Here is how I think we should move forward:

1. Your bpf_list_* work is orthogonal to BTF_ID refactoring, so it's reasonable to first focus on landing it without changes to generic kfunc handling.

There is no consensus on whether the patch below should exist at all. [PATCH bpf-next v9 1/9] bpf: refactor kfunc checks using table-driven ...

Hi Kaitao,

I think this refactoring patch should be dropped from the series. For now use the established pattern with special_kfunc_list, and don't introduce new _impl kfuncs.

Quoted 4 lines

Should we drop it entirely, or limit its scope to the is_bpf_* helpers that contain a large number of btf_id == special_kfunc_list[*]-style checks—for example by reverting to v8 or an earlier revision?

I don't think "reverting to v8" will work. Since you've sent v9 significant changes to the verifier.c have been landed, so you have some rebase work to do anyways. I suggest you minimize unnecessary refactoring in this series, and focus on bpf_list_* api extension.

pw-bot: cr

Thanks, and apologies for slow reply.

Quoted 21 lines

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

cc: Alexei Starovoitov, Emil Tsalapatis, Leon Hwang, Mykyta Yatsenko,
Kumar Kartikeya Dwivedi

Quoted 15 lines

2. I plan to send patches (soon) for resolve_btfids, and then for BTF_ID macrology to eliminate the enum + array pattern. You are welcome to join the discussion and review / test the patches.

3. After all of the above lands, we can come back to the general BTF_ID / kfunc handling discussion. If you are interested in developing this further, I suggest to re-think the approach and come up with a "single kfunc metadata definition" that doesn't require significant changes in .BTF_ids section layout.

A slightly off-topic comment: the usage of _impl pattern for kfuncs should be considered deprecated. Any new kfuncs that work with verifier-supplied arguments should use KF_IMPLICIT_ARGS mechanism. So the bpf_list_add_impl in your seires should only have one version:
bpf_list_add marked with KF_IMPLICIT_ARGS flag.

#10 lore raw

PATCH v9 2/9 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 | 21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)
kernel/bpf/helpers.c +14 -7
index cb6d242bd093..94fcd4ab39e9 100644
@@ -2426,22 +2426,25 @@ __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
 	 * called on its fields, so init here
 	 */
-	if (unlikely(!h->next))
+	if (unlikely(!h->next)) {
 		INIT_LIST_HEAD(h);
+		return NULL;
+	}
+
 	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))
+	if (unlikely(READ_ONCE(node->owner) != head))
 		return NULL;
 
 	list_del_init(n);
@@ -2451,12 +2454,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)
#11 lore raw

PATCH v9 3/9 bpf: clear list node owner and unlink before drop

In reply to Chengkaitao

From: Kaitao Cheng <[email protected]>

When draining a BPF list_head, clear each node's owner pointer while still holding the spinlock, so concurrent readers always see a consistent owner.

Delink each node with list_del_init() before calling __bpf_obj_drop_impl(), preventing subsequent users who hold a reference count to the node from acquiring an invalid next node.

---
 kernel/bpf/helpers.c | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)
kernel/bpf/helpers.c +6 -1
index 94fcd4ab39e9..8abb99712043 100644
@@ -2232,7 +2232,7 @@ EXPORT_SYMBOL_GPL(bpf_base_func_proto);
 void bpf_list_head_free(const struct btf_field *field, void *list_head,
 			struct bpf_spin_lock *spin_lock)
 {
-	struct list_head *head = list_head, *orig_head = list_head;
+	struct list_head *head = list_head, *orig_head = list_head, *pos;
 
 	BUILD_BUG_ON(sizeof(struct list_head) > sizeof(struct bpf_list_head));
 	BUILD_BUG_ON(__alignof__(struct list_head) > __alignof__(struct bpf_list_head));
@@ -2247,6 +2247,9 @@ void bpf_list_head_free(const struct btf_field *field, void *list_head,
 	if (!head->next || list_empty(head))
 		goto unlock;
 	head = head->next;
+	/* Clear owner under spinlock to ensure the owner is always valid */
+	for (pos = head; pos != orig_head; pos = pos->next)
+		WRITE_ONCE(container_of(pos, struct bpf_list_node_kern, list_head)->owner, NULL);
 unlock:
 	INIT_LIST_HEAD(orig_head);
 	__bpf_spin_unlock_irqrestore(spin_lock);
@@ -2255,7 +2258,9 @@ void bpf_list_head_free(const struct btf_field *field, void *list_head,
 		void *obj = head;
 
 		obj -= field->graph_root.node_offset;
+		pos = head;
 		head = head->next;
+		list_del_init(pos);
 		/* The contained type can also have resources, including a
 		 * bpf_list_head which needs to be freed.
 		 */
Signature · 1 line
2.50.1 (Apple Git-155)
#12 lore raw

Re: [PATCH bpf-next v9 3/9] bpf: clear list node owner and unlink before drop

Setting owner to NULL under lock A is good for concurrent readers (bpf_list_front/back), but could it open a window for concurrent writers?
Quoted 5 lines
kernel/bpf/helpers.c +0 -0
index 94fcd4ab39e9..8abb99712043 100644

kernel/bpf/helpers.c void bpf_list_head_free(const struct btf_field *field, void *list_head, · line 2255

Quoted 9 lines
kernel/bpf/helpers.c +3 -0
@@ -2247,6 +2247,9 @@ void bpf_list_head_free(const struct btf_field *field, void *list_head,
 	if (!head->next || list_empty(head))
 		goto unlock;
 	head = head->next;
+	/* Clear owner under spinlock to ensure the owner is always valid */
+	for (pos = head; pos != orig_head; pos = pos->next)
+		WRITE_ONCE(container_of(pos, struct bpf_list_node_kern, list_head)->owner, NULL);
 unlock:
 	INIT_LIST_HEAD(orig_head);
 	__bpf_spin_unlock_irqrestore(spin_lock);

Setting owner to NULL under lock A is good for concurrent readers (bpf_list_front/back), but could it open a window for concurrent writers?

After the lock is released, the drain loop below processes each node without holding any lock. Meanwhile, if a BPF program on another CPU holds a refcounted owning reference to one of these nodes (obtained earlier via bpf_refcount_acquire), it can attempt __bpf_list_add to a different list under a different lock B.

In __bpf_list_add():

    if (cmpxchg(&node->owner, NULL, BPF_PTR_POISON)) {
        ...
    }
    list_add(n, prev);

Before this patch, owner pointed to the old list head (non-NULL), so the cmpxchg would fail and the add would be rejected. With owner cleared to NULL, the cmpxchg succeeds, and list_add() modifies the node's next/prev to point into list B.

kernel/bpf/helpers.c void bpf_list_head_free(const struct btf_field *field, void *list_head, · line 2263

Quoted 7 lines
kernel/bpf/helpers.c +2 -0
@@ -2255,7 +2258,9 @@ void bpf_list_head_free(const struct btf_field *field, void *list_head,
 		void *obj = head;
 
 		obj -= field->graph_root.node_offset;
+		pos = head;
 		head = head->next;
+		list_del_init(pos);

If the concurrent list_add above has already modified head->next, does this drain loop then follow into list B's chain? The termination condition (head != orig_head) would never be satisfied by list B's nodes, and the loop would call __bpf_obj_drop_impl on list B's nodes without holding lock B.

Would it be safer to also call list_del_init() under the spinlock (e.g., splicing into a local list), so that nodes are fully detached from the chain before the lock is released? The existing comment notes that draining outside the lock avoids deadlocks from tracing programs, but the list_del_init operations themselves should be inexpensive compared to __bpf_obj_drop_impl.

This commit also appears to be a bug fix (addressing stale owner pointers after drain) but does not include a Fixes: tag. The concurrent reader issue was introduced when bpf_list_front/back was added.

Suggested tag:

    Fixes: fb5b480205ba ("bpf: Add bpf_list_{front,back} kfunc")

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

#13 lore raw

PATCH v9 4/9 bpf: Introduce the bpf_list_del kfunc.

In reply to Chengkaitao

From: Kaitao Cheng <[email protected]>

Allow users to remove any node from a linked list.

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.

---
 kernel/bpf/helpers.c  | 10 ++++++++++
 kernel/bpf/verifier.c |  4 ++++
 2 files changed, 14 insertions(+)
kernel/bpf/helpers.c +10 -0
index 8abb99712043..6dddb2377047 100644
@@ -2471,6 +2471,15 @@ __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;
+
+	/* verifier to guarantee n is a list node rather than the head */
+	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;
@@ -4557,6 +4566,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 f2d9863bb290..ae8d1f2e32de 100644
@@ -12480,6 +12480,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,
@@ -12540,6 +12541,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)
@@ -12617,6 +12619,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,
 };
@@ -12625,6 +12628,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)
#14 lore raw

PATCH v9 5/9 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 (node, 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 | 36 ++++++++++++++++++++++++++----------
 1 file changed, 26 insertions(+), 10 deletions(-)
kernel/bpf/helpers.c +26 -10
index 6dddb2377047..669e380746a6 100644
@@ -2386,9 +2386,11 @@ __bpf_kfunc void *bpf_refcount_acquire_impl(void *p__refcounted_kptr, void *meta
 
 static int __bpf_list_add(struct bpf_list_node_kern *node,
 			  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 *prev;
 
 	/* If list_head was 0-initialized by map, bpf_obj_init_field wasn't
 	 * called on its fields, so init here
@@ -2396,19 +2398,31 @@ static int __bpf_list_add(struct bpf_list_node_kern *node,
 	if (unlikely(!h->next))
 		INIT_LIST_HEAD(h);
 
+	prev = *prev_ptr;
+
+	/* When prev is not the list head, it must be a node in this list. */
+	if (prev != h) {
+		struct bpf_list_node_kern *prev_kn =
+			container_of(prev, struct bpf_list_node_kern, list_head);
+
+		if (unlikely(READ_ONCE(prev_kn->owner) != head))
+			goto fail;
+	}
+
 	/* node->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;
-	}
+	if (cmpxchg(&node->owner, NULL, BPF_PTR_POISON))
+		goto fail;
 
-	tail ? list_add_tail(n, h) : list_add(n, h);
+	list_add(n, prev);
 	WRITE_ONCE(node->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,
@@ -2417,8 +2431,9 @@ __bpf_kfunc int bpf_list_push_front_impl(struct bpf_list_head *head,
 {
 	struct bpf_list_node_kern *n = (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(n, head, &h, meta ? meta->record : NULL, off);
 }
 
 __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
@@ -2427,8 +2442,9 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 {
 	struct bpf_list_node_kern *n = (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(n, 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)
#15 lore raw

PATCH v9 6/9 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 | 12 ++++++++++--
 2 files changed, 24 insertions(+), 2 deletions(-)
kernel/bpf/helpers.c +14 -0
index 669e380746a6..68c83a009275 100644
@@ -2447,6 +2447,19 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 	return __bpf_list_add(n, 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 *n = (void *)new, *p = (void *)prev;
+	struct btf_struct_meta *meta = meta__ign;
+	struct list_head *prev_ptr = &p->list_head;
+
+	return __bpf_list_add(n, 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)
 {
@@ -4585,6 +4598,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 +10 -2
index ae8d1f2e32de..69dcf0105973 100644
@@ -12478,6 +12478,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,
@@ -12539,6 +12540,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)
@@ -12617,6 +12619,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,
@@ -12628,6 +12631,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,
 };
 
@@ -12681,6 +12685,7 @@ static const enum special_kfunc_type bpf_stream_api_kfuncs[] = {
 static const enum special_kfunc_type bpf_collection_insert_kfuncs[] = {
 	KF_bpf_list_push_front_impl,
 	KF_bpf_list_push_back_impl,
+	KF_bpf_list_add_impl,
 	KF_bpf_rbtree_add_impl,
 };
 
@@ -23354,8 +23359,11 @@ static int fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		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)
#16 lore raw

PATCH v9 7/9 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.

Add BTF suffix __nonown_allowed (is_kfunc_arg_nonown_allowed) and document it under kfuncs.rst.

---
 Documentation/bpf/kfuncs.rst | 20 +++++++++++++++++++-
 kernel/bpf/helpers.c         |  4 ++--
 kernel/bpf/verifier.c        | 13 +++++++++++++
 3 files changed, 34 insertions(+), 3 deletions(-)
Documentation/bpf/kfuncs.rst +19 -1
index 75e6c078e0e7..6760c547dd32 100644
@@ -207,7 +207,25 @@ Here, the buffer may be NULL. If the buffer is not NULL, it must be at least
 buffer__szk bytes in size. The kfunc is responsible for checking if the buffer
 is NULL before using it.
 
-2.3.5 __str Annotation
+2.3.5 __nonown_allowed Annotation
+----------------------------------
+
+This annotation is used to indicate that the parameter may be a non-owning reference.
+
+An example is given below::
+
+        __bpf_kfunc int bpf_list_add_impl(..., struct bpf_list_node
+                                          *prev__nonown_allowed, ...)
+        {
+                ...
+        }
+
+For the ``prev__nonown_allowed`` parameter (resolved as ``KF_ARG_PTR_TO_LIST_NODE``),
+suffix ``__nonown_allowed`` retains the usual owning-pointer rules and also
+permits a non-owning reference with no ref_obj_id (e.g. the return value of
+bpf_list_front() / bpf_list_back()).
+
+2.3.6 __str Annotation
 ----------------------------
 This annotation is used to indicate that the argument is a constant string.
 
kernel/bpf/helpers.c +2 -2
index 68c83a009275..743341aae5c0 100644
@@ -2449,10 +2449,10 @@ __bpf_kfunc int bpf_list_push_back_impl(struct bpf_list_head *head,
 
 __bpf_kfunc int bpf_list_add_impl(struct bpf_list_head *head,
 				  struct bpf_list_node *new,
-				  struct bpf_list_node *prev,
+				  struct bpf_list_node *prev__nonown_allowed,
 				  void *meta__ign, u64 off)
 {
-	struct bpf_list_node_kern *n = (void *)new, *p = (void *)prev;
+	struct bpf_list_node_kern *n = (void *)new, *p = (void *)prev__nonown_allowed;
 	struct btf_struct_meta *meta = meta__ign;
 	struct list_head *prev_ptr = &p->list_head;
 
kernel/bpf/verifier.c +13 -0
index 69dcf0105973..514a0aab93b8 100644
@@ -12265,6 +12265,11 @@ static bool is_kfunc_arg_nullable(const struct btf *btf, const struct btf_param
 	return btf_param_match_suffix(btf, arg, "__nullable");
 }
 
+static bool is_kfunc_arg_nonown_allowed(const struct btf *btf, const struct btf_param *arg)
+{
+	return btf_param_match_suffix(btf, arg, "__nonown_allowed");
+}
+
 static bool is_kfunc_arg_const_str(const struct btf *btf, const struct btf_param *arg)
 {
 	return btf_param_match_suffix(btf, arg, "__str");
@@ -13736,6 +13741,13 @@ 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 (is_kfunc_arg_nonown_allowed(btf, &args[i]) &&
+			    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;
@@ -13744,6 +13756,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)
#17 lore raw

PATCH v9 8/9 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 743341aae5c0..5f778da2e560 100644
@@ -2529,6 +2529,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)
 {
@@ -4599,6 +4634,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 514a0aab93b8..33fae482cd56 100644
@@ -12489,6 +12489,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,
@@ -12551,6 +12554,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)
@@ -12630,6 +12636,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 *). */
@@ -12638,6 +12647,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)
#18 lore raw

PATCH v9 9/9 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)