* David Laight (David.Laight@xxxxxxxxxx) 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-nfs" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
