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)