rte_rib (and rte_rib6) do not handle /0 correctly

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: [email protected]
          Reporter: [email protected]

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

Quoted 14 lines · On Wed, 23 Mar 2022 22:46:02 +0000 [email protected] 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: [email protected]
           Reporter: [email protected]

Quoted 9 lines

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.

app/test/test_rib.c +120 -10

index 06058f8f7c52..403fc85efe95 100644
@@ -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()
  	}