diff -urN fork-ref/include/linux/threads.h fork/include/linux/threads.h
--- fork-ref/include/linux/threads.h	Fri Apr 19 22:41:14 2002
+++ fork/include/linux/threads.h	Fri Apr 19 22:23:04 2002
@@ -19,6 +19,6 @@
 /*
  * This controls the maximum pid allocated to a process
  */
-#define PID_MAX 0x8000
+#define PID_NR 0x8000
 
 #endif
diff -urN fork-ref/kernel/fork.c fork/kernel/fork.c
--- fork-ref/kernel/fork.c	Fri Apr 19 22:41:14 2002
+++ fork/kernel/fork.c	Fri Apr 19 22:39:06 2002
@@ -21,6 +21,8 @@
 #include <linux/completion.h>
 #include <linux/namespace.h>
 #include <linux/personality.h>
+#include <linux/bitops.h>
+#include <linux/string.h>
 
 #include <asm/pgtable.h>
 #include <asm/pgalloc.h>
@@ -33,10 +35,13 @@
 
 int max_threads;
 unsigned long total_forks;	/* Handle normal Linux uptimes. */
-int last_pid;
-
 struct task_struct *pidhash[PIDHASH_SZ];
 
+/* Protects next_unsafe and last_pid. */
+static spinlock_cacheline_t lastpid_lock_cacheline = { SPIN_LOCK_UNLOCKED, };
+#define lastpid_lock (lastpid_lock_cacheline.lock)
+int last_pid;
+
 void add_wait_queue(wait_queue_head_t *q, wait_queue_t * wait)
 {
 	unsigned long flags;
@@ -79,50 +84,79 @@
 	init_task.rlim[RLIMIT_NPROC].rlim_max = max_threads/2;
 }
 
-/* Protects next_safe and last_pid. */
-spinlock_t lastpid_lock = SPIN_LOCK_UNLOCKED;
-
 static int get_pid(unsigned long flags)
 {
-	static int next_safe = PID_MAX;
+	static int next_unsafe = PID_NR;
+#define PID_FIRST	2 /* pid 1 is init, first usable pid is 2 */
+#define PID_BITMAP_SIZE	((((PID_NR + 7) / 8) + sizeof(long) - 1 ) & ~(sizeof(long) - 1))
+	static unsigned char pid_bitmap[PID_BITMAP_SIZE];
+
+	/* from here the stuff on the stack */
 	struct task_struct *p;
-	int pid;
+	int pid, found_pid;
 
 	if (flags & CLONE_PID)
 		return current->pid;
 
 	spin_lock(&lastpid_lock);
-	if((++last_pid) & 0xffff8000) {
-		last_pid = 300;		/* Skip daemons etc. */
-		goto inside;
-	}
-	if(last_pid >= next_safe) {
-inside:
-		next_safe = PID_MAX;
+	pid = last_pid + 1;
+	if (pid >= next_unsafe) {
+		next_unsafe = PID_NR;
+		memset(pid_bitmap, 0, PID_BITMAP_SIZE);
+
 		read_lock(&tasklist_lock);
-	repeat:
 		for_each_task(p) {
-			if(p->pid == last_pid	||
-			   p->pgrp == last_pid	||
-			   p->tgid == last_pid	||
-			   p->session == last_pid) {
-				if(++last_pid >= next_safe) {
-					if(last_pid & 0xffff8000)
-						last_pid = 300;
-					next_safe = PID_MAX;
+			set_bit(p->pid, pid_bitmap);
+			set_bit(p->pgrp, pid_bitmap);
+			set_bit(p->tgid, pid_bitmap);
+			set_bit(p->session, pid_bitmap);
+
+			if (next_unsafe > p->pid && p->pid > pid)
+				next_unsafe = p->pid;
+			if (next_unsafe > p->pgrp && p->pgrp > pid)
+				next_unsafe = p->pgrp;
+			if (next_unsafe > p->tgid && p->tgid > pid)
+				next_unsafe = p->tgid;
+			if (next_unsafe > p->session && p->session > pid)
+				next_unsafe = p->session;
+		}
+		/*
+		 * Release the tasklist_lock. It may happen that
+		 * a pid is freed while it's still marked in use
+		 * in the pid_bitmap[].
+		 */
+		read_unlock(&tasklist_lock);
+
+		found_pid = find_next_zero_bit(pid_bitmap, PID_NR, pid);
+		if (found_pid >= PID_NR) {
+			next_unsafe = 0; /* depends on PID_FIRST > 0 */
+			found_pid = find_next_zero_bit(pid_bitmap, pid, PID_FIRST);
+			if (found_pid >= pid) {
+				spin_unlock(&lastpid_lock);
+				return -1;
+			}
+		}
+
+		pid = found_pid;
+
+		if (pid > next_unsafe) {
+			/* recalc next_unsafe */
+			unsigned long * p = ((unsigned long *) pid_bitmap) + (pid / (sizeof(long) * 8));
+			unsigned long * end = (unsigned long *) (pid_bitmap + PID_BITMAP_SIZE);
+			unsigned long mask = ~((1UL << (pid & ((sizeof(long) * 8 - 1)))) - 1);
+
+			*p &= (mask << 1);
+
+			while (p < end) {
+				p++;
+				if (*p) {
+					next_unsafe = ffz(~*p) + (end - p) * sizeof(long);
+					break;
 				}
-				goto repeat;
 			}
-			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->session > last_pid && next_safe > p->session)
-				next_safe = p->session;
 		}
-		read_unlock(&tasklist_lock);
 	}
-	pid = last_pid;
+	last_pid = pid;
 	spin_unlock(&lastpid_lock);
 
 	return pid;