From patchwork Fri Nov 1 15:21:34 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62316 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 8538CA00BE; Fri, 1 Nov 2019 16:22:03 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id AE8AF1C113; Fri, 1 Nov 2019 16:21:54 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id C67001BEAA for ; Fri, 1 Nov 2019 16:21:52 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:21:52 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979064" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:50 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:34 +0000 Message-Id: <42e2dd500467aad09197bb31c2738bbeb11400f0.1572621162.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: dev-bounces@dpdk.org Sender: "dev" Add RIB (Routing Information Base) library. This library implements an IPv4 routing table optimized for control plane operations. It implements a control plane struct containing routes in a tree and provides fast add/del operations for routes. Also it allows to perform fast subtree traversals (i.e. retrieve existing subroutes for a giver prefix). This structure will be used as a control plane helper structure for FIB implementation. Also it might be used standalone in other different places such as bitmaps for example. Internal implementation is level compressed binary trie. Signed-off-by: Vladimir Medvedkin --- config/common_base | 5 + doc/api/doxy-api.conf.in | 1 + lib/Makefile | 2 + lib/librte_rib/Makefile | 25 ++ lib/librte_rib/meson.build | 8 + lib/librte_rib/rte_rib.c | 532 +++++++++++++++++++++++++++++++++++++ lib/librte_rib/rte_rib.h | 277 +++++++++++++++++++ lib/librte_rib/rte_rib_version.map | 20 ++ lib/meson.build | 2 +- mk/rte.app.mk | 1 + 10 files changed, 872 insertions(+), 1 deletion(-) create mode 100644 lib/librte_rib/Makefile create mode 100644 lib/librte_rib/meson.build create mode 100644 lib/librte_rib/rte_rib.c create mode 100644 lib/librte_rib/rte_rib.h create mode 100644 lib/librte_rib/rte_rib_version.map diff --git a/config/common_base b/config/common_base index 8ef75c2..5a9d4c3 100644 --- a/config/common_base +++ b/config/common_base @@ -894,6 +894,11 @@ CONFIG_RTE_LIBRTE_RCU=y CONFIG_RTE_LIBRTE_RCU_DEBUG=n # +# Compile librte_rib +# +CONFIG_RTE_LIBRTE_RIB=y + +# # Compile librte_lpm # CONFIG_RTE_LIBRTE_LPM=y diff --git a/doc/api/doxy-api.conf.in b/doc/api/doxy-api.conf.in index 908cee8..3ec012d 100644 --- a/doc/api/doxy-api.conf.in +++ b/doc/api/doxy-api.conf.in @@ -54,6 +54,7 @@ INPUT = @TOPDIR@/doc/api/doxy-api-index.md \ @TOPDIR@/lib/librte_rawdev \ @TOPDIR@/lib/librte_rcu \ @TOPDIR@/lib/librte_reorder \ + @TOPDIR@/lib/librte_rib \ @TOPDIR@/lib/librte_ring \ @TOPDIR@/lib/librte_sched \ @TOPDIR@/lib/librte_security \ diff --git a/lib/Makefile b/lib/Makefile index 41c463d..aa5ee1e 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -51,6 +51,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_HASH) += librte_hash DEPDIRS-librte_hash := librte_eal librte_ring DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd DEPDIRS-librte_efd := librte_eal librte_ring librte_hash +DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib +DEPDIRS-librte_rib := librte_eal librte_mempool DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm DEPDIRS-librte_lpm := librte_eal librte_hash DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl diff --git a/lib/librte_rib/Makefile b/lib/librte_rib/Makefile new file mode 100644 index 0000000..79f259a --- /dev/null +++ b/lib/librte_rib/Makefile @@ -0,0 +1,25 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2018 Vladimir Medvedkin +# Copyright(c) 2019 Intel Corporation + +include $(RTE_SDK)/mk/rte.vars.mk + +# library name +LIB = librte_rib.a + +CFLAGS += -O3 +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) +CFLAGS += -DALLOW_EXPERIMENTAL_API +LDLIBS += -lrte_eal -lrte_mempool + +EXPORT_MAP := rte_rib_version.map + +LIBABIVER := 1 + +# all source are stored in SRCS-y +SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c + +# install this header file +SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h + +include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_rib/meson.build b/lib/librte_rib/meson.build new file mode 100644 index 0000000..e7b8920 --- /dev/null +++ b/lib/librte_rib/meson.build @@ -0,0 +1,8 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2018 Vladimir Medvedkin +# Copyright(c) 2019 Intel Corporation + +allow_experimental_apis = true +sources = files('rte_rib.c') +headers = files('rte_rib.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..55d612d --- /dev/null +++ b/lib/librte_rib/rte_rib.c @@ -0,0 +1,532 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#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) + +#define RTE_RIB_VALID_NODE 1 +/* Maximum depth value possible for IPv4 RIB. */ +#define RIB_MAXDEPTH 32 +/* Maximum length of a RIB name. */ +#define RTE_RIB_NAMESIZE 64 + +struct rte_rib_node { + struct rte_rib_node *left; + struct rte_rib_node *right; + struct rte_rib_node *parent; + uint32_t ip; + uint8_t depth; + uint8_t flag; + uint64_t nh; + __extension__ uint64_t ext[0]; +}; + +struct rte_rib { + char name[RTE_RIB_NAMESIZE]; + struct rte_rib_node *tree; + struct rte_mempool *node_pool; + uint32_t cur_nodes; + uint32_t cur_routes; + uint32_t max_nodes; +}; + +static inline bool +is_valid_node(struct rte_rib_node *node) +{ + return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE; +} + +static inline bool +is_right_node(struct rte_rib_node *node) +{ + return node->parent->right == node; +} + +/* + * Check if ip1 is covered by ip2/depth prefix + */ +static inline bool +is_covered(uint32_t ip1, uint32_t ip2, uint8_t depth) +{ + return ((ip1 ^ ip2) & rte_rib_depth_to_mask(depth)) == 0; +} + +static inline struct rte_rib_node * +get_nxt_node(struct rte_rib_node *node, uint32_t ip) +{ + return (ip & (1 << (31 - node->depth))) ? node->right : node->left; +} + +static struct rte_rib_node * +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 +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_lookup(struct rte_rib *rib, uint32_t ip) +{ + struct rte_rib_node *cur, *prev = NULL; + + if (rib == NULL) { + rte_errno = EINVAL; + return NULL; + } + + cur = rib->tree; + while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) { + if (is_valid_node(cur)) + prev = cur; + cur = get_nxt_node(cur, ip); + } + return prev; +} + +struct rte_rib_node * +rte_rib_lookup_parent(struct rte_rib_node *ent) +{ + struct rte_rib_node *tmp; + + if (ent == NULL) + return NULL; + tmp = ent->parent; + while ((tmp != NULL) && !is_valid_node(tmp)) + tmp = tmp->parent; + return tmp; +} + +static struct rte_rib_node * +__rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth) +{ + struct rte_rib_node *cur; + + cur = rib->tree; + while (cur != NULL) { + if ((cur->ip == ip) && (cur->depth == depth) && + is_valid_node(cur)) + return cur; + if ((cur->depth > depth) || + !is_covered(ip, cur->ip, cur->depth)) + break; + cur = get_nxt_node(cur, ip); + } + return NULL; +} + +struct rte_rib_node * +rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth) +{ + if ((rib == NULL) || (depth > RIB_MAXDEPTH)) { + rte_errno = EINVAL; + return NULL; + } + ip &= rte_rib_depth_to_mask(depth); + + return __rib_lookup_exact(rib, ip, depth); +} + +/* + * Traverses on subtree and retrieves more specific routes + * for a given in args ip/depth prefix + * last = NULL means the first invocation + */ +struct rte_rib_node * +rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip, + uint8_t depth, struct rte_rib_node *last, int flag) +{ + struct rte_rib_node *tmp, *prev = NULL; + + if ((rib == NULL) || (depth > RIB_MAXDEPTH)) { + rte_errno = EINVAL; + return NULL; + } + + if (last == NULL) { + tmp = rib->tree; + while ((tmp) && (tmp->depth < depth)) + tmp = get_nxt_node(tmp, ip); + } else { + tmp = last; + while ((tmp->parent != NULL) && (is_right_node(tmp) || + (tmp->parent->right == NULL))) { + tmp = tmp->parent; + if (is_valid_node(tmp) && + (is_covered(tmp->ip, ip, depth) && + (tmp->depth > depth))) + return tmp; + } + tmp = (tmp->parent) ? tmp->parent->right : NULL; + } + while (tmp) { + if (is_valid_node(tmp) && + (is_covered(tmp->ip, ip, depth) && + (tmp->depth > depth))) { + prev = tmp; + if (flag == RTE_RIB_GET_NXT_COVER) + return prev; + } + tmp = (tmp->left) ? tmp->left : tmp->right; + } + return prev; +} + +void +rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth) +{ + struct rte_rib_node *cur, *prev, *child; + + cur = rte_rib_lookup_exact(rib, ip, depth); + if (cur == NULL) + return; + + --rib->cur_routes; + cur->flag &= ~RTE_RIB_VALID_NODE; + while (!is_valid_node(cur)) { + 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->tree = child; + node_free(rib, cur); + return; + } + if (cur->parent->left == cur) + cur->parent->left = child; + else + cur->parent->right = child; + prev = cur; + cur = cur->parent; + node_free(rib, prev); + } +} + +struct rte_rib_node * +rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth) +{ + struct rte_rib_node **tmp; + 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 ((rib == NULL) || (depth > RIB_MAXDEPTH)) { + rte_errno = EINVAL; + return NULL; + } + + tmp = &rib->tree; + ip &= rte_rib_depth_to_mask(depth); + new_node = __rib_lookup_exact(rib, ip, depth); + if (new_node != NULL) { + rte_errno = EEXIST; + return NULL; + } + + new_node = 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->ip = ip; + 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_lookup_exact() returned NULL + * but node with proper search criteria is found. + * Validate intermediate node and return. + */ + if ((ip == (*tmp)->ip) && (depth == (*tmp)->depth)) { + node_free(rib, new_node); + (*tmp)->flag |= RTE_RIB_VALID_NODE; + ++rib->cur_routes; + return *tmp; + } + d = (*tmp)->depth; + if ((d >= depth) || !is_covered(ip, (*tmp)->ip, d)) + break; + prev = *tmp; + tmp = (ip & (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 = ip ^ (*tmp)->ip; + d = __builtin_clz(common_prefix); + + common_depth = RTE_MIN(d, common_depth); + common_prefix = ip & rte_rib_depth_to_mask(common_depth); + if ((common_prefix == ip) && (common_depth == depth)) { + /* insert as a parent */ + if ((*tmp)->ip & (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 = node_alloc(rib); + if (common_node == NULL) { + node_free(rib, new_node); + rte_errno = ENOMEM; + return NULL; + } + common_node->ip = 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->ip & (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; +} + +int +rte_rib_get_ip(struct rte_rib_node *node, uint32_t *ip) +{ + if ((node == NULL) || (ip == NULL)) { + rte_errno = EINVAL; + return -1; + } + *ip = node->ip; + return 0; +} + +int +rte_rib_get_depth(struct rte_rib_node *node, uint8_t *depth) +{ + if ((node == NULL) || (depth == NULL)) { + rte_errno = EINVAL; + return -1; + } + *depth = node->depth; + return 0; +} + +void * +rte_rib_get_ext(struct rte_rib_node *node) +{ + return (node == NULL) ? NULL : &node->ext[0]; +} + +int +rte_rib_get_nh(struct rte_rib_node *node, uint64_t *nh) +{ + if ((node == NULL) || (nh == NULL)) { + rte_errno = EINVAL; + return -1; + } + *nh = node->nh; + return 0; +} + +int +rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh) +{ + if (node == NULL) { + rte_errno = EINVAL; + return -1; + } + node->nh = nh; + return 0; +} + +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) || + (conf->max_nodes == 0)) { + rte_errno = EINVAL; + return NULL; + } + + snprintf(mem_name, sizeof(mem_name), "MP_%s", name); + node_pool = rte_mempool_create(mem_name, conf->max_nodes, + sizeof(struct rte_rib_node) + conf->ext_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); + return NULL; + } + + snprintf(mem_name, sizeof(mem_name), "RIB_%s", name); + rib_list = RTE_TAILQ_CAST(rte_rib_tailq.head, rte_rib_list); + + rte_mcfg_tailq_write_lock(); + + /* 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 RIB data structures. */ + 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; + } + + rte_strlcpy(rib->name, name, sizeof(rib->name)); + rib->tree = NULL; + rib->max_nodes = conf->max_nodes; + rib->node_pool = node_pool; + te->data = (void *)rib; + TAILQ_INSERT_TAIL(rib_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + return rib; + +free_te: + rte_free(te); +exit: + rte_mcfg_tailq_write_unlock(); + 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_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, rib_list, next) { + rib = (struct rte_rib *) te->data; + if (strncmp(name, rib->name, RTE_RIB_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + + 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_mcfg_tailq_write_lock(); + + /* 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_mcfg_tailq_write_unlock(); + + while ((tmp = rte_rib_get_nxt(rib, 0, 0, tmp, + RTE_RIB_GET_NXT_ALL)) != NULL) + rte_rib_remove(rib, tmp->ip, tmp->depth); + + rte_mempool_free(rib->node_pool); + rte_free(rib); + rte_free(te); +} diff --git a/lib/librte_rib/rte_rib.h b/lib/librte_rib/rte_rib.h new file mode 100644 index 0000000..6b70de9 --- /dev/null +++ b/lib/librte_rib/rte_rib.h @@ -0,0 +1,277 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _RTE_RIB_H_ +#define _RTE_RIB_H_ + +/** + * @file + * Level compressed tree implementation for IPv4 Longest Prefix Match + */ + +#include + +/** + * rte_rib_get_nxt() flags + */ +enum { + /** flag to get all subroutes in a RIB tree */ + RTE_RIB_GET_NXT_ALL, + /** flag to get first matched subroutes in a RIB tree */ + RTE_RIB_GET_NXT_COVER +}; + +struct rte_rib; +struct rte_rib_node; + +/** RIB configuration structure */ +struct rte_rib_conf { + /** + * Size of extension block inside rte_rib_node. + * This space could be used to store additional user + * defined data. + */ + size_t ext_sz; + /* size of rte_rib_node's pool */ + int max_nodes; +}; + +/** + * Get an IPv4 mask from prefix length + * It is caller responsibility to make sure depth is not bigger than 32 + * + * @param depth + * prefix length + * @return + * IPv4 mask + */ +static inline uint32_t +rte_rib_depth_to_mask(uint8_t depth) +{ + return (uint32_t)(UINT64_MAX << (32 - depth)); +} + +/** + * Lookup an IP into the RIB structure + * + * @param rib + * RIB object handle + * @param ip + * IP to be looked up in the RIB + * @return + * pointer to struct rte_rib_node on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib_node * +rte_rib_lookup(struct rte_rib *rib, uint32_t ip); + +/** + * 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 + */ +__rte_experimental +struct rte_rib_node * +rte_rib_lookup_parent(struct rte_rib_node *ent); + +/** + * Lookup prefix into the RIB structure + * + * @param rib + * RIB object handle + * @param ip + * net to be looked up in the RIB + * @param depth + * prefix length + * @return + * pointer to struct rte_rib_node on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib_node * +rte_rib_lookup_exact(struct rte_rib *rib, uint32_t ip, uint8_t depth); + +/** + * Retrieve next more specific prefix from the RIB + * that is covered by ip/depth supernet in an ascending order + * + * @param rib + * RIB object handle + * @param ip + * 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 + * NULL if there is no prefixes left + */ +__rte_experimental +struct rte_rib_node * +rte_rib_get_nxt(struct rte_rib *rib, uint32_t ip, uint8_t depth, + struct rte_rib_node *last, int flag); + +/** + * Remove prefix from the RIB + * + * @param rib + * RIB object handle + * @param ip + * net to be removed from the RIB + * @param depth + * prefix length + */ +__rte_experimental +void +rte_rib_remove(struct rte_rib *rib, uint32_t ip, uint8_t depth); + +/** + * Insert prefix into the RIB + * + * @param rib + * RIB object handle + * @param ip + * net to be inserted to the RIB + * @param depth + * prefix length + * @return + * pointer to new rte_rib_node on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib_node * +rte_rib_insert(struct rte_rib *rib, uint32_t ip, uint8_t depth); + +/** + * Get an ip from rte_rib_node + * + * @param node + * pointer to the rib node + * @param ip + * pointer to the ip to save + * @return + * 0 on success. + * -1 on failure with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib_get_ip(struct rte_rib_node *node, uint32_t *ip); + +/** + * Get a depth from rte_rib_node + * + * @param node + * pointer to the rib node + * @param depth + * pointer to the depth to save + * @return + * 0 on success. + * -1 on failure with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib_get_depth(struct rte_rib_node *node, uint8_t *depth); + +/** + * Get ext field from the rib node + * It is caller responsibility to make sure there are necessary space + * for the ext field inside rib node. + * + * @param node + * pointer to the rib node + * @return + * pointer to the ext + */ +__rte_experimental +void * +rte_rib_get_ext(struct rte_rib_node *node); + +/** + * Get nexthop from the rib node + * + * @param node + * pointer to the rib node + * @param nh + * pointer to the nexthop to save + * @return + * 0 on success. + * -1 on failure with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib_get_nh(struct rte_rib_node *node, uint64_t *nh); + +/** + * Set nexthop into the rib node + * + * @param node + * pointer to the rib node + * @param nh + * nexthop value to set to the rib node + * @return + * 0 on success. + * -1 on failure with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib_set_nh(struct rte_rib_node *node, uint64_t nh); + +/** + * 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 indicating reason for failure. + */ +__rte_experimental +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 on success + * NULL otherwise with rte_errno indicating reason for failure. + */ +__rte_experimental +struct rte_rib * +rte_rib_find_existing(const char *name); + +/** + * Free an RIB object. + * + * @param rib + * RIB object handle + * @return + * None + */ +__rte_experimental +void +rte_rib_free(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..1432a22 --- /dev/null +++ b/lib/librte_rib/rte_rib_version.map @@ -0,0 +1,20 @@ +EXPERIMENTAL { + global: + + rte_rib_create; + rte_rib_find_existing; + rte_rib_free; + rte_rib_get_depth; + rte_rib_get_ext; + rte_rib_get_ip; + rte_rib_get_nh; + rte_rib_get_nxt; + rte_rib_insert; + rte_rib_lookup; + rte_rib_lookup_parent; + rte_rib_lookup_exact; + rte_rib_set_nh; + rte_rib_remove; + + local: *; +}; diff --git a/lib/meson.build b/lib/meson.build index e5ff838..d7f2a04 100644 --- a/lib/meson.build +++ b/lib/meson.build @@ -22,7 +22,7 @@ libraries = [ 'gro', 'gso', 'ip_frag', 'jobstats', 'kni', 'latencystats', 'lpm', 'member', 'power', 'pdump', 'rawdev', - 'rcu', 'reorder', 'sched', 'security', 'stack', 'vhost', + 'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost', # ipsec lib depends on net, crypto and security 'ipsec', # add pkt framework libs which use other libs from above diff --git a/mk/rte.app.mk b/mk/rte.app.mk index ba5c39e..4517874 100644 --- a/mk/rte.app.mk +++ b/mk/rte.app.mk @@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP) += -lrte_pdump _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR) += -lrte_distributor _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG) += -lrte_ip_frag _LDLIBS-$(CONFIG_RTE_LIBRTE_METER) += -lrte_meter +_LDLIBS-$(CONFIG_RTE_LIBRTE_RIB) += -lrte_rib _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM) += -lrte_lpm _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL) += -lrte_acl _LDLIBS-$(CONFIG_RTE_LIBRTE_TELEMETRY) += --no-as-needed From patchwork Fri Nov 1 15:21:35 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62317 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 40F36A00BE; Fri, 1 Nov 2019 16:22:17 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D7E661DFE9; Fri, 1 Nov 2019 16:21:56 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 964F21C036 for ; Fri, 1 Nov 2019 16:21:54 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:21:54 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979071" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:52 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:35 +0000 Message-Id: <8b829507599c5a814d4325c658133fdff84d4cd9.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 02/12] test/rib: add RIB library autotests 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" Functional tests for the new RIB library. Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 2 + app/test/autotest_data.py | 6 + app/test/meson.build | 3 + app/test/test_rib.c | 351 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 362 insertions(+) create mode 100644 app/test/test_rib.c diff --git a/app/test/Makefile b/app/test/Makefile index 26ba6fe..5bd8487 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -124,6 +124,8 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_multiwriter.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c +SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c + SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm6.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index 7405149..3c3b806 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -111,6 +111,12 @@ "Report": None, }, { + "Name": "RIB autotest", + "Command": "rib_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Memcpy autotest", "Command": "memcpy_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index ec40943..98524e1 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -99,6 +99,7 @@ test_sources = files('commands.c', 'test_reciprocal_division_perf.c', 'test_red.c', 'test_reorder.c', + 'test_rib.c', 'test_ring.c', 'test_ring_perf.c', 'test_rwlock.c', @@ -147,6 +148,7 @@ test_deps = ['acl', 'rawdev', 'rcu', 'reorder', + 'rib', 'ring', 'stack', 'timer' @@ -197,6 +199,7 @@ fast_test_names = [ 'prefetch_autotest', 'rcu_qsbr_autotest', 'red_autotest', + 'rib_autotest', 'ring_autotest', 'ring_pmd_autotest', 'rwlock_test1_autotest', diff --git a/app/test/test_rib.c b/app/test/test_rib.c new file mode 100644 index 0000000..c95957a --- /dev/null +++ b/app/test/test_rib.c @@ -0,0 +1,351 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include + +#include +#include + +#include "test.h" + +typedef int32_t (*rte_rib_test)(void); + +static int32_t test_create_invalid(void); +static int32_t test_multiple_create(void); +static int32_t test_free_null(void); +static int32_t test_insert_invalid(void); +static int32_t test_get_fn(void); +static int32_t test_basic(void); +static int32_t test_tree_traversal(void); + +#define MAX_DEPTH 32 +#define MAX_RULES (1 << 22) + +/* + * Check that rte_rib_create fails gracefully for incorrect user input + * arguments + */ +int32_t +test_create_invalid(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_conf config; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + /* rte_rib_create: rib name == NULL */ + rib = rte_rib_create(NULL, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_rib_create: config == NULL */ + rib = rte_rib_create(__func__, SOCKET_ID_ANY, NULL); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + + /* socket_id < -1 is invalid */ + rib = rte_rib_create(__func__, -2, &config); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_rib_create: max_nodes = 0 */ + config.max_nodes = 0; + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + config.max_nodes = MAX_RULES; + + return TEST_SUCCESS; +} + +/* + * Create rib table then delete rib table 10 times + * Use a slightly different rules size each time + */ +int32_t +test_multiple_create(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_conf config; + int32_t i; + + config.ext_sz = 0; + + for (i = 0; i < 10; i++) { + config.max_nodes = MAX_RULES - i; + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + rte_rib_free(rib); + } + /* Can not test free so return success */ + return TEST_SUCCESS; +} + +/* + * Call rte_rib_free for NULL pointer user input. Note: free has no return and + * therefore it is impossible to check for failure but this test is added to + * increase function coverage metrics and to validate that freeing null does + * not crash. + */ +int32_t +test_free_null(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_conf config; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + rte_rib_free(rib); + rte_rib_free(NULL); + return TEST_SUCCESS; +} + +/* + * Check that rte_rib_insert fails gracefully for incorrect user input arguments + */ +int32_t +test_insert_invalid(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_node *node, *node1; + struct rte_rib_conf config; + uint32_t ip = RTE_IPV4(0, 0, 0, 0); + uint8_t depth = 24; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + /* rte_rib_insert: rib == NULL */ + node = rte_rib_insert(NULL, ip, depth); + RTE_TEST_ASSERT(node == NULL, + "Call succeeded with invalid parameters\n"); + + /*Create valid rib to use in rest of test. */ + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + /* rte_rib_insert: depth > MAX_DEPTH */ + node = rte_rib_insert(rib, ip, MAX_DEPTH + 1); + RTE_TEST_ASSERT(node == NULL, + "Call succeeded with invalid parameters\n"); + + /* insert the same ip/depth twice*/ + node = rte_rib_insert(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + node1 = rte_rib_insert(rib, ip, depth); + RTE_TEST_ASSERT(node1 == NULL, + "Call succeeded with invalid parameters\n"); + + rte_rib_free(rib); + + return TEST_SUCCESS; +} + +/* + * Call rte_rib_node access functions with incorrect input. + * After call rte_rib_node access functions with correct args + * and check the return values for correctness + */ +int32_t +test_get_fn(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_node *node; + struct rte_rib_conf config; + void *ext; + uint32_t ip = RTE_IPV4(192, 0, 2, 0); + uint32_t ip_ret; + uint64_t nh_set = 10; + uint64_t nh_ret; + uint8_t depth = 24; + uint8_t depth_ret; + int ret; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + node = rte_rib_insert(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + /* test rte_rib_get_ip() with incorrect args */ + ret = rte_rib_get_ip(NULL, &ip_ret); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + ret = rte_rib_get_ip(node, NULL); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib_get_depth() with incorrect args */ + ret = rte_rib_get_depth(NULL, &depth_ret); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + ret = rte_rib_get_depth(node, NULL); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib_set_nh() with incorrect args */ + ret = rte_rib_set_nh(NULL, nh_set); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib_get_nh() with incorrect args */ + ret = rte_rib_get_nh(NULL, &nh_ret); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + ret = rte_rib_get_nh(node, NULL); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib_get_ext() with incorrect args */ + ext = rte_rib_get_ext(NULL); + RTE_TEST_ASSERT(ext == NULL, + "Call succeeded with invalid parameters\n"); + + /* check the return values */ + ret = rte_rib_get_ip(node, &ip_ret); + RTE_TEST_ASSERT((ret == 0) && (ip_ret == ip), + "Failed to get proper node ip\n"); + ret = rte_rib_get_depth(node, &depth_ret); + RTE_TEST_ASSERT((ret == 0) && (depth_ret == depth), + "Failed to get proper node depth\n"); + ret = rte_rib_set_nh(node, nh_set); + RTE_TEST_ASSERT(ret == 0, + "Failed to set rte_rib_node nexthop\n"); + ret = rte_rib_get_nh(node, &nh_ret); + RTE_TEST_ASSERT((ret == 0) && (nh_ret == nh_set), + "Failed to get proper nexthop\n"); + + rte_rib_free(rib); + + return TEST_SUCCESS; +} + +/* + * Call insert, lookup/lookup_exact and delete for a single rule + */ +int32_t +test_basic(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_node *node; + struct rte_rib_conf config; + + uint32_t ip = RTE_IPV4(192, 0, 2, 0); + uint64_t next_hop_add = 10; + uint64_t next_hop_return; + uint8_t depth = 24; + int ret; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + node = rte_rib_insert(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + ret = rte_rib_set_nh(node, next_hop_add); + RTE_TEST_ASSERT(ret == 0, + "Failed to set rte_rib_node field\n"); + + node = rte_rib_lookup(rib, ip); + RTE_TEST_ASSERT(node != NULL, "Failed to lookup\n"); + + ret = rte_rib_get_nh(node, &next_hop_return); + RTE_TEST_ASSERT((ret == 0) && (next_hop_add == next_hop_return), + "Failed to get proper nexthop\n"); + + node = rte_rib_lookup_exact(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, + "Failed to lookup\n"); + + ret = rte_rib_get_nh(node, &next_hop_return); + RTE_TEST_ASSERT((ret == 0) && (next_hop_add == next_hop_return), + "Failed to get proper nexthop\n"); + + rte_rib_remove(rib, ip, depth); + + node = rte_rib_lookup(rib, ip); + RTE_TEST_ASSERT(node == NULL, + "Lookup returns non existent rule\n"); + node = rte_rib_lookup_exact(rib, ip, depth); + RTE_TEST_ASSERT(node == NULL, + "Lookup returns non existent rule\n"); + + rte_rib_free(rib); + + return TEST_SUCCESS; +} + +int32_t +test_tree_traversal(void) +{ + struct rte_rib *rib = NULL; + struct rte_rib_node *node; + struct rte_rib_conf config; + + uint32_t ip1 = RTE_IPV4(10, 10, 10, 0); + uint32_t ip2 = RTE_IPV4(10, 10, 130, 80); + uint8_t depth = 30; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + node = rte_rib_insert(rib, ip1, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + node = rte_rib_insert(rib, ip2, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + node = NULL; + node = rte_rib_get_nxt(rib, RTE_IPV4(10, 10, 130, 0), 24, node, + RTE_RIB_GET_NXT_ALL); + RTE_TEST_ASSERT(node != NULL, "Failed to get rib_node\n"); + + rte_rib_free(rib); + + return TEST_SUCCESS; +} + +static struct unit_test_suite rib_tests = { + .suite_name = "rib autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_create_invalid), + TEST_CASE(test_multiple_create), + TEST_CASE(test_free_null), + TEST_CASE(test_insert_invalid), + TEST_CASE(test_get_fn), + TEST_CASE(test_basic), + TEST_CASE(test_tree_traversal), + TEST_CASES_END() + } +}; + +/* + * Do all unit tests. + */ +static int +test_rib(void) +{ + return unit_test_suite_runner(&rib_tests); +} + +REGISTER_TEST_COMMAND(rib_autotest, test_rib); From patchwork Fri Nov 1 15:21:36 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62318 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 06FC8A00BE; Fri, 1 Nov 2019 16:22:29 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 911901E535; Fri, 1 Nov 2019 16:21:59 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id B8CBF1BEB6 for ; Fri, 1 Nov 2019 16:21:56 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:21:56 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979084" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:54 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:36 +0000 Message-Id: <3ee0dfc1c1b2cade4d07cc9302cac0d6d17298a5.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 03/12] rib: add ipv6 support for RIB 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" Extend RIB library with ipv6 support. Signed-off-by: Vladimir Medvedkin --- lib/librte_rib/Makefile | 4 +- lib/librte_rib/meson.build | 4 +- lib/librte_rib/rte_rib6.c | 598 +++++++++++++++++++++++++++++++++++++ lib/librte_rib/rte_rib6.h | 334 +++++++++++++++++++++ lib/librte_rib/rte_rib_version.map | 15 + 5 files changed, 951 insertions(+), 4 deletions(-) create mode 100644 lib/librte_rib/rte_rib6.c create mode 100644 lib/librte_rib/rte_rib6.h diff --git a/lib/librte_rib/Makefile b/lib/librte_rib/Makefile index 79f259a..6d861ad 100644 --- a/lib/librte_rib/Makefile +++ b/lib/librte_rib/Makefile @@ -17,9 +17,9 @@ EXPORT_MAP := rte_rib_version.map LIBABIVER := 1 # all source are stored in SRCS-y -SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c +SRCS-$(CONFIG_RTE_LIBRTE_RIB) := rte_rib.c rte_rib6.c # install this header file -SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h +SYMLINK-$(CONFIG_RTE_LIBRTE_RIB)-include := rte_rib.h rte_rib6.h include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_rib/meson.build b/lib/librte_rib/meson.build index e7b8920..46a1c0c 100644 --- a/lib/librte_rib/meson.build +++ b/lib/librte_rib/meson.build @@ -3,6 +3,6 @@ # Copyright(c) 2019 Intel Corporation allow_experimental_apis = true -sources = files('rte_rib.c') -headers = files('rte_rib.h') +sources = files('rte_rib.c', 'rte_rib6.c') +headers = files('rte_rib.h', 'rte_rib6.h') deps += ['mempool'] diff --git a/lib/librte_rib/rte_rib6.c b/lib/librte_rib/rte_rib6.c new file mode 100644 index 0000000..78b8dcf --- /dev/null +++ b/lib/librte_rib/rte_rib6.c @@ -0,0 +1,598 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#define RTE_RIB_VALID_NODE 1 +#define RIB6_MAXDEPTH 128 +/* Maximum length of a RIB6 name. */ +#define RTE_RIB6_NAMESIZE 64 + +TAILQ_HEAD(rte_rib6_list, rte_tailq_entry); +static struct rte_tailq_elem rte_rib6_tailq = { + .name = "RTE_RIB6", +}; +EAL_REGISTER_TAILQ(rte_rib6_tailq) + +struct rte_rib6_node { + struct rte_rib6_node *left; + struct rte_rib6_node *right; + struct rte_rib6_node *parent; + uint64_t nh; + uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]; + uint8_t depth; + uint8_t flag; + __extension__ uint64_t ext[0]; +}; + +struct rte_rib6 { + char name[RTE_RIB6_NAMESIZE]; + struct rte_rib6_node *tree; + struct rte_mempool *node_pool; + uint32_t cur_nodes; + uint32_t cur_routes; + int max_nodes; +}; + +static inline bool +is_valid_node(struct rte_rib6_node *node) +{ + return (node->flag & RTE_RIB_VALID_NODE) == RTE_RIB_VALID_NODE; +} + +static inline bool +is_right_node(struct rte_rib6_node *node) +{ + return node->parent->right == node; +} + +/* + * Check if ip1 is covered by ip2/depth prefix + */ +static inline bool +is_covered(const uint8_t ip1[RTE_RIB6_IPV6_ADDR_SIZE], + const uint8_t ip2[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth) +{ + int i; + + for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) + if ((ip1[i] ^ ip2[i]) & get_msk_part(depth, i)) + return false; + + return true; +} + +static inline int +get_dir(const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth) +{ + int i = 0; + uint8_t p_depth, msk; + + for (p_depth = depth; p_depth >= 8; p_depth -= 8) + i++; + + msk = 1 << (7 - p_depth); + return (ip[i] & msk) != 0; +} + +static inline struct rte_rib6_node * +get_nxt_node(struct rte_rib6_node *node, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]) +{ + return (get_dir(ip, node->depth)) ? node->right : node->left; +} + +static struct rte_rib6_node * +node_alloc(struct rte_rib6 *rib) +{ + struct rte_rib6_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 +node_free(struct rte_rib6 *rib, struct rte_rib6_node *ent) +{ + --rib->cur_nodes; + rte_mempool_put(rib->node_pool, ent); +} + +struct rte_rib6_node * +rte_rib6_lookup(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]) +{ + struct rte_rib6_node *cur; + struct rte_rib6_node *prev = NULL; + + if (unlikely(rib == NULL)) { + rte_errno = EINVAL; + return NULL; + } + cur = rib->tree; + + while ((cur != NULL) && is_covered(ip, cur->ip, cur->depth)) { + if (is_valid_node(cur)) + prev = cur; + cur = get_nxt_node(cur, ip); + } + return prev; +} + +struct rte_rib6_node * +rte_rib6_lookup_parent(struct rte_rib6_node *ent) +{ + struct rte_rib6_node *tmp; + + if (ent == NULL) + return NULL; + + tmp = ent->parent; + while ((tmp != NULL) && (!is_valid_node(tmp))) + tmp = tmp->parent; + + return tmp; +} + +struct rte_rib6_node * +rte_rib6_lookup_exact(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth) +{ + struct rte_rib6_node *cur; + uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE]; + int i; + + if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) { + rte_errno = EINVAL; + return NULL; + } + cur = rib->tree; + + for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) + tmp_ip[i] = ip[i] & get_msk_part(depth, i); + + while (cur != NULL) { + if (rte_rib6_is_equal(cur->ip, tmp_ip) && + (cur->depth == depth) && + is_valid_node(cur)) + return cur; + + if (!(is_covered(tmp_ip, cur->ip, cur->depth)) || + (cur->depth >= depth)) + break; + + cur = get_nxt_node(cur, tmp_ip); + } + + return NULL; +} + +/* + * Traverses on subtree and retreeves more specific routes + * for a given in args ip/depth prefix + * last = NULL means the first invocation + */ +struct rte_rib6_node * +rte_rib6_get_nxt(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], + uint8_t depth, struct rte_rib6_node *last, int flag) +{ + struct rte_rib6_node *tmp, *prev = NULL; + uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE]; + int i; + + if ((rib == NULL) || (ip == NULL) || (depth > RIB6_MAXDEPTH)) { + rte_errno = EINVAL; + return NULL; + } + + for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) + tmp_ip[i] = ip[i] & get_msk_part(depth, i); + + if (last == NULL) { + tmp = rib->tree; + while ((tmp) && (tmp->depth < depth)) + tmp = get_nxt_node(tmp, tmp_ip); + } else { + tmp = last; + while ((tmp->parent != NULL) && (is_right_node(tmp) || + (tmp->parent->right == NULL))) { + tmp = tmp->parent; + if (is_valid_node(tmp) && + (is_covered(tmp->ip, tmp_ip, depth) && + (tmp->depth > depth))) + return tmp; + } + tmp = (tmp->parent != NULL) ? tmp->parent->right : NULL; + } + while (tmp) { + if (is_valid_node(tmp) && + (is_covered(tmp->ip, tmp_ip, depth) && + (tmp->depth > depth))) { + prev = tmp; + if (flag == RTE_RIB6_GET_NXT_COVER) + return prev; + } + tmp = (tmp->left != NULL) ? tmp->left : tmp->right; + } + return prev; +} + +void +rte_rib6_remove(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth) +{ + struct rte_rib6_node *cur, *prev, *child; + + cur = rte_rib6_lookup_exact(rib, ip, depth); + if (cur == NULL) + return; + + --rib->cur_routes; + cur->flag &= ~RTE_RIB_VALID_NODE; + while (!is_valid_node(cur)) { + 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->tree = child; + node_free(rib, cur); + return; + } + if (cur->parent->left == cur) + cur->parent->left = child; + else + cur->parent->right = child; + prev = cur; + cur = cur->parent; + node_free(rib, prev); + } +} + +struct rte_rib6_node * +rte_rib6_insert(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth) +{ + struct rte_rib6_node **tmp; + struct rte_rib6_node *prev = NULL; + struct rte_rib6_node *new_node = NULL; + struct rte_rib6_node *common_node = NULL; + uint8_t common_prefix[RTE_RIB6_IPV6_ADDR_SIZE]; + uint8_t tmp_ip[RTE_RIB6_IPV6_ADDR_SIZE]; + int i, d; + uint8_t common_depth, ip_xor; + + if (unlikely((rib == NULL) || (ip == NULL) || + (depth > RIB6_MAXDEPTH))) { + rte_errno = EINVAL; + return NULL; + } + + tmp = &rib->tree; + + for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) + tmp_ip[i] = ip[i] & get_msk_part(depth, i); + + new_node = rte_rib6_lookup_exact(rib, tmp_ip, depth); + if (new_node != NULL) { + rte_errno = EEXIST; + return NULL; + } + + new_node = node_alloc(rib); + if (new_node == NULL) { + rte_errno = ENOMEM; + return NULL; + } + new_node->left = NULL; + new_node->right = NULL; + new_node->parent = NULL; + rte_rib6_copy_addr(new_node->ip, tmp_ip); + 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_rib6_lookup_exact() returned NULL + * but node with proper search criteria is found. + * Validate intermediate node and return. + */ + if (rte_rib6_is_equal(tmp_ip, (*tmp)->ip) && + (depth == (*tmp)->depth)) { + node_free(rib, new_node); + (*tmp)->flag |= RTE_RIB_VALID_NODE; + ++rib->cur_routes; + return *tmp; + } + + if (!is_covered(tmp_ip, (*tmp)->ip, (*tmp)->depth) || + ((*tmp)->depth >= depth)) { + break; + } + prev = *tmp; + + tmp = (get_dir(tmp_ip, (*tmp)->depth)) ? &(*tmp)->right : + &(*tmp)->left; + } + + /* closest node found, new_node should be inserted in the middle */ + common_depth = RTE_MIN(depth, (*tmp)->depth); + for (i = 0, d = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) { + ip_xor = tmp_ip[i] ^ (*tmp)->ip[i]; + if (ip_xor == 0) + d += 8; + else { + d += __builtin_clz(ip_xor << 24); + break; + } + } + + common_depth = RTE_MIN(d, common_depth); + + for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) + common_prefix[i] = tmp_ip[i] & get_msk_part(common_depth, i); + + if (rte_rib6_is_equal(common_prefix, tmp_ip) && + (common_depth == depth)) { + /* insert as a parent */ + if (get_dir((*tmp)->ip, 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 = node_alloc(rib); + if (common_node == NULL) { + node_free(rib, new_node); + rte_errno = ENOMEM; + return NULL; + } + rte_rib6_copy_addr(common_node->ip, 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 (get_dir((*tmp)->ip, common_depth) == 1) { + 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; +} + +int +rte_rib6_get_ip(struct rte_rib6_node *node, uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]) +{ + if ((node == NULL) || (ip == NULL)) { + rte_errno = EINVAL; + return -1; + } + rte_rib6_copy_addr(ip, node->ip); + return 0; +} + +int +rte_rib6_get_depth(struct rte_rib6_node *node, uint8_t *depth) +{ + if ((node == NULL) || (depth == NULL)) { + rte_errno = EINVAL; + return -1; + } + *depth = node->depth; + return 0; +} + +void * +rte_rib6_get_ext(struct rte_rib6_node *node) +{ + return (node == NULL) ? NULL : &node->ext[0]; +} + +int +rte_rib6_get_nh(struct rte_rib6_node *node, uint64_t *nh) +{ + if ((node == NULL) || (nh == NULL)) { + rte_errno = EINVAL; + return -1; + } + *nh = node->nh; + return 0; +} + +int +rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh) +{ + if (node == NULL) { + rte_errno = EINVAL; + return -1; + } + node->nh = nh; + return 0; +} + +struct rte_rib6 * +rte_rib6_create(const char *name, int socket_id, struct rte_rib6_conf *conf) +{ + char mem_name[RTE_RIB6_NAMESIZE]; + struct rte_rib6 *rib = NULL; + struct rte_tailq_entry *te; + struct rte_rib6_list *rib6_list; + struct rte_mempool *node_pool; + + /* Check user arguments. */ + if ((name == NULL) || (conf == NULL) || + (conf->max_nodes == 0)) { + rte_errno = EINVAL; + return NULL; + } + + snprintf(mem_name, sizeof(mem_name), "MP_%s", name); + node_pool = rte_mempool_create(mem_name, conf->max_nodes, + sizeof(struct rte_rib6_node) + conf->ext_sz, 0, 0, + NULL, NULL, NULL, NULL, socket_id, 0); + + if (node_pool == NULL) { + RTE_LOG(ERR, LPM, + "Can not allocate mempool for RIB6 %s\n", name); + return NULL; + } + + snprintf(mem_name, sizeof(mem_name), "RIB6_%s", name); + rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list); + + rte_mcfg_tailq_write_lock(); + + /* guarantee there's no existing */ + TAILQ_FOREACH(te, rib6_list, next) { + rib = (struct rte_rib6 *)te->data; + if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0) + break; + } + rib = NULL; + if (te != NULL) { + rte_errno = EEXIST; + goto exit; + } + + /* allocate tailq entry */ + te = rte_zmalloc("RIB6_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, LPM, + "Can not allocate tailq entry for RIB6 %s\n", name); + rte_errno = ENOMEM; + goto exit; + } + + /* Allocate memory to store the RIB6 data structures. */ + rib = rte_zmalloc_socket(mem_name, + sizeof(struct rte_rib6), RTE_CACHE_LINE_SIZE, socket_id); + if (rib == NULL) { + RTE_LOG(ERR, LPM, "RIB6 %s memory allocation failed\n", name); + rte_errno = ENOMEM; + goto free_te; + } + + rte_strlcpy(rib->name, name, sizeof(rib->name)); + rib->tree = NULL; + rib->max_nodes = conf->max_nodes; + rib->node_pool = node_pool; + + te->data = (void *)rib; + TAILQ_INSERT_TAIL(rib6_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + return rib; + +free_te: + rte_free(te); +exit: + rte_mcfg_tailq_write_unlock(); + rte_mempool_free(node_pool); + + return NULL; +} + +struct rte_rib6 * +rte_rib6_find_existing(const char *name) +{ + struct rte_rib6 *rib = NULL; + struct rte_tailq_entry *te; + struct rte_rib6_list *rib6_list; + + if (unlikely(name == NULL)) { + rte_errno = EINVAL; + return NULL; + } + + rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, rib6_list, next) { + rib = (struct rte_rib6 *) te->data; + if (strncmp(name, rib->name, RTE_RIB6_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + + return rib; +} + +void +rte_rib6_free(struct rte_rib6 *rib) +{ + struct rte_tailq_entry *te; + struct rte_rib6_list *rib6_list; + struct rte_rib6_node *tmp = NULL; + + if (unlikely(rib == NULL)) { + rte_errno = EINVAL; + return; + } + + rib6_list = RTE_TAILQ_CAST(rte_rib6_tailq.head, rte_rib6_list); + + rte_mcfg_tailq_write_lock(); + + /* find our tailq entry */ + TAILQ_FOREACH(te, rib6_list, next) { + if (te->data == (void *)rib) + break; + } + if (te != NULL) + TAILQ_REMOVE(rib6_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + while ((tmp = rte_rib6_get_nxt(rib, 0, 0, tmp, + RTE_RIB6_GET_NXT_ALL)) != NULL) + rte_rib6_remove(rib, tmp->ip, tmp->depth); + + rte_mempool_free(rib->node_pool); + + rte_free(rib); + rte_free(te); +} diff --git a/lib/librte_rib/rte_rib6.h b/lib/librte_rib/rte_rib6.h new file mode 100644 index 0000000..8714571 --- /dev/null +++ b/lib/librte_rib/rte_rib6.h @@ -0,0 +1,334 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _RTE_RIB6_H_ +#define _RTE_RIB6_H_ + +/** + * @file + * Level compressed tree implementation for IPv6 Longest Prefix Match + */ + +#include +#include + +#define RTE_RIB6_IPV6_ADDR_SIZE 16 + +/** + * rte_rib6_get_nxt() flags + */ +enum { + /** flag to get all subroutes in a RIB tree */ + RTE_RIB6_GET_NXT_ALL, + /** flag to get first matched subroutes in a RIB tree */ + RTE_RIB6_GET_NXT_COVER +}; + +struct rte_rib6; +struct rte_rib6_node; + +/** RIB configuration structure */ +struct rte_rib6_conf { + /** + * Size of extension block inside rte_rib_node. + * This space could be used to store additional user + * defined data. + */ + size_t ext_sz; + /* size of rte_rib_node's pool */ + int max_nodes; +}; + +/** + * Copy IPv6 address from one location to another + * + * @param dst + * pointer to the place to copy + * @param src + * pointer from where to copy + */ +static inline void +rte_rib6_copy_addr(uint8_t *dst, const uint8_t *src) +{ + if ((dst == NULL) || (src == NULL)) + return; + rte_memcpy(dst, src, RTE_RIB6_IPV6_ADDR_SIZE); +} + +/** + * Compare two IPv6 addresses + * + * @param ip1 + * pointer to the first ipv6 address + * @param ip2 + * pointer to the second ipv6 address + * + * @return + * 1 if equal + * 0 otherwise + */ +static inline int +rte_rib6_is_equal(uint8_t *ip1, uint8_t *ip2) { + int i; + + if ((ip1 == NULL) || (ip2 == NULL)) + return 0; + for (i = 0; i < RTE_RIB6_IPV6_ADDR_SIZE; i++) { + if (ip1[i] != ip2[i]) + return 0; + } + return 1; +} + +/** + * Get 8-bit part of 128-bit IPv6 mask + * + * @param depth + * ipv6 prefix length + * @param byte + * position of a 8-bit chunk in the 128-bit mask + * + * @return + * 8-bit chunk of the 128-bit IPv6 mask + */ +static inline uint8_t +get_msk_part(uint8_t depth, int byte) { + uint8_t part; + + byte &= 0xf; + depth = RTE_MIN(depth, 128); + part = RTE_MAX((int16_t)depth - (byte * 8), 0); + part = (part > 8) ? 8 : part; + return (uint16_t)(~UINT8_MAX) >> part; +} + +/** + * Lookup an IP into the RIB structure + * + * @param rib + * RIB object handle + * @param ip + * IP to be looked up in the RIB + * @return + * pointer to struct rte_rib6_node on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib6_node * +rte_rib6_lookup(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]); + +/** + * Lookup less specific route into the RIB structure + * + * @param ent + * Pointer to struct rte_rib6_node that represents target route + * @return + * pointer to struct rte_rib6_node that represents + * less specific route on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib6_node * +rte_rib6_lookup_parent(struct rte_rib6_node *ent); + +/** + * Provides exact mach lookup of the prefix into the RIB structure + * + * @param rib + * RIB object handle + * @param ip + * net to be looked up in the RIB + * @param depth + * prefix length + * @return + * pointer to struct rte_rib6_node on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib6_node * +rte_rib6_lookup_exact(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth); + +/** + * Retrieve next more specific prefix from the RIB + * that is covered by ip/depth supernet in an ascending order + * + * @param rib + * RIB object handle + * @param ip + * 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_RIB6_GET_NXT_ALL + * get all prefixes from subtrie + * -RTE_RIB6_GET_NXT_COVER + * get only first more specific prefix even if it have more specifics + * @return + * pointer to the next more specific prefix + * NULL if there is no prefixes left + */ +__rte_experimental +struct rte_rib6_node * +rte_rib6_get_nxt(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], + uint8_t depth, struct rte_rib6_node *last, int flag); + +/** + * Remove prefix from the RIB + * + * @param rib + * RIB object handle + * @param ip + * net to be removed from the RIB + * @param depth + * prefix length + */ +__rte_experimental +void +rte_rib6_remove(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth); + +/** + * Insert prefix into the RIB + * + * @param rib + * RIB object handle + * @param ip + * net to be inserted to the RIB + * @param depth + * prefix length + * @return + * pointer to new rte_rib6_node on success + * NULL otherwise + */ +__rte_experimental +struct rte_rib6_node * +rte_rib6_insert(struct rte_rib6 *rib, + const uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE], uint8_t depth); + +/** + * Get an ip from rte_rib6_node + * + * @param node + * pointer to the rib6 node + * @param ip + * pointer to the ipv6 to save + * @return + * 0 on success + * -1 on failure with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib6_get_ip(struct rte_rib6_node *node, + uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE]); + +/** + * Get a depth from rte_rib6_node + * + * @param node + * pointer to the rib6 node + * @param depth + * pointer to the depth to save + * @return + * 0 on success + * -1 on failure with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib6_get_depth(struct rte_rib6_node *node, uint8_t *depth); + +/** + * Get ext field from the rte_rib6_node + * It is caller responsibility to make sure there are necessary space + * for the ext field inside rib6 node. + * + * @param node + * pointer to the rte_rib6_node + * @return + * pointer to the ext + */ +__rte_experimental +void * +rte_rib6_get_ext(struct rte_rib6_node *node); + +/** + * Get nexthop from the rte_rib6_node + * + * @param node + * pointer to the rib6 node + * @param nh + * pointer to the nexthop to save + * @return + * 0 on success + * -1 on failure, with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib6_get_nh(struct rte_rib6_node *node, uint64_t *nh); + +/** + * Set nexthop into the rte_rib6_node + * + * @param node + * pointer to the rib6 node + * @param nh + * nexthop value to set to the rib6 node + * @return + * 0 on success + * -1 on failure, with rte_errno indicating reason for failure. + */ +__rte_experimental +int +rte_rib6_set_nh(struct rte_rib6_node *node, uint64_t nh); + +/** + * Create RIB + * + * @param name + * RIB name + * @param socket_id + * NUMA socket ID for RIB table memory allocation + * @param conf + * Structure containing the configuration + * @return + * Pointer to RIB object on success + * NULL otherwise with rte_errno indicating reason for failure. + */ +__rte_experimental +struct rte_rib6 * +rte_rib6_create(const char *name, int socket_id, struct rte_rib6_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 on success + * NULL otherwise with rte_errno indicating reason for failure. + */ +__rte_experimental +struct rte_rib6 * +rte_rib6_find_existing(const char *name); + +/** + * Free an RIB object. + * + * @param rib + * RIB object handle + * @return + * None + */ +__rte_experimental +void +rte_rib6_free(struct rte_rib6 *rib); + +#endif /* _RTE_RIB_H_ */ diff --git a/lib/librte_rib/rte_rib_version.map b/lib/librte_rib/rte_rib_version.map index 1432a22..9b6161a 100644 --- a/lib/librte_rib/rte_rib_version.map +++ b/lib/librte_rib/rte_rib_version.map @@ -16,5 +16,20 @@ EXPERIMENTAL { rte_rib_set_nh; rte_rib_remove; + rte_rib6_create; + rte_rib6_find_existing; + rte_rib6_free; + rte_rib6_get_depth; + rte_rib6_get_ext; + rte_rib6_get_ip; + rte_rib6_get_nh; + rte_rib6_get_nxt; + rte_rib6_insert; + rte_rib6_lookup; + rte_rib6_lookup_parent; + rte_rib6_lookup_exact; + rte_rib6_set_nh; + rte_rib6_remove; + local: *; }; From patchwork Fri Nov 1 15:21:37 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62319 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 0166BA00BE; Fri, 1 Nov 2019 16:22:44 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id C0D321E549; Fri, 1 Nov 2019 16:22:01 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 9AE9C1E535 for ; Fri, 1 Nov 2019 16:21:58 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:21:58 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979092" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:56 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:37 +0000 Message-Id: <22cceeaa7b83e79beb01fa106929b8746684efb4.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 04/12] test/rib: add ipv6 support for RIB autotests 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" Functional tests for RIB6. Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 1 + app/test/autotest_data.py | 6 + app/test/meson.build | 2 + app/test/test_rib6.c | 357 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 366 insertions(+) create mode 100644 app/test/test_rib6.c diff --git a/app/test/Makefile b/app/test/Makefile index 5bd8487..4638426 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -125,6 +125,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite.c SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c +SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index 3c3b806..f35b3cc 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -117,6 +117,12 @@ "Report": None, }, { + "Name": "RIB6 autotest", + "Command": "rib6_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Memcpy autotest", "Command": "memcpy_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index 98524e1..49c1de0 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -100,6 +100,7 @@ test_sources = files('commands.c', 'test_red.c', 'test_reorder.c', 'test_rib.c', + 'test_rib6.c', 'test_ring.c', 'test_ring_perf.c', 'test_rwlock.c', @@ -200,6 +201,7 @@ fast_test_names = [ 'rcu_qsbr_autotest', 'red_autotest', 'rib_autotest', + 'rib6_autotest', 'ring_autotest', 'ring_pmd_autotest', 'rwlock_test1_autotest', diff --git a/app/test/test_rib6.c b/app/test/test_rib6.c new file mode 100644 index 0000000..638ba68 --- /dev/null +++ b/app/test/test_rib6.c @@ -0,0 +1,357 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include + +#include +#include + +#include "test.h" + +typedef int32_t (*rte_rib6_test)(void); + +static int32_t test_create_invalid(void); +static int32_t test_multiple_create(void); +static int32_t test_free_null(void); +static int32_t test_insert_invalid(void); +static int32_t test_get_fn(void); +static int32_t test_basic(void); +static int32_t test_tree_traversal(void); + +#define MAX_DEPTH 128 +#define MAX_RULES (1 << 22) + +/* + * Check that rte_rib6_create fails gracefully for incorrect user input + * arguments + */ +int32_t +test_create_invalid(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_conf config; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + /* rte_rib6_create: rib name == NULL */ + rib = rte_rib6_create(NULL, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_rib6_create: config == NULL */ + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, NULL); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + + /* socket_id < -1 is invalid */ + rib = rte_rib6_create(__func__, -2, &config); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_rib6_create: max_nodes = 0 */ + config.max_nodes = 0; + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib == NULL, + "Call succeeded with invalid parameters\n"); + config.max_nodes = MAX_RULES; + + return TEST_SUCCESS; +} + +/* + * Create rib table then delete rib table 10 times + * Use a slightly different rules size each time + */ +int32_t +test_multiple_create(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_conf config; + int32_t i; + + config.ext_sz = 0; + + for (i = 0; i < 10; i++) { + config.max_nodes = MAX_RULES - i; + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + rte_rib6_free(rib); + } + /* Can not test free so return success */ + return TEST_SUCCESS; +} + +/* + * Call rte_rib6_free for NULL pointer user input. Note: free has no return and + * therefore it is impossible to check for failure but this test is added to + * increase function coverage metrics and to validate that freeing null does + * not crash. + */ +int32_t +test_free_null(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_conf config; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + rte_rib6_free(rib); + rte_rib6_free(NULL); + return TEST_SUCCESS; +} + +/* + * Check that rte_rib6_insert fails gracefully + * for incorrect user input arguments + */ +int32_t +test_insert_invalid(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_node *node, *node1; + struct rte_rib6_conf config; + uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE] = {0}; + uint8_t depth = 24; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + /* rte_rib6_insert: rib == NULL */ + node = rte_rib6_insert(NULL, ip, depth); + RTE_TEST_ASSERT(node == NULL, + "Call succeeded with invalid parameters\n"); + + /*Create valid rib to use in rest of test. */ + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + /* rte_rib6_insert: depth > MAX_DEPTH */ + node = rte_rib6_insert(rib, ip, MAX_DEPTH + 1); + RTE_TEST_ASSERT(node == NULL, + "Call succeeded with invalid parameters\n"); + + /* insert the same ip/depth twice*/ + node = rte_rib6_insert(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + node1 = rte_rib6_insert(rib, ip, depth); + RTE_TEST_ASSERT(node1 == NULL, + "Call succeeded with invalid parameters\n"); + + rte_rib6_free(rib); + + return TEST_SUCCESS; +} + +/* + * Call rte_rib6_node access functions with incorrect input. + * After call rte_rib6_node access functions with correct args + * and check the return values for correctness + */ +int32_t +test_get_fn(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_node *node; + struct rte_rib6_conf config; + void *ext; + uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE] = {192, 0, 2, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0}; + uint8_t ip_ret[RTE_RIB6_IPV6_ADDR_SIZE]; + uint64_t nh_set = 10; + uint64_t nh_ret; + uint8_t depth = 24; + uint8_t depth_ret; + int ret; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + node = rte_rib6_insert(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + /* test rte_rib6_get_ip() with incorrect args */ + ret = rte_rib6_get_ip(NULL, ip_ret); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + ret = rte_rib6_get_ip(node, NULL); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib6_get_depth() with incorrect args */ + ret = rte_rib6_get_depth(NULL, &depth_ret); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + ret = rte_rib6_get_depth(node, NULL); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib6_set_nh() with incorrect args */ + ret = rte_rib6_set_nh(NULL, nh_set); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib6_get_nh() with incorrect args */ + ret = rte_rib6_get_nh(NULL, &nh_ret); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + ret = rte_rib6_get_nh(node, NULL); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* test rte_rib6_get_ext() with incorrect args */ + ext = rte_rib6_get_ext(NULL); + RTE_TEST_ASSERT(ext == NULL, + "Call succeeded with invalid parameters\n"); + + /* check the return values */ + ret = rte_rib6_get_ip(node, ip_ret); + RTE_TEST_ASSERT((ret == 0) && (rte_rib6_is_equal(ip_ret, ip)), + "Failed to get proper node ip\n"); + ret = rte_rib6_get_depth(node, &depth_ret); + RTE_TEST_ASSERT((ret == 0) && (depth_ret == depth), + "Failed to get proper node depth\n"); + ret = rte_rib6_set_nh(node, nh_set); + RTE_TEST_ASSERT(ret == 0, + "Failed to set rte_rib_node nexthop\n"); + ret = rte_rib6_get_nh(node, &nh_ret); + RTE_TEST_ASSERT((ret == 0) && (nh_ret == nh_set), + "Failed to get proper nexthop\n"); + + rte_rib6_free(rib); + + return TEST_SUCCESS; +} + +/* + * Call insert, lookup/lookup_exact and delete for a single rule + */ +int32_t +test_basic(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_node *node; + struct rte_rib6_conf config; + + uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE] = {192, 0, 2, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0}; + uint64_t next_hop_add = 10; + uint64_t next_hop_return; + uint8_t depth = 24; + uint32_t status = 0; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + node = rte_rib6_insert(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + status = rte_rib6_set_nh(node, next_hop_add); + RTE_TEST_ASSERT(status == 0, + "Failed to set rte_rib_node field\n"); + + node = rte_rib6_lookup(rib, ip); + RTE_TEST_ASSERT(node != NULL, "Failed to lookup\n"); + + status = rte_rib6_get_nh(node, &next_hop_return); + RTE_TEST_ASSERT((status == 0) && (next_hop_add == next_hop_return), + "Failed to get proper nexthop\n"); + + node = rte_rib6_lookup_exact(rib, ip, depth); + RTE_TEST_ASSERT(node != NULL, + "Failed to lookup\n"); + + status = rte_rib6_get_nh(node, &next_hop_return); + RTE_TEST_ASSERT((status == 0) && (next_hop_add == next_hop_return), + "Failed to get proper nexthop\n"); + + rte_rib6_remove(rib, ip, depth); + + node = rte_rib6_lookup(rib, ip); + RTE_TEST_ASSERT(node == NULL, + "Lookup returns non existent rule\n"); + node = rte_rib6_lookup_exact(rib, ip, depth); + RTE_TEST_ASSERT(node == NULL, + "Lookup returns non existent rule\n"); + + rte_rib6_free(rib); + + return TEST_SUCCESS; +} + +int32_t +test_tree_traversal(void) +{ + struct rte_rib6 *rib = NULL; + struct rte_rib6_node *node; + struct rte_rib6_conf config; + + uint8_t ip[RTE_RIB6_IPV6_ADDR_SIZE] = {10, 0, 2, 130, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0}; + uint8_t ip1[RTE_RIB6_IPV6_ADDR_SIZE] = {10, 0, 2, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0}; + uint8_t ip2[RTE_RIB6_IPV6_ADDR_SIZE] = {10, 0, 2, 130, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 80}; + uint8_t depth = 126; + + config.max_nodes = MAX_RULES; + config.ext_sz = 0; + + rib = rte_rib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(rib != NULL, "Failed to create RIB\n"); + + node = rte_rib6_insert(rib, ip1, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + node = rte_rib6_insert(rib, ip2, depth); + RTE_TEST_ASSERT(node != NULL, "Failed to insert rule\n"); + + node = NULL; + node = rte_rib6_get_nxt(rib, ip, 32, node, RTE_RIB6_GET_NXT_ALL); + RTE_TEST_ASSERT(node != NULL, "Failed to get rib_node\n"); + + rte_rib6_free(rib); + + return TEST_SUCCESS; +} + +static struct unit_test_suite rib6_tests = { + .suite_name = "rib6 autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_create_invalid), + TEST_CASE(test_multiple_create), + TEST_CASE(test_free_null), + TEST_CASE(test_insert_invalid), + TEST_CASE(test_get_fn), + TEST_CASE(test_basic), + TEST_CASE(test_tree_traversal), + TEST_CASES_END() + } +}; + +/* + * Do all unit tests. + */ +static int +test_rib6(void) +{ + return unit_test_suite_runner(&rib6_tests); +} + +REGISTER_TEST_COMMAND(rib6_autotest, test_rib6); + From patchwork Fri Nov 1 15:21:38 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62320 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 096C2A00BE; Fri, 1 Nov 2019 16:22:55 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 623231E550; Fri, 1 Nov 2019 16:22:03 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id A7A3E1E53D for ; Fri, 1 Nov 2019 16:22:00 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:00 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979101" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:21:58 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:38 +0000 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 05/12] fib: add FIB 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" Add FIB (Forwarding Information Base) library. This library implements a dataplane structures and algorithms designed for fast longest prefix match. Internally it consists of two parts - RIB (control plane ops) and implementation for the dataplane tasks. Initial version provides two implementations for both ipv4 and ipv6: dummy (uses RIB as a dataplane) and DIR24_8 (same as current LPM) Due to proposed design it allows to extend FIB with new algorithms in future (for example DXR, poptrie, etc). Signed-off-by: Vladimir Medvedkin --- config/common_base | 6 + doc/api/doxy-api.conf.in | 1 + lib/Makefile | 2 + lib/librte_fib/Makefile | 25 +++ lib/librte_fib/meson.build | 8 + lib/librte_fib/rte_fib.c | 305 +++++++++++++++++++++++++++++++++++++ lib/librte_fib/rte_fib.h | 173 +++++++++++++++++++++ lib/librte_fib/rte_fib_version.map | 14 ++ lib/meson.build | 2 + mk/rte.app.mk | 1 + 10 files changed, 537 insertions(+) create mode 100644 lib/librte_fib/Makefile create mode 100644 lib/librte_fib/meson.build create mode 100644 lib/librte_fib/rte_fib.c create mode 100644 lib/librte_fib/rte_fib.h create mode 100644 lib/librte_fib/rte_fib_version.map diff --git a/config/common_base b/config/common_base index 5a9d4c3..0f32ad7 100644 --- a/config/common_base +++ b/config/common_base @@ -899,6 +899,12 @@ CONFIG_RTE_LIBRTE_RCU_DEBUG=n CONFIG_RTE_LIBRTE_RIB=y # +# Compile librte_fib +# +CONFIG_RTE_LIBRTE_FIB=y +CONFIG_RTE_LIBRTE_FIB_DEBUG=n + +# # Compile librte_lpm # CONFIG_RTE_LIBRTE_LPM=y diff --git a/doc/api/doxy-api.conf.in b/doc/api/doxy-api.conf.in index 3ec012d..6fd3b51 100644 --- a/doc/api/doxy-api.conf.in +++ b/doc/api/doxy-api.conf.in @@ -30,6 +30,7 @@ INPUT = @TOPDIR@/doc/api/doxy-api-index.md \ @TOPDIR@/lib/librte_efd \ @TOPDIR@/lib/librte_ethdev \ @TOPDIR@/lib/librte_eventdev \ + @TOPDIR@/lib/librte_fib \ @TOPDIR@/lib/librte_flow_classify \ @TOPDIR@/lib/librte_gro \ @TOPDIR@/lib/librte_gso \ diff --git a/lib/Makefile b/lib/Makefile index aa5ee1e..5d04ab9 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -53,6 +53,8 @@ DIRS-$(CONFIG_RTE_LIBRTE_EFD) += librte_efd DEPDIRS-librte_efd := librte_eal librte_ring librte_hash DIRS-$(CONFIG_RTE_LIBRTE_RIB) += librte_rib DEPDIRS-librte_rib := librte_eal librte_mempool +DIRS-$(CONFIG_RTE_LIBRTE_FIB) += librte_fib +DEPDIRS-librte_fib := librte_eal librte_rib DIRS-$(CONFIG_RTE_LIBRTE_LPM) += librte_lpm DEPDIRS-librte_lpm := librte_eal librte_hash DIRS-$(CONFIG_RTE_LIBRTE_ACL) += librte_acl diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile new file mode 100644 index 0000000..7362f68 --- /dev/null +++ b/lib/librte_fib/Makefile @@ -0,0 +1,25 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2018 Vladimir Medvedkin +# Copyright(c) 2019 Intel Corporation + +include $(RTE_SDK)/mk/rte.vars.mk + +# library name +LIB = librte_fib.a + +CFLAGS += -O3 +CFLAGS += $(WERROR_FLAGS) -I$(SRCDIR) +CFLAGS += -DALLOW_EXPERIMENTAL_API +LDLIBS += -lrte_eal -lrte_rib + +EXPORT_MAP := rte_fib_version.map + +LIBABIVER := 1 + +# all source are stored in SRCS-y +SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c + +# install this header file +SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h + +include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_fib/meson.build b/lib/librte_fib/meson.build new file mode 100644 index 0000000..6b72360 --- /dev/null +++ b/lib/librte_fib/meson.build @@ -0,0 +1,8 @@ +# SPDX-License-Identifier: BSD-3-Clause +# Copyright(c) 2018 Vladimir Medvedkin +# Copyright(c) 2019 Intel Corporation + +allow_experimental_apis = true +sources = files('rte_fib.c') +headers = files('rte_fib.h') +deps += ['rib'] diff --git a/lib/librte_fib/rte_fib.c b/lib/librte_fib/rte_fib.c new file mode 100644 index 0000000..4d8a771 --- /dev/null +++ b/lib/librte_fib/rte_fib.c @@ -0,0 +1,305 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +TAILQ_HEAD(rte_fib_list, rte_tailq_entry); +static struct rte_tailq_elem rte_fib_tailq = { + .name = "RTE_FIB", +}; +EAL_REGISTER_TAILQ(rte_fib_tailq) + +/* Maximum length of a FIB name. */ +#define RTE_FIB_NAMESIZE 64 + +#if defined(RTE_LIBRTE_FIB_DEBUG) +#define FIB_RETURN_IF_TRUE(cond, retval) do { \ + if (cond) \ + return retval; \ +} while (0) +#else +#define FIB_RETURN_IF_TRUE(cond, retval) +#endif + +struct rte_fib { + char name[RTE_FIB_NAMESIZE]; + enum rte_fib_type type; /**< Type of FIB struct */ + struct rte_rib *rib; /**< RIB helper datastruct */ + void *dp; /**< pointer to the dataplane struct*/ + rte_fib_lookup_fn_t lookup; /**< fib lookup function */ + rte_fib_modify_fn_t modify; /**< modify fib datastruct */ + uint64_t def_nh; +}; + +static void +dummy_lookup(void *fib_p, const uint32_t *ips, uint64_t *next_hops, + const unsigned int n) +{ + unsigned int i; + struct rte_fib *fib = fib_p; + struct rte_rib_node *node; + + for (i = 0; i < n; i++) { + node = rte_rib_lookup(fib->rib, ips[i]); + if (node != NULL) + rte_rib_get_nh(node, &next_hops[i]); + else + next_hops[i] = fib->def_nh; + } +} + +static int +dummy_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, + uint64_t next_hop, int op) +{ + struct rte_rib_node *node; + if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH)) + return -EINVAL; + + node = rte_rib_lookup_exact(fib->rib, ip, depth); + + switch (op) { + case RTE_FIB_ADD: + if (node == NULL) + node = rte_rib_insert(fib->rib, ip, depth); + if (node == NULL) + return -rte_errno; + return rte_rib_set_nh(node, next_hop); + case RTE_FIB_DEL: + if (node == NULL) + return -ENOENT; + rte_rib_remove(fib->rib, ip, depth); + return 0; + } + return -EINVAL; +} + +static int +init_dataplane(struct rte_fib *fib, __rte_unused int socket_id, + struct rte_fib_conf *conf) +{ + switch (conf->type) { + case RTE_FIB_DUMMY: + fib->dp = fib; + fib->lookup = dummy_lookup; + fib->modify = dummy_modify; + return 0; + default: + return -EINVAL; + } + return 0; +} + +int +rte_fib_add(struct rte_fib *fib, uint32_t ip, uint8_t depth, uint64_t next_hop) +{ + if ((fib == NULL) || (fib->modify == NULL) || + (depth > RTE_FIB_MAXDEPTH)) + return -EINVAL; + return fib->modify(fib, ip, depth, next_hop, RTE_FIB_ADD); +} + +int +rte_fib_delete(struct rte_fib *fib, uint32_t ip, uint8_t depth) +{ + if ((fib == NULL) || (fib->modify == NULL) || + (depth > RTE_FIB_MAXDEPTH)) + return -EINVAL; + return fib->modify(fib, ip, depth, 0, RTE_FIB_DEL); +} + +int +rte_fib_lookup_bulk(struct rte_fib *fib, uint32_t *ips, + uint64_t *next_hops, int n) +{ + FIB_RETURN_IF_TRUE(((fib == NULL) || (ips == NULL) || + (next_hops == NULL) || (fib->lookup == NULL)), -EINVAL); + + fib->lookup(fib->dp, ips, next_hops, n); + return 0; +} + +struct rte_fib * +rte_fib_create(const char *name, int socket_id, struct rte_fib_conf *conf) +{ + char mem_name[RTE_FIB_NAMESIZE]; + int ret; + struct rte_fib *fib = NULL; + struct rte_rib *rib = NULL; + struct rte_tailq_entry *te; + struct rte_fib_list *fib_list; + struct rte_rib_conf rib_conf; + + /* Check user arguments. */ + if ((name == NULL) || (conf == NULL) || (conf->max_routes < 0) || + (conf->type >= RTE_FIB_TYPE_MAX)) { + rte_errno = EINVAL; + return NULL; + } + + rib_conf.ext_sz = 0; + rib_conf.max_nodes = conf->max_routes * 2; + + rib = rte_rib_create(name, socket_id, &rib_conf); + if (rib == NULL) { + RTE_LOG(ERR, LPM, + "Can not allocate RIB %s\n", name); + return NULL; + } + + snprintf(mem_name, sizeof(mem_name), "FIB_%s", name); + fib_list = RTE_TAILQ_CAST(rte_fib_tailq.head, rte_fib_list); + + rte_mcfg_tailq_write_lock(); + + /* guarantee there's no existing */ + TAILQ_FOREACH(te, fib_list, next) { + fib = (struct rte_fib *)te->data; + if (strncmp(name, fib->name, RTE_FIB_NAMESIZE) == 0) + break; + } + fib = NULL; + if (te != NULL) { + rte_errno = EEXIST; + goto exit; + } + + /* allocate tailq entry */ + te = rte_zmalloc("FIB_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, LPM, + "Can not allocate tailq entry for FIB %s\n", name); + rte_errno = ENOMEM; + goto exit; + } + + /* Allocate memory to store the FIB data structures. */ + fib = rte_zmalloc_socket(mem_name, + sizeof(struct rte_fib), RTE_CACHE_LINE_SIZE, socket_id); + if (fib == NULL) { + RTE_LOG(ERR, LPM, "FIB %s memory allocation failed\n", name); + rte_errno = ENOMEM; + goto free_te; + } + + rte_strlcpy(fib->name, name, sizeof(fib->name)); + fib->rib = rib; + fib->type = conf->type; + fib->def_nh = conf->default_nh; + ret = init_dataplane(fib, socket_id, conf); + if (ret < 0) { + RTE_LOG(ERR, LPM, + "FIB dataplane struct %s memory allocation failed " + "with err %d\n", name, ret); + rte_errno = -ret; + goto free_fib; + } + + te->data = (void *)fib; + TAILQ_INSERT_TAIL(fib_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + return fib; + +free_fib: + rte_free(fib); +free_te: + rte_free(te); +exit: + rte_mcfg_tailq_write_unlock(); + rte_rib_free(rib); + + return NULL; +} + +struct rte_fib * +rte_fib_find_existing(const char *name) +{ + struct rte_fib *fib = NULL; + struct rte_tailq_entry *te; + struct rte_fib_list *fib_list; + + fib_list = RTE_TAILQ_CAST(rte_fib_tailq.head, rte_fib_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, fib_list, next) { + fib = (struct rte_fib *) te->data; + if (strncmp(name, fib->name, RTE_FIB_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + + return fib; +} + +static void +free_dataplane(struct rte_fib *fib) +{ + switch (fib->type) { + case RTE_FIB_DUMMY: + return; + default: + return; + } +} + +void +rte_fib_free(struct rte_fib *fib) +{ + struct rte_tailq_entry *te; + struct rte_fib_list *fib_list; + + if (fib == NULL) + return; + + fib_list = RTE_TAILQ_CAST(rte_fib_tailq.head, rte_fib_list); + + rte_mcfg_tailq_write_lock(); + + /* find our tailq entry */ + TAILQ_FOREACH(te, fib_list, next) { + if (te->data == (void *)fib) + break; + } + if (te != NULL) + TAILQ_REMOVE(fib_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + free_dataplane(fib); + rte_rib_free(fib->rib); + rte_free(fib); + rte_free(te); +} + +void * +rte_fib_get_dp(struct rte_fib *fib) +{ + return (fib == NULL) ? NULL : fib->dp; +} + +struct rte_rib * +rte_fib_get_rib(struct rte_fib *fib) +{ + return (fib == NULL) ? NULL : fib->rib; +} diff --git a/lib/librte_fib/rte_fib.h b/lib/librte_fib/rte_fib.h new file mode 100644 index 0000000..096cc92 --- /dev/null +++ b/lib/librte_fib/rte_fib.h @@ -0,0 +1,173 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _RTE_FIB_H_ +#define _RTE_FIB_H_ + +/** + * @file + * FIB (Forwarding information base) implementation + * for IPv4 Longest Prefix Match + */ + +#include + +struct rte_fib; + +/** Maximum depth value possible for IPv4 FIB. */ +#define RTE_FIB_MAXDEPTH 32 + +/** Type of FIB struct */ +enum rte_fib_type { + RTE_FIB_DUMMY, /**< RIB tree based FIB */ + RTE_FIB_TYPE_MAX +}; + +/** Modify FIB function */ +typedef int (*rte_fib_modify_fn_t)(struct rte_fib *fib, uint32_t ip, + uint8_t depth, uint64_t next_hop, int op); +/** FIB bulk lookup function */ +typedef void (*rte_fib_lookup_fn_t)(void *fib, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n); + +enum rte_fib_op { + RTE_FIB_ADD, + RTE_FIB_DEL, +}; + +/** FIB configuration structure */ +struct rte_fib_conf { + enum rte_fib_type type; /**< Type of FIB struct */ + /** Default value returned on lookup if there is no route */ + uint64_t default_nh; + int max_routes; +}; + +/** + * Create FIB + * + * @param name + * FIB name + * @param socket_id + * NUMA socket ID for FIB table memory allocation + * @param conf + * Structure containing the configuration + * @return + * Handle to the FIB object on success + * NULL otherwise with rte_errno set to an appropriate values. + */ +__rte_experimental +struct rte_fib * +rte_fib_create(const char *name, int socket_id, struct rte_fib_conf *conf); + +/** + * Find an existing FIB object and return a pointer to it. + * + * @param name + * Name of the fib object as passed to rte_fib_create() + * @return + * Pointer to fib object or NULL if object not found with rte_errno + * set appropriately. Possible rte_errno values include: + * - ENOENT - required entry not available to return. + */ +__rte_experimental +struct rte_fib * +rte_fib_find_existing(const char *name); + +/** + * Free an FIB object. + * + * @param fib + * FIB object handle + * @return + * None + */ +__rte_experimental +void +rte_fib_free(struct rte_fib *fib); + +/** + * Add a route to the FIB. + * + * @param fib + * FIB object handle + * @param ip + * IPv4 prefix address to be added to the FIB + * @param depth + * Prefix length + * @param next_hop + * Next hop to be added to the FIB + * @return + * 0 on success, negative value otherwise + */ +__rte_experimental +int +rte_fib_add(struct rte_fib *fib, uint32_t ip, uint8_t depth, uint64_t next_hop); + +/** + * Delete a rule from the FIB. + * + * @param fib + * FIB object handle + * @param ip + * IPv4 prefix address to be deleted from the FIB + * @param depth + * Prefix length + * @return + * 0 on success, negative value otherwise + */ +__rte_experimental +int +rte_fib_delete(struct rte_fib *fib, uint32_t ip, uint8_t depth); + +/** + * Lookup multiple IP addresses in the FIB. + * + * @param fib + * FIB 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 nexthop value configured for a FIB. + * @param n + * Number of elements in ips (and next_hops) array to lookup. + * @return + * -EINVAL for incorrect arguments, otherwise 0 + */ +__rte_experimental +int +rte_fib_lookup_bulk(struct rte_fib *fib, uint32_t *ips, + uint64_t *next_hops, int n); + +/** + * Get pointer to the dataplane specific struct + * + * @param fib + * FIB object handle + * @return + * Pointer on the dataplane struct on success + * NULL othervise + */ +__rte_experimental +void * +rte_fib_get_dp(struct rte_fib *fib); + +/** + * Get pointer to the RIB + * + * @param fib + * FIB object handle + * @return + * Pointer on the RIB on success + * NULL othervise + */ +__rte_experimental +struct rte_rib * +rte_fib_get_rib(struct rte_fib *fib); + +#endif /* _RTE_FIB_H_ */ diff --git a/lib/librte_fib/rte_fib_version.map b/lib/librte_fib/rte_fib_version.map new file mode 100644 index 0000000..776195f --- /dev/null +++ b/lib/librte_fib/rte_fib_version.map @@ -0,0 +1,14 @@ +EXPERIMENTAL { + global: + + rte_fib_add; + rte_fib_create; + rte_fib_delete; + rte_fib_find_existing; + rte_fib_free; + rte_fib_lookup_bulk; + rte_fib_get_dp; + rte_fib_get_rib; + + local: *; +}; diff --git a/lib/meson.build b/lib/meson.build index d7f2a04..9700433 100644 --- a/lib/meson.build +++ b/lib/meson.build @@ -25,6 +25,8 @@ libraries = [ 'rcu', 'rib', 'reorder', 'sched', 'security', 'stack', 'vhost', # ipsec lib depends on net, crypto and security 'ipsec', + #fib lib depends on rib + 'fib', # add pkt framework libs which use other libs from above 'port', 'table', 'pipeline', # flow_classify lib depends on pkt framework table lib diff --git a/mk/rte.app.mk b/mk/rte.app.mk index 4517874..7ce87e7 100644 --- a/mk/rte.app.mk +++ b/mk/rte.app.mk @@ -45,6 +45,7 @@ _LDLIBS-$(CONFIG_RTE_LIBRTE_PDUMP) += -lrte_pdump _LDLIBS-$(CONFIG_RTE_LIBRTE_DISTRIBUTOR) += -lrte_distributor _LDLIBS-$(CONFIG_RTE_LIBRTE_IP_FRAG) += -lrte_ip_frag _LDLIBS-$(CONFIG_RTE_LIBRTE_METER) += -lrte_meter +_LDLIBS-$(CONFIG_RTE_LIBRTE_FIB) += -lrte_fib _LDLIBS-$(CONFIG_RTE_LIBRTE_RIB) += -lrte_rib _LDLIBS-$(CONFIG_RTE_LIBRTE_LPM) += -lrte_lpm _LDLIBS-$(CONFIG_RTE_LIBRTE_ACL) += -lrte_acl From patchwork Fri Nov 1 15:21:39 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62321 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id B07F6A00BE; Fri, 1 Nov 2019 16:23:08 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id D93011E868; Fri, 1 Nov 2019 16:22:05 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 768EE1E54C for ; Fri, 1 Nov 2019 16:22:02 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:02 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979118" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:00 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:39 +0000 Message-Id: <45bd28f190e5cb0526e8fe66ae03eefcc2005796.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 06/12] fib: add FIB ipv6 support 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" Add FIB library support for IPv6. It implements a dataplane structures and algorithms designed for fast IPv6 longest prefix match. Signed-off-by: Vladimir Medvedkin --- lib/librte_fib/Makefile | 4 +- lib/librte_fib/meson.build | 4 +- lib/librte_fib/rte_fib6.c | 308 +++++++++++++++++++++++++++++++++++++ lib/librte_fib/rte_fib6.h | 179 +++++++++++++++++++++ lib/librte_fib/rte_fib_version.map | 9 ++ 5 files changed, 500 insertions(+), 4 deletions(-) create mode 100644 lib/librte_fib/rte_fib6.c create mode 100644 lib/librte_fib/rte_fib6.h diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile index 7362f68..0bdf55b 100644 --- a/lib/librte_fib/Makefile +++ b/lib/librte_fib/Makefile @@ -17,9 +17,9 @@ EXPORT_MAP := rte_fib_version.map LIBABIVER := 1 # all source are stored in SRCS-y -SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c # install this header file -SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h +SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h include $(RTE_SDK)/mk/rte.lib.mk diff --git a/lib/librte_fib/meson.build b/lib/librte_fib/meson.build index 6b72360..32dfdec 100644 --- a/lib/librte_fib/meson.build +++ b/lib/librte_fib/meson.build @@ -3,6 +3,6 @@ # Copyright(c) 2019 Intel Corporation allow_experimental_apis = true -sources = files('rte_fib.c') -headers = files('rte_fib.h') +sources = files('rte_fib.c', 'rte_fib6.c') +headers = files('rte_fib.h', 'rte_fib6.h') deps += ['rib'] diff --git a/lib/librte_fib/rte_fib6.c b/lib/librte_fib/rte_fib6.c new file mode 100644 index 0000000..9f00a80 --- /dev/null +++ b/lib/librte_fib/rte_fib6.c @@ -0,0 +1,308 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include + +#include +#include +#include +#include +#include +#include +#include + +#include +#include + +TAILQ_HEAD(rte_fib6_list, rte_tailq_entry); +static struct rte_tailq_elem rte_fib6_tailq = { + .name = "RTE_FIB6", +}; +EAL_REGISTER_TAILQ(rte_fib6_tailq) + +/* Maximum length of a FIB name. */ +#define FIB6_NAMESIZE 64 + +#if defined(RTE_LIBRTE_FIB_DEBUG) +#define FIB6_RETURN_IF_TRUE(cond, retval) do { \ + if (cond) \ + return retval; \ +} while (0) +#else +#define FIB6_RETURN_IF_TRUE(cond, retval) +#endif + +struct rte_fib6 { + char name[FIB6_NAMESIZE]; + enum rte_fib6_type type; /**< Type of FIB struct */ + struct rte_rib6 *rib; /**< RIB helper datastruct */ + void *dp; /**< pointer to the dataplane struct*/ + rte_fib6_lookup_fn_t lookup; /**< fib lookup function */ + rte_fib6_modify_fn_t modify; /**< modify fib datastruct */ + uint64_t def_nh; +}; + +static void +dummy_lookup(void *fib_p, uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], + uint64_t *next_hops, const unsigned int n) +{ + unsigned int i; + struct rte_fib6 *fib = fib_p; + struct rte_rib6_node *node; + + for (i = 0; i < n; i++) { + node = rte_rib6_lookup(fib->rib, ips[i]); + if (node != NULL) + rte_rib6_get_nh(node, &next_hops[i]); + else + next_hops[i] = fib->def_nh; + } +} + +static int +dummy_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth, uint64_t next_hop, int op) +{ + struct rte_rib6_node *node; + if ((fib == NULL) || (depth > RTE_FIB6_MAXDEPTH)) + return -EINVAL; + + node = rte_rib6_lookup_exact(fib->rib, ip, depth); + + switch (op) { + case RTE_FIB6_ADD: + if (node == NULL) + node = rte_rib6_insert(fib->rib, ip, depth); + if (node == NULL) + return -rte_errno; + return rte_rib6_set_nh(node, next_hop); + case RTE_FIB6_DEL: + if (node == NULL) + return -ENOENT; + rte_rib6_remove(fib->rib, ip, depth); + return 0; + } + return -EINVAL; +} + +static int +init_dataplane(struct rte_fib6 *fib, __rte_unused int socket_id, + struct rte_fib6_conf *conf) +{ + switch (conf->type) { + case RTE_FIB6_DUMMY: + fib->dp = fib; + fib->lookup = dummy_lookup; + fib->modify = dummy_modify; + return 0; + default: + return -EINVAL; + } + return 0; +} + +int +rte_fib6_add(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth, uint64_t next_hop) +{ + if ((fib == NULL) || (ip == NULL) || (fib->modify == NULL) || + (depth > RTE_FIB6_MAXDEPTH)) + return -EINVAL; + return fib->modify(fib, ip, depth, next_hop, RTE_FIB6_ADD); +} + +int +rte_fib6_delete(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth) +{ + if ((fib == NULL) || (ip == NULL) || (fib->modify == NULL) || + (depth > RTE_FIB6_MAXDEPTH)) + return -EINVAL; + return fib->modify(fib, ip, depth, 0, RTE_FIB6_DEL); +} + +int +rte_fib6_lookup_bulk(struct rte_fib6 *fib, + uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], + uint64_t *next_hops, int n) +{ + FIB6_RETURN_IF_TRUE((fib == NULL) || (ips == NULL) || + (next_hops == NULL) || (fib->lookup == NULL), -EINVAL); + fib->lookup(fib->dp, ips, next_hops, n); + return 0; +} + +struct rte_fib6 * +rte_fib6_create(const char *name, int socket_id, struct rte_fib6_conf *conf) +{ + char mem_name[FIB6_NAMESIZE]; + int ret; + struct rte_fib6 *fib = NULL; + struct rte_rib6 *rib = NULL; + struct rte_tailq_entry *te; + struct rte_fib6_list *fib_list; + struct rte_rib6_conf rib_conf; + + /* Check user arguments. */ + if ((name == NULL) || (conf == NULL) || (conf->max_routes < 0) || + (conf->type >= RTE_FIB6_TYPE_MAX)) { + rte_errno = EINVAL; + return NULL; + } + + rib_conf.ext_sz = 0; + rib_conf.max_nodes = conf->max_routes * 2; + + rib = rte_rib6_create(name, socket_id, &rib_conf); + if (rib == NULL) { + RTE_LOG(ERR, LPM, + "Can not allocate RIB %s\n", name); + return NULL; + } + + snprintf(mem_name, sizeof(mem_name), "FIB6_%s", name); + fib_list = RTE_TAILQ_CAST(rte_fib6_tailq.head, rte_fib6_list); + + rte_mcfg_tailq_write_lock(); + + /* guarantee there's no existing */ + TAILQ_FOREACH(te, fib_list, next) { + fib = (struct rte_fib6 *)te->data; + if (strncmp(name, fib->name, FIB6_NAMESIZE) == 0) + break; + } + fib = NULL; + if (te != NULL) { + rte_errno = EEXIST; + goto exit; + } + + /* allocate tailq entry */ + te = rte_zmalloc("FIB_TAILQ_ENTRY", sizeof(*te), 0); + if (te == NULL) { + RTE_LOG(ERR, LPM, + "Can not allocate tailq entry for FIB %s\n", name); + rte_errno = ENOMEM; + goto exit; + } + + /* Allocate memory to store the FIB data structures. */ + fib = rte_zmalloc_socket(mem_name, + sizeof(struct rte_fib6), RTE_CACHE_LINE_SIZE, socket_id); + if (fib == NULL) { + RTE_LOG(ERR, LPM, "FIB %s memory allocation failed\n", name); + rte_errno = ENOMEM; + goto free_te; + } + + rte_strlcpy(fib->name, name, sizeof(fib->name)); + fib->rib = rib; + fib->type = conf->type; + fib->def_nh = conf->default_nh; + ret = init_dataplane(fib, socket_id, conf); + if (ret < 0) { + RTE_LOG(ERR, LPM, + "FIB dataplane struct %s memory allocation failed\n", + name); + rte_errno = -ret; + goto free_fib; + } + + te->data = (void *)fib; + TAILQ_INSERT_TAIL(fib_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + return fib; + +free_fib: + rte_free(fib); +free_te: + rte_free(te); +exit: + rte_mcfg_tailq_write_unlock(); + rte_rib6_free(rib); + + return NULL; +} + +struct rte_fib6 * +rte_fib6_find_existing(const char *name) +{ + struct rte_fib6 *fib = NULL; + struct rte_tailq_entry *te; + struct rte_fib6_list *fib_list; + + fib_list = RTE_TAILQ_CAST(rte_fib6_tailq.head, rte_fib6_list); + + rte_mcfg_tailq_read_lock(); + TAILQ_FOREACH(te, fib_list, next) { + fib = (struct rte_fib6 *) te->data; + if (strncmp(name, fib->name, FIB6_NAMESIZE) == 0) + break; + } + rte_mcfg_tailq_read_unlock(); + + if (te == NULL) { + rte_errno = ENOENT; + return NULL; + } + + return fib; +} + +static void +free_dataplane(struct rte_fib6 *fib) +{ + switch (fib->type) { + case RTE_FIB6_DUMMY: + return; + default: + return; + } +} + +void +rte_fib6_free(struct rte_fib6 *fib) +{ + struct rte_tailq_entry *te; + struct rte_fib6_list *fib_list; + + if (fib == NULL) + return; + + fib_list = RTE_TAILQ_CAST(rte_fib6_tailq.head, rte_fib6_list); + + rte_mcfg_tailq_write_lock(); + + /* find our tailq entry */ + TAILQ_FOREACH(te, fib_list, next) { + if (te->data == (void *)fib) + break; + } + if (te != NULL) + TAILQ_REMOVE(fib_list, te, next); + + rte_mcfg_tailq_write_unlock(); + + free_dataplane(fib); + rte_rib6_free(fib->rib); + rte_free(fib); + rte_free(te); +} + +void * +rte_fib6_get_dp(struct rte_fib6 *fib) +{ + return (fib == NULL) ? NULL : fib->dp; +} + +struct rte_rib6 * +rte_fib6_get_rib(struct rte_fib6 *fib) +{ + return (fib == NULL) ? NULL : fib->rib; +} + diff --git a/lib/librte_fib/rte_fib6.h b/lib/librte_fib/rte_fib6.h new file mode 100644 index 0000000..3322123 --- /dev/null +++ b/lib/librte_fib/rte_fib6.h @@ -0,0 +1,179 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _RTE_FIB6_H_ +#define _RTE_FIB6_H_ + +/** + * @file + * FIB (Forwarding information base) implementation + * for IPv6 Longest Prefix Match + */ + +#include + +#define RTE_FIB6_IPV6_ADDR_SIZE 16 +/** Maximum depth value possible for IPv6 FIB. */ +#define RTE_FIB6_MAXDEPTH 128 + +struct rte_fib6; + +/** Type of FIB struct */ +enum rte_fib6_type { + RTE_FIB6_DUMMY, /**< RIB6 tree based FIB */ + RTE_FIB6_TYPE_MAX +}; + +/** Modify FIB function */ +typedef int (*rte_fib6_modify_fn_t)(struct rte_fib6 *fib, + const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], uint8_t depth, + uint64_t next_hop, int op); +/** FIB bulk lookup function */ +typedef void (*rte_fib6_lookup_fn_t)(void *fib, + uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], + uint64_t *next_hops, const unsigned int n); + +enum rte_fib6_op { + RTE_FIB6_ADD, + RTE_FIB6_DEL, +}; + +/** FIB configuration structure */ +struct rte_fib6_conf { + enum rte_fib6_type type; /**< Type of FIB struct */ + /** Default value returned on lookup if there is no route */ + uint64_t default_nh; + int max_routes; +}; + +/** + * Create FIB + * + * @param name + * FIB name + * @param socket_id + * NUMA socket ID for FIB table memory allocation + * @param conf + * Structure containing the configuration + * @return + * Handle to FIB object on success + * NULL otherwise with rte_errno set to an appropriate values. + */ +__rte_experimental +struct rte_fib6 * +rte_fib6_create(const char *name, int socket_id, struct rte_fib6_conf *conf); + +/** + * Find an existing FIB object and return a pointer to it. + * + * @param name + * Name of the fib object as passed to rte_fib6_create() + * @return + * Pointer to fib object or NULL if object not found with rte_errno + * set appropriately. Possible rte_errno values include: + * - ENOENT - required entry not available to return. + */ +__rte_experimental +struct rte_fib6 * +rte_fib6_find_existing(const char *name); + +/** + * Free an FIB object. + * + * @param fib + * FIB object handle + * @return + * None + */ +__rte_experimental +void +rte_fib6_free(struct rte_fib6 *fib); + +/** + * Add a route to the FIB. + * + * @param fib + * FIB object handle + * @param ip + * IPv6 prefix address to be added to the FIB + * @param depth + * Prefix length + * @param next_hop + * Next hop to be added to the FIB + * @return + * 0 on success, negative value otherwise + */ +__rte_experimental +int +rte_fib6_add(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth, uint64_t next_hop); + +/** + * Delete a rule from the FIB. + * + * @param fib + * FIB object handle + * @param ip + * IPv6 prefix address to be deleted from the FIB + * @param depth + * Prefix length + * @return + * 0 on success, negative value otherwise + */ +__rte_experimental +int +rte_fib6_delete(struct rte_fib6 *fib, + const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], uint8_t depth); + +/** + * Lookup multiple IP addresses in the FIB. + * + * @param fib + * FIB object handle + * @param ips + * Array of IPv6s 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 nexthop value configured for a FIB. + * @param n + * Number of elements in ips (and next_hops) array to lookup. + * @return + * -EINVAL for incorrect arguments, otherwise 0 + */ +__rte_experimental +int +rte_fib6_lookup_bulk(struct rte_fib6 *fib, + uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], + uint64_t *next_hops, int n); + +/** + * Get pointer to the dataplane specific struct + * + * @param fib + * FIB6 object handle + * @return + * Pointer on the dataplane struct on success + * NULL othervise + */ +__rte_experimental +void * +rte_fib6_get_dp(struct rte_fib6 *fib); + +/** + * Get pointer to the RIB6 + * + * @param fib + * FIB object handle + * @return + * Pointer on the RIB6 on success + * NULL othervise + */ +__rte_experimental +struct rte_rib6 * +rte_fib6_get_rib(struct rte_fib6 *fib); + +#endif /* _RTE_FIB6_H_ */ diff --git a/lib/librte_fib/rte_fib_version.map b/lib/librte_fib/rte_fib_version.map index 776195f..9527417 100644 --- a/lib/librte_fib/rte_fib_version.map +++ b/lib/librte_fib/rte_fib_version.map @@ -10,5 +10,14 @@ EXPERIMENTAL { rte_fib_get_dp; rte_fib_get_rib; + rte_fib6_add; + rte_fib6_create; + rte_fib6_delete; + rte_fib6_find_existing; + rte_fib6_free; + rte_fib6_lookup_bulk; + rte_fib6_get_dp; + rte_fib6_get_rib; + local: *; }; From patchwork Fri Nov 1 15:21:40 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62322 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 24200A00BE; Fri, 1 Nov 2019 16:23:19 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 81F221E874; Fri, 1 Nov 2019 16:22:07 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id A2D3D1E85E for ; Fri, 1 Nov 2019 16:22:04 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:04 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979125" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:02 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:40 +0000 Message-Id: <287966d228df112528c529e0db76f22bd2d64549.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 07/12] fib: add DIR24-8 dataplane algorithm 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" Add fib implementation for DIR24_8 algorithm for ipv4. Implementation is similar to current LPM implementation but has few enhancements: faster control plabe operations more bits for userdata in table entries configurable userdata size Signed-off-by: Vladimir Medvedkin --- lib/librte_fib/Makefile | 2 +- lib/librte_fib/dir24_8.c | 737 +++++++++++++++++++++++++++++++++++++++++++++ lib/librte_fib/dir24_8.h | 36 +++ lib/librte_fib/meson.build | 2 +- lib/librte_fib/rte_fib.c | 14 + lib/librte_fib/rte_fib.h | 17 +- 6 files changed, 805 insertions(+), 3 deletions(-) create mode 100644 lib/librte_fib/dir24_8.c create mode 100644 lib/librte_fib/dir24_8.h diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile index 0bdf55b..67fde9a 100644 --- a/lib/librte_fib/Makefile +++ b/lib/librte_fib/Makefile @@ -17,7 +17,7 @@ EXPORT_MAP := rte_fib_version.map LIBABIVER := 1 # all source are stored in SRCS-y -SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c # install this header file SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h diff --git a/lib/librte_fib/dir24_8.c b/lib/librte_fib/dir24_8.c new file mode 100644 index 0000000..c9dce3c --- /dev/null +++ b/lib/librte_fib/dir24_8.c @@ -0,0 +1,737 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#include +#include +#include "dir24_8.h" + +#define DIR24_8_NAMESIZE 64 + +#define DIR24_8_TBL24_NUM_ENT (1 << 24) +#define DIR24_8_TBL8_GRP_NUM_ENT 256U +#define DIR24_8_EXT_ENT 1 +#define DIR24_8_TBL24_MASK 0xffffff00 + +#define BITMAP_SLAB_BIT_SIZE_LOG2 6 +#define BITMAP_SLAB_BIT_SIZE (1 << BITMAP_SLAB_BIT_SIZE_LOG2) +#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) + +struct dir24_8_tbl { + uint32_t number_tbl8s; /**< Total number of tbl8s */ + uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ + uint32_t cur_tbl8s; /**< Current number of tbl8s */ + enum rte_fib_dir24_8_nh_sz nh_sz; /**< Size of nexthop entry */ + uint64_t def_nh; /**< Default next hop */ + uint64_t *tbl8; /**< tbl8 table. */ + uint64_t *tbl8_idxes; /**< bitmap containing free tbl8 idxes*/ + /* tbl24 table. */ + __extension__ uint64_t tbl24[0] __rte_cache_aligned; +}; + +#define ROUNDUP(x, y) RTE_ALIGN_CEIL(x, (1 << (32 - y))) + +enum lookup_type { + MACRO, + INLINE, + UNI +}; +enum lookup_type test_lookup = MACRO; + +static inline void * +get_tbl24_p(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) +{ + return (void *)&((uint8_t *)dp->tbl24)[(ip & + DIR24_8_TBL24_MASK) >> (8 - nh_sz)]; +} + +static inline uint8_t +bits_in_nh(uint8_t nh_sz) +{ + return 8 * (1 << nh_sz); +} + +static inline uint64_t +get_max_nh(uint8_t nh_sz) +{ + return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); +} + +static inline uint32_t +get_tbl24_idx(uint32_t ip) +{ + return ip >> 8; +} + +static inline uint32_t +get_tbl8_idx(uint32_t res, uint32_t ip) +{ + return (res >> 1) * DIR24_8_TBL8_GRP_NUM_ENT + (uint8_t)ip; +} + +static inline uint64_t +lookup_msk(uint8_t nh_sz) +{ + return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; +} + +static inline uint8_t +get_psd_idx(uint32_t val, uint8_t nh_sz) +{ + return val & ((1 << (3 - nh_sz)) - 1); +} + +static inline uint32_t +get_tbl_idx(uint32_t val, uint8_t nh_sz) +{ + return val >> (3 - nh_sz); +} + +static inline uint64_t +get_tbl24(struct dir24_8_tbl *dp, uint32_t ip, uint8_t nh_sz) +{ + return ((dp->tbl24[get_tbl_idx(get_tbl24_idx(ip), nh_sz)] >> + (get_psd_idx(get_tbl24_idx(ip), nh_sz) * + bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); +} + +static inline uint64_t +get_tbl8(struct dir24_8_tbl *dp, uint32_t res, uint32_t ip, uint8_t nh_sz) +{ + return ((dp->tbl8[get_tbl_idx(get_tbl8_idx(res, ip), nh_sz)] >> + (get_psd_idx(get_tbl8_idx(res, ip), nh_sz) * + bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); +} + +static inline int +is_entry_extended(uint64_t ent) +{ + return (ent & DIR24_8_EXT_ENT) == DIR24_8_EXT_ENT; +} + +#define LOOKUP_FUNC(suffix, type, bulk_prefetch, nh_sz) \ +static void dir24_8_lookup_bulk_##suffix(void *p, const uint32_t *ips, \ + uint64_t *next_hops, const unsigned int n) \ +{ \ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; \ + uint64_t tmp; \ + uint32_t i; \ + uint32_t prefetch_offset = \ + RTE_MIN((unsigned int)bulk_prefetch, n); \ + \ + for (i = 0; i < prefetch_offset; i++) \ + rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); \ + for (i = 0; i < (n - prefetch_offset); i++) { \ + rte_prefetch0(get_tbl24_p(dp, \ + ips[i + prefetch_offset], nh_sz)); \ + tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ + if (unlikely(is_entry_extended(tmp))) \ + tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ + ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ + next_hops[i] = tmp >> 1; \ + } \ + for (; i < n; i++) { \ + tmp = ((type *)dp->tbl24)[ips[i] >> 8]; \ + if (unlikely(is_entry_extended(tmp))) \ + tmp = ((type *)dp->tbl8)[(uint8_t)ips[i] + \ + ((tmp >> 1) * DIR24_8_TBL8_GRP_NUM_ENT)]; \ + next_hops[i] = tmp >> 1; \ + } \ +} \ + +LOOKUP_FUNC(1b, uint8_t, 5, 0) +LOOKUP_FUNC(2b, uint16_t, 6, 1) +LOOKUP_FUNC(4b, uint32_t, 15, 2) +LOOKUP_FUNC(8b, uint64_t, 12, 3) + +static inline void +dir24_8_lookup_bulk(struct dir24_8_tbl *dp, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n, uint8_t nh_sz) +{ + uint64_t tmp; + uint32_t i; + uint32_t prefetch_offset = RTE_MIN(15U, n); + + for (i = 0; i < prefetch_offset; i++) + rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); + for (i = 0; i < (n - prefetch_offset); i++) { + rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], + nh_sz)); + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } + for (; i < n; i++) { + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } +} + +static void +dir24_8_lookup_bulk_0(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 0); +} + +static void +dir24_8_lookup_bulk_1(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 1); +} + +static void +dir24_8_lookup_bulk_2(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 2); +} + +static void +dir24_8_lookup_bulk_3(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + dir24_8_lookup_bulk(dp, ips, next_hops, n, 3); +} + +static void +dir24_8_lookup_bulk_uni(void *p, const uint32_t *ips, + uint64_t *next_hops, const unsigned int n) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + uint64_t tmp; + uint32_t i; + uint32_t prefetch_offset = RTE_MIN(15U, n); + uint8_t nh_sz = dp->nh_sz; + + for (i = 0; i < prefetch_offset; i++) + rte_prefetch0(get_tbl24_p(dp, ips[i], nh_sz)); + for (i = 0; i < (n - prefetch_offset); i++) { + rte_prefetch0(get_tbl24_p(dp, ips[i + prefetch_offset], + nh_sz)); + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } + for (; i < n; i++) { + tmp = get_tbl24(dp, ips[i], nh_sz); + if (unlikely(is_entry_extended(tmp))) + tmp = get_tbl8(dp, tmp, ips[i], nh_sz); + + next_hops[i] = tmp >> 1; + } +} + +rte_fib_lookup_fn_t +dir24_8_get_lookup_fn(struct rte_fib_conf *fib_conf) +{ + enum rte_fib_dir24_8_nh_sz nh_sz = fib_conf->dir24_8.nh_sz; + + if (test_lookup == MACRO) { + switch (nh_sz) { + case RTE_FIB_DIR24_8_1B: + return dir24_8_lookup_bulk_1b; + case RTE_FIB_DIR24_8_2B: + return dir24_8_lookup_bulk_2b; + case RTE_FIB_DIR24_8_4B: + return dir24_8_lookup_bulk_4b; + case RTE_FIB_DIR24_8_8B: + return dir24_8_lookup_bulk_8b; + } + } else if (test_lookup == INLINE) { + switch (nh_sz) { + case RTE_FIB_DIR24_8_1B: + return dir24_8_lookup_bulk_0; + case RTE_FIB_DIR24_8_2B: + return dir24_8_lookup_bulk_1; + case RTE_FIB_DIR24_8_4B: + return dir24_8_lookup_bulk_2; + case RTE_FIB_DIR24_8_8B: + return dir24_8_lookup_bulk_3; + } + } else + return dir24_8_lookup_bulk_uni; + return NULL; +} + +static void +write_to_fib(void *ptr, uint64_t val, enum rte_fib_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_FIB_DIR24_8_1B: + for (i = 0; i < n; i++) + ptr8[i] = (uint8_t)val; + break; + case RTE_FIB_DIR24_8_2B: + for (i = 0; i < n; i++) + ptr16[i] = (uint16_t)val; + break; + case RTE_FIB_DIR24_8_4B: + for (i = 0; i < n; i++) + ptr32[i] = (uint32_t)val; + break; + case RTE_FIB_DIR24_8_8B: + for (i = 0; i < n; i++) + ptr64[i] = (uint64_t)val; + break; + } +} + +static int +tbl8_get_idx(struct dir24_8_tbl *dp) +{ + uint32_t i; + int bit_idx; + + for (i = 0; (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) && + (dp->tbl8_idxes[i] == UINT64_MAX); i++) + ; + if (i < (dp->number_tbl8s >> BITMAP_SLAB_BIT_SIZE_LOG2)) { + bit_idx = __builtin_ctzll(~dp->tbl8_idxes[i]); + dp->tbl8_idxes[i] |= (1ULL << bit_idx); + return (i << BITMAP_SLAB_BIT_SIZE_LOG2) + bit_idx; + } + return -ENOSPC; +} + +static inline void +tbl8_free_idx(struct dir24_8_tbl *dp, int idx) +{ + dp->tbl8_idxes[idx >> BITMAP_SLAB_BIT_SIZE_LOG2] &= + ~(1ULL << (idx & BITMAP_SLAB_BITMASK)); +} + +static int +tbl8_alloc(struct dir24_8_tbl *dp, uint64_t nh) +{ + int64_t tbl8_idx; + uint8_t *tbl8_ptr; + + tbl8_idx = tbl8_get_idx(dp); + if (tbl8_idx < 0) + return tbl8_idx; + tbl8_ptr = (uint8_t *)dp->tbl8 + + ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) << + dp->nh_sz); + /*Init tbl8 entries with nexthop from tbl24*/ + write_to_fib((void *)tbl8_ptr, nh| + DIR24_8_EXT_ENT, dp->nh_sz, + DIR24_8_TBL8_GRP_NUM_ENT); + dp->cur_tbl8s++; + return tbl8_idx; +} + +static void +tbl8_recycle(struct dir24_8_tbl *dp, uint32_t ip, uint64_t tbl8_idx) +{ + uint32_t i; + uint64_t nh; + uint8_t *ptr8; + uint16_t *ptr16; + uint32_t *ptr32; + uint64_t *ptr64; + + switch (dp->nh_sz) { + case RTE_FIB_DIR24_8_1B: + ptr8 = &((uint8_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr8; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr8[i]) + return; + } + ((uint8_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr8[i] = 0; + break; + case RTE_FIB_DIR24_8_2B: + ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr16; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr16[i]) + return; + } + ((uint16_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr16[i] = 0; + break; + case RTE_FIB_DIR24_8_4B: + ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr32; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr32[i]) + return; + } + ((uint32_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr32[i] = 0; + break; + case RTE_FIB_DIR24_8_8B: + ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx * + DIR24_8_TBL8_GRP_NUM_ENT]; + nh = *ptr64; + for (i = 1; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr64[i]) + return; + } + ((uint64_t *)dp->tbl24)[ip >> 8] = + nh & ~DIR24_8_EXT_ENT; + for (i = 0; i < DIR24_8_TBL8_GRP_NUM_ENT; i++) + ptr64[i] = 0; + break; + } + tbl8_free_idx(dp, tbl8_idx); + dp->cur_tbl8s--; +} + +static int +install_to_fib(struct dir24_8_tbl *dp, uint32_t ledge, uint32_t redge, + uint64_t next_hop) +{ + uint64_t tbl24_tmp; + int tbl8_idx; + int tmp_tbl8_idx; + uint8_t *tbl8_ptr; + uint32_t len; + + len = ((ledge == 0) && (redge == 0)) ? 1 << 24 : + ((redge & DIR24_8_TBL24_MASK) - ROUNDUP(ledge, 24)) >> 8; + + if (((ledge >> 8) != (redge >> 8)) || (len == 1 << 24)) { + if ((ROUNDUP(ledge, 24) - ledge) != 0) { + tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz); + if ((tbl24_tmp & DIR24_8_EXT_ENT) != + DIR24_8_EXT_ENT) { + /** + * Make sure there is space for two TBL8. + * This is necessary when installing range that + * needs tbl8 for ledge and redge. + */ + tbl8_idx = tbl8_alloc(dp, tbl24_tmp); + tmp_tbl8_idx = tbl8_get_idx(dp); + if (tbl8_idx < 0) + return -ENOSPC; + else if (tmp_tbl8_idx < 0) { + tbl8_free_idx(dp, tbl8_idx); + return -ENOSPC; + } + tbl8_free_idx(dp, tmp_tbl8_idx); + /*update dir24 entry with tbl8 index*/ + write_to_fib(get_tbl24_p(dp, ledge, + dp->nh_sz), (tbl8_idx << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, 1); + } else + tbl8_idx = tbl24_tmp >> 1; + tbl8_ptr = (uint8_t *)dp->tbl8 + + (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) + + (ledge & ~DIR24_8_TBL24_MASK)) << + dp->nh_sz); + /*update tbl8 with new next hop*/ + write_to_fib((void *)tbl8_ptr, (next_hop << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, ROUNDUP(ledge, 24) - ledge); + tbl8_recycle(dp, ledge, tbl8_idx); + } + write_to_fib(get_tbl24_p(dp, ROUNDUP(ledge, 24), dp->nh_sz), + next_hop << 1, dp->nh_sz, len); + if (redge & ~DIR24_8_TBL24_MASK) { + tbl24_tmp = get_tbl24(dp, redge, dp->nh_sz); + if ((tbl24_tmp & DIR24_8_EXT_ENT) != + DIR24_8_EXT_ENT) { + tbl8_idx = tbl8_alloc(dp, tbl24_tmp); + if (tbl8_idx < 0) + return -ENOSPC; + /*update dir24 entry with tbl8 index*/ + write_to_fib(get_tbl24_p(dp, redge, + dp->nh_sz), (tbl8_idx << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, 1); + } else + tbl8_idx = tbl24_tmp >> 1; + tbl8_ptr = (uint8_t *)dp->tbl8 + + ((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) << + dp->nh_sz); + /*update tbl8 with new next hop*/ + write_to_fib((void *)tbl8_ptr, (next_hop << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, redge & ~DIR24_8_TBL24_MASK); + tbl8_recycle(dp, redge, tbl8_idx); + } + } else if ((redge - ledge) != 0) { + tbl24_tmp = get_tbl24(dp, ledge, dp->nh_sz); + if ((tbl24_tmp & DIR24_8_EXT_ENT) != + DIR24_8_EXT_ENT) { + tbl8_idx = tbl8_alloc(dp, tbl24_tmp); + if (tbl8_idx < 0) + return -ENOSPC; + /*update dir24 entry with tbl8 index*/ + write_to_fib(get_tbl24_p(dp, ledge, dp->nh_sz), + (tbl8_idx << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, 1); + } else + tbl8_idx = tbl24_tmp >> 1; + tbl8_ptr = (uint8_t *)dp->tbl8 + + (((tbl8_idx * DIR24_8_TBL8_GRP_NUM_ENT) + + (ledge & ~DIR24_8_TBL24_MASK)) << + dp->nh_sz); + /*update tbl8 with new next hop*/ + write_to_fib((void *)tbl8_ptr, (next_hop << 1)| + DIR24_8_EXT_ENT, + dp->nh_sz, redge - ledge); + tbl8_recycle(dp, ledge, tbl8_idx); + } + return 0; +} + +static int +modify_fib(struct dir24_8_tbl *dp, struct rte_rib *rib, uint32_t ip, + uint8_t depth, uint64_t next_hop) +{ + struct rte_rib_node *tmp = NULL; + uint32_t ledge, redge, tmp_ip; + int ret; + uint8_t tmp_depth; + + ledge = ip; + do { + tmp = rte_rib_get_nxt(rib, ip, depth, tmp, + RTE_RIB_GET_NXT_COVER); + if (tmp != NULL) { + rte_rib_get_depth(tmp, &tmp_depth); + if (tmp_depth == depth) + continue; + rte_rib_get_ip(tmp, &tmp_ip); + redge = tmp_ip & rte_rib_depth_to_mask(tmp_depth); + if (ledge == redge) { + ledge = redge + + (uint32_t)(1ULL << (32 - tmp_depth)); + continue; + } + ret = install_to_fib(dp, 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)); + if (ledge == redge) + break; + ret = install_to_fib(dp, ledge, redge, + next_hop); + if (ret != 0) + return ret; + } + } while (tmp); + + return 0; +} + +int +dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, + uint64_t next_hop, int op) +{ + struct dir24_8_tbl *dp; + struct rte_rib *rib; + struct rte_rib_node *tmp = NULL; + struct rte_rib_node *node; + struct rte_rib_node *parent; + int ret = 0; + uint64_t par_nh, node_nh; + + if ((fib == NULL) || (depth > RTE_FIB_MAXDEPTH)) + return -EINVAL; + + dp = rte_fib_get_dp(fib); + rib = rte_fib_get_rib(fib); + RTE_ASSERT((dp != NULL) && (rib != NULL)); + + if (next_hop > get_max_nh(dp->nh_sz)) + return -EINVAL; + + ip &= rte_rib_depth_to_mask(depth); + + node = rte_rib_lookup_exact(rib, ip, depth); + switch (op) { + case RTE_FIB_ADD: + if (node != NULL) { + rte_rib_get_nh(node, &node_nh); + if (node_nh == next_hop) + return 0; + ret = modify_fib(dp, rib, ip, depth, next_hop); + if (ret == 0) + rte_rib_set_nh(node, next_hop); + return 0; + } + if (depth > 24) { + tmp = rte_rib_get_nxt(rib, ip, 24, NULL, + RTE_RIB_GET_NXT_COVER); + if ((tmp == NULL) && + (dp->rsvd_tbl8s >= dp->number_tbl8s)) + return -ENOSPC; + + } + node = rte_rib_insert(rib, ip, depth); + if (node == NULL) + return -rte_errno; + rte_rib_set_nh(node, next_hop); + parent = rte_rib_lookup_parent(node); + if (parent != NULL) { + rte_rib_get_nh(parent, &par_nh); + if (par_nh == next_hop) + return 0; + } + ret = modify_fib(dp, rib, ip, depth, next_hop); + if (ret != 0) { + rte_rib_remove(rib, ip, depth); + return ret; + } + if ((depth > 24) && (tmp == NULL)) + dp->rsvd_tbl8s++; + return 0; + case RTE_FIB_DEL: + if (node == NULL) + return -ENOENT; + + parent = rte_rib_lookup_parent(node); + if (parent != NULL) { + rte_rib_get_nh(parent, &par_nh); + rte_rib_get_nh(node, &node_nh); + if (par_nh != node_nh) + ret = modify_fib(dp, rib, ip, depth, par_nh); + } else + ret = modify_fib(dp, rib, ip, depth, dp->def_nh); + if (ret == 0) { + rte_rib_remove(rib, ip, depth); + if (depth > 24) { + tmp = rte_rib_get_nxt(rib, ip, 24, NULL, + RTE_RIB_GET_NXT_COVER); + if (tmp == NULL) + dp->rsvd_tbl8s--; + } + } + return ret; + default: + break; + } + return -EINVAL; +} + +void * +dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *fib_conf) +{ + char mem_name[DIR24_8_NAMESIZE]; + struct dir24_8_tbl *dp; + uint64_t def_nh; + uint32_t num_tbl8; + enum rte_fib_dir24_8_nh_sz nh_sz; + + if ((name == NULL) || (fib_conf == NULL) || + (fib_conf->dir24_8.nh_sz < RTE_FIB_DIR24_8_1B) || + (fib_conf->dir24_8.nh_sz > RTE_FIB_DIR24_8_8B) || + (fib_conf->dir24_8.num_tbl8 > + get_max_nh(fib_conf->dir24_8.nh_sz)) || + (fib_conf->dir24_8.num_tbl8 == 0) || + (fib_conf->default_nh > + get_max_nh(fib_conf->dir24_8.nh_sz))) { + rte_errno = EINVAL; + return NULL; + } + + def_nh = fib_conf->default_nh; + nh_sz = fib_conf->dir24_8.nh_sz; + num_tbl8 = RTE_ALIGN_CEIL(fib_conf->dir24_8.num_tbl8, + BITMAP_SLAB_BIT_SIZE); + + snprintf(mem_name, sizeof(mem_name), "DP_%s", name); + dp = rte_zmalloc_socket(name, sizeof(struct dir24_8_tbl) + + DIR24_8_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE, + socket_id); + if (dp == NULL) { + rte_errno = ENOMEM; + return NULL; + } + + /* Init table with default value */ + write_to_fib(dp->tbl24, (def_nh << 1), nh_sz, 1 << 24); + + snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp); + uint64_t tbl8_sz = DIR24_8_TBL8_GRP_NUM_ENT * (1ULL << nh_sz) * + (num_tbl8 + 1); + dp->tbl8 = rte_zmalloc_socket(mem_name, tbl8_sz, + RTE_CACHE_LINE_SIZE, socket_id); + if (dp->tbl8 == NULL) { + rte_errno = ENOMEM; + rte_free(dp); + return NULL; + } + dp->def_nh = def_nh; + dp->nh_sz = nh_sz; + dp->number_tbl8s = num_tbl8; + + snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp); + dp->tbl8_idxes = rte_zmalloc_socket(mem_name, + RTE_ALIGN_CEIL(dp->number_tbl8s, 64) >> 3, + RTE_CACHE_LINE_SIZE, socket_id); + if (dp->tbl8_idxes == NULL) { + rte_errno = ENOMEM; + rte_free(dp->tbl8); + rte_free(dp); + return NULL; + } + + return dp; +} + +void +dir24_8_free(void *p) +{ + struct dir24_8_tbl *dp = (struct dir24_8_tbl *)p; + + rte_free(dp->tbl8_idxes); + rte_free(dp->tbl8); + rte_free(dp); +} diff --git a/lib/librte_fib/dir24_8.h b/lib/librte_fib/dir24_8.h new file mode 100644 index 0000000..34ddb91 --- /dev/null +++ b/lib/librte_fib/dir24_8.h @@ -0,0 +1,36 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _DIR24_8_H_ +#define _DIR24_8_H_ + +/** + * @file + * DIR24_8 algorithm + */ + +#ifdef __cplusplus +extern "C" { +#endif + +void * +dir24_8_create(const char *name, int socket_id, struct rte_fib_conf *conf); + +void +dir24_8_free(void *p); + +rte_fib_lookup_fn_t +dir24_8_get_lookup_fn(struct rte_fib_conf *conf); + +int +dir24_8_modify(struct rte_fib *fib, uint32_t ip, uint8_t depth, + uint64_t next_hop, int op); + +#ifdef __cplusplus +} +#endif + +#endif /* _DIR24_8_H_ */ + diff --git a/lib/librte_fib/meson.build b/lib/librte_fib/meson.build index 32dfdec..c63cac8 100644 --- a/lib/librte_fib/meson.build +++ b/lib/librte_fib/meson.build @@ -3,6 +3,6 @@ # Copyright(c) 2019 Intel Corporation allow_experimental_apis = true -sources = files('rte_fib.c', 'rte_fib6.c') +sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c') headers = files('rte_fib.h', 'rte_fib6.h') deps += ['rib'] diff --git a/lib/librte_fib/rte_fib.c b/lib/librte_fib/rte_fib.c index 4d8a771..e090808 100644 --- a/lib/librte_fib/rte_fib.c +++ b/lib/librte_fib/rte_fib.c @@ -17,6 +17,8 @@ #include #include +#include "dir24_8.h" + TAILQ_HEAD(rte_fib_list, rte_tailq_entry); static struct rte_tailq_elem rte_fib_tailq = { .name = "RTE_FIB", @@ -92,12 +94,22 @@ static int init_dataplane(struct rte_fib *fib, __rte_unused int socket_id, struct rte_fib_conf *conf) { + char dp_name[sizeof(void *)]; + + snprintf(dp_name, sizeof(dp_name), "%p", fib); switch (conf->type) { case RTE_FIB_DUMMY: fib->dp = fib; fib->lookup = dummy_lookup; fib->modify = dummy_modify; return 0; + case RTE_FIB_DIR24_8: + fib->dp = dir24_8_create(dp_name, socket_id, conf); + if (fib->dp == NULL) + return -rte_errno; + fib->lookup = dir24_8_get_lookup_fn(conf); + fib->modify = dir24_8_modify; + return 0; default: return -EINVAL; } @@ -258,6 +270,8 @@ free_dataplane(struct rte_fib *fib) switch (fib->type) { case RTE_FIB_DUMMY: return; + case RTE_FIB_DIR24_8: + dir24_8_free(fib->dp); default: return; } diff --git a/lib/librte_fib/rte_fib.h b/lib/librte_fib/rte_fib.h index 096cc92..d06c5ef 100644 --- a/lib/librte_fib/rte_fib.h +++ b/lib/librte_fib/rte_fib.h @@ -15,6 +15,7 @@ #include struct rte_fib; +struct rte_rib; /** Maximum depth value possible for IPv4 FIB. */ #define RTE_FIB_MAXDEPTH 32 @@ -22,6 +23,7 @@ struct rte_fib; /** Type of FIB struct */ enum rte_fib_type { RTE_FIB_DUMMY, /**< RIB tree based FIB */ + RTE_FIB_DIR24_8, /**< DIR24_8 based FIB */ RTE_FIB_TYPE_MAX }; @@ -37,12 +39,26 @@ enum rte_fib_op { RTE_FIB_DEL, }; +/** Size of nexthop (1 << nh_sz) bits for DIR24_8 based FIB */ +enum rte_fib_dir24_8_nh_sz { + RTE_FIB_DIR24_8_1B, + RTE_FIB_DIR24_8_2B, + RTE_FIB_DIR24_8_4B, + RTE_FIB_DIR24_8_8B +}; + /** FIB configuration structure */ struct rte_fib_conf { enum rte_fib_type type; /**< Type of FIB struct */ /** Default value returned on lookup if there is no route */ uint64_t default_nh; int max_routes; + union { + struct { + enum rte_fib_dir24_8_nh_sz nh_sz; + uint32_t num_tbl8; + } dir24_8; + }; }; /** @@ -143,7 +159,6 @@ __rte_experimental int rte_fib_lookup_bulk(struct rte_fib *fib, uint32_t *ips, uint64_t *next_hops, int n); - /** * Get pointer to the dataplane specific struct * From patchwork Fri Nov 1 15:21:41 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62323 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 767DAA00BE; Fri, 1 Nov 2019 16:23:34 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id A01981E886; Fri, 1 Nov 2019 16:22:09 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id D37EA1E86E for ; Fri, 1 Nov 2019 16:22:06 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:06 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979131" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:04 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:41 +0000 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 08/12] fib: add dataplane algorithm for ipv6 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" Add fib implementation for ipv6 using modified DIR24_8 algorithm. Implementation is similar to current LPM6 implementation but has few enhancements: faster control plabe operations more bits for userdata in table entries configurable userdata size Signed-off-by: Vladimir Medvedkin --- lib/librte_fib/Makefile | 2 +- lib/librte_fib/meson.build | 2 +- lib/librte_fib/rte_fib6.c | 14 + lib/librte_fib/rte_fib6.h | 14 + lib/librte_fib/trie.c | 760 +++++++++++++++++++++++++++++++++++++++++++++ lib/librte_fib/trie.h | 37 +++ 6 files changed, 827 insertions(+), 2 deletions(-) create mode 100644 lib/librte_fib/trie.c create mode 100644 lib/librte_fib/trie.h diff --git a/lib/librte_fib/Makefile b/lib/librte_fib/Makefile index 67fde9a..4abd80b 100644 --- a/lib/librte_fib/Makefile +++ b/lib/librte_fib/Makefile @@ -17,7 +17,7 @@ EXPORT_MAP := rte_fib_version.map LIBABIVER := 1 # all source are stored in SRCS-y -SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) := rte_fib.c rte_fib6.c dir24_8.c trie.c # install this header file SYMLINK-$(CONFIG_RTE_LIBRTE_FIB)-include := rte_fib.h rte_fib6.h diff --git a/lib/librte_fib/meson.build b/lib/librte_fib/meson.build index c63cac8..e2c6f44 100644 --- a/lib/librte_fib/meson.build +++ b/lib/librte_fib/meson.build @@ -3,6 +3,6 @@ # Copyright(c) 2019 Intel Corporation allow_experimental_apis = true -sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c') +sources = files('rte_fib.c', 'rte_fib6.c', 'dir24_8.c', 'trie.c') headers = files('rte_fib.h', 'rte_fib6.h') deps += ['rib'] diff --git a/lib/librte_fib/rte_fib6.c b/lib/librte_fib/rte_fib6.c index 9f00a80..354227d 100644 --- a/lib/librte_fib/rte_fib6.c +++ b/lib/librte_fib/rte_fib6.c @@ -17,6 +17,8 @@ #include #include +#include "trie.h" + TAILQ_HEAD(rte_fib6_list, rte_tailq_entry); static struct rte_tailq_elem rte_fib6_tailq = { .name = "RTE_FIB6", @@ -92,12 +94,22 @@ static int init_dataplane(struct rte_fib6 *fib, __rte_unused int socket_id, struct rte_fib6_conf *conf) { + char dp_name[sizeof(void *)]; + + snprintf(dp_name, sizeof(dp_name), "%p", fib); switch (conf->type) { case RTE_FIB6_DUMMY: fib->dp = fib; fib->lookup = dummy_lookup; fib->modify = dummy_modify; return 0; + case RTE_FIB6_TRIE: + fib->dp = trie_create(dp_name, socket_id, conf); + if (fib->dp == NULL) + return -rte_errno; + fib->lookup = rte_trie_get_lookup_fn(conf); + fib->modify = trie_modify; + return 0; default: return -EINVAL; } @@ -260,6 +272,8 @@ free_dataplane(struct rte_fib6 *fib) switch (fib->type) { case RTE_FIB6_DUMMY: return; + case RTE_FIB6_TRIE: + trie_free(fib->dp); default: return; } diff --git a/lib/librte_fib/rte_fib6.h b/lib/librte_fib/rte_fib6.h index 3322123..4268704 100644 --- a/lib/librte_fib/rte_fib6.h +++ b/lib/librte_fib/rte_fib6.h @@ -19,10 +19,12 @@ #define RTE_FIB6_MAXDEPTH 128 struct rte_fib6; +struct rte_rib6; /** Type of FIB struct */ enum rte_fib6_type { RTE_FIB6_DUMMY, /**< RIB6 tree based FIB */ + RTE_FIB6_TRIE, /**< TRIE based fib */ RTE_FIB6_TYPE_MAX }; @@ -40,12 +42,24 @@ enum rte_fib6_op { RTE_FIB6_DEL, }; +enum rte_fib_trie_nh_sz { + RTE_FIB6_TRIE_2B = 1, + RTE_FIB6_TRIE_4B, + RTE_FIB6_TRIE_8B +}; + /** FIB configuration structure */ struct rte_fib6_conf { enum rte_fib6_type type; /**< Type of FIB struct */ /** Default value returned on lookup if there is no route */ uint64_t default_nh; int max_routes; + union { + struct { + enum rte_fib_trie_nh_sz nh_sz; + uint32_t num_tbl8; + } trie; + }; }; /** diff --git a/lib/librte_fib/trie.c b/lib/librte_fib/trie.c new file mode 100644 index 0000000..198e815 --- /dev/null +++ b/lib/librte_fib/trie.c @@ -0,0 +1,760 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include + +#include +#include +#include "trie.h" + +/* @internal Total number of tbl24 entries. */ +#define TRIE_TBL24_NUM_ENT (1 << 24) + +/* Maximum depth value possible for IPv6 LPM. */ +#define TRIE_MAX_DEPTH 128 + +/* @internal Number of entries in a tbl8 group. */ +#define TRIE_TBL8_GRP_NUM_ENT 256ULL + +/* @internal Total number of tbl8 groups in the tbl8. */ +#define TRIE_TBL8_NUM_GROUPS 65536 + +/* @internal bitmask with valid and valid_group fields set */ +#define TRIE_EXT_ENT 1 + +#define TRIE_NAMESIZE 64 + +#define BITMAP_SLAB_BIT_SIZE_LOG2 6 +#define BITMAP_SLAB_BIT_SIZE (1ULL << BITMAP_SLAB_BIT_SIZE_LOG2) +#define BITMAP_SLAB_BITMASK (BITMAP_SLAB_BIT_SIZE - 1) + +struct rte_trie_tbl { + uint32_t number_tbl8s; /**< Total number of tbl8s */ + uint32_t rsvd_tbl8s; /**< Number of reserved tbl8s */ + uint32_t cur_tbl8s; /**< Current cumber of tbl8s */ + uint64_t def_nh; /**< Default next hop */ + enum rte_fib_trie_nh_sz nh_sz; /**< Size of nexthop entry */ + uint64_t *tbl8; /**< tbl8 table. */ + uint32_t *tbl8_pool; /**< bitmap containing free tbl8 idxes*/ + uint32_t tbl8_pool_pos; + /* tbl24 table. */ + __extension__ uint64_t tbl24[0] __rte_cache_aligned; +}; + +enum edge { + LEDGE, + REDGE +}; + +enum lookup_type { + MACRO, + INLINE, + UNI +}; +static enum lookup_type test_lookup = MACRO; + +static inline uint32_t +get_tbl24_idx(const uint8_t *ip) +{ + return ip[0] << 16|ip[1] << 8|ip[2]; +} + +static inline void * +get_tbl24_p(struct rte_trie_tbl *dp, const uint8_t *ip, uint8_t nh_sz) +{ + uint32_t tbl24_idx; + + tbl24_idx = get_tbl24_idx(ip); + return (void *)&((uint8_t *)dp->tbl24)[tbl24_idx << nh_sz]; +} + +static inline uint8_t +bits_in_nh(uint8_t nh_sz) +{ + return 8 * (1 << nh_sz); +} + +static inline uint64_t +get_max_nh(uint8_t nh_sz) +{ + return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); +} + +static inline uint64_t +lookup_msk(uint8_t nh_sz) +{ + return ((1ULL << ((1 << (nh_sz + 3)) - 1)) << 1) - 1; +} + +static inline uint8_t +get_psd_idx(uint32_t val, uint8_t nh_sz) +{ + return val & ((1 << (3 - nh_sz)) - 1); +} + +static inline uint32_t +get_tbl_pos(uint32_t val, uint8_t nh_sz) +{ + return val >> (3 - nh_sz); +} + +static inline uint64_t +get_tbl_val_by_idx(uint64_t *tbl, uint32_t idx, uint8_t nh_sz) +{ + return ((tbl[get_tbl_pos(idx, nh_sz)] >> (get_psd_idx(idx, nh_sz) * + bits_in_nh(nh_sz))) & lookup_msk(nh_sz)); +} + +static inline void * +get_tbl_p_by_idx(uint64_t *tbl, uint64_t idx, uint8_t nh_sz) +{ + return (uint8_t *)tbl + (idx << nh_sz); +} + +static inline int +is_entry_extended(uint64_t ent) +{ + return (ent & TRIE_EXT_ENT) == TRIE_EXT_ENT; +} + +#define LOOKUP_FUNC(suffix, type, nh_sz) \ +static void rte_trie_lookup_bulk_##suffix(void *p, \ + uint8_t ips[][RTE_FIB6_IPV6_ADDR_SIZE], \ + uint64_t *next_hops, const unsigned int n) \ +{ \ + struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p; \ + uint64_t tmp; \ + uint32_t i, j; \ + \ + for (i = 0; i < n; i++) { \ + tmp = ((type *)dp->tbl24)[get_tbl24_idx(&ips[i][0])]; \ + j = 3; \ + while (is_entry_extended(tmp)) { \ + tmp = ((type *)dp->tbl8)[ips[i][j++] + \ + ((tmp >> 1) * TRIE_TBL8_GRP_NUM_ENT)]; \ + } \ + next_hops[i] = tmp >> 1; \ + } \ +} +LOOKUP_FUNC(2b, uint16_t, 1) +LOOKUP_FUNC(4b, uint32_t, 2) +LOOKUP_FUNC(8b, uint64_t, 3) + +rte_fib6_lookup_fn_t +rte_trie_get_lookup_fn(struct rte_fib6_conf *conf) +{ + enum rte_fib_trie_nh_sz nh_sz = conf->trie.nh_sz; + + if (test_lookup == MACRO) { + switch (nh_sz) { + case RTE_FIB6_TRIE_2B: + return rte_trie_lookup_bulk_2b; + case RTE_FIB6_TRIE_4B: + return rte_trie_lookup_bulk_4b; + case RTE_FIB6_TRIE_8B: + return rte_trie_lookup_bulk_8b; + } + } + + return NULL; +} + +static void +write_to_dp(void *ptr, uint64_t val, enum rte_fib_trie_nh_sz size, int n) +{ + int i; + uint16_t *ptr16 = (uint16_t *)ptr; + uint32_t *ptr32 = (uint32_t *)ptr; + uint64_t *ptr64 = (uint64_t *)ptr; + + switch (size) { + case RTE_FIB6_TRIE_2B: + for (i = 0; i < n; i++) + ptr16[i] = (uint16_t)val; + break; + case RTE_FIB6_TRIE_4B: + for (i = 0; i < n; i++) + ptr32[i] = (uint32_t)val; + break; + case RTE_FIB6_TRIE_8B: + for (i = 0; i < n; i++) + ptr64[i] = (uint64_t)val; + break; + } +} + +static void +tbl8_pool_init(struct rte_trie_tbl *dp) +{ + uint32_t i; + + /* put entire range of indexes to the tbl8 pool */ + for (i = 0; i < dp->number_tbl8s; i++) + dp->tbl8_pool[i] = i; + + dp->tbl8_pool_pos = 0; +} + +/* + * Get an index of a free tbl8 from the pool + */ +static inline int32_t +tbl8_get(struct rte_trie_tbl *dp) +{ + if (dp->tbl8_pool_pos == dp->number_tbl8s) + /* no more free tbl8 */ + return -ENOSPC; + + /* next index */ + return dp->tbl8_pool[dp->tbl8_pool_pos++]; +} + +/* + * Put an index of a free tbl8 back to the pool + */ +static inline void +tbl8_put(struct rte_trie_tbl *dp, uint32_t tbl8_ind) +{ + dp->tbl8_pool[--dp->tbl8_pool_pos] = tbl8_ind; +} + +static int +tbl8_alloc(struct rte_trie_tbl *dp, uint64_t nh) +{ + int64_t tbl8_idx; + uint8_t *tbl8_ptr; + + tbl8_idx = tbl8_get(dp); + if (tbl8_idx < 0) + return tbl8_idx; + tbl8_ptr = (uint8_t *)dp->tbl8 + + ((tbl8_idx * TRIE_TBL8_GRP_NUM_ENT) << + dp->nh_sz); + /*Init tbl8 entries with nexthop from tbl24*/ + write_to_dp((void *)tbl8_ptr, nh, dp->nh_sz, + TRIE_TBL8_GRP_NUM_ENT); + return tbl8_idx; +} + +static void +tbl8_recycle(struct rte_trie_tbl *dp, void *par, uint64_t tbl8_idx) +{ + uint32_t i; + uint64_t nh; + uint16_t *ptr16; + uint32_t *ptr32; + uint64_t *ptr64; + + switch (dp->nh_sz) { + case RTE_FIB6_TRIE_2B: + ptr16 = &((uint16_t *)dp->tbl8)[tbl8_idx * + TRIE_TBL8_GRP_NUM_ENT]; + nh = *ptr16; + if (nh & TRIE_EXT_ENT) + return; + for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr16[i]) + return; + } + write_to_dp(par, nh, dp->nh_sz, 1); + for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++) + ptr16[i] = 0; + break; + case RTE_FIB6_TRIE_4B: + ptr32 = &((uint32_t *)dp->tbl8)[tbl8_idx * + TRIE_TBL8_GRP_NUM_ENT]; + nh = *ptr32; + if (nh & TRIE_EXT_ENT) + return; + for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr32[i]) + return; + } + write_to_dp(par, nh, dp->nh_sz, 1); + for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++) + ptr32[i] = 0; + break; + case RTE_FIB6_TRIE_8B: + ptr64 = &((uint64_t *)dp->tbl8)[tbl8_idx * + TRIE_TBL8_GRP_NUM_ENT]; + nh = *ptr64; + if (nh & TRIE_EXT_ENT) + return; + for (i = 1; i < TRIE_TBL8_GRP_NUM_ENT; i++) { + if (nh != ptr64[i]) + return; + } + write_to_dp(par, nh, dp->nh_sz, 1); + for (i = 0; i < TRIE_TBL8_GRP_NUM_ENT; i++) + ptr64[i] = 0; + break; + } + tbl8_put(dp, tbl8_idx); +} + +#define BYTE_SIZE 8 +static inline uint32_t +get_idx(const uint8_t *ip, uint32_t prev_idx, int bytes, int first_byte) +{ + int i; + uint32_t idx = 0; + uint8_t bitshift; + + for (i = first_byte; i < (first_byte + bytes); i++) { + bitshift = (int8_t)(((first_byte + bytes - 1) - i)*BYTE_SIZE); + idx |= ip[i] << bitshift; + } + return (prev_idx * 256) + idx; +} + +static inline uint64_t +get_val_by_p(void *p, uint8_t nh_sz) +{ + uint64_t val = 0; + + switch (nh_sz) { + case RTE_FIB6_TRIE_2B: + val = *(uint16_t *)p; + break; + case RTE_FIB6_TRIE_4B: + val = *(uint32_t *)p; + break; + case RTE_FIB6_TRIE_8B: + val = *(uint64_t *)p; + break; + } + return val; +} + +/* + * recursively recycle tbl8's + */ +static void +recycle_root_path(struct rte_trie_tbl *dp, const uint8_t *ip_part, + uint8_t common_tbl8, void *prev) +{ + void *p; + uint64_t val; + + val = get_val_by_p(prev, dp->nh_sz); + if (unlikely((val & TRIE_EXT_ENT) != TRIE_EXT_ENT)) + return; + + if (common_tbl8 != 0) { + p = get_tbl_p_by_idx(dp->tbl8, (val >> 1) * 256 + *ip_part, + dp->nh_sz); + recycle_root_path(dp, ip_part + 1, common_tbl8 - 1, p); + } + tbl8_recycle(dp, prev, val >> 1); +} + +static inline int +build_common_root(struct rte_trie_tbl *dp, const uint8_t *ip, + int common_bytes, void **tbl) +{ + void *tbl_ptr = NULL; + uint64_t *cur_tbl; + uint64_t val; + int i, j, idx, prev_idx = 0; + + cur_tbl = dp->tbl24; + for (i = 3, j = 0; i <= common_bytes; i++) { + idx = get_idx(ip, prev_idx, i - j, j); + val = get_tbl_val_by_idx(cur_tbl, idx, dp->nh_sz); + tbl_ptr = get_tbl_p_by_idx(cur_tbl, idx, dp->nh_sz); + if ((val & TRIE_EXT_ENT) != TRIE_EXT_ENT) { + idx = tbl8_alloc(dp, val); + if (unlikely(idx < 0)) + return idx; + write_to_dp(tbl_ptr, (idx << 1) | + TRIE_EXT_ENT, dp->nh_sz, 1); + prev_idx = idx; + } else + prev_idx = val >> 1; + + j = i; + cur_tbl = dp->tbl8; + } + *tbl = get_tbl_p_by_idx(cur_tbl, prev_idx * 256, dp->nh_sz); + return 0; +} + +static int +write_edge(struct rte_trie_tbl *dp, const uint8_t *ip_part, uint64_t next_hop, + int len, enum edge edge, void *ent) +{ + uint64_t val = next_hop << 1; + int tbl8_idx; + int ret = 0; + void *p; + + if (len != 0) { + val = get_val_by_p(ent, dp->nh_sz); + if ((val & TRIE_EXT_ENT) == TRIE_EXT_ENT) + tbl8_idx = val >> 1; + else { + tbl8_idx = tbl8_alloc(dp, val); + if (tbl8_idx < 0) + return tbl8_idx; + val = (tbl8_idx << 1)|TRIE_EXT_ENT; + } + p = get_tbl_p_by_idx(dp->tbl8, (tbl8_idx * 256) + *ip_part, + dp->nh_sz); + ret = write_edge(dp, ip_part + 1, next_hop, len - 1, edge, p); + if (ret < 0) + return ret; + if (edge == LEDGE) { + write_to_dp((uint8_t *)p + (1 << dp->nh_sz), + next_hop << 1, dp->nh_sz, UINT8_MAX - *ip_part); + } else { + write_to_dp(get_tbl_p_by_idx(dp->tbl8, tbl8_idx * 256, + dp->nh_sz), + next_hop << 1, dp->nh_sz, *ip_part); + } + tbl8_recycle(dp, &val, tbl8_idx); + } + + write_to_dp(ent, val, dp->nh_sz, 1); + return ret; +} + +#define IPV6_MAX_IDX (RTE_FIB6_IPV6_ADDR_SIZE - 1) +#define TBL24_BYTES 3 +#define TBL8_LEN (RTE_FIB6_IPV6_ADDR_SIZE - TBL24_BYTES) + +static int +install_to_dp(struct rte_trie_tbl *dp, const uint8_t *ledge, const uint8_t *r, + uint64_t next_hop) +{ + void *common_root_tbl; + void *ent; + int ret; + int i; + int common_bytes; + int llen, rlen; + uint8_t redge[16]; + + /* decrement redge by 1*/ + rte_rib6_copy_addr(redge, r); + for (i = 15; i >= 0; i--) { + redge[i]--; + if (redge[i] != 0xff) + break; + } + + for (common_bytes = 0; common_bytes < 15; common_bytes++) { + if (ledge[common_bytes] != redge[common_bytes]) + break; + } + + ret = build_common_root(dp, ledge, common_bytes, &common_root_tbl); + if (unlikely(ret != 0)) + return ret; + /*first uncommon tbl8 byte idx*/ + uint8_t first_tbl8_byte = RTE_MAX(common_bytes, TBL24_BYTES); + + for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) { + if (ledge[i] != 0) + break; + } + + llen = i - first_tbl8_byte + (common_bytes < 3); + + for (i = IPV6_MAX_IDX; i > first_tbl8_byte; i--) { + if (redge[i] != UINT8_MAX) + break; + } + rlen = i - first_tbl8_byte + (common_bytes < 3); + + /*first noncommon byte*/ + uint8_t first_byte_idx = (common_bytes < 3) ? 0 : common_bytes; + uint8_t first_idx_len = (common_bytes < 3) ? 3 : 1; + + uint32_t left_idx = get_idx(ledge, 0, first_idx_len, first_byte_idx); + uint32_t right_idx = get_idx(redge, 0, first_idx_len, first_byte_idx); + + ent = get_tbl_p_by_idx(common_root_tbl, left_idx, dp->nh_sz); + ret = write_edge(dp, &ledge[first_tbl8_byte + !(common_bytes < 3)], + next_hop, llen, LEDGE, ent); + if (ret < 0) + return ret; + + if (right_idx > left_idx + 1) { + ent = get_tbl_p_by_idx(common_root_tbl, left_idx + 1, + dp->nh_sz); + write_to_dp(ent, next_hop << 1, dp->nh_sz, + right_idx - (left_idx + 1)); + } + ent = get_tbl_p_by_idx(common_root_tbl, right_idx, dp->nh_sz); + ret = write_edge(dp, &redge[first_tbl8_byte + !((common_bytes < 3))], + next_hop, rlen, REDGE, ent); + if (ret < 0) + return ret; + + uint8_t common_tbl8 = (common_bytes < TBL24_BYTES) ? + 0 : common_bytes - (TBL24_BYTES - 1); + ent = get_tbl24_p(dp, ledge, dp->nh_sz); + recycle_root_path(dp, ledge + TBL24_BYTES, common_tbl8, ent); + return 0; +} + +static void +get_nxt_net(uint8_t *ip, uint8_t depth) +{ + int i; + uint8_t part_depth; + uint8_t prev_byte; + + for (i = 0, part_depth = depth; part_depth > 8; part_depth -= 8, i++) + ; + + prev_byte = ip[i]; + ip[i] += 1 << (8 - part_depth); + if (ip[i] < prev_byte) { + while (i > 0) { + ip[--i] += 1; + if (ip[i] != 0) + break; + } + } +} + +static int +modify_dp(struct rte_trie_tbl *dp, struct rte_rib6 *rib, + const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth, uint64_t next_hop) +{ + struct rte_rib6_node *tmp = NULL; + uint8_t ledge[RTE_FIB6_IPV6_ADDR_SIZE]; + uint8_t redge[RTE_FIB6_IPV6_ADDR_SIZE]; + int ret; + uint8_t tmp_depth; + + if (next_hop > get_max_nh(dp->nh_sz)) + return -EINVAL; + + rte_rib6_copy_addr(ledge, ip); + do { + tmp = rte_rib6_get_nxt(rib, ip, depth, tmp, + RTE_RIB6_GET_NXT_COVER); + if (tmp != NULL) { + rte_rib6_get_depth(tmp, &tmp_depth); + if (tmp_depth == depth) + continue; + rte_rib6_get_ip(tmp, redge); + if (rte_rib6_is_equal(ledge, redge)) { + get_nxt_net(ledge, tmp_depth); + continue; + } + ret = install_to_dp(dp, ledge, redge, + next_hop); + if (ret != 0) + return ret; + get_nxt_net(redge, tmp_depth); + rte_rib6_copy_addr(ledge, redge); + } else { + rte_rib6_copy_addr(redge, ip); + get_nxt_net(redge, depth); + if (rte_rib6_is_equal(ledge, redge)) + break; + ret = install_to_dp(dp, ledge, redge, + next_hop); + if (ret != 0) + return ret; + } + } while (tmp); + + return 0; +} + +int +trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth, uint64_t next_hop, int op) +{ + struct rte_trie_tbl *dp; + struct rte_rib6 *rib; + struct rte_rib6_node *tmp = NULL; + struct rte_rib6_node *node; + struct rte_rib6_node *parent; + uint8_t ip_masked[RTE_FIB6_IPV6_ADDR_SIZE]; + int i, ret = 0; + uint64_t par_nh, node_nh; + uint8_t tmp_depth, depth_diff = 0, parent_depth = 24; + + if ((fib == NULL) || (ip == NULL) || (depth > RTE_FIB6_MAXDEPTH)) + return -EINVAL; + + dp = rte_fib6_get_dp(fib); + RTE_ASSERT(dp); + rib = rte_fib6_get_rib(fib); + RTE_ASSERT(rib); + + for (i = 0; i < RTE_FIB6_IPV6_ADDR_SIZE; i++) + ip_masked[i] = ip[i] & get_msk_part(depth, i); + + if (depth > 24) { + tmp = rte_rib6_get_nxt(rib, ip_masked, + RTE_ALIGN_FLOOR(depth, 8), NULL, + RTE_RIB6_GET_NXT_COVER); + if (tmp == NULL) { + tmp = rte_rib6_lookup(rib, ip); + if (tmp != NULL) { + rte_rib6_get_depth(tmp, &tmp_depth); + parent_depth = RTE_MAX(tmp_depth, 24); + } + depth_diff = RTE_ALIGN_CEIL(depth, 8) - + RTE_ALIGN_CEIL(parent_depth, 8); + depth_diff = depth_diff >> 3; + } + } + node = rte_rib6_lookup_exact(rib, ip_masked, depth); + switch (op) { + case RTE_FIB6_ADD: + if (node != NULL) { + rte_rib6_get_nh(node, &node_nh); + if (node_nh == next_hop) + return 0; + ret = modify_dp(dp, rib, ip_masked, depth, next_hop); + if (ret == 0) + rte_rib6_set_nh(node, next_hop); + return 0; + } + + if ((depth > 24) && (dp->rsvd_tbl8s >= + dp->number_tbl8s - depth_diff)) + return -ENOSPC; + + node = rte_rib6_insert(rib, ip_masked, depth); + if (node == NULL) + return -rte_errno; + rte_rib6_set_nh(node, next_hop); + parent = rte_rib6_lookup_parent(node); + if (parent != NULL) { + rte_rib6_get_nh(parent, &par_nh); + if (par_nh == next_hop) + return 0; + } + ret = modify_dp(dp, rib, ip_masked, depth, next_hop); + if (ret != 0) { + rte_rib6_remove(rib, ip_masked, depth); + return ret; + } + + dp->rsvd_tbl8s += depth_diff; + return 0; + case RTE_FIB6_DEL: + if (node == NULL) + return -ENOENT; + + parent = rte_rib6_lookup_parent(node); + if (parent != NULL) { + rte_rib6_get_nh(parent, &par_nh); + rte_rib6_get_nh(node, &node_nh); + if (par_nh != node_nh) + ret = modify_dp(dp, rib, ip_masked, depth, + par_nh); + } else + ret = modify_dp(dp, rib, ip_masked, depth, dp->def_nh); + + if (ret != 0) + return ret; + rte_rib6_remove(rib, ip, depth); + + dp->rsvd_tbl8s -= depth_diff; + return 0; + default: + break; + } + return -EINVAL; +} + +void * +trie_create(const char *name, int socket_id, + struct rte_fib6_conf *conf) +{ + char mem_name[TRIE_NAMESIZE]; + struct rte_trie_tbl *dp = NULL; + uint64_t def_nh; + uint32_t num_tbl8; + enum rte_fib_trie_nh_sz nh_sz; + + if ((name == NULL) || (conf == NULL) || + (conf->trie.nh_sz < RTE_FIB6_TRIE_2B) || + (conf->trie.nh_sz > RTE_FIB6_TRIE_8B) || + (conf->trie.num_tbl8 > + get_max_nh(conf->trie.nh_sz)) || + (conf->trie.num_tbl8 == 0) || + (conf->default_nh > + get_max_nh(conf->trie.nh_sz))) { + + rte_errno = EINVAL; + return NULL; + } + + def_nh = conf->default_nh; + nh_sz = conf->trie.nh_sz; + num_tbl8 = conf->trie.num_tbl8; + + snprintf(mem_name, sizeof(mem_name), "DP_%s", name); + dp = rte_zmalloc_socket(name, sizeof(struct rte_trie_tbl) + + TRIE_TBL24_NUM_ENT * (1 << nh_sz), RTE_CACHE_LINE_SIZE, + socket_id); + if (dp == NULL) { + rte_errno = ENOMEM; + return dp; + } + + write_to_dp(&dp->tbl24, (def_nh << 1), nh_sz, 1 << 24); + + snprintf(mem_name, sizeof(mem_name), "TBL8_%p", dp); + dp->tbl8 = rte_zmalloc_socket(mem_name, TRIE_TBL8_GRP_NUM_ENT * + (1ll << nh_sz) * (num_tbl8 + 1), + RTE_CACHE_LINE_SIZE, socket_id); + if (dp->tbl8 == NULL) { + rte_errno = ENOMEM; + rte_free(dp); + return NULL; + } + dp->def_nh = def_nh; + dp->nh_sz = nh_sz; + dp->number_tbl8s = num_tbl8; + + snprintf(mem_name, sizeof(mem_name), "TBL8_idxes_%p", dp); + dp->tbl8_pool = rte_zmalloc_socket(mem_name, + sizeof(uint32_t) * dp->number_tbl8s, + RTE_CACHE_LINE_SIZE, socket_id); + if (dp->tbl8_pool == NULL) { + rte_errno = ENOMEM; + rte_free(dp->tbl8); + rte_free(dp); + return NULL; + } + + tbl8_pool_init(dp); + + return dp; +} + +void +trie_free(void *p) +{ + struct rte_trie_tbl *dp = (struct rte_trie_tbl *)p; + + rte_free(dp->tbl8_pool); + rte_free(dp->tbl8); + rte_free(dp); +} + diff --git a/lib/librte_fib/trie.h b/lib/librte_fib/trie.h new file mode 100644 index 0000000..7762fb9 --- /dev/null +++ b/lib/librte_fib/trie.h @@ -0,0 +1,37 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#ifndef _TRIE_H_ +#define _TRIE_H_ + +/** + * @file + * RTE IPv6 Longest Prefix Match (LPM) + */ + +#ifdef __cplusplus +extern "C" { +#endif + +void * +trie_create(const char *name, int socket_id, struct rte_fib6_conf *conf); + +void +trie_free(void *p); + +rte_fib6_lookup_fn_t +rte_trie_get_lookup_fn(struct rte_fib6_conf *fib_conf); + +int +trie_modify(struct rte_fib6 *fib, const uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t depth, uint64_t next_hop, int op); + + +#ifdef __cplusplus +} +#endif + +#endif /* _TRIE_H_ */ + From patchwork Fri Nov 1 15:21:42 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62324 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id C024FA00BE; Fri, 1 Nov 2019 16:23:46 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id F390E1E892; Fri, 1 Nov 2019 16:22:10 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 9575C1E86F for ; Fri, 1 Nov 2019 16:22:08 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:08 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979141" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:06 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:42 +0000 Message-Id: X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 09/12] test/fib: add FIB library autotests 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" Functional tests for the new FIB library. Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 1 + app/test/autotest_data.py | 12 ++ app/test/meson.build | 4 + app/test/test_fib.c | 414 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 431 insertions(+) create mode 100644 app/test/test_fib.c diff --git a/app/test/Makefile b/app/test/Makefile index 4638426..b67ca16 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -126,6 +126,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index f35b3cc..18a8595 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -123,6 +123,18 @@ "Report": None, }, { + "Name": "FIB autotest", + "Command": "fib_autotest", + "Func": default_autotest, + "Report": None, + }, + { + "Name": "FIB slow autotest", + "Command": "fib_slow_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Memcpy autotest", "Command": "memcpy_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index 49c1de0..c5d62de 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -47,6 +47,7 @@ test_sources = files('commands.c', 'test_eventdev.c', 'test_external_mem.c', 'test_fbarray.c', + 'test_fib.c', 'test_func_reentrancy.c', 'test_flow_classify.c', 'test_hash.c', @@ -137,6 +138,7 @@ test_deps = ['acl', 'efd', 'ethdev', 'eventdev', + 'fib', 'flow_classify', 'hash', 'ipsec', @@ -180,6 +182,7 @@ fast_test_names = [ 'eal_fs_autotest', 'errno_autotest', 'event_ring_autotest', + 'fib_autotest', 'func_reentrancy_autotest', 'flow_classify_autotest', 'hash_autotest', @@ -250,6 +253,7 @@ perf_test_names = [ 'reciprocal_division', 'reciprocal_division_perf', 'lpm_perf_autotest', + 'fib_slow_autotest', 'red_all', 'barrier_autotest', 'hash_multiwriter_autotest', diff --git a/app/test/test_fib.c b/app/test/test_fib.c new file mode 100644 index 0000000..ca80a5d --- /dev/null +++ b/app/test/test_fib.c @@ -0,0 +1,414 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include + +#include +#include +#include + +#include "test.h" + +typedef int32_t (*rte_fib_test)(void); + +static int32_t test_create_invalid(void); +static int32_t test_multiple_create(void); +static int32_t test_free_null(void); +static int32_t test_add_del_invalid(void); +static int32_t test_get_invalid(void); +static int32_t test_lookup(void); + +#define MAX_ROUTES (1 << 16) +#define MAX_TBL8 (1 << 15) + +/* + * Check that rte_fib_create fails gracefully for incorrect user input + * arguments + */ +int32_t +test_create_invalid(void) +{ + struct rte_fib *fib = NULL; + struct rte_fib_conf config; + + config.max_routes = MAX_ROUTES; + config.default_nh = 0; + config.type = RTE_FIB_DUMMY; + + /* rte_fib_create: fib name == NULL */ + fib = rte_fib_create(NULL, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_fib_create: config == NULL */ + fib = rte_fib_create(__func__, SOCKET_ID_ANY, NULL); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + /* socket_id < -1 is invalid */ + fib = rte_fib_create(__func__, -2, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_fib_create: max_routes = 0 */ + config.max_routes = 0; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + config.max_routes = MAX_ROUTES; + + config.type = RTE_FIB_TYPE_MAX; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + config.type = RTE_FIB_DIR24_8; + config.dir24_8.num_tbl8 = MAX_TBL8; + + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_8B + 1; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_8B; + + config.dir24_8.num_tbl8 = 0; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +/* + * Create fib table then delete fib table 10 times + * Use a slightly different rules size each time + */ +int32_t +test_multiple_create(void) +{ + struct rte_fib *fib = NULL; + struct rte_fib_conf config; + int32_t i; + + config.default_nh = 0; + config.type = RTE_FIB_DUMMY; + + for (i = 0; i < 100; i++) { + config.max_routes = MAX_ROUTES - i; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + rte_fib_free(fib); + } + /* Can not test free so return success */ + return TEST_SUCCESS; +} + +/* + * Call rte_fib_free for NULL pointer user input. Note: free has no return and + * therefore it is impossible to check for failure but this test is added to + * increase function coverage metrics and to validate that freeing null does + * not crash. + */ +int32_t +test_free_null(void) +{ + struct rte_fib *fib = NULL; + struct rte_fib_conf config; + + config.max_routes = MAX_ROUTES; + config.default_nh = 0; + config.type = RTE_FIB_DUMMY; + + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + + rte_fib_free(fib); + rte_fib_free(NULL); + return TEST_SUCCESS; +} + +/* + * Check that rte_fib_add and rte_fib_delete fails gracefully + * for incorrect user input arguments + */ +int32_t +test_add_del_invalid(void) +{ + struct rte_fib *fib = NULL; + struct rte_fib_conf config; + uint64_t nh = 100; + uint32_t ip = RTE_IPV4(0, 0, 0, 0); + int ret; + uint8_t depth = 24; + + config.max_routes = MAX_ROUTES; + config.default_nh = 0; + config.type = RTE_FIB_DUMMY; + + /* rte_fib_add: fib == NULL */ + ret = rte_fib_add(NULL, ip, depth, nh); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* rte_fib_delete: fib == NULL */ + ret = rte_fib_delete(NULL, ip, depth); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /*Create valid fib to use in rest of test. */ + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + + /* rte_fib_add: depth > RTE_FIB_MAXDEPTH */ + ret = rte_fib_add(fib, ip, RTE_FIB_MAXDEPTH + 1, nh); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* rte_fib_delete: depth > RTE_FIB_MAXDEPTH */ + ret = rte_fib_delete(fib, ip, RTE_FIB_MAXDEPTH + 1); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + rte_fib_free(fib); + + return TEST_SUCCESS; +} + +/* + * Check that rte_fib_get_dp and rte_fib_get_rib fails gracefully + * for incorrect user input arguments + */ +int32_t +test_get_invalid(void) +{ + void *p; + + p = rte_fib_get_dp(NULL); + RTE_TEST_ASSERT(p == NULL, + "Call succeeded with invalid parameters\n"); + + p = rte_fib_get_rib(NULL); + RTE_TEST_ASSERT(p == NULL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +/* + * Add routes for one supernet with all possible depths and do lookup + * on each step + * After delete routes with doing lookup on each step + */ +static int +lookup_and_check_asc(struct rte_fib *fib, uint32_t ip_arr[RTE_FIB_MAXDEPTH], + uint32_t ip_missing, uint64_t def_nh, uint32_t n) +{ + uint64_t nh_arr[RTE_FIB_MAXDEPTH]; + int ret; + uint32_t i = 0; + + ret = rte_fib_lookup_bulk(fib, ip_arr, nh_arr, RTE_FIB_MAXDEPTH); + RTE_TEST_ASSERT(ret == 0, "Failed to lookup\n"); + + for (; i <= RTE_FIB_MAXDEPTH - n; i++) + RTE_TEST_ASSERT(nh_arr[i] == n, + "Failed to get proper nexthop\n"); + + for (; i < RTE_FIB_MAXDEPTH; i++) + RTE_TEST_ASSERT(nh_arr[i] == --n, + "Failed to get proper nexthop\n"); + + ret = rte_fib_lookup_bulk(fib, &ip_missing, nh_arr, 1); + RTE_TEST_ASSERT((ret == 0) && (nh_arr[0] == def_nh), + "Failed to get proper nexthop\n"); + + return TEST_SUCCESS; +} + +static int +lookup_and_check_desc(struct rte_fib *fib, uint32_t ip_arr[RTE_FIB_MAXDEPTH], + uint32_t ip_missing, uint64_t def_nh, uint32_t n) +{ + uint64_t nh_arr[RTE_FIB_MAXDEPTH]; + int ret; + uint32_t i = 0; + + ret = rte_fib_lookup_bulk(fib, ip_arr, nh_arr, RTE_FIB_MAXDEPTH); + RTE_TEST_ASSERT(ret == 0, "Failed to lookup\n"); + + for (; i < n; i++) + RTE_TEST_ASSERT(nh_arr[i] == RTE_FIB_MAXDEPTH - i, + "Failed to get proper nexthop\n"); + + for (; i < RTE_FIB_MAXDEPTH; i++) + RTE_TEST_ASSERT(nh_arr[i] == def_nh, + "Failed to get proper nexthop\n"); + + ret = rte_fib_lookup_bulk(fib, &ip_missing, nh_arr, 1); + RTE_TEST_ASSERT((ret == 0) && (nh_arr[0] == def_nh), + "Failed to get proper nexthop\n"); + + return TEST_SUCCESS; +} + +static int +check_fib(struct rte_fib *fib) +{ + uint64_t def_nh = 100; + uint32_t ip_arr[RTE_FIB_MAXDEPTH]; + uint32_t ip_add = RTE_IPV4(128, 0, 0, 0); + uint32_t i, ip_missing = RTE_IPV4(127, 255, 255, 255); + int ret; + + for (i = 0; i < RTE_FIB_MAXDEPTH; i++) + ip_arr[i] = ip_add + (1ULL << i) - 1; + + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, def_nh, 0); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + + for (i = 1; i <= RTE_FIB_MAXDEPTH; i++) { + ret = rte_fib_add(fib, ip_add, i, i); + RTE_TEST_ASSERT(ret == 0, "Failed to add a route\n"); + ret = lookup_and_check_asc(fib, ip_arr, ip_missing, + def_nh, i); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + } + + for (i = RTE_FIB_MAXDEPTH; i > 1; i--) { + ret = rte_fib_delete(fib, ip_add, i); + RTE_TEST_ASSERT(ret == 0, "Failed to delete a route\n"); + ret = lookup_and_check_asc(fib, ip_arr, ip_missing, + def_nh, i - 1); + + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + } + ret = rte_fib_delete(fib, ip_add, i); + RTE_TEST_ASSERT(ret == 0, "Failed to delete a route\n"); + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, def_nh, 0); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + + for (i = 0; i < RTE_FIB_MAXDEPTH; i++) { + ret = rte_fib_add(fib, ip_add, RTE_FIB_MAXDEPTH - i, + RTE_FIB_MAXDEPTH - i); + RTE_TEST_ASSERT(ret == 0, "Failed to add a route\n"); + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, + def_nh, i + 1); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + } + + for (i = 1; i <= RTE_FIB_MAXDEPTH; i++) { + ret = rte_fib_delete(fib, ip_add, i); + RTE_TEST_ASSERT(ret == 0, "Failed to delete a route\n"); + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, def_nh, + RTE_FIB_MAXDEPTH - i); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + } + + return TEST_SUCCESS; +} + +int32_t +test_lookup(void) +{ + struct rte_fib *fib = NULL; + struct rte_fib_conf config; + uint64_t def_nh = 100; + int ret; + + config.max_routes = MAX_ROUTES; + config.default_nh = def_nh; + config.type = RTE_FIB_DUMMY; + + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for DUMMY type\n"); + rte_fib_free(fib); + + config.type = RTE_FIB_DIR24_8; + + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_1B; + config.dir24_8.num_tbl8 = 127; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for DIR24_8_1B type\n"); + rte_fib_free(fib); + + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_2B; + config.dir24_8.num_tbl8 = MAX_TBL8 - 1; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for DIR24_8_2B type\n"); + rte_fib_free(fib); + + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B; + config.dir24_8.num_tbl8 = MAX_TBL8; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for DIR24_8_4B type\n"); + rte_fib_free(fib); + + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_8B; + config.dir24_8.num_tbl8 = MAX_TBL8; + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for DIR24_8_8B type\n"); + rte_fib_free(fib); + + return TEST_SUCCESS; +} + +static struct unit_test_suite fib_fast_tests = { + .suite_name = "fib autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_create_invalid), + TEST_CASE(test_free_null), + TEST_CASE(test_add_del_invalid), + TEST_CASE(test_get_invalid), + TEST_CASE(test_lookup), + TEST_CASES_END() + } +}; + +static struct unit_test_suite fib_slow_tests = { + .suite_name = "fib slow autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_multiple_create), + TEST_CASES_END() + } +}; + +/* + * Do all unit tests. + */ +static int +test_fib(void) +{ + return unit_test_suite_runner(&fib_fast_tests); +} + +static int +test_slow_fib(void) +{ + return unit_test_suite_runner(&fib_slow_tests); +} + +REGISTER_TEST_COMMAND(fib_autotest, test_fib); +REGISTER_TEST_COMMAND(fib_slow_autotest, test_slow_fib); From patchwork Fri Nov 1 15:21:43 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62325 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id C897AA00BE; Fri, 1 Nov 2019 16:24:01 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 0C99E1E8A1; Fri, 1 Nov 2019 16:22:13 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 855861E889 for ; Fri, 1 Nov 2019 16:22:10 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:10 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979156" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:08 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:43 +0000 Message-Id: <70d9095f404a00d74029fa1a6ac39cf71a06b7d7.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 10/12] test/fib: add ipv6 support for FIB autotests 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" Functional ipv6 tests for the FIB library. Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 1 + app/test/autotest_data.py | 12 ++ app/test/meson.build | 3 + app/test/test_fib6.c | 423 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 439 insertions(+) create mode 100644 app/test/test_fib6.c diff --git a/app/test/Makefile b/app/test/Makefile index b67ca16..c230dbf 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -127,6 +127,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_HASH) += test_hash_readwrite_lf.c SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index 18a8595..5c220db 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -135,6 +135,18 @@ "Report": None, }, { + "Name": "FIB6 autotest", + "Command": "fib6_autotest", + "Func": default_autotest, + "Report": None, + }, + { + "Name": "FIB6 slow autotest", + "Command": "fib6_slow_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Memcpy autotest", "Command": "memcpy_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index c5d62de..0b83ada 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -48,6 +48,7 @@ test_sources = files('commands.c', 'test_external_mem.c', 'test_fbarray.c', 'test_fib.c', + 'test_fib6.c', 'test_func_reentrancy.c', 'test_flow_classify.c', 'test_hash.c', @@ -183,6 +184,7 @@ fast_test_names = [ 'errno_autotest', 'event_ring_autotest', 'fib_autotest', + 'fib6_autotest', 'func_reentrancy_autotest', 'flow_classify_autotest', 'hash_autotest', @@ -263,6 +265,7 @@ perf_test_names = [ 'member_perf_autotest', 'efd_perf_autotest', 'lpm6_perf_autotest', + 'fib6_slow_autotest', 'rcu_qsbr_perf_autotest', 'red_perf', 'distributor_perf_autotest', diff --git a/app/test/test_fib6.c b/app/test/test_fib6.c new file mode 100644 index 0000000..af589fe --- /dev/null +++ b/app/test/test_fib6.c @@ -0,0 +1,423 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include + +#include +#include +#include +#include + +#include "test.h" + +typedef int32_t (*rte_fib6_test)(void); + +static int32_t test_create_invalid(void); +static int32_t test_multiple_create(void); +static int32_t test_free_null(void); +static int32_t test_add_del_invalid(void); +static int32_t test_get_invalid(void); +static int32_t test_lookup(void); + +#define MAX_ROUTES (1 << 16) +/** Maximum number of tbl8 for 2-byte entries */ +#define MAX_TBL8 (1 << 15) + +/* + * Check that rte_fib6_create fails gracefully for incorrect user input + * arguments + */ +int32_t +test_create_invalid(void) +{ + struct rte_fib6 *fib = NULL; + struct rte_fib6_conf config; + + config.max_routes = MAX_ROUTES; + config.default_nh = 0; + config.type = RTE_FIB6_DUMMY; + + /* rte_fib6_create: fib name == NULL */ + fib = rte_fib6_create(NULL, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_fib6_create: config == NULL */ + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, NULL); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + /* socket_id < -1 is invalid */ + fib = rte_fib6_create(__func__, -2, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + /* rte_fib6_create: max_routes = 0 */ + config.max_routes = 0; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + config.max_routes = MAX_ROUTES; + + config.type = RTE_FIB6_TYPE_MAX; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + config.type = RTE_FIB6_TRIE; + config.trie.num_tbl8 = MAX_TBL8; + + config.trie.nh_sz = RTE_FIB6_TRIE_8B + 1; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + config.trie.nh_sz = RTE_FIB6_TRIE_8B; + + config.trie.num_tbl8 = 0; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib == NULL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +/* + * Create fib table then delete fib table 10 times + * Use a slightly different rules size each time + */ +int32_t +test_multiple_create(void) +{ + struct rte_fib6 *fib = NULL; + struct rte_fib6_conf config; + int32_t i; + + config.default_nh = 0; + config.type = RTE_FIB6_DUMMY; + + for (i = 0; i < 100; i++) { + config.max_routes = MAX_ROUTES - i; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + rte_fib6_free(fib); + } + /* Can not test free so return success */ + return TEST_SUCCESS; +} + +/* + * Call rte_fib6_free for NULL pointer user input. Note: free has no return and + * therefore it is impossible to check for failure but this test is added to + * increase function coverage metrics and to validate that freeing null does + * not crash. + */ +int32_t +test_free_null(void) +{ + struct rte_fib6 *fib = NULL; + struct rte_fib6_conf config; + + config.max_routes = MAX_ROUTES; + config.default_nh = 0; + config.type = RTE_FIB6_DUMMY; + + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + + rte_fib6_free(fib); + rte_fib6_free(NULL); + + return TEST_SUCCESS; +} + +/* + * Check that rte_fib6_add and rte_fib6_delete fails gracefully + * for incorrect user input arguments + */ +int32_t +test_add_del_invalid(void) +{ + struct rte_fib6 *fib = NULL; + struct rte_fib6_conf config; + uint64_t nh = 100; + uint8_t ip[RTE_FIB6_IPV6_ADDR_SIZE] = {0}; + int ret; + uint8_t depth = 24; + + config.max_routes = MAX_ROUTES; + config.default_nh = 0; + config.type = RTE_FIB6_DUMMY; + + /* rte_fib6_add: fib == NULL */ + ret = rte_fib6_add(NULL, ip, depth, nh); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* rte_fib6_delete: fib == NULL */ + ret = rte_fib6_delete(NULL, ip, depth); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /*Create valid fib to use in rest of test. */ + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + + /* rte_fib6_add: depth > RTE_FIB6_MAXDEPTH */ + ret = rte_fib6_add(fib, ip, RTE_FIB6_MAXDEPTH + 1, nh); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + /* rte_fib6_delete: depth > RTE_FIB6_MAXDEPTH */ + ret = rte_fib6_delete(fib, ip, RTE_FIB6_MAXDEPTH + 1); + RTE_TEST_ASSERT(ret < 0, + "Call succeeded with invalid parameters\n"); + + rte_fib6_free(fib); + + return TEST_SUCCESS; +} + +/* + * Check that rte_fib6_get_dp and rte_fib6_get_rib fails gracefully + * for incorrect user input arguments + */ +int32_t +test_get_invalid(void) +{ + void *p; + + p = rte_fib6_get_dp(NULL); + RTE_TEST_ASSERT(p == NULL, + "Call succeeded with invalid parameters\n"); + + p = rte_fib6_get_rib(NULL); + RTE_TEST_ASSERT(p == NULL, + "Call succeeded with invalid parameters\n"); + + return TEST_SUCCESS; +} + +/* + * Add routes for one supernet with all possible depths and do lookup + * on each step + * After delete routes with doing lookup on each step + */ +static int +lookup_and_check_asc(struct rte_fib6 *fib, + uint8_t ip_arr[RTE_FIB6_MAXDEPTH][RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t ip_missing[][RTE_FIB6_IPV6_ADDR_SIZE], uint64_t def_nh, + uint32_t n) +{ + uint64_t nh_arr[RTE_FIB6_MAXDEPTH]; + int ret; + uint32_t i = 0; + + ret = rte_fib6_lookup_bulk(fib, ip_arr, nh_arr, RTE_FIB6_MAXDEPTH); + RTE_TEST_ASSERT(ret == 0, "Failed to lookup\n"); + + for (; i <= RTE_FIB6_MAXDEPTH - n; i++) + RTE_TEST_ASSERT(nh_arr[i] == n, + "Failed to get proper nexthop\n"); + + for (; i < RTE_FIB6_MAXDEPTH; i++) + RTE_TEST_ASSERT(nh_arr[i] == --n, + "Failed to get proper nexthop\n"); + + ret = rte_fib6_lookup_bulk(fib, ip_missing, nh_arr, 1); + RTE_TEST_ASSERT((ret == 0) && (nh_arr[0] == def_nh), + "Failed to get proper nexthop\n"); + + return TEST_SUCCESS; +} + +static int +lookup_and_check_desc(struct rte_fib6 *fib, + uint8_t ip_arr[RTE_FIB6_MAXDEPTH][RTE_FIB6_IPV6_ADDR_SIZE], + uint8_t ip_missing[][RTE_FIB6_IPV6_ADDR_SIZE], uint64_t def_nh, + uint32_t n) +{ + uint64_t nh_arr[RTE_FIB6_MAXDEPTH]; + int ret; + uint32_t i = 0; + + ret = rte_fib6_lookup_bulk(fib, ip_arr, nh_arr, RTE_FIB6_MAXDEPTH); + RTE_TEST_ASSERT(ret == 0, "Failed to lookup\n"); + + for (; i < n; i++) + RTE_TEST_ASSERT(nh_arr[i] == RTE_FIB6_MAXDEPTH - i, + "Failed to get proper nexthop\n"); + + for (; i < RTE_FIB6_MAXDEPTH; i++) + RTE_TEST_ASSERT(nh_arr[i] == def_nh, + "Failed to get proper nexthop\n"); + + ret = rte_fib6_lookup_bulk(fib, ip_missing, nh_arr, 1); + RTE_TEST_ASSERT((ret == 0) && (nh_arr[0] == def_nh), + "Failed to get proper nexthop\n"); + + return TEST_SUCCESS; +} + +static int +check_fib(struct rte_fib6 *fib) +{ + uint64_t def_nh = 100; + uint8_t ip_arr[RTE_FIB6_MAXDEPTH][RTE_FIB6_IPV6_ADDR_SIZE]; + uint8_t ip_add[RTE_FIB6_IPV6_ADDR_SIZE] = {0}; + uint8_t ip_missing[1][RTE_FIB6_IPV6_ADDR_SIZE] = { {255} }; + uint32_t i, j; + int ret; + + ip_add[0] = 128; + ip_missing[0][0] = 127; + for (i = 0; i < RTE_FIB6_MAXDEPTH; i++) { + for (j = 0; j < RTE_FIB6_IPV6_ADDR_SIZE; j++) { + ip_arr[i][j] = ip_add[j] | + ~get_msk_part(RTE_FIB6_MAXDEPTH - i, j); + } + } + + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, def_nh, 0); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, "Lookup and check fails\n"); + + for (i = 1; i <= RTE_FIB6_MAXDEPTH; i++) { + ret = rte_fib6_add(fib, ip_add, i, i); + RTE_TEST_ASSERT(ret == 0, "Failed to add a route\n"); + ret = lookup_and_check_asc(fib, ip_arr, ip_missing, def_nh, i); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Lookup and check fails\n"); + } + + for (i = RTE_FIB6_MAXDEPTH; i > 1; i--) { + ret = rte_fib6_delete(fib, ip_add, i); + RTE_TEST_ASSERT(ret == 0, "Failed to delete a route\n"); + ret = lookup_and_check_asc(fib, ip_arr, ip_missing, + def_nh, i - 1); + + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Lookup and check fails\n"); + } + ret = rte_fib6_delete(fib, ip_add, i); + RTE_TEST_ASSERT(ret == 0, "Failed to delete a route\n"); + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, def_nh, 0); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Lookup and check fails\n"); + + for (i = 0; i < RTE_FIB6_MAXDEPTH; i++) { + ret = rte_fib6_add(fib, ip_add, RTE_FIB6_MAXDEPTH - i, + RTE_FIB6_MAXDEPTH - i); + RTE_TEST_ASSERT(ret == 0, "Failed to add a route\n"); + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, + def_nh, i + 1); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Lookup and check fails\n"); + } + + for (i = 1; i <= RTE_FIB6_MAXDEPTH; i++) { + ret = rte_fib6_delete(fib, ip_add, i); + RTE_TEST_ASSERT(ret == 0, "Failed to delete a route\n"); + ret = lookup_and_check_desc(fib, ip_arr, ip_missing, def_nh, + RTE_FIB6_MAXDEPTH - i); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Lookup and check fails\n"); + } + + return TEST_SUCCESS; +} + +int32_t +test_lookup(void) +{ + struct rte_fib6 *fib = NULL; + struct rte_fib6_conf config; + uint64_t def_nh = 100; + int ret; + + config.max_routes = MAX_ROUTES; + config.default_nh = def_nh; + config.type = RTE_FIB6_DUMMY; + + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for DUMMY type\n"); + rte_fib6_free(fib); + + config.type = RTE_FIB6_TRIE; + + config.trie.nh_sz = RTE_FIB6_TRIE_2B; + config.trie.num_tbl8 = MAX_TBL8 - 1; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for TRIE_2B type\n"); + rte_fib6_free(fib); + + config.trie.nh_sz = RTE_FIB6_TRIE_4B; + config.trie.num_tbl8 = MAX_TBL8; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for TRIE_4B type\n"); + rte_fib6_free(fib); + + config.trie.nh_sz = RTE_FIB6_TRIE_8B; + config.trie.num_tbl8 = MAX_TBL8; + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &config); + RTE_TEST_ASSERT(fib != NULL, "Failed to create FIB\n"); + ret = check_fib(fib); + RTE_TEST_ASSERT(ret == TEST_SUCCESS, + "Check_fib fails for TRIE_8B type\n"); + rte_fib6_free(fib); + + return TEST_SUCCESS; +} + +static struct unit_test_suite fib6_fast_tests = { + .suite_name = "fib6 autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_create_invalid), + TEST_CASE(test_free_null), + TEST_CASE(test_add_del_invalid), + TEST_CASE(test_get_invalid), + TEST_CASE(test_lookup), + TEST_CASES_END() + } +}; + +static struct unit_test_suite fib6_slow_tests = { + .suite_name = "fib6 slow autotest", + .setup = NULL, + .teardown = NULL, + .unit_test_cases = { + TEST_CASE(test_multiple_create), + TEST_CASES_END() + } +}; + +/* + * Do all unit tests. + */ +static int +test_fib6(void) +{ + return unit_test_suite_runner(&fib6_fast_tests); +} + +static int +test_slow_fib6(void) +{ + return unit_test_suite_runner(&fib6_slow_tests); +} + +REGISTER_TEST_COMMAND(fib6_autotest, test_fib6); +REGISTER_TEST_COMMAND(fib6_slow_autotest, test_slow_fib6); From patchwork Fri Nov 1 15:21:44 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62326 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 810F9A00BE; Fri, 1 Nov 2019 16:24:14 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id 782391E8AB; Fri, 1 Nov 2019 16:22:15 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 6F14E1E548 for ; Fri, 1 Nov 2019 16:22:12 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:12 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979163" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:10 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:44 +0000 Message-Id: <998b84e14a43607bde8013ac88531d8bbce0e498.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 11/12] test/fib: add FIB library performance autotests 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" Performance tests for the new FIB library. Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 1 + app/test/autotest_data.py | 6 + app/test/meson.build | 2 + app/test/test_fib_perf.c | 411 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 420 insertions(+) create mode 100644 app/test/test_fib_perf.c diff --git a/app/test/Makefile b/app/test/Makefile index c230dbf..3a3f920 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -128,6 +128,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib.c SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib_perf.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index 5c220db..0783979 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -719,6 +719,12 @@ "Report": None, }, { + "Name": "FIB perf autotest", + "Command": "fib_perf_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Efd perf autotest", "Command": "efd_perf_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index 0b83ada..929883a 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -48,6 +48,7 @@ test_sources = files('commands.c', 'test_external_mem.c', 'test_fbarray.c', 'test_fib.c', + 'test_fib_perf.c', 'test_fib6.c', 'test_func_reentrancy.c', 'test_flow_classify.c', @@ -256,6 +257,7 @@ perf_test_names = [ 'reciprocal_division_perf', 'lpm_perf_autotest', 'fib_slow_autotest', + 'fib_perf_autotest', 'red_all', 'barrier_autotest', 'hash_multiwriter_autotest', diff --git a/app/test/test_fib_perf.c b/app/test/test_fib_perf.c new file mode 100644 index 0000000..573087c --- /dev/null +++ b/app/test/test_fib_perf.c @@ -0,0 +1,411 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2018 Vladimir Medvedkin + * Copyright(c) 2019 Intel Corporation + */ + +#include +#include +#include +#include + +#include +#include +#include +#include +#include + +#include "test.h" +#include "test_xmmt_ops.h" + +#define TEST_FIB_ASSERT(cond) do { \ + if (!(cond)) { \ + printf("Error at line %d:\n", __LINE__); \ + return -1; \ + } \ +} while (0) + +#define ITERATIONS (1 << 10) +#define BATCH_SIZE (1 << 12) +#define BULK_SIZE 32 + +#define MAX_RULE_NUM (1200000) + +struct route_rule { + uint32_t ip; + uint8_t depth; +}; + +struct route_rule large_route_table[MAX_RULE_NUM]; + +static uint32_t num_route_entries; +#define NUM_ROUTE_ENTRIES num_route_entries + +enum { + IP_CLASS_A, + IP_CLASS_B, + IP_CLASS_C +}; +#define RTE_FIB_MAX_DEPTH 32 +/* 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_FIB_MAX_DEPTH]; + uint32_t b[RTE_FIB_MAX_DEPTH]; + uint32_t c[RTE_FIB_MAX_DEPTH]; +}; + +/* All following numbers of each depth of each common IP class are just + * got from previous large constant table in app/test/test_lpm_routes.h . + * In order to match similar performance, they keep same depth and IP + * address coverage as previous constant table. These numbers don't + * include any private local IP address. As previous large const rule + * table was just dumped from a real router, there are no any IP address + * in class C or D. + */ +static struct route_rule_count rule_count = { + .a = { /* IP class A in which the most significant bit is 0 */ + 0, /* depth = 1 */ + 0, /* depth = 2 */ + 1, /* depth = 3 */ + 0, /* depth = 4 */ + 2, /* depth = 5 */ + 1, /* depth = 6 */ + 3, /* depth = 7 */ + 185, /* depth = 8 */ + 26, /* depth = 9 */ + 16, /* depth = 10 */ + 39, /* depth = 11 */ + 144, /* depth = 12 */ + 233, /* depth = 13 */ + 528, /* depth = 14 */ + 866, /* depth = 15 */ + 3856, /* depth = 16 */ + 3268, /* depth = 17 */ + 5662, /* depth = 18 */ + 17301, /* depth = 19 */ + 22226, /* depth = 20 */ + 11147, /* depth = 21 */ + 16746, /* depth = 22 */ + 17120, /* depth = 23 */ + 77578, /* depth = 24 */ + 401, /* depth = 25 */ + 656, /* depth = 26 */ + 1107, /* depth = 27 */ + 1121, /* depth = 28 */ + 2316, /* depth = 29 */ + 717, /* depth = 30 */ + 10, /* depth = 31 */ + 66 /* depth = 32 */ + }, + .b = { /* IP class A in which the most 2 significant bits are 10 */ + 0, /* depth = 1 */ + 0, /* depth = 2 */ + 0, /* depth = 3 */ + 0, /* depth = 4 */ + 1, /* depth = 5 */ + 1, /* depth = 6 */ + 1, /* depth = 7 */ + 3, /* depth = 8 */ + 3, /* depth = 9 */ + 30, /* depth = 10 */ + 25, /* depth = 11 */ + 168, /* depth = 12 */ + 305, /* depth = 13 */ + 569, /* depth = 14 */ + 1129, /* depth = 15 */ + 50800, /* depth = 16 */ + 1645, /* depth = 17 */ + 1820, /* depth = 18 */ + 3506, /* depth = 19 */ + 3258, /* depth = 20 */ + 3424, /* depth = 21 */ + 4971, /* depth = 22 */ + 6885, /* depth = 23 */ + 39771, /* depth = 24 */ + 424, /* depth = 25 */ + 170, /* depth = 26 */ + 433, /* depth = 27 */ + 92, /* depth = 28 */ + 366, /* depth = 29 */ + 377, /* depth = 30 */ + 2, /* depth = 31 */ + 200 /* depth = 32 */ + }, + .c = { /* IP class A in which the most 3 significant bits are 110 */ + 0, /* depth = 1 */ + 0, /* depth = 2 */ + 0, /* depth = 3 */ + 0, /* depth = 4 */ + 0, /* depth = 5 */ + 0, /* depth = 6 */ + 0, /* depth = 7 */ + 12, /* depth = 8 */ + 8, /* depth = 9 */ + 9, /* depth = 10 */ + 33, /* depth = 11 */ + 69, /* depth = 12 */ + 237, /* depth = 13 */ + 1007, /* depth = 14 */ + 1717, /* depth = 15 */ + 14663, /* depth = 16 */ + 8070, /* depth = 17 */ + 16185, /* depth = 18 */ + 48261, /* depth = 19 */ + 36870, /* depth = 20 */ + 33960, /* depth = 21 */ + 50638, /* depth = 22 */ + 61422, /* depth = 23 */ + 466549, /* depth = 24 */ + 1829, /* depth = 25 */ + 4824, /* depth = 26 */ + 4927, /* depth = 27 */ + 5914, /* depth = 28 */ + 10254, /* depth = 29 */ + 4905, /* depth = 30 */ + 1, /* depth = 31 */ + 716 /* depth = 32 */ + } +}; + +static void generate_random_rule_prefix(uint32_t ip_class, uint8_t depth) +{ +/* IP address class A, the most significant bit is 0 */ +#define IP_HEAD_MASK_A 0x00000000 +#define IP_HEAD_BIT_NUM_A 1 + +/* IP address class B, the most significant 2 bits are 10 */ +#define IP_HEAD_MASK_B 0x80000000 +#define IP_HEAD_BIT_NUM_B 2 + +/* IP address class C, the most significant 3 bits are 110 */ +#define IP_HEAD_MASK_C 0xC0000000 +#define IP_HEAD_BIT_NUM_C 3 + + uint32_t class_depth; + uint32_t range; + uint32_t mask; + uint32_t step; + uint32_t start; + uint32_t fixed_bit_num; + uint32_t ip_head_mask; + uint32_t rule_num; + uint32_t k; + struct route_rule *ptr_rule; + + if (ip_class == IP_CLASS_A) { /* IP Address class A */ + fixed_bit_num = IP_HEAD_BIT_NUM_A; + ip_head_mask = IP_HEAD_MASK_A; + rule_num = rule_count.a[depth - 1]; + } else if (ip_class == IP_CLASS_B) { /* IP Address class B */ + fixed_bit_num = IP_HEAD_BIT_NUM_B; + ip_head_mask = IP_HEAD_MASK_B; + rule_num = rule_count.b[depth - 1]; + } else { /* IP Address class C */ + fixed_bit_num = IP_HEAD_BIT_NUM_C; + ip_head_mask = IP_HEAD_MASK_C; + rule_num = rule_count.c[depth - 1]; + } + + if (rule_num == 0) + return; + + /* the number of rest bits which don't include the most significant + * fixed bits for this IP address class + */ + class_depth = depth - fixed_bit_num; + + /* range is the maximum number of rules for this depth and + * this IP address class + */ + range = 1 << class_depth; + + /* only mask the most depth significant generated bits + * except fixed bits for IP address class + */ + mask = range - 1; + + /* Widen coverage of IP address in generated rules */ + if (range <= rule_num) + step = 1; + else + step = round((double)range / rule_num); + + /* Only generate rest bits except the most significant + * fixed bits for IP address class + */ + start = lrand48() & mask; + ptr_rule = &large_route_table[num_route_entries]; + for (k = 0; k < rule_num; k++) { + ptr_rule->ip = (start << (RTE_FIB_MAX_DEPTH - depth)) + | ip_head_mask; + ptr_rule->depth = depth; + ptr_rule++; + start = (start + step) & mask; + } + num_route_entries += rule_num; +} + +static void insert_rule_in_random_pos(uint32_t ip, uint8_t depth) +{ + uint32_t pos; + int try_count = 0; + struct route_rule tmp; + + do { + pos = lrand48(); + try_count++; + } while ((try_count < 10) && (pos > num_route_entries)); + + if ((pos > num_route_entries) || (pos >= MAX_RULE_NUM)) + pos = num_route_entries >> 1; + + tmp = large_route_table[pos]; + large_route_table[pos].ip = ip; + large_route_table[pos].depth = depth; + if (num_route_entries < MAX_RULE_NUM) + large_route_table[num_route_entries++] = tmp; +} + +static void generate_large_route_rule_table(void) +{ + uint32_t ip_class; + uint8_t depth; + + num_route_entries = 0; + memset(large_route_table, 0, sizeof(large_route_table)); + + for (ip_class = IP_CLASS_A; ip_class <= IP_CLASS_C; ip_class++) { + for (depth = 1; depth <= RTE_FIB_MAX_DEPTH; depth++) + generate_random_rule_prefix(ip_class, depth); + } + + /* Add following rules to keep same as previous large constant table, + * they are 4 rules with private local IP address and 1 all-zeros prefix + * with depth = 8. + */ + insert_rule_in_random_pos(RTE_IPV4(0, 0, 0, 0), 8); + insert_rule_in_random_pos(RTE_IPV4(10, 2, 23, 147), 32); + insert_rule_in_random_pos(RTE_IPV4(192, 168, 100, 10), 24); + insert_rule_in_random_pos(RTE_IPV4(192, 168, 25, 100), 24); + insert_rule_in_random_pos(RTE_IPV4(192, 168, 129, 124), 32); +} + +static void +print_route_distribution(const struct route_rule *table, uint32_t n) +{ + unsigned int i, j; + + printf("Route distribution per prefix width:\n"); + printf("DEPTH QUANTITY (PERCENT)\n"); + printf("---------------------------\n"); + + /* Count depths. */ + for (i = 1; i <= 32; i++) { + unsigned int depth_counter = 0; + double percent_hits; + + for (j = 0; j < n; j++) + if (table[j].depth == (uint8_t) i) + depth_counter++; + + percent_hits = ((double)depth_counter)/((double)n) * 100; + printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits); + } + printf("\n"); +} + +static int +test_fib_perf(void) +{ + struct rte_fib *fib = NULL; + struct rte_fib_conf config; + + config.max_routes = 2000000; + config.type = RTE_FIB_DIR24_8; + config.default_nh = 0; + config.dir24_8.nh_sz = RTE_FIB_DIR24_8_4B; + config.dir24_8.num_tbl8 = 65535; + uint64_t begin, total_time; + unsigned int i, j; + uint32_t next_hop_add = 0xAA; + int status = 0; + int64_t count = 0; + + rte_srand(rte_rdtsc()); + + generate_large_route_rule_table(); + + printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES); + + print_route_distribution(large_route_table, + (uint32_t) NUM_ROUTE_ENTRIES); + + fib = rte_fib_create(__func__, SOCKET_ID_ANY, &config); + TEST_FIB_ASSERT(fib != NULL); + + /* Measue add. */ + begin = rte_rdtsc(); + + for (i = 0; i < NUM_ROUTE_ENTRIES; i++) { + if (rte_fib_add(fib, large_route_table[i].ip, + large_route_table[i].depth, next_hop_add) == 0) + status++; + } + /* End Timer. */ + total_time = rte_rdtsc() - begin; + + printf("Unique added entries = %d\n", status); + + printf("Average FIB Add: %g cycles\n", + (double)total_time / NUM_ROUTE_ENTRIES); + + /* Measure bulk Lookup */ + total_time = 0; + count = 0; + for (i = 0; i < ITERATIONS; i++) { + static uint32_t ip_batch[BATCH_SIZE]; + uint64_t next_hops[BULK_SIZE]; + + /* Create array of random IP addresses */ + for (j = 0; j < BATCH_SIZE; j++) + ip_batch[j] = rte_rand(); + + /* Lookup per batch */ + begin = rte_rdtsc(); + for (j = 0; j < BATCH_SIZE; j += BULK_SIZE) { + uint32_t k; + rte_fib_lookup_bulk(fib, &ip_batch[j], next_hops, + BULK_SIZE); + for (k = 0; k < BULK_SIZE; k++) + if (unlikely(!(next_hops[k] != 0))) + count++; + } + + total_time += rte_rdtsc() - begin; + } + printf("BULK FIB Lookup: %.1f cycles (fails = %.1f%%)\n", + (double)total_time / ((double)ITERATIONS * BATCH_SIZE), + (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE)); + + /* Delete */ + status = 0; + begin = rte_rdtsc(); + for (i = 0; i < NUM_ROUTE_ENTRIES; i++) { + /* rte_lpm_delete(lpm, ip, depth) */ + status += rte_fib_delete(fib, large_route_table[i].ip, + large_route_table[i].depth); + } + + total_time += rte_rdtsc() - begin; + + printf("Average FIB Delete: %g cycles\n", + (double)total_time / NUM_ROUTE_ENTRIES); + + rte_fib_free(fib); + + return 0; +} + +REGISTER_TEST_COMMAND(fib_perf_autotest, test_fib_perf); From patchwork Fri Nov 1 15:21:45 2019 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Vladimir Medvedkin X-Patchwork-Id: 62327 X-Patchwork-Delegate: thomas@monjalon.net Return-Path: X-Original-To: patchwork@inbox.dpdk.org Delivered-To: patchwork@inbox.dpdk.org Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 9E669A00BE; Fri, 1 Nov 2019 16:24:31 +0100 (CET) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id A2A071E8B9; Fri, 1 Nov 2019 16:22:17 +0100 (CET) Received: from mga09.intel.com (mga09.intel.com [134.134.136.24]) by dpdk.org (Postfix) with ESMTP id 2B6DC1E548 for ; Fri, 1 Nov 2019 16:22:14 +0100 (CET) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from orsmga004.jf.intel.com ([10.7.209.38]) by orsmga102.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 01 Nov 2019 08:22:13 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.68,256,1569308400"; d="scan'208";a="351979171" Received: from silpixa00400072.ir.intel.com ([10.237.222.213]) by orsmga004.jf.intel.com with ESMTP; 01 Nov 2019 08:22:12 -0700 From: Vladimir Medvedkin To: dev@dpdk.org Cc: bruce.richardson@intel.com, konstantin.ananyev@intel.com, thomas@monjalon.net, aconole@redhat.com Date: Fri, 1 Nov 2019 15:21:45 +0000 Message-Id: <4e1409ab8f7331472d9107b87cc2a455692d0e43.1572621163.git.vladimir.medvedkin@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: References: In-Reply-To: References: Subject: [dpdk-dev] [PATCH v6 12/12] test/fib: add FIB library ipv6 performance autotests 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" Performance ipv6 tests for the FIB library. Signed-off-by: Vladimir Medvedkin --- app/test/Makefile | 1 + app/test/autotest_data.py | 6 ++ app/test/meson.build | 2 + app/test/test_fib6_perf.c | 157 ++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 166 insertions(+) create mode 100644 app/test/test_fib6_perf.c diff --git a/app/test/Makefile b/app/test/Makefile index 3a3f920..f792858 100644 --- a/app/test/Makefile +++ b/app/test/Makefile @@ -129,6 +129,7 @@ SRCS-$(CONFIG_RTE_LIBRTE_RIB) += test_rib6.c SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib.c SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6.c SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib_perf.c +SRCS-$(CONFIG_RTE_LIBRTE_FIB) += test_fib6_perf.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm.c SRCS-$(CONFIG_RTE_LIBRTE_LPM) += test_lpm_perf.c diff --git a/app/test/autotest_data.py b/app/test/autotest_data.py index 0783979..97e4423 100644 --- a/app/test/autotest_data.py +++ b/app/test/autotest_data.py @@ -725,6 +725,12 @@ "Report": None, }, { + "Name": "FIB6 perf autotest", + "Command": "fib6_perf_autotest", + "Func": default_autotest, + "Report": None, + }, + { "Name": "Efd perf autotest", "Command": "efd_perf_autotest", "Func": default_autotest, diff --git a/app/test/meson.build b/app/test/meson.build index 929883a..42664d8 100644 --- a/app/test/meson.build +++ b/app/test/meson.build @@ -50,6 +50,7 @@ test_sources = files('commands.c', 'test_fib.c', 'test_fib_perf.c', 'test_fib6.c', + 'test_fib6_perf.c', 'test_func_reentrancy.c', 'test_flow_classify.c', 'test_hash.c', @@ -268,6 +269,7 @@ perf_test_names = [ 'efd_perf_autotest', 'lpm6_perf_autotest', 'fib6_slow_autotest', + 'fib6_perf_autotest', 'rcu_qsbr_perf_autotest', 'red_perf', 'distributor_perf_autotest', diff --git a/app/test/test_fib6_perf.c b/app/test/test_fib6_perf.c new file mode 100644 index 0000000..56c799b --- /dev/null +++ b/app/test/test_fib6_perf.c @@ -0,0 +1,157 @@ +/* SPDX-License-Identifier: BSD-3-Clause + * Copyright(c) 2010-2014 Intel Corporation + */ + +#include +#include +#include +#include + +#include +#include +#include +#include + +#include "test.h" +#include "test_lpm6_data.h" + +#define TEST_FIB_ASSERT(cond) do { \ + if (!(cond)) { \ + printf("Error at line %d:\n", __LINE__); \ + return -1; \ + } \ +} while (0) + +#define ITERATIONS (1 << 10) +#define BATCH_SIZE 100000 +#define NUMBER_TBL8S (1 << 16) + +static void +print_route_distribution(const struct rules_tbl_entry *table, uint32_t n) +{ + unsigned int i, j; + + printf("Route distribution per prefix width:\n"); + printf("DEPTH QUANTITY (PERCENT)\n"); + printf("---------------------------\n"); + + /* Count depths. */ + for (i = 1; i <= 128; i++) { + unsigned int depth_counter = 0; + double percent_hits; + + for (j = 0; j < n; j++) + if (table[j].depth == (uint8_t) i) + depth_counter++; + + percent_hits = ((double)depth_counter)/((double)n) * 100; + printf("%.2u%15u (%.2f)\n", i, depth_counter, percent_hits); + } + printf("\n"); +} + +static inline uint8_t +bits_in_nh(uint8_t nh_sz) +{ + return 8 * (1 << nh_sz); +} + +static inline uint64_t +get_max_nh(uint8_t nh_sz) +{ + return ((1ULL << (bits_in_nh(nh_sz) - 1)) - 1); +} + +static int +test_fib6_perf(void) +{ + struct rte_fib6 *fib = NULL; + struct rte_fib6_conf conf; + uint64_t begin, total_time; + unsigned int i, j; + uint64_t next_hop_add; + int status = 0; + int64_t count = 0; + uint8_t ip_batch[NUM_IPS_ENTRIES][16]; + uint64_t next_hops[NUM_IPS_ENTRIES]; + + conf.type = RTE_FIB6_TRIE; + conf.default_nh = 0; + conf.max_routes = 1000000; + conf.trie.nh_sz = RTE_FIB6_TRIE_4B; + conf.trie.num_tbl8 = RTE_MIN(get_max_nh(conf.trie.nh_sz), 1000000U); + + rte_srand(rte_rdtsc()); + + printf("No. routes = %u\n", (unsigned int) NUM_ROUTE_ENTRIES); + + print_route_distribution(large_route_table, + (uint32_t)NUM_ROUTE_ENTRIES); + + /* Only generate IPv6 address of each item in large IPS table, + * here next_hop is not needed. + */ + generate_large_ips_table(0); + + fib = rte_fib6_create(__func__, SOCKET_ID_ANY, &conf); + TEST_FIB_ASSERT(fib != NULL); + + /* Measure add. */ + begin = rte_rdtsc(); + + for (i = 0; i < NUM_ROUTE_ENTRIES; i++) { + next_hop_add = (i & ((1 << 14) - 1)) + 1; + if (rte_fib6_add(fib, large_route_table[i].ip, + large_route_table[i].depth, next_hop_add) == 0) + status++; + } + /* End Timer. */ + total_time = rte_rdtsc() - begin; + + printf("Unique added entries = %d\n", status); + printf("Average FIB Add: %g cycles\n", + (double)total_time / NUM_ROUTE_ENTRIES); + + /* Measure bulk Lookup */ + total_time = 0; + count = 0; + + for (i = 0; i < NUM_IPS_ENTRIES; i++) + memcpy(ip_batch[i], large_ips_table[i].ip, 16); + + for (i = 0; i < ITERATIONS; i++) { + + /* Lookup per batch */ + begin = rte_rdtsc(); + rte_fib6_lookup_bulk(fib, ip_batch, next_hops, NUM_IPS_ENTRIES); + total_time += rte_rdtsc() - begin; + + for (j = 0; j < NUM_IPS_ENTRIES; j++) + if (next_hops[j] == 0) + count++; + } + printf("BULK FIB Lookup: %.1f cycles (fails = %.1f%%)\n", + (double)total_time / ((double)ITERATIONS * BATCH_SIZE), + (count * 100.0) / (double)(ITERATIONS * BATCH_SIZE)); + + /* Delete */ + status = 0; + begin = rte_rdtsc(); + + for (i = 0; i < NUM_ROUTE_ENTRIES; i++) { + /* rte_fib_delete(fib, ip, depth) */ + status += rte_fib6_delete(fib, large_route_table[i].ip, + large_route_table[i].depth); + } + + total_time = rte_rdtsc() - begin; + + printf("Average FIB Delete: %g cycles\n", + (double)total_time / NUM_ROUTE_ENTRIES); + + rte_fib6_free(fib); + + return 0; +} + +REGISTER_TEST_COMMAND(fib6_perf_autotest, test_fib6_perf);