netdev.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Sasha Levin <sashal@kernel.org>
To: linux-kernel@vger.kernel.org, stable@vger.kernel.org
Cc: Jonathan Lemon <jonathan.lemon@gmail.com>,
	Martin KaFai Lau <kafai@fb.com>,
	Daniel Borkmann <daniel@iogearbox.net>,
	Sasha Levin <sashal@kernel.org>,
	netdev@vger.kernel.org, bpf@vger.kernel.org,
	linux-kselftest@vger.kernel.org
Subject: [PATCH AUTOSEL 5.1 48/95] bpf: lpm_trie: check left child of last leftmost node for NULL
Date: Wed, 26 Jun 2019 20:29:33 -0400	[thread overview]
Message-ID: <20190627003021.19867-48-sashal@kernel.org> (raw)
In-Reply-To: <20190627003021.19867-1-sashal@kernel.org>

From: Jonathan Lemon <jonathan.lemon@gmail.com>

[ Upstream commit da2577fdd0932ea4eefe73903f1130ee366767d2 ]

If the leftmost parent node of the tree has does not have a child
on the left side, then trie_get_next_key (and bpftool map dump) will
not look at the child on the right.  This leads to the traversal
missing elements.

Lookup is not affected.

Update selftest to handle this case.

Reproducer:

 bpftool map create /sys/fs/bpf/lpm type lpm_trie key 6 \
     value 1 entries 256 name test_lpm flags 1
 bpftool map update pinned /sys/fs/bpf/lpm key  8 0 0 0  0   0 value 1
 bpftool map update pinned /sys/fs/bpf/lpm key 16 0 0 0  0 128 value 2
 bpftool map dump   pinned /sys/fs/bpf/lpm

Returns only 1 element. (2 expected)

Fixes: b471f2f1de8b ("bpf: implement MAP_GET_NEXT_KEY command for LPM_TRIE")
Signed-off-by: Jonathan Lemon <jonathan.lemon@gmail.com>
Acked-by: Martin KaFai Lau <kafai@fb.com>
Signed-off-by: Daniel Borkmann <daniel@iogearbox.net>
Signed-off-by: Sasha Levin <sashal@kernel.org>
---
 kernel/bpf/lpm_trie.c                      |  9 +++--
 tools/testing/selftests/bpf/test_lpm_map.c | 41 ++++++++++++++++++++--
 2 files changed, 45 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/lpm_trie.c b/kernel/bpf/lpm_trie.c
index 93a5cbbde421..3b03a7342f3c 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -715,9 +715,14 @@ static int trie_get_next_key(struct bpf_map *map, void *_key, void *_next_key)
 	 * have exact two children, so this function will never return NULL.
 	 */
 	for (node = search_root; node;) {
-		if (!(node->flags & LPM_TREE_NODE_FLAG_IM))
+		if (node->flags & LPM_TREE_NODE_FLAG_IM) {
+			node = rcu_dereference(node->child[0]);
+		} else {
 			next_node = node;
-		node = rcu_dereference(node->child[0]);
+			node = rcu_dereference(node->child[0]);
+			if (!node)
+				node = rcu_dereference(next_node->child[1]);
+		}
 	}
 do_copy:
 	next_key->prefixlen = next_node->prefixlen;
diff --git a/tools/testing/selftests/bpf/test_lpm_map.c b/tools/testing/selftests/bpf/test_lpm_map.c
index 02d7c871862a..006be3963977 100644
--- a/tools/testing/selftests/bpf/test_lpm_map.c
+++ b/tools/testing/selftests/bpf/test_lpm_map.c
@@ -573,13 +573,13 @@ static void test_lpm_get_next_key(void)
 
 	/* add one more element (total two) */
 	key_p->prefixlen = 24;
-	inet_pton(AF_INET, "192.168.0.0", key_p->data);
+	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);
+	       key_p->data[1] == 168 && key_p->data[2] == 128);
 
 	memset(next_key_p, 0, key_size);
 	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == 0);
@@ -592,7 +592,7 @@ static void test_lpm_get_next_key(void)
 
 	/* Add one more element (total three) */
 	key_p->prefixlen = 24;
-	inet_pton(AF_INET, "192.168.128.0", key_p->data);
+	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);
@@ -643,6 +643,41 @@ static void test_lpm_get_next_key(void)
 	assert(bpf_map_get_next_key(map_fd, key_p, next_key_p) == -1 &&
 	       errno == ENOENT);
 
+	/* Add one more element (total five) */
+	key_p->prefixlen = 28;
+	inet_pton(AF_INET, "192.168.1.128", 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 == 28 && next_key_p->data[0] == 192 &&
+	       next_key_p->data[1] == 168 && next_key_p->data[2] == 1 &&
+	       next_key_p->data[3] == 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 == 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);
-- 
2.20.1


  parent reply	other threads:[~2019-06-27  0:52 UTC|newest]

Thread overview: 52+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <20190627003021.19867-1-sashal@kernel.org>
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 08/95] bpf: fix out-of-bounds read in __bpf_skc_lookup Sasha Levin
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 09/95] samples, bpf: fix to change the buffer size for read() Sasha Levin
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 10/95] samples, bpf: suppress compiler warning Sasha Levin
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 11/95] bpf, riscv: clear target register high 32-bits for and/or/xor on ALU32 Sasha Levin
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 12/95] bpf: sockmap, restore sk_write_space when psock gets dropped Sasha Levin
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 13/95] mac80211: fix rate reporting inside cfg80211_calculate_bitrate_he() Sasha Levin
2019-06-27  0:28 ` [PATCH AUTOSEL 5.1 14/95] bpf: sockmap, fix use after free from sleep in psock backlog workqueue Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 19/95] mac80211: mesh: fix RCU warning Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 20/95] mac80211: free peer keys before vif down in mesh Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 22/95] mwifiex: Fix possible buffer overflows at parsing bss descriptor Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 23/95] mwifiex: Abort at too short BSS descriptor element Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 24/95] bpf, riscv: clear high 32 bits for ALU32 add/sub/neg/lsh/rsh/arsh Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 25/95] iwlwifi: fix load in rfkill flow for unified firmware Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 26/95] iwlwifi: clear persistence bit according to device family Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 27/95] iwlwifi: fix AX201 killer sku loading firmware issue Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 28/95] iwlwifi: Fix double-free problems in iwl_req_fw_callback() Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 29/95] mwifiex: Fix heap overflow in mwifiex_uap_parse_tail_ies() Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 30/95] bpf: udp: ipv6: Avoid running reuseport's bpf_prog from __udp6_lib_err Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 31/95] bpf: udp: Avoid calling reuseport's bpf_prog from udp_gro Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 32/95] netfilter: ipv6: nf_defrag: fix leakage of unqueued fragments Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 33/95] tools: bpftool: Fix JSON output when lookup fails Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 36/95] netfilter: ipv6: nf_defrag: accept duplicate fragments again Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 37/95] dt-bindings: can: mcp251x: add mcp25625 support Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 38/95] can: mcp251x: add support for mcp25625 Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 39/95] can: m_can: implement errata "Needless activation of MRAF irq" Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 40/95] can: af_can: Fix error path of can_init() Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 41/95] can: flexcan: Remove unneeded registration message Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 42/95] net: phy: rename Asix Electronics PHY driver Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 43/95] ibmvnic: Do not close unopened driver during reset Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 44/95] ibmvnic: Refresh device multicast list after reset Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 45/95] ibmvnic: Fix unchecked return codes of memory allocations Sasha Levin
2019-06-27  0:29 ` Sasha Levin [this message]
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 54/95] xdp: check device pointer before clearing Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 56/95] mlxsw: spectrum: Disallow prio-tagged packets when PVID is removed Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 58/95] bpf: fix div64 overflow tests to properly detect errors Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 64/95] mac80211: only warn once on chanctx_conf being NULL Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 65/95] mac80211: do not start any work during reconfigure flow Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 66/95] cfg80211: util: fix bit count off by one Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 67/95] cfg80211: report measurement start TSF correctly Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 68/95] bpf, devmap: Fix premature entry free on destroying map Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 69/95] bpf, devmap: Add missing bulk queue free Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 70/95] bpf, devmap: Add missing RCU read lock on flush Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 71/95] bpf, x64: fix stack layout of JITed bpf code Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 72/95] qmi_wwan: add support for QMAP padding in the RX path Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 73/95] qmi_wwan: avoid RCU stalls on device disconnect when in QMAP mode Sasha Levin
2019-06-27  0:29 ` [PATCH AUTOSEL 5.1 74/95] qmi_wwan: extend permitted QMAP mux_id value range Sasha Levin
2019-06-27  0:30 ` [PATCH AUTOSEL 5.1 75/95] bpf: fix nested bpf tracepoints with per-cpu data Sasha Levin
2019-06-27  0:30 ` [PATCH AUTOSEL 5.1 84/95] bnx2x: Check if transceiver implements DDM before access Sasha Levin
2019-06-27  0:30 ` [PATCH AUTOSEL 5.1 86/95] ip6_tunnel: allow not to count pkts on tstats by passing dev as NULL Sasha Levin
2019-06-27  0:30 ` [PATCH AUTOSEL 5.1 87/95] net: lio_core: fix potential sign-extension overflow on large shift Sasha Levin
2019-06-27  0:30 ` [PATCH AUTOSEL 5.1 92/95] net: dsa: mv88e6xxx: fix shift of FID bits in mv88e6185_g1_vtu_loadpurge() Sasha Levin
2019-06-27  0:30 ` [PATCH AUTOSEL 5.1 95/95] net :sunrpc :clnt :Fix xps refcount imbalance on the error path Sasha Levin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20190627003021.19867-48-sashal@kernel.org \
    --to=sashal@kernel.org \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=jonathan.lemon@gmail.com \
    --cc=kafai@fb.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-kselftest@vger.kernel.org \
    --cc=netdev@vger.kernel.org \
    --cc=stable@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).