1 /*-
2 * Copyright (c) 2006 John Baldwin <jhb@FreeBSD.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the author nor the names of any co-contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 /*
31 * Machine independent bits of reader/writer lock implementation.
32 */
33
34 #include <sys/cdefs.h>
35 __FBSDID("$FreeBSD$");
36
37 #include "opt_ddb.h"
38 #include "opt_no_adaptive_rwlocks.h"
39
40 #include <sys/param.h>
41 #include <sys/ktr.h>
42 #include <sys/lock.h>
43 #include <sys/mutex.h>
44 #include <sys/proc.h>
45 #include <sys/rwlock.h>
46 #include <sys/systm.h>
47 #include <sys/turnstile.h>
48
49 #include <machine/cpu.h>
50
51 CTASSERT((RW_RECURSE & LO_CLASSFLAGS) == RW_RECURSE);
52
53 #if defined(SMP) && !defined(NO_ADAPTIVE_RWLOCKS)
54 #define ADAPTIVE_RWLOCKS
55 #endif
56
57 #ifdef DDB
58 #include <ddb/ddb.h>
59
60 static void db_show_rwlock(struct lock_object *lock);
61 #endif
62 static void lock_rw(struct lock_object *lock, int how);
63 static int unlock_rw(struct lock_object *lock);
64
65 struct lock_class lock_class_rw = {
66 .lc_name = "rw",
67 .lc_flags = LC_SLEEPLOCK | LC_RECURSABLE | LC_UPGRADABLE,
68 #ifdef DDB
69 .lc_ddb_show = db_show_rwlock,
70 #endif
71 .lc_lock = lock_rw,
72 .lc_unlock = unlock_rw,
73 };
74
75 /*
76 * Return a pointer to the owning thread if the lock is write-locked or
77 * NULL if the lock is unlocked or read-locked.
78 */
79 #define rw_wowner(rw) \
80 ((rw)->rw_lock & RW_LOCK_READ ? NULL : \
81 (struct thread *)RW_OWNER((rw)->rw_lock))
82
83 /*
84 * Returns if a write owner is recursed. Write ownership is not assured
85 * here and should be previously checked.
86 */
87 #define rw_recursed(rw) ((rw)->rw_recurse != 0)
88
89 /*
90 * Return true if curthread helds the lock.
91 */
92 #define rw_wlocked(rw) (rw_wowner((rw)) == curthread)
93
94 /*
95 * Return a pointer to the owning thread for this lock who should receive
96 * any priority lent by threads that block on this lock. Currently this
97 * is identical to rw_wowner().
98 */
99 #define rw_owner(rw) rw_wowner(rw)
100
101 #ifndef INVARIANTS
102 #define _rw_assert(rw, what, file, line)
103 #endif
104
105 void
106 lock_rw(struct lock_object *lock, int how)
107 {
108 struct rwlock *rw;
109
110 rw = (struct rwlock *)lock;
111 if (how)
112 rw_wlock(rw);
113 else
114 rw_rlock(rw);
115 }
116
117 int
118 unlock_rw(struct lock_object *lock)
119 {
120 struct rwlock *rw;
121
122 rw = (struct rwlock *)lock;
123 rw_assert(rw, RA_LOCKED | LA_NOTRECURSED);
124 if (rw->rw_lock & RW_LOCK_READ) {
125 rw_runlock(rw);
126 return (0);
127 } else {
128 rw_wunlock(rw);
129 return (1);
130 }
131 }
132
133 void
134 rw_init_flags(struct rwlock *rw, const char *name, int opts)
135 {
136 int flags;
137
138 MPASS((opts & ~(RW_DUPOK | RW_NOPROFILE | RW_NOWITNESS | RW_QUIET |
139 RW_RECURSE)) == 0);
140
141 flags = LO_UPGRADABLE | LO_RECURSABLE;
142 if (opts & RW_DUPOK)
143 flags |= LO_DUPOK;
144 if (opts & RW_NOPROFILE)
145 flags |= LO_NOPROFILE;
146 if (!(opts & RW_NOWITNESS))
147 flags |= LO_WITNESS;
148 if (opts & RW_QUIET)
149 flags |= LO_QUIET;
150 flags |= opts & RW_RECURSE;
151
152 rw->rw_lock = RW_UNLOCKED;
153 rw->rw_recurse = 0;
154 lock_init(&rw->lock_object, &lock_class_rw, name, NULL, flags);
155 }
156
157 void
158 rw_destroy(struct rwlock *rw)
159 {
160
161 KASSERT(rw->rw_lock == RW_UNLOCKED, ("rw lock not unlocked"));
162 KASSERT(rw->rw_recurse == 0, ("rw lock still recursed"));
163 rw->rw_lock = RW_DESTROYED;
164 lock_destroy(&rw->lock_object);
165 }
166
167 void
168 rw_sysinit(void *arg)
169 {
170 struct rw_args *args = arg;
171
172 rw_init(args->ra_rw, args->ra_desc);
173 }
174
175 int
176 rw_wowned(struct rwlock *rw)
177 {
178
179 return (rw_wowner(rw) == curthread);
180 }
181
182 void
183 _rw_wlock(struct rwlock *rw, const char *file, int line)
184 {
185
186 MPASS(curthread != NULL);
187 KASSERT(rw->rw_lock != RW_DESTROYED,
188 ("rw_wlock() of destroyed rwlock @ %s:%d", file, line));
189 WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER | LOP_EXCLUSIVE, file,
190 line);
191 __rw_wlock(rw, curthread, file, line);
192 LOCK_LOG_LOCK("WLOCK", &rw->lock_object, 0, rw->rw_recurse, file, line);
193 WITNESS_LOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line);
194 curthread->td_locks++;
195 }
196
197 void
198 _rw_wunlock(struct rwlock *rw, const char *file, int line)
199 {
200
201 MPASS(curthread != NULL);
202 KASSERT(rw->rw_lock != RW_DESTROYED,
203 ("rw_wunlock() of destroyed rwlock @ %s:%d", file, line));
204 _rw_assert(rw, RA_WLOCKED, file, line);
205 curthread->td_locks--;
206 WITNESS_UNLOCK(&rw->lock_object, LOP_EXCLUSIVE, file, line);
207 LOCK_LOG_LOCK("WUNLOCK", &rw->lock_object, 0, rw->rw_recurse, file,
208 line);
209 if (!rw_recursed(rw))
210 lock_profile_release_lock(&rw->lock_object);
211 __rw_wunlock(rw, curthread, file, line);
212 }
213
214 void
215 _rw_rlock(struct rwlock *rw, const char *file, int line)
216 {
217 struct turnstile *ts;
218 #ifdef ADAPTIVE_RWLOCKS
219 volatile struct thread *owner;
220 #endif
221 #ifdef LOCK_PROFILING_SHARED
222 uint64_t waittime = 0;
223 int contested = 0;
224 #endif
225 uintptr_t x;
226
227 KASSERT(rw->rw_lock != RW_DESTROYED,
228 ("rw_rlock() of destroyed rwlock @ %s:%d", file, line));
229 KASSERT(rw_wowner(rw) != curthread,
230 ("%s (%s): wlock already held @ %s:%d", __func__,
231 rw->lock_object.lo_name, file, line));
232 WITNESS_CHECKORDER(&rw->lock_object, LOP_NEWORDER, file, line);
233
234 /*
235 * Note that we don't make any attempt to try to block read
236 * locks once a writer has blocked on the lock. The reason is
237 * that we currently allow for read locks to recurse and we
238 * don't keep track of all the holders of read locks. Thus, if
239 * we were to block readers once a writer blocked and a reader
240 * tried to recurse on their reader lock after a writer had
241 * blocked we would end up in a deadlock since the reader would
242 * be blocked on the writer, and the writer would be blocked
243 * waiting for the reader to release its original read lock.
244 */
245 for (;;) {
246 /*
247 * Handle the easy case. If no other thread has a write
248 * lock, then try to bump up the count of read locks. Note
249 * that we have to preserve the current state of the
250 * RW_LOCK_WRITE_WAITERS flag. If we fail to acquire a
251 * read lock, then rw_lock must have changed, so restart
252 * the loop. Note that this handles the case of a
253 * completely unlocked rwlock since such a lock is encoded
254 * as a read lock with no waiters.
255 */
256 x = rw->rw_lock;
257 if (x & RW_LOCK_READ) {
258
259 /*
260 * The RW_LOCK_READ_WAITERS flag should only be set
261 * if another thread currently holds a write lock,
262 * and in that case RW_LOCK_READ should be clear.
263 */
264 MPASS((x & RW_LOCK_READ_WAITERS) == 0);
265 if (atomic_cmpset_acq_ptr(&rw->rw_lock, x,
266 x + RW_ONE_READER)) {
267 #ifdef LOCK_PROFILING_SHARED
268 if (RW_READERS(x) == 0)
269 lock_profile_obtain_lock_success(
270 &rw->lock_object, contested,
271 waittime, file, line);
272 #endif
273 if (LOCK_LOG_TEST(&rw->lock_object, 0))
274 CTR4(KTR_LOCK,
275 "%s: %p succeed %p -> %p", __func__,
276 rw, (void *)x,
277 (void *)(x + RW_ONE_READER));
278 break;
279 }
280 cpu_spinwait();
281 continue;
282 }
283
284 #ifdef ADAPTIVE_RWLOCKS
285 /*
286 * If the owner is running on another CPU, spin until
287 * the owner stops running or the state of the lock
288 * changes.
289 */
290 owner = (struct thread *)RW_OWNER(x);
291 if (TD_IS_RUNNING(owner)) {
292 if (LOCK_LOG_TEST(&rw->lock_object, 0))
293 CTR3(KTR_LOCK, "%s: spinning on %p held by %p",
294 __func__, rw, owner);
295 #ifdef LOCK_PROFILING_SHARED
296 lock_profile_obtain_lock_failed(&rw->lock_object,
297 &contested, &waittime);
298 #endif
299 while ((struct thread*)RW_OWNER(rw->rw_lock) == owner &&
300 TD_IS_RUNNING(owner))
301 cpu_spinwait();
302 continue;
303 }
304 #endif
305
306 /*
307 * Okay, now it's the hard case. Some other thread already
308 * has a write lock, so acquire the turnstile lock so we can
309 * begin the process of blocking.
310 */
311 ts = turnstile_trywait(&rw->lock_object);
312
313 /*
314 * The lock might have been released while we spun, so
315 * recheck its state and restart the loop if there is no
316 * longer a write lock.
317 */
318 x = rw->rw_lock;
319 if (x & RW_LOCK_READ) {
320 turnstile_cancel(ts);
321 cpu_spinwait();
322 continue;
323 }
324
325 #ifdef ADAPTIVE_RWLOCKS
326 /*
327 * If the current owner of the lock is executing on another
328 * CPU quit the hard path and try to spin.
329 */
330 owner = (struct thread *)RW_OWNER(x);
331 if (TD_IS_RUNNING(owner)) {
332 turnstile_cancel(ts);
333 cpu_spinwait();
334 continue;
335 }
336 #endif
337
338 /*
339 * Ok, it's still a write lock. If the RW_LOCK_READ_WAITERS
340 * flag is already set, then we can go ahead and block. If
341 * it is not set then try to set it. If we fail to set it
342 * drop the turnstile lock and restart the loop.
343 */
344 if (!(x & RW_LOCK_READ_WAITERS)) {
345 if (!atomic_cmpset_ptr(&rw->rw_lock, x,
346 x | RW_LOCK_READ_WAITERS)) {
347 turnstile_cancel(ts);
348 cpu_spinwait();
349 continue;
350 }
351 if (LOCK_LOG_TEST(&rw->lock_object, 0))
352 CTR2(KTR_LOCK, "%s: %p set read waiters flag",
353 __func__, rw);
354 }
355
356 /*
357 * We were unable to acquire the lock and the read waiters
358 * flag is set, so we must block on the turnstile.
359 */
360 if (LOCK_LOG_TEST(&rw->lock_object, 0))
361 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__,
362 rw);
363 #ifdef LOCK_PROFILING_SHARED
364 lock_profile_obtain_lock_failed(&rw->lock_object, &contested,
365 &waittime);
366 #endif
367 turnstile_wait(ts, rw_owner(rw), TS_SHARED_QUEUE);
368 if (LOCK_LOG_TEST(&rw->lock_object, 0))
369 CTR2(KTR_LOCK, "%s: %p resuming from turnstile",
370 __func__, rw);
371 }
372
373 /*
374 * TODO: acquire "owner of record" here. Here be turnstile dragons
375 * however. turnstiles don't like owners changing between calls to
376 * turnstile_wait() currently.
377 */
378
379 LOCK_LOG_LOCK("RLOCK", &rw->lock_object, 0, 0, file, line);
380 WITNESS_LOCK(&rw->lock_object, 0, file, line);
381 curthread->td_locks++;
382 }
383
384 void
385 _rw_runlock(struct rwlock *rw, const char *file, int line)
386 {
387 struct turnstile *ts;
388 uintptr_t x;
389
390 KASSERT(rw->rw_lock != RW_DESTROYED,
391 ("rw_runlock() of destroyed rwlock @ %s:%d", file, line));
392 _rw_assert(rw, RA_RLOCKED, file, line);
393 curthread->td_locks--;
394 WITNESS_UNLOCK(&rw->lock_object, 0, file, line);
395 LOCK_LOG_LOCK("RUNLOCK", &rw->lock_object, 0, 0, file, line);
396
397 /* TODO: drop "owner of record" here. */
398
399 for (;;) {
400 /*
401 * See if there is more than one read lock held. If so,
402 * just drop one and return.
403 */
404 x = rw->rw_lock;
405 if (RW_READERS(x) > 1) {
406 if (atomic_cmpset_ptr(&rw->rw_lock, x,
407 x - RW_ONE_READER)) {
408 if (LOCK_LOG_TEST(&rw->lock_object, 0))
409 CTR4(KTR_LOCK,
410 "%s: %p succeeded %p -> %p",
411 __func__, rw, (void *)x,
412 (void *)(x - RW_ONE_READER));
413 break;
414 }
415 continue;
416 }
417
418
419 /*
420 * We should never have read waiters while at least one
421 * thread holds a read lock. (See note above)
422 */
423 KASSERT(!(x & RW_LOCK_READ_WAITERS),
424 ("%s: waiting readers", __func__));
425 #ifdef LOCK_PROFILING_SHARED
426 lock_profile_release_lock(&rw->lock_object);
427 #endif
428
429 /*
430 * If there aren't any waiters for a write lock, then try
431 * to drop it quickly.
432 */
433 if (!(x & RW_LOCK_WRITE_WAITERS)) {
434
435 /*
436 * There shouldn't be any flags set and we should
437 * be the only read lock. If we fail to release
438 * the single read lock, then another thread might
439 * have just acquired a read lock, so go back up
440 * to the multiple read locks case.
441 */
442 MPASS(x == RW_READERS_LOCK(1));
443 if (atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1),
444 RW_UNLOCKED)) {
445 if (LOCK_LOG_TEST(&rw->lock_object, 0))
446 CTR2(KTR_LOCK, "%s: %p last succeeded",
447 __func__, rw);
448 break;
449 }
450 continue;
451 }
452
453 /*
454 * There should just be one reader with one or more
455 * writers waiting.
456 */
457 MPASS(x == (RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS));
458
459 /*
460 * Ok, we know we have a waiting writer and we think we
461 * are the last reader, so grab the turnstile lock.
462 */
463 turnstile_chain_lock(&rw->lock_object);
464
465 /*
466 * Try to drop our lock leaving the lock in a unlocked
467 * state.
468 *
469 * If you wanted to do explicit lock handoff you'd have to
470 * do it here. You'd also want to use turnstile_signal()
471 * and you'd have to handle the race where a higher
472 * priority thread blocks on the write lock before the
473 * thread you wakeup actually runs and have the new thread
474 * "steal" the lock. For now it's a lot simpler to just
475 * wakeup all of the waiters.
476 *
477 * As above, if we fail, then another thread might have
478 * acquired a read lock, so drop the turnstile lock and
479 * restart.
480 */
481 if (!atomic_cmpset_ptr(&rw->rw_lock,
482 RW_READERS_LOCK(1) | RW_LOCK_WRITE_WAITERS, RW_UNLOCKED)) {
483 turnstile_chain_unlock(&rw->lock_object);
484 continue;
485 }
486 if (LOCK_LOG_TEST(&rw->lock_object, 0))
487 CTR2(KTR_LOCK, "%s: %p last succeeded with waiters",
488 __func__, rw);
489
490 /*
491 * Ok. The lock is released and all that's left is to
492 * wake up the waiters. Note that the lock might not be
493 * free anymore, but in that case the writers will just
494 * block again if they run before the new lock holder(s)
495 * release the lock.
496 */
497 ts = turnstile_lookup(&rw->lock_object);
498 MPASS(ts != NULL);
499 turnstile_broadcast(ts, TS_EXCLUSIVE_QUEUE);
500 turnstile_unpend(ts, TS_SHARED_LOCK);
501 turnstile_chain_unlock(&rw->lock_object);
502 break;
503 }
504 }
505
506 /*
507 * This function is called when we are unable to obtain a write lock on the
508 * first try. This means that at least one other thread holds either a
509 * read or write lock.
510 */
511 void
512 _rw_wlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line)
513 {
514 struct turnstile *ts;
515 #ifdef ADAPTIVE_RWLOCKS
516 volatile struct thread *owner;
517 #endif
518 uint64_t waittime = 0;
519 uintptr_t v;
520 int contested = 0;
521
522 if (rw_wlocked(rw)) {
523 KASSERT(rw->lock_object.lo_flags & RW_RECURSE,
524 ("%s: recursing but non-recursive rw %s @ %s:%d\n",
525 __func__, rw->lock_object.lo_name, file, line));
526 rw->rw_recurse++;
527 atomic_set_ptr(&rw->rw_lock, RW_LOCK_RECURSED);
528 if (LOCK_LOG_TEST(&rw->lock_object, 0))
529 CTR2(KTR_LOCK, "%s: %p recursing", __func__, rw);
530 return;
531 }
532
533 if (LOCK_LOG_TEST(&rw->lock_object, 0))
534 CTR5(KTR_LOCK, "%s: %s contested (lock=%p) at %s:%d", __func__,
535 rw->lock_object.lo_name, (void *)rw->rw_lock, file, line);
536
537 while (!_rw_write_lock(rw, tid)) {
538 #ifdef ADAPTIVE_RWLOCKS
539 /*
540 * If the lock is write locked and the owner is
541 * running on another CPU, spin until the owner stops
542 * running or the state of the lock changes.
543 */
544 v = rw->rw_lock;
545 owner = (struct thread *)RW_OWNER(v);
546 if (!(v & RW_LOCK_READ) && TD_IS_RUNNING(owner)) {
547 if (LOCK_LOG_TEST(&rw->lock_object, 0))
548 CTR3(KTR_LOCK, "%s: spinning on %p held by %p",
549 __func__, rw, owner);
550 lock_profile_obtain_lock_failed(&rw->lock_object,
551 &contested, &waittime);
552 while ((struct thread*)RW_OWNER(rw->rw_lock) == owner &&
553 TD_IS_RUNNING(owner))
554 cpu_spinwait();
555 continue;
556 }
557 #endif
558
559 ts = turnstile_trywait(&rw->lock_object);
560 v = rw->rw_lock;
561
562 /*
563 * If the lock was released while spinning on the
564 * turnstile chain lock, try again.
565 */
566 if (v == RW_UNLOCKED) {
567 turnstile_cancel(ts);
568 cpu_spinwait();
569 continue;
570 }
571
572 #ifdef ADAPTIVE_RWLOCKS
573 /*
574 * If the current owner of the lock is executing on another
575 * CPU quit the hard path and try to spin.
576 */
577 if (!(v & RW_LOCK_READ)) {
578 owner = (struct thread *)RW_OWNER(v);
579 if (TD_IS_RUNNING(owner)) {
580 turnstile_cancel(ts);
581 cpu_spinwait();
582 continue;
583 }
584 }
585 #endif
586
587 /*
588 * If the lock was released by a writer with both readers
589 * and writers waiting and a reader hasn't woken up and
590 * acquired the lock yet, rw_lock will be set to the
591 * value RW_UNLOCKED | RW_LOCK_WRITE_WAITERS. If we see
592 * that value, try to acquire it once. Note that we have
593 * to preserve the RW_LOCK_WRITE_WAITERS flag as there are
594 * other writers waiting still. If we fail, restart the
595 * loop.
596 */
597 if (v == (RW_UNLOCKED | RW_LOCK_WRITE_WAITERS)) {
598 if (atomic_cmpset_acq_ptr(&rw->rw_lock,
599 RW_UNLOCKED | RW_LOCK_WRITE_WAITERS,
600 tid | RW_LOCK_WRITE_WAITERS)) {
601 turnstile_claim(ts);
602 CTR2(KTR_LOCK, "%s: %p claimed by new writer",
603 __func__, rw);
604 break;
605 }
606 turnstile_cancel(ts);
607 cpu_spinwait();
608 continue;
609 }
610
611 /*
612 * If the RW_LOCK_WRITE_WAITERS flag isn't set, then try to
613 * set it. If we fail to set it, then loop back and try
614 * again.
615 */
616 if (!(v & RW_LOCK_WRITE_WAITERS)) {
617 if (!atomic_cmpset_ptr(&rw->rw_lock, v,
618 v | RW_LOCK_WRITE_WAITERS)) {
619 turnstile_cancel(ts);
620 cpu_spinwait();
621 continue;
622 }
623 if (LOCK_LOG_TEST(&rw->lock_object, 0))
624 CTR2(KTR_LOCK, "%s: %p set write waiters flag",
625 __func__, rw);
626 }
627
628 /*
629 * We were unable to acquire the lock and the write waiters
630 * flag is set, so we must block on the turnstile.
631 */
632 if (LOCK_LOG_TEST(&rw->lock_object, 0))
633 CTR2(KTR_LOCK, "%s: %p blocking on turnstile", __func__,
634 rw);
635 lock_profile_obtain_lock_failed(&rw->lock_object, &contested,
636 &waittime);
637 turnstile_wait(ts, rw_owner(rw), TS_EXCLUSIVE_QUEUE);
638 if (LOCK_LOG_TEST(&rw->lock_object, 0))
639 CTR2(KTR_LOCK, "%s: %p resuming from turnstile",
640 __func__, rw);
641 }
642 lock_profile_obtain_lock_success(&rw->lock_object, contested, waittime,
643 file, line);
644 }
645
646 /*
647 * This function is called if the first try at releasing a write lock failed.
648 * This means that one of the 2 waiter bits must be set indicating that at
649 * least one thread is waiting on this lock.
650 */
651 void
652 _rw_wunlock_hard(struct rwlock *rw, uintptr_t tid, const char *file, int line)
653 {
654 struct turnstile *ts;
655 uintptr_t v;
656 int queue;
657
658 if (rw_wlocked(rw) && rw_recursed(rw)) {
659 if ((--rw->rw_recurse) == 0)
660 atomic_clear_ptr(&rw->rw_lock, RW_LOCK_RECURSED);
661 if (LOCK_LOG_TEST(&rw->lock_object, 0))
662 CTR2(KTR_LOCK, "%s: %p unrecursing", __func__, rw);
663 return;
664 }
665
666 KASSERT(rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS),
667 ("%s: neither of the waiter flags are set", __func__));
668
669 if (LOCK_LOG_TEST(&rw->lock_object, 0))
670 CTR2(KTR_LOCK, "%s: %p contested", __func__, rw);
671
672 turnstile_chain_lock(&rw->lock_object);
673 ts = turnstile_lookup(&rw->lock_object);
674
675 MPASS(ts != NULL);
676
677 /*
678 * Use the same algo as sx locks for now. Prefer waking up shared
679 * waiters if we have any over writers. This is probably not ideal.
680 *
681 * 'v' is the value we are going to write back to rw_lock. If we
682 * have waiters on both queues, we need to preserve the state of
683 * the waiter flag for the queue we don't wake up. For now this is
684 * hardcoded for the algorithm mentioned above.
685 *
686 * In the case of both readers and writers waiting we wakeup the
687 * readers but leave the RW_LOCK_WRITE_WAITERS flag set. If a
688 * new writer comes in before a reader it will claim the lock up
689 * above. There is probably a potential priority inversion in
690 * there that could be worked around either by waking both queues
691 * of waiters or doing some complicated lock handoff gymnastics.
692 */
693 v = RW_UNLOCKED;
694 if (rw->rw_lock & RW_LOCK_READ_WAITERS) {
695 queue = TS_SHARED_QUEUE;
696 v |= (rw->rw_lock & RW_LOCK_WRITE_WAITERS);
697 } else
698 queue = TS_EXCLUSIVE_QUEUE;
699
700 /* Wake up all waiters for the specific queue. */
701 if (LOCK_LOG_TEST(&rw->lock_object, 0))
702 CTR3(KTR_LOCK, "%s: %p waking up %s waiters", __func__, rw,
703 queue == TS_SHARED_QUEUE ? "read" : "write");
704 turnstile_broadcast(ts, queue);
705 atomic_store_rel_ptr(&rw->rw_lock, v);
706 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK);
707 turnstile_chain_unlock(&rw->lock_object);
708 }
709
710 /*
711 * Attempt to do a non-blocking upgrade from a read lock to a write
712 * lock. This will only succeed if this thread holds a single read
713 * lock. Returns true if the upgrade succeeded and false otherwise.
714 */
715 int
716 _rw_try_upgrade(struct rwlock *rw, const char *file, int line)
717 {
718 uintptr_t v, tid;
719 struct turnstile *ts;
720 int success;
721
722 KASSERT(rw->rw_lock != RW_DESTROYED,
723 ("rw_try_upgrade() of destroyed rwlock @ %s:%d", file, line));
724 _rw_assert(rw, RA_RLOCKED, file, line);
725
726 /*
727 * Attempt to switch from one reader to a writer. If there
728 * are any write waiters, then we will have to lock the
729 * turnstile first to prevent races with another writer
730 * calling turnstile_wait() before we have claimed this
731 * turnstile. So, do the simple case of no waiters first.
732 */
733 tid = (uintptr_t)curthread;
734 if (!(rw->rw_lock & RW_LOCK_WRITE_WAITERS)) {
735 success = atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1),
736 tid);
737 goto out;
738 }
739
740 /*
741 * Ok, we think we have write waiters, so lock the
742 * turnstile.
743 */
744 ts = turnstile_trywait(&rw->lock_object);
745
746 /*
747 * Try to switch from one reader to a writer again. This time
748 * we honor the current state of the RW_LOCK_WRITE_WAITERS
749 * flag. If we obtain the lock with the flag set, then claim
750 * ownership of the turnstile.
751 */
752 v = rw->rw_lock & RW_LOCK_WRITE_WAITERS;
753 success = atomic_cmpset_ptr(&rw->rw_lock, RW_READERS_LOCK(1) | v,
754 tid | v);
755 if (success && v)
756 turnstile_claim(ts);
757 else
758 turnstile_cancel(ts);
759 out:
760 LOCK_LOG_TRY("WUPGRADE", &rw->lock_object, 0, success, file, line);
761 if (success)
762 WITNESS_UPGRADE(&rw->lock_object, LOP_EXCLUSIVE | LOP_TRYLOCK,
763 file, line);
764 return (success);
765 }
766
767 /*
768 * Downgrade a write lock into a single read lock.
769 */
770 void
771 _rw_downgrade(struct rwlock *rw, const char *file, int line)
772 {
773 struct turnstile *ts;
774 uintptr_t tid, v;
775
776 KASSERT(rw->rw_lock != RW_DESTROYED,
777 ("rw_downgrade() of destroyed rwlock @ %s:%d", file, line));
778 _rw_assert(rw, RA_WLOCKED | RA_NOTRECURSED, file, line);
779 #ifndef INVARIANTS
780 if (rw_recursed(rw))
781 panic("downgrade of a recursed lock");
782 #endif
783
784 WITNESS_DOWNGRADE(&rw->lock_object, 0, file, line);
785
786 /*
787 * Convert from a writer to a single reader. First we handle
788 * the easy case with no waiters. If there are any waiters, we
789 * lock the turnstile, "disown" the lock, and awaken any read
790 * waiters.
791 */
792 tid = (uintptr_t)curthread;
793 if (atomic_cmpset_rel_ptr(&rw->rw_lock, tid, RW_READERS_LOCK(1)))
794 goto out;
795
796 /*
797 * Ok, we think we have waiters, so lock the turnstile so we can
798 * read the waiter flags without any races.
799 */
800 turnstile_chain_lock(&rw->lock_object);
801 v = rw->rw_lock;
802 MPASS(v & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS));
803
804 /*
805 * Downgrade from a write lock while preserving
806 * RW_LOCK_WRITE_WAITERS and give up ownership of the
807 * turnstile. If there are any read waiters, wake them up.
808 */
809 ts = turnstile_lookup(&rw->lock_object);
810 MPASS(ts != NULL);
811 if (v & RW_LOCK_READ_WAITERS)
812 turnstile_broadcast(ts, TS_SHARED_QUEUE);
813 atomic_store_rel_ptr(&rw->rw_lock, RW_READERS_LOCK(1) |
814 (v & RW_LOCK_WRITE_WAITERS));
815 if (v & RW_LOCK_READ_WAITERS)
816 turnstile_unpend(ts, TS_EXCLUSIVE_LOCK);
817 else if (ts)
818 turnstile_disown(ts);
819 turnstile_chain_unlock(&rw->lock_object);
820 out:
821 LOCK_LOG_LOCK("WDOWNGRADE", &rw->lock_object, 0, 0, file, line);
822 }
823
824 #ifdef INVARIANT_SUPPORT
825 #ifndef INVARIANTS
826 #undef _rw_assert
827 #endif
828
829 /*
830 * In the non-WITNESS case, rw_assert() can only detect that at least
831 * *some* thread owns an rlock, but it cannot guarantee that *this*
832 * thread owns an rlock.
833 */
834 void
835 _rw_assert(struct rwlock *rw, int what, const char *file, int line)
836 {
837
838 if (panicstr != NULL)
839 return;
840 switch (what) {
841 case RA_LOCKED:
842 case RA_LOCKED | RA_RECURSED:
843 case RA_LOCKED | RA_NOTRECURSED:
844 case RA_RLOCKED:
845 #ifdef WITNESS
846 witness_assert(&rw->lock_object, what, file, line);
847 #else
848 /*
849 * If some other thread has a write lock or we have one
850 * and are asserting a read lock, fail. Also, if no one
851 * has a lock at all, fail.
852 */
853 if (rw->rw_lock == RW_UNLOCKED ||
854 (!(rw->rw_lock & RW_LOCK_READ) && (what == RA_RLOCKED ||
855 rw_wowner(rw) != curthread)))
856 panic("Lock %s not %slocked @ %s:%d\n",
857 rw->lock_object.lo_name, (what == RA_RLOCKED) ?
858 "read " : "", file, line);
859
860 if (!(rw->rw_lock & RW_LOCK_READ)) {
861 if (rw_recursed(rw)) {
862 if (what & RA_NOTRECURSED)
863 panic("Lock %s recursed @ %s:%d\n",
864 rw->lock_object.lo_name, file,
865 line);
866 } else if (what & RA_RECURSED)
867 panic("Lock %s not recursed @ %s:%d\n",
868 rw->lock_object.lo_name, file, line);
869 }
870 #endif
871 break;
872 case RA_WLOCKED:
873 case RA_WLOCKED | RA_RECURSED:
874 case RA_WLOCKED | RA_NOTRECURSED:
875 if (rw_wowner(rw) != curthread)
876 panic("Lock %s not exclusively locked @ %s:%d\n",
877 rw->lock_object.lo_name, file, line);
878 if (rw_recursed(rw)) {
879 if (what & RA_NOTRECURSED)
880 panic("Lock %s recursed @ %s:%d\n",
881 rw->lock_object.lo_name, file, line);
882 } else if (what & RA_RECURSED)
883 panic("Lock %s not recursed @ %s:%d\n",
884 rw->lock_object.lo_name, file, line);
885 break;
886 case RA_UNLOCKED:
887 #ifdef WITNESS
888 witness_assert(&rw->lock_object, what, file, line);
889 #else
890 /*
891 * If we hold a write lock fail. We can't reliably check
892 * to see if we hold a read lock or not.
893 */
894 if (rw_wowner(rw) == curthread)
895 panic("Lock %s exclusively locked @ %s:%d\n",
896 rw->lock_object.lo_name, file, line);
897 #endif
898 break;
899 default:
900 panic("Unknown rw lock assertion: %d @ %s:%d", what, file,
901 line);
902 }
903 }
904 #endif /* INVARIANT_SUPPORT */
905
906 #ifdef DDB
907 void
908 db_show_rwlock(struct lock_object *lock)
909 {
910 struct rwlock *rw;
911 struct thread *td;
912
913 rw = (struct rwlock *)lock;
914
915 db_printf(" state: ");
916 if (rw->rw_lock == RW_UNLOCKED)
917 db_printf("UNLOCKED\n");
918 else if (rw->rw_lock == RW_DESTROYED) {
919 db_printf("DESTROYED\n");
920 return;
921 } else if (rw->rw_lock & RW_LOCK_READ)
922 db_printf("RLOCK: %ju locks\n",
923 (uintmax_t)(RW_READERS(rw->rw_lock)));
924 else {
925 td = rw_wowner(rw);
926 db_printf("WLOCK: %p (tid %d, pid %d, \"%s\")\n", td,
927 td->td_tid, td->td_proc->p_pid, td->td_proc->p_comm);
928 if (rw_recursed(rw))
929 db_printf(" recursed: %u\n", rw->rw_recurse);
930 }
931 db_printf(" waiters: ");
932 switch (rw->rw_lock & (RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS)) {
933 case RW_LOCK_READ_WAITERS:
934 db_printf("readers\n");
935 break;
936 case RW_LOCK_WRITE_WAITERS:
937 db_printf("writers\n");
938 break;
939 case RW_LOCK_READ_WAITERS | RW_LOCK_WRITE_WAITERS:
940 db_printf("readers and writers\n");
941 break;
942 default:
943 db_printf("none\n");
944 break;
945 }
946 }
947
948 #endif
Cache object: fe12240ad5316b13367daefaed65c7ad
|