[dpdk-dev] [RFC] rte_hash: introduce hash list into hash lib

[Bing Zhao <bingz@mellanox.com>]

An extendible hash list library supporting add, delete, lookup action.
Extending when the elements number of any list reach the pre-set max
value, and splitting of the list is done passively when this list is
being accessed(add, del, lookup). Right now, it is not a multi-thread
safe implementation and no table size shrinking is supported.

Signed-off-by: Bing Zhao <bingz@mellanox.com>
---
 lib/librte_hash/Makefile             |   2 +
 lib/librte_hash/rte_hash_version.map |  15 +
 lib/librte_hash/rte_hlist.c          | 687 +++++++++++++++++++++++++++++++++++
 lib/librte_hash/rte_hlist.h          | 563 ++++++++++++++++++++++++++++
 4 files changed, 1267 insertions(+)
 create mode 100644 lib/librte_hash/rte_hlist.c
 create mode 100644 lib/librte_hash/rte_hlist.h

diff --git a/lib/librte_hash/Makefile b/lib/librte_hash/Makefile
index c8c435d..6de49dd 100644
--- a/lib/librte_hash/Makefile
+++ b/lib/librte_hash/Makefile
@@ -17,6 +17,7 @@ LIBABIVER := 2
 # all source are stored in SRCS-y
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) := rte_cuckoo_hash.c
 SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_fbk_hash.c
+SRCS-$(CONFIG_RTE_LIBRTE_HASH) += rte_hlist.c
 
 # install this header file
 SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include := rte_hash.h
@@ -29,5 +30,6 @@ endif
 SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_jhash.h
 SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_thash.h
 SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_fbk_hash.h
+SYMLINK-$(CONFIG_RTE_LIBRTE_HASH)-include += rte_hlist.h
 
 include $(RTE_SDK)/mk/rte.lib.mk
diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
index 734ae28..9325f4f 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -59,4 +59,19 @@ EXPERIMENTAL {
 
 	rte_hash_free_key_with_position;
 
+	rte_hlist_add_key;
+	rte_hlist_add_key_data;
+	rte_hlist_add_key_data_len;
+	rte_hlist_add_key_with_hash_data;
+	rte_hlist_add_key_with_hash_data_len;
+	rte_hlist_clear_all_entries_with_cb;
+	rte_hlist_create;
+	rte_hlist_del_entry_fast_return_data;
+	rte_hlist_del_key;
+	rte_hlist_del_key_return_data;
+	rte_hlist_free;
+	rte_hlist_hash;
+	rte_hlist_lookup;
+	rte_hlist_lookup_with_hash;
+
 };
diff --git a/lib/librte_hash/rte_hlist.c b/lib/librte_hash/rte_hlist.c
new file mode 100644
index 0000000..d2e96fe
--- /dev/null
+++ b/lib/librte_hash/rte_hlist.c
@@ -0,0 +1,687 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright 2019 Mellanox Technologies, Ltd
+ */
+
+#include <string.h>
+
+#include <rte_common.h>
+#include <rte_eal_memconfig.h>
+#include <rte_malloc.h>
+#include <rte_memcpy.h>
+#include <rte_errno.h>
+#include <rte_log.h>
+
+#include "rte_hlist.h"
+
+TAILQ_HEAD(rte_hlist_list, rte_tailq_entry);
+
+static struct rte_tailq_elem rte_hlist_tailq = {
+	.name = "RTE_HLIST",
+};
+EAL_REGISTER_TAILQ(rte_hlist_tailq)
+
+hash_sig_t
+rte_hlist_hash(const struct rte_hlist_table *h, const void *key)
+{
+	/* calc hash result by key */
+	return h->hash_func(key, h->key_len, h->init_val);
+}
+
+static inline int
+__rte_hlist_extend_list_table(struct rte_hlist_table *h)
+{
+	struct rte_hlist_head_entry *new;
+	uint32_t dsize = (h->bucket_mask + 1) << 1;
+
+	new = (struct rte_hlist_head_entry *)rte_realloc(h->t,
+				sizeof(struct rte_hlist_head_entry) * dsize, 0);
+	if (new == NULL) {
+		rte_errno = ENOMEM;
+		return -rte_errno;
+	}
+	memset(((char *)new)+sizeof(struct rte_hlist_head_entry)*(dsize>>1),
+		0, sizeof(struct rte_hlist_head_entry)*(dsize>>1));
+
+	/* new head that first element prev points to must be adjusted */
+	h->t = new;
+	h->entries *= 2;
+	h->bucket_shift += 1;
+	h->bucket_mask = dsize - 1;
+
+	return 0;
+}
+
+static inline uint32_t
+__rte_hlist_find_pre_unsplited_list(
+	const struct rte_hlist_table *h, uint32_t idx)
+{
+	struct rte_hlist_head_entry *n_he;
+	uint32_t gap = (h->bucket_shift > h->t[idx].bucket_shift) ?
+		(h->bucket_shift - h->t[idx].bucket_shift) : 0;
+	uint32_t i;
+	uint32_t p_idx = idx;
+
+	/* If the shift number is not zero, just return the one from input. */
+	for (i = 0; i <= gap; i++) {
+		p_idx = idx &
+			HLIST_CALC_PREVIOUS_BUCKET_MASK(h->bucket_mask, i);
+		n_he = &h->t[p_idx];
+		if (n_he->bucket_shift != 0)
+			break;
+	}
+
+	return p_idx;
+}
+
+static inline int
+__rte_hlist_split_one_list(const struct rte_hlist_table *h,
+	uint32_t idx)
+{
+	struct rte_hlist_node_entry *pos;
+	struct rte_hlist_node_entry *tp;
+	struct rte_hlist_head_entry *he = &h->t[idx];
+	struct rte_hlist_head_entry *n_he;
+	uint32_t new_idx;
+	uint32_t sh;
+	uint32_t sh_gap_mul;
+	uint32_t i = 0;
+
+	if (h->bucket_shift <= he->bucket_shift) {
+		rte_errno = EINVAL;
+		return -rte_errno;
+	}
+
+	/* adjust the '(elm)->field.le_prev' of first element to the new head */
+	LIST_MOVE_TO_NEW_HEAD(&he->head, &he->head, next);
+
+	/* TAILQ is easy for lists combining when shrinking the table, but a
+	 * little more memory will be costed for each head. No need to
+	 * re-calculate the hash value.
+	 */
+	LIST_FOREACH_SAFE(pos, &he->head, next, tp) {
+		new_idx = pos->d.sig & h->bucket_mask;
+		if (new_idx != idx) {
+			LIST_REMOVE(pos, next);
+			he->entries_in_bucket--;
+			n_he = &h->t[new_idx];
+			LIST_INSERT_HEAD(&n_he->head, pos, next);
+			n_he->entries_in_bucket++;
+		}
+	}
+
+	/* old_mask to speed up:
+	 * [0, old_mask+1, 2(old_mask+1) ... <mask] | idx
+	 */
+	do { i++; } while (h->bucket_mask >> i);
+	sh = i - (h->bucket_shift - he->bucket_shift);
+	sh_gap_mul = 1 << (h->bucket_shift - he->bucket_shift);
+	for (i = 0; i < sh_gap_mul; i++) {
+		new_idx = (i << sh) | idx;
+		h->t[new_idx].bucket_shift = h->bucket_shift;
+	}
+
+	return 0;
+}
+
+static inline int
+__rte_hlist_find_node_entry(struct rte_hlist_table *h,
+	const void *key, hash_sig_t sig, struct rte_hlist_node_entry **p)
+{
+	uint32_t idx;
+	uint32_t n_idx;
+	struct rte_hlist_head_entry *he;
+	struct rte_hlist_head_entry *n_he;
+	struct rte_hlist_node_entry *pos;
+	uint32_t matched = FALSE;
+	int ret;
+
+	if ((h == NULL) || (key == NULL) || (p == NULL)) {
+		rte_errno = EINVAL;
+		return -rte_errno;
+	}
+
+	idx = sig & h->bucket_mask;
+	he = &h->t[idx];
+
+	/* When the entries linked to the list reach upper limit, we try to
+	 * extend the length of the head array. Then we just split this list.
+	 * Others will be checked and splitted when being accessed.
+	 * Shift number also needs to be checked in case of extra extending.
+	 */
+	if ((he->entries_in_bucket > h->entries_per_bucket) &&
+		(he->bucket_shift == h->bucket_shift)) {
+		/* If the list operation failed, it returns nothing even if
+		 * the key will match one of the existing entries.
+		 */
+		ret = __rte_hlist_extend_list_table(h);
+		if (ret < 0) {
+			RTE_LOG(ERR, HASH,
+				"Failed to extend the list table %d\n", ret);
+			goto exit;
+		}
+	}
+
+	if (he->bucket_shift < h->bucket_shift) {
+		uint32_t p_idx = __rte_hlist_find_pre_unsplited_list(h, idx);
+
+		/* No matter how many times extending is done, one splitting
+		 * is enough. If shift is 0, then the 'oldest' list that is
+		 * not splitted should be splitted(no matter if any entry in).
+		 * If not zero, just try to split this list and try to move
+		 * entries into the new one.
+		 */
+		ret = __rte_hlist_split_one_list(h, p_idx);
+		if (ret < 0) {
+			RTE_LOG(ERR, HASH,
+				"Failed to split the bucket %d\n", ret);
+			goto exit;
+		}
+	}
+
+	/* Need to re-do since the mask & pointer may change if extended */
+	n_idx = sig & h->bucket_mask;
+	n_he = &h->t[n_idx];
+
+	/* Passive way: just split the list that being accessed.
+	 * After splitting, only one list needs to be traversed.
+	 */
+	if (n_he->entries_in_bucket > 0) {
+		LIST_FOREACH(pos, &n_he->head, next) {
+			if (pos->d.sig == sig)
+				/* Key comparison needs be optimized later */
+				if (!memcmp(pos->key, key, h->key_len)) {
+					matched = TRUE;
+					break;
+				}
+		}
+	}
+
+	if (matched == TRUE) {
+		*p = pos;
+		/* The head index will always be the calculated one
+		 * because of the splitting of the list.
+		 */
+		ret = n_idx;
+	} else {
+		*p = NULL;
+		ret = -ENOENT;
+	}
+
+exit:
+	return ret;
+}
+
+static inline struct rte_hlist_data_element *
+__rte_hlist_add_key_with_hash_data(struct rte_hlist_table *h,
+	const void *key, hash_sig_t sig, void *data, uint16_t len, uint8_t cus)
+{
+	int idx;
+	struct rte_hlist_head_entry *he;
+	struct rte_hlist_node_entry *pos;
+
+	idx = __rte_hlist_find_node_entry(h, key, sig, &pos);
+	if (idx >= 0) {
+		pos->d.flags &= (~HLIST_DATA_NEW_ENTRY);
+		return &pos->d;
+	} else if ((idx < 0) && (idx != -ENOENT))
+		return NULL;
+
+	/* All the fields will be written */
+	pos = rte_malloc(NULL,
+		sizeof(struct rte_hlist_node_entry) + h->key_len, 0);
+	if (pos == NULL) {
+		RTE_LOG(ERR, HASH, "Failed to allocate new list node\n");
+		return NULL;
+	}
+
+	pos->d.sig = sig;
+	/* should be optimized if the key length is small */
+	rte_memcpy(pos->key, key, h->key_len);
+	/* User should be responsible for the data no matter how many bytes
+	 * the length is.
+	 */
+	if (cus == TRUE) {
+		pos->d.extra_data = data;
+		pos->d.flags = HLIST_DATA_CUSTOM_EXTRA_DATA;
+		h->custom_entries++;
+	} else {
+		if ((data != NULL) && (len != 0)) {
+			pos->d.flags = HLIST_DATA_INLINE;
+			switch (len) {
+			case 1:
+				pos->d.v8 = *(uint8_t *)data;
+				break;
+			case 2:
+				pos->d.v16 = *(uint16_t *)data;
+				break;
+			case 4:
+				pos->d.v32 = *(uint32_t *)data;
+				break;
+			case 8:
+				pos->d.v64 = *(uint64_t *)data;
+				break;
+			default:
+				pos->d.extra_data = rte_malloc(NULL, len, 0);
+				if (pos->d.extra_data == NULL) {
+					rte_free(pos);
+					rte_errno = ENOMEM;
+					return NULL;
+				}
+				rte_memcpy(pos->d.extra_data, data, len);
+				pos->d.flags = HLIST_DATA_ALLOC_WITH_SIZE(len);
+				break;
+			}
+		} else {
+			pos->d.extra_data = data;
+			pos->d.flags = HLIST_DATA_NOT_EXIST;
+		}
+	}
+	pos->d.flags |= HLIST_DATA_NEW_ENTRY;
+	idx = sig & h->bucket_mask;
+	he = &h->t[idx];
+	LIST_INSERT_HEAD(&he->head, pos, next);
+	he->entries_in_bucket++;
+
+	return &pos->d;
+}
+
+struct rte_hlist_data_element *
+rte_hlist_add_key(struct rte_hlist_table *h, const void *key)
+{
+	RETURN_IF_TRUE_ERRNO(((h == NULL) || (key == NULL)), NULL, -EINVAL);
+
+	return __rte_hlist_add_key_with_hash_data(h, key,
+			rte_hlist_hash(h, key), NULL, 0, FALSE);
+}
+
+struct rte_hlist_data_element *
+rte_hlist_add_key_data(struct rte_hlist_table *h,
+	const void *key, void *data)
+{
+	RETURN_IF_TRUE_ERRNO(((h == NULL) || (key == NULL)), NULL, -EINVAL);
+
+	return __rte_hlist_add_key_with_hash_data(h, key,
+			rte_hlist_hash(h, key), data, 0, TRUE);
+}
+
+struct rte_hlist_data_element *
+rte_hlist_add_key_data_len(struct rte_hlist_table *h,
+	const void *key, void *data, uint16_t len, uint8_t cus)
+{
+	RETURN_IF_TRUE_ERRNO(((h == NULL) || (key == NULL)), NULL, -EINVAL);
+
+	return __rte_hlist_add_key_with_hash_data(h, key,
+			rte_hlist_hash(h, key), data, len, cus);
+}
+
+struct rte_hlist_data_element *
+rte_hlist_add_key_with_hash_data(struct rte_hlist_table *h,
+	const void *key, hash_sig_t sig, void *data)
+{
+	RETURN_IF_TRUE_ERRNO(((h == NULL) || (key == NULL)), NULL, -EINVAL);
+
+	return __rte_hlist_add_key_with_hash_data(h, key, sig, data, 0, TRUE);
+}
+
+struct rte_hlist_data_element *
+rte_hlist_add_key_with_hash_data_len(
+	struct rte_hlist_table *h, const void *key, hash_sig_t sig,
+	void *data, uint16_t len, uint8_t cus)
+{
+	RETURN_IF_TRUE_ERRNO(((h == NULL) || (key == NULL)), NULL, -EINVAL);
+
+	return __rte_hlist_add_key_with_hash_data(h, key, sig, data, len, cus);
+}
+
+static inline int
+__rte_hlist_del_key_with_hash_return_data(
+	struct rte_hlist_table *h, const void *key,
+	hash_sig_t sig, void **data)
+{
+	struct rte_hlist_node_entry *pos;
+	int idx = __rte_hlist_find_node_entry(h, key, sig, &pos);
+	if (idx < 0)
+		return idx;
+
+	*data = NULL;
+	if (HLIST_DATA_CUSTOM_EXTRA_DATA & pos->d.flags) {
+		*data = pos->d.extra_data;
+		h->custom_entries--;
+	} else if (HLIST_DATA_IS_ALLOCATED(&pos->d)) {
+		rte_free(pos->d.extra_data);
+	}
+
+	LIST_REMOVE(pos, next);
+	rte_free(pos);
+	h->t[idx].entries_in_bucket--;
+
+	return 0;
+}
+
+static inline int
+__rte_hlist_del_key_with_hash(struct rte_hlist_table *h,
+	const void *key, hash_sig_t sig)
+{
+	struct rte_hlist_node_entry *pos;
+	int idx;
+
+	/* Currently there will be some 'false positive' to extend the lists
+	 * head and split this list. e.g. only one more entry in the list to
+	 * be moved to another list after extending and if it is the one to be
+	 * removed, then there will be no entry in the 'brother' list after
+	 * deletion. But the length of the lists head array is extended after
+	 * searching. It is not a bug but not graceful enough right now.
+	 * (Other hash table may also face some issues with this scenario)
+	 */
+	idx = __rte_hlist_find_node_entry(h, key, sig, &pos);
+	if (idx < 0)
+		return idx;
+
+	if (HLIST_DATA_CUSTOM_EXTRA_DATA & pos->d.flags) {
+		if (h->free_func == NULL) {
+			rte_errno = EBUSY;
+			return -rte_errno;
+		}
+		h->free_func(pos->d.extra_data);
+		h->custom_entries--;
+	} else if (HLIST_DATA_IS_ALLOCATED(&pos->d)) {
+		rte_free(pos->d.extra_data);
+	}
+
+	LIST_REMOVE(pos, next);
+	rte_free(pos);
+	h->t[idx].entries_in_bucket--;
+
+	return 0;
+}
+
+static inline int
+__rte_hlist_del_entry_fast_return_data(struct rte_hlist_table *h,
+	struct rte_hlist_data_element *de, void **data)
+{
+	struct rte_hlist_node_entry *pos;
+	struct rte_hlist_head_entry *he;
+	uint32_t idx = de->sig & h->bucket_mask;
+	int ret;
+
+	pos = container_of(de, struct rte_hlist_node_entry, d);
+	he = &h->t[idx];
+
+	/* Splitting will ensure that the head and the first element pointers
+	 * are consistent, or else the deletion will cause memory corruption.
+	 */
+	if (he->bucket_shift < h->bucket_shift) {
+		uint32_t p_idx = __rte_hlist_find_pre_unsplited_list(h, idx);
+
+		ret = __rte_hlist_split_one_list(h, p_idx);
+		if (ret < 0) {
+			RTE_LOG(ERR, HASH,
+				"Failed to split the bucket %d\n", ret);
+			return ret;
+		}
+	}
+
+	if (HLIST_DATA_CUSTOM_EXTRA_DATA & pos->d.flags) {
+		*data = pos->d.extra_data;
+		h->custom_entries--;
+	} else if (HLIST_DATA_IS_ALLOCATED(&pos->d)) {
+		rte_free(pos->d.extra_data);
+	}
+	LIST_REMOVE(pos, next);
+	rte_free(pos);
+	he->entries_in_bucket--;
+
+	return 0;
+}
+
+int
+rte_hlist_del_key(struct rte_hlist_table *h, const void *key)
+{
+	RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+
+	return __rte_hlist_del_key_with_hash(h, key, rte_hlist_hash(h, key));
+}
+
+int
+rte_hlist_del_key_return_data(struct rte_hlist_table *h,
+	const void *key, void **data)
+{
+	RETURN_IF_TRUE(((h == NULL) || (key == NULL) || (data == NULL)),
+			-EINVAL);
+
+	return __rte_hlist_del_key_with_hash_return_data(h, key,
+			rte_hlist_hash(h, key), data);
+}
+
+int
+rte_hlist_del_entry_fast_return_data(struct rte_hlist_table *h,
+	struct rte_hlist_data_element *de, void **data)
+{
+	RETURN_IF_TRUE(((h == NULL) || (key == NULL) || (data == NULL)),
+			-EINVAL);
+
+	return __rte_hlist_del_entry_fast_return_data(h, de, data);
+}
+
+struct rte_hlist_data_element *
+rte_hlist_lookup_with_hash(struct rte_hlist_table *h,
+	const void *key, hash_sig_t sig)
+{
+	struct rte_hlist_node_entry *p;
+	int idx;
+
+	idx = __rte_hlist_find_node_entry(h, key, sig, &p);
+	if (idx < 0)
+		return NULL;
+
+	return &p->d;
+}
+
+struct rte_hlist_data_element *
+rte_hlist_lookup(struct rte_hlist_table *h, const void *key)
+{
+	RETURN_IF_TRUE_ERRNO(((h == NULL) || (key == NULL)), NULL, -EINVAL);
+
+	return rte_hlist_lookup_with_hash(h, key, rte_hlist_hash(h, key));
+}
+
+static inline int
+__rte_hlist_clear_all_entries(struct rte_hlist_table *h, uint8_t force)
+{
+	uint32_t size;
+	uint32_t i;
+	struct rte_hlist_head_entry *he;
+	struct rte_hlist_node_entry *pos;
+	struct rte_hlist_node_entry *tp;
+
+	if (h == NULL) {
+		rte_errno = EINVAL;
+		return -rte_errno;
+	}
+
+	if ((force == FALSE) && (h->custom_entries) && (h->free_func == NULL)) {
+		rte_errno = EBUSY;
+		return -rte_errno;
+	}
+
+	size = h->bucket_mask + 1;
+	for (i = 0; i < size; i++) {
+		he = &h->t[i];
+		if (he->entries_in_bucket > 0) {
+			LIST_MOVE_TO_NEW_HEAD(&he->head, &he->head, next);
+			LIST_FOREACH_SAFE(pos, &he->head, next, tp) {
+				if (HLIST_DATA_IS_ALLOCATED(&pos->d)) {
+					rte_free(pos->d.extra_data);
+				} else if (HLIST_DATA_CUSTOM_EXTRA_DATA &
+							pos->d.flags) {
+					h->custom_entries--;
+					if (h->free_func != NULL)
+						h->free_func(
+							pos->d.extra_data);
+				}
+				LIST_REMOVE(pos, next);
+				rte_free(pos);
+				he->entries_in_bucket--;
+			}
+		}
+	}
+
+	return 0;
+}
+
+int
+rte_hlist_clear_all_entries_with_cb(struct rte_hlist_table *h,
+	rte_hlist_free_fn fn)
+{
+	rte_hlist_free_fn saved_fn;
+	int ret;
+
+	RETURN_IF_TRUE((h == NULL), -EINVAL);
+	saved_fn = h->free_func;
+	h->free_func = fn;
+	ret = __rte_hlist_clear_all_entries(h, TRUE);
+	h->free_func = saved_fn;
+
+	return ret;
+}
+
+struct rte_hlist_table *
+rte_hlist_create(const struct rte_hlist_params *params)
+{
+	struct rte_hlist_table *ht = NULL;
+	struct rte_tailq_entry *te;
+	char hash_name[RTE_HLIST_NAMESIZE];
+	struct rte_hlist_list *hlist_list;
+	uint32_t table_size;
+
+	hlist_list = RTE_TAILQ_CAST(rte_hlist_tailq.head,
+				       rte_hlist_list);
+
+	/* Error checking of parameters. */
+	if ((!rte_is_power_of_2(params->entries)) ||
+			(!rte_is_power_of_2(params->entries_per_bucket)) ||
+			(params->entries == 0) ||
+			(params->entries_per_bucket == 0) ||
+			(params->entries_per_bucket > params->entries) ||
+			(params->entries > RTE_HLIST_ENTRIES_MAX) ||
+			(params->entries_per_bucket >
+				RTE_HLIST_ENTRIES_PER_BUCKET_MAX)) {
+		rte_errno = EINVAL;
+		return NULL;
+	}
+
+	snprintf(hash_name, sizeof(hash_name), "HLIST_%s", params->name);
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* guarantee there's no existing */
+	TAILQ_FOREACH(te, hlist_list, next) {
+		ht = (struct rte_hlist_table *)te->data;
+		if (strncmp(params->name, ht->name, RTE_HLIST_NAMESIZE) == 0)
+			break;
+	}
+	ht = NULL;
+	if (te != NULL) {
+		rte_errno = EEXIST;
+		goto exit;
+	}
+
+	te = rte_zmalloc("HLIST_TAILQ_ENTRY",
+			sizeof(struct rte_tailq_entry), 0);
+	if (te == NULL) {
+		RTE_LOG(ERR, HASH,
+			"Failed to allocate tailq entry for hlist\n");
+		goto exit;
+	}
+
+	/* Allocate memory for table. */
+	ht = (struct rte_hlist_table *)rte_zmalloc_socket(hash_name,
+			sizeof(struct rte_hlist_table), 0, params->socket_id);
+	if (ht == NULL) {
+		RTE_LOG(ERR, HASH, "Failed to allocate hlist table\n");
+		rte_free(te);
+		goto exit;
+	}
+
+	table_size = params->entries / params->entries_per_bucket;
+	ht->t = rte_zmalloc_socket(NULL,
+			sizeof(struct rte_hlist_head_entry) * table_size,
+			0, params->socket_id);
+	if (ht->t == NULL) {
+		RTE_LOG(ERR, HASH, "Failed to allocate hlist head table\n");
+		rte_free(te);
+		rte_free(ht);
+		goto exit;
+	}
+
+	/* Because HLIST_HEAD_INIT is to initialize the value to zero, skip it
+	 * here to accelerate the initialization stage.
+	 */
+
+	/* Set up hash table context. */
+	snprintf(ht->name, sizeof(ht->name), "%s", params->name);
+	ht->entries = params->entries;
+	ht->entries_per_bucket = params->entries_per_bucket;
+	/* since table size is a power of 2 */
+	ht->bucket_mask = table_size - 1;
+	ht->key_len = params->key_len;
+
+	if (params->hash_func != NULL) {
+		ht->hash_func = params->hash_func;
+		ht->init_val = params->init_val;
+	} else {
+		ht->hash_func = RTE_HLIST_FUNC_DEFAULT;
+		ht->init_val = RTE_HLIST_INIT_VAL_DEFAULT;
+	}
+
+	/* not mandatory for the free function */
+	ht->free_func = params->free_func;
+
+	te->data = (void *)ht;
+
+	TAILQ_INSERT_TAIL(hlist_list, te, next);
+
+exit:
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	return ht;
+}
+
+int rte_hlist_free(struct rte_hlist_table *h)
+{
+	struct rte_tailq_entry *te;
+	struct rte_hlist_list *hlist_list;
+
+	if (h == NULL) {
+		rte_errno = EINVAL;
+		return -rte_errno;
+	}
+
+	hlist_list = RTE_TAILQ_CAST(rte_hlist_tailq.head, rte_hlist_list);
+
+	rte_rwlock_write_lock(RTE_EAL_TAILQ_RWLOCK);
+
+	/* find out tailq entry */
+	TAILQ_FOREACH(te, hlist_list, next) {
+		if (te->data == (void *)h)
+			break;
+	}
+
+	if (te == NULL) {
+		rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+		rte_errno = EEXIST;
+		return -rte_errno;
+	}
+
+	TAILQ_REMOVE(hlist_list, te, next);
+
+	rte_rwlock_write_unlock(RTE_EAL_TAILQ_RWLOCK);
+
+	(void)__rte_hlist_clear_all_entries(h, TRUE);
+	rte_free(h);
+	rte_free(te);
+
+	return 0;
+}
+
diff --git a/lib/librte_hash/rte_hlist.h b/lib/librte_hash/rte_hlist.h
new file mode 100644
index 0000000..8fd1b6a
--- /dev/null
+++ b/lib/librte_hash/rte_hlist.h
@@ -0,0 +1,563 @@
+/* SPDX-License-Identifier: BSD-3-Clause
+ * Copyright 2019 Mellanox Technologies, Ltd
+ */
+
+#ifndef _RTE_HLIST_H_
+#define _RTE_HLIST_H_
+
+/**
+ * @file
+ *
+ * RTE Hash List
+ */
+
+#include <stdint.h>
+#include <errno.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <rte_config.h>
+#ifndef RTE_HLIST_FUNC_DEFAULT
+#if defined(RTE_ARCH_X86) || defined(RTE_MACHINE_CPUFLAG_CRC32)
+#include <rte_hash_crc.h>
+/** Default hlist hash function if none is specified. */
+#define RTE_HLIST_FUNC_DEFAULT		rte_hash_crc
+#else
+#include <rte_jhash.h>
+#define RTE_HLIST_FUNC_DEFAULT		rte_jhash
+#endif
+#endif
+
+/* To enable the deletion when iterating the list */
+#ifndef LIST_FOREACH_SAFE
+#define LIST_FOREACH_SAFE(var, head, field, tvar)			\
+	for ((var) = ((head)->lh_first);				\
+		(var) && ((tvar) = ((var)->field.le_next), 1);		\
+		(var) = (tvar))
+#endif
+
+/* To move the whole list from one head to another */
+#define LIST_MOVE_TO_NEW_HEAD(new, old, field) do {			\
+	(new)->lh_first = (old)->lh_first;				\
+	if (((new)->lh_first) != NULL)					\
+		(new)->lh_first->field.le_prev = &(new)->lh_first;	\
+} while (/*CONSTCOND*/0)
+
+#ifndef FALSE
+#define FALSE 0
+#endif
+#ifndef TRUE
+#define TRUE 1
+#endif
+
+#ifndef RTE_HLIST_INIT_VAL_DEFAULT
+/** Initialising value used when calculating hash. */
+#define RTE_HLIST_INIT_VAL_DEFAULT	0xFFFFFFFF
+#endif
+
+/* Macro to enable/disable run-time checking of function parameters */
+#if defined(RTE_LIBRTE_HASH_DEBUG)
+#define RETURN_IF_TRUE(cond, retval) do {				\
+	if (cond)							\
+		return retval;						\
+} while (0)
+
+#define RETURN_IF_TRUE_ERRNO(cond, retval, err) do {			\
+		if (cond) {						\
+			rte_errno = err;				\
+			return retval;					\
+		}							\
+	} while (0)
+#else
+#define RETURN_IF_TRUE(cond, retval)
+#define RETURN_IF_TRUE_ERRNO(cond, retval, err)
+#endif
+
+/** Maximum size of string for naming the hlist table. */
+#define RTE_HLIST_NAMESIZE			32
+
+/** The maximum number of entries in the hlist table that is supported. */
+#define RTE_HLIST_ENTRIES_MAX			(1 << 24)
+
+/** The maximum number of entries in each list that is supported. */
+#define RTE_HLIST_ENTRIES_PER_BUCKET_MAX	128
+
+/** Calculate the previous mask before splitting */
+#define HLIST_CALC_PREVIOUS_BUCKET_MASK(v, s)	((((v)+1) >> (s)) - 1)
+
+/** Flag bits for the data stored */
+#define HLIST_DATA_NEW_ENTRY			(0x80000000)
+#define HLIST_DATA_CUSTOM_EXTRA_DATA		(0x40000000)
+#define HLIST_DATA_INLINE			(0x20000000)
+#define HLIST_DATA_ALLOC_WITH_SIZE(s)		\
+					(0x10000000 | ((0x0fffffff) & (s)))
+#define HLIST_DATA_IS_ALLOCATED(d)		(!!((d)->flags & 0x10000000))
+#define HLIST_DATA_NOT_EXIST			(0x00000000)
+
+/** Signature of key that is stored internally. */
+typedef uint32_t hash_sig_t;
+
+/** Type of function that can be used for calculating the hash value. */
+typedef uint32_t (*rte_hlist_calc_fn)(const void *key, uint32_t key_len,
+					uint32_t init_val);
+
+/** Type of function that is used to free the data from customer. */
+typedef void (*rte_hlist_free_fn)(void *p);
+
+/** Parameters used when creating hash list table. */
+struct rte_hlist_params {
+	const char *name;		/**< Name of the hash table. */
+	uint32_t entries;		/**< Total number of entries. */
+	uint32_t entries_per_bucket;	/**< Number of entries in a bucket. */
+	/**< Length of the key to be calcuated. */
+	uint32_t key_len;
+	int socket_id;			/**< Socket to allocate memory on. */
+	rte_hlist_calc_fn hash_func;	/**< The hash function to calcuate. */
+	/**< The function to free the custom data. */
+	rte_hlist_free_fn free_func;
+	uint32_t init_val;		/**< For initializing hash function. */
+};
+
+/** Data element structure for future use */
+struct rte_hlist_data_element {
+	/**< Union for data, pointer or inline */
+	union {
+		void *extra_data;
+		uint64_t v64;
+		uint32_t v32;
+		uint16_t v16;
+		uint8_t v8;
+	};
+	uint32_t sig;			/**< Calcuated hash value. */
+	uint32_t flags;			/**< Flag bits of the data store. */
+};
+
+/** Node element structure on the LIST of the link */
+struct rte_hlist_node_entry {
+	LIST_ENTRY(rte_hlist_node_entry) next;	/**< Next element pointer. */
+	/**< Data element inside this noed. */
+	struct rte_hlist_data_element d;
+	char key[];				/**< Copied and stored key. */
+};
+
+/** Head of all the nodes with the same hash value */
+struct rte_hlist_head_entry {
+	LIST_HEAD(, rte_hlist_node_entry) head;	/**< Head for each hash list. */
+	/**< Current items in the list. */
+	uint16_t entries_in_bucket;
+	/**< Shift number for extension */
+	uint16_t bucket_shift;
+};
+
+/** The hlist table structure. */
+struct rte_hlist_table {
+	char name[RTE_HLIST_NAMESIZE];	/**< Name of the hash. */
+	uint32_t entries;		/**< Total number of entries. */
+	uint32_t entries_per_bucket;	/**< Number of entries in a list. */
+	/**< Number of entries with data from customer. */
+	uint32_t custom_entries;
+	uint16_t key_len;		/**< Length of the key. */
+	/**< Shift number of the whole table. */
+	uint16_t bucket_shift;
+	/**< To find which list the key is in. */
+	uint32_t bucket_mask;
+	rte_hlist_calc_fn hash_func;	/**< The hash function to calcuate. */
+	/**< The function to free the custom data. */
+	rte_hlist_free_fn free_func;
+	uint32_t init_val;		/**< For initializing hash function. */
+	/**< Reserved for fast shrinking of the table. */
+	char *map;
+	/**< A flat and extendible table of all lists. */
+	struct rte_hlist_head_entry *t;
+};
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Calc a hash value by key.
+ * This operation is not multi-thread safe.
+ *
+ * @param h
+ *   Hlist table to look in.
+ * @param key
+ *   Key to calc.
+ * @return
+ *   - hash value
+ */
+__rte_experimental
+hash_sig_t
+rte_hlist_hash(const struct rte_hlist_table *h, const void *key);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Add a key to an existing hash list without data, or return the existing
+ * element associated with the key. This operation is not multi-thread safe
+ * and should only be called from one thread.
+ *
+ * @param h
+ *   Hlist table to add the key to.
+ * @param key
+ *   Key to add to the hlist table.
+ * @return
+ *   - NULL pointer if failed to add the key, check the variable rte_errno for
+ *     more error information.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_add_key(struct rte_hlist_table *h, const void *key);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Add a key to an existing hash list with customer data, or return the existing
+ * element associated with the key(data will be ignored). This operation is not
+ * multi-thread safe and should only be called from one thread.
+ *
+ * @param h
+ *   Hlist table to add the key to.
+ * @param key
+ *   Key to add to the hlist table.
+ * @param data
+ *   Customer data pointer, and it is the caller's responsibility not to release
+ *   it if the data area will be accessed later.
+ * @return
+ *   - NULL pointer if failed to add the key, check the variable rte_errno for
+ *     more error information.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_add_key_data(struct rte_hlist_table *h, const void *key, void *data);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Add a key to an existing hash list with customer data, or return the existing
+ * element associated with the key(data will be ignored). This operation is not
+ * multi-thread safe and should only be called from one thread.
+ *
+ * @param h
+ *   Hlist table to add the key to.
+ * @param key
+ *   Key to add to the hlist table.
+ * @param data
+ *   Customer data pointer, and it is the caller's responsibility not to release
+ *   it if the data area will be accessed later.
+ * @param len
+ *   The length of the customer's data.
+ * @param cus
+ *   The allocation attribute of the data. If yes, it is the customer's
+ *   responsibility to hold/release the data, or else, a copy of the data will
+ *   be held and the data pointer is free to release or re-use.
+ * @return
+ *   - NULL pointer if failed to add the key, check the variable rte_errno for
+ *     more error information.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_add_key_data_len(struct rte_hlist_table *h, const void *key,
+				void *data, uint16_t len, uint8_t cus);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Add a key to an existing hash list with pre-calculated hash signature and
+ * customer data, or return the existing element associated with the key(data
+ * will be ignored). This operation is not multi-thread safe and should only
+ * be called from one thread.
+ *
+ * @param h
+ *   Hlist table to add the key to.
+ * @param key
+ *   Key to add to the hlist table.
+ * @param sig
+ *   Precomputed hash value for 'key'.
+ * @param data
+ *   Customer data pointer, and it is the caller's responsibility not to release
+ *   it if the data area will be accessed later.
+ * @return
+ *   - NULL pointer if failed to add the key, check the variable rte_errno for
+ *     more error information.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_add_key_with_hash_data(struct rte_hlist_table *h, const void *key,
+				hash_sig_t sig, void *data);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Add a key to an existing hash list with pre-calculated hash signature and
+ * customer data, or return the existing element associated with the key(data
+ * will be ignored). This operation is not multi-thread safe and should only
+ * be called from one thread.
+ *
+ * @param h
+ *   Hlist table to add the key to.
+ * @param key
+ *   Key to add to the hlist table.
+ * @param sig
+ *   Precomputed hash value for 'key'.
+ * @param data
+ *   Customer data pointer.
+ * @param len
+ *   The length of the customer's data.
+ * @param cus
+ *   The allocation attribute of the data. If yes, it is the customer's
+ *   responsibility to hold/release the data, or else, a copy of the data will
+ *   be held and the data pointer is free to release or re-use.
+ * @return
+ *   - NULL pointer if failed to add the key, check the variable rte_errno for
+ *     more error information.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_add_key_with_hash_data_len(struct rte_hlist_table *h, const void *key,
+			hash_sig_t sig, void *data, uint16_t len, uint8_t cus);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Remove a key from an existing hlist table. This operation is not multi-thread
+ * safe and should only be called from one thread.
+ *
+ * @param h
+ *   Hlist table to remove the key from.
+ * @param key
+ *   Key to remove from the hlist table.
+ * @return
+ *   - -EINVAL if the parameters are invalid.
+ *   - -ENOMEM if failed to extend the lists head.
+ *   - -ENOENT if the key is not found.
+ *   - -EBUSY if there is custom data but without custom free fuction.
+ *   - zero for success.
+ */
+__rte_experimental
+int
+rte_hlist_del_key(struct rte_hlist_table *h, const void *key);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Remove a key from an existing hlist table, and return the data pointer to the
+ * customer if any but without trying to free it. This operation is not
+ * multi-thread safe and should only be called from one thread.
+ *
+ * @param h
+ *   Hlist table to remove the key from.
+ * @param key
+ *   Key to remove from the hlist table.
+ * @param data
+ *   Output containing a pointer to the data.
+ * @return
+ *   - -EINVAL if the parameters are invalid.
+ *   - -ENOMEM if failed to extend the lists head.
+ *   - -ENOENT if the key is not found.
+ *   - zero for success.
+ */
+__rte_experimental
+int
+rte_hlist_del_key_return_data(struct rte_hlist_table *h, const void *key,
+				void **data);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Remove an entry from an existing hlist table, and return the data pointer to
+ * the customer if any but without trying to free it. User should ensure the
+ * integrity of the entry. This operation is not multi-thread safe and should
+ * only be called from one thread.
+ *
+ * @param h
+ *   Hlist table to remove the key from.
+ * @param de
+ *   Data element to be removed from the hlist table.
+ * @param data
+ *   Output containing a pointer to the data.
+ * @return
+ *   - -EINVAL if the parameters are invalid.
+ *   - zero for success.
+ */
+__rte_experimental
+int
+rte_hlist_del_entry_fast_return_data(struct rte_hlist_table *h,
+			struct rte_hlist_data_element *de, void **data);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Find a key in the hlist table.
+ * This operation is not multi-thread safe.
+ *
+ * @param h
+ *   Hlist table to look in.
+ * @param key
+ *   Key to find.
+ * @return
+ *   - NULL if failed to search the key in the hlist. Check the rte_errno for
+ *     more error information.
+ *     -EINVAL if the parameters are invalid.
+ *     -ENOMEM if failed to extend the lists head.
+ *     -ENOENT if the key is not found.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_lookup(struct rte_hlist_table *h, const void *key);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Find a key in the hlist table.
+ * This operation is not multi-thread safe.
+ *
+ * @param h
+ *   Hlist table to look in.
+ * @param key
+ *   Key to find.
+ * @param sig
+ *   Precomputed hash value for 'key'.
+ * @return
+ *   - NULL if failed to search the key in the hlist. Check the rte_errno for
+ *     more error information.
+ *     -EINVAL if the parameters are invalid.
+ *     -ENOMEM if failed to extend the lists head.
+ *     -ENOENT if the key is not found.
+ *   - A data element pointer with useful information for future use.
+ */
+__rte_experimental
+struct rte_hlist_data_element *
+rte_hlist_lookup_with_hash(struct rte_hlist_table *h, const void *key,
+				hash_sig_t sig);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Check if the data entry is a new one.
+ * This operation is not multi-thread safe.
+ *
+ * @param d
+ *   Pointer to the data entry.
+ * @return
+ *   No is 0 and Yes is 1.
+ */
+__rte_experimental
+static inline uint32_t
+rte_hlist_entry_is_new(struct rte_hlist_data_element *d)
+{
+	return !!(d->flags & HLIST_DATA_NEW_ENTRY);
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Append customer data to the data element.
+ * This operation is not multi-thread safe.
+ *
+ * @param h
+ *   Hlist table to look in.
+ * @param d
+ *   Pointer to the data entry.
+ * @param data
+ *   Data address to be append.
+ * @return
+ *   - -EINVAL if the parameters are invalid.
+ *   - -EEXIST if there is alreay some data.
+ *   - 0 if succeed.
+ */
+__rte_experimental
+static inline int
+rte_hlist_entry_append_custom_data(struct rte_hlist_table *h,
+		struct rte_hlist_data_element *d, void *data)
+{
+	if ((h == NULL) || (d == NULL) || (data == NULL))
+		return -EINVAL;
+
+	if ((d->flags & (~HLIST_DATA_NEW_ENTRY)) != HLIST_DATA_NOT_EXIST)
+		return -EEXIST;
+
+	d->extra_data = data;
+	d->flags |= HLIST_DATA_CUSTOM_EXTRA_DATA;
+	h->custom_entries++;
+	return 0;
+}
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Create a new hlist table. This operation is not multi-thread safe.
+ *
+ * @param params
+ *	 Parameters used in creation of hlist table.
+ *
+ * @return
+ *	 Pointer to hlist table structure that is used in future hlist table
+ *	 operations, or NULL on error with error code set in rte_errno.
+ */
+__rte_experimental
+struct rte_hlist_table *
+rte_hlist_create(const struct rte_hlist_params *params);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Free all memory used by a hlist table. Note, this will force to try to
+ * release all the customer's data before it cleans the memories of the table.
+ *
+ * @param h
+ *   Hlist table to deallocate.
+ * @return
+ *   - 0 if succeed.
+ *   - -EINVAL if the parameters are invalid.
+ *   - -EEXIST if the hlist doesn't exist.
+ */
+__rte_experimental
+int rte_hlist_free(struct rte_hlist_table *h);
+
+/**
+ * @warning
+ * @b EXPERIMENTAL: this API may change without prior notice
+ *
+ * Free all entries in the hash list table, and the customer's data could be
+ * handled by the callback function (optional).
+ *
+ * @param h
+ *   Hlist table to deallocate.
+ * @param fn
+ *   Callback function for the customer data handling.
+ * @return
+ *   - 0 if succeed.
+ *   - -EINVAL if the parameters are invalid.
+ *   - -EBUSY if the hlist doesn't exist.
+ */
+__rte_experimental
+int rte_hlist_clear_all_entries_with_cb(struct rte_hlist_table *h,
+					rte_hlist_free_fn fn);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _RTE_HLIST_H_ */
-- 
1.8.3.1