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: <20120816142821.GC29703@Krystal>
Date:	Thu, 16 Aug 2012 10:28:22 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	David Laight <David.Laight@...LAB.COM>
Cc:	"Eric W. Biederman" <ebiederm@...ssion.com>,
	Sasha Levin <levinsasha928@...il.com>,
	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, 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

* David Laight (David.Laight@...LAB.COM) wrote:
> > 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'm currently experimenting with "Judy arrays", which would likely be a
good fit for this kind of use-case.

It's basically a 256-ary trie, with fixed depth that depends on the key
size, that uses various encoding (compaction) schemes to compress
internal nodes depending on their density. The original implementation
made by HP has been criticised as somewhat too complex (20k lines of
code), but I'm currently working (in my spare time) on a more elegant
solution, that supports RCU lookups and distributed locking, and uses
much simpler node compaction schemes, and focus on having good cache
locality (and minimal number of cache line hits) for lookups.

I'll be presenting my ongoing work at Plumbers, if you are interested.

Best regards,

Mathieu

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

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