Skip to contentSkip to conversation

lib/rib: Add Routing Information Base library

PATCH Superseded Medvedkin Vladimir 2 participants 11 messages Feb 21, 2018 – Mar 29, 2018 Library code

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v2 cover lib/rib: Add Routing Information Base library

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

Medvedkin Vladimir (2):
Add RIB library
Add autotests for RIB library

 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 +++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 test/test/Makefile                 |   5 +
 test/test/test_rib.c               | 330 +++++++++++++++++++++++
 test/test/test_rib_generate_rt.c   | 297 +++++++++++++++++++++
 test/test/test_rib_generate_rt.h   |  38 +++
 test/test/test_rib_lpm_comp.c      | 187 +++++++++++++
 test/test/test_rib_perf.c          | 163 ++++++++++++
 16 files changed, 2516 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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.9.1
#1 lore raw

PATCH v2 1/2 Add RIB library

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.
- For dir24_8 implementation it is possible to remove rte_lpm_tbl_entry.depth field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- 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.

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 +++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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
config/common_base +6 -0
index ad03cf4..aceeff5 100644
@@ -679,6 +679,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 cda52fd..8e4f969 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 ec965a6..7f2323a 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
 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 +22 -0
new file mode 100644
index 0000000..cb97f02
@@ -0,0 +1,22 @@
+# 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)
+
+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/rte_dir24_8.c new file +482 -0

482 lines not on this page · raw message

lib/librte_rib/rte_dir24_8.h new file +116 -0

116 lines not on this page · raw message

lib/librte_rib/rte_rib.c new file +526 -0

526 lines not on this page · raw message

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

322 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: *;
+};
mk/rte.app.mk +1 -0
index 3eb41d1..4708aa4 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.9.1
#2 lore raw

Re: [PATCH v2 1/2] Add RIB library

Quoted 30 lines · Medvedkin Vladimir

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.
- For dir24_8 implementation it is possible to remove rte_lpm_tbl_entry.depth field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- 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.

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 +++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
Quoted 9 lines
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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

First pass review comments. For now just reviewed the main public header file rte_rib.h. Later reviews will cover the other files as best I can.

/Bruce

<snip>

Quoted 17 lines
lib/librte_rib/rte_rib.h new file +11 -0
new file mode 100644
index 0000000..6eac8fb
@@ -0,0 +1,322 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _RTE_RIB_H_
+#define _RTE_RIB_H_
+
+/**
+ * @file
+ * Compressed trie implementation for Longest Prefix Match
+ */

lib/librte_rib/rte_rib.h line 21

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+
+/** @internal Macro to enable/disable run-time checks. */
+#if defined(RTE_LIBRTE_RIB_DEBUG)
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval) do {	\
+	if (cond)					\
+		return retval;				\
+} while (0)
+#else
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval)
+#endif

use RTE_ASSERT?

lib/librte_rib/rte_rib.h line 23

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+#define RTE_RIB_VALID_NODE	1

should there be an INVALID_NODE macro?

lib/librte_rib/rte_rib.h line 34

Quoted 11 lines
lib/librte_rib/rte_rib.h new file +11 -0
+#define RTE_RIB_GET_NXT_ALL	0
+#define RTE_RIB_GET_NXT_COVER	1
+
+#define RTE_RIB_INVALID_ROUTE	0
+#define RTE_RIB_VALID_ROUTE	1
+
+/** Max number of characters in RIB name. */
+#define RTE_RIB_NAMESIZE	64
+
+/** Maximum depth value possible for IPv4 RIB. */
+#define RTE_RIB_MAXDEPTH	32

I think we should have IPv4 in the name here. Will it not be extended to support IPv6 in future?

lib/librte_rib/rte_rib.h line 42

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+
+/**
+ * Macro to check if prefix1 {key1/depth1}
+ * is covered by prefix2 {key2/depth2}
+ */
+#define RTE_RIB_IS_COVERED(key1, depth1, key2, depth2)			\
+	((((key1 ^ key2) & (uint32_t)(UINT64_MAX << (32 - depth2))) == 0)\
+		&& (depth1 > depth2))

Neat check!

Any particular reason for using UINT64_MAX here rather than UINT32_MAX? I think you can avoid the casting and have a slightly shorter mask by changing "(uint32_t)(UINT64_MAX << (32 - depth2)" to "~(UINT32_MAX >> depth2)"
I'd also suggest for readability putting the second check first, and, for maintainability, using an inline function rather than a macro.

lib/librte_rib/rte_rib.h line 48

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+
+/** @internal Macro to get next node in tree*/
+#define RTE_RIB_GET_NXT_NODE(node, key)					\
+	((key & (1 << (31 - node->depth))) ? node->right : node->left)
+/** @internal Macro to check if node is right child*/
+#define RTE_RIB_IS_RIGHT_NODE(node)	(node->parent->right == node)

Again, consider inline fns rather than macros.
For the latter macro, rather than doing additional pointer derefs to parent, can you also get if it's a right node by using:
"(node->key & (1 << (32 - node->depth)))"?

Quoted 13 lines
lib/librte_rib/rte_rib.h new file +13 -0
+
+
+struct rte_rib_node {
+	struct rte_rib_node *left;
+	struct rte_rib_node *right;
+	struct rte_rib_node *parent;
+	uint32_t	key;
+	uint8_t		depth;
+	uint8_t		flag;
+	uint64_t	nh;
+	uint64_t	ext[0];
+};
+

lib/librte_rib/rte_rib.h line 71

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+struct rte_rib;
+
+/** Type of FIB struct*/
+enum rte_rib_type {
+	RTE_RIB_DIR24_8_1B,
+	RTE_RIB_DIR24_8_2B,
+	RTE_RIB_DIR24_8_4B,
+	RTE_RIB_DIR24_8_8B,
+	RTE_RIB_TYPE_MAX
+};

If the plan is to support multiple underlying fib types and algorithms under the rib library, would it not be better to separate out the algorithm part from the data storage part? So have the type just be DIR_24_8, and have the 1, 2, 4 or 8 specified separately.

lib/librte_rib/rte_rib.h line 83

Quoted 12 lines
lib/librte_rib/rte_rib.h new file +12 -0
+
+enum rte_rib_op {
+	RTE_RIB_ADD,
+	RTE_RIB_DEL
+};
+
+/** RIB nodes allocation type */
+enum rte_rib_alloc_type {
+	RTE_RIB_MALLOC,
+	RTE_RIB_MEMPOOL,
+	RTE_RIB_ALLOC_MAX
+};

Not sure you need this any more. Malloc allocations and mempool allocations are now pretty much the same thing.

lib/librte_rib/rte_rib.h line 86

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+typedef int (*rte_rib_modify_fn_t)(struct rte_rib *rib, uint32_t key,
+	uint8_t depth, uint64_t next_hop, enum rte_rib_op op);

Do you anticipate more ops in future than just add and delete? If not, why not just split this function into two and drop the op struct.

Quoted 70 lines
lib/librte_rib/rte_rib.h new file +70 -0
+typedef int (*rte_rib_tree_lookup_fn_t)(void *fib, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned n);
+typedef struct rte_rib_node *(*rte_rib_alloc_node_fn_t)(struct rte_rib *rib);
+typedef void (*rte_rib_free_node_fn_t)(struct rte_rib *rib,
+	struct rte_rib_node *node);
+
+struct rte_rib {
+	char name[RTE_RIB_NAMESIZE];
+	/*pointer to rib trie*/
+	struct rte_rib_node	*trie;
+	/*pointer to dataplane struct*/
+	void	*fib;
+	/*prefix modification*/
+	rte_rib_modify_fn_t	modify;
+	/* Bulk lookup fn*/
+	rte_rib_tree_lookup_fn_t	lookup;
+	/*alloc trie element*/
+	rte_rib_alloc_node_fn_t	alloc_node;
+	/*free trie element*/
+	rte_rib_free_node_fn_t	free_node;
+	struct rte_mempool	*node_pool;
+	uint32_t		cur_nodes;
+	uint32_t		cur_routes;
+	int			max_nodes;
+	int			node_sz;
+	enum rte_rib_type	type;
+	enum rte_rib_alloc_type	alloc_type;
+};
+
+/** RIB configuration structure */
+struct rte_rib_conf {
+	enum rte_rib_type	type;
+	enum rte_rib_alloc_type	alloc_type;
+	int	max_nodes;
+	size_t	node_sz;
+	uint64_t def_nh;
+};
+
+/**
+ * Lookup an IP into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  IP to be looked up in the RIB
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup(struct rte_rib *rib, uint32_t key);
+
+/**
+ * Lookup less specific route into the RIB structure
+ *
+ * @param ent
+ *  Pointer to struct rte_rib_node that represents target route
+ * @return
+ *  pointer to struct rte_rib_node that represents
+ *  less specific route on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_parent(struct rte_rib_node *ent);
+
+/**
+ * Lookup prefix into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle

lib/librte_rib/rte_rib.h line 166

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * @param key
+ *  net to be looked up in the RIB
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_exact(struct rte_rib *rib, uint32_t key, uint8_t depth);

Can you explain the difference between this and regular lookup, and how they would be used. I don't think the names convey the differences sufficiently, and so we should look to rename one or both to be clearer.

lib/librte_rib/rte_rib.h line 169

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/**
+ * Retrieve next more specific prefix from the RIB

s/more/most/

Quoted 5 lines
lib/librte_rib/rte_rib.h new file +5 -0
+ * that is covered by key/depth supernet
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key

lib/librte_rib/rte_rib.h line 184

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ *  net address of supernet prefix that covers returned more specific prefixes
+ * @param depth
+ *  supernet prefix length
+ * @param cur
+ *   pointer to the last returned prefix to get next prefix
+ *   or
+ *   NULL to get first more specific prefix
+ * @param flag
+ *  -RTE_RIB_GET_NXT_ALL
+ *   get all prefixes from subtrie

By all prefixes do you mean more specific, i.e. the final prefix?

Quoted 126 lines
lib/librte_rib/rte_rib.h new file +126 -0
+ *  -RTE_RIB_GET_NXT_COVER
+ *   get only first more specific prefix even if it have more specifics
+ * @return
+ *  pointer to the next more specific prefix
+ *  or
+ *  NULL if there is no prefixes left
+ */
+struct rte_rib_node *
+rte_rib_tree_get_nxt(struct rte_rib *rib, uint32_t key, uint8_t depth,
+	struct rte_rib_node *cur, int flag);
+
+/**
+ * Remove prefix from the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be removed from the RIB
+ * @param depth
+ *  prefix length
+ */
+void
+rte_rib_tree_remove(struct rte_rib *rib, uint32_t key, uint8_t depth);
+
+/**
+ * Insert prefix into the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be inserted to the RIB
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to new rte_rib_node on success
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_insert(struct rte_rib *rib, uint32_t key, uint8_t depth);
+
+/**
+ * Create RIB
+ *
+ * @param name
+ *  RIB name
+ * @param socket_id
+ *  NUMA socket ID for RIB table memory allocation
+ * @param conf
+ *  Structure containing the configuration
+ * @return
+ *  Handle to RIB object on success
+ *  NULL otherwise with rte_errno set to an appropriate values.
+ */
+struct rte_rib *
+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf *conf);
+
+/**
+ * Find an existing RIB object and return a pointer to it.
+ *
+ * @param name
+ *  Name of the rib object as passed to rte_rib_create()
+ * @return
+ *  Pointer to rib object or NULL if object not found with rte_errno
+ *  set appropriately. Possible rte_errno values include:
+ *   - ENOENT - required entry not available to return.
+ */
+struct rte_rib *
+rte_rib_find_existing(const char *name);
+
+/**
+ * Free an RIB object.
+ *
+ * @param rib
+ *   RIB object handle
+ * @return
+ *   None
+ */
+void
+rte_rib_free(struct rte_rib *rib);
+
+/**
+ * Add a rule to the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip
+ *   IP of the rule to be added to the RIB
+ * @param depth
+ *   Depth of the rule to be added to the RIB
+ * @param next_hop
+ *   Next hop of the rule to be added to the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_add(struct rte_rib *rib, uint32_t ip, uint8_t depth, uint64_t next_hop);
+
+/**
+ * Delete a rule from the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip
+ *   IP of the rule to be deleted from the RIB
+ * @param depth
+ *   Depth of the rule to be deleted from the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_delete(struct rte_rib *rib, uint32_t ip, uint8_t depth);
+
+/**
+ * Lookup multiple IP addresses in an FIB. This may be implemented as a
+ * macro, so the address of the function should not be used.
+ *
+ * @param RIB
+ *   RIB object handle
+ * @param ips
+ *   Array of IPs to be looked up in the FIB
+ * @param next_hops
+ *   Next hop of the most specific rule found for IP.
+ *   This is an array of eight byte values.
+ *   If the lookup for the given IP failed, then corresponding element would
+ *   contain default value, see description of then next parameter.
+ * @param n

lib/librte_rib/rte_rib.h line 320

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ *   Number of elements in ips (and next_hops) array to lookup. This should be a
+ *   compile time constant, and divisible by 8 for best performance.
+ * @param defv
+ *   Default value to populate into corresponding element of hop[] array,
+ *   if lookup would fail.
+ *  @return
+ *   -EINVAL for incorrect arguments, otherwise 0
+ */
+#define rte_rib_fib_lookup_bulk(rib, ips, next_hops, n)	\
+	rib->lookup(rib->fib, ips, next_hops, n)

My main thought here is whether this needs to be a function at all? Given that it takes a full burst of addresses in a single go, how much performance would actually be lost by making this a regular function in the C file?
IF we do convert this to a regular function, then a lot of the structure definitions above - most importantly, the rib structure itself - can probably be moved to a private header file and not exposed to applications at all. This will make ABI compatibility a *lot* easier, as the structures can be changed without affecting the public ABI.

/Bruce

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+#endif /* _RTE_RIB_H_ */
#3 lore raw

Re: [PATCH v2 1/2] Add RIB library

Quoted 9 lines

lib/librte_rib/rte_rib.h line 83

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+/** RIB nodes allocation type */
+enum rte_rib_alloc_type {
+	RTE_RIB_MALLOC,
+	RTE_RIB_MEMPOOL,
+	RTE_RIB_ALLOC_MAX
+};

Not sure you need this any more. Malloc allocations and mempool allocations are now pretty much the same thing.

Sorry, please ignore this comment. I mistook mempool for memzone.

#4 lore raw

Re: [PATCH v2 1/2] Add RIB library

In reply to Bruce Richardson

Hi,

2018-03-14 14:09 GMT+03:00 Bruce Richardson <[email protected]>:

Quoted 72 lines · Medvedkin Vladimir
Quoted 5 lines

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

Quoted 8 lines

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.
- For dir24_8 implementation it is possible to remove

rte_lpm_tbl_entry.depth

Quoted 4 lines

field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- Removed RTE_LPM_LOOKUP_SUCCESS to save 1 bit and to eleminate ternary

operator.

Quoted 9 lines

Instead it returns special default value if there is no route.

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 ++++++++++++++++++++++++++++++

+++

Quoted 2 lines
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 ++++++++++++++++++++++++++++++

+++++++

Quoted 11 lines
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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

First pass review comments. For now just reviewed the main public header file rte_rib.h. Later reviews will cover the other files as best I can.

/Bruce

<snip>

Quoted 21 lines
lib/librte_rib/rte_rib.h new file +15 -0
new file mode 100644
index 0000000..6eac8fb
@@ -0,0 +1,322 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _RTE_RIB_H_
+#define _RTE_RIB_H_
+
+/**
+ * @file
+ * Compressed trie implementation for Longest Prefix Match
+ */
+
+/** @internal Macro to enable/disable run-time checks. */
+#if defined(RTE_LIBRTE_RIB_DEBUG)
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval) do {    \
Quoted 9 lines

lib/librte_rib/rte_rib.h line 21

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+     if (cond)                                       \
+             return retval;                          \
+} while (0)
+#else
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval)
+#endif

use RTE_ASSERT?

it was done just like it was done in the LPM lib. But if you think it should be RTE_ASSERT so be it.

Quoted 6 lines

lib/librte_rib/rte_rib.h line 23

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+#define RTE_RIB_VALID_NODE   1

should there be an INVALID_NODE macro?

No

Quoted 16 lines

lib/librte_rib/rte_rib.h line 34

Quoted 12 lines
lib/librte_rib/rte_rib.h new file +11 -0
+#define RTE_RIB_GET_NXT_ALL  0
+#define RTE_RIB_GET_NXT_COVER        1
+
+#define RTE_RIB_INVALID_ROUTE        0
+#define RTE_RIB_VALID_ROUTE  1
+
+/** Max number of characters in RIB name. */
+#define RTE_RIB_NAMESIZE     64
+
+/** Maximum depth value possible for IPv4 RIB. */
+#define RTE_RIB_MAXDEPTH     32

I think we should have IPv4 in the name here. Will it not be extended to support IPv6 in future?

I think there should be a separate implementation of the library for ipv6

Quoted 8 lines

lib/librte_rib/rte_rib.h

Quoted 7 lines
lib/librte_rib/rte_rib.h new file +6 -0
+
+/**
+ * Macro to check if prefix1 {key1/depth1}
+ * is covered by prefix2 {key2/depth2}
+ */
+#define RTE_RIB_IS_COVERED(key1, depth1, key2, depth2)
     \
Quoted 5 lines

lib/librte_rib/rte_rib.h line 42

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+     ((((key1 ^ key2) & (uint32_t)(UINT64_MAX << (32 - depth2))) == 0)\
+             && (depth1 > depth2))

Neat check!

Any particular reason for using UINT64_MAX here rather than UINT32_MAX?

in case when depth2 = 0 UINT32_MAX shifted left by 32 bit will remain UINT32_MAX because shift count will be masked to 5 bits.

I think you can avoid the casting and have a slightly shorter mask by

Quoted 5 lines

changing "(uint32_t)(UINT64_MAX << (32 - depth2)" to "~(UINT32_MAX >> depth2)"
I'd also suggest for readability putting the second check first, and, for maintainability, using an inline function rather than a macro.

Agree, it looks clearer

Quoted 10 lines

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/** @internal Macro to get next node in tree*/
+#define RTE_RIB_GET_NXT_NODE(node, key)
      \

lib/librte_rib/rte_rib.h line 48

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+     ((key & (1 << (31 - node->depth))) ? node->right : node->left)
+/** @internal Macro to check if node is right child*/
+#define RTE_RIB_IS_RIGHT_NODE(node)  (node->parent->right == node)

Again, consider inline fns rather than macros.

Ok

For the latter macro, rather than doing additional pointer derefs to

Quoted 3 lines

parent, can you also get if it's a right node by using:
"(node->key & (1 << (32 - node->depth)))"?

No, it is not possible. Decision whether node be left or right is made using parent and child common depth.
Consider case with 10.0.0.0/8 and 10.128.0.0/24. In this way common depth will be /8 and 10.128.0.0/24 will be right child.

Quoted 20 lines
Quoted 20 lines
lib/librte_rib/rte_rib.h new file +20 -0
+
+
+struct rte_rib_node {
+     struct rte_rib_node *left;
+     struct rte_rib_node *right;
+     struct rte_rib_node *parent;
+     uint32_t        key;
+     uint8_t         depth;
+     uint8_t         flag;
+     uint64_t        nh;
+     uint64_t        ext[0];
+};
+
+struct rte_rib;
+
+/** Type of FIB struct*/
+enum rte_rib_type {
+     RTE_RIB_DIR24_8_1B,
+     RTE_RIB_DIR24_8_2B,
+     RTE_RIB_DIR24_8_4B,
Quoted 9 lines

lib/librte_rib/rte_rib.h line 71

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+     RTE_RIB_DIR24_8_8B,
+     RTE_RIB_TYPE_MAX
+};

If the plan is to support multiple underlying fib types and algorithms under the rib library, would it not be better to separate out the algorithm part from the data storage part? So have the type just be DIR_24_8, and have the 1, 2, 4 or 8 specified separately.

Yes, we were talk about it in IRC, agree. Now I pass next hop size in union rte_rib_fib_conf inside rte_rib_conf

Quoted 17 lines

lib/librte_rib/rte_rib.h line 83

Quoted 13 lines
lib/librte_rib/rte_rib.h new file +12 -0
+
+enum rte_rib_op {
+     RTE_RIB_ADD,
+     RTE_RIB_DEL
+};
+
+/** RIB nodes allocation type */
+enum rte_rib_alloc_type {
+     RTE_RIB_MALLOC,
+     RTE_RIB_MEMPOOL,
+     RTE_RIB_ALLOC_MAX
+};

Not sure you need this any more. Malloc allocations and mempool allocations are now pretty much the same thing.

Actually I think to remove malloc. On performance tests with adding/deleting huge amount of routes malloc is slower. Maybe because of fragmentation.
What do you think?

Quoted 7 lines

lib/librte_rib/rte_rib.h line 86

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+typedef int (*rte_rib_modify_fn_t)(struct rte_rib *rib, uint32_t key,
+     uint8_t depth, uint64_t next_hop, enum rte_rib_op op);

Do you anticipate more ops in future than just add and delete? If not, why not just split this function into two and drop the op struct.

It is difficult question. I'm not ready to make decision at the moment.

Quoted 84 lines

lib/librte_rib/rte_rib.h

Quoted 4 lines
lib/librte_rib/rte_rib.h new file +3 -0
+typedef int (*rte_rib_tree_lookup_fn_t)(void *fib, const uint32_t *ips,
+     uint64_t *next_hops, const unsigned n);
+typedef struct rte_rib_node *(*rte_rib_alloc_node_fn_t)(struct rte_rib

*rib);

Quoted 67 lines
lib/librte_rib/rte_rib.h new file +67 -0
+typedef void (*rte_rib_free_node_fn_t)(struct rte_rib *rib,
+     struct rte_rib_node *node);
+
+struct rte_rib {
+     char name[RTE_RIB_NAMESIZE];
+     /*pointer to rib trie*/
+     struct rte_rib_node     *trie;
+     /*pointer to dataplane struct*/
+     void    *fib;
+     /*prefix modification*/
+     rte_rib_modify_fn_t     modify;
+     /* Bulk lookup fn*/
+     rte_rib_tree_lookup_fn_t        lookup;
+     /*alloc trie element*/
+     rte_rib_alloc_node_fn_t alloc_node;
+     /*free trie element*/
+     rte_rib_free_node_fn_t  free_node;
+     struct rte_mempool      *node_pool;
+     uint32_t                cur_nodes;
+     uint32_t                cur_routes;
+     int                     max_nodes;
+     int                     node_sz;
+     enum rte_rib_type       type;
+     enum rte_rib_alloc_type alloc_type;
+};
+
+/** RIB configuration structure */
+struct rte_rib_conf {
+     enum rte_rib_type       type;
+     enum rte_rib_alloc_type alloc_type;
+     int     max_nodes;
+     size_t  node_sz;
+     uint64_t def_nh;
+};
+
+/**
+ * Lookup an IP into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  IP to be looked up in the RIB
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup(struct rte_rib *rib, uint32_t key);
+
+/**
+ * Lookup less specific route into the RIB structure
+ *
+ * @param ent
+ *  Pointer to struct rte_rib_node that represents target route
+ * @return
+ *  pointer to struct rte_rib_node that represents
+ *  less specific route on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_parent(struct rte_rib_node *ent);
+
+/**
+ * Lookup prefix into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * @param key
+ *  net to be looked up in the RIB
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_exact(struct rte_rib *rib, uint32_t key, uint8_t

depth);

Quoted 4 lines

Can you explain the difference between this and regular lookup, and how they would be used. I don't think the names convey the differences sufficiently, and so we should look to rename one or both to be clearer.

Regular lookup (rte_rib_tree_lookup) will lookup for most specific node for passed key.
rte_rib_tree_lookup_exact will lookup node contained key and depth equal to passed in args. It used to find exact route.

Quoted 24 lines

lib/librte_rib/rte_rib.h line 169

Quoted 4 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/**
+ * Retrieve next more specific prefix from the RIB

s/more/most/

lib/librte_rib/rte_rib.h

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+ * that is covered by key/depth supernet
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net address of supernet prefix that covers returned more specific

prefixes

lib/librte_rib/rte_rib.h line 184

Quoted 9 lines
lib/librte_rib/rte_rib.h new file +9 -0
+ * @param depth
+ *  supernet prefix length
+ * @param cur
+ *   pointer to the last returned prefix to get next prefix
+ *   or
+ *   NULL to get first more specific prefix
+ * @param flag
+ *  -RTE_RIB_GET_NXT_ALL
+ *   get all prefixes from subtrie
Quoted 2 lines

By all prefixes do you mean more specific, i.e. the final prefix?

What do you mean the final prefix?

Quoted 142 lines
Quoted 45 lines
lib/librte_rib/rte_rib.h new file +45 -0
+ *  -RTE_RIB_GET_NXT_COVER
+ *   get only first more specific prefix even if it have more specifics
+ * @return
+ *  pointer to the next more specific prefix
+ *  or
+ *  NULL if there is no prefixes left
+ */
+struct rte_rib_node *
+rte_rib_tree_get_nxt(struct rte_rib *rib, uint32_t key, uint8_t depth,
+     struct rte_rib_node *cur, int flag);
+
+/**
+ * Remove prefix from the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be removed from the RIB
+ * @param depth
+ *  prefix length
+ */
+void
+rte_rib_tree_remove(struct rte_rib *rib, uint32_t key, uint8_t depth);
+
+/**
+ * Insert prefix into the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be inserted to the RIB
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to new rte_rib_node on success
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_insert(struct rte_rib *rib, uint32_t key, uint8_t depth);
+
+/**
+ * Create RIB
+ *
+ * @param name
+ *  RIB name

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * @param socket_id
+ *  NUMA socket ID for RIB table memory allocation
+ * @param conf
+ *  Structure containing the configuration
+ * @return
+ *  Handle to RIB object on success
+ *  NULL otherwise with rte_errno set to an appropriate values.
+ */
+struct rte_rib *
+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf

*conf);

Quoted 31 lines
lib/librte_rib/rte_rib.h new file +31 -0
+
+/**
+ * Find an existing RIB object and return a pointer to it.
+ *
+ * @param name
+ *  Name of the rib object as passed to rte_rib_create()
+ * @return
+ *  Pointer to rib object or NULL if object not found with rte_errno
+ *  set appropriately. Possible rte_errno values include:
+ *   - ENOENT - required entry not available to return.
+ */
+struct rte_rib *
+rte_rib_find_existing(const char *name);
+
+/**
+ * Free an RIB object.
+ *
+ * @param rib
+ *   RIB object handle
+ * @return
+ *   None
+ */
+void
+rte_rib_free(struct rte_rib *rib);
+
+/**
+ * Add a rule to the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ *   IP of the rule to be added to the RIB
+ * @param depth
+ *   Depth of the rule to be added to the RIB
+ * @param next_hop
+ *   Next hop of the rule to be added to the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_add(struct rte_rib *rib, uint32_t ip, uint8_t depth, uint64_t

next_hop);

Quoted 18 lines
lib/librte_rib/rte_rib.h new file +18 -0
+
+/**
+ * Delete a rule from the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip
+ *   IP of the rule to be deleted from the RIB
+ * @param depth
+ *   Depth of the rule to be deleted from the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_delete(struct rte_rib *rib, uint32_t ip, uint8_t depth);
+
+/**
+ * Lookup multiple IP addresses in an FIB. This may be implemented as a

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * macro, so the address of the function should not be used.
+ *
+ * @param RIB
+ *   RIB object handle
+ * @param ips
+ *   Array of IPs to be looked up in the FIB
+ * @param next_hops
+ *   Next hop of the most specific rule found for IP.
+ *   This is an array of eight byte values.
+ *   If the lookup for the given IP failed, then corresponding element

would

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+ *   contain default value, see description of then next parameter.
+ * @param n
+ *   Number of elements in ips (and next_hops) array to lookup. This

should be a

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+ *   compile time constant, and divisible by 8 for best performance.
+ * @param defv
+ *   Default value to populate into corresponding element of hop[]

array,

lib/librte_rib/rte_rib.h line 320

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+ *   if lookup would fail.
+ *  @return
+ *   -EINVAL for incorrect arguments, otherwise 0
+ */
+#define rte_rib_fib_lookup_bulk(rib, ips, next_hops, n)      \
+     rib->lookup(rib->fib, ips, next_hops, n)
Quoted 10 lines

My main thought here is whether this needs to be a function at all? Given that it takes a full burst of addresses in a single go, how much performance would actually be lost by making this a regular function in the C file?
IF we do convert this to a regular function, then a lot of the structure definitions above - most importantly, the rib structure itself - can probably be moved to a private header file and not exposed to applications at all. This will make ABI compatibility a *lot* easier, as the structures can be changed without affecting the public ABI.

I didn't quite understand what you mean.

Quoted 5 lines

/Bruce

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+#endif /* _RTE_RIB_H_ */
Signature · 2 lines
Regards,
Vladimir
#5 lore raw

Re: [PATCH v2 1/2] Add RIB library

Quoted 114 lines · Vladimir Medvedkin

Hi,

2018-03-14 14:09 GMT+03:00 Bruce Richardson <[email protected]>:

Quoted 72 lines · Medvedkin Vladimir
Quoted 5 lines

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

Quoted 8 lines

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.
- For dir24_8 implementation it is possible to remove

rte_lpm_tbl_entry.depth

Quoted 4 lines

field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- Removed RTE_LPM_LOOKUP_SUCCESS to save 1 bit and to eleminate ternary

operator.

Quoted 9 lines

Instead it returns special default value if there is no route.

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 ++++++++++++++++++++++++++++++

+++

Quoted 2 lines
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 ++++++++++++++++++++++++++++++

+++++++

Quoted 11 lines
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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

First pass review comments. For now just reviewed the main public header file rte_rib.h. Later reviews will cover the other files as best I can.

/Bruce

<snip>

Quoted 21 lines
lib/librte_rib/rte_rib.h new file +15 -0
new file mode 100644
index 0000000..6eac8fb
@@ -0,0 +1,322 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _RTE_RIB_H_
+#define _RTE_RIB_H_
+
+/**
+ * @file
+ * Compressed trie implementation for Longest Prefix Match
+ */
+
+/** @internal Macro to enable/disable run-time checks. */
+#if defined(RTE_LIBRTE_RIB_DEBUG)
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval) do {    \
Quoted 9 lines

lib/librte_rib/rte_rib.h line 21

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+     if (cond)                                       \
+             return retval;                          \
+} while (0)
+#else
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval)
+#endif

use RTE_ASSERT?

it was done just like it was done in the LPM lib. But if you think it should be RTE_ASSERT so be it.

Quoted 6 lines

lib/librte_rib/rte_rib.h line 23

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+#define RTE_RIB_VALID_NODE   1

should there be an INVALID_NODE macro?

No

Quoted 16 lines

lib/librte_rib/rte_rib.h line 34

Quoted 12 lines
lib/librte_rib/rte_rib.h new file +11 -0
+#define RTE_RIB_GET_NXT_ALL  0
+#define RTE_RIB_GET_NXT_COVER        1
+
+#define RTE_RIB_INVALID_ROUTE        0
+#define RTE_RIB_VALID_ROUTE  1
+
+/** Max number of characters in RIB name. */
+#define RTE_RIB_NAMESIZE     64
+
+/** Maximum depth value possible for IPv4 RIB. */
+#define RTE_RIB_MAXDEPTH     32

I think we should have IPv4 in the name here. Will it not be extended to support IPv6 in future?

Quoted 2 lines

I think there should be a separate implementation of the library for ipv6

I can understand the need for a separate LPM implementation, but should they both not be under the same rib library?

Quoted 99 lines
Quoted 9 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +6 -0
+
+/**
+ * Macro to check if prefix1 {key1/depth1}
+ * is covered by prefix2 {key2/depth2}
+ */
+#define RTE_RIB_IS_COVERED(key1, depth1, key2, depth2)
     \
Quoted 5 lines

lib/librte_rib/rte_rib.h line 42

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+     ((((key1 ^ key2) & (uint32_t)(UINT64_MAX << (32 - depth2))) == 0)\
+             && (depth1 > depth2))

Neat check!

Any particular reason for using UINT64_MAX here rather than UINT32_MAX?

in case when depth2 = 0 UINT32_MAX shifted left by 32 bit will remain UINT32_MAX because shift count will be masked to 5 bits.

I think you can avoid the casting and have a slightly shorter mask by

Quoted 5 lines

changing "(uint32_t)(UINT64_MAX << (32 - depth2)" to "~(UINT32_MAX >> depth2)"
I'd also suggest for readability putting the second check first, and, for maintainability, using an inline function rather than a macro.

Agree, it looks clearer

Quoted 10 lines

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/** @internal Macro to get next node in tree*/
+#define RTE_RIB_GET_NXT_NODE(node, key)
      \

lib/librte_rib/rte_rib.h line 48

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+     ((key & (1 << (31 - node->depth))) ? node->right : node->left)
+/** @internal Macro to check if node is right child*/
+#define RTE_RIB_IS_RIGHT_NODE(node)  (node->parent->right == node)

Again, consider inline fns rather than macros.

Ok

For the latter macro, rather than doing additional pointer derefs to

Quoted 3 lines

parent, can you also get if it's a right node by using:
"(node->key & (1 << (32 - node->depth)))"?

No, it is not possible. Decision whether node be left or right is made using parent and child common depth.
Consider case with 10.0.0.0/8 and 10.128.0.0/24. In this way common depth will be /8 and 10.128.0.0/24 will be right child.

Quoted 20 lines
Quoted 20 lines
lib/librte_rib/rte_rib.h new file +20 -0
+
+
+struct rte_rib_node {
+     struct rte_rib_node *left;
+     struct rte_rib_node *right;
+     struct rte_rib_node *parent;
+     uint32_t        key;
+     uint8_t         depth;
+     uint8_t         flag;
+     uint64_t        nh;
+     uint64_t        ext[0];
+};
+
+struct rte_rib;
+
+/** Type of FIB struct*/
+enum rte_rib_type {
+     RTE_RIB_DIR24_8_1B,
+     RTE_RIB_DIR24_8_2B,
+     RTE_RIB_DIR24_8_4B,
Quoted 9 lines

lib/librte_rib/rte_rib.h line 71

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+     RTE_RIB_DIR24_8_8B,
+     RTE_RIB_TYPE_MAX
+};

If the plan is to support multiple underlying fib types and algorithms under the rib library, would it not be better to separate out the algorithm part from the data storage part? So have the type just be DIR_24_8, and have the 1, 2, 4 or 8 specified separately.

Yes, we were talk about it in IRC, agree. Now I pass next hop size in union rte_rib_fib_conf inside rte_rib_conf

Quoted 17 lines

lib/librte_rib/rte_rib.h line 83

Quoted 13 lines
lib/librte_rib/rte_rib.h new file +12 -0
+
+enum rte_rib_op {
+     RTE_RIB_ADD,
+     RTE_RIB_DEL
+};
+
+/** RIB nodes allocation type */
+enum rte_rib_alloc_type {
+     RTE_RIB_MALLOC,
+     RTE_RIB_MEMPOOL,
+     RTE_RIB_ALLOC_MAX
+};

Not sure you need this any more. Malloc allocations and mempool allocations are now pretty much the same thing.

Quoted 5 lines

Actually I think to remove malloc. On performance tests with adding/deleting huge amount of routes malloc is slower. Maybe because of fragmentation.
What do you think?

Yes, definitely mempool allocations are the way to go!

Quoted 95 lines
Quoted 8 lines

lib/librte_rib/rte_rib.h line 86

Quoted 4 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+typedef int (*rte_rib_modify_fn_t)(struct rte_rib *rib, uint32_t key,
+     uint8_t depth, uint64_t next_hop, enum rte_rib_op op);

Do you anticipate more ops in future than just add and delete? If not, why not just split this function into two and drop the op struct.

It is difficult question. I'm not ready to make decision at the moment.

Quoted 84 lines

lib/librte_rib/rte_rib.h

Quoted 4 lines
lib/librte_rib/rte_rib.h new file +3 -0
+typedef int (*rte_rib_tree_lookup_fn_t)(void *fib, const uint32_t *ips,
+     uint64_t *next_hops, const unsigned n);
+typedef struct rte_rib_node *(*rte_rib_alloc_node_fn_t)(struct rte_rib

*rib);

Quoted 67 lines
lib/librte_rib/rte_rib.h new file +67 -0
+typedef void (*rte_rib_free_node_fn_t)(struct rte_rib *rib,
+     struct rte_rib_node *node);
+
+struct rte_rib {
+     char name[RTE_RIB_NAMESIZE];
+     /*pointer to rib trie*/
+     struct rte_rib_node     *trie;
+     /*pointer to dataplane struct*/
+     void    *fib;
+     /*prefix modification*/
+     rte_rib_modify_fn_t     modify;
+     /* Bulk lookup fn*/
+     rte_rib_tree_lookup_fn_t        lookup;
+     /*alloc trie element*/
+     rte_rib_alloc_node_fn_t alloc_node;
+     /*free trie element*/
+     rte_rib_free_node_fn_t  free_node;
+     struct rte_mempool      *node_pool;
+     uint32_t                cur_nodes;
+     uint32_t                cur_routes;
+     int                     max_nodes;
+     int                     node_sz;
+     enum rte_rib_type       type;
+     enum rte_rib_alloc_type alloc_type;
+};
+
+/** RIB configuration structure */
+struct rte_rib_conf {
+     enum rte_rib_type       type;
+     enum rte_rib_alloc_type alloc_type;
+     int     max_nodes;
+     size_t  node_sz;
+     uint64_t def_nh;
+};
+
+/**
+ * Lookup an IP into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  IP to be looked up in the RIB
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup(struct rte_rib *rib, uint32_t key);
+
+/**
+ * Lookup less specific route into the RIB structure
+ *
+ * @param ent
+ *  Pointer to struct rte_rib_node that represents target route
+ * @return
+ *  pointer to struct rte_rib_node that represents
+ *  less specific route on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_parent(struct rte_rib_node *ent);
+
+/**
+ * Lookup prefix into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * @param key
+ *  net to be looked up in the RIB
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_exact(struct rte_rib *rib, uint32_t key, uint8_t

depth);

Quoted 9 lines
Quoted 4 lines

Can you explain the difference between this and regular lookup, and how they would be used. I don't think the names convey the differences sufficiently, and so we should look to rename one or both to be clearer.

Regular lookup (rte_rib_tree_lookup) will lookup for most specific node for passed key.
rte_rib_tree_lookup_exact will lookup node contained key and depth equal to passed in args. It used to find exact route.

So if there is no node exactly matching the parameters, it the lookup_exact returns failure? E.g. if you request a /24 node, it won't return a /8 node that would cover the /24?

Quoted 25 lines
Quoted 25 lines

lib/librte_rib/rte_rib.h line 169

Quoted 5 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/**
+ * Retrieve next more specific prefix from the RIB

s/more/most/

lib/librte_rib/rte_rib.h

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+ * that is covered by key/depth supernet
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net address of supernet prefix that covers returned more specific

prefixes

Quoted 9 lines
lib/librte_rib/rte_rib.h new file +9 -0
+ * @param depth
+ *  supernet prefix length
+ * @param cur
+ *   pointer to the last returned prefix to get next prefix
+ *   or
+ *   NULL to get first more specific prefix
+ * @param flag
+ *  -RTE_RIB_GET_NXT_ALL
+ *   get all prefixes from subtrie
Quoted 4 lines
Quoted 2 lines

By all prefixes do you mean more specific, i.e. the final prefix?

What do you mean the final prefix?

The most specific one, or the longest prefix.

Quoted 153 lines
Quoted 143 lines
Quoted 46 lines
lib/librte_rib/rte_rib.h new file +45 -0
+ *  -RTE_RIB_GET_NXT_COVER
+ *   get only first more specific prefix even if it have more specifics
+ * @return
+ *  pointer to the next more specific prefix
+ *  or
+ *  NULL if there is no prefixes left
+ */
+struct rte_rib_node *
+rte_rib_tree_get_nxt(struct rte_rib *rib, uint32_t key, uint8_t depth,
+     struct rte_rib_node *cur, int flag);
+
+/**
+ * Remove prefix from the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be removed from the RIB
+ * @param depth
+ *  prefix length
+ */
+void
+rte_rib_tree_remove(struct rte_rib *rib, uint32_t key, uint8_t depth);
+
+/**
+ * Insert prefix into the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be inserted to the RIB
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to new rte_rib_node on success
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_insert(struct rte_rib *rib, uint32_t key, uint8_t depth);
+
+/**
+ * Create RIB
+ *
+ * @param name
+ *  RIB name

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * @param socket_id
+ *  NUMA socket ID for RIB table memory allocation
+ * @param conf
+ *  Structure containing the configuration
+ * @return
+ *  Handle to RIB object on success
+ *  NULL otherwise with rte_errno set to an appropriate values.
+ */
+struct rte_rib *
+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf

*conf);

Quoted 31 lines
lib/librte_rib/rte_rib.h new file +31 -0
+
+/**
+ * Find an existing RIB object and return a pointer to it.
+ *
+ * @param name
+ *  Name of the rib object as passed to rte_rib_create()
+ * @return
+ *  Pointer to rib object or NULL if object not found with rte_errno
+ *  set appropriately. Possible rte_errno values include:
+ *   - ENOENT - required entry not available to return.
+ */
+struct rte_rib *
+rte_rib_find_existing(const char *name);
+
+/**
+ * Free an RIB object.
+ *
+ * @param rib
+ *   RIB object handle
+ * @return
+ *   None
+ */
+void
+rte_rib_free(struct rte_rib *rib);
+
+/**
+ * Add a rule to the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ *   IP of the rule to be added to the RIB
+ * @param depth
+ *   Depth of the rule to be added to the RIB
+ * @param next_hop
+ *   Next hop of the rule to be added to the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_add(struct rte_rib *rib, uint32_t ip, uint8_t depth, uint64_t

next_hop);

Quoted 18 lines
lib/librte_rib/rte_rib.h new file +18 -0
+
+/**
+ * Delete a rule from the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip
+ *   IP of the rule to be deleted from the RIB
+ * @param depth
+ *   Depth of the rule to be deleted from the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_delete(struct rte_rib *rib, uint32_t ip, uint8_t depth);
+
+/**
+ * Lookup multiple IP addresses in an FIB. This may be implemented as a

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * macro, so the address of the function should not be used.
+ *
+ * @param RIB
+ *   RIB object handle
+ * @param ips
+ *   Array of IPs to be looked up in the FIB
+ * @param next_hops
+ *   Next hop of the most specific rule found for IP.
+ *   This is an array of eight byte values.
+ *   If the lookup for the given IP failed, then corresponding element

would

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+ *   contain default value, see description of then next parameter.
+ * @param n
+ *   Number of elements in ips (and next_hops) array to lookup. This

should be a

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+ *   compile time constant, and divisible by 8 for best performance.
+ * @param defv
+ *   Default value to populate into corresponding element of hop[]

array,

lib/librte_rib/rte_rib.h line 320

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+ *   if lookup would fail.
+ *  @return
+ *   -EINVAL for incorrect arguments, otherwise 0
+ */
+#define rte_rib_fib_lookup_bulk(rib, ips, next_hops, n)      \
+     rib->lookup(rib->fib, ips, next_hops, n)
Quoted 10 lines

My main thought here is whether this needs to be a function at all? Given that it takes a full burst of addresses in a single go, how much performance would actually be lost by making this a regular function in the C file?
IF we do convert this to a regular function, then a lot of the structure definitions above - most importantly, the rib structure itself - can probably be moved to a private header file and not exposed to applications at all. This will make ABI compatibility a *lot* easier, as the structures can be changed without affecting the public ABI.

Quoted 2 lines

I didn't quite understand what you mean.

Sorry, by "needs to be a function" in first line read "needs to be a macro". Basically, the point is to not inline anything that doesn't need it. If a function works on a burst of packets, it probably will be fine being a regular function than a macro or inline function.

/Bruce

#6 lore raw

Re: [PATCH v2 1/2] Add RIB library

2018-03-26 12:50 GMT+03:00 Bruce Richardson <[email protected]>:

Quoted 123 lines · Vladimir Medvedkin
Quoted 9 lines

Hi,

2018-03-14 14:09 GMT+03:00 Bruce Richardson <[email protected] :

Quoted 4 lines · Medvedkin Vladimir
Quoted 3 lines

RIB is an alternative to current LPM library.
It solves the following problems
- Increases the speed of control plane operations against lpm such

as

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

adding/deleting routes
- Adds abstraction from dataplane algorithms, so it is possible to

add

Quoted 1 line
Quoted 1 line
Quoted 1 line

different ip route lookup algorythms such as

DXR/poptrie/lpc-trie/etc

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

in addition to current dir24_8
- It is possible to keep user defined application specific

additional

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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),

Quoted 7 lines
Quoted 7 lines
Quoted 2 lines

plenty of additional control plane information.
- For dir24_8 implementation it is possible to remove

rte_lpm_tbl_entry.depth

Quoted 4 lines

field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- Removed RTE_LPM_LOOKUP_SUCCESS to save 1 bit and to eleminate

ternary

Quoted 10 lines
Quoted 10 lines

operator.

Quoted 9 lines

Instead it returns special default value if there is no route.

---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482

++++++++++++++++++++++++++++++

Quoted 3 lines
Quoted 3 lines

+++

Quoted 2 lines
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526

++++++++++++++++++++++++++++++

Quoted 13 lines
Quoted 13 lines

+++++++

Quoted 11 lines
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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
Quoted 1 line
Quoted 1 line

First pass review comments. For now just reviewed the main public

header

Quoted 40 lines
Quoted 26 lines

file rte_rib.h. Later reviews will cover the other files as best I can.

/Bruce

<snip>

Quoted 21 lines
lib/librte_rib/rte_rib.h new file +15 -0
new file mode 100644
index 0000000..6eac8fb
@@ -0,0 +1,322 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _RTE_RIB_H_
+#define _RTE_RIB_H_
+
+/**
+ * @file
+ * Compressed trie implementation for Longest Prefix Match
+ */
+
+/** @internal Macro to enable/disable run-time checks. */
+#if defined(RTE_LIBRTE_RIB_DEBUG)
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval) do {    \
Quoted 9 lines

lib/librte_rib/rte_rib.h line 21

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+     if (cond)                                       \
+             return retval;                          \
+} while (0)
+#else
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval)
+#endif

use RTE_ASSERT?

it was done just like it was done in the LPM lib. But if you think it should be RTE_ASSERT so be it.

Quoted 1 line
Quoted 22 lines
Quoted 5 lines

lib/librte_rib/rte_rib.h line 23

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+#define RTE_RIB_VALID_NODE   1

should there be an INVALID_NODE macro?

No

Quoted 14 lines

lib/librte_rib/rte_rib.h line 34

Quoted 12 lines
lib/librte_rib/rte_rib.h new file +11 -0
+#define RTE_RIB_GET_NXT_ALL  0
+#define RTE_RIB_GET_NXT_COVER        1
+
+#define RTE_RIB_INVALID_ROUTE        0
+#define RTE_RIB_VALID_ROUTE  1
+
+/** Max number of characters in RIB name. */
+#define RTE_RIB_NAMESIZE     64
+
+/** Maximum depth value possible for IPv4 RIB. */
+#define RTE_RIB_MAXDEPTH     32

I think we should have IPv4 in the name here. Will it not be extended

Quoted 8 lines

to

Quoted 4 lines
Quoted 2 lines

support IPv6 in future?

I think there should be a separate implementation of the library for ipv6

I can understand the need for a separate LPM implementation, but should they both not be under the same rib library?

I planned to have sepatate rib6 for ipv6.
Of course it is possible to make universal abstraction for both v4 and v6. But in this case there will be universal rte_rib_node with type (v4|v6) and variable length, keys will become union of uint32_t for v4 and uint8_t [16] for v6. I think it is overcomplication.

Quoted 214 lines
Quoted 10 lines
Quoted 10 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +6 -0
+
+/**
+ * Macro to check if prefix1 {key1/depth1}
+ * is covered by prefix2 {key2/depth2}
+ */
+#define RTE_RIB_IS_COVERED(key1, depth1, key2, depth2)
     \
Quoted 1 line
lib/librte_rib/rte_rib.h new file +1 -0
+     ((((key1 ^ key2) & (uint32_t)(UINT64_MAX << (32 - depth2))) ==

0)\

Quoted 29 lines
Quoted 4 lines

lib/librte_rib/rte_rib.h line 42

Quoted 1 line
lib/librte_rib/rte_rib.h new file +1 -0
+             && (depth1 > depth2))

Neat check!

Any particular reason for using UINT64_MAX here rather than UINT32_MAX?

in case when depth2 = 0 UINT32_MAX shifted left by 32 bit will remain UINT32_MAX because shift count will be masked to 5 bits.

I think you can avoid the casting and have a slightly shorter mask by

Quoted 5 lines

changing "(uint32_t)(UINT64_MAX << (32 - depth2)" to "~(UINT32_MAX >> depth2)"
I'd also suggest for readability putting the second check first, and, for maintainability, using an inline function rather than a macro.

Agree, it looks clearer

Quoted 10 lines

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/** @internal Macro to get next node in tree*/
+#define RTE_RIB_GET_NXT_NODE(node, key)
      \

lib/librte_rib/rte_rib.h line 48

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+     ((key & (1 << (31 - node->depth))) ? node->right : node->left)
+/** @internal Macro to check if node is right child*/
+#define RTE_RIB_IS_RIGHT_NODE(node)  (node->parent->right == node)

Again, consider inline fns rather than macros.

Ok

Quoted 7 lines

For the latter macro, rather than doing additional pointer derefs to

Quoted 3 lines

parent, can you also get if it's a right node by using:
"(node->key & (1 << (32 - node->depth)))"?

No, it is not possible. Decision whether node be left or right is made using parent and child common depth.
Consider case with 10.0.0.0/8 and 10.128.0.0/24. In this way common

depth

Quoted 53 lines

will be /8 and 10.128.0.0/24 will be right child.

Quoted 20 lines
Quoted 20 lines
lib/librte_rib/rte_rib.h new file +20 -0
+
+
+struct rte_rib_node {
+     struct rte_rib_node *left;
+     struct rte_rib_node *right;
+     struct rte_rib_node *parent;
+     uint32_t        key;
+     uint8_t         depth;
+     uint8_t         flag;
+     uint64_t        nh;
+     uint64_t        ext[0];
+};
+
+struct rte_rib;
+
+/** Type of FIB struct*/
+enum rte_rib_type {
+     RTE_RIB_DIR24_8_1B,
+     RTE_RIB_DIR24_8_2B,
+     RTE_RIB_DIR24_8_4B,
Quoted 9 lines

lib/librte_rib/rte_rib.h line 71

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+     RTE_RIB_DIR24_8_8B,
+     RTE_RIB_TYPE_MAX
+};

If the plan is to support multiple underlying fib types and algorithms under the rib library, would it not be better to separate out the algorithm part from the data storage part? So have the type just be DIR_24_8, and have the 1, 2, 4 or 8 specified separately.

Yes, we were talk about it in IRC, agree. Now I pass next hop size in union rte_rib_fib_conf inside rte_rib_conf

Quoted 17 lines

lib/librte_rib/rte_rib.h line 83

Quoted 13 lines
lib/librte_rib/rte_rib.h new file +12 -0
+
+enum rte_rib_op {
+     RTE_RIB_ADD,
+     RTE_RIB_DEL
+};
+
+/** RIB nodes allocation type */
+enum rte_rib_alloc_type {
+     RTE_RIB_MALLOC,
+     RTE_RIB_MEMPOOL,
+     RTE_RIB_ALLOC_MAX
+};

Not sure you need this any more. Malloc allocations and mempool allocations are now pretty much the same thing.

Quoted 5 lines

Actually I think to remove malloc. On performance tests with adding/deleting huge amount of routes malloc is slower. Maybe because of fragmentation.
What do you think?

Yes, definitely mempool allocations are the way to go!

Quoted 3 lines
Quoted 3 lines

lib/librte_rib/rte_rib.h line 85

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +2 -0
+
+typedef int (*rte_rib_modify_fn_t)(struct rte_rib *rib, uint32_t

key,

Quoted 10 lines
Quoted 5 lines

lib/librte_rib/rte_rib.h line 86

Quoted 1 line
lib/librte_rib/rte_rib.h new file +1 -0
+     uint8_t depth, uint64_t next_hop, enum rte_rib_op op);

Do you anticipate more ops in future than just add and delete? If not, why not just split this function into two and drop the op struct.

It is difficult question. I'm not ready to make decision at the moment.

Quoted 2 lines
Quoted 2 lines
lib/librte_rib/rte_rib.h new file +1 -0
+typedef int (*rte_rib_tree_lookup_fn_t)(void *fib, const uint32_t

*ips,

Quoted 2 lines
Quoted 2 lines

lib/librte_rib/rte_rib.h line 89

Quoted 2 lines
lib/librte_rib/rte_rib.h new file +2 -0
+     uint64_t *next_hops, const unsigned n);
+typedef struct rte_rib_node *(*rte_rib_alloc_node_fn_t)(struct

rte_rib

Quoted 70 lines
Quoted 70 lines

*rib);

Quoted 69 lines
lib/librte_rib/rte_rib.h new file +69 -0
+typedef void (*rte_rib_free_node_fn_t)(struct rte_rib *rib,
+     struct rte_rib_node *node);
+
+struct rte_rib {
+     char name[RTE_RIB_NAMESIZE];
+     /*pointer to rib trie*/
+     struct rte_rib_node     *trie;
+     /*pointer to dataplane struct*/
+     void    *fib;
+     /*prefix modification*/
+     rte_rib_modify_fn_t     modify;
+     /* Bulk lookup fn*/
+     rte_rib_tree_lookup_fn_t        lookup;
+     /*alloc trie element*/
+     rte_rib_alloc_node_fn_t alloc_node;
+     /*free trie element*/
+     rte_rib_free_node_fn_t  free_node;
+     struct rte_mempool      *node_pool;
+     uint32_t                cur_nodes;
+     uint32_t                cur_routes;
+     int                     max_nodes;
+     int                     node_sz;
+     enum rte_rib_type       type;
+     enum rte_rib_alloc_type alloc_type;
+};
+
+/** RIB configuration structure */
+struct rte_rib_conf {
+     enum rte_rib_type       type;
+     enum rte_rib_alloc_type alloc_type;
+     int     max_nodes;
+     size_t  node_sz;
+     uint64_t def_nh;
+};
+
+/**
+ * Lookup an IP into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  IP to be looked up in the RIB
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup(struct rte_rib *rib, uint32_t key);
+
+/**
+ * Lookup less specific route into the RIB structure
+ *
+ * @param ent
+ *  Pointer to struct rte_rib_node that represents target route
+ * @return
+ *  pointer to struct rte_rib_node that represents
+ *  less specific route on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_parent(struct rte_rib_node *ent);
+
+/**
+ * Lookup prefix into the RIB structure
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be looked up in the RIB
Quoted 8 lines
Quoted 8 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to struct rte_rib_node on success,
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_lookup_exact(struct rte_rib *rib, uint32_t key,

uint8_t

Quoted 5 lines
Quoted 5 lines

depth);

Can you explain the difference between this and regular lookup, and how they would be used. I don't think the names convey the differences sufficiently, and so we should look to rename one or both to be

clearer.

Quoted 2 lines
Quoted 1 line

Regular lookup (rte_rib_tree_lookup) will lookup for most specific node

for

Quoted 9 lines
Quoted 2 lines

passed key.
rte_rib_tree_lookup_exact will lookup node contained key and depth equal

to

Quoted 2 lines

passed in args. It used to find exact route.

So if there is no node exactly matching the parameters, it the lookup_exact returns failure? E.g. if you request a /24 node, it won't return a /8 node that would cover the /24?

yes, it returns failure. Use rte_rib_tree_lookup(without depth) and if you want use rte_rib_tree_lookup_parent after.

Quoted 26 lines
Quoted 8 lines
Quoted 7 lines

lib/librte_rib/rte_rib.h line 169

Quoted 5 lines
lib/librte_rib/rte_rib.h new file +3 -0
+
+/**
+ * Retrieve next more specific prefix from the RIB

s/more/most/

Quoted 6 lines
Quoted 6 lines

lib/librte_rib/rte_rib.h

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+ * that is covered by key/depth supernet
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net address of supernet prefix that covers returned more

specific

Quoted 11 lines
Quoted 11 lines

prefixes

Quoted 9 lines
lib/librte_rib/rte_rib.h new file +9 -0
+ * @param depth
+ *  supernet prefix length
+ * @param cur
+ *   pointer to the last returned prefix to get next prefix
+ *   or
+ *   NULL to get first more specific prefix
+ * @param flag
+ *  -RTE_RIB_GET_NXT_ALL
+ *   get all prefixes from subtrie
Quoted 5 lines
Quoted 4 lines
Quoted 2 lines

By all prefixes do you mean more specific, i.e. the final prefix?

What do you mean the final prefix?

The most specific one, or the longest prefix.

This function is created for different task, not for lpm lookup. This function is for traverse on trie and retrieve routes that falls under the key/depth so term the longest prefix is irrelevant here.
Let me explain with an example. Imagine there are 10.0.0.0/8, 10.0.0.0/24, 10.0.0.10/32 and 10.64.0.0/10 in routing table.
You have code like:

rte_rib_node *tmp = NULL;

do {
    tmp = rte_rib_tree_get_nxt(rib, IPv4(10,0,0,0), 8,
RTE_RIB_GET_NXT_ALL); /* retrieve all routes that belongs to 10.0.0.0/8 */
    if (node)
          printf("%u/%u\n", tmp->key, tmp->depth);
} while (tmp);

in this case you will see all subprefixes, but without 10.0.0.0/8:
10.0.0.0/24
10.0.0.10/32
10.64.0.0/10

If you want 10.0.0.0/8 do
tmp = rte_rib_tree_get_nxt(rib, IPv4(10,0,0,0), 7, RTE_RIB_GET_NXT_ALL); /* retrieve all routes that belongs to 10.0.0.0/7 */

And if you call it with RTE_RIB_GET_NXT_COVER like
tmp = rte_rib_tree_get_nxt(rib, IPv4(10,0,0,0), 8, RTE_RIB_GET_NXT_COVER); you will get
10.0.0.0/24
10.64.0.0/10
without
10.0.0.10/32
This is useful if you want to get gaps for 10.0.0.0/8 that not covered by presented routes.

Quoted 161 lines
Quoted 4 lines
Quoted 4 lines

lib/librte_rib/rte_rib.h line 186

Quoted 4 lines
lib/librte_rib/rte_rib.h new file +2 -0
+ *  -RTE_RIB_GET_NXT_COVER
+ *   get only first more specific prefix even if it have more

specifics

Quoted 7 lines
Quoted 7 lines

lib/librte_rib/rte_rib.h

Quoted 7 lines
lib/librte_rib/rte_rib.h new file +7 -0
+ * @return
+ *  pointer to the next more specific prefix
+ *  or
+ *  NULL if there is no prefixes left
+ */
+struct rte_rib_node *
+rte_rib_tree_get_nxt(struct rte_rib *rib, uint32_t key, uint8_t

depth,

Quoted 6 lines
Quoted 6 lines
Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+     struct rte_rib_node *cur, int flag);
+
+/**
+ * Remove prefix from the RIB
+ *
+ * @param rib
Quoted 8 lines
Quoted 8 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+ *  RIB object handle
+ * @param key
+ *  net to be removed from the RIB
+ * @param depth
+ *  prefix length
+ */
+void
+rte_rib_tree_remove(struct rte_rib *rib, uint32_t key, uint8_t

depth);

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+
+/**
+ * Insert prefix into the RIB
+ *
+ * @param rib
+ *  RIB object handle
+ * @param key
+ *  net to be inserted to the RIB
Quoted 8 lines
Quoted 8 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+ * @param depth
+ *  prefix length
+ * @return
+ *  pointer to new rte_rib_node on success
+ *  NULL otherwise
+ */
+struct rte_rib_node *
+rte_rib_tree_insert(struct rte_rib *rib, uint32_t key, uint8_t

depth);

Quoted 50 lines
Quoted 50 lines
Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+
+/**
+ * Create RIB
+ *
+ * @param name
+ *  RIB name

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * @param socket_id
+ *  NUMA socket ID for RIB table memory allocation
+ * @param conf
+ *  Structure containing the configuration
+ * @return
+ *  Handle to RIB object on success
+ *  NULL otherwise with rte_errno set to an appropriate values.
+ */
+struct rte_rib *
+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf

*conf);

Quoted 33 lines
lib/librte_rib/rte_rib.h new file +33 -0
+
+/**
+ * Find an existing RIB object and return a pointer to it.
+ *
+ * @param name
+ *  Name of the rib object as passed to rte_rib_create()
+ * @return
+ *  Pointer to rib object or NULL if object not found with rte_errno
+ *  set appropriately. Possible rte_errno values include:
+ *   - ENOENT - required entry not available to return.
+ */
+struct rte_rib *
+rte_rib_find_existing(const char *name);
+
+/**
+ * Free an RIB object.
+ *
+ * @param rib
+ *   RIB object handle
+ * @return
+ *   None
+ */
+void
+rte_rib_free(struct rte_rib *rib);
+
+/**
+ * Add a rule to the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip
+ *   IP of the rule to be added to the RIB
+ * @param depth
Quoted 8 lines
Quoted 8 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+ *   Depth of the rule to be added to the RIB
+ * @param next_hop
+ *   Next hop of the rule to be added to the RIB
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_add(struct rte_rib *rib, uint32_t ip, uint8_t depth,

uint64_t

Quoted 11 lines
Quoted 11 lines

next_hop);

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+
+/**
+ * Delete a rule from the RIB.
+ *
+ * @param rib
+ *   RIB object handle
+ * @param ip
+ *   IP of the rule to be deleted from the RIB
+ * @param depth
+ *   Depth of the rule to be deleted from the RIB
Quoted 8 lines
Quoted 8 lines

lib/librte_rib/rte_rib.h

Quoted 8 lines
lib/librte_rib/rte_rib.h new file +8 -0
+ * @return
+ *   0 on success, negative value otherwise
+ */
+int
+rte_rib_delete(struct rte_rib *rib, uint32_t ip, uint8_t depth);
+
+/**
+ * Lookup multiple IP addresses in an FIB. This may be implemented

as a

Quoted 10 lines
Quoted 10 lines

lib/librte_rib/rte_rib.h

Quoted 10 lines
lib/librte_rib/rte_rib.h new file +10 -0
+ * macro, so the address of the function should not be used.
+ *
+ * @param RIB
+ *   RIB object handle
+ * @param ips
+ *   Array of IPs to be looked up in the FIB
+ * @param next_hops
+ *   Next hop of the most specific rule found for IP.
+ *   This is an array of eight byte values.
+ *   If the lookup for the given IP failed, then corresponding

element

Quoted 16 lines
Quoted 16 lines

would

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+ *   contain default value, see description of then next parameter.
+ * @param n
+ *   Number of elements in ips (and next_hops) array to lookup. This

should be a

lib/librte_rib/rte_rib.h

Quoted 3 lines
lib/librte_rib/rte_rib.h new file +3 -0
+ *   compile time constant, and divisible by 8 for best performance.
+ * @param defv
+ *   Default value to populate into corresponding element of hop[]

array,

Quoted 6 lines
lib/librte_rib/rte_rib.h new file +6 -0
+ *   if lookup would fail.
+ *  @return
+ *   -EINVAL for incorrect arguments, otherwise 0
+ */
+#define rte_rib_fib_lookup_bulk(rib, ips, next_hops, n)      \
+     rib->lookup(rib->fib, ips, next_hops, n)
Quoted 5 lines
Quoted 5 lines

My main thought here is whether this needs to be a function at all? Given that it takes a full burst of addresses in a single go, how much performance would actually be lost by making this a regular function in the C file?
IF we do convert this to a regular function, then a lot of the

structure

Quoted 3 lines
Quoted 3 lines

definitions above - most importantly, the rib structure itself - can probably be moved to a private header file and not exposed to applications at all. This will make ABI compatibility a *lot* easier,

as

Quoted 9 lines
Quoted 4 lines
Quoted 2 lines

the structures can be changed without affecting the public ABI.

I didn't quite understand what you mean.

Sorry, by "needs to be a function" in first line read "needs to be a macro". Basically, the point is to not inline anything that doesn't need it. If a function works on a burst of packets, it probably will be fine being a regular function than a macro or inline function.

ok, got it after conversation in IRC

Quoted 3 lines

/Bruce

Signature · 2 lines
Regards,
Vladimir
#7 lore raw

Re: [PATCH v2 1/2] Add RIB library

In reply to Medvedkin Vladimir
Quoted 19 lines · Medvedkin Vladimir

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.
- For dir24_8 implementation it is possible to remove rte_lpm_tbl_entry.depth field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- 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.

Quoted 2 lines

---

Hi again,

some initial comments on the dir24_8 files below.

/Bruce

Quoted 18 lines
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 +++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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

<snip>

Quoted 65 lines
lib/librte_rib/rte_dir24_8.c new file +59 -0
new file mode 100644
index 0000000..a12f882
@@ -0,0 +1,482 @@
+/* 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 <rte_debug.h>
+#include <rte_malloc.h>
+#include <rte_prefetch.h>
+#include <rte_errno.h>
+
+#include <inttypes.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)
+
+#define ROUNDUP(x, y)	 RTE_ALIGN_CEIL(x, (1 << (32 - y)))
+
+static __rte_always_inline __attribute__((pure)) void *
+get_tbl24_p(struct rte_dir24_8_tbl *fib, uint32_t ip)
+{
+	return (void *)&((uint8_t *)fib->tbl24)[(ip &
+		RTE_DIR24_8_TBL24_MASK) >> (8 - fib->nh_sz)];
+}
+
+#define LOOKUP_FUNC(suffix, type, bulk_prefetch)			\
+int rte_dir24_8_lookup_bulk_##suffix(void *fib_p, const uint32_t *ips,	\
+	uint64_t *next_hops, const unsigned 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)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]));		\
+	for (i = 0; i < (n - prefetch_offset); i++) {			\
+		rte_prefetch0(get_tbl24_p(fib, ips[i + prefetch_offset])); \
+		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++) {						\

lib/librte_rib/rte_dir24_8.c line 69

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+		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;							\
+}									\

What is the advantage of doing this as a macro? Unless I'm missing something "suffix" is never actually used in the function at all, and you reference the size of the data from fix->nh_sz. Therefore there can be no performance benefit from having such a lookup function, that I can see.

Therefore, if performance is ok, I suggest just making a single lookup_bulk function that works with all sizes - as the inlined lookup function does in the header.

Alternatively, if you do want specific functions for each
entry size, you still don't need macros. Write a single function that takes as a final parameter the entry-size and use that in calculations rather than nh_sz. Then wrap that function in the set of public ones, passing in the final size parameter explicitly as "1", "2", "4" or "8". The compiler will then know that as a compile-time constant and generate the correct code for each size. However, for this path I suggest you check for any resulting performance improvement, e.g. with l3fwd, as I think it's not likely to be significant.

Quoted 474 lines
lib/librte_rib/rte_dir24_8.c new file +413 -0
+
+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;
+
+	/*case for 0.0.0.0/0*/
+	if (unlikely((ledge == 0) && (redge == 0))) {
+		write_to_fib(fib->tbl24, next_hop << 1, fib->nh_sz, 1 << 24);
+		return 0;
+	}
+	if (ROUNDUP(ledge, 24) <= redge) {
+		if (ledge < ROUNDUP(ledge, 24)) {
+			tbl24_tmp = RTE_DIR24_8_GET_TBL24(fib, ledge);
+			if ((tbl24_tmp & RTE_DIR24_8_VALID_EXT_ENT) !=
+				RTE_DIR24_8_VALID_EXT_ENT) {
+				tbl8_idx = tbl8_alloc(fib, tbl24_tmp);
+				tmp_tbl8_idx = tbl8_get_idx(fib);
+				if ((tbl8_idx < 0) || (tmp_tbl8_idx < 0))
+					return -ENOSPC;
+				tbl8_free_idx(fib, tmp_tbl8_idx);
+				/*update dir24 entry with tbl8 index*/
+				write_to_fib(get_tbl24_p(fib, ledge),
+					(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);
+		}
+		if (ROUNDUP(ledge, 24) < (redge & RTE_DIR24_8_TBL24_MASK)) {
+			write_to_fib(get_tbl24_p(fib, ROUNDUP(ledge, 24)),
+				next_hop << 1, fib->nh_sz,
+				((redge & RTE_DIR24_8_TBL24_MASK) -
+				ROUNDUP(ledge, 24)) >> 8);
+		}
+		if (redge & ~RTE_DIR24_8_TBL24_MASK) {
+			tbl24_tmp = RTE_DIR24_8_GET_TBL24(fib, redge);
+			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),
+					(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 {
+		tbl24_tmp = RTE_DIR24_8_GET_TBL24(fib, ledge);
+		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),
+				(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 = rib->fib;
+
+	if (next_hop > DIR24_8_MAX_NH(fib))
+		return -EINVAL;
+
+	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;
+			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 = rib->fib;
+	RTE_ASSERT(fib);
+
+	ip &= (uint32_t)(UINT64_MAX << (32 - 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) {
+			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,
+	enum rte_dir24_8_nh_sz nh_sz, uint64_t def_nh)
+{
+	char mem_name[RTE_RIB_NAMESIZE];
+	struct rte_dir24_8_tbl *fib;
+
+	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)
+		return fib;
+
+	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) * RTE_DIR24_8_TBL8_NUM_GROUPS,
+			RTE_CACHE_LINE_SIZE, socket_id);
+	if (fib->tbl8 == NULL) {
+		rte_free(fib);
+		return NULL;
+	}
+	fib->def_nh = def_nh;
+	fib->nh_sz = nh_sz;
+	fib->number_tbl8s = RTE_MIN((uint32_t)RTE_DIR24_8_TBL8_NUM_GROUPS,
+				DIR24_8_MAX_NH(fib));
+
+	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_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);
+}
+
+LOOKUP_FUNC(1b, uint8_t, 5)
+LOOKUP_FUNC(2b, uint16_t, 6)
+LOOKUP_FUNC(4b, uint32_t, 15)
+LOOKUP_FUNC(8b, uint64_t, 12)
lib/librte_rib/rte_dir24_8.h new file +54 -0
new file mode 100644
index 0000000..f779409
@@ -0,0 +1,116 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _RTE_DIR24_8_H_
+#define _RTE_DIR24_8_H_
+
+/**
+ * @file
+ * RTE Longest Prefix Match (LPM)
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** @internal Total number of tbl24 entries. */
+#define RTE_DIR24_8_TBL24_NUM_ENT	(1 << 24)
+
+/** Maximum depth value possible for IPv4 LPM. */
+#define RTE_DIR24_8_MAX_DEPTH		32
+
+/** @internal Number of entries in a tbl8 group. */
+#define RTE_DIR24_8_TBL8_GRP_NUM_ENT	256
+
+/** @internal Total number of tbl8 groups in the tbl8. */
+#define RTE_DIR24_8_TBL8_NUM_GROUPS	65536
+
+/** @internal bitmask with valid and valid_group fields set */
+#define RTE_DIR24_8_VALID_EXT_ENT	0x01
+
+#define RTE_DIR24_8_TBL24_MASK		0xffffff00
+
+/** Size of nexthop (1 << nh_sz) bits */
+enum rte_dir24_8_nh_sz {
+	RTE_DIR24_8_1B,
+	RTE_DIR24_8_2B,
+	RTE_DIR24_8_4B,
+	RTE_DIR24_8_8B
+};
+
+
+#define DIR24_8_BITS_IN_NH(fib)		(8 * (1 << fib->nh_sz))
+#define DIR24_8_MAX_NH(fib)	((1ULL << (DIR24_8_BITS_IN_NH(fib) - 1)) - 1)
+
+#define DIR24_8_TBL_IDX(a, fib)		((a) >> (3 - fib->nh_sz))
+#define DIR24_8_PSD_IDX(a, fib)		((a) & ((1 << (3 - fib->nh_sz)) - 1))
+
+#define DIR24_8_TBL24_VAL(ip)	(ip >> 8)
+#define DIR24_8_TBL8_VAL(res, ip)					\
+	((res >> 1) * RTE_DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip)	\
+
+#define DIR24_8_LOOKUP_MSK						\
+	(((1ULL << ((1 << (fib->nh_sz + 3)) - 1)) << 1) - 1)		\

lib/librte_rib/rte_dir24_8.h line 64

Quoted 10 lines
lib/librte_rib/rte_dir24_8.h new file +10 -0
+
+#define RTE_DIR24_8_GET_TBL24(fib, ip)					\
+	((fib->tbl24[DIR24_8_TBL_IDX(DIR24_8_TBL24_VAL(ip), fib)] >>	\
+	(DIR24_8_PSD_IDX(DIR24_8_TBL24_VAL(ip), fib) *			\
+	DIR24_8_BITS_IN_NH(fib))) & DIR24_8_LOOKUP_MSK)			\
+
+#define RTE_DIR24_8_GET_TBL8(fib, res, ip)				\
+	((fib->tbl8[DIR24_8_TBL_IDX(DIR24_8_TBL8_VAL(res, ip), fib)] >>	\
+	(DIR24_8_PSD_IDX(DIR24_8_TBL8_VAL(res, ip), fib) *		\
+	DIR24_8_BITS_IN_NH(fib))) & DIR24_8_LOOKUP_MSK)			\

I would strongly suggest making each of the above macros into inline functions instead. It would allow easier readability since you have parameter types and can split things across lines easier. Also, some comments might be good too.

+

Quoted 18 lines
lib/librte_rib/rte_dir24_8.h new file +18 -0
+
+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;
+	enum rte_dir24_8_nh_sz	nh_sz;	/**< Size of nexthop entry */
+	uint64_t	*tbl8;		/**< LPM tbl8 table. */
+	uint64_t	*tbl8_idxes;
+	uint64_t	tbl24[0] __rte_cache_aligned; /**< LPM tbl24 table. */
+};
+
+struct rte_dir24_8_tbl *rte_dir24_8_create(const char *name, int socket_id,
+	enum rte_dir24_8_nh_sz nh_sz, uint64_t def_nh);
+void rte_dir24_8_free(void *fib_p);
+int rte_dir24_8_modify(struct rte_rib *rib, uint32_t key,
+	uint8_t depth, uint64_t next_hop, enum rte_rib_op op);
+int rte_dir24_8_lookup_bulk_1b(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned n);

lib/librte_rib/rte_dir24_8.h line 93

Quoted 10 lines
lib/librte_rib/rte_dir24_8.h new file +10 -0
+int rte_dir24_8_lookup_bulk_2b(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned n);
+int rte_dir24_8_lookup_bulk_4b(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned n);
+int rte_dir24_8_lookup_bulk_8b(void *fib_p, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned n);
+
+
+static inline int
+rte_dir24_8_lookup(void *fib_p, uint32_t ip, uint64_t *next_hop)

Why use void * as parameter, since the proper type is defined just above?

Quoted 5 lines
lib/librte_rib/rte_dir24_8.h new file +5 -0
+{
+	uint64_t res;
+	struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+	RTE_RIB_RETURN_IF_TRUE(((fib == NULL) || (ip == NULL) ||

lib/librte_rib/rte_dir24_8.h line 108

Quoted 10 lines
lib/librte_rib/rte_dir24_8.h new file +10 -0
+		(next_hop == NULL)), -EINVAL);
+
+	res = RTE_DIR24_8_GET_TBL24(fib, ip);
+	if (unlikely((res & RTE_DIR24_8_VALID_EXT_ENT) ==
+		RTE_DIR24_8_VALID_EXT_ENT)) {
+		res = RTE_DIR24_8_GET_TBL8(fib, res, ip);
+	}
+	*next_hop = res >> 1;
+	return 0;
+}

Do we need this static inline function? Can the bulk functions do on their own? If we can remove this, we can move the most of the header file contents, especially the structures, out of the public header. That would greatly improve the ease with which ABI can be maintained.

Quoted 8 lines
lib/librte_rib/rte_dir24_8.h new file +8 -0
+
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_DIR24_8_H_ */
+
#8 lore raw

Re: [PATCH v2 1/2] Add RIB library

2018-03-29 13:27 GMT+03:00 Bruce Richardson <[email protected]>:

Quoted 134 lines · Medvedkin Vladimir
Quoted 5 lines

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

Quoted 8 lines

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.
- For dir24_8 implementation it is possible to remove

rte_lpm_tbl_entry.depth

Quoted 4 lines

field that helps to save 6 bits.
- Also new dir24_8 implementation supports different next_hop sizes (1/2/4/8 bytes per next hop)
- Removed RTE_LPM_LOOKUP_SUCCESS to save 1 bit and to eleminate ternary

operator.

Quoted 4 lines

Instead it returns special default value if there is no route.

---

Hi again,

some initial comments on the dir24_8 files below.

/Bruce

Quoted 5 lines
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  22 ++
 lib/librte_rib/rte_dir24_8.c       | 482 ++++++++++++++++++++++++++++++

+++

Quoted 2 lines
 lib/librte_rib/rte_dir24_8.h       | 116 ++++++++
 lib/librte_rib/rte_rib.c           | 526 ++++++++++++++++++++++++++++++

+++++++

Quoted 11 lines
 lib/librte_rib/rte_rib.h           | 322 +++++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 mk/rte.app.mk                      |   1 +
 10 files changed, 1496 insertions(+)
 create mode 100644 lib/librte_rib/Makefile
 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

<snip>

Quoted 32 lines
lib/librte_rib/rte_dir24_8.c new file +26 -0
new file mode 100644
index 0000000..a12f882
@@ -0,0 +1,482 @@
+/* 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 <rte_debug.h>
+#include <rte_malloc.h>
+#include <rte_prefetch.h>
+#include <rte_errno.h>
+
+#include <inttypes.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)
+
+#define ROUNDUP(x, y)         RTE_ALIGN_CEIL(x, (1 << (32 - y)))

lib/librte_rib/rte_dir24_8.c line 36

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+
+static __rte_always_inline __attribute__((pure)) void *
+get_tbl24_p(struct rte_dir24_8_tbl *fib, uint32_t ip)
+{
+     return (void *)&((uint8_t *)fib->tbl24)[(ip &
+             RTE_DIR24_8_TBL24_MASK) >> (8 - fib->nh_sz)];
+}
+
+#define LOOKUP_FUNC(suffix, type, bulk_prefetch)                     \
+int rte_dir24_8_lookup_bulk_##suffix(void *fib_p, const uint32_t

*ips, \

Quoted 4 lines
lib/librte_rib/rte_dir24_8.c new file +4 -0
+     uint64_t *next_hops, const unsigned n)                          \
+{                                                                    \
+     struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;  \
+     uint64_t tmp;                                                   \

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+     uint32_t i;                                                     \
+     uint32_t prefetch_offset = RTE_MIN((unsigned)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]));                \
+     for (i = 0; i < (n - prefetch_offset); i++) {                   \
+             rte_prefetch0(get_tbl24_p(fib, ips[i + prefetch_offset]));

\

lib/librte_rib/rte_dir24_8.c

Quoted 5 lines
lib/librte_rib/rte_dir24_8.c new file +5 -0
+             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)]; \

lib/librte_rib/rte_dir24_8.c

Quoted 9 lines
lib/librte_rib/rte_dir24_8.c new file +9 -0
+             }                                                       \
+             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)]; \

lib/librte_rib/rte_dir24_8.c line 69

Quoted 5 lines
lib/librte_rib/rte_dir24_8.c new file +5 -0
+             }                                                       \
+             next_hops[i] = tmp >> 1;                                \
+     }                                                               \
+     return 0;                                                       \
+}                                                                    \
Quoted 5 lines

What is the advantage of doing this as a macro? Unless I'm missing something "suffix" is never actually used in the function at all, and you reference the size of the data from fix->nh_sz. Therefore there can be no performance benefit from having such a lookup function, that I can see.

suffix is to create 4 different function names, look at the end of rte_dir24_8.c, there are
LOOKUP_FUNC(1b, uint8_t, 5)
LOOKUP_FUNC(2b, uint16_t, 6)
LOOKUP_FUNC(4b, uint32_t, 15)
LOOKUP_FUNC(8b, uint64_t, 12)

Now I made single lookup function that references the size of the data from fib->nh_sz instead of static casting to passed type in macro. was:
BULK RIB Lookup: 24.2 cycles (fails = 0.0%)
become:
BULK RIB Lookup: 26.1 cycles (fails = 0.0%)
proc [email protected]

Quoted 547 lines

Therefore, if performance is ok, I suggest just making a single lookup_bulk function that works with all sizes - as the inlined lookup function does in the header.

Alternatively, if you do want specific functions for each
entry size, you still don't need macros. Write a single function that takes as a final parameter the entry-size and use that in calculations rather than nh_sz. Then wrap that function in the set of public ones, passing in the final size parameter explicitly as "1", "2", "4" or "8". The compiler will then know that as a compile-time constant and generate the correct code for each size. However, for this path I suggest you check for any resulting performance improvement, e.g. with l3fwd, as I think it's not likely to be significant.

lib/librte_rib/rte_dir24_8.c

Quoted 3 lines
lib/librte_rib/rte_dir24_8.c new file +3 -0
+
+static void
+write_to_fib(void *ptr, uint64_t val, enum rte_dir24_8_nh_sz size, int

n)

Quoted 24 lines
lib/librte_rib/rte_dir24_8.c new file +24 -0
+{
+     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;

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+     }
+}
+
+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))

&&

Quoted 28 lines
lib/librte_rib/rte_dir24_8.c new file +28 -0
+             (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) <<

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+             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)

Quoted 57 lines
lib/librte_rib/rte_dir24_8.c new file +57 -0
+{
+     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] =

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+                     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,

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+     uint64_t next_hop)
+{
+     uint64_t        tbl24_tmp;
+     int     tbl8_idx;
+     int tmp_tbl8_idx;
+     uint8_t *tbl8_ptr;
+
+     /*case for 0.0.0.0/0*/
+     if (unlikely((ledge == 0) && (redge == 0))) {
+             write_to_fib(fib->tbl24, next_hop << 1, fib->nh_sz, 1 <<

24);

Quoted 11 lines
lib/librte_rib/rte_dir24_8.c new file +11 -0
+             return 0;
+     }
+     if (ROUNDUP(ledge, 24) <= redge) {
+             if (ledge < ROUNDUP(ledge, 24)) {
+                     tbl24_tmp = RTE_DIR24_8_GET_TBL24(fib, ledge);
+                     if ((tbl24_tmp & RTE_DIR24_8_VALID_EXT_ENT) !=
+                             RTE_DIR24_8_VALID_EXT_ENT) {
+                             tbl8_idx = tbl8_alloc(fib, tbl24_tmp);
+                             tmp_tbl8_idx = tbl8_get_idx(fib);
+                             if ((tbl8_idx < 0) || (tmp_tbl8_idx < 0))
+                                     return -ENOSPC;

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+                             tbl8_free_idx(fib, tmp_tbl8_idx);
+                             /*update dir24 entry with tbl8 index*/
+                             write_to_fib(get_tbl24_p(fib, ledge),
+                                     (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) +

lib/librte_rib/rte_dir24_8.c

Quoted 9 lines
lib/librte_rib/rte_dir24_8.c new file +9 -0
+                             (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);
+             }
+             if (ROUNDUP(ledge, 24) < (redge & RTE_DIR24_8_TBL24_MASK))

{

Quoted 11 lines
lib/librte_rib/rte_dir24_8.c new file +11 -0
+                     write_to_fib(get_tbl24_p(fib, ROUNDUP(ledge, 24)),
+                             next_hop << 1, fib->nh_sz,
+                             ((redge & RTE_DIR24_8_TBL24_MASK) -
+                             ROUNDUP(ledge, 24)) >> 8);
+             }
+             if (redge & ~RTE_DIR24_8_TBL24_MASK) {
+                     tbl24_tmp = RTE_DIR24_8_GET_TBL24(fib, redge);
+                     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)

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+                                     return -ENOSPC;
+                             /*update dir24 entry with tbl8 index*/
+                             write_to_fib(get_tbl24_p(fib, redge),
+                                     (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)

<<

lib/librte_rib/rte_dir24_8.c

Quoted 5 lines
lib/librte_rib/rte_dir24_8.c new file +5 -0
+                             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);

Quoted 44 lines
lib/librte_rib/rte_dir24_8.c new file +44 -0
+                     tbl8_recycle(fib, redge, tbl8_idx);
+             }
+     } else {
+             tbl24_tmp = RTE_DIR24_8_GET_TBL24(fib, ledge);
+             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),
+                             (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 = rib->fib;
+
+     if (next_hop > DIR24_8_MAX_NH(fib))
+             return -EINVAL;
+
+     ledge = ip;

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+     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;
+                     if (ledge == redge) {
+                             ledge = redge +
+                                     (uint32_t)(1ULL << (32 -

tmp->depth));

Quoted 70 lines
lib/librte_rib/rte_dir24_8.c new file +70 -0
+                             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 = rib->fib;
+     RTE_ASSERT(fib);
+
+     ip &= (uint32_t)(UINT64_MAX << (32 - 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) {
+                     rte_rib_tree_remove(rib, ip, depth);
+                     return ret;
+             }
+             if ((depth > 24) && (tmp == NULL))

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+                     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);

lib/librte_rib/rte_dir24_8.c

Quoted 6 lines
lib/librte_rib/rte_dir24_8.c new file +6 -0
+             } 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,

lib/librte_rib/rte_dir24_8.c

Quoted 13 lines
lib/librte_rib/rte_dir24_8.c new file +13 -0
+                                     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,

lib/librte_rib/rte_dir24_8.c

Quoted 8 lines
lib/librte_rib/rte_dir24_8.c new file +8 -0
+     enum rte_dir24_8_nh_sz nh_sz, uint64_t def_nh)
+{
+     char mem_name[RTE_RIB_NAMESIZE];
+     struct rte_dir24_8_tbl *fib;
+
+     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,

lib/librte_rib/rte_dir24_8.c

Quoted 6 lines
lib/librte_rib/rte_dir24_8.c new file +6 -0
+             socket_id);
+     if (fib == NULL)
+             return fib;
+
+     snprintf(mem_name, sizeof(mem_name), "TBL8_%s", name);
+     fib->tbl8 = rte_zmalloc_socket(mem_name,

RTE_DIR24_8_TBL8_GRP_NUM_ENT *

Quoted 78 lines
lib/librte_rib/rte_dir24_8.c new file +38 -0
+                     (1 << nh_sz) * RTE_DIR24_8_TBL8_NUM_GROUPS,
+                     RTE_CACHE_LINE_SIZE, socket_id);
+     if (fib->tbl8 == NULL) {
+             rte_free(fib);
+             return NULL;
+     }
+     fib->def_nh = def_nh;
+     fib->nh_sz = nh_sz;
+     fib->number_tbl8s = RTE_MIN((uint32_t)RTE_DIR24_8_TBL8_NUM_GROUPS,
+                             DIR24_8_MAX_NH(fib));
+
+     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_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);
+}
+
+LOOKUP_FUNC(1b, uint8_t, 5)
+LOOKUP_FUNC(2b, uint16_t, 6)
+LOOKUP_FUNC(4b, uint32_t, 15)
+LOOKUP_FUNC(8b, uint64_t, 12)
lib/librte_rib/rte_dir24_8.h new file +34 -0
new file mode 100644
index 0000000..f779409
@@ -0,0 +1,116 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <[email protected]>
+ */
+
+#ifndef _RTE_DIR24_8_H_
+#define _RTE_DIR24_8_H_
+
+/**
+ * @file
+ * RTE Longest Prefix Match (LPM)
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** @internal Total number of tbl24 entries. */
+#define RTE_DIR24_8_TBL24_NUM_ENT    (1 << 24)
+
+/** Maximum depth value possible for IPv4 LPM. */
+#define RTE_DIR24_8_MAX_DEPTH                32
+
+/** @internal Number of entries in a tbl8 group. */
+#define RTE_DIR24_8_TBL8_GRP_NUM_ENT 256
+
+/** @internal Total number of tbl8 groups in the tbl8. */
+#define RTE_DIR24_8_TBL8_NUM_GROUPS  65536
+
+/** @internal bitmask with valid and valid_group fields set */
+#define RTE_DIR24_8_VALID_EXT_ENT    0x01
+
+#define RTE_DIR24_8_TBL24_MASK               0xffffff00
+
+/** Size of nexthop (1 << nh_sz) bits */

lib/librte_rib/rte_dir24_8.h line 44

Quoted 10 lines
lib/librte_rib/rte_dir24_8.h new file +10 -0
+enum rte_dir24_8_nh_sz {
+     RTE_DIR24_8_1B,
+     RTE_DIR24_8_2B,
+     RTE_DIR24_8_4B,
+     RTE_DIR24_8_8B
+};
+
+
+#define DIR24_8_BITS_IN_NH(fib)              (8 * (1 << fib->nh_sz))
+#define DIR24_8_MAX_NH(fib)  ((1ULL << (DIR24_8_BITS_IN_NH(fib) - 1)) -

1)

lib/librte_rib/rte_dir24_8.h

Quoted 3 lines
lib/librte_rib/rte_dir24_8.h new file +3 -0
+
+#define DIR24_8_TBL_IDX(a, fib)              ((a) >> (3 - fib->nh_sz))
+#define DIR24_8_PSD_IDX(a, fib)              ((a) & ((1 << (3 -

fib->nh_sz)) - 1))

lib/librte_rib/rte_dir24_8.h

Quoted 9 lines
lib/librte_rib/rte_dir24_8.h new file +9 -0
+
+#define DIR24_8_TBL24_VAL(ip)        (ip >> 8)
+#define DIR24_8_TBL8_VAL(res, ip)                                    \
+     ((res >> 1) * RTE_DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip)       \
+
+#define DIR24_8_LOOKUP_MSK                                           \
+     (((1ULL << ((1 << (fib->nh_sz + 3)) - 1)) << 1) - 1)            \
+
+#define RTE_DIR24_8_GET_TBL24(fib, ip)
     \

lib/librte_rib/rte_dir24_8.h line 64

Quoted 9 lines
lib/librte_rib/rte_dir24_8.h new file +8 -0
+     ((fib->tbl24[DIR24_8_TBL_IDX(DIR24_8_TBL24_VAL(ip), fib)] >>    \
+     (DIR24_8_PSD_IDX(DIR24_8_TBL24_VAL(ip), fib) *                  \
+     DIR24_8_BITS_IN_NH(fib))) & DIR24_8_LOOKUP_MSK)                 \
+
+#define RTE_DIR24_8_GET_TBL8(fib, res, ip)                           \
+     ((fib->tbl8[DIR24_8_TBL_IDX(DIR24_8_TBL8_VAL(res, ip), fib)] >> \
+     (DIR24_8_PSD_IDX(DIR24_8_TBL8_VAL(res, ip), fib) *              \
+     DIR24_8_BITS_IN_NH(fib))) & DIR24_8_LOOKUP_MSK)                 \

I would strongly suggest making each of the above macros into inline functions instead. It would allow easier readability since you have parameter types and can split things across lines easier. Also, some comments might be good too.

+

lib/librte_rib/rte_dir24_8.h

Quoted 9 lines
lib/librte_rib/rte_dir24_8.h new file +9 -0
+
+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;
+     enum rte_dir24_8_nh_sz  nh_sz;  /**< Size of nexthop entry */
+     uint64_t        *tbl8;          /**< LPM tbl8 table. */
+     uint64_t        *tbl8_idxes;
+     uint64_t        tbl24[0] __rte_cache_aligned; /**< LPM tbl24

table. */

lib/librte_rib/rte_dir24_8.h

Quoted 3 lines
lib/librte_rib/rte_dir24_8.h new file +3 -0
+};
+
+struct rte_dir24_8_tbl *rte_dir24_8_create(const char *name, int

socket_id,

Quoted 10 lines
lib/librte_rib/rte_dir24_8.h new file +10 -0
+     enum rte_dir24_8_nh_sz nh_sz, uint64_t def_nh);
+void rte_dir24_8_free(void *fib_p);
+int rte_dir24_8_modify(struct rte_rib *rib, uint32_t key,
+     uint8_t depth, uint64_t next_hop, enum rte_rib_op op);
+int rte_dir24_8_lookup_bulk_1b(void *fib_p, const uint32_t *ips,
+     uint64_t *next_hops, const unsigned n);
+int rte_dir24_8_lookup_bulk_2b(void *fib_p, const uint32_t *ips,
+     uint64_t *next_hops, const unsigned n);
+int rte_dir24_8_lookup_bulk_4b(void *fib_p, const uint32_t *ips,
+     uint64_t *next_hops, const unsigned n);
Quoted 8 lines

lib/librte_rib/rte_dir24_8.h line 93

Quoted 6 lines
lib/librte_rib/rte_dir24_8.h new file +6 -0
+int rte_dir24_8_lookup_bulk_8b(void *fib_p, const uint32_t *ips,
+     uint64_t *next_hops, const unsigned n);
+
+
+static inline int
+rte_dir24_8_lookup(void *fib_p, uint32_t ip, uint64_t *next_hop)

Why use void * as parameter, since the proper type is defined just above?

agree, will change to struct rte_dir24_8_tbl *

Quoted 13 lines
Quoted 13 lines
lib/librte_rib/rte_dir24_8.h new file +12 -0
+{
+     uint64_t res;
+     struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+     RTE_RIB_RETURN_IF_TRUE(((fib == NULL) || (ip == NULL) ||
+             (next_hop == NULL)), -EINVAL);
+
+     res = RTE_DIR24_8_GET_TBL24(fib, ip);
+     if (unlikely((res & RTE_DIR24_8_VALID_EXT_ENT) ==
+             RTE_DIR24_8_VALID_EXT_ENT)) {
+             res = RTE_DIR24_8_GET_TBL8(fib, res, ip);
+     }
Quoted 9 lines

lib/librte_rib/rte_dir24_8.h line 108

Quoted 3 lines
lib/librte_rib/rte_dir24_8.h new file +3 -0
+     *next_hop = res >> 1;
+     return 0;
+}

Do we need this static inline function? Can the bulk functions do on their own? If we can remove this, we can move the most of the header file contents, especially the structures, out of the public header. That would greatly improve the ease with which ABI can be maintained.

It was done in some manner to LPM. There was separate single lookup and bulk versions.
Of course it is possible to remove this function at all and use bulk version to lookup single packet. But I thought maybe somebody could use it.

Quoted 11 lines

+

Quoted 7 lines
lib/librte_rib/rte_dir24_8.h new file +7 -0
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_DIR24_8_H_ */
+
Signature · 2 lines
Regards,
Vladimir
#9 lore raw

Re: [PATCH v2 1/2] Add RIB library

Quoted 4 lines · Vladimir Medvedkin

2018-03-29 13:27 GMT+03:00 Bruce Richardson <[email protected]>:

Quoted 2 lines · Medvedkin Vladimir
Quoted 1 line

RIB is an alternative to current LPM library.

<snip>

Quoted 52 lines
Quoted 40 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+#define LOOKUP_FUNC(suffix, type, bulk_prefetch)                     \
+int rte_dir24_8_lookup_bulk_##suffix(void *fib_p, const uint32_t

*ips, \

Quoted 4 lines
lib/librte_rib/rte_dir24_8.c new file +4 -0
+     uint64_t *next_hops, const unsigned n)                          \
+{                                                                    \
+     struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;  \
+     uint64_t tmp;                                                   \

lib/librte_rib/rte_dir24_8.c

Quoted 10 lines
lib/librte_rib/rte_dir24_8.c new file +10 -0
+     uint32_t i;                                                     \
+     uint32_t prefetch_offset = RTE_MIN((unsigned)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]));                \
+     for (i = 0; i < (n - prefetch_offset); i++) {                   \
+             rte_prefetch0(get_tbl24_p(fib, ips[i + prefetch_offset]));

\

lib/librte_rib/rte_dir24_8.c

Quoted 5 lines
lib/librte_rib/rte_dir24_8.c new file +5 -0
+             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)]; \

lib/librte_rib/rte_dir24_8.c

Quoted 9 lines
lib/librte_rib/rte_dir24_8.c new file +9 -0
+             }                                                       \
+             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)]; \

lib/librte_rib/rte_dir24_8.c line 69

Quoted 5 lines
lib/librte_rib/rte_dir24_8.c new file +5 -0
+             }                                                       \
+             next_hops[i] = tmp >> 1;                                \
+     }                                                               \
+     return 0;                                                       \
+}                                                                    \
Quoted 5 lines

What is the advantage of doing this as a macro? Unless I'm missing something "suffix" is never actually used in the function at all, and you reference the size of the data from fix->nh_sz. Therefore there can be no performance benefit from having such a lookup function, that I can see.

suffix is to create 4 different function names, look at the end of rte_dir24_8.c, there are
LOOKUP_FUNC(1b, uint8_t, 5)
LOOKUP_FUNC(2b, uint16_t, 6)
LOOKUP_FUNC(4b, uint32_t, 15)
LOOKUP_FUNC(8b, uint64_t, 12)

Quoted 9 lines

Now I made single lookup function that references the size of the data from fib->nh_sz instead of static casting to passed type in macro. was:
BULK RIB Lookup: 24.2 cycles (fails = 0.0%)
become:
BULK RIB Lookup: 26.1 cycles (fails = 0.0%)
proc [email protected]

So you are saying that it turned out to be faster to do a lookup of the size rather than hardcoding it. Seems strange, but ok.
I'm still confused why the four functions with four different names. What is different between the four implementations. Just the amount of prefetching done? It could still be done by a single call with a compile-time constant parameter. It's whats used a lot in the ring library and works well there.

Quoted 16 lines
Quoted 16 lines

Therefore, if performance is ok, I suggest just making a single lookup_bulk function that works with all sizes - as the inlined lookup function does in the header.

Alternatively, if you do want specific functions for each
entry size, you still don't need macros. Write a single function that takes as a final parameter the entry-size and use that in calculations rather than nh_sz. Then wrap that function in the set of public ones, passing in the final size parameter explicitly as "1", "2", "4" or "8". The compiler will then know that as a compile-time constant and generate the correct code for each size. However, for this path I suggest you check for any resulting performance improvement, e.g. with l3fwd, as I think it's not likely to be significant.

Quoted 1 line

+

<snip>

Quoted 22 lines
Quoted 13 lines
Quoted 13 lines
lib/librte_rib/rte_dir24_8.h new file +12 -0
+{
+     uint64_t res;
+     struct rte_dir24_8_tbl *fib = (struct rte_dir24_8_tbl *)fib_p;
+
+     RTE_RIB_RETURN_IF_TRUE(((fib == NULL) || (ip == NULL) ||
+             (next_hop == NULL)), -EINVAL);
+
+     res = RTE_DIR24_8_GET_TBL24(fib, ip);
+     if (unlikely((res & RTE_DIR24_8_VALID_EXT_ENT) ==
+             RTE_DIR24_8_VALID_EXT_ENT)) {
+             res = RTE_DIR24_8_GET_TBL8(fib, res, ip);
+     }
Quoted 9 lines

lib/librte_rib/rte_dir24_8.h line 108

Quoted 3 lines
lib/librte_rib/rte_dir24_8.h new file +3 -0
+     *next_hop = res >> 1;
+     return 0;
+}

Do we need this static inline function? Can the bulk functions do on their own? If we can remove this, we can move the most of the header file contents, especially the structures, out of the public header. That would greatly improve the ease with which ABI can be maintained.

Quoted 5 lines

It was done in some manner to LPM. There was separate single lookup and bulk versions.
Of course it is possible to remove this function at all and use bulk version to lookup single packet. But I thought maybe somebody could use it.

Yes, I understand that. However, if it's unlikely to be used, I would prioritize having ABI-friendliness over having it.

/Bruce

#10 lore raw

PATCH v2 2/2 Add autotests for RIB library

In reply to Medvedkin Vladimir
---
 test/test/Makefile               |   5 +
 test/test/test_rib.c             | 330 +++++++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.c | 297 +++++++++++++++++++++++++++++++++++
 test/test/test_rib_generate_rt.h |  38 +++++
 test/test/test_rib_lpm_comp.c    | 187 ++++++++++++++++++++++
 test/test/test_rib_perf.c        | 163 +++++++++++++++++++
 6 files changed, 1020 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 a88cc38..7644f6d 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/test_rib.c new file +330 -0

330 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 +187 -0

187 lines not on this page · raw message

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

163 lines not on this page · raw message

Signature · 1 line
1.9.1