Ping? > 在 2016年6月23日，下午4:05，HePeng <[email protected]> 写道： > > Hello，is there anyone who is reviewing this patch? >> 在 2016年6月17日，下午2:01，HePeng <[email protected]> 写道： >> >> Ping? >>> 在 2016年6月14日，上午9:30，HePeng <[email protected]> 写道： >>> >>> 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 >
_______________________________________________ lng-odp mailing list [email protected] https://lists.linaro.org/mailman/listinfo/lng-odp
