Skip to contentSkip to conversation

bpf: fix kernel page fault in lpm map trie_get_next_key

PATCH Applied Yonghong Song 2 participants 4 messages Jan 26, 2018 – Jan 27, 2018

Subsystems (5)
Networking Network drivers Kselftest BPF +1 more subsystems
lore
Share & tools
lore

Yonghong Song

author
#0 lore raw

cover bpf: fix kernel page fault in lpm map trie_get_next_key

A kernel page fault which happens in lpm map trie_get_next_key is reported by syzbot and Eric. The issue was introduced by commit b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map"). Patch #1 fixed the issue in the kernel and patch #2 adds a multithreaded test case in tools/testing/selftests/bpf/test_lpm_map.

Yonghong Song (2):
bpf: fix kernel page fault in lpm map trie_get_next_key tools/bpf: add a multithreaded stress test in bpf selftests
test_lpm_map

 kernel/bpf/lpm_trie.c                      | 26 ++++----
 tools/testing/selftests/bpf/Makefile       |  2 +-
 tools/testing/selftests/bpf/test_lpm_map.c | 95 ++++++++++++++++++++++++++++++
 3 files changed, 107 insertions(+), 16 deletions(-)
Signature · 1 line
2.9.5
author
#1 lore raw

PATCH 1/2 bpf: fix kernel page fault in lpm map trie_get_next_key

Commit b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map") introduces a bug likes below:

    if (!rcu_dereference(trie->root))
        return -ENOENT;
    if (!key || key->prefixlen > trie->max_prefixlen) {
        root = &trie->root;
        goto find_leftmost;
    }
    ......
  find_leftmost:
    for (node = rcu_dereference(*root); node;) {

In the code after label find_leftmost, it is assumed that *root should not be NULL, but it is not true as it is possbile trie->root is changed to NULL by an asynchronous delete operation.

The issue is reported by syzbot and Eric Dumazet with the below error log:
......
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
  ......

This patch fixed the issue by use local rcu_dereferenced pointer instead of *(&trie->root) later on.

Fixes b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command or LPM_TRIE map")
Reported-by syzbot <[email protected]>
Reported-by Eric Dumazet <[email protected]>
Signed-off-by Yonghong Song <[email protected]>
---
 kernel/bpf/lpm_trie.c | 26 +++++++++++---------------
 1 file changed, 11 insertions(+), 15 deletions(-)
kernel/bpf/lpm_trie.c +11 -15
index 8f083ea..7b469d1 100644
@@ -593,11 +593,10 @@ static void trie_free(struct bpf_map *map)
 
 static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 {
+	struct lpm_trie_node *node, *next_node = NULL, *parent, *search_root;
 	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;

@@ -614,14 +613,13 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 	 */
 
 	/* Empty trie */
-	if (!rcu_dereference(trie->root))
+	search_root = rcu_dereference(trie->root);
+	if (!search_root)
 		return -ENOENT;
 
 	/* For invalid key, find the leftmost node in the trie */
-	if (!key || key->prefixlen > trie->max_prefixlen) {
-		root = &trie->root;
+	if (!key || key->prefixlen > trie->max_prefixlen)
 		goto find_leftmost;
-	}
 
 	node_stack = kmalloc(trie->max_prefixlen * sizeof(struct lpm_trie_node *),
 			     GFP_ATOMIC | __GFP_NOWARN);

@@ -629,7 +627,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 		return -ENOMEM;
 
 	/* Try to find the exact node for the given key */
-	for (node = rcu_dereference(trie->root); node;) {
+	for (node = search_root; node;) {
 		node_stack[++stack_ptr] = node;
 		matchlen = longest_prefix_match(trie, node, key);
 		if (node->prefixlen != matchlen ||

@@ -640,10 +638,8 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 		node = rcu_dereference(node->child[next_bit]);
 	}
 	if (!node || node->prefixlen != key->prefixlen ||
-	    (node->flags & LPM_TREE_NODE_FLAG_IM)) {
-		root = &trie->root;
+	    (node->flags & LPM_TREE_NODE_FLAG_IM))
 		goto find_leftmost;
-	}
 
 	/* The node with the exactly-matching key has been found,
 	 * find the first node in postorder after the matched node.

@@ -651,10 +647,10 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 	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 (rcu_dereference(parent->child[0]) == node) {
+			search_root = rcu_dereference(parent->child[1]);
+			if (search_root)
+				goto find_leftmost;
 		}
 		if (!(parent->flags & LPM_TREE_NODE_FLAG_IM)) {
 			next_node = parent;

@@ -673,7 +669,7 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 	/* 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;) {
+	for (node = search_root; node;) {
 		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
 			next_node = node;
 		node = rcu_dereference(node->child[0]);
Signature · 1 line
2.9.5
author
#2 lore raw

PATCH 2/2 tools/bpf: add a multithreaded stress test in bpf selftests test_lpm_map

In reply to Yonghong Song

The new test will spawn four threads, doing map update, delete, lookup and get_next_key in parallel. It is able to reproduce the issue in the previous commit found by syzbot and Eric Dumazet.

Signed-off-by Yonghong Song <[email protected]>
---
 tools/testing/selftests/bpf/Makefile       |  2 +-
 tools/testing/selftests/bpf/test_lpm_map.c | 95 ++++++++++++++++++++++++++++++
 2 files changed, 96 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/Makefile +1 -1
index 9868835..bf05bc5 100644
@@ -11,7 +11,7 @@ ifneq ($(wildcard $(GENHDR)),)
 endif
 
 CFLAGS += -Wall -O2 -I$(APIDIR) -I$(LIBDIR) -I$(GENDIR) $(GENFLAGS) -I../../../include
-LDLIBS += -lcap -lelf -lrt
+LDLIBS += -lcap -lelf -lrt -lpthread
 
 TEST_GEN_PROGS = test_verifier test_tag test_maps test_lru_map test_lpm_map test_progs \
 	test_align test_verifier_log test_dev_cgroup test_tcpbpf_user
tools/testing/selftests/bpf/test_lpm_map.c +95 -0

113 lines not on this page · raw message

Signature · 1 line
2.9.5
Applied
#3 lore raw
In reply to Yonghong Song
Quoted 5 lines · Yonghong Song

A kernel page fault which happens in lpm map trie_get_next_key is reported by syzbot and Eric. The issue was introduced by commit b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE map"). Patch #1 fixed the issue in the kernel and patch #2 adds a multithreaded test case in tools/testing/selftests/bpf/test_lpm_map.

Applied to bpf-next, thank you Yonghong!