[v2,bpf-next,1/2] bpf: Fix release_on_unlock release logic for multiple refs

Commit Message

Dave Marchevsky Dec. 1, 2022, 6:34 p.m. UTC

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 <[e-mail]>
Acked-by: Yonghong Song <[e-mail]>
cc: Kumar Kartikeya Dwivedi <[e-mail]>
Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
---
v1 -> v2 lore.kernel.org/bpf/[e-mail]:

  * 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(-)

Comments

Yonghong Song Dec. 2, 2022, 12:10 a.m. UTC | #1

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 <[e-mail]>
> Acked-by: Yonghong Song <[e-mail]>
> cc: Kumar Kartikeya Dwivedi <[e-mail]>
> Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
> ---
> v1 -> v2 lore.kernel.org/bpf/[e-mail]:
> 
>    * Update second example in patch summary to use a new ref_id for the
>      non-release_on_unlock ref. (Yonghong)
>    * Add Yonghong's ack
[...]

[e-mail] Dec. 2, 2022, 3:50 a.m. UTC | #2

Hello:

This series was applied to bpf/bpf-next.git (master)
by Alexei Starovoitov <[e-mail]>:

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!

Patch

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