This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "".
The branch, api-next has been updated via c4aefb88d31452b3add8cf16f9eef152525c3e93 (commit) via 52dbfc9fc964ca292a777f11336854e88538f46d (commit) from 1a24b758857eef4caf2a1801851315b6c93edd76 (commit)
Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below.
- Log ----------------------------------------------------------------- commit c4aefb88d31452b3add8cf16f9eef152525c3e93 Author: Ru Jia jiaru@ict.ac.cn Date: Thu Jun 30 16:15:32 2016 +0800
helper: test: add validation test of ip lookup table
Signed-off-by: Ru Jia jiaru@ict.ac.cn Reviewed-and-tested-by: Bill Fischofer bill.fischofer@linaro.org Signed-off-by: Maxim Uvarov maxim.uvarov@linaro.org
diff --git a/helper/test/Makefile.am b/helper/test/Makefile.am index 0811d28..d9eb437 100644 --- a/helper/test/Makefile.am +++ b/helper/test/Makefile.am @@ -10,7 +10,8 @@ EXECUTABLES = chksum$(EXEEXT) \ table$(EXEEXT) \ thread$(EXEEXT) \ parse$(EXEEXT)\ - process$(EXEEXT) + process$(EXEEXT) \ + iplookuptable$(EXEEXT)
COMPILE_ONLY = odpthreads
@@ -37,3 +38,4 @@ dist_process_SOURCES = process.c dist_parse_SOURCES = parse.c process_LDADD = $(LIB)/libodphelper-linux.la $(LIB)/libodp-linux.la dist_table_SOURCES = table.c +dist_iplookuptable_SOURCES = iplookuptable.c diff --git a/helper/test/iplookuptable.c b/helper/test/iplookuptable.c new file mode 100644 index 0000000..e1d2820 --- /dev/null +++ b/helper/test/iplookuptable.c @@ -0,0 +1,174 @@ +/* Copyright (c) 2016, Linaro Limited + * All rights reserved. + * + * SPDX-License-Identifier: BSD-3-Clause + */ + +#include <stdio.h> +#include <stdint.h> +#include <string.h> +#include <stdlib.h> +#include <errno.h> + +#include <odp_api.h> +#include <test_debug.h> +#include <../odph_iplookuptable.h> +#include <odp/helper/ip.h> + +static void print_prefix_info( + const char *msg, uint32_t ip, uint8_t cidr) +{ + int i = 0; + uint8_t *ptr = (uint8_t *)(&ip); + + printf("%s IP prefix: ", msg); + for (i = 3; i >= 0; i--) { + if (i != 3) + printf("."); + printf("%d", ptr[i]); + } + printf("/%d\n", cidr); +} + +/* + * Basic sequence of operations for a single key: + * - put short prefix + * - put long prefix + * - get (hit long prefix) + * - remove long prefix + * - get (hit short prefix) + */ +static int test_ip_lookup_table(void) +{ + odph_iplookup_prefix_t prefix1, prefix2; + odph_table_t table; + int ret; + uint64_t value1 = 1, value2 = 2, result = 0; + uint32_t lkp_ip = 0; + + table = odph_iplookup_table_create( + "prefix_test", 0, 0, sizeof(uint32_t)); + if (table == NULL) { + printf("IP prefix lookup table creation failed\n"); + return -1; + } + + ret = odph_ipv4_addr_parse(&prefix1.ip, "192.168.0.0"); + if (ret < 0) { + printf("Failed to get IP addr from str\n"); + odph_iplookup_table_destroy(table); + return -1; + } + prefix1.cidr = 11; + + ret = odph_ipv4_addr_parse(&prefix2.ip, "192.168.0.0"); + if (ret < 0) { + printf("Failed to get IP addr from str\n"); + odph_iplookup_table_destroy(table); + return -1; + } + prefix2.cidr = 24; + + ret = odph_ipv4_addr_parse(&lkp_ip, "192.168.0.1"); + if (ret < 0) { + printf("Failed to get IP addr from str\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + /* test with standard put/get/remove functions */ + ret = odph_iplookup_table_put_value(table, &prefix1, &value1); + print_prefix_info("Add", prefix1.ip, prefix1.cidr); + if (ret < 0) { + printf("Failed to add ip prefix\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + ret = odph_iplookup_table_get_value(table, &lkp_ip, &result, 0); + print_prefix_info("Lkp", lkp_ip, 32); + if (ret < 0 || result != 1) { + printf("Failed to find longest prefix\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + /* add a longer prefix */ + ret = odph_iplookup_table_put_value(table, &prefix2, &value2); + print_prefix_info("Add", prefix2.ip, prefix2.cidr); + if (ret < 0) { + printf("Failed to add ip prefix\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + ret = odph_iplookup_table_get_value(table, &lkp_ip, &result, 0); + print_prefix_info("Lkp", lkp_ip, 32); + if (ret < 0 || result != 2) { + printf("Failed to find longest prefix\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + ret = odph_iplookup_table_remove_value(table, &prefix2); + print_prefix_info("Del", prefix2.ip, prefix2.cidr); + if (ret < 0) { + printf("Failed to delete ip prefix\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + ret = odph_iplookup_table_get_value(table, &lkp_ip, &result, 0); + print_prefix_info("Lkp", lkp_ip, 32); + if (ret < 0 || result != 1) { + printf("Error: found result ater deleting\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + ret = odph_iplookup_table_remove_value(table, &prefix1); + print_prefix_info("Del", prefix1.ip, prefix1.cidr); + if (ret < 0) { + printf("Failed to delete prefix\n"); + odph_iplookup_table_destroy(table); + return -1; + } + + odph_iplookup_table_destroy(table); + return 0; +} + +int main(int argc TEST_UNUSED, char *argv[] TEST_UNUSED) +{ + odp_instance_t instance; + int ret = 0; + + ret = odp_init_global(&instance, NULL, NULL); + if (ret != 0) { + fprintf(stderr, "Error: ODP global init failed.\n"); + exit(EXIT_FAILURE); + } + + ret = odp_init_local(instance, ODP_THREAD_WORKER); + if (ret != 0) { + fprintf(stderr, "Error: ODP local init failed.\n"); + exit(EXIT_FAILURE); + } + + if (test_ip_lookup_table() < 0) + printf("Test failed\n"); + else + printf("All tests passed\n"); + + if (odp_term_local()) { + fprintf(stderr, "Error: ODP local term failed.\n"); + exit(EXIT_FAILURE); + } + + if (odp_term_global(instance)) { + fprintf(stderr, "Error: ODP global term failed.\n"); + exit(EXIT_FAILURE); + } + + return ret; +}
commit 52dbfc9fc964ca292a777f11336854e88538f46d Author: Ru Jia jiaru@ict.ac.cn Date: Thu Jun 30 16:15:31 2016 +0800
helper: table: add impl of ip lookup table
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 jiaru@ict.ac.cn Reviewed-and-tested-by: Bill Fischofer bill.fischofer@linaro.org Signed-off-by: Maxim Uvarov maxim.uvarov@linaro.org
diff --git a/helper/Makefile.am b/helper/Makefile.am index 116a1f0..24a0748 100644 --- a/helper/Makefile.am +++ b/helper/Makefile.am @@ -28,7 +28,8 @@ noinst_HEADERS = \ $(srcdir)/odph_hashtable.h \ $(srcdir)/odph_lineartable.h \ $(srcdir)/odph_cuckootable.h \ - $(srcdir)/odph_list_internal.h + $(srcdir)/odph_list_internal.h \ + $(srcdir)/odph_iplookuptable.h
__LIB__libodphelper_linux_la_SOURCES = \ eth.c \ @@ -37,6 +38,7 @@ __LIB__libodphelper_linux_la_SOURCES = \ linux.c \ hashtable.c \ lineartable.c \ - cuckootable.c + cuckootable.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..5f80743 --- /dev/null +++ b/helper/iplookuptable.c @@ -0,0 +1,937 @@ +/* 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 two 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..0ae6b37 --- /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_ */
-----------------------------------------------------------------------
Summary of changes: helper/Makefile.am | 6 +- helper/iplookuptable.c | 937 ++++++++++++++++++++++++++++++++++++++++++++ helper/odph_iplookuptable.h | 58 +++ helper/test/Makefile.am | 4 +- helper/test/iplookuptable.c | 174 ++++++++ 5 files changed, 1176 insertions(+), 3 deletions(-) create mode 100644 helper/iplookuptable.c create mode 100644 helper/odph_iplookuptable.h create mode 100644 helper/test/iplookuptable.c
hooks/post-receive