[PATCH bpf-next 0/2] bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map

[PATCH bpf-next 0/2] bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map

[Yonghong Song]

This patch set implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
This command is really useful for key enumeration, and for key deletion
if what keys in the trie are unknown.

Patch #1 implements the functionality in the kernel and patch #2
adds a test case in tools/testing/selftests/bpf.

Yonghong Song (2):
  bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map
  tools/bpf: add a testcase for MAP_GET_NEXT_KEY command of LPM_TRIE map

 kernel/bpf/lpm_trie.c                      |  95 +++++++++++++++++++++-
 tools/testing/selftests/bpf/test_lpm_map.c | 122 +++++++++++++++++++++++++++++
 2 files changed, 215 insertions(+), 2 deletions(-)

-- 
2.9.5

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

[Yonghong Song]

Current LPM_TRIE map type does not implement MAP_GET_NEXT_KEY
command. This command is handy when users want to enumerate
keys. Otherwise, a different map which supports key
enumeration may be required to store the keys. If the
map data is sparse and all map data are to be deleted without
closing file descriptor, using MAP_GET_NEXT_KEY to find
all keys is much faster than enumerating all key space.

This patch implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
If user provided key pointer is NULL or the key does not have
an exact match in the trie, the first key will be returned.
Otherwise, the next key will be returned.

In this implemenation, key enumeration follows a postorder
traversal of internal trie. More specific keys
will be returned first than less specific ones, given
a sequence of MAP_GET_NEXT_KEY syscalls.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/lpm_trie.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 93 insertions(+), 2 deletions(-)

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 584e022..d7ea962 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -591,9 +591,100 @@ static void trie_free(struct bpf_map *map)
 	raw_spin_unlock(&trie->lock);
 }
 
-static int trie_get_next_key(struct bpf_map *map, void *key, void *next_key)
+static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 {
-	return -ENOTSUPP;
+	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
+	struct bpf_lpm_trie_key *key = _key, *next_key = _next_key;
+	struct lpm_trie_node *node, *next_node = NULL, *parent;
+	struct lpm_trie_node **node_stack = NULL;
+	struct lpm_trie_node __rcu **root;
+	int err = 0, stack_ptr = -1;
+	unsigned int next_bit;
+	size_t matchlen;
+
+	/* The get_next_key follows postorder. For the 4 node example in
+	 * the top of this file, the trie_get_next_key() returns the following
+	 * one after another:
+	 *   192.168.0.0/24
+	 *   192.168.1.0/24
+	 *   192.168.128.0/24
+	 *   192.168.0.0/16
+	 *
+	 * The idea is to return more specific keys before less specific ones.
+	 */
+
+	/* Empty trie */
+	if (!rcu_dereference(trie->root))
+		return -ENOENT;
+
+	/* For invalid key, find the leftmost node in the trie */
+	if (!key || key->prefixlen > trie->max_prefixlen) {
+		root = &trie->root;
+		goto find_leftmost;
+	}
+
+	node_stack = kmalloc(trie->max_prefixlen * sizeof(struct lpm_trie_node *),
+			     GFP_USER | __GFP_NOWARN);
+	if (!node_stack)
+		return -ENOMEM;
+
+	/* Try to find the exact node for the given key */
+	for (node = rcu_dereference(trie->root); node;) {
+		node_stack[++stack_ptr] = node;
+		matchlen = longest_prefix_match(trie, node, key);
+		if (node->prefixlen != matchlen ||
+		    node->prefixlen == key->prefixlen)
+			break;
+
+		next_bit = extract_bit(key->data, node->prefixlen);
+		node = rcu_dereference(node->child[next_bit]);
+	}
+	if (!node || node->prefixlen != key->prefixlen ||
+	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {
+		root = &trie->root;
+		goto find_leftmost;
+	}
+
+	/* The node with the exactly-matching key has been found,
+	 * find the first node in postorder after the matched node.
+	 */
+	node = node_stack[stack_ptr];
+	while (stack_ptr > 0) {
+		parent = node_stack[stack_ptr - 1];
+		if (rcu_dereference(parent->child[0]) == node &&
+		    rcu_dereference(parent->child[1])) {
+			root = &parent->child[1];
+			goto find_leftmost;
+		}
+		if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) {
+			next_node = parent;
+			goto do_copy;
+		}
+
+		node = parent;
+		stack_ptr--;
+	}
+
+	/* did not find anything */
+	err = -ENOENT;
+	goto free_stack;
+
+find_leftmost:
+	/* Find the leftmost non-intermediate node, all intermediate nodes
+	 * have exact two children, so this function will never return NULL.
+	 */
+	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);
+free_stack:
+	kfree(node_stack);
+	return err;
 }
 
 const struct bpf_map_ops trie_map_ops = {
-- 
2.9.5

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

[Eric Dumazet]

On Thu, 2018-01-18 at 15:08 -0800, Yonghong Song wrote:
> Current LPM_TRIE map type does not implement MAP_GET_NEXT_KEY
> command. This command is handy when users want to enumerate
> keys. Otherwise, a different map which supports key
> enumeration may be required to store the keys. If the
> map data is sparse and all map data are to be deleted without
> closing file descriptor, using MAP_GET_NEXT_KEY to find
> all keys is much faster than enumerating all key space.
> 
> This patch implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
> If user provided key pointer is NULL or the key does not have
> an exact match in the trie, the first key will be returned.
> Otherwise, the next key will be returned.
> 
> In this implemenation, key enumeration follows a postorder
> traversal of internal trie. More specific keys
> will be returned first than less specific ones, given
> a sequence of MAP_GET_NEXT_KEY syscalls.
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>
> ---
>  kernel/bpf/lpm_trie.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 93 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
> index 584e022..d7ea962 100644
> --- a/kernel/bpf/lpm_trie.c
> +++ b/kernel/bpf/lpm_trie.c
> @@ -591,9 +591,100 @@ static void trie_free(struct bpf_map *map)
>  	raw_spin_unlock(&trie->lock);
>  }
>  
> -static int trie_get_next_key(struct bpf_map *map, void *key, void *next_key)
> +static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
>  {
> -	return -ENOTSUPP;
> +	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
> +	struct bpf_lpm_trie_key *key = _key, *next_key = _next_key;
> +	struct lpm_trie_node *node, *next_node = NULL, *parent;
> +	struct lpm_trie_node **node_stack = NULL;
> +	struct lpm_trie_node __rcu **root;
> +	int err = 0, stack_ptr = -1;
> +	unsigned int next_bit;
> +	size_t matchlen;
> +
> +	/* The get_next_key follows postorder. For the 4 node example in
> +	 * the top of this file, the trie_get_next_key() returns the following
> +	 * one after another:
> +	 *   192.168.0.0/24
> +	 *   192.168.1.0/24
> +	 *   192.168.128.0/24
> +	 *   192.168.0.0/16
> +	 *
> +	 * The idea is to return more specific keys before less specific ones.
> +	 */
> +
> +	/* Empty trie */
> +	if (!rcu_dereference(trie->root))
> +		return -ENOENT;
> +
> +	/* For invalid key, find the leftmost node in the trie */
> +	if (!key || key->prefixlen > trie->max_prefixlen) {
> +		root = &trie->root;
> +		goto find_leftmost;
> +	}
> +
> +	node_stack = kmalloc(trie->max_prefixlen * sizeof(struct lpm_trie_node *),
> +			     GFP_USER | __GFP_NOWARN);

It is illegal to use a blocking kmalloc() while holding RCU.

CONFIG_DEBUG_ATOMIC_SLEEP=y is your friend

> +	if (!node_stack)
> +		return -ENOMEM;
> +
> +	/* Try to find the exact node for the given key */
> +	for (node = rcu_dereference(trie->root); node;) {
> +		node_stack[++stack_ptr] = node;
> +		matchlen = longest_prefix_match(trie, node, key);
> +		if (node->prefixlen != matchlen ||
> +		    node->prefixlen == key->prefixlen)
> +			break;
> +
> +		next_bit = extract_bit(key->data, node->prefixlen);
> +		node = rcu_dereference(node->child[next_bit]);
> +	}
> +	if (!node || node->prefixlen != key->prefixlen ||
> +	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {
> +		root = &trie->root;
> +		goto find_leftmost;
> +	}
> +
> +	/* The node with the exactly-matching key has been found,
> +	 * find the first node in postorder after the matched node.
> +	 */
> +	node = node_stack[stack_ptr];
> +	while (stack_ptr > 0) {
> +		parent = node_stack[stack_ptr - 1];
> +		if (rcu_dereference(parent->child[0]) == node &&
> +		    rcu_dereference(parent->child[1])) {
> +			root = &parent->child[1];
> +			goto find_leftmost;
> +		}
> +		if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) {
> +			next_node = parent;
> +			goto do_copy;
> +		}
> +
> +		node = parent;
> +		stack_ptr--;
> +	}
> +
> +	/* did not find anything */
> +	err = -ENOENT;
> +	goto free_stack;
> +
> +find_leftmost:
> +	/* Find the leftmost non-intermediate node, all intermediate nodes
> +	 * have exact two children, so this function will never return NULL.
> +	 */
> +	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);
> +free_stack:
> +	kfree(node_stack);
> +	return err;
>  }
>  
>  const struct bpf_map_ops trie_map_ops = {

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

[Yonghong Song]

On 1/22/18 11:28 AM, Eric Dumazet wrote:
> On Thu, 2018-01-18 at 15:08 -0800, Yonghong Song wrote:
>> Current LPM_TRIE map type does not implement MAP_GET_NEXT_KEY
>> command. This command is handy when users want to enumerate
>> keys. Otherwise, a different map which supports key
>> enumeration may be required to store the keys. If the
>> map data is sparse and all map data are to be deleted without
>> closing file descriptor, using MAP_GET_NEXT_KEY to find
>> all keys is much faster than enumerating all key space.
>>
>> This patch implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
>> If user provided key pointer is NULL or the key does not have
>> an exact match in the trie, the first key will be returned.
>> Otherwise, the next key will be returned.
>>
>> In this implemenation, key enumeration follows a postorder
>> traversal of internal trie. More specific keys
>> will be returned first than less specific ones, given
>> a sequence of MAP_GET_NEXT_KEY syscalls.
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
>> ---
>>   kernel/bpf/lpm_trie.c | 95 +++++++++++++++++++++++++++++++++++++++++++++++++--
>>   1 file changed, 93 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
>> index 584e022..d7ea962 100644
>> --- a/kernel/bpf/lpm_trie.c
>> +++ b/kernel/bpf/lpm_trie.c
>> @@ -591,9 +591,100 @@ static void trie_free(struct bpf_map *map)
>>   	raw_spin_unlock(&trie->lock);
>>   }
>>   
>> -static int trie_get_next_key(struct bpf_map *map, void *key, void *next_key)
>> +static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
>>   {
>> -	return -ENOTSUPP;
>> +	struct lpm_trie *trie = container_of(map, struct lpm_trie, map);
>> +	struct bpf_lpm_trie_key *key = _key, *next_key = _next_key;
>> +	struct lpm_trie_node *node, *next_node = NULL, *parent;
>> +	struct lpm_trie_node **node_stack = NULL;
>> +	struct lpm_trie_node __rcu **root;
>> +	int err = 0, stack_ptr = -1;
>> +	unsigned int next_bit;
>> +	size_t matchlen;
>> +
>> +	/* The get_next_key follows postorder. For the 4 node example in
>> +	 * the top of this file, the trie_get_next_key() returns the following
>> +	 * one after another:
>> +	 *   192.168.0.0/24
>> +	 *   192.168.1.0/24
>> +	 *   192.168.128.0/24
>> +	 *   192.168.0.0/16
>> +	 *
>> +	 * The idea is to return more specific keys before less specific ones.
>> +	 */
>> +
>> +	/* Empty trie */
>> +	if (!rcu_dereference(trie->root))
>> +		return -ENOENT;
>> +
>> +	/* For invalid key, find the leftmost node in the trie */
>> +	if (!key || key->prefixlen > trie->max_prefixlen) {
>> +		root = &trie->root;
>> +		goto find_leftmost;
>> +	}
>> +
>> +	node_stack = kmalloc(trie->max_prefixlen * sizeof(struct lpm_trie_node *),
>> +			     GFP_USER | __GFP_NOWARN);
> 
> It is illegal to use a blocking kmalloc() while holding RCU.
> 
> CONFIG_DEBUG_ATOMIC_SLEEP=y is your friend

Thanks Eric for spotting the problem. Will fix the issue soon.

> 
>> +	if (!node_stack)
>> +		return -ENOMEM;
>> +
>> +	/* Try to find the exact node for the given key */
>> +	for (node = rcu_dereference(trie->root); node;) {
>> +		node_stack[++stack_ptr] = node;
>> +		matchlen = longest_prefix_match(trie, node, key);
>> +		if (node->prefixlen != matchlen ||
>> +		    node->prefixlen == key->prefixlen)
>> +			break;
>> +
>> +		next_bit = extract_bit(key->data, node->prefixlen);
>> +		node = rcu_dereference(node->child[next_bit]);
>> +	}
>> +	if (!node || node->prefixlen != key->prefixlen ||
>> +	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {
>> +		root = &trie->root;
>> +		goto find_leftmost;
>> +	}
>> +
>> +	/* The node with the exactly-matching key has been found,
>> +	 * find the first node in postorder after the matched node.
>> +	 */
>> +	node = node_stack[stack_ptr];
>> +	while (stack_ptr > 0) {
>> +		parent = node_stack[stack_ptr - 1];
>> +		if (rcu_dereference(parent->child[0]) == node &&
>> +		    rcu_dereference(parent->child[1])) {
>> +			root = &parent->child[1];
>> +			goto find_leftmost;
>> +		}
>> +		if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) {
>> +			next_node = parent;
>> +			goto do_copy;
>> +		}
>> +
>> +		node = parent;
>> +		stack_ptr--;
>> +	}
>> +
>> +	/* did not find anything */
>> +	err = -ENOENT;
>> +	goto free_stack;
>> +
>> +find_leftmost:
>> +	/* Find the leftmost non-intermediate node, all intermediate nodes
>> +	 * have exact two children, so this function will never return NULL.
>> +	 */
>> +	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);
>> +free_stack:
>> +	kfree(node_stack);
>> +	return err;
>>   }
>>   
>>   const struct bpf_map_ops trie_map_ops = {

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

[Eric Dumazet]

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

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

[Yonghong Song]

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

[PATCH bpf-next 2/2] tools/bpf: add a testcase for MAP_GET_NEXT_KEY command of LPM_TRIE map

[Yonghong Song]

A test case is added in tools/testing/selftests/bpf/test_lpm_map.c
for MAP_GET_NEXT_KEY command. A four node trie, which
is described in kernel/bpf/lpm_trie.c, is built and the
MAP_GET_NEXT_KEY results are checked.

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 tools/testing/selftests/bpf/test_lpm_map.c | 122 +++++++++++++++++++++++++++++
 1 file changed, 122 insertions(+)

diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c
index f614806..0815108 100644
--- a/tools/testing/selftests/bpf/test_lpm_map.c
+++ b/tools/testing/selftests/bpf/test_lpm_map.c
@@ -521,6 +521,126 @@ static void test_lpm_delete(void)
 	close(map_fd);
 }
 
+static void test_lpm_get_next_key(void)
+{
+	struct bpf_lpm_trie_key *key_p, *next_key_p;
+	size_t key_size;
+	__u32 value = 0;
+	int map_fd;
+
+	key_size = sizeof(*key_p) + sizeof(__u32);
+	key_p = alloca(key_size);
+	next_key_p = alloca(key_size);
+
+	map_fd = bpf_create_map(BPF_MAP_TYPE_LPM_TRIE, key_size, sizeof(value),
+				100, BPF_F_NO_PREALLOC);
+	assert(map_fd >= 0);
+
+	/* empty tree. get_next_key should return ENOENT */
+	assert(bpf_map_get_next_key(map_fd, NULL, key_p) == -1 &&
+	       errno == ENOENT);
+
+	/* get and verify the first key, get the second one should fail. */
+	key_p->prefixlen = 16;
+	inet_pton(AF_INET, "192.168.0.0", key_p->data);
+	assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
+
+	memset(key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
+	assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
+	       key_p->data[1] == 168);
+
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
+	       errno == ENOENT);
+
+	/* no exact matching key should get the first one in post order. */
+	key_p->prefixlen = 8;
+	assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
+	assert(key_p->prefixlen == 16 && key_p->data[0] == 192 &&
+	       key_p->data[1] == 168);
+
+	/* add one more element (total two) */
+	key_p->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.0.0", key_p->data);
+	assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
+
+	memset(key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
+	assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
+	       key_p->data[1] == 168 && key_p->data[2] == 0);
+
+	memset(next_key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168);
+
+	memcpy(key_p, next_key_p, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
+	       errno == ENOENT);
+
+	/* Add one more element (total three) */
+	key_p->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.128.0", key_p->data);
+	assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
+
+	memset(key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
+	assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
+	       key_p->data[1] == 168 && key_p->data[2] == 0);
+
+	memset(next_key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
+
+	memcpy(key_p, next_key_p, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168);
+
+	memcpy(key_p, next_key_p, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
+	       errno == ENOENT);
+
+	/* Add one more element (total four) */
+	key_p->prefixlen = 24;
+	inet_pton(AF_INET, "192.168.1.0", key_p->data);
+	assert(bpf_map_update_elem(map_fd, key_p, &value, 0) == 0);
+
+	memset(key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, NULL, key_p) == 0);
+	assert(key_p->prefixlen == 24 && key_p->data[0] == 192 &&
+	       key_p->data[1] == 168 && key_p->data[2] == 0);
+
+	memset(next_key_p, 0, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168 && next_key_p->data[2] == 1);
+
+	memcpy(key_p, next_key_p, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168 && next_key_p->data[2] == 128);
+
+	memcpy(key_p, next_key_p, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 16 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168);
+
+	memcpy(key_p, next_key_p, key_size);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
+	       errno == ENOENT);
+
+	/* no exact matching key should return the first one in post order */
+	key_p->prefixlen = 22;
+	inet_pton(AF_INET, "192.168.1.0", key_p->data);
+	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
+	assert(next_key_p->prefixlen == 24 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168 && next_key_p->data[2] == 0);
+
+	close(map_fd);
+}
+
 int main(void)
 {
 	struct rlimit limit  = { RLIM_INFINITY, RLIM_INFINITY };
@@ -545,6 +665,8 @@ int main(void)
 
 	test_lpm_delete();
 
+	test_lpm_get_next_key();
+
 	printf("test_lpm: OK\n");
 	return 0;
 }
-- 
2.9.5

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

[Daniel Borkmann]

On 01/19/2018 12:08 AM, Yonghong Song wrote:
> This patch set implements MAP_GET_NEXT_KEY command for LPM_TRIE map.
> This command is really useful for key enumeration, and for key deletion
> if what keys in the trie are unknown.
> 
> Patch #1 implements the functionality in the kernel and patch #2
> adds a test case in tools/testing/selftests/bpf.

Looks good to me, thanks Yonghong, applied to bpf-next!