path: root/helper/iplookuptable.c

/* 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 <odp/helper/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 {
		odp_buffer_t nexthop;
		void *ptr;
	};
	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
		};
	};
} prefix_entry_t;

#define ENTRY_SIZE (sizeof(prefix_entry_t) + sizeof(odp_buffer_t))
#define ENTRY_BUFF_ARR(x) ((odp_buffer_t *)(void *)((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, &param);
	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;
	odp_shm_t shm;

	if (name == NULL || strlen(name) >= ODPH_TABLE_NAME_LEN)
		return NULL;

	shm = odp_shm_lookup(name);
	if (shm != ODP_SHM_INVALID)
		tbl = (odph_iplookup_table_impl *)odp_shm_addr(shm);

	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 p1 ODP_UNUSED,
					uint32_t p2 ODP_UNUSED,
					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 = (void *)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 *)(void *)((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 *)(void *)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)
			(void)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)
{
	odph_iplookup_table_impl *impl = (void *)tbl;
	odph_iplookup_prefix_t *prefix = (odph_iplookup_prefix_t *)key;
	prefix_entry_t *l1e = NULL;
	odp_buffer_t nexthop;
	int ret = 0;

	if ((tbl == NULL) || (key == NULL) || (value == NULL))
		return -1;

	nexthop = *((odp_buffer_t *)value);

	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 ODP_UNUSED,
				  uint32_t buffer_size ODP_UNUSED)
{
	odph_iplookup_table_impl *impl = (void *)tbl;
	uint32_t ip;
	prefix_entry_t *entry;
	odp_buffer_t *buff = (odp_buffer_t *)buffer;

	if ((tbl == NULL) || (key == NULL) || (buffer == NULL))
		return -EINVAL;

	ip = *((uint32_t *)key);
	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->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)
{
	odph_iplookup_table_impl *impl = (void *)tbl;
	odph_iplookup_prefix_t *prefix = (odph_iplookup_prefix_t *)key;
	uint32_t ip;
	uint8_t cidr;

	if ((tbl == NULL) || (key == NULL))
		return -EINVAL;

	ip   = prefix->ip;
	cidr = prefix->cidr;

	if (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
};