netdev - Re: [PATCH bpf 1/2] bpf: do not use bucket

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <f93015c5-5fed-4775-93c3-6b85a8e7c0da@fb.com>
Date:   Wed, 2 Sep 2020 19:44:34 -0700
From:   Yonghong Song <yhs@...com>
To:     Andrii Nakryiko <andrii.nakryiko@...il.com>
CC:     bpf <bpf@...r.kernel.org>, Lorenz Bauer <lmb@...udflare.com>,
        Martin KaFai Lau <kafai@...com>,
        Networking <netdev@...r.kernel.org>,
        Alexei Starovoitov <ast@...com>,
        Daniel Borkmann <daniel@...earbox.net>,
        Kernel Team <kernel-team@...com>
Subject: Re: [PATCH bpf 1/2] bpf: do not use bucket_lock for hashmap iterator



On 9/2/20 6:25 PM, Andrii Nakryiko wrote:
> On Wed, Sep 2, 2020 at 4:56 PM Yonghong Song <yhs@...com> wrote:
>>
>> Currently, for hashmap, the bpf iterator will grab a bucket lock, a
>> spinlock, before traversing the elements in the bucket. This can ensure
>> all bpf visted elements are valid. But this mechanism may cause
>> deadlock if update/deletion happens to the same bucket of the
>> visited map in the program. For example, if we added bpf_map_update_elem()
>> call to the same visited element in selftests bpf_iter_bpf_hash_map.c,
>> we will have the following deadlock:
>>
> 
> [...]
> 
>>
>> Compared to old bucket_lock mechanism, if concurrent updata/delete happens,
>> we may visit stale elements, miss some elements, or repeat some elements.
>> I think this is a reasonable compromise. For users wanting to avoid
> 
> I agree, the only reliable way to iterate map without duplicates and
> missed elements is to not update that map during iteration (unless we
> start supporting point-in-time snapshots, which is a very different
> matter).
> 
> 
>> stale, missing/repeated accesses, bpf_map batch access syscall interface
>> can be used.
>>
>> Signed-off-by: Yonghong Song <yhs@...com>
>> ---
>>   kernel/bpf/hashtab.c | 15 ++++-----------
>>   1 file changed, 4 insertions(+), 11 deletions(-)
>>
>> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
>> index 78dfff6a501b..7df28a45c66b 100644
>> --- a/kernel/bpf/hashtab.c
>> +++ b/kernel/bpf/hashtab.c
>> @@ -1622,7 +1622,6 @@ struct bpf_iter_seq_hash_map_info {
>>          struct bpf_map *map;
>>          struct bpf_htab *htab;
>>          void *percpu_value_buf; // non-zero means percpu hash
>> -       unsigned long flags;
>>          u32 bucket_id;
>>          u32 skip_elems;
>>   };
>> @@ -1632,7 +1631,6 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,
>>                             struct htab_elem *prev_elem)
>>   {
>>          const struct bpf_htab *htab = info->htab;
>> -       unsigned long flags = info->flags;
>>          u32 skip_elems = info->skip_elems;
>>          u32 bucket_id = info->bucket_id;
>>          struct hlist_nulls_head *head;
>> @@ -1656,19 +1654,18 @@ bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info,
>>
>>                  /* not found, unlock and go to the next bucket */
>>                  b = &htab->buckets[bucket_id++];
>> -               htab_unlock_bucket(htab, b, flags);
>> +               rcu_read_unlock();
> 
> Just double checking as I don't yet completely understand all the
> sleepable BPF implications. If the map is used from a sleepable BPF
> program, we are still ok doing just rcu_read_lock/rcu_read_unlock when
> accessing BPF map elements, right? No need for extra
> rcu_read_lock_trace/rcu_read_unlock_trace?
I think it is fine now since currently bpf_iter program cannot be 
sleepable and the current sleepable program framework already allows the 
following scenario.
   - map1 is a preallocated hashmap shared by two programs,
     prog1_nosleep and prog2_sleepable

...				  ...
rcu_read_lock()			  rcu_read_lock_trace()
run prog1_nosleep                 run prog2_sleepable
   lookup/update/delete map1 elem    lookup/update/delete map1 elem
rcu_read_unlock()		  rcu_read_unlock_trace()
...				  ...

The prog1_nosleep could be a bpf_iter program or a networking problem.

Alexei, could you confirm the above scenario is properly supported now?

> 
>>                  skip_elems = 0;
>>          }
>>
> 
> [...]
>