From owner-freebsd-current@FreeBSD.ORG Mon Apr 12 16:33:12 2004 Return-Path: Delivered-To: freebsd-current@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id E5D4F16A4CE for ; Mon, 12 Apr 2004 16:33:12 -0700 (PDT) Received: from smtp02.syd.iprimus.net.au (smtp02.syd.iprimus.net.au [210.50.76.52]) by mx1.FreeBSD.org (Postfix) with ESMTP id F007B43D5D for ; Mon, 12 Apr 2004 16:33:11 -0700 (PDT) (envelope-from tim@robbins.dropbear.id.au) Received: from robbins.dropbear.id.au (210.50.216.216) by smtp02.syd.iprimus.net.au (7.0.024) id 402CF870013B2B15; Tue, 13 Apr 2004 09:33:04 +1000 Received: by robbins.dropbear.id.au (Postfix, from userid 1000) id 34A3C41DC; Tue, 13 Apr 2004 09:37:01 +1000 (EST) Date: Tue, 13 Apr 2004 09:37:01 +1000 From: Tim Robbins To: Julian Elischer Message-ID: <20040412233701.GA71177@cat.robbins.dropbear.id.au> References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.4.1i cc: FreeBSD current users Subject: Re: JKH project.. X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 12 Apr 2004 23:33:13 -0000 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;