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_ */