Patchwork [v7,10/16] dlm: use new hashtable implementation

login
register
mail settings
Submitter Sasha Levin
Date Oct. 28, 2012, 7:02 p.m.
Message ID <1351450948-15618-10-git-send-email-levinsasha928@gmail.com>
Download mbox | patch
Permalink /patch/194737/
State Not Applicable
Delegated to: David Miller
Headers show

Comments

Sasha Levin - Oct. 28, 2012, 7:02 p.m.
Switch dlm to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the dlm.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
---
 fs/dlm/lowcomms.c | 47 +++++++++++++----------------------------------
 1 file changed, 13 insertions(+), 34 deletions(-)
Mathieu Desnoyers - Oct. 29, 2012, 12:46 p.m.
* Sasha Levin (levinsasha928@gmail.com) wrote:
[...]
> @@ -158,34 +159,21 @@ static int dlm_allow_conn;
>  static struct workqueue_struct *recv_workqueue;
>  static struct workqueue_struct *send_workqueue;
>  
> -static struct hlist_head connection_hash[CONN_HASH_SIZE];
> +static struct hlist_head connection_hash[CONN_HASH_BITS];
>  static DEFINE_MUTEX(connections_lock);
>  static struct kmem_cache *con_cache;
>  
>  static void process_recv_sockets(struct work_struct *work);
>  static void process_send_sockets(struct work_struct *work);
>  
> -
> -/* This is deliberately very simple because most clusters have simple
> -   sequential nodeids, so we should be able to go straight to a connection
> -   struct in the array */
> -static inline int nodeid_hash(int nodeid)
> -{
> -	return nodeid & (CONN_HASH_SIZE-1);
> -}

There is one thing I dislike about this change: you remove a useful
comment. It's good to be informed of the reason why a direct mapping
"value -> hash" without any dispersion function is preferred here.

Thanks,

Mathieu
Mathieu Desnoyers - Oct. 29, 2012, 1:07 p.m.
* Mathieu Desnoyers (mathieu.desnoyers@efficios.com) wrote:
> * Sasha Levin (levinsasha928@gmail.com) wrote:
> [...]
> > @@ -158,34 +159,21 @@ static int dlm_allow_conn;
> >  static struct workqueue_struct *recv_workqueue;
> >  static struct workqueue_struct *send_workqueue;
> >  
> > -static struct hlist_head connection_hash[CONN_HASH_SIZE];
> > +static struct hlist_head connection_hash[CONN_HASH_BITS];
> >  static DEFINE_MUTEX(connections_lock);
> >  static struct kmem_cache *con_cache;
> >  
> >  static void process_recv_sockets(struct work_struct *work);
> >  static void process_send_sockets(struct work_struct *work);
> >  
> > -
> > -/* This is deliberately very simple because most clusters have simple
> > -   sequential nodeids, so we should be able to go straight to a connection
> > -   struct in the array */
> > -static inline int nodeid_hash(int nodeid)
> > -{
> > -	return nodeid & (CONN_HASH_SIZE-1);
> > -}
> 
> There is one thing I dislike about this change: you remove a useful
> comment. It's good to be informed of the reason why a direct mapping
> "value -> hash" without any dispersion function is preferred here.

And now that I come to think of it: you're changing the behavior : you
will now use a dispersion function on the key, which goes against the
intent expressed in this comment.

It might be good to change hash_add(), hash_add_rcu(),
hash_for_each_possible*() key parameter for a "hash" parameter, and let
the caller provide the hash value computed by the function they like as
parameter, rather than enforcing hash_32/hash_64.

Thoughts ?

Thanks,

Mathieu
Sasha Levin - Oct. 29, 2012, 3:53 p.m.
On Mon, Oct 29, 2012 at 9:07 AM, Mathieu Desnoyers
<mathieu.desnoyers@efficios.com> wrote:
> * Mathieu Desnoyers (mathieu.desnoyers@efficios.com) wrote:
>> * Sasha Levin (levinsasha928@gmail.com) wrote:
>> [...]
>> > @@ -158,34 +159,21 @@ static int dlm_allow_conn;
>> >  static struct workqueue_struct *recv_workqueue;
>> >  static struct workqueue_struct *send_workqueue;
>> >
>> > -static struct hlist_head connection_hash[CONN_HASH_SIZE];
>> > +static struct hlist_head connection_hash[CONN_HASH_BITS];
>> >  static DEFINE_MUTEX(connections_lock);
>> >  static struct kmem_cache *con_cache;
>> >
>> >  static void process_recv_sockets(struct work_struct *work);
>> >  static void process_send_sockets(struct work_struct *work);
>> >
>> > -
>> > -/* This is deliberately very simple because most clusters have simple
>> > -   sequential nodeids, so we should be able to go straight to a connection
>> > -   struct in the array */
>> > -static inline int nodeid_hash(int nodeid)
>> > -{
>> > -   return nodeid & (CONN_HASH_SIZE-1);
>> > -}
>>
>> There is one thing I dislike about this change: you remove a useful
>> comment. It's good to be informed of the reason why a direct mapping
>> "value -> hash" without any dispersion function is preferred here.

Yes, I've removed the comment because it's no longer true with the patch :)

> And now that I come to think of it: you're changing the behavior : you
> will now use a dispersion function on the key, which goes against the
> intent expressed in this comment.

The comment gave us the information that nodeids are mostly
sequential, we no longer need to rely on that.

> It might be good to change hash_add(), hash_add_rcu(),
> hash_for_each_possible*() key parameter for a "hash" parameter, and let
> the caller provide the hash value computed by the function they like as
> parameter, rather than enforcing hash_32/hash_64.

Why? We already proved that hash_32() is more than enough as a hashing
function, why complicate things?

Even doing hash_32() on top of another hash is probably a good idea to
keep things simple.

Thanks,
Sasha
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Mathieu Desnoyers - Oct. 29, 2012, 4:07 p.m.
* Sasha Levin (levinsasha928@gmail.com) wrote:
> On Mon, Oct 29, 2012 at 9:07 AM, Mathieu Desnoyers
> <mathieu.desnoyers@efficios.com> wrote:
> > * Mathieu Desnoyers (mathieu.desnoyers@efficios.com) wrote:
> >> * Sasha Levin (levinsasha928@gmail.com) wrote:
> >> [...]
> >> > @@ -158,34 +159,21 @@ static int dlm_allow_conn;
> >> >  static struct workqueue_struct *recv_workqueue;
> >> >  static struct workqueue_struct *send_workqueue;
> >> >
> >> > -static struct hlist_head connection_hash[CONN_HASH_SIZE];
> >> > +static struct hlist_head connection_hash[CONN_HASH_BITS];
> >> >  static DEFINE_MUTEX(connections_lock);
> >> >  static struct kmem_cache *con_cache;
> >> >
> >> >  static void process_recv_sockets(struct work_struct *work);
> >> >  static void process_send_sockets(struct work_struct *work);
> >> >
> >> > -
> >> > -/* This is deliberately very simple because most clusters have simple
> >> > -   sequential nodeids, so we should be able to go straight to a connection
> >> > -   struct in the array */
> >> > -static inline int nodeid_hash(int nodeid)
> >> > -{
> >> > -   return nodeid & (CONN_HASH_SIZE-1);
> >> > -}
> >>
> >> There is one thing I dislike about this change: you remove a useful
> >> comment. It's good to be informed of the reason why a direct mapping
> >> "value -> hash" without any dispersion function is preferred here.
> 
> Yes, I've removed the comment because it's no longer true with the patch :)
> 
> > And now that I come to think of it: you're changing the behavior : you
> > will now use a dispersion function on the key, which goes against the
> > intent expressed in this comment.
> 
> The comment gave us the information that nodeids are mostly
> sequential, we no longer need to rely on that.

I'm fine with turning a direct + modulo mapping into a dispersed hash as
long as there are no underlying assumptions about sequentiality of value
accesses.

If the access pattern would happen to be typically sequential, then
adding dispersion could hurt performances significantly, turning a
frequent L1 access into a L2 access for instance.

> 
> > It might be good to change hash_add(), hash_add_rcu(),
> > hash_for_each_possible*() key parameter for a "hash" parameter, and let
> > the caller provide the hash value computed by the function they like as
> > parameter, rather than enforcing hash_32/hash_64.
> 
> Why? We already proved that hash_32() is more than enough as a hashing
> function, why complicate things?
> 
> Even doing hash_32() on top of another hash is probably a good idea to
> keep things simple.

All I'm asking is: have you made sure that this hash table is not
deliberately kept sequential (without dispersion) to accelerate specific
access patterns ? This should at least be documented in the changelog.

Thanks,

Mathieu


> 
> Thanks,
> Sasha
David Teigland - Oct. 29, 2012, 4:23 p.m.
On Mon, Oct 29, 2012 at 12:07:10PM -0400, Mathieu Desnoyers wrote:
> I'm fine with turning a direct + modulo mapping into a dispersed hash as
> long as there are no underlying assumptions about sequentiality of value
> accesses.
> 
> If the access pattern would happen to be typically sequential, then
> adding dispersion could hurt performances significantly, turning a
> frequent L1 access into a L2 access for instance.
  
> All I'm asking is: have you made sure that this hash table is not
> deliberately kept sequential (without dispersion) to accelerate specific
> access patterns ? This should at least be documented in the changelog.

It was not intentional.  I don't expect any benefit would be lost by
making it non-sequential.

--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Patch

diff --git a/fs/dlm/lowcomms.c b/fs/dlm/lowcomms.c
index 331ea4f..9f21774 100644
--- a/fs/dlm/lowcomms.c
+++ b/fs/dlm/lowcomms.c
@@ -55,6 +55,7 @@ 
 #include <net/sctp/sctp.h>
 #include <net/sctp/user.h>
 #include <net/ipv6.h>
+#include <linux/hashtable.h>
 
 #include "dlm_internal.h"
 #include "lowcomms.h"
@@ -62,7 +63,7 @@ 
 #include "config.h"
 
 #define NEEDED_RMEM (4*1024*1024)
-#define CONN_HASH_SIZE 32
+#define CONN_HASH_BITS 5
 
 /* Number of messages to send before rescheduling */
 #define MAX_SEND_MSG_COUNT 25
@@ -158,34 +159,21 @@  static int dlm_allow_conn;
 static struct workqueue_struct *recv_workqueue;
 static struct workqueue_struct *send_workqueue;
 
-static struct hlist_head connection_hash[CONN_HASH_SIZE];
+static struct hlist_head connection_hash[CONN_HASH_BITS];
 static DEFINE_MUTEX(connections_lock);
 static struct kmem_cache *con_cache;
 
 static void process_recv_sockets(struct work_struct *work);
 static void process_send_sockets(struct work_struct *work);
 
-
-/* This is deliberately very simple because most clusters have simple
-   sequential nodeids, so we should be able to go straight to a connection
-   struct in the array */
-static inline int nodeid_hash(int nodeid)
-{
-	return nodeid & (CONN_HASH_SIZE-1);
-}
-
 static struct connection *__find_con(int nodeid)
 {
-	int r;
 	struct hlist_node *h;
 	struct connection *con;
 
-	r = nodeid_hash(nodeid);
-
-	hlist_for_each_entry(con, h, &connection_hash[r], list) {
+	hash_for_each_possible(connection_hash, con, h, list, nodeid)
 		if (con->nodeid == nodeid)
 			return con;
-	}
 	return NULL;
 }
 
@@ -196,7 +184,6 @@  static struct connection *__find_con(int nodeid)
 static struct connection *__nodeid2con(int nodeid, gfp_t alloc)
 {
 	struct connection *con = NULL;
-	int r;
 
 	con = __find_con(nodeid);
 	if (con || !alloc)
@@ -206,8 +193,7 @@  static struct connection *__nodeid2con(int nodeid, gfp_t alloc)
 	if (!con)
 		return NULL;
 
-	r = nodeid_hash(nodeid);
-	hlist_add_head(&con->list, &connection_hash[r]);
+	hash_add(connection_hash, &con->list, nodeid);
 
 	con->nodeid = nodeid;
 	mutex_init(&con->sock_mutex);
@@ -235,11 +221,8 @@  static void foreach_conn(void (*conn_func)(struct connection *c))
 	struct hlist_node *h, *n;
 	struct connection *con;
 
-	for (i = 0; i < CONN_HASH_SIZE; i++) {
-		hlist_for_each_entry_safe(con, h, n, &connection_hash[i], list){
-			conn_func(con);
-		}
-	}
+	hash_for_each_safe(connection_hash, i, h, n, con, list)
+		conn_func(con);
 }
 
 static struct connection *nodeid2con(int nodeid, gfp_t allocation)
@@ -262,12 +245,10 @@  static struct connection *assoc2con(int assoc_id)
 
 	mutex_lock(&connections_lock);
 
-	for (i = 0 ; i < CONN_HASH_SIZE; i++) {
-		hlist_for_each_entry(con, h, &connection_hash[i], list) {
-			if (con->sctp_assoc == assoc_id) {
-				mutex_unlock(&connections_lock);
-				return con;
-			}
+	hash_for_each(connection_hash, i, h, con, list) {
+		if (con->sctp_assoc == assoc_id) {
+			mutex_unlock(&connections_lock);
+			return con;
 		}
 	}
 	mutex_unlock(&connections_lock);
@@ -1638,7 +1619,7 @@  static void free_conn(struct connection *con)
 	close_connection(con, true);
 	if (con->othercon)
 		kmem_cache_free(con_cache, con->othercon);
-	hlist_del(&con->list);
+	hash_del(&con->list);
 	kmem_cache_free(con_cache, con);
 }
 
@@ -1667,10 +1648,8 @@  int dlm_lowcomms_start(void)
 {
 	int error = -EINVAL;
 	struct connection *con;
-	int i;
 
-	for (i = 0; i < CONN_HASH_SIZE; i++)
-		INIT_HLIST_HEAD(&connection_hash[i]);
+	hash_init(connection_hash);
 
 	init_local();
 	if (!dlm_local_count) {