Source-Changes-HG archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

[src/trunk]: src/sys Change sleepq_t from a TAILQ to a LIST and remove SOBJ_S...



details:   https://anonhg.NetBSD.org/src/rev/991fbbdc1540
branches:  trunk
changeset: 1008559:991fbbdc1540
user:      ad <ad%NetBSD.org@localhost>
date:      Thu Mar 26 19:46:42 2020 +0000

description:
Change sleepq_t from a TAILQ to a LIST and remove SOBJ_SLEEPQ_FIFO.  Only
select/poll used the FIFO method and that was for collisions which rarely
occur.  Shrinks sleep_t and condvar_t.

diffstat:

 sys/kern/kern_condvar.c   |  29 ++++++++++++++---------------
 sys/kern/kern_sleepq.c    |  25 +++++++++++--------------
 sys/kern/kern_turnstile.c |  19 ++++++++++---------
 sys/kern/sys_select.c     |  14 ++++++++++----
 sys/sys/condvar.h         |   6 +++---
 sys/sys/lwp.h             |   4 ++--
 sys/sys/sleepq.h          |   9 +++++----
 7 files changed, 55 insertions(+), 51 deletions(-)

diffs (truncated from 352 to 300 lines):

diff -r 5b960b9768c4 -r 991fbbdc1540 sys/kern/kern_condvar.c
--- a/sys/kern/kern_condvar.c   Thu Mar 26 19:42:39 2020 +0000
+++ b/sys/kern/kern_condvar.c   Thu Mar 26 19:46:42 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: kern_condvar.c,v 1.43 2020/02/15 17:09:24 ad Exp $     */
+/*     $NetBSD: kern_condvar.c,v 1.44 2020/03/26 19:46:42 ad Exp $     */
 
 /*-
  * Copyright (c) 2006, 2007, 2008, 2019, 2020 The NetBSD Foundation, Inc.
@@ -34,7 +34,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.43 2020/02/15 17:09:24 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.44 2020/03/26 19:46:42 ad Exp $");
 
 #include <sys/param.h>
 #include <sys/systm.h>
@@ -48,20 +48,19 @@
 /*
  * Accessors for the private contents of the kcondvar_t data type.
  *
- *     cv_opaque[0]    sleepq...
- *     cv_opaque[1]    ...pointers
- *     cv_opaque[2]    description for ps(1)
+ *     cv_opaque[0]    sleepq_t
+ *     cv_opaque[1]    description for ps(1)
  *
- * cv_opaque[0..1] is protected by the interlock passed to cv_wait() (enqueue
+ * cv_opaque[0] is protected by the interlock passed to cv_wait() (enqueue
  * only), and the sleep queue lock acquired with sleepq_hashlock() (enqueue
  * and dequeue).
  *
- * cv_opaque[2] (the wmesg) is static and does not change throughout the life
+ * cv_opaque[1] (the wmesg) is static and does not change throughout the life
  * of the CV.
  */
 #define        CV_SLEEPQ(cv)           ((sleepq_t *)(cv)->cv_opaque)
-#define        CV_WMESG(cv)            ((const char *)(cv)->cv_opaque[2])
-#define        CV_SET_WMESG(cv, v)     (cv)->cv_opaque[2] = __UNCONST(v)
+#define        CV_WMESG(cv)            ((const char *)(cv)->cv_opaque[1])
+#define        CV_SET_WMESG(cv, v)     (cv)->cv_opaque[1] = __UNCONST(v)
 
 #define        CV_DEBUG_P(cv)  (CV_WMESG(cv) != nodebug)
 #define        CV_RA           ((uintptr_t)__builtin_return_address(0))
@@ -486,7 +485,7 @@
        /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */
        KASSERT(cv_is_valid(cv));
 
-       if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv))))
+       if (__predict_false(!LIST_EMPTY(CV_SLEEPQ(cv))))
                cv_wakeup_one(cv);
 }
 
@@ -508,7 +507,7 @@
 
        mp = sleepq_hashlock(cv);
        sq = CV_SLEEPQ(cv);
-       l = TAILQ_FIRST(sq);
+       l = LIST_FIRST(sq);
        if (__predict_false(l == NULL)) {
                mutex_spin_exit(mp);
                return;
@@ -536,7 +535,7 @@
        /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */
        KASSERT(cv_is_valid(cv));
 
-       if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv))))  
+       if (__predict_false(!LIST_EMPTY(CV_SLEEPQ(cv))))  
                cv_wakeup_all(cv);
 }
 
@@ -558,11 +557,11 @@
 
        mp = sleepq_hashlock(cv);
        sq = CV_SLEEPQ(cv);
-       for (l = TAILQ_FIRST(sq); l != NULL; l = next) {
+       for (l = LIST_FIRST(sq); l != NULL; l = next) {
                KASSERT(l->l_sleepq == sq);
                KASSERT(l->l_mutex == mp);
                KASSERT(l->l_wchan == cv);
-               next = TAILQ_NEXT(l, l_sleepchain);
+               next = LIST_NEXT(l, l_sleepchain);
                CV_LOCKDEBUG_PROCESS(l, cv);
                sleepq_remove(sq, l);
        }
@@ -581,7 +580,7 @@
 cv_has_waiters(kcondvar_t *cv)
 {
 
-       return !TAILQ_EMPTY(CV_SLEEPQ(cv));
+       return !LIST_EMPTY(CV_SLEEPQ(cv));
 }
 
 /*
diff -r 5b960b9768c4 -r 991fbbdc1540 sys/kern/kern_sleepq.c
--- a/sys/kern/kern_sleepq.c    Thu Mar 26 19:42:39 2020 +0000
+++ b/sys/kern/kern_sleepq.c    Thu Mar 26 19:46:42 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: kern_sleepq.c,v 1.62 2020/03/24 21:05:06 ad Exp $      */
+/*     $NetBSD: kern_sleepq.c,v 1.63 2020/03/26 19:46:42 ad Exp $      */
 
 /*-
  * Copyright (c) 2006, 2007, 2008, 2009, 2019, 2020 The NetBSD Foundation, Inc.
@@ -35,7 +35,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_sleepq.c,v 1.62 2020/03/24 21:05:06 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_sleepq.c,v 1.63 2020/03/26 19:46:42 ad Exp $");
 
 #include <sys/param.h>
 #include <sys/kernel.h>
@@ -98,7 +98,7 @@
 sleepq_init(sleepq_t *sq)
 {
 
-       TAILQ_INIT(sq);
+       LIST_INIT(sq);
 }
 
 /*
@@ -116,7 +116,7 @@
 
        if ((l->l_syncobj->sobj_flag & SOBJ_SLEEPQ_NULL) == 0) {
                KASSERT(sq != NULL);
-               TAILQ_REMOVE(sq, l, l_sleepchain);
+               LIST_REMOVE(l, l_sleepchain);
        } else {
                KASSERT(sq == NULL);
        }
@@ -191,18 +191,15 @@
                lwp_t *l2;
                const pri_t pri = lwp_eprio(l);
 
-               TAILQ_FOREACH(l2, sq, l_sleepchain) {
+               LIST_FOREACH(l2, sq, l_sleepchain) {
                        if (lwp_eprio(l2) < pri) {
-                               TAILQ_INSERT_BEFORE(l2, l, l_sleepchain);
+                               LIST_INSERT_BEFORE(l2, l, l_sleepchain);
                                return;
                        }
                }
        }
 
-       if ((sobj->sobj_flag & SOBJ_SLEEPQ_LIFO) != 0)
-               TAILQ_INSERT_HEAD(sq, l, l_sleepchain);
-       else
-               TAILQ_INSERT_TAIL(sq, l, l_sleepchain);
+       LIST_INSERT_HEAD(sq, l, l_sleepchain);
 }
 
 /*
@@ -334,10 +331,10 @@
 
        KASSERT(mutex_owned(mp));
 
-       for (l = TAILQ_FIRST(sq); l != NULL; l = next) {
+       for (l = LIST_FIRST(sq); l != NULL; l = next) {
                KASSERT(l->l_sleepq == sq);
                KASSERT(l->l_mutex == mp);
-               next = TAILQ_NEXT(l, l_sleepchain);
+               next = LIST_NEXT(l, l_sleepchain);
                if (l->l_wchan != wchan)
                        continue;
                sleepq_remove(sq, l);
@@ -463,10 +460,10 @@
         * sleep queue lock held and need to see a non-empty queue
         * head if there are waiters.
         */
-       if (TAILQ_FIRST(sq) == l && TAILQ_NEXT(l, l_sleepchain) == NULL) {
+       if (LIST_FIRST(sq) == l && LIST_NEXT(l, l_sleepchain) == NULL) {
                return;
        }
-       TAILQ_REMOVE(sq, l, l_sleepchain);
+       LIST_REMOVE(l, l_sleepchain);
        sleepq_insert(sq, l, l->l_syncobj);
 }
 
diff -r 5b960b9768c4 -r 991fbbdc1540 sys/kern/kern_turnstile.c
--- a/sys/kern/kern_turnstile.c Thu Mar 26 19:42:39 2020 +0000
+++ b/sys/kern/kern_turnstile.c Thu Mar 26 19:46:42 2020 +0000
@@ -1,7 +1,8 @@
-/*     $NetBSD: kern_turnstile.c,v 1.36 2020/01/21 20:31:57 ad Exp $   */
+/*     $NetBSD: kern_turnstile.c,v 1.37 2020/03/26 19:46:42 ad Exp $   */
 
 /*-
- * Copyright (c) 2002, 2006, 2007, 2009, 2019 The NetBSD Foundation, Inc.
+ * Copyright (c) 2002, 2006, 2007, 2009, 2019, 2020
+ *     The NetBSD Foundation, Inc.
  * All rights reserved.
  *
  * This code is derived from software contributed to The NetBSD Foundation
@@ -60,7 +61,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_turnstile.c,v 1.36 2020/01/21 20:31:57 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_turnstile.c,v 1.37 2020/03/26 19:46:42 ad Exp $");
 
 #include <sys/param.h>
 #include <sys/lockdebug.h>
@@ -397,8 +398,8 @@
                 */
                ts = l->l_ts;
                KASSERT(TS_ALL_WAITERS(ts) == 0);
-               KASSERT(TAILQ_EMPTY(&ts->ts_sleepq[TS_READER_Q]) &&
-                       TAILQ_EMPTY(&ts->ts_sleepq[TS_WRITER_Q]));
+               KASSERT(LIST_EMPTY(&ts->ts_sleepq[TS_READER_Q]) &&
+                       LIST_EMPTY(&ts->ts_sleepq[TS_WRITER_Q]));
                ts->ts_obj = obj;
                ts->ts_inheritor = NULL;
                LIST_INSERT_HEAD(tc, ts, ts_chain);
@@ -416,8 +417,8 @@
 
                KASSERT(ts->ts_obj == obj);
                KASSERT(TS_ALL_WAITERS(ts) != 0);
-               KASSERT(!TAILQ_EMPTY(&ts->ts_sleepq[TS_READER_Q]) ||
-                       !TAILQ_EMPTY(&ts->ts_sleepq[TS_WRITER_Q]));
+               KASSERT(!LIST_EMPTY(&ts->ts_sleepq[TS_READER_Q]) ||
+                       !LIST_EMPTY(&ts->ts_sleepq[TS_WRITER_Q]));
        }
 
        sq = &ts->ts_sleepq[q];
@@ -476,7 +477,7 @@
 
        if (nl != NULL) {
 #if defined(DEBUG) || defined(LOCKDEBUG)
-               TAILQ_FOREACH(l, sq, l_sleepchain) {
+               LIST_FOREACH(l, sq, l_sleepchain) {
                        if (l == nl)
                                break;
                }
@@ -486,7 +487,7 @@
                turnstile_remove(ts, nl, q);
        } else {
                while (count-- > 0) {
-                       l = TAILQ_FIRST(sq);
+                       l = LIST_FIRST(sq);
                        KASSERT(l != NULL);
                        turnstile_remove(ts, l, q);
                }
diff -r 5b960b9768c4 -r 991fbbdc1540 sys/kern/sys_select.c
--- a/sys/kern/sys_select.c     Thu Mar 26 19:42:39 2020 +0000
+++ b/sys/kern/sys_select.c     Thu Mar 26 19:46:42 2020 +0000
@@ -1,7 +1,7 @@
-/*     $NetBSD: sys_select.c,v 1.52 2020/02/15 17:09:24 ad Exp $       */
+/*     $NetBSD: sys_select.c,v 1.53 2020/03/26 19:46:42 ad Exp $       */
 
 /*-
- * Copyright (c) 2007, 2008, 2009, 2010, 2019 The NetBSD Foundation, Inc.
+ * Copyright (c) 2007, 2008, 2009, 2010, 2019, 2020 The NetBSD Foundation, Inc.
  * All rights reserved.
  *
  * This code is derived from software contributed to The NetBSD Foundation
@@ -84,7 +84,7 @@
  */
 
 #include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: sys_select.c,v 1.52 2020/02/15 17:09:24 ad Exp $");
+__KERNEL_RCSID(0, "$NetBSD: sys_select.c,v 1.53 2020/03/26 19:46:42 ad Exp $");
 
 #include <sys/param.h>
 #include <sys/systm.h>
@@ -136,8 +136,14 @@
        POLLRDBAND
 };
 
+/* 
+ * LWPs are woken using the sleep queue only due to a collision, the case
+ * with the maximum Suck Factor.  Save the cost of sorting for named waiters
+ * by inserting in LIFO order.  In the future it would be preferable to not
+ * enqueue LWPs at all, unless subject to a collision.
+ */
 syncobj_t select_sobj = {
-       .sobj_flag      = SOBJ_SLEEPQ_FIFO,
+       .sobj_flag      = SOBJ_SLEEPQ_LIFO,
        .sobj_unsleep   = sleepq_unsleep,
        .sobj_changepri = sleepq_changepri,
        .sobj_lendpri   = sleepq_lendpri,
diff -r 5b960b9768c4 -r 991fbbdc1540 sys/sys/condvar.h
--- a/sys/sys/condvar.h Thu Mar 26 19:42:39 2020 +0000
+++ b/sys/sys/condvar.h Thu Mar 26 19:46:42 2020 +0000
@@ -1,7 +1,7 @@
-/*     $NetBSD: condvar.h,v 1.14 2017/07/03 03:12:42 riastradh Exp $   */
+/*     $NetBSD: condvar.h,v 1.15 2020/03/26 19:46:42 ad Exp $  */
 
 /*-
- * Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc.
+ * Copyright (c) 2006, 2007, 2008, 2020 The NetBSD Foundation, Inc.
  * All rights reserved.
  *
  * This code is derived from software contributed to The NetBSD Foundation
@@ -33,7 +33,7 @@
 #define        _SYS_CONDVAR_H_
 
 typedef struct kcondvar {
-       void            *cv_opaque[3];
+       void            *cv_opaque[2];
 } kcondvar_t;



Home | Main Index | Thread Index | Old Index