Skip to contentSkip to conversation

bpf: Refactor active lock management

PATCH Superseded Kumar Kartikeya Dwivedi 2 participants 5 messages Nov 9, 2024

Subsystems (2)

v4 of 6 Superseded Latest is v6 →

lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

PATCH v4 1/1 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.

---
Changelog:
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.

---
 include/linux/bpf_verifier.h |  53 ++++++-------
 kernel/bpf/verifier.c        | 143 ++++++++++++++++++++++++++---------
 2 files changed, 134 insertions(+), 62 deletions(-)
include/linux/bpf_verifier.h +25 -28
index 4513372c5bc8..b248850396ac 100644
@@ -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 {
@@ -434,7 +431,7 @@ struct bpf_verifier_state {
 	u32 insn_idx;
 	u32 curframe;
 
-	struct bpf_active_lock active_lock;
+	int active_lock;
 	bool speculative;
 	bool active_rcu_lock;
 	u32 active_preempt_lock;
kernel/bpf/verifier.c +109 -34

269 lines not on this page · raw message

--
2.43.5

#1 lore raw

include/linux/bpf_verifier.h struct bpf_verifier_state { · line 434

Quoted 7 lines · Kumar Kartikeya Dwivedi

struct bpf_retval_range {

include/linux/bpf_verifier.h +1 -1
@@ -434,7 +431,7 @@ struct bpf_verifier_state {
        u32 insn_idx;
        u32 curframe;
 
-       struct bpf_active_lock active_lock;
+       int active_lock;

What about this comment from v3:

Review struct bpf_verifier_state { · line 435

Quoted 1 line
(quoted diff) +1 -0
+       bool active_lock;

In the next patch it becomes 'int',
so let's make it 'int' right away and move it to bpf_func_state next to:

        int acquired_refs;
        struct bpf_reference_state *refs;

?

wouldn't it be cleaner to keep the count of locks in bpf_func_state next to refs ?

acquire_lock_state() would increment it and release will dec it.

check_resource_leak() will
instead of:
env->cur_state->active_lock
do:
cur_func(env)->active_lock

so behavior is the same, but counting of locks is clean.

Since in this patch it's kinda counting locks across all frames which is a bit odd.

author maintainer
#2 lore raw
Quoted 14 lines · Alexei Starovoitov

include/linux/bpf_verifier.h struct bpf_verifier_state { · line 434

Quoted 7 lines · Kumar Kartikeya Dwivedi

struct bpf_retval_range {

include/linux/bpf_verifier.h +1 -1
@@ -434,7 +431,7 @@ struct bpf_verifier_state {
        u32 insn_idx;
        u32 curframe;
 
-       struct bpf_active_lock active_lock;
+       int active_lock;

What about this comment from v3:

Review struct bpf_verifier_state { · line 435

Quoted 1 line
(quoted diff) +1 -0
+       bool active_lock;
Quoted 7 lines

In the next patch it becomes 'int',
so let's make it 'int' right away and move it to bpf_func_state next to:

        int acquired_refs;
        struct bpf_reference_state *refs;

?

Ah, sorry, I somehow missed this part of the comment (twice). Mea culpa.

Quoted 12 lines

wouldn't it be cleaner to keep the count of locks in bpf_func_state next to refs

acquire_lock_state() would increment it and release will dec it.

check_resource_leak() will
instead of:
env->cur_state->active_lock
do:
cur_func(env)->active_lock

Quoted 4 lines

so behavior is the same, but counting of locks is clean.

Since in this patch it's kinda counting locks across all frames which is a bit odd.

It would work, but we'd need to copy it over to a new frame's bpf_func_state and copy it back on exit.
None of that would matter currently as only one lock can be held, but it would become relevant later.

It's the same situation with reference states. It is inherited from the parent frame for every new frame, and then possibly changed, and then copied back to parent frame.

I have no preference either way, but if you think maintaining it as part of func state is better I can make that change.

#3 lore raw
Quoted 44 lines · Kumar Kartikeya Dwivedi
Quoted 14 lines · Alexei Starovoitov

include/linux/bpf_verifier.h struct bpf_verifier_state { · line 434

Quoted 7 lines · Kumar Kartikeya Dwivedi

struct bpf_retval_range {

include/linux/bpf_verifier.h +1 -1
@@ -434,7 +431,7 @@ struct bpf_verifier_state {
        u32 insn_idx;
        u32 curframe;
 
-       struct bpf_active_lock active_lock;
+       int active_lock;

What about this comment from v3:

Review struct bpf_verifier_state { · line 435

Quoted 1 line
(quoted diff) +1 -0
+       bool active_lock;
Quoted 7 lines

In the next patch it becomes 'int',
so let's make it 'int' right away and move it to bpf_func_state next to:

        int acquired_refs;
        struct bpf_reference_state *refs;

?

Ah, sorry, I somehow missed this part of the comment (twice). Mea culpa.

Quoted 12 lines

wouldn't it be cleaner to keep the count of locks in bpf_func_state next to refs

acquire_lock_state() would increment it and release will dec it.

check_resource_leak() will
instead of:
env->cur_state->active_lock
do:
cur_func(env)->active_lock

Quoted 4 lines

so behavior is the same, but counting of locks is clean.

Since in this patch it's kinda counting locks across all frames which is a bit odd.

Quoted 8 lines

It would work, but we'd need to copy it over to a new frame's bpf_func_state and copy it back on exit.
None of that would matter currently as only one lock can be held, but it would become relevant later.

It's the same situation with reference states. It is inherited from the parent frame for every new frame, and then possibly changed, and then copied back to parent frame.

Exactly, but since we're unifying held locks as references would it make sense to treat them the same way everywhere? active_lock is just a count of held locks in ref state. For refs we do:
if (!exception_exit && state->in_callback_fn && state->refs[i].callback_ref != state->frameno)

so that
task = task_acquire().
bpf_loop(cb)
task_release(task)
doesn't trip.

Wouldn't we want the same for locks eventually ?

Just if (env->cur_state->active_lock) will change obviously. We may even need two counters for regular and resilient locks ? And in that case two counters in bpf_verifier_state looks even more odd. While two counters in bpf_func_state feels more logical.

Just trying to anticipate the future changes...

author maintainer
#4 lore raw
Quoted 62 lines · Alexei Starovoitov
Quoted 44 lines · Kumar Kartikeya Dwivedi
Quoted 14 lines · Alexei Starovoitov

include/linux/bpf_verifier.h struct bpf_verifier_state { · line 434

Quoted 7 lines · Kumar Kartikeya Dwivedi

struct bpf_retval_range {

include/linux/bpf_verifier.h +1 -1
@@ -434,7 +431,7 @@ struct bpf_verifier_state {
        u32 insn_idx;
        u32 curframe;
 
-       struct bpf_active_lock active_lock;
+       int active_lock;

What about this comment from v3:

Review struct bpf_verifier_state { · line 435

Quoted 1 line
(quoted diff) +1 -0
+       bool active_lock;
Quoted 7 lines

In the next patch it becomes 'int',
so let's make it 'int' right away and move it to bpf_func_state next to:

        int acquired_refs;
        struct bpf_reference_state *refs;

?

Ah, sorry, I somehow missed this part of the comment (twice). Mea culpa.

Quoted 12 lines

wouldn't it be cleaner to keep the count of locks in bpf_func_state next to refs

acquire_lock_state() would increment it and release will dec it.

check_resource_leak() will
instead of:
env->cur_state->active_lock
do:
cur_func(env)->active_lock

Quoted 4 lines

so behavior is the same, but counting of locks is clean.

Since in this patch it's kinda counting locks across all frames which is a bit odd.

Quoted 8 lines

It would work, but we'd need to copy it over to a new frame's bpf_func_state and copy it back on exit.
None of that would matter currently as only one lock can be held, but it would become relevant later.

It's the same situation with reference states. It is inherited from the parent frame for every new frame, and then possibly changed, and then copied back to parent frame.

Exactly, but since we're unifying held locks as references would it make sense to treat them the same way everywhere? active_lock is just a count of held locks in ref state. For refs we do:
if (!exception_exit && state->in_callback_fn && state->refs[i].callback_ref != state->frameno)

Quoted 8 lines

so that
task = task_acquire().
bpf_loop(cb)
task_release(task)
doesn't trip.

Wouldn't we want the same for locks eventually ?

This prompted me to dig into why (I) added that check. Turns out it would no longer be necessary after Eduard fixed callback verification some time ago.
It was a stop gap to prevent certain bad patterns since verifier simulated a callback once. So preventing addition of references from callback, and release of parent references prevented unsafe behavior when callback actually ran N times. Now that's no longer necessary, so I went ahead and dropped all of that cruft from the verifier, and the selftests added back then still failed correctly.

Anyhow, all of it makes sense, so I went ahead and put active_locks as part of bpf_func_state.

Quoted 6 lines

Just if (env->cur_state->active_lock) will change obviously. We may even need two counters for regular and resilient locks ? And in that case two counters in bpf_verifier_state looks even more odd. While two counters in bpf_func_state feels more logical.

Just trying to anticipate the future changes...