The functions of this IP lookup table are almost same with odph_table API. Compared with providing a new IP lookup table API, I think it’s better to use the existing odph_table API. So I didn’t put the header file into odp/helper/include/.
From: Bill Fischofer [mailto:bill.fischo...@linaro.org] Sent: Sunday, May 15, 2016 6:41 AM To: Ru Jia Cc: LNG ODP Mailman List Subject: Re: [lng-odp] [API-NEXT 1/2] helper: table: add impl of ip lookup table On Fri, May 13, 2016 at 12:47 AM, Ru Jia <ji...@ict.ac.cn <mailto:ji...@ict.ac.cn> > wrote: This is an implementation of the 16,8,8 ip lookup (longest prefix matching) algorithm. The key of the table is 32-bit IPv4 address. Signed-off-by: Ru Jia <ji...@ict.ac.cn <mailto:ji...@ict.ac.cn> > --- helper/Makefile.am | 2 + helper/iplookuptable.c | 974 ++++++++++++++++++++++++++++++++++++++++++++ helper/odph_iplookuptable.h | 58 +++ 3 files changed, 1034 insertions(+) create mode 100644 helper/iplookuptable.c create mode 100644 helper/odph_iplookuptable.h diff --git a/helper/Makefile.am b/helper/Makefile.am index aa58e8c..e629c14 100644 --- a/helper/Makefile.am +++ b/helper/Makefile.am @@ -27,6 +27,7 @@ noinst_HEADERS = \ $(srcdir)/odph_debug.h \ $(srcdir)/odph_hashtable.h \ $(srcdir)/odph_lineartable.h \ + $(srcdir)/odph_iplookuptable.h \ $(srcdir)/odph_list_internal.h __LIB__libodphelper_linux_la_SOURCES = \ @@ -35,6 +36,7 @@ __LIB__libodphelper_linux_la_SOURCES = \ chksum.c \ linux.c \ hashtable.c \ + iplookuptable.c \ lineartable.c lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la <http://libodphelper-linux.la> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c new file mode 100644 index 0000000..a0b7e6b --- /dev/null +++ b/helper/iplookuptable.c @@ -0,0 +1,974 @@ +/* Copyright (c) 2015, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#include <string.h> +#include <stdint.h> +#include <errno.h> +#include <stdio.h> + +#include "odph_iplookuptable.h" +#include "odph_list_internal.h" +#include "odph_debug.h" +#include <odp_api.h> + +/** @magic word, write to the first byte of the memory block + * to indicate this block is used by a ip lookup table + */ +#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC + +/* The length(bit) of the IPv4 address */ +#define IP_LENGTH 32 + +/* The number of L1 entries */ +#define ENTRY_NUM_L1 (1 << 16) +/* The size of one L2\L3 subtree */ +#define ENTRY_NUM_SUBTREE (1 << 8) + +#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x00000001) + +/** @internal entry struct + * Structure store an entry of the ip prefix table. + * Because of the leaf pushing, each entry of the table must have + * either a child entry, or a nexthop info. + * If child == 0 and index != ODP_BUFFER_INVALID, this entry has + * a nexthop info, index indicates the buffer that stores the + * nexthop value, and ptr points to the address of the buffer. + * If child == 1, this entry has a subtree, index indicates + * the buffer that stores the subtree, and ptr points to the + * address of the buffer. + */ +typedef struct { + union { + uint8_t u8; + struct { +#if ODP_BYTE_ORDER == ODP_BIG_ENDIAN + uint8_t child : 1; + uint8_t cidr : 7; +#else + uint8_t cidr : 7; + uint8_t child : 1; +#endif + }; + }; + odp_buffer_t index; + void *ptr; +} prefix_entry_t; + +/** @internal trie node struct + * In this IP lookup algorithm, we use a + * binary tire to detect the overlap prefix. + */ +typedef struct trie_node { + /* tree structure */ + struct trie_node *parent; + struct trie_node *left; + struct trie_node *right; + /* IP prefix length */ + uint8_t cidr; + /* Nexthop buffer index */ + odp_buffer_t nexthop; + /* Buffer that stores this node */ + odp_buffer_t buffer; +} trie_node_t; + +/** Number of L2\L3 entries(subtrees) per cache cube. */ +#define CACHE_NUM_SUBTREE (1 << 13) +/** Number of nexthop values per cache cube. */ +#define CACHE_NUM_NEXTHOP (1 << 20) +/** Number of trie nodes per cache cube. */ +#define CACHE_NUM_TRIE (1 << 20) + +/** @typedef cache_type_t + * Cache node type + */ +typedef enum { + CACHE_TYPE_SUBTREE = 0, + CACHE_TYPE_TRIE, + CACHE_TYPE_NEXTHOP +} cache_type_t; + +/** A IP lookup table structure. */ +typedef struct { + /**< for check */ + uint32_t magicword; + /** Name of the hash. */ + char name[ODPH_TABLE_NAME_LEN]; + /** Total L1 entries. */ + prefix_entry_t *l1e; + /** Root node of the binary trie */ + trie_node_t *trie; + /** Length of value. */ + uint32_t nexthop_len; + /** Queues of free slots (caches) + * There are three queues: + * - free_slots[CACHE_TYPE_SUBTREE] is used for L2 and + * L3 entries (subtrees). Each buffer stores an 8-bit + * subtree. + * - free_slots[CACHE_TYPE_TRIE] is used for the binary + * trie. Each buffer contains a trie node. + * - free_slots[CACHE_TYPE_NEXTHOP] is used for the + * nexthop information storage. + */ + odp_queue_t free_slots[3]; + /** The number of pool used by each queue. */ + uint32_t cache_count[3]; +} odph_iplookup_table_impl ODP_ALIGNED_CACHE; + +/*********************************************************** + ***************** Cache management ******************** + ***********************************************************/ + +/** Destroy all caches */ +static void +cache_destroy(odph_iplookup_table_impl *impl) +{ + odp_queue_t queue; + odp_event_t ev; + uint32_t i = 0, count = 0; + char pool_name[ODPH_TABLE_NAME_LEN + 8]; + + /* free all buffers in the queue */ + for (; i < 3; i++) { + queue = impl->free_slots[i]; + if (queue == ODP_QUEUE_INVALID) + continue; + + while ((ev = odp_queue_deq(queue)) + != ODP_EVENT_INVALID) { + odp_buffer_free(odp_buffer_from_event(ev)); + } + odp_queue_destroy(queue); + } + + /* destroy all cache pools */ + for (i = 0; i < 3; i++) { + for (count = 0; count < impl->cache_count[i]; count++) { + sprintf( + pool_name, "%s_%d_%d", + impl->name, i, count); + odp_pool_destroy(odp_pool_lookup(pool_name)); + } + } +} + +/** According to the type of cahce, set the value of + * a buffer to the initial value. + */ +static void +cache_init_buffer(odp_buffer_t buffer, cache_type_t type, uint32_t size) { + int i = 0; + void *addr = odp_buffer_addr(buffer); + + memset(addr, 0, size); + if (type == CACHE_TYPE_SUBTREE) { + prefix_entry_t *entry = (prefix_entry_t *)addr; + + for (i = 0; i < ENTRY_NUM_SUBTREE; i++, entry++) { + entry->cidr = 0; + entry->index = ODP_BUFFER_INVALID; + entry->ptr = NULL; + } + } else if (type == CACHE_TYPE_TRIE) { + trie_node_t *node = (trie_node_t *)addr; + + node->buffer = buffer; + node->nexthop = ODP_BUFFER_INVALID; + } +} + +/** Create a new buffer pool, and insert its buffer into the queue. */ +static int +cache_alloc_new_pool( + odph_iplookup_table_impl *tbl, cache_type_t type) +{ + odp_pool_t pool; + odp_pool_param_t param; + odp_queue_t queue = tbl->free_slots[type]; + + odp_buffer_t buffer; + char pool_name[ODPH_TABLE_NAME_LEN + 8]; + char queue_name[ODPH_TABLE_NAME_LEN + 10]; + uint32_t size = 0, num = 0; + + /* Create new pool (new free buffers). */ + param.type = ODP_POOL_BUFFER; + param.buf.align = ODP_CACHE_LINE_SIZE; + if (type == CACHE_TYPE_SUBTREE) { + num = CACHE_NUM_SUBTREE; + size = sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE; + } else if (type == CACHE_TYPE_TRIE) { + num = CACHE_NUM_TRIE; + size = sizeof(trie_node_t); + } else if (type == CACHE_TYPE_NEXTHOP) { + num = CACHE_NUM_NEXTHOP; + size = tbl->nexthop_len; + } else { + ODPH_DBG("wrong cache_type_t.\n"); + return -1; + } + param.buf.size = size; + param.buf.num = num; + + sprintf( + pool_name, "%s_%d_%d", + tbl->name, type, tbl->cache_count[type]); + pool = odp_pool_create(pool_name, ¶m); + if (pool == ODP_POOL_INVALID) { + ODPH_DBG("failed to create a new pool.\n"); + return -1; + } + + /* insert new free buffers into queue */ + while ((buffer = odp_buffer_alloc(pool)) + != ODP_BUFFER_INVALID) { + cache_init_buffer(buffer, type, size); + odp_queue_enq(queue, odp_buffer_to_event(buffer)); + } + + tbl->cache_count[type]++; + return 0; +} + +/** Get a new buffer from a cache list. If there is no + * available buffer, allocate a new pool. + */ +static odp_buffer_t +cache_get_buffer(odph_iplookup_table_impl *tbl, cache_type_t type) +{ + odp_buffer_t buffer = ODP_BUFFER_INVALID; + odp_queue_t queue = tbl->free_slots[type]; + uint32_t size = 0; + + /* get free buffer from queue */ + buffer = odp_buffer_from_event( + odp_queue_deq(queue)); + + /* If there is no free buffer available, allocate new pool */ + if (buffer == ODP_BUFFER_INVALID) { + cache_alloc_new_pool(tbl, type); + buffer = odp_buffer_from_event(odp_queue_deq(queue)); + } + + return buffer; +} + +/*********************************************************** + ****************** Binary trie ******************** + ***********************************************************/ + +/* Initialize the root node of the trie */ +static int +trie_init(odph_iplookup_table_impl *tbl) +{ + trie_node_t *root = NULL; + odp_buffer_t buffer = cache_get_buffer(tbl, CACHE_TYPE_TRIE); + + if (buffer != ODP_BUFFER_INVALID) { + root = (trie_node_t *)odp_buffer_addr(buffer); + root->cidr = 0; + tbl->trie = root; + return 0; + } + + return -1; +} + +/* Destroy the whole trie (recursively) */ +static void +trie_destroy(odph_iplookup_table_impl *tbl, trie_node_t *trie) +{ + if (trie->left != NULL) + trie_destroy(tbl, trie->left); + if (trie->right != NULL) + trie_destroy(tbl, trie->right); + + /* destroy this node */ + if (trie->nexthop != ODP_BUFFER_INVALID) { + odp_queue_enq( + tbl->free_slots[CACHE_TYPE_NEXTHOP], + odp_buffer_to_event(trie->nexthop)); + } + odp_queue_enq( + tbl->free_slots[CACHE_TYPE_TRIE], + odp_buffer_to_event(trie->buffer)); +} + +/* Insert a new prefix node into the trie + * If the node is already existed, update its nexthop info, + * Return 0 and set nexthop pointer to INVALID. + * If the node is not exitsed, create this target node and + * all nodes along the path from root to the target node. + * Then return 0 and set nexthop pointer points to the + * new buffer. + * Return -1 for error. + */ +static int +trie_insert_node( + odph_iplookup_table_impl *tbl, trie_node_t *root, + uint32_t ip, uint8_t cidr, void *value, + odp_buffer_t *nexthop) +{ + uint8_t level = 0, child; + odp_buffer_t buf; + trie_node_t *node = root, *prev = root; + void *val_buf = NULL; + + *nexthop = ODP_BUFFER_INVALID; + + /* create/update all nodes along the path + * from root to the new node. */ + for (level = 1; level <= cidr; level++) { + child = WHICH_CHILD(ip, level); + + node = child == 0 ? prev->left : prev->right; + /* If the child node doesn't exit, create it. */ + if (node == NULL) { + buf = cache_get_buffer(tbl, CACHE_TYPE_TRIE); + if (buf == ODP_BUFFER_INVALID) + return -1; + + node = (trie_node_t *)odp_buffer_addr(buf); + node->cidr = level; + node->parent = prev; + + if (child == 0) + prev->left = node; + else + prev->right = node; + } + prev = node; + } + + /* The final one is the target. If its nexthop buffer + * is invalid, create a new buffer. + */ + if (node->nexthop == ODP_BUFFER_INVALID) { + buf = cache_get_buffer(tbl, CACHE_TYPE_NEXTHOP); + if (buf == ODP_BUFFER_INVALID) + return -1; + val_buf = odp_buffer_addr(buf); + *nexthop = buf; + node->nexthop = buf; + } + /* copy the value into the nexthop buffer */ + memcpy(val_buf, value, tbl->nexthop_len); + return 0; +} + +/* Delete a node */ +static int +trie_delete_node( + odph_iplookup_table_impl *tbl, + trie_node_t *root, uint32_t ip, uint8_t cidr) +{ + if (root == NULL) + return -1; + + /* The default prefix (root node) cannot be deleted. */ + if (cidr == 0) + return -1; + + trie_node_t *node = root, *prev = NULL; + uint8_t level = 1, child = 0; + odp_buffer_t tmp; + + /* Find the target node. */ + for (level = 1; level <= cidr; level++) { + child = WHICH_CHILD(ip, level); + node = (child == 0) ? node->left : node->right; + if (node == NULL) { + ODPH_DBG("Trie node is not existed\n"); + return -1; + } + } + + /* free nexthop buffer */ + if (node->nexthop != ODP_BUFFER_INVALID) { + cache_init_buffer( + node->nexthop, CACHE_TYPE_NEXTHOP, + tbl->nexthop_len); + odp_queue_enq( + tbl->free_slots[CACHE_TYPE_NEXTHOP], + odp_buffer_to_event(node->nexthop)); + node->nexthop = ODP_BUFFER_INVALID; + } + + /* Delete all redundant nodes along the path. */ + for (level = cidr; level > 0; level--) { + if ( + node->left != NULL || node->right != NULL || + node->nexthop != ODP_BUFFER_INVALID) + break; + + child = WHICH_CHILD(ip, level); + prev = node->parent; + + /* free trie node */ + tmp = node->buffer; + cache_init_buffer( + tmp, CACHE_TYPE_TRIE, sizeof(trie_node_t)); + odp_queue_enq( + tbl->free_slots[CACHE_TYPE_TRIE], + odp_buffer_to_event(tmp)); + + if (child == 0) + prev->left = NULL; + else + prev->right = NULL; + node = prev; + } + return 0; +} + +/* Detect the longest overlapping prefix. */ +static int +trie_detect_overlap( + trie_node_t *trie, uint32_t ip, uint8_t cidr, + uint8_t leaf_push, uint8_t *over_cidr, + odp_buffer_t *over_nexthop) +{ + uint8_t child = 0; + uint32_t level, limit = cidr > leaf_push ? leaf_push + 1 : cidr; + trie_node_t *node = trie, *longest = trie; + + for (level = 1; level < limit; level++) { + child = WHICH_CHILD(ip, level); + node = (child == 0) ? node->left : node->right; + if (node->nexthop != ODP_BUFFER_INVALID) + longest = node; + } + + *over_cidr = longest->cidr; + *over_nexthop = longest->nexthop; + return 0; +} + +/*********************************************************** + *************** IP prefix lookup table **************** + ***********************************************************/ + +odph_table_t +odph_iplookup_table_lookup(const char *name) +{ + odph_iplookup_table_impl *tbl = NULL; + + if (name == NULL || strlen(name) >= ODPH_TABLE_NAME_LEN) + return NULL; + + tbl = (odph_iplookup_table_impl *)odp_shm_addr(odp_shm_lookup(name)); + + if ( + tbl != NULL && + tbl->magicword == ODPH_IP_LOOKUP_TABLE_MAGIC_WORD && + strcmp(tbl->name, name) == 0) + return (odph_table_t)tbl; +} + +odph_table_t +odph_iplookup_table_create( + const char *name, uint32_t ODP_IGNORED_1, + uint32_t ODP_IGNORED_2, uint32_t value_size) +{ + odph_iplookup_table_impl *tbl; + odp_shm_t shm_tbl; + odp_queue_t queue; + odp_queue_param_t qparam; + + unsigned i; + uint32_t impl_size, l1_size; + char queue_name[ODPH_TABLE_NAME_LEN + 2]; + + /* Check for valid parameters */ + if (strlen(name) == 0) { + ODPH_DBG("invalid parameters\n"); + return NULL; + } + + /* Guarantee there's no existing */ + tbl = (odph_iplookup_table_impl *)odph_iplookup_table_lookup(name); + if (tbl != NULL) { + ODPH_DBG("IP prefix table %s already exists\n", name); + return NULL; + } + + /* Calculate the sizes of different parts of IP prefix table */ + impl_size = sizeof(odph_iplookup_table_impl); + l1_size = sizeof(prefix_entry_t) * ENTRY_NUM_L1; + + shm_tbl = odp_shm_reserve( + name, impl_size + l1_size, + ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY); + + if (shm_tbl == ODP_SHM_INVALID) { + ODPH_DBG( + "shm allocation failed for odph_iplookup_table_impl %s\n", + name); + return NULL; + } + + tbl = (odph_iplookup_table_impl *)odp_shm_addr(shm_tbl); + memset(tbl, 0, impl_size + l1_size); + + /* header of this mem block is the table impl struct, + * then the l1 entries array. + */ + tbl->l1e = (prefix_entry_t *)((char *)tbl + impl_size); + for (i = 0; i < ENTRY_NUM_L1; i++) { + tbl->l1e[i].index = ODP_BUFFER_INVALID; + tbl->l1e[i].ptr = NULL; + } + + /* Setup table context. */ + snprintf(tbl->name, sizeof(tbl->name), "%s", name); + tbl->magicword = ODPH_IP_LOOKUP_TABLE_MAGIC_WORD; + tbl->nexthop_len = value_size; + + /* Initialize cache */ + for (i = 0; i < 3; i++) { + tbl->cache_count[i] = 0; + + odp_queue_param_init(&qparam); + qparam.type = ODP_QUEUE_TYPE_PLAIN; + sprintf(queue_name, "%s_%d", name, i); + queue = odp_queue_create(queue_name, &qparam); + if (queue == ODP_QUEUE_INVALID) { + ODPH_DBG("failed to create queue"); + cache_destroy(tbl); + return NULL; + } + tbl->free_slots[i] = queue; + cache_alloc_new_pool(tbl, i); + } + + /* Initialize tire */ + if (trie_init(tbl) < 0) { + odp_shm_free(shm_tbl); + return NULL; + } + + return (odph_table_t)tbl; +} + +int +odph_iplookup_table_destroy(odph_table_t tbl) +{ + int i, j; + odph_iplookup_table_impl *impl = NULL; + prefix_entry_t *subtree = NULL; + + if (tbl == NULL) + return -1; + + impl = (odph_iplookup_table_impl *)tbl; + + /* check magic word */ + if (impl->magicword != ODPH_IP_LOOKUP_TABLE_MAGIC_WORD) { + ODPH_DBG("wrong magicword for IP prefix table\n"); + return -1; + } + + /* destroy trie */ + trie_destroy(impl, impl->trie); + + /* free all L2 and L3 entries */ + for (i = 0; i < ENTRY_NUM_L1; i++) { + if ((impl->l1e[i]).child == 0) + continue; + + subtree = (prefix_entry_t *)odp_buffer_addr( + impl->l1e[i].index); + /* destroy all l3 subtrees of this l2 subtree */ + for (j = 0; j < ENTRY_NUM_SUBTREE; j++) { + if (subtree[j].child == 0) + continue; + odp_queue_enq( + impl->free_slots[CACHE_TYPE_TRIE], + odp_buffer_to_event(subtree[j].index)); + } + /* destroy this l2 subtree */ + odp_queue_enq( + impl->free_slots[CACHE_TYPE_TRIE], + odp_buffer_to_event(impl->l1e[i].index)); + } + + /* destroy all cache */ + cache_destroy(impl); + + /* free impl */ + odp_shm_free(odp_shm_lookup(impl->name)); +} + +/* Insert the prefix into level x + * Return: + * -1 error + * 0 the table is unmodified + * 1 the table is modified + */ +static int +prefix_insert_into_lx( + odph_iplookup_table_impl *tbl, prefix_entry_t *entry, + uint8_t cidr, odp_buffer_t nexthop, uint8_t level) +{ + uint8_t ret = 0; + uint32_t i = 0, limit = (1 << (level - cidr)); + prefix_entry_t *e = entry, *ne = NULL; + + for (i = 0; i < limit; i++, e++) { + if (e->child == 1) { + if (e->cidr > cidr) + continue; + + e->cidr = cidr; + if (e->index == ODP_BUFFER_INVALID) { + ODPH_DBG("Subtree is not existed.\n"); + return -1; + } + /* push to next level */ + ne = odp_buffer_addr(e->index); + ret = prefix_insert_into_lx( + tbl, ne, cidr, nexthop, cidr + 8); + } else { + if (e->cidr > cidr) + continue; + + e->child = 0; + e->cidr = cidr; + e->index = nexthop; + ret = 1; + } + } + return ret; +} + +static int +prefix_insert_iter( + odph_iplookup_table_impl *tbl, prefix_entry_t *entry, + uint32_t ip, uint8_t cidr, odp_buffer_t nexthop, + uint8_t level, uint8_t depth) +{ + uint8_t state = 0; + prefix_entry_t *ne = NULL; + int i = 0; + + /* If child subtree is existed, get it. */ + if (entry->child) { + ne = (prefix_entry_t *)odp_buffer_addr(entry->index); + } else { + /* If the child is not existed, create a new subtree. */ + odp_buffer_t buf, push = entry->index; + + buf = cache_get_buffer(tbl, CACHE_TYPE_SUBTREE); + if (buf == ODP_BUFFER_INVALID) { + ODPH_DBG("failed to get subtree buffer from cache.\n"); + return -1; + } + ne = (prefix_entry_t *)odp_buffer_addr(buf); + + /* initialize subtree */ + for (; i < ENTRY_NUM_SUBTREE; i++) + ne[i].index = ODP_BUFFER_INVALID; + + entry->child = 1; + entry->index = buf; + entry->ptr = ne; + + /* If this entry contains a nexthop and a small cidr, + * push it to the next level. + */ + if (entry->cidr > 0) { + state = prefix_insert_into_lx( + tbl, ne, entry->cidr, + push, entry->cidr + 8); + } + } + + ne += (ip >> 24); + if (cidr <= 8) { + state = prefix_insert_into_lx( + tbl, ne, cidr + depth * 8, nexthop, level); + } else { + state = prefix_insert_iter( + tbl, ne, ip << 8, cidr - 8, + nexthop, level + 8, depth + 1); + } + + return state; +} + +int +odph_iplookup_table_put_value(odph_table_t tbl, void *key, void *value) +{ + if ((tbl == NULL) || (key == NULL) || (value == NULL)) + return -1; + + odph_iplookup_table_impl *impl = (odph_iplookup_table_impl *)tbl; + odph_iplookup_prefix_t *prefix = (odph_iplookup_prefix_t *)key; + prefix_entry_t *l1e = NULL; + odp_buffer_t nexthop; + int ret = 0; + + if (prefix->cidr == 0) + return -1; + prefix->ip = prefix->ip & (0xffffffff << (IP_LENGTH - prefix->cidr)); + + /* insert into trie */ + ret = trie_insert_node( + impl, impl->trie, prefix->ip, prefix->cidr, + value, &nexthop); + + if (ret < 0) { + ODPH_DBG("failed to insert into trie\n"); + return -1; + } + + /* If the prefix is already existed, trie_insert_node has + * already updated the corresponding nexthop buffer. The + * insertion finished. + */ + if (nexthop == ODP_BUFFER_INVALID) + return 0; + + /* get L1 entry */ + l1e = &impl->l1e[prefix->ip >> 16]; + + if (prefix->cidr <= 16) { + ret = prefix_insert_into_lx( + impl, l1e, prefix->cidr, nexthop, 16); + } else { + ret = prefix_insert_iter( + impl, l1e, + ((prefix->ip) << 16), prefix->cidr - 16, + nexthop, 24, 2); + } + + return ret; +} + +int +odph_iplookup_table_get_value( + odph_table_t tbl, void *key, void *buffer, uint32_t buffer_size) +{ + if ((tbl == NULL) || (key == NULL) || (buffer == NULL)) + return -EINVAL; + + odph_iplookup_table_impl *impl = (odph_iplookup_table_impl *)tbl; + uint32_t ip = *((uint32_t *)key); + prefix_entry_t *entry = &impl->l1e[ip >> 16]; + + if (entry == NULL) { + ODPH_DBG("failed to get L1 entry.\n"); + return -1; + } + + ip <<= 16; + while (entry->child) { + entry = (prefix_entry_t *)entry->ptr; + entry += ip >> 24; + ip <<= 8; + } + + /* copy data */ + if (entry->index == ODP_BUFFER_INVALID) { + /* ONLY match the default prefix */ + memset(buffer, 0, impl->nexthop_len); + } else { + memcpy( + buffer, odp_buffer_addr(entry->index), + impl->nexthop_len); + } + + return 0; +} + +static int +prefix_delete_lx( + odph_iplookup_table_impl *tbl, prefix_entry_t *l1e, + uint8_t cidr, uint8_t over_cidr, odp_buffer_t over_nexthop, + uint8_t level) +{ + uint8_t ret, flag = 1; + prefix_entry_t *e = l1e; + uint32_t i = 0, limit = 1 << (level - cidr); + + for (i = 0; i < limit; i++, e++) { + if (e->child == 1) { + if (e->cidr > cidr) { + flag = 0; + continue; + } + + prefix_entry_t *ne = (prefix_entry_t *)odp_buffer_addr( + e->index); + + e->cidr = over_cidr; + ret = prefix_delete_lx( + tbl, ne, cidr, over_cidr, + over_nexthop, cidr + 8); + + /* If ret == 1, the next 2^8 entries equal to + * (over_cidr, over_nexthop). In this case, we + * should not push the (over_cidr, over_nexthop) + * to the next level. In fact, we should recycle + * the next 2^8 entries. + */ + if (ret) { + /* destroy subtree */ + cache_init_buffer( + e->index, CACHE_TYPE_SUBTREE, + sizeof(prefix_entry_t) + * ENTRY_NUM_SUBTREE); + odp_queue_enq( + tbl->free_slots[CACHE_TYPE_SUBTREE], + odp_buffer_to_event(e->index)); + e->child = 0; + e->index = over_nexthop; + } else { + flag = 0; + } + } else { + if (e->cidr > cidr) { + flag = 0; + continue; + } else { + e->cidr = over_cidr; + e->index = over_nexthop; + } + } + } + return flag; +} + +/* Check if the entry can be recycled. + * An entry can be recycled duo to two reasons: + * - all children of the entry are the same, + * - all children of the entry have a cidr smaller than the level + * bottom bound. + */ +static uint8_t +can_recycle(prefix_entry_t *e, uint32_t level) +{ + uint8_t recycle = 1; + int i = 1; + prefix_entry_t *ne = (prefix_entry_t *)odp_buffer_addr(e->index); + + if (ne->child) + return 0; + + uint8_t cidr = ne->cidr; + odp_buffer_t index = ne->index; + + if (cidr > level) + return 0; + + ne++; + for (; i < 256; i++, ne++) { + if (ne->child != 0 || ne->cidr != cidr || ne->index != index) { + recycle = 0; + break; + } + } + return recycle; +} + +static uint8_t +prefix_delete_iter( + odph_iplookup_table_impl *tbl, prefix_entry_t *e, + uint32_t ip, uint8_t cidr, uint8_t level, uint8_t depth) +{ + uint8_t ret = 0, over_cidr; + odp_buffer_t over_nexthop; + + trie_detect_overlap( + tbl->trie, ip, cidr + 8 * depth, level, + &over_cidr, &over_nexthop); + if (cidr > 8) { + prefix_entry_t *ne = + (prefix_entry_t *)odp_buffer_addr(e->index); + prefix_entry_t *org_ne = ne; + + ne += ((uint32_t)(ip << level) >> 24); + ret = prefix_delete_iter( + tbl, ne, ip, cidr - 8, level + 8, depth + 1); + + if (ret && can_recycle(e, level)) { + /* destroy subtree */ + cache_init_buffer( + e->index, CACHE_TYPE_SUBTREE, + sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE); + odp_queue_enq( + tbl->free_slots[CACHE_TYPE_SUBTREE], + odp_buffer_to_event(e->index)); + e->child = 0; + e->index = over_nexthop; + e->cidr = over_cidr; + return 1; + } + return 0; + } + + ret = prefix_delete_lx( + tbl, e, cidr + 8 * depth, + over_cidr, over_nexthop, level); + return ret; +} + +int +odph_iplookup_table_remove_value(odph_table_t tbl, void *key) +{ + if ((tbl == NULL) || (key == NULL)) + return -EINVAL; + + odph_iplookup_table_impl *impl = (odph_iplookup_table_impl *)tbl; + odph_iplookup_prefix_t *prefix = (odph_iplookup_prefix_t *)key; + uint32_t ip = prefix->ip; + uint8_t cidr = prefix->cidr; + + if (prefix->cidr < 0) + return -EINVAL; + + prefix_entry_t *entry = &impl->l1e[ip >> 16]; + uint8_t over_cidr, ret; + odp_buffer_t over_nexthop; + + trie_detect_overlap( + impl->trie, ip, cidr, 16, &over_cidr, &over_nexthop); + + if (cidr <= 16) { + prefix_delete_lx( + impl, entry, cidr, over_cidr, over_nexthop, 16); + } else { + prefix_entry_t *ne = (prefix_entry_t *)odp_buffer_addr( + entry->index); + prefix_entry_t *org_ne = ne; + + ne += ((uint32_t)(ip << 16) >> 24); + ret = prefix_delete_iter(impl, ne, ip, cidr - 16, 24, 2); + + if (ret && can_recycle(entry, 16)) { + /* destroy subtree */ + cache_init_buffer( + entry->index, CACHE_TYPE_SUBTREE, + sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE); + odp_queue_enq( + impl->free_slots[CACHE_TYPE_SUBTREE], + odp_buffer_to_event(entry->index)); + entry->child = 0; + entry->cidr = over_cidr; + entry->index = over_nexthop; + } + } + + return trie_delete_node(impl, impl->trie, ip, cidr); +} + +odph_table_ops_t odph_iplookup_table_ops = { + odph_iplookup_table_create, + odph_iplookup_table_lookup, + odph_iplookup_table_destroy, + odph_iplookup_table_put_value, + odph_iplookup_table_get_value, + odph_iplookup_table_remove_value +}; diff --git a/helper/odph_iplookuptable.h b/helper/odph_iplookuptable.h new file mode 100644 index 0000000..e6040ca --- /dev/null +++ b/helper/odph_iplookuptable.h @@ -0,0 +1,58 @@ +/* Copyright (c) 2015, Linaro Limited Should be a 2016 copyright These functions should also have doxygen documentation and be included in the helper guide. As such, it should appear in helper/include/odp/helper rather than helper. + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +/** + * @file + * + * ODP IP Lookup Table + * + * This is an implementation of the IP lookup table. The key of + * this table is IPv4 address (32 bits), and the value can be + * defined by user. This table uses the 16,8,8 ip lookup (longest + * prefix matching) algorithm. + */ + +#ifndef odph_iplookup_TABLE_H_ +#define odph_iplookup_TABLE_H_ + +#include <odp/helper/table.h> + +#ifdef __cplusplus +extern "C" { +#endif + +typedef struct { + uint32_t ip; + uint8_t cidr; +} odph_iplookup_prefix_t; + +odph_table_t odph_iplookup_table_create( + const char *name, + uint32_t ODP_IGNORED_1, + uint32_t ODP_IGNORED_2, + uint32_t value_size); + +odph_table_t odph_iplookup_table_lookup(const char *name); + +int odph_iplookup_table_destroy(odph_table_t table); + +int odph_iplookup_table_put_value( + odph_table_t table, void *key, void *value); + +int odph_iplookup_table_get_value( + odph_table_t table, void *key, + void *buffer, uint32_t buffer_size); + +int odph_iplookup_table_remove_value( + odph_table_t table, void *key); + +extern odph_table_ops_t odph_iplookup_table_ops; + +#ifdef __cplusplus +} +#endif + +#endif /* odph_iplookup_TABLE_H_ */ -- 1.9.1 _______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org <mailto:lng-odp@lists.linaro.org> https://lists.linaro.org/mailman/listinfo/lng-odp
_______________________________________________ lng-odp mailing list lng-odp@lists.linaro.org https://lists.linaro.org/mailman/listinfo/lng-odp
