linux-kernel - Re: [PATCH 02/16] user_ns: 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:	Wed, 15 Aug 2012 02:47:00 +0200
From:	Sasha Levin <levinsasha928@...il.com>
To:	"Eric W. Biederman" <ebiederm@...ssion.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,
	aarcange@...hat.com, ericvh@...il.com, netdev@...r.kernel.org,
	josh@...htriplett.org, eric.dumazet@...il.com,
	mathieu.desnoyers@...icios.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 02/16] user_ns: use new hashtable implementation

On 08/15/2012 01:52 AM, Eric W. Biederman wrote:
> Sasha Levin <levinsasha928@...il.com> writes:
> 
>> Switch user_ns to use the new hashtable implementation. This reduces the amount of
>> generic unrelated code in user_ns.
> 
> Two concerns here.
> 1) When adding a new entry you recompute the hash where previously that
>    was not done.  I believe that will slow down adding of new entries.

I figured that the price for the extra hashing isn't significant since hash_32
is just a multiplication and a shift.

I'll modify the code to calculate the key just once.

> 2) Using hash_32 for uids is an interesting choice.  hash_32 discards
>    the low bits.  Last I checked for uids the low bits were the bits
>    that were most likely to be different and had the most entropy.
> 
>    I'm not certain how multiplying by the GOLDEN_RATION_PRIME_32 will
>    affect things but I would be surprised if it shifted all of the
>    randomness from the low bits to the high bits.

"Is hash_* good enough for our purpose?" - I was actually surprised that no one
raised that question during the RFC and assumed it was because everybody agreed
that it's indeed good enough.

I can offer the following: I'll write a small module that will hash 1...10000
into a hashtable which uses 7 bits (just like user_ns) and post the distribution
we'll get.

If the results of the above will be satisfactory we can avoid the discussion
about which hash function we should really be using. If not, I guess now is a
good time for that :)

--
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/