From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/verifier.c | 79 +++++++++++++++++++++++++++++++------------ 1 file changed, 57 insertions(+), 22 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 4fbacd2149cd..64c1f8343dfa 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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", -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/helpers.c | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index cb6d242bd093..e87b263c5fe6 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -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) -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/helpers.c | 11 +++++++++++ kernel/bpf/verifier.c | 4 ++++ 2 files changed, 15 insertions(+) diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index e87b263c5fe6..dac346eb1e2f 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -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) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 64c1f8343dfa..e928ad4290c7 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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 *). */ -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/helpers.c | 44 ++++++++++++++++++++++++++++---------------- 1 file changed, 28 insertions(+), 16 deletions(-) diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index dac346eb1e2f..a9665f97b3bc 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -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, -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/helpers.c | 14 ++++++++++++++ kernel/bpf/verifier.c | 13 +++++++++++-- 2 files changed, 25 insertions(+), 2 deletions(-) diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index a9665f97b3bc..dc4f8b4eec01 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -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) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index e928ad4290c7..98ddb370feb5 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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; } -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/verifier.c | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 98ddb370feb5..0a6f2e6a5d28 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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; -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- kernel/bpf/helpers.c | 38 ++++++++++++++++++++++++++++++++++++++ kernel/bpf/verifier.c | 11 +++++++++++ 2 files changed, 49 insertions(+) diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c index dc4f8b4eec01..da70dcff4ba8 100644 --- a/kernel/bpf/helpers.c +++ b/kernel/bpf/helpers.c @@ -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) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 0a6f2e6a5d28..c2cc622bb3a1 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -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 *). */ -- 2.50.1 (Apple Git-155) From: Kaitao Cheng 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. Signed-off-by: Kaitao Cheng --- .../testing/selftests/bpf/bpf_experimental.h | 16 + .../selftests/bpf/progs/refcounted_kptr.c | 311 ++++++++++++++++++ 2 files changed, 327 insertions(+) diff --git a/tools/testing/selftests/bpf/bpf_experimental.h b/tools/testing/selftests/bpf/bpf_experimental.h index 44466acf8083..5821f0000e1f 100644 --- a/tools/testing/selftests/bpf/bpf_experimental.h +++ b/tools/testing/selftests/bpf/bpf_experimental.h @@ -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 diff --git a/tools/testing/selftests/bpf/progs/refcounted_kptr.c b/tools/testing/selftests/bpf/progs/refcounted_kptr.c index c847398837cc..e5558994a76d 100644 --- a/tools/testing/selftests/bpf/progs/refcounted_kptr.c +++ b/tools/testing/selftests/bpf/progs/refcounted_kptr.c @@ -367,6 +367,317 @@ long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ INSERT_STASH_READ(true, "insert_stash_read: remove from tree"); INSERT_STASH_READ(false, "insert_stash_read: don't remove from tree"); +SEC("tc") +__description("list_empty_test: list empty before add, non-empty after add") +__success __retval(0) +int list_empty_test(void *ctx) +{ + struct node_data *node_new; + + bpf_spin_lock(&lock); + if (!bpf_list_empty(&head)) { + bpf_spin_unlock(&lock); + return -1; + } + bpf_spin_unlock(&lock); + + node_new = bpf_obj_new(typeof(*node_new)); + if (!node_new) + return -2; + + bpf_spin_lock(&lock); + bpf_list_push_front(&head, &node_new->l); + + if (bpf_list_empty(&head)) { + bpf_spin_unlock(&lock); + return -3; + } + bpf_spin_unlock(&lock); + return 0; +} + +static struct node_data *__add_in_list(struct bpf_list_head *head, + struct bpf_spin_lock *lock) +{ + struct node_data *node_new, *node_ref; + + node_new = bpf_obj_new(typeof(*node_new)); + if (!node_new) + return NULL; + + node_ref = bpf_refcount_acquire(node_new); + + bpf_spin_lock(lock); + bpf_list_push_front(head, &node_new->l); + bpf_spin_unlock(lock); + return node_ref; +} + +SEC("tc") +__description("list_is_edge_test: is_first on first node, is_last on last node") +__success __retval(0) +int list_is_edge_test(void *ctx) +{ + struct node_data *node_first, *node_last; + int err = 0; + + node_last = __add_in_list(&head, &lock); + if (!node_last) + return -1; + + node_first = __add_in_list(&head, &lock); + if (!node_first) { + bpf_obj_drop(node_last); + return -2; + } + + bpf_spin_lock(&lock); + if (!bpf_list_is_first(&head, &node_first->l)) { + err = -3; + goto fail; + } + if (!bpf_list_is_last(&head, &node_last->l)) + err = -4; + +fail: + bpf_spin_unlock(&lock); + bpf_obj_drop(node_first); + bpf_obj_drop(node_last); + return err; +} + +SEC("tc") +__description("list_del_test1: del returns removed nodes") +__success __retval(0) +int list_del_test1(void *ctx) +{ + struct node_data *node_first, *node_last; + struct bpf_list_node *bpf_node_first, *bpf_node_last; + int err = 0; + + node_last = __add_in_list(&head, &lock); + if (!node_last) + return -1; + + node_first = __add_in_list(&head, &lock); + if (!node_first) { + bpf_obj_drop(node_last); + return -2; + } + + bpf_spin_lock(&lock); + bpf_node_last = bpf_list_del(&head, &node_last->l); + bpf_node_first = bpf_list_del(&head, &node_first->l); + bpf_spin_unlock(&lock); + + if (bpf_node_first) + bpf_obj_drop(container_of(bpf_node_first, struct node_data, l)); + else + err = -3; + + if (bpf_node_last) + bpf_obj_drop(container_of(bpf_node_last, struct node_data, l)); + else + err = -4; + + bpf_obj_drop(node_first); + bpf_obj_drop(node_last); + return err; +} + +SEC("tc") +__description("list_del_test2: remove an arbitrary node from the list") +__success __retval(0) +int list_del_test2(void *ctx) +{ + struct bpf_rb_node *rb; + struct bpf_list_node *l; + struct node_data *n; + long err; + + err = __insert_in_tree_and_list(&head, &root, &lock); + if (err) + return err; + + bpf_spin_lock(&lock); + rb = bpf_rbtree_first(&root); + if (!rb) { + bpf_spin_unlock(&lock); + return -4; + } + + rb = bpf_rbtree_remove(&root, rb); + if (!rb) { + bpf_spin_unlock(&lock); + return -5; + } + + n = container_of(rb, struct node_data, r); + l = bpf_list_del(&head, &n->l); + bpf_spin_unlock(&lock); + bpf_obj_drop(n); + if (!l) + return -6; + + bpf_obj_drop(container_of(l, struct node_data, l)); + return 0; +} + +SEC("tc") +__description("list_add_test1: insert new node after prev") +__success __retval(0) +int list_add_test1(void *ctx) +{ + struct node_data *node_first; + struct node_data *new_node; + long err = 0; + + node_first = __add_in_list(&head, &lock); + if (!node_first) + return -1; + + new_node = bpf_obj_new(typeof(*new_node)); + if (!new_node) { + err = -2; + goto fail; + } + + bpf_spin_lock(&lock); + err = bpf_list_add(&head, &new_node->l, &node_first->l); + bpf_spin_unlock(&lock); + if (err) { + err = -3; + goto fail; + } + +fail: + bpf_obj_drop(node_first); + return 0; +} + +SEC("tc") +__description("list_add_test2: list_add accepts list_front return value as prev") +__success __retval(0) +int list_add_test2(void *ctx) +{ + struct node_data *new_node, *tmp; + struct bpf_list_node *bpf_node; + long err = 0; + + tmp = __add_in_list(&head, &lock); + if (!tmp) + return -1; + + new_node = bpf_obj_new(typeof(*new_node)); + if (!new_node) { + err = -2; + goto fail; + } + + bpf_spin_lock(&lock); + bpf_node = bpf_list_front(&head); + if (!bpf_node) { + bpf_spin_unlock(&lock); + bpf_obj_drop(new_node); + err = -3; + goto fail; + } + + err = bpf_list_add(&head, &new_node->l, bpf_node); + bpf_spin_unlock(&lock); + if (err) { + err = -4; + goto fail; + } + +fail: + bpf_obj_drop(tmp); + return err; +} + +struct uninit_head_val { + struct bpf_spin_lock lock; + struct bpf_list_head head __contains(node_data, l); +}; + +struct { + __uint(type, BPF_MAP_TYPE_ARRAY); + __type(key, int); + __type(value, struct uninit_head_val); + __uint(max_entries, 1); +} uninit_head_map SEC(".maps"); + +SEC("tc") +__description("list_push_back_uninit_head: push_back on 0-initialized list head") +__success __retval(0) +int list_push_back_uninit_head(void *ctx) +{ + struct uninit_head_val *st; + struct node_data *node; + int ret = -1, key = 0; + + st = bpf_map_lookup_elem(&uninit_head_map, &key); + if (!st) + return -1; + + node = bpf_obj_new(typeof(*node)); + if (!node) + return -1; + + bpf_spin_lock(&st->lock); + ret = bpf_list_push_back(&st->head, &node->l); + bpf_spin_unlock(&st->lock); + + return ret; +} + +SEC("?tc") +__failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") +long list_del_without_lock_fail(void *ctx) +{ + struct bpf_rb_node *rb; + struct bpf_list_node *l; + struct node_data *n; + + bpf_spin_lock(&lock); + rb = bpf_rbtree_first(&root); + bpf_spin_unlock(&lock); + if (!rb) + return -1; + + n = container_of(rb, struct node_data, r); + /* Error case: delete list node without holding lock */ + l = bpf_list_del(&head, &n->l); + if (!l) + return -2; + bpf_obj_drop(container_of(l, struct node_data, l)); + + return 0; +} + +SEC("?tc") +__failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") +long list_add_without_lock_fail(void *ctx) +{ + struct bpf_rb_node *rb; + struct bpf_list_node *l; + struct node_data *n; + + bpf_spin_lock(&lock); + rb = bpf_rbtree_first(&root); + l = bpf_list_front(&head); + bpf_spin_unlock(&lock); + if (!rb || !l) + return -1; + + n = container_of(l, struct node_data, l); + /* Error case: add list node without holding lock */ + if (bpf_list_add(&head, &n->l, l)) + return -2; + + return 0; +} + SEC("tc") __success long rbtree_refcounted_node_ref_escapes(void *ctx) -- 2.50.1 (Apple Git-155)