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

* 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>