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]

Message-ID: <AE90C24D6B3A694183C094C60CF0A2F6026B6FB5@saturn3.aculab.com>
Date:	Wed, 15 Aug 2012 09:46:57 +0100
From:	"David Laight" <David.Laight@...LAB.COM>
To:	"Eric W. Biederman" <ebiederm@...ssion.com>,
	"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>,
	<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

> Yes hash_32 seems reasonable for the uid hash.   With those long hash
> chains I wouldn't like to be on a machine with 10,000 processes with
> each with a different uid, and a processes calling setuid in the fast
> path.
> 
> The uid hash that we are playing with is one that I sort of wish that
> the hash table could grow in size, so that we could scale up better.

Since uids are likely to be allocated in dense blocks, maybe an
unhashed multi-level lookup scheme might be appropriate.

Index an array with the low 8 (say) bits of the uid.
Each item can be either:  
  1) NULL => free entry.
  2) a pointer to a uid structure (check uid value).
  3) a pointer to an array to index with the next 8 bits.
(2) and (3) can be differentiated by the low address bit.
I think that is updateable with cmpxchg.

Clearly this is a bad algorithm if uids are all multiples of 2^24
but that is true or any hash function.

	David



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