sys/kern/kern_condvar.c

   1 /*      $NetBSD: kern_condvar.c,v 1.27 2009/10/21 21:12:06 rmind Exp $  */
   2
   3 /*-
   4  * Copyright (c) 2006, 2007, 2008 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Andrew Doran.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31
  32 /*
  33  * Kernel condition variable implementation.
  34  */
  35
  36 #include <sys/cdefs.h>
  37 __KERNEL_RCSID(0, "$NetBSD: kern_condvar.c,v 1.27 2009/10/21 21:12:06 rmind Exp $");
  38
  39 #include <sys/param.h>
  40 #include <sys/proc.h>
  41 #include <sys/sched.h>
  42 #include <sys/systm.h>
  43 #include <sys/condvar.h>
  44 #include <sys/sleepq.h>
  45 #include <sys/lockdebug.h>
  46 #include <sys/cpu.h>
  47
  48 #include <uvm/uvm_extern.h>
  49
  50 /*
  51  * Accessors for the private contents of the kcondvar_t data type.
  52  *
  53  *      cv_opaque[0]    sleepq...
  54  *      cv_opaque[1]    ...pointers
  55  *      cv_opaque[2]    description for ps(1)
  56  *
  57  * cv_opaque[0..1] is protected by the interlock passed to cv_wait() (enqueue
  58  * only), and the sleep queue lock acquired with sleeptab_lookup() (enqueue
  59  * and dequeue).
  60  *
  61  * cv_opaque[2] (the wmesg) is static and does not change throughout the life
  62  * of the CV.
  63  */
  64 #define CV_SLEEPQ(cv)           ((sleepq_t *)(cv)->cv_opaque)
  65 #define CV_WMESG(cv)            ((const char *)(cv)->cv_opaque[2])
  66 #define CV_SET_WMESG(cv, v)     (cv)->cv_opaque[2] = __UNCONST(v)
  67
  68 #define CV_DEBUG_P(cv)  (CV_WMESG(cv) != nodebug)
  69 #define CV_RA           ((uintptr_t)__builtin_return_address(0))
  70
  71 static void     cv_unsleep(lwp_t *, bool);
  72 static void     cv_wakeup_one(kcondvar_t *);
  73 static void     cv_wakeup_all(kcondvar_t *);
  74
  75 static syncobj_t cv_syncobj = {
  76         SOBJ_SLEEPQ_SORTED,
  77         cv_unsleep,
  78         sleepq_changepri,
  79         sleepq_lendpri,
  80         syncobj_noowner,
  81 };
  82
  83 lockops_t cv_lockops = {
  84         "Condition variable",
  85         LOCKOPS_CV,
  86         NULL
  87 };
  88
  89 static const char deadcv[] = "deadcv";
  90 static const char nodebug[] = "nodebug";
  91
  92 /*
  93  * cv_init:
  94  *
  95  *      Initialize a condition variable for use.
  96  */
  97 void
  98 cv_init(kcondvar_t *cv, const char *wmesg)
  99 {
 100 #ifdef LOCKDEBUG
 101         bool dodebug;
 102
 103         dodebug = LOCKDEBUG_ALLOC(cv, &cv_lockops,
 104             (uintptr_t)__builtin_return_address(0));
 105         if (!dodebug) {
 106                 /* XXX This will break vfs_lockf. */
 107                 wmesg = nodebug;
 108         }
 109 #endif
 110         KASSERT(wmesg != NULL);
 111         CV_SET_WMESG(cv, wmesg);
 112         sleepq_init(CV_SLEEPQ(cv));
 113 }
 114
 115 /*
 116  * cv_destroy:
 117  *
 118  *      Tear down a condition variable.
 119  */
 120 void
 121 cv_destroy(kcondvar_t *cv)
 122 {
 123
 124         LOCKDEBUG_FREE(CV_DEBUG_P(cv), cv);
 125 #ifdef DIAGNOSTIC
 126         KASSERT(cv_is_valid(cv));
 127         CV_SET_WMESG(cv, deadcv);
 128 #endif
 129 }
 130
 131 /*
 132  * cv_enter:
 133  *
 134  *      Look up and lock the sleep queue corresponding to the given
 135  *      condition variable, and increment the number of waiters.
 136  */
 137 static inline void
 138 cv_enter(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l)
 139 {
 140         sleepq_t *sq;
 141         kmutex_t *mp;
 142
 143         KASSERT(cv_is_valid(cv));
 144         KASSERT(!cpu_intr_p());
 145         KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL);
 146
 147         LOCKDEBUG_LOCKED(CV_DEBUG_P(cv), cv, mtx, CV_RA, 0);
 148
 149         l->l_kpriority = true;
 150         mp = sleepq_hashlock(cv);
 151         sq = CV_SLEEPQ(cv);
 152         sleepq_enter(sq, l, mp);
 153         sleepq_enqueue(sq, cv, CV_WMESG(cv), &cv_syncobj);
 154         mutex_exit(mtx);
 155         KASSERT(cv_has_waiters(cv));
 156 }
 157
 158 /*
 159  * cv_exit:
 160  *
 161  *      After resuming execution, check to see if we have been restarted
 162  *      as a result of cv_signal().  If we have, but cannot take the
 163  *      wakeup (because of eg a pending Unix signal or timeout) then try
 164  *      to ensure that another LWP sees it.  This is necessary because
 165  *      there may be multiple waiters, and at least one should take the
 166  *      wakeup if possible.
 167  */
 168 static inline int
 169 cv_exit(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, const int error)
 170 {
 171
 172         mutex_enter(mtx);
 173         if (__predict_false(error != 0))
 174                 cv_signal(cv);
 175
 176         LOCKDEBUG_UNLOCKED(CV_DEBUG_P(cv), cv, CV_RA, 0);
 177         KASSERT(cv_is_valid(cv));
 178
 179         return error;
 180 }
 181
 182 /*
 183  * cv_unsleep:
 184  *
 185  *      Remove an LWP from the condition variable and sleep queue.  This
 186  *      is called when the LWP has not been awoken normally but instead
 187  *      interrupted: for example, when a signal is received.  Must be
 188  *      called with the LWP locked, and must return it unlocked.
 189  */
 190 static void
 191 cv_unsleep(lwp_t *l, bool cleanup)
 192 {
 193         kcondvar_t *cv;
 194
 195         cv = (kcondvar_t *)(uintptr_t)l->l_wchan;
 196
 197         KASSERT(l->l_wchan == (wchan_t)cv);
 198         KASSERT(l->l_sleepq == CV_SLEEPQ(cv));
 199         KASSERT(cv_is_valid(cv));
 200         KASSERT(cv_has_waiters(cv));
 201
 202         sleepq_unsleep(l, cleanup);
 203 }
 204
 205 /*
 206  * cv_wait:
 207  *
 208  *      Wait non-interruptably on a condition variable until awoken.
 209  */
 210 void
 211 cv_wait(kcondvar_t *cv, kmutex_t *mtx)
 212 {
 213         lwp_t *l = curlwp;
 214
 215         KASSERT(mutex_owned(mtx));
 216
 217         cv_enter(cv, mtx, l);
 218         (void)sleepq_block(0, false);
 219         (void)cv_exit(cv, mtx, l, 0);
 220 }
 221
 222 /*
 223  * cv_wait_sig:
 224  *
 225  *      Wait on a condition variable until a awoken or a signal is received.
 226  *      Will also return early if the process is exiting.  Returns zero if
 227  *      awoken normallly, ERESTART if a signal was received and the system
 228  *      call is restartable, or EINTR otherwise.
 229  */
 230 int
 231 cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx)
 232 {
 233         lwp_t *l = curlwp;
 234         int error;
 235
 236         KASSERT(mutex_owned(mtx));
 237
 238         cv_enter(cv, mtx, l);
 239         error = sleepq_block(0, true);
 240         return cv_exit(cv, mtx, l, error);
 241 }
 242
 243 /*
 244  * cv_timedwait:
 245  *
 246  *      Wait on a condition variable until awoken or the specified timeout
 247  *      expires.  Returns zero if awoken normally or EWOULDBLOCK if the
 248  *      timeout expired.
 249  */
 250 int
 251 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo)
 252 {
 253         lwp_t *l = curlwp;
 254         int error;
 255
 256         KASSERT(mutex_owned(mtx));
 257
 258         cv_enter(cv, mtx, l);
 259         error = sleepq_block(timo, false);
 260         return cv_exit(cv, mtx, l, error);
 261 }
 262
 263 /*
 264  * cv_timedwait_sig:
 265  *
 266  *      Wait on a condition variable until a timeout expires, awoken or a
 267  *      signal is received.  Will also return early if the process is
 268  *      exiting.  Returns zero if awoken normallly, EWOULDBLOCK if the
 269  *      timeout expires, ERESTART if a signal was received and the system
 270  *      call is restartable, or EINTR otherwise.
 271  */
 272 int
 273 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo)
 274 {
 275         lwp_t *l = curlwp;
 276         int error;
 277
 278         KASSERT(mutex_owned(mtx));
 279
 280         cv_enter(cv, mtx, l);
 281         error = sleepq_block(timo, true);
 282         return cv_exit(cv, mtx, l, error);
 283 }
 284
 285 /*
 286  * cv_signal:
 287  *
 288  *      Wake the highest priority LWP waiting on a condition variable.
 289  *      Must be called with the interlocking mutex held.
 290  */
 291 void
 292 cv_signal(kcondvar_t *cv)
 293 {
 294
 295         /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */
 296         KASSERT(cv_is_valid(cv));
 297
 298         if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv))))
 299                 cv_wakeup_one(cv);
 300 }
 301
 302 static void __noinline
 303 cv_wakeup_one(kcondvar_t *cv)
 304 {
 305         sleepq_t *sq;
 306         kmutex_t *mp;
 307         lwp_t *l;
 308
 309         KASSERT(cv_is_valid(cv));
 310
 311         mp = sleepq_hashlock(cv);
 312         sq = CV_SLEEPQ(cv);
 313         l = TAILQ_FIRST(sq);
 314         if (l == NULL) {
 315                 mutex_spin_exit(mp);
 316                 return;
 317         }
 318         KASSERT(l->l_sleepq == sq);
 319         KASSERT(l->l_mutex == mp);
 320         KASSERT(l->l_wchan == cv);
 321         sleepq_remove(sq, l);
 322         mutex_spin_exit(mp);
 323
 324         KASSERT(cv_is_valid(cv));
 325 }
 326
 327 /*
 328  * cv_broadcast:
 329  *
 330  *      Wake all LWPs waiting on a condition variable.  Must be called
 331  *      with the interlocking mutex held.
 332  */
 333 void
 334 cv_broadcast(kcondvar_t *cv)
 335 {
 336
 337         /* LOCKDEBUG_WAKEUP(CV_DEBUG_P(cv), cv, CV_RA); */
 338         KASSERT(cv_is_valid(cv));
 339
 340         if (__predict_false(!TAILQ_EMPTY(CV_SLEEPQ(cv))))
 341                 cv_wakeup_all(cv);
 342 }
 343
 344 static void __noinline
 345 cv_wakeup_all(kcondvar_t *cv)
 346 {
 347         sleepq_t *sq;
 348         kmutex_t *mp;
 349         lwp_t *l, *next;
 350
 351         KASSERT(cv_is_valid(cv));
 352
 353         mp = sleepq_hashlock(cv);
 354         sq = CV_SLEEPQ(cv);
 355         for (l = TAILQ_FIRST(sq); l != NULL; l = next) {
 356                 KASSERT(l->l_sleepq == sq);
 357                 KASSERT(l->l_mutex == mp);
 358                 KASSERT(l->l_wchan == cv);
 359                 next = TAILQ_NEXT(l, l_sleepchain);
 360                 sleepq_remove(sq, l);
 361         }
 362         mutex_spin_exit(mp);
 363
 364         KASSERT(cv_is_valid(cv));
 365 }
 366
 367 /*
 368  * cv_has_waiters:
 369  *
 370  *      For diagnostic assertions: return non-zero if a condition
 371  *      variable has waiters.
 372  */
 373 bool
 374 cv_has_waiters(kcondvar_t *cv)
 375 {
 376
 377         return !TAILQ_EMPTY(CV_SLEEPQ(cv));
 378 }
 379
 380 /*
 381  * cv_is_valid:
 382  *
 383  *      For diagnostic assertions: return non-zero if a condition
 384  *      variable appears to be valid.  No locks need be held.
 385  */
 386 bool
 387 cv_is_valid(kcondvar_t *cv)
 388 {
 389
 390         return CV_WMESG(cv) != deadcv && CV_WMESG(cv) != NULL;
 391 }