Fwd: [Lse-tech] get_pid() performance fix

[Hubertus Franke <frankeh@watson.ibm.com>]

[-- Attachment #1: Type: text/plain, Size: 4033 bytes --]


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)

[-- Attachment #2: output --]
[-- Type: application/octet-stream, Size: 1014 bytes --]

./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>


[-- Attachment #3: getpid.c --]
[-- Type: application/octet-stream, Size: 4613 bytes --]

/* 
 * 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);
}