- Subject: Re: [PATCH 02/16] user_ns: use new hashtable implementation
- From: "David Laight" <David.Laight@xxxxxxxxxx>
- Date: Wed, 15 Aug 2012 09:46:57 +0100
- Cc: snitzer@xxxxxxxxxx, fweisbec@xxxxxxxxx, Trond.Myklebust@xxxxxxxxxx, bfields@xxxxxxxxxxxx, paul.gortmaker@xxxxxxxxxxxxx, dm-devel@xxxxxxxxxx, agk@xxxxxxxxxx, aarcange@xxxxxxxxxx, rds-devel@xxxxxxxxxxxxxx, eric.dumazet@xxxxxxxxx, venkat.x.venkatsubra@xxxxxxxxxx, ccaulfie@xxxxxxxxxx, mingo@xxxxxxx, dev@xxxxxxxxxxxxxxx, jesse@xxxxxxxxxx, josh@xxxxxxxxxxxxxxxx, rostedt@xxxxxxxxxxx, lw@xxxxxxxxxxxxxx, mathieu.desnoyers@xxxxxxxxxxxx, axboe@xxxxxxxxx, linux-nfs@xxxxxxxxxxxxxxx, edumazet@xxxxxxxxxx, linux-mm@xxxxxxxxx, netdev@xxxxxxxxxxxxxxx, linux-kernel@xxxxxxxxxxxxxxx, ejt@xxxxxxxxxx, tj@xxxxxxxxxx, teigland@xxxxxxxxxx, akpm@xxxxxxxxxxxxxxxxxxxx, torvalds@xxxxxxxxxxxxxxxxxxxx, davem@xxxxxxxxxxxxx
- In-reply-to: <firstname.lastname@example.org>
- References: <email@example.com><firstname.lastname@example.org><email@example.com> <502AF184.firstname.lastname@example.org><email@example.com> <502AFCD5.firstname.lastname@example.org> <email@example.com>
- Reply-to: device-mapper development <dm-devel@xxxxxxxxxx>
- Thread-index: Ac16k+/CnUwwKHjCQTarP6REmO6aMgALLDtA
- Thread-topic: [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
> 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.
dm-devel mailing list