Re: [dm-devel] [PATCH 02/16] user_ns: use new hashtable implementation

[Mathieu Desnoyers <mathieu desnoyers efficios com>]

* David Laight (David Laight ACULAB 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