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
|