1/* $NetBSD: subr_pserialize.c,v 1.8 2015/06/12 19:18:30 dholland Exp $ */
2
3/*-
4 * Copyright (c) 2010, 2011 The NetBSD Foundation, Inc.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
17 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
18 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
20 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/*
30 * Passive serialization.
31 *
32 * Implementation accurately matches the lapsed US patent 4809168, therefore
33 * code is patent-free in the United States. Your use of this code is at
34 * your own risk.
35 *
36 * Note for NetBSD developers: all changes to this source file must be
37 * approved by the <core>.
38 */
39
40#include <sys/cdefs.h>
41__KERNEL_RCSID(0, "$NetBSD: subr_pserialize.c,v 1.8 2015/06/12 19:18:30 dholland Exp $");
42
43#include <sys/param.h>
44
45#include <sys/condvar.h>
46#include <sys/cpu.h>
47#include <sys/evcnt.h>
48#include <sys/kmem.h>
49#include <sys/mutex.h>
50#include <sys/pserialize.h>
51#include <sys/proc.h>
52#include <sys/queue.h>
53#include <sys/xcall.h>
54
55struct pserialize {
56 TAILQ_ENTRY(pserialize) psz_chain;
57 lwp_t * psz_owner;
58 kcpuset_t * psz_target;
59 kcpuset_t * psz_pass;
60};
61
62static u_int psz_work_todo __cacheline_aligned;
63static kmutex_t psz_lock __cacheline_aligned;
64static struct evcnt psz_ev_excl __cacheline_aligned;
65
66/*
67 * As defined in "Method 1":
68 * q0: "0 MP checkpoints have occured".
69 * q1: "1 MP checkpoint has occured".
70 * q2: "2 MP checkpoints have occured".
71 */
72static TAILQ_HEAD(, pserialize) psz_queue0 __cacheline_aligned;
73static TAILQ_HEAD(, pserialize) psz_queue1 __cacheline_aligned;
74static TAILQ_HEAD(, pserialize) psz_queue2 __cacheline_aligned;
75
76/*
77 * pserialize_init:
78 *
79 * Initialize passive serialization structures.
80 */
81void
82pserialize_init(void)
83{
84
85 psz_work_todo = 0;
86 TAILQ_INIT(&psz_queue0);
87 TAILQ_INIT(&psz_queue1);
88 TAILQ_INIT(&psz_queue2);
89 mutex_init(&psz_lock, MUTEX_DEFAULT, IPL_SCHED);
90 evcnt_attach_dynamic(&psz_ev_excl, EVCNT_TYPE_MISC, NULL,
91 "pserialize", "exclusive access");
92}
93
94/*
95 * pserialize_create:
96 *
97 * Create and initialize a passive serialization object.
98 */
99pserialize_t
100pserialize_create(void)
101{
102 pserialize_t psz;
103
104 psz = kmem_zalloc(sizeof(struct pserialize), KM_SLEEP);
105 kcpuset_create(&psz->psz_target, true);
106 kcpuset_create(&psz->psz_pass, true);
107 psz->psz_owner = NULL;
108
109 return psz;
110}
111
112/*
113 * pserialize_destroy:
114 *
115 * Destroy a passive serialization object.
116 */
117void
118pserialize_destroy(pserialize_t psz)
119{
120
121 KASSERT(psz->psz_owner == NULL);
122
123 kcpuset_destroy(psz->psz_target);
124 kcpuset_destroy(psz->psz_pass);
125 kmem_free(psz, sizeof(struct pserialize));
126}
127
128/*
129 * pserialize_perform:
130 *
131 * Perform the write side of passive serialization. The calling
132 * thread holds an exclusive lock on the data object(s) being updated.
133 * We wait until every processor in the system has made at least two
134 * passes through cpu_switchto(). The wait is made with the caller's
135 * update lock held, but is short term.
136 */
137void
138pserialize_perform(pserialize_t psz)
139{
140 uint64_t xc;
141
142 KASSERT(!cpu_intr_p());
143 KASSERT(!cpu_softintr_p());
144
145 if (__predict_false(panicstr != NULL)) {
146 return;
147 }
148 KASSERT(psz->psz_owner == NULL);
149 KASSERT(ncpu > 0);
150
151 /*
152 * Set up the object and put it onto the queue. The lock
153 * activity here provides the necessary memory barrier to
154 * make the caller's data update completely visible to
155 * other processors.
156 */
157 psz->psz_owner = curlwp;
158 kcpuset_copy(psz->psz_target, kcpuset_running);
159 kcpuset_zero(psz->psz_pass);
160
161 mutex_spin_enter(&psz_lock);
162 TAILQ_INSERT_TAIL(&psz_queue0, psz, psz_chain);
163 psz_work_todo++;
164
165 do {
166 mutex_spin_exit(&psz_lock);
167
168 /*
169 * Force some context switch activity on every CPU, as
170 * the system may not be busy. Pause to not flood.
171 */
172 xc = xc_broadcast(XC_HIGHPRI, (xcfunc_t)nullop, NULL, NULL);
173 xc_wait(xc);
174 kpause("psrlz", false, 1, NULL);
175
176 mutex_spin_enter(&psz_lock);
177 } while (!kcpuset_iszero(psz->psz_target));
178
179 psz_ev_excl.ev_count++;
180 mutex_spin_exit(&psz_lock);
181
182 psz->psz_owner = NULL;
183}
184
185int
186pserialize_read_enter(void)
187{
188
189 KASSERT(!cpu_intr_p());
190 return splsoftserial();
191}
192
193void
194pserialize_read_exit(int s)
195{
196
197 splx(s);
198}
199
200/*
201 * pserialize_switchpoint:
202 *
203 * Monitor system context switch activity. Called from machine
204 * independent code after mi_switch() returns.
205 */
206void
207pserialize_switchpoint(void)
208{
209 pserialize_t psz, next;
210 cpuid_t cid;
211
212 /*
213 * If no updates pending, bail out. No need to lock in order to
214 * test psz_work_todo; the only ill effect of missing an update
215 * would be to delay LWPs waiting in pserialize_perform(). That
216 * will not happen because updates are on the queue before an
217 * xcall is generated (serialization) to tickle every CPU.
218 */
219 if (__predict_true(psz_work_todo == 0)) {
220 return;
221 }
222 mutex_spin_enter(&psz_lock);
223 cid = cpu_index(curcpu());
224
225 /*
226 * At first, scan through the second queue and update each request,
227 * if passed all processors, then transfer to the third queue.
228 */
229 for (psz = TAILQ_FIRST(&psz_queue1); psz != NULL; psz = next) {
230 next = TAILQ_NEXT(psz, psz_chain);
231 kcpuset_set(psz->psz_pass, cid);
232 if (!kcpuset_match(psz->psz_pass, psz->psz_target)) {
233 continue;
234 }
235 kcpuset_zero(psz->psz_pass);
236 TAILQ_REMOVE(&psz_queue1, psz, psz_chain);
237 TAILQ_INSERT_TAIL(&psz_queue2, psz, psz_chain);
238 }
239 /*
240 * Scan through the first queue and update each request,
241 * if passed all processors, then move to the second queue.
242 */
243 for (psz = TAILQ_FIRST(&psz_queue0); psz != NULL; psz = next) {
244 next = TAILQ_NEXT(psz, psz_chain);
245 kcpuset_set(psz->psz_pass, cid);
246 if (!kcpuset_match(psz->psz_pass, psz->psz_target)) {
247 continue;
248 }
249 kcpuset_zero(psz->psz_pass);
250 TAILQ_REMOVE(&psz_queue0, psz, psz_chain);
251 TAILQ_INSERT_TAIL(&psz_queue1, psz, psz_chain);
252 }
253 /*
254 * Process the third queue: entries have been seen twice on every
255 * processor, remove from the queue and notify the updating thread.
256 */
257 while ((psz = TAILQ_FIRST(&psz_queue2)) != NULL) {
258 TAILQ_REMOVE(&psz_queue2, psz, psz_chain);
259 kcpuset_zero(psz->psz_target);
260 psz_work_todo--;
261 }
262 mutex_spin_exit(&psz_lock);
263}
264