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
Line 
1/*
2 * Copyright (c) 2001-2004 Jakub Jermar
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
29/** @addtogroup sync
30 * @{
31 */
32
33/**
34 * @file
35 * @brief Wait queue.
36 *
37 * Wait queue is the basic synchronization primitive upon which all
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
45#include <synch/waitq.h>
46#include <synch/synch.h>
47#include <synch/spinlock.h>
48#include <proc/thread.h>
49#include <proc/scheduler.h>
50#include <arch/asm.h>
51#include <arch/types.h>
52#include <time/timeout.h>
53#include <arch.h>
54#include <context.h>
55#include <adt/list.h>
56
57static void waitq_timeouted_sleep(void *data);
58
59/** Initialize wait queue
60 *
61 * Initialize wait queue.
62 *
63 * @param wq Pointer to wait queue to be initialized.
64 */
65void waitq_initialize(waitq_t *wq)
66{
67 spinlock_initialize(&wq->lock, "waitq_lock");
68 list_initialize(&wq->head);
69 wq->missed_wakeups = 0;
70}
71
72/** Handle timeout during waitq_sleep_timeout() call
73 *
74 * This routine is called when waitq_sleep_timeout() timeouts.
75 * Interrupts are disabled.
76 *
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().
83 */
84void waitq_timeouted_sleep(void *data)
85{
86 thread_t *t = (thread_t *) data;
87 waitq_t *wq;
88 bool do_wakeup = false;
89 DEADLOCK_PROBE_INIT(p_wqlock);
90
91 spinlock_lock(&threads_lock);
92 if (!thread_exists(t))
93 goto out;
94
95grab_locks:
96 spinlock_lock(&t->lock);
97 if ((wq = t->sleep_queue)) { /* assignment */
98 if (!spinlock_trylock(&wq->lock)) {
99 spinlock_unlock(&t->lock);
100 DEADLOCK_PROBE(p_wqlock, DEADLOCK_THRESHOLD);
101 goto grab_locks; /* avoid deadlock */
102 }
103
104 list_remove(&t->wq_link);
105 t->saved_context = t->sleep_timeout_context;
106 do_wakeup = true;
107 t->sleep_queue = NULL;
108 spinlock_unlock(&wq->lock);
109 }
110
111 t->timeout_pending = false;
112 spinlock_unlock(&t->lock);
113
114 if (do_wakeup)
115 thread_ready(t);
116
117out:
118 spinlock_unlock(&threads_lock);
119}
120
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;
133 DEADLOCK_PROBE_INIT(p_wqlock);
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);
153 DEADLOCK_PROBE(p_wqlock, DEADLOCK_THRESHOLD);
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}
175
176/** Sleep until either wakeup, timeout or interruption occurs
177 *
178 * This is a sleep implementation which allows itself to time out or to be
179 * interrupted from the sleep, restoring a failover context.
180 *
181 * Sleepers are organised in a FIFO fashion in a structure called wait queue.
182 *
183 * This function is really basic in that other functions as waitq_sleep()
184 * and all the *_timeout() functions use it.
185 *
186 * @param wq Pointer to wait queue.
187 * @param usec Timeout in microseconds.
188 * @param flags Specify mode of the sleep.
189 *
190 * The sleep can be interrupted only if the
191 * SYNCH_FLAGS_INTERRUPTIBLE bit is specified in flags.
192 *
193 * If usec is greater than zero, regardless of the value of the
194 * SYNCH_FLAGS_NON_BLOCKING bit in flags, the call will not return until either
195 * timeout, interruption or wakeup comes.
196 *
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.
199 *
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.
202 *
203 * @return One of: ESYNCH_WOULD_BLOCK, ESYNCH_TIMEOUT, ESYNCH_INTERRUPTED,
204 * ESYNCH_OK_ATOMIC, ESYNCH_OK_BLOCKED.
205 *
206 * @li ESYNCH_WOULD_BLOCK means that the sleep failed because at the time of the
207 * call there was no pending wakeup.
208 *
209 * @li ESYNCH_TIMEOUT means that the sleep timed out.
210 *
211 * @li ESYNCH_INTERRUPTED means that somebody interrupted the sleeping thread.
212 *
213 * @li ESYNCH_OK_ATOMIC means that the sleep succeeded and that there was
214 * a pending wakeup at the time of the call. The caller was not put
215 * asleep at all.
216 *
217 * @li ESYNCH_OK_BLOCKED means that the sleep succeeded; the full sleep was
218 * attempted.
219 */
220int waitq_sleep_timeout(waitq_t *wq, uint32_t usec, int flags)
221{
222 ipl_t ipl;
223 int rc;
224
225 ipl = waitq_sleep_prepare(wq);
226 rc = waitq_sleep_timeout_unsafe(wq, usec, flags);
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;
243
244restart:
245 ipl = interrupts_disable();
246
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 }
261 spinlock_unlock(&THREAD->lock);
262 }
263
264 spinlock_lock(&wq->lock);
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().
299 * @param flags See waitq_sleep_timeout().
300 *
301 * @return See waitq_sleep_timeout().
302 */
303int waitq_sleep_timeout_unsafe(waitq_t *wq, uint32_t usec, int flags)
304{
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 {
311 if ((flags & SYNCH_FLAGS_NON_BLOCKING) && (usec == 0)) {
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 */
320 spinlock_lock(&THREAD->lock);
321
322 if (flags & SYNCH_FLAGS_INTERRUPTIBLE) {
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
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 }
344
345 } else {
346 THREAD->sleep_interruptible = false;
347 }
348
349 if (usec) {
350 /* We use the timeout variant. */
351 if (!context_save(&THREAD->sleep_timeout_context)) {
352 /* Short emulation of scheduler() return code. */
353 spinlock_unlock(&THREAD->lock);
354 return ESYNCH_TIMEOUT;
355 }
356 THREAD->timeout_pending = true;
357 timeout_register(&THREAD->sleep_timeout, (uint64_t) usec,
358 waitq_timeouted_sleep, THREAD);
359 }
360
361 list_append(&THREAD->wq_link, &wq->head);
362
363 /*
364 * Suspend execution.
365 */
366 THREAD->state = Sleeping;
367 THREAD->sleep_queue = wq;
368
369 spinlock_unlock(&THREAD->lock);
370
371 /* wq->lock is released in scheduler_separated_stack() */
372 scheduler();
373
374 return ESYNCH_OK_BLOCKED;
375}
376
377
378/** Wake up first thread sleeping in a wait queue
379 *
380 * Wake up first thread sleeping in a wait queue. This is the SMP- and IRQ-safe
381 * wrapper meant for general use.
382 *
383 * Besides its 'normal' wakeup operation, it attempts to unregister possible
384 * timeout.
385 *
386 * @param wq Pointer to wait queue.
387 * @param mode Wakeup mode.
388 */
389void waitq_wakeup(waitq_t *wq, wakeup_mode_t mode)
390{
391 ipl_t ipl;
392
393 ipl = interrupts_disable();
394 spinlock_lock(&wq->lock);
395
396 _waitq_wakeup_unsafe(wq, mode);
397
398 spinlock_unlock(&wq->lock);
399 interrupts_restore(ipl);
400}
401
402/** Internal SMP- and IRQ-unsafe version of waitq_wakeup()
403 *
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.
406 *
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.
413 */
414void _waitq_wakeup_unsafe(waitq_t *wq, wakeup_mode_t mode)
415{
416 thread_t *t;
417 count_t count = 0;
418
419loop:
420 if (list_empty(&wq->head)) {
421 wq->missed_wakeups++;
422 if (count && mode == WAKEUP_ALL)
423 wq->missed_wakeups--;
424 return;
425 }
426
427 count++;
428 t = list_get_instance(wq->head.next, thread_t, wq_link);
429
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()
435 * and thread_interrupt_sleep().
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 */
446 spinlock_lock(&t->lock);
447 list_remove(&t->wq_link);
448
449 if (t->timeout_pending && timeout_unregister(&t->sleep_timeout))
450 t->timeout_pending = false;
451 t->sleep_queue = NULL;
452 spinlock_unlock(&t->lock);
453
454 thread_ready(t);
455
456 if (mode == WAKEUP_ALL)
457 goto loop;
458}
459
460/** @}
461 */
Note: See TracBrowser for help on using the repository browser.