Convert the lwp list into a red-black tree. This greatly reduces the
authorMatthew Dillon <dillon@dragonflybsd.org>
Wed, 15 Aug 2007 03:15:07 +0000 (03:15 +0000)
committerMatthew Dillon <dillon@dragonflybsd.org>
Wed, 15 Aug 2007 03:15:07 +0000 (03:15 +0000)
overhead of looking up LWPs for numerous operations including select and
removes the hokey fork code that tried to avoid doing a list traversal.

One inefficiency remains which cannot be easily fixed, and may not matter
much anyway, and that is delivering a generic signal the process may have
to iterate through many LWPs before finding one that can handle the signal.

12 files changed:
sys/ddb/db_ps.c
sys/kern/init_main.c
sys/kern/kern_exit.c
sys/kern/kern_fork.c
sys/kern/kern_resource.c
sys/kern/kern_sig.c
sys/kern/sys_generic.c
sys/platform/pc32/i386/pmap.c
sys/platform/vkernel/platform/pmap.c
sys/sys/proc.h
sys/sys/tree.h
sys/vm/vm_vmspace.c

index cba7928..485fabb 100644 (file)
@@ -31,7 +31,7 @@
  * SUCH DAMAGE.
  *
  * $FreeBSD: src/sys/ddb/db_ps.c,v 1.20 1999/08/28 00:41:09 peter Exp $
- * $DragonFly: src/sys/ddb/db_ps.c,v 1.23 2007/05/13 18:33:57 swildner Exp $
+ * $DragonFly: src/sys/ddb/db_ps.c,v 1.24 2007/08/15 03:15:05 dillon Exp $
  */
 #include <sys/param.h>
 #include <sys/systm.h>
@@ -57,7 +57,7 @@ db_ps(db_expr_t dummy1, boolean_t dummy2, db_expr_t dummy3, char *dummy4)
                p = allproc.lh_first;
        else
                p = &proc0;
-       lp = FIRST_LWP_IN_PROC(p);
+       lp = FIRST_LWP_IN_PROC(__DEVOLATILE(struct proc *, p));
 
        if (db_more(&nl) < 0)
            return;
@@ -90,7 +90,7 @@ db_ps(db_expr_t dummy1, boolean_t dummy2, db_expr_t dummy3, char *dummy4)
                db_printf(" %s\n", p->p_comm ? p->p_comm : "");
                db_dump_td_tokens(lp->lwp_thread);
 
-               lp = LIST_NEXT(lp, lwp_list);
+               lp = lwp_rb_tree_RB_NEXT(lp);
                if (lp == NULL) {
                        --np;
                        p = p->p_list.le_next;
@@ -98,7 +98,7 @@ db_ps(db_expr_t dummy1, boolean_t dummy2, db_expr_t dummy3, char *dummy4)
                                p = zombproc.lh_first;
                        if (p == NULL)
                                break;
-                       lp = FIRST_LWP_IN_PROC(p);
+                       lp = FIRST_LWP_IN_PROC(__DEVOLATILE(struct proc *, p));
                }
        }
 
index 3f67762..133239d 100644 (file)
@@ -40,7 +40,7 @@
  *
  *     @(#)init_main.c 8.9 (Berkeley) 1/21/94
  * $FreeBSD: src/sys/kern/init_main.c,v 1.134.2.8 2003/06/06 20:21:32 tegge Exp $
- * $DragonFly: src/sys/kern/init_main.c,v 1.81 2007/06/29 21:54:08 dillon Exp $
+ * $DragonFly: src/sys/kern/init_main.c,v 1.82 2007/08/15 03:15:06 dillon Exp $
  */
 
 #include "opt_init_path.h"
@@ -160,8 +160,9 @@ mi_proc0init(struct globaldata *gd, struct user *proc0paddr)
 {
        lwkt_init_thread(&thread0, proc0paddr, LWKT_THREAD_STACK, 0, gd);
        lwkt_set_comm(&thread0, "thread0");
-       LIST_INIT(&proc0.p_lwps);
-       LIST_INSERT_HEAD(&proc0.p_lwps, &lwp0, lwp_list);
+       RB_INIT(&proc0.p_lwp_tree);
+       proc0.p_lasttid = 0;    /* +1 = next TID */
+       lwp_rb_tree_RB_INSERT(&proc0.p_lwp_tree, &lwp0);
        lwp0.lwp_thread = &thread0;
        lwp0.lwp_proc = &proc0;
        proc0.p_usched = usched_init();
index 891748d..a064e96 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)kern_exit.c 8.7 (Berkeley) 2/12/94
  * $FreeBSD: src/sys/kern/kern_exit.c,v 1.92.2.11 2003/01/13 22:51:16 dillon Exp $
- * $DragonFly: src/sys/kern/kern_exit.c,v 1.84 2007/07/12 21:56:22 dillon Exp $
+ * $DragonFly: src/sys/kern/kern_exit.c,v 1.85 2007/08/15 03:15:06 dillon Exp $
  */
 
 #include "opt_compat.h"
@@ -82,6 +82,7 @@
 #include <sys/sysref2.h>
 
 static void reaplwps(void *context, int dummy);
+static void reaplwp(struct lwp *lp);
 static void killlwps(struct lwp *lp);
 
 static MALLOC_DEFINE(M_ATEXIT, "atexit", "atexit callback");
@@ -580,10 +581,10 @@ lwp_exit(int masterexit)
         * synchronously, which is much faster.
         */
        if (masterexit == 0) {
-               LIST_REMOVE(lp, lwp_list);
+               lwp_rb_tree_RB_REMOVE(&p->p_lwp_tree, lp);
                --p->p_nthreads;
                wakeup(&p->p_nthreads);
-               LIST_INSERT_HEAD(&deadlwp_list[mycpuid], lp, lwp_list);
+               LIST_INSERT_HEAD(&deadlwp_list[mycpuid], lp, u.lwp_reap_entry);
                taskqueue_enqueue(taskqueue_thread[mycpuid], deadlwp_task[mycpuid]);
        } else {
                --p->p_nthreads;
@@ -684,6 +685,7 @@ int
 kern_wait(pid_t pid, int *status, int options, struct rusage *rusage, int *res)
 {
        struct thread *td = curthread;
+       struct lwp *lp;
        struct proc *q = td->td_proc;
        struct proc *p, *t;
        int nfound, error;
@@ -741,7 +743,10 @@ loop:
                         * Once that is accomplished p_nthreads had better
                         * be zero.
                         */
-                       reaplwps(&p->p_lwps, 0);
+                       while ((lp = RB_ROOT(&p->p_lwp_tree)) != NULL) {
+                               lwp_rb_tree_RB_REMOVE(&p->p_lwp_tree, lp);
+                               reaplwp(lp);
+                       }
                        KKASSERT(p->p_nthreads == 0);
 
                        /*
@@ -916,13 +921,19 @@ reaplwps(void *context, int dummy)
        struct lwp *lp;
 
        while ((lp = LIST_FIRST(lwplist))) {
-               LIST_REMOVE(lp, lwp_list);
-               while (lwp_wait(lp) == 0)
-                       tsleep(lp, 0, "lwpreap", 1);
-               lwp_dispose(lp);
+               LIST_REMOVE(lp, u.lwp_reap_entry);
+               reaplwp(lp);
        }
 }
 
+static void
+reaplwp(struct lwp *lp)
+{
+       while (lwp_wait(lp) == 0)
+               tsleep(lp, 0, "lwpreap", 1);
+       lwp_dispose(lp);
+}
+
 static void
 deadlwp_init(void)
 {
index 2fe8b8f..636748a 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)kern_fork.c 8.6 (Berkeley) 4/8/94
  * $FreeBSD: src/sys/kern/kern_fork.c,v 1.72.2.14 2003/06/26 04:15:10 silby Exp $
- * $DragonFly: src/sys/kern/kern_fork.c,v 1.70 2007/07/02 17:06:54 dillon Exp $
+ * $DragonFly: src/sys/kern/kern_fork.c,v 1.71 2007/08/15 03:15:06 dillon Exp $
  */
 
 #include "opt_ktrace.h"
@@ -87,6 +87,23 @@ static struct lwp *lwp_fork(struct lwp *, struct proc *, int flags);
 
 int forksleep; /* Place for fork1() to sleep on. */
 
+/*
+ * Red-Black tree support for LWPs
+ */
+
+static int
+rb_lwp_compare(struct lwp *lp1, struct lwp *lp2)
+{
+       if (lp1->lwp_tid < lp2->lwp_tid)
+               return(-1);
+       if (lp1->lwp_tid > lp2->lwp_tid)
+               return(1);
+       return(0);
+}
+
+RB_GENERATE2(lwp_rb_tree, lwp, u.lwp_rbnode, rb_lwp_compare, lwpid_t, lwp_tid);
+
+
 /* ARGSUSED */
 int
 sys_fork(struct fork_args *uap)
@@ -186,7 +203,7 @@ sys_lwp_create(struct lwp_create_args *uap)
 
 fail:
        --p->p_nthreads;
-       LIST_REMOVE(lp, lwp_list);
+       lwp_rb_tree_RB_REMOVE(&p->p_lwp_tree, lp);
        /* lwp_dispose expects an exited lwp, and a held proc */
        lp->lwp_flag |= LWP_WEXIT;
        lp->lwp_thread->td_flags |= TDF_EXITING;
@@ -329,7 +346,8 @@ fork1(struct lwp *lp1, int flags, struct proc **procp)
                p2->p_leader = p2;
        }
 
-       LIST_INIT(&p2->p_lwps);
+       RB_INIT(&p2->p_lwp_tree);
+       p2->p_lasttid = -1;     /* first tid will be 0 */
 
        /*
         * Setting the state to SIDL protects the partially initialized
@@ -535,43 +553,12 @@ lwp_fork(struct lwp *origlp, struct proc *destproc, int flags)
 {
        struct lwp *lp;
        struct thread *td;
-       lwpid_t tid;
-
-       /*
-        * We need to prevent wrap-around collisions.
-        * Until we have a nice tid allocator, we need to
-        * start searching for free tids once we wrap around.
-        *
-        * XXX give me a nicer allocator
-        */
-       if (destproc->p_lasttid + 1 <= 0) {
-               tid = 0;
-restart:
-               FOREACH_LWP_IN_PROC(lp, destproc) {
-                       if (lp->lwp_tid != tid)
-                               continue;
-                       /* tids match, search next. */
-                       tid++;
-                       /*
-                        * Wait -- the whole tid space is depleted?
-                        * Impossible.
-                        */
-                       if (tid <= 0)
-                               panic("lwp_fork: All tids depleted?!");
-                       goto restart;
-               }
-               /* When we come here, the tid is not occupied */
-       } else {
-               tid = destproc->p_lasttid++;
-       }
 
        lp = zalloc(lwp_zone);
        bzero(lp, sizeof(*lp));
+
        lp->lwp_proc = destproc;
        lp->lwp_vmspace = destproc->p_vmspace;
-       lp->lwp_tid = tid;
-       LIST_INSERT_HEAD(&destproc->p_lwps, lp, lwp_list);
-       destproc->p_nthreads++;
        lp->lwp_stat = LSRUN;
        bcopy(&origlp->lwp_startcopy, &lp->lwp_startcopy,
            (unsigned) ((caddr_t)&lp->lwp_endcopy -
@@ -591,6 +578,18 @@ restart:
        crit_exit();
        lp->lwp_cpumask &= usched_mastermask;
 
+       /*
+        * Assign a TID to the lp.  Loop until the insert succeeds (returns
+        * NULL).
+        */
+       lp->lwp_tid = destproc->p_lasttid;
+       do {
+               if (++lp->lwp_tid < 0)
+                       lp->lwp_tid = 1;
+       } while (lwp_rb_tree_RB_INSERT(&destproc->p_lwp_tree, lp) != NULL);
+       destproc->p_lasttid = lp->lwp_tid;
+       destproc->p_nthreads++;
+
        td = lwkt_alloc_thread(NULL, LWKT_THREAD_STACK, -1, 0);
        lp->lwp_thread = td;
        td->td_proc = destproc;
index 9dff715..f30614a 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)kern_resource.c     8.5 (Berkeley) 1/21/94
  * $FreeBSD: src/sys/kern/kern_resource.c,v 1.55.2.5 2001/11/03 01:41:08 ps Exp $
- * $DragonFly: src/sys/kern/kern_resource.c,v 1.32 2007/05/03 23:04:31 dillon Exp $
+ * $DragonFly: src/sys/kern/kern_resource.c,v 1.33 2007/08/15 03:15:06 dillon Exp $
  */
 
 #include "opt_compat.h"
@@ -295,14 +295,9 @@ sys_lwp_rtprio(struct lwp_rtprio_args *uap)
                 */
                lp = curthread->td_lwp;
        } else {
-               FOREACH_LWP_IN_PROC(lp, p) {
-                       if (lp->lwp_tid == uap->tid) {
-                               break;
-                       }
-               }
-               if (!lp) {
+               lp = lwp_rb_tree_RB_LOOKUP(&p->p_lwp_tree, uap->tid);
+               if (lp == NULL)
                        return ESRCH;
-               }
        }
 
        switch (uap->function) {
index 755b012..06c9347 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)kern_sig.c  8.7 (Berkeley) 4/18/94
  * $FreeBSD: src/sys/kern/kern_sig.c,v 1.72.2.17 2003/05/16 16:34:34 obrien Exp $
- * $DragonFly: src/sys/kern/kern_sig.c,v 1.82 2007/07/01 01:11:35 dillon Exp $
+ * $DragonFly: src/sys/kern/kern_sig.c,v 1.83 2007/08/15 03:15:06 dillon Exp $
  */
 
 #include "opt_ktrace.h"
@@ -721,10 +721,7 @@ kern_kill(int sig, pid_t pid, lwpid_t tid)
                if (p->p_flag & P_WEXIT)
                        return (0);
                if (tid != -1) {
-                       FOREACH_LWP_IN_PROC(lp, p) {
-                               if (lp->lwp_tid == tid)
-                                       break;
-                       }
+                       lp = lwp_rb_tree_RB_LOOKUP(&p->p_lwp_tree, tid);
                        if (lp == NULL)
                                return (ESRCH);
                }
index a31c20d..9ee35cb 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)sys_generic.c       8.5 (Berkeley) 1/21/94
  * $FreeBSD: src/sys/kern/sys_generic.c,v 1.55.2.10 2001/03/17 10:39:32 peter Exp $
- * $DragonFly: src/sys/kern/sys_generic.c,v 1.45 2007/08/02 13:29:41 corecode Exp $
+ * $DragonFly: src/sys/kern/sys_generic.c,v 1.46 2007/08/15 03:15:06 dillon Exp $
  */
 
 #include "opt_ktrace.h"
@@ -1083,12 +1083,8 @@ selrecord(struct thread *selector, struct selinfo *sip)
        if (sip->si_pid == selector->td_proc->p_pid &&
            sip->si_tid == selector->td_lwp->lwp_tid)
                return;
-       if (sip->si_pid && (p = pfind(sip->si_pid))) {
-               FOREACH_LWP_IN_PROC(lp, p) {
-                       if (sip->si_tid == lp->lwp_tid)
-                               break;
-               }
-       }
+       if (sip->si_pid && (p = pfind(sip->si_pid)))
+               lp = lwp_rb_tree_RB_LOOKUP(&p->p_lwp_tree, sip->si_tid);
        if (lp != NULL && lp->lwp_wchan == (caddr_t)&selwait) {
                sip->si_flags |= SI_COLL;
        } else {
@@ -1117,10 +1113,7 @@ selwakeup(struct selinfo *sip)
        sip->si_pid = 0;
        if (p == NULL)
                return;
-       FOREACH_LWP_IN_PROC(lp, p) {
-               if (lp->lwp_tid == sip->si_tid)
-                       break;
-       }
+       lp = lwp_rb_tree_RB_LOOKUP(&p->p_lwp_tree, sip->si_tid);
        if (lp == NULL)
                return;
 
index 213b7c7..b8d55ca 100644 (file)
@@ -40,7 +40,7 @@
  *
  *     from:   @(#)pmap.c      7.7 (Berkeley)  5/12/91
  * $FreeBSD: src/sys/i386/i386/pmap.c,v 1.250.2.18 2002/03/06 22:48:53 silby Exp $
- * $DragonFly: src/sys/platform/pc32/i386/pmap.c,v 1.80 2007/06/29 21:54:10 dillon Exp $
+ * $DragonFly: src/sys/platform/pc32/i386/pmap.c,v 1.81 2007/08/15 03:15:07 dillon Exp $
  */
 
 /*
@@ -3230,7 +3230,7 @@ pmap_replacevm(struct proc *p, struct vmspace *newvm, int adjrefs)
        if (oldvm != newvm) {
                p->p_vmspace = newvm;
                KKASSERT(p->p_nthreads == 1);
-               lp = LIST_FIRST(&p->p_lwps);
+               lp = RB_ROOT(&p->p_lwp_tree);
                pmap_setlwpvm(lp, newvm);
                if (adjrefs) {
                        sysref_get(&newvm->vm_sysref);
index c654a24..262a89f 100644 (file)
@@ -38,7 +38,7 @@
  * 
  * from:   @(#)pmap.c      7.7 (Berkeley)  5/12/91
  * $FreeBSD: src/sys/i386/i386/pmap.c,v 1.250.2.18 2002/03/06 22:48:53 silby Exp $
- * $DragonFly: src/sys/platform/vkernel/platform/pmap.c,v 1.25 2007/07/02 02:22:58 dillon Exp $
+ * $DragonFly: src/sys/platform/vkernel/platform/pmap.c,v 1.26 2007/08/15 03:15:07 dillon Exp $
  */
 /*
  * NOTE: PMAP_INVAL_ADD: In pc32 this function is called prior to adjusting
@@ -2980,7 +2980,7 @@ pmap_replacevm(struct proc *p, struct vmspace *newvm, int adjrefs)
        if (oldvm != newvm) {
                p->p_vmspace = newvm;
                KKASSERT(p->p_nthreads == 1);
-               lp = LIST_FIRST(&p->p_lwps);
+               lp = RB_ROOT(&p->p_lwp_tree);
                pmap_setlwpvm(lp, newvm);
                if (adjrefs) {
                        sysref_get(&newvm->vm_sysref);
index 99a8695..8260703 100644 (file)
@@ -37,7 +37,7 @@
  *
  *     @(#)proc.h      8.15 (Berkeley) 5/19/95
  * $FreeBSD: src/sys/sys/proc.h,v 1.99.2.9 2003/06/06 20:21:32 tegge Exp $
- * $DragonFly: src/sys/sys/proc.h,v 1.111 2007/07/12 21:56:20 dillon Exp $
+ * $DragonFly: src/sys/sys/proc.h,v 1.112 2007/08/15 03:15:07 dillon Exp $
  */
 
 #ifndef _SYS_PROC_H_
@@ -52,6 +52,7 @@
 #include <sys/callout.h>               /* For struct callout_handle. */
 #include <sys/filedesc.h>
 #include <sys/queue.h>
+#include <sys/tree.h>
 #include <sys/rtprio.h>                        /* For struct rtprio. */
 #include <sys/signal.h>
 #include <sys/lock.h>
 LIST_HEAD(proclist, proc);
 LIST_HEAD(lwplist, lwp);
 
+struct lwp_rb_tree;
+RB_HEAD(lwp_rb_tree, lwp);
+RB_PROTOTYPE2(lwp_rb_tree, lwp, u.lwp_rbnode, rb_lwp_compare, lwpid_t);
+
 /*
  * One structure allocated per session.
  */
@@ -150,7 +155,10 @@ enum procstat {
 
 struct lwp {
        TAILQ_ENTRY(lwp) lwp_procq;     /* run/sleep queue. */
-       LIST_ENTRY(lwp) lwp_list;       /* List of all threads in the proc. */
+       union {
+           RB_ENTRY(lwp)       lwp_rbnode;     /* RB tree node - lwp in proc */
+           LIST_ENTRY(lwp)     lwp_reap_entry; /* reaper list */
+       } u;
 
        struct proc     *lwp_proc;      /* Link to our proc. */
        struct vmspace  *lwp_vmspace;   /* Inherited from p_vmspace */
@@ -289,7 +297,7 @@ struct      proc {
        int             p_nthreads;     /* Number of threads in this process. */
        int             p_nstopped;     /* Number of stopped threads. */
        int             p_lasttid;      /* Last tid used. */
-       struct lwplist  p_lwps; /* List of threads in this process. */
+       struct lwp_rb_tree p_lwp_tree;  /* RB tree of LWPs for this process */
        void            *p_aioinfo;     /* ASYNC I/O info */
        int             p_wakeup;       /* thread id XXX lwp */
        struct proc     *p_peers;       /* XXX lwp */
@@ -356,14 +364,14 @@ struct    proc {
 #define        LWP_WEXIT       0x0000040 /* working on exiting */
 #define        LWP_WSTOP       0x0000080 /* working on stopping */
 
-#define        FIRST_LWP_IN_PROC(p)            LIST_FIRST(&(p)->p_lwps)
+#define        FIRST_LWP_IN_PROC(p)            RB_FIRST(lwp_rb_tree, &(p)->p_lwp_tree)
 #define        FOREACH_LWP_IN_PROC(lp, p)      \
-       LIST_FOREACH((lp), &(p)->p_lwps, lwp_list)
+       RB_FOREACH(lp, lwp_rb_tree, &(p)->p_lwp_tree)
 #define        ONLY_LWP_IN_PROC(p)             \
        (p->p_nthreads != 1 &&          \
        (panic("%s: proc %p (pid %d cmd %s) has more than one thread",  \
               __func__, p, p->p_pid, p->p_comm), 1),   \
-       FIRST_LWP_IN_PROC(p))
+       RB_ROOT(&p->p_lwp_tree))
 
 /*
  * We use process IDs <= PID_MAX; PID_MAX + 1 must also fit in a pid_t,
index 17dc39f..4ef4915 100644 (file)
@@ -1,6 +1,6 @@
 /*     $NetBSD: tree.h,v 1.8 2004/03/28 19:38:30 provos Exp $  */
 /*     $OpenBSD: tree.h,v 1.7 2002/10/17 21:51:54 art Exp $    */
-/*     $DragonFly: src/sys/sys/tree.h,v 1.7 2007/06/17 07:58:33 dillon Exp $ */
+/*     $DragonFly: src/sys/sys/tree.h,v 1.8 2007/08/15 03:15:07 dillon Exp $ */
 /*
  * Copyright 2002 Niels Provos <provos@citi.umich.edu>
  * All rights reserved.
@@ -937,6 +937,7 @@ name##_RB_LOOKUP_##ext (struct name *head, datatype value)          \
 #define RB_RLOOKUP(name, root, value)  name##_RB_RLOOKUP(root, value)
 #define RB_SCAN(name, root, cmp, callback, data)                       \
                                name##_RB_SCAN(root, cmp, callback, data)
+#define RB_FIRST(name, root)           name##_RB_MINMAX(root, RB_NEGINF)
 #define RB_NEXT(name, root, elm)       name##_RB_NEXT(elm)
 #define RB_PREV(name, root, elm)       name##_RB_PREV(elm)
 #define RB_MIN(name, root)             name##_RB_MINMAX(root, RB_NEGINF)
index fb2cdcf..2414ff9 100644 (file)
@@ -31,7 +31,7 @@
  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  * SUCH DAMAGE.
  * 
- * $DragonFly: src/sys/vm/vm_vmspace.c,v 1.13 2007/07/01 01:11:37 dillon Exp $
+ * $DragonFly: src/sys/vm/vm_vmspace.c,v 1.14 2007/08/15 03:15:07 dillon Exp $
  */
 #include "opt_ddb.h"
 
@@ -450,7 +450,7 @@ vkernel_exit(struct proc *p)
         * that the process should enter vkernel_trap() before the handling
         * the signal.
         */
-       LIST_FOREACH(lp, &p->p_lwps, lwp_list) {
+       RB_FOREACH(lp, lwp_rb_tree, &p->p_lwp_tree) {
                vkernel_lwp_exit(lp);
        }