DPDK patches and discussions
 help / color / mirror / Atom feed
From: "Wiles, Keith" <keith.wiles@intel.com>
To: Qiaobin Fu <qiaobinf@bu.edu>
Cc: "Richardson, Bruce" <bruce.richardson@intel.com>,
	"De Lara Guarch, Pablo" <pablo.de.lara.guarch@intel.com>,
	"dev@dpdk.org" <dev@dpdk.org>,
	"michel@digirati.com.br" <michel@digirati.com.br>,
	"doucette@bu.edu" <doucette@bu.edu>
Subject: Re: [dpdk-dev] [PATCH] hash table: add a bucket iterator function
Date: Sun, 29 Jul 2018 13:17:09 +0000	[thread overview]
Message-ID: <5CCC4983-8B4F-480B-B6E1-3A01806BC416@intel.com> (raw)
In-Reply-To: <20180728174851.46422-1-qiaobinf@bu.edu>



> On Jul 28, 2018, at 12:48 PM, Qiaobin Fu <qiaobinf@bu.edu> wrote:
> 
> Function rte_hash_bucket_iterate() enables callers to
> incrementally iterate over the hash table bucket by bucket,
> so that it can avoid creating hiccups and thrashing the cache
> of the processor.
> 
> This patch mainly deals with cases in which
> the hash table is full and one needs to decide if the incoming
> entry is more valuable than the entries already in the hash table.
> 
> Signed-off-by: Qiaobin Fu <qiaobinf@bu.edu>
> Reviewed-by: Cody Doucette <doucette@bu.edu>
> Reviewed-by: Michel Machado <michel@digirati.com.br>
> ---
> lib/librte_hash/rte_cuckoo_hash.c    | 60 +++++++++++++++++++++++++
> lib/librte_hash/rte_hash.h           | 66 ++++++++++++++++++++++++++++
> lib/librte_hash/rte_hash_version.map |  4 ++
> 3 files changed, 130 insertions(+)
> 
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
> index a07543a29..2b90f3593 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -1160,3 +1160,63 @@ rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32
> 
> 	return position - 1;
> }
> +
> +int
> +rte_hash_get_num_buckets(struct rte_hash *h)
> +{
> +	RETURN_IF_TRUE((h == NULL), -EINVAL);
> +	return h->num_buckets;
> +}
> +
> +uint32_t
> +rte_hash_get_primary_bucket(const struct rte_hash *h, hash_sig_t sig)
> +{
> +	return sig & h->bucket_bitmask;
> +}
> +
> +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;
> +}

The above two functions should have the RETURN_IF_TRUE((h == NULL), -EINVAL); statements just like the first one.

> +
> +int32_t
> +rte_hash_bucket_iterate(const struct rte_hash *h,
> +	const void **key, void **data, uint32_t *bidx, uint32_t *next)
> +{
> +	uint32_t position;
> +	struct rte_hash_key *next_key;
> +
> +	RETURN_IF_TRUE(((h == NULL) || (key == NULL) || (data == NULL) ||
> +		(bidx == NULL) || (next == NULL)), -EINVAL);
> +
> +	/* Out of bounds. */
> +	if (*bidx >= h->num_buckets || *next >= RTE_HASH_BUCKET_ENTRIES)
> +		goto next_bucket;
> +
> +	/* If current position is empty, go to the next one. */
> +	while (h->buckets[*bidx].key_idx[*next] == EMPTY_SLOT) {
> +		(*next)++;
> +		/* End of bucket. */
> +		if (*next >= RTE_HASH_BUCKET_ENTRIES)
> +			goto next_bucket;
> +	}
> +
> +	/* Get position of entry in key table. */
> +	position = h->buckets[*bidx].key_idx[*next];
> +	next_key = (struct rte_hash_key *) ((char *)h->key_store +
> +				position * h->key_entry_size);
> +	/* Return key and data. */
> +	*key = next_key->key;
> +	*data = next_key->pdata;
> +
> +	/* Increment iterator. */
> +	(*next)++;
> +
> +	return position - 1;
> +
> +next_bucket:
> +	*bidx = (*bidx + 1) >= h->num_buckets ? 0 : *bidx + 1;
> +	*next = 0;

If this is an error case why are we setting *next to zero and incrementing *bidx ?
I would expect we should not change the values on an error because they cannot debug the values on return.

> +	return -ENOENT;
> +}
> diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
> index f71ca9fbf..329bf42d6 100644
> --- a/lib/librte_hash/rte_hash.h
> +++ b/lib/librte_hash/rte_hash.h
> @@ -94,6 +94,17 @@ rte_hash_create(const struct rte_hash_parameters *params);
>  */
> void rte_hash_set_cmp_func(struct rte_hash *h, rte_hash_cmp_eq_t func);
> 
> +/**
> + * Get the number of buckets in the hash table.
> + * @param h
> + *   Hash table for which the function queries.
> + * @return
> + *   The number of buckets in the hash table h.
> + *    - EINVAL - invalid parameter passed to function
> + */
> +int

Needs to change to ‘int __rte_experimental’

> +rte_hash_get_num_buckets(struct rte_hash *h);
> +
> /**
>  * Find an existing hash table object and return a pointer to it.
>  *
> @@ -261,6 +272,34 @@ int
> rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
> 			       void **key);
> 
> +/**
> + * Get the primary bucket index given the precomputed hash value.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + *   Hash table to get the key from.
> + * @param sig
> + *   Precomputed hash value.
> + * @return
> + *   The primary bucket index.

Comment the error case here.
> + */
> +uint32_t

Needs to change to ‘uint32_t __rte_experimental’
> +rte_hash_get_primary_bucket(const struct rte_hash *h, hash_sig_t sig);
> +
> +/**
> + * Get the secondary bucket index given the precomputed hash value.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + *   Hash table to get the key from.
> + * @param sig
> + *   Precomputed hash value.
> + * @return
> + *   The primary bucket index.

Comment the error case here.
> + */
> +uint32_t

Needs to change to ‘uint32_t __rte_experimental’
> +rte_hash_get_secondary_bucket(const struct rte_hash *h, hash_sig_t sig);
> +
> /**
>  * Find a key-value pair in the hash table.
>  * This operation is multi-thread safe.
> @@ -419,6 +458,33 @@ rte_hash_lookup_bulk(const struct rte_hash *h, const void **keys,
>  */
> int32_t
> rte_hash_iterate(const struct rte_hash *h, const void **key, void **data, uint32_t *next);
> +
> +/**
> + * Iterate through the buckets in hash table, returning key-value pairs.
> + *
> + * @param h
> + *   Hash table to iterate
> + * @param key
> + *   Output containing the key where current iterator
> + *   was pointing at
> + * @param data
> + *   Output containing the data associated with key.
> + *   Returns NULL if data was not stored.
> + * @param bidx
> + *   Pointer to the current bucket index. Should be 0 to start
> + *   iterating the hash table. Iterator is incremented after
> + *   RTE_HASH_BUCKET_ENTRIES calls of this function.

The wording of the last line seem odd to me, should the ‘of’ be removed?

> + * @param next
> + *   Pointer to iterator. Should be 0 to start iterating the bucket.
> + *   Iterator is incremented after each call of this function.
> + * @return
> + *   Position where key was stored, if successful.
> + *   - -EINVAL if the parameters are invalid.
> + *   - -ENOENT if end of the bucket.
> + */
> +int32_t

Needs to change to ‘int32_t __rte_experimental’ and why use ‘int32_t' when everywhere else we are using ‘int'?

> +rte_hash_bucket_iterate(const struct rte_hash *h,
> +	const void **key, void **data, uint32_t *bidx, uint32_t *next);

Should have a blank line here before the #ifdef.
> #ifdef __cplusplus
> }
> #endif
> diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
> index 52a2576f9..7d48f32c9 100644
> --- a/lib/librte_hash/rte_hash_version.map
> +++ b/lib/librte_hash/rte_hash_version.map
> @@ -15,6 +15,10 @@ DPDK_2.0 {
> 	rte_hash_lookup;
> 	rte_hash_lookup_bulk;
> 	rte_hash_lookup_with_hash;
> +	rte_hash_get_num_buckets;
> +	rte_hash_get_primary_bucket;
> +	rte_hash_get_secondary_bucket;
> +	rte_hash_bucket_iterate;

These must be added to a EXPERIMENTAL clause in the file and later you can remove the experimental indictor.

> 
> 	local: *;
> };
> -- 
> 2.17.1
> 

Regards,
Keith


  reply	other threads:[~2018-07-29 13:17 UTC|newest]

Thread overview: 10+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-07-28 17:48 Qiaobin Fu
2018-07-29 13:17 ` Wiles, Keith [this message]
     [not found]   ` <D2C4A16CA39F7F4E8E384D204491D7A66148250A@ORSMSX105.amr.corp.intel.com>
2018-07-31  6:09     ` Fu, Qiaobin
2018-07-31 14:57       ` Wiles, Keith
2018-07-31 15:32         ` Michel Machado
2018-08-01  1:40           ` Wang, Yipeng1
2018-08-01 12:57             ` Michel Machado
2018-08-03 15:24               ` Stephen Hemminger
2018-08-07 13:24                 ` Michel Machado
  -- strict thread matches above, loose matches on Subject: below --
2018-07-15 17:15 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=5CCC4983-8B4F-480B-B6E1-3A01806BC416@intel.com \
    --to=keith.wiles@intel.com \
    --cc=bruce.richardson@intel.com \
    --cc=dev@dpdk.org \
    --cc=doucette@bu.edu \
    --cc=michel@digirati.com.br \
    --cc=pablo.de.lara.guarch@intel.com \
    --cc=qiaobinf@bu.edu \
    /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
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).