Allow bpf_refcount_acquire of mapval obtained via direct LD
Subsystems (4)
v2 cover Allow bpf_refcount_acquire of mapval obtained via direct LD
Consider this BPF program:
struct cgv_node {
int d;
struct bpf_refcount r;
struct bpf_rb_node rb;
};
struct val_stash {
struct cgv_node __kptr *v;
};
struct {
__uint(type, BPF_MAP_TYPE_ARRAY);
__type(key, int);
__type(value, struct val_stash);
__uint(max_entries, 10);
} array_map SEC(".maps");
long bpf_program(void *ctx)
{
struct val_stash *mapval;
struct cgv_node *p;
int idx = 0; mapval = bpf_map_lookup_elem(&array_map, &idx);
if (!mapval || !mapval->v) { /* omitted */ }
p = bpf_refcount_acquire(mapval->v); /* Verification FAILs here */
/* Add p to some tree */
return 0;}
Verification fails on the refcount_acquire:
160: (79) r1 = *(u64 *)(r8 +8) ; R1_w=untrusted_ptr_or_null_cgv_node(id=11,off=0,imm=0) R8_w=map_value(id=10,off=0,ks=8,vs=16,imm=0) refs=6
161: (b7) r2 = 0 ; R2_w=0 refs=6
162: (85) call bpf_refcount_acquire_impl#117824
arg#0 is neither owning or non-owning ref
The above verifier dump is actually from sched_ext's scx_flatcg [0], which is the motivating usecase for this series' changes. Specifically, scx_flatcg stashes a rb_node type w/ cgroup-specific info (struct cgv_node) in a map when the cgroup is created, then later puts that cgroup's node in a rbtree in .enqueue . Making struct cgv_node refcounted would simplify the code a bit by virtue of allowing us to remove the kptr_xchg's, but "later puts that cgroups node in a rbtree" is not possible without a refcount_acquire, which suffers from the above verification failure.
If we get rid of PTR_UNTRUSTED flag, and add MEM_ALLOC | NON_OWN_REF, mapval->v would be a non-owning ref and verification would succeed. Due to the most recent set of refcount changes [1], which modified bpf_obj_drop behavior to not reuse refcounted graph node's underlying memory until after RCU grace period, this is safe to do. Once mapval->v has the correct flags it _is_ a non-owning reference and verification of the motivating example will succeed.
[0]: https://github.com/sched-ext/sched_ext/blob/52911e1040a0f94b9c426dddcc00be5364a7ae9f/tools/sched_ext/scx_flatcg.bpf.c#L275
[1]: https://lore.kernel.org/bpf/[email protected]/
Summary of patches:
* Patch 1 fixes an issue with bpf_refcount_acquire verification letting MAYBE_NULL ptrs through
* Patch 2 tests Patch 1's fix
* Patch 3 broadens the use of "free only after RCU GP" to all user-allocated types
* Patch 4 is a small nonfunctional refactoring
* Patch 5 changes verifier to mark direct LD of stashed graph node kptr as non-owning ref
* Patch 6 tests Patch 5's verifier changes
Changelog:
v1 -> v2: https://lore.kernel.org/bpf/[email protected]/
Series title changed to "Allow bpf_refcount_acquire of mapval obtained via direct LD". V1's title was mistakenly truncated.
* Patch 5 ("bpf: Mark direct ld of stashed bpf_{rb,list}_node as non-owning ref")
* Direct LD of percpu kptr should not have MEM_ALLOC flag (Yonghong)
* Patch 6 ("selftests/bpf: Test bpf_refcount_acquire of node obtained via direct ld")
* Test read from stashed value as well
Dave Marchevsky (6):
bpf: Add KF_RCU flag to bpf_refcount_acquire_impl selftests/bpf: Add test passing MAYBE_NULL reg to bpf_refcount_acquire
bpf: Use bpf_mem_free_rcu when bpf_obj_dropping non-refcounted nodes
bpf: Move GRAPH_{ROOT,NODE}_MASK macros into btf_field_type enum
bpf: Mark direct ld of stashed bpf_{rb,list}_node as non-owning ref selftests/bpf: Test bpf_refcount_acquire of node obtained via direct
ld
include/linux/bpf.h | 4 +- kernel/bpf/btf.c | 11 ++- kernel/bpf/helpers.c | 7 +- kernel/bpf/verifier.c | 36 ++++++++-- .../bpf/prog_tests/local_kptr_stash.c | 33 +++++++++ .../selftests/bpf/progs/local_kptr_stash.c | 71 +++++++++++++++++++ .../bpf/progs/refcounted_kptr_fail.c | 19 +++++ 7 files changed, 162 insertions(+), 19 deletions(-)
Signature · 1 line
2.34.1
PATCH v2 1/6 bpf: Add KF_RCU flag to bpf_refcount_acquire_impl
Refcounted local kptrs are kptrs to user-defined types with a bpf_refcount field. Recent commits ([0], [1]) modified the lifetime of refcounted local kptrs such that the underlying memory is not reused until RCU grace period has elapsed.
Separately, verification of bpf_refcount_acquire calls currently succeeds for MAYBE_NULL non-owning reference input, which is a problem as bpf_refcount_acquire_impl has no handling for this case.
This patch takes advantage of aforementioned lifetime changes to tag bpf_refcount_acquire_impl kfunc KF_RCU, thereby preventing MAYBE_NULL input to the kfunc. The KF_RCU flag applies to all kfunc params; it's fine for it to apply to the void *meta__ign param as that's populated by the verifier and is tagged __ign regardless.
[0]: commit 7e26cd12ad1c ("bpf: Use bpf_mem_free_rcu when
bpf_obj_dropping refcounted nodes") is the actual change to allocation behaivor
[1]: commit 0816b8c6bf7f ("bpf: Consider non-owning refs to refcounted
nodes RCU protected") modified verifier understanding of refcounted local kptrs to match [0]'s changes
--- kernel/bpf/helpers.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/helpers.c +1 -1
@@ -2515,7 +2515,7 @@ BTF_ID_FLAGS(func, bpf_obj_new_impl, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_percpu_obj_new_impl, KF_ACQUIRE | KF_RET_NULL) BTF_ID_FLAGS(func, bpf_obj_drop_impl, KF_RELEASE) BTF_ID_FLAGS(func, bpf_percpu_obj_drop_impl, KF_RELEASE) -BTF_ID_FLAGS(func, bpf_refcount_acquire_impl, KF_ACQUIRE | KF_RET_NULL) +BTF_ID_FLAGS(func, bpf_refcount_acquire_impl, KF_ACQUIRE | KF_RET_NULL | KF_RCU) 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 )
Signature · 1 line
2.34.1
PATCH v2 2/6 selftests/bpf: Add test passing MAYBE_NULL reg to bpf_refcount_acquire
In reply to Dave MarchevskyThe test added in this patch exercises the logic fixed in the previous patch in this series. Before the previous patch's changes, bpf_refcount_acquire accepts MAYBE_NULL local kptrs; after the change the verifier correctly rejects the such a call.
--- .../bpf/progs/refcounted_kptr_fail.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+)
tools/testing/selftests/bpf/progs/refcounted_kptr_fail.c +19 -0
@@ -53,6 +53,25 @@ long rbtree_refcounted_node_ref_escapes(void *ctx)return 0 ; } +SEC("?tc") +__failure __msg("Possibly NULL pointer passed to trusted arg0") +long refcount_acquire_maybe_null(void *ctx) +{ +struct node_acquire *n, *m; + + n =bpf_obj_new (typeof (*n)); +/* Intentionally not testing !n +* it's MAYBE_NULL for refcount_acquire +*/ + m =bpf_refcount_acquire (n); +if (m) +bpf_obj_drop (m); +if (n) +bpf_obj_drop (n); + +return 0 ; +} + SEC("?tc") __failure __msg("Unreleased reference id=3 alloc_insn=9") long rbtree_refcounted_node_ref_escapes_owning_input(void *ctx)
Signature · 1 line
2.34.1
PATCH v2 3/6 bpf: Use bpf_mem_free_rcu when bpf_obj_dropping non-refcounted nodes
In reply to Dave MarchevskyThe use of bpf_mem_free_rcu to free refcounted local kptrs was added in commit 7e26cd12ad1c ("bpf: Use bpf_mem_free_rcu when bpf_obj_dropping refcounted nodes"). In the cover letter for the series containing that patch [0] I commented:
Perhaps it makes sense to move to mem_free_rcu for _all_ non-owning refs in the future, not just refcounted. This might allow custom non-owning ref lifetime + invalidation logic to be entirely subsumed by MEM_RCU handling. IMO this needs a bit more thought and should be tackled outside of a fix series, so it's not attempted here.
It's time to start moving in the "non-owning refs have MEM_RCU lifetime" direction. As mentioned in that comment, using bpf_mem_free_rcu for all local kptrs - not just refcounted - is necessarily the first step towards that goal. This patch does so.
After this patch the memory pointed to by all local kptrs will not be reused until RCU grace period elapses. The verifier's understanding of non-owning ref validity and the clobbering logic it uses to enforce that understanding are not changed here, that'll happen gradually in future work, including further patches in the series.
[0]: https://lore.kernel.org/all/[email protected]/
--- kernel/bpf/helpers.c | 5 +---- 1 file changed, 1 insertion(+), 4 deletions(-)
kernel/bpf/helpers.c +1 -4
@@ -1932,10 +1932,7 @@ void __bpf_obj_drop_impl(void *p, const struct btf_record *rec, bool percpu) ma = &bpf_global_percpu_ma; else ma = &bpf_global_ma; -if (rec && rec->refcount_off >=0 ) -bpf_mem_free_rcu (ma, p); -else -bpf_mem_free (ma, p); +bpf_mem_free_rcu (ma, p); } __bpf_kfunc void bpf_obj_drop_impl(void *p__alloc, void *meta__ign)
Signature · 1 line
2.34.1
PATCH v2 4/6 bpf: Move GRAPH_{ROOT,NODE}_MASK macros into btf_field_type enum
In reply to Dave MarchevskyThis refactoring patch removes the unused BPF_GRAPH_NODE_OR_ROOT btf_field_type and moves BPF_GRAPH_{NODE,ROOT} macros into the btf_field_type enum. Further patches in the series will use BPF_GRAPH_NODE, so let's move this useful definition out of btf.c.
--- include/linux/bpf.h | 4 ++-- kernel/bpf/btf.c | 11 ++++------- 2 files changed, 6 insertions(+), 9 deletions(-)
include/linux/bpf.h +2 -2
@@ -186,8 +186,8 @@ enum btf_field_type {BPF_LIST_NODE = (1 <<6 ),BPF_RB_ROOT = (1 <<7 ),BPF_RB_NODE = (1 <<8 ), -BPF_GRAPH_NODE_OR_ROOT =BPF_LIST_NODE |BPF_LIST_HEAD | -BPF_RB_NODE |BPF_RB_ROOT , +BPF_GRAPH_NODE =BPF_RB_NODE |BPF_LIST_NODE , +BPF_GRAPH_ROOT =BPF_RB_ROOT |BPF_LIST_HEAD , BPF_REFCOUNT = (1 << 9), };
kernel/bpf/btf.c +4 -7
@@ -3840,9 +3840,6 @@ struct btf_record *btf_parse_fields(const struct btf *btf, const struct btf_typereturn ERR_PTR (ret); } -#define GRAPH_ROOT_MASK (BPF_LIST_HEAD | BPF_RB_ROOT) -#define GRAPH_NODE_MASK (BPF_LIST_NODE | BPF_RB_NODE) -int btf_check_and_fixup_fields (const struct btf *btf,struct btf_record *rec) {int i;
@@ -3855,13 +3852,13 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)* Hence we only need to ensure that bpf_{list_head,rb_root} ownership * does not form cycles. */ -if (IS_ERR_OR_NULL (rec) || !(rec->field_mask &GRAPH_ROOT_MASK )) +if (IS_ERR_OR_NULL (rec) || !(rec->field_mask &BPF_GRAPH_ROOT ))return 0 ;for (i =0 ; i < rec->cnt; i++) {struct btf_struct_meta *meta;u32 btf_id; -if (!(rec->fields[i].type &GRAPH_ROOT_MASK )) +if (!(rec->fields[i].type &BPF_GRAPH_ROOT ))continue ; btf_id = rec->fields[i].graph_root.value_btf_id; meta =btf_find_struct_meta (btf, btf_id);
@@ -3873,7 +3870,7 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)* to check ownership cycle for a type unless it's also a * node type. */ -if (!(rec->field_mask &GRAPH_NODE_MASK )) +if (!(rec->field_mask &BPF_GRAPH_NODE ))continue ;/* We need to ensure ownership acyclicity among all types. The
@@ -3909,7 +3906,7 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)* - A is both an root and node. * - B is only an node. */ -if (meta->record->field_mask &GRAPH_ROOT_MASK ) +if (meta->record->field_mask &BPF_GRAPH_ROOT )return -ELOOP ; }return 0 ;
Signature · 1 line
2.34.1
PATCH v2 5/6 bpf: Mark direct ld of stashed bpf_{rb,list}_node as non-owning ref
In reply to Dave MarchevskyThis patch enables the following pattern:
/* mapval contains a __kptr pointing to refcounted local kptr */
mapval = bpf_map_lookup_elem(&map, &idx);
if (!mapval || !mapval->some_kptr) { /* omitted */ }
p = bpf_refcount_acquire(&mapval->some_kptr);Currently this doesn't work because bpf_refcount_acquire expects an owning or non-owning ref. The verifier defines non-owning ref as a type:
PTR_TO_BTF_ID | MEM_ALLOC | NON_OWN_REF
while mapval->some_kptr is PTR_TO_BTF_ID | PTR_UNTRUSTED. It's possible to do the refcount_acquire by first bpf_kptr_xchg'ing mapval->some_kptr into a temp kptr, refcount_acquiring that, and xchg'ing back into mapval, but this is unwieldy and shouldn't be necessary.
This patch modifies btf_ld_kptr_type such that user-allocated types are marked MEM_ALLOC and if those types have a bpf_{rb,list}_node they're marked NON_OWN_REF as well. Additionally, due to changes to bpf_obj_drop_impl earlier in this series, rcu_protected_object now returns true for all user-allocated types, resulting in mapval->some_kptr being marked MEM_RCU.
After this patch's changes, mapval->some_kptr is now:
PTR_TO_BTF_ID | MEM_ALLOC | NON_OWN_REF | MEM_RCU
which results in it passing the non-owning ref test, and the motivating example passing verification.
Future work will likely get rid of special non-owning ref lifetime logic in the verifier, at which point we'll be able to delete the NON_OWN_REF flag entirely.
--- kernel/bpf/verifier.c | 36 +++++++++++++++++++++++++++++++----- 1 file changed, 31 insertions(+), 5 deletions(-)
kernel/bpf/verifier.c +31 -5
@@ -5542,10 +5542,23 @@ BTF_SET_END(rcu_protected_types)static bool rcu_protected_object (const struct btf *btf,u32 btf_id) {if (!btf_is_kernel (btf)) -return false; +return true;return btf_id_set_contains (&rcu_protected_types, btf_id); } +static struct btf_record *kptr_pointee_btf_record (struct btf_field *kptr_field) +{ +struct btf_struct_meta *meta; + +if (btf_is_kernel (kptr_field->kptr.btf)) +return NULL ; + + meta =btf_find_struct_meta (kptr_field->kptr.btf, + kptr_field->kptr.btf_id); + +return meta ? meta->record :NULL ; +} +static bool rcu_safe_kptr (const struct btf_field *field) {const struct btf_field_kptr *kptr = &field->kptr;
@@ -5556,12 +5569,25 @@ static bool rcu_safe_kptr(const struct btf_field *field)static u32 btf_ld_kptr_type (struct bpf_verifier_env *env,struct btf_field *kptr_field) { +struct btf_record *rec; +u32 ret; + + ret =PTR_MAYBE_NULL ;if (rcu_safe_kptr (kptr_field) &&in_rcu_cs (env)) { -if (kptr_field->type !=BPF_KPTR_PERCPU ) -return PTR_MAYBE_NULL |MEM_RCU ; -return PTR_MAYBE_NULL |MEM_RCU |MEM_PERCPU ; + ret |=MEM_RCU ; +if (kptr_field->type ==BPF_KPTR_PERCPU ) + ret |=MEM_PERCPU ; +else if (!btf_is_kernel (kptr_field->kptr.btf)) + ret |=MEM_ALLOC ; + + rec =kptr_pointee_btf_record (kptr_field); +if (rec &&btf_record_has_field (rec,BPF_GRAPH_NODE )) + ret |=NON_OWN_REF ; + }else { + ret |=PTR_UNTRUSTED ; } -return PTR_MAYBE_NULL |PTR_UNTRUSTED ; + +return ret; } static int check_map_kptr_access(struct bpf_verifier_env *env, u32 regno,
Signature · 1 line
2.34.1
PATCH v2 6/6 selftests/bpf: Test bpf_refcount_acquire of node obtained via direct ld
In reply to Dave MarchevskyThis patch demonstrates that verifier changes earlier in this series result in bpf_refcount_acquire(mapval->stashed_kptr) passing verification. The added test additionally validates that stashing a kptr in mapval and - in a separate BPF program - refcount_acquiring the kptr without unstashing works as expected at runtime.
--- .../bpf/prog_tests/local_kptr_stash.c | 33 +++++++++ .../selftests/bpf/progs/local_kptr_stash.c | 71 +++++++++++++++++++ 2 files changed, 104 insertions(+)
tools/testing/selftests/bpf/prog_tests/local_kptr_stash.c +33 -0
@@ -73,6 +73,37 @@ static void test_local_kptr_stash_unstash(void)local_kptr_stash__destroy (skel); } +static void test_refcount_acquire_without_unstash (void ) +{ +LIBBPF_OPTS (bpf_test_run_opts, opts, + .data_in = &pkt_v4, + .data_size_in = sizeof(pkt_v4), + .repeat = 1, + ); +struct local_kptr_stash *skel; +int ret; + + skel =local_kptr_stash__open_and_load (); +if (!ASSERT_OK_PTR (skel,"local_kptr_stash__open_and_load" )) +return ; + + ret =bpf_prog_test_run_opts (bpf_program__fd (skel->progs.refcount_acquire_without_unstash), + &opts); +ASSERT_OK (ret,"refcount_acquire_without_unstash run" ); +ASSERT_EQ (opts.retval,2 ,"refcount_acquire_without_unstash retval" ); + + ret =bpf_prog_test_run_opts (bpf_program__fd (skel->progs.stash_refcounted_node), &opts); +ASSERT_OK (ret,"stash_refcounted_node run" ); +ASSERT_OK (opts.retval,"stash_refcounted_node retval" ); + + ret =bpf_prog_test_run_opts (bpf_program__fd (skel->progs.refcount_acquire_without_unstash), + &opts); +ASSERT_OK (ret,"refcount_acquire_without_unstash (2) run" ); +ASSERT_EQ (opts.retval,42 ,"refcount_acquire_without_unstash (2) retval" ); + +local_kptr_stash__destroy (skel); +} +static void test_local_kptr_stash_fail (void ) {RUN_TESTS (local_kptr_stash_fail);
@@ -86,6 +117,8 @@ void test_local_kptr_stash(void)test_local_kptr_stash_plain ();if (test__start_subtest ("local_kptr_stash_unstash" ))test_local_kptr_stash_unstash (); +if (test__start_subtest ("refcount_acquire_without_unstash" )) +test_refcount_acquire_without_unstash ();if (test__start_subtest ("local_kptr_stash_fail" ))test_local_kptr_stash_fail (); }
tools/testing/selftests/bpf/progs/local_kptr_stash.c +71 -0
87 lines not on this page · raw message
Signature · 1 line
2.34.1
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Tue, 7 Nov 2023 00:56:33 -0800 you wrote:
Consider this BPF program:
struct cgv_node { int d; struct bpf_refcount r; struct bpf_rb_node rb; };[...]
Here is the summary with links:
- [v2,bpf-next,1/6] bpf: Add KF_RCU flag to bpf_refcount_acquire_impl
https://git.kernel.org/bpf/bpf-next/c/8a53f8c65c9f - [v2,bpf-next,2/6] selftests/bpf: Add test passing MAYBE_NULL reg to bpf_refcount_acquire https://git.kernel.org/bpf/bpf-next/c/315bbb93dafc - [v2,bpf-next,3/6] bpf: Use bpf_mem_free_rcu when bpf_obj_dropping non-refcounted nodes https://git.kernel.org/bpf/bpf-next/c/cf1ec20de34b - [v2,bpf-next,4/6] bpf: Move GRAPH_{ROOT,NODE}_MASK macros into btf_field_type enum https://git.kernel.org/bpf/bpf-next/c/a7b6ab9481d0 - [v2,bpf-next,5/6] bpf: Mark direct ld of stashed bpf_{rb,list}_node as non-owning ref https://git.kernel.org/bpf/bpf-next/c/6eba51e33182 - [v2,bpf-next,6/6] selftests/bpf: Test bpf_refcount_acquire of node obtained via direct ld https://git.kernel.org/bpf/bpf-next/c/3975f7e7494b
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html