Re: send_sigio() scalability

Alexander Kjeldaas (astor@fast.no)
Tue, 18 May 1999 11:10:57 +0200


On Mon, May 17, 1999 at 01:17:59PM +1000, Richard Gooch wrote:
> Hi, all. I just noticed that send_sigio() walks the task list,
> looking for the process(es) to send a signal to. This appears to be a
> potential scalability problem, as a large number of tasks is going to
> slow this down.
>
> Has anyone done any benchmarking to evaluate the effect of this? In
> the absence of numbers, how about some convincing handwaving? Is it
> worth exploring options to fix this?
>
> I can think of one quick and simple hack to fix this for 90% (maybe
> 99%) of cases: record the task pointer at fcntl() time. Then at
> send_sigio() time, if the recorded pid and task match, skip the
> task list walk.
>

In the case where send_sigio is sending a signal to a specific
process, why isn't it using find_task_by_pid()?. For the other case,
I'm working on a more general solution to most of the for_each_task()
uses in the kernel. I made a patch last year that adds fast
for_each_task_in_pgrp(), and for_each_task_in_session() macros. I
have measurements that prove that the patch helps a lot for the
fork()+exit() case. Please look at

http://www.guardian.no/~astor/pidhash/pidhash.gif

for a graph of this that I made for the patch for Linux 2.1.90. It
shows that when you have a lot of processes running, doing a
fork()+exit() takes a long time. This is due to for_each_task()'ing
in exit to send signals. I'd guess that send_sigio() will perform
similar to the above graph.

The general idea of the patch is to sort the entrires in the
task_list. Primarily by session-id, secondary by process group, and
tertiary by pid. In addition to that, we make sure that all pgids,
sids and pids are available in the pidhash-hash-table. So to traverse
all tasks in a process group, you just look up that pgid in the
pidhash and traverse the task list until the pgid changes. Likewise
with sids.

So the patch generally does the following:
- When forking, insert the new process behind its parent instead of
at the start/end of the task-list.
- When changing pgid or sid, change position of the process in the
task-list.
- Make sure all kernel threads have pid==pgid==sid
- For some special places that want to do a "signal each children", we have
to traverse the whole task list if one of the children is ptraced so
we have a counter of the number of ptraced children of a process
so we can optimize the common case.

I've started to port the patch to 2.2.8.

astor

-- 
 Alexander Kjeldaas, Fast Search & Transfer, Trondheim, Norway

- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/