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..
