Messages in this thread | | | Subject | RE: [PATCH 02/16] user_ns: use new hashtable implementation | Date | Wed, 15 Aug 2012 09:46:57 +0100 | From | "David Laight" <> |
| |
> 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
| |