> The previous code used just two int variables, didn't it? At least
> for process ID allocation.

+ a soddding great big hash table and a double linked list through both
the pgrp and proc structures.

> How much memory does the new pid allocation code use e.g.
> when there are 128 IDs used? How much memory if 1024 used?
> How much did the old pid allocation code used in these cases?

The overhead for the table is 8 bytes per pid (assuming 32bit pointers).
(rounded up to the next power of 2, and not using the last few slots).
The old code had two hash tables that had maxproc/4 entries each, plus
the corresponding pointers in both the pgrp and proc structures.
Unfortunately I could only dispose of one of the 2 pointers in the
proc structures - the deadproc list (processes waiting to be reaped)
borrowed the hash chain pointer.

> > The performance change it mainly to pfind() and pgfind() which are
> > called quite often, and are now table lookups, not searches.
> 
> IIRC you said earlier you didn't see any performance difference
> when you tried to benchmark this?

I didn't say that, what I said is that (in the usual cases) the
cost of allocating the vm space in fork() will be dominant.

> The only place where I see pfind()/pgfind() being used on common
> code path is in kill(2).  Otherwise they are used in ioctl/ktrace/setup
> code, which not done frequently enough to matter. So speeding up
> pfind()/pgfind() doesn't seem to be really a priority, IMHO.

Don't forget setpgrp.

> If the only aim is to speed up pfind(), this could be easily
> done with a hash - PIDs have very good distribution.

Actually they used to have a very bad distribution, since they
are not random.  I could very easily write code that allocated
pathologically pad pids (just keep forking until you get a number
you want).

You could consider that the new code has a perfect hash function.
pids are only allocated if they hit an empty slot in the hash table.

Also the 'hash' by masking with (2^n - 1) is significantly cheaper
than the software divide used by the old code on systems without
a divide instruction.

> > The old code has a compile time dependency on MAXUSERS, this sucks.
> 
> This is totally orthogonal.

Actually it is where I staretd from!

> I'd still be interested to know if you tested the code
> for PID > 16k and PID > 30k cases, though.

The cases where tested by seeing the effects of running a kernel
that was compiled with a very low PID_MAX.
(I probably ran one with PID_MAX set to 16, and an initial table size of 2).

	David

-- 
David Laight: david@l8s.co.uk