rte_rib_get_nxt() and rte_rib6_get_nxt() skip the exact match top-level route when iterating subroutes. This is the expected behavior in most cases but some users need the full subtree including the root.
Add a RTE_RIB_GET_NXT_ALL_TOP (and RTE_RIB6_GET_NXT_ALL_TOP) mode that uses >= instead of > when comparing depths so that the top-level route is returned as well. Signed-off-by: Robin Jarry <[email protected]> --- app/test/test_rib.c | 16 ++++++++++++++++ app/test/test_rib6.c | 16 ++++++++++++++++ lib/rib/rte_rib.c | 12 ++++++++++-- lib/rib/rte_rib.h | 4 ++++ lib/rib/rte_rib6.c | 12 ++++++++++-- lib/rib/rte_rib6.h | 4 ++++ 6 files changed, 60 insertions(+), 4 deletions(-) diff --git a/app/test/test_rib.c b/app/test/test_rib.c index a4a683140df3..f56490e67ec0 100644 --- a/app/test/test_rib.c +++ b/app/test/test_rib.c @@ -300,6 +300,7 @@ test_tree_traversal(void) uint32_t ip1 = RTE_IPV4(10, 10, 10, 0); uint32_t ip2 = RTE_IPV4(10, 10, 130, 80); uint8_t depth = 30; + unsigned int num; config.max_nodes = MAX_RULES; config.ext_sz = 0; @@ -313,11 +314,26 @@ test_tree_traversal(void) node = rte_rib_insert(rib, ip2, depth); RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + node = rte_rib_insert(rib, 0, 0); + RTE_TEST_ASSERT(node != NULL, "Failed to insert default rule\n"); + 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"); + num = 0; + node = NULL; + while ((node = rte_rib_get_nxt(rib, 0, 0, node, RTE_RIB_GET_NXT_ALL)) != NULL) + num++; + RTE_TEST_ASSERT(num == 2, "Invalid number of routes\n"); + + num = 0; + node = NULL; + while ((node = rte_rib_get_nxt(rib, 0, 0, node, RTE_RIB_GET_NXT_ALL_TOP)) != NULL) + num++; + RTE_TEST_ASSERT(num == 3, "Default route not returned by rte_rib_get_nxt\n"); + rte_rib_free(rib); return TEST_SUCCESS; diff --git a/app/test/test_rib6.c b/app/test/test_rib6.c index 0295a9640cfa..542c955eee8c 100644 --- a/app/test/test_rib6.c +++ b/app/test/test_rib6.c @@ -300,7 +300,9 @@ test_tree_traversal(void) struct rte_ipv6_addr ip = RTE_IPV6(0x0a00, 0x0282, 0, 0, 0, 0, 0, 0); struct rte_ipv6_addr ip1 = RTE_IPV6(0x0a00, 0x0200, 0, 0, 0, 0, 0, 0); struct rte_ipv6_addr ip2 = RTE_IPV6(0x0a00, 0x0282, 0, 0, 0, 0, 0, 0x0050); + struct rte_ipv6_addr unspec = RTE_IPV6(0, 0, 0, 0, 0, 0, 0, 0); uint8_t depth = 126; + unsigned int num; config.max_nodes = MAX_RULES; config.ext_sz = 0; @@ -312,11 +314,25 @@ test_tree_traversal(void) RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); node = rte_rib6_insert(rib, &ip2, depth); RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + node = rte_rib6_insert(rib, &unspec, 0); + RTE_TEST_ASSERT(node != NULL, "Failed to insert default route\n"); node = NULL; node = rte_rib6_get_nxt(rib, &ip, 32, node, RTE_RIB6_GET_NXT_ALL); RTE_TEST_ASSERT(node != NULL, "Failed to get rib_node\n"); + num = 0; + node = NULL; + while ((node = rte_rib6_get_nxt(rib, 0, 0, node, RTE_RIB6_GET_NXT_ALL)) != NULL) + num++; + RTE_TEST_ASSERT(num == 2, "Invalid number of routes\n"); + + num = 0; + node = NULL; + while ((node = rte_rib6_get_nxt(rib, 0, 0, node, RTE_RIB6_GET_NXT_ALL_TOP)) != NULL) + num++; + RTE_TEST_ASSERT(num == 3, "Default route not returned by rte_rib6_get_nxt\n"); + rte_rib6_free(rib); return TEST_SUCCESS; diff --git a/lib/rib/rte_rib.c b/lib/rib/rte_rib.c index 89061829a23c..a3c287e215ec 100644 --- a/lib/rib/rte_rib.c +++ b/lib/rib/rte_rib.c @@ -167,6 +167,14 @@ rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth) return __rib_lookup_exact(rib, ip, depth); } +static bool +depth_match(struct rte_rib_node *node, uint8_t depth, int flag) +{ + if (flag == RTE_RIB_GET_NXT_ALL_TOP) + return node->depth >= depth; + return node->depth > depth; +} + /* * Traverses on subtree and retrieves more specific routes * for a given in args ip/depth prefix @@ -195,7 +203,7 @@ rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip, tmp = tmp->parent; if (is_valid_node(tmp) && (is_covered(tmp->ip, ip, depth) && - (tmp->depth > depth))) + (depth_match(tmp, depth, mode)))) return tmp; } tmp = (tmp->parent) ? tmp->parent->right : NULL; @@ -203,7 +211,7 @@ rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip, while (tmp) { if (is_valid_node(tmp) && (is_covered(tmp->ip, ip, depth) && - (tmp->depth > depth))) { + (depth_match(tmp, depth, mode)))) { prev = tmp; if (mode == RTE_RIB_GET_NXT_COVER) return prev; diff --git a/lib/rib/rte_rib.h b/lib/rib/rte_rib.h index 0fabfb2a41a6..5e72fa9273e2 100644 --- a/lib/rib/rte_rib.h +++ b/lib/rib/rte_rib.h @@ -31,6 +31,8 @@ enum rte_rib_nxt_mode { RTE_RIB_GET_NXT_ALL, /** get first matched subroutes in a RIB tree, excluding any exact match top-level route */ RTE_RIB_GET_NXT_COVER, + /** get all subroutes in a RIB tree, including the exact match top-level route, if any */ + RTE_RIB_GET_NXT_ALL_TOP, }; struct rte_rib; @@ -125,6 +127,8 @@ rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth); * get all prefixes from subtrie * -RTE_RIB_GET_NXT_COVER * get only first more specific prefix even if it have more specifics + * -RTE_RIB_GET_NXT_ALL_TOP + * get the top-level exact matching prefix, if any * @return * pointer to the next more specific prefix * NULL if there is no prefixes left diff --git a/lib/rib/rte_rib6.c b/lib/rib/rte_rib6.c index c23881f6247e..5114fb522e3e 100644 --- a/lib/rib/rte_rib6.c +++ b/lib/rib/rte_rib6.c @@ -186,6 +186,14 @@ rte_rib6_lookup_exact(struct rte_rib6 *rib, return NULL; } +static bool +depth_match(struct rte_rib6_node *node, uint8_t depth, enum rte_rib6_nxt_mode mode) +{ + if (mode == RTE_RIB6_GET_NXT_ALL_TOP) + return node->depth >= depth; + return node->depth > depth; +} + /* * Traverses on subtree and retrieves more specific routes * for a given in args ip/depth prefix @@ -219,7 +227,7 @@ rte_rib6_get_nxt(struct rte_rib6 *rib, tmp = tmp->parent; if (is_valid_node(tmp) && (rte_ipv6_addr_eq_prefix(&tmp->ip, &tmp_ip, depth) && - (tmp->depth > depth))) + (depth_match(tmp, depth, mode)))) return tmp; } tmp = (tmp->parent != NULL) ? tmp->parent->right : NULL; @@ -227,7 +235,7 @@ rte_rib6_get_nxt(struct rte_rib6 *rib, while (tmp) { if (is_valid_node(tmp) && (rte_ipv6_addr_eq_prefix(&tmp->ip, &tmp_ip, depth) && - (tmp->depth > depth))) { + (depth_match(tmp, depth, mode)))) { prev = tmp; if (mode == RTE_RIB6_GET_NXT_COVER) return prev; diff --git a/lib/rib/rte_rib6.h b/lib/rib/rte_rib6.h index ed2761492bc8..1d8b56b89b13 100644 --- a/lib/rib/rte_rib6.h +++ b/lib/rib/rte_rib6.h @@ -32,6 +32,8 @@ enum rte_rib6_nxt_mode { RTE_RIB6_GET_NXT_ALL, /** get first matched subroutes in a RIB tree, excluding any exact match top-level route */ RTE_RIB6_GET_NXT_COVER, + /** get all subroutes in a RIB tree, including the exact match top-level route, if any */ + RTE_RIB6_GET_NXT_ALL_TOP, }; struct rte_rib6; @@ -184,6 +186,8 @@ rte_rib6_lookup_exact(struct rte_rib6 *rib, * get all prefixes from subtrie * -RTE_RIB6_GET_NXT_COVER * get only first more specific prefix even if it have more specifics + * -RTE_RIB6_GET_NXT_ALL_TOP + * get the top-level exact matching prefix, if any * @return * pointer to the next more specific prefix * NULL if there is no prefixes left -- 2.54.0
