Patch Detail
get:
Show a patch.
patch:
Update a patch.
put:
Update a patch.
GET /api/patches/62316/?format=api
{ "id": 62316, "url": "http://patches.dpdk.org/api/patches/62316/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/patch/42e2dd500467aad09197bb31c2738bbeb11400f0.1572621162.git.vladimir.medvedkin@intel.com/", "project": { "id": 1, "url": "http://patches.dpdk.org/api/projects/1/?format=api", "name": "DPDK", "link_name": "dpdk", "list_id": "dev.dpdk.org", "list_email": "dev@dpdk.org", "web_url": "http://core.dpdk.org", "scm_url": "git://dpdk.org/dpdk", "webscm_url": "http://git.dpdk.org/dpdk", "list_archive_url": "https://inbox.dpdk.org/dev", "list_archive_url_format": "https://inbox.dpdk.org/dev/{}", "commit_url_format": "" }, "msgid": "<42e2dd500467aad09197bb31c2738bbeb11400f0.1572621162.git.vladimir.medvedkin@intel.com>", "list_archive_url": "https://inbox.dpdk.org/dev/42e2dd500467aad09197bb31c2738bbeb11400f0.1572621162.git.vladimir.medvedkin@intel.com", "date": "2019-11-01T15:21:34", "name": "[v6,01/12] rib: add RIB library", "commit_ref": null, "pull_url": null, "state": "accepted", "archived": true, "hash": "739031f7762d61e8154e86bddb87e5e6638c2fc4", "submitter": { "id": 1216, "url": "http://patches.dpdk.org/api/people/1216/?format=api", "name": "Vladimir Medvedkin", "email": "vladimir.medvedkin@intel.com" }, "delegate": { "id": 1, "url": "http://patches.dpdk.org/api/users/1/?format=api", "username": "tmonjalo", "first_name": "Thomas", "last_name": "Monjalon", "email": "thomas@monjalon.net" }, "mbox": "http://patches.dpdk.org/project/dpdk/patch/42e2dd500467aad09197bb31c2738bbeb11400f0.1572621162.git.vladimir.medvedkin@intel.com/mbox/", "series": [ { "id": 7198, "url": "http://patches.dpdk.org/api/series/7198/?format=api", "web_url": "http://patches.dpdk.org/project/dpdk/list/?series=7198", "date": "2019-11-01T15:21:33", "name": "lib: add RIB and FIB liraries", "version": 6, "mbox": "http://patches.dpdk.org/series/7198/mbox/" } ], "comments": "http://patches.dpdk.org/api/patches/62316/comments/", "check": "success", "checks": "http://patches.dpdk.org/api/patches/62316/checks/", "tags": {}, "related": [], "headers": { "Return-Path": "<dev-bounces@dpdk.org>", "X-Original-To": "patchwork@inbox.dpdk.org", "Delivered-To": "patchwork@inbox.dpdk.org", "Received": [ "from dpdk.org (dpdk.org [92.243.14.124])\n\tby inbox.dpdk.org (Postfix) with ESMTP id 8538CA00BE;\n\tFri, 1 Nov 2019 16:22:03 +0100 (CET)", "from [92.243.14.124] (localhost [127.0.0.1])\n\tby dpdk.org (Postfix) with ESMTP id AE8AF1C113;\n\tFri, 1 Nov 2019 16:21:54 +0100 (CET)", "from mga09.intel.com (mga09.intel.com [134.134.136.24])\n by dpdk.org (Postfix) with ESMTP id C67001BEAA\n for <dev@dpdk.org>; Fri, 1 Nov 2019 16:21:52 +0100 (CET)", "from orsmga004.jf.intel.com ([10.7.209.38])\n by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384;\n 01 Nov 2019 08:21:52 -0700", "from silpixa00400072.ir.intel.com ([10.237.222.213])\n by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:50 -0700" ], "X-Amp-Result": "SKIPPED(no attachment in message)", "X-Amp-File-Uploaded": "False", "X-ExtLoop1": "1", "X-IronPort-AV": "E=Sophos;i=\"5.68,256,1569308400\"; d=\"scan'208\";a=\"351979064\"", "From": "Vladimir Medvedkin <vladimir.medvedkin@intel.com>", "To": "dev@dpdk.org", "Cc": "bruce.richardson@intel.com, konstantin.ananyev@intel.com,\n thomas@monjalon.net, aconole@redhat.com", "Date": "Fri, 1 Nov 2019 15:21:34 +0000", "Message-Id": "\n <42e2dd500467aad09197bb31c2738bbeb11400f0.1572621162.git.vladimir.medvedkin@intel.com>", "X-Mailer": "git-send-email 2.7.4", "In-Reply-To": [ "<cover.1572621162.git.vladimir.medvedkin@intel.com>", "<cover.1572621162.git.vladimir.medvedkin@intel.com>" ], "References": [ "<cover.1572621162.git.vladimir.medvedkin@intel.com>", "<cover.1568221361.git.vladimir.medvedkin@intel.com>\n <cover.1572621162.git.vladimir.medvedkin@intel.com>" ], "Subject": "[dpdk-dev] [PATCH v6 01/12] rib: add RIB library", "X-BeenThere": "dev@dpdk.org", "X-Mailman-Version": "2.1.15", "Precedence": "list", "List-Id": "DPDK patches and discussions <dev.dpdk.org>", "List-Unsubscribe": "<https://mails.dpdk.org/options/dev>,\n <mailto:dev-request@dpdk.org?subject=unsubscribe>", "List-Archive": "<http://mails.dpdk.org/archives/dev/>", "List-Post": "<mailto:dev@dpdk.org>", "List-Help": "<mailto:dev-request@dpdk.org?subject=help>", "List-Subscribe": "<https://mails.dpdk.org/listinfo/dev>,\n <mailto:dev-request@dpdk.org?subject=subscribe>", "Errors-To": "dev-bounces@dpdk.org", "Sender": "\"dev\" <dev-bounces@dpdk.org>" }, "content": "Add RIB (Routing Information Base) library. This library\nimplements an IPv4 routing table optimized for control plane\noperations. It implements a control plane struct containing routes\nin a tree and provides fast add/del operations for routes.\nAlso it allows to perform fast subtree traversals\n(i.e. retrieve existing subroutes for a giver prefix).\nThis structure will be used as a control plane helper structure\nfor FIB implementation. Also it might be used standalone in other\ndifferent places such as bitmaps for example.\nInternal implementation is level compressed binary trie.\n\nSigned-off-by: Vladimir Medvedkin <vladimir.medvedkin@intel.com>\n---\n config/common_base | 5 +\n doc/api/doxy-api.conf.in | 1 +\n lib/Makefile | 2 +\n lib/librte_rib/Makefile | 25 ++\n lib/librte_rib/meson.build | 8 +\n lib/librte_rib/rte_rib.c | 532 +++++++++++++++++++++++++++++++++++++\n lib/librte_rib/rte_rib.h | 277 +++++++++++++++++++\n lib/librte_rib/rte_rib_version.map | 20 ++\n lib/meson.build | 2 +-\n mk/rte.app.mk | 1 +\n 10 files changed, 872 insertions(+), 1 deletion(-)\n create mode 100644 lib/librte_rib/Makefile\n create mode 100644 lib/librte_rib/meson.build\n create mode 100644 lib/librte_rib/rte_rib.c\n create mode 100644 lib/librte_rib/rte_rib.h\n create mode 100644 lib/librte_rib/rte_rib_version.map", "diff": "diff --git a/config/common_base b/config/common_base\nindex 8ef75c2..5a9d4c3 100644\n--- a/config/common_base\n+++ b/config/common_base\n@@ -894,6 +894,11 @@ CONFIG_RTE_LIBRTE_RCU=y\n CONFIG_RTE_LIBRTE_RCU_DEBUG=n\n \n #\n+# Compile librte_rib\n+#\n+CONFIG_RTE_LIBRTE_RIB=y\n+\n+#\n # Compile librte_lpm\n #\n CONFIG_RTE_LIBRTE_LPM=y\ndiff --git a/doc/api/doxy-api.conf.in b/doc/api/doxy-api.conf.in\nindex 908cee8..3ec012d 100644\n--- a/doc/api/doxy-api.conf.in\n+++ b/doc/api/doxy-api.conf.in\n@@ -54,6 +54,7 @@ INPUT = @TOPDIR@/doc/api/doxy-api-index.md \\\n @TOPDIR@/lib/librte_rawdev \\\n @TOPDIR@/lib/librte_rcu \\\n @TOPDIR@/lib/librte_reorder \\\n+ @TOPDIR@/lib/librte_rib \\\n @TOPDIR@/lib/librte_ring \\\n @TOPDIR@/lib/librte_sched \\\n @TOPDIR@/lib/librte_security \\\ndiff --git a/lib/Makefile b/lib/Makefile\nindex 41c463d..aa5ee1e 100644\n--- a/lib/Makefile\n+++ b/lib/Makefile\n@@ -51,6 +51,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_HASH) += librte_hash\n DEPDIRS-librte_hash := librte_eal librte_ring\n DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd\n DEPDIRS-librte_efd := librte_eal librte_ring librte_hash\n+DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib\n+DEPDIRS-librte_rib := librte_eal librte_mempool\n DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm\n DEPDIRS-librte_lpm := librte_eal librte_hash\n DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl\ndiff --git a/lib/librte_rib/Makefile b/lib/librte_rib/Makefile\nnew file mode 100644\nindex 0000000..79f259a\n--- /dev/null\n+++ b/lib/librte_rib/Makefile\n@@ -0,0 +1,25 @@\n+# SPDX-License-Identifier: BSD-3-Clause\n+# Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>\n+# Copyright(c) 2019 Intel Corporation\n+\n+include $(RTE_SDK)/mk/rte.vars.mk\n+\n+# library name\n+LIB = librte_rib.a\n+\n+CFLAGS += -O3\n+CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR)\n+CFLAGS += -DALLOW_EXPERIMENTAL_API\n+LDLIBS += -lrte_eal -lrte_mempool\n+\n+EXPORT_MAP := rte_rib_version.map\n+\n+LIBABIVER := 1\n+\n+# all source are stored in SRCS-y\n+SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c\n+\n+# install this header file\n+SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h\n+\n+include $(RTE_SDK)/mk/rte.lib.mk\ndiff --git a/lib/librte_rib/meson.build b/lib/librte_rib/meson.build\nnew file mode 100644\nindex 0000000..e7b8920\n--- /dev/null\n+++ b/lib/librte_rib/meson.build\n@@ -0,0 +1,8 @@\n+# SPDX-License-Identifier: BSD-3-Clause\n+# Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>\n+# Copyright(c) 2019 Intel Corporation\n+\n+allow_experimental_apis = true\n+sources = files('rte_rib.c')\n+headers = files('rte_rib.h')\n+deps += ['mempool']\ndiff --git a/lib/librte_rib/rte_rib.c b/lib/librte_rib/rte_rib.c\nnew file mode 100644\nindex 0000000..55d612d\n--- /dev/null\n+++ b/lib/librte_rib/rte_rib.c\n@@ -0,0 +1,532 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#include <stdbool.h>\n+#include <stdint.h>\n+\n+#include <rte_eal.h>\n+#include <rte_eal_memconfig.h>\n+#include <rte_errno.h>\n+#include <rte_malloc.h>\n+#include <rte_mempool.h>\n+#include <rte_rwlock.h>\n+#include <rte_string_fns.h>\n+#include <rte_tailq.h>\n+\n+#include <rte_rib.h>\n+\n+TAILQ_HEAD(rte_rib_list, rte_tailq_entry);\n+static struct rte_tailq_elem rte_rib_tailq = {\n+\t.name = \"RTE_RIB\",\n+};\n+EAL_REGISTER_TAILQ(rte_rib_tailq)\n+\n+#define RTE_RIB_VALID_NODE\t1\n+/* Maximum depth value possible for IPv4 RIB. */\n+#define RIB_MAXDEPTH\t\t32\n+/* Maximum length of a RIB name. */\n+#define RTE_RIB_NAMESIZE\t64\n+\n+struct rte_rib_node {\n+\tstruct rte_rib_node\t*left;\n+\tstruct rte_rib_node\t*right;\n+\tstruct rte_rib_node\t*parent;\n+\tuint32_t\tip;\n+\tuint8_t\t\tdepth;\n+\tuint8_t\t\tflag;\n+\tuint64_t\tnh;\n+\t__extension__ uint64_t\text[0];\n+};\n+\n+struct rte_rib {\n+\tchar\t\tname[RTE_RIB_NAMESIZE];\n+\tstruct rte_rib_node\t*tree;\n+\tstruct rte_mempool\t*node_pool;\n+\tuint32_t\t\tcur_nodes;\n+\tuint32_t\t\tcur_routes;\n+\tuint32_t\t\tmax_nodes;\n+};\n+\n+static inline bool\n+is_valid_node(struct rte_rib_node *node)\n+{\n+\treturn (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE;\n+}\n+\n+static inline bool\n+is_right_node(struct rte_rib_node *node)\n+{\n+\treturn node->parent->right == node;\n+}\n+\n+/*\n+ * Check if ip1 is covered by ip2/depth prefix\n+ */\n+static inline bool\n+is_covered(uint32_t ip1, uint32_t ip2, uint8_t depth)\n+{\n+\treturn ((ip1 ^ ip2) & rte_rib_depth_to_mask(depth)) == 0;\n+}\n+\n+static inline struct rte_rib_node *\n+get_nxt_node(struct rte_rib_node *node, uint32_t ip)\n+{\n+\treturn (ip & (1 << (31 - node->depth))) ? node->right : node->left;\n+}\n+\n+static struct rte_rib_node *\n+node_alloc(struct rte_rib *rib)\n+{\n+\tstruct rte_rib_node *ent;\n+\tint ret;\n+\n+\tret = rte_mempool_get(rib->node_pool, (void *)&ent);\n+\tif (unlikely(ret != 0))\n+\t\treturn NULL;\n+\t++rib->cur_nodes;\n+\treturn ent;\n+}\n+\n+static void\n+node_free(struct rte_rib *rib, struct rte_rib_node *ent)\n+{\n+\t--rib->cur_nodes;\n+\trte_mempool_put(rib->node_pool, ent);\n+}\n+\n+struct rte_rib_node *\n+rte_rib_lookup(struct rte_rib *rib, uint32_t ip)\n+{\n+\tstruct rte_rib_node *cur, *prev = NULL;\n+\n+\tif (rib == NULL) {\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\n+\tcur = rib->tree;\n+\twhile ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) {\n+\t\tif (is_valid_node(cur))\n+\t\t\tprev = cur;\n+\t\tcur = get_nxt_node(cur, ip);\n+\t}\n+\treturn prev;\n+}\n+\n+struct rte_rib_node *\n+rte_rib_lookup_parent(struct rte_rib_node *ent)\n+{\n+\tstruct rte_rib_node *tmp;\n+\n+\tif (ent == NULL)\n+\t\treturn NULL;\n+\ttmp = ent->parent;\n+\twhile ((tmp != NULL) &&\t!is_valid_node(tmp))\n+\t\ttmp = tmp->parent;\n+\treturn tmp;\n+}\n+\n+static struct rte_rib_node *\n+__rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)\n+{\n+\tstruct rte_rib_node *cur;\n+\n+\tcur = rib->tree;\n+\twhile (cur != NULL) {\n+\t\tif ((cur->ip == ip) && (cur->depth == depth) &&\n+\t\t\t\tis_valid_node(cur))\n+\t\t\treturn cur;\n+\t\tif ((cur->depth > depth) ||\n+\t\t\t\t!is_covered(ip, cur->ip, cur->depth))\n+\t\t\tbreak;\n+\t\tcur = get_nxt_node(cur, ip);\n+\t}\n+\treturn NULL;\n+}\n+\n+struct rte_rib_node *\n+rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth)\n+{\n+\tif ((rib == NULL) || (depth > RIB_MAXDEPTH)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\tip &= rte_rib_depth_to_mask(depth);\n+\n+\treturn __rib_lookup_exact(rib, ip, depth);\n+}\n+\n+/*\n+ * Traverses on subtree and retrieves more specific routes\n+ * for a given in args ip/depth prefix\n+ * last = NULL means the first invocation\n+ */\n+struct rte_rib_node *\n+rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip,\n+\tuint8_t depth, struct rte_rib_node *last, int flag)\n+{\n+\tstruct rte_rib_node *tmp, *prev = NULL;\n+\n+\tif ((rib == NULL) || (depth > RIB_MAXDEPTH)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\n+\tif (last == NULL) {\n+\t\ttmp = rib->tree;\n+\t\twhile ((tmp) && (tmp->depth < depth))\n+\t\t\ttmp = get_nxt_node(tmp, ip);\n+\t} else {\n+\t\ttmp = last;\n+\t\twhile ((tmp->parent != NULL) && (is_right_node(tmp) ||\n+\t\t\t\t(tmp->parent->right == NULL))) {\n+\t\t\ttmp = tmp->parent;\n+\t\t\tif (is_valid_node(tmp) &&\n+\t\t\t\t\t(is_covered(tmp->ip, ip, depth) &&\n+\t\t\t\t\t(tmp->depth > depth)))\n+\t\t\t\treturn tmp;\n+\t\t}\n+\t\ttmp = (tmp->parent) ? tmp->parent->right : NULL;\n+\t}\n+\twhile (tmp) {\n+\t\tif (is_valid_node(tmp) &&\n+\t\t\t\t(is_covered(tmp->ip, ip, depth) &&\n+\t\t\t\t(tmp->depth > depth))) {\n+\t\t\tprev = tmp;\n+\t\t\tif (flag == RTE_RIB_GET_NXT_COVER)\n+\t\t\t\treturn prev;\n+\t\t}\n+\t\ttmp = (tmp->left) ? tmp->left : tmp->right;\n+\t}\n+\treturn prev;\n+}\n+\n+void\n+rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth)\n+{\n+\tstruct rte_rib_node *cur, *prev, *child;\n+\n+\tcur = rte_rib_lookup_exact(rib, ip, depth);\n+\tif (cur == NULL)\n+\t\treturn;\n+\n+\t--rib->cur_routes;\n+\tcur->flag &= ~RTE_RIB_VALID_NODE;\n+\twhile (!is_valid_node(cur)) {\n+\t\tif ((cur->left != NULL) && (cur->right != NULL))\n+\t\t\treturn;\n+\t\tchild = (cur->left == NULL) ? cur->right : cur->left;\n+\t\tif (child != NULL)\n+\t\t\tchild->parent = cur->parent;\n+\t\tif (cur->parent == NULL) {\n+\t\t\trib->tree = child;\n+\t\t\tnode_free(rib, cur);\n+\t\t\treturn;\n+\t\t}\n+\t\tif (cur->parent->left == cur)\n+\t\t\tcur->parent->left = child;\n+\t\telse\n+\t\t\tcur->parent->right = child;\n+\t\tprev = cur;\n+\t\tcur = cur->parent;\n+\t\tnode_free(rib, prev);\n+\t}\n+}\n+\n+struct rte_rib_node *\n+rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth)\n+{\n+\tstruct rte_rib_node **tmp;\n+\tstruct rte_rib_node *prev = NULL;\n+\tstruct rte_rib_node *new_node = NULL;\n+\tstruct rte_rib_node *common_node = NULL;\n+\tint d = 0;\n+\tuint32_t common_prefix;\n+\tuint8_t common_depth;\n+\n+\tif ((rib == NULL) || (depth > RIB_MAXDEPTH)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\n+\ttmp = &rib->tree;\n+\tip &= rte_rib_depth_to_mask(depth);\n+\tnew_node = __rib_lookup_exact(rib, ip, depth);\n+\tif (new_node != NULL) {\n+\t\trte_errno = EEXIST;\n+\t\treturn NULL;\n+\t}\n+\n+\tnew_node = node_alloc(rib);\n+\tif (new_node == NULL) {\n+\t\trte_errno = ENOMEM;\n+\t\treturn NULL;\n+\t}\n+\tnew_node->left = NULL;\n+\tnew_node->right = NULL;\n+\tnew_node->parent = NULL;\n+\tnew_node->ip = ip;\n+\tnew_node->depth = depth;\n+\tnew_node->flag = RTE_RIB_VALID_NODE;\n+\n+\t/* traverse down the tree to find matching node or closest matching */\n+\twhile (1) {\n+\t\t/* insert as the last node in the branch */\n+\t\tif (*tmp == NULL) {\n+\t\t\t*tmp = new_node;\n+\t\t\tnew_node->parent = prev;\n+\t\t\t++rib->cur_routes;\n+\t\t\treturn *tmp;\n+\t\t}\n+\t\t/*\n+\t\t * Intermediate node found.\n+\t\t * Previous rte_rib_lookup_exact() returned NULL\n+\t\t * but node with proper search criteria is found.\n+\t\t * Validate intermediate node and return.\n+\t\t */\n+\t\tif ((ip == (*tmp)->ip) && (depth == (*tmp)->depth)) {\n+\t\t\tnode_free(rib, new_node);\n+\t\t\t(*tmp)->flag |= RTE_RIB_VALID_NODE;\n+\t\t\t++rib->cur_routes;\n+\t\t\treturn *tmp;\n+\t\t}\n+\t\td = (*tmp)->depth;\n+\t\tif ((d >= depth) || !is_covered(ip, (*tmp)->ip, d))\n+\t\t\tbreak;\n+\t\tprev = *tmp;\n+\t\ttmp = (ip & (1 << (31 - d))) ? &(*tmp)->right : &(*tmp)->left;\n+\t}\n+\t/* closest node found, new_node should be inserted in the middle */\n+\tcommon_depth = RTE_MIN(depth, (*tmp)->depth);\n+\tcommon_prefix = ip ^ (*tmp)->ip;\n+\td = __builtin_clz(common_prefix);\n+\n+\tcommon_depth = RTE_MIN(d, common_depth);\n+\tcommon_prefix = ip & rte_rib_depth_to_mask(common_depth);\n+\tif ((common_prefix == ip) && (common_depth == depth)) {\n+\t\t/* insert as a parent */\n+\t\tif ((*tmp)->ip & (1 << (31 - depth)))\n+\t\t\tnew_node->right = *tmp;\n+\t\telse\n+\t\t\tnew_node->left = *tmp;\n+\t\tnew_node->parent = (*tmp)->parent;\n+\t\t(*tmp)->parent = new_node;\n+\t\t*tmp = new_node;\n+\t} else {\n+\t\t/* create intermediate node */\n+\t\tcommon_node = node_alloc(rib);\n+\t\tif (common_node == NULL) {\n+\t\t\tnode_free(rib, new_node);\n+\t\t\trte_errno = ENOMEM;\n+\t\t\treturn NULL;\n+\t\t}\n+\t\tcommon_node->ip = common_prefix;\n+\t\tcommon_node->depth = common_depth;\n+\t\tcommon_node->flag = 0;\n+\t\tcommon_node->parent = (*tmp)->parent;\n+\t\tnew_node->parent = common_node;\n+\t\t(*tmp)->parent = common_node;\n+\t\tif ((new_node->ip & (1 << (31 - common_depth))) == 0) {\n+\t\t\tcommon_node->left = new_node;\n+\t\t\tcommon_node->right = *tmp;\n+\t\t} else {\n+\t\t\tcommon_node->left = *tmp;\n+\t\t\tcommon_node->right = new_node;\n+\t\t}\n+\t\t*tmp = common_node;\n+\t}\n+\t++rib->cur_routes;\n+\treturn new_node;\n+}\n+\n+int\n+rte_rib_get_ip(struct rte_rib_node *node, uint32_t *ip)\n+{\n+\tif ((node == NULL) || (ip == NULL)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\t*ip = node->ip;\n+\treturn 0;\n+}\n+\n+int\n+rte_rib_get_depth(struct rte_rib_node *node, uint8_t *depth)\n+{\n+\tif ((node == NULL) || (depth == NULL)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\t*depth = node->depth;\n+\treturn 0;\n+}\n+\n+void *\n+rte_rib_get_ext(struct rte_rib_node *node)\n+{\n+\treturn (node == NULL) ? NULL : &node->ext[0];\n+}\n+\n+int\n+rte_rib_get_nh(struct rte_rib_node *node, uint64_t *nh)\n+{\n+\tif ((node == NULL) || (nh == NULL)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\t*nh = node->nh;\n+\treturn 0;\n+}\n+\n+int\n+rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh)\n+{\n+\tif (node == NULL) {\n+\t\trte_errno = EINVAL;\n+\t\treturn -1;\n+\t}\n+\tnode->nh = nh;\n+\treturn 0;\n+}\n+\n+struct rte_rib *\n+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf *conf)\n+{\n+\tchar mem_name[RTE_RIB_NAMESIZE];\n+\tstruct rte_rib *rib = NULL;\n+\tstruct rte_tailq_entry *te;\n+\tstruct rte_rib_list *rib_list;\n+\tstruct rte_mempool *node_pool;\n+\n+\t/* Check user arguments. */\n+\tif ((name == NULL) || (conf == NULL) ||\n+\t\t\t(conf->max_nodes == 0)) {\n+\t\trte_errno = EINVAL;\n+\t\treturn NULL;\n+\t}\n+\n+\tsnprintf(mem_name, sizeof(mem_name), \"MP_%s\", name);\n+\tnode_pool = rte_mempool_create(mem_name, conf->max_nodes,\n+\t\tsizeof(struct rte_rib_node) + conf->ext_sz, 0, 0,\n+\t\tNULL, NULL, NULL, NULL, socket_id, 0);\n+\n+\tif (node_pool == NULL) {\n+\t\tRTE_LOG(ERR, LPM,\n+\t\t\t\"Can not allocate mempool for RIB %s\\n\", name);\n+\t\treturn NULL;\n+\t}\n+\n+\tsnprintf(mem_name, sizeof(mem_name), \"RIB_%s\", name);\n+\trib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);\n+\n+\trte_mcfg_tailq_write_lock();\n+\n+\t/* guarantee there's no existing */\n+\tTAILQ_FOREACH(te, rib_list, next) {\n+\t\trib = (struct rte_rib *)te->data;\n+\t\tif (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)\n+\t\t\tbreak;\n+\t}\n+\trib = NULL;\n+\tif (te != NULL) {\n+\t\trte_errno = EEXIST;\n+\t\tgoto exit;\n+\t}\n+\n+\t/* allocate tailq entry */\n+\tte = rte_zmalloc(\"RIB_TAILQ_ENTRY\", sizeof(*te), 0);\n+\tif (te == NULL) {\n+\t\tRTE_LOG(ERR, LPM,\n+\t\t\t\"Can not allocate tailq entry for RIB %s\\n\", name);\n+\t\trte_errno = ENOMEM;\n+\t\tgoto exit;\n+\t}\n+\n+\t/* Allocate memory to store the RIB data structures. */\n+\trib = rte_zmalloc_socket(mem_name,\n+\t\tsizeof(struct rte_rib),\tRTE_CACHE_LINE_SIZE, socket_id);\n+\tif (rib == NULL) {\n+\t\tRTE_LOG(ERR, LPM, \"RIB %s memory allocation failed\\n\", name);\n+\t\trte_errno = ENOMEM;\n+\t\tgoto free_te;\n+\t}\n+\n+\trte_strlcpy(rib->name, name, sizeof(rib->name));\n+\trib->tree = NULL;\n+\trib->max_nodes = conf->max_nodes;\n+\trib->node_pool = node_pool;\n+\tte->data = (void *)rib;\n+\tTAILQ_INSERT_TAIL(rib_list, te, next);\n+\n+\trte_mcfg_tailq_write_unlock();\n+\n+\treturn rib;\n+\n+free_te:\n+\trte_free(te);\n+exit:\n+\trte_mcfg_tailq_write_unlock();\n+\trte_mempool_free(node_pool);\n+\n+\treturn NULL;\n+}\n+\n+struct rte_rib *\n+rte_rib_find_existing(const char *name)\n+{\n+\tstruct rte_rib *rib = NULL;\n+\tstruct rte_tailq_entry *te;\n+\tstruct rte_rib_list *rib_list;\n+\n+\trib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);\n+\n+\trte_mcfg_tailq_read_lock();\n+\tTAILQ_FOREACH(te, rib_list, next) {\n+\t\trib = (struct rte_rib *) te->data;\n+\t\tif (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0)\n+\t\t\tbreak;\n+\t}\n+\trte_mcfg_tailq_read_unlock();\n+\n+\tif (te == NULL) {\n+\t\trte_errno = ENOENT;\n+\t\treturn NULL;\n+\t}\n+\n+\treturn rib;\n+}\n+\n+void\n+rte_rib_free(struct rte_rib *rib)\n+{\n+\tstruct rte_tailq_entry *te;\n+\tstruct rte_rib_list *rib_list;\n+\tstruct rte_rib_node *tmp = NULL;\n+\n+\tif (rib == NULL)\n+\t\treturn;\n+\n+\trib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list);\n+\n+\trte_mcfg_tailq_write_lock();\n+\n+\t/* find our tailq entry */\n+\tTAILQ_FOREACH(te, rib_list, next) {\n+\t\tif (te->data == (void *)rib)\n+\t\t\tbreak;\n+\t}\n+\tif (te != NULL)\n+\t\tTAILQ_REMOVE(rib_list, te, next);\n+\n+\trte_mcfg_tailq_write_unlock();\n+\n+\twhile ((tmp = rte_rib_get_nxt(rib, 0, 0, tmp,\n+\t\t\tRTE_RIB_GET_NXT_ALL)) != NULL)\n+\t\trte_rib_remove(rib, tmp->ip, tmp->depth);\n+\n+\trte_mempool_free(rib->node_pool);\n+\trte_free(rib);\n+\trte_free(te);\n+}\ndiff --git a/lib/librte_rib/rte_rib.h b/lib/librte_rib/rte_rib.h\nnew file mode 100644\nindex 0000000..6b70de9\n--- /dev/null\n+++ b/lib/librte_rib/rte_rib.h\n@@ -0,0 +1,277 @@\n+/* SPDX-License-Identifier: BSD-3-Clause\n+ * Copyright(c) 2018 Vladimir Medvedkin <medvedkinv@gmail.com>\n+ * Copyright(c) 2019 Intel Corporation\n+ */\n+\n+#ifndef _RTE_RIB_H_\n+#define _RTE_RIB_H_\n+\n+/**\n+ * @file\n+ * Level compressed tree implementation for IPv4 Longest Prefix Match\n+ */\n+\n+#include <rte_compat.h>\n+\n+/**\n+ * rte_rib_get_nxt() flags\n+ */\n+enum {\n+\t/** flag to get all subroutes in a RIB tree */\n+\tRTE_RIB_GET_NXT_ALL,\n+\t/** flag to get first matched subroutes in a RIB tree */\n+\tRTE_RIB_GET_NXT_COVER\n+};\n+\n+struct rte_rib;\n+struct rte_rib_node;\n+\n+/** RIB configuration structure */\n+struct rte_rib_conf {\n+\t/**\n+\t * Size of extension block inside rte_rib_node.\n+\t * This space could be used to store additional user\n+\t * defined data.\n+\t */\n+\tsize_t\text_sz;\n+\t/* size of rte_rib_node's pool */\n+\tint\tmax_nodes;\n+};\n+\n+/**\n+ * Get an IPv4 mask from prefix length\n+ * It is caller responsibility to make sure depth is not bigger than 32\n+ *\n+ * @param depth\n+ * prefix length\n+ * @return\n+ * IPv4 mask\n+ */\n+static inline uint32_t\n+rte_rib_depth_to_mask(uint8_t depth)\n+{\n+\treturn (uint32_t)(UINT64_MAX << (32 - depth));\n+}\n+\n+/**\n+ * Lookup an IP into the RIB structure\n+ *\n+ * @param rib\n+ * RIB object handle\n+ * @param ip\n+ * IP to be looked up in the RIB\n+ * @return\n+ * pointer to struct rte_rib_node on success\n+ * NULL otherwise\n+ */\n+__rte_experimental\n+struct rte_rib_node *\n+rte_rib_lookup(struct rte_rib *rib, uint32_t ip);\n+\n+/**\n+ * Lookup less specific route into the RIB structure\n+ *\n+ * @param ent\n+ * Pointer to struct rte_rib_node that represents target route\n+ * @return\n+ * pointer to struct rte_rib_node that represents\n+ * less specific route on success\n+ * NULL otherwise\n+ */\n+__rte_experimental\n+struct rte_rib_node *\n+rte_rib_lookup_parent(struct rte_rib_node *ent);\n+\n+/**\n+ * Lookup prefix into the RIB structure\n+ *\n+ * @param rib\n+ * RIB object handle\n+ * @param ip\n+ * net to be looked up in the RIB\n+ * @param depth\n+ * prefix length\n+ * @return\n+ * pointer to struct rte_rib_node on success\n+ * NULL otherwise\n+ */\n+__rte_experimental\n+struct rte_rib_node *\n+rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth);\n+\n+/**\n+ * Retrieve next more specific prefix from the RIB\n+ * that is covered by ip/depth supernet in an ascending order\n+ *\n+ * @param rib\n+ * RIB object handle\n+ * @param ip\n+ * net address of supernet prefix that covers returned more specific prefixes\n+ * @param depth\n+ * supernet prefix length\n+ * @param last\n+ * pointer to the last returned prefix to get next prefix\n+ * or\n+ * NULL to get first more specific prefix\n+ * @param flag\n+ * -RTE_RIB_GET_NXT_ALL\n+ * get all prefixes from subtrie\n+ * -RTE_RIB_GET_NXT_COVER\n+ * get only first more specific prefix even if it have more specifics\n+ * @return\n+ * pointer to the next more specific prefix\n+ * NULL if there is no prefixes left\n+ */\n+__rte_experimental\n+struct rte_rib_node *\n+rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip, uint8_t depth,\n+\tstruct rte_rib_node *last, int flag);\n+\n+/**\n+ * Remove prefix from the RIB\n+ *\n+ * @param rib\n+ * RIB object handle\n+ * @param ip\n+ * net to be removed from the RIB\n+ * @param depth\n+ * prefix length\n+ */\n+__rte_experimental\n+void\n+rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth);\n+\n+/**\n+ * Insert prefix into the RIB\n+ *\n+ * @param rib\n+ * RIB object handle\n+ * @param ip\n+ * net to be inserted to the RIB\n+ * @param depth\n+ * prefix length\n+ * @return\n+ * pointer to new rte_rib_node on success\n+ * NULL otherwise\n+ */\n+__rte_experimental\n+struct rte_rib_node *\n+rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth);\n+\n+/**\n+ * Get an ip from rte_rib_node\n+ *\n+ * @param node\n+ * pointer to the rib node\n+ * @param ip\n+ * pointer to the ip to save\n+ * @return\n+ * 0 on success.\n+ * -1 on failure with rte_errno indicating reason for failure.\n+ */\n+__rte_experimental\n+int\n+rte_rib_get_ip(struct rte_rib_node *node, uint32_t *ip);\n+\n+/**\n+ * Get a depth from rte_rib_node\n+ *\n+ * @param node\n+ * pointer to the rib node\n+ * @param depth\n+ * pointer to the depth to save\n+ * @return\n+ * 0 on success.\n+ * -1 on failure with rte_errno indicating reason for failure.\n+ */\n+__rte_experimental\n+int\n+rte_rib_get_depth(struct rte_rib_node *node, uint8_t *depth);\n+\n+/**\n+ * Get ext field from the rib node\n+ * It is caller responsibility to make sure there are necessary space\n+ * for the ext field inside rib node.\n+ *\n+ * @param node\n+ * pointer to the rib node\n+ * @return\n+ * pointer to the ext\n+ */\n+__rte_experimental\n+void *\n+rte_rib_get_ext(struct rte_rib_node *node);\n+\n+/**\n+ * Get nexthop from the rib node\n+ *\n+ * @param node\n+ * pointer to the rib node\n+ * @param nh\n+ * pointer to the nexthop to save\n+ * @return\n+ * 0 on success.\n+ * -1 on failure with rte_errno indicating reason for failure.\n+ */\n+__rte_experimental\n+int\n+rte_rib_get_nh(struct rte_rib_node *node, uint64_t *nh);\n+\n+/**\n+ * Set nexthop into the rib node\n+ *\n+ * @param node\n+ * pointer to the rib node\n+ * @param nh\n+ * nexthop value to set to the rib node\n+ * @return\n+ * 0 on success.\n+ * -1 on failure with rte_errno indicating reason for failure.\n+ */\n+__rte_experimental\n+int\n+rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh);\n+\n+/**\n+ * Create RIB\n+ *\n+ * @param name\n+ * RIB name\n+ * @param socket_id\n+ * NUMA socket ID for RIB table memory allocation\n+ * @param conf\n+ * Structure containing the configuration\n+ * @return\n+ * Handle to RIB object on success\n+ * NULL otherwise with rte_errno indicating reason for failure.\n+ */\n+__rte_experimental\n+struct rte_rib *\n+rte_rib_create(const char *name, int socket_id, struct rte_rib_conf *conf);\n+\n+/**\n+ * Find an existing RIB object and return a pointer to it.\n+ *\n+ * @param name\n+ * Name of the rib object as passed to rte_rib_create()\n+ * @return\n+ * Pointer to RIB object on success\n+ * NULL otherwise with rte_errno indicating reason for failure.\n+ */\n+__rte_experimental\n+struct rte_rib *\n+rte_rib_find_existing(const char *name);\n+\n+/**\n+ * Free an RIB object.\n+ *\n+ * @param rib\n+ * RIB object handle\n+ * @return\n+ * None\n+ */\n+__rte_experimental\n+void\n+rte_rib_free(struct rte_rib *rib);\n+\n+#endif /* _RTE_RIB_H_ */\ndiff --git a/lib/librte_rib/rte_rib_version.map b/lib/librte_rib/rte_rib_version.map\nnew file mode 100644\nindex 0000000..1432a22\n--- /dev/null\n+++ b/lib/librte_rib/rte_rib_version.map\n@@ -0,0 +1,20 @@\n+EXPERIMENTAL {\n+\tglobal:\n+\n+\trte_rib_create;\n+\trte_rib_find_existing;\n+\trte_rib_free;\n+\trte_rib_get_depth;\n+\trte_rib_get_ext;\n+\trte_rib_get_ip;\n+\trte_rib_get_nh;\n+\trte_rib_get_nxt;\n+\trte_rib_insert;\n+\trte_rib_lookup;\n+\trte_rib_lookup_parent;\n+\trte_rib_lookup_exact;\n+\trte_rib_set_nh;\n+\trte_rib_remove;\n+\n+\tlocal: *;\n+};\ndiff --git a/lib/meson.build b/lib/meson.build\nindex e5ff838..d7f2a04 100644\n--- a/lib/meson.build\n+++ b/lib/meson.build\n@@ -22,7 +22,7 @@ libraries = [\n \t'gro', 'gso', 'ip_frag', 'jobstats',\n \t'kni', 'latencystats', 'lpm', 'member',\n \t'power', 'pdump', 'rawdev',\n-\t'rcu', 'reorder', 'sched', 'security', 'stack', 'vhost',\n+\t'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost',\n \t# ipsec lib depends on net, crypto and security\n \t'ipsec',\n \t# add pkt framework libs which use other libs from above\ndiff --git a/mk/rte.app.mk b/mk/rte.app.mk\nindex ba5c39e..4517874 100644\n--- a/mk/rte.app.mk\n+++ b/mk/rte.app.mk\n@@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP) += -lrte_pdump\n _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR) += -lrte_distributor\n _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG) += -lrte_ip_frag\n _LDLIBS-$(CONFIG_RTE_LIBRTE_METER) += -lrte_meter\n+_LDLIBS-$(CONFIG_RTE_LIBRTE_RIB) += -lrte_rib\n _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM) += -lrte_lpm\n _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL) += -lrte_acl\n _LDLIBS-$(CONFIG_RTE_LIBRTE_TELEMETRY) += --no-as-needed\n", "prefixes": [ "v6", "01/12" ] }