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

Commit Message

Dave Marchevsky Nov. 30, 2022, 7:25 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
not release_on_unlock and loop from the back, we'd see:

  state->refs = [2 4 6] (start of idx=2)

  state->refs = [2 4 6] (start of idx=1)

  state->refs = [2 6]   (start of idx=0)

  state->refs = [6]     (after idx=0, loop terminates)

Signed-off-by: Dave Marchevsky <[e-mail]>
cc: Kumar Kartikeya Dwivedi <[e-mail]>
Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
---

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. 1, 2022, 3:21 a.m. UTC | #1

On 11/30/22 11:25 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
> not release_on_unlock and loop from the back, we'd see:
> 
>    state->refs = [2 4 6] (start of idx=2)
> 
>    state->refs = [2 4 6] (start of idx=1)
> 
>    state->refs = [2 6]   (start of idx=0)
> 
>    state->refs = [6]     (after idx=0, loop terminates)

I am not sure whether the above is correct or not. Should it be:

     state->refs = [2 4 6] (idx=2)
       => release state->refs[2] (id 6)
     state->refs = [2 4] (idx=1)
       => release state->refs[1] (id 4)
     state->refs = [2] (idx = 0)
       => release state->refs[0] (id 2)
?

> 
> Signed-off-by: Dave Marchevsky <[e-mail]>
> cc: Kumar Kartikeya Dwivedi <[e-mail]>
> Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
> ---
> 
> 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(-)

The code change itself looks good to me, so

Acked-by: Yonghong Song <[e-mail]>

> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 4e7f1d085e53..ac3e1219a7a5 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -5726,7 +5726,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

Dave Marchevsky Dec. 1, 2022, 6:19 p.m. UTC | #2

On 11/30/22 7:21 PM, Yonghong Song wrote:
> 
> 
> On 11/30/22 11:25 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
>> not release_on_unlock and loop from the back, we'd see:
>>
>>    state->refs = [2 4 6] (start of idx=2)
>>
>>    state->refs = [2 4 6] (start of idx=1)
>>
>>    state->refs = [2 6]   (start of idx=0)
>>
>>    state->refs = [6]     (after idx=0, loop terminates)
> 
> I am not sure whether the above is correct or not. Should it be:
> 
>     state->refs = [2 4 6] (idx=2)
>       => release state->refs[2] (id 6)
>     state->refs = [2 4] (idx=1)
>       => release state->refs[1] (id 4)
>     state->refs = [2] (idx = 0)
>       => release state->refs[0] (id 2)
> ?
>
For this second example, the ref with id 6 is not release_on_unlock while the
others are. So that ref should not be released and should be the only one
remaining after the loop completes. This was intended to demonstrate the
swapping of "refs which have already been examined and kept".

It would be less confusing if I used a new ref_id for the second example
instead of changing the properties of ref 6. Will respin with this change.

>>
>> Signed-off-by: Dave Marchevsky <[e-mail]>
>> cc: Kumar Kartikeya Dwivedi <[e-mail]>
>> Fixes: 534e86bc6c66 ("bpf: Add 'release on unlock' logic for bpf_list_push_{front,back}")
>> ---
>>
>> 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(-)
> 
> The code change itself looks good to me, so
> 
> Acked-by: Yonghong Song <[e-mail]>
> 
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 4e7f1d085e53..ac3e1219a7a5 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -5726,7 +5726,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

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4e7f1d085e53..ac3e1219a7a5 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -5726,7 +5726,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