bpf/verifier: Expand the usage scenarios of bpf_kptr_xchg
Subsystems (4)
v6 cover bpf/verifier: Expand the usage scenarios of bpf_kptr_xchg
From: Kaitao Cheng <[email protected]>
When using bpf_kptr_xchg, we triggered the following error:
31: (85) call bpf_kptr_xchg#194
function calls are not allowed while holding a lockbpf_kptr_xchg can now be used in lock-held contexts, so we extended its usage scope in [patch 1/5].
When writing test cases using bpf_kptr_xchg and bpf_rbtree_*, the following approach must be followed:
bpf_spin_lock(&lock);
rb_n = bpf_rbtree_root(&root);
while (rb_n && can_loop) {
rb_n = bpf_rbtree_remove(&root, rb_n);
if (!rb_n)
goto fail;
tnode = container_of(rb_n, struct tree_node, node);
node_data = bpf_kptr_xchg(&tnode->node_data, NULL);
if (!node_data)
goto fail;
data = node_data->data;
/* use data to do something */
node_data = bpf_kptr_xchg(&tnode->node_data, node_data);
if (node_data)
goto fail;
bpf_rbtree_add(&root, rb_n, less);
if (lookup_key < tnode->key)
rb_n = bpf_rbtree_left(&root, rb_n);
else
rb_n = bpf_rbtree_right(&root, rb_n);
}
bpf_spin_unlock(&lock);The above illustrates a lock-remove-read-add-unlock workflow, which exhibits lower performance. To address this, we introduced support for a streamlined lock-read-unlock operation in [patch 2/5] and [patch 4/5].
Changes in v6:
- allow using bpf_kptr_xchg even if the MEM_RCU flag is set
- Add test case
Changes in v5:
- add lastname
Changes in v4:
- Fix the dead logic issue in the test case
Changes in v3:
- Fix compilation errors
Changes in v2:
- Allow using bpf_kptr_xchg even if the NON_OWN_REF flag is set
- Add test case
Link to v5:
https://lore.kernel.org/all/[email protected]/
Link to v4:
https://lore.kernel.org/all/[email protected]/
Link to V3:
https://lore.kernel.org/all/[email protected]/
Link to V2:
https://lore.kernel.org/all/[email protected]/
Link to V1:
https://lore.kernel.org/all/[email protected]/
Kaitao Cheng (5):
bpf/verifier: allow calling bpf_kptr_xchg while holding a lock bpf/verifier: allow using bpf_kptr_xchg even if the NON_OWN_REF flag
is set
selftests/bpf: Add supplementary tests for bpf_kptr_xchg bpf/verifier: allow using bpf_kptr_xchg even if the MEM_RCU flag is
set
selftests/bpf: Add test case for rbtree nodes that contain both
bpf_refcount and kptr fields.
kernel/bpf/verifier.c | 9 +- .../testing/selftests/bpf/prog_tests/rbtree.c | 6 + tools/testing/selftests/bpf/progs/bpf_misc.h | 4 + .../selftests/bpf/progs/rbtree_search_kptr.c | 290 ++++++++++++++++++ 4 files changed, 307 insertions(+), 2 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/rbtree_search_kptr.c
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v6 1/5 bpf/verifier: allow calling bpf_kptr_xchg while holding a lock
From: Kaitao Cheng <[email protected]>
For the following scenario:
struct tree_node {
struct bpf_rb_node node;
struct request __kptr *req;
u64 key;
};struct bpf_rb_root tree_root __contains(tree_node, node); struct bpf_spin_lock tree_lock;
If we need to traverse all nodes in the rbtree, retrieve the __kptr pointer from each node, and read kernel data from the referenced object, using bpf_kptr_xchg appears unavoidable.
This patch skips the BPF verifier checks for bpf_kptr_xchg when called while holding a lock.
--- kernel/bpf/verifier.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +2 -1
@@ -20387,7 +20387,8 @@ static int do_check_insn(struct bpf_verifier_env *env, bool *do_print_state)if (env->cur_state->active_locks) {if ((insn->src_reg ==BPF_REG_0 && - insn->imm != BPF_FUNC_spin_unlock) || + insn->imm != BPF_FUNC_spin_unlock && + insn->imm != BPF_FUNC_kptr_xchg) || (insn->src_reg ==BPF_PSEUDO_KFUNC_CALL && (insn->off !=0 || !kfunc_spin_allowed (insn->imm)))) { verbose(env,
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v6 2/5 bpf/verifier: allow using bpf_kptr_xchg even if the NON_OWN_REF flag is set
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
When traversing an rbtree using bpf_rbtree_left/right, if bpf_kptr_xchg is used to access the __kptr pointer contained in a node, it currently requires first removing the node with bpf_rbtree_remove and clearing the NON_OWN_REF flag, then re-adding the node to the original rbtree with bpf_rbtree_add after usage. This process significantly degrades rbtree traversal performance. The patch enables accessing __kptr pointers with the NON_OWN_REF flag set while holding the lock, eliminating the need for this remove-read-add sequence.
--- kernel/bpf/verifier.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +3 -1
@@ -9260,7 +9260,8 @@ static const struct bpf_reg_types timer_types = { .types = { PTR_TO_MAP_VALUE }static const struct bpf_reg_types kptr_xchg_dest_types = { .types = {PTR_TO_MAP_VALUE , -PTR_TO_BTF_ID |MEM_ALLOC +PTR_TO_BTF_ID |MEM_ALLOC , +PTR_TO_BTF_ID |MEM_ALLOC |NON_OWN_REF } };static const struct bpf_reg_types dynptr_types = {
@@ -9420,6 +9421,7 @@ static int check_reg_type(struct bpf_verifier_env *env, u32 regno, }case PTR_TO_BTF_ID |MEM_ALLOC :case PTR_TO_BTF_ID |MEM_PERCPU |MEM_ALLOC : +case PTR_TO_BTF_ID |MEM_ALLOC |NON_OWN_REF :if (meta->func_id != BPF_FUNC_spin_lock && meta->func_id != BPF_FUNC_spin_unlock && meta->func_id != BPF_FUNC_kptr_xchg) {verifier_bug (env,"unimplemented handling of MEM_ALLOC" );
Signature · 1 line
2.50.1 (Apple Git-155)
Re: [PATCH v6 2/5] bpf/verifier: allow using bpf_kptr_xchg even if the NON_OWN_REF flag is set
Quoted 23 lines · Chengkaitao
From: Kaitao Cheng <[email protected]>
When traversing an rbtree using bpf_rbtree_left/right, if
bpf_kptr_xchgis used to access the__kptrpointer contained in a node, it currently requires first removing the node withbpf_rbtree_removeand clearing theNON_OWN_REFflag, then re-adding the node to the original rbtree withbpf_rbtree_addafter usage. This process significantly degrades rbtree traversal performance. The patch enables accessing__kptrpointers with theNON_OWN_REFflag set while holding the lock, eliminating the need for this remove-read-add sequence.Signed-off-by Kaitao Cheng <[email protected]>Signed-off-by Feng Yang <[email protected]>--- kernel/bpf/verifier.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static const struct bpf_reg_types timer_types = { .types = { PTR_TO_MAP_VALUE } · line 9264
Quoted 6 lines
kernel/bpf/verifier.c +2
-1@@ -9260,7 +9260,8 @@ static const struct bpf_reg_types timer_types = { .types = { PTR_TO_MAP_VALUE }static const struct bpf_reg_types kptr_xchg_dest_types = { .types = {PTR_TO_MAP_VALUE , -PTR_TO_BTF_ID |MEM_ALLOC +PTR_TO_BTF_ID |MEM_ALLOC , +PTR_TO_BTF_ID |MEM_ALLOC |NON_OWN_REF
add a comma, so the next patch doesn't need to add it and has less churn.PTR_TO_BTF_ID | MEM_ALLOC | NON_OWN_REF | MEM_RCU , <-- comma too
Also don't invent new prefixes.
Either "bpf: ..." or "selftests/bpf: ...".
pw-bot: cr
PATCH v6 3/5 selftests/bpf: Add supplementary tests for bpf_kptr_xchg
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
1. Allow using bpf_kptr_xchg while holding a lock.
2. When the rb_node contains a __kptr pointer, we do not need to perform a remove-read-add operation.
This patch implements the following workflow:
1. Construct a rbtree with 16 elements.
2. Traverse the rbtree, locate the kptr pointer in the target node, and read the content pointed to by the pointer.
3. Remove all nodes from the rbtree.
--- .../testing/selftests/bpf/prog_tests/rbtree.c | 6 + tools/testing/selftests/bpf/progs/bpf_misc.h | 4 + .../selftests/bpf/progs/rbtree_search_kptr.c | 167 ++++++++++++++++++ 3 files changed, 177 insertions(+) create mode 100644 tools/testing/selftests/bpf/progs/rbtree_search_kptr.c
tools/testing/selftests/bpf/prog_tests/rbtree.c +6 -0
@@ -9,6 +9,7 @@#include "rbtree_btf_fail__wrong_node_type.skel.h" #include "rbtree_btf_fail__add_wrong_type.skel.h" #include "rbtree_search.skel.h" +#include "rbtree_search_kptr.skel.h" static void test_rbtree_add_nodes (void ) {
@@ -193,3 +194,8 @@ void test_rbtree_search(void) {RUN_TESTS (rbtree_search); } + +void test_rbtree_search_kptr (void ) +{ +RUN_TESTS (rbtree_search_kptr); +}
tools/testing/selftests/bpf/progs/bpf_misc.h +4 -0
@@ -188,6 +188,10 @@#define POINTER_VALUE 0xbadcafe#define TEST_DATA_LEN 64 +#ifndef __aligned +#define __aligned (x) __attribute__((aligned(x))) +#endif +#ifndef __used#define __used __attribute__((used))#endif
tools/testing/selftests/bpf/progs/rbtree_search_kptr.c new file +167 -0
167 lines not on this page · raw message
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v6 4/5 bpf/verifier: allow using bpf_kptr_xchg even if the MEM_RCU flag is set
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
For the following scenario:
struct tree_node {
struct bpf_refcount ref;
struct bpf_rb_node node;
struct node_data __kptr * node_data;
u64 key;
};This means node_data would have the type PTR_TO_BTF_ID | MEM_ALLOC | NON_OWN_REF | MEM_RCU.
When traversing an rbtree using bpf_rbtree_left/right, if we need to use bpf_kptr_xchg to read the __kptr pointer, we still need to follow the remove-read-add sequence.
This patch allows us to use bpf_kptr_xchg to directly read the __kptr pointer without any prior operations.
--- kernel/bpf/verifier.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +3 -1
@@ -9261,7 +9261,8 @@ static const struct bpf_reg_types kptr_xchg_dest_types = { .types = {PTR_TO_MAP_VALUE ,PTR_TO_BTF_ID |MEM_ALLOC , - PTR_TO_BTF_ID | MEM_ALLOC | NON_OWN_REF +PTR_TO_BTF_ID |MEM_ALLOC |NON_OWN_REF , + PTR_TO_BTF_ID | MEM_ALLOC | NON_OWN_REF | MEM_RCU } };static const struct bpf_reg_types dynptr_types = {
@@ -9422,6 +9423,7 @@ static int check_reg_type(struct bpf_verifier_env *env, u32 regno,case PTR_TO_BTF_ID |MEM_ALLOC :case PTR_TO_BTF_ID |MEM_PERCPU |MEM_ALLOC :case PTR_TO_BTF_ID |MEM_ALLOC |NON_OWN_REF : +case PTR_TO_BTF_ID |MEM_ALLOC |NON_OWN_REF |MEM_RCU :if (meta->func_id != BPF_FUNC_spin_lock && meta->func_id != BPF_FUNC_spin_unlock && meta->func_id != BPF_FUNC_kptr_xchg) {verifier_bug (env,"unimplemented handling of MEM_ALLOC" );
Signature · 1 line
2.50.1 (Apple Git-155)
PATCH v6 5/5 selftests/bpf: Add test case for rbtree nodes that contain both bpf_refcount and kptr fields.
In reply to ChengkaitaoFrom: Kaitao Cheng <[email protected]>
Allow bpf_kptr_xchg to directly operate on pointers marked with NON_OWN_REF | MEM_RCU.
In the example demonstrated in this patch, as long as "struct bpf_refcount ref" exists, the __kptr pointer is guaranteed to carry the MEM_RCU flag. The ref member itself does not need to be explicitly used.
--- .../selftests/bpf/progs/rbtree_search_kptr.c | 123 ++++++++++++++++++ 1 file changed, 123 insertions(+)
tools/testing/selftests/bpf/progs/rbtree_search_kptr.c +123 -0
@@ -18,11 +18,21 @@ struct tree_node { struct node_data __kptr * node_data; }; +struct tree_node_ref { +struct bpf_refcount ref; +struct bpf_rb_node node; +u64 key; + struct node_data __kptr * node_data; +}; +#define private (name) SEC(".data." #name) __hidden __aligned(8) private(A) struct bpf_rb_root root __contains(tree_node, node); private(A) struct bpf_spin_lock lock; +private(B) struct bpf_rb_root root_r __contains(tree_node_ref, node); +private(B) struct bpf_spin_lock lock_r; +static bool less (struct bpf_rb_node *a,const struct bpf_rb_node *b) {struct tree_node *node_a, *node_b;
@@ -130,6 +140,119 @@ long rbtree_search_kptr(void *ctx)return ret; } +static bool less_r (struct bpf_rb_node *a,const struct bpf_rb_node *b) +{ +struct tree_node_ref *node_a, *node_b; + + node_a = container_of(a, struct tree_node_ref, node); + node_b = container_of(b, struct tree_node_ref, node); + +return node_a->key < node_b->key; +} + +SEC("syscall") +__retval(0) +long rbtree_search_kptr_ref (void *ctx) +{ +struct tree_node_ref *tnode_r, *tnode_m; +struct bpf_rb_node *rb_n; + struct node_data __kptr * node_data; +int lookup_key =NR_NODES /2 ; +int lookup_data =NR_NODES /2 ; +int i, data, ret =0 ; + +for (i =0 ; i <NR_NODES && can_loop; i++) { + tnode_r =bpf_obj_new (typeof (*tnode_r)); +if (!tnode_r) +return __LINE__; + + node_data =bpf_obj_new (typeof (*node_data)); +if (!node_data) { +bpf_obj_drop (tnode_r); +return __LINE__; + } + + tnode_r->key = i; + node_data->data = i; + + node_data =bpf_kptr_xchg (&tnode_r->node_data, node_data); +if (node_data) +bpf_obj_drop (node_data); + +/* Unused reference */ + tnode_m =bpf_refcount_acquire (tnode_r); +if (!tnode_m) +return __LINE__; + +bpf_spin_lock (&lock_r); +bpf_rbtree_add (&root_r, &tnode_r->node, less_r); +bpf_spin_unlock (&lock_r); + +bpf_obj_drop (tnode_m); + } + +bpf_spin_lock (&lock_r); + rb_n =bpf_rbtree_root (&root_r); +while (rb_n && can_loop) { + tnode_r = container_of(rb_n, struct tree_node_ref, node); + node_data =bpf_kptr_xchg (&tnode_r->node_data,NULL ); +if (!node_data) { + ret = __LINE__; + goto fail; + } + + data = node_data->data; + node_data =bpf_kptr_xchg (&tnode_r->node_data, node_data); +if (node_data) { +bpf_spin_unlock (&lock_r); +bpf_obj_drop (node_data); +return __LINE__; + } + +if (lookup_key == tnode_r->key) { +if (data == lookup_data) +break ; + + ret = __LINE__; + goto fail; + } + +if (lookup_key < tnode_r->key) + rb_n =bpf_rbtree_left (&root_r, rb_n); +else + rb_n =bpf_rbtree_right (&root_r, rb_n); + } +bpf_spin_unlock (&lock_r); + +while (can_loop) { +bpf_spin_lock (&lock_r); + rb_n =bpf_rbtree_first (&root_r); +if (!rb_n) { +bpf_spin_unlock (&lock_r); +return 0 ; + } + + rb_n =bpf_rbtree_remove (&root_r, rb_n); +if (!rb_n) { + ret = __LINE__; + goto fail; + } +bpf_spin_unlock (&lock_r); + + tnode_r = container_of(rb_n, struct tree_node_ref, node); + + node_data =bpf_kptr_xchg (&tnode_r->node_data,NULL ); +if (node_data) +bpf_obj_drop (node_data); + +bpf_obj_drop (tnode_r); + } + +return 0 ; +fail: +bpf_spin_unlock (&lock_r); +return ret; +} SEC("syscall") __failure __msg("R1 type=scalar expected=map_value, ptr_, ptr_")
Signature · 1 line
2.50.1 (Apple Git-155)