linux-kernel - Re: [PATCH v7 10/16] dlm: use new hashtable implementation

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 29 Oct 2012 12:07:10 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	Sasha Levin <levinsasha928@...il.com>
Cc:	torvalds@...ux-foundation.org, tj@...nel.org,
	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
	linux-mm@...ck.org, paul.gortmaker@...driver.com,
	davem@...emloft.net, rostedt@...dmis.org, mingo@...e.hu,
	ebiederm@...ssion.com, aarcange@...hat.com, ericvh@...il.com,
	netdev@...r.kernel.org, josh@...htriplett.org,
	eric.dumazet@...il.com, axboe@...nel.dk, agk@...hat.com,
	dm-devel@...hat.com, neilb@...e.de, ccaulfie@...hat.com,
	teigland@...hat.com, Trond.Myklebust@...app.com,
	bfields@...ldses.org, fweisbec@...il.com, jesse@...ira.com,
	venkat.x.venkatsubra@...cle.com, ejt@...hat.com,
	snitzer@...hat.com, edumazet@...gle.com, linux-nfs@...r.kernel.org,
	dev@...nvswitch.org, rds-devel@....oracle.com, lw@...fujitsu.com
Subject: Re: [PATCH v7 10/16] dlm: use new hashtable implementation

* Sasha Levin (levinsasha928@...il.com) wrote:
> On Mon, Oct 29, 2012 at 9:07 AM, Mathieu Desnoyers
> <mathieu.desnoyers@...icios.com> wrote:
> > * Mathieu Desnoyers (mathieu.desnoyers@...icios.com) wrote:
> >> * Sasha Levin (levinsasha928@...il.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

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/