Allow kernel to be compile without _KPOSIX_PRIORITY_SCHEDULING.
[dragonfly.git] / sys / kern / kern_lock.c
1 /* 
2  * Copyright (c) 1995
3  *      The Regents of the University of California.  All rights reserved.
4  *
5  * Copyright (C) 1997
6  *      John S. Dyson.  All rights reserved.
7  *
8  * This code contains ideas from software contributed to Berkeley by
9  * Avadis Tevanian, Jr., Michael Wayne Young, and the Mach Operating
10  * System project at Carnegie-Mellon University.
11  *
12  * Redistribution and use in source and binary forms, with or without
13  * modification, are permitted provided that the following conditions
14  * are met:
15  * 1. Redistributions of source code must retain the above copyright
16  *    notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  *    notice, this list of conditions and the following disclaimer in the
19  *    documentation and/or other materials provided with the distribution.
20  * 3. All advertising materials mentioning features or use of this software
21  *    must display the following acknowledgement:
22  *      This product includes software developed by the University of
23  *      California, Berkeley and its contributors.
24  * 4. Neither the name of the University nor the names of its contributors
25  *    may be used to endorse or promote products derived from this software
26  *    without specific prior written permission.
27  *
28  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38  * SUCH DAMAGE.
39  *
40  *      @(#)kern_lock.c 8.18 (Berkeley) 5/21/95
41  * $FreeBSD: src/sys/kern/kern_lock.c,v 1.31.2.3 2001/12/25 01:44:44 dillon Exp $
42  * $DragonFly: src/sys/kern/kern_lock.c,v 1.27 2008/01/09 10:59:12 corecode Exp $
43  */
44
45 #include "opt_lint.h"
46
47 #include <sys/param.h>
48 #include <sys/systm.h>
49 #include <sys/kernel.h>
50 #include <sys/proc.h>
51 #include <sys/lock.h>
52 #include <sys/sysctl.h>
53 #include <sys/spinlock.h>
54 #include <sys/thread2.h>
55 #include <sys/spinlock2.h>
56
57 /*
58  * 0: no warnings, 1: warnings, 2: panic
59  */
60 static int lockmgr_from_int = 1;
61 SYSCTL_INT(_debug, OID_AUTO, lockmgr_from_int, CTLFLAG_RW, &lockmgr_from_int, 0, "");
62
63 /*
64  * Locking primitives implementation.
65  * Locks provide shared/exclusive sychronization.
66  */
67
68 #ifdef SIMPLELOCK_DEBUG
69 #define COUNT(td, x) (td)->td_locks += (x)
70 #else
71 #define COUNT(td, x)
72 #endif
73
74 #define LOCK_WAIT_TIME 100
75 #define LOCK_SAMPLE_WAIT 7
76
77 #if defined(DIAGNOSTIC)
78 #define LOCK_INLINE
79 #else
80 #define LOCK_INLINE __inline
81 #endif
82
83 #define LK_ALL (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE | \
84         LK_SHARE_NONZERO | LK_WAIT_NONZERO)
85
86 static int acquire(struct lock *lkp, int extflags, int wanted);
87
88 static LOCK_INLINE void
89 sharelock(struct lock *lkp, int incr) {
90         lkp->lk_flags |= LK_SHARE_NONZERO;
91         lkp->lk_sharecount += incr;
92 }
93
94 static LOCK_INLINE int
95 shareunlock(struct lock *lkp, int decr) 
96 {
97         int dowakeup = 0;
98
99         KASSERT(lkp->lk_sharecount >= decr, ("shareunlock: count < decr"));
100
101         if (lkp->lk_sharecount == decr) {
102                 lkp->lk_flags &= ~LK_SHARE_NONZERO;
103                 if (lkp->lk_flags & (LK_WANT_UPGRADE | LK_WANT_EXCL)) {
104                         dowakeup = 1;
105                 }
106                 lkp->lk_sharecount = 0;
107         } else {
108                 lkp->lk_sharecount -= decr;
109         }
110         return(dowakeup);
111 }
112
113 /*
114  * lock acquisition helper routine.  Called with the lock's spinlock held.
115  */
116 static int
117 acquire(struct lock *lkp, int extflags, int wanted) 
118 {
119         int error;
120
121         if ((extflags & LK_NOWAIT) && (lkp->lk_flags & wanted)) {
122                 return EBUSY;
123         }
124
125         while ((lkp->lk_flags & wanted) != 0) {
126                 lkp->lk_flags |= LK_WAIT_NONZERO;
127                 lkp->lk_waitcount++;
128
129                 /*
130                  * Atomic spinlock release/sleep/reacquire.
131                  */
132                 error = ssleep(lkp, &lkp->lk_spinlock,
133                                ((extflags & LK_PCATCH) ? PCATCH : 0),
134                                lkp->lk_wmesg, 
135                                ((extflags & LK_TIMELOCK) ? lkp->lk_timo : 0));
136                 if (lkp->lk_waitcount == 1) {
137                         lkp->lk_flags &= ~LK_WAIT_NONZERO;
138                         lkp->lk_waitcount = 0;
139                 } else {
140                         lkp->lk_waitcount--;
141                 }
142                 if (error)
143                         return error;
144                 if (extflags & LK_SLEEPFAIL)
145                         return ENOLCK;
146         }
147         return 0;
148 }
149
150 /*
151  * Set, change, or release a lock.
152  *
153  * Shared requests increment the shared count. Exclusive requests set the
154  * LK_WANT_EXCL flag (preventing further shared locks), and wait for already
155  * accepted shared locks and shared-to-exclusive upgrades to go away.
156  *
157  * A spinlock is held for most of the procedure.  We must not do anything
158  * fancy while holding the spinlock.
159  */
160 int
161 #ifndef DEBUG_LOCKS
162 lockmgr(struct lock *lkp, u_int flags)
163 #else
164 debuglockmgr(struct lock *lkp, u_int flags,
165              const char *name, const char *file, int line)
166 #endif
167 {
168         thread_t td;
169         int error;
170         int extflags;
171         int dowakeup;
172         static int didpanic;
173
174         error = 0;
175         dowakeup = 0;
176
177         if (lockmgr_from_int && mycpu->gd_intr_nesting_level &&
178             (flags & LK_NOWAIT) == 0 &&
179             (flags & LK_TYPE_MASK) != LK_RELEASE && didpanic == 0) {
180 #ifndef DEBUG_LOCKS
181                     if (lockmgr_from_int == 2) {
182                             didpanic = 1;
183                             panic(
184                                 "lockmgr %s from %p: called from interrupt",
185                                 lkp->lk_wmesg, ((int **)&lkp)[-1]);
186                             didpanic = 0;
187                     } else {
188                             kprintf(
189                                 "lockmgr %s from %p: called from interrupt\n",
190                                 lkp->lk_wmesg, ((int **)&lkp)[-1]);
191                     }
192 #else
193                     if (lockmgr_from_int == 2) {
194                             didpanic = 1;
195                             panic(
196                                 "lockmgr %s from %s:%d: called from interrupt",
197                                 lkp->lk_wmesg, file, line);
198                             didpanic = 0;
199                     } else {
200                             kprintf(
201                                 "lockmgr %s from %s:%d: called from interrupt\n",
202                                 lkp->lk_wmesg, file, line);
203                     }
204 #endif
205         }
206
207         /*
208          * So sue me, I'm too tired.
209          */
210         if (spin_trylock_wr(&lkp->lk_spinlock) == FALSE) {
211                 if (flags & LK_NOSPINWAIT)
212                         return(EBUSY);
213                 spin_lock_wr(&lkp->lk_spinlock);
214         }
215
216         extflags = (flags | lkp->lk_flags) & LK_EXTFLG_MASK;
217         td = curthread;
218
219         switch (flags & LK_TYPE_MASK) {
220         case LK_SHARED:
221                 /*
222                  * If we are not the exclusive lock holder, we have to block
223                  * while there is an exclusive lock holder or while an
224                  * exclusive lock request or upgrade request is in progress.
225                  *
226                  * However, if P_DEADLKTREAT is set, we override exclusive
227                  * lock requests or upgrade requests ( but not the exclusive
228                  * lock itself ).
229                  */
230                 if (lkp->lk_lockholder != td) {
231                         if (td->td_flags & TDF_DEADLKTREAT) {
232                                 error = acquire(
233                                             lkp,
234                                             extflags,
235                                             LK_HAVE_EXCL
236                                         );
237                         } else {
238                                 error = acquire(
239                                             lkp, 
240                                             extflags,
241                                             LK_HAVE_EXCL | LK_WANT_EXCL | 
242                                              LK_WANT_UPGRADE
243                                         );
244                         }
245                         if (error)
246                                 break;
247                         sharelock(lkp, 1);
248                         COUNT(td, 1);
249                         break;
250                 }
251                 /*
252                  * We hold an exclusive lock, so downgrade it to shared.
253                  * An alternative would be to fail with EDEADLK.
254                  */
255                 sharelock(lkp, 1);
256                 COUNT(td, 1);
257                 /* fall into downgrade */
258
259         case LK_DOWNGRADE:
260                 if (lkp->lk_lockholder != td || lkp->lk_exclusivecount == 0) {
261                         spin_unlock_wr(&lkp->lk_spinlock);
262                         panic("lockmgr: not holding exclusive lock");
263                 }
264                 sharelock(lkp, lkp->lk_exclusivecount);
265                 lkp->lk_exclusivecount = 0;
266                 lkp->lk_flags &= ~LK_HAVE_EXCL;
267                 lkp->lk_lockholder = LK_NOTHREAD;
268                 if (lkp->lk_waitcount)
269                         dowakeup = 1;
270                 break;
271
272         case LK_EXCLUPGRADE:
273                 /*
274                  * If another process is ahead of us to get an upgrade,
275                  * then we want to fail rather than have an intervening
276                  * exclusive access.
277                  */
278                 if (lkp->lk_flags & LK_WANT_UPGRADE) {
279                         dowakeup = shareunlock(lkp, 1);
280                         COUNT(td, -1);
281                         error = EBUSY;
282                         break;
283                 }
284                 /* fall into normal upgrade */
285
286         case LK_UPGRADE:
287                 /*
288                  * Upgrade a shared lock to an exclusive one. If another
289                  * shared lock has already requested an upgrade to an
290                  * exclusive lock, our shared lock is released and an
291                  * exclusive lock is requested (which will be granted
292                  * after the upgrade). If we return an error, the file
293                  * will always be unlocked.
294                  */
295                 if ((lkp->lk_lockholder == td) || (lkp->lk_sharecount <= 0)) {
296                         spin_unlock_wr(&lkp->lk_spinlock);
297                         panic("lockmgr: upgrade exclusive lock");
298                 }
299                 dowakeup += shareunlock(lkp, 1);
300                 COUNT(td, -1);
301                 /*
302                  * If we are just polling, check to see if we will block.
303                  */
304                 if ((extflags & LK_NOWAIT) &&
305                     ((lkp->lk_flags & LK_WANT_UPGRADE) ||
306                      lkp->lk_sharecount > 1)) {
307                         error = EBUSY;
308                         break;
309                 }
310                 if ((lkp->lk_flags & LK_WANT_UPGRADE) == 0) {
311                         /*
312                          * We are first shared lock to request an upgrade, so
313                          * request upgrade and wait for the shared count to
314                          * drop to zero, then take exclusive lock.
315                          */
316                         lkp->lk_flags |= LK_WANT_UPGRADE;
317                         error = acquire(lkp, extflags, LK_SHARE_NONZERO);
318                         lkp->lk_flags &= ~LK_WANT_UPGRADE;
319
320                         if (error)
321                                 break;
322                         lkp->lk_flags |= LK_HAVE_EXCL;
323                         lkp->lk_lockholder = td;
324                         if (lkp->lk_exclusivecount != 0) {
325                                 spin_unlock_wr(&lkp->lk_spinlock);
326                                 panic("lockmgr: non-zero exclusive count");
327                         }
328                         lkp->lk_exclusivecount = 1;
329 #if defined(DEBUG_LOCKS)
330                         lkp->lk_filename = file;
331                         lkp->lk_lineno = line;
332                         lkp->lk_lockername = name;
333 #endif
334                         COUNT(td, 1);
335                         break;
336                 }
337                 /*
338                  * Someone else has requested upgrade. Release our shared
339                  * lock, awaken upgrade requestor if we are the last shared
340                  * lock, then request an exclusive lock.
341                  */
342                 if ( (lkp->lk_flags & (LK_SHARE_NONZERO|LK_WAIT_NONZERO)) ==
343                         LK_WAIT_NONZERO) {
344                         ++dowakeup;
345                 }
346                 /* fall into exclusive request */
347
348         case LK_EXCLUSIVE:
349                 if (lkp->lk_lockholder == td && td != LK_KERNTHREAD) {
350                         /*
351                          *      Recursive lock.
352                          */
353                         if ((extflags & (LK_NOWAIT | LK_CANRECURSE)) == 0) {
354                                 spin_unlock_wr(&lkp->lk_spinlock);
355                                 panic("lockmgr: locking against myself");
356                         }
357                         if ((extflags & LK_CANRECURSE) != 0) {
358                                 lkp->lk_exclusivecount++;
359                                 COUNT(td, 1);
360                                 break;
361                         }
362                 }
363                 /*
364                  * If we are just polling, check to see if we will sleep.
365                  */
366                 if ((extflags & LK_NOWAIT) &&
367                     (lkp->lk_flags & (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE | LK_SHARE_NONZERO))) {
368                         error = EBUSY;
369                         break;
370                 }
371                 /*
372                  * Try to acquire the want_exclusive flag.
373                  */
374                 error = acquire(lkp, extflags, (LK_HAVE_EXCL | LK_WANT_EXCL));
375                 if (error)
376                         break;
377                 lkp->lk_flags |= LK_WANT_EXCL;
378                 /*
379                  * Wait for shared locks and upgrades to finish.
380                  */
381                 error = acquire(lkp, extflags, LK_WANT_UPGRADE | LK_SHARE_NONZERO);
382                 lkp->lk_flags &= ~LK_WANT_EXCL;
383                 if (error)
384                         break;
385                 lkp->lk_flags |= LK_HAVE_EXCL;
386                 lkp->lk_lockholder = td;
387                 if (lkp->lk_exclusivecount != 0) {
388                         spin_unlock_wr(&lkp->lk_spinlock);
389                         panic("lockmgr: non-zero exclusive count");
390                 }
391                 lkp->lk_exclusivecount = 1;
392 #if defined(DEBUG_LOCKS)
393                         lkp->lk_filename = file;
394                         lkp->lk_lineno = line;
395                         lkp->lk_lockername = name;
396 #endif
397                 COUNT(td, 1);
398                 break;
399
400         case LK_RELEASE:
401                 if (lkp->lk_exclusivecount != 0) {
402                         if (lkp->lk_lockholder != td &&
403                             lkp->lk_lockholder != LK_KERNTHREAD) {
404                                 spin_unlock_wr(&lkp->lk_spinlock);
405                                 panic("lockmgr: pid %d, not %s thr %p/%p unlocking",
406                                     (td->td_proc ? td->td_proc->p_pid : -1),
407                                     "exclusive lock holder",
408                                     td, lkp->lk_lockholder);
409                         }
410                         if (lkp->lk_lockholder != LK_KERNTHREAD) {
411                                 COUNT(td, -1);
412                         }
413                         if (lkp->lk_exclusivecount == 1) {
414                                 lkp->lk_flags &= ~LK_HAVE_EXCL;
415                                 lkp->lk_lockholder = LK_NOTHREAD;
416                                 lkp->lk_exclusivecount = 0;
417                         } else {
418                                 lkp->lk_exclusivecount--;
419                         }
420                 } else if (lkp->lk_flags & LK_SHARE_NONZERO) {
421                         dowakeup += shareunlock(lkp, 1);
422                         COUNT(td, -1);
423                 }
424                 if (lkp->lk_flags & LK_WAIT_NONZERO)
425                         ++dowakeup;
426                 break;
427
428         default:
429                 spin_unlock_wr(&lkp->lk_spinlock);
430                 panic("lockmgr: unknown locktype request %d",
431                     flags & LK_TYPE_MASK);
432                 /* NOTREACHED */
433         }
434         spin_unlock_wr(&lkp->lk_spinlock);
435         if (dowakeup)
436                 wakeup(lkp);
437         return (error);
438 }
439
440 void
441 lockmgr_kernproc(struct lock *lp)
442 {
443         struct thread *td __debugvar = curthread;
444
445         if (lp->lk_lockholder != LK_KERNTHREAD) {
446                 KASSERT(lp->lk_lockholder == td, 
447                     ("lockmgr_kernproc: lock not owned by curthread %p", td));
448                 COUNT(td, -1);
449                 lp->lk_lockholder = LK_KERNTHREAD;
450         }
451 }
452
453 /*
454  * Set the lock to be exclusively held.  The caller is holding the lock's
455  * spinlock and the spinlock remains held on return.  A panic will occur
456  * if the lock cannot be set to exclusive.
457  */
458 void
459 lockmgr_setexclusive_interlocked(struct lock *lkp)
460 {
461         thread_t td = curthread;
462
463         KKASSERT((lkp->lk_flags & (LK_HAVE_EXCL|LK_SHARE_NONZERO)) == 0);
464         KKASSERT(lkp->lk_exclusivecount == 0);
465         lkp->lk_flags |= LK_HAVE_EXCL;
466         lkp->lk_lockholder = td;
467         lkp->lk_exclusivecount = 1;
468         COUNT(td, 1);
469 }
470
471 /*
472  * Clear the caller's exclusive lock.  The caller is holding the lock's
473  * spinlock.  THIS FUNCTION WILL UNLOCK THE SPINLOCK.
474  *
475  * A panic will occur if the caller does not hold the lock.
476  */
477 void
478 lockmgr_clrexclusive_interlocked(struct lock *lkp)
479 {
480         thread_t td __debugvar = curthread;
481         int dowakeup = 0;
482
483         KKASSERT((lkp->lk_flags & LK_HAVE_EXCL) && lkp->lk_exclusivecount == 1
484                  && lkp->lk_lockholder == td);
485         lkp->lk_lockholder = LK_NOTHREAD;
486         lkp->lk_flags &= ~LK_HAVE_EXCL;
487         lkp->lk_exclusivecount = 0;
488         if (lkp->lk_flags & LK_WAIT_NONZERO)
489                 dowakeup = 1;
490         COUNT(td, -1);
491         spin_unlock_wr(&lkp->lk_spinlock);
492         if (dowakeup)
493                 wakeup((void *)lkp);
494 }
495
496 /*
497  * Initialize a lock; required before use.
498  */
499 void
500 lockinit(struct lock *lkp, char *wmesg, int timo, int flags)
501 {
502         spin_init(&lkp->lk_spinlock);
503         lkp->lk_flags = (flags & LK_EXTFLG_MASK);
504         lkp->lk_sharecount = 0;
505         lkp->lk_waitcount = 0;
506         lkp->lk_exclusivecount = 0;
507         lkp->lk_wmesg = wmesg;
508         lkp->lk_timo = timo;
509         lkp->lk_lockholder = LK_NOTHREAD;
510 }
511
512 /*
513  * Reinitialize a lock that is being reused for a different purpose, but
514  * which may have pending (blocked) threads sitting on it.  The caller
515  * must already hold the interlock.
516  */
517 void
518 lockreinit(struct lock *lkp, char *wmesg, int timo, int flags)
519 {
520         spin_lock_wr(&lkp->lk_spinlock);
521         lkp->lk_flags = (lkp->lk_flags & ~LK_EXTFLG_MASK) |
522                         (flags & LK_EXTFLG_MASK);
523         lkp->lk_wmesg = wmesg;
524         lkp->lk_timo = timo;
525         spin_unlock_wr(&lkp->lk_spinlock);
526 }
527
528 /*
529  * Requires that the caller is the exclusive owner of this lock.
530  */
531 void
532 lockuninit(struct lock *l)
533 {
534         /*
535          * At this point we should have removed all the references to this lock
536          * so there can't be anyone waiting on it.
537          */
538         KKASSERT(l->lk_waitcount == 0);
539
540         spin_uninit(&l->lk_spinlock);
541 }
542
543 /*
544  * Determine the status of a lock.
545  */
546 int
547 lockstatus(struct lock *lkp, struct thread *td)
548 {
549         int lock_type = 0;
550
551         spin_lock_wr(&lkp->lk_spinlock);
552         if (lkp->lk_exclusivecount != 0) {
553                 if (td == NULL || lkp->lk_lockholder == td)
554                         lock_type = LK_EXCLUSIVE;
555                 else
556                         lock_type = LK_EXCLOTHER;
557         } else if (lkp->lk_sharecount != 0) {
558                 lock_type = LK_SHARED;
559         }
560         spin_unlock_wr(&lkp->lk_spinlock);
561         return (lock_type);
562 }
563
564 /*
565  * Determine the number of holders of a lock.
566  *
567  * The non-blocking version can usually be used for assertions.
568  */
569 int
570 lockcount(struct lock *lkp)
571 {
572         int count;
573
574         spin_lock_wr(&lkp->lk_spinlock);
575         count = lkp->lk_exclusivecount + lkp->lk_sharecount;
576         spin_unlock_wr(&lkp->lk_spinlock);
577         return (count);
578 }
579
580 int
581 lockcountnb(struct lock *lkp)
582 {
583         return (lkp->lk_exclusivecount + lkp->lk_sharecount);
584 }
585
586 /*
587  * Print out information about state of a lock. Used by VOP_PRINT
588  * routines to display status about contained locks.
589  */
590 void
591 lockmgr_printinfo(struct lock *lkp)
592 {
593         struct thread *td = lkp->lk_lockholder;
594         struct proc *p;
595
596         if (td && td != LK_KERNTHREAD && td != LK_NOTHREAD)
597                 p = td->td_proc;
598         else
599                 p = NULL;
600
601         if (lkp->lk_sharecount)
602                 kprintf(" lock type %s: SHARED (count %d)", lkp->lk_wmesg,
603                     lkp->lk_sharecount);
604         else if (lkp->lk_flags & LK_HAVE_EXCL)
605                 kprintf(" lock type %s: EXCL (count %d) by td %p pid %d",
606                     lkp->lk_wmesg, lkp->lk_exclusivecount, td,
607                     p ? p->p_pid : -99);
608         if (lkp->lk_waitcount > 0)
609                 kprintf(" with %d pending", lkp->lk_waitcount);
610 }
611