From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by dpdk.org (Postfix) with ESMTP id 875285A50 for ; Fri, 5 Jun 2015 16:33:27 +0200 (CEST) Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by fmsmga102.fm.intel.com with ESMTP; 05 Jun 2015 07:33:26 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,559,1427785200"; d="scan'208";a="503280431" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by FMSMGA003.fm.intel.com with ESMTP; 05 Jun 2015 07:33:25 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t55EXOB5003760 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t55EXObF007137 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t55EXOVU007133 for dev@dpdk.org; Fri, 5 Jun 2015 15:33:24 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Fri, 5 Jun 2015 15:33:22 +0100 Message-Id: <1433514804-7075-5-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 In-Reply-To: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH 4/6] hash: add new functions rte_hash_rehash and rte_hash_reset X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 05 Jun 2015 14:33:28 -0000 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 --- 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