[dpdk-dev] [PATCH] Make rte_hash struct internal - Cuckoo hash part 1

[dpdk-dev] [PATCH] Make rte_hash struct internal - Cuckoo hash part 1

[Pablo de Lara]

First part of the changes for new hash implementation.
This patch makes the current public rte_hash structure internal,
as it should not be inspected directly by any applications.

Pablo de Lara (1):
  hash: move rte_hash structure to C file and make it internal

 app/test/test_hash.c       |  6 +-----
 lib/librte_hash/rte_hash.c | 30 +++++++++++++++++++++++++++++-
 lib/librte_hash/rte_hash.h | 35 +++++------------------------------
 3 files changed, 35 insertions(+), 36 deletions(-)

-- 
2.4.2

[dpdk-dev] [PATCH] hash: move rte_hash structure to C file and make it internal

[Pablo de Lara]

rte_hash structure should not be a public structure,
and therefore it should be moved to the C file and be declared
as internal. rte_hash_hash implementation is also moved
to the C file, as it uses the structure.

This patch also removes part of a unit test that was checking
a field of the structure.

Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
---
 app/test/test_hash.c       |  6 +-----
 lib/librte_hash/rte_hash.c | 30 +++++++++++++++++++++++++++++-
 lib/librte_hash/rte_hash.h | 35 +++++------------------------------
 3 files changed, 35 insertions(+), 36 deletions(-)

diff --git a/app/test/test_hash.c b/app/test/test_hash.c
index 4ecb11b..4300de9 100644
--- a/app/test/test_hash.c
+++ b/app/test/test_hash.c
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -1110,10 +1110,6 @@ test_hash_creation_with_good_parameters(void)
 		printf("Creating hash with null hash_func failed\n");
 		return -1;
 	}
-	if (handle->hash_func == NULL) {
-		printf("Hash function should have been DEFAULT_HASH_FUNC\n");
-		return -1;
-	}
 
 	/* this test is trying to create a hash with the same name as previous one.
 	 * this should return a pointer to the hash we previously created.
diff --git a/lib/librte_hash/rte_hash.c b/lib/librte_hash/rte_hash.c
index 67dff5b..5100a75 100644
--- a/lib/librte_hash/rte_hash.c
+++ b/lib/librte_hash/rte_hash.c
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -92,6 +92,27 @@ EAL_REGISTER_TAILQ(rte_hash_tailq)
 /* The high bit is always set in real signatures */
 #define NULL_SIGNATURE          0
 
+struct rte_hash {
+	char name[RTE_HASH_NAMESIZE];	/**< Name of the hash. */
+	uint32_t entries;		/**< Total table entries. */
+	uint32_t bucket_entries;	/**< Bucket entries. */
+	uint32_t key_len;		/**< Length of hash key. */
+	rte_hash_function hash_func;	/**< Function used to calculate hash. */
+	uint32_t hash_func_init_val;	/**< Init value used by hash_func. */
+	uint32_t num_buckets;		/**< Number of buckets in table. */
+	uint32_t bucket_bitmask;	/**< Bitmask for getting bucket index
+							from hash signature. */
+	hash_sig_t sig_msb;	/**< MSB is always set in valid signatures. */
+	uint8_t *sig_tbl;	/**< Flat array of hash signature buckets. */
+	uint32_t sig_tbl_bucket_size;	/**< Signature buckets may be padded for
+					   alignment reasons, and this is the
+					   bucket size used by sig_tbl. */
+	uint8_t *key_tbl;	/**< Flat array of key value buckets. */
+	uint32_t key_tbl_key_size;	/**< Keys may be padded for alignment
+					   reasons, and this is the key size
+					   used	by key_tbl. */
+};
+
 /* Returns a pointer to the first signature in specified bucket. */
 static inline hash_sig_t *
 get_sig_tbl_bucket(const struct rte_hash *h, uint32_t bucket_index)
@@ -291,6 +312,13 @@ rte_hash_free(struct rte_hash *h)
 	rte_free(te);
 }
 
+hash_sig_t
+rte_hash_hash(const struct rte_hash *h, const void *key)
+{
+	/* calc hash result by key */
+	return h->hash_func(key, h->key_len, h->hash_func_init_val);
+}
+
 static inline int32_t
 __rte_hash_add_key_with_hash(const struct rte_hash *h,
 				const void *key, hash_sig_t sig)
diff --git a/lib/librte_hash/rte_hash.h b/lib/librte_hash/rte_hash.h
index 821a9d4..da0a00a 100644
--- a/lib/librte_hash/rte_hash.h
+++ b/lib/librte_hash/rte_hash.h
@@ -1,7 +1,7 @@
 /*-
  *   BSD LICENSE
  *
- *   Copyright(c) 2010-2014 Intel Corporation. All rights reserved.
+ *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
  *   All rights reserved.
  *
  *   Redistribution and use in source and binary forms, with or without
@@ -41,7 +41,6 @@
  */
 
 #include <stdint.h>
-#include <sys/queue.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -84,27 +83,8 @@ struct rte_hash_parameters {
 	int socket_id;			/**< NUMA Socket ID for memory. */
 };
 
-/** A hash table structure. */
-struct rte_hash {
-	char name[RTE_HASH_NAMESIZE];	/**< Name of the hash. */
-	uint32_t entries;		/**< Total table entries. */
-	uint32_t bucket_entries;	/**< Bucket entries. */
-	uint32_t key_len;		/**< Length of hash key. */
-	rte_hash_function hash_func;	/**< Function used to calculate hash. */
-	uint32_t hash_func_init_val;	/**< Init value used by hash_func. */
-	uint32_t num_buckets;		/**< Number of buckets in table. */
-	uint32_t bucket_bitmask;	/**< Bitmask for getting bucket index
-							from hash signature. */
-	hash_sig_t sig_msb;	/**< MSB is always set in valid signatures. */
-	uint8_t *sig_tbl;	/**< Flat array of hash signature buckets. */
-	uint32_t sig_tbl_bucket_size;	/**< Signature buckets may be padded for
-					   alignment reasons, and this is the
-					   bucket size used by sig_tbl. */
-	uint8_t *key_tbl;	/**< Flat array of key value buckets. */
-	uint32_t key_tbl_key_size;	/**< Keys may be padded for alignment
-					   reasons, and this is the key size
-					   used	by key_tbl. */
-};
+/** @internal A hash table structure. */
+struct rte_hash;
 
 /**
  * Create a new hash table.
@@ -262,7 +242,6 @@ int32_t
 rte_hash_lookup_with_hash(const struct rte_hash *h,
 				const void *key, hash_sig_t sig);
 
-
 /**
  * Calc a hash value by key. This operation is not multi-process safe.
  *
@@ -273,12 +252,8 @@ rte_hash_lookup_with_hash(const struct rte_hash *h,
  * @return
  *   - hash value
  */
-static inline hash_sig_t
-rte_hash_hash(const struct rte_hash *h, const void *key)
-{
-	/* calc hash result by key */
-	return h->hash_func(key, h->key_len, h->hash_func_init_val);
-}
+hash_sig_t
+rte_hash_hash(const struct rte_hash *h, const void *key);
 
 #define rte_hash_lookup_multi rte_hash_lookup_bulk
 /**
-- 
2.4.2

Re: [dpdk-dev] [PATCH] hash: move rte_hash structure to C file and make it internal

[Bruce Richardson]

On Wed, Jul 08, 2015 at 12:27:34PM +0100, Pablo de Lara wrote:
> rte_hash structure should not be a public structure,
> and therefore it should be moved to the C file and be declared
> as internal. rte_hash_hash implementation is also moved
> to the C file, as it uses the structure.
> 
> This patch also removes part of a unit test that was checking
> a field of the structure.
> 
> Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>

Irrespective of whether or not we change the underlying hash table implementation
this looks a good change to me. The rte_hash structure should not be used directly
by any applications - the APIs all take pointers to the structure,
so there should be no ABI breakage from this, I think.

Therefore:

Acked-by: Bruce Richardson <bruce.richardson@intel.com>

Re: [dpdk-dev] [PATCH] hash: move rte_hash structure to C file and make it internal

[Matthew Hall]

On Wed, Jul 08, 2015 at 02:21:42PM +0100, Bruce Richardson wrote:
> Irrespective of whether or not we change the underlying hash table implementation
> this looks a good change to me. The rte_hash structure should not be used directly
> by any applications - the APIs all take pointers to the structure,
> so there should be no ABI breakage from this, I think.
> 
> Therefore:
> 
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>

Hi guys,

There are places where this will be annoying on the app side.

A lot of rte_hash, rte_lpm*, rte_table, etc. don't provide methods to iterate 
whole structures with a callback function that includes the current structure 
node, and a user-data pointer.

This can make it real unpleasant when you want to walk through the structure 
and free a bunch of items it points to and so forth.

So if you're going to obfuscate things by censoring the structure contents 
then we'd really like to be sure they have a full set of CRUD operations and 
iteration support so one could manage the nodes individually and in bulk.

Matthew.

Re: [dpdk-dev] [PATCH] hash: move rte_hash structure to C file and make it internal

[Bruce Richardson]

On Wed, Jul 08, 2015 at 09:57:03AM -0700, Matthew Hall wrote:
> On Wed, Jul 08, 2015 at 02:21:42PM +0100, Bruce Richardson wrote:
> > Irrespective of whether or not we change the underlying hash table implementation
> > this looks a good change to me. The rte_hash structure should not be used directly
> > by any applications - the APIs all take pointers to the structure,
> > so there should be no ABI breakage from this, I think.
> > 
> > Therefore:
> > 
> > Acked-by: Bruce Richardson <bruce.richardson@intel.com>
> 
> Hi guys,
> 
> There are places where this will be annoying on the app side.
> 
> A lot of rte_hash, rte_lpm*, rte_table, etc. don't provide methods to iterate 
> whole structures with a callback function that includes the current structure 
> node, and a user-data pointer.
> 
> This can make it real unpleasant when you want to walk through the structure 
> and free a bunch of items it points to and so forth.
> 
> So if you're going to obfuscate things by censoring the structure contents 
> then we'd really like to be sure they have a full set of CRUD operations and 
> iteration support so one could manage the nodes individually and in bulk.
> 
> Matthew.

Thanks for the feedback Matthew. Can you suggest a function prototype for such
a walk operation that would make it useful for you. While we can keep the
hash structure public, I'd prefer if we could avoid it, as it makes making changes
hard due to ABI issues.

/Bruce

Re: [dpdk-dev] [PATCH] hash: move rte_hash structure to C file and make it internal

[Matthew Hall]

On Thu, Jul 09, 2015 at 09:12:23AM +0100, Bruce Richardson wrote:
> Thanks for the feedback Matthew. Can you suggest a function prototype for such
> a walk operation that would make it useful for you. While we can keep the
> hash structure public, I'd prefer if we could avoid it, as it makes making changes
> hard due to ABI issues.
> 
> /Bruce

Hi Bruce,

I understand about the ABI issues. Hence my suggestion of an iterator if the 
structs are opaque. The names could be something like these:

rte_hash_iterate(_safe)
rte_hash_foreach(_safe)

If required due to the implementation, the safe version would be similar to 
what's seen in BSD queue.h, where you can do a slower iteration that allows 
removing a current entry without corrupting the table or iterator.

Then the function would look something like this:

rte_hash_iterate(rte_hash_t* h, rte_hash_callback_t callback, void* data)
rte_hash_iterate(rte_hash_t* h, rte_hash_callback_t callback, void* data)
rte_hash_iterate(rte_hash_t* h, rte_hash_callback_t callback, void* data)

rte_hash_callback_t would be a typedef of a function pointer for a callback 
function, something like this on the function depending how it works inside 
the hash:

int application_hash_callback(void* key, void* value, void* data)
int application_hash_callback(void* key, rte_hash_entry_t* entry, void* data)
int application_hash_callback(void* key, void* key, void* value, void* data)

The data pointer will contain the same pointer passed to the iterator. If the 
iteration function returns non-zero, iteration could be discontinued, as the 
client code found what it wanted already.

Threading synchronization responsibility will fall on the client as before. 
The iterator should say if it's thread-safe for read-only, read-write, or 
unsafe for anything, etc.

Matthew.

Re: [dpdk-dev] [PATCH] hash: move rte_hash structure to C file and make it internal

[Thomas Monjalon]

2015-07-08 14:21, Bruce Richardson:
> On Wed, Jul 08, 2015 at 12:27:34PM +0100, Pablo de Lara wrote:
> > rte_hash structure should not be a public structure,
> > and therefore it should be moved to the C file and be declared
> > as internal. rte_hash_hash implementation is also moved
> > to the C file, as it uses the structure.
> > 
> > This patch also removes part of a unit test that was checking
> > a field of the structure.
> > 
> > Signed-off-by: Pablo de Lara <pablo.de.lara.guarch@intel.com>
> 
> Irrespective of whether or not we change the underlying hash table implementation
> this looks a good change to me. The rte_hash structure should not be used directly
> by any applications - the APIs all take pointers to the structure,
> so there should be no ABI breakage from this, I think.
> 
> Therefore:
> 
> Acked-by: Bruce Richardson <bruce.richardson@intel.com>

Applied, thanks