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

[Yonghong Song <yhs@meta.com>]

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 <davemarchevsky@fb.com>
> cc: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> 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 <yhs@fb.com>

> 
> 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