patch 'fib6: fix tbl8 reservation drift in trie' has been queued to stable release 24.11.7
luca.boccassi at gmail.com
luca.boccassi at gmail.com
Mon Jul 6 12:20:37 CEST 2026
Hi,
FYI, your patch has been queued to stable release 24.11.7
Note it hasn't been pushed to http://dpdk.org/browse/dpdk-stable yet.
It will be pushed if I get no objections before 07/05/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/bluca/dpdk-stable
This queued commit can be viewed at:
https://github.com/bluca/dpdk-stable/commit/e106b90e3fed4574ff9190ad3d648c03a58ec638
Thanks.
Luca Boccassi
---
>From e106b90e3fed4574ff9190ad3d648c03a58ec638 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 | 13 +++++++
lib/rib/version.map | 7 ++++
5 files changed, 159 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 79220a88b1..6e87bc69b4 100644
--- a/app/test/test_fib6.c
+++ b/app/test/test_fib6.c
@@ -22,6 +22,7 @@ static int32_t test_free_null(void);
static int32_t test_add_del_invalid(void);
static int32_t test_get_invalid(void);
static int32_t test_lookup(void);
+static int32_t test_drift(void);
#define MAX_ROUTES (1 << 16)
/** Maximum number of tbl8 for 2-byte entries */
@@ -387,6 +388,78 @@ test_lookup(void)
return TEST_SUCCESS;
}
+/*
+ * 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",
.setup = NULL,
@@ -397,6 +470,7 @@ static struct unit_test_suite fib6_fast_tests = {
TEST_CASE(test_add_del_invalid),
TEST_CASE(test_get_invalid),
TEST_CASE(test_lookup),
+ TEST_CASE(test_drift),
TEST_CASES_END()
}
};
diff --git a/lib/fib/trie.c b/lib/fib/trie.c
index 29ca8e3bf7..ab9e24caa2 100644
--- a/lib/fib/trie.c
+++ b/lib/fib/trie.c
@@ -12,6 +12,7 @@
#include <rte_rib6.h>
#include <rte_fib6.h>
+#include <rib6_internal.h>
#include "trie.h"
#ifdef CC_TRIE_AVX512_SUPPORT
@@ -506,19 +507,47 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
return 0;
}
+/*
+ * 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,
uint8_t depth, uint64_t next_hop, int op)
{
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))
return -EINVAL;
@@ -531,37 +560,6 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
ip_masked = *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) {
case RTE_FIB6_ADD:
@@ -576,12 +574,16 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
return ret;
}
- 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);
if (parent != NULL) {
@@ -595,7 +597,7 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
return ret;
}
successfully_added:
- dp->rsvd_tbl8s += depth_diff;
+ dp->rsvd_tbl8s += new_levels;
return 0;
case RTE_FIB6_DEL:
if (node == NULL)
@@ -613,9 +615,10 @@ 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:
break;
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 84c47fed6d..a36a128d01 100644
--- a/lib/rib/rte_rib6.c
+++ b/lib/rib/rte_rib6.c
@@ -18,6 +18,7 @@
#include <rte_rib6.h>
#include "rib_log.h"
+#include "rib6_internal.h"
#define RTE_RIB_VALID_NODE 1
/* Maximum length of a RIB6 name. */
@@ -415,6 +416,18 @@ rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
return 0;
}
+bool
+rte_rib6_node_has_children(const struct rte_rib6_node *node)
+{
+ return node->left != NULL || node->right != NULL;
+}
+
+struct rte_rib6_node *
+rte_rib6_get_parent(const struct rte_rib6_node *node)
+{
+ return node->parent;
+}
+
void *
rte_rib6_get_ext(struct rte_rib6_node *node)
{
diff --git a/lib/rib/version.map b/lib/rib/version.map
index 145d9c2602..f0949b97ff 100644
--- a/lib/rib/version.map
+++ b/lib/rib/version.map
@@ -32,3 +32,10 @@ DPDK_25 {
local: *;
};
+
+INTERNAL {
+ global:
+
+ rte_rib6_node_has_children;
+ rte_rib6_get_parent;
+};
--
2.47.3
---
Diff of the applied patch vs upstream commit (please double-check if non-empty:
---
--- - 2026-07-03 12:55:48.394386952 +0100
+++ 0045-fib6-fix-tbl8-reservation-drift-in-trie.patch 2026-07-03 12:55:46.674574086 +0100
@@ -1 +1 @@
-From 7ff51847e2704448ecbd59d4168842ccb074cfd4 Mon Sep 17 00:00:00 2001
+From e106b90e3fed4574ff9190ad3d648c03a58ec638 Mon Sep 17 00:00:00 2001
@@ -5,0 +6,2 @@
+[ upstream commit 7ff51847e2704448ecbd59d4168842ccb074cfd4 ]
+
@@ -39 +40,0 @@
-Cc: stable at dpdk.org
@@ -47,2 +48,3 @@
- lib/rib/rte_rib6.c | 15 ++++++++
- 4 files changed, 154 insertions(+), 40 deletions(-)
+ lib/rib/rte_rib6.c | 13 +++++++
+ lib/rib/version.map | 7 ++++
+ 5 files changed, 159 insertions(+), 40 deletions(-)
@@ -52 +54 @@
-index fffb590dbf..c4283f3f2d 100644
+index 79220a88b1..6e87bc69b4 100644
@@ -55 +57,3 @@
-@@ -25,6 +25,7 @@ static int32_t test_get_invalid(void);
+@@ -22,6 +22,7 @@ static int32_t test_free_null(void);
+ static int32_t test_add_del_invalid(void);
+ static int32_t test_get_invalid(void);
@@ -57,2 +60,0 @@
- static int32_t test_invalid_rcu(void);
- static int32_t test_fib_rcu_sync_rw(void);
@@ -63,2 +65,2 @@
-@@ -599,6 +600,78 @@ error:
- return status == 0 ? TEST_SUCCESS : TEST_FAILED;
+@@ -387,6 +388,78 @@ test_lookup(void)
+ return TEST_SUCCESS;
@@ -142 +144,3 @@
-@@ -611,6 +684,7 @@ static struct unit_test_suite fib6_fast_tests = {
+@@ -397,6 +470,7 @@ static struct unit_test_suite fib6_fast_tests = {
+ TEST_CASE(test_add_del_invalid),
+ TEST_CASE(test_get_invalid),
@@ -144,2 +147,0 @@
- TEST_CASE(test_invalid_rcu),
- TEST_CASE(test_fib_rcu_sync_rw),
@@ -151 +153 @@
-index 99272f45bd..187360d1c8 100644
+index 29ca8e3bf7..ab9e24caa2 100644
@@ -154 +156 @@
-@@ -13,6 +13,7 @@
+@@ -12,6 +12,7 @@
@@ -159 +160,0 @@
- #include "fib_log.h"
@@ -162 +163,2 @@
-@@ -534,19 +535,47 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
+ #ifdef CC_TRIE_AVX512_SUPPORT
+@@ -506,19 +507,47 @@ modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
@@ -213 +215 @@
-@@ -559,37 +588,6 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
+@@ -531,37 +560,6 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
@@ -251 +253 @@
-@@ -604,12 +602,16 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
+@@ -576,12 +574,16 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
@@ -271 +273 @@
-@@ -623,7 +625,7 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
+@@ -595,7 +597,7 @@ trie_modify(struct rte_fib6 *fib, const struct rte_ipv6_addr *ip,
@@ -280 +282 @@
-@@ -641,9 +643,10 @@ successfully_added:
+@@ -613,9 +615,10 @@ successfully_added:
@@ -322 +324 @@
-index ec8ff68e87..918ddbdfd3 100644
+index 84c47fed6d..a36a128d01 100644
@@ -325 +327 @@
-@@ -19,6 +19,7 @@
+@@ -18,6 +18,7 @@
@@ -333 +335 @@
-@@ -424,6 +425,20 @@ rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
+@@ -415,6 +416,18 @@ rte_rib6_get_depth(const struct rte_rib6_node *node, uint8_t *depth)
@@ -337 +338,0 @@
-+RTE_EXPORT_INTERNAL_SYMBOL(rte_rib6_node_has_children)
@@ -344 +344,0 @@
-+RTE_EXPORT_INTERNAL_SYMBOL(rte_rib6_get_parent)
@@ -351 +350,0 @@
- RTE_EXPORT_SYMBOL(rte_rib6_get_ext)
@@ -353,0 +353,16 @@
+ {
+diff --git a/lib/rib/version.map b/lib/rib/version.map
+index 145d9c2602..f0949b97ff 100644
+--- a/lib/rib/version.map
++++ b/lib/rib/version.map
+@@ -32,3 +32,10 @@ DPDK_25 {
+
+ local: *;
+ };
++
++INTERNAL {
++ global:
++
++ rte_rib6_node_has_children;
++ rte_rib6_get_parent;
++};
More information about the stable
mailing list