[dpdk-dev,v4,1/4] Add RIB library

Message ID 1524780214-23196-2-git-send-email-medvedkinv@gmail.com
State Superseded
Delegated to: Thomas Monjalon
Headers show

Checks

Context Check Description
ci/Intel-compilation fail apply patch file failure
ci/checkpatch warning coding style issues

Commit Message

Vladimir Medvedkin April 26, 2018, 10:03 p.m.
Signed-off-by: Medvedkin Vladimir <medvedkinv@gmail.com>
---
 config/common_base                 |   6 +
 doc/api/doxy-api.conf              |   1 +
 lib/Makefile                       |   2 +
 lib/librte_rib/Makefile            |  23 ++
 lib/librte_rib/meson.build         |   6 +
 lib/librte_rib/rte_rib.c           | 520 +++++++++++++++++++++++++++++++++++++
 lib/librte_rib/rte_rib.h           | 302 +++++++++++++++++++++
 lib/librte_rib/rte_rib_version.map |  18 ++
 lib/meson.build                    |   2 +-
 mk/rte.app.mk                      |   1 +
 10 files changed, 880 insertions(+), 1 deletion(-)
 create mode 100644 lib/librte_rib/Makefile
 create mode 100644 lib/librte_rib/meson.build
 create mode 100644 lib/librte_rib/rte_rib.c
 create mode 100644 lib/librte_rib/rte_rib.h
 create mode 100644 lib/librte_rib/rte_rib_version.map

Comments

Stephen Hemminger April 26, 2018, 10:17 p.m. | #1
On Fri, 27 Apr 2018 01:03:31 +0300
Medvedkin Vladimir <medvedkinv@gmail.com> wrote:

> +static inline int __attribute__((pure))
> +rte_rib_is_right_node(struct rte_rib_node *node)
> +{
> +	return (node->parent->right == node);
> +}
> +

Minor nit (repeated in several places).
DPDK uses Linux (not BSD) style where extra paranthesis are not needed on return statement.
Stephen Hemminger April 26, 2018, 10:18 p.m. | #2
On Fri, 27 Apr 2018 01:03:31 +0300
Medvedkin Vladimir <medvedkinv@gmail.com> wrote:

> +/**
> + * Check if prefix1 {key1/depth1}
> + * is covered by prefix2 {key2/depth2}
> + */
> +static inline int __attribute__((pure))
> +rte_rib_is_covered(uint32_t key1, uint8_t depth1, uint32_t key2, uint8_t depth2)
> +{
> +	return ((((key1 ^ key2) & rte_rib_depth_to_mask(depth2)) == 0)
> +		&& (depth1 > depth2));
> +}

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

Plus you really don't need the  pure attribute for static (or inline) functions
since compiler determines that itself.
Stephen Hemminger April 26, 2018, 10:19 p.m. | #3
On Fri, 27 Apr 2018 01:03:31 +0300
Medvedkin Vladimir <medvedkinv@gmail.com> wrote:

> +	snprintf(rib->name, sizeof(rib->name), "%s", name);

Use strlcpy
Stephen Hemminger April 26, 2018, 10:19 p.m. | #4
On Fri, 27 Apr 2018 01:03:31 +0300
Medvedkin Vladimir <medvedkinv@gmail.com> wrote:

> rib = (struct rte_rib *)rte_zmalloc_socket(mem_name,
> +		sizeof(struct rte_rib),	RTE_CACHE_LINE_SIZE, socket_id);

Cast of void * pointer is not required in C.
Stephen Hemminger April 26, 2018, 10:20 p.m. | #5
On Fri, 27 Apr 2018 01:03:31 +0300
Medvedkin Vladimir <medvedkinv@gmail.com> wrote:

> +		/**
> +		 * Intermediate node found.
> +		 * Previous rte_rib_tree_lookup_exact() returned NULL
> +		 * but node with proper search criteria is found.
> +		 * Validate intermediate node and return.
> +		 */
> +		if ((key == (*tmp)->key) && (depth == (*tmp)->depth)) {

Comments with /** are intended to be docbook comments.
This is not a docbook comment for a function.
Vladimir Medvedkin April 27, 2018, 6:45 a.m. | #6
Hi Stephen,

Thanks for comments! Will fix in next version.

2018-04-27 1:20 GMT+03:00 Stephen Hemminger <stephen@networkplumber.org>:

> On Fri, 27 Apr 2018 01:03:31 +0300
> Medvedkin Vladimir <medvedkinv@gmail.com> wrote:
>
> > +             /**
> > +              * Intermediate node found.
> > +              * Previous rte_rib_tree_lookup_exact() returned NULL
> > +              * but node with proper search criteria is found.
> > +              * Validate intermediate node and return.
> > +              */
> > +             if ((key == (*tmp)->key) && (depth == (*tmp)->depth)) {
>
> Comments with /** are intended to be docbook comments.
> This is not a docbook comment for a function.
>
Bruce Richardson June 29, 2018, 1:54 p.m. | #7
On Fri, Apr 27, 2018 at 01:03:31AM +0300, Medvedkin Vladimir wrote:
> Signed-off-by: Medvedkin Vladimir <medvedkinv@gmail.com>
> ---
>  config/common_base                 |   6 +
>  doc/api/doxy-api.conf              |   1 +
>  lib/Makefile                       |   2 +
>  lib/librte_rib/Makefile            |  23 ++
>  lib/librte_rib/meson.build         |   6 +
>  lib/librte_rib/rte_rib.c           | 520 +++++++++++++++++++++++++++++++++++++
>  lib/librte_rib/rte_rib.h           | 302 +++++++++++++++++++++
>  lib/librte_rib/rte_rib_version.map |  18 ++
>  lib/meson.build                    |   2 +-
>  mk/rte.app.mk                      |   1 +
>  10 files changed, 880 insertions(+), 1 deletion(-)
>  create mode 100644 lib/librte_rib/Makefile
>  create mode 100644 lib/librte_rib/meson.build
>  create mode 100644 lib/librte_rib/rte_rib.c
>  create mode 100644 lib/librte_rib/rte_rib.h
>  create mode 100644 lib/librte_rib/rte_rib_version.map
> 
<snip>
> --- /dev/null
> +++ b/lib/librte_rib/meson.build
> @@ -0,0 +1,6 @@
> +# SPDX-License-Identifier: BSD-3-Clause
> +# Copyright(c) 2017 Intel Corporation
> +
> +sources = files('rte_rib.c', 'rte_dir24_8.c')
> +headers = files('rte_rib.h', 'rte_dir24_8.h')
> +deps += ['mempool']

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

/Bruce
Bruce Richardson June 29, 2018, 2:02 p.m. | #8
On Fri, Apr 27, 2018 at 01:03:31AM +0300, Medvedkin Vladimir wrote:
> Signed-off-by: Medvedkin Vladimir <medvedkinv@gmail.com>
> ---
>  config/common_base                 |   6 +
>  doc/api/doxy-api.conf              |   1 +
>  lib/Makefile                       |   2 +
>  lib/librte_rib/Makefile            |  23 ++
>  lib/librte_rib/meson.build         |   6 +
>  lib/librte_rib/rte_rib.c           | 520 +++++++++++++++++++++++++++++++++++++
>  lib/librte_rib/rte_rib.h           | 302 +++++++++++++++++++++
>  lib/librte_rib/rte_rib_version.map |  18 ++
>  lib/meson.build                    |   2 +-
>  mk/rte.app.mk                      |   1 +
>  10 files changed, 880 insertions(+), 1 deletion(-)
>  create mode 100644 lib/librte_rib/Makefile
>  create mode 100644 lib/librte_rib/meson.build
>  create mode 100644 lib/librte_rib/rte_rib.c
>  create mode 100644 lib/librte_rib/rte_rib.h
>  create mode 100644 lib/librte_rib/rte_rib_version.map
> 
<snip>
> +}
> +
> +int
> +rte_rib_fib_lookup_bulk(struct rte_rib *rib, uint32_t *ips,
> +	uint64_t *next_hops, int n)
> +{
> +	return rib->lookup(rib->fib, ips, next_hops, n);
> +}

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

/Bruce

Patch

diff --git a/config/common_base b/config/common_base
index 7e45412..833442c 100644
--- a/config/common_base
+++ b/config/common_base
@@ -709,6 +709,12 @@  CONFIG_RTE_LIBRTE_LPM=y
 CONFIG_RTE_LIBRTE_LPM_DEBUG=n
 
 #
+# Compile librte_rib
+#
+CONFIG_RTE_LIBRTE_RIB=y
+CONFIG_RTE_LIBRTE_RIB_DEBUG=n
+
+#
 # Compile librte_acl
 #
 CONFIG_RTE_LIBRTE_ACL=y
diff --git a/doc/api/doxy-api.conf b/doc/api/doxy-api.conf
index ad8bdcf..8f42564 100644
--- a/doc/api/doxy-api.conf
+++ b/doc/api/doxy-api.conf
@@ -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 \
diff --git a/lib/Makefile b/lib/Makefile
index 965be6c..cb1d4e0 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -43,6 +43,8 @@  DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd
 DEPDIRS-librte_efd := librte_eal librte_ring librte_hash
 DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm
 DEPDIRS-librte_lpm := librte_eal
+DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib
+DEPDIRS-librte_rib := librte_eal librte_mempool
 DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl
 DEPDIRS-librte_acl := librte_eal
 DIRS-$(CONFIG_RTE_LIBRTE_MEMBER) += librte_member
diff --git a/lib/librte_rib/Makefile b/lib/librte_rib/Makefile
new file mode 100644
index 0000000..f6431b6
--- /dev/null
+++ b/lib/librte_rib/Makefile
@@ -0,0 +1,23 @@ 
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+
+include $(RTE_SDK)/mk/rte.vars.mk
+
+# library name
+LIB = librte_rib.a
+
+CFLAGS += -O3
+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)
+LDLIBS += -lrte_eal -lrte_mempool
+
+EXPORT_MAP := rte_rib_version.map
+
+LIBABIVER := 1
+
+# all source are stored in SRCS-y
+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c rte_dir24_8.c
+
+# install this header file
+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h rte_dir24_8.h
+
+include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_rib/meson.build b/lib/librte_rib/meson.build
new file mode 100644
index 0000000..0f4b865
--- /dev/null
+++ b/lib/librte_rib/meson.build
@@ -0,0 +1,6 @@ 
+# SPDX-License-Identifier: BSD-3-Clause
+# Copyright(c) 2017 Intel Corporation
+
+sources = files('rte_rib.c', 'rte_dir24_8.c')
+headers = files('rte_rib.h', 'rte_dir24_8.h')
+deps += ['mempool']
diff --git a/lib/librte_rib/rte_rib.c b/lib/librte_rib/rte_rib.c
new file mode 100644
index 0000000..67a637b
--- /dev/null
+++ b/lib/librte_rib/rte_rib.c
@@ -0,0 +1,520 @@ 
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ */
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/queue.h>
+
+#include <rte_eal.h>
+#include <rte_eal_memconfig.h>
+#include <rte_common.h>
+#include <rte_tailq.h>
+#include <rte_errno.h>
+#include <rte_rwlock.h>
+#include <rte_memory.h>
+#include <rte_memzone.h>
+#include <rte_mempool.h>
+#include <rte_malloc.h>
+#include <rte_log.h>
+
+#include <rte_rib.h>
+#include <rte_dir24_8.h>
+
+TAILQ_HEAD(rte_rib_list, rte_tailq_entry);
+static struct rte_tailq_elem rte_rib_tailq = {
+	.name = "RTE_RIB",
+};
+EAL_REGISTER_TAILQ(rte_rib_tailq)
+
+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_lookup_fn_t	lookup;
+	struct rte_mempool	*node_pool;
+	uint32_t		cur_nodes;
+	uint32_t		cur_routes;
+	int			max_nodes;
+	int			node_sz;
+	enum rte_rib_type	type;
+};
+
+static inline int __attribute__((pure))
+rte_rib_is_right_node(struct rte_rib_node *node)
+{
+	return (node->parent->right == node);
+}
+
+/**
+ * Check if prefix1 {key1/depth1}
+ * is covered by prefix2 {key2/depth2}
+ */
+static inline int __attribute__((pure))
+rte_rib_is_covered(uint32_t key1, uint8_t depth1, uint32_t key2, uint8_t depth2)
+{
+	return ((((key1 ^ key2) & rte_rib_depth_to_mask(depth2)) == 0)
+		&& (depth1 > depth2));
+}
+
+static inline struct rte_rib_node *__attribute__((pure))
+rte_rib_get_nxt_node(struct rte_rib_node *node, uint32_t key)
+{
+	return ((key & (1 << (31 - node->depth))) ? node->right : node->left);
+}
+
+static struct rte_rib_node *
+rte_rib_node_alloc(struct rte_rib *rib)
+{
+	struct rte_rib_node *ent;
+	int ret;
+
+	ret = rte_mempool_get(rib->node_pool, (void *)&ent);
+	if (unlikely(ret != 0))
+		return NULL;
+	++rib->cur_nodes;
+	return ent;
+}
+
+static void
+rte_rib_node_free(struct rte_rib *rib, struct rte_rib_node *ent)
+{
+	--rib->cur_nodes;
+	rte_mempool_put(rib->node_pool, ent);
+}
+
+struct rte_rib_node *
+rte_rib_tree_lookup(struct rte_rib *rib, uint32_t key)
+{
+	struct rte_rib_node *cur = rib->trie;
+	struct rte_rib_node *prev = NULL;
+
+	while ((cur != NULL) && (((cur->key ^ key) &
+			rte_rib_depth_to_mask(cur->depth)) == 0)) {
+		if ((cur->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE)
+			prev = cur;
+		cur = rte_rib_get_nxt_node(cur, key);
+	}
+	return prev;
+}
+
+struct rte_rib_node *
+rte_rib_tree_lookup_parent(struct rte_rib_node *ent)
+{
+	struct rte_rib_node *tmp;
+
+	if (ent == NULL)
+		return NULL;
+	tmp = ent->parent;
+	while ((tmp != NULL) &&	(tmp->flag & RTE_RIB_VALID_NODE)
+			!= RTE_RIB_VALID_NODE) {
+		tmp = tmp->parent;
+	}
+	return tmp;
+}
+
+struct rte_rib_node *
+rte_rib_tree_lookup_exact(struct rte_rib *rib, uint32_t key, uint8_t depth)
+{
+	struct rte_rib_node *cur = rib->trie;
+
+	key &= rte_rib_depth_to_mask(depth);
+	while (cur != NULL) {
+		if ((cur->key == key) && (cur->depth == depth) &&
+				(cur->flag & RTE_RIB_VALID_NODE))
+			return cur;
+		if ((cur->depth > depth) ||
+				(((uint64_t)key >> (32 - cur->depth)) !=
+				((uint64_t)cur->key >> (32 - cur->depth))))
+			break;
+		cur = rte_rib_get_nxt_node(cur, key);
+	}
+	return NULL;
+}
+
+/**
+ *  Traverses on subtree and retrieves more specific routes
+ *  for a given in args key/depth prefix
+ *  last = NULL means the first invocation
+ */
+struct rte_rib_node *
+rte_rib_tree_get_nxt(struct rte_rib *rib, uint32_t key,
+	uint8_t depth, struct rte_rib_node *last, int flag)
+{
+	struct rte_rib_node *tmp, *prev = NULL;
+
+	if (last == NULL) {
+		tmp = rib->trie;
+		while ((tmp) && (tmp->depth < depth))
+			tmp = rte_rib_get_nxt_node(tmp, key);
+	} else {
+		tmp = last;
+		while ((tmp->parent != NULL) && (rte_rib_is_right_node(tmp) ||
+				(tmp->parent->right == NULL))) {
+			tmp = tmp->parent;
+			if ((tmp->flag & RTE_RIB_VALID_NODE) &&
+					(rte_rib_is_covered(tmp->key,
+					tmp->depth, key, depth)))
+				return tmp;
+		}
+		tmp = (tmp->parent) ? tmp->parent->right : NULL;
+	}
+	while (tmp) {
+		if ((tmp->flag & RTE_RIB_VALID_NODE) &&
+				(rte_rib_is_covered(tmp->key, tmp->depth,
+				key, depth))) {
+			prev = tmp;
+			if (flag == RTE_RIB_GET_NXT_COVER)
+				return prev;
+		}
+		tmp = (tmp->left) ? tmp->left : tmp->right;
+	}
+	return prev;
+}
+
+void
+rte_rib_tree_remove(struct rte_rib *rib, uint32_t key, uint8_t depth)
+{
+	struct rte_rib_node *cur, *prev, *child;
+
+	cur = rte_rib_tree_lookup_exact(rib, key, depth);
+	if (cur == NULL)
+		return;
+
+	--rib->cur_routes;
+	cur->flag &= ~RTE_RIB_VALID_NODE;
+	while ((cur->flag & RTE_RIB_VALID_NODE) != RTE_RIB_VALID_NODE) {
+		if ((cur->left != NULL) && (cur->right != NULL))
+			return;
+		child = (cur->left == NULL) ? cur->right : cur->left;
+		if (child != NULL)
+			child->parent = cur->parent;
+		if (cur->parent == NULL) {
+			rib->trie = child;
+			rte_rib_node_free(rib, cur);
+			return;
+		}
+		if (cur->parent->left == cur)
+			cur->parent->left = child;
+		else
+			cur->parent->right = child;
+		prev = cur;
+		cur = cur->parent;
+		rte_rib_node_free(rib, prev);
+	}
+}
+
+struct rte_rib_node *
+rte_rib_tree_insert(struct rte_rib *rib, uint32_t key, uint8_t depth)
+{
+	struct rte_rib_node **tmp = &rib->trie;
+	struct rte_rib_node *prev = NULL;
+	struct rte_rib_node *new_node = NULL;
+	struct rte_rib_node *common_node = NULL;
+	int d = 0;
+	uint32_t common_prefix;
+	uint8_t common_depth;
+
+	if (depth > 32) {
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	key &= rte_rib_depth_to_mask(depth);
+	new_node = rte_rib_tree_lookup_exact(rib, key, depth);
+	if (new_node != NULL) {
+		rte_errno = EEXIST;
+		return NULL;
+	}
+
+	new_node = rte_rib_node_alloc(rib);
+	if (new_node == NULL) {
+		rte_errno = ENOMEM;
+		return NULL;
+	}
+	new_node->left = NULL;
+	new_node->right = NULL;
+	new_node->parent = NULL;
+	new_node->key = key;
+	new_node->depth = depth;
+	new_node->flag = RTE_RIB_VALID_NODE;
+
+	/* traverse down the tree to find matching node or closest matching */
+	while (1) {
+		/* insert as the last node in the branch */
+		if (*tmp == NULL) {
+			*tmp = new_node;
+			new_node->parent = prev;
+			++rib->cur_routes;
+			return *tmp;
+		}
+		/**
+		 * Intermediate node found.
+		 * Previous rte_rib_tree_lookup_exact() returned NULL
+		 * but node with proper search criteria is found.
+		 * Validate intermediate node and return.
+		 */
+		if ((key == (*tmp)->key) && (depth == (*tmp)->depth)) {
+			rte_rib_node_free(rib, new_node);
+			(*tmp)->flag |= RTE_RIB_VALID_NODE;
+			++rib->cur_routes;
+			return *tmp;
+		}
+		d = (*tmp)->depth;
+		if ((d >= depth) || (((uint64_t)key >> (32 - d)) !=
+				((uint64_t)(*tmp)->key >> (32 - d))))
+			break;
+		prev = *tmp;
+		tmp = (key & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;
+	}
+	/* closest node found, new_node should be inserted in the middle */
+	common_depth = RTE_MIN(depth, (*tmp)->depth);
+	common_prefix = key ^ (*tmp)->key;
+	d = __builtin_clz(common_prefix);
+
+	common_depth = RTE_MIN(d, common_depth);
+	common_prefix = key & rte_rib_depth_to_mask(common_depth);
+	if ((common_prefix == key) && (common_depth == depth)) {
+		/* insert as a parent */
+		if ((*tmp)->key & (1 << (31 - depth)))
+			new_node->right = *tmp;
+		else
+			new_node->left = *tmp;
+		new_node->parent = (*tmp)->parent;
+		(*tmp)->parent = new_node;
+		*tmp = new_node;
+	} else {
+		/* create intermediate node */
+		common_node = rte_rib_node_alloc(rib);
+		if (common_node == NULL) {
+			rte_rib_node_free(rib, new_node);
+			rte_errno = ENOMEM;
+			return NULL;
+		}
+		common_node->key = common_prefix;
+		common_node->depth = common_depth;
+		common_node->flag = 0;
+		common_node->parent = (*tmp)->parent;
+		new_node->parent = common_node;
+		(*tmp)->parent = common_node;
+		if ((new_node->key & (1 << (31 - common_depth))) == 0) {
+			common_node->left = new_node;
+			common_node->right = *tmp;
+		} else {
+			common_node->left = *tmp;
+			common_node->right = new_node;
+		}
+		*tmp = common_node;
+	}
+	++rib->cur_routes;
+	return new_node;
+}
+
+struct rte_rib *
+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf *conf)
+{
+	char mem_name[RTE_RIB_NAMESIZE];
+	struct rte_rib *rib = NULL;
+	struct rte_tailq_entry *te;
+	struct rte_rib_list *rib_list;
+	struct rte_mempool *node_pool;
+
+	/* Check user arguments. */
+	if ((name == NULL) || (conf == NULL) || (socket_id < -1) ||
+			(conf->type >= RTE_RIB_TYPE_MAX) ||
+			(conf->max_nodes == 0) ||
+			(conf->node_sz < sizeof(struct rte_rib_node))) {
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	snprintf(mem_name, sizeof(mem_name), "MP_%s", name);
+	node_pool = rte_mempool_create(mem_name, conf->max_nodes,
+		conf->node_sz, 0, 0, NULL, NULL, NULL, NULL, socket_id, 0);
+
+	if (node_pool == NULL) {
+		RTE_LOG(ERR, LPM,
+			"Can not allocate mempool for RIB %s\n", name);
+		rte_errno = ENOMEM;
+		return NULL;
+	}
+
+	snprintf(mem_name, sizeof(mem_name), "RIB_%s", name);
+	rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* guarantee there's no existing */
+	TAILQ_FOREACH(te, rib_list, next) {
+		rib = (struct rte_rib *)te->data;
+		if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
+			break;
+	}
+	rib = NULL;
+	if (te != NULL) {
+		rte_errno = EEXIST;
+		goto exit;
+	}
+
+	/* allocate tailq entry */
+	te = rte_zmalloc("RIB_TAILQ_ENTRY", sizeof(*te), 0);
+	if (te == NULL) {
+		RTE_LOG(ERR, LPM,
+			"Can not allocate tailq entry for RIB %s\n", name);
+		rte_errno = ENOMEM;
+		goto exit;
+	}
+
+	/* Allocate memory to store the LPM data structures. */
+	rib = (struct rte_rib *)rte_zmalloc_socket(mem_name,
+		sizeof(struct rte_rib),	RTE_CACHE_LINE_SIZE, socket_id);
+	if (rib == NULL) {
+		RTE_LOG(ERR, LPM, "RIB %s memory allocation failed\n", name);
+		rte_errno = ENOMEM;
+		goto free_te;
+	}
+
+	snprintf(rib->name, sizeof(rib->name), "%s", name);
+	rib->trie = NULL;
+	rib->max_nodes = conf->max_nodes;
+	rib->node_sz = conf->node_sz;
+	rib->type = conf->type;
+	rib->node_pool = node_pool;
+
+	switch (conf->type) {
+	case RTE_RIB_DIR24_8:
+		rib->lookup = rte_dir24_8_get_lookup_fn(conf);
+		rib->modify = rte_dir24_8_modify;
+		rib->fib = (void *)rte_dir24_8_create(name, socket_id, conf);
+		if (rib->fib == NULL)
+			goto free_rib;
+		break;
+	case RTE_RIB_TYPE_MAX:
+	default:
+		RTE_LOG(ERR, LPM, "Bad RIB %s type\n", name);
+		rte_errno = EINVAL;
+		goto free_rib;
+	}
+
+	te->data = (void *)rib;
+	TAILQ_INSERT_TAIL(rib_list, te, next);
+
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	return rib;
+
+free_rib:
+	rte_free(rib);
+free_te:
+	rte_free(te);
+exit:
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+	rte_mempool_free(node_pool);
+
+	return NULL;
+}
+
+struct rte_rib *
+rte_rib_find_existing(const char *name)
+{
+	struct rte_rib *rib = NULL;
+	struct rte_tailq_entry *te;
+	struct rte_rib_list *rib_list;
+
+	rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
+
+	rte_rwlock_read_lock(RTE_EAL_TAILQ_RWLOCK);
+	TAILQ_FOREACH(te, rib_list, next) {
+		rib = (struct rte_rib *) te->data;
+		if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)
+			break;
+	}
+	rte_rwlock_read_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	if (te == NULL) {
+		rte_errno = ENOENT;
+		return NULL;
+	}
+
+	return rib;
+}
+
+void
+rte_rib_free(struct rte_rib *rib)
+{
+	struct rte_tailq_entry *te;
+	struct rte_rib_list *rib_list;
+	struct rte_rib_node *tmp = NULL;
+
+	if (rib == NULL)
+		return;
+
+	rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* find our tailq entry */
+	TAILQ_FOREACH(te, rib_list, next) {
+		if (te->data == (void *)rib)
+			break;
+	}
+	if (te != NULL)
+		TAILQ_REMOVE(rib_list, te, next);
+
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	while ((tmp = rte_rib_tree_get_nxt(rib, 0, 0, tmp,
+			RTE_RIB_GET_NXT_ALL)) != NULL)
+		rte_rib_tree_remove(rib, tmp->key, tmp->depth);
+
+	rte_mempool_free(rib->node_pool);
+
+	switch (rib->type) {
+	case RTE_RIB_DIR24_8:
+		rte_dir24_8_free(rib->fib);
+		break;
+	default:
+		break;
+	}
+
+	rte_free(rib);
+	rte_free(te);
+}
+
+int
+rte_rib_add(struct rte_rib *rib, uint32_t ip, uint8_t depth, uint64_t next_hop)
+{
+	if ((rib == NULL) || (depth > RTE_RIB_MAXDEPTH))
+		return -EINVAL;
+
+	return rib->modify(rib, ip, depth, next_hop, RTE_RIB_ADD);
+}
+
+int
+rte_rib_delete(struct rte_rib *rib, uint32_t ip, uint8_t depth)
+{
+	if ((rib == NULL) || (depth > RTE_RIB_MAXDEPTH))
+		return -EINVAL;
+
+	return rib->modify(rib, ip, depth, 0, RTE_RIB_DEL);
+}
+
+int
+rte_rib_fib_lookup_bulk(struct rte_rib *rib, uint32_t *ips,
+	uint64_t *next_hops, int n)
+{
+	return rib->lookup(rib->fib, ips, next_hops, n);
+}
+
+void *
+rte_rib_get_fibp(struct rte_rib *rib)
+{
+	return rib->fib;
+}
diff --git a/lib/librte_rib/rte_rib.h b/lib/librte_rib/rte_rib.h
new file mode 100644
index 0000000..404deb2
--- /dev/null
+++ b/lib/librte_rib/rte_rib.h
@@ -0,0 +1,302 @@ 
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>
+ */
+
+#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 {	\
+	if (cond)					\
+		return retval;				\
+} while (0)
+#else
+#define RTE_RIB_RETURN_IF_TRUE(cond, retval)
+#endif
+
+#define RTE_RIB_VALID_NODE	1
+#define RTE_RIB_GET_NXT_ALL	0
+#define RTE_RIB_GET_NXT_COVER	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
+
+struct rte_rib;
+
+static inline uint32_t __attribute__((pure))
+rte_rib_depth_to_mask(uint8_t depth)
+{
+	return (uint32_t)(UINT64_MAX << (32 - depth));
+}
+
+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];
+};
+
+/** Type of FIB struct*/
+enum rte_rib_type {
+	RTE_RIB_DIR24_8,
+	RTE_RIB_TYPE_MAX
+};
+
+enum rte_rib_op {
+	RTE_RIB_ADD,
+	RTE_RIB_DEL
+};
+
+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);
+typedef int (*rte_rib_lookup_fn_t)(void *fib, const uint32_t *ips,
+	uint64_t *next_hops, const unsigned int n);
+
+/** 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
+};
+
+/** DIR24_8 FIB configuration structure */
+struct rte_rib_dir24_8_conf {
+	uint64_t	def_nh;
+	uint32_t	num_tbl8;
+	enum rte_dir24_8_nh_sz	nh_sz;
+};
+
+/** RIB configuration structure */
+struct rte_rib_conf {
+	enum rte_rib_type	type;
+	int	max_nodes;
+	size_t	node_sz;
+	union {
+		struct rte_rib_dir24_8_conf dir24_8;
+	} fib_conf;
+};
+
+/**
+ * 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
+ * @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);
+
+/**
+ * Retrieve next more specific prefix from the RIB
+ * 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
+ * @param depth
+ *  supernet prefix length
+ * @param last
+ *   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
+ *  -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 *last, 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
+ *   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
+ */
+int
+rte_rib_fib_lookup_bulk(struct rte_rib *rib, uint32_t *ips,
+		uint64_t *next_hops, int n);
+
+/**
+ * Function to retrieve pointer to fib struct
+ *
+ * @param RIB
+ *   RIB object handle
+ * @return
+ *   pointer to fib
+ */
+void *
+rte_rib_get_fibp(struct rte_rib *rib);
+
+#endif /* _RTE_RIB_H_ */
diff --git a/lib/librte_rib/rte_rib_version.map b/lib/librte_rib/rte_rib_version.map
new file mode 100644
index 0000000..b193d6c
--- /dev/null
+++ b/lib/librte_rib/rte_rib_version.map
@@ -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: *;
+};
diff --git a/lib/meson.build b/lib/meson.build
index 73d6f25..6d06304 100644
--- a/lib/meson.build
+++ b/lib/meson.build
@@ -20,7 +20,7 @@  libraries = [ 'compat', # just a header, used for versioning
 	'gro', 'gso', 'ip_frag', 'jobstats',
 	'kni', 'latencystats', 'lpm', 'member',
 	'meter', 'power', 'pdump', 'rawdev',
-	'reorder', 'sched', 'security', 'vhost',
+	'reorder', 'rib', 'sched', 'security', 'vhost',
 	# add pkt framework libs which use other libs from above
 	'port', 'table', 'pipeline',
 	# flow_classify lib depends on pkt framework table lib
diff --git a/mk/rte.app.mk b/mk/rte.app.mk
index a145791..b7c5cce 100644
--- a/mk/rte.app.mk
+++ b/mk/rte.app.mk
@@ -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