From patchwork Thu Apr 26 22:03:31 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 39061 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@dpdk.org Delivered-To: patchwork@dpdk.org Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 5123B8D35; Fri, 27 Apr 2018 00:03:51 +0200 (CEST) Received: from mailrelay1.rambler.ru (mailrelay1.rambler.ru [81.19.66.239]) by dpdk.org (Postfix) with ESMTP id 593E97EC0 for ; Fri, 27 Apr 2018 00:03:45 +0200 (CEST) Received: from testlab1.ipnoc.rambler.tech (unknown [10.201.1.3]) by mailrelay1.rambler.ru (Postfix) with ESMTP id 40XB0c5n5RzKhh; Fri, 27 Apr 2018 01:03:44 +0300 (MSK) From: Medvedkin Vladimir To: dev@dpdk.org Cc: bruce.richardson@intel.com, thomas@monjalon.net, cristian.dumitrescu@intel.com, Medvedkin Vladimir Date: Fri, 27 Apr 2018 01:03:31 +0300 Message-Id: <1524780214-23196-2-git-send-email-medvedkinv@gmail.com> X-Mailer: git-send-email 1.8.3.1 In-Reply-To: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> References: <1524780214-23196-1-git-send-email-medvedkinv@gmail.com> X-Rcpt-To: , , , , Subject: [dpdk-dev] [PATCH v4 1/4] Add RIB library X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Signed-off-by: Medvedkin Vladimir --- config/common_base | 6 + doc/api/doxy-api.conf | 1 + lib/Makefile | 2 + lib/librte_rib/Makefile | 23 ++ lib/librte_rib/meson.build | 6 + lib/librte_rib/rte_rib.c | 520 +++++++++++++++++++++++++++++++++++++ lib/librte_rib/rte_rib.h | 302 +++++++++++++++++++++ lib/librte_rib/rte_rib_version.map | 18 ++ lib/meson.build | 2 +- mk/rte.app.mk | 1 + 10 files changed, 880 insertions(+), 1 deletion(-) create mode 100644 lib/librte_rib/Makefile create mode 100644 lib/librte_rib/meson.build create mode 100644 lib/librte_rib/rte_rib.c create mode 100644 lib/librte_rib/rte_rib.h create mode 100644 lib/librte_rib/rte_rib_version.map 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 + +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 + */ + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +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 + */ + +#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