Module Name: src
Committed By: christos
Date: Sat Jul 30 17:01:05 UTC 2011
Modified Files:
src/sys/conf: files
src/sys/kern: init_main.c kern_lwp.c kern_synch.c
Added Files:
src/sys/kern: subr_pserialize.c
src/sys/sys: pserialize.h
Log Message:
Add an implementation of passive serialization as described in expired
US patent 4809168. This is a reader / writer synchronization mechanism,
designed for lock-less read operations.
To generate a diff of this commit:
cvs rdiff -u -r1.1021 -r1.1022 src/sys/conf/files
cvs rdiff -u -r1.433 -r1.434 src/sys/kern/init_main.c
cvs rdiff -u -r1.160 -r1.161 src/sys/kern/kern_lwp.c
cvs rdiff -u -r1.289 -r1.290 src/sys/kern/kern_synch.c
cvs rdiff -u -r0 -r1.1 src/sys/kern/subr_pserialize.c
cvs rdiff -u -r0 -r1.1 src/sys/sys/pserialize.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/conf/files
diff -u src/sys/conf/files:1.1021 src/sys/conf/files:1.1022
--- src/sys/conf/files:1.1021 Thu Jul 28 09:42:16 2011
+++ src/sys/conf/files Sat Jul 30 13:01:04 2011
@@ -1,4 +1,4 @@
-# $NetBSD: files,v 1.1021 2011/07/28 13:42:16 uebayasi Exp $
+# $NetBSD: files,v 1.1022 2011/07/30 17:01:04 christos Exp $
# @(#)files.newconf 7.5 (Berkeley) 5/10/93
version 20100430
@@ -1543,6 +1543,7 @@
file kern/subr_pool.c
file kern/subr_prf.c
file kern/subr_prof.c
+file kern/subr_pserialize.c
file kern/subr_specificdata.c
file kern/subr_tftproot.c tftproot
file kern/subr_time.c
Index: src/sys/kern/init_main.c
diff -u src/sys/kern/init_main.c:1.433 src/sys/kern/init_main.c:1.434
--- src/sys/kern/init_main.c:1.433 Sat Jul 2 13:53:50 2011
+++ src/sys/kern/init_main.c Sat Jul 30 13:01:04 2011
@@ -1,4 +1,4 @@
-/* $NetBSD: init_main.c,v 1.433 2011/07/02 17:53:50 bouyer Exp $ */
+/* $NetBSD: init_main.c,v 1.434 2011/07/30 17:01:04 christos Exp $ */
/*-
* Copyright (c) 2008, 2009 The NetBSD Foundation, Inc.
@@ -97,7 +97,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: init_main.c,v 1.433 2011/07/02 17:53:50 bouyer Exp $");
+__KERNEL_RCSID(0, "$NetBSD: init_main.c,v 1.434 2011/07/30 17:01:04 christos Exp $");
#include "opt_ddb.h"
#include "opt_ipsec.h"
@@ -149,6 +149,7 @@
#include <sys/socketvar.h>
#include <sys/protosw.h>
#include <sys/percpu.h>
+#include <sys/pserialize.h>
#include <sys/pset.h>
#include <sys/sysctl.h>
#include <sys/reboot.h>
@@ -297,6 +298,7 @@
kernel_lock_init();
once_init();
+
mutex_init(&cpu_lock, MUTEX_DEFAULT, IPL_NONE);
kernconfig_lock_init();
kthread_sysinit();
@@ -322,6 +324,9 @@
mutex_obj_init();
rw_obj_init();
+ /* Passive serialization. */
+ pserialize_init();
+
/* Initialize the extent manager. */
extent_init();
Index: src/sys/kern/kern_lwp.c
diff -u src/sys/kern/kern_lwp.c:1.160 src/sys/kern/kern_lwp.c:1.161
--- src/sys/kern/kern_lwp.c:1.160 Tue Jul 26 09:03:57 2011
+++ src/sys/kern/kern_lwp.c Sat Jul 30 13:01:04 2011
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_lwp.c,v 1.160 2011/07/26 13:03:57 yamt Exp $ */
+/* $NetBSD: kern_lwp.c,v 1.161 2011/07/30 17:01:04 christos Exp $ */
/*-
* Copyright (c) 2001, 2006, 2007, 2008, 2009 The NetBSD Foundation, Inc.
@@ -211,7 +211,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_lwp.c,v 1.160 2011/07/26 13:03:57 yamt Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_lwp.c,v 1.161 2011/07/30 17:01:04 christos Exp $");
#include "opt_ddb.h"
#include "opt_lockdebug.h"
@@ -230,6 +230,7 @@
#include <sys/syscallargs.h>
#include <sys/syscall_stats.h>
#include <sys/kauth.h>
+#include <sys/pserialize.h>
#include <sys/sleepq.h>
#include <sys/lockdebug.h>
#include <sys/kmem.h>
@@ -865,6 +866,10 @@
KPREEMPT_DISABLE(new);
spl0();
pmap_activate(new);
+
+ /* Note trip through cpu_switchto(). */
+ pserialize_switchpoint();
+
LOCKDEBUG_BARRIER(NULL, 0);
KPREEMPT_ENABLE(new);
if ((new->l_pflag & LP_MPSAFE) == 0) {
Index: src/sys/kern/kern_synch.c
diff -u src/sys/kern/kern_synch.c:1.289 src/sys/kern/kern_synch.c:1.290
--- src/sys/kern/kern_synch.c:1.289 Fri May 13 18:16:43 2011
+++ src/sys/kern/kern_synch.c Sat Jul 30 13:01:04 2011
@@ -1,4 +1,4 @@
-/* $NetBSD: kern_synch.c,v 1.289 2011/05/13 22:16:43 rmind Exp $ */
+/* $NetBSD: kern_synch.c,v 1.290 2011/07/30 17:01:04 christos Exp $ */
/*-
* Copyright (c) 1999, 2000, 2004, 2006, 2007, 2008, 2009
@@ -69,7 +69,7 @@
*/
#include <sys/cdefs.h>
-__KERNEL_RCSID(0, "$NetBSD: kern_synch.c,v 1.289 2011/05/13 22:16:43 rmind Exp $");
+__KERNEL_RCSID(0, "$NetBSD: kern_synch.c,v 1.290 2011/07/30 17:01:04 christos Exp $");
#include "opt_kstack.h"
#include "opt_perfctrs.h"
@@ -86,6 +86,7 @@
#include <sys/pmc.h>
#endif
#include <sys/cpu.h>
+#include <sys/pserialize.h>
#include <sys/resourcevar.h>
#include <sys/sched.h>
#include <sys/sa.h>
@@ -808,6 +809,9 @@
l->l_lwpctl->lc_pctr++;
}
+ /* Note trip through cpu_switchto(). */
+ pserialize_switchpoint();
+
KASSERT(l->l_cpu == ci);
splx(oldspl);
retval = 1;
Added files:
Index: src/sys/kern/subr_pserialize.c
diff -u /dev/null src/sys/kern/subr_pserialize.c:1.1
--- /dev/null Sat Jul 30 13:01:05 2011
+++ src/sys/kern/subr_pserialize.c Sat Jul 30 13:01:04 2011
@@ -0,0 +1,268 @@
+/* $NetBSD: subr_pserialize.c,v 1.1 2011/07/30 17:01:04 christos Exp $ */
+
+/*-
+ * Copyright (c) 2010, 2011 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/*
+ * Passive serialization.
+ *
+ * Implementation accurately matches the lapsed US patent 4809168, therefore
+ * code is patent-free in the United States. Your use of this code is at
+ * your own risk.
+ *
+ * Note for NetBSD developers: all changes to this source file must be
+ * approved by the <core>.
+ */
+
+#include <sys/cdefs.h>
+__KERNEL_RCSID(0, "$NetBSD: subr_pserialize.c,v 1.1 2011/07/30 17:01:04 christos Exp $");
+
+#include <sys/param.h>
+
+#include <sys/condvar.h>
+#include <sys/cpu.h>
+#include <sys/kmem.h>
+#include <sys/mutex.h>
+#include <sys/pserialize.h>
+#include <sys/queue.h>
+#include <sys/xcall.h>
+
+struct pserialize {
+ TAILQ_ENTRY(pserialize) psz_chain;
+ lwp_t * psz_owner;
+ kcondvar_t psz_notifier;
+ kcpuset_t * psz_target;
+ kcpuset_t * psz_pass;
+};
+
+static u_int psz_work_todo __cacheline_aligned;
+static kmutex_t psz_lock __cacheline_aligned;
+static struct evcnt psz_ev_excl __cacheline_aligned;
+
+/*
+ * As defined in "Method 1":
+ * q0: "0 MP checkpoints have occured".
+ * q1: "1 MP checkpoint has occured".
+ * q2: "2 MP checkpoints have occured".
+ */
+static TAILQ_HEAD(, pserialize) psz_queue0 __cacheline_aligned;
+static TAILQ_HEAD(, pserialize) psz_queue1 __cacheline_aligned;
+static TAILQ_HEAD(, pserialize) psz_queue2 __cacheline_aligned;
+
+/*
+ * pserialize_init:
+ *
+ * Initialize passive serialization structures.
+ */
+void
+pserialize_init(void)
+{
+
+ psz_work_todo = 0;
+ TAILQ_INIT(&psz_queue0);
+ TAILQ_INIT(&psz_queue1);
+ TAILQ_INIT(&psz_queue2);
+ mutex_init(&psz_lock, MUTEX_DEFAULT, IPL_SCHED);
+ evcnt_attach_dynamic(&psz_ev_excl, EVCNT_TYPE_MISC, NULL,
+ "pserialize", "exclusive access");
+}
+
+/*
+ * pserialize_create:
+ *
+ * Create and initialize a passive serialization object.
+ */
+pserialize_t
+pserialize_create(void)
+{
+ pserialize_t psz;
+
+ psz = kmem_zalloc(sizeof(struct pserialize), KM_SLEEP);
+ cv_init(&psz->psz_notifier, "psrlz");
+ psz->psz_target = kcpuset_create();
+ psz->psz_pass = kcpuset_create();
+ psz->psz_owner = NULL;
+
+ return psz;
+}
+
+/*
+ * pserialize_destroy:
+ *
+ * Destroy a passive serialization object.
+ */
+void
+pserialize_destroy(pserialize_t psz)
+{
+
+ KASSERT(psz->psz_owner == NULL);
+
+ cv_destroy(&psz->psz_notifier);
+ kcpuset_destroy(psz->psz_target);
+ kcpuset_destroy(psz->psz_pass);
+ kmem_free(psz, sizeof(struct pserialize));
+}
+
+/*
+ * pserialize_perform:
+ *
+ * Perform the write side of passive serialization. The calling
+ * thread holds an exclusive lock on the data object(s) being updated.
+ * We wait until every processor in the system has made at least two
+ * passes through cpu_swichto(). The wait is made with the caller's
+ * update lock held, but is short term.
+ */
+void
+pserialize_perform(pserialize_t psz)
+{
+
+ KASSERT(!cpu_intr_p());
+ KASSERT(!cpu_softintr_p());
+
+ if (__predict_false(panicstr != NULL)) {
+ return;
+ }
+ KASSERT(psz->psz_owner == NULL);
+ KASSERT(kcpuset_iszero(psz->psz_target));
+ KASSERT(ncpu > 0);
+
+ /*
+ * Set up the object and put it onto the queue. The lock
+ * activity here provides the necessary memory barrier to
+ * make the caller's data update completely visible to
+ * other processors.
+ */
+ psz->psz_owner = curlwp;
+ kcpuset_fill(psz->psz_target);
+ kcpuset_zero(psz->psz_pass);
+
+ mutex_spin_enter(&psz_lock);
+ TAILQ_INSERT_TAIL(&psz_queue0, psz, psz_chain);
+ psz_work_todo++;
+ mutex_spin_exit(&psz_lock);
+
+ /*
+ * Force some context switch activity on every CPU, as the system
+ * may not be busy. Note: should pass the point twice.
+ */
+ xc_broadcast(XC_HIGHPRI, (xcfunc_t)nullop, NULL, NULL);
+ xc_broadcast(XC_HIGHPRI, (xcfunc_t)nullop, NULL, NULL);
+
+ /*
+ * Wait for all CPUs to cycle through mi_switch() twice.
+ * The last one through will remove our update from the
+ * queue and awaken us.
+ */
+ mutex_spin_enter(&psz_lock);
+ while (!kcpuset_iszero(psz->psz_target)) {
+ cv_wait(&psz->psz_notifier, &psz_lock);
+ }
+ psz_ev_excl.ev_count++;
+ mutex_spin_exit(&psz_lock);
+
+ psz->psz_owner = NULL;
+}
+
+int
+pserialize_read_enter(void)
+{
+
+ KASSERT(!cpu_intr_p());
+ return splsoftclock();
+}
+
+void
+pserialize_read_exit(int s)
+{
+
+ splx(s);
+}
+
+/*
+ * pserialize_switchpoint:
+ *
+ * Monitor system context switch activity. Called from machine
+ * independent code after mi_switch() returns.
+ */
+void
+pserialize_switchpoint(void)
+{
+ pserialize_t psz, next;
+ cpuid_t cid;
+
+ /*
+ * If no updates pending, bail out. No need to lock in order to
+ * test psz_work_todo; the only ill effect of missing an update
+ * would be to delay LWPs waiting in pserialize_perform(). That
+ * will not happen because updates are on the queue before an
+ * xcall is generated (serialization) to tickle every CPU.
+ */
+ if (__predict_true(psz_work_todo == 0)) {
+ return;
+ }
+ mutex_spin_enter(&psz_lock);
+ cid = cpu_index(curcpu());
+
+ /*
+ * At first, scan through the second queue and update each request,
+ * if passed all processors, then transfer to the third queue.
+ */
+ for (psz = TAILQ_FIRST(&psz_queue1); psz != NULL; psz = next) {
+ next = TAILQ_NEXT(psz, psz_chain);
+ if (!kcpuset_match(psz->psz_pass, psz->psz_target)) {
+ kcpuset_set(cid, psz->psz_pass);
+ continue;
+ }
+ kcpuset_zero(psz->psz_pass);
+ TAILQ_REMOVE(&psz_queue1, psz, psz_chain);
+ TAILQ_INSERT_TAIL(&psz_queue2, psz, psz_chain);
+ }
+ /*
+ * Scan through the first queue and update each request,
+ * if passed all processors, then move to the second queue.
+ */
+ for (psz = TAILQ_FIRST(&psz_queue0); psz != NULL; psz = next) {
+ next = TAILQ_NEXT(psz, psz_chain);
+ if (!kcpuset_match(psz->psz_pass, psz->psz_target)) {
+ kcpuset_set(cid, psz->psz_pass);
+ continue;
+ }
+ kcpuset_zero(psz->psz_pass);
+ TAILQ_REMOVE(&psz_queue0, psz, psz_chain);
+ TAILQ_INSERT_TAIL(&psz_queue1, psz, psz_chain);
+ }
+ /*
+ * Process the third queue: entries have been seen twice on every
+ * processor, remove from the queue and notify the updating thread.
+ */
+ while ((psz = TAILQ_FIRST(&psz_queue2)) != NULL) {
+ TAILQ_REMOVE(&psz_queue2, psz, psz_chain);
+ kcpuset_zero(psz->psz_target);
+ cv_signal(&psz->psz_notifier);
+ psz_work_todo--;
+ }
+ mutex_spin_exit(&psz_lock);
+}
Index: src/sys/sys/pserialize.h
diff -u /dev/null src/sys/sys/pserialize.h:1.1
--- /dev/null Sat Jul 30 13:01:05 2011
+++ src/sys/sys/pserialize.h Sat Jul 30 13:01:04 2011
@@ -0,0 +1,49 @@
+/* $NetBSD: pserialize.h,v 1.1 2011/07/30 17:01:04 christos Exp $ */
+
+/*-
+ * Copyright (c) 2010, 2011 The NetBSD Foundation, Inc.
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
+ * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_PSERIALIZE_H_
+#define _SYS_PSERIALIZE_H_
+
+#ifdef _KERNEL
+
+struct pserialize;
+typedef struct pserialize *pserialize_t;
+
+void pserialize_init(void);
+void pserialize_switchpoint(void);
+
+pserialize_t pserialize_create(void);
+void pserialize_destroy(pserialize_t);
+void pserialize_perform(pserialize_t);
+
+int pserialize_read_enter(void);
+void pserialize_read_exit(int);
+
+#endif /* _KERNEL */
+
+#endif /* _SYS_PSERIALIZE_H_ */
