Refactor lock management
Subsystems (4)
Kumar Kartikeya Dwivedi
maintainerv5 cover Refactor lock management
This set refactors lock management in the verifier in preparation for spin locks that can be acquired multiple times. In addition to this, unnecessary code special case reference leak logic for callbacks is also dropped, that is no longer necessary. See patches for details.
Changelog:
----------
v4 -> v5
v4: https://lore.kernel.org/bpf/[email protected]
* Make active_locks part of bpf_func_state (Alexei)
* Remove unneeded in_callback_fn logic for references
v3 -> v4
v3: https://lore.kernel.org/bpf/[email protected]
* Address comments from Alexei
* Drop struct bpf_active_lock definition
* Name enum type, expand definition to multiple lines
* s/REF_TYPE_BPF_LOCK/REF_TYPE_LOCK/g
* Change active_lock type to int
* Fix type of 'type' in acquire_lock_state
* Filter by taking type explicitly in find_lock_state
* WARN for default case in refsafe switch statement
v2 -> v3
v2: https://lore.kernel.org/bpf/[email protected]
* Rebase on bpf-next to resolve merge conflict
v1 -> v2
v1: https://lore.kernel.org/bpf/[email protected]
* Fix refsafe state comparison to check callback_ref and ptr separately.
Kumar Kartikeya Dwivedi (2):
bpf: Refactor active lock management
bpf: Drop special callback reference handling
include/linux/bpf_verifier.h | 40 ++--- kernel/bpf/verifier.c | 168 ++++++++++++------ .../selftests/bpf/prog_tests/cb_refs.c | 4 +- 3 files changed, 126 insertions(+), 86 deletions(-)
base-commit: 163ea3dec3c8048618f561a2c3b30f4c5795e991
Signature · 1 line
2.43.5
Kumar Kartikeya Dwivedi
maintainerPATCH v5 1/2 bpf: Refactor active lock management
When bpf_spin_lock was introduced originally, there was deliberation on whether to use an array of lock IDs, but since bpf_spin_lock is limited to holding a single lock at any given time, we've been using a single ID to identify the held lock.
In preparation for introducing spin locks that can be taken multiple times, introduce support for acquiring multiple lock IDs. For this purpose, reuse the acquired_refs array and store both lock and pointer references. We tag the entry with REF_TYPE_PTR or REF_TYPE_LOCK to disambiguate and find the relevant entry. The ptr field is used to track the map_ptr or btf (for bpf_obj_new allocations) to ensure locks can be matched with protected fields within the same "allocation", i.e. bpf_obj_new object or map value.
The struct active_lock is changed to an int as the state is part of the acquired_refs array, and we only need active_lock as a cheap way of detecting lock presence.
--- include/linux/bpf_verifier.h | 53 ++++++------- kernel/bpf/verifier.c | 149 ++++++++++++++++++++++++++--------- 2 files changed, 135 insertions(+), 67 deletions(-)
include/linux/bpf_verifier.h +25 -28
@@ -48,22 +48,6 @@ enum bpf_reg_liveness { REG_LIVE_DONE = 0x8, /* liveness won't be updating this register anymore */ }; -/* For every reg representing a map value or allocated object pointer, -* we consider the tuple of (ptr, id) for them to be unique in verifier -* context and conside them to not alias each other for the purposes of -* tracking lock state. -*/ -struct bpf_active_lock { -/* This can either be reg->map_ptr or reg->btf. If ptr is NULL, -* there's no active lock held, and other fields have no -* meaning. If non-NULL, it indicates that a lock is held and -* id member has the reg->id of the register which can be >= 0. -*/ -void *ptr; -/* This will be reg->id */ -u32 id; -}; -#define ITER_PREFIX "bpf_iter_"enum bpf_iter_state {
@@ -266,6 +250,13 @@ struct bpf_stack_state { };struct bpf_reference_state { +/* Each reference object has a type. Ensure REF_TYPE_PTR is zero to +* default to pointer reference on zero initialization of a state. +*/ +enum ref_state_type { +REF_TYPE_PTR =0 , +REF_TYPE_LOCK , + } type;/* Track each reference created with a unique id, even if the same * instruction creates the reference multiple times (eg, via CALL). */
@@ -274,17 +265,23 @@ struct bpf_reference_state {* is used purely to inform the user of a reference leak. */ int insn_idx; -/* There can be a case like: -* main (frame 0) -* cb (frame 1) -* func (frame 3) -* cb (frame 4) -* Hence for frame 4, if callback_ref just stored boolean, it would be -* impossible to distinguish nested callback refs. Hence store the -* frameno and compare that to callback_ref in check_reference_leak when -* exiting a callback function. -*/ -int callback_ref; +union { +/* There can be a case like: +* main (frame 0) +* cb (frame 1) +* func (frame 3) +* cb (frame 4) +* Hence for frame 4, if callback_ref just stored boolean, it would be +* impossible to distinguish nested callback refs. Hence store the +* frameno and compare that to callback_ref in check_reference_leak when +* exiting a callback function. +*/ +int callback_ref; +/* Use to keep track of the source object of a lock, to ensure +* it matches on unlock. +*/ +void *ptr; + }; };struct bpf_retval_range {
@@ -332,6 +329,7 @@ struct bpf_func_state {/* The following fields should be last. See copy_func_state() */ int acquired_refs; +int active_locks;struct bpf_reference_state *refs;/* The state of the stack. Each element of the array describes BPF_REG_SIZE * (i.e. 8) bytes worth of stack memory.
@@ -434,7 +432,6 @@ struct bpf_verifier_state {u32 insn_idx;u32 curframe; -struct bpf_active_lock active_lock;bool speculative;bool active_rcu_lock;u32 active_preempt_lock;
kernel/bpf/verifier.c +110 -39
290 lines not on this page · raw message
Signature · 1 line
2.43.5
Re: [PATCH bpf-next v5 1/2] bpf: Refactor active lock management
kernel/bpf/verifier.c static int process_spin_lock(struct bpf_verifier_env *env, int regno, · line 7850
Quoted 9 lines · Kumar Kartikeya Dwivedi
kernel/bpf/verifier.c +9
-0+ err =acquire_lock_state (env, env->insn_idx,REF_TYPE_LOCK , reg->id, ptr); +if (err <0 ) { +verbose (env,"Failed to acquire lock state\n" ); +return err; + } +/* It is not safe to allow multiple bpf_spin_lock calls, so +* disallow them until this lock has been unlocked. +*/ + cur->active_locks++;
One more thing as suggested earlier...
pls move active_locks++ into acquire_lock_state().
Quoted 15 lines
} else { void *ptr;kernel/bpf/verifier.c +2
-3@@ -7786,20 +7856,18 @@ static int process_spin_lock(struct bpf_verifier_env *env, int regno,else ptr = btf; -if (!cur->active_lock.ptr) { +if (!cur->active_locks) {verbose (env,"bpf_spin_unlock without taking a lock\n" );return -EINVAL ; } -if (cur->active_lock.ptr != ptr || - cur->active_lock.id != reg->id) { +
kernel/bpf/verifier.c static int process_spin_lock(struct bpf_verifier_env *env, int regno, · line 7870
Quoted 10 lines
kernel/bpf/verifier.c +2
-3+if (release_lock_state (cur_func (env),REF_TYPE_LOCK , reg->id, ptr)) {verbose (env,"bpf_spin_unlock of different lock\n" );return -EINVAL ; }invalidate_non_owning_refs (env); - - cur->active_lock.ptr =NULL ; - cur->active_lock.id =0 ; + cur->active_locks--;
And similar with decrement.
imo it's cleaner this way.
The rest looks good.
Patch 2 is a nice cleanup. Thanks!
Kumar Kartikeya Dwivedi
maintainerPATCH v5 2/2 bpf: Drop special callback reference handling
In reply to Kumar Kartikeya DwivediLogic to prevent callbacks from acquiring new references for the program (i.e. leaving acquired references), and releasing caller references (i.e. those acquired in parent frames) was introduced in commit 9d9d00ac29d0 ("bpf: Fix reference state management for synchronous callbacks").
This was necessary because back then, the verifier simulated each callback once (that could potentially be executed N times, where N can be zero). This meant that callbacks that left lingering resources or cleared caller resources could do it more than once, operating on undefined state or leaking memory.
With the fixes to callback verification in commitab5cfac139ab ("bpf: verify callbacks as if they are called unknown number of times"), all of this extra logic is no longer necessary. Hence, drop it as part of this commit.
--- include/linux/bpf_verifier.h | 21 +++------------- kernel/bpf/verifier.c | 25 ++++--------------- .../selftests/bpf/prog_tests/cb_refs.c | 4 +-- 3 files changed, 11 insertions(+), 39 deletions(-)
include/linux/bpf_verifier.h +4 -17
@@ -265,23 +265,10 @@ struct bpf_reference_state {* is used purely to inform the user of a reference leak. */ int insn_idx; -union { -/* There can be a case like: -* main (frame 0) -* cb (frame 1) -* func (frame 3) -* cb (frame 4) -* Hence for frame 4, if callback_ref just stored boolean, it would be -* impossible to distinguish nested callback refs. Hence store the -* frameno and compare that to callback_ref in check_reference_leak when -* exiting a callback function. -*/ -int callback_ref; -/* Use to keep track of the source object of a lock, to ensure -* it matches on unlock. -*/ -void *ptr; - }; +/* Use to keep track of the source object of a lock, to ensure +* it matches on unlock. +*/ +void *ptr; };struct bpf_retval_range {
kernel/bpf/verifier.c +5 -20
@@ -1358,7 +1358,6 @@ static int acquire_reference_state(struct bpf_verifier_env *env, int insn_idx) state->refs[new_ofs].type =REF_TYPE_PTR ; state->refs[new_ofs].id = id; state->refs[new_ofs].insn_idx = insn_idx; - state->refs[new_ofs].callback_ref = state->in_callback_fn ? state->frameno :0 ;return id; }
@@ -1391,9 +1390,6 @@ static int release_reference_state(struct bpf_func_state *state, int ptr_id)if (state->refs[i].type !=REF_TYPE_PTR )continue ;if (state->refs[i].id == ptr_id) { -/* Cannot release caller references in callbacks */ -if (state->in_callback_fn && state->refs[i].callback_ref != state->frameno) -return -EINVAL ;if (last_idx && i != last_idx)memcpy (&state->refs[i], &state->refs[last_idx],sizeof (*state->refs));
@@ -10270,17 +10266,10 @@ static int prepare_func_exit(struct bpf_verifier_env *env, int *insn_idx) caller->regs[BPF_REG_0 ] = *r0; } -/* callback_fn frame should have released its own additions to parent's -* reference state at this point, or check_reference_leak would -* complain, hence it must be the same as the caller. There is no need -* to copy it back. -*/ -if (!callee->in_callback_fn) { -/* Transfer references to the caller */ - err =copy_reference_state (caller, callee); -if (err) -return err; - } +/* Transfer references to the caller */ + err =copy_reference_state (caller, callee); +if (err) +return err;/* for callbacks like bpf_loop or bpf_for_each_map_elem go back to callsite, * there function call logic would reschedule callback visit. If iteration
@@ -10450,14 +10439,12 @@ static int check_reference_leak(struct bpf_verifier_env *env, bool exception_exibool refs_lingering = false;int i; -if (!exception_exit && state->frameno && !state->in_callback_fn) +if (!exception_exit && state->frameno)return 0 ;for (i =0 ; i < state->acquired_refs; i++) {if (state->refs[i].type !=REF_TYPE_PTR )continue ; -if (!exception_exit && state->in_callback_fn && state->refs[i].callback_ref != state->frameno) -continue ;verbose (env,"Unreleased reference id=%d alloc_insn=%d\n" , state->refs[i].id, state->refs[i].insn_idx); refs_lingering = true;
@@ -17710,8 +17697,6 @@ static bool refsafe(struct bpf_func_state *old, struct bpf_func_state *cur,return false;switch (old->refs[i].type) {case REF_TYPE_PTR : -if (old->refs[i].callback_ref != cur->refs[i].callback_ref) -return false;break ;case REF_TYPE_LOCK :if (old->refs[i].ptr != cur->refs[i].ptr)
tools/testing/selftests/bpf/prog_tests/cb_refs.c +2 -2
@@ -11,8 +11,8 @@ struct {const char *prog_name;const char *err_msg; } cb_refs_tests[] = { - { "underflow_prog", "reference has not been acquired before" }, - { "leak_prog", "Unreleased reference" }, + { "underflow_prog", "must point to scalar, or struct with scalar" }, + { "leak_prog", "Possibly NULL pointer passed to helper arg2" }, { "nested_cb", "Unreleased reference id=4 alloc_insn=2" }, /* alloc_insn=2{4,5} */ { "non_cb_transfer_ref", "Unreleased reference id=4 alloc_insn=1" }, /* alloc_insn=1{1,2} */ };
Signature · 1 line
2.43.5