[PATCH v1 5/5] fib6: speed up tbl8 reservation accounting

[Maxime Leroy]

Replace the local count_empty_levels() helper, which issued up to 13
rte_rib6_get_nxt() calls each descending the binary tree from root,
with the new __rte_internal rte_rib6_count_empty_supernets(). The
latter descends once and consults the valid_descendants counter
maintained inside rte_rib6, answering all byte boundary questions
in O(tree depth) with O(1) work per boundary.

For a /128 ADD with ancestors at every byte boundary, this reduces
the worst-case query cost from 13 trie descents to 1.

Signed-off-by: Maxime Leroy <maxime at leroys.fr>
---
 lib/fib/trie.c | 30 +++---------------------------
 1 file changed, 3 insertions(+), 27 deletions(-)

diff --git a/lib/fib/trie.c b/lib/fib/trie.c
index 44b90f72ff..b6ef626fd4 100644
--- a/lib/fib/trie.c
+++ b/lib/fib/trie.c
@@ -13,6 +13,7 @@
 
 #include <rte_rib6.h>
 #include <rte_fib6.h>
+#include <rib6_internal.h>
 #include "fib_log.h"
 #include "trie.h"
 
@@ -534,31 +535,6 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
 	return 0;
 }
 
-/*
- * Count byte boundaries between 24 and CEIL(depth, 8) where the
- * supernet of ip has no descendant in the RIB. This is the number of
- * new tbl8 levels an ADD of ip/depth would introduce, or the number
- * to free at DEL once the prefix has been removed from the RIB.
- *
- * A NULL answer at level L propagates upwards: narrower supernets at
- * L+8, L+16, ... are subsets of S_L and cannot contain descendants
- * either. The loop stops at the first NULL and tallies the remaining
- * boundaries in one shot.
- */
-static uint8_t
-count_empty_levels(struct rte_rib6 *rib, const struct rte_ipv6_addr *ip,
-	uint8_t depth)
-{
-	uint8_t level, top = RTE_ALIGN_CEIL(depth, 8);
-
-	for (level = 24; level < top; level += 8) {
-		if (rte_rib6_get_nxt(rib, ip, level, NULL,
-				RTE_RIB6_GET_NXT_COVER) == NULL)
-			return (top - level) >> 3;
-	}
-	return 0;
-}
-
 int
 trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
 	uint8_t depth, uint64_t next_hop, int op)
@@ -596,7 +572,7 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
 			return 0;
 		}
 
-		new_levels = count_empty_levels(rib, &ip_masked, depth);
+		new_levels = rte_rib6_count_empty_supernets(rib, &ip_masked, depth);
 		if (dp->rsvd_tbl8s + new_levels > dp->number_tbl8s)
 			return -ENOSPC;
 
@@ -635,7 +611,7 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
 		if (ret != 0)
 			return ret;
 		rte_rib6_remove(rib, &ip_masked, depth);
-		dp->rsvd_tbl8s -= count_empty_levels(rib, &ip_masked, depth);
+		dp->rsvd_tbl8s -= rte_rib6_count_empty_supernets(rib, &ip_masked, depth);
 		return 0;
 	default:
 		break;
-- 
2.43.0