summaryrefslogtreecommitdiffstats
path: root/src/spdk/dpdk/lib/librte_fib
diff options
context:
space:
mode:
Diffstat (limited to 'src/spdk/dpdk/lib/librte_fib')
-rw-r--r--src/spdk/dpdk/lib/librte_fib/Makefile22
-rw-r--r--src/spdk/dpdk/lib/librte_fib/dir24_8.c737
-rw-r--r--src/spdk/dpdk/lib/librte_fib/dir24_8.h35
-rw-r--r--src/spdk/dpdk/lib/librte_fib/meson.build9
-rw-r--r--src/spdk/dpdk/lib/librte_fib/rte_fib.c319
-rw-r--r--src/spdk/dpdk/lib/librte_fib/rte_fib.h196
-rw-r--r--src/spdk/dpdk/lib/librte_fib/rte_fib6.c321
-rw-r--r--src/spdk/dpdk/lib/librte_fib/rte_fib6.h201
-rw-r--r--src/spdk/dpdk/lib/librte_fib/rte_fib_version.map23
-rw-r--r--src/spdk/dpdk/lib/librte_fib/trie.c759
-rw-r--r--src/spdk/dpdk/lib/librte_fib/trie.h36
11 files changed, 2658 insertions, 0 deletions
diff --git a/src/spdk/dpdk/lib/librte_fib/Makefile b/src/spdk/dpdk/lib/librte_fib/Makefile
new file mode 100644
index 000000000..1dd2a495b
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/Makefile
@@ -0,0 +1,22 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_fib.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+LDLIBS += -lrte_eal -lrte_rib
+
+EXPORT_MAP := rte_fib_version.map
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c trie.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/src/spdk/dpdk/lib/librte_fib/dir24_8.c b/src/spdk/dpdk/lib/librte_fib/dir24_8.c
new file mode 100644
index 000000000..c9dce3cbc
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/dir24_8.c
@@ -0,0 +1,737 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <inttypes.h>
+
+#include <rte_debug.h>
+#include <rte_malloc.h>
+#include <rte_prefetch.h>
+#include <rte_errno.h>
+#include <rte_memory.h>
+#include <rte_branch_prediction.h>
+
+#include <rte_fib.h>
+#include <rte_rib.h>
+#include "dir24_8.h"
+
+#define DIR24_8_NAMESIZE 64
+
+#define DIR24_8_TBL24_NUM_ENT (1 << 24)
+#define DIR24_8_TBL8_GRP_NUM_ENT 256U
+#define DIR24_8_EXT_ENT 1
+#define DIR24_8_TBL24_MASK 0xffffff00
+
+#define BITMAP_SLAB_BIT_SIZE_LOG2 6
+#define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2)
+#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1)
+
+struct dir24_8_tbl {
+ uint32_t number_tbl8s; /**< Total number of tbl8s */
+ uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */
+ uint32_t cur_tbl8s; /**< Current number of tbl8s */
+ enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */
+ uint64_t def_nh; /**< Default next hop */
+ uint64_t *tbl8; /**< tbl8 table. */
+ uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/
+ /* tbl24 table. */
+ __extension__ uint64_t tbl24[0] __rte_cache_aligned;
+};
+
+#define ROUNDUP(x, y) RTE_ALIGN_CEIL(x, (1 << (32 - y)))
+
+enum lookup_type {
+ MACRO,
+ INLINE,
+ UNI
+};
+enum lookup_type test_lookup = MACRO;
+
+static inline void *
+get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
+{
+ return (void *)&((uint8_t *)dp->tbl24)[(ip &
+ DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
+}
+
+static inline uint8_t
+bits_in_nh(uint8_t nh_sz)
+{
+ return 8 * (1 << nh_sz);
+}
+
+static inline uint64_t
+get_max_nh(uint8_t nh_sz)
+{
+ return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
+}
+
+static inline uint32_t
+get_tbl24_idx(uint32_t ip)
+{
+ return ip >> 8;
+}
+
+static inline uint32_t
+get_tbl8_idx(uint32_t res, uint32_t ip)
+{
+ return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
+}
+
+static inline uint64_t
+lookup_msk(uint8_t nh_sz)
+{
+ return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
+}
+
+static inline uint8_t
+get_psd_idx(uint32_t val, uint8_t nh_sz)
+{
+ return val & ((1 << (3 - nh_sz)) - 1);
+}
+
+static inline uint32_t
+get_tbl_idx(uint32_t val, uint8_t nh_sz)
+{
+ return val >> (3 - nh_sz);
+}
+
+static inline uint64_t
+get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz)
+{
+ return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >>
+ (get_psd_idx(get_tbl24_idx(ip), nh_sz) *
+ bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
+}
+
+static inline uint64_t
+get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz)
+{
+ return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >>
+ (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) *
+ bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
+}
+
+static inline int
+is_entry_extended(uint64_t ent)
+{
+ return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT;
+}
+
+#define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \
+static void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \
+ uint64_t *next_hops, const unsigned int n) \
+{ \
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \
+ uint64_t tmp; \
+ uint32_t i; \
+ uint32_t prefetch_offset = \
+ RTE_MIN((unsigned int)bulk_prefetch, n); \
+ \
+ for (i = 0; i < prefetch_offset; i++) \
+ rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \
+ for (i = 0; i < (n - prefetch_offset); i++) { \
+ rte_prefetch0(get_tbl24_p(dp, \
+ ips[i + prefetch_offset], nh_sz)); \
+ tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \
+ if (unlikely(is_entry_extended(tmp))) \
+ tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \
+ ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
+ next_hops[i] = tmp >> 1; \
+ } \
+ for (; i < n; i++) { \
+ tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \
+ if (unlikely(is_entry_extended(tmp))) \
+ tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \
+ ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \
+ next_hops[i] = tmp >> 1; \
+ } \
+} \
+
+LOOKUP_FUNC(1b, uint8_t, 5, 0)
+LOOKUP_FUNC(2b, uint16_t, 6, 1)
+LOOKUP_FUNC(4b, uint32_t, 15, 2)
+LOOKUP_FUNC(8b, uint64_t, 12, 3)
+
+static inline void
+dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n, uint8_t nh_sz)
+{
+ uint64_t tmp;
+ uint32_t i;
+ uint32_t prefetch_offset = RTE_MIN(15U, n);
+
+ for (i = 0; i < prefetch_offset; i++)
+ rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
+ for (i = 0; i < (n - prefetch_offset); i++) {
+ rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
+ nh_sz));
+ tmp = get_tbl24(dp, ips[i], nh_sz);
+ if (unlikely(is_entry_extended(tmp)))
+ tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
+
+ next_hops[i] = tmp >> 1;
+ }
+ for (; i < n; i++) {
+ tmp = get_tbl24(dp, ips[i], nh_sz);
+ if (unlikely(is_entry_extended(tmp)))
+ tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
+
+ next_hops[i] = tmp >> 1;
+ }
+}
+
+static void
+dir24_8_lookup_bulk_0(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
+
+ dir24_8_lookup_bulk(dp, ips, next_hops, n, 0);
+}
+
+static void
+dir24_8_lookup_bulk_1(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
+
+ dir24_8_lookup_bulk(dp, ips, next_hops, n, 1);
+}
+
+static void
+dir24_8_lookup_bulk_2(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
+
+ dir24_8_lookup_bulk(dp, ips, next_hops, n, 2);
+}
+
+static void
+dir24_8_lookup_bulk_3(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
+
+ dir24_8_lookup_bulk(dp, ips, next_hops, n, 3);
+}
+
+static void
+dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n)
+{
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
+ uint64_t tmp;
+ uint32_t i;
+ uint32_t prefetch_offset = RTE_MIN(15U, n);
+ uint8_t nh_sz = dp->nh_sz;
+
+ for (i = 0; i < prefetch_offset; i++)
+ rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz));
+ for (i = 0; i < (n - prefetch_offset); i++) {
+ rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset],
+ nh_sz));
+ tmp = get_tbl24(dp, ips[i], nh_sz);
+ if (unlikely(is_entry_extended(tmp)))
+ tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
+
+ next_hops[i] = tmp >> 1;
+ }
+ for (; i < n; i++) {
+ tmp = get_tbl24(dp, ips[i], nh_sz);
+ if (unlikely(is_entry_extended(tmp)))
+ tmp = get_tbl8(dp, tmp, ips[i], nh_sz);
+
+ next_hops[i] = tmp >> 1;
+ }
+}
+
+rte_fib_lookup_fn_t
+dir24_8_get_lookup_fn(struct rte_fib_conf *fib_conf)
+{
+ enum rte_fib_dir24_8_nh_sz nh_sz = fib_conf->dir24_8.nh_sz;
+
+ if (test_lookup == MACRO) {
+ switch (nh_sz) {
+ case RTE_FIB_DIR24_8_1B:
+ return dir24_8_lookup_bulk_1b;
+ case RTE_FIB_DIR24_8_2B:
+ return dir24_8_lookup_bulk_2b;
+ case RTE_FIB_DIR24_8_4B:
+ return dir24_8_lookup_bulk_4b;
+ case RTE_FIB_DIR24_8_8B:
+ return dir24_8_lookup_bulk_8b;
+ }
+ } else if (test_lookup == INLINE) {
+ switch (nh_sz) {
+ case RTE_FIB_DIR24_8_1B:
+ return dir24_8_lookup_bulk_0;
+ case RTE_FIB_DIR24_8_2B:
+ return dir24_8_lookup_bulk_1;
+ case RTE_FIB_DIR24_8_4B:
+ return dir24_8_lookup_bulk_2;
+ case RTE_FIB_DIR24_8_8B:
+ return dir24_8_lookup_bulk_3;
+ }
+ } else
+ return dir24_8_lookup_bulk_uni;
+ return NULL;
+}
+
+static void
+write_to_fib(void *ptr, uint64_t val, enum rte_fib_dir24_8_nh_sz size, int n)
+{
+ int i;
+ uint8_t *ptr8 = (uint8_t *)ptr;
+ uint16_t *ptr16 = (uint16_t *)ptr;
+ uint32_t *ptr32 = (uint32_t *)ptr;
+ uint64_t *ptr64 = (uint64_t *)ptr;
+
+ switch (size) {
+ case RTE_FIB_DIR24_8_1B:
+ for (i = 0; i < n; i++)
+ ptr8[i] = (uint8_t)val;
+ break;
+ case RTE_FIB_DIR24_8_2B:
+ for (i = 0; i < n; i++)
+ ptr16[i] = (uint16_t)val;
+ break;
+ case RTE_FIB_DIR24_8_4B:
+ for (i = 0; i < n; i++)
+ ptr32[i] = (uint32_t)val;
+ break;
+ case RTE_FIB_DIR24_8_8B:
+ for (i = 0; i < n; i++)
+ ptr64[i] = (uint64_t)val;
+ break;
+ }
+}
+
+static int
+tbl8_get_idx(struct dir24_8_tbl *dp)
+{
+ uint32_t i;
+ int bit_idx;
+
+ for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) &&
+ (dp->tbl8_idxes[i] == UINT64_MAX); i++)
+ ;
+ if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) {
+ bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]);
+ dp->tbl8_idxes[i] |= (1ULL << bit_idx);
+ return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx;
+ }
+ return -ENOSPC;
+}
+
+static inline void
+tbl8_free_idx(struct dir24_8_tbl *dp, int idx)
+{
+ dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &=
+ ~(1ULL << (idx & BITMAP_SLAB_BITMASK));
+}
+
+static int
+tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh)
+{
+ int64_t tbl8_idx;
+ uint8_t *tbl8_ptr;
+
+ tbl8_idx = tbl8_get_idx(dp);
+ if (tbl8_idx < 0)
+ return tbl8_idx;
+ tbl8_ptr = (uint8_t *)dp->tbl8 +
+ ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
+ dp->nh_sz);
+ /*Init tbl8 entries with nexthop from tbl24*/
+ write_to_fib((void *)tbl8_ptr, nh|
+ DIR24_8_EXT_ENT, dp->nh_sz,
+ DIR24_8_TBL8_GRP_NUM_ENT);
+ dp->cur_tbl8s++;
+ return tbl8_idx;
+}
+
+static void
+tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx)
+{
+ uint32_t i;
+ uint64_t nh;
+ uint8_t *ptr8;
+ uint16_t *ptr16;
+ uint32_t *ptr32;
+ uint64_t *ptr64;
+
+ switch (dp->nh_sz) {
+ case RTE_FIB_DIR24_8_1B:
+ ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx *
+ DIR24_8_TBL8_GRP_NUM_ENT];
+ nh = *ptr8;
+ for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr8[i])
+ return;
+ }
+ ((uint8_t *)dp->tbl24)[ip >> 8] =
+ nh & ~DIR24_8_EXT_ENT;
+ for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
+ ptr8[i] = 0;
+ break;
+ case RTE_FIB_DIR24_8_2B:
+ ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
+ DIR24_8_TBL8_GRP_NUM_ENT];
+ nh = *ptr16;
+ for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr16[i])
+ return;
+ }
+ ((uint16_t *)dp->tbl24)[ip >> 8] =
+ nh & ~DIR24_8_EXT_ENT;
+ for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
+ ptr16[i] = 0;
+ break;
+ case RTE_FIB_DIR24_8_4B:
+ ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
+ DIR24_8_TBL8_GRP_NUM_ENT];
+ nh = *ptr32;
+ for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr32[i])
+ return;
+ }
+ ((uint32_t *)dp->tbl24)[ip >> 8] =
+ nh & ~DIR24_8_EXT_ENT;
+ for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
+ ptr32[i] = 0;
+ break;
+ case RTE_FIB_DIR24_8_8B:
+ ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
+ DIR24_8_TBL8_GRP_NUM_ENT];
+ nh = *ptr64;
+ for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr64[i])
+ return;
+ }
+ ((uint64_t *)dp->tbl24)[ip >> 8] =
+ nh & ~DIR24_8_EXT_ENT;
+ for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++)
+ ptr64[i] = 0;
+ break;
+ }
+ tbl8_free_idx(dp, tbl8_idx);
+ dp->cur_tbl8s--;
+}
+
+static int
+install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge,
+ uint64_t next_hop)
+{
+ uint64_t tbl24_tmp;
+ int tbl8_idx;
+ int tmp_tbl8_idx;
+ uint8_t *tbl8_ptr;
+ uint32_t len;
+
+ len = ((ledge == 0) && (redge == 0)) ? 1 << 24 :
+ ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8;
+
+ if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) {
+ if ((ROUNDUP(ledge, 24) - ledge) != 0) {
+ tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
+ if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
+ DIR24_8_EXT_ENT) {
+ /**
+ * Make sure there is space for two TBL8.
+ * This is necessary when installing range that
+ * needs tbl8 for ledge and redge.
+ */
+ tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
+ tmp_tbl8_idx = tbl8_get_idx(dp);
+ if (tbl8_idx < 0)
+ return -ENOSPC;
+ else if (tmp_tbl8_idx < 0) {
+ tbl8_free_idx(dp, tbl8_idx);
+ return -ENOSPC;
+ }
+ tbl8_free_idx(dp, tmp_tbl8_idx);
+ /*update dir24 entry with tbl8 index*/
+ write_to_fib(get_tbl24_p(dp, ledge,
+ dp->nh_sz), (tbl8_idx << 1)|
+ DIR24_8_EXT_ENT,
+ dp->nh_sz, 1);
+ } else
+ tbl8_idx = tbl24_tmp >> 1;
+ tbl8_ptr = (uint8_t *)dp->tbl8 +
+ (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
+ (ledge & ~DIR24_8_TBL24_MASK)) <<
+ dp->nh_sz);
+ /*update tbl8 with new next hop*/
+ write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
+ DIR24_8_EXT_ENT,
+ dp->nh_sz, ROUNDUP(ledge, 24) - ledge);
+ tbl8_recycle(dp, ledge, tbl8_idx);
+ }
+ write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz),
+ next_hop << 1, dp->nh_sz, len);
+ if (redge & ~DIR24_8_TBL24_MASK) {
+ tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz);
+ if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
+ DIR24_8_EXT_ENT) {
+ tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
+ if (tbl8_idx < 0)
+ return -ENOSPC;
+ /*update dir24 entry with tbl8 index*/
+ write_to_fib(get_tbl24_p(dp, redge,
+ dp->nh_sz), (tbl8_idx << 1)|
+ DIR24_8_EXT_ENT,
+ dp->nh_sz, 1);
+ } else
+ tbl8_idx = tbl24_tmp >> 1;
+ tbl8_ptr = (uint8_t *)dp->tbl8 +
+ ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) <<
+ dp->nh_sz);
+ /*update tbl8 with new next hop*/
+ write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
+ DIR24_8_EXT_ENT,
+ dp->nh_sz, redge & ~DIR24_8_TBL24_MASK);
+ tbl8_recycle(dp, redge, tbl8_idx);
+ }
+ } else if ((redge - ledge) != 0) {
+ tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz);
+ if ((tbl24_tmp & DIR24_8_EXT_ENT) !=
+ DIR24_8_EXT_ENT) {
+ tbl8_idx = tbl8_alloc(dp, tbl24_tmp);
+ if (tbl8_idx < 0)
+ return -ENOSPC;
+ /*update dir24 entry with tbl8 index*/
+ write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz),
+ (tbl8_idx << 1)|
+ DIR24_8_EXT_ENT,
+ dp->nh_sz, 1);
+ } else
+ tbl8_idx = tbl24_tmp >> 1;
+ tbl8_ptr = (uint8_t *)dp->tbl8 +
+ (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) +
+ (ledge & ~DIR24_8_TBL24_MASK)) <<
+ dp->nh_sz);
+ /*update tbl8 with new next hop*/
+ write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
+ DIR24_8_EXT_ENT,
+ dp->nh_sz, redge - ledge);
+ tbl8_recycle(dp, ledge, tbl8_idx);
+ }
+ return 0;
+}
+
+static int
+modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip,
+ uint8_t depth, uint64_t next_hop)
+{
+ struct rte_rib_node *tmp = NULL;
+ uint32_t ledge, redge, 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 +
+ (uint32_t)(1ULL << (32 - tmp_depth));
+ continue;
+ }
+ ret = install_to_fib(dp, ledge, redge,
+ next_hop);
+ if (ret != 0)
+ return ret;
+ ledge = redge +
+ (uint32_t)(1ULL << (32 - tmp_depth));
+ } else {
+ redge = ip + (uint32_t)(1ULL << (32 - depth));
+ if (ledge == redge)
+ break;
+ ret = install_to_fib(dp, ledge, redge,
+ next_hop);
+ if (ret != 0)
+ return ret;
+ }
+ } while (tmp);
+
+ return 0;
+}
+
+int
+dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
+ uint64_t next_hop, int op)
+{
+ struct dir24_8_tbl *dp;
+ struct rte_rib *rib;
+ struct rte_rib_node *tmp = NULL;
+ 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 > get_max_nh(dp->nh_sz))
+ 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 0;
+ }
+ if (depth > 24) {
+ tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
+ RTE_RIB_GET_NXT_COVER);
+ if ((tmp == NULL) &&
+ (dp->rsvd_tbl8s >= dp->number_tbl8s))
+ return -ENOSPC;
+
+ }
+ 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;
+ }
+ if ((depth > 24) && (tmp == NULL))
+ dp->rsvd_tbl8s++;
+ 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);
+ if (depth > 24) {
+ tmp = rte_rib_get_nxt(rib, ip, 24, NULL,
+ RTE_RIB_GET_NXT_COVER);
+ if (tmp == NULL)
+ dp->rsvd_tbl8s--;
+ }
+ }
+ return ret;
+ default:
+ break;
+ }
+ return -EINVAL;
+}
+
+void *
+dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf)
+{
+ char mem_name[DIR24_8_NAMESIZE];
+ struct dir24_8_tbl *dp;
+ uint64_t def_nh;
+ uint32_t num_tbl8;
+ enum rte_fib_dir24_8_nh_sz nh_sz;
+
+ if ((name == NULL) || (fib_conf == NULL) ||
+ (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) ||
+ (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) ||
+ (fib_conf->dir24_8.num_tbl8 >
+ get_max_nh(fib_conf->dir24_8.nh_sz)) ||
+ (fib_conf->dir24_8.num_tbl8 == 0) ||
+ (fib_conf->default_nh >
+ get_max_nh(fib_conf->dir24_8.nh_sz))) {
+ rte_errno = EINVAL;
+ return NULL;
+ }
+
+ def_nh = fib_conf->default_nh;
+ nh_sz = fib_conf->dir24_8.nh_sz;
+ num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8,
+ BITMAP_SLAB_BIT_SIZE);
+
+ snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
+ dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) +
+ DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
+ socket_id);
+ if (dp == NULL) {
+ rte_errno = ENOMEM;
+ return NULL;
+ }
+
+ /* Init table with default value */
+ write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
+
+ snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
+ uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) *
+ (num_tbl8 + 1);
+ dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz,
+ RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl8 == NULL) {
+ rte_errno = ENOMEM;
+ rte_free(dp);
+ return NULL;
+ }
+ dp->def_nh = def_nh;
+ dp->nh_sz = nh_sz;
+ dp->number_tbl8s = num_tbl8;
+
+ snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
+ dp->tbl8_idxes = rte_zmalloc_socket(mem_name,
+ RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3,
+ RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl8_idxes == NULL) {
+ rte_errno = ENOMEM;
+ rte_free(dp->tbl8);
+ rte_free(dp);
+ return NULL;
+ }
+
+ return dp;
+}
+
+void
+dir24_8_free(void *p)
+{
+ struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p;
+
+ rte_free(dp->tbl8_idxes);
+ rte_free(dp->tbl8);
+ rte_free(dp);
+}
diff --git a/src/spdk/dpdk/lib/librte_fib/dir24_8.h b/src/spdk/dpdk/lib/librte_fib/dir24_8.h
new file mode 100644
index 000000000..1ec437c0c
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/dir24_8.h
@@ -0,0 +1,35 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _DIR24_8_H_
+#define _DIR24_8_H_
+
+/**
+ * @file
+ * DIR24_8 algorithm
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void *
+dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf);
+
+void
+dir24_8_free(void *p);
+
+rte_fib_lookup_fn_t
+dir24_8_get_lookup_fn(struct rte_fib_conf *conf);
+
+int
+dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
+ uint64_t next_hop, int op);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _DIR24_8_H_ */
diff --git a/src/spdk/dpdk/lib/librte_fib/meson.build b/src/spdk/dpdk/lib/librte_fib/meson.build
new file mode 100644
index 000000000..6ff86e330
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/meson.build
@@ -0,0 +1,9 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+# Copyright(c) 2019 Intel Corporation
+
+sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'trie.c')
+headers = files('rte_fib.h', 'rte_fib6.h')
+deps += ['rib']
+build = false
+reason = 'not needed by SPDK'
diff --git a/src/spdk/dpdk/lib/librte_fib/rte_fib.c b/src/spdk/dpdk/lib/librte_fib/rte_fib.c
new file mode 100644
index 000000000..e0908084f
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/rte_fib.c
@@ -0,0 +1,319 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include <rte_eal.h>
+#include <rte_eal_memconfig.h>
+#include <rte_errno.h>
+#include <rte_malloc.h>
+#include <rte_rwlock.h>
+#include <rte_string_fns.h>
+#include <rte_tailq.h>
+
+#include <rte_rib.h>
+#include <rte_fib.h>
+
+#include "dir24_8.h"
+
+TAILQ_HEAD(rte_fib_list, rte_tailq_entry);
+static struct rte_tailq_elem rte_fib_tailq = {
+ .name = "RTE_FIB",
+};
+EAL_REGISTER_TAILQ(rte_fib_tailq)
+
+/* Maximum length of a FIB name. */
+#define RTE_FIB_NAMESIZE 64
+
+#if defined(RTE_LIBRTE_FIB_DEBUG)
+#define FIB_RETURN_IF_TRUE(cond, retval) do { \
+ if (cond) \
+ return retval; \
+} while (0)
+#else
+#define FIB_RETURN_IF_TRUE(cond, retval)
+#endif
+
+struct rte_fib {
+ char name[RTE_FIB_NAMESIZE];
+ enum rte_fib_type type; /**< Type of FIB struct */
+ struct rte_rib *rib; /**< RIB helper datastruct */
+ void *dp; /**< pointer to the dataplane struct*/
+ rte_fib_lookup_fn_t lookup; /**< fib lookup function */
+ rte_fib_modify_fn_t modify; /**< modify fib datastruct */
+ uint64_t def_nh;
+};
+
+static void
+dummy_lookup(void *fib_p, const uint32_t *ips, uint64_t *next_hops,
+ const unsigned int n)
+{
+ unsigned int i;
+ struct rte_fib *fib = fib_p;
+ struct rte_rib_node *node;
+
+ for (i = 0; i < n; i++) {
+ node = rte_rib_lookup(fib->rib, ips[i]);
+ if (node != NULL)
+ rte_rib_get_nh(node, &next_hops[i]);
+ else
+ next_hops[i] = fib->def_nh;
+ }
+}
+
+static int
+dummy_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth,
+ uint64_t next_hop, int op)
+{
+ struct rte_rib_node *node;
+ if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH))
+ return -EINVAL;
+
+ node = rte_rib_lookup_exact(fib->rib, ip, depth);
+
+ switch (op) {
+ case RTE_FIB_ADD:
+ if (node == NULL)
+ node = rte_rib_insert(fib->rib, ip, depth);
+ if (node == NULL)
+ return -rte_errno;
+ return rte_rib_set_nh(node, next_hop);
+ case RTE_FIB_DEL:
+ if (node == NULL)
+ return -ENOENT;
+ rte_rib_remove(fib->rib, ip, depth);
+ return 0;
+ }
+ return -EINVAL;
+}
+
+static int
+init_dataplane(struct rte_fib *fib, __rte_unused int socket_id,
+ struct rte_fib_conf *conf)
+{
+ char dp_name[sizeof(void *)];
+
+ snprintf(dp_name, sizeof(dp_name), "%p", fib);
+ switch (conf->type) {
+ case RTE_FIB_DUMMY:
+ fib->dp = fib;
+ fib->lookup = dummy_lookup;
+ fib->modify = dummy_modify;
+ return 0;
+ case RTE_FIB_DIR24_8:
+ fib->dp = dir24_8_create(dp_name, socket_id, conf);
+ if (fib->dp == NULL)
+ return -rte_errno;
+ fib->lookup = dir24_8_get_lookup_fn(conf);
+ fib->modify = dir24_8_modify;
+ return 0;
+ default:
+ return -EINVAL;
+ }
+ return 0;
+}
+
+int
+rte_fib_add(struct rte_fib *fib, uint32_t ip, uint8_t depth, uint64_t next_hop)
+{
+ if ((fib == NULL) || (fib->modify == NULL) ||
+ (depth > RTE_FIB_MAXDEPTH))
+ return -EINVAL;
+ return fib->modify(fib, ip, depth, next_hop, RTE_FIB_ADD);
+}
+
+int
+rte_fib_delete(struct rte_fib *fib, uint32_t ip, uint8_t depth)
+{
+ if ((fib == NULL) || (fib->modify == NULL) ||
+ (depth > RTE_FIB_MAXDEPTH))
+ return -EINVAL;
+ return fib->modify(fib, ip, depth, 0, RTE_FIB_DEL);
+}
+
+int
+rte_fib_lookup_bulk(struct rte_fib *fib, uint32_t *ips,
+ uint64_t *next_hops, int n)
+{
+ FIB_RETURN_IF_TRUE(((fib == NULL) || (ips == NULL) ||
+ (next_hops == NULL) || (fib->lookup == NULL)), -EINVAL);
+
+ fib->lookup(fib->dp, ips, next_hops, n);
+ return 0;
+}
+
+struct rte_fib *
+rte_fib_create(const char *name, int socket_id, struct rte_fib_conf *conf)
+{
+ char mem_name[RTE_FIB_NAMESIZE];
+ int ret;
+ struct rte_fib *fib = NULL;
+ struct rte_rib *rib = NULL;
+ struct rte_tailq_entry *te;
+ struct rte_fib_list *fib_list;
+ struct rte_rib_conf rib_conf;
+
+ /* Check user arguments. */
+ if ((name == NULL) || (conf == NULL) || (conf->max_routes < 0) ||
+ (conf->type >= RTE_FIB_TYPE_MAX)) {
+ rte_errno = EINVAL;
+ return NULL;
+ }
+
+ rib_conf.ext_sz = 0;
+ rib_conf.max_nodes = conf->max_routes * 2;
+
+ rib = rte_rib_create(name, socket_id, &rib_conf);
+ if (rib == NULL) {
+ RTE_LOG(ERR, LPM,
+ "Can not allocate RIB %s\n", name);
+ return NULL;
+ }
+
+ snprintf(mem_name, sizeof(mem_name), "FIB_%s", name);
+ fib_list = RTE_TAILQ_CAST(rte_fib_tailq.head, rte_fib_list);
+
+ rte_mcfg_tailq_write_lock();
+
+ /* guarantee there's no existing */
+ TAILQ_FOREACH(te, fib_list, next) {
+ fib = (struct rte_fib *)te->data;
+ if (strncmp(name, fib->name, RTE_FIB_NAMESIZE) == 0)
+ break;
+ }
+ fib = NULL;
+ if (te != NULL) {
+ rte_errno = EEXIST;
+ goto exit;
+ }
+
+ /* allocate tailq entry */
+ te = rte_zmalloc("FIB_TAILQ_ENTRY", sizeof(*te), 0);
+ if (te == NULL) {
+ RTE_LOG(ERR, LPM,
+ "Can not allocate tailq entry for FIB %s\n", name);
+ rte_errno = ENOMEM;
+ goto exit;
+ }
+
+ /* Allocate memory to store the FIB data structures. */
+ fib = rte_zmalloc_socket(mem_name,
+ sizeof(struct rte_fib), RTE_CACHE_LINE_SIZE, socket_id);
+ if (fib == NULL) {
+ RTE_LOG(ERR, LPM, "FIB %s memory allocation failed\n", name);
+ rte_errno = ENOMEM;
+ goto free_te;
+ }
+
+ rte_strlcpy(fib->name, name, sizeof(fib->name));
+ fib->rib = rib;
+ fib->type = conf->type;
+ fib->def_nh = conf->default_nh;
+ ret = init_dataplane(fib, socket_id, conf);
+ if (ret < 0) {
+ RTE_LOG(ERR, LPM,
+ "FIB dataplane struct %s memory allocation failed "
+ "with err %d\n", name, ret);
+ rte_errno = -ret;
+ goto free_fib;
+ }
+
+ te->data = (void *)fib;
+ TAILQ_INSERT_TAIL(fib_list, te, next);
+
+ rte_mcfg_tailq_write_unlock();
+
+ return fib;
+
+free_fib:
+ rte_free(fib);
+free_te:
+ rte_free(te);
+exit:
+ rte_mcfg_tailq_write_unlock();
+ rte_rib_free(rib);
+
+ return NULL;
+}
+
+struct rte_fib *
+rte_fib_find_existing(const char *name)
+{
+ struct rte_fib *fib = NULL;
+ struct rte_tailq_entry *te;
+ struct rte_fib_list *fib_list;
+
+ fib_list = RTE_TAILQ_CAST(rte_fib_tailq.head, rte_fib_list);
+
+ rte_mcfg_tailq_read_lock();
+ TAILQ_FOREACH(te, fib_list, next) {
+ fib = (struct rte_fib *) te->data;
+ if (strncmp(name, fib->name, RTE_FIB_NAMESIZE) == 0)
+ break;
+ }
+ rte_mcfg_tailq_read_unlock();
+
+ if (te == NULL) {
+ rte_errno = ENOENT;
+ return NULL;
+ }
+
+ return fib;
+}
+
+static void
+free_dataplane(struct rte_fib *fib)
+{
+ switch (fib->type) {
+ case RTE_FIB_DUMMY:
+ return;
+ case RTE_FIB_DIR24_8:
+ dir24_8_free(fib->dp);
+ default:
+ return;
+ }
+}
+
+void
+rte_fib_free(struct rte_fib *fib)
+{
+ struct rte_tailq_entry *te;
+ struct rte_fib_list *fib_list;
+
+ if (fib == NULL)
+ return;
+
+ fib_list = RTE_TAILQ_CAST(rte_fib_tailq.head, rte_fib_list);
+
+ rte_mcfg_tailq_write_lock();
+
+ /* find our tailq entry */
+ TAILQ_FOREACH(te, fib_list, next) {
+ if (te->data == (void *)fib)
+ break;
+ }
+ if (te != NULL)
+ TAILQ_REMOVE(fib_list, te, next);
+
+ rte_mcfg_tailq_write_unlock();
+
+ free_dataplane(fib);
+ rte_rib_free(fib->rib);
+ rte_free(fib);
+ rte_free(te);
+}
+
+void *
+rte_fib_get_dp(struct rte_fib *fib)
+{
+ return (fib == NULL) ? NULL : fib->dp;
+}
+
+struct rte_rib *
+rte_fib_get_rib(struct rte_fib *fib)
+{
+ return (fib == NULL) ? NULL : fib->rib;
+}
diff --git a/src/spdk/dpdk/lib/librte_fib/rte_fib.h b/src/spdk/dpdk/lib/librte_fib/rte_fib.h
new file mode 100644
index 000000000..af3bbf07e
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/rte_fib.h
@@ -0,0 +1,196 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _RTE_FIB_H_
+#define _RTE_FIB_H_
+
+/**
+ * @file
+ * FIB (Forwarding information base) implementation
+ * for IPv4 Longest Prefix Match
+ */
+
+#include <rte_compat.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct rte_fib;
+struct rte_rib;
+
+/** Maximum depth value possible for IPv4 FIB. */
+#define RTE_FIB_MAXDEPTH 32
+
+/** 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_TYPE_MAX
+};
+
+/** Modify FIB function */
+typedef int (*rte_fib_modify_fn_t)(struct rte_fib *fib, uint32_t ip,
+ uint8_t depth, uint64_t next_hop, int op);
+/** FIB bulk lookup function */
+typedef void (*rte_fib_lookup_fn_t)(void *fib, const uint32_t *ips,
+ uint64_t *next_hops, const unsigned int n);
+
+enum rte_fib_op {
+ RTE_FIB_ADD,
+ RTE_FIB_DEL,
+};
+
+/** Size of nexthop (1 << nh_sz) bits for DIR24_8 based FIB */
+enum rte_fib_dir24_8_nh_sz {
+ RTE_FIB_DIR24_8_1B,
+ RTE_FIB_DIR24_8_2B,
+ RTE_FIB_DIR24_8_4B,
+ RTE_FIB_DIR24_8_8B
+};
+
+/** FIB configuration structure */
+struct rte_fib_conf {
+ enum rte_fib_type type; /**< Type of FIB struct */
+ /** Default value returned on lookup if there is no route */
+ uint64_t default_nh;
+ int max_routes;
+ union {
+ struct {
+ enum rte_fib_dir24_8_nh_sz nh_sz;
+ uint32_t num_tbl8;
+ } dir24_8;
+ };
+};
+
+/**
+ * Create FIB
+ *
+ * @param name
+ * FIB name
+ * @param socket_id
+ * NUMA socket ID for FIB table memory allocation
+ * @param conf
+ * Structure containing the configuration
+ * @return
+ * Handle to the FIB object on success
+ * NULL otherwise with rte_errno set to an appropriate values.
+ */
+__rte_experimental
+struct rte_fib *
+rte_fib_create(const char *name, int socket_id, struct rte_fib_conf *conf);
+
+/**
+ * Find an existing FIB object and return a pointer to it.
+ *
+ * @param name
+ * Name of the fib object as passed to rte_fib_create()
+ * @return
+ * Pointer to fib object or NULL if object not found with rte_errno
+ * set appropriately. Possible rte_errno values include:
+ * - ENOENT - required entry not available to return.
+ */
+__rte_experimental
+struct rte_fib *
+rte_fib_find_existing(const char *name);
+
+/**
+ * Free an FIB object.
+ *
+ * @param fib
+ * FIB object handle
+ * @return
+ * None
+ */
+__rte_experimental
+void
+rte_fib_free(struct rte_fib *fib);
+
+/**
+ * Add a route to the FIB.
+ *
+ * @param fib
+ * FIB object handle
+ * @param ip
+ * IPv4 prefix address to be added to the FIB
+ * @param depth
+ * Prefix length
+ * @param next_hop
+ * Next hop to be added to the FIB
+ * @return
+ * 0 on success, negative value otherwise
+ */
+__rte_experimental
+int
+rte_fib_add(struct rte_fib *fib, uint32_t ip, uint8_t depth, uint64_t next_hop);
+
+/**
+ * Delete a rule from the FIB.
+ *
+ * @param fib
+ * FIB object handle
+ * @param ip
+ * IPv4 prefix address to be deleted from the FIB
+ * @param depth
+ * Prefix length
+ * @return
+ * 0 on success, negative value otherwise
+ */
+__rte_experimental
+int
+rte_fib_delete(struct rte_fib *fib, uint32_t ip, uint8_t depth);
+
+/**
+ * Lookup multiple IP addresses in the FIB.
+ *
+ * @param fib
+ * FIB object handle
+ * @param ips
+ * Array of IPs to be looked up in the FIB
+ * @param next_hops
+ * Next hop of the most specific rule found for IP.
+ * This is an array of eight byte values.
+ * If the lookup for the given IP failed, then corresponding element would
+ * contain default nexthop value configured for a FIB.
+ * @param n
+ * Number of elements in ips (and next_hops) array to lookup.
+ * @return
+ * -EINVAL for incorrect arguments, otherwise 0
+ */
+__rte_experimental
+int
+rte_fib_lookup_bulk(struct rte_fib *fib, uint32_t *ips,
+ uint64_t *next_hops, int n);
+/**
+ * Get pointer to the dataplane specific struct
+ *
+ * @param fib
+ * FIB object handle
+ * @return
+ * Pointer on the dataplane struct on success
+ * NULL othervise
+ */
+__rte_experimental
+void *
+rte_fib_get_dp(struct rte_fib *fib);
+
+/**
+ * Get pointer to the RIB
+ *
+ * @param fib
+ * FIB object handle
+ * @return
+ * Pointer on the RIB on success
+ * NULL othervise
+ */
+__rte_experimental
+struct rte_rib *
+rte_fib_get_rib(struct rte_fib *fib);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_FIB_H_ */
diff --git a/src/spdk/dpdk/lib/librte_fib/rte_fib6.c b/src/spdk/dpdk/lib/librte_fib/rte_fib6.c
new file mode 100644
index 000000000..a1f0db844
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/rte_fib6.c
@@ -0,0 +1,321 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdint.h>
+#include <string.h>
+
+#include <rte_eal.h>
+#include <rte_eal_memconfig.h>
+#include <rte_tailq.h>
+#include <rte_errno.h>
+#include <rte_rwlock.h>
+#include <rte_malloc.h>
+#include <rte_string_fns.h>
+
+#include <rte_rib6.h>
+#include <rte_fib6.h>
+
+#include "trie.h"
+
+TAILQ_HEAD(rte_fib6_list, rte_tailq_entry);
+static struct rte_tailq_elem rte_fib6_tailq = {
+ .name = "RTE_FIB6",
+};
+EAL_REGISTER_TAILQ(rte_fib6_tailq)
+
+/* Maximum length of a FIB name. */
+#define FIB6_NAMESIZE 64
+
+#if defined(RTE_LIBRTE_FIB_DEBUG)
+#define FIB6_RETURN_IF_TRUE(cond, retval) do { \
+ if (cond) \
+ return retval; \
+} while (0)
+#else
+#define FIB6_RETURN_IF_TRUE(cond, retval)
+#endif
+
+struct rte_fib6 {
+ char name[FIB6_NAMESIZE];
+ enum rte_fib6_type type; /**< Type of FIB struct */
+ struct rte_rib6 *rib; /**< RIB helper datastruct */
+ void *dp; /**< pointer to the dataplane struct*/
+ rte_fib6_lookup_fn_t lookup; /**< fib lookup function */
+ rte_fib6_modify_fn_t modify; /**< modify fib datastruct */
+ uint64_t def_nh;
+};
+
+static void
+dummy_lookup(void *fib_p, uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE],
+ uint64_t *next_hops, const unsigned int n)
+{
+ unsigned int i;
+ struct rte_fib6 *fib = fib_p;
+ struct rte_rib6_node *node;
+
+ for (i = 0; i < n; i++) {
+ node = rte_rib6_lookup(fib->rib, ips[i]);
+ if (node != NULL)
+ rte_rib6_get_nh(node, &next_hops[i]);
+ else
+ next_hops[i] = fib->def_nh;
+ }
+}
+
+static int
+dummy_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ uint8_t depth, uint64_t next_hop, int op)
+{
+ struct rte_rib6_node *node;
+ if ((fib == NULL) || (depth > RTE_FIB6_MAXDEPTH))
+ return -EINVAL;
+
+ node = rte_rib6_lookup_exact(fib->rib, ip, depth);
+
+ switch (op) {
+ case RTE_FIB6_ADD:
+ if (node == NULL)
+ node = rte_rib6_insert(fib->rib, ip, depth);
+ if (node == NULL)
+ return -rte_errno;
+ return rte_rib6_set_nh(node, next_hop);
+ case RTE_FIB6_DEL:
+ if (node == NULL)
+ return -ENOENT;
+ rte_rib6_remove(fib->rib, ip, depth);
+ return 0;
+ }
+ return -EINVAL;
+}
+
+static int
+init_dataplane(struct rte_fib6 *fib, __rte_unused int socket_id,
+ struct rte_fib6_conf *conf)
+{
+ char dp_name[sizeof(void *)];
+
+ snprintf(dp_name, sizeof(dp_name), "%p", fib);
+ switch (conf->type) {
+ case RTE_FIB6_DUMMY:
+ fib->dp = fib;
+ fib->lookup = dummy_lookup;
+ fib->modify = dummy_modify;
+ return 0;
+ case RTE_FIB6_TRIE:
+ fib->dp = trie_create(dp_name, socket_id, conf);
+ if (fib->dp == NULL)
+ return -rte_errno;
+ fib->lookup = rte_trie_get_lookup_fn(conf);
+ fib->modify = trie_modify;
+ return 0;
+ default:
+ return -EINVAL;
+ }
+ return 0;
+}
+
+int
+rte_fib6_add(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ uint8_t depth, uint64_t next_hop)
+{
+ if ((fib == NULL) || (ip == NULL) || (fib->modify == NULL) ||
+ (depth > RTE_FIB6_MAXDEPTH))
+ return -EINVAL;
+ return fib->modify(fib, ip, depth, next_hop, RTE_FIB6_ADD);
+}
+
+int
+rte_fib6_delete(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ uint8_t depth)
+{
+ if ((fib == NULL) || (ip == NULL) || (fib->modify == NULL) ||
+ (depth > RTE_FIB6_MAXDEPTH))
+ return -EINVAL;
+ return fib->modify(fib, ip, depth, 0, RTE_FIB6_DEL);
+}
+
+int
+rte_fib6_lookup_bulk(struct rte_fib6 *fib,
+ uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE],
+ uint64_t *next_hops, int n)
+{
+ FIB6_RETURN_IF_TRUE((fib == NULL) || (ips == NULL) ||
+ (next_hops == NULL) || (fib->lookup == NULL), -EINVAL);
+ fib->lookup(fib->dp, ips, next_hops, n);
+ return 0;
+}
+
+struct rte_fib6 *
+rte_fib6_create(const char *name, int socket_id, struct rte_fib6_conf *conf)
+{
+ char mem_name[FIB6_NAMESIZE];
+ int ret;
+ struct rte_fib6 *fib = NULL;
+ struct rte_rib6 *rib = NULL;
+ struct rte_tailq_entry *te;
+ struct rte_fib6_list *fib_list;
+ struct rte_rib6_conf rib_conf;
+
+ /* Check user arguments. */
+ if ((name == NULL) || (conf == NULL) || (conf->max_routes < 0) ||
+ (conf->type >= RTE_FIB6_TYPE_MAX)) {
+ rte_errno = EINVAL;
+ return NULL;
+ }
+
+ rib_conf.ext_sz = 0;
+ rib_conf.max_nodes = conf->max_routes * 2;
+
+ rib = rte_rib6_create(name, socket_id, &rib_conf);
+ if (rib == NULL) {
+ RTE_LOG(ERR, LPM,
+ "Can not allocate RIB %s\n", name);
+ return NULL;
+ }
+
+ snprintf(mem_name, sizeof(mem_name), "FIB6_%s", name);
+ fib_list = RTE_TAILQ_CAST(rte_fib6_tailq.head, rte_fib6_list);
+
+ rte_mcfg_tailq_write_lock();
+
+ /* guarantee there's no existing */
+ TAILQ_FOREACH(te, fib_list, next) {
+ fib = (struct rte_fib6 *)te->data;
+ if (strncmp(name, fib->name, FIB6_NAMESIZE) == 0)
+ break;
+ }
+ fib = NULL;
+ if (te != NULL) {
+ rte_errno = EEXIST;
+ goto exit;
+ }
+
+ /* allocate tailq entry */
+ te = rte_zmalloc("FIB_TAILQ_ENTRY", sizeof(*te), 0);
+ if (te == NULL) {
+ RTE_LOG(ERR, LPM,
+ "Can not allocate tailq entry for FIB %s\n", name);
+ rte_errno = ENOMEM;
+ goto exit;
+ }
+
+ /* Allocate memory to store the FIB data structures. */
+ fib = rte_zmalloc_socket(mem_name,
+ sizeof(struct rte_fib6), RTE_CACHE_LINE_SIZE, socket_id);
+ if (fib == NULL) {
+ RTE_LOG(ERR, LPM, "FIB %s memory allocation failed\n", name);
+ rte_errno = ENOMEM;
+ goto free_te;
+ }
+
+ rte_strlcpy(fib->name, name, sizeof(fib->name));
+ fib->rib = rib;
+ fib->type = conf->type;
+ fib->def_nh = conf->default_nh;
+ ret = init_dataplane(fib, socket_id, conf);
+ if (ret < 0) {
+ RTE_LOG(ERR, LPM,
+ "FIB dataplane struct %s memory allocation failed\n",
+ name);
+ rte_errno = -ret;
+ goto free_fib;
+ }
+
+ te->data = (void *)fib;
+ TAILQ_INSERT_TAIL(fib_list, te, next);
+
+ rte_mcfg_tailq_write_unlock();
+
+ return fib;
+
+free_fib:
+ rte_free(fib);
+free_te:
+ rte_free(te);
+exit:
+ rte_mcfg_tailq_write_unlock();
+ rte_rib6_free(rib);
+
+ return NULL;
+}
+
+struct rte_fib6 *
+rte_fib6_find_existing(const char *name)
+{
+ struct rte_fib6 *fib = NULL;
+ struct rte_tailq_entry *te;
+ struct rte_fib6_list *fib_list;
+
+ fib_list = RTE_TAILQ_CAST(rte_fib6_tailq.head, rte_fib6_list);
+
+ rte_mcfg_tailq_read_lock();
+ TAILQ_FOREACH(te, fib_list, next) {
+ fib = (struct rte_fib6 *) te->data;
+ if (strncmp(name, fib->name, FIB6_NAMESIZE) == 0)
+ break;
+ }
+ rte_mcfg_tailq_read_unlock();
+
+ if (te == NULL) {
+ rte_errno = ENOENT;
+ return NULL;
+ }
+
+ return fib;
+}
+
+static void
+free_dataplane(struct rte_fib6 *fib)
+{
+ switch (fib->type) {
+ case RTE_FIB6_DUMMY:
+ return;
+ case RTE_FIB6_TRIE:
+ trie_free(fib->dp);
+ default:
+ return;
+ }
+}
+
+void
+rte_fib6_free(struct rte_fib6 *fib)
+{
+ struct rte_tailq_entry *te;
+ struct rte_fib6_list *fib_list;
+
+ if (fib == NULL)
+ return;
+
+ fib_list = RTE_TAILQ_CAST(rte_fib6_tailq.head, rte_fib6_list);
+
+ rte_mcfg_tailq_write_lock();
+
+ /* find our tailq entry */
+ TAILQ_FOREACH(te, fib_list, next) {
+ if (te->data == (void *)fib)
+ break;
+ }
+ if (te != NULL)
+ TAILQ_REMOVE(fib_list, te, next);
+
+ rte_mcfg_tailq_write_unlock();
+
+ free_dataplane(fib);
+ rte_rib6_free(fib->rib);
+ rte_free(fib);
+ rte_free(te);
+}
+
+void *
+rte_fib6_get_dp(struct rte_fib6 *fib)
+{
+ return (fib == NULL) ? NULL : fib->dp;
+}
+
+struct rte_rib6 *
+rte_fib6_get_rib(struct rte_fib6 *fib)
+{
+ return (fib == NULL) ? NULL : fib->rib;
+}
diff --git a/src/spdk/dpdk/lib/librte_fib/rte_fib6.h b/src/spdk/dpdk/lib/librte_fib/rte_fib6.h
new file mode 100644
index 000000000..66c71c84c
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/rte_fib6.h
@@ -0,0 +1,201 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _RTE_FIB6_H_
+#define _RTE_FIB6_H_
+
+/**
+ * @file
+ * FIB (Forwarding information base) implementation
+ * for IPv6 Longest Prefix Match
+ */
+
+#include <rte_compat.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#define RTE_FIB6_IPV6_ADDR_SIZE 16
+/** Maximum depth value possible for IPv6 FIB. */
+#define RTE_FIB6_MAXDEPTH 128
+
+struct rte_fib6;
+struct rte_rib6;
+
+/** Type of FIB struct */
+enum rte_fib6_type {
+ RTE_FIB6_DUMMY, /**< RIB6 tree based FIB */
+ RTE_FIB6_TRIE, /**< TRIE based fib */
+ RTE_FIB6_TYPE_MAX
+};
+
+/** Modify FIB function */
+typedef int (*rte_fib6_modify_fn_t)(struct rte_fib6 *fib,
+ const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], uint8_t depth,
+ uint64_t next_hop, int op);
+/** FIB bulk lookup function */
+typedef void (*rte_fib6_lookup_fn_t)(void *fib,
+ uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE],
+ uint64_t *next_hops, const unsigned int n);
+
+enum rte_fib6_op {
+ RTE_FIB6_ADD,
+ RTE_FIB6_DEL,
+};
+
+enum rte_fib_trie_nh_sz {
+ RTE_FIB6_TRIE_2B = 1,
+ RTE_FIB6_TRIE_4B,
+ RTE_FIB6_TRIE_8B
+};
+
+/** FIB configuration structure */
+struct rte_fib6_conf {
+ enum rte_fib6_type type; /**< Type of FIB struct */
+ /** Default value returned on lookup if there is no route */
+ uint64_t default_nh;
+ int max_routes;
+ union {
+ struct {
+ enum rte_fib_trie_nh_sz nh_sz;
+ uint32_t num_tbl8;
+ } trie;
+ };
+};
+
+/**
+ * Create FIB
+ *
+ * @param name
+ * FIB name
+ * @param socket_id
+ * NUMA socket ID for FIB table memory allocation
+ * @param conf
+ * Structure containing the configuration
+ * @return
+ * Handle to FIB object on success
+ * NULL otherwise with rte_errno set to an appropriate values.
+ */
+__rte_experimental
+struct rte_fib6 *
+rte_fib6_create(const char *name, int socket_id, struct rte_fib6_conf *conf);
+
+/**
+ * Find an existing FIB object and return a pointer to it.
+ *
+ * @param name
+ * Name of the fib object as passed to rte_fib6_create()
+ * @return
+ * Pointer to fib object or NULL if object not found with rte_errno
+ * set appropriately. Possible rte_errno values include:
+ * - ENOENT - required entry not available to return.
+ */
+__rte_experimental
+struct rte_fib6 *
+rte_fib6_find_existing(const char *name);
+
+/**
+ * Free an FIB object.
+ *
+ * @param fib
+ * FIB object handle
+ * @return
+ * None
+ */
+__rte_experimental
+void
+rte_fib6_free(struct rte_fib6 *fib);
+
+/**
+ * Add a route to the FIB.
+ *
+ * @param fib
+ * FIB object handle
+ * @param ip
+ * IPv6 prefix address to be added to the FIB
+ * @param depth
+ * Prefix length
+ * @param next_hop
+ * Next hop to be added to the FIB
+ * @return
+ * 0 on success, negative value otherwise
+ */
+__rte_experimental
+int
+rte_fib6_add(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ uint8_t depth, uint64_t next_hop);
+
+/**
+ * Delete a rule from the FIB.
+ *
+ * @param fib
+ * FIB object handle
+ * @param ip
+ * IPv6 prefix address to be deleted from the FIB
+ * @param depth
+ * Prefix length
+ * @return
+ * 0 on success, negative value otherwise
+ */
+__rte_experimental
+int
+rte_fib6_delete(struct rte_fib6 *fib,
+ const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], uint8_t depth);
+
+/**
+ * Lookup multiple IP addresses in the FIB.
+ *
+ * @param fib
+ * FIB object handle
+ * @param ips
+ * Array of IPv6s to be looked up in the FIB
+ * @param next_hops
+ * Next hop of the most specific rule found for IP.
+ * This is an array of eight byte values.
+ * If the lookup for the given IP failed, then corresponding element would
+ * contain default nexthop value configured for a FIB.
+ * @param n
+ * Number of elements in ips (and next_hops) array to lookup.
+ * @return
+ * -EINVAL for incorrect arguments, otherwise 0
+ */
+__rte_experimental
+int
+rte_fib6_lookup_bulk(struct rte_fib6 *fib,
+ uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE],
+ uint64_t *next_hops, int n);
+
+/**
+ * Get pointer to the dataplane specific struct
+ *
+ * @param fib
+ * FIB6 object handle
+ * @return
+ * Pointer on the dataplane struct on success
+ * NULL othervise
+ */
+__rte_experimental
+void *
+rte_fib6_get_dp(struct rte_fib6 *fib);
+
+/**
+ * Get pointer to the RIB6
+ *
+ * @param fib
+ * FIB object handle
+ * @return
+ * Pointer on the RIB6 on success
+ * NULL othervise
+ */
+__rte_experimental
+struct rte_rib6 *
+rte_fib6_get_rib(struct rte_fib6 *fib);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_FIB6_H_ */
diff --git a/src/spdk/dpdk/lib/librte_fib/rte_fib_version.map b/src/spdk/dpdk/lib/librte_fib/rte_fib_version.map
new file mode 100644
index 000000000..9527417d2
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/rte_fib_version.map
@@ -0,0 +1,23 @@
+EXPERIMENTAL {
+ global:
+
+ rte_fib_add;
+ rte_fib_create;
+ rte_fib_delete;
+ rte_fib_find_existing;
+ rte_fib_free;
+ rte_fib_lookup_bulk;
+ rte_fib_get_dp;
+ rte_fib_get_rib;
+
+ rte_fib6_add;
+ rte_fib6_create;
+ rte_fib6_delete;
+ rte_fib6_find_existing;
+ rte_fib6_free;
+ rte_fib6_lookup_bulk;
+ rte_fib6_get_dp;
+ rte_fib6_get_rib;
+
+ local: *;
+};
diff --git a/src/spdk/dpdk/lib/librte_fib/trie.c b/src/spdk/dpdk/lib/librte_fib/trie.c
new file mode 100644
index 000000000..2ae2add4f
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/trie.c
@@ -0,0 +1,759 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <inttypes.h>
+
+#include <rte_debug.h>
+#include <rte_malloc.h>
+#include <rte_prefetch.h>
+#include <rte_errno.h>
+#include <rte_memory.h>
+#include <rte_branch_prediction.h>
+
+#include <rte_rib6.h>
+#include <rte_fib6.h>
+#include "trie.h"
+
+/* @internal Total number of tbl24 entries. */
+#define TRIE_TBL24_NUM_ENT (1 << 24)
+
+/* Maximum depth value possible for IPv6 LPM. */
+#define TRIE_MAX_DEPTH 128
+
+/* @internal Number of entries in a tbl8 group. */
+#define TRIE_TBL8_GRP_NUM_ENT 256ULL
+
+/* @internal Total number of tbl8 groups in the tbl8. */
+#define TRIE_TBL8_NUM_GROUPS 65536
+
+/* @internal bitmask with valid and valid_group fields set */
+#define TRIE_EXT_ENT 1
+
+#define TRIE_NAMESIZE 64
+
+#define BITMAP_SLAB_BIT_SIZE_LOG2 6
+#define BITMAP_SLAB_BIT_SIZE (1ULL << BITMAP_SLAB_BIT_SIZE_LOG2)
+#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1)
+
+struct rte_trie_tbl {
+ uint32_t number_tbl8s; /**< Total number of tbl8s */
+ uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */
+ uint32_t cur_tbl8s; /**< Current cumber of tbl8s */
+ uint64_t def_nh; /**< Default next hop */
+ enum rte_fib_trie_nh_sz nh_sz; /**< Size of nexthop entry */
+ uint64_t *tbl8; /**< tbl8 table. */
+ uint32_t *tbl8_pool; /**< bitmap containing free tbl8 idxes*/
+ uint32_t tbl8_pool_pos;
+ /* tbl24 table. */
+ __extension__ uint64_t tbl24[0] __rte_cache_aligned;
+};
+
+enum edge {
+ LEDGE,
+ REDGE
+};
+
+enum lookup_type {
+ MACRO,
+ INLINE,
+ UNI
+};
+static enum lookup_type test_lookup = MACRO;
+
+static inline uint32_t
+get_tbl24_idx(const uint8_t *ip)
+{
+ return ip[0] << 16|ip[1] << 8|ip[2];
+}
+
+static inline void *
+get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz)
+{
+ uint32_t tbl24_idx;
+
+ tbl24_idx = get_tbl24_idx(ip);
+ return (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz];
+}
+
+static inline uint8_t
+bits_in_nh(uint8_t nh_sz)
+{
+ return 8 * (1 << nh_sz);
+}
+
+static inline uint64_t
+get_max_nh(uint8_t nh_sz)
+{
+ return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
+}
+
+static inline uint64_t
+lookup_msk(uint8_t nh_sz)
+{
+ return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
+}
+
+static inline uint8_t
+get_psd_idx(uint32_t val, uint8_t nh_sz)
+{
+ return val & ((1 << (3 - nh_sz)) - 1);
+}
+
+static inline uint32_t
+get_tbl_pos(uint32_t val, uint8_t nh_sz)
+{
+ return val >> (3 - nh_sz);
+}
+
+static inline uint64_t
+get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz)
+{
+ return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) *
+ bits_in_nh(nh_sz))) & lookup_msk(nh_sz));
+}
+
+static inline void *
+get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz)
+{
+ return (uint8_t *)tbl + (idx << nh_sz);
+}
+
+static inline int
+is_entry_extended(uint64_t ent)
+{
+ return (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT;
+}
+
+#define LOOKUP_FUNC(suffix, type, nh_sz) \
+static void rte_trie_lookup_bulk_##suffix(void *p, \
+ uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], \
+ uint64_t *next_hops, const unsigned int n) \
+{ \
+ struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p; \
+ uint64_t tmp; \
+ uint32_t i, j; \
+ \
+ for (i = 0; i < n; i++) { \
+ tmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])]; \
+ j = 3; \
+ while (is_entry_extended(tmp)) { \
+ tmp = ((type *)dp->tbl8)[ips[i][j++] + \
+ ((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)]; \
+ } \
+ next_hops[i] = tmp >> 1; \
+ } \
+}
+LOOKUP_FUNC(2b, uint16_t, 1)
+LOOKUP_FUNC(4b, uint32_t, 2)
+LOOKUP_FUNC(8b, uint64_t, 3)
+
+rte_fib6_lookup_fn_t
+rte_trie_get_lookup_fn(struct rte_fib6_conf *conf)
+{
+ enum rte_fib_trie_nh_sz nh_sz = conf->trie.nh_sz;
+
+ if (test_lookup == MACRO) {
+ switch (nh_sz) {
+ case RTE_FIB6_TRIE_2B:
+ return rte_trie_lookup_bulk_2b;
+ case RTE_FIB6_TRIE_4B:
+ return rte_trie_lookup_bulk_4b;
+ case RTE_FIB6_TRIE_8B:
+ return rte_trie_lookup_bulk_8b;
+ }
+ }
+
+ return NULL;
+}
+
+static void
+write_to_dp(void *ptr, uint64_t val, enum rte_fib_trie_nh_sz size, int n)
+{
+ int i;
+ uint16_t *ptr16 = (uint16_t *)ptr;
+ uint32_t *ptr32 = (uint32_t *)ptr;
+ uint64_t *ptr64 = (uint64_t *)ptr;
+
+ switch (size) {
+ case RTE_FIB6_TRIE_2B:
+ for (i = 0; i < n; i++)
+ ptr16[i] = (uint16_t)val;
+ break;
+ case RTE_FIB6_TRIE_4B:
+ for (i = 0; i < n; i++)
+ ptr32[i] = (uint32_t)val;
+ break;
+ case RTE_FIB6_TRIE_8B:
+ for (i = 0; i < n; i++)
+ ptr64[i] = (uint64_t)val;
+ break;
+ }
+}
+
+static void
+tbl8_pool_init(struct rte_trie_tbl *dp)
+{
+ uint32_t i;
+
+ /* put entire range of indexes to the tbl8 pool */
+ for (i = 0; i < dp->number_tbl8s; i++)
+ dp->tbl8_pool[i] = i;
+
+ dp->tbl8_pool_pos = 0;
+}
+
+/*
+ * Get an index of a free tbl8 from the pool
+ */
+static inline int32_t
+tbl8_get(struct rte_trie_tbl *dp)
+{
+ if (dp->tbl8_pool_pos == dp->number_tbl8s)
+ /* no more free tbl8 */
+ return -ENOSPC;
+
+ /* next index */
+ return dp->tbl8_pool[dp->tbl8_pool_pos++];
+}
+
+/*
+ * Put an index of a free tbl8 back to the pool
+ */
+static inline void
+tbl8_put(struct rte_trie_tbl *dp, uint32_t tbl8_ind)
+{
+ dp->tbl8_pool[--dp->tbl8_pool_pos] = tbl8_ind;
+}
+
+static int
+tbl8_alloc(struct rte_trie_tbl *dp, uint64_t nh)
+{
+ int64_t tbl8_idx;
+ uint8_t *tbl8_ptr;
+
+ tbl8_idx = tbl8_get(dp);
+ if (tbl8_idx < 0)
+ return tbl8_idx;
+ tbl8_ptr = get_tbl_p_by_idx(dp->tbl8,
+ tbl8_idx * TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz);
+ /*Init tbl8 entries with nexthop from tbl24*/
+ write_to_dp((void *)tbl8_ptr, nh, dp->nh_sz,
+ TRIE_TBL8_GRP_NUM_ENT);
+ return tbl8_idx;
+}
+
+static void
+tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t tbl8_idx)
+{
+ uint32_t i;
+ uint64_t nh;
+ uint16_t *ptr16;
+ uint32_t *ptr32;
+ uint64_t *ptr64;
+
+ switch (dp->nh_sz) {
+ case RTE_FIB6_TRIE_2B:
+ ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx *
+ TRIE_TBL8_GRP_NUM_ENT];
+ nh = *ptr16;
+ if (nh & TRIE_EXT_ENT)
+ return;
+ for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr16[i])
+ return;
+ }
+ write_to_dp(par, nh, dp->nh_sz, 1);
+ for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
+ ptr16[i] = 0;
+ break;
+ case RTE_FIB6_TRIE_4B:
+ ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx *
+ TRIE_TBL8_GRP_NUM_ENT];
+ nh = *ptr32;
+ if (nh & TRIE_EXT_ENT)
+ return;
+ for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr32[i])
+ return;
+ }
+ write_to_dp(par, nh, dp->nh_sz, 1);
+ for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
+ ptr32[i] = 0;
+ break;
+ case RTE_FIB6_TRIE_8B:
+ ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx *
+ TRIE_TBL8_GRP_NUM_ENT];
+ nh = *ptr64;
+ if (nh & TRIE_EXT_ENT)
+ return;
+ for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) {
+ if (nh != ptr64[i])
+ return;
+ }
+ write_to_dp(par, nh, dp->nh_sz, 1);
+ for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++)
+ ptr64[i] = 0;
+ break;
+ }
+ tbl8_put(dp, tbl8_idx);
+}
+
+#define BYTE_SIZE 8
+static inline uint32_t
+get_idx(const uint8_t *ip, uint32_t prev_idx, int bytes, int first_byte)
+{
+ int i;
+ uint32_t idx = 0;
+ uint8_t bitshift;
+
+ for (i = first_byte; i < (first_byte + bytes); i++) {
+ bitshift = (int8_t)(((first_byte + bytes - 1) - i)*BYTE_SIZE);
+ idx |= ip[i] << bitshift;
+ }
+ return (prev_idx * TRIE_TBL8_GRP_NUM_ENT) + idx;
+}
+
+static inline uint64_t
+get_val_by_p(void *p, uint8_t nh_sz)
+{
+ uint64_t val = 0;
+
+ switch (nh_sz) {
+ case RTE_FIB6_TRIE_2B:
+ val = *(uint16_t *)p;
+ break;
+ case RTE_FIB6_TRIE_4B:
+ val = *(uint32_t *)p;
+ break;
+ case RTE_FIB6_TRIE_8B:
+ val = *(uint64_t *)p;
+ break;
+ }
+ return val;
+}
+
+/*
+ * recursively recycle tbl8's
+ */
+static void
+recycle_root_path(struct rte_trie_tbl *dp, const uint8_t *ip_part,
+ uint8_t common_tbl8, void *prev)
+{
+ void *p;
+ uint64_t val;
+
+ val = get_val_by_p(prev, dp->nh_sz);
+ if (unlikely((val & TRIE_EXT_ENT) != TRIE_EXT_ENT))
+ return;
+
+ if (common_tbl8 != 0) {
+ p = get_tbl_p_by_idx(dp->tbl8, (val >> 1) *
+ TRIE_TBL8_GRP_NUM_ENT + *ip_part, dp->nh_sz);
+ recycle_root_path(dp, ip_part + 1, common_tbl8 - 1, p);
+ }
+ tbl8_recycle(dp, prev, val >> 1);
+}
+
+static inline int
+build_common_root(struct rte_trie_tbl *dp, const uint8_t *ip,
+ int common_bytes, void **tbl)
+{
+ void *tbl_ptr = NULL;
+ uint64_t *cur_tbl;
+ uint64_t val;
+ int i, j, idx, prev_idx = 0;
+
+ cur_tbl = dp->tbl24;
+ for (i = 3, j = 0; i <= common_bytes; i++) {
+ idx = get_idx(ip, prev_idx, i - j, j);
+ val = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz);
+ tbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz);
+ if ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) {
+ idx = tbl8_alloc(dp, val);
+ if (unlikely(idx < 0))
+ return idx;
+ write_to_dp(tbl_ptr, (idx << 1) |
+ TRIE_EXT_ENT, dp->nh_sz, 1);
+ prev_idx = idx;
+ } else
+ prev_idx = val >> 1;
+
+ j = i;
+ cur_tbl = dp->tbl8;
+ }
+ *tbl = get_tbl_p_by_idx(cur_tbl, prev_idx * TRIE_TBL8_GRP_NUM_ENT,
+ dp->nh_sz);
+ return 0;
+}
+
+static int
+write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part, uint64_t next_hop,
+ int len, enum edge edge, void *ent)
+{
+ uint64_t val = next_hop << 1;
+ int tbl8_idx;
+ int ret = 0;
+ void *p;
+
+ if (len != 0) {
+ val = get_val_by_p(ent, dp->nh_sz);
+ if ((val & TRIE_EXT_ENT) == TRIE_EXT_ENT)
+ tbl8_idx = val >> 1;
+ else {
+ tbl8_idx = tbl8_alloc(dp, val);
+ if (tbl8_idx < 0)
+ return tbl8_idx;
+ val = (tbl8_idx << 1)|TRIE_EXT_ENT;
+ }
+ p = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx *
+ TRIE_TBL8_GRP_NUM_ENT) + *ip_part, dp->nh_sz);
+ ret = write_edge(dp, ip_part + 1, next_hop, len - 1, edge, p);
+ if (ret < 0)
+ return ret;
+ if (edge == LEDGE) {
+ write_to_dp((uint8_t *)p + (1 << dp->nh_sz),
+ next_hop << 1, dp->nh_sz, UINT8_MAX - *ip_part);
+ } else {
+ write_to_dp(get_tbl_p_by_idx(dp->tbl8, tbl8_idx *
+ TRIE_TBL8_GRP_NUM_ENT, dp->nh_sz),
+ next_hop << 1, dp->nh_sz, *ip_part);
+ }
+ tbl8_recycle(dp, &val, tbl8_idx);
+ }
+
+ write_to_dp(ent, val, dp->nh_sz, 1);
+ return ret;
+}
+
+#define IPV6_MAX_IDX (RTE_FIB6_IPV6_ADDR_SIZE - 1)
+#define TBL24_BYTES 3
+#define TBL8_LEN (RTE_FIB6_IPV6_ADDR_SIZE - TBL24_BYTES)
+
+static int
+install_to_dp(struct rte_trie_tbl *dp, const uint8_t *ledge, const uint8_t *r,
+ uint64_t next_hop)
+{
+ void *common_root_tbl;
+ void *ent;
+ int ret;
+ int i;
+ int common_bytes;
+ int llen, rlen;
+ uint8_t redge[16];
+
+ /* decrement redge by 1*/
+ rte_rib6_copy_addr(redge, r);
+ for (i = 15; i >= 0; i--) {
+ redge[i]--;
+ if (redge[i] != 0xff)
+ break;
+ }
+
+ for (common_bytes = 0; common_bytes < 15; common_bytes++) {
+ if (ledge[common_bytes] != redge[common_bytes])
+ break;
+ }
+
+ ret = build_common_root(dp, ledge, common_bytes, &common_root_tbl);
+ if (unlikely(ret != 0))
+ return ret;
+ /*first uncommon tbl8 byte idx*/
+ uint8_t first_tbl8_byte = RTE_MAX(common_bytes, TBL24_BYTES);
+
+ for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
+ if (ledge[i] != 0)
+ break;
+ }
+
+ llen = i - first_tbl8_byte + (common_bytes < 3);
+
+ for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) {
+ if (redge[i] != UINT8_MAX)
+ break;
+ }
+ rlen = i - first_tbl8_byte + (common_bytes < 3);
+
+ /*first noncommon byte*/
+ uint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes;
+ uint8_t first_idx_len = (common_bytes < 3) ? 3 : 1;
+
+ uint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx);
+ uint32_t right_idx = get_idx(redge, 0, first_idx_len, first_byte_idx);
+
+ ent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz);
+ ret = write_edge(dp, &ledge[first_tbl8_byte + !(common_bytes < 3)],
+ next_hop, llen, LEDGE, ent);
+ if (ret < 0)
+ return ret;
+
+ if (right_idx > left_idx + 1) {
+ ent = get_tbl_p_by_idx(common_root_tbl, left_idx + 1,
+ dp->nh_sz);
+ write_to_dp(ent, next_hop << 1, dp->nh_sz,
+ right_idx - (left_idx + 1));
+ }
+ ent = get_tbl_p_by_idx(common_root_tbl, right_idx, dp->nh_sz);
+ ret = write_edge(dp, &redge[first_tbl8_byte + !((common_bytes < 3))],
+ next_hop, rlen, REDGE, ent);
+ if (ret < 0)
+ return ret;
+
+ uint8_t common_tbl8 = (common_bytes < TBL24_BYTES) ?
+ 0 : common_bytes - (TBL24_BYTES - 1);
+ ent = get_tbl24_p(dp, ledge, dp->nh_sz);
+ recycle_root_path(dp, ledge + TBL24_BYTES, common_tbl8, ent);
+ return 0;
+}
+
+static void
+get_nxt_net(uint8_t *ip, uint8_t depth)
+{
+ int i;
+ uint8_t part_depth;
+ uint8_t prev_byte;
+
+ for (i = 0, part_depth = depth; part_depth > 8; part_depth -= 8, i++)
+ ;
+
+ prev_byte = ip[i];
+ ip[i] += 1 << (8 - part_depth);
+ if (ip[i] < prev_byte) {
+ while (i > 0) {
+ ip[--i] += 1;
+ if (ip[i] != 0)
+ break;
+ }
+ }
+}
+
+static int
+modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib,
+ const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ uint8_t depth, uint64_t next_hop)
+{
+ struct rte_rib6_node *tmp = NULL;
+ uint8_t ledge[RTE_FIB6_IPV6_ADDR_SIZE];
+ uint8_t redge[RTE_FIB6_IPV6_ADDR_SIZE];
+ int ret;
+ uint8_t tmp_depth;
+
+ if (next_hop > get_max_nh(dp->nh_sz))
+ return -EINVAL;
+
+ rte_rib6_copy_addr(ledge, ip);
+ do {
+ tmp = rte_rib6_get_nxt(rib, ip, depth, tmp,
+ RTE_RIB6_GET_NXT_COVER);
+ if (tmp != NULL) {
+ rte_rib6_get_depth(tmp, &tmp_depth);
+ if (tmp_depth == depth)
+ continue;
+ rte_rib6_get_ip(tmp, redge);
+ if (rte_rib6_is_equal(ledge, redge)) {
+ get_nxt_net(ledge, tmp_depth);
+ continue;
+ }
+ ret = install_to_dp(dp, ledge, redge,
+ next_hop);
+ if (ret != 0)
+ return ret;
+ get_nxt_net(redge, tmp_depth);
+ rte_rib6_copy_addr(ledge, redge);
+ } else {
+ rte_rib6_copy_addr(redge, ip);
+ get_nxt_net(redge, depth);
+ if (rte_rib6_is_equal(ledge, redge))
+ break;
+ ret = install_to_dp(dp, ledge, redge,
+ next_hop);
+ if (ret != 0)
+ return ret;
+ }
+ } while (tmp);
+
+ return 0;
+}
+
+int
+trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ 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;
+ uint8_t ip_masked[RTE_FIB6_IPV6_ADDR_SIZE];
+ int i, ret = 0;
+ uint64_t par_nh, node_nh;
+ uint8_t tmp_depth, depth_diff = 0, parent_depth = 24;
+
+ if ((fib == NULL) || (ip == NULL) || (depth > RTE_FIB6_MAXDEPTH))
+ return -EINVAL;
+
+ dp = rte_fib6_get_dp(fib);
+ RTE_ASSERT(dp);
+ rib = rte_fib6_get_rib(fib);
+ RTE_ASSERT(rib);
+
+ for (i = 0; i < RTE_FIB6_IPV6_ADDR_SIZE; i++)
+ ip_masked[i] = ip[i] & get_msk_part(depth, i);
+
+ if (depth > 24) {
+ tmp = rte_rib6_get_nxt(rib, ip_masked,
+ RTE_ALIGN_FLOOR(depth, 8), NULL,
+ RTE_RIB6_GET_NXT_COVER);
+ if (tmp == NULL) {
+ tmp = rte_rib6_lookup(rib, ip);
+ 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:
+ if (node != NULL) {
+ rte_rib6_get_nh(node, &node_nh);
+ if (node_nh == next_hop)
+ return 0;
+ ret = modify_dp(dp, rib, ip_masked, depth, next_hop);
+ if (ret == 0)
+ rte_rib6_set_nh(node, next_hop);
+ return 0;
+ }
+
+ if ((depth > 24) && (dp->rsvd_tbl8s >=
+ dp->number_tbl8s - depth_diff))
+ return -ENOSPC;
+
+ node = rte_rib6_insert(rib, ip_masked, depth);
+ if (node == NULL)
+ return -rte_errno;
+ rte_rib6_set_nh(node, next_hop);
+ parent = rte_rib6_lookup_parent(node);
+ if (parent != NULL) {
+ rte_rib6_get_nh(parent, &par_nh);
+ if (par_nh == next_hop)
+ return 0;
+ }
+ ret = modify_dp(dp, rib, ip_masked, depth, next_hop);
+ if (ret != 0) {
+ rte_rib6_remove(rib, ip_masked, depth);
+ return ret;
+ }
+
+ dp->rsvd_tbl8s += depth_diff;
+ return 0;
+ case RTE_FIB6_DEL:
+ if (node == NULL)
+ return -ENOENT;
+
+ parent = rte_rib6_lookup_parent(node);
+ if (parent != NULL) {
+ rte_rib6_get_nh(parent, &par_nh);
+ rte_rib6_get_nh(node, &node_nh);
+ if (par_nh != node_nh)
+ ret = modify_dp(dp, rib, ip_masked, depth,
+ par_nh);
+ } else
+ ret = modify_dp(dp, rib, ip_masked, depth, dp->def_nh);
+
+ if (ret != 0)
+ return ret;
+ rte_rib6_remove(rib, ip, depth);
+
+ dp->rsvd_tbl8s -= depth_diff;
+ return 0;
+ default:
+ break;
+ }
+ return -EINVAL;
+}
+
+void *
+trie_create(const char *name, int socket_id,
+ struct rte_fib6_conf *conf)
+{
+ char mem_name[TRIE_NAMESIZE];
+ struct rte_trie_tbl *dp = NULL;
+ uint64_t def_nh;
+ uint32_t num_tbl8;
+ enum rte_fib_trie_nh_sz nh_sz;
+
+ if ((name == NULL) || (conf == NULL) ||
+ (conf->trie.nh_sz < RTE_FIB6_TRIE_2B) ||
+ (conf->trie.nh_sz > RTE_FIB6_TRIE_8B) ||
+ (conf->trie.num_tbl8 >
+ get_max_nh(conf->trie.nh_sz)) ||
+ (conf->trie.num_tbl8 == 0) ||
+ (conf->default_nh >
+ get_max_nh(conf->trie.nh_sz))) {
+
+ rte_errno = EINVAL;
+ return NULL;
+ }
+
+ def_nh = conf->default_nh;
+ nh_sz = conf->trie.nh_sz;
+ num_tbl8 = conf->trie.num_tbl8;
+
+ snprintf(mem_name, sizeof(mem_name), "DP_%s", name);
+ dp = rte_zmalloc_socket(name, sizeof(struct rte_trie_tbl) +
+ TRIE_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
+ socket_id);
+ if (dp == NULL) {
+ rte_errno = ENOMEM;
+ return dp;
+ }
+
+ write_to_dp(&dp->tbl24, (def_nh << 1), nh_sz, 1 << 24);
+
+ snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp);
+ dp->tbl8 = rte_zmalloc_socket(mem_name, TRIE_TBL8_GRP_NUM_ENT *
+ (1ll << nh_sz) * (num_tbl8 + 1),
+ RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl8 == NULL) {
+ rte_errno = ENOMEM;
+ rte_free(dp);
+ return NULL;
+ }
+ dp->def_nh = def_nh;
+ dp->nh_sz = nh_sz;
+ dp->number_tbl8s = num_tbl8;
+
+ snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp);
+ dp->tbl8_pool = rte_zmalloc_socket(mem_name,
+ sizeof(uint32_t) * dp->number_tbl8s,
+ RTE_CACHE_LINE_SIZE, socket_id);
+ if (dp->tbl8_pool == NULL) {
+ rte_errno = ENOMEM;
+ rte_free(dp->tbl8);
+ rte_free(dp);
+ return NULL;
+ }
+
+ tbl8_pool_init(dp);
+
+ return dp;
+}
+
+void
+trie_free(void *p)
+{
+ struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p;
+
+ rte_free(dp->tbl8_pool);
+ rte_free(dp->tbl8);
+ rte_free(dp);
+}
diff --git a/src/spdk/dpdk/lib/librte_fib/trie.h b/src/spdk/dpdk/lib/librte_fib/trie.h
new file mode 100644
index 000000000..bb750c5ae
--- /dev/null
+++ b/src/spdk/dpdk/lib/librte_fib/trie.h
@@ -0,0 +1,36 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ * Copyright(c) 2019 Intel Corporation
+ */
+
+#ifndef _TRIE_H_
+#define _TRIE_H_
+
+/**
+ * @file
+ * RTE IPv6 Longest Prefix Match (LPM)
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+void *
+trie_create(const char *name, int socket_id, struct rte_fib6_conf *conf);
+
+void
+trie_free(void *p);
+
+rte_fib6_lookup_fn_t
+rte_trie_get_lookup_fn(struct rte_fib6_conf *fib_conf);
+
+int
+trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE],
+ uint8_t depth, uint64_t next_hop, int op);
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _TRIE_H_ */
generated by cgit v1.2.3 (git 2.39.1) at 2025-01-13 06:20:54 +0000