[Bug 976] rte_rib (and rte_rib6) do not handle /0 correctly

[Stephen Hemminger]

On Wed, 23 Mar 2022 22:46:02 +0000
bugzilla at dpdk.org wrote:

> https://bugs.dpdk.org/show_bug.cgi?id=976
> 
>             Bug ID: 976
>            Summary: rte_rib (and rte_rib6) do not handle /0 correctly
>            Product: DPDK
>            Version: 21.11
>           Hardware: All
>                 OS: All
>             Status: UNCONFIRMED
>           Severity: normal
>           Priority: Normal
>          Component: other
>           Assignee: dev at dpdk.org
>           Reporter: stephen at networkplumber.org
>   Target Milestone: ---
> 
> The function rte_rib_insert() allows inserting 0/0 as a default route, but it
> is not correctly handled by the current tree code. For example lookups will
> never match the default route and tree traversal never finds this default
> route.
> 
> Same bug probably exists in rte_rib6
> 

Here is a patch to existing RIB test that tests boundary conditions.
It shows that /0 and /32 work correctly for lookup, it is just the
tree traversal that is problematic.

diff --git a/app/test/test_rib.c b/app/test/test_rib.c
index 06058f8f7c52..403fc85efe95 100644
--- a/app/test/test_rib.c
+++ b/app/test/test_rib.c
@@ -307,6 +307,79 @@ test_basic(void)
 	return TEST_SUCCESS;
 }
 
+/*
+ * Call insert for successive depths from 0 to 32
+ * and then make sure we get the most specific rule.
+ */
+static int32_t
+test_depth(void)
+{
+	struct rte_rib *rib = NULL;
+	struct rte_rib_node *node;
+	const struct rte_rib_conf config = {
+		.max_nodes = MAX_RULES,
+	};
+	const uint32_t ip = RTE_IPV4(192, 18, 10, 1);
+	uint64_t next_hop_add = 0;
+	uint64_t next_hop_return;
+	uint8_t depth;
+	int ret;
+
+	rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config);
+	RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n");
+
+	for (depth = 0; depth <= MAX_DEPTH; depth++) {
+		node = rte_rib_insert(rib, ip, depth);
+		RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n");
+
+		ret = rte_rib_set_nh(node, next_hop_add);
+		RTE_TEST_ASSERT(ret == 0,
+				"Failed to set rte_rib_node field\n");
+
+		node = rte_rib_lookup_exact(rib, ip, depth);
+		RTE_TEST_ASSERT(node != NULL,
+				"Failed to lookup\n");
+
+		ret = rte_rib_get_nh(node, &next_hop_return);
+		RTE_TEST_ASSERT((ret == 0) && (next_hop_add == next_hop_return),
+				"Failed to get proper nexthop\n");
+		++next_hop_add;
+	}
+
+	/* depth = 33 = MAX_DEPTH + 1 */
+	do {
+		uint32_t this_ip;
+		uint8_t this_depth;
+
+		--depth;
+
+		node = rte_rib_lookup(rib, ip);
+		RTE_TEST_ASSERT(node != NULL, "Failed to lookup\n");
+
+		ret = rte_rib_get_nh(node, &next_hop_return);
+		RTE_TEST_ASSERT((ret == 0) && (depth == next_hop_return),
+				"Failed to get proper nexthop\n");
+
+		ret = rte_rib_get_depth(node, &this_depth);
+		RTE_TEST_ASSERT((ret == 0) && (this_depth == depth),
+				"Failed to get proper depth\n");
+
+		ret = rte_rib_get_ip(node, &this_ip);
+		RTE_TEST_ASSERT(ret == 0, "Failed to get ip\n");
+
+		rte_rib_remove(rib, this_ip, this_depth);
+	} while (depth != 0);
+
+	/* all rules removed should return NULL now */
+	node = rte_rib_lookup(rib, ip);
+	RTE_TEST_ASSERT(node == NULL,
+		"Lookup returns non existent rule\n");
+
+	rte_rib_free(rib);
+
+	return TEST_SUCCESS;
+}
+
 int32_t
 test_tree_traversal(void)
 {
@@ -314,9 +387,17 @@ test_tree_traversal(void)
 	struct rte_rib_node *node;
 	struct rte_rib_conf config;
 
-	uint32_t ip1 = RTE_IPV4(10, 10, 10, 0);
-	uint32_t ip2 = RTE_IPV4(10, 10, 130, 80);
-	uint8_t depth = 30;
+	uint32_t ips[] = {
+		RTE_IPV4(0, 0, 0, 0),		/* /0 */
+		RTE_IPV4(10, 10, 0, 0),		/* /8 */
+		RTE_IPV4(10, 11, 0, 0),		/* /16 */
+		RTE_IPV4(10, 10, 130, 0),	/* /24 */
+		RTE_IPV4(10, 10, 130, 9),	/* /32 */
+	};
+	unsigned int count;
+	uint32_t ip;
+	uint8_t depth;
+	int ret;
 
 	config.max_nodes = MAX_RULES;
 	config.ext_sz = 0;
@@ -324,16 +405,44 @@ test_tree_traversal(void)
 	rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config);
 	RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n");
 
-	node = rte_rib_insert(rib, ip1, depth);
-	RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n");
+	for (count = 0; count < RTE_DIM(ips); count++) {
+		depth = count * 8;
 
-	node = rte_rib_insert(rib, ip2, depth);
-	RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n");
+		node = rte_rib_insert(rib, ips[count], depth);
+		RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n");
+
+		ret = rte_rib_get_ip(node, &ip);
+		RTE_TEST_ASSERT(ret == 0, "Failed to get ip\n");
+
+		printf("%u: insert [%p] %u.%u.%u.%u/%u\n",
+		       count, node,
+		       (ip >> 24) & 0xff,
+		       (ip >> 16) & 0xff,
+		       (ip >> 8) & 0xff,
+		       ip & 0xff, depth);
+	}
 
+	/* Expect to be able to traverse to all nodes */
 	node = NULL;
-	node = rte_rib_get_nxt(rib, RTE_IPV4(10, 10, 130, 0), 24, node,
-			RTE_RIB_GET_NXT_ALL);
-	RTE_TEST_ASSERT(node != NULL, "Failed to get rib_node\n");
+	for (count = 0; count < RTE_DIM(ips); count++) {
+
+		node = rte_rib_get_nxt(rib, 0, 0,
+				       node, RTE_RIB_GET_NXT_ALL);
+		RTE_TEST_ASSERT(node != NULL, "Failed to get rib_node\n");
+
+		ret = rte_rib_get_ip(node, &ip);
+		RTE_TEST_ASSERT(ret == 0, "Failed to get ip\n");
+
+		ret = rte_rib_get_depth(node, &depth);
+		RTE_TEST_ASSERT(ret == 0, "Failed to get depth\n");
+
+		printf("%u: walk [%p] %u.%u.%u.%u/%u\n",
+		       count, node,
+		       (ip >> 24) & 0xff,
+		       (ip >> 16) & 0xff,
+		       (ip >> 8) & 0xff,
+		       ip & 0xff, depth);
+	}
 
 	rte_rib_free(rib);
 
@@ -350,6 +459,7 @@ static struct unit_test_suite rib_tests = {
 		TEST_CASE(test_insert_invalid),
 		TEST_CASE(test_get_fn),
 		TEST_CASE(test_basic),
+		TEST_CASE(test_depth),
 		TEST_CASE(test_tree_traversal),
 		TEST_CASES_END()
 	}