kern_rwlock.c revision 1.28 1 1.28 thorpej /* $NetBSD: kern_rwlock.c,v 1.28 2008/07/29 16:13:39 thorpej Exp $ */
2 1.2 ad
3 1.2 ad /*-
4 1.16 ad * Copyright (c) 2002, 2006, 2007, 2008 The NetBSD Foundation, Inc.
5 1.2 ad * All rights reserved.
6 1.2 ad *
7 1.2 ad * This code is derived from software contributed to The NetBSD Foundation
8 1.2 ad * by Jason R. Thorpe and Andrew Doran.
9 1.2 ad *
10 1.2 ad * Redistribution and use in source and binary forms, with or without
11 1.2 ad * modification, are permitted provided that the following conditions
12 1.2 ad * are met:
13 1.2 ad * 1. Redistributions of source code must retain the above copyright
14 1.2 ad * notice, this list of conditions and the following disclaimer.
15 1.2 ad * 2. Redistributions in binary form must reproduce the above copyright
16 1.2 ad * notice, this list of conditions and the following disclaimer in the
17 1.2 ad * documentation and/or other materials provided with the distribution.
18 1.2 ad *
19 1.2 ad * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
20 1.2 ad * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
21 1.2 ad * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 1.2 ad * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
23 1.2 ad * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
24 1.2 ad * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
25 1.2 ad * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
26 1.2 ad * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 1.2 ad * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
28 1.2 ad * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 1.2 ad * POSSIBILITY OF SUCH DAMAGE.
30 1.2 ad */
31 1.2 ad
32 1.2 ad /*
33 1.2 ad * Kernel reader/writer lock implementation, modeled after those
34 1.2 ad * found in Solaris, a description of which can be found in:
35 1.2 ad *
36 1.2 ad * Solaris Internals: Core Kernel Architecture, Jim Mauro and
37 1.2 ad * Richard McDougall.
38 1.2 ad */
39 1.2 ad
40 1.10 dsl #include <sys/cdefs.h>
41 1.28 thorpej __KERNEL_RCSID(0, "$NetBSD: kern_rwlock.c,v 1.28 2008/07/29 16:13:39 thorpej Exp $");
42 1.2 ad
43 1.2 ad #define __RWLOCK_PRIVATE
44 1.2 ad
45 1.2 ad #include <sys/param.h>
46 1.2 ad #include <sys/proc.h>
47 1.2 ad #include <sys/rwlock.h>
48 1.2 ad #include <sys/sched.h>
49 1.2 ad #include <sys/sleepq.h>
50 1.2 ad #include <sys/systm.h>
51 1.2 ad #include <sys/lockdebug.h>
52 1.11 ad #include <sys/cpu.h>
53 1.14 ad #include <sys/atomic.h>
54 1.15 ad #include <sys/lock.h>
55 1.2 ad
56 1.2 ad #include <dev/lockstat.h>
57 1.2 ad
58 1.2 ad /*
59 1.2 ad * LOCKDEBUG
60 1.2 ad */
61 1.2 ad
62 1.2 ad #if defined(LOCKDEBUG)
63 1.2 ad
64 1.23 ad #define RW_WANTLOCK(rw, op, t) \
65 1.12 yamt LOCKDEBUG_WANTLOCK(RW_DEBUG_P(rw), (rw), \
66 1.23 ad (uintptr_t)__builtin_return_address(0), op == RW_READER, t);
67 1.2 ad #define RW_LOCKED(rw, op) \
68 1.25 ad LOCKDEBUG_LOCKED(RW_DEBUG_P(rw), (rw), NULL, \
69 1.2 ad (uintptr_t)__builtin_return_address(0), op == RW_READER);
70 1.2 ad #define RW_UNLOCKED(rw, op) \
71 1.12 yamt LOCKDEBUG_UNLOCKED(RW_DEBUG_P(rw), (rw), \
72 1.2 ad (uintptr_t)__builtin_return_address(0), op == RW_READER);
73 1.2 ad #define RW_DASSERT(rw, cond) \
74 1.2 ad do { \
75 1.2 ad if (!(cond)) \
76 1.11 ad rw_abort(rw, __func__, "assertion failed: " #cond); \
77 1.2 ad } while (/* CONSTCOND */ 0);
78 1.2 ad
79 1.2 ad #else /* LOCKDEBUG */
80 1.2 ad
81 1.23 ad #define RW_WANTLOCK(rw, op, t) /* nothing */
82 1.2 ad #define RW_LOCKED(rw, op) /* nothing */
83 1.2 ad #define RW_UNLOCKED(rw, op) /* nothing */
84 1.2 ad #define RW_DASSERT(rw, cond) /* nothing */
85 1.2 ad
86 1.2 ad #endif /* LOCKDEBUG */
87 1.2 ad
88 1.2 ad /*
89 1.2 ad * DIAGNOSTIC
90 1.2 ad */
91 1.2 ad
92 1.2 ad #if defined(DIAGNOSTIC)
93 1.2 ad
94 1.2 ad #define RW_ASSERT(rw, cond) \
95 1.2 ad do { \
96 1.2 ad if (!(cond)) \
97 1.11 ad rw_abort(rw, __func__, "assertion failed: " #cond); \
98 1.2 ad } while (/* CONSTCOND */ 0)
99 1.2 ad
100 1.2 ad #else
101 1.2 ad
102 1.2 ad #define RW_ASSERT(rw, cond) /* nothing */
103 1.2 ad
104 1.2 ad #endif /* DIAGNOSTIC */
105 1.2 ad
106 1.12 yamt #define RW_SETDEBUG(rw, on) ((rw)->rw_owner |= (on) ? RW_DEBUG : 0)
107 1.12 yamt #define RW_DEBUG_P(rw) (((rw)->rw_owner & RW_DEBUG) != 0)
108 1.12 yamt #if defined(LOCKDEBUG)
109 1.12 yamt #define RW_INHERITDEBUG(new, old) (new) |= (old) & RW_DEBUG
110 1.12 yamt #else /* defined(LOCKDEBUG) */
111 1.12 yamt #define RW_INHERITDEBUG(new, old) /* nothing */
112 1.12 yamt #endif /* defined(LOCKDEBUG) */
113 1.12 yamt
114 1.20 ad static void rw_abort(krwlock_t *, const char *, const char *);
115 1.20 ad static void rw_dump(volatile void *);
116 1.20 ad static lwp_t *rw_owner(wchan_t);
117 1.20 ad
118 1.20 ad static inline uintptr_t
119 1.20 ad rw_cas(krwlock_t *rw, uintptr_t o, uintptr_t n)
120 1.12 yamt {
121 1.12 yamt
122 1.20 ad RW_INHERITDEBUG(n, o);
123 1.20 ad return (uintptr_t)atomic_cas_ptr((volatile void *)&rw->rw_owner,
124 1.20 ad (void *)o, (void *)n);
125 1.12 yamt }
126 1.2 ad
127 1.20 ad static inline void
128 1.20 ad rw_swap(krwlock_t *rw, uintptr_t o, uintptr_t n)
129 1.2 ad {
130 1.2 ad
131 1.20 ad RW_INHERITDEBUG(n, o);
132 1.20 ad n = (uintptr_t)atomic_swap_ptr((volatile void *)&rw->rw_owner,
133 1.20 ad (void *)n);
134 1.20 ad RW_DASSERT(rw, n == o);
135 1.2 ad }
136 1.2 ad
137 1.2 ad /*
138 1.2 ad * For platforms that do not provide stubs, or for the LOCKDEBUG case.
139 1.2 ad */
140 1.2 ad #ifdef LOCKDEBUG
141 1.2 ad #undef __HAVE_RW_STUBS
142 1.2 ad #endif
143 1.2 ad
144 1.2 ad #ifndef __HAVE_RW_STUBS
145 1.6 itohy __strong_alias(rw_enter,rw_vector_enter);
146 1.6 itohy __strong_alias(rw_exit,rw_vector_exit);
147 1.16 ad __strong_alias(rw_tryenter,rw_vector_tryenter);
148 1.2 ad #endif
149 1.2 ad
150 1.2 ad lockops_t rwlock_lockops = {
151 1.2 ad "Reader / writer lock",
152 1.25 ad LOCKOPS_SLEEP,
153 1.2 ad rw_dump
154 1.2 ad };
155 1.2 ad
156 1.4 yamt syncobj_t rw_syncobj = {
157 1.4 yamt SOBJ_SLEEPQ_SORTED,
158 1.4 yamt turnstile_unsleep,
159 1.4 yamt turnstile_changepri,
160 1.4 yamt sleepq_lendpri,
161 1.4 yamt rw_owner,
162 1.4 yamt };
163 1.4 yamt
164 1.2 ad /*
165 1.2 ad * rw_dump:
166 1.2 ad *
167 1.2 ad * Dump the contents of a rwlock structure.
168 1.2 ad */
169 1.11 ad static void
170 1.2 ad rw_dump(volatile void *cookie)
171 1.2 ad {
172 1.2 ad volatile krwlock_t *rw = cookie;
173 1.2 ad
174 1.2 ad printf_nolog("owner/count : %#018lx flags : %#018x\n",
175 1.2 ad (long)RW_OWNER(rw), (int)RW_FLAGS(rw));
176 1.2 ad }
177 1.2 ad
178 1.2 ad /*
179 1.11 ad * rw_abort:
180 1.11 ad *
181 1.11 ad * Dump information about an error and panic the system. This
182 1.11 ad * generates a lot of machine code in the DIAGNOSTIC case, so
183 1.11 ad * we ask the compiler to not inline it.
184 1.11 ad */
185 1.26 ad static void __noinline
186 1.11 ad rw_abort(krwlock_t *rw, const char *func, const char *msg)
187 1.11 ad {
188 1.11 ad
189 1.11 ad if (panicstr != NULL)
190 1.11 ad return;
191 1.11 ad
192 1.12 yamt LOCKDEBUG_ABORT(rw, &rwlock_lockops, func, msg);
193 1.11 ad }
194 1.11 ad
195 1.11 ad /*
196 1.2 ad * rw_init:
197 1.2 ad *
198 1.2 ad * Initialize a rwlock for use.
199 1.2 ad */
200 1.2 ad void
201 1.2 ad rw_init(krwlock_t *rw)
202 1.2 ad {
203 1.12 yamt bool dodebug;
204 1.2 ad
205 1.2 ad memset(rw, 0, sizeof(*rw));
206 1.2 ad
207 1.12 yamt dodebug = LOCKDEBUG_ALLOC(rw, &rwlock_lockops,
208 1.11 ad (uintptr_t)__builtin_return_address(0));
209 1.12 yamt RW_SETDEBUG(rw, dodebug);
210 1.2 ad }
211 1.2 ad
212 1.2 ad /*
213 1.2 ad * rw_destroy:
214 1.2 ad *
215 1.2 ad * Tear down a rwlock.
216 1.2 ad */
217 1.2 ad void
218 1.2 ad rw_destroy(krwlock_t *rw)
219 1.2 ad {
220 1.2 ad
221 1.12 yamt RW_ASSERT(rw, (rw->rw_owner & ~RW_DEBUG) == 0);
222 1.12 yamt LOCKDEBUG_FREE(RW_DEBUG_P(rw), rw);
223 1.2 ad }
224 1.2 ad
225 1.2 ad /*
226 1.20 ad * rw_onproc:
227 1.20 ad *
228 1.20 ad * Return true if an rwlock owner is running on a CPU in the system.
229 1.20 ad * If the target is waiting on the kernel big lock, then we must
230 1.20 ad * release it. This is necessary to avoid deadlock.
231 1.20 ad *
232 1.20 ad * Note that we can't use the rwlock owner field as an LWP pointer. We
233 1.20 ad * don't have full control over the timing of our execution, and so the
234 1.20 ad * pointer could be completely invalid by the time we dereference it.
235 1.20 ad */
236 1.20 ad static int
237 1.20 ad rw_onproc(uintptr_t owner, struct cpu_info **cip)
238 1.20 ad {
239 1.20 ad #ifdef MULTIPROCESSOR
240 1.20 ad CPU_INFO_ITERATOR cii;
241 1.20 ad struct cpu_info *ci;
242 1.20 ad lwp_t *l;
243 1.20 ad
244 1.20 ad if ((owner & (RW_WRITE_LOCKED|RW_HAS_WAITERS)) != RW_WRITE_LOCKED)
245 1.20 ad return 0;
246 1.20 ad l = (lwp_t *)(owner & RW_THREAD);
247 1.20 ad
248 1.20 ad /* See if the target is running on a CPU somewhere. */
249 1.20 ad if ((ci = *cip) != NULL && ci->ci_curlwp == l)
250 1.20 ad goto run;
251 1.20 ad for (CPU_INFO_FOREACH(cii, ci))
252 1.20 ad if (ci->ci_curlwp == l)
253 1.20 ad goto run;
254 1.20 ad
255 1.20 ad /* No: it may be safe to block now. */
256 1.20 ad *cip = NULL;
257 1.20 ad return 0;
258 1.20 ad
259 1.20 ad run:
260 1.20 ad /* Target is running; do we need to block? */
261 1.20 ad *cip = ci;
262 1.20 ad return ci->ci_biglock_wanted != l;
263 1.20 ad #else
264 1.20 ad return 0;
265 1.20 ad #endif /* MULTIPROCESSOR */
266 1.20 ad }
267 1.20 ad
268 1.20 ad /*
269 1.2 ad * rw_vector_enter:
270 1.2 ad *
271 1.2 ad * Acquire a rwlock.
272 1.2 ad */
273 1.2 ad void
274 1.2 ad rw_vector_enter(krwlock_t *rw, const krw_t op)
275 1.2 ad {
276 1.20 ad uintptr_t owner, incr, need_wait, set_wait, curthread, next;
277 1.19 ad struct cpu_info *ci;
278 1.2 ad turnstile_t *ts;
279 1.2 ad int queue;
280 1.7 ad lwp_t *l;
281 1.2 ad LOCKSTAT_TIMER(slptime);
282 1.20 ad LOCKSTAT_TIMER(slpcnt);
283 1.19 ad LOCKSTAT_TIMER(spintime);
284 1.19 ad LOCKSTAT_COUNTER(spincnt);
285 1.2 ad LOCKSTAT_FLAG(lsflag);
286 1.2 ad
287 1.2 ad l = curlwp;
288 1.2 ad curthread = (uintptr_t)l;
289 1.2 ad
290 1.13 ad RW_ASSERT(rw, !cpu_intr_p());
291 1.2 ad RW_ASSERT(rw, curthread != 0);
292 1.23 ad RW_WANTLOCK(rw, op, false);
293 1.2 ad
294 1.2 ad if (panicstr == NULL) {
295 1.2 ad LOCKDEBUG_BARRIER(&kernel_lock, 1);
296 1.2 ad }
297 1.2 ad
298 1.2 ad /*
299 1.2 ad * We play a slight trick here. If we're a reader, we want
300 1.2 ad * increment the read count. If we're a writer, we want to
301 1.2 ad * set the owner field and whe WRITE_LOCKED bit.
302 1.2 ad *
303 1.2 ad * In the latter case, we expect those bits to be zero,
304 1.2 ad * therefore we can use an add operation to set them, which
305 1.2 ad * means an add operation for both cases.
306 1.2 ad */
307 1.2 ad if (__predict_true(op == RW_READER)) {
308 1.2 ad incr = RW_READ_INCR;
309 1.2 ad set_wait = RW_HAS_WAITERS;
310 1.2 ad need_wait = RW_WRITE_LOCKED | RW_WRITE_WANTED;
311 1.2 ad queue = TS_READER_Q;
312 1.2 ad } else {
313 1.2 ad RW_DASSERT(rw, op == RW_WRITER);
314 1.2 ad incr = curthread | RW_WRITE_LOCKED;
315 1.2 ad set_wait = RW_HAS_WAITERS | RW_WRITE_WANTED;
316 1.2 ad need_wait = RW_WRITE_LOCKED | RW_THREAD;
317 1.2 ad queue = TS_WRITER_Q;
318 1.2 ad }
319 1.2 ad
320 1.2 ad LOCKSTAT_ENTER(lsflag);
321 1.2 ad
322 1.20 ad for (ci = NULL, owner = rw->rw_owner;;) {
323 1.2 ad /*
324 1.2 ad * Read the lock owner field. If the need-to-wait
325 1.2 ad * indicator is clear, then try to acquire the lock.
326 1.2 ad */
327 1.2 ad if ((owner & need_wait) == 0) {
328 1.20 ad next = rw_cas(rw, owner, (owner + incr) &
329 1.20 ad ~RW_WRITE_WANTED);
330 1.20 ad if (__predict_true(next == owner)) {
331 1.2 ad /* Got it! */
332 1.20 ad #ifndef __HAVE_ATOMIC_AS_MEMBAR
333 1.20 ad membar_enter();
334 1.20 ad #endif
335 1.2 ad break;
336 1.2 ad }
337 1.2 ad
338 1.2 ad /*
339 1.2 ad * Didn't get it -- spin around again (we'll
340 1.2 ad * probably sleep on the next iteration).
341 1.2 ad */
342 1.20 ad owner = next;
343 1.2 ad continue;
344 1.2 ad }
345 1.2 ad
346 1.20 ad if (__predict_false(panicstr != NULL))
347 1.2 ad return;
348 1.20 ad if (__predict_false(RW_OWNER(rw) == curthread))
349 1.11 ad rw_abort(rw, __func__, "locking against myself");
350 1.2 ad
351 1.19 ad /*
352 1.19 ad * If the lock owner is running on another CPU, and
353 1.19 ad * there are no existing waiters, then spin.
354 1.19 ad */
355 1.20 ad if (rw_onproc(owner, &ci)) {
356 1.19 ad LOCKSTAT_START_TIMER(lsflag, spintime);
357 1.19 ad u_int count = SPINLOCK_BACKOFF_MIN;
358 1.20 ad do {
359 1.20 ad SPINLOCK_BACKOFF(count);
360 1.19 ad owner = rw->rw_owner;
361 1.20 ad } while (rw_onproc(owner, &ci));
362 1.19 ad LOCKSTAT_STOP_TIMER(lsflag, spintime);
363 1.19 ad LOCKSTAT_COUNT(spincnt, 1);
364 1.19 ad if ((owner & need_wait) == 0)
365 1.19 ad continue;
366 1.19 ad }
367 1.19 ad
368 1.2 ad /*
369 1.2 ad * Grab the turnstile chain lock. Once we have that, we
370 1.2 ad * can adjust the waiter bits and sleep queue.
371 1.2 ad */
372 1.2 ad ts = turnstile_lookup(rw);
373 1.2 ad
374 1.2 ad /*
375 1.2 ad * Mark the rwlock as having waiters. If the set fails,
376 1.2 ad * then we may not need to sleep and should spin again.
377 1.20 ad * Reload rw_owner because turnstile_lookup() may have
378 1.20 ad * spun on the turnstile chain lock.
379 1.2 ad */
380 1.20 ad owner = rw->rw_owner;
381 1.20 ad if ((owner & need_wait) == 0 || rw_onproc(owner, &ci)) {
382 1.20 ad turnstile_exit(rw);
383 1.20 ad continue;
384 1.20 ad }
385 1.20 ad next = rw_cas(rw, owner, owner | set_wait);
386 1.20 ad if (__predict_false(next != owner)) {
387 1.2 ad turnstile_exit(rw);
388 1.20 ad owner = next;
389 1.2 ad continue;
390 1.2 ad }
391 1.2 ad
392 1.2 ad LOCKSTAT_START_TIMER(lsflag, slptime);
393 1.4 yamt turnstile_block(ts, queue, rw, &rw_syncobj);
394 1.2 ad LOCKSTAT_STOP_TIMER(lsflag, slptime);
395 1.20 ad LOCKSTAT_COUNT(slpcnt, 1);
396 1.2 ad
397 1.20 ad /*
398 1.20 ad * No need for a memory barrier because of context switch.
399 1.20 ad * If not handed the lock, then spin again.
400 1.20 ad */
401 1.20 ad if (op == RW_READER || (rw->rw_owner & RW_THREAD) == curthread)
402 1.20 ad break;
403 1.2 ad }
404 1.2 ad
405 1.20 ad LOCKSTAT_EVENT(lsflag, rw, LB_RWLOCK |
406 1.20 ad (op == RW_WRITER ? LB_SLEEP1 : LB_SLEEP2), slpcnt, slptime);
407 1.19 ad LOCKSTAT_EVENT(lsflag, rw, LB_RWLOCK | LB_SPIN, spincnt, spintime);
408 1.2 ad LOCKSTAT_EXIT(lsflag);
409 1.2 ad
410 1.2 ad RW_DASSERT(rw, (op != RW_READER && RW_OWNER(rw) == curthread) ||
411 1.2 ad (op == RW_READER && RW_COUNT(rw) != 0));
412 1.2 ad RW_LOCKED(rw, op);
413 1.2 ad }
414 1.2 ad
415 1.2 ad /*
416 1.2 ad * rw_vector_exit:
417 1.2 ad *
418 1.2 ad * Release a rwlock.
419 1.2 ad */
420 1.2 ad void
421 1.2 ad rw_vector_exit(krwlock_t *rw)
422 1.2 ad {
423 1.20 ad uintptr_t curthread, owner, decr, new, next;
424 1.2 ad turnstile_t *ts;
425 1.2 ad int rcnt, wcnt;
426 1.7 ad lwp_t *l;
427 1.2 ad
428 1.2 ad curthread = (uintptr_t)curlwp;
429 1.2 ad RW_ASSERT(rw, curthread != 0);
430 1.2 ad
431 1.20 ad if (__predict_false(panicstr != NULL))
432 1.2 ad return;
433 1.2 ad
434 1.2 ad /*
435 1.2 ad * Again, we use a trick. Since we used an add operation to
436 1.2 ad * set the required lock bits, we can use a subtract to clear
437 1.2 ad * them, which makes the read-release and write-release path
438 1.2 ad * the same.
439 1.2 ad */
440 1.2 ad owner = rw->rw_owner;
441 1.2 ad if (__predict_false((owner & RW_WRITE_LOCKED) != 0)) {
442 1.2 ad RW_UNLOCKED(rw, RW_WRITER);
443 1.2 ad RW_ASSERT(rw, RW_OWNER(rw) == curthread);
444 1.2 ad decr = curthread | RW_WRITE_LOCKED;
445 1.2 ad } else {
446 1.2 ad RW_UNLOCKED(rw, RW_READER);
447 1.2 ad RW_ASSERT(rw, RW_COUNT(rw) != 0);
448 1.2 ad decr = RW_READ_INCR;
449 1.2 ad }
450 1.2 ad
451 1.2 ad /*
452 1.2 ad * Compute what we expect the new value of the lock to be. Only
453 1.2 ad * proceed to do direct handoff if there are waiters, and if the
454 1.2 ad * lock would become unowned.
455 1.2 ad */
456 1.20 ad #ifndef __HAVE_ATOMIC_AS_MEMBAR
457 1.20 ad membar_exit();
458 1.20 ad #endif
459 1.20 ad for (;;) {
460 1.2 ad new = (owner - decr);
461 1.2 ad if ((new & (RW_THREAD | RW_HAS_WAITERS)) == RW_HAS_WAITERS)
462 1.2 ad break;
463 1.20 ad next = rw_cas(rw, owner, new);
464 1.20 ad if (__predict_true(next == owner))
465 1.2 ad return;
466 1.20 ad owner = next;
467 1.2 ad }
468 1.2 ad
469 1.20 ad /*
470 1.20 ad * Grab the turnstile chain lock. This gets the interlock
471 1.20 ad * on the sleep queue. Once we have that, we can adjust the
472 1.20 ad * waiter bits.
473 1.20 ad */
474 1.20 ad ts = turnstile_lookup(rw);
475 1.20 ad owner = rw->rw_owner;
476 1.20 ad RW_DASSERT(rw, ts != NULL);
477 1.20 ad RW_DASSERT(rw, (owner & RW_HAS_WAITERS) != 0);
478 1.2 ad
479 1.20 ad wcnt = TS_WAITERS(ts, TS_WRITER_Q);
480 1.20 ad rcnt = TS_WAITERS(ts, TS_READER_Q);
481 1.2 ad
482 1.20 ad /*
483 1.20 ad * Give the lock away.
484 1.20 ad *
485 1.20 ad * If we are releasing a write lock, then prefer to wake all
486 1.20 ad * outstanding readers. Otherwise, wake one writer if there
487 1.20 ad * are outstanding readers, or all writers if there are no
488 1.20 ad * pending readers. If waking one specific writer, the writer
489 1.20 ad * is handed the lock here. If waking multiple writers, we
490 1.20 ad * set WRITE_WANTED to block out new readers, and let them
491 1.20 ad * do the work of acquring the lock in rw_vector_enter().
492 1.20 ad */
493 1.20 ad if (rcnt == 0 || (decr == RW_READ_INCR && wcnt != 0)) {
494 1.20 ad RW_DASSERT(rw, wcnt != 0);
495 1.20 ad RW_DASSERT(rw, (owner & RW_WRITE_WANTED) != 0);
496 1.2 ad
497 1.20 ad if (rcnt != 0) {
498 1.20 ad /* Give the lock to the longest waiting writer. */
499 1.2 ad l = TS_FIRST(ts, TS_WRITER_Q);
500 1.20 ad new = (uintptr_t)l | RW_WRITE_LOCKED | RW_HAS_WAITERS;
501 1.28 thorpej if (wcnt > 1)
502 1.20 ad new |= RW_WRITE_WANTED;
503 1.20 ad rw_swap(rw, owner, new);
504 1.7 ad turnstile_wakeup(ts, TS_WRITER_Q, 1, l);
505 1.2 ad } else {
506 1.20 ad /* Wake all writers and let them fight it out. */
507 1.20 ad rw_swap(rw, owner, RW_WRITE_WANTED);
508 1.20 ad turnstile_wakeup(ts, TS_WRITER_Q, wcnt, NULL);
509 1.20 ad }
510 1.20 ad } else {
511 1.20 ad RW_DASSERT(rw, rcnt != 0);
512 1.2 ad
513 1.20 ad /*
514 1.20 ad * Give the lock to all blocked readers. If there
515 1.20 ad * is a writer waiting, new readers that arrive
516 1.20 ad * after the release will be blocked out.
517 1.20 ad */
518 1.20 ad new = rcnt << RW_READ_COUNT_SHIFT;
519 1.20 ad if (wcnt != 0)
520 1.20 ad new |= RW_HAS_WAITERS | RW_WRITE_WANTED;
521 1.12 yamt
522 1.20 ad /* Wake up all sleeping readers. */
523 1.20 ad rw_swap(rw, owner, new);
524 1.20 ad turnstile_wakeup(ts, TS_READER_Q, rcnt, NULL);
525 1.2 ad }
526 1.2 ad }
527 1.2 ad
528 1.2 ad /*
529 1.16 ad * rw_vector_tryenter:
530 1.2 ad *
531 1.2 ad * Try to acquire a rwlock.
532 1.2 ad */
533 1.2 ad int
534 1.16 ad rw_vector_tryenter(krwlock_t *rw, const krw_t op)
535 1.2 ad {
536 1.20 ad uintptr_t curthread, owner, incr, need_wait, next;
537 1.2 ad
538 1.2 ad curthread = (uintptr_t)curlwp;
539 1.2 ad
540 1.2 ad RW_ASSERT(rw, curthread != 0);
541 1.2 ad
542 1.2 ad if (op == RW_READER) {
543 1.2 ad incr = RW_READ_INCR;
544 1.2 ad need_wait = RW_WRITE_LOCKED | RW_WRITE_WANTED;
545 1.2 ad } else {
546 1.2 ad RW_DASSERT(rw, op == RW_WRITER);
547 1.2 ad incr = curthread | RW_WRITE_LOCKED;
548 1.2 ad need_wait = RW_WRITE_LOCKED | RW_THREAD;
549 1.2 ad }
550 1.2 ad
551 1.20 ad for (owner = rw->rw_owner;; owner = next) {
552 1.2 ad owner = rw->rw_owner;
553 1.20 ad if (__predict_false((owner & need_wait) != 0))
554 1.20 ad return 0;
555 1.20 ad next = rw_cas(rw, owner, owner + incr);
556 1.20 ad if (__predict_true(next == owner)) {
557 1.20 ad /* Got it! */
558 1.20 ad break;
559 1.2 ad }
560 1.2 ad }
561 1.2 ad
562 1.20 ad #ifndef __HAVE_ATOMIC_AS_MEMBAR
563 1.20 ad membar_enter();
564 1.20 ad #endif
565 1.23 ad RW_WANTLOCK(rw, op, true);
566 1.2 ad RW_LOCKED(rw, op);
567 1.2 ad RW_DASSERT(rw, (op != RW_READER && RW_OWNER(rw) == curthread) ||
568 1.2 ad (op == RW_READER && RW_COUNT(rw) != 0));
569 1.7 ad
570 1.2 ad return 1;
571 1.2 ad }
572 1.2 ad
573 1.2 ad /*
574 1.2 ad * rw_downgrade:
575 1.2 ad *
576 1.2 ad * Downgrade a write lock to a read lock.
577 1.2 ad */
578 1.2 ad void
579 1.2 ad rw_downgrade(krwlock_t *rw)
580 1.2 ad {
581 1.20 ad uintptr_t owner, curthread, new, next;
582 1.2 ad turnstile_t *ts;
583 1.2 ad int rcnt, wcnt;
584 1.2 ad
585 1.2 ad curthread = (uintptr_t)curlwp;
586 1.2 ad RW_ASSERT(rw, curthread != 0);
587 1.2 ad RW_DASSERT(rw, (rw->rw_owner & RW_WRITE_LOCKED) != 0);
588 1.2 ad RW_ASSERT(rw, RW_OWNER(rw) == curthread);
589 1.2 ad RW_UNLOCKED(rw, RW_WRITER);
590 1.2 ad
591 1.20 ad #ifndef __HAVE_ATOMIC_AS_MEMBAR
592 1.20 ad membar_producer();
593 1.20 ad #endif
594 1.20 ad
595 1.2 ad owner = rw->rw_owner;
596 1.2 ad if ((owner & RW_HAS_WAITERS) == 0) {
597 1.2 ad /*
598 1.2 ad * There are no waiters, so we can do this the easy way.
599 1.2 ad * Try swapping us down to one read hold. If it fails, the
600 1.2 ad * lock condition has changed and we most likely now have
601 1.2 ad * waiters.
602 1.2 ad */
603 1.20 ad next = rw_cas(rw, owner, RW_READ_INCR);
604 1.20 ad if (__predict_true(next == owner)) {
605 1.2 ad RW_LOCKED(rw, RW_READER);
606 1.2 ad RW_DASSERT(rw, (rw->rw_owner & RW_WRITE_LOCKED) == 0);
607 1.2 ad RW_DASSERT(rw, RW_COUNT(rw) != 0);
608 1.2 ad return;
609 1.2 ad }
610 1.20 ad owner = next;
611 1.2 ad }
612 1.2 ad
613 1.2 ad /*
614 1.2 ad * Grab the turnstile chain lock. This gets the interlock
615 1.2 ad * on the sleep queue. Once we have that, we can adjust the
616 1.2 ad * waiter bits.
617 1.2 ad */
618 1.20 ad for (;; owner = next) {
619 1.2 ad ts = turnstile_lookup(rw);
620 1.2 ad RW_DASSERT(rw, ts != NULL);
621 1.2 ad
622 1.2 ad rcnt = TS_WAITERS(ts, TS_READER_Q);
623 1.2 ad wcnt = TS_WAITERS(ts, TS_WRITER_Q);
624 1.2 ad
625 1.2 ad /*
626 1.2 ad * If there are no readers, just preserve the waiters
627 1.2 ad * bits, swap us down to one read hold and return.
628 1.2 ad */
629 1.2 ad if (rcnt == 0) {
630 1.2 ad RW_DASSERT(rw, wcnt != 0);
631 1.2 ad RW_DASSERT(rw, (rw->rw_owner & RW_WRITE_WANTED) != 0);
632 1.2 ad RW_DASSERT(rw, (rw->rw_owner & RW_HAS_WAITERS) != 0);
633 1.2 ad
634 1.2 ad new = RW_READ_INCR | RW_HAS_WAITERS | RW_WRITE_WANTED;
635 1.20 ad next = rw_cas(rw, owner, new);
636 1.27 rmind turnstile_exit(rw);
637 1.20 ad if (__predict_true(next == owner))
638 1.20 ad break;
639 1.20 ad } else {
640 1.20 ad /*
641 1.20 ad * Give the lock to all blocked readers. We may
642 1.20 ad * retain one read hold if downgrading. If there
643 1.20 ad * is a writer waiting, new readers will be blocked
644 1.20 ad * out.
645 1.20 ad */
646 1.20 ad new = (rcnt << RW_READ_COUNT_SHIFT) + RW_READ_INCR;
647 1.20 ad if (wcnt != 0)
648 1.20 ad new |= RW_HAS_WAITERS | RW_WRITE_WANTED;
649 1.20 ad
650 1.20 ad next = rw_cas(rw, owner, new);
651 1.20 ad if (__predict_true(next == owner)) {
652 1.20 ad /* Wake up all sleeping readers. */
653 1.20 ad turnstile_wakeup(ts, TS_READER_Q, rcnt, NULL);
654 1.20 ad break;
655 1.2 ad }
656 1.27 rmind turnstile_exit(rw);
657 1.2 ad }
658 1.2 ad }
659 1.2 ad
660 1.2 ad RW_LOCKED(rw, RW_READER);
661 1.2 ad RW_DASSERT(rw, (rw->rw_owner & RW_WRITE_LOCKED) == 0);
662 1.2 ad RW_DASSERT(rw, RW_COUNT(rw) != 0);
663 1.2 ad }
664 1.2 ad
665 1.2 ad /*
666 1.2 ad * rw_tryupgrade:
667 1.2 ad *
668 1.2 ad * Try to upgrade a read lock to a write lock. We must be the
669 1.2 ad * only reader.
670 1.2 ad */
671 1.2 ad int
672 1.2 ad rw_tryupgrade(krwlock_t *rw)
673 1.2 ad {
674 1.20 ad uintptr_t owner, curthread, new, next;
675 1.2 ad
676 1.2 ad curthread = (uintptr_t)curlwp;
677 1.2 ad RW_ASSERT(rw, curthread != 0);
678 1.23 ad RW_WANTLOCK(rw, RW_WRITER, true);
679 1.2 ad
680 1.20 ad for (owner = rw->rw_owner;; owner = next) {
681 1.2 ad RW_ASSERT(rw, (owner & RW_WRITE_LOCKED) == 0);
682 1.20 ad if (__predict_false((owner & RW_THREAD) != RW_READ_INCR)) {
683 1.2 ad RW_ASSERT(rw, (owner & RW_THREAD) != 0);
684 1.2 ad return 0;
685 1.2 ad }
686 1.2 ad new = curthread | RW_WRITE_LOCKED | (owner & ~RW_THREAD);
687 1.20 ad next = rw_cas(rw, owner, new);
688 1.20 ad if (__predict_true(next == owner))
689 1.2 ad break;
690 1.2 ad }
691 1.2 ad
692 1.2 ad RW_UNLOCKED(rw, RW_READER);
693 1.2 ad RW_LOCKED(rw, RW_WRITER);
694 1.2 ad RW_DASSERT(rw, rw->rw_owner & RW_WRITE_LOCKED);
695 1.2 ad RW_DASSERT(rw, RW_OWNER(rw) == curthread);
696 1.2 ad
697 1.20 ad #ifndef __HAVE_ATOMIC_AS_MEMBAR
698 1.20 ad membar_producer();
699 1.20 ad #endif
700 1.20 ad
701 1.2 ad return 1;
702 1.2 ad }
703 1.2 ad
704 1.2 ad /*
705 1.2 ad * rw_read_held:
706 1.2 ad *
707 1.2 ad * Returns true if the rwlock is held for reading. Must only be
708 1.2 ad * used for diagnostic assertions, and never be used to make
709 1.2 ad * decisions about how to use a rwlock.
710 1.2 ad */
711 1.2 ad int
712 1.2 ad rw_read_held(krwlock_t *rw)
713 1.2 ad {
714 1.2 ad uintptr_t owner;
715 1.2 ad
716 1.2 ad if (panicstr != NULL)
717 1.2 ad return 1;
718 1.21 ad if (rw == NULL)
719 1.21 ad return 0;
720 1.2 ad owner = rw->rw_owner;
721 1.2 ad return (owner & RW_WRITE_LOCKED) == 0 && (owner & RW_THREAD) != 0;
722 1.2 ad }
723 1.2 ad
724 1.2 ad /*
725 1.2 ad * rw_write_held:
726 1.2 ad *
727 1.2 ad * Returns true if the rwlock is held for writing. Must only be
728 1.2 ad * used for diagnostic assertions, and never be used to make
729 1.2 ad * decisions about how to use a rwlock.
730 1.2 ad */
731 1.2 ad int
732 1.2 ad rw_write_held(krwlock_t *rw)
733 1.2 ad {
734 1.2 ad
735 1.2 ad if (panicstr != NULL)
736 1.2 ad return 1;
737 1.21 ad if (rw == NULL)
738 1.21 ad return 0;
739 1.17 ad return (rw->rw_owner & (RW_WRITE_LOCKED | RW_THREAD)) ==
740 1.18 ad (RW_WRITE_LOCKED | (uintptr_t)curlwp);
741 1.2 ad }
742 1.2 ad
743 1.2 ad /*
744 1.2 ad * rw_lock_held:
745 1.2 ad *
746 1.2 ad * Returns true if the rwlock is held for reading or writing. Must
747 1.2 ad * only be used for diagnostic assertions, and never be used to make
748 1.2 ad * decisions about how to use a rwlock.
749 1.2 ad */
750 1.2 ad int
751 1.2 ad rw_lock_held(krwlock_t *rw)
752 1.2 ad {
753 1.2 ad
754 1.2 ad if (panicstr != NULL)
755 1.2 ad return 1;
756 1.21 ad if (rw == NULL)
757 1.21 ad return 0;
758 1.2 ad return (rw->rw_owner & RW_THREAD) != 0;
759 1.2 ad }
760 1.4 yamt
761 1.5 ad /*
762 1.5 ad * rw_owner:
763 1.5 ad *
764 1.5 ad * Return the current owner of an RW lock, but only if it is write
765 1.5 ad * held. Used for priority inheritance.
766 1.5 ad */
767 1.7 ad static lwp_t *
768 1.4 yamt rw_owner(wchan_t obj)
769 1.4 yamt {
770 1.4 yamt krwlock_t *rw = (void *)(uintptr_t)obj; /* discard qualifiers */
771 1.4 yamt uintptr_t owner = rw->rw_owner;
772 1.4 yamt
773 1.4 yamt if ((owner & RW_WRITE_LOCKED) == 0)
774 1.4 yamt return NULL;
775 1.4 yamt
776 1.4 yamt return (void *)(owner & RW_THREAD);
777 1.4 yamt }
778