3 * The Regents of the University of California. All rights reserved.
5 * John S. Dyson. All rights reserved.
6 * Copyright (C) 2013-2014
7 * Matthew Dillon, All rights reserved.
9 * This code contains ideas from software contributed to Berkeley by
10 * Avadis Tevanian, Jr., Michael Wayne Young, and the Mach Operating
11 * System project at Carnegie-Mellon University.
13 * Redistribution and use in source and binary forms, with or without
14 * modification, are permitted provided that the following conditions
16 * 1. Redistributions of source code must retain the above copyright
17 * notice, this list of conditions and the following disclaimer.
18 * 2. Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the distribution.
21 * 3. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 #include <sys/param.h>
41 #include <sys/systm.h>
42 #include <sys/kernel.h>
45 #include <sys/sysctl.h>
46 #include <sys/spinlock.h>
47 #include <sys/thread2.h>
48 #include <sys/spinlock2.h>
50 extern struct lock sysctllock;
52 static void undo_upreq(struct lock *lkp);
54 #ifdef DEBUG_CANCEL_LOCKS
56 static int sysctl_cancel_lock(SYSCTL_HANDLER_ARGS);
57 static int sysctl_cancel_test(SYSCTL_HANDLER_ARGS);
59 static struct lock cancel_lk;
60 LOCK_SYSINIT(cancellk, &cancel_lk, "cancel", 0);
61 SYSCTL_PROC(_kern, OID_AUTO, cancel_lock, CTLTYPE_INT|CTLFLAG_RW, 0, 0,
62 sysctl_cancel_lock, "I", "test cancelable locks");
63 SYSCTL_PROC(_kern, OID_AUTO, cancel_test, CTLTYPE_INT|CTLFLAG_RW, 0, 0,
64 sysctl_cancel_test, "I", "test cancelable locks");
69 * Locking primitives implementation.
70 * Locks provide shared/exclusive sychronization.
74 #define COUNT(td, x) (td)->td_locks += (x)
79 #define LOCK_WAIT_TIME 100
80 #define LOCK_SAMPLE_WAIT 7
83 * Set, change, or release a lock.
87 lockmgr(struct lock *lkp, u_int flags)
89 debuglockmgr(struct lock *lkp, u_int flags,
90 const char *name, const char *file, int line)
107 if (mycpu->gd_intr_nesting_level &&
108 (flags & LK_NOWAIT) == 0 &&
109 (flags & LK_TYPE_MASK) != LK_RELEASE &&
110 panic_cpu_gd != mycpu
114 panic("lockmgr %s from %p: called from interrupt, ipi, "
115 "or hard code section",
116 lkp->lk_wmesg, ((int **)&lkp)[-1]);
118 panic("lockmgr %s from %s:%d: called from interrupt, ipi, "
119 "or hard code section",
120 lkp->lk_wmesg, file, line);
125 if (mycpu->gd_spinlocks && ((flags & LK_NOWAIT) == 0)) {
126 panic("lockmgr %s from %s:%d: called with %d spinlocks held",
127 lkp->lk_wmesg, file, line, mycpu->gd_spinlocks);
131 extflags = (flags | lkp->lk_flags) & LK_EXTFLG_MASK;
135 count = lkp->lk_count;
138 switch (flags & LK_TYPE_MASK) {
141 * Shared lock critical path case
143 if ((count & (LKC_EXREQ|LKC_UPREQ|LKC_EXCL)) == 0) {
144 if (atomic_cmpset_int(&lkp->lk_count,
153 * If the caller already holds the lock exclusively then
154 * we silently obtain another count on the exclusive lock.
156 * WARNING! The old FreeBSD behavior was to downgrade,
157 * but this creates a problem when recursions
158 * return to the caller and the caller expects
159 * its original exclusive lock to remain exclusively
162 if (lkp->lk_lockholder == td) {
163 KKASSERT(count & LKC_EXCL);
164 if ((extflags & LK_CANRECURSE) == 0) {
165 if (extflags & LK_NOWAIT) {
169 panic("lockmgr: locking against myself");
171 atomic_add_int(&lkp->lk_count, 1);
179 pflags = (extflags & LK_PCATCH) ? PCATCH : 0;
180 timo = (extflags & LK_TIMELOCK) ? lkp->lk_timo : 0;
181 wflags = (td->td_flags & TDF_DEADLKTREAT) ?
182 LKC_EXCL : (LKC_EXCL|LKC_EXREQ|LKC_UPREQ);
185 * Block while the lock is held exclusively or, conditionally,
186 * if other threads are tring to obtain an exclusive lock or
189 if (count & wflags) {
190 if (extflags & LK_CANCELABLE) {
191 if (count & LKC_CANCEL) {
196 if (extflags & LK_NOWAIT) {
200 tsleep_interlock(lkp, pflags);
201 if (!atomic_cmpset_int(&lkp->lk_count, count,
202 count | LKC_SHREQ)) {
206 mycpu->gd_cnt.v_lock_name[0] = 'S';
207 strncpy(mycpu->gd_cnt.v_lock_name + 1,
209 sizeof(mycpu->gd_cnt.v_lock_name) - 2);
210 ++mycpu->gd_cnt.v_lock_colls;
212 error = tsleep(lkp, pflags | PINTERLOCKED,
213 lkp->lk_wmesg, timo);
216 if (extflags & LK_SLEEPFAIL) {
224 * Otherwise we can bump the count
226 if (atomic_cmpset_int(&lkp->lk_count, count, count + 1)) {
234 * Exclusive lock critical path.
237 if (atomic_cmpset_int(&lkp->lk_count, count,
238 LKC_EXCL | (count + 1))) {
239 lkp->lk_lockholder = td;
247 * Recursive lock if we already hold it exclusively.
249 if (lkp->lk_lockholder == td) {
250 KKASSERT(count & LKC_EXCL);
251 if ((extflags & LK_CANRECURSE) == 0) {
252 if (extflags & LK_NOWAIT) {
256 panic("lockmgr: locking against myself");
258 atomic_add_int(&lkp->lk_count, 1);
264 * We will block, handle LK_NOWAIT
266 if (extflags & LK_NOWAIT) {
270 if (extflags & LK_CANCELABLE) {
271 if (count & LKC_CANCEL) {
278 * Wait until we can obtain the exclusive lock. EXREQ is
279 * automatically cleared when all current holders release
280 * so if we abort the operation we can safely leave it set.
281 * There might be other exclusive requesters.
283 pflags = (extflags & LK_PCATCH) ? PCATCH : 0;
284 timo = (extflags & LK_TIMELOCK) ? lkp->lk_timo : 0;
286 tsleep_interlock(lkp, pflags);
287 if (!atomic_cmpset_int(&lkp->lk_count, count,
288 count | LKC_EXREQ)) {
292 mycpu->gd_cnt.v_lock_name[0] = 'X';
293 strncpy(mycpu->gd_cnt.v_lock_name + 1,
295 sizeof(mycpu->gd_cnt.v_lock_name) - 2);
296 ++mycpu->gd_cnt.v_lock_colls;
298 error = tsleep(lkp, pflags | PINTERLOCKED,
299 lkp->lk_wmesg, timo);
302 if (extflags & LK_SLEEPFAIL) {
310 * Downgrade an exclusive lock into a shared lock. All
311 * counts on a recursive exclusive lock become shared.
313 * This function always succeeds.
315 if (lkp->lk_lockholder != td ||
316 (count & (LKC_EXCL|LKC_MASK)) != (LKC_EXCL|1)) {
317 panic("lockmgr: not holding exclusive lock");
321 for (i = 0; i < LOCKMGR_DEBUG_ARRAY_SIZE; i++) {
322 if (td->td_lockmgr_stack[i] == lkp &&
323 td->td_lockmgr_stack_id[i] > 0
325 td->td_lockmgr_stack_id[i]--;
331 * NOTE! Must NULL-out lockholder before releasing LKC_EXCL.
333 otd = lkp->lk_lockholder;
334 lkp->lk_lockholder = NULL;
335 if (atomic_cmpset_int(&lkp->lk_count, count,
336 count & ~(LKC_EXCL|LKC_SHREQ))) {
337 if (count & LKC_SHREQ)
341 lkp->lk_lockholder = otd;
346 * Upgrade from a single shared lock to an exclusive lock.
348 * If another process is ahead of us to get an upgrade,
349 * then we want to fail rather than have an intervening
350 * exclusive access. The shared lock is released on
353 if (count & LKC_UPREQ) {
358 /* fall through into normal upgrade */
362 * Upgrade a shared lock to an exclusive one. This can cause
363 * the lock to be temporarily released and stolen by other
364 * threads. LK_SLEEPFAIL or LK_NOWAIT may be used to detect
365 * this case, or use LK_EXCLUPGRADE.
367 * If the lock is already exclusively owned by us, this
368 * operation is a NOP.
370 * If we return an error (even NOWAIT), the current lock will
373 * Start with the critical path.
375 if ((count & (LKC_UPREQ|LKC_EXCL|LKC_MASK)) == 1) {
376 if (atomic_cmpset_int(&lkp->lk_count, count,
378 lkp->lk_lockholder = td;
385 * If we already hold the lock exclusively this operation
386 * succeeds and is a NOP.
388 if (count & LKC_EXCL) {
389 if (lkp->lk_lockholder == td)
391 panic("lockmgr: upgrade unowned lock");
393 if ((count & LKC_MASK) == 0)
394 panic("lockmgr: upgrade unowned lock");
397 * We cannot upgrade without blocking at this point.
399 if (extflags & LK_NOWAIT) {
404 if (extflags & LK_CANCELABLE) {
405 if (count & LKC_CANCEL) {
412 * Release the shared lock and request the upgrade.
414 pflags = (extflags & LK_PCATCH) ? PCATCH : 0;
415 timo = (extflags & LK_TIMELOCK) ? lkp->lk_timo : 0;
416 tsleep_interlock(lkp, pflags);
417 wflags = (count & LKC_UPREQ) ? LKC_EXREQ : LKC_UPREQ;
420 * If someone else owns UPREQ and this transition would
421 * allow it to be granted, we have to grant it. Otherwise
422 * we release the shared lock.
424 if ((count & (LKC_UPREQ|LKC_MASK)) == (LKC_UPREQ | 1)) {
425 wflags |= LKC_EXCL | LKC_UPGRANT;
427 wflags &= ~LKC_UPREQ;
429 wflags |= (count - 1);
432 if (atomic_cmpset_int(&lkp->lk_count, count, wflags)) {
436 * Must wakeup the thread granted the upgrade.
438 if ((count & (LKC_UPREQ|LKC_MASK)) == (LKC_UPREQ | 1))
441 mycpu->gd_cnt.v_lock_name[0] = 'U';
442 strncpy(mycpu->gd_cnt.v_lock_name + 1,
444 sizeof(mycpu->gd_cnt.v_lock_name) - 2);
445 ++mycpu->gd_cnt.v_lock_colls;
447 error = tsleep(lkp, pflags | PINTERLOCKED,
448 lkp->lk_wmesg, timo);
451 if (extflags & LK_SLEEPFAIL) {
457 * Refactor to either LK_EXCLUSIVE or LK_WAITUPGRADE,
458 * depending on whether we were able to acquire the
461 if (count & LKC_UPREQ)
462 flags = LK_EXCLUSIVE; /* someone else */
464 flags = LK_WAITUPGRADE; /* we own the bit */
470 * We own the LKC_UPREQ bit, wait until we are granted the
471 * exclusive lock (LKC_UPGRANT is set).
473 * IF THE OPERATION FAILS (tsleep error tsleep+LK_SLEEPFAIL),
474 * we have to undo the upgrade request and clean up any lock
475 * that might have been granted via a race.
477 if (count & LKC_UPGRANT) {
478 if (atomic_cmpset_int(&lkp->lk_count, count,
479 count & ~LKC_UPGRANT)) {
480 lkp->lk_lockholder = td;
481 KKASSERT(count & LKC_EXCL);
485 } else if ((count & LKC_CANCEL) && (extflags & LK_CANCELABLE)) {
490 pflags = (extflags & LK_PCATCH) ? PCATCH : 0;
491 timo = (extflags & LK_TIMELOCK) ? lkp->lk_timo : 0;
492 tsleep_interlock(lkp, pflags);
493 if (atomic_cmpset_int(&lkp->lk_count, count, count)) {
495 mycpu->gd_cnt.v_lock_name[0] = 'U';
496 strncpy(mycpu->gd_cnt.v_lock_name + 1,
498 sizeof(mycpu->gd_cnt.v_lock_name) - 2);
499 ++mycpu->gd_cnt.v_lock_colls;
501 error = tsleep(lkp, pflags | PINTERLOCKED,
502 lkp->lk_wmesg, timo);
507 if (extflags & LK_SLEEPFAIL) {
519 * Release the currently held lock. If releasing the current
520 * lock as part of an error return, error will ALREADY be
523 * When releasing the last lock we automatically transition
524 * LKC_UPREQ to LKC_EXCL|1.
526 * WARNING! We cannot detect when there are multiple exclusive
527 * requests pending. We clear EXREQ unconditionally
528 * on the 1->0 transition so it is possible for
529 * shared requests to race the next exclusive
534 if ((count & LKC_MASK) == 0)
535 panic("lockmgr: LK_RELEASE: no lock held");
537 if (count & LKC_EXCL) {
538 if (lkp->lk_lockholder != LK_KERNTHREAD &&
539 lkp->lk_lockholder != td) {
540 panic("lockmgr: pid %d, not exlusive "
541 "lock holder thr %p/%p unlocking",
542 (td->td_proc ? td->td_proc->p_pid : -1),
543 td, lkp->lk_lockholder);
545 if ((count & (LKC_UPREQ|LKC_MASK)) == 1) {
547 * Last exclusive count is being released
549 otd = lkp->lk_lockholder;
550 lkp->lk_lockholder = NULL;
551 if (!atomic_cmpset_int(&lkp->lk_count, count,
553 ~(LKC_EXCL | LKC_EXREQ |
554 LKC_SHREQ| LKC_CANCEL))) {
555 lkp->lk_lockholder = otd;
558 if (count & (LKC_EXREQ|LKC_SHREQ))
561 } else if ((count & (LKC_UPREQ|LKC_MASK)) ==
564 * Last exclusive count is being released but
565 * an upgrade request is present, automatically
566 * grant an exclusive state to the owner of
567 * the upgrade request.
569 otd = lkp->lk_lockholder;
570 lkp->lk_lockholder = NULL;
571 if (!atomic_cmpset_int(&lkp->lk_count, count,
572 (count & ~LKC_UPREQ) |
574 lkp->lk_lockholder = otd;
579 otd = lkp->lk_lockholder;
580 if (!atomic_cmpset_int(&lkp->lk_count, count,
587 if (otd != LK_KERNTHREAD)
590 if ((count & (LKC_UPREQ|LKC_MASK)) == 1) {
592 * Last shared count is being released.
594 if (!atomic_cmpset_int(&lkp->lk_count, count,
596 ~(LKC_EXREQ | LKC_SHREQ |
600 if (count & (LKC_EXREQ|LKC_SHREQ))
603 } else if ((count & (LKC_UPREQ|LKC_MASK)) ==
606 * Last shared count is being released but
607 * an upgrade request is present, automatically
608 * grant an exclusive state to the owner of
609 * the upgrade request. Masked count
612 if (!atomic_cmpset_int(&lkp->lk_count, count,
613 (count & ~(LKC_UPREQ |
615 LKC_EXCL | LKC_UPGRANT)) {
620 if (!atomic_cmpset_int(&lkp->lk_count, count,
632 * Start canceling blocked requestors or later requestors.
633 * requestors must use CANCELABLE. Don't waste time issuing
634 * a wakeup if nobody is pending.
636 KKASSERT((count & LKC_CANCEL) == 0); /* disallowed case */
637 KKASSERT((count & LKC_MASK) != 0); /* issue w/lock held */
638 if (!atomic_cmpset_int(&lkp->lk_count,
639 count, count | LKC_CANCEL)) {
642 if (count & (LKC_EXREQ|LKC_SHREQ|LKC_UPREQ)) {
648 atomic_clear_int(&lkp->lk_count, LKC_CANCEL);
652 panic("lockmgr: unknown locktype request %d",
653 flags & LK_TYPE_MASK);
660 * Undo an upgrade request
664 undo_upreq(struct lock *lkp)
669 count = lkp->lk_count;
671 if (count & LKC_UPGRANT) {
673 * UPREQ was shifted to UPGRANT. We own UPGRANT now,
674 * another thread might own UPREQ. Clear UPGRANT
675 * and release the granted lock.
677 if (atomic_cmpset_int(&lkp->lk_count, count,
678 count & ~LKC_UPGRANT)) {
679 lockmgr(lkp, LK_RELEASE);
682 } else if (count & LKC_EXCL) {
684 * Clear the UPREQ we still own. Nobody to wakeup
685 * here because there is an existing exclusive
688 KKASSERT(count & LKC_UPREQ);
689 KKASSERT((count & LKC_MASK) > 0);
690 if (atomic_cmpset_int(&lkp->lk_count, count,
691 count & ~LKC_UPREQ)) {
695 } else if (count & LKC_EXREQ) {
697 * Clear the UPREQ we still own. We cannot wakeup any
698 * shared waiters because there is an exclusive
701 KKASSERT(count & LKC_UPREQ);
702 KKASSERT((count & LKC_MASK) > 0);
703 if (atomic_cmpset_int(&lkp->lk_count, count,
704 count & ~LKC_UPREQ)) {
709 * Clear the UPREQ we still own. Wakeup any shared
712 KKASSERT(count & LKC_UPREQ);
713 KKASSERT((count & LKC_MASK) > 0);
714 if (atomic_cmpset_int(&lkp->lk_count, count,
716 ~(LKC_UPREQ | LKC_SHREQ))) {
717 if (count & LKC_SHREQ)
727 lockmgr_kernproc(struct lock *lp)
729 struct thread *td __debugvar = curthread;
731 if (lp->lk_lockholder != LK_KERNTHREAD) {
732 KASSERT(lp->lk_lockholder == td,
733 ("lockmgr_kernproc: lock not owned by curthread %p", td));
734 lp->lk_lockholder = LK_KERNTHREAD;
740 * Initialize a lock; required before use.
743 lockinit(struct lock *lkp, const char *wmesg, int timo, int flags)
745 lkp->lk_flags = (flags & LK_EXTFLG_MASK);
747 lkp->lk_wmesg = wmesg;
749 lkp->lk_lockholder = LK_NOTHREAD;
753 * Reinitialize a lock that is being reused for a different purpose, but
754 * which may have pending (blocked) threads sitting on it. The caller
755 * must already hold the interlock.
758 lockreinit(struct lock *lkp, const char *wmesg, int timo, int flags)
760 lkp->lk_wmesg = wmesg;
765 * De-initialize a lock. The structure must no longer be used by anyone.
768 lockuninit(struct lock *lkp)
770 KKASSERT((lkp->lk_count & (LKC_EXREQ|LKC_SHREQ|LKC_UPREQ)) == 0);
774 * Determine the status of a lock.
777 lockstatus(struct lock *lkp, struct thread *td)
782 count = lkp->lk_count;
785 if (count & LKC_EXCL) {
786 if (td == NULL || lkp->lk_lockholder == td)
787 lock_type = LK_EXCLUSIVE;
789 lock_type = LK_EXCLOTHER;
790 } else if (count & LKC_MASK) {
791 lock_type = LK_SHARED;
797 * Return non-zero if the caller owns the lock shared or exclusive.
798 * We can only guess re: shared locks.
801 lockowned(struct lock *lkp)
803 thread_t td = curthread;
806 count = lkp->lk_count;
809 if (count & LKC_EXCL)
810 return(lkp->lk_lockholder == td);
812 return((count & LKC_MASK) != 0);
816 * Determine the number of holders of a lock.
818 * The non-blocking version can usually be used for assertions.
821 lockcount(struct lock *lkp)
823 return(lkp->lk_count & LKC_MASK);
827 lockcountnb(struct lock *lkp)
829 return(lkp->lk_count & LKC_MASK);
833 * Print out information about state of a lock. Used by VOP_PRINT
834 * routines to display status about contained locks.
837 lockmgr_printinfo(struct lock *lkp)
839 struct thread *td = lkp->lk_lockholder;
843 count = lkp->lk_count;
846 if (td && td != LK_KERNTHREAD && td != LK_NOTHREAD)
851 if (count & LKC_EXCL) {
852 kprintf(" lock type %s: EXCLUS (count %08x) by td %p pid %d",
853 lkp->lk_wmesg, count, td,
855 } else if (count & LKC_MASK) {
856 kprintf(" lock type %s: SHARED (count %08x)",
857 lkp->lk_wmesg, count);
859 kprintf(" lock type %s: NOTHELD", lkp->lk_wmesg);
861 if (count & (LKC_EXREQ|LKC_SHREQ))
862 kprintf(" with waiters\n");
868 lock_sysinit(struct lock_args *arg)
870 lockinit(arg->la_lock, arg->la_desc, 0, arg->la_flags);
873 #ifdef DEBUG_CANCEL_LOCKS
877 sysctl_cancel_lock(SYSCTL_HANDLER_ARGS)
882 lockmgr(&sysctllock, LK_RELEASE);
883 lockmgr(&cancel_lk, LK_EXCLUSIVE);
885 error = tsleep(&error, PCATCH, "canmas", hz * 5);
886 lockmgr(&cancel_lk, LK_CANCEL_BEG);
888 error = tsleep(&error, PCATCH, "canmas", hz * 5);
890 lockmgr(&cancel_lk, LK_RELEASE);
891 lockmgr(&sysctllock, LK_EXCLUSIVE);
892 SYSCTL_OUT(req, &error, sizeof(error));
901 sysctl_cancel_test(SYSCTL_HANDLER_ARGS)
906 error = lockmgr(&cancel_lk, LK_EXCLUSIVE|LK_CANCELABLE);
908 lockmgr(&cancel_lk, LK_RELEASE);
909 SYSCTL_OUT(req, &error, sizeof(error));
910 kprintf("test %d\n", error);