Re: JKH project..

On Sun, Apr 11, 2004 at 03:51:45PM -0700, Julian Elischer wrote:

> Junior kernel hacker project..
> 
> the fork syscall has to check the new PID against all exixting pids..
> 
> here's the current code.. when teh PID-space starts becoming
> "fragmented.."  this starts to take "real time".
[...]
> with several thousand processes, forking a lot, this starts to take 
> a 'noticable' amount of time.

I've been using a hashtable-based PID allocator for the last few months.
I didn't have enough time to run any serious benchmarks, so I never
committed it. If the amount of time is noticeable in your environment,
would you mind trying the patch below?

> a small amount of time could be spent on trying to work out an
> O(1) solution to this.
>
> Possibly a small separate PID object that keeps reference counts
> of how many procs refer to it in various ways, and lives in a
> hash-table, and is freed when there are no more processes referring to
> it.

Sounds like System V. I considered doing that, but it was just too tempting
to reuse the existing PIDHASH/PGRPHASH mechanisms.

> 
> Suggestions welcome.. :-)


Index: kern/kern_exit.c
===================================================================
RCS file: /home/ncvs/src/sys/kern/kern_exit.c,v
retrieving revision 1.229
diff -u -r1.229 kern_exit.c
--- kern/kern_exit.c	5 Apr 2004 21:03:34 -0000	1.229
+++ kern/kern_exit.c	12 Apr 2004 23:16:19 -0000
_at__at_ -401,13 +401,12 _at__at_
 	crfree(td->td_ucred);
 
 	/*
-	 * Remove proc from allproc queue and pidhash chain.
+	 * Remove proc from allproc queue.
 	 * Place onto zombproc.  Unlink from parent's child list.
 	 */
 	sx_xlock(&allproc_lock);
 	LIST_REMOVE(p, p_list);
 	LIST_INSERT_HEAD(&zombproc, p, p_list);
-	LIST_REMOVE(p, p_hash);
 	sx_xunlock(&allproc_lock);
 
 	sx_xlock(&proctree_lock);
_at__at_ -650,6 +649,7 _at__at_
 			 */
 			sx_xlock(&allproc_lock);
 			LIST_REMOVE(p, p_list);	/* off zombproc */
+			LIST_REMOVE(p, p_hash);	/* off pidhash chain */
 			sx_xunlock(&allproc_lock);
 			LIST_REMOVE(p, p_sibling);
 			leavepgrp(p);
Index: kern/kern_fork.c
===================================================================
RCS file: /home/ncvs/src/sys/kern/kern_fork.c,v
retrieving revision 1.226
diff -u -r1.226 kern_fork.c
--- kern/kern_fork.c	5 Apr 2004 21:03:34 -0000	1.226
+++ kern/kern_fork.c	12 Apr 2004 23:16:19 -0000
_at__at_ -154,9 +154,7 _at__at_
  * Random component to lastpid generation.  We mix in a random factor to make
  * it a little harder to predict.  We sanity check the modulus value to avoid
  * doing it in critical paths.  Don't let it be too small or we pointlessly
- * waste randomness entropy, and don't let it be impossibly large.  Using a
- * modulus that is too big causes a LOT more process table scans and slows
- * down fork processing as the pidchecked caching is defeated.
+ * waste randomness entropy, and don't let it be impossibly large.
  */
 static int randompid = 0;
 
_at__at_ -197,8 +195,8 _at__at_
 	struct proc *p1, *p2, *pptr;
 	uid_t uid;
 	struct proc *newproc;
-	int ok, trypid;
-	static int curfail, pidchecked = 0;
+	int ok, trypid, wrapped;
+	static int curfail;
 	static struct timeval lastfail;
 	struct filedesc *fd;
 	struct filedesc_to_leader *fdtol;
_at__at_ -206,6 +204,9 _at__at_
 	struct kse *ke2;
 	struct ksegrp *kg2;
 	struct sigacts *newsigacts;
+	struct proc *pi;
+	struct pgrp *pgi;
+	struct session *si;
 	int error;
 
 	/* Can't copy and clear. */
_at__at_ -325,8 +326,7 _at__at_
 	nprocs++;
 
 	/*
-	 * Find an unused process ID.  We remember a range of unused IDs
-	 * ready to use (from lastpid+1 through pidchecked-1).
+	 * Find an unused process ID.
 	 *
 	 * If RFHIGHPID is set (used during system boot), do not allocate
 	 * low-numbered pids.
_at__at_ -339,69 +339,45 _at__at_
 		if (randompid)
 			trypid += arc4random() % randompid;
 	}
-retry:
-	/*
-	 * If the process ID prototype has wrapped around,
-	 * restart somewhat above 0, as the low-numbered procs
-	 * tend to include daemons that don't exit.
-	 */
-	if (trypid >= PID_MAX) {
-		trypid = trypid % PID_MAX;
-		if (trypid < 100)
-			trypid += 100;
-		pidchecked = 0;
-	}
-	if (trypid >= pidchecked) {
-		int doingzomb = 0;
-
-		pidchecked = PID_MAX;
-		/*
-		 * Scan the active and zombie procs to check whether this pid
-		 * is in use.  Remember the lowest pid that's greater
-		 * than trypid, so we can avoid checking for a while.
-		 */
-		p2 = LIST_FIRST(&allproc);
-again:
-		for (; p2 != NULL; p2 = LIST_NEXT(p2, p_list)) {
-			PROC_LOCK(p2);
-			while (p2->p_pid == trypid ||
-			    (p2->p_pgrp != NULL &&
-			    (p2->p_pgrp->pg_id == trypid ||
-			    (p2->p_session != NULL &&
-			    p2->p_session->s_sid == trypid)))) {
-				trypid++;
-				if (trypid >= pidchecked) {
-					PROC_UNLOCK(p2);
-					goto retry;
-				}
-			}
-			if (p2->p_pid > trypid && pidchecked > p2->p_pid)
-				pidchecked = p2->p_pid;
-			if (p2->p_pgrp != NULL) {
-				if (p2->p_pgrp->pg_id > trypid &&
-				    pidchecked > p2->p_pgrp->pg_id)
-					pidchecked = p2->p_pgrp->pg_id;
-				if (p2->p_session != NULL &&
-				    p2->p_session->s_sid > trypid &&
-				    pidchecked > p2->p_session->s_sid)
-					pidchecked = p2->p_session->s_sid;
-			}
-			PROC_UNLOCK(p2);
-		}
-		if (!doingzomb) {
-			doingzomb = 1;
-			p2 = LIST_FIRST(&zombproc);
-			goto again;
+	wrapped = 0;
+	while (!wrapped || trypid < lastpid + 1) {
+		/*
+		 * If the process ID prototype has wrapped around,
+		 * restart somewhat above 0, as the low-numbered procs
+		 * tend to include daemons that don't exit.
+		 */
+		if (trypid >= PID_MAX) {
+			trypid = trypid % PID_MAX;
+			if (trypid < 100)
+				trypid += 100;
+			wrapped = 1;
+		}
+		/*
+		 * Check that the prospective ID hasn't already been used.
+		 * Use the hash tables to avoid scanning allproc.
+		 */
+		LIST_FOREACH(pi, PIDHASH(trypid), p_hash) {
+			if (pi->p_pid == trypid)
+				goto trynext;
+		}
+		LIST_FOREACH(pgi, PGRPHASH(trypid), pg_hash) {
+			if (pgi->pg_id == trypid)
+				goto trynext;
+		}
+		LIST_FOREACH(si, SESSHASH(trypid), s_hash) {
+			if (si->s_sid == trypid)
+				goto trynext;
 		}
+		break;
+trynext:
+		trypid++;
 	}
 	sx_sunlock(&proctree_lock);
 
 	/*
 	 * RFHIGHPID does not mess with the lastpid counter during boot.
 	 */
-	if (flags & RFHIGHPID)
-		pidchecked = 0;
-	else
+	if (!(flags & RFHIGHPID))
 		lastpid = trypid;
 
 	p2 = newproc;
Index: kern/kern_proc.c
===================================================================
RCS file: /home/ncvs/src/sys/kern/kern_proc.c,v
retrieving revision 1.202
diff -u -r1.202 kern_proc.c
--- kern/kern_proc.c	5 Apr 2004 21:03:34 -0000	1.202
+++ kern/kern_proc.c	12 Apr 2004 23:16:25 -0000
_at__at_ -86,6 +86,8 _at__at_
 u_long pidhash;
 struct pgrphashhead *pgrphashtbl;
 u_long pgrphash;
+struct sesshashhead *sesshashtbl;
+u_long sesshash;
 struct proclist allproc;
 struct proclist zombproc;
 struct sx allproc_lock;
_at__at_ -119,6 +121,7 _at__at_
 	LIST_INIT(&zombproc);
 	pidhashtbl = hashinit(maxproc / 4, M_PROC, &pidhash);
 	pgrphashtbl = hashinit(maxproc / 4, M_PROC, &pgrphash);
+	sesshashtbl = hashinit(maxproc / 4, M_PROC, &sesshash);
 	proc_zone = uma_zcreate("PROC", sched_sizeof_proc(),
 	    proc_ctor, proc_dtor, proc_init, proc_fini,
 	    UMA_ALIGN_PTR, UMA_ZONE_NOFREE);
_at__at_ -250,7 +253,7 _at__at_
 
 	sx_slock(&allproc_lock);
 	LIST_FOREACH(p, PIDHASH(pid), p_hash)
-		if (p->p_pid == pid) {
+		if (p->p_pid == pid && p->p_state != PRS_ZOMBIE) {
 			PROC_LOCK(p);
 			break;
 		}
_at__at_ -324,6 +327,7 _at__at_
 		sess->s_ttyp = NULL;
 		bcopy(p->p_session->s_login, sess->s_login,
 			    sizeof(sess->s_login));
+		LIST_INSERT_HEAD(SESSHASH(sess->s_sid), sess, s_hash);
 		pgrp->pg_session = sess;
 		KASSERT(p == curproc,
 		    ("enterpgrp: mksession and p != curproc"));
_at__at_ -469,8 +473,9 _at__at_
 	SESS_UNLOCK(savesess);
 	PGRP_UNLOCK(pgrp);
 	if (savesess->s_count == 0) {
+		LIST_REMOVE(savesess, s_hash);
 		mtx_destroy(&savesess->s_mtx);
-		FREE(pgrp->pg_session, M_SESSION);
+		FREE(savesess, M_SESSION);
 	}
 	mtx_destroy(&pgrp->pg_mtx);
 	FREE(pgrp, M_PGRP);
_at__at_ -825,8 +830,8 _at__at_
 	struct proc *p;
 
 	sx_slock(&allproc_lock);
-	LIST_FOREACH(p, &zombproc, p_list)
-		if (p->p_pid == pid) {
+	LIST_FOREACH(p, PIDHASH(pid), p_hash)
+		if (p->p_pid == pid && p->p_state == PRS_ZOMBIE) {
 			PROC_LOCK(p);
 			break;
 		}
_at__at_ -927,7 +932,7 _at__at_
 			return (EINVAL);
 		break;
 	case KERN_PROC_PROC:
-		if (namelen != 0 && namelen != 1)
+		if (namelen != 0)
 			return (EINVAL);
 		break;
 	default:
Index: sys/proc.h
===================================================================
RCS file: /home/ncvs/src/sys/sys/proc.h,v
retrieving revision 1.374
diff -u -r1.374 proc.h
--- sys/proc.h	7 Apr 2004 04:19:49 -0000	1.374
+++ sys/proc.h	12 Apr 2004 23:16:25 -0000
_at__at_ -69,6 +69,7 _at__at_
  * (c)		const until freeing
  */
 struct session {
+	LIST_ENTRY(session) s_hash;	/* (e) Hash chain. */
 	int		s_count;	/* (m) Ref cnt; pgrps in session. */
 	struct proc	*s_leader;	/* (m + e) Session leader. */
 	struct vnode	*s_ttyvp;	/* (m) Vnode of controlling tty. */
_at__at_ -789,6 +790,10 _at__at_
 #define	PGRPHASH(pgid)	(&pgrphashtbl[(pgid) & pgrphash])
 extern LIST_HEAD(pgrphashhead, pgrp) *pgrphashtbl;
 extern u_long pgrphash;
+
+#define	SESSHASH(sid)	(&sesshashtbl[(sid) & sesshash])
+extern LIST_HEAD(sesshashhead, session) *sesshashtbl;
+extern u_long sesshash;
 
 extern struct sx allproc_lock;
 extern struct sx proctree_lock;