[dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its position

[dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its position

[Yari Adan Petralanda]

The function rte_hash_get_key_with_position is added in this patch.
As the position returned when adding a key is frequently used as an
offset into an array of user data, this function performs the operation
of retrieving a key given this offset.

A possible use case would be to delete a key from the hash table when
its entry in the array of data has certain value. For instance, the key
could be a flow 5-tuple, and the value stored in the array a time
stamp.

Signed-off-by: Juan Antonio Montesinos <juan.antonio.montesinos.delgado@ericsson.com>
Signed-off-by: Yari Adan Petralanda <yari.adan.petralanda@ericsson.com>
---
 app/test/test_hash.c                 | 42 ++++++++++++++++++++++++++++++++++++
 lib/librte_hash/rte_cuckoo_hash.c    | 20 +++++++++++++++++
 lib/librte_hash/rte_hash.h           | 18 ++++++++++++++++
 lib/librte_hash/rte_hash_version.map |  7 ++++++
 4 files changed, 87 insertions(+)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 7e41725..29abcd9 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -421,6 +421,46 @@ static int test_add_update_delete(void)
 }
 
 /*
+ * Sequence of operations for retrieving a key with its position
+ *
+ *  - create table
+ *  - add key
+ *  - get the key with its position: hit
+ *  - delete key
+ *  - try to get the deleted key: miss
+ *
+ */
+static int test_hash_get_key_with_position(void)
+{
+	struct rte_hash *handle = NULL;
+	int pos, expectedPos, result;
+	void *key;
+
+	ut_params.name = "hash_get_key_w_pos";
+	handle = rte_hash_create(&ut_params);
+	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
+
+	pos = rte_hash_add_key(handle, &keys[0]);
+	print_key_info("Add", &keys[0], pos);
+	RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
+	expectedPos = pos;
+
+	result = rte_hash_get_key_with_position(handle, pos, &key);
+	RETURN_IF_ERROR(result != 0, "error retrieving a key");
+
+	pos = rte_hash_del_key(handle, &keys[0]);
+	print_key_info("Del", &keys[0], pos);
+	RETURN_IF_ERROR(pos != expectedPos,
+			"failed to delete key (pos0=%d)", pos);
+
+	result = rte_hash_get_key_with_position(handle, pos, &key);
+	RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
+
+	rte_hash_free(handle);
+	return 0;
+}
+
+/*
  * Sequence of operations for find existing hash table
  *
  *  - create table
@@ -1442,6 +1482,8 @@ test_hash(void)
 		return -1;
 	if (test_hash_add_delete_jhash_3word() < 0)
 		return -1;
+	if (test_hash_get_key_with_position() < 0)
+		return -1;
 	if (test_hash_find_existing() < 0)
 		return -1;
 	if (test_add_update_delete() < 0)
diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
index 7b7d1f8..a3c9091 100644
--- a/lib/librte_hash/rte_cuckoo_hash.c
+++ b/lib/librte_hash/rte_cuckoo_hash.c
@@ -973,6 +973,26 @@ rte_hash_del_key(const struct rte_hash *h, const void *key)
 	return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
 }
 
+int
+rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
+			       void **key)
+{
+	RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
+
+	struct rte_hash_key *k, *keys = h->key_store;
+	k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
+				     h->key_entry_size);
+	*key = k->key;
+
+	if (position !=
+	    __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
+					NULL)) {
+		return -ENOENT;
+	}
+
+	return 0;
+}
+
 /* Lookup bulk stage 0: Prefetch input key */
 static inline void
 lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index 724315a..78af365 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -268,6 +268,24 @@ rte_hash_del_key(const struct rte_hash *h, const void *key);
 int32_t
 rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
 
+/**
+ * Find a key in the hash table given the position.
+ * This operation is multi-thread safe.
+ *
+ * @param h
+ *   Hash table to get the key from.
+ * @param position
+ *   Position returned when the key was inserted.
+ * @param key
+ *   Output containing a pointer to the key
+ * @return
+ *   - 0 if retrieved successfully
+ *   - EINVAL if the parameters are invalid.
+ *   - ENOENT if no valid key is found in the given position.
+ */
+int
+rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
+			       void **key);
 
 /**
  * Find a key-value pair in the hash table.
diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
index 4f25436..4237995 100644
--- a/lib/librte_hash/rte_hash_version.map
+++ b/lib/librte_hash/rte_hash_version.map
@@ -38,3 +38,10 @@ DPDK_2.2 {
 	rte_hash_set_cmp_func;
 
 } DPDK_2.1;
+
+DPDK_16.07 {
+	global:
+
+	rte_hash_get_key_with_position;
+
+}; DPDK_2.2
-- 
2.1.4

Re: [dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its position

[De Lara Guarch, Pablo]

Hi Yari,

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Yari Adan
> Petralanda
> Sent: Monday, July 04, 2016 10:00 AM
> To: dev@dpdk.org
> Subject: [dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its
> position
> 
> The function rte_hash_get_key_with_position is added in this patch.
> As the position returned when adding a key is frequently used as an
> offset into an array of user data, this function performs the operation
> of retrieving a key given this offset.
> 
> A possible use case would be to delete a key from the hash table when
> its entry in the array of data has certain value. For instance, the key
> could be a flow 5-tuple, and the value stored in the array a time
> stamp.
> 
> Signed-off-by: Juan Antonio Montesinos
> <juan.antonio.montesinos.delgado@ericsson.com>
> Signed-off-by: Yari Adan Petralanda <yari.adan.petralanda@ericsson.com>

Could you mention what you changed in this v3? We always add the changes that
we have made between versions, so reviewers know what you have changed.

Thanks,
Pablo

Re: [dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its position

[Yari Adan Petralanda]

Sorry, didn't mentioned the changes introduced in v3:

*) solves some tabs for whitespaces issues
*) references the right DPDK version
*) reduces the size of the rte_hash_create() argument in the unit tests

Thanks!!

On 07/04/2016 10:59 AM, Yari Adan Petralanda wrote:
> The function rte_hash_get_key_with_position is added in this patch.
> As the position returned when adding a key is frequently used as an
> offset into an array of user data, this function performs the operation
> of retrieving a key given this offset.
> 
> A possible use case would be to delete a key from the hash table when
> its entry in the array of data has certain value. For instance, the key
> could be a flow 5-tuple, and the value stored in the array a time
> stamp.
> 
> Signed-off-by: Juan Antonio Montesinos <juan.antonio.montesinos.delgado@ericsson.com>
> Signed-off-by: Yari Adan Petralanda <yari.adan.petralanda@ericsson.com>
> ---
>  app/test/test_hash.c                 | 42 ++++++++++++++++++++++++++++++++++++
>  lib/librte_hash/rte_cuckoo_hash.c    | 20 +++++++++++++++++
>  lib/librte_hash/rte_hash.h           | 18 ++++++++++++++++
>  lib/librte_hash/rte_hash_version.map |  7 ++++++
>  4 files changed, 87 insertions(+)
> 
> diff --git a/app/test/test_hash.c b/app/test/test_hash.c
> index 7e41725..29abcd9 100644
> --- a/app/test/test_hash.c
> +++ b/app/test/test_hash.c
> @@ -421,6 +421,46 @@ static int test_add_update_delete(void)
>  }
>  
>  /*
> + * Sequence of operations for retrieving a key with its position
> + *
> + *  - create table
> + *  - add key
> + *  - get the key with its position: hit
> + *  - delete key
> + *  - try to get the deleted key: miss
> + *
> + */
> +static int test_hash_get_key_with_position(void)
> +{
> +	struct rte_hash *handle = NULL;
> +	int pos, expectedPos, result;
> +	void *key;
> +
> +	ut_params.name = "hash_get_key_w_pos";
> +	handle = rte_hash_create(&ut_params);
> +	RETURN_IF_ERROR(handle == NULL, "hash creation failed");
> +
> +	pos = rte_hash_add_key(handle, &keys[0]);
> +	print_key_info("Add", &keys[0], pos);
> +	RETURN_IF_ERROR(pos < 0, "failed to add key (pos0=%d)", pos);
> +	expectedPos = pos;
> +
> +	result = rte_hash_get_key_with_position(handle, pos, &key);
> +	RETURN_IF_ERROR(result != 0, "error retrieving a key");
> +
> +	pos = rte_hash_del_key(handle, &keys[0]);
> +	print_key_info("Del", &keys[0], pos);
> +	RETURN_IF_ERROR(pos != expectedPos,
> +			"failed to delete key (pos0=%d)", pos);
> +
> +	result = rte_hash_get_key_with_position(handle, pos, &key);
> +	RETURN_IF_ERROR(result != -ENOENT, "non valid key retrieved");
> +
> +	rte_hash_free(handle);
> +	return 0;
> +}
> +
> +/*
>   * Sequence of operations for find existing hash table
>   *
>   *  - create table
> @@ -1442,6 +1482,8 @@ test_hash(void)
>  		return -1;
>  	if (test_hash_add_delete_jhash_3word() < 0)
>  		return -1;
> +	if (test_hash_get_key_with_position() < 0)
> +		return -1;
>  	if (test_hash_find_existing() < 0)
>  		return -1;
>  	if (test_add_update_delete() < 0)
> diff --git a/lib/librte_hash/rte_cuckoo_hash.c b/lib/librte_hash/rte_cuckoo_hash.c
> index 7b7d1f8..a3c9091 100644
> --- a/lib/librte_hash/rte_cuckoo_hash.c
> +++ b/lib/librte_hash/rte_cuckoo_hash.c
> @@ -973,6 +973,26 @@ rte_hash_del_key(const struct rte_hash *h, const void *key)
>  	return __rte_hash_del_key_with_hash(h, key, rte_hash_hash(h, key));
>  }
>  
> +int
> +rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
> +			       void **key)
> +{
> +	RETURN_IF_TRUE(((h == NULL) || (key == NULL)), -EINVAL);
> +
> +	struct rte_hash_key *k, *keys = h->key_store;
> +	k = (struct rte_hash_key *) ((char *) keys + (position + 1) *
> +				     h->key_entry_size);
> +	*key = k->key;
> +
> +	if (position !=
> +	    __rte_hash_lookup_with_hash(h, *key, rte_hash_hash(h, *key),
> +					NULL)) {
> +		return -ENOENT;
> +	}
> +
> +	return 0;
> +}
> +
>  /* Lookup bulk stage 0: Prefetch input key */
>  static inline void
>  lookup_stage0(unsigned *idx, uint64_t *lookup_mask,
> diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
> index 724315a..78af365 100644
> --- a/lib/librte_hash/rte_hash.h
> +++ b/lib/librte_hash/rte_hash.h
> @@ -268,6 +268,24 @@ rte_hash_del_key(const struct rte_hash *h, const void *key);
>  int32_t
>  rte_hash_del_key_with_hash(const struct rte_hash *h, const void *key, hash_sig_t sig);
>  
> +/**
> + * Find a key in the hash table given the position.
> + * This operation is multi-thread safe.
> + *
> + * @param h
> + *   Hash table to get the key from.
> + * @param position
> + *   Position returned when the key was inserted.
> + * @param key
> + *   Output containing a pointer to the key
> + * @return
> + *   - 0 if retrieved successfully
> + *   - EINVAL if the parameters are invalid.
> + *   - ENOENT if no valid key is found in the given position.
> + */
> +int
> +rte_hash_get_key_with_position(const struct rte_hash *h, const int32_t position,
> +			       void **key);
>  
>  /**
>   * Find a key-value pair in the hash table.
> diff --git a/lib/librte_hash/rte_hash_version.map b/lib/librte_hash/rte_hash_version.map
> index 4f25436..4237995 100644
> --- a/lib/librte_hash/rte_hash_version.map
> +++ b/lib/librte_hash/rte_hash_version.map
> @@ -38,3 +38,10 @@ DPDK_2.2 {
>  	rte_hash_set_cmp_func;
>  
>  } DPDK_2.1;
> +
> +DPDK_16.07 {
> +	global:
> +
> +	rte_hash_get_key_with_position;
> +
> +}; DPDK_2.2
> 

Re: [dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its position

[De Lara Guarch, Pablo]

> -----Original Message-----
> From: dev [mailto:dev-bounces@dpdk.org] On Behalf Of Yari Adan
> Petralanda
> Sent: Monday, July 04, 2016 10:00 AM
> To: dev@dpdk.org
> Subject: [dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its
> position
> 
> The function rte_hash_get_key_with_position is added in this patch.
> As the position returned when adding a key is frequently used as an
> offset into an array of user data, this function performs the operation
> of retrieving a key given this offset.
> 
> A possible use case would be to delete a key from the hash table when
> its entry in the array of data has certain value. For instance, the key
> could be a flow 5-tuple, and the value stored in the array a time
> stamp.
> 
> Signed-off-by: Juan Antonio Montesinos
> <juan.antonio.montesinos.delgado@ericsson.com>
> Signed-off-by: Yari Adan Petralanda <yari.adan.petralanda@ericsson.com>

Acked-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>

Re: [dpdk-dev] [PATCH v3] hash: new function to retrieve a key given its position

[Thomas Monjalon]

> > The function rte_hash_get_key_with_position is added in this patch.
> > As the position returned when adding a key is frequently used as an
> > offset into an array of user data, this function performs the operation
> > of retrieving a key given this offset.
> > 
> > A possible use case would be to delete a key from the hash table when
> > its entry in the array of data has certain value. For instance, the key
> > could be a flow 5-tuple, and the value stored in the array a time
> > stamp.
> > 
> > Signed-off-by: Juan Antonio Montesinos
> > <juan.antonio.montesinos.delgado@ericsson.com>
> > Signed-off-by: Yari Adan Petralanda <yari.adan.petralanda@ericsson.com>
> 
> Acked-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>

Applied, thanks