* [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs
@ 2022-12-01 18:34 Dave Marchevsky
2022-12-01 18:34 ` [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic Dave Marchevsky
` (2 more replies)
0 siblings, 3 replies; 5+ messages in thread
From: Dave Marchevsky @ 2022-12-01 18:34 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Kernel Team, Yonghong Song, Dave Marchevsky, Yonghong Song,
Kumar Kartikeya Dwivedi
Consider a verifier state with three acquired references, all with
release_on_unlock = true:
idx 0 1 2
state->refs = [2 4 6]
(with 2, 4, and 6 being the ref ids).
When bpf_spin_unlock is called, process_spin_lock will loop through all
acquired_refs and, for each ref, if it's release_on_unlock, calls
release_reference on it. That function in turn calls
release_reference_state, which removes the reference from state->refs by
swapping the reference state with the last reference state in
refs array and decrements acquired_refs count.
process_spin_lock's loop logic, which is essentially:
for (i = 0; i < state->acquired_refs; i++) {
if (!state->refs[i].release_on_unlock)
continue;
release_reference(state->refs[i].id);
}
will fail to release release_on_unlock references which are swapped from
the end. Running this logic on our example demonstrates:
state->refs = [2 4 6] (start of idx=0 iter)
release state->refs[0] by swapping w/ state->refs[2]
state->refs = [6 4] (start of idx=1)
release state->refs[1], no need to swap as it's the last idx
state->refs = [6] (start of idx=2, loop terminates)
ref_id 6 should have been removed but was skipped.
Fix this by looping from back-to-front, which results in refs that are
candidates for removal being swapped with refs which have already been
examined and kept.
If we modify our initial example such that ref 6 is replaced with ref 7,
which is _not_ release_on_unlock, and loop from the back, we'd see:
state->refs = [2 4 7] (start of idx=2)
state->refs = [2 4 7] (start of idx=1)
state->refs = [2 7] (start of idx=0, refs 7 and 4 swapped)
state->refs = [7] (after idx=0, 7 and 2 swapped, loop terminates)
Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
Acked-by: Yonghong Song <yhs@fb.com>
cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
---
v1 -> v2 lore.kernel.org/bpf/b5d46fd5-2693-cd46-9515-700fef1a110b@meta.com:
* Update second example in patch summary to use a new ref_id for the
non-release_on_unlock ref. (Yonghong)
* Add Yonghong's ack
I noticed this while testing ng_ds version of rbtree. Submitting
separately so that this fix can be applied before the rest of rbtree
work, as the latter will likely need a few respins.
An alternative to this fix would be to modify or add new helper
functions which enable safe release_reference in a loop. The additional
complexity of this alternative seems unnecessary to me for now as this
is currently the only place in verifier where release_reference in a
loop is used.
kernel/bpf/verifier.c | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d0ecc0b18b20..b0db9c10567b 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5738,7 +5738,7 @@ static int process_spin_lock(struct bpf_verifier_env *env, int regno,
cur->active_lock.ptr = NULL;
cur->active_lock.id = 0;
- for (i = 0; i < fstate->acquired_refs; i++) {
+ for (i = fstate->acquired_refs - 1; i >= 0; i--) {
int err;
/* Complain on error because this reference state cannot
--
2.30.2
^ permalink raw reply related [flat|nested] 5+ messages in thread
* [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic
2022-12-01 18:34 [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Dave Marchevsky
@ 2022-12-01 18:34 ` Dave Marchevsky
2022-12-02 3:21 ` Yonghong Song
2022-12-02 0:10 ` [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Yonghong Song
2022-12-02 3:50 ` patchwork-bot+netdevbpf
2 siblings, 1 reply; 5+ messages in thread
From: Dave Marchevsky @ 2022-12-01 18:34 UTC (permalink / raw)
To: bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Kernel Team, Yonghong Song, Dave Marchevsky,
Kumar Kartikeya Dwivedi
Modify list_push_pop_multiple to alloc and insert nodes 2-at-a-time.
Without the previous patch's fix, this block of code:
bpf_spin_lock(lock);
bpf_list_push_front(head, &f[i]->node);
bpf_list_push_front(head, &f[i + 1]->node);
bpf_spin_unlock(lock);
would fail check_reference_leak check as release_on_unlock logic would miss
a ref that should've been released.
Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
tools/testing/selftests/bpf/progs/linked_list.c | 17 ++++++++++++++++-
1 file changed, 16 insertions(+), 1 deletion(-)
diff --git a/tools/testing/selftests/bpf/progs/linked_list.c b/tools/testing/selftests/bpf/progs/linked_list.c
index 2c7b615c6d41..4ad88da5cda2 100644
--- a/tools/testing/selftests/bpf/progs/linked_list.c
+++ b/tools/testing/selftests/bpf/progs/linked_list.c
@@ -99,13 +99,28 @@ int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *hea
struct foo *f[8], *pf;
int i;
- for (i = 0; i < ARRAY_SIZE(f); i++) {
+ /* Loop following this check adds nodes 2-at-a-time in order to
+ * validate multiple release_on_unlock release logic
+ */
+ if (ARRAY_SIZE(f) % 2)
+ return 10;
+
+ for (i = 0; i < ARRAY_SIZE(f); i += 2) {
f[i] = bpf_obj_new(typeof(**f));
if (!f[i])
return 2;
f[i]->data = i;
+
+ f[i + 1] = bpf_obj_new(typeof(**f));
+ if (!f[i + 1]) {
+ bpf_obj_drop(f[i]);
+ return 9;
+ }
+ f[i + 1]->data = i + 1;
+
bpf_spin_lock(lock);
bpf_list_push_front(head, &f[i]->node);
+ bpf_list_push_front(head, &f[i + 1]->node);
bpf_spin_unlock(lock);
}
--
2.30.2
^ permalink raw reply related [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs
2022-12-01 18:34 [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Dave Marchevsky
2022-12-01 18:34 ` [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic Dave Marchevsky
@ 2022-12-02 0:10 ` Yonghong Song
2022-12-02 3:50 ` patchwork-bot+netdevbpf
2 siblings, 0 replies; 5+ messages in thread
From: Yonghong Song @ 2022-12-02 0:10 UTC (permalink / raw)
To: Dave Marchevsky, bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Kernel Team, Yonghong Song, Kumar Kartikeya Dwivedi
On 12/1/22 10:34 AM, Dave Marchevsky wrote:
> Consider a verifier state with three acquired references, all with
> release_on_unlock = true:
>
> idx 0 1 2
> state->refs = [2 4 6]
>
> (with 2, 4, and 6 being the ref ids).
>
> When bpf_spin_unlock is called, process_spin_lock will loop through all
> acquired_refs and, for each ref, if it's release_on_unlock, calls
> release_reference on it. That function in turn calls
> release_reference_state, which removes the reference from state->refs by
> swapping the reference state with the last reference state in
> refs array and decrements acquired_refs count.
>
> process_spin_lock's loop logic, which is essentially:
>
> for (i = 0; i < state->acquired_refs; i++) {
> if (!state->refs[i].release_on_unlock)
> continue;
> release_reference(state->refs[i].id);
> }
>
> will fail to release release_on_unlock references which are swapped from
> the end. Running this logic on our example demonstrates:
>
> state->refs = [2 4 6] (start of idx=0 iter)
> release state->refs[0] by swapping w/ state->refs[2]
>
> state->refs = [6 4] (start of idx=1)
> release state->refs[1], no need to swap as it's the last idx
>
> state->refs = [6] (start of idx=2, loop terminates)
>
> ref_id 6 should have been removed but was skipped.
>
> Fix this by looping from back-to-front, which results in refs that are
> candidates for removal being swapped with refs which have already been
> examined and kept.
>
> If we modify our initial example such that ref 6 is replaced with ref 7,
> which is _not_ release_on_unlock, and loop from the back, we'd see:
>
> state->refs = [2 4 7] (start of idx=2)
>
> state->refs = [2 4 7] (start of idx=1)
>
> state->refs = [2 7] (start of idx=0, refs 7 and 4 swapped)
>
> state->refs = [7] (after idx=0, 7 and 2 swapped, loop terminates)
Thanks, new description is much better.
>
> Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
> Acked-by: Yonghong Song <yhs@fb.com>
> cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
> ---
> v1 -> v2 lore.kernel.org/bpf/b5d46fd5-2693-cd46-9515-700fef1a110b@meta.com:
>
> * Update second example in patch summary to use a new ref_id for the
> non-release_on_unlock ref. (Yonghong)
> * Add Yonghong's ack
[...]
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic
2022-12-01 18:34 ` [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic Dave Marchevsky
@ 2022-12-02 3:21 ` Yonghong Song
0 siblings, 0 replies; 5+ messages in thread
From: Yonghong Song @ 2022-12-02 3:21 UTC (permalink / raw)
To: Dave Marchevsky, bpf
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Kernel Team, Kumar Kartikeya Dwivedi
On 12/1/22 10:34 AM, Dave Marchevsky wrote:
> Modify list_push_pop_multiple to alloc and insert nodes 2-at-a-time.
> Without the previous patch's fix, this block of code:
>
> bpf_spin_lock(lock);
> bpf_list_push_front(head, &f[i]->node);
> bpf_list_push_front(head, &f[i + 1]->node);
> bpf_spin_unlock(lock);
>
> would fail check_reference_leak check as release_on_unlock logic would miss
> a ref that should've been released.
>
> Signed-off-by: Dave Marchevsky <davemarchevsky@fb.com>
> cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Acked-by: Yonghong Song <yhs@fb.com>
^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs
2022-12-01 18:34 [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Dave Marchevsky
2022-12-01 18:34 ` [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic Dave Marchevsky
2022-12-02 0:10 ` [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Yonghong Song
@ 2022-12-02 3:50 ` patchwork-bot+netdevbpf
2 siblings, 0 replies; 5+ messages in thread
From: patchwork-bot+netdevbpf @ 2022-12-02 3:50 UTC (permalink / raw)
To: Dave Marchevsky; +Cc: bpf, ast, daniel, andrii, kernel-team, yhs, yhs, memxor
Hello:
This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <ast@kernel.org>:
On Thu, 1 Dec 2022 10:34:05 -0800 you wrote:
> Consider a verifier state with three acquired references, all with
> release_on_unlock = true:
>
> idx 0 1 2
> state->refs = [2 4 6]
>
> (with 2, 4, and 6 being the ref ids).
>
> [...]
Here is the summary with links:
- [v2,bpf-next,1/2] bpf: Fix release_on_unlock release logic for multiple refs
https://git.kernel.org/bpf/bpf-next/c/1f82dffc10ff
- [v2,bpf-next,2/2] selftests/bpf: Validate multiple ref release_on_unlock logic
https://git.kernel.org/bpf/bpf-next/c/78b037bd402d
You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2022-12-02 3:50 UTC | newest]
Thread overview: 5+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-12-01 18:34 [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Dave Marchevsky
2022-12-01 18:34 ` [PATCH v2 bpf-next 2/2] selftests/bpf: Validate multiple ref release_on_unlock logic Dave Marchevsky
2022-12-02 3:21 ` Yonghong Song
2022-12-02 0:10 ` [PATCH v2 bpf-next 1/2] bpf: Fix release_on_unlock release logic for multiple refs Yonghong Song
2022-12-02 3:50 ` patchwork-bot+netdevbpf
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.