The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/kern_condvar.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*      $NetBSD: kern_condvar.c,v 1.54 2022/06/29 22:27:01 riastradh Exp $      */
    2 
    3 /*-
    4  * Copyright (c) 2006, 2007, 2008, 2019, 2020 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.54 2022/06/29 22:27:01 riastradh Exp $");
   38 
   39 #include <sys/param.h>
   40 #include <sys/systm.h>
   41 #include <sys/lwp.h>
   42 #include <sys/condvar.h>
   43 #include <sys/sleepq.h>
   44 #include <sys/lockdebug.h>
   45 #include <sys/cpu.h>
   46 #include <sys/kernel.h>
   47 
   48 /*
   49  * Accessors for the private contents of the kcondvar_t data type.
   50  *
   51  *      cv_opaque[0]    sleepq_t
   52  *      cv_opaque[1]    description for ps(1)
   53  *
   54  * cv_opaque[0] is protected by the interlock passed to cv_wait() (enqueue
   55  * only), and the sleep queue lock acquired with sleepq_hashlock() (enqueue
   56  * and dequeue).
   57  *
   58  * cv_opaque[1] (the wmesg) is static and does not change throughout the life
   59  * of the CV.
   60  */
   61 #define CV_SLEEPQ(cv)           ((sleepq_t *)(cv)->cv_opaque)
   62 #define CV_WMESG(cv)            ((const char *)(cv)->cv_opaque[1])
   63 #define CV_SET_WMESG(cv, v)     (cv)->cv_opaque[1] = __UNCONST(v)
   64 
   65 #define CV_DEBUG_P(cv)  (CV_WMESG(cv) != nodebug)
   66 #define CV_RA           ((uintptr_t)__builtin_return_address(0))
   67 
   68 static void             cv_unsleep(lwp_t *, bool);
   69 static inline void      cv_wakeup_one(kcondvar_t *);
   70 static inline void      cv_wakeup_all(kcondvar_t *);
   71 
   72 syncobj_t cv_syncobj = {
   73         .sobj_flag      = SOBJ_SLEEPQ_SORTED,
   74         .sobj_unsleep   = cv_unsleep,
   75         .sobj_changepri = sleepq_changepri,
   76         .sobj_lendpri   = sleepq_lendpri,
   77         .sobj_owner     = syncobj_noowner,
   78 };
   79 
   80 static const char deadcv[] = "deadcv";
   81 
   82 /*
   83  * cv_init:
   84  *
   85  *      Initialize a condition variable for use.
   86  */
   87 void
   88 cv_init(kcondvar_t *cv, const char *wmesg)
   89 {
   90 
   91         KASSERT(wmesg != NULL);
   92         CV_SET_WMESG(cv, wmesg);
   93         sleepq_init(CV_SLEEPQ(cv));
   94 }
   95 
   96 /*
   97  * cv_destroy:
   98  *
   99  *      Tear down a condition variable.
  100  */
  101 void
  102 cv_destroy(kcondvar_t *cv)
  103 {
  104 
  105         sleepq_destroy(CV_SLEEPQ(cv));
  106 #ifdef DIAGNOSTIC
  107         KASSERT(cv_is_valid(cv));
  108         KASSERT(!cv_has_waiters(cv));
  109         CV_SET_WMESG(cv, deadcv);
  110 #endif
  111 }
  112 
  113 /*
  114  * cv_enter:
  115  *
  116  *      Look up and lock the sleep queue corresponding to the given
  117  *      condition variable, and increment the number of waiters.
  118  */
  119 static inline void
  120 cv_enter(kcondvar_t *cv, kmutex_t *mtx, lwp_t *l, bool catch_p)
  121 {
  122         sleepq_t *sq;
  123         kmutex_t *mp;
  124 
  125         KASSERT(cv_is_valid(cv));
  126         KASSERT(!cpu_intr_p());
  127         KASSERT((l->l_pflag & LP_INTR) == 0 || panicstr != NULL);
  128 
  129         l->l_kpriority = true;
  130         mp = sleepq_hashlock(cv);
  131         sq = CV_SLEEPQ(cv);
  132         sleepq_enter(sq, l, mp);
  133         sleepq_enqueue(sq, cv, CV_WMESG(cv), &cv_syncobj, catch_p);
  134         mutex_exit(mtx);
  135         KASSERT(cv_has_waiters(cv));
  136 }
  137 
  138 /*
  139  * cv_unsleep:
  140  *
  141  *      Remove an LWP from the condition variable and sleep queue.  This
  142  *      is called when the LWP has not been awoken normally but instead
  143  *      interrupted: for example, when a signal is received.  Must be
  144  *      called with the LWP locked.  Will unlock if "unlock" is true.
  145  */
  146 static void
  147 cv_unsleep(lwp_t *l, bool unlock)
  148 {
  149         kcondvar_t *cv __diagused;
  150 
  151         cv = (kcondvar_t *)(uintptr_t)l->l_wchan;
  152 
  153         KASSERT(l->l_wchan == (wchan_t)cv);
  154         KASSERT(l->l_sleepq == CV_SLEEPQ(cv));
  155         KASSERT(cv_is_valid(cv));
  156         KASSERT(cv_has_waiters(cv));
  157 
  158         sleepq_unsleep(l, unlock);
  159 }
  160 
  161 /*
  162  * cv_wait:
  163  *
  164  *      Wait non-interruptably on a condition variable until awoken.
  165  */
  166 void
  167 cv_wait(kcondvar_t *cv, kmutex_t *mtx)
  168 {
  169         lwp_t *l = curlwp;
  170 
  171         KASSERT(mutex_owned(mtx));
  172 
  173         cv_enter(cv, mtx, l, false);
  174         (void)sleepq_block(0, false, &cv_syncobj);
  175         mutex_enter(mtx);
  176 }
  177 
  178 /*
  179  * cv_wait_sig:
  180  *
  181  *      Wait on a condition variable until a awoken or a signal is received. 
  182  *      Will also return early if the process is exiting.  Returns zero if
  183  *      awoken normally, ERESTART if a signal was received and the system
  184  *      call is restartable, or EINTR otherwise.
  185  */
  186 int
  187 cv_wait_sig(kcondvar_t *cv, kmutex_t *mtx)
  188 {
  189         lwp_t *l = curlwp;
  190         int error;
  191 
  192         KASSERT(mutex_owned(mtx));
  193 
  194         cv_enter(cv, mtx, l, true);
  195         error = sleepq_block(0, true, &cv_syncobj);
  196         mutex_enter(mtx);
  197         return error;
  198 }
  199 
  200 /*
  201  * cv_timedwait:
  202  *
  203  *      Wait on a condition variable until awoken or the specified timeout
  204  *      expires.  Returns zero if awoken normally or EWOULDBLOCK if the
  205  *      timeout expired.
  206  *
  207  *      timo is a timeout in ticks.  timo = 0 specifies an infinite timeout.
  208  */
  209 int
  210 cv_timedwait(kcondvar_t *cv, kmutex_t *mtx, int timo)
  211 {
  212         lwp_t *l = curlwp;
  213         int error;
  214 
  215         KASSERT(mutex_owned(mtx));
  216 
  217         cv_enter(cv, mtx, l, false);
  218         error = sleepq_block(timo, false, &cv_syncobj);
  219         mutex_enter(mtx);
  220         return error;
  221 }
  222 
  223 /*
  224  * cv_timedwait_sig:
  225  *
  226  *      Wait on a condition variable until a timeout expires, awoken or a
  227  *      signal is received.  Will also return early if the process is
  228  *      exiting.  Returns zero if awoken normally, EWOULDBLOCK if the
  229  *      timeout expires, ERESTART if a signal was received and the system
  230  *      call is restartable, or EINTR otherwise.
  231  *
  232  *      timo is a timeout in ticks.  timo = 0 specifies an infinite timeout.
  233  */
  234 int
  235 cv_timedwait_sig(kcondvar_t *cv, kmutex_t *mtx, int timo)
  236 {
  237         lwp_t *l = curlwp;
  238         int error;
  239 
  240         KASSERT(mutex_owned(mtx));
  241 
  242         cv_enter(cv, mtx, l, true);
  243         error = sleepq_block(timo, true, &cv_syncobj);
  244         mutex_enter(mtx);
  245         return error;
  246 }
  247 
  248 /*
  249  * Given a number of seconds, sec, and 2^64ths of a second, frac, we
  250  * want a number of ticks for a timeout:
  251  *
  252  *      timo = hz*(sec + frac/2^64)
  253  *           = hz*sec + hz*frac/2^64
  254  *           = hz*sec + hz*(frachi*2^32 + fraclo)/2^64
  255  *           = hz*sec + hz*frachi/2^32 + hz*fraclo/2^64,
  256  *
  257  * where frachi is the high 32 bits of frac and fraclo is the
  258  * low 32 bits.
  259  *
  260  * We assume hz < INT_MAX/2 < UINT32_MAX, so
  261  *
  262  *      hz*fraclo/2^64 < fraclo*2^32/2^64 <= 1,
  263  *
  264  * since fraclo < 2^32.
  265  *
  266  * We clamp the result at INT_MAX/2 for a timeout in ticks, since we
  267  * can't represent timeouts higher than INT_MAX in cv_timedwait, and
  268  * spurious wakeup is OK.  Moreover, we don't want to wrap around,
  269  * because we compute end - start in ticks in order to compute the
  270  * remaining timeout, and that difference cannot wrap around, so we use
  271  * a timeout less than INT_MAX.  Using INT_MAX/2 provides plenty of
  272  * margin for paranoia and will exceed most waits in practice by far.
  273  */
  274 static unsigned
  275 bintime2timo(const struct bintime *bt)
  276 {
  277 
  278         KASSERT(hz < INT_MAX/2);
  279         CTASSERT(INT_MAX/2 < UINT32_MAX);
  280         if (bt->sec > ((INT_MAX/2)/hz))
  281                 return INT_MAX/2;
  282         if ((hz*(bt->frac >> 32) >> 32) > (INT_MAX/2 - hz*bt->sec))
  283                 return INT_MAX/2;
  284 
  285         return hz*bt->sec + (hz*(bt->frac >> 32) >> 32);
  286 }
  287 
  288 /*
  289  * timo is in units of ticks.  We want units of seconds and 2^64ths of
  290  * a second.  We know hz = 1 sec/tick, and 2^64 = 1 sec/(2^64th of a
  291  * second), from which we can conclude 2^64 / hz = 1 (2^64th of a
  292  * second)/tick.  So for the fractional part, we compute
  293  *
  294  *      frac = rem * 2^64 / hz
  295  *           = ((rem * 2^32) / hz) * 2^32
  296  *
  297  * Using truncating integer division instead of real division will
  298  * leave us with only about 32 bits of precision, which means about
  299  * 1/4-nanosecond resolution, which is good enough for our purposes.
  300  */
  301 static struct bintime
  302 timo2bintime(unsigned timo)
  303 {
  304 
  305         return (struct bintime) {
  306                 .sec = timo / hz,
  307                 .frac = (((uint64_t)(timo % hz) << 32)/hz << 32),
  308         };
  309 }
  310 
  311 /*
  312  * cv_timedwaitbt:
  313  *
  314  *      Wait on a condition variable until awoken or the specified
  315  *      timeout expires.  Returns zero if awoken normally or
  316  *      EWOULDBLOCK if the timeout expires.
  317  *
  318  *      On entry, bt is a timeout in bintime.  cv_timedwaitbt subtracts
  319  *      the time slept, so on exit, bt is the time remaining after
  320  *      sleeping, possibly negative if the complete time has elapsed.
  321  *      No infinite timeout; use cv_wait_sig instead.
  322  *
  323  *      epsilon is a requested maximum error in timeout (excluding
  324  *      spurious wakeups).  Currently not used, will be used in the
  325  *      future to choose between low- and high-resolution timers.
  326  *      Actual wakeup time will be somewhere in [t, t + max(e, r) + s)
  327  *      where r is the finest resolution of clock available and s is
  328  *      scheduling delays for scheduler overhead and competing threads.
  329  *      Time is measured by the interrupt source implementing the
  330  *      timeout, not by another timecounter.
  331  */
  332 int
  333 cv_timedwaitbt(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt,
  334     const struct bintime *epsilon __diagused)
  335 {
  336         struct bintime slept;
  337         unsigned start, end;
  338         int timo;
  339         int error;
  340 
  341         KASSERTMSG(bt->sec >= 0, "negative timeout");
  342         KASSERTMSG(epsilon != NULL, "specify maximum requested delay");
  343 
  344         /* If there's nothing left to wait, time out.  */
  345         if (bt->sec == 0 && bt->frac == 0)
  346                 return EWOULDBLOCK;
  347 
  348         /* Convert to ticks, but clamp to be >=1.  */
  349         timo = bintime2timo(bt);
  350         KASSERTMSG(timo >= 0, "negative ticks: %d", timo);
  351         if (timo == 0)
  352                 timo = 1;
  353 
  354         /*
  355          * getticks() is technically int, but nothing special
  356          * happens instead of overflow, so we assume two's-complement
  357          * wraparound and just treat it as unsigned.
  358          */
  359         start = getticks();
  360         error = cv_timedwait(cv, mtx, timo);
  361         end = getticks();
  362 
  363         /*
  364          * Set it to the time left, or zero, whichever is larger.  We
  365          * do not fail with EWOULDBLOCK here because this may have been
  366          * an explicit wakeup, so the caller needs to check before they
  367          * give up or else cv_signal would be lost.
  368          */
  369         slept = timo2bintime(end - start);
  370         if (bintimecmp(bt, &slept, <=)) {
  371                 bt->sec = 0;
  372                 bt->frac = 0;
  373         } else {
  374                 /* bt := bt - slept */
  375                 bintime_sub(bt, &slept);
  376         }
  377 
  378         return error;
  379 }
  380 
  381 /*
  382  * cv_timedwaitbt_sig:
  383  *
  384  *      Wait on a condition variable until awoken, the specified
  385  *      timeout expires, or interrupted by a signal.  Returns zero if
  386  *      awoken normally, EWOULDBLOCK if the timeout expires, or
  387  *      EINTR/ERESTART if interrupted by a signal.
  388  *
  389  *      On entry, bt is a timeout in bintime.  cv_timedwaitbt_sig
  390  *      subtracts the time slept, so on exit, bt is the time remaining
  391  *      after sleeping.  No infinite timeout; use cv_wait instead.
  392  *
  393  *      epsilon is a requested maximum error in timeout (excluding
  394  *      spurious wakeups).  Currently not used, will be used in the
  395  *      future to choose between low- and high-resolution timers.
  396  */
  397 int
  398 cv_timedwaitbt_sig(kcondvar_t *cv, kmutex_t *mtx, struct bintime *bt,
  399     const struct bintime *epsilon __diagused)
  400 {
  401         struct bintime slept;
  402         unsigned start, end;
  403         int timo;
  404         int error;
  405 
  406         KASSERTMSG(bt->sec >= 0, "negative timeout");
  407         KASSERTMSG(epsilon != NULL, "specify maximum requested delay");
  408 
  409         /* If there's nothing left to wait, time out.  */
  410         if (bt->sec == 0 && bt->frac == 0)
  411                 return EWOULDBLOCK;
  412 
  413         /* Convert to ticks, but clamp to be >=1.  */
  414         timo = bintime2timo(bt);
  415         KASSERTMSG(timo >= 0, "negative ticks: %d", timo);
  416         if (timo == 0)
  417                 timo = 1;
  418 
  419         /*
  420          * getticks() is technically int, but nothing special
  421          * happens instead of overflow, so we assume two's-complement
  422          * wraparound and just treat it as unsigned.
  423          */
  424         start = getticks();
  425         error = cv_timedwait_sig(cv, mtx, timo);
  426         end = getticks();
  427 
  428         /*
  429          * Set it to the time left, or zero, whichever is larger.  We
  430          * do not fail with EWOULDBLOCK here because this may have been
  431          * an explicit wakeup, so the caller needs to check before they
  432          * give up or else cv_signal would be lost.
  433          */
  434         slept = timo2bintime(end - start);
  435         if (bintimecmp(bt, &slept, <=)) {
  436                 bt->sec = 0;
  437                 bt->frac = 0;
  438         } else {
  439                 /* bt := bt - slept */
  440                 bintime_sub(bt, &slept);
  441         }
  442 
  443         return error;
  444 }
  445 
  446 /*
  447  * cv_signal:
  448  *
  449  *      Wake the highest priority LWP waiting on a condition variable.
  450  *      Must be called with the interlocking mutex held.
  451  */
  452 void
  453 cv_signal(kcondvar_t *cv)
  454 {
  455 
  456         KASSERT(cv_is_valid(cv));
  457 
  458         if (__predict_false(!LIST_EMPTY(CV_SLEEPQ(cv))))
  459                 cv_wakeup_one(cv);
  460 }
  461 
  462 /*
  463  * cv_wakeup_one:
  464  *
  465  *      Slow path for cv_signal().  Deliberately marked __noinline to
  466  *      prevent the compiler pulling it in to cv_signal(), which adds
  467  *      extra prologue and epilogue code.
  468  */
  469 static __noinline void
  470 cv_wakeup_one(kcondvar_t *cv)
  471 {
  472         sleepq_t *sq;
  473         kmutex_t *mp;
  474         lwp_t *l;
  475 
  476         /*
  477          * Keep waking LWPs until a non-interruptable waiter is found.  An
  478          * interruptable waiter could fail to do something useful with the
  479          * wakeup due to an error return from cv_[timed]wait_sig(), and the
  480          * caller of cv_signal() may not expect such a scenario.
  481          *
  482          * This isn't a problem for non-interruptable waits (untimed and
  483          * timed), because if such a waiter is woken here it will not return
  484          * an error.
  485          */
  486         mp = sleepq_hashlock(cv);
  487         sq = CV_SLEEPQ(cv);
  488         while ((l = LIST_FIRST(sq)) != NULL) {
  489                 KASSERT(l->l_sleepq == sq);
  490                 KASSERT(l->l_mutex == mp);
  491                 KASSERT(l->l_wchan == cv);
  492                 if ((l->l_flag & LW_SINTR) == 0) {
  493                         sleepq_remove(sq, l);
  494                         break;
  495                 } else
  496                         sleepq_remove(sq, l);
  497         }
  498         mutex_spin_exit(mp);
  499 }
  500 
  501 /*
  502  * cv_broadcast:
  503  *
  504  *      Wake all LWPs waiting on a condition variable.  Must be called
  505  *      with the interlocking mutex held.
  506  */
  507 void
  508 cv_broadcast(kcondvar_t *cv)
  509 {
  510 
  511         KASSERT(cv_is_valid(cv));
  512 
  513         if (__predict_false(!LIST_EMPTY(CV_SLEEPQ(cv))))  
  514                 cv_wakeup_all(cv);
  515 }
  516 
  517 /*
  518  * cv_wakeup_all:
  519  *
  520  *      Slow path for cv_broadcast().  Deliberately marked __noinline to
  521  *      prevent the compiler pulling it in to cv_broadcast(), which adds
  522  *      extra prologue and epilogue code.
  523  */
  524 static __noinline void
  525 cv_wakeup_all(kcondvar_t *cv)
  526 {
  527         sleepq_t *sq;
  528         kmutex_t *mp;
  529         lwp_t *l;
  530 
  531         mp = sleepq_hashlock(cv);
  532         sq = CV_SLEEPQ(cv);
  533         while ((l = LIST_FIRST(sq)) != NULL) {
  534                 KASSERT(l->l_sleepq == sq);
  535                 KASSERT(l->l_mutex == mp);
  536                 KASSERT(l->l_wchan == cv);
  537                 sleepq_remove(sq, l);
  538         }
  539         mutex_spin_exit(mp);
  540 }
  541 
  542 /*
  543  * cv_has_waiters:
  544  *
  545  *      For diagnostic assertions: return non-zero if a condition
  546  *      variable has waiters.
  547  */
  548 bool
  549 cv_has_waiters(kcondvar_t *cv)
  550 {
  551 
  552         return !LIST_EMPTY(CV_SLEEPQ(cv));
  553 }
  554 
  555 /*
  556  * cv_is_valid:
  557  *
  558  *      For diagnostic assertions: return non-zero if a condition
  559  *      variable appears to be valid.  No locks need be held.
  560  */
  561 bool
  562 cv_is_valid(kcondvar_t *cv)
  563 {
  564 
  565         return CV_WMESG(cv) != deadcv && CV_WMESG(cv) != NULL;
  566 }

Cache object: 19e766f7b4666d77d02b3fa0cc907ce7


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.