On Wed, Feb 19, 2020 at 11:50 AM Martin KaFai Lau <kafai@xxxxxx> wrote:
>
> On Wed, Feb 19, 2020 at 11:31:06AM -0800, Yonghong Song wrote:
> > Commit 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> > added lookup_and_delete batch operation for hash table.
> > The current implementation has bpf_lru_push_free() inside
> > the bucket lock, which may cause a deadlock.
> >
> > syzbot reports:
> > -> #2 (&htab->buckets[i].lock#2){....}:
> > __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
> > _raw_spin_lock_irqsave+0x95/0xcd kernel/locking/spinlock.c:159
> > htab_lru_map_delete_node+0xce/0x2f0 kernel/bpf/hashtab.c:593
> > __bpf_lru_list_shrink_inactive kernel/bpf/bpf_lru_list.c:220 [inline]
> > __bpf_lru_list_shrink+0xf9/0x470 kernel/bpf/bpf_lru_list.c:266
> > bpf_lru_list_pop_free_to_local kernel/bpf/bpf_lru_list.c:340 [inline]
> > bpf_common_lru_pop_free kernel/bpf/bpf_lru_list.c:447 [inline]
> > bpf_lru_pop_free+0x87c/0x1670 kernel/bpf/bpf_lru_list.c:499
> > prealloc_lru_pop+0x2c/0xa0 kernel/bpf/hashtab.c:132
> > __htab_lru_percpu_map_update_elem+0x67e/0xa90 kernel/bpf/hashtab.c:1069
> > bpf_percpu_hash_update+0x16e/0x210 kernel/bpf/hashtab.c:1585
> > bpf_map_update_value.isra.0+0x2d7/0x8e0 kernel/bpf/syscall.c:181
> > generic_map_update_batch+0x41f/0x610 kernel/bpf/syscall.c:1319
> > bpf_map_do_batch+0x3f5/0x510 kernel/bpf/syscall.c:3348
> > __do_sys_bpf+0x9b7/0x41e0 kernel/bpf/syscall.c:3460
> > __se_sys_bpf kernel/bpf/syscall.c:3355 [inline]
> > __x64_sys_bpf+0x73/0xb0 kernel/bpf/syscall.c:3355
> > do_syscall_64+0xfa/0x790 arch/x86/entry/common.c:294
> > entry_SYSCALL_64_after_hwframe+0x49/0xbe
> >
> > -> #0 (&loc_l->lock){....}:
> > check_prev_add kernel/locking/lockdep.c:2475 [inline]
> > check_prevs_add kernel/locking/lockdep.c:2580 [inline]
> > validate_chain kernel/locking/lockdep.c:2970 [inline]
> > __lock_acquire+0x2596/0x4a00 kernel/locking/lockdep.c:3954
> > lock_acquire+0x190/0x410 kernel/locking/lockdep.c:4484
> > __raw_spin_lock_irqsave include/linux/spinlock_api_smp.h:110 [inline]
> > _raw_spin_lock_irqsave+0x95/0xcd kernel/locking/spinlock.c:159
> > bpf_common_lru_push_free kernel/bpf/bpf_lru_list.c:516 [inline]
> > bpf_lru_push_free+0x250/0x5b0 kernel/bpf/bpf_lru_list.c:555
> > __htab_map_lookup_and_delete_batch+0x8d4/0x1540 kernel/bpf/hashtab.c:1374
> > htab_lru_map_lookup_and_delete_batch+0x34/0x40 kernel/bpf/hashtab.c:1491
> > bpf_map_do_batch+0x3f5/0x510 kernel/bpf/syscall.c:3348
> > __do_sys_bpf+0x1f7d/0x41e0 kernel/bpf/syscall.c:3456
> > __se_sys_bpf kernel/bpf/syscall.c:3355 [inline]
> > __x64_sys_bpf+0x73/0xb0 kernel/bpf/syscall.c:3355
> > do_syscall_64+0xfa/0x790 arch/x86/entry/common.c:294
> > entry_SYSCALL_64_after_hwframe+0x49/0xbe
> >
> > Possible unsafe locking scenario:
> >
> > CPU0 CPU2
> > ---- ----
> > lock(&htab->buckets[i].lock#2);
> > lock(&l->lock);
> > lock(&htab->buckets[i].lock#2);
> > lock(&loc_l->lock);
> >
> > *** DEADLOCK ***
> >
> > To fix the issue, for htab_lru_map_lookup_and_delete_batch() in CPU0,
> > let us do bpf_lru_push_free() out of the htab bucket lock. This can
> > avoid the above deadlock scenario.
> >
> > Fixes: 057996380a42 ("bpf: Add batch ops to all htab bpf map")
> > Reported-by: syzbot+a38ff3d9356388f2fb83@xxxxxxxxxxxxxxxxxxxxxxxxx
> > Reported-by: syzbot+122b5421d14e68f29cd1@xxxxxxxxxxxxxxxxxxxxxxxxx
> > Suggested-by: Hillf Danton <hdanton@xxxxxxxx>
> > Suggested-by: Martin KaFai Lau <kafai@xxxxxx>
> > Acked-by: Brian Vazquez <brianvv@xxxxxxxxxx>
> > Reviewed-by: Jakub Sitnicki <jakub@xxxxxxxxxxxxxx>
> > Signed-off-by: Yonghong Song <yhs@xxxxxx>
> > ---
> > kernel/bpf/hashtab.c | 34 +++++++++++++++++++++++++++++++---
> > 1 file changed, 31 insertions(+), 3 deletions(-)
> >
> > Changelog:
> > v2 -> v3:
> > . changed variable name, fixed reverse Christmas tree
> > coding style and added more comments, from Martin.
> Acked-by: Martin KaFai Lau <kafai@xxxxxx>
It conflicts with Brian's fix. Please respin.
