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 /** Handle timeout during waitq_sleep_timeout() call
81 * This routine is called when waitq_sleep_timeout() times out.
82 * Interrupts are disabled.
84 * It is supposed to try to remove 'its' thread from the wait queue;
85 * it can eventually fail to achieve this goal when these two events
86 * overlap. In that case it behaves just as though there was no
89 * @param data Pointer to the thread that called waitq_sleep_timeout().
92 void waitq_sleep_timed_out(void *data
)
94 thread_t
*thread
= (thread_t
*) data
;
95 bool do_wakeup
= false;
96 DEADLOCK_PROBE_INIT(p_wqlock
);
98 irq_spinlock_lock(&threads_lock
, false);
99 if (!thread_exists(thread
))
103 irq_spinlock_lock(&thread
->lock
, false);
106 if ((wq
= thread
->sleep_queue
)) { /* Assignment */
107 if (!irq_spinlock_trylock(&wq
->lock
)) {
108 irq_spinlock_unlock(&thread
->lock
, false);
109 DEADLOCK_PROBE(p_wqlock
, DEADLOCK_THRESHOLD
);
114 list_remove(&thread
->wq_link
);
115 thread
->saved_context
= thread
->sleep_timeout_context
;
117 if (thread
->sleep_composable
)
118 wq
->ignore_wakeups
++;
119 thread
->sleep_queue
= NULL
;
120 irq_spinlock_unlock(&wq
->lock
, false);
123 irq_spinlock_unlock(&thread
->lock
, false);
126 thread_ready(thread
);
129 irq_spinlock_unlock(&threads_lock
, false);
132 /** Interrupt sleeping thread.
134 * This routine attempts to interrupt a thread from its sleep in
135 * a waitqueue. If the thread is not found sleeping, no action
138 * The threads_lock must be already held and interrupts must be
139 * disabled upon calling this function.
141 * @param thread Thread to be interrupted.
144 void waitq_interrupt_sleep(thread_t
*thread
)
146 bool do_wakeup
= false;
147 DEADLOCK_PROBE_INIT(p_wqlock
);
150 * The thread is quaranteed to exist because
151 * threads_lock is held.
155 irq_spinlock_lock(&thread
->lock
, false);
158 if ((wq
= thread
->sleep_queue
)) { /* Assignment */
159 if (!(thread
->sleep_interruptible
)) {
161 * The sleep cannot be interrupted.
163 irq_spinlock_unlock(&thread
->lock
, false);
167 if (!irq_spinlock_trylock(&wq
->lock
)) {
169 irq_spinlock_unlock(&thread
->lock
, false);
170 DEADLOCK_PROBE(p_wqlock
, DEADLOCK_THRESHOLD
);
174 list_remove(&thread
->wq_link
);
175 thread
->saved_context
= thread
->sleep_interruption_context
;
176 if (thread
->sleep_composable
)
177 wq
->ignore_wakeups
++;
179 thread
->sleep_queue
= NULL
;
180 irq_spinlock_unlock(&wq
->lock
, false);
183 irq_spinlock_unlock(&thread
->lock
, false);
186 thread_ready(thread
);
189 #define PARAM_NON_BLOCKING(flags, usec) \
190 (((flags) & SYNCH_FLAGS_NON_BLOCKING) && ((usec) == 0))
192 errno_t
waitq_sleep(waitq_t
*wq
)
194 return waitq_sleep_timeout(wq
, SYNCH_NO_TIMEOUT
, SYNCH_FLAGS_NONE
, NULL
);
197 /** Sleep until either wakeup, timeout or interruption occurs
199 * This is a sleep implementation which allows itself to time out or to be
200 * interrupted from the sleep, restoring a failover context.
202 * Sleepers are organised in a FIFO fashion in a structure called wait queue.
204 * This function is really basic in that other functions as waitq_sleep()
205 * and all the *_timeout() functions use it.
207 * @param wq Pointer to wait queue.
208 * @param usec Timeout in microseconds.
209 * @param flags Specify mode of the sleep.
211 * @param[out] blocked On return, regardless of the return code,
212 * `*blocked` is set to `true` iff the thread went to
215 * The sleep can be interrupted only if the
216 * SYNCH_FLAGS_INTERRUPTIBLE bit is specified in flags.
218 * If usec is greater than zero, regardless of the value of the
219 * SYNCH_FLAGS_NON_BLOCKING bit in flags, the call will not return until either
220 * timeout, interruption or wakeup comes.
222 * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is not set in flags,
223 * the call will not return until wakeup or interruption comes.
225 * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is set in flags, the
226 * call will immediately return, reporting either success or failure.
228 * @return EAGAIN, meaning that the sleep failed because it was requested
229 * as SYNCH_FLAGS_NON_BLOCKING, but there was no pending wakeup.
230 * @return ETIMEOUT, meaning that the sleep timed out.
231 * @return EINTR, meaning that somebody interrupted the sleeping
232 * thread. Check the value of `*blocked` to see if the thread slept,
233 * or if a pending interrupt forced it to return immediately.
234 * @return EOK, meaning that none of the above conditions occured, and the
235 * thread was woken up successfuly by `waitq_wakeup()`. Check
236 * the value of `*blocked` to see if the thread slept or if
237 * the wakeup was already pending.
240 errno_t
waitq_sleep_timeout(waitq_t
*wq
, uint32_t usec
, unsigned int flags
, bool *blocked
)
242 assert((!PREEMPTION_DISABLED
) || (PARAM_NON_BLOCKING(flags
, usec
)));
244 ipl_t ipl
= waitq_sleep_prepare(wq
);
246 errno_t rc
= waitq_sleep_timeout_unsafe(wq
, usec
, flags
, &nblocked
);
247 waitq_sleep_finish(wq
, nblocked
, ipl
);
249 if (blocked
!= NULL
) {
255 /** Prepare to sleep in a waitq.
257 * This function will return holding the lock of the wait queue
258 * and interrupts disabled.
260 * @param wq Wait queue.
262 * @return Interrupt level as it existed on entry to this function.
265 ipl_t
waitq_sleep_prepare(waitq_t
*wq
)
267 ipl_t ipl
= interrupts_disable();
268 irq_spinlock_lock(&wq
->lock
, false);
272 /** Finish waiting in a wait queue.
274 * This function restores interrupts to the state that existed prior
275 * to the call to waitq_sleep_prepare(). If necessary, the wait queue
278 * @param wq Wait queue.
279 * @param blocked Out parameter of waitq_sleep_timeout_unsafe().
280 * @param ipl Interrupt level returned by waitq_sleep_prepare().
283 void waitq_sleep_finish(waitq_t
*wq
, bool blocked
, ipl_t ipl
)
287 * Wait for a waitq_wakeup() or waitq_unsleep() to complete
288 * before returning from waitq_sleep() to the caller. Otherwise
289 * the caller might expect that the wait queue is no longer used
290 * and deallocate it (although the wakeup on a another cpu has
291 * not yet completed and is using the wait queue).
293 * Note that we have to do this for EOK and EINTR, but not
294 * necessarily for ETIMEOUT where the timeout handler stops
295 * using the waitq before waking us up. To be on the safe side,
296 * ensure the waitq is not in use anymore in this case as well.
298 waitq_complete_wakeup(wq
);
300 irq_spinlock_unlock(&wq
->lock
, false);
303 interrupts_restore(ipl
);
306 errno_t
waitq_sleep_unsafe(waitq_t
*wq
, bool *blocked
)
308 return waitq_sleep_timeout_unsafe(wq
, SYNCH_NO_TIMEOUT
, SYNCH_FLAGS_NONE
, blocked
);
311 /** Internal implementation of waitq_sleep_timeout().
313 * This function implements logic of sleeping in a wait queue.
314 * This call must be preceded by a call to waitq_sleep_prepare()
315 * and followed by a call to waitq_sleep_finish().
317 * @param wq See waitq_sleep_timeout().
318 * @param usec See waitq_sleep_timeout().
319 * @param flags See waitq_sleep_timeout().
321 * @param[out] blocked See waitq_sleep_timeout().
323 * @return See waitq_sleep_timeout().
326 errno_t
waitq_sleep_timeout_unsafe(waitq_t
*wq
, uint32_t usec
, unsigned int flags
, bool *blocked
)
330 /* Checks whether to go to sleep at all */
331 if (wq
->missed_wakeups
) {
332 wq
->missed_wakeups
--;
335 if (PARAM_NON_BLOCKING(flags
, usec
)) {
336 /* Return immediately instead of going to sleep */
342 * Now we are firmly decided to go to sleep.
345 irq_spinlock_lock(&THREAD
->lock
, false);
348 timeout_initialize(&timeout
);
350 THREAD
->sleep_composable
= (flags
& SYNCH_FLAGS_FUTEX
);
352 if (flags
& SYNCH_FLAGS_INTERRUPTIBLE
) {
354 * If the thread was already interrupted,
355 * don't go to sleep at all.
357 if (THREAD
->interrupted
) {
358 irq_spinlock_unlock(&THREAD
->lock
, false);
363 * Set context that will be restored if the sleep
364 * of this thread is ever interrupted.
366 THREAD
->sleep_interruptible
= true;
367 if (!context_save(&THREAD
->sleep_interruption_context
)) {
368 /* Short emulation of scheduler() return code. */
369 THREAD
->last_cycle
= get_cycle();
370 irq_spinlock_unlock(&THREAD
->lock
, false);
372 timeout_unregister(&timeout
);
377 THREAD
->sleep_interruptible
= false;
380 /* We use the timeout variant. */
381 if (!context_save(&THREAD
->sleep_timeout_context
)) {
382 /* Short emulation of scheduler() return code. */
383 THREAD
->last_cycle
= get_cycle();
384 irq_spinlock_unlock(&THREAD
->lock
, false);
388 timeout_register(&timeout
, (uint64_t) usec
, waitq_sleep_timed_out
, THREAD
);
391 list_append(&THREAD
->wq_link
, &wq
->sleepers
);
397 THREAD
->state
= Sleeping
;
398 THREAD
->sleep_queue
= wq
;
401 * Must be before entry to scheduler, because there are multiple
406 irq_spinlock_unlock(&THREAD
->lock
, false);
408 /* wq->lock is released in scheduler_separated_stack() */
412 timeout_unregister(&timeout
);
418 /** Wake up first thread sleeping in a wait queue
420 * Wake up first thread sleeping in a wait queue. This is the SMP- and IRQ-safe
421 * wrapper meant for general use.
423 * Besides its 'normal' wakeup operation, it attempts to unregister possible
426 * @param wq Pointer to wait queue.
427 * @param mode Wakeup mode.
430 void waitq_wakeup(waitq_t
*wq
, wakeup_mode_t mode
)
432 irq_spinlock_lock(&wq
->lock
, true);
433 _waitq_wakeup_unsafe(wq
, mode
);
434 irq_spinlock_unlock(&wq
->lock
, true);
437 /** If there is a wakeup in progress actively waits for it to complete.
439 * The function returns once the concurrently running waitq_wakeup()
440 * exits. It returns immediately if there are no concurrent wakeups
443 * Interrupts must be disabled.
447 * void callback(waitq *wq)
449 * // Do something and notify wait_for_completion() that we're done.
452 * void wait_for_completion(void)
455 * waitq_initialize(&wq);
456 * // Run callback() in the background, pass it wq.
457 * do_asynchronously(callback, &wq);
458 * // Wait for callback() to complete its work.
460 * // callback() completed its work, but it may still be accessing
461 * // wq in waitq_wakeup(). Therefore it is not yet safe to return
462 * // from waitq_sleep() or it would clobber up our stack (where wq
463 * // is stored). waitq_sleep() ensures the wait queue is no longer
464 * // in use by invoking waitq_complete_wakeup() internally.
466 * // waitq_sleep() returned, it is safe to free wq.
470 * @param wq Pointer to a wait queue.
472 static void waitq_complete_wakeup(waitq_t
*wq
)
474 assert(interrupts_disabled());
476 irq_spinlock_lock(&wq
->lock
, false);
477 irq_spinlock_unlock(&wq
->lock
, false);
480 /** Internal SMP- and IRQ-unsafe version of waitq_wakeup()
482 * This is the internal SMP- and IRQ-unsafe version of waitq_wakeup(). It
483 * assumes wq->lock is already locked and interrupts are already disabled.
485 * @param wq Pointer to wait queue.
486 * @param mode If mode is WAKEUP_FIRST, then the longest waiting
487 * thread, if any, is woken up. If mode is WAKEUP_ALL, then
488 * all waiting threads, if any, are woken up. If there are
489 * no waiting threads to be woken up, the missed wakeup is
490 * recorded in the wait queue.
493 void _waitq_wakeup_unsafe(waitq_t
*wq
, wakeup_mode_t mode
)
497 assert(interrupts_disabled());
498 assert(irq_spinlock_locked(&wq
->lock
));
500 if (wq
->ignore_wakeups
> 0) {
501 if (mode
== WAKEUP_FIRST
) {
502 wq
->ignore_wakeups
--;
505 wq
->ignore_wakeups
= 0;
509 if (list_empty(&wq
->sleepers
)) {
510 if (mode
!= WAKEUP_ALL
) {
511 wq
->missed_wakeups
++;
518 thread_t
*thread
= list_get_instance(list_first(&wq
->sleepers
),
522 * Lock the thread prior to removing it from the wq.
523 * This is not necessary because of mutual exclusion
524 * (the link belongs to the wait queue), but because
525 * of synchronization with waitq_sleep_timed_out()
526 * and thread_interrupt_sleep().
528 * In order for these two functions to work, the following
529 * invariant must hold:
531 * thread->sleep_queue != NULL <=> thread sleeps in a wait queue
533 * For an observer who locks the thread, the invariant
534 * holds only when the lock is held prior to removing
535 * it from the wait queue.
538 irq_spinlock_lock(&thread
->lock
, false);
539 list_remove(&thread
->wq_link
);
541 thread
->sleep_queue
= NULL
;
542 irq_spinlock_unlock(&thread
->lock
, false);
544 thread_ready(thread
);
546 if (mode
== WAKEUP_ALL
)
550 /** Get the missed wakeups count.
552 * @param wq Pointer to wait queue.
553 * @return The wait queue's missed_wakeups count.
555 int waitq_count_get(waitq_t
*wq
)
559 irq_spinlock_lock(&wq
->lock
, true);
560 cnt
= wq
->missed_wakeups
;
561 irq_spinlock_unlock(&wq
->lock
, true);
566 /** Set the missed wakeups count.
568 * @param wq Pointer to wait queue.
569 * @param val New value of the missed_wakeups count.
571 void waitq_count_set(waitq_t
*wq
, int val
)
573 irq_spinlock_lock(&wq
->lock
, true);
574 wq
->missed_wakeups
= val
;
575 irq_spinlock_unlock(&wq
->lock
, true);