Hi, bill this patch is based on the current API-NEXT … > 在 2016年6月14日，上午6:24，Bill Fischofer <[email protected]> 写道： > > v4 of this patch still doesn't apply for me: > > bill@Ubuntu15:~/linaro/review$ git am --reject ~/Mail/Incoming/Ru/5 > Applying: helper: table: add impl of ip lookup table > fatal: corrupt patch at line 14 > Patch failed at 0001 helper: table: add impl of ip lookup table > The copy of the patch that failed is found in: .git/rebase-apply/patch > When you have resolved this problem, run "git am --continue". > If you prefer to skip this patch, run "git am --skip" instead. > To restore the original branch and stop patching, run "git am --abort". > > Looks like this still needs a rebase on to the current master? > > Thanks. > > Bill > > > > On Mon, Jun 13, 2016 at 3:57 AM, Ru Jia <[email protected]> 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 <[email protected]> >> --- >> helper/Makefile.am | 4 +- >> helper/iplookuptable.c | 934 >> ++++++++++++++++++++++++++++++++++++++++++++ >> helper/odph_iplookuptable.h | 58 +++ >> 3 files changed, 995 insertions(+), 1 deletion(-) >> 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..2e1d519 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 \ >> - lineartable.c >> + lineartable.c \ >> + iplookuptable.c >> >> lib_LTLIBRARIES = $(LIB)/libodphelper-linux.la >> diff --git a/helper/iplookuptable.c b/helper/iplookuptable.c >> new file mode 100644 >> index 0000000..8763abc >> --- /dev/null >> +++ b/helper/iplookuptable.c >> @@ -0,0 +1,934 @@ >> +/* Copyright (c) 2016, 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 >> + }; >> + }; >> + union { >> + odp_buffer_t nexthop; >> + void *ptr; >> + }; >> +} prefix_entry_t; >> + >> +#define ENTRY_SIZE (sizeof(prefix_entry_t) + sizeof(odp_buffer_t)) >> +#define ENTRY_BUFF_ARR(x) ((odp_buffer_t *)((char *)x \ >> + + sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE)) >> + >> +/** @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 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_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 entry stores an 8-bit >> + * subtree. >> + * - free_slots[CACHE_TYPE_TRIE] is used for the binary >> + * trie. Each entry contains a trie node. >> + */ >> + odp_queue_t free_slots[2]; >> + /** The number of pool used by each queue. */ >> + uint32_t cache_count[2]; >> +} 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 < 2; 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 < 2; 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->nexthop = ODP_BUFFER_INVALID; >> + } 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]; >> + 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 = ENTRY_SIZE * ENTRY_NUM_SUBTREE; >> + } else if (type == CACHE_TYPE_TRIE) { >> + num = CACHE_NUM_TRIE; >> + size = sizeof(trie_node_t); >> + } 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]; >> + >> + /* 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 */ >> + 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, odp_buffer_t nexthop) >> +{ >> + uint8_t level = 0, child; >> + odp_buffer_t buf; >> + trie_node_t *node = root, *prev = root; >> + >> + /* 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. */ >> + node->nexthop = nexthop; >> + 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; >> + } >> + } >> + >> + 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; >> + >> + return NULL; >> +} >> + >> +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 = ENTRY_SIZE * 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].nexthop = ODP_BUFFER_INVALID; >> + } >> + >> + /* 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 < 2; 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; >> + odp_buffer_t *buff1 = NULL, *buff2 = 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 */ >> + buff1 = ENTRY_BUFF_ARR(impl->l1e); >> + for (i = 0; i < ENTRY_NUM_L1; i++) { >> + if ((impl->l1e[i]).child == 0) >> + continue; >> + >> + subtree = (prefix_entry_t *)impl->l1e[i].ptr; >> + buff2 = ENTRY_BUFF_ARR(subtree); >> + /* 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(buff2[j])); >> + } >> + /* destroy this l2 subtree */ >> + odp_queue_enq( >> + impl->free_slots[CACHE_TYPE_TRIE], >> + odp_buffer_to_event(buff1[i])); >> + } >> + >> + /* destroy all cache */ >> + cache_destroy(impl); >> + >> + /* free impl */ >> + odp_shm_free(odp_shm_lookup(impl->name)); >> + >> + return 0; >> +} >> + >> +/* 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; >> + /* push to next level */ >> + ne = (prefix_entry_t *)e->ptr; >> + ret = prefix_insert_into_lx( >> + tbl, ne, cidr, nexthop, cidr + 8); >> + } else { >> + if (e->cidr > cidr) >> + continue; >> + >> + e->child = 0; >> + e->cidr = cidr; >> + e->nexthop = nexthop; >> + ret = 1; >> + } >> + } >> + return ret; >> +} >> + >> +static int >> +prefix_insert_iter( >> + odph_iplookup_table_impl *tbl, prefix_entry_t *entry, >> odp_buffer_t *buff, >> + 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; >> + odp_buffer_t *nbuff = NULL; >> + >> + /* If child subtree is existed, get it. */ >> + if (entry->child) { >> + ne = (prefix_entry_t *)entry->ptr; >> + nbuff = ENTRY_BUFF_ARR(ne); >> + } else { >> + /* If the child is not existed, create a new subtree. */ >> + odp_buffer_t buf, push = entry->nexthop; >> + >> + 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); >> + nbuff = ENTRY_BUFF_ARR(ne); >> + >> + entry->child = 1; >> + entry->ptr = ne; >> + *buff = buf; >> + >> + /* 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); >> + nbuff += (ip >> 24); >> + if (cidr <= 8) { >> + state = prefix_insert_into_lx( >> + tbl, ne, cidr + depth * 8, nexthop, level); >> + } else { >> + state = prefix_insert_iter( >> + tbl, ne, nbuff, 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 = *((odp_buffer_t *)value); >> + 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, nexthop); >> + >> + if (ret < 0) { >> + ODPH_DBG("failed to insert into trie\n"); >> + return -1; >> + } >> + >> + /* get L1 entry */ >> + l1e = &impl->l1e[prefix->ip >> 16]; >> + odp_buffer_t *buff = ENTRY_BUFF_ARR(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, buff, >> + ((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]; >> + odp_buffer_t *buff = (odp_buffer_t *)buffer; >> + >> + 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->nexthop == ODP_BUFFER_INVALID) { >> + /* ONLY match the default prefix */ >> + printf("only match the default prefix\n"); >> + *buff = ODP_BUFFER_INVALID; >> + } else { >> + *buff = entry->nexthop; >> + } >> + >> + return 0; >> +} >> + >> +static int >> +prefix_delete_lx( >> + odph_iplookup_table_impl *tbl, prefix_entry_t *l1e, >> odp_buffer_t *buff, >> + 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; >> + odp_buffer_t *b = buff; >> + uint32_t i = 0, limit = 1 << (level - cidr); >> + >> + for (i = 0; i < limit; i++, e++, b++) { >> + if (e->child == 1) { >> + if (e->cidr > cidr) { >> + flag = 0; >> + continue; >> + } >> + >> + prefix_entry_t *ne = (prefix_entry_t *)e->ptr; >> + odp_buffer_t *nbuff = ENTRY_BUFF_ARR(ne); >> + >> + e->cidr = over_cidr; >> + ret = prefix_delete_lx( >> + tbl, ne, nbuff, 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( >> + *b, CACHE_TYPE_SUBTREE, >> + ENTRY_SIZE * ENTRY_NUM_SUBTREE); >> + odp_queue_enq( >> + >> tbl->free_slots[CACHE_TYPE_SUBTREE], >> + odp_buffer_to_event(*b)); >> + e->child = 0; >> + e->nexthop = over_nexthop; >> + } else { >> + flag = 0; >> + } >> + } else { >> + if (e->cidr > cidr) { >> + flag = 0; >> + continue; >> + } else { >> + e->cidr = over_cidr; >> + e->nexthop = 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 *)e->ptr; >> + >> + if (ne->child) >> + return 0; >> + >> + uint8_t cidr = ne->cidr; >> + odp_buffer_t index = ne->nexthop; >> + >> + if (cidr > level) >> + return 0; >> + >> + ne++; >> + for (; i < 256; i++, ne++) { >> + if (ne->child != 0 || ne->cidr != cidr || ne->nexthop != >> index) { >> + recycle = 0; >> + break; >> + } >> + } >> + return recycle; >> +} >> + >> +static uint8_t >> +prefix_delete_iter( >> + odph_iplookup_table_impl *tbl, prefix_entry_t *e, >> odp_buffer_t *buff, >> + 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 *)e->ptr; >> + odp_buffer_t *nbuff = ENTRY_BUFF_ARR(ne); >> + >> + ne += ((uint32_t)(ip << level) >> 24); >> + nbuff += ((uint32_t)(ip << level) >> 24); >> + ret = prefix_delete_iter( >> + tbl, ne, nbuff, ip, cidr - 8, level + 8, >> depth + 1); >> + >> + if (ret && can_recycle(e, level)) { >> + /* destroy subtree */ >> + cache_init_buffer( >> + *buff, CACHE_TYPE_SUBTREE, >> + ENTRY_SIZE * ENTRY_NUM_SUBTREE); >> + odp_queue_enq( >> + tbl->free_slots[CACHE_TYPE_SUBTREE], >> + odp_buffer_to_event(*buff)); >> + e->child = 0; >> + e->nexthop = over_nexthop; >> + e->cidr = over_cidr; >> + return 1; >> + } >> + return 0; >> + } >> + >> + ret = prefix_delete_lx( >> + tbl, e, buff, 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]; >> + odp_buffer_t *buff = ENTRY_BUFF_ARR(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, buff, cidr, over_cidr, over_nexthop, >> 16); >> + } else { >> + prefix_entry_t *ne = (prefix_entry_t *)entry->ptr; >> + odp_buffer_t *nbuff = ENTRY_BUFF_ARR(ne); >> + >> + ne += ((uint32_t)(ip << 16) >> 24); >> + nbuff += ((uint32_t)(ip << 16) >> 24); >> + ret = prefix_delete_iter(impl, ne, nbuff, ip, cidr - 16, >> 24, 2); >> + >> + if (ret && can_recycle(entry, 16)) { >> + /* destroy subtree */ >> + cache_init_buffer( >> + *buff, CACHE_TYPE_SUBTREE, >> + sizeof(prefix_entry_t) * >> ENTRY_NUM_SUBTREE); >> + odp_queue_enq( >> + impl->free_slots[CACHE_TYPE_SUBTREE], >> + odp_buffer_to_event(*buff)); >> + entry->child = 0; >> + entry->cidr = over_cidr; >> + entry->nexthop = 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) 2016, Linaro Limited >> + * 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 >> [email protected] >> https://lists.linaro.org/mailman/listinfo/lng-odp >> > _______________________________________________ > lng-odp mailing list > [email protected] > https://lists.linaro.org/mailman/listinfo/lng-odp
_______________________________________________ lng-odp mailing list [email protected] https://lists.linaro.org/mailman/listinfo/lng-odp
