148fd23c3012f4a29b34e09b23947d529ad601b7
[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.16 2006/03/02 19:07:59 dillon 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 static int acquiredrain(struct lock *lkp, int extflags) ;
88
89 static LOCK_INLINE void
90 sharelock(struct lock *lkp, int incr) {
91         lkp->lk_flags |= LK_SHARE_NONZERO;
92         lkp->lk_sharecount += incr;
93 }
94
95 static LOCK_INLINE void
96 shareunlock(struct lock *lkp, int decr) {
97
98         KASSERT(lkp->lk_sharecount >= decr, ("shareunlock: count < decr"));
99
100         if (lkp->lk_sharecount == decr) {
101                 lkp->lk_flags &= ~LK_SHARE_NONZERO;
102                 if (lkp->lk_flags & (LK_WANT_UPGRADE | LK_WANT_EXCL)) {
103                         wakeup(lkp);
104                 }
105                 lkp->lk_sharecount = 0;
106         } else {
107                 lkp->lk_sharecount -= decr;
108         }
109 }
110
111 /*
112  * lock acquisition helper routine.  Called with the lock's spinlock held.
113  */
114 static int
115 acquire(struct lock *lkp, int extflags, int wanted) 
116 {
117         int error;
118
119         if ((extflags & LK_NOWAIT) && (lkp->lk_flags & wanted)) {
120                 return EBUSY;
121         }
122
123         if (((lkp->lk_flags | extflags) & LK_NOPAUSE) == 0) {
124                 if ((lkp->lk_flags & wanted) == 0)
125                         return 0;
126         }
127
128         while ((lkp->lk_flags & wanted) != 0) {
129                 lkp->lk_flags |= LK_WAIT_NONZERO;
130                 lkp->lk_waitcount++;
131
132                 /*
133                  * Use the _quick version so the critical section is left
134                  * intact, protecting the tsleep interlock.  See 
135                  * tsleep_interlock() for a description of what is
136                  * happening here.
137                  */
138                 tsleep_interlock(lkp);
139                 spin_unlock_quick(&lkp->lk_spinlock);
140                 error = tsleep(lkp, 
141                                ((extflags & LK_PCATCH) ? PCATCH : 0),
142                                lkp->lk_wmesg, 
143                                ((extflags & LK_TIMELOCK) ? lkp->lk_timo : 0));
144                 spin_lock_quick(&lkp->lk_spinlock);
145                 if (lkp->lk_waitcount == 1) {
146                         lkp->lk_flags &= ~LK_WAIT_NONZERO;
147                         lkp->lk_waitcount = 0;
148                 } else {
149                         lkp->lk_waitcount--;
150                 }
151                 if (error)
152                         return error;
153                 if (extflags & LK_SLEEPFAIL)
154                         return ENOLCK;
155         }
156         return 0;
157 }
158
159 /*
160  * Set, change, or release a lock.
161  *
162  * Shared requests increment the shared count. Exclusive requests set the
163  * LK_WANT_EXCL flag (preventing further shared locks), and wait for already
164  * accepted shared locks and shared-to-exclusive upgrades to go away.
165  *
166  * A spinlock is held for most of the procedure.  We must not do anything
167  * fancy while holding the spinlock.
168  */
169 int
170 #ifndef DEBUG_LOCKS
171 lockmgr(struct lock *lkp, u_int flags, struct spinlock *interlkp,
172         struct thread *td)
173 #else
174 debuglockmgr(struct lock *lkp, u_int flags, struct spinlock *interlkp,
175         struct thread *td, const char *name, const char *file, int line)
176 #endif
177 {
178         int error;
179         int extflags;
180         static int didpanic;
181
182         error = 0;
183
184         if (lockmgr_from_int && mycpu->gd_intr_nesting_level &&
185             (flags & LK_NOWAIT) == 0 &&
186             (flags & LK_TYPE_MASK) != LK_RELEASE && didpanic == 0) {
187 #ifndef DEBUG_LOCKS
188                     if (lockmgr_from_int == 2) {
189                             didpanic = 1;
190                             if (flags & LK_INTERLOCK)
191                                     spin_unlock(interlkp);
192                             panic(
193                                 "lockmgr %s from %p: called from interrupt",
194                                 lkp->lk_wmesg, ((int **)&lkp)[-1]);
195                             didpanic = 0;
196                     } else {
197                             printf(
198                                 "lockmgr %s from %p: called from interrupt\n",
199                                 lkp->lk_wmesg, ((int **)&lkp)[-1]);
200                     }
201 #else
202                     if (lockmgr_from_int == 2) {
203                             didpanic = 1;
204                             if (flags & LK_INTERLOCK)
205                                     spin_unlock(interlkp);
206                             panic(
207                                 "lockmgr %s from %s:%d: called from interrupt",
208                                 lkp->lk_wmesg, file, line);
209                             didpanic = 0;
210                     } else {
211                             printf(
212                                 "lockmgr %s from %s:%d: called from interrupt\n",
213                                 lkp->lk_wmesg, file, line);
214                     }
215 #endif
216         }
217
218         spin_lock(&lkp->lk_spinlock);
219         if (flags & LK_INTERLOCK)
220                 spin_unlock(interlkp);
221
222         extflags = (flags | lkp->lk_flags) & LK_EXTFLG_MASK;
223
224         switch (flags & LK_TYPE_MASK) {
225         case LK_SHARED:
226                 /*
227                  * If we are not the exclusive lock holder, we have to block
228                  * while there is an exclusive lock holder or while an
229                  * exclusive lock request or upgrade request is in progress.
230                  *
231                  * However, if P_DEADLKTREAT is set, we override exclusive
232                  * lock requests or upgrade requests ( but not the exclusive
233                  * lock itself ).
234                  */
235                 if (lkp->lk_lockholder != td) {
236                         if (td->td_flags & TDF_DEADLKTREAT) {
237                                 error = acquire(
238                                             lkp,
239                                             extflags,
240                                             LK_HAVE_EXCL
241                                         );
242                         } else {
243                                 error = acquire(
244                                             lkp, 
245                                             extflags,
246                                             LK_HAVE_EXCL | LK_WANT_EXCL | 
247                                              LK_WANT_UPGRADE
248                                         );
249                         }
250                         if (error)
251                                 break;
252                         sharelock(lkp, 1);
253                         COUNT(td, 1);
254                         break;
255                 }
256                 /*
257                  * We hold an exclusive lock, so downgrade it to shared.
258                  * An alternative would be to fail with EDEADLK.
259                  */
260                 sharelock(lkp, 1);
261                 COUNT(td, 1);
262                 /* fall into downgrade */
263
264         case LK_DOWNGRADE:
265                 if (lkp->lk_lockholder != td || lkp->lk_exclusivecount == 0) {
266                         spin_unlock(&lkp->lk_spinlock);
267                         panic("lockmgr: not holding exclusive lock");
268                 }
269                 sharelock(lkp, lkp->lk_exclusivecount);
270                 lkp->lk_exclusivecount = 0;
271                 lkp->lk_flags &= ~LK_HAVE_EXCL;
272                 lkp->lk_lockholder = LK_NOTHREAD;
273                 if (lkp->lk_waitcount)
274                         wakeup((void *)lkp);
275                 break;
276
277         case LK_EXCLUPGRADE:
278                 /*
279                  * If another process is ahead of us to get an upgrade,
280                  * then we want to fail rather than have an intervening
281                  * exclusive access.
282                  */
283                 if (lkp->lk_flags & LK_WANT_UPGRADE) {
284                         shareunlock(lkp, 1);
285                         COUNT(td, -1);
286                         error = EBUSY;
287                         break;
288                 }
289                 /* fall into normal upgrade */
290
291         case LK_UPGRADE:
292                 /*
293                  * Upgrade a shared lock to an exclusive one. If another
294                  * shared lock has already requested an upgrade to an
295                  * exclusive lock, our shared lock is released and an
296                  * exclusive lock is requested (which will be granted
297                  * after the upgrade). If we return an error, the file
298                  * will always be unlocked.
299                  */
300                 if ((lkp->lk_lockholder == td) || (lkp->lk_sharecount <= 0)) {
301                         spin_unlock(&lkp->lk_spinlock);
302                         panic("lockmgr: upgrade exclusive lock");
303                 }
304                 shareunlock(lkp, 1);
305                 COUNT(td, -1);
306                 /*
307                  * If we are just polling, check to see if we will block.
308                  */
309                 if ((extflags & LK_NOWAIT) &&
310                     ((lkp->lk_flags & LK_WANT_UPGRADE) ||
311                      lkp->lk_sharecount > 1)) {
312                         error = EBUSY;
313                         break;
314                 }
315                 if ((lkp->lk_flags & LK_WANT_UPGRADE) == 0) {
316                         /*
317                          * We are first shared lock to request an upgrade, so
318                          * request upgrade and wait for the shared count to
319                          * drop to zero, then take exclusive lock.
320                          */
321                         lkp->lk_flags |= LK_WANT_UPGRADE;
322                         error = acquire(lkp, extflags, LK_SHARE_NONZERO);
323                         lkp->lk_flags &= ~LK_WANT_UPGRADE;
324
325                         if (error)
326                                 break;
327                         lkp->lk_flags |= LK_HAVE_EXCL;
328                         lkp->lk_lockholder = td;
329                         if (lkp->lk_exclusivecount != 0) {
330                                 spin_unlock(&lkp->lk_spinlock);
331                                 panic("lockmgr: non-zero exclusive count");
332                         }
333                         lkp->lk_exclusivecount = 1;
334 #if defined(DEBUG_LOCKS)
335                         lkp->lk_filename = file;
336                         lkp->lk_lineno = line;
337                         lkp->lk_lockername = name;
338 #endif
339                         COUNT(td, 1);
340                         break;
341                 }
342                 /*
343                  * Someone else has requested upgrade. Release our shared
344                  * lock, awaken upgrade requestor if we are the last shared
345                  * lock, then request an exclusive lock.
346                  */
347                 if ( (lkp->lk_flags & (LK_SHARE_NONZERO|LK_WAIT_NONZERO)) ==
348                         LK_WAIT_NONZERO)
349                         wakeup((void *)lkp);
350                 /* fall into exclusive request */
351
352         case LK_EXCLUSIVE:
353                 if (lkp->lk_lockholder == td && td != LK_KERNTHREAD) {
354                         /*
355                          *      Recursive lock.
356                          */
357                         if ((extflags & (LK_NOWAIT | LK_CANRECURSE)) == 0) {
358                                 spin_unlock(&lkp->lk_spinlock);
359                                 panic("lockmgr: locking against myself");
360                         }
361                         if ((extflags & LK_CANRECURSE) != 0) {
362                                 lkp->lk_exclusivecount++;
363                                 COUNT(td, 1);
364                                 break;
365                         }
366                 }
367                 /*
368                  * If we are just polling, check to see if we will sleep.
369                  */
370                 if ((extflags & LK_NOWAIT) &&
371                     (lkp->lk_flags & (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE | LK_SHARE_NONZERO))) {
372                         error = EBUSY;
373                         break;
374                 }
375                 /*
376                  * Try to acquire the want_exclusive flag.
377                  */
378                 error = acquire(lkp, extflags, (LK_HAVE_EXCL | LK_WANT_EXCL));
379                 if (error)
380                         break;
381                 lkp->lk_flags |= LK_WANT_EXCL;
382                 /*
383                  * Wait for shared locks and upgrades to finish.
384                  */
385                 error = acquire(lkp, extflags, LK_WANT_UPGRADE | LK_SHARE_NONZERO);
386                 lkp->lk_flags &= ~LK_WANT_EXCL;
387                 if (error)
388                         break;
389                 lkp->lk_flags |= LK_HAVE_EXCL;
390                 lkp->lk_lockholder = td;
391                 if (lkp->lk_exclusivecount != 0) {
392                         spin_unlock(&lkp->lk_spinlock);
393                         panic("lockmgr: non-zero exclusive count");
394                 }
395                 lkp->lk_exclusivecount = 1;
396 #if defined(DEBUG_LOCKS)
397                         lkp->lk_filename = file;
398                         lkp->lk_lineno = line;
399                         lkp->lk_lockername = name;
400 #endif
401                 COUNT(td, 1);
402                 break;
403
404         case LK_RELEASE:
405                 if (lkp->lk_exclusivecount != 0) {
406                         if (lkp->lk_lockholder != td &&
407                             lkp->lk_lockholder != LK_KERNTHREAD) {
408                                 spin_unlock(&lkp->lk_spinlock);
409                                 panic("lockmgr: pid %d, not %s thr %p unlocking",
410                                     (td->td_proc ? td->td_proc->p_pid : -99),
411                                     "exclusive lock holder",
412                                     lkp->lk_lockholder);
413                         }
414                         if (lkp->lk_lockholder != LK_KERNTHREAD) {
415                                 COUNT(td, -1);
416                         }
417                         if (lkp->lk_exclusivecount == 1) {
418                                 lkp->lk_flags &= ~LK_HAVE_EXCL;
419                                 lkp->lk_lockholder = LK_NOTHREAD;
420                                 lkp->lk_exclusivecount = 0;
421                         } else {
422                                 lkp->lk_exclusivecount--;
423                         }
424                 } else if (lkp->lk_flags & LK_SHARE_NONZERO) {
425                         shareunlock(lkp, 1);
426                         COUNT(td, -1);
427                 }
428                 if (lkp->lk_flags & LK_WAIT_NONZERO)
429                         wakeup((void *)lkp);
430                 break;
431
432         case LK_DRAIN:
433                 /*
434                  * Check that we do not already hold the lock, as it can 
435                  * never drain if we do. Unfortunately, we have no way to
436                  * check for holding a shared lock, but at least we can
437                  * check for an exclusive one.
438                  */
439                 if (lkp->lk_lockholder == td) {
440                         spin_unlock(&lkp->lk_spinlock);
441                         panic("lockmgr: draining against myself");
442                 }
443
444                 error = acquiredrain(lkp, extflags);
445                 if (error)
446                         break;
447                 lkp->lk_flags |= LK_DRAINING | LK_HAVE_EXCL;
448                 lkp->lk_lockholder = td;
449                 lkp->lk_exclusivecount = 1;
450 #if defined(DEBUG_LOCKS)
451                         lkp->lk_filename = file;
452                         lkp->lk_lineno = line;
453                         lkp->lk_lockername = name;
454 #endif
455                 COUNT(td, 1);
456                 break;
457
458         default:
459                 spin_unlock(&lkp->lk_spinlock);
460                 panic("lockmgr: unknown locktype request %d",
461                     flags & LK_TYPE_MASK);
462                 /* NOTREACHED */
463         }
464         if ((lkp->lk_flags & LK_WAITDRAIN) &&
465             (lkp->lk_flags & (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE |
466                 LK_SHARE_NONZERO | LK_WAIT_NONZERO)) == 0) {
467                 lkp->lk_flags &= ~LK_WAITDRAIN;
468                 wakeup((void *)&lkp->lk_flags);
469         }
470         spin_unlock(&lkp->lk_spinlock);
471         return (error);
472 }
473
474 /*
475  * lock acquisition helper routine.  Called with the lock's spinlock held.
476  */
477 static int
478 acquiredrain(struct lock *lkp, int extflags)
479 {
480         int error;
481
482         if ((extflags & LK_NOWAIT) && (lkp->lk_flags & LK_ALL)) {
483                 return EBUSY;
484         }
485
486         if ((lkp->lk_flags & LK_ALL) == 0)
487                 return 0;
488
489         while (lkp->lk_flags & LK_ALL) {
490                 lkp->lk_flags |= LK_WAITDRAIN;
491                 /*
492                  * Use the _quick version so the critical section is left
493                  * intact, protecting the tsleep interlock.  See 
494                  * tsleep_interlock() for a description of what is
495                  * happening here.
496                  */
497                 tsleep_interlock(&lkp->lk_flags);
498                 spin_unlock_quick(&lkp->lk_spinlock);
499                 error = tsleep(&lkp->lk_flags,
500                                ((extflags & LK_PCATCH) ? PCATCH : 0),
501                                lkp->lk_wmesg, 
502                                ((extflags & LK_TIMELOCK) ? lkp->lk_timo : 0));
503                 spin_lock_quick(&lkp->lk_spinlock);
504                 if (error)
505                         return error;
506                 if (extflags & LK_SLEEPFAIL) {
507                         return ENOLCK;
508                 }
509         }
510         return 0;
511 }
512
513 /*
514  * Initialize a lock; required before use.
515  */
516 void
517 lockinit(struct lock *lkp, char *wmesg, int timo, int flags)
518 {
519         spin_init(&lkp->lk_spinlock);
520         lkp->lk_flags = (flags & LK_EXTFLG_MASK);
521         lkp->lk_sharecount = 0;
522         lkp->lk_waitcount = 0;
523         lkp->lk_exclusivecount = 0;
524         lkp->lk_wmesg = wmesg;
525         lkp->lk_timo = timo;
526         lkp->lk_lockholder = LK_NOTHREAD;
527 }
528
529 /*
530  * Reinitialize a lock that is being reused for a different purpose, but
531  * which may have pending (blocked) threads sitting on it.  The caller
532  * must already hold the interlock.
533  */
534 void
535 lockreinit(struct lock *lkp, char *wmesg, int timo, int flags)
536 {
537         lkp->lk_flags = (lkp->lk_flags & ~(LK_EXTFLG_MASK|LK_DRAINING)) |
538                         (flags & LK_EXTFLG_MASK);
539         lkp->lk_wmesg = wmesg;
540         lkp->lk_timo = timo;
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(&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(&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(&lkp->lk_spinlock);
575         count = lkp->lk_exclusivecount + lkp->lk_sharecount;
576         spin_unlock(&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                 printf(" lock type %s: SHARED (count %d)", lkp->lk_wmesg,
603                     lkp->lk_sharecount);
604         else if (lkp->lk_flags & LK_HAVE_EXCL)
605                 printf(" 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                 printf(" with %d pending", lkp->lk_waitcount);
610 }
611