[PATCH v1 0/4] fib: fix full table overwrite on address wraparound

[PATCH v1 0/4] fib: fix full table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

Both FIB dataplanes can overwrite their entire lookup table when a
prefix whose range ends at the top of the address space is added,
deleted, or has its next hop changed, while more-specific routes cover
its range up to that point. The call returns 0, so the corruption is
silent.

One real-world trigger is a default route coexisting with explicit /1
routes: with 0.0.0.0/0, 0.0.0.0/1 and 128.0.0.0/1 installed, deleting
0.0.0.0/0 makes every lookup miss. IPv6 behaves the same with ::/0,
::/1 and 8000::/1.

In modify_fib() (dir24_8.c) and modify_dp() (trie.c), the branch that
skips a route starting exactly at the current left edge has no
wraparound check, while the branch that installs a gap does. Patches 1
and 2 add the missing check. Patches 3 and 4 add unit tests that fail
without the fixes and pass with them.

Robert Sanford (4):
  fib: fix full table overwrite on address wraparound
  fib6: fix full table overwrite on address wraparound
  test/fib: reproduce table overwrite on address wraparound
  test/fib6: reproduce table overwrite on address wraparound

 app/test/test_fib.c  |  94 +++++++++++++++++++++++++++++++++++++++
 app/test/test_fib6.c | 103 +++++++++++++++++++++++++++++++++++++++++++
 lib/fib/dir24_8.c    |   6 +++
 lib/fib/trie.c       |   6 +++
 4 files changed, 209 insertions(+)

-- 
2.34.1

[PATCH v1 1/4] fib: fix full table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

When a prefix whose range ends at 255.255.255.255 is added, deleted,
or has its next hop changed, modify_fib() walks the more-specific
routes under it and installs the next hop into the gaps. If the last
of those routes starts exactly at the current left edge and ends at
255.255.255.255, the equal-edges branch advances ledge past it, and
ledge wraps to 0. That branch has no wraparound check, so the loop
continues. With no more routes, the final branch computes redge,
which also wraps to 0. Its ledge != 0 exception, which exists for a
default route added as the first route, lets the call through, and
install_to_fib(dp, 0, 0, nh) overwrites the entire table. The call
returns 0, so the corruption is silent.

For example, with 0.0.0.0/0, 0.0.0.0/1 and 128.0.0.0/1 installed,
deleting 0.0.0.0/0 makes every lookup miss. With 10.0.0.0/8,
255.255.255.0/25 and 255.255.255.128/25 installed, adding
255.255.255.0/24 makes every address, including 10.1.1.1, return the
/24's next hop.

Commit ab1b927cd73e ("fib: fix adding default route overwriting
entire table") added the wraparound check to the other branch only.
Add the same check to the equal-edges branch.

Fixes: 880bc2b5f3bd ("fib: fix adding default route")
Cc: stable@dpdk.org

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 lib/fib/dir24_8.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/fib/dir24_8.c b/lib/fib/dir24_8.c
index c135285a65..68029c6165 100644
--- a/lib/fib/dir24_8.c
+++ b/lib/fib/dir24_8.c
@@ -436,6 +436,12 @@ modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
 			if (ledge == redge) {
 				ledge = redge +
 					(uint32_t)(1ULL << (32 - tmp_depth));
+				/*
+				 * we got to the end of address space
+				 * and wrapped around
+				 */
+				if (ledge == 0)
+					break;
 				continue;
 			}
 			ret = install_to_fib(dp, ledge, redge,
-- 
2.34.1

[PATCH v1 2/4] fib6: fix full table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

When a prefix whose range ends at the top of the address space
(ffff:ffff:...:ffff) is added, deleted, or has its next hop changed,
modify_dp() walks the more-specific routes under it and installs the
next hop into the gaps. If the last of those routes starts exactly at
the current left edge and ends at the top of the address space, the
equal-edges branch advances ledge past it with get_nxt_net(), and
ledge wraps to ::. That branch has no wraparound check, so the loop
continues. With no more routes, the final branch computes redge,
which also wraps to ::. Its exception for an unspecified ledge, which
exists for a default route added as the first route, lets the call
through, and install_to_dp() with both edges at :: overwrites the
entire table. The call returns 0, so the corruption is silent.

For example, with ::/0, ::/1 and 8000::/1 installed, deleting ::/0
makes every lookup miss. With 2001:db8::/32 and two /121 routes at
ffff:...:ff00 and ffff:...:ff80 installed, adding their covering /120
makes every address, including 2001:db8::1, return the /120's next
hop.

The same commit added a wraparound check to the other branch only.
Add the same check to the equal-edges branch.

Fixes: fd66617c5774 ("fib6: fix adding default route as first route")
Cc: stable@dpdk.org

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 lib/fib/trie.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/fib/trie.c b/lib/fib/trie.c
index 187360d1c8..59f043ce0e 100644
--- a/lib/fib/trie.c
+++ b/lib/fib/trie.c
@@ -506,6 +506,12 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
 			rte_rib6_get_ip(tmp, &redge);
 			if (rte_ipv6_addr_eq(&ledge, &redge)) {
 				get_nxt_net(&ledge, tmp_depth);
+				/*
+				 * we got to the end of address space
+				 * and wrapped around
+				 */
+				if (rte_ipv6_addr_is_unspec(&ledge))
+					break;
 				continue;
 			}
 			ret = install_to_dp(dp, &ledge, &redge, next_hop);
-- 
2.34.1

[PATCH v1 3/4] test/fib: reproduce table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

Add a test for the case where the more-specific routes under a
modified prefix cover its range up to 255.255.255.255. It checks
two cases:

  - delete 0.0.0.0/0 while 0.0.0.0/1 and 128.0.0.0/1 are installed,
    and check that both /1 routes still resolve.

  - add 255.255.255.0/24 over 255.255.255.0/25 and
    255.255.255.128/25, and check that an unrelated route, an
    unrouted address and both /25 routes are unchanged.

Without the fix, the first lookup returns the default next hop and
the second case returns the /24's next hop for every address.

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 app/test/test_fib.c | 94 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/app/test/test_fib.c b/app/test/test_fib.c
index bd73399d56..62c0ce1e70 100644
--- a/app/test/test_fib.c
+++ b/app/test/test_fib.c
@@ -22,6 +22,7 @@ static int32_t test_free_null(void);
 static int32_t test_add_del_invalid(void);
 static int32_t test_get_invalid(void);
 static int32_t test_lookup(void);
+static int32_t test_wraparound(void);
 static int32_t test_invalid_rcu(void);
 static int32_t test_fib_rcu_sync_rw(void);
 
@@ -379,6 +380,98 @@ test_lookup(void)
 	return TEST_SUCCESS;
 }
 
+/*
+ * Reproducer for the address wraparound bug in modify_fib(). When the
+ * more-specific routes under a modified prefix cover its range up to
+ * 255.255.255.255, and the last of them starts exactly at the current
+ * left edge, the left edge wraps to 0 and the entire table must not
+ * be overwritten.
+ *
+ *   Case A: ADD 0.0.0.0/0, 0.0.0.0/1 and 128.0.0.0/1, then DEL
+ *           0.0.0.0/0. Both /1 routes must still resolve.
+ *   Case B: ADD 10.0.0.0/8, 255.255.255.0/25 and 255.255.255.128/25,
+ *           then ADD their covering 255.255.255.0/24. No lookup result
+ *           may change.
+ */
+static int32_t
+test_wraparound(void)
+{
+	struct rte_fib_conf config = { 0 };
+	struct rte_fib *fib;
+	uint64_t def_nh = 100;
+	uint32_t ip[4];
+	uint64_t nh[4];
+	int ret;
+
+	config.max_routes = 1024;
+	config.rib_ext_sz = 0;
+	config.default_nh = def_nh;
+	config.type = RTE_FIB_DIR24_8;
+	config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B;
+	config.dir24_8.num_tbl8 = 256;
+
+	/* Case A */
+	fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib_add(fib, RTE_IPV4(0, 0, 0, 0), 0, 1);
+	RTE_TEST_ASSERT(ret == 0, "ADD 0.0.0.0/0 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(0, 0, 0, 0), 1, 2);
+	RTE_TEST_ASSERT(ret == 0, "ADD 0.0.0.0/1 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(128, 0, 0, 0), 1, 3);
+	RTE_TEST_ASSERT(ret == 0, "ADD 128.0.0.0/1 failed (ret=%d)\n", ret);
+
+	ret = rte_fib_delete(fib, RTE_IPV4(0, 0, 0, 0), 0);
+	RTE_TEST_ASSERT(ret == 0, "DEL 0.0.0.0/0 failed (ret=%d)\n", ret);
+
+	ip[0] = RTE_IPV4(1, 1, 1, 1);
+	ip[1] = RTE_IPV4(200, 1, 1, 1);
+	ret = rte_fib_lookup_bulk(fib, ip, nh, 2);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 2,
+		"1.1.1.1: got nh %" PRIu64 ", want 2\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == 3,
+		"200.1.1.1: got nh %" PRIu64 ", want 3\n", nh[1]);
+
+	rte_fib_free(fib);
+
+	/* Case B */
+	fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib_add(fib, RTE_IPV4(10, 0, 0, 0), 8, 10);
+	RTE_TEST_ASSERT(ret == 0, "ADD 10.0.0.0/8 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(255, 255, 255, 0), 25, 5);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD 255.255.255.0/25 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(255, 255, 255, 128), 25, 6);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD 255.255.255.128/25 failed (ret=%d)\n", ret);
+
+	ret = rte_fib_add(fib, RTE_IPV4(255, 255, 255, 0), 24, 7);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD 255.255.255.0/24 failed (ret=%d)\n", ret);
+
+	ip[0] = RTE_IPV4(10, 1, 1, 1);
+	ip[1] = RTE_IPV4(1, 2, 3, 4);
+	ip[2] = RTE_IPV4(255, 255, 255, 1);
+	ip[3] = RTE_IPV4(255, 255, 255, 129);
+	ret = rte_fib_lookup_bulk(fib, ip, nh, 4);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 10,
+		"10.1.1.1: got nh %" PRIu64 ", want 10\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == def_nh,
+		"1.2.3.4: got nh %" PRIu64 ", want %" PRIu64 "\n",
+		nh[1], def_nh);
+	RTE_TEST_ASSERT(nh[2] == 5,
+		"255.255.255.1: got nh %" PRIu64 ", want 5\n", nh[2]);
+	RTE_TEST_ASSERT(nh[3] == 6,
+		"255.255.255.129: got nh %" PRIu64 ", want 6\n", nh[3]);
+
+	rte_fib_free(fib);
+	return TEST_SUCCESS;
+}
+
 /*
  * rte_fib_rcu_qsbr_add positive and negative tests.
  *  - Add RCU QSBR variable to FIB
@@ -598,6 +691,7 @@ static struct unit_test_suite fib_fast_tests = {
 	TEST_CASE(test_add_del_invalid),
 	TEST_CASE(test_get_invalid),
 	TEST_CASE(test_lookup),
+	TEST_CASE(test_wraparound),
 	TEST_CASE(test_invalid_rcu),
 	TEST_CASE(test_fib_rcu_sync_rw),
 	TEST_CASES_END()
-- 
2.34.1

[PATCH v1 4/4] test/fib6: reproduce table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

Add a test for the case where the more-specific routes under a
modified prefix cover its range up to the top of the address space.
It checks two cases:

  - delete ::/0 while ::/1 and 8000::/1 are installed, and check that
    both /1 routes still resolve.

  - add ffff:...:ff00/120 over ffff:...:ff00/121 and
    ffff:...:ff80/121, and check that an unrelated route, an unrouted
    address and both /121 routes are unchanged.

Without the fix, the first lookup returns the default next hop and
the second case returns the /120's next hop for every address.

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 app/test/test_fib6.c | 103 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)

diff --git a/app/test/test_fib6.c b/app/test/test_fib6.c
index ad68645428..c44b136760 100644
--- a/app/test/test_fib6.c
+++ b/app/test/test_fib6.c
@@ -23,6 +23,7 @@ static int32_t test_free_null(void);
 static int32_t test_add_del_invalid(void);
 static int32_t test_get_invalid(void);
 static int32_t test_lookup(void);
+static int32_t test_wraparound(void);
 static int32_t test_invalid_rcu(void);
 static int32_t test_fib_rcu_sync_rw(void);
 static int32_t test_drift(void);
@@ -395,6 +396,107 @@ test_lookup(void)
 	return TEST_SUCCESS;
 }
 
+/*
+ * Reproducer for the address wraparound bug in modify_dp(). When the
+ * more-specific routes under a modified prefix cover its range up to
+ * ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff, and the last of them starts
+ * exactly at the current left edge, the left edge wraps to :: and the
+ * entire table must not be overwritten.
+ *
+ *   Case A: ADD ::/0, ::/1 and 8000::/1, then DEL ::/0. Both /1
+ *           routes must still resolve.
+ *   Case B: ADD 2001:db8::/32, ffff:...:ff00/121 and
+ *           ffff:...:ff80/121, then ADD their covering
+ *           ffff:...:ff00/120. No lookup result may change.
+ */
+static int32_t
+test_wraparound(void)
+{
+	struct rte_fib6_conf config = { 0 };
+	struct rte_fib6 *fib;
+	const struct rte_ipv6_addr zero = RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 0);
+	const struct rte_ipv6_addr high = RTE_IPV6(0x8000, 0, 0, 0, 0, 0, 0, 0);
+	const struct rte_ipv6_addr net = RTE_IPV6(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0);
+	const struct rte_ipv6_addr top00 = RTE_IPV6(0xffff, 0xffff, 0xffff,
+		0xffff, 0xffff, 0xffff, 0xffff, 0xff00);
+	const struct rte_ipv6_addr top80 = RTE_IPV6(0xffff, 0xffff, 0xffff,
+		0xffff, 0xffff, 0xffff, 0xffff, 0xff80);
+	uint64_t def_nh = 100;
+	struct rte_ipv6_addr ip[4];
+	uint64_t nh[4];
+	int ret;
+
+	config.max_routes = 1024;
+	config.rib_ext_sz = 0;
+	config.default_nh = def_nh;
+	config.type = RTE_FIB6_TRIE;
+	config.trie.nh_sz = RTE_FIB6_TRIE_4B;
+	config.trie.num_tbl8 = 256;
+
+	/* Case A */
+	fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib6_add(fib, &zero, 0, 1);
+	RTE_TEST_ASSERT(ret == 0, "ADD ::/0 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &zero, 1, 2);
+	RTE_TEST_ASSERT(ret == 0, "ADD ::/1 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &high, 1, 3);
+	RTE_TEST_ASSERT(ret == 0, "ADD 8000::/1 failed (ret=%d)\n", ret);
+
+	ret = rte_fib6_delete(fib, &zero, 0);
+	RTE_TEST_ASSERT(ret == 0, "DEL ::/0 failed (ret=%d)\n", ret);
+
+	ip[0] = (struct rte_ipv6_addr)RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 1);
+	ip[1] = (struct rte_ipv6_addr)RTE_IPV6(0xffff, 0, 0, 0, 0, 0, 0, 1);
+	ret = rte_fib6_lookup_bulk(fib, ip, nh, 2);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 2,
+		"::1: got nh %" PRIu64 ", want 2\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == 3,
+		"ffff::1: got nh %" PRIu64 ", want 3\n", nh[1]);
+
+	rte_fib6_free(fib);
+
+	/* Case B */
+	fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib6_add(fib, &net, 32, 10);
+	RTE_TEST_ASSERT(ret == 0, "ADD 2001:db8::/32 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &top00, 121, 5);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD ffff:...:ff00/121 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &top80, 121, 6);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD ffff:...:ff80/121 failed (ret=%d)\n", ret);
+
+	ret = rte_fib6_add(fib, &top00, 120, 7);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD ffff:...:ff00/120 failed (ret=%d)\n", ret);
+
+	ip[0] = (struct rte_ipv6_addr)RTE_IPV6(0x2001, 0xdb8, 0, 0, 0, 0, 0, 1);
+	ip[1] = (struct rte_ipv6_addr)RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 1);
+	ip[2] = top00;
+	ip[2].a[15] = 0x01;
+	ip[3] = top80;
+	ip[3].a[15] = 0x81;
+	ret = rte_fib6_lookup_bulk(fib, ip, nh, 4);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 10,
+		"2001:db8::1: got nh %" PRIu64 ", want 10\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == def_nh,
+		"::1: got nh %" PRIu64 ", want %" PRIu64 "\n",
+		nh[1], def_nh);
+	RTE_TEST_ASSERT(nh[2] == 5,
+		"ffff:...:ff01: got nh %" PRIu64 ", want 5\n", nh[2]);
+	RTE_TEST_ASSERT(nh[3] == 6,
+		"ffff:...:ff81: got nh %" PRIu64 ", want 6\n", nh[3]);
+
+	rte_fib6_free(fib);
+	return TEST_SUCCESS;
+}
+
 /*
  * rte_fib6_rcu_qsbr_add positive and negative tests.
  *  - Add RCU QSBR variable to FIB
@@ -939,6 +1041,7 @@ static struct unit_test_suite fib6_fast_tests = {
 	TEST_CASE(test_add_del_invalid),
 	TEST_CASE(test_get_invalid),
 	TEST_CASE(test_lookup),
+	TEST_CASE(test_wraparound),
 	TEST_CASE(test_invalid_rcu),
 	TEST_CASE(test_fib_rcu_sync_rw),
 	TEST_CASE(test_drift),
-- 
2.34.1

[PATCH v2 0/5] fib: fix full table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

Both FIB dataplanes can overwrite their entire lookup table when a
prefix whose range ends at the top of the address space is added,
deleted, or has its next hop changed, while more-specific routes cover
its range up to that point. The call returns 0, so the corruption is
silent.

One real-world trigger is a default route coexisting with explicit /1
routes: with 0.0.0.0/0, 0.0.0.0/1 and 128.0.0.0/1 installed, deleting
0.0.0.0/0 makes every lookup miss. IPv6 behaves the same with ::/0,
::/1 and 8000::/1.

In modify_fib() (dir24_8.c) and modify_dp() (trie.c), the branch that
skips a route starting exactly at the current left edge has no
wraparound check, while the branch that installs a gap does. Patches 2
and 3 add the missing check. Patches 4 and 5 add unit tests that fail
without the fixes and pass with them.

Patch 1 fixes undefined behavior in rte_rib.c that the new IPv4 test
reaches: its bit test computes 1 << 31 on a signed int for nodes at
depth 0. No existing test adds a depth-0 route.

v2:
- Add patch 1. The CI UBSan build reported the undefined behavior in
  rte_rib.c when running the v1 test/fib wraparound test.
- Patches 2-5 are unchanged from v1.

Robert Sanford (5):
  rib: fix undefined behavior in bit test
  fib: fix full table overwrite on address wraparound
  fib6: fix full table overwrite on address wraparound
  test/fib: reproduce table overwrite on address wraparound
  test/fib6: reproduce table overwrite on address wraparound

 app/test/test_fib.c  |  94 +++++++++++++++++++++++++++++++++++++++
 app/test/test_fib6.c | 103 +++++++++++++++++++++++++++++++++++++++++++
 lib/fib/dir24_8.c    |   6 +++
 lib/fib/trie.c       |   6 +++
 lib/rib/rte_rib.c    |   8 ++--
 5 files changed, 213 insertions(+), 4 deletions(-)

-- 
2.34.1

[PATCH v2 1/5] rib: fix undefined behavior in bit test

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

The tree walk in rte_rib.c tests the bit below a node's depth with
1 << (31 - depth). For a node at depth 0, which exists for a default
route or for a common parent of routes in both halves of the address
space, that is 1 << 31 on a signed int, which is undefined behavior.
UBSan reports:

  rte_rib.c:82:18: runtime error: left shift of 1 by 31 places
  cannot be represented in type 'int'

and the same at lines 311 and 343. No existing unit test adds a
depth-0 route, so this was not caught before. The new test/fib
wraparound test in this series does.

Use an unsigned constant in all four bit tests. The shift count is
between 0 and 31 at each of them.

Fixes: 5a5793a5ffa2 ("rib: add RIB library")
Cc: stable@dpdk.org

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
v2: new patch in this series.

 lib/rib/rte_rib.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/lib/rib/rte_rib.c b/lib/rib/rte_rib.c
index 046db131ca..43d5ab1498 100644
--- a/lib/rib/rte_rib.c
+++ b/lib/rib/rte_rib.c
@@ -79,7 +79,7 @@ get_nxt_node(struct rte_rib_node *node, uint32_t ip)
 {
 	if (node->depth == RIB_MAXDEPTH)
 		return NULL;
-	return (ip & (1 << (31 - node->depth))) ? node->right : node->left;
+	return (ip & (1U << (31 - node->depth))) ? node->right : node->left;
 }
 
 static struct rte_rib_node *
@@ -308,7 +308,7 @@ rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 		if ((d >= depth) || !is_covered(ip, (*tmp)->ip, d))
 			break;
 		prev = *tmp;
-		tmp = (ip & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
+		tmp = (ip & (1U << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
 	}
 	/* closest node found, new_node should be inserted in the middle */
 	common_depth = RTE_MIN(depth, (*tmp)->depth);
@@ -319,7 +319,7 @@ rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 	common_prefix = ip & rte_rib_depth_to_mask(common_depth);
 	if ((common_prefix == ip) && (common_depth == depth)) {
 		/* insert as a parent */
-		if ((*tmp)->ip & (1 << (31 - depth)))
+		if ((*tmp)->ip & (1U << (31 - depth)))
 			new_node->right = *tmp;
 		else
 			new_node->left = *tmp;
@@ -340,7 +340,7 @@ rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)
 		common_node->parent = (*tmp)->parent;
 		new_node->parent = common_node;
 		(*tmp)->parent = common_node;
-		if ((new_node->ip & (1 << (31 - common_depth))) == 0) {
+		if ((new_node->ip & (1U << (31 - common_depth))) == 0) {
 			common_node->left = new_node;
 			common_node->right = *tmp;
 		} else {
-- 
2.34.1

[PATCH v2 2/5] fib: fix full table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

When a prefix whose range ends at 255.255.255.255 is added, deleted,
or has its next hop changed, modify_fib() walks the more-specific
routes under it and installs the next hop into the gaps. If the last
of those routes starts exactly at the current left edge and ends at
255.255.255.255, the equal-edges branch advances ledge past it, and
ledge wraps to 0. That branch has no wraparound check, so the loop
continues. With no more routes, the final branch computes redge,
which also wraps to 0. Its ledge != 0 exception, which exists for a
default route added as the first route, lets the call through, and
install_to_fib(dp, 0, 0, nh) overwrites the entire table. The call
returns 0, so the corruption is silent.

For example, with 0.0.0.0/0, 0.0.0.0/1 and 128.0.0.0/1 installed,
deleting 0.0.0.0/0 makes every lookup miss. With 10.0.0.0/8,
255.255.255.0/25 and 255.255.255.128/25 installed, adding
255.255.255.0/24 makes every address, including 10.1.1.1, return the
/24's next hop.

Commit ab1b927cd73e ("fib: fix adding default route overwriting
entire table") added the wraparound check to the other branch only.
Add the same check to the equal-edges branch.

Fixes: 880bc2b5f3bd ("fib: fix adding default route")
Cc: stable@dpdk.org

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 lib/fib/dir24_8.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/fib/dir24_8.c b/lib/fib/dir24_8.c
index c135285a65..68029c6165 100644
--- a/lib/fib/dir24_8.c
+++ b/lib/fib/dir24_8.c
@@ -436,6 +436,12 @@ modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
 			if (ledge == redge) {
 				ledge = redge +
 					(uint32_t)(1ULL << (32 - tmp_depth));
+				/*
+				 * we got to the end of address space
+				 * and wrapped around
+				 */
+				if (ledge == 0)
+					break;
 				continue;
 			}
 			ret = install_to_fib(dp, ledge, redge,
-- 
2.34.1

[PATCH v2 3/5] fib6: fix full table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

When a prefix whose range ends at the top of the address space
(ffff:ffff:...:ffff) is added, deleted, or has its next hop changed,
modify_dp() walks the more-specific routes under it and installs the
next hop into the gaps. If the last of those routes starts exactly at
the current left edge and ends at the top of the address space, the
equal-edges branch advances ledge past it with get_nxt_net(), and
ledge wraps to ::. That branch has no wraparound check, so the loop
continues. With no more routes, the final branch computes redge,
which also wraps to ::. Its exception for an unspecified ledge, which
exists for a default route added as the first route, lets the call
through, and install_to_dp() with both edges at :: overwrites the
entire table. The call returns 0, so the corruption is silent.

For example, with ::/0, ::/1 and 8000::/1 installed, deleting ::/0
makes every lookup miss. With 2001:db8::/32 and two /121 routes at
ffff:...:ff00 and ffff:...:ff80 installed, adding their covering /120
makes every address, including 2001:db8::1, return the /120's next
hop.

The same commit added a wraparound check to the other branch only.
Add the same check to the equal-edges branch.

Fixes: fd66617c5774 ("fib6: fix adding default route as first route")
Cc: stable@dpdk.org

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 lib/fib/trie.c | 6 ++++++
 1 file changed, 6 insertions(+)

diff --git a/lib/fib/trie.c b/lib/fib/trie.c
index 187360d1c8..59f043ce0e 100644
--- a/lib/fib/trie.c
+++ b/lib/fib/trie.c
@@ -506,6 +506,12 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
 			rte_rib6_get_ip(tmp, &redge);
 			if (rte_ipv6_addr_eq(&ledge, &redge)) {
 				get_nxt_net(&ledge, tmp_depth);
+				/*
+				 * we got to the end of address space
+				 * and wrapped around
+				 */
+				if (rte_ipv6_addr_is_unspec(&ledge))
+					break;
 				continue;
 			}
 			ret = install_to_dp(dp, &ledge, &redge, next_hop);
-- 
2.34.1

[PATCH v2 4/5] test/fib: reproduce table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

Add a test for the case where the more-specific routes under a
modified prefix cover its range up to 255.255.255.255. It checks
two cases:

  - delete 0.0.0.0/0 while 0.0.0.0/1 and 128.0.0.0/1 are installed,
    and check that both /1 routes still resolve.

  - add 255.255.255.0/24 over 255.255.255.0/25 and
    255.255.255.128/25, and check that an unrelated route, an
    unrouted address and both /25 routes are unchanged.

Without the fix, the first lookup returns the default next hop and
the second case returns the /24's next hop for every address.

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 app/test/test_fib.c | 94 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 94 insertions(+)

diff --git a/app/test/test_fib.c b/app/test/test_fib.c
index bd73399d56..62c0ce1e70 100644
--- a/app/test/test_fib.c
+++ b/app/test/test_fib.c
@@ -22,6 +22,7 @@ static int32_t test_free_null(void);
 static int32_t test_add_del_invalid(void);
 static int32_t test_get_invalid(void);
 static int32_t test_lookup(void);
+static int32_t test_wraparound(void);
 static int32_t test_invalid_rcu(void);
 static int32_t test_fib_rcu_sync_rw(void);
 
@@ -379,6 +380,98 @@ test_lookup(void)
 	return TEST_SUCCESS;
 }
 
+/*
+ * Reproducer for the address wraparound bug in modify_fib(). When the
+ * more-specific routes under a modified prefix cover its range up to
+ * 255.255.255.255, and the last of them starts exactly at the current
+ * left edge, the left edge wraps to 0 and the entire table must not
+ * be overwritten.
+ *
+ *   Case A: ADD 0.0.0.0/0, 0.0.0.0/1 and 128.0.0.0/1, then DEL
+ *           0.0.0.0/0. Both /1 routes must still resolve.
+ *   Case B: ADD 10.0.0.0/8, 255.255.255.0/25 and 255.255.255.128/25,
+ *           then ADD their covering 255.255.255.0/24. No lookup result
+ *           may change.
+ */
+static int32_t
+test_wraparound(void)
+{
+	struct rte_fib_conf config = { 0 };
+	struct rte_fib *fib;
+	uint64_t def_nh = 100;
+	uint32_t ip[4];
+	uint64_t nh[4];
+	int ret;
+
+	config.max_routes = 1024;
+	config.rib_ext_sz = 0;
+	config.default_nh = def_nh;
+	config.type = RTE_FIB_DIR24_8;
+	config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B;
+	config.dir24_8.num_tbl8 = 256;
+
+	/* Case A */
+	fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib_add(fib, RTE_IPV4(0, 0, 0, 0), 0, 1);
+	RTE_TEST_ASSERT(ret == 0, "ADD 0.0.0.0/0 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(0, 0, 0, 0), 1, 2);
+	RTE_TEST_ASSERT(ret == 0, "ADD 0.0.0.0/1 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(128, 0, 0, 0), 1, 3);
+	RTE_TEST_ASSERT(ret == 0, "ADD 128.0.0.0/1 failed (ret=%d)\n", ret);
+
+	ret = rte_fib_delete(fib, RTE_IPV4(0, 0, 0, 0), 0);
+	RTE_TEST_ASSERT(ret == 0, "DEL 0.0.0.0/0 failed (ret=%d)\n", ret);
+
+	ip[0] = RTE_IPV4(1, 1, 1, 1);
+	ip[1] = RTE_IPV4(200, 1, 1, 1);
+	ret = rte_fib_lookup_bulk(fib, ip, nh, 2);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 2,
+		"1.1.1.1: got nh %" PRIu64 ", want 2\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == 3,
+		"200.1.1.1: got nh %" PRIu64 ", want 3\n", nh[1]);
+
+	rte_fib_free(fib);
+
+	/* Case B */
+	fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib_add(fib, RTE_IPV4(10, 0, 0, 0), 8, 10);
+	RTE_TEST_ASSERT(ret == 0, "ADD 10.0.0.0/8 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(255, 255, 255, 0), 25, 5);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD 255.255.255.0/25 failed (ret=%d)\n", ret);
+	ret = rte_fib_add(fib, RTE_IPV4(255, 255, 255, 128), 25, 6);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD 255.255.255.128/25 failed (ret=%d)\n", ret);
+
+	ret = rte_fib_add(fib, RTE_IPV4(255, 255, 255, 0), 24, 7);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD 255.255.255.0/24 failed (ret=%d)\n", ret);
+
+	ip[0] = RTE_IPV4(10, 1, 1, 1);
+	ip[1] = RTE_IPV4(1, 2, 3, 4);
+	ip[2] = RTE_IPV4(255, 255, 255, 1);
+	ip[3] = RTE_IPV4(255, 255, 255, 129);
+	ret = rte_fib_lookup_bulk(fib, ip, nh, 4);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 10,
+		"10.1.1.1: got nh %" PRIu64 ", want 10\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == def_nh,
+		"1.2.3.4: got nh %" PRIu64 ", want %" PRIu64 "\n",
+		nh[1], def_nh);
+	RTE_TEST_ASSERT(nh[2] == 5,
+		"255.255.255.1: got nh %" PRIu64 ", want 5\n", nh[2]);
+	RTE_TEST_ASSERT(nh[3] == 6,
+		"255.255.255.129: got nh %" PRIu64 ", want 6\n", nh[3]);
+
+	rte_fib_free(fib);
+	return TEST_SUCCESS;
+}
+
 /*
  * rte_fib_rcu_qsbr_add positive and negative tests.
  *  - Add RCU QSBR variable to FIB
@@ -598,6 +691,7 @@ static struct unit_test_suite fib_fast_tests = {
 	TEST_CASE(test_add_del_invalid),
 	TEST_CASE(test_get_invalid),
 	TEST_CASE(test_lookup),
+	TEST_CASE(test_wraparound),
 	TEST_CASE(test_invalid_rcu),
 	TEST_CASE(test_fib_rcu_sync_rw),
 	TEST_CASES_END()
-- 
2.34.1

[PATCH v2 5/5] test/fib6: reproduce table overwrite on address wraparound

[Robert Sanford]

From: Robert Sanford <rsanford@akamai.com>

Add a test for the case where the more-specific routes under a
modified prefix cover its range up to the top of the address space.
It checks two cases:

  - delete ::/0 while ::/1 and 8000::/1 are installed, and check that
    both /1 routes still resolve.

  - add ffff:...:ff00/120 over ffff:...:ff00/121 and
    ffff:...:ff80/121, and check that an unrelated route, an unrouted
    address and both /121 routes are unchanged.

Without the fix, the first lookup returns the default next hop and
the second case returns the /120's next hop for every address.

Signed-off-by: Robert Sanford <rsanford@akamai.com>
---
 app/test/test_fib6.c | 103 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 103 insertions(+)

diff --git a/app/test/test_fib6.c b/app/test/test_fib6.c
index ad68645428..c44b136760 100644
--- a/app/test/test_fib6.c
+++ b/app/test/test_fib6.c
@@ -23,6 +23,7 @@ static int32_t test_free_null(void);
 static int32_t test_add_del_invalid(void);
 static int32_t test_get_invalid(void);
 static int32_t test_lookup(void);
+static int32_t test_wraparound(void);
 static int32_t test_invalid_rcu(void);
 static int32_t test_fib_rcu_sync_rw(void);
 static int32_t test_drift(void);
@@ -395,6 +396,107 @@ test_lookup(void)
 	return TEST_SUCCESS;
 }
 
+/*
+ * Reproducer for the address wraparound bug in modify_dp(). When the
+ * more-specific routes under a modified prefix cover its range up to
+ * ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff, and the last of them starts
+ * exactly at the current left edge, the left edge wraps to :: and the
+ * entire table must not be overwritten.
+ *
+ *   Case A: ADD ::/0, ::/1 and 8000::/1, then DEL ::/0. Both /1
+ *           routes must still resolve.
+ *   Case B: ADD 2001:db8::/32, ffff:...:ff00/121 and
+ *           ffff:...:ff80/121, then ADD their covering
+ *           ffff:...:ff00/120. No lookup result may change.
+ */
+static int32_t
+test_wraparound(void)
+{
+	struct rte_fib6_conf config = { 0 };
+	struct rte_fib6 *fib;
+	const struct rte_ipv6_addr zero = RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 0);
+	const struct rte_ipv6_addr high = RTE_IPV6(0x8000, 0, 0, 0, 0, 0, 0, 0);
+	const struct rte_ipv6_addr net = RTE_IPV6(0x2001, 0xdb8, 0, 0, 0, 0, 0, 0);
+	const struct rte_ipv6_addr top00 = RTE_IPV6(0xffff, 0xffff, 0xffff,
+		0xffff, 0xffff, 0xffff, 0xffff, 0xff00);
+	const struct rte_ipv6_addr top80 = RTE_IPV6(0xffff, 0xffff, 0xffff,
+		0xffff, 0xffff, 0xffff, 0xffff, 0xff80);
+	uint64_t def_nh = 100;
+	struct rte_ipv6_addr ip[4];
+	uint64_t nh[4];
+	int ret;
+
+	config.max_routes = 1024;
+	config.rib_ext_sz = 0;
+	config.default_nh = def_nh;
+	config.type = RTE_FIB6_TRIE;
+	config.trie.nh_sz = RTE_FIB6_TRIE_4B;
+	config.trie.num_tbl8 = 256;
+
+	/* Case A */
+	fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib6_add(fib, &zero, 0, 1);
+	RTE_TEST_ASSERT(ret == 0, "ADD ::/0 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &zero, 1, 2);
+	RTE_TEST_ASSERT(ret == 0, "ADD ::/1 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &high, 1, 3);
+	RTE_TEST_ASSERT(ret == 0, "ADD 8000::/1 failed (ret=%d)\n", ret);
+
+	ret = rte_fib6_delete(fib, &zero, 0);
+	RTE_TEST_ASSERT(ret == 0, "DEL ::/0 failed (ret=%d)\n", ret);
+
+	ip[0] = (struct rte_ipv6_addr)RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 1);
+	ip[1] = (struct rte_ipv6_addr)RTE_IPV6(0xffff, 0, 0, 0, 0, 0, 0, 1);
+	ret = rte_fib6_lookup_bulk(fib, ip, nh, 2);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 2,
+		"::1: got nh %" PRIu64 ", want 2\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == 3,
+		"ffff::1: got nh %" PRIu64 ", want 3\n", nh[1]);
+
+	rte_fib6_free(fib);
+
+	/* Case B */
+	fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+	ret = rte_fib6_add(fib, &net, 32, 10);
+	RTE_TEST_ASSERT(ret == 0, "ADD 2001:db8::/32 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &top00, 121, 5);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD ffff:...:ff00/121 failed (ret=%d)\n", ret);
+	ret = rte_fib6_add(fib, &top80, 121, 6);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD ffff:...:ff80/121 failed (ret=%d)\n", ret);
+
+	ret = rte_fib6_add(fib, &top00, 120, 7);
+	RTE_TEST_ASSERT(ret == 0,
+		"ADD ffff:...:ff00/120 failed (ret=%d)\n", ret);
+
+	ip[0] = (struct rte_ipv6_addr)RTE_IPV6(0x2001, 0xdb8, 0, 0, 0, 0, 0, 1);
+	ip[1] = (struct rte_ipv6_addr)RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 1);
+	ip[2] = top00;
+	ip[2].a[15] = 0x01;
+	ip[3] = top80;
+	ip[3].a[15] = 0x81;
+	ret = rte_fib6_lookup_bulk(fib, ip, nh, 4);
+	RTE_TEST_ASSERT(ret == 0, "Lookup failed (ret=%d)\n", ret);
+	RTE_TEST_ASSERT(nh[0] == 10,
+		"2001:db8::1: got nh %" PRIu64 ", want 10\n", nh[0]);
+	RTE_TEST_ASSERT(nh[1] == def_nh,
+		"::1: got nh %" PRIu64 ", want %" PRIu64 "\n",
+		nh[1], def_nh);
+	RTE_TEST_ASSERT(nh[2] == 5,
+		"ffff:...:ff01: got nh %" PRIu64 ", want 5\n", nh[2]);
+	RTE_TEST_ASSERT(nh[3] == 6,
+		"ffff:...:ff81: got nh %" PRIu64 ", want 6\n", nh[3]);
+
+	rte_fib6_free(fib);
+	return TEST_SUCCESS;
+}
+
 /*
  * rte_fib6_rcu_qsbr_add positive and negative tests.
  *  - Add RCU QSBR variable to FIB
@@ -939,6 +1041,7 @@ static struct unit_test_suite fib6_fast_tests = {
 	TEST_CASE(test_add_del_invalid),
 	TEST_CASE(test_get_invalid),
 	TEST_CASE(test_lookup),
+	TEST_CASE(test_wraparound),
 	TEST_CASE(test_invalid_rcu),
 	TEST_CASE(test_fib_rcu_sync_rw),
 	TEST_CASE(test_drift),
-- 
2.34.1