Module Name: src
Committed By: ad
Date: Thu Mar 26 19:46:42 UTC 2020
Modified Files:
src/sys/kern: kern_condvar.c kern_sleepq.c kern_turnstile.c
sys_select.c
src/sys/sys: condvar.h lwp.h sleepq.h
Log Message:
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.
To generate a diff of this commit:
cvs rdiff -u -r1.43 -r1.44 src/sys/kern/kern_condvar.c
cvs rdiff -u -r1.62 -r1.63 src/sys/kern/kern_sleepq.c
cvs rdiff -u -r1.36 -r1.37 src/sys/kern/kern_turnstile.c
cvs rdiff -u -r1.52 -r1.53 src/sys/kern/sys_select.c
cvs rdiff -u -r1.14 -r1.15 src/sys/sys/condvar.h
cvs rdiff -u -r1.202 -r1.203 src/sys/sys/lwp.h
cvs rdiff -u -r1.27 -r1.28 src/sys/sys/sleepq.h
Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.
Modified files:
Index: src/sys/kern/kern_condvar.c
diff -u src/sys/kern/kern_condvar.c:1.43 src/sys/kern/kern_condvar.c:1.44
--- src/sys/kern/kern_condvar.c:1.43 Sat Feb 15 17:09:24 2020
+++ src/sys/kern/kern_condvar.c Thu Mar 26 19:46:42 2020
@@ -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 @@ __KERNEL_RCSID(0, "$NetBSD: kern_condvar
/*
* 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 @@ cv_signal(kcondvar_t *cv)
/* 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 @@ cv_wakeup_one(kcondvar_t *cv)
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 @@ cv_broadcast(kcondvar_t *cv)
/* 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 @@ cv_wakeup_all(kcondvar_t *cv)
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 @@ bool
cv_has_waiters(kcondvar_t *cv)
{
- return !TAILQ_EMPTY(CV_SLEEPQ(cv));
+ return !LIST_EMPTY(CV_SLEEPQ(cv));
}
/*
Index: src/sys/kern/kern_sleepq.c
diff -u src/sys/kern/kern_sleepq.c:1.62 src/sys/kern/kern_sleepq.c:1.63
--- src/sys/kern/kern_sleepq.c:1.62 Tue Mar 24 21:05:06 2020
+++ src/sys/kern/kern_sleepq.c Thu Mar 26 19:46:42 2020
@@ -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 @@ void
sleepq_init(sleepq_t *sq)
{
- TAILQ_INIT(sq);
+ LIST_INIT(sq);
}
/*
@@ -116,7 +116,7 @@ sleepq_remove(sleepq_t *sq, lwp_t *l)
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 @@ sleepq_insert(sleepq_t *sq, lwp_t *l, sy
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 @@ sleepq_wake(sleepq_t *sq, wchan_t wchan,
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 @@ sleepq_reinsert(sleepq_t *sq, lwp_t *l)
* 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);
}
Index: src/sys/kern/kern_turnstile.c
diff -u src/sys/kern/kern_turnstile.c:1.36 src/sys/kern/kern_turnstile.c:1.37
--- src/sys/kern/kern_turnstile.c:1.36 Tue Jan 21 20:31:57 2020
+++ src/sys/kern/kern_turnstile.c Thu Mar 26 19:46:42 2020
@@ -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 @@ turnstile_block(turnstile_t *ts, int q,
*/
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 @@ turnstile_block(turnstile_t *ts, int q,
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 @@ turnstile_wakeup(turnstile_t *ts, int q,
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_wakeup(turnstile_t *ts, int q,
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);
}
Index: src/sys/kern/sys_select.c
diff -u src/sys/kern/sys_select.c:1.52 src/sys/kern/sys_select.c:1.53
--- src/sys/kern/sys_select.c:1.52 Sat Feb 15 17:09:24 2020
+++ src/sys/kern/sys_select.c Thu Mar 26 19:46:42 2020
@@ -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 @@ static const int sel_flag[] = {
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,
Index: src/sys/sys/condvar.h
diff -u src/sys/sys/condvar.h:1.14 src/sys/sys/condvar.h:1.15
--- src/sys/sys/condvar.h:1.14 Mon Jul 3 03:12:42 2017
+++ src/sys/sys/condvar.h Thu Mar 26 19:46:42 2020
@@ -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;
#ifdef _KERNEL
Index: src/sys/sys/lwp.h
diff -u src/sys/sys/lwp.h:1.202 src/sys/sys/lwp.h:1.203
--- src/sys/sys/lwp.h:1.202 Sat Feb 15 18:12:15 2020
+++ src/sys/sys/lwp.h Thu Mar 26 19:46:42 2020
@@ -1,4 +1,4 @@
-/* $NetBSD: lwp.h,v 1.202 2020/02/15 18:12:15 ad Exp $ */
+/* $NetBSD: lwp.h,v 1.203 2020/03/26 19:46:42 ad Exp $ */
/*
* Copyright (c) 2001, 2006, 2007, 2008, 2009, 2010, 2019, 2020
@@ -125,7 +125,7 @@ struct lwp {
/* Synchronisation. */
struct turnstile *l_ts; /* l: current turnstile */
struct syncobj *l_syncobj; /* l: sync object operations set */
- TAILQ_ENTRY(lwp) l_sleepchain; /* l: sleep queue */
+ LIST_ENTRY(lwp) l_sleepchain; /* l: sleep queue */
wchan_t l_wchan; /* l: sleep address */
const char *l_wmesg; /* l: reason for sleep */
struct sleepq *l_sleepq; /* l: current sleep queue */
Index: src/sys/sys/sleepq.h
diff -u src/sys/sys/sleepq.h:1.27 src/sys/sys/sleepq.h:1.28
--- src/sys/sys/sleepq.h:1.27 Mon Dec 16 19:43:36 2019
+++ src/sys/sys/sleepq.h Thu Mar 26 19:46:42 2020
@@ -1,7 +1,8 @@
-/* $NetBSD: sleepq.h,v 1.27 2019/12/16 19:43:36 ad Exp $ */
+/* $NetBSD: sleepq.h,v 1.28 2020/03/26 19:46:42 ad Exp $ */
/*-
- * Copyright (c) 2002, 2006, 2007, 2008, 2009, 2019 The NetBSD Foundation, Inc.
+ * Copyright (c) 2002, 2006, 2007, 2008, 2009, 2019, 2020
+ * The NetBSD Foundation, Inc.
* All rights reserved.
*
* This code is derived from software contributed to The NetBSD Foundation
@@ -49,7 +50,7 @@
#define SLEEPTAB_HASH_MASK (SLEEPTAB_HASH_SIZE - 1)
#define SLEEPTAB_HASH(wchan) (((uintptr_t)(wchan) >> 8) & SLEEPTAB_HASH_MASK)
-TAILQ_HEAD(sleepq, lwp);
+LIST_HEAD(sleepq, lwp);
typedef struct sleepq sleepq_t;
@@ -169,7 +170,7 @@ typedef struct tschain tschain_t;
((ts)->ts_waiters[TS_READER_Q] + \
(ts)->ts_waiters[TS_WRITER_Q])
-#define TS_FIRST(ts, q) (TAILQ_FIRST(&(ts)->ts_sleepq[(q)]))
+#define TS_FIRST(ts, q) (LIST_FIRST(&(ts)->ts_sleepq[(q)]))
#ifdef _KERNEL
