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

Hubertus Franke
2002-03-05T14:50:46Z

[-- 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);
}