DPDK patches and discussions
 help / color / mirror / Atom feed
From: Michel Machado <michel@digirati.com.br>
To: Honnappa Nagarahalli <Honnappa.Nagarahalli@arm.com>,
	Qiaobin Fu <qiaobinf@bu.edu>,
	"bruce.richardson@intel.com" <bruce.richardson@intel.com>,
	"pablo.de.lara.guarch@intel.com" <pablo.de.lara.guarch@intel.com>
Cc: "dev@dpdk.org" <dev@dpdk.org>,
	"doucette@bu.edu" <doucette@bu.edu>,
	"keith.wiles@intel.com" <keith.wiles@intel.com>,
	"sameh.gobriel@intel.com" <sameh.gobriel@intel.com>,
	"charlie.tai@intel.com" <charlie.tai@intel.com>,
	"stephen@networkplumber.org" <stephen@networkplumber.org>,
	nd <nd@arm.com>,
	"yipeng1.wang@intel.com" <yipeng1.wang@intel.com>
Subject: Re: [dpdk-dev] [PATCH v3] hash table: add an iterator over conflicting entries
Date: Tue, 4 Sep 2018 15:36:54 -0400
Message-ID: <8ff2d6be-df5b-51cb-95e9-f227127b7d45@digirati.com.br> (raw)
In-Reply-To: <AM6PR08MB3672AAB871FD81B06EA0F37D980D0@AM6PR08MB3672.eurprd08.prod.outlook.com>

Hi Honnappa,

On 09/02/2018 06:05 PM, Honnappa Nagarahalli wrote:
> +/* istate stands for internal state. */ struct rte_hash_iterator_istate
> +{
> +	const struct rte_hash *h;
> This can be outside of this structure. This will help keep the API definitions consistent with existing APIs. Please see further comments below.

    Discussed later.

> +	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?

> +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?

>   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?

    Thank you for the link. We'll check how to proceed with the ABI change.

>   {
> +	struct rte_hash_iterator_istate *__state;
> '__state' can be replaced with 's'.

    Gaëtan Rivet has already pointed this out in his review of this 
version of our patch.

>   	uint32_t bucket_idx, idx, position;
>   	struct rte_hash_key *next_key;
>   
> -	RETURN_IF_TRUE(((h == NULL) || (next == NULL)), -EINVAL);
> +	RETURN_IF_TRUE(((state == NULL) || (key == NULL) ||
> +		(data == NULL)), -EINVAL);
> +
> +	__state = (struct rte_hash_iterator_istate *)state;
>   
> -	const uint32_t total_entries = h->num_buckets * RTE_HASH_BUCKET_ENTRIES;
>   	/* Out of bounds */
> -	if (*next >= total_entries)
> +	if (__state->next >= __state->total_entries)
>   		return -ENOENT;
>   
> 'if (__state->next == 0)' is required to avoid creating 'rte_hash_iterator_init' API.

    The argument to keep _init() is presented above in this email.

>   	/* 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?

>   	return position - 1;
>   }
> +
> +/* istate stands for internal state. */ struct
> +rte_hash_iterator_conflict_entries_istate {
> +	const struct rte_hash *h;
> This can be moved outside of this structure.

    Discussed earlier.

> +	uint32_t              vnext;
> +	uint32_t              primary_bidx;
> +	uint32_t              secondary_bidx;
> +};
> +
> +int32_t __rte_experimental
> +rte_hash_iterator_conflict_entries_init_with_hash(const struct rte_hash *h,
> +	hash_sig_t sig, struct rte_hash_iterator_state *state) {
> +	struct rte_hash_iterator_conflict_entries_istate *__state;
> +
> +	RETURN_IF_TRUE(((h == NULL) || (state == NULL)), -EINVAL);
> +
> +	__state = (struct rte_hash_iterator_conflict_entries_istate *)state;
> +	__state->h = h;
> +	__state->vnext = 0;
> +
> +	/* Get the primary bucket index given the precomputed hash value. */
> +	__state->primary_bidx = sig & h->bucket_bitmask;
> +	/* Get the secondary bucket index given the precomputed hash value. */
> +	__state->secondary_bidx =
> +		rte_hash_secondary_hash(sig) & h->bucket_bitmask;
> +
> +	return 0;
> +}
> IMO, as mentioned above, it is possible to avoid creating this API.

    Discussed earlier.

> +
> +int32_t __rte_experimental
> +rte_hash_iterate_conflict_entries(
> +	struct rte_hash_iterator_state *state, const void **key, void **data)
> Signature of this API can be changed as follows:
> rte_hash_iterate_conflict_entries(
> 	struct rte_hash *h, const void **key, void **data, struct rte_hash_iterator_state *state)

    Discussed earlier.

> +{
> +	struct rte_hash_iterator_conflict_entries_istate *__state;
> +
> +	RETURN_IF_TRUE(((state == NULL) || (key == NULL) ||
> +		(data == NULL)), -EINVAL);
> +
> +	__state = (struct rte_hash_iterator_conflict_entries_istate *)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);
> 
> take the reader lock before reading bucket entry

    Thanks for pointing this out. We are going to do so. The lock came 
in as we go through the versions of this patch.

> +		uint32_t position = __state->h->buckets[bidx].key_idx[next];
> +		struct rte_hash_key *next_key;
> +
> +		/* Increment iterator. */
> +		__state->vnext++;
> +
> +		/*
> +		 * The test below is unlikely because this iterator is meant
> +		 * to be used after a failed insert.
> +		 */
> +		if (unlikely(position == EMPTY_SLOT))
> +			continue;
> +
> +		/* 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;
> give the reader lock

    We'll do so.

> +
> +		return position - 1;
> +	}
> +
> +	return -ENOENT;
> +}
> 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 <stdint.h>
>   #include <stddef.h>
>   
> +#include <rte_compat.h>
> +
>   #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.

[ ]'s
Michel Machado

  reply	other threads:[~2018-09-04 19:37 UTC|newest]

Thread overview: 22+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-08-31 16:51 Qiaobin Fu
2018-08-31 22:53 ` Gaëtan Rivet
2018-09-04 18:46   ` Michel Machado
2018-09-02 22:05 ` Honnappa Nagarahalli
2018-09-04 19:36   ` Michel Machado [this message]
2018-09-05 22:13     ` Honnappa Nagarahalli
2018-09-06 14:28       ` Michel Machado
2018-09-12 20:37         ` Honnappa Nagarahalli
2018-09-20 19:50           ` Michel Machado
2018-09-04 18:55 ` Wang, Yipeng1
2018-09-04 19:07   ` Michel Machado
2018-09-04 19:51     ` Wang, Yipeng1
2018-09-04 20:26       ` Michel Machado
2018-09-04 20:57         ` Wang, Yipeng1
2018-09-05 17:52           ` Michel Machado
2018-09-05 20:27             ` Wang, Yipeng1
2018-09-06 13:34               ` Michel Machado
2018-10-09 19:29 ` [dpdk-dev] [PATCH v4 1/2] hash table: fix a bug in rte_hash_iterate() Qiaobin Fu
2018-10-09 19:29   ` [dpdk-dev] [PATCH v4 2/2] hash table: add an iterator over conflicting entries Qiaobin Fu
2018-10-10  2:54     ` Wang, Yipeng1
2018-10-10  1:55   ` [dpdk-dev] [PATCH v4 1/2] hash table: fix a bug in rte_hash_iterate() Wang, Yipeng1
  -- strict thread matches above, loose matches on Subject: below --
2018-08-30 15:56 [dpdk-dev] [PATCH v3] hash table: add an iterator over conflicting entries Qiaobin Fu

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=8ff2d6be-df5b-51cb-95e9-f227127b7d45@digirati.com.br \
    --to=michel@digirati.com.br \
    --cc=Honnappa.Nagarahalli@arm.com \
    --cc=bruce.richardson@intel.com \
    --cc=charlie.tai@intel.com \
    --cc=dev@dpdk.org \
    --cc=doucette@bu.edu \
    --cc=keith.wiles@intel.com \
    --cc=nd@arm.com \
    --cc=pablo.de.lara.guarch@intel.com \
    --cc=qiaobinf@bu.edu \
    --cc=sameh.gobriel@intel.com \
    --cc=stephen@networkplumber.org \
    --cc=yipeng1.wang@intel.com \
    /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

DPDK patches and discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror https://inbox.dpdk.org/dev/0 dev/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 dev dev/ https://inbox.dpdk.org/dev \
		dev@dpdk.org
	public-inbox-index dev

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://inbox.dpdk.org/inbox.dpdk.dev


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git