Netdev Archive on lore.kernel.org
 help / color / 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 4.19 31/60] bpf: lpm_trie: check left child of last leftmost node for NULL
Date: Wed, 26 Jun 2019 20:35:46 -0400
Message-ID: <20190627003616.20767-31-sashal@kernel.org> (raw)
In-Reply-To: <20190627003616.20767-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 4f3138e6ecb2..1a8b208f6c55 100644
--- a/kernel/bpf/lpm_trie.c
+++ b/kernel/bpf/lpm_trie.c
@@ -676,9 +676,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 index

Thread overview: 41+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <20190627003616.20767-1-sashal@kernel.org>
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 04/60] samples, bpf: fix to change the buffer size for read() Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 05/60] samples, bpf: suppress compiler warning Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 06/60] mac80211: fix rate reporting inside cfg80211_calculate_bitrate_he() Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 07/60] bpf: sockmap, fix use after free from sleep in psock backlog workqueue Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 11/60] mac80211: mesh: fix RCU warning Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 12/60] mac80211: free peer keys before vif down in mesh Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 13/60] mwifiex: Fix possible buffer overflows at parsing bss descriptor Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 14/60] mwifiex: Abort at too short BSS descriptor element Sasha Levin
2019-06-28 22:58   ` Brian Norris
2019-07-10 14:51     ` Sasha Levin
2019-07-10 21:12       ` Brian Norris
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 15/60] iwlwifi: Fix double-free problems in iwl_req_fw_callback() Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 16/60] mwifiex: Fix heap overflow in mwifiex_uap_parse_tail_ies() Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 17/60] bpf: udp: Avoid calling reuseport's bpf_prog from udp_gro Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 18/60] netfilter: ipv6: nf_defrag: fix leakage of unqueued fragments Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 20/60] netfilter: ipv6: nf_defrag: accept duplicate fragments again Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 21/60] dt-bindings: can: mcp251x: add mcp25625 support Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 22/60] can: mcp251x: add support for mcp25625 Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 23/60] can: m_can: implement errata "Needless activation of MRAF irq" Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 24/60] can: af_can: Fix error path of can_init() Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 25/60] net: phy: rename Asix Electronics PHY driver Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 26/60] ibmvnic: Do not close unopened driver during reset Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 27/60] ibmvnic: Refresh device multicast list after reset Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 28/60] ibmvnic: Fix unchecked return codes of memory allocations Sasha Levin
2019-06-27  0:35 ` Sasha Levin [this message]
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 37/60] mlxsw: spectrum: Disallow prio-tagged packets when PVID is removed Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 40/60] mac80211: only warn once on chanctx_conf being NULL Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 41/60] mac80211: do not start any work during reconfigure flow Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 42/60] bpf, devmap: Fix premature entry free on destroying map Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 43/60] bpf, devmap: Add missing bulk queue free Sasha Levin
2019-06-27  0:35 ` [PATCH AUTOSEL 4.19 44/60] bpf, devmap: Add missing RCU read lock on flush Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 45/60] bpf, x64: fix stack layout of JITed bpf code Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 46/60] qmi_wwan: add support for QMAP padding in the RX path Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 47/60] qmi_wwan: avoid RCU stalls on device disconnect when in QMAP mode Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 48/60] qmi_wwan: extend permitted QMAP mux_id value range Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 49/60] bpf: fix nested bpf tracepoints with per-cpu data Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 52/60] bnx2x: Check if transceiver implements DDM before access Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 54/60] ip6_tunnel: allow not to count pkts on tstats by passing dev as NULL Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 55/60] net: lio_core: fix potential sign-extension overflow on large shift Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 58/60] net: dsa: mv88e6xxx: fix shift of FID bits in mv88e6185_g1_vtu_loadpurge() Sasha Levin
2019-06-27  0:36 ` [PATCH AUTOSEL 4.19 60/60] net :sunrpc :clnt :Fix xps refcount imbalance on the error path Sasha Levin

Reply instructions:

You may reply publically 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=20190627003616.20767-31-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

Netdev Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/netdev/0 netdev/git/0.git
	git clone --mirror https://lore.kernel.org/netdev/1 netdev/git/1.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 netdev netdev/ https://lore.kernel.org/netdev \
		netdev@vger.kernel.org
	public-inbox-index netdev

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.netdev


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git