在 2016年5月23日，下午12:26，Ru Jia <[email protected]> 写道：
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 | 974 ++++++++++++++++++++++++++++++++++++++++++++
helper/odph_iplookuptable.h | 58 +++
3 files changed, 1035 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..a0b7e6b
--- /dev/null
+++ b/helper/iplookuptable.c
@@ -0,0 +1,974 @@
+/* Copyright (c) 2015, Linaro Limited
+ * All rights reserved.
+ *
+ * SPDX-License-Identifier: BSD-3-Clause
+ */
+
+#include <string.h>
+#include <stdint.h>
+#include <errno.h>
+#include <stdio.h>
+
+#include "odph_iplookuptable.h"
+#include "odph_list_internal.h"
+#include "odph_debug.h"
+#include <odp_api.h>
+
+/** @magic word, write to the first byte of the memory block
+ * to indicate this block is used by a ip lookup table
+ */
+#define ODPH_IP_LOOKUP_TABLE_MAGIC_WORD 0xCFCFFCFC
+
+/* The length(bit) of the IPv4 address */
+#define IP_LENGTH 32
+
+/* The number of L1 entries */
+#define ENTRY_NUM_L1 (1 << 16)
+/* The size of one L2\L3 subtree */
+#define ENTRY_NUM_SUBTREE (1 << 8)
+
+#define WHICH_CHILD(ip, cidr) ((ip >> (IP_LENGTH - cidr)) & 0x00000001)
+
+/** @internal entry struct
+ * Structure store an entry of the ip prefix table.
+ * Because of the leaf pushing, each entry of the table must have
+ * either a child entry, or a nexthop info.
+ * If child == 0 and index != ODP_BUFFER_INVALID, this entry has
+ * a nexthop info, index indicates the buffer that stores the
+ * nexthop value, and ptr points to the address of the buffer.
+ * If child == 1, this entry has a subtree, index indicates
+ * the buffer that stores the subtree, and ptr points to the
+ * address of the buffer.
+ */
+typedef struct {
+ union {
+ uint8_t u8;
+ struct {
+#if ODP_BYTE_ORDER == ODP_BIG_ENDIAN
+ uint8_t child : 1;
+ uint8_t cidr : 7;
+#else
+ uint8_t cidr : 7;
+ uint8_t child : 1;
+#endif
+ };
+ };
+ odp_buffer_t index;
+ void *ptr;
+} prefix_entry_t;
+
+/** @internal trie node struct
+ * In this IP lookup algorithm, we use a
+ * binary tire to detect the overlap prefix.
+ */
+typedef struct trie_node {
+ /* tree structure */
+ struct trie_node *parent;
+ struct trie_node *left;
+ struct trie_node *right;
+ /* IP prefix length */
+ uint8_t cidr;
+ /* Nexthop buffer index */
+ odp_buffer_t nexthop;
+ /* Buffer that stores this node */
+ odp_buffer_t buffer;
+} trie_node_t;
+
+/** Number of L2\L3 entries(subtrees) per cache cube. */
+#define CACHE_NUM_SUBTREE (1 << 13)
+/** Number of nexthop values per cache cube. */
+#define CACHE_NUM_NEXTHOP (1 << 20)
+/** Number of trie nodes per cache cube. */
+#define CACHE_NUM_TRIE (1 << 20)
+
+/** @typedef cache_type_t
+ * Cache node type
+ */
+typedef enum {
+ CACHE_TYPE_SUBTREE = 0,
+ CACHE_TYPE_TRIE,
+ CACHE_TYPE_NEXTHOP
+} cache_type_t;
+
+/** A IP lookup table structure. */
+typedef struct {
+ /**< for check */
+ uint32_t magicword;
+ /** Name of the hash. */
+ char name[ODPH_TABLE_NAME_LEN];
+ /** Total L1 entries. */
+ prefix_entry_t *l1e;
+ /** Root node of the binary trie */
+ trie_node_t *trie;
+ /** Length of value. */
+ uint32_t nexthop_len;
+ /** Queues of free slots (caches)
+ * There are three queues:
+ * - free_slots[CACHE_TYPE_SUBTREE] is used for L2 and
+ * L3 entries (subtrees). Each buffer stores an 8-bit
+ * subtree.
+ * - free_slots[CACHE_TYPE_TRIE] is used for the binary
+ * trie. Each buffer contains a trie node.
+ * - free_slots[CACHE_TYPE_NEXTHOP] is used for the
+ * nexthop information storage.
+ */
+ odp_queue_t free_slots[3];
+ /** The number of pool used by each queue. */
+ uint32_t cache_count[3];
+} odph_iplookup_table_impl ODP_ALIGNED_CACHE;
+
+/***********************************************************
+ ***************** Cache management ********************
+ ***********************************************************/
+
+/** Destroy all caches */
+static void
+cache_destroy(odph_iplookup_table_impl *impl)
+{
+ odp_queue_t queue;
+ odp_event_t ev;
+ uint32_t i = 0, count = 0;
+ char pool_name[ODPH_TABLE_NAME_LEN + 8];
+
+ /* free all buffers in the queue */
+ for (; i < 3; i++) {
+ queue = impl->free_slots[i];
+ if (queue == ODP_QUEUE_INVALID)
+ continue;
+
+ while ((ev = odp_queue_deq(queue))
+ != ODP_EVENT_INVALID) {
+ odp_buffer_free(odp_buffer_from_event(ev));
+ }
+ odp_queue_destroy(queue);
+ }
+
+ /* destroy all cache pools */
+ for (i = 0; i < 3; i++) {
+ for (count = 0; count < impl->cache_count[i]; count++) {
+ sprintf(
+ pool_name, "%s_%d_%d",
+ impl->name, i, count);
+ odp_pool_destroy(odp_pool_lookup(pool_name));
+ }
+ }
+}
+
+/** According to the type of cahce, set the value of
+ * a buffer to the initial value.
+ */
+static void
+cache_init_buffer(odp_buffer_t buffer, cache_type_t type, uint32_t size) {
+ int i = 0;
+ void *addr = odp_buffer_addr(buffer);
+
+ memset(addr, 0, size);
+ if (type == CACHE_TYPE_SUBTREE) {
+ prefix_entry_t *entry = (prefix_entry_t *)addr;
+
+ for (i = 0; i < ENTRY_NUM_SUBTREE; i++, entry++) {
+ entry->cidr = 0;
+ entry->index = ODP_BUFFER_INVALID;
+ entry->ptr = NULL;
+ }
+ } else if (type == CACHE_TYPE_TRIE) {
+ trie_node_t *node = (trie_node_t *)addr;
+
+ node->buffer = buffer;
+ node->nexthop = ODP_BUFFER_INVALID;
+ }
+}
+
+/** Create a new buffer pool, and insert its buffer into the queue. */
+static int
+cache_alloc_new_pool(
+ odph_iplookup_table_impl *tbl, cache_type_t type)
+{
+ odp_pool_t pool;
+ odp_pool_param_t param;
+ odp_queue_t queue = tbl->free_slots[type];
+
+ odp_buffer_t buffer;
+ char pool_name[ODPH_TABLE_NAME_LEN + 8];
+ char queue_name[ODPH_TABLE_NAME_LEN + 10];
+ uint32_t size = 0, num = 0;
+
+ /* Create new pool (new free buffers). */
+ param.type = ODP_POOL_BUFFER;
+ param.buf.align = ODP_CACHE_LINE_SIZE;
+ if (type == CACHE_TYPE_SUBTREE) {
+ num = CACHE_NUM_SUBTREE;
+ size = sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE;
+ } else if (type == CACHE_TYPE_TRIE) {
+ num = CACHE_NUM_TRIE;
+ size = sizeof(trie_node_t);
+ } else if (type == CACHE_TYPE_NEXTHOP) {
+ num = CACHE_NUM_NEXTHOP;
+ size = tbl->nexthop_len;
+ } else {
+ ODPH_DBG("wrong cache_type_t.\n");
+ return -1;
+ }
+ param.buf.size = size;
+ param.buf.num = num;
+
+ sprintf(
+ pool_name, "%s_%d_%d",
+ tbl->name, type, tbl->cache_count[type]);
+ pool = odp_pool_create(pool_name, ¶m);
+ if (pool == ODP_POOL_INVALID) {
+ ODPH_DBG("failed to create a new pool.\n");
+ return -1;
+ }
+
+ /* insert new free buffers into queue */
+ while ((buffer = odp_buffer_alloc(pool))
+ != ODP_BUFFER_INVALID) {
+ cache_init_buffer(buffer, type, size);
+ odp_queue_enq(queue, odp_buffer_to_event(buffer));
+ }
+
+ tbl->cache_count[type]++;
+ return 0;
+}
+
+/** Get a new buffer from a cache list. If there is no
+ * available buffer, allocate a new pool.
+ */
+static odp_buffer_t
+cache_get_buffer(odph_iplookup_table_impl *tbl, cache_type_t type)
+{
+ odp_buffer_t buffer = ODP_BUFFER_INVALID;
+ odp_queue_t queue = tbl->free_slots[type];
+ uint32_t size = 0;
+
+ /* get free buffer from queue */
+ buffer = odp_buffer_from_event(
+ odp_queue_deq(queue));
+
+ /* If there is no free buffer available, allocate new pool */
+ if (buffer == ODP_BUFFER_INVALID) {
+ cache_alloc_new_pool(tbl, type);
+ buffer = odp_buffer_from_event(odp_queue_deq(queue));
+ }
+
+ return buffer;
+}
+
+/***********************************************************
+ ****************** Binary trie ********************
+ ***********************************************************/
+
+/* Initialize the root node of the trie */
+static int
+trie_init(odph_iplookup_table_impl *tbl)
+{
+ trie_node_t *root = NULL;
+ odp_buffer_t buffer = cache_get_buffer(tbl, CACHE_TYPE_TRIE);
+
+ if (buffer != ODP_BUFFER_INVALID) {
+ root = (trie_node_t *)odp_buffer_addr(buffer);
+ root->cidr = 0;
+ tbl->trie = root;
+ return 0;
+ }
+
+ return -1;
+}
+
+/* Destroy the whole trie (recursively) */
+static void
+trie_destroy(odph_iplookup_table_impl *tbl, trie_node_t *trie)
+{
+ if (trie->left != NULL)
+ trie_destroy(tbl, trie->left);
+ if (trie->right != NULL)
+ trie_destroy(tbl, trie->right);
+
+ /* destroy this node */
+ if (trie->nexthop != ODP_BUFFER_INVALID) {
+ odp_queue_enq(
+ tbl->free_slots[CACHE_TYPE_NEXTHOP],
+ odp_buffer_to_event(trie->nexthop));
+ }
+ odp_queue_enq(
+ tbl->free_slots[CACHE_TYPE_TRIE],
+ odp_buffer_to_event(trie->buffer));
+}
+
+/* Insert a new prefix node into the trie
+ * If the node is already existed, update its nexthop info,
+ * Return 0 and set nexthop pointer to INVALID.
+ * If the node is not exitsed, create this target node and
+ * all nodes along the path from root to the target node.
+ * Then return 0 and set nexthop pointer points to the
+ * new buffer.
+ * Return -1 for error.
+ */
+static int
+trie_insert_node(
+ odph_iplookup_table_impl *tbl, trie_node_t *root,
+ uint32_t ip, uint8_t cidr, void *value,
+ odp_buffer_t *nexthop)
+{
+ uint8_t level = 0, child;
+ odp_buffer_t buf;
+ trie_node_t *node = root, *prev = root;
+ void *val_buf = NULL;
+
+ *nexthop = ODP_BUFFER_INVALID;
+
+ /* create/update all nodes along the path
+ * from root to the new node. */
+ for (level = 1; level <= cidr; level++) {
+ child = WHICH_CHILD(ip, level);
+
+ node = child == 0 ? prev->left : prev->right;
+ /* If the child node doesn't exit, create it. */
+ if (node == NULL) {
+ buf = cache_get_buffer(tbl, CACHE_TYPE_TRIE);
+ if (buf == ODP_BUFFER_INVALID)
+ return -1;
+
+ node = (trie_node_t *)odp_buffer_addr(buf);
+ node->cidr = level;
+ node->parent = prev;
+
+ if (child == 0)
+ prev->left = node;
+ else
+ prev->right = node;
+ }
+ prev = node;
+ }
+
+ /* The final one is the target. If its nexthop buffer
+ * is invalid, create a new buffer.
+ */
+ if (node->nexthop == ODP_BUFFER_INVALID) {
+ buf = cache_get_buffer(tbl, CACHE_TYPE_NEXTHOP);
+ if (buf == ODP_BUFFER_INVALID)
+ return -1;
+ val_buf = odp_buffer_addr(buf);
+ *nexthop = buf;
+ node->nexthop = buf;
+ }
+ /* copy the value into the nexthop buffer */
+ memcpy(val_buf, value, tbl->nexthop_len);
+ return 0;
+}
+
+/* Delete a node */
+static int
+trie_delete_node(
+ odph_iplookup_table_impl *tbl,
+ trie_node_t *root, uint32_t ip, uint8_t cidr)
+{
+ if (root == NULL)
+ return -1;
+
+ /* The default prefix (root node) cannot be deleted. */
+ if (cidr == 0)
+ return -1;
+
+ trie_node_t *node = root, *prev = NULL;
+ uint8_t level = 1, child = 0;
+ odp_buffer_t tmp;
+
+ /* Find the target node. */
+ for (level = 1; level <= cidr; level++) {
+ child = WHICH_CHILD(ip, level);
+ node = (child == 0) ? node->left : node->right;
+ if (node == NULL) {
+ ODPH_DBG("Trie node is not existed\n");
+ return -1;
+ }
+ }
+
+ /* free nexthop buffer */
+ if (node->nexthop != ODP_BUFFER_INVALID) {
+ cache_init_buffer(
+ node->nexthop, CACHE_TYPE_NEXTHOP,
+ tbl->nexthop_len);
+ odp_queue_enq(
+ tbl->free_slots[CACHE_TYPE_NEXTHOP],
+ odp_buffer_to_event(node->nexthop));
+ node->nexthop = ODP_BUFFER_INVALID;
+ }
+
+ /* Delete all redundant nodes along the path. */
+ for (level = cidr; level > 0; level--) {
+ if (
+ node->left != NULL || node->right != NULL ||
+ node->nexthop != ODP_BUFFER_INVALID)
+ break;
+
+ child = WHICH_CHILD(ip, level);
+ prev = node->parent;
+
+ /* free trie node */
+ tmp = node->buffer;
+ cache_init_buffer(
+ tmp, CACHE_TYPE_TRIE, sizeof(trie_node_t));
+ odp_queue_enq(
+ tbl->free_slots[CACHE_TYPE_TRIE],
+ odp_buffer_to_event(tmp));
+
+ if (child == 0)
+ prev->left = NULL;
+ else
+ prev->right = NULL;
+ node = prev;
+ }
+ return 0;
+}
+
+/* Detect the longest overlapping prefix. */
+static int
+trie_detect_overlap(
+ trie_node_t *trie, uint32_t ip, uint8_t cidr,
+ uint8_t leaf_push, uint8_t *over_cidr,
+ odp_buffer_t *over_nexthop)
+{
+ uint8_t child = 0;
+ uint32_t level, limit = cidr > leaf_push ? leaf_push + 1 : cidr;
+ trie_node_t *node = trie, *longest = trie;
+
+ for (level = 1; level < limit; level++) {
+ child = WHICH_CHILD(ip, level);
+ node = (child == 0) ? node->left : node->right;
+ if (node->nexthop != ODP_BUFFER_INVALID)
+ longest = node;
+ }
+
+ *over_cidr = longest->cidr;
+ *over_nexthop = longest->nexthop;
+ return 0;
+}
+
+/***********************************************************
+ *************** IP prefix lookup table ****************
+ ***********************************************************/
+
+odph_table_t
+odph_iplookup_table_lookup(const char *name)
+{
+ odph_iplookup_table_impl *tbl = NULL;
+
+ if (name == NULL || strlen(name) >= ODPH_TABLE_NAME_LEN)
+ return NULL;
+
+ tbl = (odph_iplookup_table_impl *)odp_shm_addr(odp_shm_lookup(name));
+
+ if (
+ tbl != NULL &&
+ tbl->magicword == ODPH_IP_LOOKUP_TABLE_MAGIC_WORD &&
+ strcmp(tbl->name, name) == 0)
+ return (odph_table_t)tbl;
+}
+
+odph_table_t
+odph_iplookup_table_create(
+ const char *name, uint32_t ODP_IGNORED_1,
+ uint32_t ODP_IGNORED_2, uint32_t value_size)
+{
+ odph_iplookup_table_impl *tbl;
+ odp_shm_t shm_tbl;
+ odp_queue_t queue;
+ odp_queue_param_t qparam;
+
+ unsigned i;
+ uint32_t impl_size, l1_size;
+ char queue_name[ODPH_TABLE_NAME_LEN + 2];
+
+ /* Check for valid parameters */
+ if (strlen(name) == 0) {
+ ODPH_DBG("invalid parameters\n");
+ return NULL;
+ }
+
+ /* Guarantee there's no existing */
+ tbl = (odph_iplookup_table_impl *)odph_iplookup_table_lookup(name);
+ if (tbl != NULL) {
+ ODPH_DBG("IP prefix table %s already exists\n", name);
+ return NULL;
+ }
+
+ /* Calculate the sizes of different parts of IP prefix table */
+ impl_size = sizeof(odph_iplookup_table_impl);
+ l1_size = sizeof(prefix_entry_t) * ENTRY_NUM_L1;
+
+ shm_tbl = odp_shm_reserve(
+ name, impl_size + l1_size,
+ ODP_CACHE_LINE_SIZE, ODP_SHM_SW_ONLY);
+
+ if (shm_tbl == ODP_SHM_INVALID) {
+ ODPH_DBG(
+ "shm allocation failed for odph_iplookup_table_impl
%s\n",
+ name);
+ return NULL;
+ }
+
+ tbl = (odph_iplookup_table_impl *)odp_shm_addr(shm_tbl);
+ memset(tbl, 0, impl_size + l1_size);
+
+ /* header of this mem block is the table impl struct,
+ * then the l1 entries array.
+ */
+ tbl->l1e = (prefix_entry_t *)((char *)tbl + impl_size);
+ for (i = 0; i < ENTRY_NUM_L1; i++) {
+ tbl->l1e[i].index = ODP_BUFFER_INVALID;
+ tbl->l1e[i].ptr = NULL;
+ }
+
+ /* Setup table context. */
+ snprintf(tbl->name, sizeof(tbl->name), "%s", name);
+ tbl->magicword = ODPH_IP_LOOKUP_TABLE_MAGIC_WORD;
+ tbl->nexthop_len = value_size;
+
+ /* Initialize cache */
+ for (i = 0; i < 3; i++) {
+ tbl->cache_count[i] = 0;
+
+ odp_queue_param_init(&qparam);
+ qparam.type = ODP_QUEUE_TYPE_PLAIN;
+ sprintf(queue_name, "%s_%d", name, i);
+ queue = odp_queue_create(queue_name, &qparam);
+ if (queue == ODP_QUEUE_INVALID) {
+ ODPH_DBG("failed to create queue");
+ cache_destroy(tbl);
+ return NULL;
+ }
+ tbl->free_slots[i] = queue;
+ cache_alloc_new_pool(tbl, i);
+ }
+
+ /* Initialize tire */
+ if (trie_init(tbl) < 0) {
+ odp_shm_free(shm_tbl);
+ return NULL;
+ }
+
+ return (odph_table_t)tbl;
+}
+
+int
+odph_iplookup_table_destroy(odph_table_t tbl)
+{
+ int i, j;
+ odph_iplookup_table_impl *impl = NULL;
+ prefix_entry_t *subtree = NULL;
+
+ if (tbl == NULL)
+ return -1;
+
+ impl = (odph_iplookup_table_impl *)tbl;
+
+ /* check magic word */
+ if (impl->magicword != ODPH_IP_LOOKUP_TABLE_MAGIC_WORD) {
+ ODPH_DBG("wrong magicword for IP prefix table\n");
+ return -1;
+ }
+
+ /* destroy trie */
+ trie_destroy(impl, impl->trie);
+
+ /* free all L2 and L3 entries */
+ for (i = 0; i < ENTRY_NUM_L1; i++) {
+ if ((impl->l1e[i]).child == 0)
+ continue;
+
+ subtree = (prefix_entry_t *)odp_buffer_addr(
+ impl->l1e[i].index);
+ /* destroy all l3 subtrees of this l2 subtree */
+ for (j = 0; j < ENTRY_NUM_SUBTREE; j++) {
+ if (subtree[j].child == 0)
+ continue;
+ odp_queue_enq(
+ impl->free_slots[CACHE_TYPE_TRIE],
+ odp_buffer_to_event(subtree[j].index));
+ }
+ /* destroy this l2 subtree */
+ odp_queue_enq(
+ impl->free_slots[CACHE_TYPE_TRIE],
+ odp_buffer_to_event(impl->l1e[i].index));
+ }
+
+ /* destroy all cache */
+ cache_destroy(impl);
+
+ /* free impl */
+ odp_shm_free(odp_shm_lookup(impl->name));
+}
+
+/* Insert the prefix into level x
+ * Return:
+ * -1 error
+ * 0 the table is unmodified
+ * 1 the table is modified
+ */
+static int
+prefix_insert_into_lx(
+ odph_iplookup_table_impl *tbl, prefix_entry_t *entry,
+ uint8_t cidr, odp_buffer_t nexthop, uint8_t level)
+{
+ uint8_t ret = 0;
+ uint32_t i = 0, limit = (1 << (level - cidr));
+ prefix_entry_t *e = entry, *ne = NULL;
+
+ for (i = 0; i < limit; i++, e++) {
+ if (e->child == 1) {
+ if (e->cidr > cidr)
+ continue;
+
+ e->cidr = cidr;
+ if (e->index == ODP_BUFFER_INVALID) {
+ ODPH_DBG("Subtree is not existed.\n");
+ return -1;
+ }
+ /* push to next level */
+ ne = odp_buffer_addr(e->index);
+ ret = prefix_insert_into_lx(
+ tbl, ne, cidr, nexthop, cidr + 8);
+ } else {
+ if (e->cidr > cidr)
+ continue;
+
+ e->child = 0;
+ e->cidr = cidr;
+ e->index = nexthop;
+ ret = 1;
+ }
+ }
+ return ret;
+}
+
+static int
+prefix_insert_iter(
+ odph_iplookup_table_impl *tbl, prefix_entry_t *entry,
+ uint32_t ip, uint8_t cidr, odp_buffer_t nexthop,
+ uint8_t level, uint8_t depth)
+{
+ uint8_t state = 0;
+ prefix_entry_t *ne = NULL;
+ int i = 0;
+
+ /* If child subtree is existed, get it. */
+ if (entry->child) {
+ ne = (prefix_entry_t *)odp_buffer_addr(entry->index);
+ } else {
+ /* If the child is not existed, create a new subtree. */
+ odp_buffer_t buf, push = entry->index;
+
+ buf = cache_get_buffer(tbl, CACHE_TYPE_SUBTREE);
+ if (buf == ODP_BUFFER_INVALID) {
+ ODPH_DBG("failed to get subtree buffer from cache.\n");
+ return -1;
+ }
+ ne = (prefix_entry_t *)odp_buffer_addr(buf);
+
+ /* initialize subtree */
+ for (; i < ENTRY_NUM_SUBTREE; i++)
+ ne[i].index = ODP_BUFFER_INVALID;
+
+ entry->child = 1;
+ entry->index = buf;
+ entry->ptr = ne;
+
+ /* If this entry contains a nexthop and a small cidr,
+ * push it to the next level.
+ */
+ if (entry->cidr > 0) {
+ state = prefix_insert_into_lx(
+ tbl, ne, entry->cidr,
+ push, entry->cidr + 8);
+ }
+ }
+
+ ne += (ip >> 24);
+ if (cidr <= 8) {
+ state = prefix_insert_into_lx(
+ tbl, ne, cidr + depth * 8, nexthop, level);
+ } else {
+ state = prefix_insert_iter(
+ tbl, ne, ip << 8, cidr - 8,
+ nexthop, level + 8, depth + 1);
+ }
+
+ return state;
+}
+
+int
+odph_iplookup_table_put_value(odph_table_t tbl, void *key, void *value)
+{
+ if ((tbl == NULL) || (key == NULL) || (value == NULL))
+ return -1;
+
+ odph_iplookup_table_impl *impl = (odph_iplookup_table_impl *)tbl;
+ odph_iplookup_prefix_t *prefix = (odph_iplookup_prefix_t *)key;
+ prefix_entry_t *l1e = NULL;
+ odp_buffer_t nexthop;
+ int ret = 0;
+
+ if (prefix->cidr == 0)
+ return -1;
+ prefix->ip = prefix->ip & (0xffffffff << (IP_LENGTH - prefix->cidr));
+
+ /* insert into trie */
+ ret = trie_insert_node(
+ impl, impl->trie, prefix->ip, prefix->cidr,
+ value, &nexthop);
+
+ if (ret < 0) {
+ ODPH_DBG("failed to insert into trie\n");
+ return -1;
+ }
+
+ /* If the prefix is already existed, trie_insert_node has
+ * already updated the corresponding nexthop buffer. The
+ * insertion finished.
+ */
+ if (nexthop == ODP_BUFFER_INVALID)
+ return 0;
+
+ /* get L1 entry */
+ l1e = &impl->l1e[prefix->ip >> 16];
+
+ if (prefix->cidr <= 16) {
+ ret = prefix_insert_into_lx(
+ impl, l1e, prefix->cidr, nexthop, 16);
+ } else {
+ ret = prefix_insert_iter(
+ impl, l1e,
+ ((prefix->ip) << 16), prefix->cidr - 16,
+ nexthop, 24, 2);
+ }
+
+ return ret;
+}
+
+int
+odph_iplookup_table_get_value(
+ odph_table_t tbl, void *key, void *buffer, uint32_t buffer_size)
+{
+ if ((tbl == NULL) || (key == NULL) || (buffer == NULL))
+ return -EINVAL;
+
+ odph_iplookup_table_impl *impl = (odph_iplookup_table_impl *)tbl;
+ uint32_t ip = *((uint32_t *)key);
+ prefix_entry_t *entry = &impl->l1e[ip >> 16];
+
+ if (entry == NULL) {
+ ODPH_DBG("failed to get L1 entry.\n");
+ return -1;
+ }
+
+ ip <<= 16;
+ while (entry->child) {
+ entry = (prefix_entry_t *)entry->ptr;
+ entry += ip >> 24;
+ ip <<= 8;
+ }
+
+ /* copy data */
+ if (entry->index == ODP_BUFFER_INVALID) {
+ /* ONLY match the default prefix */
+ memset(buffer, 0, impl->nexthop_len);
+ } else {
+ memcpy(
+ buffer, odp_buffer_addr(entry->index),
+ impl->nexthop_len);
+ }
+
+ return 0;
+}
+
+static int
+prefix_delete_lx(
+ odph_iplookup_table_impl *tbl, prefix_entry_t *l1e,
+ uint8_t cidr, uint8_t over_cidr, odp_buffer_t over_nexthop,
+ uint8_t level)
+{
+ uint8_t ret, flag = 1;
+ prefix_entry_t *e = l1e;
+ uint32_t i = 0, limit = 1 << (level - cidr);
+
+ for (i = 0; i < limit; i++, e++) {
+ if (e->child == 1) {
+ if (e->cidr > cidr) {
+ flag = 0;
+ continue;
+ }
+
+ prefix_entry_t *ne = (prefix_entry_t *)odp_buffer_addr(
+ e->index);
+
+ e->cidr = over_cidr;
+ ret = prefix_delete_lx(
+ tbl, ne, cidr, over_cidr,
+ over_nexthop, cidr + 8);
+
+ /* If ret == 1, the next 2^8 entries equal to
+ * (over_cidr, over_nexthop). In this case, we
+ * should not push the (over_cidr, over_nexthop)
+ * to the next level. In fact, we should recycle
+ * the next 2^8 entries.
+ */
+ if (ret) {
+ /* destroy subtree */
+ cache_init_buffer(
+ e->index, CACHE_TYPE_SUBTREE,
+ sizeof(prefix_entry_t)
+ * ENTRY_NUM_SUBTREE);
+ odp_queue_enq(
+ tbl->free_slots[CACHE_TYPE_SUBTREE],
+ odp_buffer_to_event(e->index));
+ e->child = 0;
+ e->index = over_nexthop;
+ } else {
+ flag = 0;
+ }
+ } else {
+ if (e->cidr > cidr) {
+ flag = 0;
+ continue;
+ } else {
+ e->cidr = over_cidr;
+ e->index = over_nexthop;
+ }
+ }
+ }
+ return flag;
+}
+
+/* Check if the entry can be recycled.
+ * An entry can be recycled duo to two reasons:
+ * - all children of the entry are the same,
+ * - all children of the entry have a cidr smaller than the level
+ * bottom bound.
+ */
+static uint8_t
+can_recycle(prefix_entry_t *e, uint32_t level)
+{
+ uint8_t recycle = 1;
+ int i = 1;
+ prefix_entry_t *ne = (prefix_entry_t *)odp_buffer_addr(e->index);
+
+ if (ne->child)
+ return 0;
+
+ uint8_t cidr = ne->cidr;
+ odp_buffer_t index = ne->index;
+
+ if (cidr > level)
+ return 0;
+
+ ne++;
+ for (; i < 256; i++, ne++) {
+ if (ne->child != 0 || ne->cidr != cidr || ne->index != index) {
+ recycle = 0;
+ break;
+ }
+ }
+ return recycle;
+}
+
+static uint8_t
+prefix_delete_iter(
+ odph_iplookup_table_impl *tbl, prefix_entry_t *e,
+ uint32_t ip, uint8_t cidr, uint8_t level, uint8_t depth)
+{
+ uint8_t ret = 0, over_cidr;
+ odp_buffer_t over_nexthop;
+
+ trie_detect_overlap(
+ tbl->trie, ip, cidr + 8 * depth, level,
+ &over_cidr, &over_nexthop);
+ if (cidr > 8) {
+ prefix_entry_t *ne =
+ (prefix_entry_t *)odp_buffer_addr(e->index);
+ prefix_entry_t *org_ne = ne;
+
+ ne += ((uint32_t)(ip << level) >> 24);
+ ret = prefix_delete_iter(
+ tbl, ne, ip, cidr - 8, level + 8, depth + 1);
+
+ if (ret && can_recycle(e, level)) {
+ /* destroy subtree */
+ cache_init_buffer(
+ e->index, CACHE_TYPE_SUBTREE,
+ sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE);
+ odp_queue_enq(
+ tbl->free_slots[CACHE_TYPE_SUBTREE],
+ odp_buffer_to_event(e->index));
+ e->child = 0;
+ e->index = over_nexthop;
+ e->cidr = over_cidr;
+ return 1;
+ }
+ return 0;
+ }
+
+ ret = prefix_delete_lx(
+ tbl, e, cidr + 8 * depth,
+ over_cidr, over_nexthop, level);
+ return ret;
+}
+
+int
+odph_iplookup_table_remove_value(odph_table_t tbl, void *key)
+{
+ if ((tbl == NULL) || (key == NULL))
+ return -EINVAL;
+
+ odph_iplookup_table_impl *impl = (odph_iplookup_table_impl *)tbl;
+ odph_iplookup_prefix_t *prefix = (odph_iplookup_prefix_t *)key;
+ uint32_t ip = prefix->ip;
+ uint8_t cidr = prefix->cidr;
+
+ if (prefix->cidr < 0)
+ return -EINVAL;
+
+ prefix_entry_t *entry = &impl->l1e[ip >> 16];
+ uint8_t over_cidr, ret;
+ odp_buffer_t over_nexthop;
+
+ trie_detect_overlap(
+ impl->trie, ip, cidr, 16, &over_cidr, &over_nexthop);
+
+ if (cidr <= 16) {
+ prefix_delete_lx(
+ impl, entry, cidr, over_cidr, over_nexthop, 16);
+ } else {
+ prefix_entry_t *ne = (prefix_entry_t *)odp_buffer_addr(
+ entry->index);
+ prefix_entry_t *org_ne = ne;
+
+ ne += ((uint32_t)(ip << 16) >> 24);
+ ret = prefix_delete_iter(impl, ne, ip, cidr - 16, 24, 2);
+
+ if (ret && can_recycle(entry, 16)) {
+ /* destroy subtree */
+ cache_init_buffer(
+ entry->index, CACHE_TYPE_SUBTREE,
+ sizeof(prefix_entry_t) * ENTRY_NUM_SUBTREE);
+ odp_queue_enq(
+ impl->free_slots[CACHE_TYPE_SUBTREE],
+ odp_buffer_to_event(entry->index));
+ entry->child = 0;
+ entry->cidr = over_cidr;
+ entry->index = over_nexthop;
+ }
+ }
+
+ return trie_delete_node(impl, impl->trie, ip, cidr);
+}
+
+odph_table_ops_t odph_iplookup_table_ops = {
+ odph_iplookup_table_create,
+ odph_iplookup_table_lookup,
+ odph_iplookup_table_destroy,
+ odph_iplookup_table_put_value,
+ odph_iplookup_table_get_value,
+ odph_iplookup_table_remove_value
+};
diff --git a/helper/odph_iplookuptable.h b/helper/odph_iplookuptable.h
new file mode 100644
index 0000000..e6040ca
--- /dev/null
+++ b/helper/odph_iplookuptable.h
@@ -0,0 +1,58 @@
+/* Copyright (c) 2015, Linaro Limited
+ * 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
