Re: [dpdk-dev] [PATCH] hash table: add a bucket iterator function

["Wiles, Keith" <keith.wiles@intel.com>]

> 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