From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 -- 2.7.4