From: Pablo de Lara <pablo.de.lara.guarch@intel.com>
To: dev@dpdk.org
Subject: [PATCH 4/6] hash: add new functions rte_hash_rehash and rte_hash_reset
Date: Fri, 5 Jun 2015 15:33:22 +0100 [thread overview]
Message-ID: <1433514804-7075-5-git-send-email-pablo.de.lara.guarch@intel.com> (raw)
In-Reply-To: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com>
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@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
next prev parent reply other threads:[~2015-06-05 14:33 UTC|newest]
Thread overview: 92+ messages / expand[flat|nested] mbox.gz Atom feed top
2015-06-05 14:33 [PATCH 0/6] Cuckoo hash Pablo de Lara
2015-06-05 14:33 ` [PATCH 1/6] eal: add const in prefetch functions Pablo de Lara
2015-06-16 15:10 ` Bruce Richardson
2015-06-05 14:33 ` [PATCH 2/6] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-17 15:31 ` Bruce Richardson
2015-06-18 9:50 ` Bruce Richardson
2015-06-05 14:33 ` [PATCH 3/6] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-05 14:33 ` Pablo de Lara [this message]
2015-06-05 14:33 ` [PATCH 5/6] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-05 14:33 ` [PATCH 6/6] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-16 13:44 ` [PATCH 0/6] Cuckoo hash Thomas Monjalon
2015-06-16 21:44 ` De Lara Guarch, Pablo
2015-06-25 22:05 ` [PATCH v2 00/11] " Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-26 16:49 ` Stephen Hemminger
2015-06-28 22:23 ` De Lara Guarch, Pablo
2015-06-30 7:36 ` Stephen Hemminger
2015-07-10 10:39 ` Bruce Richardson
2015-06-25 22:05 ` [PATCH v2 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-25 22:05 ` [PATCH v2 11/11] doc: update hash documentation Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 00/11] Cuckoo hash Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-28 22:25 ` [PATCH v3 11/11] doc: update hash documentation Pablo de Lara
2015-07-08 23:23 ` [PATCH v3 00/11] Cuckoo hash Thomas Monjalon
2015-07-09 8:02 ` Bruce Richardson
2015-07-10 17:24 ` [PATCH v4 0/7] Cuckoo hash - part 3 of " Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 4/7] hash: add iterate function Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 17:24 ` [PATCH v4 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 20:52 ` [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 21:57 ` [PATCH v5 " Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 4/7] hash: add iterate function Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 21:57 ` [PATCH v5 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 22:52 ` [PATCH v5 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 23:30 ` [PATCH v6 " Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 4/7] hash: add iterate function Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 23:30 ` [PATCH v6 7/7] doc: update hash documentation Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-12 22:29 ` Thomas Monjalon
2015-07-13 16:11 ` Bruce Richardson
2015-07-13 16:14 ` Bruce Richardson
2015-07-13 16:20 ` Thomas Monjalon
2015-07-13 16:26 ` Bruce Richardson
2015-07-16 9:39 ` Tony Lu
2015-07-16 20:42 ` De Lara Guarch, Pablo
2015-07-17 3:34 ` Tony Lu
2015-07-17 7:34 ` De Lara Guarch, Pablo
2015-07-17 7:58 ` Tony Lu
2015-07-17 9:06 ` De Lara Guarch, Pablo
2015-07-17 14:39 ` Tony Lu
2015-07-11 0:18 ` [PATCH v7 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-12 22:16 ` Thomas Monjalon
2015-07-11 0:18 ` [PATCH v7 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-12 22:00 ` Thomas Monjalon
2015-07-11 0:18 ` [PATCH v7 4/7] hash: add iterate function Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-11 0:18 ` [PATCH v7 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-12 22:38 ` Thomas Monjalon
2015-07-11 0:18 ` [PATCH v7 7/7] doc: update hash documentation Pablo de Lara
2015-07-12 22:46 ` [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Thomas Monjalon
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1433514804-7075-5-git-send-email-pablo.de.lara.guarch@intel.com \
--to=pablo.de.lara.guarch@intel.com \
--cc=dev@dpdk.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.