From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 7C3C66CC7 for ; Tue, 6 Sep 2016 21:33:48 +0200 (CEST) Received: from orsmga005.jf.intel.com ([10.7.209.41]) by fmsmga103.fm.intel.com with ESMTP; 06 Sep 2016 12:33:47 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.30,292,1470726000"; d="scan'208";a="5378584" Received: from sie-lab-214-036.ir.intel.com (HELO silpixa00394365.ir.intel.com) ([10.237.214.36]) by orsmga005.jf.intel.com with ESMTP; 06 Sep 2016 12:33:46 -0700 From: Pablo de Lara To: dev@dpdk.org Cc: bruce.richardson@intel.com, Byron Marohn , Saikrishna Edupuganti Date: Tue, 6 Sep 2016 20:34:02 +0100 Message-Id: <1473190444-120795-3-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 2.7.4 In-Reply-To: <1473190444-120795-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1472856999-31028-1-git-send-email-pablo.de.lara.guarch@intel.com> <1473190444-120795-1-git-send-email-pablo.de.lara.guarch@intel.com> Subject: [dpdk-dev] [PATCH v3 2/4] hash: reorganize bucket structure 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: Tue, 06 Sep 2016 19:33:49 -0000 From: Byron Marohn Move current signatures of all entries together in the bucket and same with all alternative signatures, instead of having current and alternative signatures together per entry in the bucket. This will be benefitial in the next commits, where a vectorized comparison will be performed, achieving better performance. Signed-off-by: Byron Marohn Signed-off-by: Saikrishna Edupuganti --- lib/librte_hash/rte_cuckoo_hash.c | 43 ++++++++++++++++++----------------- lib/librte_hash/rte_cuckoo_hash.h | 17 ++++---------- lib/librte_hash/rte_cuckoo_hash_x86.h | 20 ++++++++-------- 3 files changed, 37 insertions(+), 43 deletions(-) diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c index dd0290f..9d507b6 100644 --- a/lib/librte_hash/rte_cuckoo_hash.c +++ b/lib/librte_hash/rte_cuckoo_hash.c @@ -420,7 +420,7 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { /* Search for space in alternative locations */ - next_bucket_idx = bkt->signatures[i].alt & h->bucket_bitmask; + next_bucket_idx = bkt->sig_alt[i] & h->bucket_bitmask; next_bkt[i] = &h->buckets[next_bucket_idx]; for (j = 0; j < RTE_HASH_BUCKET_ENTRIES; j++) { if (next_bkt[i]->key_idx[j] == EMPTY_SLOT) @@ -433,8 +433,8 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) /* Alternative location has spare room (end of recursive function) */ if (i != RTE_HASH_BUCKET_ENTRIES) { - next_bkt[i]->signatures[j].alt = bkt->signatures[i].current; - next_bkt[i]->signatures[j].current = bkt->signatures[i].alt; + next_bkt[i]->sig_alt[j] = bkt->sig_current[i]; + next_bkt[i]->sig_current[j] = bkt->sig_alt[i]; next_bkt[i]->key_idx[j] = bkt->key_idx[i]; return i; } @@ -460,8 +460,8 @@ make_space_bucket(const struct rte_hash *h, struct rte_hash_bucket *bkt) */ bkt->flag[i] = 0; if (ret >= 0) { - next_bkt[i]->signatures[ret].alt = bkt->signatures[i].current; - next_bkt[i]->signatures[ret].current = bkt->signatures[i].alt; + next_bkt[i]->sig_alt[ret] = bkt->sig_current[i]; + next_bkt[i]->sig_current[ret] = bkt->sig_alt[i]; next_bkt[i]->key_idx[ret] = bkt->key_idx[i]; return i; } else @@ -543,8 +543,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, /* Check if key is already inserted in primary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (prim_bkt->signatures[i].current == sig && - prim_bkt->signatures[i].alt == alt_hash) { + if (prim_bkt->sig_current[i] == sig && + prim_bkt->sig_alt[i] == alt_hash) { k = (struct rte_hash_key *) ((char *)keys + prim_bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { @@ -563,8 +563,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, /* Check if key is already inserted in secondary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (sec_bkt->signatures[i].alt == sig && - sec_bkt->signatures[i].current == alt_hash) { + if (sec_bkt->sig_alt[i] == sig && + sec_bkt->sig_current[i] == alt_hash) { k = (struct rte_hash_key *) ((char *)keys + sec_bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { @@ -610,8 +610,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { /* Check if slot is available */ if (likely(prim_bkt->key_idx[i] == EMPTY_SLOT)) { - prim_bkt->signatures[i].current = sig; - prim_bkt->signatures[i].alt = alt_hash; + prim_bkt->sig_current[i] = sig; + prim_bkt->sig_alt[i] = alt_hash; prim_bkt->key_idx[i] = new_idx; break; } @@ -631,8 +631,8 @@ __rte_hash_add_key_with_hash(const struct rte_hash *h, const void *key, */ ret = make_space_bucket(h, prim_bkt); if (ret >= 0) { - prim_bkt->signatures[ret].current = sig; - prim_bkt->signatures[ret].alt = alt_hash; + prim_bkt->sig_current[ret] = sig; + prim_bkt->sig_alt[ret] = alt_hash; prim_bkt->key_idx[ret] = new_idx; if (h->add_key == ADD_KEY_MULTIWRITER) rte_spinlock_unlock(h->multiwriter_lock); @@ -706,7 +706,7 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in primary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->signatures[i].current == sig && + if (bkt->sig_current[i] == sig && bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); @@ -729,8 +729,8 @@ __rte_hash_lookup_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in secondary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->signatures[i].current == alt_hash && - bkt->signatures[i].alt == sig) { + if (bkt->sig_current[i] == alt_hash && + bkt->sig_alt[i] == sig) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); if (rte_hash_cmp_eq(key, k->key, h) == 0) { @@ -784,7 +784,8 @@ remove_entry(const struct rte_hash *h, struct rte_hash_bucket *bkt, unsigned i) unsigned lcore_id, n_slots; struct lcore_cache *cached_free_slots; - bkt->signatures[i].sig = NULL_SIGNATURE; + bkt->sig_current[i] = NULL_SIGNATURE; + bkt->sig_alt[i] = NULL_SIGNATURE; if (h->hw_trans_mem_support) { lcore_id = rte_lcore_id(); cached_free_slots = &h->local_free_slots[lcore_id]; @@ -822,7 +823,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in primary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->signatures[i].current == sig && + if (bkt->sig_current[i] == sig && bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); @@ -847,7 +848,7 @@ __rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, /* Check if key is in secondary location */ for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - if (bkt->signatures[i].current == alt_hash && + if (bkt->sig_current[i] == alt_hash && bkt->key_idx[i] != EMPTY_SLOT) { k = (struct rte_hash_key *) ((char *)keys + bkt->key_idx[i] * h->key_entry_size); @@ -956,8 +957,8 @@ lookup_stage2(unsigned idx, hash_sig_t prim_hash, hash_sig_t sec_hash, prim_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES; sec_hash_matches = 1 << RTE_HASH_BUCKET_ENTRIES; for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { - prim_hash_matches |= ((prim_hash == prim_bkt->signatures[i].current) << i); - sec_hash_matches |= ((sec_hash == sec_bkt->signatures[i].current) << i); + prim_hash_matches |= ((prim_hash == prim_bkt->sig_current[i]) << i); + sec_hash_matches |= ((sec_hash == sec_bkt->sig_current[i]) << i); } key_idx = prim_bkt->key_idx[__builtin_ctzl(prim_hash_matches)]; diff --git a/lib/librte_hash/rte_cuckoo_hash.h b/lib/librte_hash/rte_cuckoo_hash.h index 701531a..86471f7 100644 --- a/lib/librte_hash/rte_cuckoo_hash.h +++ b/lib/librte_hash/rte_cuckoo_hash.h @@ -151,17 +151,6 @@ struct lcore_cache { void *objs[LCORE_CACHE_SIZE]; /**< Cache objects */ } __rte_cache_aligned; -/* Structure storing both primary and secondary hashes */ -struct rte_hash_signatures { - union { - struct { - hash_sig_t current; - hash_sig_t alt; - }; - uint64_t sig; - }; -}; - /* Structure that stores key-value pair */ struct rte_hash_key { union { @@ -174,10 +163,14 @@ struct rte_hash_key { /** Bucket structure */ struct rte_hash_bucket { - struct rte_hash_signatures signatures[RTE_HASH_BUCKET_ENTRIES]; + hash_sig_t sig_current[RTE_HASH_BUCKET_ENTRIES]; + /* Includes dummy key index that always contains index 0 */ uint32_t key_idx[RTE_HASH_BUCKET_ENTRIES + 1]; + uint8_t flag[RTE_HASH_BUCKET_ENTRIES]; + + hash_sig_t sig_alt[RTE_HASH_BUCKET_ENTRIES]; } __rte_cache_aligned; /** A hash table structure. */ diff --git a/lib/librte_hash/rte_cuckoo_hash_x86.h b/lib/librte_hash/rte_cuckoo_hash_x86.h index e16d69c..494c160 100644 --- a/lib/librte_hash/rte_cuckoo_hash_x86.h +++ b/lib/librte_hash/rte_cuckoo_hash_x86.h @@ -54,8 +54,8 @@ rte_hash_cuckoo_insert_mw_tm(struct rte_hash_bucket *prim_bkt, for (i = 0; i < RTE_HASH_BUCKET_ENTRIES; i++) { /* Check if slot is available */ if (likely(prim_bkt->key_idx == EMPTY_SLOT)) { - prim_bkt->signatures[i].current = sig; - prim_bkt->signatures[i].alt = alt_hash; + prim_bkt->sig_current[i] = sig; + prim_bkt->sig_alt[i] = alt_hash; prim_bkt->key_idx[i] = new_idx; break; } @@ -101,7 +101,7 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h, prev_slot = curr_node->prev_slot; prev_alt_bkt_idx - = prev_bkt->signatures[prev_slot].alt + = prev_bkt->sig_alt[prev_slot] & h->bucket_bitmask; if (unlikely(&h->buckets[prev_alt_bkt_idx] @@ -113,10 +113,10 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h, * Cuckoo insert to move elements back to its * primary bucket if available */ - curr_bkt->signatures[curr_slot].alt = - prev_bkt->signatures[prev_slot].current; - curr_bkt->signatures[curr_slot].current = - prev_bkt->signatures[prev_slot].alt; + curr_bkt->sig_alt[curr_slot] = + prev_bkt->sig_current[prev_slot]; + curr_bkt->sig_current[curr_slot] = + prev_bkt->sig_alt[prev_slot]; curr_bkt->key_idx[curr_slot] = prev_bkt->key_idx[prev_slot]; @@ -125,8 +125,8 @@ rte_hash_cuckoo_move_insert_mw_tm(const struct rte_hash *h, curr_bkt = curr_node->bkt; } - curr_bkt->signatures[curr_slot].current = sig; - curr_bkt->signatures[curr_slot].alt = alt_hash; + curr_bkt->sig_current[curr_slot] = sig; + curr_bkt->sig_alt[curr_slot] = alt_hash; curr_bkt->key_idx[curr_slot] = new_idx; rte_xend(); @@ -178,7 +178,7 @@ rte_hash_cuckoo_make_space_mw_tm(const struct rte_hash *h, } /* Enqueue new node and keep prev node info */ - alt_bkt = &(h->buckets[curr_bkt->signatures[i].alt + alt_bkt = &(h->buckets[curr_bkt->sig_alt[i] & h->bucket_bitmask]); head->bkt = alt_bkt; head->prev = tail; -- 2.7.4