Sasha Levin [off-list ref] writes:
On 08/15/2012 03:08 AM, Eric W. Biederman wrote:
quoted
quoted
I can offer the following: I'll write a small module that will hash 1...10000
quoted
into a hashtable which uses 7 bits (just like user_ns) and post the distribution
we'll get.
That won't hurt. I think 1-100 then 1000-1100 may actually be more
representative. Not that I would mind seeing the larger range.
Especially since I am in the process of encouraging the use of more
uids.
Alrighty, the results are in (numbers are objects in bucket):
For the 0...10000 range:
Average: 78.125
Std dev: 1.4197704151
Min: 75
Max: 80
For the 1...100 range:
Average: 0.78125
Std dev: 0.5164613088
Min: 0
Max: 2
For the 1000...1100 range:
Average: 0.7890625
Std dev: 0.4964812206
Min: 0
Max: 2
Looks like hash_32 is pretty good with small numbers.
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.
Aw well. Most of the time we only have a very small number of uids
in play, so it doesn't matter at this point.
Eric
* Eric W. Biederman (ebiederm@xmission.com) wrote:
Sasha Levin [off-list ref] writes:
quoted
On 08/15/2012 03:08 AM, Eric W. Biederman wrote:
quoted
quoted
I can offer the following: I'll write a small module that will hash 1...10000
quoted
into a hashtable which uses 7 bits (just like user_ns) and post the distribution
we'll get.
That won't hurt. I think 1-100 then 1000-1100 may actually be more
representative. Not that I would mind seeing the larger range.
Especially since I am in the process of encouraging the use of more
uids.
Alrighty, the results are in (numbers are objects in bucket):
For the 0...10000 range:
Average: 78.125
Std dev: 1.4197704151
Min: 75
Max: 80
For the 1...100 range:
Average: 0.78125
Std dev: 0.5164613088
Min: 0
Max: 2
For the 1000...1100 range:
Average: 0.7890625
Std dev: 0.4964812206
Min: 0
Max: 2
Looks like hash_32 is pretty good with small numbers.
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.
Hi Eric,
If you want to try out something that has more features than a basic
hash table, already exists and is available for you to play with, you
might want to have a look at the RCU lock-free resizable hash table.
It's initially done in userspace, but shares the same RCU semantic as
the kernel, and has chunk-based kernel-friendly index backends (thanks
to Lai Jiangshan), very useful to integrate with the kernel page
allocator.
It has the following properties that might make this container a good
fit for uid hashing:
- Real-time friendly lookups: Lookups are RCU and wait-free.
- Fast and real-time friendly updates: Use cmpxchg for update, and RCU
to deal with ABA.
- Resize (expand/shrink) for each power of two size, performed
concurrently with ongoing updates and lookups.
- Has add_unique (uniquify), add_replace, and also duplicate semantics.
- Provide uniqueness guarantees for RCU traversals of the hash table
with respect to add_unique and add_replace.
So if you are looking for a fast, RT-friendly, resizable hash table to
play with, you might want to have a look at the userspace RCU
implementation, which now features this hash table:
https://lttng.org/urcu
See urcu/rculfhash.h for the API.
Best regards,
Mathieu
Aw well. Most of the time we only have a very small number of uids
in play, so it doesn't matter at this point.
Eric
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
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
On 08/15/2012 05:31 AM, Mathieu Desnoyers wrote:
* Eric W. Biederman (ebiederm-aS9lmoZGLiVWk0Htik3J/w@public.gmane.org) wrote:
quoted
Sasha Levin [off-list ref] writes:
quoted
On 08/15/2012 03:08 AM, Eric W. Biederman wrote:
quoted
quoted
I can offer the following: I'll write a small module that will hash 1...10000
quoted
into a hashtable which uses 7 bits (just like user_ns) and post the distribution
we'll get.
That won't hurt. I think 1-100 then 1000-1100 may actually be more
representative. Not that I would mind seeing the larger range.
Especially since I am in the process of encouraging the use of more
uids.
Alrighty, the results are in (numbers are objects in bucket):
For the 0...10000 range:
Average: 78.125
Std dev: 1.4197704151
Min: 75
Max: 80
For the 1...100 range:
Average: 0.78125
Std dev: 0.5164613088
Min: 0
Max: 2
For the 1000...1100 range:
Average: 0.7890625
Std dev: 0.4964812206
Min: 0
Max: 2
Looks like hash_32 is pretty good with small numbers.
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.
Hi Eric,
If you want to try out something that has more features than a basic
hash table, already exists and is available for you to play with, you
might want to have a look at the RCU lock-free resizable hash table.
It's initially done in userspace, but shares the same RCU semantic as
the kernel, and has chunk-based kernel-friendly index backends (thanks
to Lai Jiangshan), very useful to integrate with the kernel page
allocator.
I'm guessing that once this static hashtable is stable, a
DEFINE_DYNAMIC_HASHTABLE() will get introduced which will evolve into something
similar to what Mathieu has pointed out in the urcu.
* David Laight (David.Laight-ZS65k/vG3HxXrIkS9f7CXA@public.gmane.org) wrote:
quoted
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