[bpf-next,1/2] bpf: hash map, avoid deadlock with suitable hash mask

Commit Message

Tonghao Zhang Dec. 14, 2022, 10:38 a.m. UTC

From: Tonghao Zhang <[e-mail]>

The deadlock still may occur while accessed in NMI and non-NMI
context. Because in NMI, we still may access the same bucket but with
different map_locked index.

For example, on the same CPU, .max_entries = 2, we update the hash map,
with key = 4, while running bpf prog in NMI nmi_handle(), to update
hash map with key = 20, so it will have the same bucket index but have
different map_locked index.

To fix this issue, using min mask to hash again.

Signed-off-by: Tonghao Zhang <[e-mail]>
Cc: Alexei Starovoitov <[e-mail]>
Cc: Daniel Borkmann <[e-mail]>
Cc: Andrii Nakryiko <[e-mail]>
Cc: Martin KaFai Lau <[e-mail]>
Cc: Song Liu <[e-mail]>
Cc: Yonghong Song <[e-mail]>
Cc: John Fastabend <[e-mail]>
Cc: KP Singh <[e-mail]>
Cc: Stanislav Fomichev <[e-mail]>
Cc: Hao Luo <[e-mail]>
Cc: Jiri Olsa <[e-mail]>
Cc: Hou Tao <[e-mail]>
---
 kernel/bpf/hashtab.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

Comments

Yonghong Song Dec. 16, 2022, 3:43 a.m. UTC | #1

On 12/14/22 2:38 AM, [e-mail] wrote:
> From: Tonghao Zhang <[e-mail]>
> 
> The deadlock still may occur while accessed in NMI and non-NMI
> context. Because in NMI, we still may access the same bucket but with
> different map_locked index.
> 
> For example, on the same CPU, .max_entries = 2, we update the hash map,
> with key = 4, while running bpf prog in NMI nmi_handle(), to update
> hash map with key = 20, so it will have the same bucket index but have
> different map_locked index.
> 
> To fix this issue, using min mask to hash again.
> 
> Signed-off-by: Tonghao Zhang <[e-mail]>
> Cc: Alexei Starovoitov <[e-mail]>
> Cc: Daniel Borkmann <[e-mail]>
> Cc: Andrii Nakryiko <[e-mail]>
> Cc: Martin KaFai Lau <[e-mail]>
> Cc: Song Liu <[e-mail]>
> Cc: Yonghong Song <[e-mail]>
> Cc: John Fastabend <[e-mail]>
> Cc: KP Singh <[e-mail]>
> Cc: Stanislav Fomichev <[e-mail]>
> Cc: Hao Luo <[e-mail]>
> Cc: Jiri Olsa <[e-mail]>
> Cc: Hou Tao <[e-mail]>

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

Hou Tao Dec. 16, 2022, 10:15 a.m. UTC | #2

Hi,

On 12/14/2022 6:38 PM, [e-mail] wrote:
> From: Tonghao Zhang <[e-mail]>
>
> The deadlock still may occur while accessed in NMI and non-NMI
> context. Because in NMI, we still may access the same bucket but with
> different map_locked index.
>
> For example, on the same CPU, .max_entries = 2, we update the hash map,
> with key = 4, while running bpf prog in NMI nmi_handle(), to update
> hash map with key = 20, so it will have the same bucket index but have
> different map_locked index.
>
> To fix this issue, using min mask to hash again.
>
> Signed-off-by: Tonghao Zhang <[e-mail]>
> Cc: Alexei Starovoitov <[e-mail]>
> Cc: Daniel Borkmann <[e-mail]>
> Cc: Andrii Nakryiko <[e-mail]>
> Cc: Martin KaFai Lau <[e-mail]>
> Cc: Song Liu <[e-mail]>
> Cc: Yonghong Song <[e-mail]>
> Cc: John Fastabend <[e-mail]>
> Cc: KP Singh <[e-mail]>
> Cc: Stanislav Fomichev <[e-mail]>
> Cc: Hao Luo <[e-mail]>
> Cc: Jiri Olsa <[e-mail]>
> Cc: Hou Tao <[e-mail]>
> ---
>  kernel/bpf/hashtab.c | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 5aa2b5525f79..8b25036a8690 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -152,7 +152,7 @@ static inline int htab_lock_bucket(const struct bpf_htab *htab,
>  {
>  	unsigned long flags;
>  
> -	hash = hash & HASHTAB_MAP_LOCK_MASK;
> +	hash = hash & min(HASHTAB_MAP_LOCK_MASK, htab->n_buckets -1);
There is warning for kernel test robot and it seems that min_t(...) is required
here.

Otherwise, this patch looks good to me, so:

Acked-by: Hou Tao <[e-mail]>
>  
>  	preempt_disable();
>  	if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
> @@ -171,7 +171,7 @@ static inline void htab_unlock_bucket(const struct bpf_htab *htab,
>  				      struct bucket *b, u32 hash,
>  				      unsigned long flags)
>  {
> -	hash = hash & HASHTAB_MAP_LOCK_MASK;
> +	hash = hash & min(HASHTAB_MAP_LOCK_MASK, htab->n_buckets -1);
>  	raw_spin_unlock_irqrestore(&b->raw_lock, flags);
>  	__this_cpu_dec(*(htab->map_locked[hash]));
>  	preempt_enable();

Tonghao Zhang Dec. 16, 2022, 10:31 a.m. UTC | #3

On Fri, Dec 16, 2022 at 6:15 PM Hou Tao <[e-mail]> wrote:
>
> Hi,
>
> On 12/14/2022 6:38 PM, [e-mail] wrote:
> > From: Tonghao Zhang <[e-mail]>
> >
> > The deadlock still may occur while accessed in NMI and non-NMI
> > context. Because in NMI, we still may access the same bucket but with
> > different map_locked index.
> >
> > For example, on the same CPU, .max_entries = 2, we update the hash map,
> > with key = 4, while running bpf prog in NMI nmi_handle(), to update
> > hash map with key = 20, so it will have the same bucket index but have
> > different map_locked index.
> >
> > To fix this issue, using min mask to hash again.
> >
> > Signed-off-by: Tonghao Zhang <[e-mail]>
> > Cc: Alexei Starovoitov <[e-mail]>
> > Cc: Daniel Borkmann <[e-mail]>
> > Cc: Andrii Nakryiko <[e-mail]>
> > Cc: Martin KaFai Lau <[e-mail]>
> > Cc: Song Liu <[e-mail]>
> > Cc: Yonghong Song <[e-mail]>
> > Cc: John Fastabend <[e-mail]>
> > Cc: KP Singh <[e-mail]>
> > Cc: Stanislav Fomichev <[e-mail]>
> > Cc: Hao Luo <[e-mail]>
> > Cc: Jiri Olsa <[e-mail]>
> > Cc: Hou Tao <[e-mail]>
> > ---
> >  kernel/bpf/hashtab.c | 4 ++--
> >  1 file changed, 2 insertions(+), 2 deletions(-)
> >
> > diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> > index 5aa2b5525f79..8b25036a8690 100644
> > --- a/kernel/bpf/hashtab.c
> > +++ b/kernel/bpf/hashtab.c
> > @@ -152,7 +152,7 @@ static inline int htab_lock_bucket(const struct bpf_htab *htab,
> >  {
> >       unsigned long flags;
> >
> > -     hash = hash & HASHTAB_MAP_LOCK_MASK;
> > +     hash = hash & min(HASHTAB_MAP_LOCK_MASK, htab->n_buckets -1);
> There is warning for kernel test robot and it seems that min_t(...) is required
I will send v2 soon. Thanks.
> here.
>
> Otherwise, this patch looks good to me, so:
>
> Acked-by: Hou Tao <[e-mail]>
> >
> >       preempt_disable();
> >       if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
> > @@ -171,7 +171,7 @@ static inline void htab_unlock_bucket(const struct bpf_htab *htab,
> >                                     struct bucket *b, u32 hash,
> >                                     unsigned long flags)
> >  {
> > -     hash = hash & HASHTAB_MAP_LOCK_MASK;
> > +     hash = hash & min(HASHTAB_MAP_LOCK_MASK, htab->n_buckets -1);
> >       raw_spin_unlock_irqrestore(&b->raw_lock, flags);
> >       __this_cpu_dec(*(htab->map_locked[hash]));
> >       preempt_enable();
>

Patch

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 5aa2b5525f79..8b25036a8690 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -152,7 +152,7 @@  static inline int htab_lock_bucket(const struct bpf_htab *htab,
 {
 	unsigned long flags;
 
-	hash = hash & HASHTAB_MAP_LOCK_MASK;
+	hash = hash & min(HASHTAB_MAP_LOCK_MASK, htab->n_buckets -1);
 
 	preempt_disable();
 	if (unlikely(__this_cpu_inc_return(*(htab->map_locked[hash])) != 1)) {
@@ -171,7 +171,7 @@  static inline void htab_unlock_bucket(const struct bpf_htab *htab,
 				      struct bucket *b, u32 hash,
 				      unsigned long flags)
 {
-	hash = hash & HASHTAB_MAP_LOCK_MASK;
+	hash = hash & min(HASHTAB_MAP_LOCK_MASK, htab->n_buckets -1);
 	raw_spin_unlock_irqrestore(&b->raw_lock, flags);
 	__this_cpu_dec(*(htab->map_locked[hash]));
 	preempt_enable();