Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/sys Add an implementation of passive serialization as descri...
details: https://anonhg.NetBSD.org/src/rev/1f2b0bdcffe7
branches: trunk
changeset: 767789:1f2b0bdcffe7
user: christos <christos%NetBSD.org@localhost>
date: Sat Jul 30 17:01:04 2011 +0000
description:
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.
diffstat:
sys/conf/files | 3 +-
sys/kern/init_main.c | 9 +-
sys/kern/kern_lwp.c | 9 +-
sys/kern/kern_synch.c | 8 +-
sys/kern/subr_pserialize.c | 268 +++++++++++++++++++++++++++++++++++++++++++++
sys/sys/pserialize.h | 49 ++++++++
6 files changed, 339 insertions(+), 7 deletions(-)
diffs (truncated from 459 to 300 lines):
diff -r ba38768aed44 -r 1f2b0bdcffe7 sys/conf/files
--- a/sys/conf/files Sat Jul 30 16:37:05 2011 +0000
+++ b/sys/conf/files Sat Jul 30 17:01:04 2011 +0000
@@ -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
diff -r ba38768aed44 -r 1f2b0bdcffe7 sys/kern/init_main.c
--- a/sys/kern/init_main.c Sat Jul 30 16:37:05 2011 +0000
+++ b/sys/kern/init_main.c Sat Jul 30 17:01:04 2011 +0000
@@ -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();
diff -r ba38768aed44 -r 1f2b0bdcffe7 sys/kern/kern_lwp.c
--- a/sys/kern/kern_lwp.c Sat Jul 30 16:37:05 2011 +0000
+++ b/sys/kern/kern_lwp.c Sat Jul 30 17:01:04 2011 +0000
@@ -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) {
diff -r ba38768aed44 -r 1f2b0bdcffe7 sys/kern/kern_synch.c
--- a/sys/kern/kern_synch.c Sat Jul 30 16:37:05 2011 +0000
+++ b/sys/kern/kern_synch.c Sat Jul 30 17:01:04 2011 +0000
@@ -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;
diff -r ba38768aed44 -r 1f2b0bdcffe7 sys/kern/subr_pserialize.c
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/sys/kern/subr_pserialize.c Sat Jul 30 17:01:04 2011 +0000
@@ -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);
Home |
Main Index |
Thread Index |
Old Index