Hi Robin,
Thanks for the patch, see comments inline
On 6/10/2025 3:53 PM, Robin Jarry wrote:
Currently, for the TRIE algorithm (actually, it should be called
DIR-24-8-8-8-8-8-8-8-8-8-8-8-8),
Technically yes, but we can look at this structure as an n-ary tree
(tree with associativity equal to n), where the first layer of the tree
has associativity of 2^24 and subsequent layers (up to max 13) have
associativity of 2^8. It has properties to keep prefixes, so it can also
be considered a Trie.
the tbl8 group is freed even though the
readers might be using the tbl8 group entries. The freed tbl8 group can
be reallocated quickly. As a result, lookup may be performed
incorrectly.
To address that, RCU QSBR is integrated for safe tbl8 group reclamation.
Cc: Vladimir Medvedkin <[email protected]>
Signed-off-by: Robin Jarry <[email protected]>
---
Notes:
This is a semi-copy-paste of the FIB4 implementation.
I couldn't understand the implementation of trie_modify with regard to
depth_diff handling.
The unit tests fail because depth_diff is always 0 when deleting a route
which causes any subsequent add to fail with a -ENOSPC error.
Vladimir, could you give some more insights on the matter?
I'll be happy to explain.
depth_diff represents a number of layers(tbl8 entries) that should be
built towards the target new prefix(prefix we add) from existing least
significant prefix that covers prefix we are going to add, or number of
destroyed layers from the prefix we are going to delete to the
next least significant prefix that covers prefix we are going to delete.
Here, we determine whether a prebuilt path already exists for the
prefix’s location or if it needs to be created (by allocating depth_diff
tbl8 entries). Or find the number of tbl8 we can free.
There is a bug in the current implementation, where the number of tbl8
entries to be freed is always zero when a prefix is deleted. I’ll send a
fix for this issue, please refer to it for details.
app/test/test_fib6.c | 214 +++++++++++++++++++++++++++++++++++++++++++
lib/fib/rte_fib6.c | 15 +++
lib/fib/rte_fib6.h | 54 +++++++++++
lib/fib/trie.c | 89 ++++++++++++++++--
lib/fib/trie.h | 8 ++
5 files changed, 373 insertions(+), 7 deletions(-)
<snip>
diff --git a/lib/fib/rte_fib6.h b/lib/fib/rte_fib6.h
index 42e613870886..a4e1d34fb1c4 100644
--- a/lib/fib/rte_fib6.h
+++ b/lib/fib/rte_fib6.h
@@ -19,6 +19,7 @@
#include <rte_common.h>
#include <rte_ip6.h>
+#include <rte_rcu_qsbr.h>
#ifdef __cplusplus
extern "C" {
@@ -31,6 +32,19 @@ extern "C" {
struct rte_fib6;
struct rte_rib6;
+/** @internal Default RCU defer queue entries to reclaim in one go. */
+#define RTE_FIB6_RCU_DQ_RECLAIM_MAX 16
+/** @internal Default RCU defer queue size. */
+#define RTE_FIB6_RCU_DQ_RECLAIM_SZ 128
+
+/** RCU reclamation modes */
+enum rte_fib6_qsbr_mode {
+ /** Create defer queue for reclaim. */
+ RTE_FIB6_QSBR_MODE_DQ = 0,
+ /** Use blocking mode reclaim. No defer queue created. */
+ RTE_FIB6_QSBR_MODE_SYNC
+};
+
/** Type of FIB struct */
enum rte_fib6_type {
RTE_FIB6_DUMMY, /**< RIB6 tree based FIB */
@@ -82,6 +96,26 @@ struct rte_fib6_conf {
};
};
+/** FIB RCU QSBR configuration structure. */
+struct rte_fib6_rcu_config {
+ /** RCU QSBR variable. */
+ struct rte_rcu_qsbr *v;
+ /** Mode of RCU QSBR. See RTE_FIB_QSBR_MODE_xxx.
typo, did you mean RTE_FIB6_QSBR_MODE_xxx ?
+ * Default: RTE_FIB6_QSBR_MODE_DQ, create defer queue for reclaim.
+ */
+ enum rte_fib6_qsbr_mode mode;
+ /** RCU defer queue size.
+ * Default: RTE_FIB6_RCU_DQ_RECLAIM_SZ.
+ */
+ uint32_t dq_size;
+ /** Threshold to trigger auto reclaim. */
+ uint32_t reclaim_thd;
+ /** Max entries to reclaim in one go.
+ * Default: RTE_FIB6_RCU_DQ_RECLAIM_MAX.
+ */
+ uint32_t reclaim_max;
+};
+
/**
* Free an FIB object.
*
@@ -217,6 +251,26 @@ rte_fib6_get_rib(struct rte_fib6 *fib);
int
rte_fib6_select_lookup(struct rte_fib6 *fib, enum rte_fib6_lookup_type type);
+/**
+ * Associate RCU QSBR variable with a FIB object.
+ *
+ * @param fib
+ * FIB object handle
+ * @param cfg
+ * RCU QSBR configuration
+ * @return
+ * On success - 0
+ * On error - 1 with error code set in rte_errno.
Please fix this doxygen documentation to reflect actual behavior of the
function with respect to return value
+ * Possible rte_errno codes are:
+ * - EINVAL - invalid pointer
+ * - EEXIST - already added QSBR
+ * - ENOMEM - memory allocation failure
+ * - ENOTSUP - not supported by configured dataplane algorithm
+ */
+__rte_experimental
+int
+rte_fib6_rcu_qsbr_add(struct rte_fib6 *fib, struct rte_fib6_rcu_config *cfg);
+
<snip>
--
Regards,
Vladimir
