| Message ID | 1351450948-15618-10-git-send-email-levinsasha928@gmail.com |
|---|---|
| State | Not Applicable, archived |
| Delegated to: | David Miller |
| Headers | show |
* 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 (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
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
* 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
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
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) {
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(-)