lkml.org 
[lkml]   [1998]   [Mar]   [21]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
Subjectpidhash: fork()+exit()+waitpid() in *constant time*

We have done some initial measurements on a new scheme for hashing
process groups and session ids. This removes all uses of for_each_task
in fork and exit [we did a new version of get_pid, it might be faster
or slower than the original - it's hard to say]. The initial
measurements shows that in 2.1.90, a program doing fork and waiting on
the child (which only does exit()), behaves _linearly_ with the number
of other processes on the system. 2.1.90 with a new "pidhash" scheme
doesn't have this weakness and runs out test in _constant_ time. This
means that the overhead of having 2000 running processes have no
effect on fork(), exit() or waitpid().

median times on a ppro300/128MB, new scheme (2.1.90+pidhash+mmrepair):
fork()+exit()+waitpid() = 49089 cycles running 10 background processes.
fork()+exit()+waitpid() = 50194 cycles running 2000 background processes.

median times on a ppro300/128MB, old scheme (2.1.90+mmrepair):
fork()+exit()+waitpid() = 52923 cycles running 10 background processes.
fork()+exit()+waitpid() = 271301 cycles running 2000 background processes.

[full graph: ftp://ftp.guardian.no/pub/free/linux/pidhash.gif ]

The new pidhash scheme uses the fact that a process is a member of a
process group which in turn is a member of a session. The tasks in the
tasklist are sorted so that all processes in the same process group
are grouped together, and process groups belonging to a session are
grouped together. The first task in a pgrp or session is called the
"fake" pgrp/session-leader. In many cases, the fake session-leader
will be the same as the real leader, and this might be enforced in a
later version of the patch.

pids, pgrps and sessions are all hashed in the _same_ hashtable. This
means that a process calling setsid() will not get any extra
hash-entries since its pid is already hashed. When a real session
leader dies, and there is still tasks in the session, a new fake [in
this case a real "fake"] task is hashed in the original session's
place. A process can thus have a maximum of 3 hashentries in the
pidhashtable by having pid!=pgrp!=session and being fake session
leader and fake pgrp leader.

The following new functions are defined:

for_each_task_in_pgrp(p, pgrp) - traverse a pgrp
for_each_task_in_session(p, session) - traverse a session
find_task_by_pgrp(pgrp) - find fake pgrp leader
find_task_by_session(session) - find fake session leader

On fork, we link the new task after its parent instead of at the end
of the list. On setpgid and setsid, we so some trickery to move the
task in the tasklist. In many cases, we don't move the task at all
(first in a pgrp, last in a pgrp, first in a session and last in a
session are candidates for this optimization).

To remove one of the for_each_tasks in exit required a different
change. When a task is ptraced, the parent changes to the ptracing
process. The tasks sibling-pointers are destroyed (or relinked into
the new ptracing parent process) which makes the parent-child tree
implemented by pointers in task_struct unreliable as information about
your own children. When a process dies and we set its children's
parent to init, we thus have to do a for_each_task instead of using
these unreliable pointers. To fix this problem, we introduce a member
in the task_struct called 'ptraced_children' which indicates the
number of children currently being ptraced. In most cases this will be
0 and we can use the child-pointers and only have to do a
for_each_task in the rare case when a child is ptraced.

What we "really" wanted to do was to implement random pids, but the
previous scheme made it difficult to implement them efficiently :-)
With the new scheme we only have to look in the pidhash to see if a
pid is taken or not. You're not allowed to allocate a pid which is
used by a process group or a session leader, so in the old scheme we
had to traverse all tasks to double check.

astor

--
Alexander Kjeldaas, Guardian Networks AS, Trondheim, Norway
http://www.guardian.no/
[unhandled content-type:application/x-gunzip]
\
 
 \ /
  Last update: 2005-03-22 13:41    [W:0.024 / U:0.144 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site