From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mta123.f1.k8.com.br (mta123.f1.k8.com.br [187.73.32.199]) by dpdk.org (Postfix) with ESMTP id 974BE235 for ; Fri, 17 Aug 2018 15:34:51 +0200 (CEST) X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-DKIM: OpenDKIM Filter v2.6.8 smtpz.f1.k8.com.br 3F47B600F6 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=digirati.com.br; s=default; t=1534512889; bh=TJ7TA3UMI7d+E9tHh8n1w05h1j6BFwMAa1P2GaBxlwI=; h=Subject:To:Cc:References:From:Date:In-Reply-To; b=dxTqTEIVd/8kJyS5p4CEXG8uNUi2MPhqEWrovYR5q85AJUISMbx59Su14BLHkZAk5 T1vNqgdSXuP1d68WHFntT57TqNz1ZW32B8d4IhIqbJWi3/wyHoSrUIVZXEIs7UzLMw HV5f115dKaDcMCJ6XcwpKbGjXDQTrtOJ8eG+cV2c= X-HN-R: bmRAYXJtLmNvbQ== X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: c3RlcGhlbkBuZXR3b3JrcGx1bWJlci5vcmc= X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: Y2hhcmxpZS50YWlAaW50ZWwuY29t X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: c2FtZWguZ29icmllbEBpbnRlbC5jb20= X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: a2VpdGgud2lsZXNAaW50ZWwuY29t X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: eWlwZW5nMS53YW5nQGludGVsLmNvbQ== X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: ZG91Y2V0dGVAYnUuZWR1 X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: ZGV2QGRwZGsub3Jn X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: cGFibG8uZGUubGFyYS5ndWFyY2hAaW50ZWwuY29t X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: YnJ1Y2UucmljaGFyZHNvbkBpbnRlbC5jb20= X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: cWlhb2JpbmZAYnUuZWR1 X-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: aG9ubmFwcGEubmFnYXJhaGFsbGlAYXJtLmNvbQ== Received: from [192.168.1.4] (pool-173-48-214-200.bstnma.fios.verizon.net [173.48.214.200]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtpz.f1.k8.com.br (Postfix) with ESMTPSA id 3F47B600F6; Fri, 17 Aug 2018 13:34:43 +0000 (UTC) To: Honnappa Nagarahalli , "Fu, Qiaobin" , "Richardson, Bruce" , "De Lara Guarch, Pablo" Cc: "dev@dpdk.org" , "Doucette, Cody, Joseph" , "Wang, Yipeng1" , "Wiles, Keith" , "Gobriel, Sameh" , "Tai, Charlie" , Stephen Hemminger , nd References: From: Michel Machado Organization: Digirati Internet LTDA. Message-ID: <5e809298-ee0e-f03f-e83a-59b764e3a9b8@digirati.com.br> Date: Fri, 17 Aug 2018 09:34:41 -0400 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Language: en-US Content-Transfer-Encoding: 7bit X-Mailman-Approved-At: Tue, 21 Aug 2018 22:23:55 +0200 Subject: Re: [dpdk-dev] [PATCH v2] hash table: add an iterator over conflicting entries X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 17 Aug 2018 13:34:53 -0000 On 08/16/2018 10:33 PM, Honnappa Nagarahalli wrote: > +/* Get the primary bucket index given the precomputed hash value. */ > +static inline uint32_t rte_hash_get_primary_bucket(const struct > +rte_hash *h, hash_sig_t sig) { > + return sig & h->bucket_bitmask; > +} > + > +/* Get the secondary bucket index given the precomputed hash value. */ > +static inline uint32_t rte_hash_get_secondary_bucket(const struct > +rte_hash *h, hash_sig_t sig) { > + return rte_hash_secondary_hash(sig) & h->bucket_bitmask; } > + > IMO, to keep the code consistent, we do not need to have the above 2 functions. Ok. > +int32_t __rte_experimental > +rte_hash_iterate_conflict_entries(struct rte_conflict_iterator_state *state, > + const void **key, const void **data) > +{ > + struct rte_hash_iterator_conflict_entries_state *__state; > + > + RETURN_IF_TRUE(((state == NULL) || (key == NULL) || > + (data == NULL)), -EINVAL); > + > + __state = (struct rte_hash_iterator_conflict_entries_state *)state; > + > + while (__state->vnext < RTE_HASH_BUCKET_ENTRIES * 2) { > + uint32_t bidx = (__state->vnext < RTE_HASH_BUCKET_ENTRIES) ? > + __state->primary_bidx : __state->secondary_bidx; > + uint32_t next = __state->vnext & (RTE_HASH_BUCKET_ENTRIES - 1); > + uint32_t position = __state->h->buckets[bidx].key_idx[next]; > + struct rte_hash_key *next_key; > + /* > + * The test below is unlikely because this iterator is meant > + * to be used after a failed insert. > + * */ > + if (unlikely(position == EMPTY_SLOT)) > + goto next; > + > + /* Get the entry in key table. */ > + next_key = (struct rte_hash_key *) ( > + (char *)__state->h->key_store + > + position * __state->h->key_entry_size); > + /* Return key and data. */ > + *key = next_key->key; > + *data = next_key->pdata; > + > +next: > + /* Increment iterator. */ > + __state->vnext++; > + > + if (likely(position != EMPTY_SLOT)) > + return position - 1; > + } > + > + return -ENOENT; > +} > > > I think, we can make this API similar to 'rte_hash_iterate'. I suggest the following API signature: > > int32_t > rte_hash_iterate_conflict_entries (const struct rte_hash *h, const void **key, void **data, hash_sig_t sig, uint32_t *next) The goal of our interface is to support changing the underlying hash table algorithm without requiring changes in applications. As Yipeng1 Wang exemplified in the discussion of the first version of this patch, "in future, rte_hash may use three hash functions, or as I mentioned each bucket may have an additional linked list or even a second level hash table, or if the hopscotch hash replaces cuckoo hash as the new algorithm." These new algorithms may require more state than sig and next can efficiently provide in order to browse the conflicting entries. > I also suggest to change the API name to ' rte_hash_iterate_bucket_entries' - 'bucket' is a well understood term in the context of hash algorithms. It's a matter of semantics here. rte_hash_iterate_conflict_entries() may cross more than one bucket. In fact, the first version of this patch tried to do exactly that, but it exposes the underlying algorithm. In addition, future algorithms may stretch what is being browsed even further. > Do we also need to have 'rte_hash_iterate_conflict_entries_with_hash' API? I may have not understood the question. We are already working with the hash (i.e. sig). Did you mean something else? > diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h index f71ca9fbf..7ecb6a7eb 100644 > --- a/lib/librte_hash/rte_hash.h > +++ b/lib/librte_hash/rte_hash.h > @@ -61,6 +61,11 @@ struct rte_hash_parameters { > /** @internal A hash table structure. */ struct rte_hash; > > +/** @internal A hash table conflict iterator state structure. */ struct > +rte_conflict_iterator_state { > + uint8_t space[64]; > +}; > + > > The size depends on the current size of the state, which is subject to change with the algorithm used. We chose a size that should be robust for any future underlying algorithm. Do you have a suggestion on how to go about it? We chose to have a simple struct to enable applications to allocate a state as a local variable and avoid a memory allocation. [ ]'s Michel Machado