2 * Copyright (c) 2001-2004 Jakub Jermar
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 /** @addtogroup kernel_sync
37 * Wait queue is the basic synchronization primitive upon which all
38 * other synchronization primitives build.
40 * It allows threads to wait for an event in first-come, first-served
41 * fashion. Conditional operation as well as timeouts and interruptions
48 #include <synch/waitq.h>
49 #include <synch/spinlock.h>
50 #include <preemption.h>
51 #include <proc/thread.h>
52 #include <proc/scheduler.h>
55 #include <time/timeout.h>
59 #include <arch/cycle.h>
62 static void waitq_sleep_timed_out(void *);
63 static void waitq_complete_wakeup(waitq_t
*);
65 /** Initialize wait queue
67 * Initialize wait queue.
69 * @param wq Pointer to wait queue to be initialized.
72 void waitq_initialize(waitq_t
*wq
)
74 memsetb(wq
, sizeof(*wq
), 0);
75 irq_spinlock_initialize(&wq
->lock
, "wq.lock");
76 list_initialize(&wq
->sleepers
);
79 void waitq_initialize_with_count(waitq_t
*wq
, int count
)
81 memsetb(wq
, sizeof(*wq
), 0);
82 irq_spinlock_initialize(&wq
->lock
, "wq.lock");
83 list_initialize(&wq
->sleepers
);
84 wq
->missed_wakeups
= count
;
87 /** Handle timeout during waitq_sleep_timeout() call
89 * This routine is called when waitq_sleep_timeout() times out.
90 * Interrupts are disabled.
92 * It is supposed to try to remove 'its' thread from the wait queue;
93 * it can eventually fail to achieve this goal when these two events
94 * overlap. In that case it behaves just as though there was no
97 * @param data Pointer to the thread that called waitq_sleep_timeout().
100 void waitq_sleep_timed_out(void *data
)
102 thread_t
*thread
= (thread_t
*) data
;
103 bool do_wakeup
= false;
104 DEADLOCK_PROBE_INIT(p_wqlock
);
106 irq_spinlock_lock(&threads_lock
, false);
109 irq_spinlock_lock(&thread
->lock
, false);
112 if ((wq
= thread
->sleep_queue
)) { /* Assignment */
113 if (!irq_spinlock_trylock(&wq
->lock
)) {
114 irq_spinlock_unlock(&thread
->lock
, false);
115 DEADLOCK_PROBE(p_wqlock
, DEADLOCK_THRESHOLD
);
120 list_remove(&thread
->wq_link
);
121 thread
->saved_context
= thread
->sleep_timeout_context
;
123 if (thread
->sleep_composable
)
124 wq
->ignore_wakeups
++;
125 thread
->sleep_queue
= NULL
;
126 irq_spinlock_unlock(&wq
->lock
, false);
129 irq_spinlock_unlock(&thread
->lock
, false);
132 thread_ready(thread
);
134 irq_spinlock_unlock(&threads_lock
, false);
137 /** Interrupt sleeping thread.
139 * This routine attempts to interrupt a thread from its sleep in
140 * a waitqueue. If the thread is not found sleeping, no action
143 * The threads_lock must be already held and interrupts must be
144 * disabled upon calling this function.
146 * @param thread Thread to be interrupted.
149 void waitq_interrupt_sleep(thread_t
*thread
)
151 bool do_wakeup
= false;
152 DEADLOCK_PROBE_INIT(p_wqlock
);
155 * The thread is quaranteed to exist because
156 * threads_lock is held.
160 irq_spinlock_lock(&thread
->lock
, false);
163 if ((wq
= thread
->sleep_queue
)) { /* Assignment */
164 if (!(thread
->sleep_interruptible
)) {
166 * The sleep cannot be interrupted.
168 irq_spinlock_unlock(&thread
->lock
, false);
172 if (!irq_spinlock_trylock(&wq
->lock
)) {
174 irq_spinlock_unlock(&thread
->lock
, false);
175 DEADLOCK_PROBE(p_wqlock
, DEADLOCK_THRESHOLD
);
179 list_remove(&thread
->wq_link
);
180 thread
->saved_context
= thread
->sleep_interruption_context
;
181 if (thread
->sleep_composable
)
182 wq
->ignore_wakeups
++;
184 thread
->sleep_queue
= NULL
;
185 irq_spinlock_unlock(&wq
->lock
, false);
188 irq_spinlock_unlock(&thread
->lock
, false);
191 thread_ready(thread
);
194 #define PARAM_NON_BLOCKING(flags, usec) \
195 (((flags) & SYNCH_FLAGS_NON_BLOCKING) && ((usec) == 0))
197 errno_t
waitq_sleep(waitq_t
*wq
)
199 return waitq_sleep_timeout(wq
, SYNCH_NO_TIMEOUT
, SYNCH_FLAGS_NONE
, NULL
);
202 /** Sleep until either wakeup, timeout or interruption occurs
204 * This is a sleep implementation which allows itself to time out or to be
205 * interrupted from the sleep, restoring a failover context.
207 * Sleepers are organised in a FIFO fashion in a structure called wait queue.
209 * This function is really basic in that other functions as waitq_sleep()
210 * and all the *_timeout() functions use it.
212 * @param wq Pointer to wait queue.
213 * @param usec Timeout in microseconds.
214 * @param flags Specify mode of the sleep.
216 * @param[out] blocked On return, regardless of the return code,
217 * `*blocked` is set to `true` iff the thread went to
220 * The sleep can be interrupted only if the
221 * SYNCH_FLAGS_INTERRUPTIBLE bit is specified in flags.
223 * If usec is greater than zero, regardless of the value of the
224 * SYNCH_FLAGS_NON_BLOCKING bit in flags, the call will not return until either
225 * timeout, interruption or wakeup comes.
227 * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is not set in flags,
228 * the call will not return until wakeup or interruption comes.
230 * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is set in flags, the
231 * call will immediately return, reporting either success or failure.
233 * @return EAGAIN, meaning that the sleep failed because it was requested
234 * as SYNCH_FLAGS_NON_BLOCKING, but there was no pending wakeup.
235 * @return ETIMEOUT, meaning that the sleep timed out.
236 * @return EINTR, meaning that somebody interrupted the sleeping
237 * thread. Check the value of `*blocked` to see if the thread slept,
238 * or if a pending interrupt forced it to return immediately.
239 * @return EOK, meaning that none of the above conditions occured, and the
240 * thread was woken up successfuly by `waitq_wakeup()`. Check
241 * the value of `*blocked` to see if the thread slept or if
242 * the wakeup was already pending.
245 errno_t
waitq_sleep_timeout(waitq_t
*wq
, uint32_t usec
, unsigned int flags
, bool *blocked
)
247 assert((!PREEMPTION_DISABLED
) || (PARAM_NON_BLOCKING(flags
, usec
)));
249 ipl_t ipl
= waitq_sleep_prepare(wq
);
251 errno_t rc
= waitq_sleep_timeout_unsafe(wq
, usec
, flags
, &nblocked
);
252 waitq_sleep_finish(wq
, nblocked
, ipl
);
254 if (blocked
!= NULL
) {
260 /** Prepare to sleep in a waitq.
262 * This function will return holding the lock of the wait queue
263 * and interrupts disabled.
265 * @param wq Wait queue.
267 * @return Interrupt level as it existed on entry to this function.
270 ipl_t
waitq_sleep_prepare(waitq_t
*wq
)
272 ipl_t ipl
= interrupts_disable();
273 irq_spinlock_lock(&wq
->lock
, false);
277 /** Finish waiting in a wait queue.
279 * This function restores interrupts to the state that existed prior
280 * to the call to waitq_sleep_prepare(). If necessary, the wait queue
283 * @param wq Wait queue.
284 * @param blocked Out parameter of waitq_sleep_timeout_unsafe().
285 * @param ipl Interrupt level returned by waitq_sleep_prepare().
288 void waitq_sleep_finish(waitq_t
*wq
, bool blocked
, ipl_t ipl
)
292 * Wait for a waitq_wakeup() or waitq_unsleep() to complete
293 * before returning from waitq_sleep() to the caller. Otherwise
294 * the caller might expect that the wait queue is no longer used
295 * and deallocate it (although the wakeup on a another cpu has
296 * not yet completed and is using the wait queue).
298 * Note that we have to do this for EOK and EINTR, but not
299 * necessarily for ETIMEOUT where the timeout handler stops
300 * using the waitq before waking us up. To be on the safe side,
301 * ensure the waitq is not in use anymore in this case as well.
303 waitq_complete_wakeup(wq
);
305 irq_spinlock_unlock(&wq
->lock
, false);
308 interrupts_restore(ipl
);
311 errno_t
waitq_sleep_unsafe(waitq_t
*wq
, bool *blocked
)
313 return waitq_sleep_timeout_unsafe(wq
, SYNCH_NO_TIMEOUT
, SYNCH_FLAGS_NONE
, blocked
);
316 /** Internal implementation of waitq_sleep_timeout().
318 * This function implements logic of sleeping in a wait queue.
319 * This call must be preceded by a call to waitq_sleep_prepare()
320 * and followed by a call to waitq_sleep_finish().
322 * @param wq See waitq_sleep_timeout().
323 * @param usec See waitq_sleep_timeout().
324 * @param flags See waitq_sleep_timeout().
326 * @param[out] blocked See waitq_sleep_timeout().
328 * @return See waitq_sleep_timeout().
331 errno_t
waitq_sleep_timeout_unsafe(waitq_t
*wq
, uint32_t usec
, unsigned int flags
, bool *blocked
)
335 /* Checks whether to go to sleep at all */
336 if (wq
->missed_wakeups
) {
337 wq
->missed_wakeups
--;
340 if (PARAM_NON_BLOCKING(flags
, usec
)) {
341 /* Return immediately instead of going to sleep */
347 * Now we are firmly decided to go to sleep.
350 irq_spinlock_lock(&THREAD
->lock
, false);
353 timeout_initialize(&timeout
);
355 THREAD
->sleep_composable
= (flags
& SYNCH_FLAGS_FUTEX
);
357 if (flags
& SYNCH_FLAGS_INTERRUPTIBLE
) {
359 * If the thread was already interrupted,
360 * don't go to sleep at all.
362 if (THREAD
->interrupted
) {
363 irq_spinlock_unlock(&THREAD
->lock
, false);
368 * Set context that will be restored if the sleep
369 * of this thread is ever interrupted.
371 THREAD
->sleep_interruptible
= true;
372 if (!context_save(&THREAD
->sleep_interruption_context
)) {
373 /* Short emulation of scheduler() return code. */
374 THREAD
->last_cycle
= get_cycle();
375 irq_spinlock_unlock(&THREAD
->lock
, false);
377 timeout_unregister(&timeout
);
382 THREAD
->sleep_interruptible
= false;
385 /* We use the timeout variant. */
386 if (!context_save(&THREAD
->sleep_timeout_context
)) {
387 /* Short emulation of scheduler() return code. */
388 THREAD
->last_cycle
= get_cycle();
389 irq_spinlock_unlock(&THREAD
->lock
, false);
393 timeout_register(&timeout
, (uint64_t) usec
, waitq_sleep_timed_out
, THREAD
);
396 list_append(&THREAD
->wq_link
, &wq
->sleepers
);
402 THREAD
->state
= Sleeping
;
403 THREAD
->sleep_queue
= wq
;
406 * Must be before entry to scheduler, because there are multiple
411 irq_spinlock_unlock(&THREAD
->lock
, false);
413 /* wq->lock is released in scheduler_separated_stack() */
417 timeout_unregister(&timeout
);
423 /** Wake up first thread sleeping in a wait queue
425 * Wake up first thread sleeping in a wait queue. This is the SMP- and IRQ-safe
426 * wrapper meant for general use.
428 * Besides its 'normal' wakeup operation, it attempts to unregister possible
431 * @param wq Pointer to wait queue.
432 * @param mode Wakeup mode.
435 void waitq_wakeup(waitq_t
*wq
, wakeup_mode_t mode
)
437 irq_spinlock_lock(&wq
->lock
, true);
438 _waitq_wakeup_unsafe(wq
, mode
);
439 irq_spinlock_unlock(&wq
->lock
, true);
442 /** If there is a wakeup in progress actively waits for it to complete.
444 * The function returns once the concurrently running waitq_wakeup()
445 * exits. It returns immediately if there are no concurrent wakeups
448 * Interrupts must be disabled.
452 * void callback(waitq *wq)
454 * // Do something and notify wait_for_completion() that we're done.
457 * void wait_for_completion(void)
460 * waitq_initialize(&wq);
461 * // Run callback() in the background, pass it wq.
462 * do_asynchronously(callback, &wq);
463 * // Wait for callback() to complete its work.
465 * // callback() completed its work, but it may still be accessing
466 * // wq in waitq_wakeup(). Therefore it is not yet safe to return
467 * // from waitq_sleep() or it would clobber up our stack (where wq
468 * // is stored). waitq_sleep() ensures the wait queue is no longer
469 * // in use by invoking waitq_complete_wakeup() internally.
471 * // waitq_sleep() returned, it is safe to free wq.
475 * @param wq Pointer to a wait queue.
477 static void waitq_complete_wakeup(waitq_t
*wq
)
479 assert(interrupts_disabled());
481 irq_spinlock_lock(&wq
->lock
, false);
482 irq_spinlock_unlock(&wq
->lock
, false);
485 /** Internal SMP- and IRQ-unsafe version of waitq_wakeup()
487 * This is the internal SMP- and IRQ-unsafe version of waitq_wakeup(). It
488 * assumes wq->lock is already locked and interrupts are already disabled.
490 * @param wq Pointer to wait queue.
491 * @param mode If mode is WAKEUP_FIRST, then the longest waiting
492 * thread, if any, is woken up. If mode is WAKEUP_ALL, then
493 * all waiting threads, if any, are woken up. If there are
494 * no waiting threads to be woken up, the missed wakeup is
495 * recorded in the wait queue.
498 void _waitq_wakeup_unsafe(waitq_t
*wq
, wakeup_mode_t mode
)
502 assert(interrupts_disabled());
503 assert(irq_spinlock_locked(&wq
->lock
));
505 if (wq
->ignore_wakeups
> 0) {
506 if (mode
== WAKEUP_FIRST
) {
507 wq
->ignore_wakeups
--;
510 wq
->ignore_wakeups
= 0;
514 if (list_empty(&wq
->sleepers
)) {
515 if (mode
== WAKEUP_CLOSE
) {
516 // FIXME: this can technically fail if we get two billion sleeps after the wakeup call.
517 wq
->missed_wakeups
= INT_MAX
;
518 } else if (mode
!= WAKEUP_ALL
) {
519 wq
->missed_wakeups
++;
526 thread_t
*thread
= list_get_instance(list_first(&wq
->sleepers
),
530 * Lock the thread prior to removing it from the wq.
531 * This is not necessary because of mutual exclusion
532 * (the link belongs to the wait queue), but because
533 * of synchronization with waitq_sleep_timed_out()
534 * and thread_interrupt_sleep().
536 * In order for these two functions to work, the following
537 * invariant must hold:
539 * thread->sleep_queue != NULL <=> thread sleeps in a wait queue
541 * For an observer who locks the thread, the invariant
542 * holds only when the lock is held prior to removing
543 * it from the wait queue.
546 irq_spinlock_lock(&thread
->lock
, false);
547 list_remove(&thread
->wq_link
);
549 thread
->sleep_queue
= NULL
;
550 irq_spinlock_unlock(&thread
->lock
, false);
552 thread_ready(thread
);
554 if (mode
== WAKEUP_ALL
)