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

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.