patch 'fib6: fix tbl8 reservation drift in trie' has been queued to stable release 25.11.3
Kevin Traynor
ktraynor at redhat.com
Tue Jul 28 17:56:50 CEST 2026
Hi,
FYI, your patch has been queued to stable release 25.11.3
Note it hasn't been pushed to http://dpdk.org/browse/dpdk-stable yet.
It will be pushed if I get no objections before 08/01/26. So please
shout if anyone has objections.
Also note that after the patch there's a diff of the upstream commit vs the
patch applied to the branch. This will indicate if there was any rebasing
needed to apply to the stable branch. If there were code changes for rebasing
(ie: not only metadata diffs), please double check that the rebase was
correctly done.
Queued patches are on a temporary branch at:
https://github.com/kevintraynor/dpdk-stable
This queued commit can be viewed at:
https://github.com/kevintraynor/dpdk-stable/commit/39b1f0402a69f38d5eb271479ba45ce3e3bb7eb0
Thanks.
Kevin
---
>From 39b1f0402a69f38d5eb271479ba45ce3e3bb7eb0 Mon Sep 17 00:00:00 2001
From: Maxime Leroy <maxime at leroys.fr>
Date: Wed, 17 Jun 2026 10:23:58 +0200
Subject: [PATCH] fib6: fix tbl8 reservation drift in trie
[ upstream commit 7ff51847e2704448ecbd59d4168842ccb074cfd4 ]
trie_modify() maintained rsvd_tbl8s incrementally: it added a
depth_diff at ADD and subtracted one at DEL. Each depth_diff was an
independent estimate derived from the covering parent returned by a
lookup at the time of the operation. The parent seen at an ADD could
differ from the one seen at the matching DEL (a covering parent added
or removed in between), so the amount subtracted did not match the
amount added. rsvd_tbl8s was not tied to any function of the current
route set, so nothing corrected the accumulating error; it eventually
wrapped to UINT32_MAX, rejecting all subsequent /25+ ADDs with -ENOSPC.
Define rsvd_tbl8s as the number of tbl8 levels the current route set
needs: one per byte boundary (24, 32, ..., 120) whose supernet holds
at least one longer prefix. count_empty_levels(node) returns how many
of those levels the node occupies on its own in the committed RIB:
zero if it still has more specifics, otherwise CEIL(depth, 8) -
CEIL(parent_depth, 8) in tbl8 units (has_children + parent depth). On
ADD that is the levels the node is first to occupy; on DEL the levels
it is last to vacate. The per-node increment and decrement need not
match (deleting a prefix that still has a more specific frees nothing,
and that level is released later by whichever prefix leaves last), yet
rsvd_tbl8s stays equal to the number of occupied levels at every step,
so it tracks the RIB exactly and cannot drift.
Add the internal RIB helpers rte_rib6_node_has_children() and
rte_rib6_get_parent() used by the count.
Finally, add coverage for this issue.
test_drift covers the asymmetric ADD parent / ADD children / DEL
parent / DEL children sequence that wraps rsvd_tbl8s past zero in a
single iteration. After the wrap the next /25+ ADD is rejected with
-ENOSPC even though the tbl8 pool is empty.
Fixes: c3e12e0f0354 ("fib: add dataplane algorithm for IPv6")
Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin at intel.com>
Signed-off-by: Maxime Leroy <maxime at leroys.fr>
---
app/test/test_fib6.c | 74 ++++++++++++++++++++++++++++++++++++
lib/fib/trie.c | 83 +++++++++++++++++++++--------------------
lib/rib/rib6_internal.h | 22 +++++++++++
lib/rib/rte_rib6.c | 15 ++++++++
4 files changed, 154 insertions(+), 40 deletions(-)
create mode 100644 lib/rib/rib6_internal.h
diff --git a/app/test/test_fib6.c b/app/test/test_fib6.c
index 843a4086c1..045b392886 100644
--- a/app/test/test_fib6.c
+++ b/app/test/test_fib6.c
@@ -26,4 +26,5 @@ static int32_t test_lookup(void);
static int32_t test_invalid_rcu(void);
static int32_t test_fib_rcu_sync_rw(void);
+static int32_t test_drift(void);
#define MAX_ROUTES (1 << 16)
@@ -600,4 +601,76 @@ error:
}
+/*
+ * Reproducer for the rsvd_tbl8s drift bug. depth_diff used to maintain
+ * rsvd_tbl8s is computed from the current RIB state, so it is not
+ * invariant between the ADD of a prefix and its later DEL when a
+ * covering parent prefix is removed in between.
+ *
+ * Layout: one /28 parent (fcde::/28) and three /48 siblings under it
+ * (fcde:0:6000::/48, fcde:1:6000::/48, fcde:2:6000::/48). The second
+ * hextet's high 12 bits are zero, so the three /48 IPs all fall inside
+ * the /28.
+ *
+ * One asymmetric sequence is enough to wrap the counter:
+ * ADD /28 rsvd_tbl8s += 1
+ * ADD /48 child_0,1,2 (with /28 parent) rsvd_tbl8s += 2 each (+6)
+ * DEL /28 (sibling /48 found) rsvd_tbl8s -= 0
+ * DEL /48 child_0,1,2 (no parent left) rsvd_tbl8s -= 3 each (-9)
+ */
+static int32_t
+test_drift(void)
+{
+ struct rte_fib6_conf config = { 0 };
+ struct rte_fib6 *fib;
+ struct rte_ipv6_addr parent =
+ RTE_IPV6(0xfcde, 0, 0, 0, 0, 0, 0, 0);
+ struct rte_ipv6_addr child[3] = {
+ RTE_IPV6(0xfcde, 0, 0x6000, 0, 0, 0, 0, 0),
+ RTE_IPV6(0xfcde, 1, 0x6000, 0, 0, 0, 0, 0),
+ RTE_IPV6(0xfcde, 2, 0x6000, 0, 0, 0, 0, 0),
+ };
+ unsigned int c;
+ int ret;
+
+ config.max_routes = 1024;
+ config.rib_ext_sz = 0;
+ config.default_nh = 0;
+ config.type = RTE_FIB6_TRIE;
+ config.trie.nh_sz = RTE_FIB6_TRIE_2B;
+ config.trie.num_tbl8 = 256;
+
+ fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config);
+ RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+ ret = rte_fib6_add(fib, &parent, 28, 0xa);
+ RTE_TEST_ASSERT(ret == 0, "ADD /28 failed (ret=%d)\n", ret);
+
+ for (c = 0; c < 3; c++) {
+ ret = rte_fib6_add(fib, &child[c], 48, 0xb + c);
+ RTE_TEST_ASSERT(ret == 0,
+ "ADD /48 child %u failed (ret=%d)\n", c, ret);
+ }
+
+ ret = rte_fib6_delete(fib, &parent, 28);
+ RTE_TEST_ASSERT(ret == 0, "DEL /28 failed (ret=%d)\n", ret);
+
+ for (c = 0; c < 3; c++) {
+ ret = rte_fib6_delete(fib, &child[c], 48);
+ RTE_TEST_ASSERT(ret == 0,
+ "DEL /48 child %u failed (ret=%d)\n", c, ret);
+ }
+
+ /* Pre-fix: -ENOSPC. Post-fix: succeeds. */
+ ret = rte_fib6_add(fib, &parent, 28, 0xe);
+ RTE_TEST_ASSERT(ret == 0,
+ "Fresh ADD /28 spuriously failed (ret=%d)\n", ret);
+
+ ret = rte_fib6_delete(fib, &parent, 28);
+ RTE_TEST_ASSERT(ret == 0, "Final DEL /28 failed (ret=%d)\n", ret);
+
+ rte_fib6_free(fib);
+ return TEST_SUCCESS;
+}
+
static struct unit_test_suite fib6_fast_tests = {
.suite_name = "fib6 autotest",
@@ -612,4 +685,5 @@ static struct unit_test_suite fib6_fast_tests = {
TEST_CASE(test_invalid_rcu),
TEST_CASE(test_fib_rcu_sync_rw),
+ TEST_CASE(test_drift),
TEST_CASES_END()
}
diff --git a/lib/fib/trie.c b/lib/fib/trie.c
index 99272f45bd..187360d1c8 100644
--- a/lib/fib/trie.c
+++ b/lib/fib/trie.c
@@ -14,4 +14,5 @@
#include <rte_rib6.h>
#include <rte_fib6.h>
+#include <rib6_internal.h>
#include "fib_log.h"
#include "trie.h"
@@ -535,4 +536,33 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
}
+/*
+ * Count number of TBL8s that can be freed after deleting a prefix or allocated
+ * after adding a prefix.
+ */
+static uint8_t
+count_empty_levels(const struct rte_rib6_node *node)
+{
+ struct rte_rib6_node *parent;
+ uint8_t depth, parent_depth = 24;
+
+ /* more specifics present */
+ if (rte_rib6_node_has_children(node))
+ return 0;
+
+ rte_rib6_get_depth(node, &depth);
+ depth = RTE_MAX(depth, 24);
+
+ /* we know parent depth lt a target node depth
+ * also, there exists tbl8 path up to RTE_ALIGN_CEIL(parent depth, 8)
+ */
+ parent = rte_rib6_get_parent(node);
+ if (parent != NULL) {
+ rte_rib6_get_depth(parent, &parent_depth);
+ parent_depth = RTE_MAX(parent_depth, 24);
+ }
+
+ return (RTE_ALIGN_CEIL(depth, 8) - RTE_ALIGN_CEIL(parent_depth, 8)) >> 3;
+}
+
int
trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
@@ -541,11 +571,10 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
struct rte_trie_tbl *dp;
struct rte_rib6 *rib;
- struct rte_rib6_node *tmp = NULL;
struct rte_rib6_node *node;
struct rte_rib6_node *parent;
- struct rte_ipv6_addr ip_masked, tmp_ip;
+ struct rte_ipv6_addr ip_masked;
int ret = 0;
uint64_t par_nh, node_nh;
- uint8_t tmp_depth, depth_diff = 0, parent_depth = 24;
+ uint8_t new_levels;
if ((fib == NULL) || (ip == NULL) || (depth > RTE_IPV6_MAX_DEPTH))
@@ -560,35 +589,4 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
rte_ipv6_addr_mask(&ip_masked, depth);
- if (depth > 24) {
- tmp = rte_rib6_get_nxt(rib, &ip_masked,
- RTE_ALIGN_FLOOR(depth, 8), NULL,
- RTE_RIB6_GET_NXT_ALL);
- if (tmp && op == RTE_FIB6_DEL) {
- /* in case of delete operation, skip the prefix we are going to delete */
- rte_rib6_get_ip(tmp, &tmp_ip);
- rte_rib6_get_depth(tmp, &tmp_depth);
- if (rte_ipv6_addr_eq(&ip_masked, &tmp_ip) && depth == tmp_depth)
- tmp = rte_rib6_get_nxt(rib, &ip_masked,
- RTE_ALIGN_FLOOR(depth, 8), tmp, RTE_RIB6_GET_NXT_ALL);
- }
-
- if (tmp == NULL) {
- tmp = rte_rib6_lookup(rib, ip);
- /**
- * in case of delete operation, lookup returns the prefix
- * we are going to delete. Find the parent.
- */
- if (tmp && op == RTE_FIB6_DEL)
- tmp = rte_rib6_lookup_parent(tmp);
-
- if (tmp != NULL) {
- rte_rib6_get_depth(tmp, &tmp_depth);
- parent_depth = RTE_MAX(tmp_depth, 24);
- }
- depth_diff = RTE_ALIGN_CEIL(depth, 8) -
- RTE_ALIGN_CEIL(parent_depth, 8);
- depth_diff = depth_diff >> 3;
- }
- }
node = rte_rib6_lookup_exact(rib, &ip_masked, depth);
switch (op) {
@@ -605,10 +603,14 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
}
- if ((depth > 24) && (dp->rsvd_tbl8s + depth_diff > dp->number_tbl8s))
- return -ENOSPC;
-
node = rte_rib6_insert(rib, &ip_masked, depth);
if (node == NULL)
return -rte_errno;
+
+ new_levels = count_empty_levels(node);
+ if (dp->rsvd_tbl8s + new_levels > dp->number_tbl8s) {
+ rte_rib6_remove(rib, &ip_masked, depth);
+ return -ENOSPC;
+ }
+
rte_rib6_set_nh(node, next_hop);
parent = rte_rib6_lookup_parent(node);
@@ -624,5 +626,5 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
}
successfully_added:
- dp->rsvd_tbl8s += depth_diff;
+ dp->rsvd_tbl8s += new_levels;
return 0;
case RTE_FIB6_DEL:
@@ -642,7 +644,8 @@ successfully_added:
if (ret != 0)
return ret;
- rte_rib6_remove(rib, ip, depth);
- dp->rsvd_tbl8s -= depth_diff;
+ dp->rsvd_tbl8s -= count_empty_levels(node);
+ rte_rib6_remove(rib, &ip_masked, depth);
+
return 0;
default:
diff --git a/lib/rib/rib6_internal.h b/lib/rib/rib6_internal.h
new file mode 100644
index 0000000000..6d5218a08f
--- /dev/null
+++ b/lib/rib/rib6_internal.h
@@ -0,0 +1,22 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2026 Maxime Leroy, Free Mobile
+ */
+
+#ifndef RIB6_INTERNAL_H
+#define RIB6_INTERNAL_H
+
+#include <stdbool.h>
+
+#include <rte_compat.h>
+
+struct rte_rib6_node;
+
+__rte_internal
+bool
+rte_rib6_node_has_children(const struct rte_rib6_node *node);
+
+__rte_internal
+struct rte_rib6_node *
+rte_rib6_get_parent(const struct rte_rib6_node *node);
+
+#endif /* RIB6_INTERNAL_H */
diff --git a/lib/rib/rte_rib6.c b/lib/rib/rte_rib6.c
index ec8ff68e87..918ddbdfd3 100644
--- a/lib/rib/rte_rib6.c
+++ b/lib/rib/rte_rib6.c
@@ -20,4 +20,5 @@
#include "rib_log.h"
+#include "rib6_internal.h"
#define RTE_RIB_VALID_NODE 1
@@ -425,4 +426,18 @@ rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
}
+RTE_EXPORT_INTERNAL_SYMBOL(rte_rib6_node_has_children)
+bool
+rte_rib6_node_has_children(const struct rte_rib6_node *node)
+{
+ return node->left != NULL || node->right != NULL;
+}
+
+RTE_EXPORT_INTERNAL_SYMBOL(rte_rib6_get_parent)
+struct rte_rib6_node *
+rte_rib6_get_parent(const struct rte_rib6_node *node)
+{
+ return node->parent;
+}
+
RTE_EXPORT_SYMBOL(rte_rib6_get_ext)
void *
--
2.55.0
---
Diff of the applied patch vs upstream commit (please double-check if non-empty:
---
--- - 2026-07-28 16:54:53.125019442 +0100
+++ 0080-fib6-fix-tbl8-reservation-drift-in-trie.patch 2026-07-28 16:54:50.835794449 +0100
@@ -1 +1 @@
-From 7ff51847e2704448ecbd59d4168842ccb074cfd4 Mon Sep 17 00:00:00 2001
+From 39b1f0402a69f38d5eb271479ba45ce3e3bb7eb0 Mon Sep 17 00:00:00 2001
@@ -5,0 +6,2 @@
+[ upstream commit 7ff51847e2704448ecbd59d4168842ccb074cfd4 ]
+
@@ -39 +40,0 @@
-Cc: stable at dpdk.org
@@ -52 +53 @@
-index fffb590dbf..c4283f3f2d 100644
+index 843a4086c1..045b392886 100644
More information about the stable
mailing list