From 40d41a8a7b342f2cb77ceb500dacea87421b9d49 Mon Sep 17 00:00:00 2001 From: Vladimir Medvedkin Date: Fri, 1 Nov 2019 15:21:39 +0000 Subject: [PATCH] fib: support IPv6 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 7362f68455..0bdf55bd38 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 6b7236014a..32dfdec1e7 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 0000000000..9f00a805a4 --- /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 0000000000..33221236bf --- /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 776195f0a3..9527417d22 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: *; }; -- 2.20.1