Messages in this thread Patch in this message | | | From | Hubertus Franke <> | Subject | Fwd: [Lse-tech] get_pid() performance fix | Date | Mon, 4 Mar 2002 20:57:49 -0500 |
| |
Can somebody post why this patch shouldn't be picked up ? The attached program shows the problem in user space and the patch is almost trivial ..
-- Hubertus
---------- Forwarded Message ----------
Subject: [Lse-tech] get_pid() performance fix Date: Tue, 26 Feb 2002 18:58:51 -0500 From: "Rajan Ravindran" <rajancr@us.ibm.com> To: lse-tech@lists.sourceforge.net Cc: linux-kernel@vger.kernel.org, davej@suse.de
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);
-------------------------------------------------------
-- -- Hubertus Franke (frankeh@watson.ibm.com)./getpid -p 32771 -n 4
Output when compiled without -DNEW_METHOD ----------------------------------------- nprocs: 32771, ndelete:0, nitems:4 start creating 32771 processes reached max pid <32768> reset last_pid to <300> removed pid: <17767> removed pid: <9158> removed pid: <6249> removed pid: <18547> spent 1.172945 seconds in finding free pid <6249> spent 2.519057 seconds in finding free pid <9158> spent 9.857908 seconds in finding free pid <17767> spent 10.924213 seconds in finding free pid <18547>
Output when compiled with -DNEW_METHOD -------------------------------------- nprocs: 32771, ndelete:0, nitems:4 start creating 32771 processes reached max pid <32768> reset last_pid to <300> removed pid: <17767> removed pid: <9158> spent 0.18468 seconds in finding free pid <17767> removed pid: <6249> removed pid: <18547> spent 0.30833 seconds in finding free pid <6249> spent 0.34572 seconds in finding free pid <9158> spent 0.41594 seconds in finding free pid <18547>
/* * Program to measure the get_pid() function performance * */
#include <stdio.h> #include <errno.h> #include <sched.h> #include <sys/types.h> #include <sys/wait.h> #include <sys/time.h> #include <getopt.h> #include <stdlib.h>
struct task_struct { int pid; struct task_struct *next_task; };
#define PID_MAX 0x8000 #define GETPID_MASK 0xffff8000 #define STACK_SIZE 8192
struct task_struct *tsk_head; int last_pid; unsigned long nprocs; int verbose; int start_del;
#define alloc_task_struct() \ ((struct task_struct *)malloc(sizeof(struct task_struct))) #define for_each_task(p) \ for (p = tsk_head ; (p = p->next_task) != tsk_head ; )
int create_task(); int (*ctask) (void *arg);
int __clone (int (*fn) (void *arg), void *thread_stack, int flags, void *arg);
int get_pid() { static int next_safe = PID_MAX; struct task_struct *p; static struct timeval stime, etime; static int start_search=0; int beginpid; long sec,usec;
beginpid = last_pid; if((++last_pid) & GETPID_MASK) { printf("reached max pid <%d> reset last_pid to <300>\n", last_pid); last_pid = 300; /* Skip daemons etc. */ start_del = start_search =1; gettimeofday(&stime, (struct timezone *) 0); goto inside; }
#ifdef NEW_METHOD if(last_pid >= next_safe) { inside: next_safe = PID_MAX; repeat: for (p = tsk_head ; (p = p->next_task) != tsk_head ; ) { if(p->pid == last_pid) { if(++last_pid >= next_safe) { if(last_pid & GETPID_MASK) last_pid = 300; next_safe = PID_MAX; goto repeat; } continue; } if(p->pid > last_pid && next_safe > p->pid) next_safe = p->pid; } } #else if(last_pid >= next_safe) { inside: next_safe = PID_MAX; repeat: for (p = tsk_head ; (p = p->next_task) != tsk_head ; ) { if(p->pid == last_pid) { if(++last_pid >= next_safe) { if(last_pid & GETPID_MASK) last_pid = 300; next_safe = PID_MAX; } goto repeat; } if(p->pid > last_pid && next_safe > p->pid) next_safe = p->pid; } } #endif if (start_search) { gettimeofday(&etime, (struct timezone *) 0); if ((etime.tv_usec - stime.tv_usec) < 0) { sec = (etime.tv_sec - stime.tv_sec) -1; usec = stime.tv_usec - etime.tv_usec; } else { sec = (etime.tv_sec - stime.tv_sec); usec = etime.tv_usec - stime.tv_usec; } printf("spent %d.%02d seconds in finding free pid <%d>\n", sec, usec, last_pid); } return last_pid; }
int create_task() { struct task_struct *p, *prev; unsigned int i;
prev = tsk_head; tsk_head->pid = 0; tsk_head->next_task = tsk_head; printf("start creating %d processes\n", nprocs); for (i=0; i<nprocs; i++) { p = alloc_task_struct(); p->next_task = tsk_head; p->pid = get_pid(); if (verbose) printf("created <%d>\n", p->pid); prev->next_task = p; prev = prev->next_task; } }
void delete_task(int nitems) { struct task_struct *p, *prev; unsigned int i; long int rand;
while (!start_del); for (i=0; i < nitems; i++) { rand = random() % PID_MAX; for (prev = p = tsk_head ; (p = p->next_task) != tsk_head ; ) { if (p->pid == rand) { prev->next_task = p->next_task; printf("removed pid: <%d>\n", rand); } prev = p; } } start_del=0; }
void usage() { printf("Usage: getpid -p <nprocs> -n <npids> -s <seed> -v [verbose]\n"); printf(" nprocs: number of process to create\n"); printf(" npids: number of process to delete\n"); printf(" verbose: print debug strings\n"); }
int main(int argc, char *argv[]) { int pid; char *stk; int wait_status, rc; int c, nitems=0;
while ((c = getopt(argc, argv, "p:s:n:v:")) != -1) { switch(c) { case 'p': nprocs = atoi(optarg); break; case 'n': nitems = atoi(optarg); break; case 's': srand(atoi(optarg)); break; case 'v': verbose = 1; break; default: usage(); return 0; } }
if ((nprocs == 0) || (nitems > PID_MAX)) { printf("Invalid parameter\n"); usage(); return 0; } tsk_head = alloc_task_struct(); stk = (char *)malloc(2 * STACK_SIZE);
ctask = create_task; pid = __clone(ctask, &stk[STACK_SIZE], CLONE_VM | CLONE_FS | CLONE_SIGHAND, (void *)0); if (pid == -1) printf("errno=%d <%s>\n", errno,strerror(errno)); delete_task(nitems); waitpid(-1, &wait_status, __WCLONE); }
| |