[dpdk-dev] [PATCH 4/6] hash: add new functions rte_hash_rehash and rte_hash_reset

Pablo de Lara pablo.de.lara.guarch at intel.com
Fri Jun 5 16:33:22 CEST 2015


Added rehash function to be able to keep adding more entries,
when a key cannot be added, as a result of a loop
evicting entries infinitely.

Also added reset function to be able to empty the table,
without having to destroy and create it again.

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch at intel.com>
---
 lib/librte_hash/rte_hash.c           | 91 ++++++++++++++++++++++++++++++++++++
 lib/librte_hash/rte_hash.h           | 26 +++++++++++
 lib/librte_hash/rte_hash_version.map |  2 +
 3 files changed, 119 insertions(+)

diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c
index 9599413..0b7f543 100644
--- a/lib/librte_hash/rte_hash.c
+++ b/lib/librte_hash/rte_hash.c
@@ -301,6 +301,33 @@ rte_hash_free(struct rte_hash *h)
 	rte_free(te);
 }
 
+void
+rte_hash_reset(struct rte_hash *h)
+{
+	void *ptr;
+	unsigned i;
+	uint32_t num_buckets, bucket_size, tbl_size;
+
+	if (h == NULL)
+		return;
+
+	num_buckets = h->num_buckets;
+	bucket_size = align_size(sizeof(struct rte_hash_bucket), BUCKET_ALIGNMENT);
+	tbl_size = align_size(num_buckets * bucket_size,
+				  RTE_CACHE_LINE_SIZE);
+
+	memset(h->buckets, 0, tbl_size);
+	memset(h->key_store, 0, h->key_entry_size * h->entries);
+
+	/* clear the free ring */
+	while (rte_ring_dequeue(h->free_slots, &ptr) == 0)
+		rte_pause();
+
+	/* Repopulate the free slots ring. Entry zero is reserved for key misses */
+	for (i = 1; i < h->entries + 1; i++)
+		rte_ring_sp_enqueue(h->free_slots, (void *)((uintptr_t) i));
+}
+
 static inline int32_t
 run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, uint32_t key_idx,
 		uint64_t hash, uint64_t original_hash, const void *original_key)
@@ -396,6 +423,70 @@ run_cuckoo(const struct rte_hash *h, struct rte_hash_bucket *bkt, uint32_t key_i
 				original_hash, original_key);
 }
 
+int
+rte_hash_rehash(struct rte_hash *h, rte_hash_function hash_func,
+		uint32_t hash_func_init_val)
+{
+	uint32_t tbl_size, mem_size, bucket_size, hash_struct_size;
+	uint64_t hash;
+	struct rte_hash_bucket *bkt;
+	void *k;
+	struct rte_hash *sec_h;
+	uint32_t bucket_idx;
+	int32_t ret;
+	unsigned i, j;
+	unsigned num_entries = 0;
+
+	/* Create new table to reorganize the entries */
+	hash_struct_size = align_size(sizeof(struct rte_hash), RTE_CACHE_LINE_SIZE);
+	bucket_size = align_size(sizeof(struct rte_hash_bucket), BUCKET_ALIGNMENT);
+	tbl_size = align_size(h->num_buckets * bucket_size, RTE_CACHE_LINE_SIZE);
+	mem_size = hash_struct_size + tbl_size;
+
+	sec_h = (struct rte_hash *) rte_zmalloc_socket(NULL, mem_size,
+					RTE_CACHE_LINE_SIZE, h->socket_id);
+
+	memcpy(sec_h, h, hash_struct_size);
+	sec_h->buckets = (struct rte_hash_bucket *)((uint8_t *)sec_h + hash_struct_size);
+
+	/* Updates the primary hash function and/or its initial value to rehash */
+	sec_h->hash_func_init_val = hash_func_init_val;
+	if (hash_func != NULL)
+		sec_h->hash_func = hash_func;
+
+	for (i = 0; i < h->num_buckets; i++) {
+		for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) {
+			/* Check if entry in bucket is not empty */
+			if (h->buckets[i].signatures[j] != NULL_SIGNATURE) {
+				k = (char *)h->key_store +
+					h->buckets[i].key_idx[j] * h->key_entry_size;
+				/* Get new hash (with new initial value) */
+				hash = rte_hash_hash(sec_h, k);
+				bucket_idx = hash & sec_h->bucket_bitmask;
+				hash |= sec_h->sig_msb;
+				bkt = &sec_h->buckets[bucket_idx];
+				/* Add entry on secondary hash table */
+				ret = run_cuckoo(sec_h, bkt, h->buckets[i].key_idx[j],
+						hash, hash, k);
+				if (ret == -EAGAIN)
+					goto exit;
+				num_entries++;
+			}
+		}
+	}
+
+	/* Replace old table with the new table */
+	h->hash_func_init_val = hash_func_init_val;
+	if (hash_func != NULL)
+		sec_h->hash_func = hash_func;
+	memcpy(h->buckets, sec_h->buckets, tbl_size);
+	ret = 0;
+
+exit:
+	rte_free(sec_h);
+	return ret;
+}
+
 static inline int32_t
 __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key,
 						hash_sig_t sig)
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index b364a43..c92d935 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -168,6 +168,32 @@ void
 rte_hash_free(struct rte_hash *h);
 
 /**
+ * Changes the hash function and/or its initial value
+ * of the hash table and rehash it
+ * @param h
+ *   Hash table to rehash
+ * @param hash_function
+ *   Hash function to change (if NULL, hash function will not be changed)
+ * @param hash_func_init_val
+ *   Initial value to change in the current or new hash function
+ * @return
+ *   - 0 if success
+ *   - -EINVAL if the parameters are invalid
+ *   - -EAGAIN if rehash could not be performed
+ *   - -ENOMEM if there was not enough memory to resize
+ */
+int
+rte_hash_rehash(struct rte_hash *h, rte_hash_function hash_func, uint32_t hash_func_init_val);
+
+/**
+ * Reset all hash structure, by zeroing all entries
+ * @param h
+ *   Hash table to reset
+ */
+void
+rte_hash_reset(struct rte_hash *h);
+
+/**
  * Add a key to an existing hash table. This operation is not multi-thread safe
  * and should only be called from one thread.
  *
diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
index fd92def..0a78756 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -22,6 +22,8 @@ DPDK_2.1 {
 	global:
 
 	rte_hash_lookup_bulk_with_hash;
+	rte_hash_rehash;
+	rte_hash_reset;
 
 	local: *;
 } DPDK_2.0;
-- 
2.4.2



More information about the dev mailing list