Date: Tue, 13 Apr 2004 09:37:01 +1000 From: Tim Robbins <tjr@freebsd.org> To: Julian Elischer <julian@elischer.org> Cc: FreeBSD current users <current@freebsd.org> Subject: Re: JKH project.. Message-ID: <20040412233701.GA71177@cat.robbins.dropbear.id.au> In-Reply-To: <Pine.BSF.4.21.0404111539430.82054-100000@InterJet.elischer.org> References: <Pine.BSF.4.21.0404111539430.82054-100000@InterJet.elischer.org>
next in thread | previous in thread | raw e-mail | index | archive | help
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
@@ -401,13 +401,12 @@
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);
@@ -650,6 +649,7 @@
*/
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
@@ -154,9 +154,7 @@
* 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;
@@ -197,8 +195,8 @@
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;
@@ -206,6 +204,9 @@
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. */
@@ -325,8 +326,7 @@
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.
@@ -339,69 +339,45 @@
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
@@ -86,6 +86,8 @@
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;
@@ -119,6 +121,7 @@
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);
@@ -250,7 +253,7 @@
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;
}
@@ -324,6 +327,7 @@
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"));
@@ -469,8 +473,9 @@
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);
@@ -825,8 +830,8 @@
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;
}
@@ -927,7 +932,7 @@
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
@@ -69,6 +69,7 @@
* (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. */
@@ -789,6 +790,10 @@
#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;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20040412233701.GA71177>