2 * Generic waiting primitives.
4 * (C) 2004 Nadia Yvette Chambers, Oracle
6 #include <linux/init.h>
7 #include <linux/export.h>
8 #include <linux/sched.h>
10 #include <linux/wait.h>
11 #include <linux/hash.h>
13 void __init_waitqueue_head(wait_queue_head_t
*q
, const char *name
, struct lock_class_key
*key
)
15 spin_lock_init(&q
->lock
);
16 lockdep_set_class_and_name(&q
->lock
, key
, name
);
17 INIT_LIST_HEAD(&q
->task_list
);
20 EXPORT_SYMBOL(__init_waitqueue_head
);
22 void add_wait_queue(wait_queue_head_t
*q
, wait_queue_t
*wait
)
26 wait
->flags
&= ~WQ_FLAG_EXCLUSIVE
;
27 spin_lock_irqsave(&q
->lock
, flags
);
28 __add_wait_queue(q
, wait
);
29 spin_unlock_irqrestore(&q
->lock
, flags
);
31 EXPORT_SYMBOL(add_wait_queue
);
33 void add_wait_queue_exclusive(wait_queue_head_t
*q
, wait_queue_t
*wait
)
37 wait
->flags
|= WQ_FLAG_EXCLUSIVE
;
38 spin_lock_irqsave(&q
->lock
, flags
);
39 __add_wait_queue_tail(q
, wait
);
40 spin_unlock_irqrestore(&q
->lock
, flags
);
42 EXPORT_SYMBOL(add_wait_queue_exclusive
);
44 void remove_wait_queue(wait_queue_head_t
*q
, wait_queue_t
*wait
)
48 spin_lock_irqsave(&q
->lock
, flags
);
49 __remove_wait_queue(q
, wait
);
50 spin_unlock_irqrestore(&q
->lock
, flags
);
52 EXPORT_SYMBOL(remove_wait_queue
);
56 * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
57 * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
58 * number) then we wake all the non-exclusive tasks and one exclusive task.
60 * There are circumstances in which we can try to wake a task which has already
61 * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
62 * zero in this (rare) case, and we handle it by continuing to scan the queue.
64 static void __wake_up_common(wait_queue_head_t
*q
, unsigned int mode
,
65 int nr_exclusive
, int wake_flags
, void *key
)
67 wait_queue_t
*curr
, *next
;
69 list_for_each_entry_safe(curr
, next
, &q
->task_list
, task_list
) {
70 unsigned flags
= curr
->flags
;
72 if (curr
->func(curr
, mode
, wake_flags
, key
) &&
73 (flags
& WQ_FLAG_EXCLUSIVE
) && !--nr_exclusive
)
79 * __wake_up - wake up threads blocked on a waitqueue.
81 * @mode: which threads
82 * @nr_exclusive: how many wake-one or wake-many threads to wake up
83 * @key: is directly passed to the wakeup function
85 * It may be assumed that this function implies a write memory barrier before
86 * changing the task state if and only if any tasks are woken up.
88 void __wake_up(wait_queue_head_t
*q
, unsigned int mode
,
89 int nr_exclusive
, void *key
)
93 spin_lock_irqsave(&q
->lock
, flags
);
94 __wake_up_common(q
, mode
, nr_exclusive
, 0, key
);
95 spin_unlock_irqrestore(&q
->lock
, flags
);
97 EXPORT_SYMBOL(__wake_up
);
100 * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
102 void __wake_up_locked(wait_queue_head_t
*q
, unsigned int mode
, int nr
)
104 __wake_up_common(q
, mode
, nr
, 0, NULL
);
106 EXPORT_SYMBOL_GPL(__wake_up_locked
);
108 void __wake_up_locked_key(wait_queue_head_t
*q
, unsigned int mode
, void *key
)
110 __wake_up_common(q
, mode
, 1, 0, key
);
112 EXPORT_SYMBOL_GPL(__wake_up_locked_key
);
115 * __wake_up_sync_key - wake up threads blocked on a waitqueue.
117 * @mode: which threads
118 * @nr_exclusive: how many wake-one or wake-many threads to wake up
119 * @key: opaque value to be passed to wakeup targets
121 * The sync wakeup differs that the waker knows that it will schedule
122 * away soon, so while the target thread will be woken up, it will not
123 * be migrated to another CPU - ie. the two threads are 'synchronized'
124 * with each other. This can prevent needless bouncing between CPUs.
126 * On UP it can prevent extra preemption.
128 * It may be assumed that this function implies a write memory barrier before
129 * changing the task state if and only if any tasks are woken up.
131 void __wake_up_sync_key(wait_queue_head_t
*q
, unsigned int mode
,
132 int nr_exclusive
, void *key
)
135 int wake_flags
= 1; /* XXX WF_SYNC */
140 if (unlikely(nr_exclusive
!= 1))
143 spin_lock_irqsave(&q
->lock
, flags
);
144 __wake_up_common(q
, mode
, nr_exclusive
, wake_flags
, key
);
145 spin_unlock_irqrestore(&q
->lock
, flags
);
147 EXPORT_SYMBOL_GPL(__wake_up_sync_key
);
150 * __wake_up_sync - see __wake_up_sync_key()
152 void __wake_up_sync(wait_queue_head_t
*q
, unsigned int mode
, int nr_exclusive
)
154 __wake_up_sync_key(q
, mode
, nr_exclusive
, NULL
);
156 EXPORT_SYMBOL_GPL(__wake_up_sync
); /* For internal use only */
159 * Note: we use "set_current_state()" _after_ the wait-queue add,
160 * because we need a memory barrier there on SMP, so that any
161 * wake-function that tests for the wait-queue being active
162 * will be guaranteed to see waitqueue addition _or_ subsequent
163 * tests in this thread will see the wakeup having taken place.
165 * The spin_unlock() itself is semi-permeable and only protects
166 * one way (it only protects stuff inside the critical region and
167 * stops them from bleeding out - it would still allow subsequent
168 * loads to move into the critical region).
171 prepare_to_wait(wait_queue_head_t
*q
, wait_queue_t
*wait
, int state
)
175 wait
->flags
&= ~WQ_FLAG_EXCLUSIVE
;
176 spin_lock_irqsave(&q
->lock
, flags
);
177 if (list_empty(&wait
->task_list
))
178 __add_wait_queue(q
, wait
);
179 set_current_state(state
);
180 spin_unlock_irqrestore(&q
->lock
, flags
);
182 EXPORT_SYMBOL(prepare_to_wait
);
185 prepare_to_wait_exclusive(wait_queue_head_t
*q
, wait_queue_t
*wait
, int state
)
189 wait
->flags
|= WQ_FLAG_EXCLUSIVE
;
190 spin_lock_irqsave(&q
->lock
, flags
);
191 if (list_empty(&wait
->task_list
))
192 __add_wait_queue_tail(q
, wait
);
193 set_current_state(state
);
194 spin_unlock_irqrestore(&q
->lock
, flags
);
196 EXPORT_SYMBOL(prepare_to_wait_exclusive
);
198 long prepare_to_wait_event(wait_queue_head_t
*q
, wait_queue_t
*wait
, int state
)
202 if (signal_pending_state(state
, current
))
205 wait
->private = current
;
206 wait
->func
= autoremove_wake_function
;
208 spin_lock_irqsave(&q
->lock
, flags
);
209 if (list_empty(&wait
->task_list
)) {
210 if (wait
->flags
& WQ_FLAG_EXCLUSIVE
)
211 __add_wait_queue_tail(q
, wait
);
213 __add_wait_queue(q
, wait
);
215 set_current_state(state
);
216 spin_unlock_irqrestore(&q
->lock
, flags
);
220 EXPORT_SYMBOL(prepare_to_wait_event
);
223 * finish_wait - clean up after waiting in a queue
224 * @q: waitqueue waited on
225 * @wait: wait descriptor
227 * Sets current thread back to running state and removes
228 * the wait descriptor from the given waitqueue if still
231 void finish_wait(wait_queue_head_t
*q
, wait_queue_t
*wait
)
235 __set_current_state(TASK_RUNNING
);
237 * We can check for list emptiness outside the lock
239 * - we use the "careful" check that verifies both
240 * the next and prev pointers, so that there cannot
241 * be any half-pending updates in progress on other
242 * CPU's that we haven't seen yet (and that might
243 * still change the stack area.
245 * - all other users take the lock (ie we can only
246 * have _one_ other CPU that looks at or modifies
249 if (!list_empty_careful(&wait
->task_list
)) {
250 spin_lock_irqsave(&q
->lock
, flags
);
251 list_del_init(&wait
->task_list
);
252 spin_unlock_irqrestore(&q
->lock
, flags
);
255 EXPORT_SYMBOL(finish_wait
);
258 * abort_exclusive_wait - abort exclusive waiting in a queue
259 * @q: waitqueue waited on
260 * @wait: wait descriptor
261 * @mode: runstate of the waiter to be woken
262 * @key: key to identify a wait bit queue or %NULL
264 * Sets current thread back to running state and removes
265 * the wait descriptor from the given waitqueue if still
268 * Wakes up the next waiter if the caller is concurrently
269 * woken up through the queue.
271 * This prevents waiter starvation where an exclusive waiter
272 * aborts and is woken up concurrently and no one wakes up
275 void abort_exclusive_wait(wait_queue_head_t
*q
, wait_queue_t
*wait
,
276 unsigned int mode
, void *key
)
280 __set_current_state(TASK_RUNNING
);
281 spin_lock_irqsave(&q
->lock
, flags
);
282 if (!list_empty(&wait
->task_list
))
283 list_del_init(&wait
->task_list
);
284 else if (waitqueue_active(q
))
285 __wake_up_locked_key(q
, mode
, key
);
286 spin_unlock_irqrestore(&q
->lock
, flags
);
288 EXPORT_SYMBOL(abort_exclusive_wait
);
290 int autoremove_wake_function(wait_queue_t
*wait
, unsigned mode
, int sync
, void *key
)
292 int ret
= default_wake_function(wait
, mode
, sync
, key
);
295 list_del_init(&wait
->task_list
);
298 EXPORT_SYMBOL(autoremove_wake_function
);
300 int wake_bit_function(wait_queue_t
*wait
, unsigned mode
, int sync
, void *arg
)
302 struct wait_bit_key
*key
= arg
;
303 struct wait_bit_queue
*wait_bit
304 = container_of(wait
, struct wait_bit_queue
, wait
);
306 if (wait_bit
->key
.flags
!= key
->flags
||
307 wait_bit
->key
.bit_nr
!= key
->bit_nr
||
308 test_bit(key
->bit_nr
, key
->flags
))
311 return autoremove_wake_function(wait
, mode
, sync
, key
);
313 EXPORT_SYMBOL(wake_bit_function
);
316 * To allow interruptible waiting and asynchronous (i.e. nonblocking)
317 * waiting, the actions of __wait_on_bit() and __wait_on_bit_lock() are
318 * permitted return codes. Nonzero return codes halt waiting and return.
321 __wait_on_bit(wait_queue_head_t
*wq
, struct wait_bit_queue
*q
,
322 wait_bit_action_f
*action
, unsigned mode
)
327 prepare_to_wait(wq
, &q
->wait
, mode
);
328 if (test_bit(q
->key
.bit_nr
, q
->key
.flags
))
329 ret
= (*action
)(&q
->key
);
330 } while (test_bit(q
->key
.bit_nr
, q
->key
.flags
) && !ret
);
331 finish_wait(wq
, &q
->wait
);
334 EXPORT_SYMBOL(__wait_on_bit
);
336 int __sched
out_of_line_wait_on_bit(void *word
, int bit
,
337 wait_bit_action_f
*action
, unsigned mode
)
339 wait_queue_head_t
*wq
= bit_waitqueue(word
, bit
);
340 DEFINE_WAIT_BIT(wait
, word
, bit
);
342 return __wait_on_bit(wq
, &wait
, action
, mode
);
344 EXPORT_SYMBOL(out_of_line_wait_on_bit
);
346 int __sched
out_of_line_wait_on_bit_timeout(
347 void *word
, int bit
, wait_bit_action_f
*action
,
348 unsigned mode
, unsigned long timeout
)
350 wait_queue_head_t
*wq
= bit_waitqueue(word
, bit
);
351 DEFINE_WAIT_BIT(wait
, word
, bit
);
353 wait
.key
.timeout
= jiffies
+ timeout
;
354 return __wait_on_bit(wq
, &wait
, action
, mode
);
356 EXPORT_SYMBOL_GPL(out_of_line_wait_on_bit_timeout
);
359 __wait_on_bit_lock(wait_queue_head_t
*wq
, struct wait_bit_queue
*q
,
360 wait_bit_action_f
*action
, unsigned mode
)
365 prepare_to_wait_exclusive(wq
, &q
->wait
, mode
);
366 if (!test_bit(q
->key
.bit_nr
, q
->key
.flags
))
368 ret
= action(&q
->key
);
371 abort_exclusive_wait(wq
, &q
->wait
, mode
, &q
->key
);
373 } while (test_and_set_bit(q
->key
.bit_nr
, q
->key
.flags
));
374 finish_wait(wq
, &q
->wait
);
377 EXPORT_SYMBOL(__wait_on_bit_lock
);
379 int __sched
out_of_line_wait_on_bit_lock(void *word
, int bit
,
380 wait_bit_action_f
*action
, unsigned mode
)
382 wait_queue_head_t
*wq
= bit_waitqueue(word
, bit
);
383 DEFINE_WAIT_BIT(wait
, word
, bit
);
385 return __wait_on_bit_lock(wq
, &wait
, action
, mode
);
387 EXPORT_SYMBOL(out_of_line_wait_on_bit_lock
);
389 void __wake_up_bit(wait_queue_head_t
*wq
, void *word
, int bit
)
391 struct wait_bit_key key
= __WAIT_BIT_KEY_INITIALIZER(word
, bit
);
392 if (waitqueue_active(wq
))
393 __wake_up(wq
, TASK_NORMAL
, 1, &key
);
395 EXPORT_SYMBOL(__wake_up_bit
);
398 * wake_up_bit - wake up a waiter on a bit
399 * @word: the word being waited on, a kernel virtual address
400 * @bit: the bit of the word being waited on
402 * There is a standard hashed waitqueue table for generic use. This
403 * is the part of the hashtable's accessor API that wakes up waiters
404 * on a bit. For instance, if one were to have waiters on a bitflag,
405 * one would call wake_up_bit() after clearing the bit.
407 * In order for this to function properly, as it uses waitqueue_active()
408 * internally, some kind of memory barrier must be done prior to calling
409 * this. Typically, this will be smp_mb__after_atomic(), but in some
410 * cases where bitflags are manipulated non-atomically under a lock, one
411 * may need to use a less regular barrier, such fs/inode.c's smp_mb(),
412 * because spin_unlock() does not guarantee a memory barrier.
414 void wake_up_bit(void *word
, int bit
)
416 __wake_up_bit(bit_waitqueue(word
, bit
), word
, bit
);
418 EXPORT_SYMBOL(wake_up_bit
);
420 wait_queue_head_t
*bit_waitqueue(void *word
, int bit
)
422 const int shift
= BITS_PER_LONG
== 32 ? 5 : 6;
423 const struct zone
*zone
= page_zone(virt_to_page(word
));
424 unsigned long val
= (unsigned long)word
<< shift
| bit
;
426 return &zone
->wait_table
[hash_long(val
, zone
->wait_table_bits
)];
428 EXPORT_SYMBOL(bit_waitqueue
);
431 * Manipulate the atomic_t address to produce a better bit waitqueue table hash
432 * index (we're keying off bit -1, but that would produce a horrible hash
435 static inline wait_queue_head_t
*atomic_t_waitqueue(atomic_t
*p
)
437 if (BITS_PER_LONG
== 64) {
438 unsigned long q
= (unsigned long)p
;
439 return bit_waitqueue((void *)(q
& ~1), q
& 1);
441 return bit_waitqueue(p
, 0);
444 static int wake_atomic_t_function(wait_queue_t
*wait
, unsigned mode
, int sync
,
447 struct wait_bit_key
*key
= arg
;
448 struct wait_bit_queue
*wait_bit
449 = container_of(wait
, struct wait_bit_queue
, wait
);
450 atomic_t
*val
= key
->flags
;
452 if (wait_bit
->key
.flags
!= key
->flags
||
453 wait_bit
->key
.bit_nr
!= key
->bit_nr
||
454 atomic_read(val
) != 0)
456 return autoremove_wake_function(wait
, mode
, sync
, key
);
460 * To allow interruptible waiting and asynchronous (i.e. nonblocking) waiting,
461 * the actions of __wait_on_atomic_t() are permitted return codes. Nonzero
462 * return codes halt waiting and return.
465 int __wait_on_atomic_t(wait_queue_head_t
*wq
, struct wait_bit_queue
*q
,
466 int (*action
)(atomic_t
*), unsigned mode
)
472 prepare_to_wait(wq
, &q
->wait
, mode
);
474 if (atomic_read(val
) == 0)
476 ret
= (*action
)(val
);
477 } while (!ret
&& atomic_read(val
) != 0);
478 finish_wait(wq
, &q
->wait
);
482 #define DEFINE_WAIT_ATOMIC_T(name, p) \
483 struct wait_bit_queue name = { \
484 .key = __WAIT_ATOMIC_T_KEY_INITIALIZER(p), \
486 .private = current, \
487 .func = wake_atomic_t_function, \
489 LIST_HEAD_INIT((name).wait.task_list), \
493 __sched
int out_of_line_wait_on_atomic_t(atomic_t
*p
, int (*action
)(atomic_t
*),
496 wait_queue_head_t
*wq
= atomic_t_waitqueue(p
);
497 DEFINE_WAIT_ATOMIC_T(wait
, p
);
499 return __wait_on_atomic_t(wq
, &wait
, action
, mode
);
501 EXPORT_SYMBOL(out_of_line_wait_on_atomic_t
);
504 * wake_up_atomic_t - Wake up a waiter on a atomic_t
505 * @p: The atomic_t being waited on, a kernel virtual address
507 * Wake up anyone waiting for the atomic_t to go to zero.
509 * Abuse the bit-waker function and its waitqueue hash table set (the atomic_t
510 * check is done by the waiter's wake function, not the by the waker itself).
512 void wake_up_atomic_t(atomic_t
*p
)
514 __wake_up_bit(atomic_t_waitqueue(p
), p
, WAIT_ATOMIC_T_BIT_NR
);
516 EXPORT_SYMBOL(wake_up_atomic_t
);
518 __sched
int bit_wait(struct wait_bit_key
*word
)
520 if (signal_pending_state(current
->state
, current
))
525 EXPORT_SYMBOL(bit_wait
);
527 __sched
int bit_wait_io(struct wait_bit_key
*word
)
529 if (signal_pending_state(current
->state
, current
))
534 EXPORT_SYMBOL(bit_wait_io
);
536 __sched
int bit_wait_timeout(struct wait_bit_key
*word
)
538 unsigned long now
= ACCESS_ONCE(jiffies
);
539 if (signal_pending_state(current
->state
, current
))
541 if (time_after_eq(now
, word
->timeout
))
543 schedule_timeout(word
->timeout
- now
);
546 EXPORT_SYMBOL_GPL(bit_wait_timeout
);
548 __sched
int bit_wait_io_timeout(struct wait_bit_key
*word
)
550 unsigned long now
= ACCESS_ONCE(jiffies
);
551 if (signal_pending_state(current
->state
, current
))
553 if (time_after_eq(now
, word
->timeout
))
555 io_schedule_timeout(word
->timeout
- now
);
558 EXPORT_SYMBOL_GPL(bit_wait_io_timeout
);