Skip to contentSkip to conversation

lib/rib: Add Routing Information Base library

PATCH In review Medvedkin Vladimir 8 participants 61 messages Apr 26, 2018 – Nov 6, 2019

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

v4 cover lib/rib: Add Routing Information Base library

This patch series introduces new library librte_rib which potentially could replace librte_lpm.

RIB is an alternative to current LPM library.
It solves the following problems
- Increases the speed of control plane operations against lpm such as adding/deleting routes
- Adds abstraction from dataplane algorithms, so it is possible to add different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc in addition to current dir24_8
- It is possible to keep user defined application specific additional information in struct rte_rib_node which represents route entry. It can be next hop/set of next hops (i.e. active and feasible), pointers to link rte_rib_node based on some criteria (i.e. next_hop), plenty of additional control plane information.

v4:
fix various bugs
make struct rte_rib opaque
make inline functions instead of macro
remove RTE_RIB_MALLOC node allocation type
add new lookup functions
remove rte_dir24_8_lookup()
add rte_dir24_8_get_lookup()
add meson support
add fib configuration

Medvedkin Vladimir (4):
Add RIB library
Add dir24_8 implementation for rib library
Add autotests for RIB library
Add support for lpm and rib bulk lookup

 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 examples/l3fwd/l3fwd_lpm.c         | 132 +++++++
 examples/l3fwd/meson.build         |   2 +-
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  23 ++
 lib/librte_rib/meson.build         |   6 +
 lib/librte_rib/rte_dir24_8.c       | 725 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_dir24_8.h       |  47 +++
 lib/librte_rib/rte_rib.c           | 520 ++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 302 +++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 +
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 test/test/Makefile                 |   5 +
 test/test/meson.build              |   8 +
 test/test/test_rib.c               | 308 ++++++++++++++++
 test/test/test_rib_generate_rt.c   | 297 +++++++++++++++
 test/test/test_rib_generate_rt.h   |  38 ++
 test/test/test_rib_lpm_comp.c      | 189 ++++++++++
 test/test/test_rib_perf.c          | 145 ++++++++
 21 files changed, 2775 insertions(+), 2 deletions(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_dir24_8.c
 create mode 100644 lib/librte_rib/rte_dir24_8.h
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map
 create mode 100644 test/test/test_rib.c
 create mode 100644 test/test/test_rib_generate_rt.c
 create mode 100644 test/test/test_rib_generate_rt.h
 create mode 100644 test/test/test_rib_lpm_comp.c
 create mode 100644 test/test/test_rib_perf.c
Signature · 1 line
1.8.3.1
#1 lore raw

PATCH v4 1/4 Add RIB library

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  23 ++
 lib/librte_rib/meson.build         |   6 +
 lib/librte_rib/rte_rib.c           | 520 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 302 +++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 10 files changed, 880 insertions(+), 1 deletion(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map
config/common_base +6 -0
index 7e45412..833442c 100644
@@ -709,6 +709,12 @@ CONFIG_RTE_LIBRTE_LPM=y
 CONFIG_RTE_LIBRTE_LPM_DEBUG=n
 
 #
+# Compile librte_rib
+#
+CONFIG_RTE_LIBRTE_RIB=y
+CONFIG_RTE_LIBRTE_RIB_DEBUG=n
+
+#
 # Compile librte_acl
 #
 CONFIG_RTE_LIBRTE_ACL=y
doc/api/doxy-api.conf +1 -0
index ad8bdcf..8f42564 100644
@@ -60,6 +60,7 @@ INPUT                   = doc/api/doxy-api-index.md \
                           lib/librte_kvargs \
                           lib/librte_latencystats \
                           lib/librte_lpm \
+                          lib/librte_rib \
                           lib/librte_mbuf \
                           lib/librte_member \
                           lib/librte_mempool \
lib/Makefile +2 -0
index 965be6c..cb1d4e0 100644
@@ -43,6 +43,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
 DEPDIRS-librte_lpm := librte_eal
+DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib
+DEPDIRS-librte_rib := librte_eal librte_mempool
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
 DEPDIRS-librte_acl := librte_eal
 DIRS-$(CONFIG_RTE_LIBRTE_MEMBER) += librte_member
lib/librte_rib/Makefile new file +23 -0
new file mode 100644
index 0000000..f6431b6
@@ -0,0 +1,23 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_rib.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_rib_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c rte_dir24_8.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h rte_dir24_8.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_rib/meson.build new file +6 -0
new file mode 100644
index 0000000..0f4b865
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2017 Intel Corporation
+
+sources = files('rte_rib.c', 'rte_dir24_8.c')
+headers = files('rte_rib.h', 'rte_dir24_8.h')
+deps += ['mempool']
lib/librte_rib/rte_rib.c new file +520 -0

520 lines not on this page · raw message

lib/librte_rib/rte_rib.h new file +302 -0

302 lines not on this page · raw message

lib/librte_rib/rte_rib_version.map new file +18 -0
new file mode 100644
index 0000000..b193d6c
@@ -0,0 +1,18 @@
+DPDK_17.08 {
+	global:
+
+	rte_rib_create;
+	rte_rib_free;
+	rte_rib_tree_lookup;
+	rte_rib_tree_lookup_parent;
+	rte_rib_tree_lookup_exact;
+	rte_rib_tree_get_nxt;
+	rte_rib_tree_remove;
+	rte_rib_tree_insert;
+	rte_rib_find_existing;
+	rte_rib_add;
+	rte_rib_delete;
+	rte_rib_delete_all;
+
+	local: *;
+};
lib/meson.build +1 -1
index 73d6f25..6d06304 100644
@@ -20,7 +20,7 @@ libraries = [ 'compat', # just a header, used for versioning
 	'gro', 'gso', 'ip_frag', 'jobstats',
 	'kni', 'latencystats', 'lpm', 'member',
 	'meter', 'power', 'pdump', 'rawdev',
-	'reorder', 'sched', 'security', 'vhost',
+	'reorder', 'rib', 'sched', 'security', 'vhost',
 	# add pkt framework libs which use other libs from above
 	'port', 'table', 'pipeline',
 	# flow_classify lib depends on pkt framework table lib
mk/rte.app.mk +1 -0
index a145791..b7c5cce 100644
@@ -70,6 +70,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_GRO)            += -lrte_gro
 _LDLIBS-$(CONFIG_RTE_LIBRTE_GSO)            += -lrte_gso
 _LDLIBS-$(CONFIG_RTE_LIBRTE_METER)          += -lrte_meter
 _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM)            += -lrte_lpm
+_LDLIBS-$(CONFIG_RTE_LIBRTE_RIB)            += -lrte_rib
 # librte_acl needs --whole-archive because of weak functions
 _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL)            += --whole-archive
 _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL)            += -lrte_acl
Signature · 1 line
1.8.3.1
#2 lore raw

Re: [PATCH v4 1/4] Add RIB library

lib/librte_rib/rte_rib.c line 55

Quoted 6 lines · On Fri, 27 Apr 2018 01:03:31 +0300 Medvedkin Vladimir <[email protected]>…
lib/librte_rib/rte_rib.c new file +6 -0
+static inline int __attribute__((pure))
+rte_rib_is_right_node(struct rte_rib_node *node)
+{
+	return (node->parent->right == node);
+}
+

Minor nit (repeated in several places).
DPDK uses Linux (not BSD) style where extra paranthesis are not needed on return statement.

#3 lore raw

Re: [PATCH v4 1/4] Add RIB library

In reply to Medvedkin Vladimir

lib/librte_rib/rte_rib.c line 65

Quoted 10 lines · On Fri, 27 Apr 2018 01:03:31 +0300 Medvedkin Vladimir <[email protected]>…
lib/librte_rib/rte_rib.c new file +10 -0
+/**
+ * Check if prefix1 {key1/depth1}
+ * is covered by prefix2 {key2/depth2}
+ */
+static inline int __attribute__((pure))
+rte_rib_is_covered(uint32_t key1, uint8_t depth1, uint32_t key2, uint8_t depth2)
+{
+	return ((((key1 ^ key2) & rte_rib_depth_to_mask(depth2)) == 0)
+		&& (depth1 > depth2));
+}

Use standard boolean type (bool) for these kind of functions.

Plus you really don't need the pure attribute for static (or inline) functions since compiler determines that itself.

#5 lore raw

Re: [PATCH v4 1/4] Add RIB library

In reply to Medvedkin Vladimir

lib/librte_rib/rte_rib.c line 377

Quoted 2 lines · On Fri, 27 Apr 2018 01:03:31 +0300 Medvedkin Vladimir <[email protected]>…

rib = (struct rte_rib *)rte_zmalloc_socket(mem_name,

lib/librte_rib/rte_rib.c new file +1 -0
+		sizeof(struct rte_rib),	RTE_CACHE_LINE_SIZE, socket_id);

Cast of void * pointer is not required in C.

#6 lore raw

Re: [PATCH v4 1/4] Add RIB library

In reply to Medvedkin Vladimir

lib/librte_rib/rte_rib.c line 264

Quoted 7 lines · On Fri, 27 Apr 2018 01:03:31 +0300 Medvedkin Vladimir <[email protected]>…
lib/librte_rib/rte_rib.c new file +7 -0
+		/**
+		 * Intermediate node found.
+		 * Previous rte_rib_tree_lookup_exact() returned NULL
+		 * but node with proper search criteria is found.
+		 * Validate intermediate node and return.
+		 */
+		if ((key == (*tmp)->key) && (depth == (*tmp)->depth)) {

Comments with /** are intended to be docbook comments. This is not a docbook comment for a function.

#7 lore raw

Re: [PATCH v4 1/4] Add RIB library

Hi Stephen,

Thanks for comments! Will fix in next version.

2018-04-27 1:20 GMT+03:00 Stephen Hemminger <[email protected]>:

Quoted 14 lines

lib/librte_rib/rte_rib.c line 264

Quoted 7 lines · On Fri, 27 Apr 2018 01:03:31 +0300 Medvedkin Vladimir <[email protected]>…
lib/librte_rib/rte_rib.c new file +7 -0
+             /**
+              * Intermediate node found.
+              * Previous rte_rib_tree_lookup_exact() returned NULL
+              * but node with proper search criteria is found.
+              * Validate intermediate node and return.
+              */
+             if ((key == (*tmp)->key) && (depth == (*tmp)->depth)) {

Comments with /** are intended to be docbook comments. This is not a docbook comment for a function.

Signature · 2 lines
Regards,
Vladimir
#8 lore raw

Re: [PATCH v4 1/4] Add RIB library

In reply to Medvedkin Vladimir
Quoted 19 lines · Medvedkin Vladimir
---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  23 ++
 lib/librte_rib/meson.build         |   6 +
 lib/librte_rib/rte_rib.c           | 520 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 302 +++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 10 files changed, 880 insertions(+), 1 deletion(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map

<snip>

lib/librte_rib/meson.build line 6

Quoted 9 lines
lib/librte_rib/meson.build new file +6 -0
@@ -0,0 +1,6 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2017 Intel Corporation
+
+sources = files('rte_rib.c', 'rte_dir24_8.c')
+headers = files('rte_rib.h', 'rte_dir24_8.h')
+deps += ['mempool']

The dir24_8 files don't exist yet - to avoid breaking the build they should be added in a subsequent patch.

/Bruce

#9 lore raw

Re: [PATCH v4 1/4] Add RIB library

In reply to Medvedkin Vladimir
Quoted 19 lines · Medvedkin Vladimir
---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  23 ++
 lib/librte_rib/meson.build         |   6 +
 lib/librte_rib/rte_rib.c           | 520 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 302 +++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 10 files changed, 880 insertions(+), 1 deletion(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map

<snip>

lib/librte_rib/rte_rib.c line 514

Quoted 8 lines
lib/librte_rib/rte_rib.c new file +8 -0
+}
+
+int
+rte_rib_fib_lookup_bulk(struct rte_rib *rib, uint32_t *ips,
+	uint64_t *next_hops, int n)
+{
+	return rib->lookup(rib->fib, ips, next_hops, n);
+}

This function is missing from the map file, causing shared library build failures [seen with meson when linking the unit tests after applying patch 3]

/Bruce

#10 lore raw

PATCH v4 2/4 Add dir24_8 implementation for rib library

In reply to Medvedkin Vladimir

- Fast table modifcations (add/del routes)
- Variable length next hops (1/2/4/8 bytes)
- Removed RTE_LPM_LOOKUP_SUCCESS to save 1 bit and to eleminate ternary operator. Instead it returns special default value if there is no route.

---
 lib/librte_rib/rte_dir24_8.c | 725 +++++++++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_dir24_8.h |  47 +++
 2 files changed, 772 insertions(+)
 create mode 100644 lib/librte_rib/rte_dir24_8.c
 create mode 100644 lib/librte_rib/rte_dir24_8.h
lib/librte_rib/rte_dir24_8.c new file +725 -0
new file mode 100644
index 0000000..b89b1dc
@@ -0,0 +1,725 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#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_rib.h>
+#include <rte_dir24_8.h>
+
+#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 rte_dir24_8_tbl {
+	uint32_t	number_tbl8s;	/**< Total number of tbl8s */
+	uint32_t	cur_tbl8s;	/**< Current cumber of tbl8s */
+	uint64_t	def_nh;		/**< Default next hop */
+	enum rte_dir24_8_nh_sz	nh_sz;	/**< Size of nexthop entry */
+	uint64_t	*tbl8;		/**< LPM tbl8 table. */
+	uint64_t	*tbl8_idxes;	/**< bitmap containing free tbl8 idxes*/
+	uint64_t	tbl24[0] __rte_cache_aligned;	/**< LPM tbl24 table. */
+};
+
+#define ROUNDUP(x, y)	 RTE_ALIGN_CEIL(x, (1 << (32 - y)))
+
+enum lookup_type {
+	MACRO,
+	INLINE,
+	UNI
+};
+enum lookup_type test_lookup = MACRO;
+
+static __rte_always_inline __attribute__((pure)) void *
+get_tbl24_p(struct rte_dir24_8_tbl *fib, uint32_t ip, uint8_t nh_sz)
+{
+	return (void *)&((uint8_t *)fib->tbl24)[(ip &
+		RTE_DIR24_8_TBL24_MASK) >> (8 - nh_sz)];
+}
+
+static __rte_always_inline __attribute__((pure)) uint8_t
+bits_in_nh(uint8_t nh_sz)
+{
+	return 8 * (1 << nh_sz);
+}
+
+static  __rte_always_inline __attribute__((pure)) uint64_t
+get_max_nh(uint8_t nh_sz)
+{
+	return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1);
+}
+
+static  __rte_always_inline __attribute__((pure)) uint32_t
+get_tbl24_idx(uint32_t ip)
+{
+	return ip >> 8;
+}
+
+static  __rte_always_inline __attribute__((pure)) uint32_t
+get_tbl8_idx(uint32_t res, uint32_t ip)
+{
+	return (res >> 1) * RTE_DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip;
+}
+
+static __rte_always_inline __attribute__((pure)) uint64_t
+lookup_msk(uint8_t nh_sz)
+{
+	return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1;
+}
+
+static __rte_always_inline __attribute__((pure)) uint8_t
+get_psd_idx(uint32_t val, uint8_t nh_sz)
+{
+	return val & ((1 << (3 - nh_sz)) - 1);
+}
+
+static  __rte_always_inline __attribute__((pure)) uint32_t
+get_tbl_idx(uint32_t val, uint8_t nh_sz)
+{
+	return val >> (3 - nh_sz);
+}
+
+static  __rte_always_inline __attribute__((pure)) uint64_t
+get_tbl24(struct rte_dir24_8_tbl *fib, uint32_t ip, uint8_t nh_sz)
+{
+	return ((fib->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  __rte_always_inline __attribute__((pure)) uint64_t
+get_tbl8(struct rte_dir24_8_tbl *fib, uint32_t res, uint32_t ip, uint8_t nh_sz)
+{
+	return ((fib->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));
+}
+
+#define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz)			\
+static int rte_dir24_8_lookup_bulk_##suffix(void *fib_p, const uint32_t *ips, \
+	uint64_t *next_hops, const unsigned int n)			\
+{									\
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;	\
+	uint64_t tmp;							\
+	uint32_t i;							\
+	uint32_t prefetch_offset =					\
+		RTE_MIN((unsigned int)bulk_prefetch, n);		\
+									\
+	RTE_RIB_RETURN_IF_TRUE(((fib == NULL) || (ips == NULL) ||	\
+		(next_hops == NULL)), -EINVAL);				\
+									\
+	for (i = 0; i < prefetch_offset; i++)				\
+		rte_prefetch0(get_tbl24_p(fib, ips[i], nh_sz));		\
+	for (i = 0; i < (n - prefetch_offset); i++) {			\
+		rte_prefetch0(get_tbl24_p(fib,				\
+			ips[i + prefetch_offset], nh_sz));		\
+		tmp = ((type *)fib->tbl24)[ips[i] >> 8];		\
+		if (unlikely((tmp & RTE_DIR24_8_VALID_EXT_ENT) ==	\
+				RTE_DIR24_8_VALID_EXT_ENT)) {		\
+			tmp = ((type *)fib->tbl8)[(uint8_t)ips[i] +	\
+				((tmp >> 1) * RTE_DIR24_8_TBL8_GRP_NUM_ENT)]; \
+		}							\
+		next_hops[i] = tmp >> 1;				\
+	}								\
+	for (; i < n; i++) {						\
+		tmp = ((type *)fib->tbl24)[ips[i] >> 8];		\
+		if (unlikely((tmp & RTE_DIR24_8_VALID_EXT_ENT) ==	\
+				RTE_DIR24_8_VALID_EXT_ENT)) {		\
+			tmp = ((type *)fib->tbl8)[(uint8_t)ips[i] +	\
+				((tmp >> 1) * RTE_DIR24_8_TBL8_GRP_NUM_ENT)]; \
+		}							\
+		next_hops[i] = tmp >> 1;				\
+	}								\
+	return 0;							\
+}									\
+
+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 int
+rte_dir24_8_lookup_bulk(struct rte_dir24_8_tbl *fib, 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);
+
+	RTE_RIB_RETURN_IF_TRUE(((fib == NULL) || (ips == NULL) ||
+		(next_hops == NULL)), -EINVAL);
+
+	for (i = 0; i < prefetch_offset; i++)
+		rte_prefetch0(get_tbl24_p(fib, ips[i], nh_sz));
+	for (i = 0; i < (n - prefetch_offset); i++) {
+		rte_prefetch0(get_tbl24_p(fib, ips[i + prefetch_offset],
+			nh_sz));
+		tmp = get_tbl24(fib, ips[i], nh_sz);
+		if (unlikely((tmp & RTE_DIR24_8_VALID_EXT_ENT) ==
+				RTE_DIR24_8_VALID_EXT_ENT)) {
+			tmp = get_tbl8(fib, tmp, ips[i], nh_sz);
+		}
+		next_hops[i] = tmp >> 1;
+	}
+	for (; i < n; i++) {
+		tmp = get_tbl24(fib, ips[i], nh_sz);
+		if (unlikely((tmp & RTE_DIR24_8_VALID_EXT_ENT) ==
+				RTE_DIR24_8_VALID_EXT_ENT)) {
+			tmp = get_tbl8(fib, tmp, ips[i], nh_sz);
+		}
+		next_hops[i] = tmp >> 1;
+	}
+	return 0;
+}
+
+static int
+rte_dir24_8_lookup_bulk_0(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned int n)
+{
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+	return rte_dir24_8_lookup_bulk(fib, ips, next_hops, n, 0);
+}
+
+static int
+rte_dir24_8_lookup_bulk_1(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned int n)
+{
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+	return rte_dir24_8_lookup_bulk(fib, ips, next_hops, n, 1);
+}
+
+static int
+rte_dir24_8_lookup_bulk_2(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned int n)
+{
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+	return rte_dir24_8_lookup_bulk(fib, ips, next_hops, n, 2);
+}
+
+static int
+rte_dir24_8_lookup_bulk_3(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned int n)
+{
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+	return rte_dir24_8_lookup_bulk(fib, ips, next_hops, n, 3);
+}
+
+static int
+rte_dir24_8_lookup_bulk_uni(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned int n)
+{
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+	uint64_t tmp;
+	uint32_t i;
+	uint32_t prefetch_offset = RTE_MIN(15U, n);
+	uint8_t nh_sz = fib->nh_sz
+
+	RTE_RIB_RETURN_IF_TRUE(((fib == NULL) || (ips == NULL) ||
+		(next_hops == NULL)), -EINVAL);
+
+	for (i = 0; i < prefetch_offset; i++)
+		rte_prefetch0(get_tbl24_p(fib, ips[i], nh_sz));
+	for (i = 0; i < (n - prefetch_offset); i++) {
+		rte_prefetch0(get_tbl24_p(fib, ips[i + prefetch_offset],
+			nh_sz));
+		tmp = get_tbl24(fib, ips[i], nh_sz);
+		if (unlikely((tmp & RTE_DIR24_8_VALID_EXT_ENT) ==
+				RTE_DIR24_8_VALID_EXT_ENT)) {
+			tmp = get_tbl8(fib, tmp, ips[i], nh_sz);
+		}
+		next_hops[i] = tmp >> 1;
+	}
+	for (; i < n; i++) {
+		tmp = get_tbl24(fib, ips[i], nh_sz);
+		if (unlikely((tmp & RTE_DIR24_8_VALID_EXT_ENT) ==
+				RTE_DIR24_8_VALID_EXT_ENT)) {
+			tmp = get_tbl8(fib, tmp, ips[i], nh_sz);
+		}
+		next_hops[i] = tmp >> 1;
+	}
+	return 0;
+}
+
+rte_rib_lookup_fn_t
+rte_dir24_8_get_lookup_fn(struct rte_rib_conf *rib_conf)
+{
+	enum rte_dir24_8_nh_sz nh_sz = rib_conf->fib_conf.dir24_8.nh_sz;
+
+	if (test_lookup == MACRO) {
+		switch (nh_sz) {
+		case(RTE_DIR24_8_1B):
+			return rte_dir24_8_lookup_bulk_1b;
+		case(RTE_DIR24_8_2B):
+			return rte_dir24_8_lookup_bulk_2b;
+		case(RTE_DIR24_8_4B):
+			return rte_dir24_8_lookup_bulk_4b;
+		case(RTE_DIR24_8_8B):
+			return rte_dir24_8_lookup_bulk_8b;
+		}
+	} else if (test_lookup == INLINE) {
+		switch (nh_sz) {
+		case(RTE_DIR24_8_1B):
+			return rte_dir24_8_lookup_bulk_0;
+		case(RTE_DIR24_8_2B):
+			return rte_dir24_8_lookup_bulk_1;
+		case(RTE_DIR24_8_4B):
+			return rte_dir24_8_lookup_bulk_2;
+		case(RTE_DIR24_8_8B):
+			return rte_dir24_8_lookup_bulk_3;
+		}
+	} else
+		return rte_dir24_8_lookup_bulk_uni;
+	return NULL;
+}
+
+static void
+write_to_fib(void *ptr, uint64_t val, enum rte_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_DIR24_8_1B:
+		for (i = 0; i < n; i++)
+			ptr8[i] = (uint8_t)val;
+		break;
+	case RTE_DIR24_8_2B:
+		for (i = 0; i < n; i++)
+			ptr16[i] = (uint16_t)val;
+		break;
+	case RTE_DIR24_8_4B:
+		for (i = 0; i < n; i++)
+			ptr32[i] = (uint32_t)val;
+		break;
+	case RTE_DIR24_8_8B:
+		for (i = 0; i < n; i++)
+			ptr64[i] = (uint64_t)val;
+		break;
+	}
+}
+
+static int
+tbl8_get_idx(struct rte_dir24_8_tbl *fib)
+{
+	uint32_t i;
+	int bit_idx;
+
+	for (i = 0; (i <= (fib->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) &&
+			(fib->tbl8_idxes[i] == UINT64_MAX); i++)
+		;
+	if (i <= (fib->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) {
+		bit_idx = __builtin_ctzll(~fib->tbl8_idxes[i]);
+		fib->tbl8_idxes[i] |= (1ULL << bit_idx);
+		return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx;
+	}
+	return -ENOSPC;
+}
+
+static inline void
+tbl8_free_idx(struct rte_dir24_8_tbl *fib, int idx)
+{
+	fib->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &=
+		~(1ULL << (idx & BITMAP_SLAB_BITMASK));
+}
+
+static int
+tbl8_alloc(struct rte_dir24_8_tbl *fib, uint64_t nh)
+{
+	int	tbl8_idx;
+	uint8_t	*tbl8_ptr;
+
+	tbl8_idx = tbl8_get_idx(fib);
+	if (tbl8_idx < 0)
+		return tbl8_idx;
+	tbl8_ptr = (uint8_t *)fib->tbl8 +
+		((tbl8_idx * RTE_DIR24_8_TBL8_GRP_NUM_ENT) <<
+		fib->nh_sz);
+	/*Init tbl8 entries with nexthop from tbl24*/
+	write_to_fib((void *)tbl8_ptr, nh|
+		RTE_DIR24_8_VALID_EXT_ENT, fib->nh_sz,
+		RTE_DIR24_8_TBL8_GRP_NUM_ENT);
+	return tbl8_idx;
+}
+
+static void
+tbl8_recycle(struct rte_dir24_8_tbl *fib, uint32_t ip, uint64_t tbl8_idx)
+{
+	int i;
+	uint64_t nh;
+	uint8_t *ptr8;
+	uint16_t *ptr16;
+	uint32_t *ptr32;
+	uint64_t *ptr64;
+
+	switch (fib->nh_sz) {
+	case RTE_DIR24_8_1B:
+		ptr8 = &((uint8_t *)fib->tbl8)[tbl8_idx *
+				RTE_DIR24_8_TBL8_GRP_NUM_ENT];
+		nh = *ptr8;
+		for (i = 1; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+			if (nh != ptr8[i])
+				return;
+		}
+		((uint8_t *)fib->tbl24)[ip >> 8] =
+			nh & ~RTE_DIR24_8_VALID_EXT_ENT;
+		for (i = 0; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++)
+			ptr8[i] = 0;
+		break;
+	case RTE_DIR24_8_2B:
+		ptr16 = &((uint16_t *)fib->tbl8)[tbl8_idx *
+				RTE_DIR24_8_TBL8_GRP_NUM_ENT];
+		nh = *ptr16;
+		for (i = 1; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+			if (nh != ptr16[i])
+				return;
+		}
+		((uint16_t *)fib->tbl24)[ip >> 8] =
+			nh & ~RTE_DIR24_8_VALID_EXT_ENT;
+		for (i = 0; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++)
+			ptr16[i] = 0;
+		break;
+	case RTE_DIR24_8_4B:
+		ptr32 = &((uint32_t *)fib->tbl8)[tbl8_idx *
+				RTE_DIR24_8_TBL8_GRP_NUM_ENT];
+		nh = *ptr32;
+		for (i = 1; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+			if (nh != ptr32[i])
+				return;
+		}
+		((uint32_t *)fib->tbl24)[ip >> 8] =
+			nh & ~RTE_DIR24_8_VALID_EXT_ENT;
+		for (i = 0; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++)
+			ptr32[i] = 0;
+		break;
+	case RTE_DIR24_8_8B:
+		ptr64 = &((uint64_t *)fib->tbl8)[tbl8_idx *
+				RTE_DIR24_8_TBL8_GRP_NUM_ENT];
+		nh = *ptr64;
+		for (i = 1; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++) {
+			if (nh != ptr64[i])
+				return;
+		}
+		((uint64_t *)fib->tbl24)[ip >> 8] =
+			nh & ~RTE_DIR24_8_VALID_EXT_ENT;
+		for (i = 0; i < RTE_DIR24_8_TBL8_GRP_NUM_ENT; i++)
+			ptr64[i] = 0;
+		break;
+	}
+	tbl8_free_idx(fib, tbl8_idx);
+}
+
+static int
+install_to_fib(struct rte_dir24_8_tbl *fib, 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 = (unlikely((ledge == 0) && (redge == 0))) ? 1 << 24 :
+		((redge & RTE_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(fib, ledge, fib->nh_sz);
+			if ((tbl24_tmp & RTE_DIR24_8_VALID_EXT_ENT) !=
+					RTE_DIR24_8_VALID_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(fib, tbl24_tmp);
+				tmp_tbl8_idx = tbl8_get_idx(fib);
+				if (tbl8_idx < 0)
+					return -ENOSPC;
+				else if (tmp_tbl8_idx < 0) {
+					tbl8_free_idx(fib, tbl8_idx);
+					return -ENOSPC;
+				}
+				tbl8_free_idx(fib, tmp_tbl8_idx);
+				/*update dir24 entry with tbl8 index*/
+				write_to_fib(get_tbl24_p(fib, ledge,
+					fib->nh_sz), (tbl8_idx << 1)|
+					RTE_DIR24_8_VALID_EXT_ENT,
+					fib->nh_sz, 1);
+			} else
+				tbl8_idx = tbl24_tmp >> 1;
+			tbl8_ptr = (uint8_t *)fib->tbl8 +
+				(((tbl8_idx * RTE_DIR24_8_TBL8_GRP_NUM_ENT) +
+				(ledge & ~RTE_DIR24_8_TBL24_MASK)) <<
+				fib->nh_sz);
+			/*update tbl8 with new next hop*/
+			write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
+				RTE_DIR24_8_VALID_EXT_ENT,
+				fib->nh_sz, ROUNDUP(ledge, 24) - ledge);
+			tbl8_recycle(fib, ledge, tbl8_idx);
+		}
+		write_to_fib(get_tbl24_p(fib, ROUNDUP(ledge, 24), fib->nh_sz),
+			next_hop << 1, fib->nh_sz, len);
+		if (redge & ~RTE_DIR24_8_TBL24_MASK) {
+			tbl24_tmp = get_tbl24(fib, redge, fib->nh_sz);
+			if ((tbl24_tmp & RTE_DIR24_8_VALID_EXT_ENT) !=
+					RTE_DIR24_8_VALID_EXT_ENT) {
+				tbl8_idx = tbl8_alloc(fib, tbl24_tmp);
+				if (tbl8_idx < 0)
+					return -ENOSPC;
+				/*update dir24 entry with tbl8 index*/
+				write_to_fib(get_tbl24_p(fib, redge,
+					fib->nh_sz), (tbl8_idx << 1)|
+					RTE_DIR24_8_VALID_EXT_ENT,
+					fib->nh_sz, 1);
+			} else
+				tbl8_idx = tbl24_tmp >> 1;
+			tbl8_ptr = (uint8_t *)fib->tbl8 +
+				((tbl8_idx * RTE_DIR24_8_TBL8_GRP_NUM_ENT) <<
+				fib->nh_sz);
+			/*update tbl8 with new next hop*/
+			write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
+				RTE_DIR24_8_VALID_EXT_ENT,
+				fib->nh_sz, redge & ~RTE_DIR24_8_TBL24_MASK);
+			tbl8_recycle(fib, redge, tbl8_idx);
+		}
+	} else if ((redge - ledge) != 0) {
+		tbl24_tmp = get_tbl24(fib, ledge, fib->nh_sz);
+		if ((tbl24_tmp & RTE_DIR24_8_VALID_EXT_ENT) !=
+				RTE_DIR24_8_VALID_EXT_ENT) {
+			tbl8_idx = tbl8_alloc(fib, tbl24_tmp);
+			if (tbl8_idx < 0)
+				return -ENOSPC;
+			/*update dir24 entry with tbl8 index*/
+			write_to_fib(get_tbl24_p(fib, ledge, fib->nh_sz),
+				(tbl8_idx << 1)|
+				RTE_DIR24_8_VALID_EXT_ENT,
+				fib->nh_sz, 1);
+		} else
+			tbl8_idx = tbl24_tmp >> 1;
+		tbl8_ptr = (uint8_t *)fib->tbl8 +
+			(((tbl8_idx * RTE_DIR24_8_TBL8_GRP_NUM_ENT) +
+			(ledge & ~RTE_DIR24_8_TBL24_MASK)) <<
+			fib->nh_sz);
+		/*update tbl8 with new next hop*/
+		write_to_fib((void *)tbl8_ptr, (next_hop << 1)|
+			RTE_DIR24_8_VALID_EXT_ENT,
+			fib->nh_sz, redge - ledge);
+		tbl8_recycle(fib, ledge, tbl8_idx);
+	}
+	return 0;
+}
+
+static int
+modify_fib(struct rte_rib *rib, uint32_t ip, uint8_t depth,
+	uint64_t next_hop)
+{
+	struct rte_rib_node *tmp = NULL;
+	struct rte_dir24_8_tbl *fib;
+	uint32_t ledge, redge;
+	int ret;
+
+	fib = rte_rib_get_fibp(rib);
+
+	if (next_hop > get_max_nh(fib->nh_sz))
+		return -EINVAL;
+
+	ip &= rte_rib_depth_to_mask(depth);
+	ledge = ip;
+	do {
+		tmp = rte_rib_tree_get_nxt(rib, ip, depth, tmp,
+			RTE_RIB_GET_NXT_COVER);
+		if (tmp != NULL) {
+			if (tmp->depth == depth)
+				continue;
+			redge = tmp->key & rte_rib_depth_to_mask(tmp->depth);
+			if (ledge == redge) {
+				ledge = redge +
+					(uint32_t)(1ULL << (32 - tmp->depth));
+				continue;
+			}
+			ret = install_to_fib(fib, 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));
+			ret = install_to_fib(fib, ledge, redge,
+				next_hop);
+			if (ret != 0)
+				return ret;
+		}
+	} while (tmp);
+
+	return 0;
+}
+
+int
+rte_dir24_8_modify(struct rte_rib *rib, uint32_t ip, uint8_t depth,
+	uint64_t next_hop, enum rte_rib_op op)
+{
+	struct rte_dir24_8_tbl *fib;
+	struct rte_rib_node *tmp = NULL;
+	struct rte_rib_node *node;
+	struct rte_rib_node *parent;
+	int ret = 0;
+
+	if ((rib == NULL) || (depth > RTE_RIB_MAXDEPTH))
+		return -EINVAL;
+
+	fib = rte_rib_get_fibp(rib);
+	RTE_ASSERT(fib);
+
+	ip &= rte_rib_depth_to_mask(depth);
+
+	node = rte_rib_tree_lookup_exact(rib, ip, depth);
+	switch (op) {
+	case RTE_RIB_ADD:
+		if (node != NULL) {
+			if (node->nh == next_hop)
+				return 0;
+			ret = modify_fib(rib, ip, depth, next_hop);
+			if (ret == 0)
+				node->nh = next_hop;
+			return 0;
+		}
+		if (depth > 24) {
+			tmp = rte_rib_tree_get_nxt(rib, ip, 24, NULL,
+				RTE_RIB_GET_NXT_COVER);
+			if ((tmp == NULL) &&
+				(fib->cur_tbl8s >= fib->number_tbl8s))
+				return -ENOSPC;
+
+		}
+		node = rte_rib_tree_insert(rib, ip, depth);
+		if (node == NULL)
+			return -rte_errno;
+		node->nh = next_hop;
+		parent = rte_rib_tree_lookup_parent(node);
+		if ((parent != NULL) && (parent->nh == next_hop))
+			return 0;
+		ret = modify_fib(rib, ip, depth, next_hop);
+		if (ret != 0) {
+			rte_rib_tree_remove(rib, ip, depth);
+			return ret;
+		}
+		if ((depth > 24) && (tmp == NULL))
+			fib->cur_tbl8s++;
+		return 0;
+	case RTE_RIB_DEL:
+		if (node == NULL)
+			return -ENOENT;
+
+		parent = rte_rib_tree_lookup_parent(node);
+		if (parent != NULL) {
+			if (parent->nh != node->nh)
+				ret = modify_fib(rib, ip, depth, parent->nh);
+		} else
+			ret = modify_fib(rib, ip, depth, fib->def_nh);
+		if (ret == 0) {
+			rte_rib_tree_remove(rib, ip, depth);
+			if (depth > 24) {
+				tmp = rte_rib_tree_get_nxt(rib, ip, 24, NULL,
+					RTE_RIB_GET_NXT_COVER);
+				if (tmp == NULL)
+					fib->cur_tbl8s--;
+			}
+		}
+		return ret;
+	default:
+		break;
+	}
+	return -EINVAL;
+}
+
+struct rte_dir24_8_tbl *rte_dir24_8_create(const char *name, int socket_id,
+	struct rte_rib_conf *rib_conf)
+{
+	char mem_name[RTE_RIB_NAMESIZE];
+	struct rte_dir24_8_tbl *fib;
+	uint64_t	def_nh;
+	uint32_t	num_tbl8;
+	enum rte_dir24_8_nh_sz	nh_sz;
+
+	if ((name == NULL) || (socket_id < -1) || (rib_conf == NULL) ||
+			(rib_conf->fib_conf.dir24_8.nh_sz < RTE_DIR24_8_1B) ||
+			(rib_conf->fib_conf.dir24_8.nh_sz > RTE_DIR24_8_8B) ||
+			(rib_conf->fib_conf.dir24_8.num_tbl8 >
+			get_max_nh(rib_conf->fib_conf.dir24_8.nh_sz)) ||
+			(rib_conf->fib_conf.dir24_8.num_tbl8 == 0) ||
+			(rib_conf->fib_conf.dir24_8.def_nh >
+			get_max_nh(rib_conf->fib_conf.dir24_8.nh_sz))) {
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	def_nh = rib_conf->fib_conf.dir24_8.def_nh;
+	nh_sz = rib_conf->fib_conf.dir24_8.nh_sz;
+	num_tbl8 = rib_conf->fib_conf.dir24_8.num_tbl8;
+
+	snprintf(mem_name, sizeof(mem_name), "FIB_%s", name);
+	fib = rte_zmalloc_socket(name, sizeof(struct rte_dir24_8_tbl) +
+		RTE_DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE,
+		socket_id);
+	if (fib == NULL) {
+		rte_errno = ENOMEM;
+		return fib;
+	}
+
+	write_to_fib(&fib->tbl24, (def_nh << 1), nh_sz, 1 << 24);
+
+	snprintf(mem_name, sizeof(mem_name), "TBL8_%s", name);
+	fib->tbl8 = rte_zmalloc_socket(mem_name, RTE_DIR24_8_TBL8_GRP_NUM_ENT *
+			(1 << nh_sz) * (num_tbl8 + 1),
+			RTE_CACHE_LINE_SIZE, socket_id);
+	if (fib->tbl8 == NULL) {
+		rte_errno = ENOMEM;
+		rte_free(fib);
+		return NULL;
+	}
+	fib->def_nh = def_nh;
+	fib->nh_sz = nh_sz;
+	fib->number_tbl8s = num_tbl8;
+
+	snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%s", name);
+	fib->tbl8_idxes = rte_zmalloc_socket(mem_name,
+			RTE_ALIGN_CEIL(fib->number_tbl8s, 64) >> 3,
+			RTE_CACHE_LINE_SIZE, socket_id);
+	if (fib->tbl8_idxes == NULL) {
+		rte_errno = ENOMEM;
+		rte_free(fib->tbl8);
+		rte_free(fib);
+		return NULL;
+	}
+
+	return fib;
+}
+
+void
+rte_dir24_8_free(void *fib_p)
+{
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+	rte_free(fib->tbl8_idxes);
+	rte_free(fib->tbl8);
+	rte_free(fib);
+}
lib/librte_rib/rte_dir24_8.h new file +47 -0

47 lines not on this page · raw message

Signature · 1 line
1.8.3.1
#11 lore raw

PATCH v4 3/4 Add autotests for RIB library

In reply to Medvedkin Vladimir
---
 test/test/Makefile               |   5 +
 test/test/meson.build            |   8 +
 test/test/test_rib.c             | 308 +++++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.c | 297 +++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.h |  38 +++++
 test/test/test_rib_lpm_comp.c    | 189 ++++++++++++++++++++++++
 test/test/test_rib_perf.c        | 145 ++++++++++++++++++
 7 files changed, 990 insertions(+)
 create mode 100644 test/test/test_rib.c
 create mode 100644 test/test/test_rib_generate_rt.c
 create mode 100644 test/test/test_rib_generate_rt.h
 create mode 100644 test/test/test_rib_lpm_comp.c
 create mode 100644 test/test/test_rib_perf.c
test/test/Makefile +5 -0
index 2630ab4..b5f4fb3 100644
@@ -119,6 +119,11 @@ SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm6.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm6_perf.c
 
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
+SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_rib_generate_rt.c
+SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_rib_perf.c
+SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_rib_lpm_comp.c
+
 SRCS-y += test_debug.c
 SRCS-y += test_errno.c
 SRCS-y += test_tailq.c
test/test/meson.build +8 -0
index ad0a650..f9abc3d 100644
@@ -74,6 +74,10 @@ test_sources = files('commands.c',
 	'test_reciprocal_division_perf.c',
 	'test_red.c',
 	'test_reorder.c',
+	'test_rib.c',
+	'test_rib_generate_rt.c',
+	'test_rib_perf.c',
+	'test_rib_lpm_comp.c',
 	'test_ring.c',
 	'test_ring_perf.c',
 	'test_rwlock.c',
@@ -111,6 +115,7 @@ test_deps = ['acl',
 	'pipeline',
 	'port',
 	'reorder',
+	'rib',
 	'ring',
 	'timer'
 ]
@@ -192,6 +197,9 @@ test_names = [
 	'red_autotest',
 	'red_perf',
 	'reorder_autotest',
+	'rib_autotest',
+	'rib_perf_autotest',
+	'rib_lpm_comp_autotest',
 	'ring_autotest',
 	'ring_perf_autotest',
 	'ring_pmd_autotest',
test/test/test_rib.c new file +308 -0

308 lines not on this page · raw message

test/test/test_rib_generate_rt.c new file +297 -0

297 lines not on this page · raw message

test/test/test_rib_generate_rt.h new file +38 -0
new file mode 100644
index 0000000..90573c7
@@ -0,0 +1,38 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _TEST_RIB_GENERATE_RT_H_
+#define _TEST_RIB_GENERATE_RT_H_
+
+#define RTE_RIB_MAXDEPTH	32
+
+struct route_rule {
+	uint64_t nh;
+	uint32_t ip;
+	uint8_t depth;
+};
+
+enum {
+	IP_CLASS_A,
+	IP_CLASS_B,
+	IP_CLASS_C
+};
+
+/* struct route_rule_count defines the total number of rules in following a/b/c
+ * each item in a[]/b[]/c[] is the number of common IP address class A/B/C, not
+ * including the ones for private local network.
+ */
+struct route_rule_count {
+	uint32_t a[RTE_RIB_MAXDEPTH];
+	uint32_t b[RTE_RIB_MAXDEPTH];
+	uint32_t c[RTE_RIB_MAXDEPTH];
+};
+
+
+uint32_t generate_large_route_rule_table(uint32_t num_routes,
+	struct route_rule *rt);
+void print_route_distribution(const struct route_rule *table, uint32_t n);
+void shuffle_rt(struct route_rule *rt, uint32_t n);
+
+#endif /* _TEST_RIB_GENERATE_RT_H_ */
test/test/test_rib_lpm_comp.c new file +189 -0

189 lines not on this page · raw message

test/test/test_rib_perf.c new file +145 -0

145 lines not on this page · raw message

Signature · 1 line
1.8.3.1
#12 lore raw

Re: [PATCH v4 3/4] Add autotests for RIB library

Quoted 16 lines · Medvedkin Vladimir
---
 test/test/Makefile               |   5 +
 test/test/meson.build            |   8 +
 test/test/test_rib.c             | 308 +++++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.c | 297 +++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.h |  38 +++++
 test/test/test_rib_lpm_comp.c    | 189 ++++++++++++++++++++++++
 test/test/test_rib_perf.c        | 145 ++++++++++++++++++
 7 files changed, 990 insertions(+)
 create mode 100644 test/test/test_rib.c
 create mode 100644 test/test/test_rib_generate_rt.c
 create mode 100644 test/test/test_rib_generate_rt.h
 create mode 100644 test/test/test_rib_lpm_comp.c
 create mode 100644 test/test/test_rib_perf.c

Clang is giving some errors after this patch, nothing to serious, but they need to be fixed in the next version:

../test/test/test_rib_perf.c:87:12: error: equality comparison with extraneous parentheses [-Werror,-Wparentheses-equality]

                if ((ret == 0))
                     ~~~~^~~~
../test/test/test_rib_perf.c:87:12: note: remove extraneous parentheses around the comparison to silence this warning
                if ((ret == 0))
                    ~    ^   ~
../test/test/test_rib_perf.c:87:12: note: use '=' to turn this equality comparison into an assignment
                if ((ret == 0))
                         ^~
                         =

1 error generated.

#13 lore raw

Re: [PATCH v4 3/4] Add autotests for RIB library

In reply to Medvedkin Vladimir
Quoted 16 lines · Medvedkin Vladimir
---
 test/test/Makefile               |   5 +
 test/test/meson.build            |   8 +
 test/test/test_rib.c             | 308 +++++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.c | 297 +++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.h |  38 +++++
 test/test/test_rib_lpm_comp.c    | 189 ++++++++++++++++++++++++
 test/test/test_rib_perf.c        | 145 ++++++++++++++++++
 7 files changed, 990 insertions(+)
 create mode 100644 test/test/test_rib.c
 create mode 100644 test/test/test_rib_generate_rt.c
 create mode 100644 test/test/test_rib_generate_rt.h
 create mode 100644 test/test/test_rib_lpm_comp.c
 create mode 100644 test/test/test_rib_perf.c

<snip>

Quoted 32 lines
test/test/test_rib_lpm_comp.c new file +26 -0
new file mode 100644
index 0000000..ef48c8c
@@ -0,0 +1,189 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <rte_random.h>
+#include <rte_cycles.h>
+#include <rte_branch_prediction.h>
+#include <rte_ip.h>
+#include <rte_malloc.h>
+#include <rte_lpm.h>
+#include <rte_rib.h>
+
+#include "test.h"
+#include "test_xmmt_ops.h"
+#include "test_rib_generate_rt.h"
+
+#define TEST_RIB_ASSERT(cond) do {				\
+	if (!(cond)) {						\
+		printf("Error at line %d:\n", __LINE__);	\
+		return -1;					\
+	}							\
+} while (0)

test/test/test_rib_lpm_comp.c line 36

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+
+#define ITERATIONS (1 << 25)
+#define BATCH_SIZE (1 << 7)
+#define BULK_SIZE 32
+#define LPM_NH_MASK	((1 << 24) - 1)
+
+static uint64_t default_nh;
+
+static int
+test_lookup(struct rte_rib *rib, struct rte_lpm *lpm)

It should be fairly obvious, but put in a comment explaining the function and what it does, and how.

Quoted 19 lines
test/test/test_rib_lpm_comp.c new file +19 -0
+{
+	static uint32_t ip_batch[BATCH_SIZE];
+	uint64_t rib_next_hops[BULK_SIZE];
+	uint32_t lpm_next_hops[BULK_SIZE];
+	int i, j, k;
+
+	for (i = 0; i < ITERATIONS; i++) {
+		for (j = 0; j < BATCH_SIZE; j++)
+			ip_batch[j] = (i << 7) + j;
+
+		for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) {
+			rte_rib_fib_lookup_bulk(rib, &ip_batch[j],
+				rib_next_hops, BULK_SIZE);
+			rte_lpm_lookup_bulk(lpm, &ip_batch[j],
+				lpm_next_hops, BULK_SIZE);
+			for (k = 0; k < BULK_SIZE; k++) {
+				if (likely(lpm_next_hops[k] &
+					RTE_LPM_LOOKUP_SUCCESS))
+					lpm_next_hops[k] &= LPM_NH_MASK;

test/test/test_rib_lpm_comp.c line 65

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+				else
+					lpm_next_hops[k] = default_nh;
+			}
+			for (k = 0; k < BULK_SIZE; k++)
+				TEST_RIB_ASSERT(rib_next_hops[k] ==
+						lpm_next_hops[k]);
+		}
+	}
+	return 0;
+}

This looks a good unit test for comparisons. Although it's scanning linearly, I wonder if it may be worthwhile to rework the loops so you do all lookups for a batch for lpm first then for fib, and track the cycles for each. Then at the end you can print out the lookup perf comparison. Alternatively, an additional batch at the end with random lookups could be done. [Yes, I know the info can be got by running the perf tests for lpm and rib separately, but it would be nice to have it as part of a comparison autotest]

Quoted 15 lines
test/test/test_rib_lpm_comp.c new file +15 -0
+
+static int
+test_rib_lpm_comp(void)
+{
+	struct rte_rib *rib = NULL;
+	struct rte_lpm *lpm = NULL;
+	struct route_rule *rt = NULL;
+	unsigned int i;
+	int rib_add = 0, lpm_add = 0;
+	int ret, nh_bits, nr_tbl8;
+	uint32_t num_routes;
+	struct rte_rib_conf conf;
+	struct rte_lpm_config config;
+
+	rte_srand(rte_rdtsc());

test/test/test_rib_lpm_comp.c line 90

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+	default_nh = 17;
+
+	conf.max_nodes = 3000000;
+	conf.node_sz = sizeof(struct rte_rib_node);
+	conf.type = RTE_RIB_DIR24_8;
+	conf.fib_conf.dir24_8.def_nh = default_nh;
+	conf.fib_conf.dir24_8.nh_sz = RTE_DIR24_8_8B;
+
+	nh_bits = RTE_MIN(((1 << (3 + conf.fib_conf.dir24_8.nh_sz)) - 1), 24);
+	nr_tbl8 = RTE_MIN(((1 << nh_bits) - 1), 65535);

These two lines need a comment explaining them - especially the former one.

Quoted 18 lines
test/test/test_rib_lpm_comp.c new file +18 -0
+	config.number_tbl8s = nr_tbl8;
+	conf.fib_conf.dir24_8.num_tbl8 = nr_tbl8;
+	config.max_rules = 2000000;
+	config.flags = 0;
+
+	num_routes = 1200000;
+
+	rt = rte_zmalloc("struct route_rule *", sizeof(struct route_rule) *
+		num_routes + 5, 0);
+	TEST_RIB_ASSERT(rt != NULL);
+
+	num_routes = generate_large_route_rule_table(num_routes, rt);
+	TEST_RIB_ASSERT(num_routes != 0);
+	printf("No. routes = %u\n", (unsigned int) num_routes);
+
+	shuffle_rt(rt, num_routes);
+
+	print_route_distribution(rt, (uint32_t) num_routes);

test/test/test_rib_lpm_comp.c line 118

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+
+	rib = rte_rib_create(__func__, SOCKET_ID_ANY, &conf);
+	TEST_RIB_ASSERT(rib != NULL);
+
+	lpm = rte_lpm_create(__func__, SOCKET_ID_ANY, &config);
+	TEST_RIB_ASSERT(lpm != NULL);
+
+	for (i = 0; i < num_routes; i++)
+		rt[i].nh = rte_rand() & ((1ULL << nh_bits) - 1);
+

Put comment here explaining this next block.

Quoted 13 lines
test/test/test_rib_lpm_comp.c new file +13 -0
+	for (i = 0; i < num_routes; i++) {
+		ret = rte_rib_add(rib, rt[i].ip, rt[i].depth, rt[i].nh);
+		if (ret == 0)
+			rib_add++;
+		else
+			continue;
+
+		ret = rte_lpm_add(lpm, rt[i].ip, rt[i].depth, rt[i].nh);
+		if (ret == 0)
+			lpm_add++;
+		else {
+			rte_rib_delete(rib, rt[i].ip, rt[i].depth);
+			rib_add--;

test/test/test_rib_lpm_comp.c line 141

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+		}
+	}
+	TEST_RIB_ASSERT(rib_add == lpm_add);
+
+	ret = test_lookup(rib, lpm);
+	if (ret != 0)
+		return ret;
+
+	for (i = 0; i < num_routes; i++) {
+		if ((i % 3) == 0) {

I assume the intention here is after filling the table and doing the lookup tests, we drop 1/3 of the entries and retest. Put in a comment explaining the why.
Rather than putting in the if statement, why not just change the loop to be:

	for (i = 0; i < num_routes; i += 3)
Quoted 9 lines
test/test/test_rib_lpm_comp.c new file +9 -0
+			ret = rte_rib_delete(rib, rt[i].ip, rt[i].depth);
+			if (ret == 0)
+				rib_add--;
+			else
+				continue;
+
+			ret = rte_lpm_delete(lpm, rt[i].ip, rt[i].depth);
+			if (ret == 0)
+				lpm_add--;

test/test/test_rib_lpm_comp.c line 160

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+		}
+	}
+	TEST_RIB_ASSERT(rib_add == lpm_add);
+
+	ret = test_lookup(rib, lpm);
+	if (ret != 0)
+		return ret;
+
+	for (i = 0; i < num_routes; i++) {
+		if ((i % 6) == 0) {

As above, put in a comment, and consider removing the if statment. It helps having the reduced indentation.

Quoted 17 lines
test/test/test_rib_lpm_comp.c new file +17 -0
+			ret = rte_rib_add(rib, rt[i].ip, rt[i].depth, rt[i].nh);
+			if (ret == 0)
+				rib_add++;
+			else
+				continue;
+
+			ret = rte_lpm_add(lpm, rt[i].ip, rt[i].depth, rt[i].nh);
+			if (ret == 0)
+				lpm_add++;
+			else {
+				rte_rib_delete(rib, rt[i].ip, rt[i].depth);
+				rib_add--;
+			}
+		}
+	}
+	TEST_RIB_ASSERT(rib_add == lpm_add);
+

test/test/test_rib_lpm_comp.c line 187

Quoted 10 lines
test/test/test_rib_lpm_comp.c new file +10 -0
+	ret = test_lookup(rib, lpm);
+	if (ret != 0)
+		return ret;
+
+	rte_rib_free(rib);
+	rte_lpm_free(lpm);
+	rte_free(rt);
+
+	return 0;
+}

Looks a really good test. Only issue I have is that it sits for a long time doing the checks in the background without any output. I would therefore suggest:
* At end of each stage, add, lookup, delete, etc print out a message stating what was done with how many entries, e.g X adds, Y lookups etc.
* For any of those individual items that takes a long time on its own, consider printing out every e.g. 100,000 items, and/or printing a dot every 10,000 items, so the user can see progress.

Quoted 2 lines
test/test/test_rib_lpm_comp.c new file +2 -0
+
+REGISTER_TEST_COMMAND(rib_lpm_comp_autotest, test_rib_lpm_comp);

<snip>

#14 lore raw

Re: [PATCH v4 3/4] Add autotests for RIB library

In reply to Medvedkin Vladimir
Quoted 16 lines · Medvedkin Vladimir
---
 test/test/Makefile               |   5 +
 test/test/meson.build            |   8 +
 test/test/test_rib.c             | 308 +++++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.c | 297 +++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.h |  38 +++++
 test/test/test_rib_lpm_comp.c    | 189 ++++++++++++++++++++++++
 test/test/test_rib_perf.c        | 145 ++++++++++++++++++
 7 files changed, 990 insertions(+)
 create mode 100644 test/test/test_rib.c
 create mode 100644 test/test/test_rib_generate_rt.c
 create mode 100644 test/test/test_rib_generate_rt.h
 create mode 100644 test/test/test_rib_lpm_comp.c
 create mode 100644 test/test/test_rib_perf.c

<snip>

Quoted 49 lines
test/test/test_rib_perf.c new file +43 -0
new file mode 100644
index 0000000..42fbd1e
@@ -0,0 +1,145 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#include <stdio.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#include <rte_cycles.h>
+#include <rte_random.h>
+#include <rte_branch_prediction.h>
+#include <rte_ip.h>
+#include <rte_malloc.h>
+#include <rte_rib.h>
+#include <rte_dir24_8.h>
+
+#include "test.h"
+#include "test_xmmt_ops.h"
+#include "test_rib_generate_rt.h"
+
+#define TEST_RIB_ASSERT(cond) do {				\
+	if (!(cond)) {						\
+		printf("Error at line %d:\n", __LINE__);	\
+		return -1;					\
+	}							\
+} while (0)
+
+#define ITERATIONS (1 << 15)
+#define BATCH_SIZE (1 << 12)
+#define BULK_SIZE 32
+
+#define NH_MSK(nh_sz)	((1ULL << ((1 << (3 + nh_sz)) - 1)) - 1)
+
+static int
+test_rib_perf(void)
+{
+	struct rte_rib *rib = NULL;
+	struct rte_rib_conf conf;
+	struct route_rule *rt;
+	uint64_t begin, total_time;
+	uint64_t next_hop_add;
+	uint64_t default_nh = 0;
+	int64_t count = 0;

test/test/test_rib_perf.c line 53

Quoted 10 lines
test/test/test_rib_perf.c new file +10 -0
+	unsigned int i, j;
+	int status = 0;
+	int ret, nh_bits, nr_tbl8;
+	uint32_t num_routes;
+
+	conf.max_nodes = 3000000;
+	conf.node_sz = sizeof(struct rte_rib_node);
+	conf.type = RTE_RIB_DIR24_8;
+	conf.fib_conf.dir24_8.def_nh = default_nh;
+	conf.fib_conf.dir24_8.nh_sz = RTE_DIR24_8_8B;

It's good that you are taking the worst-case to show the perf, but it means that the library comes out a bit slower than LPM in the autotest. How about running the same test cases for multiple data sizes, 8, 4, 2?

Quoted 95 lines
test/test/test_rib_perf.c new file +92 -0
+
+	rte_srand(rte_rdtsc());
+
+	nh_bits = RTE_MIN(((1 << (3 + conf.fib_conf.dir24_8.nh_sz)) - 1), 24);
+	nr_tbl8 = RTE_MIN(((1 << nh_bits) - 1), 131071);
+	conf.fib_conf.dir24_8.num_tbl8 = nr_tbl8;
+	num_routes = 1200000;
+
+	rt = rte_zmalloc("struct route_rule *", sizeof(struct route_rule) *
+		num_routes, 0);
+	TEST_RIB_ASSERT(rt != NULL);
+
+	num_routes = generate_large_route_rule_table(num_routes, rt);
+	TEST_RIB_ASSERT(num_routes != 0);
+
+	printf("No. routes = %u\n", (unsigned int) num_routes);
+
+	shuffle_rt(rt, num_routes);
+
+	print_route_distribution(rt, (uint32_t) num_routes);
+
+	rib = rte_rib_create(__func__, SOCKET_ID_ANY, &conf);
+	TEST_RIB_ASSERT(rib != NULL);
+
+	/* Measue add. */
+	begin = rte_rdtsc();
+
+	for (i = 0; i < num_routes; i++) {
+		do {
+			next_hop_add = rte_rand() & NH_MSK(conf.fib_conf.dir24_8.nh_sz);
+		} while (next_hop_add == default_nh);
+
+		ret = rte_rib_add(rib, rt[i].ip, rt[i].depth, next_hop_add);
+		if ((ret == 0))
+			status++;
+	}
+
+	total_time = rte_rdtsc() - begin;
+
+	printf("Unique added entries = %d\n", status);
+	printf("Average RIB Add: %g cycles\n",
+			(double)total_time / num_routes);
+
+	/* Measure bulk Lookup */
+	total_time = 0;
+	count = 0;
+	for (i = 0; i < ITERATIONS; i++) {
+		static uint32_t ip_batch[BATCH_SIZE];
+		uint64_t next_hops[BULK_SIZE];
+
+		/* Create array of random IP addresses */
+		for (j = 0; j < BATCH_SIZE; j++)
+			ip_batch[j] = rte_rand();
+
+		/* Lookup per batch */
+		begin = rte_rdtsc();
+		for (j = 0; j < BATCH_SIZE; j += BULK_SIZE)
+			rte_rib_fib_lookup_bulk(rib, &ip_batch[j], next_hops,
+				BULK_SIZE);
+
+		total_time += rte_rdtsc() - begin;
+		for (j = 0; j < BULK_SIZE; j++) {
+			if (next_hops[j] == default_nh)
+				count++;
+		}
+	}
+	printf("BULK RIB Lookup: %.1f cycles (fails = %.1f%%)\n",
+			(double)total_time / ((double)ITERATIONS * BATCH_SIZE),
+			(count * 100.0) / (double)(ITERATIONS * BATCH_SIZE));
+
+	/* Delete */
+	status = 0;
+	begin = rte_rdtsc();
+
+	for (i = 0; i < num_routes; i++) {
+		ret = rte_rib_delete(rib, rt[i].ip, rt[i].depth);
+		if (ret == 0)
+			status++;
+	}
+
+	total_time = rte_rdtsc() - begin;
+
+	printf("Average RIB Delete: %g cycles\n",
+			(double)total_time / num_routes);
+
+	rte_rib_free(rib);
+	rte_free(rt);
+
+	return 0;
+}
+
+REGISTER_TEST_COMMAND(rib_perf_autotest, test_rib_perf);
Signature · 1 line
1.8.3.1
#15 lore raw

PATCH v4 4/4 Add support for lpm and rib bulk lookup

In reply to Medvedkin Vladimir
---
 examples/l3fwd/l3fwd_lpm.c | 132 +++++++++++++++++++++++++++++++++++++++++++++
 examples/l3fwd/meson.build |   2 +-
 2 files changed, 133 insertions(+), 1 deletion(-)
examples/l3fwd/l3fwd_lpm.c +132 -0
index a747126..9ad1ddc 100644
@@ -24,9 +24,12 @@
 #include <rte_tcp.h>
 #include <rte_udp.h>
 #include <rte_lpm.h>
+#include <rte_rib.h>
 #include <rte_lpm6.h>
 
 #include "l3fwd.h"
+#define BULK_LOOKUP
+#define USE_RIB
 
 struct ipv4_l3fwd_lpm_route {
 	uint32_t ip;
@@ -72,7 +75,11 @@ struct ipv6_l3fwd_lpm_route {
 #define IPV6_L3FWD_LPM_MAX_RULES         1024
 #define IPV6_L3FWD_LPM_NUMBER_TBL8S (1 << 16)
 
+#if  defined(BULK_LOOKUP) && defined(USE_RIB)
+struct rte_rib *ipv4_l3fwd_lpm_lookup_struct[NB_SOCKETS];
+#else
 struct rte_lpm *ipv4_l3fwd_lpm_lookup_struct[NB_SOCKETS];
+#endif
 struct rte_lpm6 *ipv6_l3fwd_lpm_lookup_struct[NB_SOCKETS];
 
 static inline uint16_t
@@ -168,6 +175,104 @@ struct ipv6_l3fwd_lpm_route {
 #include "l3fwd_lpm.h"
 #endif
 
+static __rte_always_inline int
+l3fwd_rib_handle_pkt(struct rte_mbuf *m, uint32_t *dst_ip)
+{
+	struct ipv4_hdr *ipv4_hdr;
+
+	if (RTE_ETH_IS_IPV4_HDR(m->packet_type)) {
+		/* Handle IPv4 headers.*/
+		ipv4_hdr = rte_pktmbuf_mtod_offset(m, struct ipv4_hdr *,
+				sizeof(struct ether_hdr));
+#ifdef DO_RFC_1812_CHECKS
+		/* Check to make sure the packet is valid (RFC1812) */
+		if (is_valid_ipv4_pkt(ipv4_hdr, m->pkt_len) < 0)
+			return -1;
+		/* Update time to live and header checksum */
+		--(ipv4_hdr->time_to_live);
+		++(ipv4_hdr->hdr_checksum);
+#endif
+		*dst_ip = rte_be_to_cpu_32(ipv4_hdr->dst_addr);
+	} else
+		return -1;
+
+	return 0;
+}
+
+static inline void
+l3fwd_rib_send_packets(int nb_rx, struct rte_mbuf **pkts_burst,
+			uint16_t portid, struct lcore_conf *qconf)
+{
+	struct rte_mbuf *send_pkts[MAX_PKT_BURST];
+#ifdef USE_RIB
+	uint64_t next_hops[MAX_PKT_BURST];
+#else
+	uint32_t next_hops[MAX_PKT_BURST];
+#endif
+	uint32_t dst_ips[MAX_PKT_BURST];
+#ifdef USE_RIB
+	struct rte_rib *rib = qconf->ipv4_lookup_struct;
+#else
+	struct rte_lpm *rib = qconf->ipv4_lookup_struct;
+#endif
+	struct ether_hdr *eth_hdr;
+        int32_t j, k = 0;
+	int ret;
+	uint16_t dst_port;
+
+	for (j = 0; j < PREFETCH_OFFSET && j < nb_rx; j++)
+		rte_prefetch0(rte_pktmbuf_mtod(pkts_burst[j], void *));
+
+	for (j = 0; j < (nb_rx - PREFETCH_OFFSET); j++) {
+		rte_prefetch0(rte_pktmbuf_mtod(pkts_burst[
+			j + PREFETCH_OFFSET], void *));
+
+		ret = l3fwd_rib_handle_pkt(pkts_burst[j], &dst_ips[k]);
+		if (ret != 0) {
+			rte_pktmbuf_free(pkts_burst[j]);
+			continue;
+		}
+		send_pkts[k++] = pkts_burst[j];
+        }
+
+        for (; j < nb_rx; j++) {
+		ret = l3fwd_rib_handle_pkt(pkts_burst[j], &dst_ips[k]);
+		if (ret != 0) {
+			rte_pktmbuf_free(pkts_burst[j]);
+			continue;
+		}
+		send_pkts[k++] = pkts_burst[j];
+	}
+
+#ifdef USE_RIB
+	ret = rte_rib_fib_lookup_bulk(rib, dst_ips, next_hops, k);
+#else
+	ret = rte_lpm_lookup_bulk(rib, dst_ips, next_hops, k);
+#endif
+	if (ret != 0) {
+		for (j = 0; j < k; j++)
+			rte_pktmbuf_free(send_pkts[j]);
+	} else {
+		for (j = 0; j < k; j++) {
+#ifdef USE_RIB
+			dst_port = next_hops[j];
+#else
+			dst_port = next_hops[j] & 0x00FFFFFF;
+#endif
+			if (dst_port >= RTE_MAX_ETHPORTS ||
+				(enabled_port_mask & 1 << dst_port) == 0) {
+				dst_port = portid;
+			}
+			eth_hdr = rte_pktmbuf_mtod(send_pkts[j], struct ether_hdr *);
+			/* dst addr */
+			*(uint64_t *)&eth_hdr->d_addr = dest_eth_addr[dst_port];
+			/* src addr */
+			ether_addr_copy(&ports_eth_addr[dst_port], &eth_hdr->s_addr);
+			send_single_packet(qconf, send_pkts[j], dst_port);
+		}
+	}
+}
+
 /* main processing loop */
 int
 lpm_main_loop(__attribute__((unused)) void *dummy)
@@ -237,6 +342,10 @@ struct ipv6_l3fwd_lpm_route {
 			if (nb_rx == 0)
 				continue;
 
+#if defined(BULK_LOOKUP)
+			l3fwd_rib_send_packets(nb_rx, pkts_burst,
+						portid, qconf);
+#else
 #if defined RTE_ARCH_X86 || defined RTE_MACHINE_CPUFLAG_NEON \
 			 || defined RTE_ARCH_PPC_64
 			l3fwd_lpm_send_packets(nb_rx, pkts_burst,
@@ -245,6 +354,7 @@ struct ipv6_l3fwd_lpm_route {
 			l3fwd_lpm_no_opt_send_packets(nb_rx, pkts_burst,
 							portid, qconf);
 #endif /* X86 */
+#endif /* BULK_LOOKUP*/
 		}
 	}
 
@@ -255,18 +365,36 @@ struct ipv6_l3fwd_lpm_route {
 setup_lpm(const int socketid)
 {
 	struct rte_lpm6_config config;
+#if defined(BULK_LOOKUP) && defined(USE_RIB)
+	struct rte_rib_conf config_ipv4;
+#else
 	struct rte_lpm_config config_ipv4;
+#endif
 	unsigned i;
 	int ret;
 	char s[64];
 
 	/* create the LPM table */
+#if defined(BULK_LOOKUP) && defined(USE_RIB)
+	config_ipv4.type = RTE_RIB_DIR24_8;
+	config_ipv4.max_nodes = IPV4_L3FWD_LPM_MAX_RULES;
+	config_ipv4.node_sz = sizeof(struct rte_rib_node);
+	config_ipv4.fib_conf.dir24_8.def_nh = 0;
+	config_ipv4.fib_conf.dir24_8.nh_sz = RTE_DIR24_8_4B;
+	config_ipv4.fib_conf.dir24_8.num_tbl8 = IPV4_L3FWD_LPM_NUMBER_TBL8S;
+#else
 	config_ipv4.max_rules = IPV4_L3FWD_LPM_MAX_RULES;
 	config_ipv4.number_tbl8s = IPV4_L3FWD_LPM_NUMBER_TBL8S;
 	config_ipv4.flags = 0;
+#endif
 	snprintf(s, sizeof(s), "IPV4_L3FWD_LPM_%d", socketid);
+
 	ipv4_l3fwd_lpm_lookup_struct[socketid] =
+#if defined(BULK_LOOKUP) && defined(USE_RIB)
+			rte_rib_create(s, socketid, &config_ipv4);
+#else
 			rte_lpm_create(s, socketid, &config_ipv4);
+#endif
 	if (ipv4_l3fwd_lpm_lookup_struct[socketid] == NULL)
 		rte_exit(EXIT_FAILURE,
 			"Unable to create the l3fwd LPM table on socket %d\n",
@@ -280,7 +408,11 @@ struct ipv6_l3fwd_lpm_route {
 				enabled_port_mask) == 0)
 			continue;
 
+#if defined(BULK_LOOKUP) && defined(USE_RIB)
+		ret = rte_rib_add(ipv4_l3fwd_lpm_lookup_struct[socketid],
+#else
 		ret = rte_lpm_add(ipv4_l3fwd_lpm_lookup_struct[socketid],
+#endif
 			ipv4_l3fwd_lpm_route_array[i].ip,
 			ipv4_l3fwd_lpm_route_array[i].depth,
 			ipv4_l3fwd_lpm_route_array[i].if_out);
examples/l3fwd/meson.build +1 -1
index cbef07f..f742fb1 100644
@@ -6,7 +6,7 @@
 # To build this example as a standalone application with an already-installed
 # DPDK instance, use 'make'
 
-deps += ['hash', 'lpm']
+deps += ['hash', 'lpm', 'rib']
 allow_experimental_apis = true
 sources = files(
 	'l3fwd_em.c', 'l3fwd_lpm.c', 'main.c'
Signature · 1 line
1.8.3.1
#16 lore raw
In reply to Medvedkin Vladimir
Quoted 28 lines · On Fri, 27 Apr 2018 01:03:30 +0300 Medvedkin Vladimir <[email protected]>…

This patch series introduces new library librte_rib which potentially could replace librte_lpm.

RIB is an alternative to current LPM library.
It solves the following problems
- Increases the speed of control plane operations against lpm such as adding/deleting routes
- Adds abstraction from dataplane algorithms, so it is possible to add different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc in addition to current dir24_8
- It is possible to keep user defined application specific additional information in struct rte_rib_node which represents route entry. It can be next hop/set of next hops (i.e. active and feasible), pointers to link rte_rib_node based on some criteria (i.e. next_hop), plenty of additional control plane information.

v4:
fix various bugs
make struct rte_rib opaque
make inline functions instead of macro
remove RTE_RIB_MALLOC node allocation type
add new lookup functions
remove rte_dir24_8_lookup()
add rte_dir24_8_get_lookup()
add meson support
add fib configuration

Quoted 4 lines

Medvedkin Vladimir (4):
Add RIB library
Add dir24_8 implementation for rib library
Add autotests for RIB library

The existing DPDK LPM code does need more work it does trade space for time.

It does have some advantages though:
* LPM lookup table is independent of number of routes.
* LPM lookup table can be lock free reader safe using RCU.

The existing slowness of add and delete was fixed at Vyatta/Brocade by replacing list with red-black tree. Patches were submitted but never merged.

#17 lore raw

27/04/2018 00:24, Stephen Hemminger:

Quoted 2 lines

The existing slowness of add and delete was fixed at Vyatta/Brocade by replacing list with red-black tree. Patches were submitted but never merged.

I don't remember these patches.
Why they were not merged?

#18 lore raw
Quoted 8 lines · On Fri, 27 Apr 2018 00:27:03 +0200 Thomas Monjalon <[email protected]> wrote:

27/04/2018 00:24, Stephen Hemminger:

Quoted 2 lines

The existing slowness of add and delete was fixed at Vyatta/Brocade by replacing list with red-black tree. Patches were submitted but never merged.

I don't remember these patches.
Why they were not merged?

Probably because they caused dependency on -libbsd on Linux?

#20 lore raw
In reply to Stephen Hemminger

Hi Stephen,

2018-04-27 1:24 GMT+03:00 Stephen Hemminger <[email protected]>:

Quoted 37 lines
Quoted 1 line · On Fri, 27 Apr 2018 01:03:30 +0300 Medvedkin Vladimir <[email protected]>…

This patch series introduces new library librte_rib which potentially

could

Quoted 27 lines

replace librte_lpm.

RIB is an alternative to current LPM library.
It solves the following problems
- Increases the speed of control plane operations against lpm such as adding/deleting routes
- Adds abstraction from dataplane algorithms, so it is possible to add different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc in addition to current dir24_8
- It is possible to keep user defined application specific additional information in struct rte_rib_node which represents route entry. It can be next hop/set of next hops (i.e. active and feasible), pointers to link rte_rib_node based on some criteria (i.e. next_hop), plenty of additional control plane information.

v4:
fix various bugs
make struct rte_rib opaque
make inline functions instead of macro
remove RTE_RIB_MALLOC node allocation type
add new lookup functions
remove rte_dir24_8_lookup()
add rte_dir24_8_get_lookup()
add meson support
add fib configuration

Quoted 4 lines

Medvedkin Vladimir (4):
Add RIB library
Add dir24_8 implementation for rib library
Add autotests for RIB library

Quoted 6 lines

The existing DPDK LPM code does need more work it does trade space for time.

It does have some advantages though:
* LPM lookup table is independent of number of routes.

To be honest it depends on number of prefixes longer 24. But despite this my implementation is independent of number of routes too.

Quoted 2 lines

* LPM lookup table can be lock free reader safe using RCU.

As I see you are using rcu only for tbl8's growing. This feature was out of scope and could be added if needed. But I'm afraid about license constraints.

Quoted 5 lines

The existing slowness of add and delete was fixed at Vyatta/Brocade by replacing list with red-black tree. Patches were submitted but never merged.

Could you please share lpm_perf_autotest results for your version? Here my results for lpm_perf_autotest and rib_perf_autotest (sizeof key == sizeof(struct rte_lpm_tbl_entry) so memory footprint is the same) LPM:
Unique added entries = 1037026
Used table 24 entries = 14680064 (87.5%)
64 byte Cache entries used = 458753 (29360192 bytes)
Average LPM Add: 306566 cycles
Average LPM Lookup: 29.7 cycles (fails = 0.0%)
BULK LPM Lookup: 29.4 cycles (fails = 0.0%)
LPM LookupX4: 27.1 cycles (fails = 0.0%)
Average LPM Delete: 201360 cycles
Test OK
RIB:
Unique added entries = 1076816
Average RIB Add: 3149.62 cycles
BULK RIB Lookup: 23.8 cycles (fails = 0.0%)
Average RIB Delete: 2949.62 cycles
Test OK

As you can see for 1M+ routes I have 100 times faster add and 70 times faster delete. Lookup speed is faster too.
It was achieved due to:
1. routes are kept in compressed binary tree so rule insertion/deletion are cheap comparing to flat array in LPM. And yes, rb_tree implementation fixes that problem too.
2. routes are kept in compressed binary tree so you can get less specific prefix (parent node) for a given prefix (you want add/del to) and compare it's next hop to a given next hop. There is no need to touch fib table if they are equal.
3. routes are kept in compressed binary tree so you can traverse on some part of that tree to get subprefixes for a given prefix (you want add/del to). Hence you can get gaps between retrieved more specific routes and based on this gaps unconditionally rewrite part of fib table. Comparing to LPM where every write to tbl24 or tbl8 is accompanied by a comparison of depth. In addition there is no need to keep depth in fib anymore.
4. LPM tbl8_alloc is expensive due to memory scan through tbl8 to find a free tbl8 group. More effective to keep free tbl8 indexes in bitmap.

Signature · 2 lines
Regards,
Vladimir
#21 lore raw
In reply to Medvedkin Vladimir
Quoted 28 lines · Medvedkin Vladimir

This patch series introduces new library librte_rib which potentially could replace librte_lpm.

RIB is an alternative to current LPM library.
It solves the following problems
- Increases the speed of control plane operations against lpm such as adding/deleting routes
- Adds abstraction from dataplane algorithms, so it is possible to add different ip route lookup algorythms such as DXR/poptrie/lpc-trie/etc in addition to current dir24_8
- It is possible to keep user defined application specific additional information in struct rte_rib_node which represents route entry. It can be next hop/set of next hops (i.e. active and feasible), pointers to link rte_rib_node based on some criteria (i.e. next_hop), plenty of additional control plane information.

v4:
fix various bugs
make struct rte_rib opaque
make inline functions instead of macro
remove RTE_RIB_MALLOC node allocation type
add new lookup functions
remove rte_dir24_8_lookup()
add rte_dir24_8_get_lookup()
add meson support
add fib configuration

Quoted 6 lines

Medvedkin Vladimir (4):
Add RIB library
Add dir24_8 implementation for rib library
Add autotests for RIB library
Add support for lpm and rib bulk lookup

Some general comments on this set:

* run checkpatches and check-git-log from devtools on the set, a number of warnings are thrown up by both [e.g. no initial-caps for patch titles]
* before merge to DPDK this probably needs to be split up into smaller patches with more limited set of functionality in each one. For example, the create/destroy, add/delete and lookup functions can probably go in separate patches to make reviews easier.

#22 lore raw

v5 cover lib: add RIB and FIB liraries

In reply to Medvedkin Vladimir

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

Current lpm implementation while provides really good lookup performance has number of problems.
One of them is very low speed for control plane operations such as add or delete a route.
Another disadvantage is fixed number of bits for userdata (24 for v4 and 21 for v6)
Also it is hard to introduce changes in existing LPM code or add new algorithms without breaking ABI.

This patch series tries to solve this problems by:
Introduce two new libraries - RIB and FIB.
RIB that is Routing Information Base.
It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals (i.e. retrieve existing subroutes for a given prefix). This structure will be used as a control plane helper structure for FIB implementation.
Also it might be used standalone in other different places such as bitmaps for example.

Second library is FIB that is Forwarding Information Base. It represents dataplane related struct and algorithms for longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future (for example DXR, poptrie, etc).

From our measurements we saw 10x speedup for control plane operations comparing with current LPM library (depending on prefix length distribution)

ToDo:
- introduce new performance measurement app.
- add documentation.
- add support into existing examples (l3fwd)

Vladimir Medvedkin (12):
rib: add RIB library
test/rib: add RIB library autotests
rib: add ipv6 support for RIB
test/rib: add ipv6 support for RIB autotests
fib: add FIB library
fib: add FIB ipv6 support
fib: add DIR24-8 dataplane algorithm
fib: add dataplane algorithm for ipv6 test/fib: add FIB library autotests test/fib: add ipv6 support for FIB autotests test/fib: add FIB library performance autotests test/fib: add FIB library ipv6 performance autotests

 app/test/Makefile                  |   7 +
 app/test/autotest_data.py          |  36 ++
 app/test/meson.build               |  14 +
 app/test/test_fib.c                | 397 +++++++++++++++++++
 app/test/test_fib6.c               | 405 ++++++++++++++++++++
 app/test/test_fib6_perf.c          | 157 ++++++++
 app/test/test_fib_perf.c           | 411 ++++++++++++++++++++
 app/test/test_rib.c                | 351 +++++++++++++++++
 app/test/test_rib6.c               | 357 +++++++++++++++++
 config/common_base                 |  11 +
 doc/api/doxy-api.conf.in           |   2 +
 lib/Makefile                       |   4 +
 lib/librte_fib/Makefile            |  25 ++
 lib/librte_fib/dir24_8.c           | 737 +++++++++++++++++++++++++++++++++++
 lib/librte_fib/dir24_8.h           |  36 ++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 319 ++++++++++++++++
 lib/librte_fib/rte_fib.h           | 188 +++++++++
 lib/librte_fib/rte_fib6.c          | 322 ++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 193 ++++++++++
 lib/librte_fib/rte_fib_version.map |  23 ++
 lib/librte_fib/trie.c              | 760 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h              |  37 ++
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
 lib/librte_rib/rte_rib.c           | 532 ++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 ++++++++++++++
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 ++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  35 ++
 lib/meson.build                    |   4 +-
 mk/rte.app.mk                      |   2 +
 32 files changed, 6614 insertions(+), 1 deletion(-)
 create mode 100644 app/test/test_fib.c
 create mode 100644 app/test/test_fib6.c
 create mode 100644 app/test/test_fib6_perf.c
 create mode 100644 app/test/test_fib_perf.c
 create mode 100644 app/test/test_rib.c
 create mode 100644 app/test/test_rib6.c
 create mode 100644 lib/librte_fib/Makefile
 create mode 100644 lib/librte_fib/dir24_8.c
 create mode 100644 lib/librte_fib/dir24_8.h
 create mode 100644 lib/librte_fib/meson.build
 create mode 100644 lib/librte_fib/rte_fib.c
 create mode 100644 lib/librte_fib/rte_fib.h
 create mode 100644 lib/librte_fib/rte_fib6.c
 create mode 100644 lib/librte_fib/rte_fib6.h
 create mode 100644 lib/librte_fib/rte_fib_version.map
 create mode 100644 lib/librte_fib/trie.c
 create mode 100644 lib/librte_fib/trie.h
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib6.c
 create mode 100644 lib/librte_rib/rte_rib6.h
 create mode 100644 lib/librte_rib/rte_rib_version.map
Signature · 1 line
2.7.4
#23 lore raw

PATCH v5 1/12 rib: add RIB library

Add RIB (Routing Information Base) library. This library implements an IPv4 routing table optimized for control plane operations. It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals
(i.e. retrieve existing subroutes for a giver prefix). This structure will be used as a control plane helper structure for FIB implementation. Also it might be used standalone in other different places such as bitmaps for example.
Internal implementation is level compressed binary trie.

---
 config/common_base                 |   5 +
 doc/api/doxy-api.conf.in           |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
 lib/librte_rib/rte_rib.c           | 532 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 +++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  20 ++
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 10 files changed, 872 insertions(+), 1 deletion(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map
config/common_base +5 -0
index 8ef75c2..5a9d4c3 100644
@@ -894,6 +894,11 @@ CONFIG_RTE_LIBRTE_RCU=y
 CONFIG_RTE_LIBRTE_RCU_DEBUG=n
 
 #
+# Compile librte_rib
+#
+CONFIG_RTE_LIBRTE_RIB=y
+
+#
 # Compile librte_lpm
 #
 CONFIG_RTE_LIBRTE_LPM=y
doc/api/doxy-api.conf.in +1 -0
index 908cee8..3ec012d 100644
@@ -54,6 +54,7 @@ INPUT                   = @TOPDIR@/doc/api/doxy-api-index.md \
                           @TOPDIR@/lib/librte_rawdev \
                           @TOPDIR@/lib/librte_rcu \
                           @TOPDIR@/lib/librte_reorder \
+                          @TOPDIR@/lib/librte_rib \
                           @TOPDIR@/lib/librte_ring \
                           @TOPDIR@/lib/librte_sched \
                           @TOPDIR@/lib/librte_security \
lib/Makefile +2 -0
index 41c463d..aa5ee1e 100644
@@ -51,6 +51,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_HASH) += librte_hash
 DEPDIRS-librte_hash := librte_eal librte_ring
 DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
+DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib
+DEPDIRS-librte_rib := librte_eal librte_mempool
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
 DEPDIRS-librte_lpm := librte_eal librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
lib/librte_rib/Makefile new file +25 -0
new file mode 100644
index 0000000..79f259a
@@ -0,0 +1,25 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_rib.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+CFLAGS += -DALLOW_EXPERIMENTAL_API
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_rib_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_rib/meson.build new file +8 -0
new file mode 100644
index 0000000..e7b8920
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# Copyright(c) 2019 Intel Corporation
+
+allow_experimental_apis = true
+sources = files('rte_rib.c')
+headers = files('rte_rib.h')
+deps += ['mempool']
lib/librte_rib/rte_rib.c new file +532 -0

532 lines not on this page · raw message

lib/librte_rib/rte_rib.h new file +277 -0

277 lines not on this page · raw message

lib/librte_rib/rte_rib_version.map new file +20 -0
new file mode 100644
index 0000000..1432a22
@@ -0,0 +1,20 @@
+EXPERIMENTAL {
+	global:
+
+	rte_rib_create;
+	rte_rib_find_existing;
+	rte_rib_free;
+	rte_rib_get_depth;
+	rte_rib_get_ext;
+	rte_rib_get_ip;
+	rte_rib_get_nh;
+	rte_rib_get_nxt;
+	rte_rib_insert;
+	rte_rib_lookup;
+	rte_rib_lookup_parent;
+	rte_rib_lookup_exact;
+	rte_rib_set_nh;
+	rte_rib_remove;
+
+	local: *;
+};
lib/meson.build +1 -1
index e5ff838..d7f2a04 100644
@@ -22,7 +22,7 @@ libraries = [
 	'gro', 'gso', 'ip_frag', 'jobstats',
 	'kni', 'latencystats', 'lpm', 'member',
 	'power', 'pdump', 'rawdev',
-	'rcu', 'reorder', 'sched', 'security', 'stack', 'vhost',
+	'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost',
 	# ipsec lib depends on net, crypto and security
 	'ipsec',
 	# add pkt framework libs which use other libs from above
mk/rte.app.mk +1 -0
index ba5c39e..4517874 100644
@@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP)          += -lrte_pdump
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR)    += -lrte_distributor
 _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG)        += -lrte_ip_frag
 _LDLIBS-$(CONFIG_RTE_LIBRTE_METER)          += -lrte_meter
+_LDLIBS-$(CONFIG_RTE_LIBRTE_RIB)            += -lrte_rib
 _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM)            += -lrte_lpm
 _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL)            += -lrte_acl
 _LDLIBS-$(CONFIG_RTE_LIBRTE_TELEMETRY)      += --no-as-needed
Signature · 1 line
2.7.4
#24 lore raw

PATCH v5 2/12 test/rib: add RIB library autotests

In reply to Vladimir Medvedkin

Functional tests for the new RIB library.

---
 app/test/Makefile         |   2 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   3 +
 app/test/test_rib.c       | 351 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 362 insertions(+)
 create mode 100644 app/test/test_rib.c
app/test/Makefile +2 -0
index 26ba6fe..5bd8487 100644
@@ -124,6 +124,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_multiwriter.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
+
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm6.c
app/test/autotest_data.py +6 -0
index 7405149..3c3b806 100644
@@ -111,6 +111,12 @@
         "Report":  None,
     },
     {
+        "Name":    "RIB autotest",
+        "Command": "rib_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +3 -0
index ec40943..98524e1 100644
@@ -99,6 +99,7 @@ test_sources = files('commands.c',
 	'test_reciprocal_division_perf.c',
 	'test_red.c',
 	'test_reorder.c',
+	'test_rib.c',
 	'test_ring.c',
 	'test_ring_perf.c',
 	'test_rwlock.c',
@@ -147,6 +148,7 @@ test_deps = ['acl',
 	'rawdev',
 	'rcu',
 	'reorder',
+	'rib',
 	'ring',
 	'stack',
 	'timer'
@@ -197,6 +199,7 @@ fast_test_names = [
         'prefetch_autotest',
         'rcu_qsbr_autotest',
         'red_autotest',
+        'rib_autotest',
         'ring_autotest',
         'ring_pmd_autotest',
         'rwlock_test1_autotest',
app/test/test_rib.c new file +351 -0

351 lines not on this page · raw message

Signature · 1 line
2.7.4
#25 lore raw

PATCH v5 3/12 rib: add ipv6 support for RIB

In reply to Vladimir Medvedkin

Extend RIB library with ipv6 support.

---
 lib/librte_rib/Makefile            |   4 +-
 lib/librte_rib/meson.build         |   4 +-
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 +++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  15 +
 5 files changed, 951 insertions(+), 4 deletions(-)
 create mode 100644 lib/librte_rib/rte_rib6.c
 create mode 100644 lib/librte_rib/rte_rib6.h
lib/librte_rib/Makefile +2 -2
index 79f259a..6d861ad 100644
@@ -17,9 +17,9 @@ EXPORT_MAP := rte_rib_version.map
 LIBABIVER := 1
 
 # all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c rte_rib6.c
 
 # install this header file
-SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h rte_rib6.h
 
 include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_rib/meson.build +2 -2
index e7b8920..46a1c0c 100644
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_rib.c')
-headers = files('rte_rib.h')
+sources = files('rte_rib.c', 'rte_rib6.c')
+headers = files('rte_rib.h', 'rte_rib6.h')
 deps += ['mempool']
lib/librte_rib/rte_rib6.c new file +598 -0

598 lines not on this page · raw message

lib/librte_rib/rte_rib6.h new file +334 -0

334 lines not on this page · raw message

lib/librte_rib/rte_rib_version.map +15 -0
index 1432a22..9b6161a 100644
@@ -16,5 +16,20 @@ EXPERIMENTAL {
 	rte_rib_set_nh;
 	rte_rib_remove;
 
+	rte_rib6_create;
+	rte_rib6_find_existing;
+	rte_rib6_free;
+	rte_rib6_get_depth;
+	rte_rib6_get_ext;
+	rte_rib6_get_ip;
+	rte_rib6_get_nh;
+	rte_rib6_get_nxt;
+	rte_rib6_insert;
+	rte_rib6_lookup;
+	rte_rib6_lookup_parent;
+	rte_rib6_lookup_exact;
+	rte_rib6_set_nh;
+	rte_rib6_remove;
+
 	local: *;
 };
Signature · 1 line
2.7.4
#26 lore raw

PATCH v5 4/12 test/rib: add ipv6 support for RIB autotests

In reply to Vladimir Medvedkin

Functional tests for RIB6.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   2 +
 app/test/test_rib6.c      | 357 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 366 insertions(+)
 create mode 100644 app/test/test_rib6.c
app/test/Makefile +1 -0
index 5bd8487..4638426 100644
@@ -125,6 +125,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index 3c3b806..f35b3cc 100644
@@ -117,6 +117,12 @@
         "Report":  None,
     },
     {
+        "Name":    "RIB6 autotest",
+        "Command": "rib6_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +2 -0
index 98524e1..49c1de0 100644
@@ -100,6 +100,7 @@ test_sources = files('commands.c',
 	'test_red.c',
 	'test_reorder.c',
 	'test_rib.c',
+	'test_rib6.c',
 	'test_ring.c',
 	'test_ring_perf.c',
 	'test_rwlock.c',
@@ -200,6 +201,7 @@ fast_test_names = [
         'rcu_qsbr_autotest',
         'red_autotest',
         'rib_autotest',
+        'rib6_autotest',
         'ring_autotest',
         'ring_pmd_autotest',
         'rwlock_test1_autotest',
app/test/test_rib6.c new file +357 -0

357 lines not on this page · raw message

Signature · 1 line
2.7.4
#27 lore raw

PATCH v5 5/12 fib: add FIB library

In reply to Vladimir Medvedkin

Add FIB (Forwarding Information Base) library. This library implements a dataplane structures and algorithms designed for fast longest prefix match.
Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future (for example DXR, poptrie, etc).

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf.in           |   1 +
 lib/Makefile                       |   2 +
 lib/librte_fib/Makefile            |  25 +++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 305 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/rte_fib.h           | 173 +++++++++++++++++++++
 lib/librte_fib/rte_fib_version.map |  14 ++
 lib/meson.build                    |   2 +
 mk/rte.app.mk                      |   1 +
 10 files changed, 537 insertions(+)
 create mode 100644 lib/librte_fib/Makefile
 create mode 100644 lib/librte_fib/meson.build
 create mode 100644 lib/librte_fib/rte_fib.c
 create mode 100644 lib/librte_fib/rte_fib.h
 create mode 100644 lib/librte_fib/rte_fib_version.map
config/common_base +6 -0
index 5a9d4c3..0f32ad7 100644
@@ -899,6 +899,12 @@ CONFIG_RTE_LIBRTE_RCU_DEBUG=n
 CONFIG_RTE_LIBRTE_RIB=y
 
 #
+# Compile librte_fib
+#
+CONFIG_RTE_LIBRTE_FIB=y
+CONFIG_RTE_LIBRTE_FIB_DEBUG=n
+
+#
 # Compile librte_lpm
 #
 CONFIG_RTE_LIBRTE_LPM=y
doc/api/doxy-api.conf.in +1 -0
index 3ec012d..6fd3b51 100644
@@ -30,6 +30,7 @@ INPUT                   = @TOPDIR@/doc/api/doxy-api-index.md \
                           @TOPDIR@/lib/librte_efd \
                           @TOPDIR@/lib/librte_ethdev \
                           @TOPDIR@/lib/librte_eventdev \
+                          @TOPDIR@/lib/librte_fib \
                           @TOPDIR@/lib/librte_flow_classify \
                           @TOPDIR@/lib/librte_gro \
                           @TOPDIR@/lib/librte_gso \
lib/Makefile +2 -0
index aa5ee1e..5d04ab9 100644
@@ -53,6 +53,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib
 DEPDIRS-librte_rib := librte_eal librte_mempool
+DIRS-$(CONFIG_RTE_LIBRTE_FIB) += librte_fib
+DEPDIRS-librte_fib := librte_eal librte_rib
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
 DEPDIRS-librte_lpm := librte_eal librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
lib/librte_fib/Makefile new file +25 -0
new file mode 100644
index 0000000..7362f68
@@ -0,0 +1,25 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# 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)
+CFLAGS += -DALLOW_EXPERIMENTAL_API
+LDLIBS += -lrte_eal -lrte_rib
+
+EXPORT_MAP := rte_fib_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_fib/meson.build new file +8 -0
new file mode 100644
index 0000000..6b72360
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# Copyright(c) 2019 Intel Corporation
+
+allow_experimental_apis = true
+sources = files('rte_fib.c')
+headers = files('rte_fib.h')
+deps += ['rib']
lib/librte_fib/rte_fib.c new file +305 -0

305 lines not on this page · raw message

lib/librte_fib/rte_fib.h new file +173 -0

173 lines not on this page · raw message

lib/librte_fib/rte_fib_version.map new file +14 -0
new file mode 100644
index 0000000..776195f
@@ -0,0 +1,14 @@
+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;
+
+	local: *;
+};
lib/meson.build +2 -0
index d7f2a04..9700433 100644
@@ -25,6 +25,8 @@ libraries = [
 	'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost',
 	# ipsec lib depends on net, crypto and security
 	'ipsec',
+	#fib lib depends on rib
+	'fib',
 	# add pkt framework libs which use other libs from above
 	'port', 'table', 'pipeline',
 	# flow_classify lib depends on pkt framework table lib
mk/rte.app.mk +1 -0
index 4517874..7ce87e7 100644
@@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP)          += -lrte_pdump
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR)    += -lrte_distributor
 _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG)        += -lrte_ip_frag
 _LDLIBS-$(CONFIG_RTE_LIBRTE_METER)          += -lrte_meter
+_LDLIBS-$(CONFIG_RTE_LIBRTE_FIB)            += -lrte_fib
 _LDLIBS-$(CONFIG_RTE_LIBRTE_RIB)            += -lrte_rib
 _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM)            += -lrte_lpm
 _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL)            += -lrte_acl
Signature · 1 line
2.7.4
#28 lore raw

PATCH v5 6/12 fib: add FIB ipv6 support

In reply to Vladimir Medvedkin

Add FIB library support for IPv6.
It implements a dataplane structures and algorithms designed for fast IPv6 longest prefix match.

---
 lib/librte_fib/Makefile            |   4 +-
 lib/librte_fib/meson.build         |   4 +-
 lib/librte_fib/rte_fib6.c          | 308 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 179 +++++++++++++++++++++
 lib/librte_fib/rte_fib_version.map |   9 ++
 5 files changed, 500 insertions(+), 4 deletions(-)
 create mode 100644 lib/librte_fib/rte_fib6.c
 create mode 100644 lib/librte_fib/rte_fib6.h
lib/librte_fib/Makefile +2 -2
index 7362f68..0bdf55b 100644
@@ -17,9 +17,9 @@ EXPORT_MAP := rte_fib_version.map
 LIBABIVER := 1
 
 # all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c
 
 # install this header file
-SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h
 
 include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_fib/meson.build +2 -2
index 6b72360..32dfdec 100644
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_fib.c')
-headers = files('rte_fib.h')
+sources = files('rte_fib.c', 'rte_fib6.c')
+headers = files('rte_fib.h', 'rte_fib6.h')
 deps += ['rib']
lib/librte_fib/rte_fib6.c new file +308 -0

308 lines not on this page · raw message

lib/librte_fib/rte_fib6.h new file +179 -0

179 lines not on this page · raw message

lib/librte_fib/rte_fib_version.map +9 -0
index 776195f..9527417 100644
@@ -10,5 +10,14 @@ EXPERIMENTAL {
 	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: *;
 };
Signature · 1 line
2.7.4
#29 lore raw

PATCH v5 7/12 fib: add DIR24-8 dataplane algorithm

In reply to Vladimir Medvedkin

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

---
 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
lib/librte_fib/Makefile +1 -1
index 0bdf55b..67fde9a 100644
@@ -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
lib/librte_fib/dir24_8.c new file +737 -0

737 lines not on this page · raw message

lib/librte_fib/dir24_8.h new file +36 -0
new file mode 100644
index 0000000..34ddb91
@@ -0,0 +1,36 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ * 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_ */
+
lib/librte_fib/meson.build +1 -1
index 32dfdec..c63cac8 100644
@@ -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']
lib/librte_fib/rte_fib.c +14 -0
index 4d8a771..e090808 100644
@@ -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;
 	}
lib/librte_fib/rte_fib.h +16 -1
index 096cc92..d06c5ef 100644
@@ -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
  *
Signature · 1 line
2.7.4
#30 lore raw

PATCH v5 8/12 fib: add dataplane algorithm for ipv6

In reply to Vladimir Medvedkin

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

---
 lib/librte_fib/Makefile    |   2 +-
 lib/librte_fib/meson.build |   2 +-
 lib/librte_fib/rte_fib6.c  |  14 +
 lib/librte_fib/rte_fib6.h  |  14 +
 lib/librte_fib/trie.c      | 760 +++++++++++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h      |  37 +++
 6 files changed, 827 insertions(+), 2 deletions(-)
 create mode 100644 lib/librte_fib/trie.c
 create mode 100644 lib/librte_fib/trie.h
lib/librte_fib/Makefile +1 -1
index 67fde9a..4abd80b 100644
@@ -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 dir24_8.c
+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
lib/librte_fib/meson.build +1 -1
index c63cac8..e2c6f44 100644
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c')
+sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'trie.c')
 headers = files('rte_fib.h', 'rte_fib6.h')
 deps += ['rib']
lib/librte_fib/rte_fib6.c +14 -0
index 9f00a80..354227d 100644
@@ -17,6 +17,8 @@
 #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",
@@ -92,12 +94,22 @@ 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;
 	}
@@ -260,6 +272,8 @@ free_dataplane(struct rte_fib6 *fib)
 	switch (fib->type) {
 	case RTE_FIB6_DUMMY:
 		return;
+	case RTE_FIB6_TRIE:
+		trie_free(fib->dp);
 	default:
 		return;
 	}
lib/librte_fib/rte_fib6.h +14 -0
index 3322123..4268704 100644
@@ -19,10 +19,12 @@
 #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
 };
 
@@ -40,12 +42,24 @@ enum rte_fib6_op {
 	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;
+	};
 };
 
 /**
lib/librte_fib/trie.c new file +760 -0

760 lines not on this page · raw message

lib/librte_fib/trie.h new file +37 -0
new file mode 100644
index 0000000..7762fb9
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ * 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_ */
+
Signature · 1 line
2.7.4
#31 lore raw

PATCH v5 9/12 test/fib: add FIB library autotests

In reply to Vladimir Medvedkin

Functional tests for the new FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   3 +
 app/test/test_fib.c       | 397 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 407 insertions(+)
 create mode 100644 app/test/test_fib.c
app/test/Makefile +1 -0
index 4638426..b67ca16 100644
@@ -126,6 +126,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index f35b3cc..e736c03 100644
@@ -123,6 +123,12 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB autotest",
+        "Command": "fib_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +3 -0
index 49c1de0..9f1895d 100644
@@ -47,6 +47,7 @@ test_sources = files('commands.c',
 	'test_eventdev.c',
 	'test_external_mem.c',
 	'test_fbarray.c',
+	'test_fib.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
 	'test_hash.c',
@@ -137,6 +138,7 @@ test_deps = ['acl',
 	'efd',
 	'ethdev',
 	'eventdev',
+	'fib',
 	'flow_classify',
 	'hash',
 	'ipsec',
@@ -180,6 +182,7 @@ fast_test_names = [
         'eal_fs_autotest',
         'errno_autotest',
         'event_ring_autotest',
+        'fib_autotest',
         'func_reentrancy_autotest',
         'flow_classify_autotest',
         'hash_autotest',
app/test/test_fib.c new file +397 -0

397 lines not on this page · raw message

Signature · 1 line
2.7.4
#32 lore raw

Re: [dpdk-dev] [PATCH v5 09/12] test/fib: add FIB library autotests

Quoted 11 lines · Vladimir Medvedkin

Functional tests for the new FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   3 +
 app/test/test_fib.c       | 397 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 407 insertions(+)
 create mode 100644 app/test/test_fib.c

Thanks so much for adding tests with your library.

Please note that even after 30s, these tests don't complete:

https://travis-ci.com/ovsrobot/dpdk/jobs/234132379

Can you restrict some of your lpm test vectors rather than looping through all of combinations? Or perhaps take the long poll tests and move them into a perf test?

#33 lore raw

Re: [dpdk-dev] [PATCH v5 09/12] test/fib: add FIB library autotests

Hi Aaron,

Quoted 15 lines · Aaron Conole
Quoted 11 lines · Vladimir Medvedkin

Functional tests for the new FIB library.

---
  app/test/Makefile         |   1 +
  app/test/autotest_data.py |   6 +
  app/test/meson.build      |   3 +
  app/test/test_fib.c       | 397 ++++++++++++++++++++++++++++++++++++++++++++++
  4 files changed, 407 insertions(+)

create mode 100644 app/test/test_fib.c

Thanks so much for adding tests with your library.

Quoted 7 lines

Please note that even after 30s, these tests don't complete:

   https://travis-ci.com/ovsrobot/dpdk/jobs/234132379

Can you restrict some of your lpm test vectors rather than looping through all of combinations? Or perhaps take the long poll tests and move them into a perf test?

Sorry for the late reply. I'll try to make it work faster :)

Signature · 2 lines
Regards,
Vladimir
#34 lore raw

Re: [dpdk-dev] [PATCH v5 09/12] test/fib: add FIB library autotests

01/10/2019 19:12, Medvedkin, Vladimir:

Quoted 18 lines · Aaron Conole
Quoted 17 lines
Quoted 11 lines · Vladimir Medvedkin

Functional tests for the new FIB library.

---
  app/test/Makefile         |   1 +
  app/test/autotest_data.py |   6 +
  app/test/meson.build      |   3 +
  app/test/test_fib.c       | 397 ++++++++++++++++++++++++++++++++++++++++++++++
  4 files changed, 407 insertions(+)

create mode 100644 app/test/test_fib.c

Thanks so much for adding tests with your library.

Please note that even after 30s, these tests don't complete:

Quoted 7 lines
Quoted 5 lines
   https://travis-ci.com/ovsrobot/dpdk/jobs/234132379

Can you restrict some of your lpm test vectors rather than looping through all of combinations? Or perhaps take the long poll tests and move them into a perf test?

Sorry for the late reply. I'll try to make it work faster :)

Because of the test duration, this series is waiting for a v6. I hope we could merge it in 19.11-rc2.

#35 lore raw

PATCH v5 10/12 test/fib: add ipv6 support for FIB autotests

In reply to Vladimir Medvedkin

Functional ipv6 tests for the FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   2 +
 app/test/test_fib6.c      | 405 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 414 insertions(+)
 create mode 100644 app/test/test_fib6.c
app/test/Makefile +1 -0
index b67ca16..c230dbf 100644
@@ -127,6 +127,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index e736c03..1244ec4 100644
@@ -129,6 +129,12 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB6 autotest",
+        "Command": "fib6_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +2 -0
index 9f1895d..fb3595b 100644
@@ -48,6 +48,7 @@ test_sources = files('commands.c',
 	'test_external_mem.c',
 	'test_fbarray.c',
 	'test_fib.c',
+	'test_fib6.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
 	'test_hash.c',
@@ -183,6 +184,7 @@ fast_test_names = [
         'errno_autotest',
         'event_ring_autotest',
         'fib_autotest',
+        'fib6_autotest',
         'func_reentrancy_autotest',
         'flow_classify_autotest',
         'hash_autotest',
app/test/test_fib6.c new file +405 -0

405 lines not on this page · raw message

Signature · 1 line
2.7.4
#36 lore raw

PATCH v5 11/12 test/fib: add FIB library performance autotests

In reply to Vladimir Medvedkin

Performance tests for the new FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   2 +
 app/test/test_fib_perf.c  | 411 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 420 insertions(+)
 create mode 100644 app/test/test_fib_perf.c
app/test/Makefile +1 -0
index c230dbf..3a3f920 100644
@@ -128,6 +128,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib_perf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index 1244ec4..7668203 100644
@@ -707,6 +707,12 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB perf autotest",
+        "Command": "fib_perf_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
          "Name":    "Efd perf autotest",
          "Command": "efd_perf_autotest",
          "Func":    default_autotest,
app/test/meson.build +2 -0
index fb3595b..e95e7cb 100644
@@ -48,6 +48,7 @@ test_sources = files('commands.c',
 	'test_external_mem.c',
 	'test_fbarray.c',
 	'test_fib.c',
+	'test_fib_perf.c',
 	'test_fib6.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
@@ -255,6 +256,7 @@ perf_test_names = [
         'reciprocal_division',
         'reciprocal_division_perf',
         'lpm_perf_autotest',
+        'fib_perf_autotest',
         'red_all',
         'barrier_autotest',
         'hash_multiwriter_autotest',
app/test/test_fib_perf.c new file +411 -0

411 lines not on this page · raw message

Signature · 1 line
2.7.4
#37 lore raw

PATCH v5 12/12 test/fib: add FIB library ipv6 performance autotests

In reply to Vladimir Medvedkin

Performance ipv6 tests for the FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 ++
 app/test/meson.build      |   2 +
 app/test/test_fib6_perf.c | 157 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 166 insertions(+)
 create mode 100644 app/test/test_fib6_perf.c
app/test/Makefile +1 -0
index 3a3f920..f792858 100644
@@ -129,6 +129,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib_perf.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6_perf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index 7668203..692b55a 100644
@@ -713,6 +713,12 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB6 perf autotest",
+        "Command": "fib6_perf_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
          "Name":    "Efd perf autotest",
          "Command": "efd_perf_autotest",
          "Func":    default_autotest,
app/test/meson.build +2 -0
index e95e7cb..5942997 100644
@@ -50,6 +50,7 @@ test_sources = files('commands.c',
 	'test_fib.c',
 	'test_fib_perf.c',
 	'test_fib6.c',
+	'test_fib6_perf.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
 	'test_hash.c',
@@ -266,6 +267,7 @@ perf_test_names = [
         'member_perf_autotest',
         'efd_perf_autotest',
         'lpm6_perf_autotest',
+        'fib6_perf_autotest',
         'rcu_qsbr_perf_autotest',
         'red_perf',
         'distributor_perf_autotest',
app/test/test_fib6_perf.c new file +157 -0

157 lines not on this page · raw message

Signature · 1 line
2.7.4
#38 lore raw

Re: [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries

In reply to Vladimir Medvedkin
Quoted 15 lines

-----Original Message-----
From: dev [mailto:[email protected]] On Behalf Of Vladimir Medvedkin

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

Current lpm implementation while provides really good lookup performance has number of problems.
One of them is very low speed for control plane operations such as add or delete a route.
Another disadvantage is fixed number of bits for userdata (24 for v4 and 21 for v6)
Also it is hard to introduce changes in existing LPM code or add new algorithms without breaking ABI.

Quoted 12 lines

This patch series tries to solve this problems by:
Introduce two new libraries - RIB and FIB.
RIB that is Routing Information Base.
It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals (i.e. retrieve existing subroutes for a given prefix). This structure will be used as a control plane helper structure
for FIB implementation.
Also it might be used standalone in other different places such as bitmaps for example.

Great!

Quoted 10 lines

Second library is FIB that is Forwarding Information Base. It represents
dataplane related struct and algorithms for longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future
(for example DXR, poptrie, etc).

The feedback following here is meant as a comment, not an objection. Feel free to ignore!

This FIB library is designed for IP based forwarding only.

How about forwarding based on other criteria?
E.g. the FIB in a standard Ethernet switch is based on VLAN+MAC.

Such a FIB would probably require a different library, based on a hash structure, and would also require a compare-and-set function callable from the data plane in order to provide wire speed learning.

So I suggest that the documentation highlights that this FIB library is for IP based forwarding. Optionally also reconsider the name of the library and its functions, structures etc..

Quoted 10 lines

From our measurements we saw 10x speedup for control plane operations comparing with current LPM library (depending on prefix length distribution)

ToDo:
- introduce new performance measurement app.
- add documentation.
- add support into existing examples (l3fwd)

Med venlig hilsen / kind regards
- Morten Brørup

#39 lore raw

Re: [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries

Hi Brørup,

Quoted 42 lines · Morten Brørup
Quoted 15 lines

-----Original Message-----
From: dev [mailto:[email protected]] On Behalf Of Vladimir Medvedkin

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

Current lpm implementation while provides really good lookup performance has number of problems.
One of them is very low speed for control plane operations such as add or delete a route.
Another disadvantage is fixed number of bits for userdata (24 for v4 and 21 for v6)
Also it is hard to introduce changes in existing LPM code or add new algorithms without breaking ABI.

Quoted 12 lines

This patch series tries to solve this problems by:
Introduce two new libraries - RIB and FIB.
RIB that is Routing Information Base.
It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals (i.e. retrieve existing subroutes for a given prefix). This structure will be used as a control plane helper structure
for FIB implementation.
Also it might be used standalone in other different places such as bitmaps for example.

Great!

Quoted 10 lines

Second library is FIB that is Forwarding Information Base. It represents
dataplane related struct and algorithms for longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future
(for example DXR, poptrie, etc).

The feedback following here is meant as a comment, not an objection. Feel free to ignore!

Quoted 8 lines

This FIB library is designed for IP based forwarding only.

How about forwarding based on other criteria?
E.g. the FIB in a standard Ethernet switch is based on VLAN+MAC.

Such a FIB would probably require a different library, based on a hash structure, and would also require a compare-and-set function callable from the data plane in order to provide wire speed learning.

So I suggest that the documentation highlights that this FIB library is for IP based forwarding. Optionally also reconsider the name of the library and its functions, structures etc..

Thanks for the feedback.

Yes, at the moment FIB has only longest prefix match algorithms. However, it is possible to add different exact match algorithms for VLAN+MAC/MPLS/etc processing.

It is always hard to find proper name for library/function/variable, so if you think that fib name is not relevant feel free to suggest better :)

Quoted 13 lines
Quoted 10 lines

From our measurements we saw 10x speedup for control plane operations
comparing with current LPM library (depending on prefix length distribution)

ToDo:
- introduce new performance measurement app.
- add documentation.
- add support into existing examples (l3fwd)

Med venlig hilsen / kind regards
- Morten Brørup

Signature · 2 lines
Regards,
Vladimir
#40 lore raw

Re: [dpdk-dev] [PATCH v5 00/12] lib: add RIB and FIB liraries

Hi Vladimir,

Quoted 14 lines

-----Original Message-----
From: dev [mailto:[email protected]] On Behalf Of Medvedkin, Vladimir

Hi Brørup,

Quoted 2 lines · Morten Brørup
Quoted 2 lines

-----Original Message-----
From: dev [mailto:[email protected]] On Behalf Of Vladimir

Medvedkin

Quoted 4 lines
Quoted 4 lines

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

[snip]

Quoted 29 lines
Quoted 8 lines
Quoted 8 lines

Second library is FIB that is Forwarding Information Base. It represents
dataplane related struct and algorithms for longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms

in

Quoted 3 lines
Quoted 2 lines

future
(for example DXR, poptrie, etc).

The feedback following here is meant as a comment, not an objection.

Feel free to ignore!

Quoted 7 lines

This FIB library is designed for IP based forwarding only.

How about forwarding based on other criteria?
E.g. the FIB in a standard Ethernet switch is based on VLAN+MAC.

Such a FIB would probably require a different library, based on a

hash structure, and would also require a compare-and-set function callable from the data plane in order to provide wire speed learning.

Quoted 2 lines

So I suggest that the documentation highlights that this FIB library

is for IP based forwarding. Optionally also reconsider the name of the library and its functions, structures etc..

Thanks for the feedback.

Quoted 8 lines

Yes, at the moment FIB has only longest prefix match algorithms. However, it is possible to add different exact match algorithms for VLAN+MAC/MPLS/etc processing.

It is always hard to find proper name for library/function/variable, so if you think that fib name is not relevant feel free to suggest better :)

You can use ip_/ipv4_/ipv6_ somewhere in the common prefix, like the ip_frag library, and unlike many other libraries. :-)

And again: Feel free to ignore!

Quoted 5 lines

--
Regards,
Vladimir

Med venlig hilsen / kind regards
- Morten Brørup

#41 lore raw

v6 cover lib: add RIB and FIB liraries

In reply to Vladimir Medvedkin

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

Current lpm implementation while provides really good lookup performance has number of problems.
One of them is very low speed for control plane operations such as add or delete a route.
Another disadvantage is fixed number of bits for userdata (24 for v4 and 21 for v6)
Also it is hard to introduce changes in existing LPM code or add new algorithms without breaking ABI.

This patch series tries to solve this problems by:
Introduce two new libraries - RIB and FIB.
RIB that is Routing Information Base.
It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals (i.e. retrieve existing subroutes for a given prefix). This structure will be used as a control plane helper structure for FIB implementation.
Also it might be used standalone in other different places such as bitmaps for example.

Second library is FIB that is Forwarding Information Base. It represents dataplane related struct and algorithms for longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future (for example DXR, poptrie, etc).

From our measurements we saw 10x speedup for control plane operations comparing with current LPM library (depending on prefix length distribution)

ToDo:
- introduce new performance measurement app.
- add documentation.
- add support into existing examples (l3fwd)

v6:
Move long-running tests into a pref test section

Vladimir Medvedkin (12):
rib: add RIB library
test/rib: add RIB library autotests
rib: add ipv6 support for RIB
test/rib: add ipv6 support for RIB autotests
fib: add FIB library
fib: add FIB ipv6 support
fib: add DIR24-8 dataplane algorithm
fib: add dataplane algorithm for ipv6 test/fib: add FIB library autotests test/fib: add ipv6 support for FIB autotests test/fib: add FIB library performance autotests test/fib: add FIB library ipv6 performance autotests

 app/test/Makefile                  |   7 +
 app/test/autotest_data.py          |  48 +++
 app/test/meson.build               |  16 +
 app/test/test_fib.c                | 414 ++++++++++++++++++++
 app/test/test_fib6.c               | 423 +++++++++++++++++++++
 app/test/test_fib6_perf.c          | 157 ++++++++
 app/test/test_fib_perf.c           | 411 ++++++++++++++++++++
 app/test/test_rib.c                | 351 +++++++++++++++++
 app/test/test_rib6.c               | 357 +++++++++++++++++
 config/common_base                 |  11 +
 doc/api/doxy-api.conf.in           |   2 +
 lib/Makefile                       |   4 +
 lib/librte_fib/Makefile            |  25 ++
 lib/librte_fib/dir24_8.c           | 737 +++++++++++++++++++++++++++++++++++
 lib/librte_fib/dir24_8.h           |  36 ++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 319 ++++++++++++++++
 lib/librte_fib/rte_fib.h           | 188 +++++++++
 lib/librte_fib/rte_fib6.c          | 322 ++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 193 ++++++++++
 lib/librte_fib/rte_fib_version.map |  23 ++
 lib/librte_fib/trie.c              | 760 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h              |  37 ++
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
 lib/librte_rib/rte_rib.c           | 532 ++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 ++++++++++++++
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 ++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  35 ++
 lib/meson.build                    |   4 +-
 mk/rte.app.mk                      |   2 +
 32 files changed, 6663 insertions(+), 1 deletion(-)
 create mode 100644 app/test/test_fib.c
 create mode 100644 app/test/test_fib6.c
 create mode 100644 app/test/test_fib6_perf.c
 create mode 100644 app/test/test_fib_perf.c
 create mode 100644 app/test/test_rib.c
 create mode 100644 app/test/test_rib6.c
 create mode 100644 lib/librte_fib/Makefile
 create mode 100644 lib/librte_fib/dir24_8.c
 create mode 100644 lib/librte_fib/dir24_8.h
 create mode 100644 lib/librte_fib/meson.build
 create mode 100644 lib/librte_fib/rte_fib.c
 create mode 100644 lib/librte_fib/rte_fib.h
 create mode 100644 lib/librte_fib/rte_fib6.c
 create mode 100644 lib/librte_fib/rte_fib6.h
 create mode 100644 lib/librte_fib/rte_fib_version.map
 create mode 100644 lib/librte_fib/trie.c
 create mode 100644 lib/librte_fib/trie.h
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib6.c
 create mode 100644 lib/librte_rib/rte_rib6.h
 create mode 100644 lib/librte_rib/rte_rib_version.map
Signature · 1 line
2.7.4
#42 lore raw

PATCH v6 1/12 rib: add RIB library

Add RIB (Routing Information Base) library. This library implements an IPv4 routing table optimized for control plane operations. It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals
(i.e. retrieve existing subroutes for a giver prefix). This structure will be used as a control plane helper structure for FIB implementation. Also it might be used standalone in other different places such as bitmaps for example.
Internal implementation is level compressed binary trie.

---
 config/common_base                 |   5 +
 doc/api/doxy-api.conf.in           |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
 lib/librte_rib/rte_rib.c           | 532 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 +++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  20 ++
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 10 files changed, 872 insertions(+), 1 deletion(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map
config/common_base +5 -0
index 8ef75c2..5a9d4c3 100644
@@ -894,6 +894,11 @@ CONFIG_RTE_LIBRTE_RCU=y
 CONFIG_RTE_LIBRTE_RCU_DEBUG=n
 
 #
+# Compile librte_rib
+#
+CONFIG_RTE_LIBRTE_RIB=y
+
+#
 # Compile librte_lpm
 #
 CONFIG_RTE_LIBRTE_LPM=y
doc/api/doxy-api.conf.in +1 -0
index 908cee8..3ec012d 100644
@@ -54,6 +54,7 @@ INPUT                   = @TOPDIR@/doc/api/doxy-api-index.md \
                           @TOPDIR@/lib/librte_rawdev \
                           @TOPDIR@/lib/librte_rcu \
                           @TOPDIR@/lib/librte_reorder \
+                          @TOPDIR@/lib/librte_rib \
                           @TOPDIR@/lib/librte_ring \
                           @TOPDIR@/lib/librte_sched \
                           @TOPDIR@/lib/librte_security \
lib/Makefile +2 -0
index 41c463d..aa5ee1e 100644
@@ -51,6 +51,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_HASH) += librte_hash
 DEPDIRS-librte_hash := librte_eal librte_ring
 DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
+DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib
+DEPDIRS-librte_rib := librte_eal librte_mempool
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
 DEPDIRS-librte_lpm := librte_eal librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
lib/librte_rib/Makefile new file +25 -0
new file mode 100644
index 0000000..79f259a
@@ -0,0 +1,25 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# Copyright(c) 2019 Intel Corporation
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_rib.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+CFLAGS += -DALLOW_EXPERIMENTAL_API
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_rib_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_rib/meson.build new file +8 -0
new file mode 100644
index 0000000..e7b8920
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# Copyright(c) 2019 Intel Corporation
+
+allow_experimental_apis = true
+sources = files('rte_rib.c')
+headers = files('rte_rib.h')
+deps += ['mempool']
lib/librte_rib/rte_rib.c new file +532 -0

532 lines not on this page · raw message

lib/librte_rib/rte_rib.h new file +277 -0

277 lines not on this page · raw message

lib/librte_rib/rte_rib_version.map new file +20 -0
new file mode 100644
index 0000000..1432a22
@@ -0,0 +1,20 @@
+EXPERIMENTAL {
+	global:
+
+	rte_rib_create;
+	rte_rib_find_existing;
+	rte_rib_free;
+	rte_rib_get_depth;
+	rte_rib_get_ext;
+	rte_rib_get_ip;
+	rte_rib_get_nh;
+	rte_rib_get_nxt;
+	rte_rib_insert;
+	rte_rib_lookup;
+	rte_rib_lookup_parent;
+	rte_rib_lookup_exact;
+	rte_rib_set_nh;
+	rte_rib_remove;
+
+	local: *;
+};
lib/meson.build +1 -1
index e5ff838..d7f2a04 100644
@@ -22,7 +22,7 @@ libraries = [
 	'gro', 'gso', 'ip_frag', 'jobstats',
 	'kni', 'latencystats', 'lpm', 'member',
 	'power', 'pdump', 'rawdev',
-	'rcu', 'reorder', 'sched', 'security', 'stack', 'vhost',
+	'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost',
 	# ipsec lib depends on net, crypto and security
 	'ipsec',
 	# add pkt framework libs which use other libs from above
mk/rte.app.mk +1 -0
index ba5c39e..4517874 100644
@@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP)          += -lrte_pdump
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR)    += -lrte_distributor
 _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG)        += -lrte_ip_frag
 _LDLIBS-$(CONFIG_RTE_LIBRTE_METER)          += -lrte_meter
+_LDLIBS-$(CONFIG_RTE_LIBRTE_RIB)            += -lrte_rib
 _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM)            += -lrte_lpm
 _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL)            += -lrte_acl
 _LDLIBS-$(CONFIG_RTE_LIBRTE_TELEMETRY)      += --no-as-needed
Signature · 1 line
2.7.4
#43 lore raw

PATCH v6 2/12 test/rib: add RIB library autotests

In reply to Vladimir Medvedkin

Functional tests for the new RIB library.

---
 app/test/Makefile         |   2 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   3 +
 app/test/test_rib.c       | 351 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 362 insertions(+)
 create mode 100644 app/test/test_rib.c
app/test/Makefile +2 -0
index 26ba6fe..5bd8487 100644
@@ -124,6 +124,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_multiwriter.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
+
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm6.c
app/test/autotest_data.py +6 -0
index 7405149..3c3b806 100644
@@ -111,6 +111,12 @@
         "Report":  None,
     },
     {
+        "Name":    "RIB autotest",
+        "Command": "rib_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +3 -0
index ec40943..98524e1 100644
@@ -99,6 +99,7 @@ test_sources = files('commands.c',
 	'test_reciprocal_division_perf.c',
 	'test_red.c',
 	'test_reorder.c',
+	'test_rib.c',
 	'test_ring.c',
 	'test_ring_perf.c',
 	'test_rwlock.c',
@@ -147,6 +148,7 @@ test_deps = ['acl',
 	'rawdev',
 	'rcu',
 	'reorder',
+	'rib',
 	'ring',
 	'stack',
 	'timer'
@@ -197,6 +199,7 @@ fast_test_names = [
         'prefetch_autotest',
         'rcu_qsbr_autotest',
         'red_autotest',
+        'rib_autotest',
         'ring_autotest',
         'ring_pmd_autotest',
         'rwlock_test1_autotest',
app/test/test_rib.c new file +351 -0

351 lines not on this page · raw message

Signature · 1 line
2.7.4
#44 lore raw

PATCH v6 3/12 rib: add ipv6 support for RIB

In reply to Vladimir Medvedkin

Extend RIB library with ipv6 support.

---
 lib/librte_rib/Makefile            |   4 +-
 lib/librte_rib/meson.build         |   4 +-
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 +++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  15 +
 5 files changed, 951 insertions(+), 4 deletions(-)
 create mode 100644 lib/librte_rib/rte_rib6.c
 create mode 100644 lib/librte_rib/rte_rib6.h
lib/librte_rib/Makefile +2 -2
index 79f259a..6d861ad 100644
@@ -17,9 +17,9 @@ EXPORT_MAP := rte_rib_version.map
 LIBABIVER := 1
 
 # all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c rte_rib6.c
 
 # install this header file
-SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h rte_rib6.h
 
 include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_rib/meson.build +2 -2
index e7b8920..46a1c0c 100644
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_rib.c')
-headers = files('rte_rib.h')
+sources = files('rte_rib.c', 'rte_rib6.c')
+headers = files('rte_rib.h', 'rte_rib6.h')
 deps += ['mempool']
lib/librte_rib/rte_rib6.c new file +598 -0

598 lines not on this page · raw message

lib/librte_rib/rte_rib6.h new file +334 -0

334 lines not on this page · raw message

lib/librte_rib/rte_rib_version.map +15 -0
index 1432a22..9b6161a 100644
@@ -16,5 +16,20 @@ EXPERIMENTAL {
 	rte_rib_set_nh;
 	rte_rib_remove;
 
+	rte_rib6_create;
+	rte_rib6_find_existing;
+	rte_rib6_free;
+	rte_rib6_get_depth;
+	rte_rib6_get_ext;
+	rte_rib6_get_ip;
+	rte_rib6_get_nh;
+	rte_rib6_get_nxt;
+	rte_rib6_insert;
+	rte_rib6_lookup;
+	rte_rib6_lookup_parent;
+	rte_rib6_lookup_exact;
+	rte_rib6_set_nh;
+	rte_rib6_remove;
+
 	local: *;
 };
Signature · 1 line
2.7.4
#45 lore raw

PATCH v6 4/12 test/rib: add ipv6 support for RIB autotests

In reply to Vladimir Medvedkin

Functional tests for RIB6.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   2 +
 app/test/test_rib6.c      | 357 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 366 insertions(+)
 create mode 100644 app/test/test_rib6.c
app/test/Makefile +1 -0
index 5bd8487..4638426 100644
@@ -125,6 +125,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index 3c3b806..f35b3cc 100644
@@ -117,6 +117,12 @@
         "Report":  None,
     },
     {
+        "Name":    "RIB6 autotest",
+        "Command": "rib6_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +2 -0
index 98524e1..49c1de0 100644
@@ -100,6 +100,7 @@ test_sources = files('commands.c',
 	'test_red.c',
 	'test_reorder.c',
 	'test_rib.c',
+	'test_rib6.c',
 	'test_ring.c',
 	'test_ring_perf.c',
 	'test_rwlock.c',
@@ -200,6 +201,7 @@ fast_test_names = [
         'rcu_qsbr_autotest',
         'red_autotest',
         'rib_autotest',
+        'rib6_autotest',
         'ring_autotest',
         'ring_pmd_autotest',
         'rwlock_test1_autotest',
app/test/test_rib6.c new file +357 -0

357 lines not on this page · raw message

Signature · 1 line
2.7.4
#46 lore raw

PATCH v6 5/12 fib: add FIB library

In reply to Vladimir Medvedkin

Add FIB (Forwarding Information Base) library. This library implements a dataplane structures and algorithms designed for fast longest prefix match.
Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks.
Initial version provides two implementations for both ipv4 and ipv6:
dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future (for example DXR, poptrie, etc).

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf.in           |   1 +
 lib/Makefile                       |   2 +
 lib/librte_fib/Makefile            |  25 +++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 305 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/rte_fib.h           | 173 +++++++++++++++++++++
 lib/librte_fib/rte_fib_version.map |  14 ++
 lib/meson.build                    |   2 +
 mk/rte.app.mk                      |   1 +
 10 files changed, 537 insertions(+)
 create mode 100644 lib/librte_fib/Makefile
 create mode 100644 lib/librte_fib/meson.build
 create mode 100644 lib/librte_fib/rte_fib.c
 create mode 100644 lib/librte_fib/rte_fib.h
 create mode 100644 lib/librte_fib/rte_fib_version.map
config/common_base +6 -0
index 5a9d4c3..0f32ad7 100644
@@ -899,6 +899,12 @@ CONFIG_RTE_LIBRTE_RCU_DEBUG=n
 CONFIG_RTE_LIBRTE_RIB=y
 
 #
+# Compile librte_fib
+#
+CONFIG_RTE_LIBRTE_FIB=y
+CONFIG_RTE_LIBRTE_FIB_DEBUG=n
+
+#
 # Compile librte_lpm
 #
 CONFIG_RTE_LIBRTE_LPM=y
doc/api/doxy-api.conf.in +1 -0
index 3ec012d..6fd3b51 100644
@@ -30,6 +30,7 @@ INPUT                   = @TOPDIR@/doc/api/doxy-api-index.md \
                           @TOPDIR@/lib/librte_efd \
                           @TOPDIR@/lib/librte_ethdev \
                           @TOPDIR@/lib/librte_eventdev \
+                          @TOPDIR@/lib/librte_fib \
                           @TOPDIR@/lib/librte_flow_classify \
                           @TOPDIR@/lib/librte_gro \
                           @TOPDIR@/lib/librte_gso \
lib/Makefile +2 -0
index aa5ee1e..5d04ab9 100644
@@ -53,6 +53,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib
 DEPDIRS-librte_rib := librte_eal librte_mempool
+DIRS-$(CONFIG_RTE_LIBRTE_FIB) += librte_fib
+DEPDIRS-librte_fib := librte_eal librte_rib
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
 DEPDIRS-librte_lpm := librte_eal librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
lib/librte_fib/Makefile new file +25 -0
new file mode 100644
index 0000000..7362f68
@@ -0,0 +1,25 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# 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)
+CFLAGS += -DALLOW_EXPERIMENTAL_API
+LDLIBS += -lrte_eal -lrte_rib
+
+EXPORT_MAP := rte_fib_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_fib/meson.build new file +8 -0
new file mode 100644
index 0000000..6b72360
@@ -0,0 +1,8 @@
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+# Copyright(c) 2019 Intel Corporation
+
+allow_experimental_apis = true
+sources = files('rte_fib.c')
+headers = files('rte_fib.h')
+deps += ['rib']
lib/librte_fib/rte_fib.c new file +305 -0

305 lines not on this page · raw message

lib/librte_fib/rte_fib.h new file +173 -0

173 lines not on this page · raw message

lib/librte_fib/rte_fib_version.map new file +14 -0
new file mode 100644
index 0000000..776195f
@@ -0,0 +1,14 @@
+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;
+
+	local: *;
+};
lib/meson.build +2 -0
index d7f2a04..9700433 100644
@@ -25,6 +25,8 @@ libraries = [
 	'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost',
 	# ipsec lib depends on net, crypto and security
 	'ipsec',
+	#fib lib depends on rib
+	'fib',
 	# add pkt framework libs which use other libs from above
 	'port', 'table', 'pipeline',
 	# flow_classify lib depends on pkt framework table lib
mk/rte.app.mk +1 -0
index 4517874..7ce87e7 100644
@@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP)          += -lrte_pdump
 _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR)    += -lrte_distributor
 _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG)        += -lrte_ip_frag
 _LDLIBS-$(CONFIG_RTE_LIBRTE_METER)          += -lrte_meter
+_LDLIBS-$(CONFIG_RTE_LIBRTE_FIB)            += -lrte_fib
 _LDLIBS-$(CONFIG_RTE_LIBRTE_RIB)            += -lrte_rib
 _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM)            += -lrte_lpm
 _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL)            += -lrte_acl
Signature · 1 line
2.7.4
#47 lore raw

PATCH v6 6/12 fib: add FIB ipv6 support

In reply to Vladimir Medvedkin

Add FIB library support for IPv6.
It implements a dataplane structures and algorithms designed for fast IPv6 longest prefix match.

---
 lib/librte_fib/Makefile            |   4 +-
 lib/librte_fib/meson.build         |   4 +-
 lib/librte_fib/rte_fib6.c          | 308 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 179 +++++++++++++++++++++
 lib/librte_fib/rte_fib_version.map |   9 ++
 5 files changed, 500 insertions(+), 4 deletions(-)
 create mode 100644 lib/librte_fib/rte_fib6.c
 create mode 100644 lib/librte_fib/rte_fib6.h
lib/librte_fib/Makefile +2 -2
index 7362f68..0bdf55b 100644
@@ -17,9 +17,9 @@ EXPORT_MAP := rte_fib_version.map
 LIBABIVER := 1
 
 # all source are stored in SRCS-y
-SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c
 
 # install this header file
-SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h
 
 include $(RTE_SDK)/mk/rte.lib.mk
lib/librte_fib/meson.build +2 -2
index 6b72360..32dfdec 100644
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_fib.c')
-headers = files('rte_fib.h')
+sources = files('rte_fib.c', 'rte_fib6.c')
+headers = files('rte_fib.h', 'rte_fib6.h')
 deps += ['rib']
lib/librte_fib/rte_fib6.c new file +308 -0

308 lines not on this page · raw message

lib/librte_fib/rte_fib6.h new file +179 -0

179 lines not on this page · raw message

lib/librte_fib/rte_fib_version.map +9 -0
index 776195f..9527417 100644
@@ -10,5 +10,14 @@ EXPERIMENTAL {
 	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: *;
 };
Signature · 1 line
2.7.4
#48 lore raw

PATCH v6 7/12 fib: add DIR24-8 dataplane algorithm

In reply to Vladimir Medvedkin

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

---
 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
lib/librte_fib/Makefile +1 -1
index 0bdf55b..67fde9a 100644
@@ -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
lib/librte_fib/dir24_8.c new file +737 -0

737 lines not on this page · raw message

lib/librte_fib/dir24_8.h new file +36 -0
new file mode 100644
index 0000000..34ddb91
@@ -0,0 +1,36 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ * 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_ */
+
lib/librte_fib/meson.build +1 -1
index 32dfdec..c63cac8 100644
@@ -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']
lib/librte_fib/rte_fib.c +14 -0
index 4d8a771..e090808 100644
@@ -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;
 	}
lib/librte_fib/rte_fib.h +16 -1
index 096cc92..d06c5ef 100644
@@ -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
  *
Signature · 1 line
2.7.4
#49 lore raw

PATCH v6 8/12 fib: add dataplane algorithm for ipv6

In reply to Vladimir Medvedkin

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

---
 lib/librte_fib/Makefile    |   2 +-
 lib/librte_fib/meson.build |   2 +-
 lib/librte_fib/rte_fib6.c  |  14 +
 lib/librte_fib/rte_fib6.h  |  14 +
 lib/librte_fib/trie.c      | 760 +++++++++++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h      |  37 +++
 6 files changed, 827 insertions(+), 2 deletions(-)
 create mode 100644 lib/librte_fib/trie.c
 create mode 100644 lib/librte_fib/trie.h
lib/librte_fib/Makefile +1 -1
index 67fde9a..4abd80b 100644
@@ -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 dir24_8.c
+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
lib/librte_fib/meson.build +1 -1
index c63cac8..e2c6f44 100644
@@ -3,6 +3,6 @@
 # Copyright(c) 2019 Intel Corporation
 
 allow_experimental_apis = true
-sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c')
+sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'trie.c')
 headers = files('rte_fib.h', 'rte_fib6.h')
 deps += ['rib']
lib/librte_fib/rte_fib6.c +14 -0
index 9f00a80..354227d 100644
@@ -17,6 +17,8 @@
 #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",
@@ -92,12 +94,22 @@ 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;
 	}
@@ -260,6 +272,8 @@ free_dataplane(struct rte_fib6 *fib)
 	switch (fib->type) {
 	case RTE_FIB6_DUMMY:
 		return;
+	case RTE_FIB6_TRIE:
+		trie_free(fib->dp);
 	default:
 		return;
 	}
lib/librte_fib/rte_fib6.h +14 -0
index 3322123..4268704 100644
@@ -19,10 +19,12 @@
 #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
 };
 
@@ -40,12 +42,24 @@ enum rte_fib6_op {
 	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;
+	};
 };
 
 /**
lib/librte_fib/trie.c new file +760 -0

760 lines not on this page · raw message

lib/librte_fib/trie.h new file +37 -0
new file mode 100644
index 0000000..7762fb9
@@ -0,0 +1,37 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ * 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_ */
+
Signature · 1 line
2.7.4
#50 lore raw

PATCH v6 9/12 test/fib: add FIB library autotests

In reply to Vladimir Medvedkin

Functional tests for the new FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |  12 ++
 app/test/meson.build      |   4 +
 app/test/test_fib.c       | 414 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 431 insertions(+)
 create mode 100644 app/test/test_fib.c
app/test/Makefile +1 -0
index 4638426..b67ca16 100644
@@ -126,6 +126,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +12 -0
index f35b3cc..18a8595 100644
@@ -123,6 +123,18 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB autotest",
+        "Command": "fib_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
+        "Name":    "FIB slow autotest",
+        "Command": "fib_slow_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +4 -0
index 49c1de0..c5d62de 100644
@@ -47,6 +47,7 @@ test_sources = files('commands.c',
 	'test_eventdev.c',
 	'test_external_mem.c',
 	'test_fbarray.c',
+	'test_fib.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
 	'test_hash.c',
@@ -137,6 +138,7 @@ test_deps = ['acl',
 	'efd',
 	'ethdev',
 	'eventdev',
+	'fib',
 	'flow_classify',
 	'hash',
 	'ipsec',
@@ -180,6 +182,7 @@ fast_test_names = [
         'eal_fs_autotest',
         'errno_autotest',
         'event_ring_autotest',
+        'fib_autotest',
         'func_reentrancy_autotest',
         'flow_classify_autotest',
         'hash_autotest',
@@ -250,6 +253,7 @@ perf_test_names = [
         'reciprocal_division',
         'reciprocal_division_perf',
         'lpm_perf_autotest',
+        'fib_slow_autotest',
         'red_all',
         'barrier_autotest',
         'hash_multiwriter_autotest',
app/test/test_fib.c new file +414 -0

414 lines not on this page · raw message

Signature · 1 line
2.7.4
#51 lore raw

PATCH v6 10/12 test/fib: add ipv6 support for FIB autotests

In reply to Vladimir Medvedkin

Functional ipv6 tests for the FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |  12 ++
 app/test/meson.build      |   3 +
 app/test/test_fib6.c      | 423 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 439 insertions(+)
 create mode 100644 app/test/test_fib6.c
app/test/Makefile +1 -0
index b67ca16..c230dbf 100644
@@ -127,6 +127,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +12 -0
index 18a8595..5c220db 100644
@@ -135,6 +135,18 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB6 autotest",
+        "Command": "fib6_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
+        "Name":    "FIB6 slow autotest",
+        "Command": "fib6_slow_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
         "Name":    "Memcpy autotest",
         "Command": "memcpy_autotest",
         "Func":    default_autotest,
app/test/meson.build +3 -0
index c5d62de..0b83ada 100644
@@ -48,6 +48,7 @@ test_sources = files('commands.c',
 	'test_external_mem.c',
 	'test_fbarray.c',
 	'test_fib.c',
+	'test_fib6.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
 	'test_hash.c',
@@ -183,6 +184,7 @@ fast_test_names = [
         'errno_autotest',
         'event_ring_autotest',
         'fib_autotest',
+        'fib6_autotest',
         'func_reentrancy_autotest',
         'flow_classify_autotest',
         'hash_autotest',
@@ -263,6 +265,7 @@ perf_test_names = [
         'member_perf_autotest',
         'efd_perf_autotest',
         'lpm6_perf_autotest',
+        'fib6_slow_autotest',
         'rcu_qsbr_perf_autotest',
         'red_perf',
         'distributor_perf_autotest',
app/test/test_fib6.c new file +423 -0

423 lines not on this page · raw message

Signature · 1 line
2.7.4
#52 lore raw

PATCH v6 11/12 test/fib: add FIB library performance autotests

In reply to Vladimir Medvedkin

Performance tests for the new FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 +
 app/test/meson.build      |   2 +
 app/test/test_fib_perf.c  | 411 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 420 insertions(+)
 create mode 100644 app/test/test_fib_perf.c
app/test/Makefile +1 -0
index c230dbf..3a3f920 100644
@@ -128,6 +128,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c
 SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib_perf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index 5c220db..0783979 100644
@@ -719,6 +719,12 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB perf autotest",
+        "Command": "fib_perf_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
          "Name":    "Efd perf autotest",
          "Command": "efd_perf_autotest",
          "Func":    default_autotest,
app/test/meson.build +2 -0
index 0b83ada..929883a 100644
@@ -48,6 +48,7 @@ test_sources = files('commands.c',
 	'test_external_mem.c',
 	'test_fbarray.c',
 	'test_fib.c',
+	'test_fib_perf.c',
 	'test_fib6.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
@@ -256,6 +257,7 @@ perf_test_names = [
         'reciprocal_division_perf',
         'lpm_perf_autotest',
         'fib_slow_autotest',
+        'fib_perf_autotest',
         'red_all',
         'barrier_autotest',
         'hash_multiwriter_autotest',
app/test/test_fib_perf.c new file +411 -0

411 lines not on this page · raw message

Signature · 1 line
2.7.4
#53 lore raw

PATCH v6 12/12 test/fib: add FIB library ipv6 performance autotests

In reply to Vladimir Medvedkin

Performance ipv6 tests for the FIB library.

---
 app/test/Makefile         |   1 +
 app/test/autotest_data.py |   6 ++
 app/test/meson.build      |   2 +
 app/test/test_fib6_perf.c | 157 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 166 insertions(+)
 create mode 100644 app/test/test_fib6_perf.c
app/test/Makefile +1 -0
index 3a3f920..f792858 100644
@@ -129,6 +129,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c
 SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib_perf.c
+SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6_perf.c
 
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c
 SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c
app/test/autotest_data.py +6 -0
index 0783979..97e4423 100644
@@ -725,6 +725,12 @@
         "Report":  None,
     },
     {
+        "Name":    "FIB6 perf autotest",
+        "Command": "fib6_perf_autotest",
+        "Func":    default_autotest,
+        "Report":  None,
+    },
+    {
          "Name":    "Efd perf autotest",
          "Command": "efd_perf_autotest",
          "Func":    default_autotest,
app/test/meson.build +2 -0
index 929883a..42664d8 100644
@@ -50,6 +50,7 @@ test_sources = files('commands.c',
 	'test_fib.c',
 	'test_fib_perf.c',
 	'test_fib6.c',
+	'test_fib6_perf.c',
 	'test_func_reentrancy.c',
 	'test_flow_classify.c',
 	'test_hash.c',
@@ -268,6 +269,7 @@ perf_test_names = [
         'efd_perf_autotest',
         'lpm6_perf_autotest',
         'fib6_slow_autotest',
+        'fib6_perf_autotest',
         'rcu_qsbr_perf_autotest',
         'red_perf',
         'distributor_perf_autotest',
app/test/test_fib6_perf.c new file +157 -0

157 lines not on this page · raw message

Signature · 1 line
2.7.4
#54 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

In reply to Vladimir Medvedkin

01/11/2019 16:21, Vladimir Medvedkin:

Quoted 28 lines

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

 app/test/Makefile                  |   7 +
 app/test/autotest_data.py          |  48 +++
 app/test/meson.build               |  16 +
 app/test/test_fib.c                | 414 ++++++++++++++++++++
 app/test/test_fib6.c               | 423 +++++++++++++++++++++
 app/test/test_fib6_perf.c          | 157 ++++++++
 app/test/test_fib_perf.c           | 411 ++++++++++++++++++++
 app/test/test_rib.c                | 351 +++++++++++++++++
 app/test/test_rib6.c               | 357 +++++++++++++++++
 config/common_base                 |  11 +
 doc/api/doxy-api.conf.in           |   2 +
 lib/Makefile                       |   4 +
 lib/librte_fib/Makefile            |  25 ++
 lib/librte_fib/dir24_8.c           | 737 +++++++++++++++++++++++++++++++++++
 lib/librte_fib/dir24_8.h           |  36 ++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 319 ++++++++++++++++
 lib/librte_fib/rte_fib.h           | 188 +++++++++
 lib/librte_fib/rte_fib6.c          | 322 ++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 193 ++++++++++
 lib/librte_fib/rte_fib_version.map |  23 ++
 lib/librte_fib/trie.c              | 760 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h              |  37 ++
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
Quoted 8 lines
 lib/librte_rib/rte_rib.c           | 532 ++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 ++++++++++++++
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 ++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  35 ++
 lib/meson.build                    |   4 +-
 mk/rte.app.mk                      |   2 +
 32 files changed, 6663 insertions(+), 1 deletion(-)

You forgot to update MAINTAINERS and the release notes. I did it while merging.

Applied, thanks

#55 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

Quoted 39 lines · Thomas Monjalon

01/11/2019 16:21, Vladimir Medvedkin:

Quoted 28 lines

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

 app/test/Makefile                  |   7 +
 app/test/autotest_data.py          |  48 +++
 app/test/meson.build               |  16 +
 app/test/test_fib.c                | 414 ++++++++++++++++++++
 app/test/test_fib6.c               | 423 +++++++++++++++++++++
 app/test/test_fib6_perf.c          | 157 ++++++++
 app/test/test_fib_perf.c           | 411 ++++++++++++++++++++
 app/test/test_rib.c                | 351 +++++++++++++++++
 app/test/test_rib6.c               | 357 +++++++++++++++++
 config/common_base                 |  11 +
 doc/api/doxy-api.conf.in           |   2 +
 lib/Makefile                       |   4 +
 lib/librte_fib/Makefile            |  25 ++
 lib/librte_fib/dir24_8.c           | 737 +++++++++++++++++++++++++++++++++++
 lib/librte_fib/dir24_8.h           |  36 ++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 319 ++++++++++++++++
 lib/librte_fib/rte_fib.h           | 188 +++++++++
 lib/librte_fib/rte_fib6.c          | 322 ++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 193 ++++++++++
 lib/librte_fib/rte_fib_version.map |  23 ++
 lib/librte_fib/trie.c              | 760 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h              |  37 ++
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
Quoted 8 lines
 lib/librte_rib/rte_rib.c           | 532 ++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 ++++++++++++++
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 ++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  35 ++
 lib/meson.build                    |   4 +-
 mk/rte.app.mk                      |   2 +
 32 files changed, 6663 insertions(+), 1 deletion(-)
Quoted 4 lines

You forgot to update MAINTAINERS and the release notes. I did it while merging.

Applied, thanks

The added tests are timeouting:
https://travis-ci.com/DPDK/dpdk/jobs/253293904
47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s
48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s

Signature · 1 line
David Marchand
#56 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

06/11/2019 06:50, David Marchand:

Quoted 7 lines · Thomas Monjalon
Quoted 1 line

Applied, thanks

The added tests are timeouting:
https://travis-ci.com/DPDK/dpdk/jobs/253293904
47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s
48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s

Vladimir, the slow test were supposed to be moved out of fast tests. Please can you fix it quickly?

#57 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

Hi Thomas,

-----Original Message-----
From: Thomas Monjalon <[email protected]>
Sent: Wednesday, November 6, 2019 7:51 AM
To: Medvedkin, Vladimir <[email protected]>
Cc: David Marchand <[email protected]>; dev <[email protected]>; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Aaron Conole <[email protected]>
Subject: Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

06/11/2019 06:50, David Marchand:

Quoted 7 lines · Thomas Monjalon
Quoted 1 line

Applied, thanks

The added tests are timeouting:
https://travis-ci.com/DPDK/dpdk/jobs/253293904
47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s
48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s

Vladimir, the slow test were supposed to be moved out of fast tests. Please can you fix it quickly?

Yes, I'll send a fix now.
In v6 I split only fib_autotests, rib_autotests was not so slow in our CI.

#58 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

06/11/2019 12:53, Medvedkin, Vladimir:

Quoted 10 lines

From: Thomas Monjalon <[email protected]>

Quoted 9 lines

06/11/2019 06:50, David Marchand:

Quoted 7 lines · Thomas Monjalon
Quoted 1 line

Applied, thanks

The added tests are timeouting:
https://travis-ci.com/DPDK/dpdk/jobs/253293904
47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s
48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s

Quoted 5 lines
Quoted 2 lines

Vladimir, the slow test were supposed to be moved out of fast tests. Please can you fix it quickly?

Yes, I'll send a fix now.
In v6 I split only fib_autotests, rib_autotests was not so slow in our CI.

The goal is to have fast tests that developers can run frequently without being annoyed.
I think the whole run should be below a minute.
It means a single test case should not exceed one second ideally.

Aaron, we should make a status about test duration, agree on a policy and make a plan to apply such policy.

#59 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

Quoted 17 lines · Thomas Monjalon

06/11/2019 12:53, Medvedkin, Vladimir:

Quoted 10 lines

From: Thomas Monjalon <[email protected]>

Quoted 9 lines

06/11/2019 06:50, David Marchand:

Quoted 7 lines · Thomas Monjalon
Quoted 1 line

Applied, thanks

The added tests are timeouting:
https://travis-ci.com/DPDK/dpdk/jobs/253293904
47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s
48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s

Quoted 5 lines
Quoted 2 lines

Vladimir, the slow test were supposed to be moved out of fast tests. Please can you fix it quickly?

Yes, I'll send a fix now.
In v6 I split only fib_autotests, rib_autotests was not so slow in our CI.

Quoted 7 lines

The goal is to have fast tests that developers can run frequently without being annoyed.
I think the whole run should be below a minute.
It means a single test case should not exceed one second ideally.

Aaron, we should make a status about test duration, agree on a policy and make a plan to apply such policy.

Agreed. I'll write something up.

#60 lore raw

Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

In reply to David Marchand

Hi David,

-----Original Message-----
From: David Marchand <[email protected]>
Sent: Wednesday, November 6, 2019 5:51 AM
To: Thomas Monjalon <[email protected]>; Medvedkin, Vladimir <[email protected]>
Cc: dev <[email protected]>; Richardson, Bruce <[email protected]>; Ananyev, Konstantin <[email protected]>; Aaron Conole <[email protected]>
Subject: Re: [dpdk-dev] [PATCH v6 00/12] lib: add RIB and FIB liraries

Quoted 39 lines · Thomas Monjalon

01/11/2019 16:21, Vladimir Medvedkin:

Quoted 28 lines

This is heavily reworked version of previous RIB library series:
https://mails.dpdk.org/archives/dev/2018-April/099492.html

 app/test/Makefile                  |   7 +
 app/test/autotest_data.py          |  48 +++
 app/test/meson.build               |  16 +
 app/test/test_fib.c                | 414 ++++++++++++++++++++
 app/test/test_fib6.c               | 423 +++++++++++++++++++++
 app/test/test_fib6_perf.c          | 157 ++++++++
 app/test/test_fib_perf.c           | 411 ++++++++++++++++++++
 app/test/test_rib.c                | 351 +++++++++++++++++
 app/test/test_rib6.c               | 357 +++++++++++++++++
 config/common_base                 |  11 +
 doc/api/doxy-api.conf.in           |   2 +
 lib/Makefile                       |   4 +
 lib/librte_fib/Makefile            |  25 ++
 lib/librte_fib/dir24_8.c           | 737 +++++++++++++++++++++++++++++++++++
 lib/librte_fib/dir24_8.h           |  36 ++
 lib/librte_fib/meson.build         |   8 +
 lib/librte_fib/rte_fib.c           | 319 ++++++++++++++++
 lib/librte_fib/rte_fib.h           | 188 +++++++++
 lib/librte_fib/rte_fib6.c          | 322 ++++++++++++++++
 lib/librte_fib/rte_fib6.h          | 193 ++++++++++
 lib/librte_fib/rte_fib_version.map |  23 ++
 lib/librte_fib/trie.c              | 760 +++++++++++++++++++++++++++++++++++++
 lib/librte_fib/trie.h              |  37 ++
 lib/librte_rib/Makefile            |  25 ++
 lib/librte_rib/meson.build         |   8 +
Quoted 8 lines
 lib/librte_rib/rte_rib.c           | 532 ++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 277 ++++++++++++++
 lib/librte_rib/rte_rib6.c          | 598 +++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib6.h          | 334 ++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  35 ++
 lib/meson.build                    |   4 +-
 mk/rte.app.mk                      |   2 +
 32 files changed, 6663 insertions(+), 1 deletion(-)
Quoted 4 lines

You forgot to update MAINTAINERS and the release notes. I did it while merging.

Applied, thanks

The added tests are timeouting:
https://travis-ci.com/DPDK/dpdk/jobs/253293904
47/86 DPDK:fast-tests / rib_autotest TIMEOUT 30.01 s
48/86 DPDK:fast-tests / rib6_autotest TIMEOUT 30.01 s

Oh, ok, I'll send fix today. On my board these tests run in less than 10 seconds, and our CI runs these tests faster, so I split only really slow FIB tests. I'll send fixes asap.

Signature · 1 line
David Marchand