netdev - Re: [PATCH 4/4] rhashtable: Add parent argument to mutex_is

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]

Message-ID: <20141115112313.GA20970@gondor.apana.org.au>
Date:	Sat, 15 Nov 2014 19:23:13 +0800
From:	Herbert Xu <herbert@...dor.apana.org.au>
To:	Thomas Graf <tgraf@...g.ch>
Cc:	netdev@...r.kernel.org, eric.dumazet@...il.com,
	paulmck@...ux.vnet.ibm.com, josh@...htriplett.org,
	"David S. Miller" <davem@...emloft.net>
Subject: Re: [PATCH 4/4] rhashtable: Add parent argument to mutex_is_held

On Sat, Nov 15, 2014 at 11:16:26AM +0000, Thomas Graf wrote:
>
> > Thomas, it appears that rhashtable as it stands cannot handle
> > changing the random seed because of the way it constructs the
> > new hash table without degrading into a linked list.  Is there
> > something I'm missing?
> > 
> > FWIW my hashtable in net/bridge/br_multicast.c handles rehashing
> > correctly.  Any objections to me converting rhashtable to use my
> > scheme instead?
> 
> Can you elaborate a bit?
> 
> The point of rhashtable is to not require two sets of linked list
> pointers as done by MDB or OVS flow tables to work around the
> increased cache footprint of that approach. The difference of the
> two algos is dicussed in this paper [0].
> 
> The disadvantage of rhashtable is that, AFAIK, the hash function
> cannot change while resizing as it would break the mutual linked
> lists.

Well it doesn't break so much as degenerate into a linked list (I'm
talking about the concept rather than what the current code does).

This is I think a show-stopper because for anything that can be
influenced by remote parties we have to reseed and therefore
be able to cope with hashes changing on the fly.  Since most
hash tables in the network stack can be influenced by remote
entities (including the xfrm policy bydst hash that I am currently
working on), this is something rhashtable must be able to support
if it is to be used throughout the network stack.

Unless there is a better solution then I think keeping two lists
will have to do.

Cheers,
-- 
Email: Herbert Xu <herbert@...dor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt
--
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html