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)
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Thu Mar 07 2002 - 21:00:42 EST