[RFC PATCH v2 4/7] fib: add DIR8-16-8 algorithm
Vladimir Medvedkin
vladimir.medvedkin at intel.com
Wed Oct 14 20:39:18 CEST 2026
Add an IPv4 dataplane algorithm splitting the address in three strides
of 8, 16 and 8 bits: a 256 entry root table resolves the first stride,
then 65536 entry groups (tbl16) and 256 entry groups (tbl8) allocated
from pools sized on FIB creation resolve the next ones. A lookup needs
one to three memory accesses.
Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin at intel.com>
---
app/test-fib/main.c | 86 +++-
app/test/test_fib.c | 101 +++-
app/test/test_fib_perf.c | 65 ++-
doc/guides/prog_guide/fib_lib.rst | 26 ++
doc/guides/rel_notes/release_26_11.rst | 5 +
lib/fib/dir8_16_8.c | 614 +++++++++++++++++++++++++
lib/fib/dir8_16_8.h | 143 ++++++
lib/fib/dir8_16_8_avx512.c | 142 ++++++
lib/fib/dir8_16_8_avx512.h | 16 +
lib/fib/meson.build | 4 +-
lib/fib/rte_fib.c | 24 +-
lib/fib/rte_fib.h | 17 +-
12 files changed, 1204 insertions(+), 39 deletions(-)
create mode 100644 lib/fib/dir8_16_8.c
create mode 100644 lib/fib/dir8_16_8.h
create mode 100644 lib/fib/dir8_16_8_avx512.c
create mode 100644 lib/fib/dir8_16_8_avx512.h
diff --git a/app/test-fib/main.c b/app/test-fib/main.c
index 0bc8dd2aa4..be1ba20277 100644
--- a/app/test-fib/main.c
+++ b/app/test-fib/main.c
@@ -39,6 +39,8 @@
#define DEF_LOOKUP_IPS_NUM 0x100000
#define BURST_SZ 64
#define DEFAULT_LPM_TBL8 100000U
+/* One second level (16 bit stride) group per /8 covers the whole space. */
+#define DIR8_16_8_MAX_TBL16 256U
#define CMP_FLAG (1 << 0)
#define CMP_ALL_FLAG (1 << 1)
@@ -46,9 +48,12 @@
#define FIB_RIB_TYPE (1 << 3)
#define FIB_V4_DIR_TYPE (1 << 4)
#define FIB_V6_TRIE_TYPE (1 << 4)
-#define FIB_TYPE_MASK (FIB_RIB_TYPE|FIB_V4_DIR_TYPE|FIB_V6_TRIE_TYPE)
+#define FIB_V4_DIR_8_16_8_TYPE (1 << 5)
+#define FIB_TYPE_MASK (FIB_RIB_TYPE|FIB_V4_DIR_TYPE|FIB_V6_TRIE_TYPE| \
+ FIB_V4_DIR_8_16_8_TYPE)
#define SHUFFLE_FLAG (1 << 7)
#define DRY_RUN_FLAG (1 << 8)
+#define ENT_SZ_FLAG (1 << 9)
static char *distrib_string;
static char line[LINE_MAX];
@@ -147,6 +152,8 @@ get_fib_type(void)
} else {
if ((config.flags & FIB_TYPE_MASK) == FIB_V4_DIR_TYPE)
return RTE_FIB_DIR24_8;
+ if ((config.flags & FIB_TYPE_MASK) == FIB_V4_DIR_8_16_8_TYPE)
+ return RTE_FIB_DIR8_16_8;
if ((config.flags & FIB_TYPE_MASK) == FIB_RIB_TYPE)
return RTE_FIB_DUMMY;
}
@@ -619,18 +626,20 @@ print_usage(void)
"[-b <fib algorithm>]\n\tavailable options for ipv4\n"
"\t\trib - RIB based FIB\n"
"\t\tdir - DIR24_8 based FIB\n"
+ "\t\tdir8_16_8 - DIR8_16_8 based FIB (8 byte next hop)\n"
"\tavailable options for ipv6:\n"
"\t\trib - RIB based FIB\n"
"\t\ttrie - TRIE based FIB\n"
"defaults are: dir for ipv4 and trie for ipv6\n"
"[-e <entry size (valid only for dir and trie fib types): "
"1/2/4/8 (default 4)>]\n"
- "[-g <number of tbl8's for dir24_8 or trie FIBs>]\n"
+ "[-g <number of tbl8's for dir24_8, dir8_16_8 or trie FIBs>]\n"
"[-w <path to the file to dump routing table>]\n"
"[-u <path to the file to dump ip's for lookup>]\n"
"[-v <type of lookup function:"
"\ts1, s2, s3 (3 types of scalar), v (vector) -"
" for DIR24_8 based FIB\n"
+ "\ts, v - for DIR8_16_8 based FIB\n"
"\ts, v - for TRIE based ipv6 FIB>]\n",
config.prgname);
}
@@ -665,6 +674,22 @@ check_config(void)
printf("-e 1 is valid only for ipv4\n");
return -1;
}
+
+ if ((config.flags & FIB_V4_DIR_8_16_8_TYPE) &&
+ (config.flags & IPV6_FLAG)) {
+ printf("dir8_16_8 fib type is only valid for ipv4\n");
+ return -1;
+ }
+ /* The dir8_16_8 fib type only supports 8 byte next hops. */
+ if ((config.flags & FIB_TYPE_MASK) == FIB_V4_DIR_8_16_8_TYPE) {
+ if ((config.flags & ENT_SZ_FLAG) && config.ent_sz != 8) {
+ printf("-e %u is not valid for the dir8_16_8 fib type, "
+ "only 8 byte next hops are supported\n",
+ config.ent_sz);
+ return -1;
+ }
+ config.ent_sz = 8;
+ }
return 0;
}
@@ -744,6 +769,9 @@ parse_opts(int argc, char **argv)
} else if (strcmp(optarg, "dir") == 0) {
config.flags &= ~FIB_TYPE_MASK;
config.flags |= FIB_V4_DIR_TYPE;
+ } else if (strcmp(optarg, "dir8_16_8") == 0) {
+ config.flags &= ~FIB_TYPE_MASK;
+ config.flags |= FIB_V4_DIR_8_16_8_TYPE;
} else if (strcmp(optarg, "trie") == 0) {
config.flags &= ~FIB_TYPE_MASK;
config.flags |= FIB_V6_TRIE_TYPE;
@@ -757,6 +785,7 @@ parse_opts(int argc, char **argv)
print_usage();
rte_exit(-EINVAL, "Invalid option -e\n");
}
+ config.flags |= ENT_SZ_FLAG;
break;
case 'g':
errno = 0;
@@ -817,6 +846,35 @@ print_depth_err(void)
"-d 0:0 option or remove /0 prefix from routes file\n");
}
+static int
+select_lookup_fn_v4(struct rte_fib *fib, enum rte_fib_type type)
+{
+ enum rte_fib_lookup_type lookup_type;
+
+ if (type == RTE_FIB_DIR8_16_8) {
+ if (config.lookup_fn == 1)
+ lookup_type = RTE_FIB_LOOKUP_DIR8_16_8_SCALAR;
+ else if (config.lookup_fn == 2)
+ lookup_type = RTE_FIB_LOOKUP_DIR8_16_8_VECTOR_AVX512;
+ else
+ return -EINVAL;
+ } else if (type == RTE_FIB_DIR24_8) {
+ if (config.lookup_fn == 1)
+ lookup_type = RTE_FIB_LOOKUP_DIR24_8_SCALAR_MACRO;
+ else if (config.lookup_fn == 2)
+ lookup_type = RTE_FIB_LOOKUP_DIR24_8_VECTOR_AVX512;
+ else if (config.lookup_fn == 3)
+ lookup_type = RTE_FIB_LOOKUP_DIR24_8_SCALAR_INLINE;
+ else if (config.lookup_fn == 4)
+ lookup_type = RTE_FIB_LOOKUP_DIR24_8_SCALAR_UNI;
+ else
+ return -EINVAL;
+ } else {
+ return -EINVAL;
+ }
+ return rte_fib_select_lookup(fib, lookup_type);
+}
+
static int
run_v4(void)
{
@@ -853,6 +911,15 @@ run_v4(void)
conf.dir24_8.nh_sz = rte_ctz32(config.ent_sz);
conf.dir24_8.num_tbl8 = RTE_MIN(config.tbl8,
get_max_nh(conf.dir24_8.nh_sz));
+ } else if (conf.type == RTE_FIB_DIR8_16_8) {
+ /*
+ * DIR8_16_8 only supports 8 byte next hops. The first stride
+ * (8 bits) needs at most one second level group per /8, so 256
+ * groups always suffice. The third level (last 8 bits) groups
+ * are sized like the DIR24_8 tbl8s.
+ */
+ conf.dir8_16_8.num_tbl16 = DIR8_16_8_MAX_TBL16;
+ conf.dir8_16_8.num_tbl8 = config.tbl8;
}
fib = rte_fib_create("test", -1, &conf);
@@ -862,20 +929,7 @@ run_v4(void)
}
if (config.lookup_fn != 0) {
- if (config.lookup_fn == 1)
- ret = rte_fib_select_lookup(fib,
- RTE_FIB_LOOKUP_DIR24_8_SCALAR_MACRO);
- else if (config.lookup_fn == 2)
- ret = rte_fib_select_lookup(fib,
- RTE_FIB_LOOKUP_DIR24_8_VECTOR_AVX512);
- else if (config.lookup_fn == 3)
- ret = rte_fib_select_lookup(fib,
- RTE_FIB_LOOKUP_DIR24_8_SCALAR_INLINE);
- else if (config.lookup_fn == 4)
- ret = rte_fib_select_lookup(fib,
- RTE_FIB_LOOKUP_DIR24_8_SCALAR_UNI);
- else
- ret = -EINVAL;
+ ret = select_lookup_fn_v4(fib, conf.type);
if (ret != 0) {
printf("Can not init lookup function\n");
return ret;
diff --git a/app/test/test_fib.c b/app/test/test_fib.c
index bd73399d56..bb8021c818 100644
--- a/app/test/test_fib.c
+++ b/app/test/test_fib.c
@@ -6,9 +6,12 @@
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
+#include <string.h>
+#include <inttypes.h>
#include <rte_ip.h>
#include <rte_log.h>
+#include <rte_byteorder.h>
#include <rte_fib.h>
#include <rte_malloc.h>
@@ -65,7 +68,7 @@ test_create_invalid(void)
"Call succeeded with invalid parameters\n");
config.max_routes = MAX_ROUTES;
- config.type = RTE_FIB_DIR24_8 + 1;
+ config.type = RTE_FIB_DIR8_16_8 + 1;
fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
RTE_TEST_ASSERT(fib == NULL,
"Call succeeded with invalid parameters\n");
@@ -84,6 +87,19 @@ test_create_invalid(void)
RTE_TEST_ASSERT(fib == NULL,
"Call succeeded with invalid parameters\n");
+ config.type = RTE_FIB_DIR8_16_8;
+ config.dir8_16_8.num_tbl16 = MAX_TBL8;
+ config.dir8_16_8.num_tbl8 = 0;
+ fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+ RTE_TEST_ASSERT(fib == NULL,
+ "Call succeeded with invalid parameters\n");
+
+ config.dir8_16_8.num_tbl16 = 0;
+ config.dir8_16_8.num_tbl8 = MAX_TBL8;
+ fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+ RTE_TEST_ASSERT(fib == NULL,
+ "Call succeeded with invalid parameters\n");
+
return TEST_SUCCESS;
}
@@ -376,6 +392,23 @@ test_lookup(void)
"Check_fib fails for DIR24_8_8B type\n");
rte_fib_free(fib);
+ config.type = RTE_FIB_DIR8_16_8;
+ config.dir8_16_8.num_tbl16 = 16;
+ config.dir8_16_8.num_tbl8 = MAX_TBL8;
+ fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+ RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+ ret = check_fib(fib);
+ RTE_TEST_ASSERT(ret == TEST_SUCCESS,
+ "Check_fib fails for DIR8_16_8 type\n");
+ /* The vector lookup is only available with a 512 bit SIMD width. */
+ if (rte_fib_select_lookup(fib,
+ RTE_FIB_LOOKUP_DIR8_16_8_VECTOR_AVX512) == 0) {
+ ret = check_fib(fib);
+ RTE_TEST_ASSERT(ret == TEST_SUCCESS,
+ "Check_fib fails for DIR8_16_8 type, AVX512 lookup\n");
+ }
+ rte_fib_free(fib);
+
return TEST_SUCCESS;
}
@@ -588,6 +621,71 @@ test_fib_rcu_sync_rw(void)
return status == 0 ? TEST_SUCCESS : TEST_FAILED;
}
+#define TEST_NUM_TBL16 16
+#define TEST_NUM_TBL8 64
+#define DEF_NH 77
+
+/*
+ * Network order lookups with every lookup implementation of DIR8_16_8, with a
+ * burst of two vector groups and a leftover.
+ */
+static int32_t
+test_lookup_network_order(void)
+{
+ const enum rte_fib_lookup_type types[] = {
+ RTE_FIB_LOOKUP_DIR8_16_8_SCALAR,
+ RTE_FIB_LOOKUP_DIR8_16_8_VECTOR_AVX512,
+ };
+ const uint32_t probes[] = {
+ RTE_IPV4(10, 2, 3, 4), /* /8 */
+ RTE_IPV4(10, 1, 1, 5), /* /24 */
+ RTE_IPV4(10, 1, 1, 7), /* /32 */
+ RTE_IPV4(8, 8, 8, 8), /* miss */
+ };
+ const uint64_t probe_nhs[] = { 100, 300, 400, DEF_NH };
+ struct rte_fib_conf cfg = { 0 };
+ struct rte_fib *fib;
+ uint32_t ips[17];
+ uint64_t nhs[17];
+ unsigned int i, t;
+
+ cfg.type = RTE_FIB_DIR8_16_8;
+ cfg.max_routes = 100;
+ cfg.default_nh = DEF_NH;
+ cfg.flags = RTE_FIB_F_LOOKUP_NETWORK_ORDER;
+ cfg.dir8_16_8.num_tbl16 = TEST_NUM_TBL16;
+ cfg.dir8_16_8.num_tbl8 = TEST_NUM_TBL8;
+
+ fib = rte_fib_create("fib_be", SOCKET_ID_ANY, &cfg);
+ RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n");
+
+ RTE_TEST_ASSERT(rte_fib_add(fib, RTE_IPV4(10, 0, 0, 0), 8, 100) == 0,
+ "add /8\n");
+ RTE_TEST_ASSERT(rte_fib_add(fib, RTE_IPV4(10, 1, 1, 0), 24, 300) == 0,
+ "add /24\n");
+ RTE_TEST_ASSERT(rte_fib_add(fib, RTE_IPV4(10, 1, 1, 7), 32, 400) == 0,
+ "add /32\n");
+ for (i = 0; i < RTE_DIM(ips); i++)
+ ips[i] = rte_cpu_to_be_32(probes[i % RTE_DIM(probes)]);
+
+ for (t = 0; t < RTE_DIM(types); t++) {
+ /* The vector lookup needs a 512 bit SIMD width. */
+ if (rte_fib_select_lookup(fib, types[t]) != 0)
+ continue;
+
+ memset(nhs, 0, sizeof(nhs));
+ RTE_TEST_ASSERT(rte_fib_lookup_bulk(fib, ips, nhs,
+ RTE_DIM(ips)) == 0, "lookup failed\n");
+ for (i = 0; i < RTE_DIM(ips); i++)
+ RTE_TEST_ASSERT(nhs[i] == probe_nhs[i % RTE_DIM(probes)],
+ "lookup type %u: ip %u got %"PRIu64"\n",
+ types[t], i, nhs[i]);
+ }
+ rte_fib_free(fib);
+
+ return TEST_SUCCESS;
+}
+
static struct unit_test_suite fib_fast_tests = {
.suite_name = "fib autotest",
.setup = NULL,
@@ -598,6 +696,7 @@ static struct unit_test_suite fib_fast_tests = {
TEST_CASE(test_add_del_invalid),
TEST_CASE(test_get_invalid),
TEST_CASE(test_lookup),
+ TEST_CASE(test_lookup_network_order),
TEST_CASE(test_invalid_rcu),
TEST_CASE(test_fib_rcu_sync_rw),
TEST_CASES_END()
diff --git a/app/test/test_fib_perf.c b/app/test/test_fib_perf.c
index 1b2ad04854..0967644316 100644
--- a/app/test/test_fib_perf.c
+++ b/app/test/test_fib_perf.c
@@ -7,6 +7,7 @@
#include <stdint.h>
#include <stdlib.h>
#include <math.h>
+#include <inttypes.h>
#include <rte_cycles.h>
#include <rte_random.h>
@@ -317,31 +318,16 @@ print_route_distribution(const struct route_rule *table, uint32_t n)
}
static int
-test_fib_perf(void)
+measure_fib_perf(const char *name, struct rte_fib_conf *config)
{
struct rte_fib *fib = NULL;
- struct rte_fib_conf config = { 0 };
-
- config.max_routes = 2000000;
- config.rib_ext_sz = 0;
- config.type = RTE_FIB_DIR24_8;
- config.default_nh = 0;
- config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B;
- config.dir24_8.num_tbl8 = 65535;
uint64_t begin, total_time;
unsigned int i, j;
uint32_t next_hop_add = 0xAA;
int status = 0;
int64_t count = 0;
- generate_large_route_rule_table();
-
- printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES);
-
- print_route_distribution(large_route_table,
- (uint32_t) NUM_ROUTE_ENTRIES);
-
- fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config);
+ fib = rte_fib_create(name, SOCKET_ID_ANY, config);
TEST_FIB_ASSERT(fib != NULL);
/* Measure add. */
@@ -407,4 +393,49 @@ test_fib_perf(void)
return 0;
}
+static int
+test_fib_perf(void)
+{
+ struct rte_fib_conf config = { 0 };
+
+ config.max_routes = 2000000;
+ config.rib_ext_sz = 0;
+ config.type = RTE_FIB_DIR24_8;
+ config.default_nh = 0;
+ config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B;
+ config.dir24_8.num_tbl8 = 65535;
+
+ generate_large_route_rule_table();
+
+ printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES);
+
+ print_route_distribution(large_route_table,
+ (uint32_t) NUM_ROUTE_ENTRIES);
+
+ return measure_fib_perf("fib_perf_dir24_8", &config);
+}
+
+static int
+test_fib_perf_dir8_16_8(void)
+{
+ struct rte_fib_conf config = { 0 };
+
+ config.max_routes = 2000000;
+ config.rib_ext_sz = 0;
+ config.type = RTE_FIB_DIR8_16_8;
+ config.default_nh = 0;
+ config.dir8_16_8.num_tbl16 = 256;
+ config.dir8_16_8.num_tbl8 = 1 << 16;
+
+ generate_large_route_rule_table();
+
+ printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES);
+
+ print_route_distribution(large_route_table,
+ (uint32_t) NUM_ROUTE_ENTRIES);
+
+ return measure_fib_perf("fib_perf_dir8_16_8", &config);
+}
+
REGISTER_PERF_TEST(fib_perf_autotest, test_fib_perf);
+REGISTER_PERF_TEST(fib_perf_dir8_16_8_autotest, test_fib_perf_dir8_16_8);
diff --git a/doc/guides/prog_guide/fib_lib.rst b/doc/guides/prog_guide/fib_lib.rst
index 41ab5764b6..c20759faaf 100644
--- a/doc/guides/prog_guide/fib_lib.rst
+++ b/doc/guides/prog_guide/fib_lib.rst
@@ -127,6 +127,32 @@ An entry in a tbl8 contains the following fields:
* 1 bit indicating if the lookup should proceed inside the tbl8.
+DIR-8-16-8
+~~~~~~~~~~
+
+This algorithm is a three level variant of DIR-24-8: the IPv4 address is split
+in strides of 8, 16 and 8 bits. The first level is a 256 entry root table, the
+second level is made of 65536 entry groups (``tbl16``) and the third level of
+256 entry groups (``tbl8``), both allocated from pools sized on FIB creation.
+A lookup needs one to three memory accesses. Only 8 byte next hop IDs are
+supported.
+
+This algorithm will be used if the ``RTE_FIB_DIR8_16_8`` type is configured as the
+dataplane algorithm on FIB creation.
+
+The main FIB configuration struct stores the dataplane parameters inside ``dir8_16_8``
+within the ``rte_fib_conf`` and it consists of:
+
+* ``num_tbl16``: The number of second level groups, at most one per /8 is ever
+ needed.
+
+* ``num_tbl8``: The number of third level groups.
+
+Compared to DIR-24-8, the root table is small (2 KB), which makes it suitable
+when many tables must be kept, at the price of an extra memory access for
+prefixes longer than 8 bits.
+
+
Use cases
---------
diff --git a/doc/guides/rel_notes/release_26_11.rst b/doc/guides/rel_notes/release_26_11.rst
index 03b4feae0f..04781a2761 100644
--- a/doc/guides/rel_notes/release_26_11.rst
+++ b/doc/guides/rel_notes/release_26_11.rst
@@ -206,6 +206,11 @@ New Features
when using ``RTE_UNCORE_PM_ENV_AUTO_DETECT``,
instead of defaulting only to the Intel uncore driver.
+* **Added new FIB dataplane algorithms.**
+
+ * Added the ``RTE_FIB_DIR8_16_8`` IPv4 algorithm, a three level variant of
+ DIR-24-8 with a small root table, with scalar and AVX512 lookup functions.
+
Removed Items
-------------
diff --git a/lib/fib/dir8_16_8.c b/lib/fib/dir8_16_8.c
new file mode 100644
index 0000000000..7207cd4748
--- /dev/null
+++ b/lib/fib/dir8_16_8.c
@@ -0,0 +1,614 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2026 Intel Corporation
+ */
+
+#include <stdint.h>
+#include <stdio.h>
+
+#include <rte_debug.h>
+#include <rte_malloc.h>
+#include <rte_errno.h>
+#include <rte_vect.h>
+#include <rte_cpuflags.h>
+
+#include <rte_rib.h>
+#include <rte_fib.h>
+#include "dir8_16_8.h"
+#include "fib_log.h"
+
+#ifdef CC_AVX512_SUPPORT
+#include "dir8_16_8_avx512.h"
+#endif
+
+#define DIR8_16_8_NAMESIZE 64
+
+/*
+ * The IPv4 address is split in three strides handled by three table levels:
+ * level 0: bits [31..24], 8 bits, fixed 256 entry root table (dp->tbl0)
+ * level 1: bits [23..8], 16 bits, dynamically allocated 65536 entry groups
+ * level 2: bits [7..0], 8 bits, dynamically allocated 256 entry groups
+ */
+
+struct dir8_16_8_level {
+ uint32_t num_ent; /**< Number of entries per group. */
+ uint8_t shift; /**< IP bit offset of this level. */
+ uint8_t mask_bits; /**< Number of IP bits at this level. */
+};
+
+static const struct dir8_16_8_level dir8_16_8_levels[] = {
+ { DIR8_16_8_TBL0_NUM_ENT, 24, 8 },
+ { DIR8_16_8_TBL16_GRP_NUM_ENT, 8, 16 },
+ { DIR8_16_8_TBL8_GRP_NUM_ENT, 0, 8 },
+};
+
+#define DIR8_16_8_NUM_LEVELS RTE_DIM(dir8_16_8_levels)
+
+static inline uint32_t
+dir8_16_8_level_idx(uint32_t ip, int level)
+{
+ const struct dir8_16_8_level *l = &dir8_16_8_levels[level];
+
+ return (ip >> l->shift) & ((1U << l->mask_bits) - 1);
+}
+
+struct dir8_16_8_rcu_dq_entry {
+ uint32_t tbl_idx;
+ uint32_t level;
+};
+
+static rte_fib_lookup_fn_t
+get_scalar_fn(bool be_addr)
+{
+ return be_addr ? dir8_16_8_lookup_bulk_be : dir8_16_8_lookup_bulk;
+}
+
+static rte_fib_lookup_fn_t
+get_vector_fn(bool be_addr)
+{
+#ifdef CC_AVX512_SUPPORT
+ if (rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512F) <= 0 ||
+ rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512DQ) <= 0 ||
+ rte_vect_get_max_simd_bitwidth() < RTE_VECT_SIMD_512)
+ return NULL;
+
+ if (be_addr && rte_cpu_get_flag_enabled(RTE_CPUFLAG_AVX512BW) <= 0)
+ return NULL;
+
+ return be_addr ? rte_dir8_16_8_vec_lookup_bulk_be :
+ rte_dir8_16_8_vec_lookup_bulk;
+#else
+ RTE_SET_USED(be_addr);
+ return NULL;
+#endif
+}
+
+rte_fib_lookup_fn_t
+dir8_16_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type, bool be_addr)
+{
+ struct dir8_16_8_tbl *dp = p;
+ rte_fib_lookup_fn_t fn;
+
+ if (dp == NULL)
+ return NULL;
+
+ switch (type) {
+ case RTE_FIB_LOOKUP_DIR8_16_8_SCALAR:
+ return get_scalar_fn(be_addr);
+ case RTE_FIB_LOOKUP_DIR8_16_8_VECTOR_AVX512:
+ return get_vector_fn(be_addr);
+ case RTE_FIB_LOOKUP_DEFAULT:
+ fn = get_vector_fn(be_addr);
+ return (fn != NULL) ? fn : get_scalar_fn(be_addr);
+ default:
+ return NULL;
+ }
+}
+
+static inline uint64_t *
+get_tbl_by_level(struct dir8_16_8_tbl *dp, int level)
+{
+ switch (level) {
+ case 1:
+ return dp->tbl16;
+ case 2:
+ return dp->tbl8;
+ default:
+ return dp->tbl0;
+ }
+}
+
+static inline int32_t
+tbl_pool_get(struct dir8_16_8_tbl *dp, int level)
+{
+ uint32_t *pool = (level == 1) ? dp->tbl16_pool : dp->tbl8_pool;
+ uint32_t *pos = (level == 1) ? &dp->tbl16_pool_pos : &dp->tbl8_pool_pos;
+ uint32_t num = (level == 1) ? dp->number_tbl16s : dp->number_tbl8s;
+
+ if (*pos == num)
+ return -ENOSPC;
+
+ return pool[(*pos)++];
+}
+
+static inline void
+tbl_pool_put(struct dir8_16_8_tbl *dp, int level, uint32_t idx)
+{
+ uint32_t *pool = (level == 1) ? dp->tbl16_pool : dp->tbl8_pool;
+ uint32_t *pos = (level == 1) ? &dp->tbl16_pool_pos : &dp->tbl8_pool_pos;
+
+ pool[--(*pos)] = idx;
+}
+
+static inline uint64_t *
+group_ptr(struct dir8_16_8_tbl *dp, int level, uint32_t grp_idx)
+{
+ uint64_t *tbl = get_tbl_by_level(dp, level);
+
+ return &tbl[(uint64_t)grp_idx * dir8_16_8_levels[level].num_ent];
+}
+
+static int
+tbl_group_alloc(struct dir8_16_8_tbl *dp, int level, uint64_t nh)
+{
+ uint32_t i, ent_num = dir8_16_8_levels[level].num_ent;
+ uint64_t *grp;
+ int idx;
+
+ idx = tbl_pool_get(dp, level);
+
+ /* If there are no free groups try to reclaim one. */
+ if (unlikely(idx == -ENOSPC && dp->dq)) {
+ /*
+ * Deferred queue contains tbl8 mixed with tbl16 groups.
+ * Reclaim until required group is reclaimed
+ */
+ unsigned int freed = 0;
+ int ret;
+ do {
+ ret = rte_rcu_qsbr_dq_reclaim(dp->dq, 1, &freed, NULL, NULL);
+ idx = tbl_pool_get(dp, level);
+ } while (idx < 0 && ret == 0 && freed != 0);
+ }
+
+ if (idx < 0)
+ return idx;
+
+ grp = group_ptr(dp, level, idx);
+ for (i = 0; i < ent_num; i++)
+ grp[i] = nh & ~(uint64_t)DIR8_16_8_EXT_ENT;
+
+ if (level == 1)
+ dp->cur_tbl16s++;
+ else
+ dp->cur_tbl8s++;
+
+ return idx;
+}
+
+static void
+tbl_group_cleanup_and_free(struct dir8_16_8_tbl *dp, int level, uint32_t idx)
+{
+ uint64_t *grp = group_ptr(dp, level, idx);
+
+ memset(grp, 0, dir8_16_8_levels[level].num_ent * sizeof(uint64_t));
+ tbl_pool_put(dp, level, idx);
+ if (level == 1)
+ dp->cur_tbl16s--;
+ else
+ dp->cur_tbl8s--;
+}
+
+static void
+__rcu_qsbr_free_resource(void *p, void *data, unsigned int n __rte_unused)
+{
+ struct dir8_16_8_tbl *dp = p;
+ struct dir8_16_8_rcu_dq_entry *e = data;
+
+ tbl_group_cleanup_and_free(dp, e->level, e->tbl_idx);
+}
+
+/*
+ * If every entry of a group holds the same final nexthop, collapse the group:
+ * write that nexthop into the parent entry and free the group.
+ */
+static void
+tbl_group_recycle(struct dir8_16_8_tbl *dp, int level, uint64_t *par_ent,
+ uint32_t grp_idx)
+{
+ struct dir8_16_8_rcu_dq_entry dq_entry;
+ uint64_t *grp = group_ptr(dp, level, grp_idx);
+ uint64_t nh = grp[0];
+ uint32_t i;
+
+ if (dir8_16_8_is_entry_extended(nh))
+ return;
+ for (i = 1; i < dir8_16_8_levels[level].num_ent; i++) {
+ if (nh != grp[i])
+ return;
+ }
+
+ *par_ent = nh & ~DIR8_16_8_EXT_ENT;
+
+ if (dp->v == NULL) {
+ tbl_group_cleanup_and_free(dp, level, grp_idx);
+ } else if (dp->rcu_mode == RTE_FIB_QSBR_MODE_SYNC) {
+ rte_rcu_qsbr_synchronize(dp->v, RTE_QSBR_THRID_INVALID);
+ tbl_group_cleanup_and_free(dp, level, grp_idx);
+ } else { /* RTE_FIB_QSBR_MODE_DQ */
+ dq_entry.tbl_idx = grp_idx;
+ dq_entry.level = level;
+ if (rte_rcu_qsbr_dq_enqueue(dp->dq, &dq_entry))
+ FIB_LOG(ERR, "Failed to push QSBR FIFO");
+ }
+}
+
+/*
+ * Make sure the entry "ent" at "level" points to a child group, allocating a
+ * new group (initialized with the entry's current nexthop) if necessary.
+ * On success returns the child group index, otherwise a negative errno.
+ */
+static int
+tbl_get_child(struct dir8_16_8_tbl *dp, int level, uint64_t *ent)
+{
+ int idx;
+
+ if (dir8_16_8_is_entry_extended(*ent))
+ return *ent >> 1;
+
+ idx = tbl_group_alloc(dp, level + 1, *ent);
+ if (idx < 0)
+ return idx;
+ *ent = ((uint64_t)idx << 1) | DIR8_16_8_EXT_ENT;
+
+ return idx;
+}
+
+static int
+install_to_fib(struct dir8_16_8_tbl *dp, int level, uint64_t base,
+ uint64_t ledge, uint64_t redge, uint64_t next_hop)
+{
+ const struct dir8_16_8_level *l = &dir8_16_8_levels[level];
+ uint64_t *tbl = get_tbl_by_level(dp, level);
+ uint64_t step = 1ULL << l->shift;
+ uint64_t lalign, ralign;
+ uint32_t lidx, ridx, idx;
+ int child, ret;
+
+ if (level == (int)DIR8_16_8_NUM_LEVELS - 1) {
+ /* Leaf level: every entry is a single address, plain fill. */
+ lidx = dir8_16_8_level_idx((uint32_t)ledge, level);
+ ridx = lidx + (uint32_t)(redge - ledge);
+ for (idx = lidx; idx < ridx; idx++)
+ tbl[base + idx] = (next_hop << 1);
+
+ return 0;
+ }
+
+ lalign = RTE_ALIGN_CEIL(ledge, step);
+ ralign = RTE_ALIGN_FLOOR(redge, step);
+
+ /* Left partial sub-range that does not start on a child boundary. */
+ if (ledge < lalign) {
+ uint64_t sub_right_edge = RTE_MIN(lalign, redge);
+
+ lidx = dir8_16_8_level_idx((uint32_t)ledge, level);
+ child = tbl_get_child(dp, level, &tbl[base + lidx]);
+ if (child < 0)
+ return child;
+
+ ret = install_to_fib(dp, level + 1,
+ (uint64_t)child * dir8_16_8_levels[level + 1].num_ent,
+ ledge, sub_right_edge, next_hop);
+ if (ret != 0)
+ return ret;
+
+ tbl_group_recycle(dp, level + 1, &tbl[base + lidx], child);
+ ledge = sub_right_edge;
+ }
+
+ /* Whole child sub-ranges filled directly at this level. */
+ if (ledge < ralign) {
+ lidx = dir8_16_8_level_idx((uint32_t)ledge, level);
+ ridx = lidx + (uint32_t)((ralign - ledge) >> l->shift);
+ for (idx = lidx; idx < ridx; idx++)
+ tbl[base + idx] = (next_hop << 1);
+
+ ledge = ralign;
+ }
+
+ /* Right partial sub-range that does not end on a child boundary. */
+ if (ledge < redge) {
+ lidx = dir8_16_8_level_idx((uint32_t)ledge, level);
+ child = tbl_get_child(dp, level, &tbl[base + lidx]);
+ if (child < 0)
+ return child;
+
+ ret = install_to_fib(dp, level + 1,
+ (uint64_t)child * dir8_16_8_levels[level + 1].num_ent,
+ ledge, redge, next_hop);
+ if (ret != 0)
+ return ret;
+
+ tbl_group_recycle(dp, level + 1, &tbl[base + lidx], child);
+ }
+
+ return 0;
+}
+
+static int
+modify_fib(struct dir8_16_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
+ uint8_t depth, uint64_t next_hop)
+{
+ struct rte_rib_node *tmp = NULL;
+ uint64_t ledge, redge;
+ uint32_t tmp_ip;
+ int ret;
+ uint8_t tmp_depth;
+
+ ledge = ip;
+ do {
+ tmp = rte_rib_get_nxt(rib, ip, depth, tmp,
+ RTE_RIB_GET_NXT_COVER);
+ if (tmp != NULL) {
+ rte_rib_get_depth(tmp, &tmp_depth);
+ if (tmp_depth == depth)
+ continue;
+
+ rte_rib_get_ip(tmp, &tmp_ip);
+ redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth);
+ if (ledge == redge) {
+ ledge = redge + (1ULL << (32 - tmp_depth));
+ continue;
+ }
+
+ ret = install_to_fib(dp, 0, 0, ledge, redge, next_hop);
+ if (ret != 0)
+ return ret;
+
+ ledge = redge + (1ULL << (32 - tmp_depth));
+ /*
+ * we got to the end of address space
+ * and wrapped around
+ */
+ if (ledge >= (1ULL << 32))
+ break;
+ } else {
+ redge = (uint64_t)ip + (1ULL << (32 - depth));
+ if (ledge == redge && ledge != 0)
+ break;
+
+ ret = install_to_fib(dp, 0, 0, ledge, redge, next_hop);
+ if (ret != 0)
+ return ret;
+ }
+ } while (tmp);
+
+ return 0;
+}
+
+int
+dir8_16_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
+ uint64_t next_hop, int op)
+{
+ struct dir8_16_8_tbl *dp;
+ struct rte_rib *rib;
+ struct rte_rib_node *node;
+ struct rte_rib_node *parent;
+ int ret = 0;
+ uint64_t par_nh, node_nh;
+
+ if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH))
+ return -EINVAL;
+
+ dp = rte_fib_get_dp(fib);
+ rib = rte_fib_get_rib(fib);
+ RTE_ASSERT((dp != NULL) && (rib != NULL));
+
+ if (next_hop > dir8_16_8_get_max_nh())
+ return -EINVAL;
+
+ ip &= rte_rib_depth_to_mask(depth);
+
+ node = rte_rib_lookup_exact(rib, ip, depth);
+ switch (op) {
+ case RTE_FIB_ADD:
+ if (node != NULL) {
+ rte_rib_get_nh(node, &node_nh);
+ if (node_nh == next_hop)
+ return 0;
+
+ ret = modify_fib(dp, rib, ip, depth, next_hop);
+ if (ret == 0)
+ rte_rib_set_nh(node, next_hop);
+
+ return ret;
+ }
+ node = rte_rib_insert(rib, ip, depth);
+ if (node == NULL)
+ return -rte_errno;
+
+ rte_rib_set_nh(node, next_hop);
+ parent = rte_rib_lookup_parent(node);
+ if (parent != NULL) {
+ rte_rib_get_nh(parent, &par_nh);
+ if (par_nh == next_hop)
+ return 0;
+ }
+ ret = modify_fib(dp, rib, ip, depth, next_hop);
+ if (ret != 0) {
+ rte_rib_remove(rib, ip, depth);
+ return ret;
+ }
+
+ return 0;
+ case RTE_FIB_DEL:
+ if (node == NULL)
+ return -ENOENT;
+
+ parent = rte_rib_lookup_parent(node);
+ if (parent != NULL) {
+ rte_rib_get_nh(parent, &par_nh);
+ rte_rib_get_nh(node, &node_nh);
+ if (par_nh != node_nh)
+ ret = modify_fib(dp, rib, ip, depth, par_nh);
+ } else
+ ret = modify_fib(dp, rib, ip, depth, dp->def_nh);
+ if (ret == 0)
+ rte_rib_remove(rib, ip, depth);
+ return ret;
+ default:
+ break;
+ }
+
+ return -EINVAL;
+}
+
+void *
+dir8_16_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf)
+{
+ char mem_name[DIR8_16_8_NAMESIZE];
+ struct dir8_16_8_tbl *dp;
+ uint64_t def_nh;
+ uint32_t num_tbl16, num_tbl8;
+ uint32_t i;
+ uint64_t tbl16_sz, tbl8_sz;
+
+ if ((name == NULL) || (fib_conf == NULL) || (fib_conf->dir8_16_8.num_tbl16 == 0) ||
+ (fib_conf->dir8_16_8.num_tbl8 == 0) ||
+ (fib_conf->default_nh > dir8_16_8_get_max_nh())) {
+ rte_errno = EINVAL;
+ return NULL;
+ }
+
+ def_nh = fib_conf->default_nh;
+ num_tbl16 = fib_conf->dir8_16_8.num_tbl16;
+ num_tbl8 = fib_conf->dir8_16_8.num_tbl8;
+
+ dp = rte_zmalloc_socket(name, sizeof(struct dir8_16_8_tbl) +
+ DIR8_16_8_TBL0_NUM_ENT * sizeof(uint64_t), RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp == NULL) {
+ rte_errno = ENOMEM;
+ return NULL;
+ }
+
+ /* Init first level table with the default nexthop. */
+ for (i = 0; i < DIR8_16_8_TBL0_NUM_ENT; i++)
+ dp->tbl0[i] = def_nh << 1;
+
+ snprintf(mem_name, sizeof(mem_name), "TBL16_%p", dp);
+ tbl16_sz = (uint64_t)DIR8_16_8_TBL16_GRP_NUM_ENT * sizeof(uint64_t) * num_tbl16;
+ dp->tbl16 = rte_zmalloc_socket(mem_name, tbl16_sz, RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl16 == NULL) {
+ rte_errno = ENOMEM;
+ goto free_dp;
+ }
+
+ snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
+ tbl8_sz = (uint64_t)DIR8_16_8_TBL8_GRP_NUM_ENT * sizeof(uint64_t) * num_tbl8;
+ dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz, RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl8 == NULL) {
+ rte_errno = ENOMEM;
+ goto free_tbl16;
+ }
+
+ snprintf(mem_name, sizeof(mem_name), "TBL16_pool_%p", dp);
+ dp->tbl16_pool = rte_zmalloc_socket(mem_name, sizeof(uint32_t) * num_tbl16,
+ RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl16_pool == NULL) {
+ rte_errno = ENOMEM;
+ goto free_tbl8;
+ }
+ for (i = 0; i < num_tbl16; i++)
+ dp->tbl16_pool[i] = i;
+
+ snprintf(mem_name, sizeof(mem_name), "TBL8_pool_%p", dp);
+ dp->tbl8_pool = rte_zmalloc_socket(mem_name, sizeof(uint32_t) * num_tbl8,
+ RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl8_pool == NULL) {
+ rte_errno = ENOMEM;
+ goto free_tbl16_pool;
+ }
+
+ for (i = 0; i < num_tbl8; i++)
+ dp->tbl8_pool[i] = i;
+
+ dp->def_nh = def_nh;
+ dp->number_tbl16s = num_tbl16;
+ dp->number_tbl8s = num_tbl8;
+
+ return dp;
+
+free_tbl16_pool:
+ rte_free(dp->tbl16_pool);
+free_tbl8:
+ rte_free(dp->tbl8);
+free_tbl16:
+ rte_free(dp->tbl16);
+free_dp:
+ rte_free(dp);
+ return NULL;
+}
+
+void
+dir8_16_8_free(void *p)
+{
+ struct dir8_16_8_tbl *dp = (struct dir8_16_8_tbl *)p;
+
+ if (dp == NULL)
+ return;
+
+ rte_rcu_qsbr_dq_delete(dp->dq);
+ rte_free(dp->tbl8_pool);
+ rte_free(dp->tbl16_pool);
+ rte_free(dp->tbl8);
+ rte_free(dp->tbl16);
+ rte_free(dp);
+}
+
+int
+dir8_16_8_rcu_qsbr_add(struct dir8_16_8_tbl *dp, struct rte_fib_rcu_config *cfg,
+ const char *name)
+{
+ struct rte_rcu_qsbr_dq_parameters params = {0};
+ char rcu_dq_name[RTE_RCU_QSBR_DQ_NAMESIZE];
+
+ if (dp == NULL || cfg == NULL)
+ return -EINVAL;
+
+ if (dp->v != NULL)
+ return -EEXIST;
+
+ if (cfg->mode == RTE_FIB_QSBR_MODE_SYNC) {
+ /* No other things to do. */
+ } else if (cfg->mode == RTE_FIB_QSBR_MODE_DQ) {
+ /* Init QSBR defer queue. */
+ snprintf(rcu_dq_name, sizeof(rcu_dq_name),
+ "FIB_RCU_%s", name);
+ params.name = rcu_dq_name;
+ params.size = cfg->dq_size;
+ if (params.size == 0)
+ params.size = RTE_FIB_RCU_DQ_RECLAIM_SZ;
+
+ params.trigger_reclaim_limit = cfg->reclaim_thd;
+ params.max_reclaim_size = cfg->reclaim_max;
+ if (params.max_reclaim_size == 0)
+ params.max_reclaim_size = RTE_FIB_RCU_DQ_RECLAIM_MAX;
+
+ params.esize = sizeof(struct dir8_16_8_rcu_dq_entry);
+ params.free_fn = __rcu_qsbr_free_resource;
+ params.p = dp;
+ params.v = cfg->v;
+ dp->dq = rte_rcu_qsbr_dq_create(¶ms);
+ if (dp->dq == NULL) {
+ FIB_LOG(ERR, "LPM defer queue creation failed");
+ return -rte_errno;
+ }
+ } else {
+ return -EINVAL;
+ }
+
+ dp->rcu_mode = cfg->mode;
+ dp->v = cfg->v;
+
+ return 0;
+}
diff --git a/lib/fib/dir8_16_8.h b/lib/fib/dir8_16_8.h
new file mode 100644
index 0000000000..31ca5162de
--- /dev/null
+++ b/lib/fib/dir8_16_8.h
@@ -0,0 +1,143 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2026 Intel Corporation
+ */
+
+#ifndef _DIR8_16_8_H_
+#define _DIR8_16_8_H_
+
+#include <stdalign.h>
+#include <stdbool.h>
+
+#include <rte_byteorder.h>
+#include <rte_prefetch.h>
+#include <rte_branch_prediction.h>
+#include <rte_rcu_qsbr.h>
+
+/**
+ * @file
+ * DIR8_16_8 algorithm
+ *
+ * Three level variant of the DIR24_8 algorithm.
+ * The 32 bit IPv4 address is split in three strides of 8, 16 and 8 bits.
+ * Only a single nexthop size of 8 bytes is supported.
+ */
+
+/** Number of entries in the first level table (top 8 bits). */
+#define DIR8_16_8_TBL0_NUM_ENT 256U
+/** Number of entries in a second level group (middle 16 bits). */
+#define DIR8_16_8_TBL16_GRP_NUM_ENT (1U << 16)
+/** Number of entries in a third level group (last 8 bits). */
+#define DIR8_16_8_TBL8_GRP_NUM_ENT 256U
+/** Flag set in an entry pointing to the next level table. */
+#define DIR8_16_8_EXT_ENT 1
+
+struct dir8_16_8_tbl {
+ uint32_t number_tbl16s; /**< Total number of tbl16 groups. */
+ uint32_t cur_tbl16s; /**< Current number of tbl16 groups. */
+ uint32_t number_tbl8s; /**< Total number of tbl8 groups. */
+ uint32_t cur_tbl8s; /**< Current number of tbl8 groups. */
+ uint64_t def_nh; /**< Default next hop. */
+ uint64_t *tbl16; /**< Second level table. */
+ uint64_t *tbl8; /**< Third level table. */
+ uint32_t *tbl16_pool; /**< Stack of free tbl16 group idxes. */
+ uint32_t *tbl8_pool; /**< Stack of free tbl8 group idxes. */
+ uint32_t tbl16_pool_pos; /**< Allocation pos in tbl16 pool. */
+ uint32_t tbl8_pool_pos; /**< Allocation pos in tbl8 pool. */
+ /* RCU config. */
+ enum rte_fib_qsbr_mode rcu_mode;/* Blocking, defer queue. */
+ struct rte_rcu_qsbr *v; /* RCU QSBR variable. */
+ struct rte_rcu_qsbr_dq *dq; /* RCU QSBR defer queue. */
+ /* First level table (top 8 bits). */
+ alignas(RTE_CACHE_LINE_SIZE) uint64_t tbl0[];
+};
+
+static inline uint32_t
+dir8_16_8_get_tbl0_idx(uint32_t ip)
+{
+ return ip >> 24;
+}
+
+static inline size_t
+dir8_16_8_get_tbl16_idx(uint64_t ent, uint32_t ip)
+{
+ return (ent >> 1) * DIR8_16_8_TBL16_GRP_NUM_ENT +
+ ((ip >> 8) & 0xffff);
+}
+
+static inline size_t
+dir8_16_8_get_tbl8_idx(uint64_t ent, uint32_t ip)
+{
+ return (ent >> 1) * DIR8_16_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
+}
+
+static inline uint64_t
+dir8_16_8_get_max_nh(void)
+{
+ return (UINT64_MAX >> 1);
+}
+
+static inline int
+dir8_16_8_is_entry_extended(uint64_t ent)
+{
+ return (ent & DIR8_16_8_EXT_ENT) == DIR8_16_8_EXT_ENT;
+}
+
+static inline void
+dir8_16_8_lookup_bulk(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ struct dir8_16_8_tbl *dp = (struct dir8_16_8_tbl *)p;
+ uint64_t tmp;
+ uint32_t i;
+
+ for (i = 0; i < n; i++) {
+ tmp = dp->tbl0[dir8_16_8_get_tbl0_idx(ips[i])];
+ /* Prefixes are usually longer than /8. */
+ if (dir8_16_8_is_entry_extended(tmp))
+ tmp = dp->tbl16[dir8_16_8_get_tbl16_idx(tmp, ips[i])];
+ if (unlikely(dir8_16_8_is_entry_extended(tmp)))
+ tmp = dp->tbl8[dir8_16_8_get_tbl8_idx(tmp, ips[i])];
+ next_hops[i] = tmp >> 1;
+ }
+}
+
+#define DIR8_16_8_BSWAP_MAX_LENGTH 64
+
+static inline void
+dir8_16_8_lookup_bulk_be(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+#if RTE_BYTE_ORDER == RTE_BIG_ENDIAN
+ dir8_16_8_lookup_bulk(p, ips, next_hops, n);
+#else
+ uint32_t le_ips[DIR8_16_8_BSWAP_MAX_LENGTH];
+ unsigned int i;
+
+ for (i = 0; i < n; i += DIR8_16_8_BSWAP_MAX_LENGTH) {
+ unsigned int j;
+ for (j = 0; j < DIR8_16_8_BSWAP_MAX_LENGTH && i + j < n; j++)
+ le_ips[j] = rte_be_to_cpu_32(ips[i + j]);
+
+ dir8_16_8_lookup_bulk(p, le_ips, next_hops + i, j);
+ }
+#endif
+}
+
+void *
+dir8_16_8_create(const char *name, int socket_id, struct rte_fib_conf *conf);
+
+void
+dir8_16_8_free(void *p);
+
+rte_fib_lookup_fn_t
+dir8_16_8_get_lookup_fn(void *p, enum rte_fib_lookup_type type, bool be_addr);
+
+int
+dir8_16_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
+ uint64_t next_hop, int op);
+
+int
+dir8_16_8_rcu_qsbr_add(struct dir8_16_8_tbl *dp, struct rte_fib_rcu_config *cfg,
+ const char *name);
+
+#endif /* _DIR8_16_8_H_ */
diff --git a/lib/fib/dir8_16_8_avx512.c b/lib/fib/dir8_16_8_avx512.c
new file mode 100644
index 0000000000..c147451252
--- /dev/null
+++ b/lib/fib/dir8_16_8_avx512.c
@@ -0,0 +1,142 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2026 Intel Corporation
+ */
+
+#include <rte_vect.h>
+#include <rte_fib.h>
+
+#include "dir8_16_8.h"
+#include "dir8_16_8_avx512.h"
+
+static inline __m256i
+dir8_16_8_vec_load_ips(const uint32_t *ips, bool be_addr)
+{
+ const __m256i bswap32 = _mm256_set_epi8(
+ 12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3,
+ 12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3
+ );
+ __m256i ip_vec = _mm256_loadu_si256((const void *)ips);
+
+ return be_addr ? _mm256_shuffle_epi8(ip_vec, bswap32) : ip_vec;
+}
+
+static inline __m256i
+dir8_16_8_vec_get_tbl0_idx(__m256i ip_vec)
+{
+ return _mm256_srli_epi32(ip_vec, 24);
+}
+
+/* Second lookup stage input for 8 IPs, filled by the first stage. */
+struct dir8_16_8_vec_stage {
+ /* Address of the entry to read for every IP. */
+ const uint64_t *ent[8];
+ /*
+ * Copy of the tbl0 entries. A not extended entry is read from here,
+ * reading it again from tbl0 could see a concurrent update.
+ */
+ uint64_t tbl0_ent[8];
+};
+
+/*
+ * First lookup stage of 8 IPs: read their tbl0 entries and prefetch the
+ * tbl16 entries the extended ones point to. Scalar loads are used, as on
+ * some CPUs a gather costs much more than the 8 loads it replaces.
+ */
+static inline void
+dir8_16_8_vec_prefetch_x8(const struct dir8_16_8_tbl *dp, const uint32_t *ips, bool be_addr,
+ struct dir8_16_8_vec_stage *st)
+{
+ const __m256i ip_vec = dir8_16_8_vec_load_ips(ips, be_addr);
+ const rte_ymm_t idx0 = { .y = dir8_16_8_vec_get_tbl0_idx(ip_vec) };
+ const rte_ymm_t ip = { .y = ip_vec };
+ const uint64_t *tbl0 = dp->tbl0;
+ const uint64_t *tbl16 = dp->tbl16;
+ uint64_t ent;
+ uint32_t i;
+
+ for (i = 0; i < 8; i++) {
+ ent = tbl0[idx0.u32[i]];
+ st->tbl0_ent[i] = ent;
+ st->ent[i] = &st->tbl0_ent[i];
+ if (dir8_16_8_is_entry_extended(ent)) {
+ st->ent[i] = &tbl16[dir8_16_8_get_tbl16_idx(ent, ip.u32[i])];
+ rte_prefetch0(st->ent[i]);
+ }
+ }
+}
+
+/* Second lookup stage of 8 IPs: read the entries found by the first stage. */
+static inline void
+dir8_16_8_vec_lookup_x8(const struct dir8_16_8_tbl *dp, const struct dir8_16_8_vec_stage *st,
+ const uint32_t *ips, bool be_addr, uint64_t *next_hops)
+{
+ const uint64_t * const *ent = st->ent;
+ const __m512i lsb = _mm512_set1_epi64(1);
+ __m512i ip64, res, idxes;
+ __mmask8 msk_ext;
+
+ res = _mm512_set_epi64(*ent[7], *ent[6], *ent[5], *ent[4],
+ *ent[3], *ent[2], *ent[1], *ent[0]);
+ ip64 = _mm512_cvtepu32_epi64(dir8_16_8_vec_load_ips(ips, be_addr));
+
+ msk_ext = _mm512_test_epi64_mask(res, lsb);
+ if (msk_ext != 0) {
+ idxes = _mm512_slli_epi64(_mm512_srli_epi64(res, 1), 8);
+ idxes = _mm512_add_epi64(idxes, _mm512_and_epi64(ip64, _mm512_set1_epi64(0xff)));
+ res = _mm512_mask_i64gather_epi64(res, msk_ext, idxes, (const void *)dp->tbl8, 8);
+ }
+
+ _mm512_storeu_si512(next_hops, _mm512_srli_epi64(res, 1));
+}
+
+static inline void
+vec_lookup_bulk(void *p, const uint32_t *ips, uint64_t *next_hops, unsigned int n, bool be_addr)
+{
+ const struct dir8_16_8_tbl *dp = p;
+ struct dir8_16_8_vec_stage stage[3];
+ struct dir8_16_8_vec_stage *st0 = &stage[0];
+ struct dir8_16_8_vec_stage *st1 = &stage[1];
+ struct dir8_16_8_vec_stage *st2 = &stage[2];
+ struct dir8_16_8_vec_stage *tmp;
+ unsigned int i = 0;
+
+ if (n >= 16) {
+ dir8_16_8_vec_prefetch_x8(dp, ips, be_addr, st0);
+ dir8_16_8_vec_prefetch_x8(dp, &ips[8], be_addr, st1);
+ for (; i + 24 <= n; i += 8) {
+ dir8_16_8_vec_prefetch_x8(dp, &ips[i + 16], be_addr, st2);
+ dir8_16_8_vec_lookup_x8(dp, st0, &ips[i], be_addr, &next_hops[i]);
+ tmp = st0;
+ st0 = st1;
+ st1 = st2;
+ st2 = tmp;
+ }
+ dir8_16_8_vec_lookup_x8(dp, st0, &ips[i], be_addr, &next_hops[i]);
+ dir8_16_8_vec_lookup_x8(dp, st1, &ips[i + 8], be_addr, &next_hops[i + 8]);
+ i += 16;
+ } else if (n >= 8) {
+ dir8_16_8_vec_prefetch_x8(dp, ips, be_addr, st0);
+ dir8_16_8_vec_lookup_x8(dp, st0, ips, be_addr, next_hops);
+ i = 8;
+ }
+
+ /* Scalar lookup of the last n % 8 IPs. */
+ if (be_addr)
+ dir8_16_8_lookup_bulk_be(p, &ips[i], &next_hops[i], n - i);
+ else
+ dir8_16_8_lookup_bulk(p, &ips[i], &next_hops[i], n - i);
+}
+
+void
+rte_dir8_16_8_vec_lookup_bulk(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ vec_lookup_bulk(p, ips, next_hops, n, false);
+}
+
+void
+rte_dir8_16_8_vec_lookup_bulk_be(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ vec_lookup_bulk(p, ips, next_hops, n, true);
+}
diff --git a/lib/fib/dir8_16_8_avx512.h b/lib/fib/dir8_16_8_avx512.h
new file mode 100644
index 0000000000..d468481029
--- /dev/null
+++ b/lib/fib/dir8_16_8_avx512.h
@@ -0,0 +1,16 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2026 Intel Corporation
+ */
+
+#ifndef _DIR8_16_8_AVX512_H_
+#define _DIR8_16_8_AVX512_H_
+
+void
+rte_dir8_16_8_vec_lookup_bulk(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n);
+
+void
+rte_dir8_16_8_vec_lookup_bulk_be(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n);
+
+#endif /* _DIR8_16_8_AVX512_H_ */
diff --git a/lib/fib/meson.build b/lib/fib/meson.build
index 573fc50ff1..f24f679039 100644
--- a/lib/fib/meson.build
+++ b/lib/fib/meson.build
@@ -2,14 +2,14 @@
# Copyright(c) 2018 Vladimir Medvedkin <medvedkinv at gmail.com>
# Copyright(c) 2019 Intel Corporation
-sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'trie.c')
+sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'dir8_16_8.c', 'trie.c')
headers = files('rte_fib.h', 'rte_fib6.h')
deps += ['rib']
deps += ['rcu']
deps += ['net']
if dpdk_conf.has('RTE_ARCH_X86_64')
- sources_avx512 += files('dir24_8_avx512.c', 'trie_avx512.c')
+ sources_avx512 += files('dir24_8_avx512.c', 'dir8_16_8_avx512.c', 'trie_avx512.c')
elif dpdk_conf.has('RTE_ARCH_RISCV')
sources += files('dir24_8_rvv.c')
endif
diff --git a/lib/fib/rte_fib.c b/lib/fib/rte_fib.c
index 184210f380..fcc28899cb 100644
--- a/lib/fib/rte_fib.c
+++ b/lib/fib/rte_fib.c
@@ -18,6 +18,7 @@
#include <rte_fib.h>
#include "dir24_8.h"
+#include "dir8_16_8.h"
#include "fib_log.h"
RTE_LOG_REGISTER_DEFAULT(fib_logtype, INFO);
@@ -112,6 +113,14 @@ init_dataplane(struct rte_fib *fib, __rte_unused int socket_id,
RTE_FIB_LOOKUP_DEFAULT, !!(fib->flags & RTE_FIB_F_LOOKUP_NETWORK_ORDER));
fib->modify = dir24_8_modify;
return 0;
+ case RTE_FIB_DIR8_16_8:
+ fib->dp = dir8_16_8_create(dp_name, socket_id, conf);
+ if (fib->dp == NULL)
+ return -rte_errno;
+ fib->lookup = dir8_16_8_get_lookup_fn(fib->dp,
+ RTE_FIB_LOOKUP_DEFAULT, !!(fib->flags & RTE_FIB_F_LOOKUP_NETWORK_ORDER));
+ fib->modify = dir8_16_8_modify;
+ return 0;
default:
return -EINVAL;
}
@@ -165,7 +174,7 @@ rte_fib_create(const char *name, int socket_id, struct rte_fib_conf *conf)
/* Check user arguments. */
if ((name == NULL) || (conf == NULL) || (conf->max_routes < 0) ||
(conf->flags & ~RTE_FIB_ALLOWED_FLAGS) ||
- (conf->type > RTE_FIB_DIR24_8)) {
+ (conf->type > RTE_FIB_DIR8_16_8)) {
rte_errno = EINVAL;
return NULL;
}
@@ -281,6 +290,10 @@ free_dataplane(struct rte_fib *fib)
return;
case RTE_FIB_DIR24_8:
dir24_8_free(fib->dp);
+ return;
+ case RTE_FIB_DIR8_16_8:
+ dir8_16_8_free(fib->dp);
+ return;
default:
return;
}
@@ -345,6 +358,13 @@ rte_fib_select_lookup(struct rte_fib *fib,
return -EINVAL;
fib->lookup = fn;
return 0;
+ case RTE_FIB_DIR8_16_8:
+ fn = dir8_16_8_get_lookup_fn(fib->dp, type,
+ !!(fib->flags & RTE_FIB_F_LOOKUP_NETWORK_ORDER));
+ if (fn == NULL)
+ return -EINVAL;
+ fib->lookup = fn;
+ return 0;
default:
return -EINVAL;
}
@@ -360,6 +380,8 @@ rte_fib_rcu_qsbr_add(struct rte_fib *fib, struct rte_fib_rcu_config *cfg)
switch (fib->type) {
case RTE_FIB_DIR24_8:
return dir24_8_rcu_qsbr_add(fib->dp, cfg, fib->name);
+ case RTE_FIB_DIR8_16_8:
+ return dir8_16_8_rcu_qsbr_add(fib->dp, cfg, fib->name);
default:
return -ENOTSUP;
}
diff --git a/lib/fib/rte_fib.h b/lib/fib/rte_fib.h
index b16a653535..68ee6f0652 100644
--- a/lib/fib/rte_fib.h
+++ b/lib/fib/rte_fib.h
@@ -49,7 +49,8 @@ enum rte_fib_qsbr_mode {
/** Type of FIB struct */
enum rte_fib_type {
RTE_FIB_DUMMY, /**< RIB tree based FIB */
- RTE_FIB_DIR24_8 /**< DIR24_8 based FIB */
+ RTE_FIB_DIR24_8, /**< DIR24_8 based FIB */
+ RTE_FIB_DIR8_16_8 /**< DIR8_16_8 based FIB */
};
/** Modify FIB function */
@@ -87,8 +88,14 @@ enum rte_fib_lookup_type {
/**<
* Unified lookup function for all next hop sizes
*/
- RTE_FIB_LOOKUP_DIR24_8_VECTOR_AVX512
+ RTE_FIB_LOOKUP_DIR24_8_VECTOR_AVX512,
/**< Vector implementation using AVX512 */
+ RTE_FIB_LOOKUP_DIR8_16_8_SCALAR,
+ /**<
+ * Scalar implementation for the DIR8_16_8 algorithm
+ */
+ RTE_FIB_LOOKUP_DIR8_16_8_VECTOR_AVX512
+ /**< Vector (AVX512) lookup for the DIR8_16_8 algorithm */
};
/** If set, fib lookup is expecting IPv4 address in network byte order */
@@ -108,6 +115,12 @@ struct rte_fib_conf {
enum rte_fib_dir24_8_nh_sz nh_sz;
uint32_t num_tbl8;
} dir24_8;
+ struct {
+ /** Number of second level (16 bit stride) groups. */
+ uint32_t num_tbl16;
+ /** Number of third level (8 bit stride) groups. */
+ uint32_t num_tbl8;
+ } dir8_16_8;
};
unsigned int flags; /**< Optional feature flags from RTE_FIB_F_* */
};
--
2.43.0
More information about the dev
mailing list