source: mainline/kernel/generic/src/synch/waitq.c@ 8ccd2ea

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 8ccd2ea was 5c8ba05, checked in by Jakub Jermar <jakub@…>, 18 years ago

Cleanup the waitq_wakeup() interface.
Replace numeric constants (i.e. 0)
and boolean constants (i.e. false) with
more readable WAKEUP_FIRST. Also change the
type of the second argument of waitq_wakeup()
to a newly introduced type wakeup_mode_t.

Fix behaviour of waitq_wakeup() in case
that WAKEUP_ALL semantics is required
but no threads are sleeping in the wait
queue. This is a similar fix to that of
Jan Hudecek committed in the RCU branch,
but, IMHO, is more straightforward and
also doesn't eat up previous missed
wakeups.

  • Property mode set to 100644
File size: 12.3 KB
RevLine 
[f761f1eb]1/*
[df4ed85]2 * Copyright (c) 2001-2004 Jakub Jermar
[f761f1eb]3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
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.
16 *
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.
27 */
28
[cc73a8a1]29/** @addtogroup sync
[b45c443]30 * @{
31 */
32
[9179d0a]33/**
[b45c443]34 * @file
[9179d0a]35 * @brief Wait queue.
36 *
[e3c762cd]37 * Wait queue is the basic synchronization primitive upon which all
[9179d0a]38 * other synchronization primitives build.
39 *
40 * It allows threads to wait for an event in first-come, first-served
41 * fashion. Conditional operation as well as timeouts and interruptions
42 * are supported.
43 */
44
[f761f1eb]45#include <synch/waitq.h>
[922c7ce]46#include <synch/synch.h>
[f761f1eb]47#include <synch/spinlock.h>
[922c7ce]48#include <proc/thread.h>
[4b2c872d]49#include <proc/scheduler.h>
[f761f1eb]50#include <arch/asm.h>
51#include <arch/types.h>
[922c7ce]52#include <time/timeout.h>
[f761f1eb]53#include <arch.h>
[922c7ce]54#include <context.h>
[5c9a08b]55#include <adt/list.h>
[f761f1eb]56
[203f4c3]57static void waitq_timeouted_sleep(void *data);
58
[922c7ce]59/** Initialize wait queue
60 *
61 * Initialize wait queue.
62 *
63 * @param wq Pointer to wait queue to be initialized.
64 */
[f761f1eb]65void waitq_initialize(waitq_t *wq)
66{
[2d93f1f9]67 spinlock_initialize(&wq->lock, "waitq_lock");
[f761f1eb]68 list_initialize(&wq->head);
69 wq->missed_wakeups = 0;
70}
71
[922c7ce]72/** Handle timeout during waitq_sleep_timeout() call
73 *
74 * This routine is called when waitq_sleep_timeout() timeouts.
75 * Interrupts are disabled.
[f761f1eb]76 *
[922c7ce]77 * It is supposed to try to remove 'its' thread from the wait queue;
78 * it can eventually fail to achieve this goal when these two events
79 * overlap. In that case it behaves just as though there was no
80 * timeout at all.
81 *
82 * @param data Pointer to the thread that called waitq_sleep_timeout().
[f761f1eb]83 */
[203f4c3]84void waitq_timeouted_sleep(void *data)
[f761f1eb]85{
86 thread_t *t = (thread_t *) data;
87 waitq_t *wq;
[05e2a7ad]88 bool do_wakeup = false;
[31d8e10]89 DEADLOCK_PROBE_INIT(p_wqlock);
[f761f1eb]90
91 spinlock_lock(&threads_lock);
[016acbe]92 if (!thread_exists(t))
[f761f1eb]93 goto out;
94
95grab_locks:
96 spinlock_lock(&t->lock);
[5a95b25]97 if ((wq = t->sleep_queue)) { /* assignment */
[f761f1eb]98 if (!spinlock_trylock(&wq->lock)) {
99 spinlock_unlock(&t->lock);
[31d8e10]100 DEADLOCK_PROBE(p_wqlock, DEADLOCK_THRESHOLD);
[05e2a7ad]101 goto grab_locks; /* avoid deadlock */
[f761f1eb]102 }
103
104 list_remove(&t->wq_link);
105 t->saved_context = t->sleep_timeout_context;
[05e2a7ad]106 do_wakeup = true;
[f761f1eb]107 t->sleep_queue = NULL;
[4b74488]108 spinlock_unlock(&wq->lock);
[f761f1eb]109 }
110
[05e2a7ad]111 t->timeout_pending = false;
[f761f1eb]112 spinlock_unlock(&t->lock);
113
[05e2a7ad]114 if (do_wakeup)
115 thread_ready(t);
[f761f1eb]116
117out:
118 spinlock_unlock(&threads_lock);
119}
120
[5573942]121/** Interrupt sleeping thread.
122 *
123 * This routine attempts to interrupt a thread from its sleep in a waitqueue.
124 * If the thread is not found sleeping, no action is taken.
125 *
126 * @param t Thread to be interrupted.
127 */
128void waitq_interrupt_sleep(thread_t *t)
129{
130 waitq_t *wq;
131 bool do_wakeup = false;
132 ipl_t ipl;
[31d8e10]133 DEADLOCK_PROBE_INIT(p_wqlock);
[5573942]134
135 ipl = interrupts_disable();
136 spinlock_lock(&threads_lock);
137 if (!thread_exists(t))
138 goto out;
139
140grab_locks:
141 spinlock_lock(&t->lock);
142 if ((wq = t->sleep_queue)) { /* assignment */
143 if (!(t->sleep_interruptible)) {
144 /*
145 * The sleep cannot be interrupted.
146 */
147 spinlock_unlock(&t->lock);
148 goto out;
149 }
150
151 if (!spinlock_trylock(&wq->lock)) {
152 spinlock_unlock(&t->lock);
[31d8e10]153 DEADLOCK_PROBE(p_wqlock, DEADLOCK_THRESHOLD);
[5573942]154 goto grab_locks; /* avoid deadlock */
155 }
156
157 if (t->timeout_pending && timeout_unregister(&t->sleep_timeout))
158 t->timeout_pending = false;
159
160 list_remove(&t->wq_link);
161 t->saved_context = t->sleep_interruption_context;
162 do_wakeup = true;
163 t->sleep_queue = NULL;
164 spinlock_unlock(&wq->lock);
165 }
166 spinlock_unlock(&t->lock);
167
168 if (do_wakeup)
169 thread_ready(t);
170
171out:
172 spinlock_unlock(&threads_lock);
173 interrupts_restore(ipl);
174}
[203f4c3]175
176/** Sleep until either wakeup, timeout or interruption occurs
[922c7ce]177 *
[116d1ef4]178 * This is a sleep implementation which allows itself to time out or to be
[f761f1eb]179 * interrupted from the sleep, restoring a failover context.
180 *
[c0bc189]181 * Sleepers are organised in a FIFO fashion in a structure called wait queue.
[922c7ce]182 *
[f761f1eb]183 * This function is really basic in that other functions as waitq_sleep()
184 * and all the *_timeout() functions use it.
185 *
[922c7ce]186 * @param wq Pointer to wait queue.
[a783ca4]187 * @param usec Timeout in microseconds.
[116d1ef4]188 * @param flags Specify mode of the sleep.
[922c7ce]189 *
[116d1ef4]190 * The sleep can be interrupted only if the
191 * SYNCH_FLAGS_INTERRUPTIBLE bit is specified in flags.
[6f4495f5]192 *
[116d1ef4]193 * If usec is greater than zero, regardless of the value of the
[4e33b6b]194 * SYNCH_FLAGS_NON_BLOCKING bit in flags, the call will not return until either
195 * timeout, interruption or wakeup comes.
[f761f1eb]196 *
[4e33b6b]197 * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is not set in flags,
198 * the call will not return until wakeup or interruption comes.
[a783ca4]199 *
[4e33b6b]200 * If usec is zero and the SYNCH_FLAGS_NON_BLOCKING bit is set in flags, the
201 * call will immediately return, reporting either success or failure.
[f761f1eb]202 *
[4e33b6b]203 * @return One of: ESYNCH_WOULD_BLOCK, ESYNCH_TIMEOUT, ESYNCH_INTERRUPTED,
204 * ESYNCH_OK_ATOMIC, ESYNCH_OK_BLOCKED.
[922c7ce]205 *
[4e33b6b]206 * @li ESYNCH_WOULD_BLOCK means that the sleep failed because at the time of the
207 * call there was no pending wakeup.
[a783ca4]208 *
[9179d0a]209 * @li ESYNCH_TIMEOUT means that the sleep timed out.
[922c7ce]210 *
[9179d0a]211 * @li ESYNCH_INTERRUPTED means that somebody interrupted the sleeping thread.
[203f4c3]212 *
[9179d0a]213 * @li ESYNCH_OK_ATOMIC means that the sleep succeeded and that there was
[a783ca4]214 * a pending wakeup at the time of the call. The caller was not put
215 * asleep at all.
216 *
[9179d0a]217 * @li ESYNCH_OK_BLOCKED means that the sleep succeeded; the full sleep was
[a783ca4]218 * attempted.
[f761f1eb]219 */
[7f1c620]220int waitq_sleep_timeout(waitq_t *wq, uint32_t usec, int flags)
[f761f1eb]221{
[c0bc189]222 ipl_t ipl;
223 int rc;
[f761f1eb]224
[c0bc189]225 ipl = waitq_sleep_prepare(wq);
[116d1ef4]226 rc = waitq_sleep_timeout_unsafe(wq, usec, flags);
[c0bc189]227 waitq_sleep_finish(wq, rc, ipl);
228 return rc;
229}
230
231/** Prepare to sleep in a waitq.
232 *
233 * This function will return holding the lock of the wait queue
234 * and interrupts disabled.
235 *
236 * @param wq Wait queue.
237 *
238 * @return Interrupt level as it existed on entry to this function.
239 */
240ipl_t waitq_sleep_prepare(waitq_t *wq)
241{
242 ipl_t ipl;
[f761f1eb]243
244restart:
[22f7769]245 ipl = interrupts_disable();
[c0bc189]246
[343fc179]247 if (THREAD) { /* needed during system initiailzation */
248 /*
249 * Busy waiting for a delayed timeout.
250 * This is an important fix for the race condition between
251 * a delayed timeout and a next call to waitq_sleep_timeout().
252 * Simply, the thread is not allowed to go to sleep if
253 * there are timeouts in progress.
254 */
255 spinlock_lock(&THREAD->lock);
256 if (THREAD->timeout_pending) {
257 spinlock_unlock(&THREAD->lock);
258 interrupts_restore(ipl);
259 goto restart;
260 }
[43114c5]261 spinlock_unlock(&THREAD->lock);
[f761f1eb]262 }
[c0bc189]263
[f761f1eb]264 spinlock_lock(&wq->lock);
[c0bc189]265 return ipl;
266}
267
268/** Finish waiting in a wait queue.
269 *
270 * This function restores interrupts to the state that existed prior
271 * to the call to waitq_sleep_prepare(). If necessary, the wait queue
272 * lock is released.
273 *
274 * @param wq Wait queue.
275 * @param rc Return code of waitq_sleep_timeout_unsafe().
276 * @param ipl Interrupt level returned by waitq_sleep_prepare().
277 */
278void waitq_sleep_finish(waitq_t *wq, int rc, ipl_t ipl)
279{
280 switch (rc) {
281 case ESYNCH_WOULD_BLOCK:
282 case ESYNCH_OK_ATOMIC:
283 spinlock_unlock(&wq->lock);
284 break;
285 default:
286 break;
287 }
288 interrupts_restore(ipl);
289}
290
291/** Internal implementation of waitq_sleep_timeout().
292 *
293 * This function implements logic of sleeping in a wait queue.
294 * This call must be preceeded by a call to waitq_sleep_prepare()
295 * and followed by a call to waitq_slee_finish().
296 *
297 * @param wq See waitq_sleep_timeout().
298 * @param usec See waitq_sleep_timeout().
[116d1ef4]299 * @param flags See waitq_sleep_timeout().
[c0bc189]300 *
301 * @return See waitq_sleep_timeout().
302 */
[7f1c620]303int waitq_sleep_timeout_unsafe(waitq_t *wq, uint32_t usec, int flags)
[c0bc189]304{
[f761f1eb]305 /* checks whether to go to sleep at all */
306 if (wq->missed_wakeups) {
307 wq->missed_wakeups--;
308 return ESYNCH_OK_ATOMIC;
309 }
310 else {
[116d1ef4]311 if ((flags & SYNCH_FLAGS_NON_BLOCKING) && (usec == 0)) {
[f761f1eb]312 /* return immediatelly instead of going to sleep */
313 return ESYNCH_WOULD_BLOCK;
314 }
315 }
316
317 /*
318 * Now we are firmly decided to go to sleep.
319 */
[43114c5]320 spinlock_lock(&THREAD->lock);
[203f4c3]321
[116d1ef4]322 if (flags & SYNCH_FLAGS_INTERRUPTIBLE) {
[34dcd3f]323
324 /*
325 * If the thread was already interrupted,
326 * don't go to sleep at all.
327 */
328 if (THREAD->interrupted) {
329 spinlock_unlock(&THREAD->lock);
330 spinlock_unlock(&wq->lock);
331 return ESYNCH_INTERRUPTED;
332 }
333
[116d1ef4]334 /*
335 * Set context that will be restored if the sleep
336 * of this thread is ever interrupted.
337 */
338 THREAD->sleep_interruptible = true;
339 if (!context_save(&THREAD->sleep_interruption_context)) {
340 /* Short emulation of scheduler() return code. */
341 spinlock_unlock(&THREAD->lock);
342 return ESYNCH_INTERRUPTED;
343 }
[34dcd3f]344
[116d1ef4]345 } else {
346 THREAD->sleep_interruptible = false;
[203f4c3]347 }
348
[f761f1eb]349 if (usec) {
350 /* We use the timeout variant. */
[43114c5]351 if (!context_save(&THREAD->sleep_timeout_context)) {
[203f4c3]352 /* Short emulation of scheduler() return code. */
[43114c5]353 spinlock_unlock(&THREAD->lock);
[f761f1eb]354 return ESYNCH_TIMEOUT;
355 }
[05e2a7ad]356 THREAD->timeout_pending = true;
[4e33b6b]357 timeout_register(&THREAD->sleep_timeout, (uint64_t) usec,
[6f4495f5]358 waitq_timeouted_sleep, THREAD);
[f761f1eb]359 }
360
[43114c5]361 list_append(&THREAD->wq_link, &wq->head);
[f761f1eb]362
363 /*
364 * Suspend execution.
365 */
[43114c5]366 THREAD->state = Sleeping;
367 THREAD->sleep_queue = wq;
[f761f1eb]368
[43114c5]369 spinlock_unlock(&THREAD->lock);
[f761f1eb]370
[4e33b6b]371 /* wq->lock is released in scheduler_separated_stack() */
372 scheduler();
[f761f1eb]373
374 return ESYNCH_OK_BLOCKED;
375}
376
377
[922c7ce]378/** Wake up first thread sleeping in a wait queue
379 *
[4e33b6b]380 * Wake up first thread sleeping in a wait queue. This is the SMP- and IRQ-safe
381 * wrapper meant for general use.
[922c7ce]382 *
[4e33b6b]383 * Besides its 'normal' wakeup operation, it attempts to unregister possible
384 * timeout.
[922c7ce]385 *
[5c8ba05]386 * @param wq Pointer to wait queue.
387 * @param mode Wakeup mode.
[f761f1eb]388 */
[5c8ba05]389void waitq_wakeup(waitq_t *wq, wakeup_mode_t mode)
[f761f1eb]390{
[22f7769]391 ipl_t ipl;
[f761f1eb]392
[22f7769]393 ipl = interrupts_disable();
[f761f1eb]394 spinlock_lock(&wq->lock);
395
[5c8ba05]396 _waitq_wakeup_unsafe(wq, mode);
[f761f1eb]397
[5c8ba05]398 spinlock_unlock(&wq->lock);
399 interrupts_restore(ipl);
[f761f1eb]400}
401
[922c7ce]402/** Internal SMP- and IRQ-unsafe version of waitq_wakeup()
403 *
[4e33b6b]404 * This is the internal SMP- and IRQ-unsafe version of waitq_wakeup(). It
405 * assumes wq->lock is already locked and interrupts are already disabled.
[922c7ce]406 *
[5c8ba05]407 * @param wq Pointer to wait queue.
408 * @param mode If mode is WAKEUP_FIRST, then the longest waiting thread,
409 * if any, is woken up. If mode is WAKEUP_ALL, then all
410 * waiting threads, if any, are woken up. If there are no
411 * waiting threads to be woken up, the missed wakeup is
412 * recorded in the wait queue.
[f761f1eb]413 */
[5c8ba05]414void _waitq_wakeup_unsafe(waitq_t *wq, wakeup_mode_t mode)
[f761f1eb]415{
416 thread_t *t;
[5c8ba05]417 count_t count = 0;
[f761f1eb]418
419loop:
420 if (list_empty(&wq->head)) {
421 wq->missed_wakeups++;
[5c8ba05]422 if (count && mode == WAKEUP_ALL)
423 wq->missed_wakeups--;
[f761f1eb]424 return;
425 }
426
[5c8ba05]427 count++;
[f761f1eb]428 t = list_get_instance(wq->head.next, thread_t, wq_link);
429
[4b74488]430 /*
431 * Lock the thread prior to removing it from the wq.
432 * This is not necessary because of mutual exclusion
433 * (the link belongs to the wait queue), but because
434 * of synchronization with waitq_timeouted_sleep()
[b3f8fb7]435 * and thread_interrupt_sleep().
[4b74488]436 *
437 * In order for these two functions to work, the following
438 * invariant must hold:
439 *
440 * t->sleep_queue != NULL <=> t sleeps in a wait queue
441 *
442 * For an observer who locks the thread, the invariant
443 * holds only when the lock is held prior to removing
444 * it from the wait queue.
445 */
[f761f1eb]446 spinlock_lock(&t->lock);
[4b74488]447 list_remove(&t->wq_link);
448
[f761f1eb]449 if (t->timeout_pending && timeout_unregister(&t->sleep_timeout))
[05e2a7ad]450 t->timeout_pending = false;
[f761f1eb]451 t->sleep_queue = NULL;
452 spinlock_unlock(&t->lock);
453
454 thread_ready(t);
455
[5c8ba05]456 if (mode == WAKEUP_ALL)
[05e2a7ad]457 goto loop;
[f761f1eb]458}
[b45c443]459
[cc73a8a1]460/** @}
[b45c443]461 */
Note: See TracBrowser for help on using the repository browser.