Yes, I'm seeing this on API-NEXT as well as master. On Wednesday, June 29, 2016, HePeng <[email protected]> wrote:
> Hi, do you guys use patch this using API-NEXT branch? > > > > 在 2016年6月30日，上午1:23，Bill Fischofer <[email protected] > <javascript:;>> 写道： > > > > I see the same behavior. git am reports the first patch is corrupt at > line > > 14, but patch can apply it. Not sure what is going on with that. > > > > The test runs fine, however this still has a number of checkpatch issues > > that need to be addressed: > > > > WARNING: please, no spaces at the start of a line > > #480: FILE: helper/iplookuptable.c:434: > > + return NULL;$ > > > > WARNING: braces {} are not necessary for single statement blocks > > #532: FILE: helper/iplookuptable.c:486: > > + for (i = 0; i < ENTRY_NUM_L1; i++) { > > + tbl->l1e[i].nexthop = ODP_BUFFER_INVALID; > > + } > > > > WARNING: please, no spaces at the start of a line > > #617: FILE: helper/iplookuptable.c:571: > > + return 0;$ > > > > WARNING: line over 80 characters > > #660: FILE: helper/iplookuptable.c:614: > > + odph_iplookup_table_impl *tbl, prefix_entry_t *entry, odp_buffer_t > *buff, > > > > WARNING: line over 80 characters > > #730: FILE: helper/iplookuptable.c:684: > > + impl, impl->trie, prefix->ip, prefix->cidr, nexthop); > > > > WARNING: line over 80 characters > > #792: FILE: helper/iplookuptable.c:746: > > + odph_iplookup_table_impl *tbl, prefix_entry_t *l1e, odp_buffer_t *buff, > > > > WARNING: line over 80 characters > > #872: FILE: helper/iplookuptable.c:826: > > + if (ne->child != 0 || ne->cidr != cidr || ne->nexthop != index) { > > > > WARNING: line over 80 characters > > #882: FILE: helper/iplookuptable.c:836: > > + odph_iplookup_table_impl *tbl, prefix_entry_t *e, odp_buffer_t *buff, > > > > WARNING: line over 80 characters > > #899: FILE: helper/iplookuptable.c:853: > > + tbl, ne, nbuff, ip, cidr - 8, level + 8, depth + 1); > > > > total: 0 errors, 9 warnings, 0 checks, 1007 lines checked > > > > NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL > > DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO > > > > 0001-helper-table-add-impl-of-ip-lookup-table.patch has style problems, > > please review. > > > > If any of these errors are false positives, please report > > them to the maintainer, see CHECKPATCH in MAINTAINERS. > > total: 0 errors, 0 warnings, 0 checks, 187 lines checked > > > > NOTE: Ignored message types: BIT_MACRO COMPARISON_TO_NULL > > DEPRECATED_VARIABLE NEW_TYPEDEFS SPLIT_STRING SSCANF_TO_KSTRTO > > > > 0002-helper-test-add-validation-test-of-ip-lookup-table.patch has no > > obvious style problems and is ready for submission. > > > > > > On Fri, Jun 17, 2016 at 2:13 AM, Maxim Uvarov <[email protected] > <javascript:;>> > > wrote: > > > >> Bill, > >> > >> I'm able to apply it with just: > >> git am -s -3 /tmp/1/*.eml > >> patch -p1 < /opt/Linaro/odp3.git/.git/rebase-apply/patch > >> git add -A > >> git am --continue > >> > >> Interesting that git am -3 can not resolve conflicts but patch -p1 works > >> fine. > >> > >> He, Bill is travelling and will be on conference so it will take some > time > >> for him to respond / review. > >> > >> Maxim. > >> > >> > >> On 06/17/16 09:01, HePeng wrote: > >> > >>> Ping? > >>> > >>>> 在 2016年6月14日，上午9:30，HePeng <[email protected] <javascript:;>> 写道： > >>>> > >>>> Hi, bill > >>>> this patch is based on the current API-NEXT … > >>>> > >>>> 在 2016年6月14日，上午6:24，Bill Fischofer <[email protected] > <javascript:;>> 写道： > >>>>> > >>>>> 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] > <javascript:;>> 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] <javascript:;>> > >>>>>> --- > >>>>>> 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] <javascript:;> > >>>>>> https://lists.linaro.org/mailman/listinfo/lng-odp > >>>>>> > >>>>>> _______________________________________________ > >>>>> lng-odp mailing list > >>>>> [email protected] <javascript:;> > >>>>> https://lists.linaro.org/mailman/listinfo/lng-odp > >>>>> > >>>> > >>> _______________________________________________ > >>> lng-odp mailing list > >>> [email protected] <javascript:;> > >>> https://lists.linaro.org/mailman/listinfo/lng-odp > >>> > >> > >> _______________________________________________ > >> lng-odp mailing list > >> [email protected] <javascript:;> > >> https://lists.linaro.org/mailman/listinfo/lng-odp > >> > > _______________________________________________ > > lng-odp mailing list > > [email protected] <javascript:;> > > https://lists.linaro.org/mailman/listinfo/lng-odp > > > _______________________________________________ lng-odp mailing list [email protected] https://lists.linaro.org/mailman/listinfo/lng-odp
