Date:   Fri, 26 Jan 2018 08:50:31 -0800
From:   Yonghong Song <yhs@...com>
To:     Eric Dumazet <eric.dumazet@...il.com>, <ast@...com>,
        <daniel@...earbox.net>, <netdev@...r.kernel.org>
CC:     <kernel-team@...com>
Subject: Re: [PATCH bpf-next 1/2] bpf: implement MAP_GET_NEXT_KEY command for
 LPM_TRIE map



On 1/25/18 8:47 PM, Eric Dumazet wrote:
> 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);

Thanks for reporting the issue. I looked at the update and delete code 
in lpm_trie.c, it looks the comment that each intermediate node has two 
children still holds. But I do find a problem:

616         /* Empty trie */
617         if (!rcu_dereference(trie->root))
618                 return -ENOENT;
619
620         /* For invalid key, find the leftmost node in the trie */
621         if (!key || key->prefixlen > trie->max_prefixlen) {
622                 root = &trie->root;
623                 goto find_leftmost;
624         }
......
672 find_leftmost:
673         /* Find the leftmost non-intermediate node, all intermediate 
nodes
674          * have exact two children, so this function will never 
return NULL.
675          */
676         for (node = rcu_dereference(*root); node;) {
677                 if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
678                         next_node = node;
679                 node = rcu_dereference(node->child[0]);
680         }

It is possible that at line 617, trie->root is not NULL, but
later at line 676 is NULL. This will lead to next_node is NULL.

Will write a test to demonstrate this and examine intermediate node
property and propose a fix soon.

> 
> [1]
> 
> syzbot hit the following crash on e9dcd80b9d77a92bfae6ce42a451f5c5fd318832
> git://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
> config: https://urldefense.proofpoint.com/v2/url?u=https-3A__syzkaller-2Dbuganizer.googleplex.com_text-3Ftag-3DConfig-26id-3Db2216f04db2aa337e2bbf5ebd233919c3e2aa05f&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=aHeuptD-ytpgZCGZK_koCI1pUdJBACYveZ3RmN35g90&e=
> compiler: gcc (GCC) 7.1.1 20170620
> 
> 
> Unfortunately, I don't have any reproducer for this bug yet.
> raw crash log: https://urldefense.proofpoint.com/v2/url?u=https-3A__syzkaller-2Dbuganizer.googleplex.com_text-3Ftag-3DCrashLog-26id-3D4f78be02e2cd37040b8796322e02b147caae6024&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=RS0jaMd3n5ipeDtuFCL8B0152mZoHBx0b8xNq9AjDes&e=
> dashboard link: https://urldefense.proofpoint.com/v2/url?u=https-3A__syzkaller.appspot.com_bug-3Fextid-3D148b56534d9269ab7433&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=6L_1a0P1zZJmhAN49_cgfs8_LjnBW7h4L-SXEFF4orc&e=
> 
> See https://urldefense.proofpoint.com/v2/url?u=http-3A__go_syzbot&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=i6WobKxbeG3slzHSIOxTVtYIJw7qjCE6S0spDTKL-J4&m=RlBFk8FZhgGNl21aXGyx6UTYgjRdx0JLPJJXuREGo_c&s=iajwDJDDZzMqC0CxPLANoybk0lVIpuh2r7pz0rcD8kI&e= 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..
> 

Powered by blists - more mailing lists