Messages in this thread Patch in this message | | | From | "Rajan Ravindran" <> | Date | Tue, 26 Feb 2002 18:58:51 -0500 | Subject | get_pid() performance fix |
| |
Paul Larson posted a patch which fixes the get_pid() hang, if we run out of available pids. Nevertheless, we have observed that it takes a long time to find the next available pid once the last pid reaches the PID_MAX. This is due to a constant rescan of the task list while progressing only one pid at time, yielding an O(n**2) problem. Here is a patch (together with Paul's fix) which eliminates the time taken to search for an available pid, by not constantly restarting the search through the entire task list.
Attached is also a user level test program getpid.c), by which one can simulate creation and deletion of processes. This application will measure the time taken for the get_pid() routine to find the next available process.
example: getpid -p 32770 -n 3
which will try to create 32770 process, eventually get_pid can't find any free pid after 32767, so it will delete 3 pids randomly from the existing list and start calculating the time taken to find the available pid (which we deleted).
In getpid.c the new fixes are inside the #define NEW_METHOD. Try compiling the getpid.c with and without -DNEW_METHOD compile option to see the performance improvement.
here is an example output for the old and the new algorithm and their respective execution time to find a new pid.
(See attached file: output)
This can/should be applied to 2.5 and 2.4 kernels.
(See attached file: getpid.c)
Thanks, Rajan
diff -Naur linux-2.5.5/kernel/fork.c linux-2.5.5-new/kernel/fork.c --- linux-2.5.5/kernel/fork.c Tue Feb 19 21:10:55 2002 +++ linux-2.5.5-new/kernel/fork.c Tue Feb 26 15:46:36 2002 @@ -24,6 +24,7 @@ #include <linux/file.h> #include <linux/binfmts.h> #include <linux/fs.h> +#include <linux/compiler.h>
#include <asm/pgtable.h> #include <asm/pgalloc.h> @@ -129,12 +130,13 @@ { static int next_safe = PID_MAX; struct task_struct *p; - int pid; + int pid, beginpid;
if (flags & CLONE_PID) return current->pid;
spin_lock(&lastpid_lock); + beginpid = last_pid; if((++last_pid) & 0xffff8000) { last_pid = 300; /* Skip daemons etc. */ goto inside; @@ -153,13 +155,18 @@ if(last_pid & 0xffff8000) last_pid = 300; next_safe = PID_MAX; + goto repeat; } - goto repeat; + if(unlikely(last_pid == beginpid)) + goto nomorepids; + continue; } if(p->pid > last_pid && next_safe > p->pid) next_safe = p->pid; if(p->pgrp > last_pid && next_safe > p->pgrp) next_safe = p->pgrp; + if(p->tgid > last_pid && next_safe > p->tgid) + next_safe = p->tgid; if(p->session > last_pid && next_safe > p->session) next_safe = p->session; } @@ -169,6 +176,11 @@ spin_unlock(&lastpid_lock);
return pid; + +nomorepids: + read_unlock(&tasklist_lock); + spin_unlock(&lastpid_lock); + return 0; }
static inline int dup_mmap(struct mm_struct * mm) @@ -667,6 +679,8 @@
copy_flags(clone_flags, p); p->pid = get_pid(clone_flags); + if (p->pid == 0 && current->pid != 0) + goto bad_fork_cleanup;
INIT_LIST_HEAD(&p->run_list); [unhandled content-type:application/octet-stream][unhandled content-type:application/octet-stream]
| |