From: Pablo de Lara <pablo.de.lara.guarch@intel.com>
To: dev@dpdk.org
Subject: [dpdk-dev] [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 [dpdk-dev] [PATCH 0/6] Cuckoo hash Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 1/6] eal: add const in prefetch functions Pablo de Lara
2015-06-16 15:10 ` Bruce Richardson
2015-06-05 14:33 ` [dpdk-dev] [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 ` [dpdk-dev] [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 ` [dpdk-dev] [PATCH 5/6] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-05 14:33 ` [dpdk-dev] [PATCH 6/6] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-16 13:44 ` [dpdk-dev] [PATCH 0/6] Cuckoo hash Thomas Monjalon
2015-06-16 21:44 ` De Lara Guarch, Pablo
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 00/11] " Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [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 ` [dpdk-dev] [PATCH v2 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-25 22:05 ` [dpdk-dev] [PATCH v2 11/11] doc: update hash documentation Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 00/11] Cuckoo hash Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 01/11] eal: add const in prefetch functions Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 02/11] hash: move rte_hash structure to C file and make it internal Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 03/11] test/hash: enhance hash unit tests Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 04/11] test/hash: rename new hash perf unit test back to original name Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 05/11] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 06/11] hash: add new lookup_bulk_with_hash function Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 07/11] hash: add new function rte_hash_reset Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 08/11] hash: add new functionality to store data in hash table Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 09/11] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 10/11] doc: announce ABI change of librte_hash Pablo de Lara
2015-06-28 22:25 ` [dpdk-dev] [PATCH v3 11/11] doc: update hash documentation Pablo de Lara
2015-07-08 23:23 ` [dpdk-dev] [PATCH v3 00/11] Cuckoo hash Thomas Monjalon
2015-07-09 8:02 ` Bruce Richardson
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of " Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 4/7] hash: add iterate function Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 17:24 ` [dpdk-dev] [PATCH v4 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 20:52 ` [dpdk-dev] [PATCH v4 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 " Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 4/7] hash: add iterate function Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 21:57 ` [dpdk-dev] [PATCH v5 7/7] doc: update hash documentation Pablo de Lara
2015-07-10 22:52 ` [dpdk-dev] [PATCH v5 0/7] Cuckoo hash - part 3 of Cuckoo hash Bruce Richardson
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 " Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 1/7] hash: replace existing hash library with cuckoo hash implementation Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 2/7] hash: add new function rte_hash_reset Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 3/7] hash: add new functionality to store data in hash table Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 4/7] hash: add iterate function Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 6/7] doc: announce ABI change of librte_hash Pablo de Lara
2015-07-10 23:30 ` [dpdk-dev] [PATCH v6 7/7] doc: update hash documentation Pablo de Lara
2015-07-11 0:18 ` [dpdk-dev] [PATCH v7 0/7] Cuckoo hash - part 3 of Cuckoo hash Pablo de Lara
2015-07-11 0:18 ` [dpdk-dev] [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 ` [dpdk-dev] [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 ` [dpdk-dev] [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 ` [dpdk-dev] [PATCH v7 4/7] hash: add iterate function Pablo de Lara
2015-07-11 0:18 ` [dpdk-dev] [PATCH v7 5/7] MAINTAINERS: claim responsability for hash library Pablo de Lara
2015-07-11 0:18 ` [dpdk-dev] [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 ` [dpdk-dev] [PATCH v7 7/7] doc: update hash documentation Pablo de Lara
2015-07-12 22:46 ` [dpdk-dev] [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 a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).