DPDK patches and discussions
 help / color / Atom feed
From: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
To: dev@dpdk.org
Cc: bruce.richardson@intel.com
Subject: [dpdk-dev] [PATCH v5 07/12] fib: add DIR24-8 dataplane algorithm
Date: Wed, 11 Sep 2019 18:09:47 +0100
Message-ID: <287966d228df112528c529e0db76f22bd2d64549.1568221364.git.vladimir.medvedkin@intel.com> (raw)
In-Reply-To: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com>

Add fib implementation for DIR24_8 algorithm for ipv4.
Implementation is similar to current LPM implementation but has
few enhancements:
faster control plabe operations
more bits for userdata in table entries
configurable userdata size

Signed-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>
---
 lib/librte_fib/Makefile    |   2 +-
 lib/librte_fib/dir24_8.c   | 737 +++++++++++++++++++++++++++++++++++++++++++++
 lib/librte_fib/dir24_8.h   |  36 +++
 lib/librte_fib/meson.build |   2 +-
 lib/librte_fib/rte_fib.c   |  14 +
 lib/librte_fib/rte_fib.h   |  17 +-
 6 files changed, 805 insertions(+), 3 deletions(-)
 create mode 100644 lib/librte_fib/dir24_8.c
 create mode 100644 lib/librte_fib/dir24_8.h

diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile
index 0bdf55b..67fde9a 100644
--- a/lib/librte_fib/Makefile
+++ b/lib/librte_fib/Makefile
@@ -17,7 +17,7 @@ EXPORT_MAP := rte_fib_version.map
 LIBABIVER := 1
 
 # all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c
 
 # install this header file
 SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h
diff --git a/lib/librte_fib/dir24_8.c b/lib/librte_fib/dir24_8.c
new file mode 100644
index 0000000..c9dce3c
--- /dev/null
+++ b/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/lib/librte_fib/dir24_8.h b/lib/librte_fib/dir24_8.h
new file mode 100644
index 0000000..34ddb91
--- /dev/null
+++ b/lib/librte_fib/dir24_8.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 _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/lib/librte_fib/meson.build b/lib/librte_fib/meson.build
index 32dfdec..c63cac8 100644
--- a/lib/librte_fib/meson.build
+++ b/lib/librte_fib/meson.build
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_fib.c', 'rte_fib6.c')
+sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c')
 headers = files('rte_fib.h', 'rte_fib6.h')
 deps += ['rib']
diff --git a/lib/librte_fib/rte_fib.c b/lib/librte_fib/rte_fib.c
index 4d8a771..e090808 100644
--- a/lib/librte_fib/rte_fib.c
+++ b/lib/librte_fib/rte_fib.c
@@ -17,6 +17,8 @@
 #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",
@@ -92,12 +94,22 @@ 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;
 	}
@@ -258,6 +270,8 @@ 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;
 	}
diff --git a/lib/librte_fib/rte_fib.h b/lib/librte_fib/rte_fib.h
index 096cc92..d06c5ef 100644
--- a/lib/librte_fib/rte_fib.h
+++ b/lib/librte_fib/rte_fib.h
@@ -15,6 +15,7 @@
 #include <rte_compat.h>
 
 struct rte_fib;
+struct rte_rib;
 
 /** Maximum depth value possible for IPv4 FIB. */
 #define RTE_FIB_MAXDEPTH	32
@@ -22,6 +23,7 @@ struct rte_fib;
 /** 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
 };
 
@@ -37,12 +39,26 @@ enum rte_fib_op {
 	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;
+	};
 };
 
 /**
@@ -143,7 +159,6 @@ __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
  *
-- 
2.7.4


  parent reply index

Thread overview: 61+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-04-26 22:03 [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library Medvedkin Vladimir
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 1/4] Add RIB library Medvedkin Vladimir
2018-04-26 22:17   ` Stephen Hemminger
2018-04-26 22:18   ` Stephen Hemminger
2018-04-26 22:19   ` Stephen Hemminger
2018-04-26 22:19   ` Stephen Hemminger
2018-04-26 22:20   ` Stephen Hemminger
2018-04-27  6:45     ` Vladimir Medvedkin
2018-06-29 13:54   ` Bruce Richardson
2018-06-29 14:02   ` Bruce Richardson
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 2/4] Add dir24_8 implementation for rib library Medvedkin Vladimir
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 3/4] Add autotests for RIB library Medvedkin Vladimir
2018-06-29 14:13   ` Bruce Richardson
2018-06-29 15:07   ` Bruce Richardson
2018-06-29 15:31   ` Bruce Richardson
2018-04-26 22:03 ` [dpdk-dev] [PATCH v4 4/4] Add support for lpm and rib bulk lookup Medvedkin Vladimir
2018-04-26 22:24 ` [dpdk-dev] [PATCH v4 0/4] lib/rib: Add Routing Information Base library Stephen Hemminger
2018-04-26 22:27   ` Thomas Monjalon
2018-04-26 22:42     ` Stephen Hemminger
2018-04-26 22:49     ` Stephen Hemminger
2018-04-27  8:27   ` Vladimir Medvedkin
2018-06-29 15:48 ` Bruce Richardson
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries Vladimir Medvedkin
2019-09-12  7:37   ` Morten Brørup
2019-09-12  9:47     ` Medvedkin, Vladimir
2019-09-12 12:00       ` Morten Brørup
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 " Vladimir Medvedkin
2019-11-05 23:14     ` Thomas Monjalon
2019-11-06  5:50       ` David Marchand
2019-11-06  7:50         ` Thomas Monjalon
2019-11-06 11:53           ` Medvedkin, Vladimir
2019-11-06 11:59             ` Thomas Monjalon
2019-11-06 14:37               ` Aaron Conole
2019-11-06 11:50         ` Medvedkin, Vladimir
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 01/12] rib: add RIB library Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 02/12] test/rib: add RIB library autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 03/12] rib: add ipv6 support for RIB Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 04/12] test/rib: add ipv6 support for RIB autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 05/12] fib: add FIB library Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 06/12] fib: add FIB ipv6 support Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 07/12] fib: add DIR24-8 dataplane algorithm Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 08/12] fib: add dataplane algorithm for ipv6 Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 09/12] test/fib: add FIB library autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 10/12] test/fib: add ipv6 support for FIB autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 11/12] test/fib: add FIB library performance autotests Vladimir Medvedkin
2019-11-01 15:21   ` [dpdk-dev] [PATCH v6 12/12] test/fib: add FIB library ipv6 " Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 01/12] rib: add RIB library Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 02/12] test/rib: add RIB library autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 03/12] rib: add ipv6 support for RIB Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 04/12] test/rib: add ipv6 support for RIB autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 05/12] fib: add FIB library Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 06/12] fib: add FIB ipv6 support Vladimir Medvedkin
2019-09-11 17:09 ` Vladimir Medvedkin [this message]
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 08/12] fib: add dataplane algorithm for ipv6 Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 09/12] test/fib: add FIB library autotests Vladimir Medvedkin
2019-09-12 14:07   ` Aaron Conole
2019-10-01 17:12     ` Medvedkin, Vladimir
2019-10-24 15:55       ` Thomas Monjalon
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 10/12] test/fib: add ipv6 support for FIB autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 11/12] test/fib: add FIB library performance autotests Vladimir Medvedkin
2019-09-11 17:09 ` [dpdk-dev] [PATCH v5 12/12] test/fib: add FIB library ipv6 " Vladimir Medvedkin

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=287966d228df112528c529e0db76f22bd2d64549.1568221364.git.vladimir.medvedkin@intel.com \
    --to=vladimir.medvedkin@intel.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

DPDK patches and discussions

Archives are clonable:
	git clone --mirror http://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ http://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev


Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/ public-inbox