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