Misc interrupts/LWKT 1/2: interlock the idle thread. Put execution of
[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.3 2003/06/25 03:55:57 dillon Exp $
43  */
44
45 #include "opt_lint.h"
46
47 #include <sys/param.h>
48 #include <sys/proc.h>
49 #include <sys/lock.h>
50 #include <sys/systm.h>
51
52 /*
53  * Locking primitives implementation.
54  * Locks provide shared/exclusive sychronization.
55  */
56
57 #ifdef SIMPLELOCK_DEBUG
58 #define COUNT(td, x) (td)->td_locks += (x)
59 #else
60 #define COUNT(td, x)
61 #endif
62
63 #define LOCK_WAIT_TIME 100
64 #define LOCK_SAMPLE_WAIT 7
65
66 #if defined(DIAGNOSTIC)
67 #define LOCK_INLINE
68 #else
69 #define LOCK_INLINE __inline
70 #endif
71
72 #define LK_ALL (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE | \
73         LK_SHARE_NONZERO | LK_WAIT_NONZERO)
74
75 static int acquire(struct lock *lkp, int extflags, int wanted);
76 static int apause(struct lock *lkp, int flags);
77 static int acquiredrain(struct lock *lkp, int extflags) ;
78
79 static LOCK_INLINE void
80 sharelock(struct lock *lkp, int incr) {
81         lkp->lk_flags |= LK_SHARE_NONZERO;
82         lkp->lk_sharecount += incr;
83 }
84
85 static LOCK_INLINE void
86 shareunlock(struct lock *lkp, int decr) {
87
88         KASSERT(lkp->lk_sharecount >= decr, ("shareunlock: count < decr"));
89
90         if (lkp->lk_sharecount == decr) {
91                 lkp->lk_flags &= ~LK_SHARE_NONZERO;
92                 if (lkp->lk_flags & (LK_WANT_UPGRADE | LK_WANT_EXCL)) {
93                         wakeup(lkp);
94                 }
95                 lkp->lk_sharecount = 0;
96         } else {
97                 lkp->lk_sharecount -= decr;
98         }
99 }
100
101 /*
102  * This is the waitloop optimization, and note for this to work
103  * simple_lock and simple_unlock should be subroutines to avoid
104  * optimization troubles.
105  */
106 static int
107 apause(struct lock *lkp, int flags)
108 {
109 #ifdef SMP
110         int i, lock_wait;
111 #endif
112
113         if ((lkp->lk_flags & flags) == 0)
114                 return 0;
115 #ifdef SMP
116         for (lock_wait = LOCK_WAIT_TIME; lock_wait > 0; lock_wait--) {
117                 simple_unlock(&lkp->lk_interlock);
118                 for (i = LOCK_SAMPLE_WAIT; i > 0; i--)
119                         if ((lkp->lk_flags & flags) == 0)
120                                 break;
121                 simple_lock(&lkp->lk_interlock);
122                 if ((lkp->lk_flags & flags) == 0)
123                         return 0;
124         }
125 #endif
126         return 1;
127 }
128
129 static int
130 acquire(struct lock *lkp, int extflags, int wanted) {
131         int s, error;
132
133         if ((extflags & LK_NOWAIT) && (lkp->lk_flags & wanted)) {
134                 return EBUSY;
135         }
136
137         if (((lkp->lk_flags | extflags) & LK_NOPAUSE) == 0) {
138                 error = apause(lkp, wanted);
139                 if (error == 0)
140                         return 0;
141         }
142
143         s = splhigh();
144         while ((lkp->lk_flags & wanted) != 0) {
145                 lkp->lk_flags |= LK_WAIT_NONZERO;
146                 lkp->lk_waitcount++;
147                 simple_unlock(&lkp->lk_interlock);
148                 error = tsleep(lkp, lkp->lk_prio, lkp->lk_wmesg, 
149                             ((extflags & LK_TIMELOCK) ? lkp->lk_timo : 0));
150                 simple_lock(&lkp->lk_interlock);
151                 if (lkp->lk_waitcount == 1) {
152                         lkp->lk_flags &= ~LK_WAIT_NONZERO;
153                         lkp->lk_waitcount = 0;
154                 } else {
155                         lkp->lk_waitcount--;
156                 }
157                 if (error) {
158                         splx(s);
159                         return error;
160                 }
161                 if (extflags & LK_SLEEPFAIL) {
162                         splx(s);
163                         return ENOLCK;
164                 }
165         }
166         splx(s);
167         return 0;
168 }
169
170 /*
171  * Set, change, or release a lock.
172  *
173  * Shared requests increment the shared count. Exclusive requests set the
174  * LK_WANT_EXCL flag (preventing further shared locks), and wait for already
175  * accepted shared locks and shared-to-exclusive upgrades to go away.
176  */
177 int
178 #ifndef DEBUG_LOCKS
179 lockmgr(struct lock *lkp, u_int flags, struct simplelock *interlkp,
180         struct thread *td)
181 #else
182 debuglockmgr(struct lock *lkp, u_int flags, struct simplelock *interlkp,
183         struct thread *td, const char *name, const char *file, int line)
184 #endif
185 {
186         int error;
187         int extflags;
188
189         error = 0;
190
191         simple_lock(&lkp->lk_interlock);
192         if (flags & LK_INTERLOCK)
193                 simple_unlock(interlkp);
194
195         extflags = (flags | lkp->lk_flags) & LK_EXTFLG_MASK;
196
197         switch (flags & LK_TYPE_MASK) {
198
199         case LK_SHARED:
200                 /*
201                  * If we are not the exclusive lock holder, we have to block
202                  * while there is an exclusive lock holder or while an
203                  * exclusive lock request or upgrade request is in progress.
204                  *
205                  * However, if P_DEADLKTREAT is set, we override exclusive
206                  * lock requests or upgrade requests ( but not the exclusive
207                  * lock itself ).
208                  */
209                 if (lkp->lk_lockholder != td) {
210                         if (td->td_flags & TDF_DEADLKTREAT) {
211                                 error = acquire(
212                                             lkp,
213                                             extflags,
214                                             LK_HAVE_EXCL
215                                         );
216                         } else {
217                                 error = acquire(
218                                             lkp, 
219                                             extflags,
220                                             LK_HAVE_EXCL | LK_WANT_EXCL | 
221                                              LK_WANT_UPGRADE
222                                         );
223                         }
224                         if (error)
225                                 break;
226                         sharelock(lkp, 1);
227                         COUNT(p, 1);
228                         break;
229                 }
230                 /*
231                  * We hold an exclusive lock, so downgrade it to shared.
232                  * An alternative would be to fail with EDEADLK.
233                  */
234                 sharelock(lkp, 1);
235                 COUNT(p, 1);
236                 /* fall into downgrade */
237
238         case LK_DOWNGRADE:
239                 if (lkp->lk_lockholder != td || lkp->lk_exclusivecount == 0)
240                         panic("lockmgr: not holding exclusive lock");
241                 sharelock(lkp, lkp->lk_exclusivecount);
242                 lkp->lk_exclusivecount = 0;
243                 lkp->lk_flags &= ~LK_HAVE_EXCL;
244                 lkp->lk_lockholder = LK_NOTHREAD;
245                 if (lkp->lk_waitcount)
246                         wakeup((void *)lkp);
247                 break;
248
249         case LK_EXCLUPGRADE:
250                 /*
251                  * If another process is ahead of us to get an upgrade,
252                  * then we want to fail rather than have an intervening
253                  * exclusive access.
254                  */
255                 if (lkp->lk_flags & LK_WANT_UPGRADE) {
256                         shareunlock(lkp, 1);
257                         COUNT(p, -1);
258                         error = EBUSY;
259                         break;
260                 }
261                 /* fall into normal upgrade */
262
263         case LK_UPGRADE:
264                 /*
265                  * Upgrade a shared lock to an exclusive one. If another
266                  * shared lock has already requested an upgrade to an
267                  * exclusive lock, our shared lock is released and an
268                  * exclusive lock is requested (which will be granted
269                  * after the upgrade). If we return an error, the file
270                  * will always be unlocked.
271                  */
272                 if ((lkp->lk_lockholder == td) || (lkp->lk_sharecount <= 0))
273                         panic("lockmgr: upgrade exclusive lock");
274                 shareunlock(lkp, 1);
275                 COUNT(p, -1);
276                 /*
277                  * If we are just polling, check to see if we will block.
278                  */
279                 if ((extflags & LK_NOWAIT) &&
280                     ((lkp->lk_flags & LK_WANT_UPGRADE) ||
281                      lkp->lk_sharecount > 1)) {
282                         error = EBUSY;
283                         break;
284                 }
285                 if ((lkp->lk_flags & LK_WANT_UPGRADE) == 0) {
286                         /*
287                          * We are first shared lock to request an upgrade, so
288                          * request upgrade and wait for the shared count to
289                          * drop to zero, then take exclusive lock.
290                          */
291                         lkp->lk_flags |= LK_WANT_UPGRADE;
292                         error = acquire(lkp, extflags, LK_SHARE_NONZERO);
293                         lkp->lk_flags &= ~LK_WANT_UPGRADE;
294
295                         if (error)
296                                 break;
297                         lkp->lk_flags |= LK_HAVE_EXCL;
298                         lkp->lk_lockholder = td;
299                         if (lkp->lk_exclusivecount != 0)
300                                 panic("lockmgr: non-zero exclusive count");
301                         lkp->lk_exclusivecount = 1;
302 #if defined(DEBUG_LOCKS)
303                         lkp->lk_filename = file;
304                         lkp->lk_lineno = line;
305                         lkp->lk_lockername = name;
306 #endif
307                         COUNT(p, 1);
308                         break;
309                 }
310                 /*
311                  * Someone else has requested upgrade. Release our shared
312                  * lock, awaken upgrade requestor if we are the last shared
313                  * lock, then request an exclusive lock.
314                  */
315                 if ( (lkp->lk_flags & (LK_SHARE_NONZERO|LK_WAIT_NONZERO)) ==
316                         LK_WAIT_NONZERO)
317                         wakeup((void *)lkp);
318                 /* fall into exclusive request */
319
320         case LK_EXCLUSIVE:
321                 if (lkp->lk_lockholder == td && td != LK_KERNTHREAD) {
322                         /*
323                          *      Recursive lock.
324                          */
325                         if ((extflags & (LK_NOWAIT | LK_CANRECURSE)) == 0)
326                                 panic("lockmgr: locking against myself");
327                         if ((extflags & LK_CANRECURSE) != 0) {
328                                 lkp->lk_exclusivecount++;
329                                 COUNT(p, 1);
330                                 break;
331                         }
332                 }
333                 /*
334                  * If we are just polling, check to see if we will sleep.
335                  */
336                 if ((extflags & LK_NOWAIT) &&
337                     (lkp->lk_flags & (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE | LK_SHARE_NONZERO))) {
338                         error = EBUSY;
339                         break;
340                 }
341                 /*
342                  * Try to acquire the want_exclusive flag.
343                  */
344                 error = acquire(lkp, extflags, (LK_HAVE_EXCL | LK_WANT_EXCL));
345                 if (error)
346                         break;
347                 lkp->lk_flags |= LK_WANT_EXCL;
348                 /*
349                  * Wait for shared locks and upgrades to finish.
350                  */
351                 error = acquire(lkp, extflags, LK_WANT_UPGRADE | LK_SHARE_NONZERO);
352                 lkp->lk_flags &= ~LK_WANT_EXCL;
353                 if (error)
354                         break;
355                 lkp->lk_flags |= LK_HAVE_EXCL;
356                 lkp->lk_lockholder = td;
357                 if (lkp->lk_exclusivecount != 0)
358                         panic("lockmgr: non-zero exclusive count");
359                 lkp->lk_exclusivecount = 1;
360 #if defined(DEBUG_LOCKS)
361                         lkp->lk_filename = file;
362                         lkp->lk_lineno = line;
363                         lkp->lk_lockername = name;
364 #endif
365                 COUNT(p, 1);
366                 break;
367
368         case LK_RELEASE:
369                 if (lkp->lk_exclusivecount != 0) {
370                         if (lkp->lk_lockholder != td &&
371                             lkp->lk_lockholder != LK_KERNTHREAD) {
372                                 panic("lockmgr: pid %d, not %s thr %p unlocking",
373                                     (td->td_proc ? td->td_proc->p_pid : -99),
374                                     "exclusive lock holder",
375                                     lkp->lk_lockholder);
376                         }
377                         if (lkp->lk_lockholder != LK_KERNTHREAD) {
378                                 COUNT(p, -1);
379                         }
380                         if (lkp->lk_exclusivecount == 1) {
381                                 lkp->lk_flags &= ~LK_HAVE_EXCL;
382                                 lkp->lk_lockholder = LK_NOTHREAD;
383                                 lkp->lk_exclusivecount = 0;
384                         } else {
385                                 lkp->lk_exclusivecount--;
386                         }
387                 } else if (lkp->lk_flags & LK_SHARE_NONZERO) {
388                         shareunlock(lkp, 1);
389                         COUNT(p, -1);
390                 }
391                 if (lkp->lk_flags & LK_WAIT_NONZERO)
392                         wakeup((void *)lkp);
393                 break;
394
395         case LK_DRAIN:
396                 /*
397                  * Check that we do not already hold the lock, as it can 
398                  * never drain if we do. Unfortunately, we have no way to
399                  * check for holding a shared lock, but at least we can
400                  * check for an exclusive one.
401                  */
402                 if (lkp->lk_lockholder == td)
403                         panic("lockmgr: draining against myself");
404
405                 error = acquiredrain(lkp, extflags);
406                 if (error)
407                         break;
408                 lkp->lk_flags |= LK_DRAINING | LK_HAVE_EXCL;
409                 lkp->lk_lockholder = td;
410                 lkp->lk_exclusivecount = 1;
411 #if defined(DEBUG_LOCKS)
412                         lkp->lk_filename = file;
413                         lkp->lk_lineno = line;
414                         lkp->lk_lockername = name;
415 #endif
416                 COUNT(p, 1);
417                 break;
418
419         default:
420                 simple_unlock(&lkp->lk_interlock);
421                 panic("lockmgr: unknown locktype request %d",
422                     flags & LK_TYPE_MASK);
423                 /* NOTREACHED */
424         }
425         if ((lkp->lk_flags & LK_WAITDRAIN) &&
426             (lkp->lk_flags & (LK_HAVE_EXCL | LK_WANT_EXCL | LK_WANT_UPGRADE |
427                 LK_SHARE_NONZERO | LK_WAIT_NONZERO)) == 0) {
428                 lkp->lk_flags &= ~LK_WAITDRAIN;
429                 wakeup((void *)&lkp->lk_flags);
430         }
431         simple_unlock(&lkp->lk_interlock);
432         return (error);
433 }
434
435 static int
436 acquiredrain(struct lock *lkp, int extflags) {
437         int error;
438
439         if ((extflags & LK_NOWAIT) && (lkp->lk_flags & LK_ALL)) {
440                 return EBUSY;
441         }
442
443         error = apause(lkp, LK_ALL);
444         if (error == 0)
445                 return 0;
446
447         while (lkp->lk_flags & LK_ALL) {
448                 lkp->lk_flags |= LK_WAITDRAIN;
449                 simple_unlock(&lkp->lk_interlock);
450                 error = tsleep(&lkp->lk_flags, lkp->lk_prio,
451                         lkp->lk_wmesg, 
452                         ((extflags & LK_TIMELOCK) ? lkp->lk_timo : 0));
453                 simple_lock(&lkp->lk_interlock);
454                 if (error)
455                         return error;
456                 if (extflags & LK_SLEEPFAIL) {
457                         return ENOLCK;
458                 }
459         }
460         return 0;
461 }
462
463 /*
464  * Initialize a lock; required before use.
465  */
466 void
467 lockinit(lkp, prio, wmesg, timo, flags)
468         struct lock *lkp;
469         int prio;
470         char *wmesg;
471         int timo;
472         int flags;
473 {
474
475         simple_lock_init(&lkp->lk_interlock);
476         lkp->lk_flags = (flags & LK_EXTFLG_MASK);
477         lkp->lk_sharecount = 0;
478         lkp->lk_waitcount = 0;
479         lkp->lk_exclusivecount = 0;
480         lkp->lk_prio = prio;
481         lkp->lk_wmesg = wmesg;
482         lkp->lk_timo = timo;
483         lkp->lk_lockholder = LK_NOTHREAD;
484 }
485
486 /*
487  * Determine the status of a lock.
488  */
489 int
490 lockstatus(struct lock *lkp, struct thread *td)
491 {
492         int lock_type = 0;
493
494         simple_lock(&lkp->lk_interlock);
495         if (lkp->lk_exclusivecount != 0) {
496                 if (td == NULL || lkp->lk_lockholder == td)
497                         lock_type = LK_EXCLUSIVE;
498                 else
499                         lock_type = LK_EXCLOTHER;
500         } else if (lkp->lk_sharecount != 0)
501                 lock_type = LK_SHARED;
502         simple_unlock(&lkp->lk_interlock);
503         return (lock_type);
504 }
505
506 /*
507  * Determine the number of holders of a lock.
508  */
509 int
510 lockcount(lkp)
511         struct lock *lkp;
512 {
513         int count;
514
515         simple_lock(&lkp->lk_interlock);
516         count = lkp->lk_exclusivecount + lkp->lk_sharecount;
517         simple_unlock(&lkp->lk_interlock);
518         return (count);
519 }
520
521 /*
522  * Print out information about state of a lock. Used by VOP_PRINT
523  * routines to display status about contained locks.
524  */
525 void
526 lockmgr_printinfo(lkp)
527         struct lock *lkp;
528 {
529         struct thread *td = lkp->lk_lockholder;
530         struct proc *p;
531
532         if (td && td != LK_KERNTHREAD && td != LK_NOTHREAD)
533                 p = td->td_proc;
534         else
535                 p = NULL;
536
537         if (lkp->lk_sharecount)
538                 printf(" lock type %s: SHARED (count %d)", lkp->lk_wmesg,
539                     lkp->lk_sharecount);
540         else if (lkp->lk_flags & LK_HAVE_EXCL)
541                 printf(" lock type %s: EXCL (count %d) by td %p pid %d",
542                     lkp->lk_wmesg, lkp->lk_exclusivecount, td,
543                     p ? p->p_pid : -99);
544         if (lkp->lk_waitcount > 0)
545                 printf(" with %d pending", lkp->lk_waitcount);
546 }
547
548 #if defined(SIMPLELOCK_DEBUG) && (MAXCPU == 1 || defined(COMPILING_LINT))
549 #include <sys/kernel.h>
550 #include <sys/sysctl.h>
551
552 static int lockpausetime = 0;
553 SYSCTL_INT(_debug, OID_AUTO, lockpausetime, CTLFLAG_RW, &lockpausetime, 0, "");
554
555 static int simplelockrecurse;
556
557 /*
558  * Simple lock functions so that the debugger can see from whence
559  * they are being called.
560  */
561 void
562 simple_lock_init(alp)
563         struct simplelock *alp;
564 {
565
566         alp->lock_data = 0;
567 }
568
569 void
570 _simple_lock(alp, id, l)
571         struct simplelock *alp;
572         const char *id;
573         int l;
574 {
575
576         if (simplelockrecurse)
577                 return;
578         if (alp->lock_data == 1) {
579                 if (lockpausetime == -1)
580                         panic("%s:%d: simple_lock: lock held", id, l);
581                 printf("%s:%d: simple_lock: lock held\n", id, l);
582                 if (lockpausetime == 1) {
583                         Debugger("simple_lock");
584                         /*BACKTRACE(curproc); */
585                 } else if (lockpausetime > 1) {
586                         printf("%s:%d: simple_lock: lock held...", id, l);
587                         tsleep(&lockpausetime, PCATCH | PPAUSE, "slock",
588                             lockpausetime * hz);
589                         printf(" continuing\n");
590                 }
591         }
592         alp->lock_data = 1;
593         if (curproc)
594                 curproc->p_simple_locks++;
595 }
596
597 int
598 _simple_lock_try(alp, id, l)
599         struct simplelock *alp;
600         const char *id;
601         int l;
602 {
603
604         if (alp->lock_data)
605                 return (0);
606         if (simplelockrecurse)
607                 return (1);
608         alp->lock_data = 1;
609         if (curproc)
610                 curproc->p_simple_locks++;
611         return (1);
612 }
613
614 void
615 _simple_unlock(alp, id, l)
616         struct simplelock *alp;
617         const char *id;
618         int l;
619 {
620
621         if (simplelockrecurse)
622                 return;
623         if (alp->lock_data == 0) {
624                 if (lockpausetime == -1)
625                         panic("%s:%d: simple_unlock: lock not held", id, l);
626                 printf("%s:%d: simple_unlock: lock not held\n", id, l);
627                 if (lockpausetime == 1) {
628                         Debugger("simple_unlock");
629                         /* BACKTRACE(curproc); */
630                 } else if (lockpausetime > 1) {
631                         printf("%s:%d: simple_unlock: lock not held...", id, l);
632                         tsleep(&lockpausetime, PCATCH | PPAUSE, "sunlock",
633                             lockpausetime * hz);
634                         printf(" continuing\n");
635                 }
636         }
637         alp->lock_data = 0;
638         if (curproc)
639                 curproc->p_simple_locks--;
640 }
641 #elif defined(SIMPLELOCK_DEBUG)
642 #error "SIMPLELOCK_DEBUG is not compatible with SMP!"
643 #endif /* SIMPLELOCK_DEBUG && MAXCPU == 1 */