Subject: Re: [PATCH bpf-next 1/2] bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map

From: Eric Dumazet <[email-masked]>
Date: Thu, 25 Jan 2018 20:47:33 -0800

On Thu, 2018-01-18 at 15:08 -0800, Yonghong Song wrote:

> +find_leftmost:
> +	/* Find the leftmost non-intermediate node, all intermediate nodes
> +	 * have exact two children, so this function will never return NULL.
> +	 */

syzbot [1] disagrees violently with this comment.

> +	for (node = rcu_dereference(*root); node;) {
> +		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
> +			next_node = node;
> +		node = rcu_dereference(node->child[0]);
> +	}
> +do_copy:
> +	next_key->prefixlen = next_node->prefixlen;
> +	memcpy((void *)next_key + offsetof(struct bpf_lpm_trie_key, data),
> +	       next_node->data, trie->data_size);

[1]

syzbot hit the following crash on e9dcd80b9d77a92bfae6ce42a451f5c5fd318832
git://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
config: https://syzkaller-buganizer.googleplex.com/text?tag=Config&id=b2216f04db2aa337e2bbf5ebd233919c3e2aa05f
compiler: gcc (GCC) 7.1.1 20170620

Unfortunately, I don't have any reproducer for this bug yet.
raw crash log: https://syzkaller-buganizer.googleplex.com/text?tag=CrashLog&id=4f78be02e2cd37040b8796322e02b147caae6024
dashboard link: https://syzkaller.appspot.com/bug?extid=148b56534d9269ab7433

See http://go/syzbot for details on how to handle this bug.

kasan: CONFIG_KASAN_INLINE enabled
kasan: GPF could be caused by NULL-ptr deref or user memory access
general protection fault: 0000 [#1] SMP KASAN
Dumping ftrace buffer:
   (ftrace buffer empty)
Modules linked in:
CPU: 1 PID: 8033 Comm: syz-executor3 Not tainted 4.15.0-rc8+ #4
Hardware name: Google Google Compute Engine/Google Compute Engine, BIOS Google 01/01/2011
RIP: 0010:trie_get_next_key+0x3c2/0xf10 kernel/bpf/lpm_trie.c:682
RSP: 0018:ffff8801aa44f628 EFLAGS: 00010202
RAX: dffffc0000000000 RBX: 0000000000000000 RCX: ffffffff81829a9d
RDX: 0000000000000004 RSI: ffffc90003b7b000 RDI: 0000000000000020
RBP: ffff8801aa44f8b0 R08: ffffffff817e8f95 R09: 0000000000000002
R10: ffff8801aa44f790 R11: 0000000000000000 R12: 0000000000000000
R13: 1ffff10035489f01 R14: fffffffffffffff4 R15: 0000000000000000
FS:  00007fbb3b39b700(0000) GS:ffff8801db300000(0000) knlGS:0000000000000000
CS:  0010 DS: 0000 ES: 0000 CR0: 0000000080050033
CR2: 000000002057a000 CR3: 00000001c26e4005 CR4: 00000000001606e0
DR0: 0000000000000000 DR1: 0000000000000000 DR2: 0000000000000000
DR3: 0000000000000000 DR6: 00000000fffe0ff0 DR7: 0000000000000400
Call Trace:
 map_get_next_key kernel/bpf/syscall.c:842 [inline]
 SYSC_bpf kernel/bpf/syscall.c:1881 [inline]
 SyS_bpf+0x11b4/0x4860 kernel/bpf/syscall.c:1846
 entry_SYSCALL_64_fastpath+0x29/0xa0
RIP: 0033:0x452f19
RSP: 002b:00007fbb3b39ac58 EFLAGS: 00000212 ORIG_RAX: 0000000000000141
RAX: ffffffffffffffda RBX: 000000000071bea0 RCX: 0000000000452f19
RDX: 0000000000000018 RSI: 0000000020daf000 RDI: 0000000000000004
RBP: 000000000000003e R08: 0000000000000000 R09: 0000000000000000
R10: 0000000000000000 R11: 0000000000000212 R12: 00000000006ef670
R13: 00000000ffffffff R14: 00007fbb3b39b6d4 R15: 0000000000000000
Code: 19 d3 ff e8 81 98 ed ff 4d 85 e4 0f 85 30 ff ff ff e8 73 98 ed ff 49 8d 7f 20 48 b8 00 00 00 00 00 fc ff df 48 89 fa 48 c1 ea 03 <0f> b6 04 02 84 c0 74 08 3c 03 0f 8e f2 0a 00 00 48 8b b5 98 fd 
RIP: trie_get_next_key+0x3c2/0xf10 kernel/bpf/lpm_trie.c:682 RSP: ffff8801aa44f628
---[ end trace b4eb675edf4c4059 ]---
Kernel panic - not syncing: Fatal exception
Dumping ftrace buffer:
   (ftrace buffer empty)
Kernel Offset: disabled
Rebooting in 86400 seconds..