From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mta112.f1.k8.com.br (mta112.f1.k8.com.br [187.73.32.184]) by dpdk.org (Postfix) with ESMTP id 698843256 for ; Thu, 6 Sep 2018 16:28:52 +0200 (CEST) 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 5136A8001C; Thu, 6 Sep 2018 14:28:43 +0000 (UTC) X-DKIM: OpenDKIM Filter v2.6.8 smtpz.f1.k8.com.br 5136A8001C DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=digirati.com.br; s=default; t=1536244129; bh=s0d6dpTa2/QpKVG1srz8ho/noS23CDNdZh1xu8mZmgI=; h=Subject:To:From:Date:Feedback-ID; b=vuqcP4cJhJOl4EVQv5Pdh90rWXv2QeQEzm9yagsolEHOCAhN4l7MfJeg5TyNCfh1O 9b7M1CpMJtLBL6Qi6qw/Gqdzj7m1EmVAMzJdNmFZdHTSQWVmA9y+1VHDtmO7umngFF tNCX2BZknJ2CmO4pIbp4oKrAp4e0jSKY3s9BobbY= DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=k8.com.br; s=default; t=1536244129; bh=s0d6dpTa2/QpKVG1srz8ho/noS23CDNdZh1xu8mZmgI=; h=Subject:To:From:Date:Feedback-ID; b=b8WbAWmJdbS1xHydcLp3/JPXexhtxfqEuiAc94M3BHzOg8+2J4jsGNSoNyp16OJlX VtHohGeqZTb5HUWlvuH4pT2JDhFX20LzOAVqVzjtoLOs2IppNF+x3U4X/VPfpKkE+8 XJ9TOpQblj5b6COVMecJbUEnzneJLPY/P6WjacSY= To: Honnappa Nagarahalli , Qiaobin Fu , "bruce.richardson@intel.com" , "pablo.de.lara.guarch@intel.com" Cc: "dev@dpdk.org" , "doucette@bu.edu" , "keith.wiles@intel.com" , "sameh.gobriel@intel.com" , "charlie.tai@intel.com" , "stephen@networkplumber.org" , nd , "yipeng1.wang@intel.com" References: <20180831165101.20026-1-qiaobinf@bu.edu> <8ff2d6be-df5b-51cb-95e9-f227127b7d45@digirati.com.br> From: Michel Machado Organization: Digirati Internet LTDA. Message-ID: Date: Thu, 6 Sep 2018 10:28: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-HN-S: bWljaGVsQGRpZ2lyYXRpLmNvbS5icg== X-HN-R: eWlwZW5nMS53YW5nQGludGVsLmNvbSxuZEBhcm0uY29tLHN0ZXBoZW5AbmV0d29ya3BsdW1iZXIub3JnLGNoYXJsaWUudGFpQGludGVsLmNvbSxzYW1laC5nb2JyaWVsQGludGVsLmNvbSxrZWl0aC53aWxlc0BpbnRlbC5jb20sZG91Y2V0dGVAYnUuZWR1LGRldkBkcGRrLm9yZyxwYWJsby5kZS5sYXJhLmd1YXJjaEBpbnRlbC5jb20sYnJ1Y2UucmljaGFyZHNvbkBpbnRlbC5jb20scWlhb2JpbmZAYnUuZWR1LEhvbm5hcHBhLk5hZ2FyYWhhbGxpQGFybS5jb20= Feedback-ID: MjAxODA5MDY=:bWljaGVsQGRpZ2lyYXRpLmNvbS5icg==:ZGlnaXJhdGkuY29tLmJy:k8networks X-Mailman-Approved-At: Fri, 07 Sep 2018 13:28:17 +0200 Subject: Re: [dpdk-dev] [PATCH v3] 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: Thu, 06 Sep 2018 14:28:52 -0000 On 09/05/2018 06:13 PM, Honnappa Nagarahalli wrote: >> + uint32_t next; >> + uint32_t total_entries; >> +}; >> This structure can be moved to rte_cuckoo_hash.h file. > > What's the purpose of moving this struct to a header file since it's only used in the C file rte_cuckoo_hash.c? > > This is to maintain consistency. For ex: 'struct queue_node', which is an internal structure, is kept in rte_cuckoo_hash.h Okay. We'll move it there. >> +int32_t >> +rte_hash_iterator_init(const struct rte_hash *h, >> + struct rte_hash_iterator_state *state) { >> + struct rte_hash_iterator_istate *__state; >> '__state' can be replaced by 's'. >> >> + >> + RETURN_IF_TRUE(((h == NULL) || (state == NULL)), -EINVAL); >> + >> + __state = (struct rte_hash_iterator_istate *)state; >> + __state->h = h; >> + __state->next = 0; >> + __state->total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES; >> + >> + return 0; >> +} >> IMO, creating this API can be avoided if the initialization is handled in 'rte_hash_iterate' function. The cost of doing this is very trivial (one extra 'if' statement) in 'rte_hash_iterate' function. It will help keep the number of APIs to minimal. > > Applications would have to initialize struct rte_hash_iterator_state *state before calling rte_hash_iterate() anyway. Why not initializing the fields of a state only once? > > My concern is about creating another API for every iterator API. You have a valid point on saving cycles as this API applies for data plane. Have you done any performance benchmarking with and without this API? May be we can guide our decision based on that. It's not just about creating one init function for each iterator because an iterator may have a couple of init functions. For example, someone may eventually find useful to add another init function for the conflicting-entry iterator that we are advocating in this patch. A possibility would be for this new init function to use the key of the new entry instead of its signature to initialize the state. Similar to what is already done in rte_hash_lookup*() functions. In spite of possibly having multiple init functions, there will be a single iterator function. About the performance benchmarking, the current API only requites applications to initialize a single 32-bit integer. But with the adoption of a struct for the state, the initialization will grow to 64 bytes. >> int32_t >> -rte_hash_iterate(const struct rte_hash *h, const void **key, void >> **data, uint32_t *next) >> +rte_hash_iterate( >> + struct rte_hash_iterator_state *state, const void **key, void >> +**data) >> >> IMO, as suggested above, do not store 'struct rte_hash *h' in 'struct rte_hash_iterator_state'. Instead, change the API definition as follows: >> rte_hash_iterate(const struct rte_hash *h, const void **key, void >> **data, struct rte_hash_iterator_state *state) >> >> This will help keep the API signature consistent with existing APIs. >> >> This is an ABI change. Please take a look at https://doc.dpdk.org/guides/contributing/versioning.html. > > The ABI will change in a way or another, so why not going for a single state instead of requiring parameters that are already needed for the initialization of the state? > > Are there any cost savings we can achieve by keeping the 'h' in the iterator state? There's a tiny cost saving: avoiding to push that parameter in the execution stack every time the iterator will get another entry. However, the reason I find more important is to make impossible to introduce a bug in the code. Consider a function that is dealing with two hash tables and two iterators. Without asking for the hash table to make progress in an iterator, it's impossible to mix up hash tables and iterator states. There's even the possibility that an iterator doesn't need the hash table after its initialization. This would be an *unlikely* case, but consider an iterator that only returns a couple of entries. It could cache those entries during initialization. >> /* Calculate bucket and index of current iterator */ >> - bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES; >> - idx = *next % RTE_HASH_BUCKET_ENTRIES; >> + bucket_idx = __state->next / RTE_HASH_BUCKET_ENTRIES; >> + idx = __state->next % RTE_HASH_BUCKET_ENTRIES; >> >> /* If current position is empty, go to the next one */ >> - while (h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) { >> - (*next)++; >> + while (__state->h->buckets[bucket_idx].key_idx[idx] == EMPTY_SLOT) { >> + __state->next++; >> /* End of table */ >> - if (*next == total_entries) >> + if (__state->next == __state->total_entries) >> return -ENOENT; >> - bucket_idx = *next / RTE_HASH_BUCKET_ENTRIES; >> - idx = *next % RTE_HASH_BUCKET_ENTRIES; >> + bucket_idx = __state->next / RTE_HASH_BUCKET_ENTRIES; >> + idx = __state->next % RTE_HASH_BUCKET_ENTRIES; >> } >> - __hash_rw_reader_lock(h); >> + __hash_rw_reader_lock(__state->h); >> /* Get position of entry in key table */ >> - position = h->buckets[bucket_idx].key_idx[idx]; >> - next_key = (struct rte_hash_key *) ((char *)h->key_store + >> - position * h->key_entry_size); >> + position = __state->h->buckets[bucket_idx].key_idx[idx]; >> + 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; >> >> - __hash_rw_reader_unlock(h); >> + __hash_rw_reader_unlock(__state->h); >> >> /* Increment iterator */ >> - (*next)++; >> + __state->next++; >> This comment is not related to this change, it is better to place this inside the lock. > > Even though __state->next does not depend on the lock? > > It depends on if this API needs to be multi-thread safe. Interestingly, the documentation does not say it is multi-thread safe. If it has to be multi-thread safe, then the state also needs to be protected. For ex: what happens if the user uses a global variable for the state? If an application needs to share an iterator state between threads, it has to have a synchronization mechanism for that as it would for any other shared variable. The lock above is allowing applications to share a hash table between threads, it has no semantic over anything else. >> diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h >> index 9e7d9315f..fdb01023e 100644 >> --- a/lib/librte_hash/rte_hash.h >> +++ b/lib/librte_hash/rte_hash.h >> @@ -14,6 +14,8 @@ >> #include >> #include >> >> +#include >> + >> #ifdef __cplusplus >> extern "C" { >> #endif >> @@ -64,6 +66,16 @@ struct rte_hash_parameters { >> /** @internal A hash table structure. */ struct rte_hash; >> >> +/** >> + * @warning >> + * @b EXPERIMENTAL: this API may change without prior notice. >> + * >> + * @internal A hash table iterator state structure. >> + */ >> +struct rte_hash_iterator_state { >> + uint8_t space[64]; >> I would call this 'state'. 64 can be replaced by 'RTE_CACHE_LINE_SIZE'. > > Okay. I think we should not replace 64 with RTE_CACHE_LINE_SIZE because the ABI would change based on the architecture for which it's compiled. [ ]'s Michel Machado