sched/wait: Provide infrastructure to deal with nested blocking
[firefly-linux-kernel-4.4.55.git] / kernel / sched / wait.c
1 /*
2  * Generic waiting primitives.
3  *
4  * (C) 2004 Nadia Yvette Chambers, Oracle
5  */
6 #include <linux/init.h>
7 #include <linux/export.h>
8 #include <linux/sched.h>
9 #include <linux/mm.h>
10 #include <linux/wait.h>
11 #include <linux/hash.h>
12
13 void __init_waitqueue_head(wait_queue_head_t *q, const char *name, struct lock_class_key *key)
14 {
15         spin_lock_init(&q->lock);
16         lockdep_set_class_and_name(&q->lock, key, name);
17         INIT_LIST_HEAD(&q->task_list);
18 }
19
20 EXPORT_SYMBOL(__init_waitqueue_head);
21
22 void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
23 {
24         unsigned long flags;
25
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);
30 }
31 EXPORT_SYMBOL(add_wait_queue);
32
33 void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait)
34 {
35         unsigned long flags;
36
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);
41 }
42 EXPORT_SYMBOL(add_wait_queue_exclusive);
43
44 void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
45 {
46         unsigned long flags;
47
48         spin_lock_irqsave(&q->lock, flags);
49         __remove_wait_queue(q, wait);
50         spin_unlock_irqrestore(&q->lock, flags);
51 }
52 EXPORT_SYMBOL(remove_wait_queue);
53
54
55 /*
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.
59  *
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.
63  */
64 static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
65                         int nr_exclusive, int wake_flags, void *key)
66 {
67         wait_queue_t *curr, *next;
68
69         list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
70                 unsigned flags = curr->flags;
71
72                 if (curr->func(curr, mode, wake_flags, key) &&
73                                 (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
74                         break;
75         }
76 }
77
78 /**
79  * __wake_up - wake up threads blocked on a waitqueue.
80  * @q: the 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
84  *
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.
87  */
88 void __wake_up(wait_queue_head_t *q, unsigned int mode,
89                         int nr_exclusive, void *key)
90 {
91         unsigned long flags;
92
93         spin_lock_irqsave(&q->lock, flags);
94         __wake_up_common(q, mode, nr_exclusive, 0, key);
95         spin_unlock_irqrestore(&q->lock, flags);
96 }
97 EXPORT_SYMBOL(__wake_up);
98
99 /*
100  * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
101  */
102 void __wake_up_locked(wait_queue_head_t *q, unsigned int mode, int nr)
103 {
104         __wake_up_common(q, mode, nr, 0, NULL);
105 }
106 EXPORT_SYMBOL_GPL(__wake_up_locked);
107
108 void __wake_up_locked_key(wait_queue_head_t *q, unsigned int mode, void *key)
109 {
110         __wake_up_common(q, mode, 1, 0, key);
111 }
112 EXPORT_SYMBOL_GPL(__wake_up_locked_key);
113
114 /**
115  * __wake_up_sync_key - wake up threads blocked on a waitqueue.
116  * @q: the 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
120  *
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.
125  *
126  * On UP it can prevent extra preemption.
127  *
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.
130  */
131 void __wake_up_sync_key(wait_queue_head_t *q, unsigned int mode,
132                         int nr_exclusive, void *key)
133 {
134         unsigned long flags;
135         int wake_flags = 1; /* XXX WF_SYNC */
136
137         if (unlikely(!q))
138                 return;
139
140         if (unlikely(nr_exclusive != 1))
141                 wake_flags = 0;
142
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);
146 }
147 EXPORT_SYMBOL_GPL(__wake_up_sync_key);
148
149 /*
150  * __wake_up_sync - see __wake_up_sync_key()
151  */
152 void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
153 {
154         __wake_up_sync_key(q, mode, nr_exclusive, NULL);
155 }
156 EXPORT_SYMBOL_GPL(__wake_up_sync);      /* For internal use only */
157
158 /*
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.
164  *
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).
169  */
170 void
171 prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
172 {
173         unsigned long flags;
174
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);
181 }
182 EXPORT_SYMBOL(prepare_to_wait);
183
184 void
185 prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)
186 {
187         unsigned long flags;
188
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);
195 }
196 EXPORT_SYMBOL(prepare_to_wait_exclusive);
197
198 long prepare_to_wait_event(wait_queue_head_t *q, wait_queue_t *wait, int state)
199 {
200         unsigned long flags;
201
202         if (signal_pending_state(state, current))
203                 return -ERESTARTSYS;
204
205         wait->private = current;
206         wait->func = autoremove_wake_function;
207
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);
212                 else
213                         __add_wait_queue(q, wait);
214         }
215         set_current_state(state);
216         spin_unlock_irqrestore(&q->lock, flags);
217
218         return 0;
219 }
220 EXPORT_SYMBOL(prepare_to_wait_event);
221
222 /**
223  * finish_wait - clean up after waiting in a queue
224  * @q: waitqueue waited on
225  * @wait: wait descriptor
226  *
227  * Sets current thread back to running state and removes
228  * the wait descriptor from the given waitqueue if still
229  * queued.
230  */
231 void finish_wait(wait_queue_head_t *q, wait_queue_t *wait)
232 {
233         unsigned long flags;
234
235         __set_current_state(TASK_RUNNING);
236         /*
237          * We can check for list emptiness outside the lock
238          * IFF:
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.
244          * and
245          *  - all other users take the lock (ie we can only
246          *    have _one_ other CPU that looks at or modifies
247          *    the list).
248          */
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);
253         }
254 }
255 EXPORT_SYMBOL(finish_wait);
256
257 /**
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
263  *
264  * Sets current thread back to running state and removes
265  * the wait descriptor from the given waitqueue if still
266  * queued.
267  *
268  * Wakes up the next waiter if the caller is concurrently
269  * woken up through the queue.
270  *
271  * This prevents waiter starvation where an exclusive waiter
272  * aborts and is woken up concurrently and no one wakes up
273  * the next waiter.
274  */
275 void abort_exclusive_wait(wait_queue_head_t *q, wait_queue_t *wait,
276                         unsigned int mode, void *key)
277 {
278         unsigned long flags;
279
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);
287 }
288 EXPORT_SYMBOL(abort_exclusive_wait);
289
290 int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
291 {
292         int ret = default_wake_function(wait, mode, sync, key);
293
294         if (ret)
295                 list_del_init(&wait->task_list);
296         return ret;
297 }
298 EXPORT_SYMBOL(autoremove_wake_function);
299
300
301 /*
302  * DEFINE_WAIT_FUNC(wait, woken_wake_func);
303  *
304  * add_wait_queue(&wq, &wait);
305  * for (;;) {
306  *     if (condition)
307  *         break;
308  *
309  *     p->state = mode;                         condition = true;
310  *     smp_mb(); // A                           smp_wmb(); // C
311  *     if (!wait->flags & WQ_FLAG_WOKEN)        wait->flags |= WQ_FLAG_WOKEN;
312  *         schedule()                           try_to_wake_up();
313  *     p->state = TASK_RUNNING;             ~~~~~~~~~~~~~~~~~~
314  *     wait->flags &= ~WQ_FLAG_WOKEN;           condition = true;
315  *     smp_mb() // B                            smp_wmb(); // C
316  *                                              wait->flags |= WQ_FLAG_WOKEN;
317  * }
318  * remove_wait_queue(&wq, &wait);
319  *
320  */
321 long wait_woken(wait_queue_t *wait, unsigned mode, long timeout)
322 {
323         set_current_state(mode); /* A */
324         /*
325          * The above implies an smp_mb(), which matches with the smp_wmb() from
326          * woken_wake_function() such that if we observe WQ_FLAG_WOKEN we must
327          * also observe all state before the wakeup.
328          */
329         if (!(wait->flags & WQ_FLAG_WOKEN))
330                 timeout = schedule_timeout(timeout);
331         __set_current_state(TASK_RUNNING);
332
333         /*
334          * The below implies an smp_mb(), it too pairs with the smp_wmb() from
335          * woken_wake_function() such that we must either observe the wait
336          * condition being true _OR_ WQ_FLAG_WOKEN such that we will not miss
337          * an event.
338          */
339         set_mb(wait->flags, wait->flags & ~WQ_FLAG_WOKEN); /* B */
340
341         return timeout;
342 }
343 EXPORT_SYMBOL(wait_woken);
344
345 int woken_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
346 {
347         /*
348          * Although this function is called under waitqueue lock, LOCK
349          * doesn't imply write barrier and the users expects write
350          * barrier semantics on wakeup functions.  The following
351          * smp_wmb() is equivalent to smp_wmb() in try_to_wake_up()
352          * and is paired with set_mb() in wait_woken().
353          */
354         smp_wmb(); /* C */
355         wait->flags |= WQ_FLAG_WOKEN;
356
357         return default_wake_function(wait, mode, sync, key);
358 }
359 EXPORT_SYMBOL(woken_wake_function);
360
361 int wake_bit_function(wait_queue_t *wait, unsigned mode, int sync, void *arg)
362 {
363         struct wait_bit_key *key = arg;
364         struct wait_bit_queue *wait_bit
365                 = container_of(wait, struct wait_bit_queue, wait);
366
367         if (wait_bit->key.flags != key->flags ||
368                         wait_bit->key.bit_nr != key->bit_nr ||
369                         test_bit(key->bit_nr, key->flags))
370                 return 0;
371         else
372                 return autoremove_wake_function(wait, mode, sync, key);
373 }
374 EXPORT_SYMBOL(wake_bit_function);
375
376 /*
377  * To allow interruptible waiting and asynchronous (i.e. nonblocking)
378  * waiting, the actions of __wait_on_bit() and __wait_on_bit_lock() are
379  * permitted return codes. Nonzero return codes halt waiting and return.
380  */
381 int __sched
382 __wait_on_bit(wait_queue_head_t *wq, struct wait_bit_queue *q,
383               wait_bit_action_f *action, unsigned mode)
384 {
385         int ret = 0;
386
387         do {
388                 prepare_to_wait(wq, &q->wait, mode);
389                 if (test_bit(q->key.bit_nr, q->key.flags))
390                         ret = (*action)(&q->key);
391         } while (test_bit(q->key.bit_nr, q->key.flags) && !ret);
392         finish_wait(wq, &q->wait);
393         return ret;
394 }
395 EXPORT_SYMBOL(__wait_on_bit);
396
397 int __sched out_of_line_wait_on_bit(void *word, int bit,
398                                     wait_bit_action_f *action, unsigned mode)
399 {
400         wait_queue_head_t *wq = bit_waitqueue(word, bit);
401         DEFINE_WAIT_BIT(wait, word, bit);
402
403         return __wait_on_bit(wq, &wait, action, mode);
404 }
405 EXPORT_SYMBOL(out_of_line_wait_on_bit);
406
407 int __sched out_of_line_wait_on_bit_timeout(
408         void *word, int bit, wait_bit_action_f *action,
409         unsigned mode, unsigned long timeout)
410 {
411         wait_queue_head_t *wq = bit_waitqueue(word, bit);
412         DEFINE_WAIT_BIT(wait, word, bit);
413
414         wait.key.timeout = jiffies + timeout;
415         return __wait_on_bit(wq, &wait, action, mode);
416 }
417 EXPORT_SYMBOL_GPL(out_of_line_wait_on_bit_timeout);
418
419 int __sched
420 __wait_on_bit_lock(wait_queue_head_t *wq, struct wait_bit_queue *q,
421                         wait_bit_action_f *action, unsigned mode)
422 {
423         do {
424                 int ret;
425
426                 prepare_to_wait_exclusive(wq, &q->wait, mode);
427                 if (!test_bit(q->key.bit_nr, q->key.flags))
428                         continue;
429                 ret = action(&q->key);
430                 if (!ret)
431                         continue;
432                 abort_exclusive_wait(wq, &q->wait, mode, &q->key);
433                 return ret;
434         } while (test_and_set_bit(q->key.bit_nr, q->key.flags));
435         finish_wait(wq, &q->wait);
436         return 0;
437 }
438 EXPORT_SYMBOL(__wait_on_bit_lock);
439
440 int __sched out_of_line_wait_on_bit_lock(void *word, int bit,
441                                          wait_bit_action_f *action, unsigned mode)
442 {
443         wait_queue_head_t *wq = bit_waitqueue(word, bit);
444         DEFINE_WAIT_BIT(wait, word, bit);
445
446         return __wait_on_bit_lock(wq, &wait, action, mode);
447 }
448 EXPORT_SYMBOL(out_of_line_wait_on_bit_lock);
449
450 void __wake_up_bit(wait_queue_head_t *wq, void *word, int bit)
451 {
452         struct wait_bit_key key = __WAIT_BIT_KEY_INITIALIZER(word, bit);
453         if (waitqueue_active(wq))
454                 __wake_up(wq, TASK_NORMAL, 1, &key);
455 }
456 EXPORT_SYMBOL(__wake_up_bit);
457
458 /**
459  * wake_up_bit - wake up a waiter on a bit
460  * @word: the word being waited on, a kernel virtual address
461  * @bit: the bit of the word being waited on
462  *
463  * There is a standard hashed waitqueue table for generic use. This
464  * is the part of the hashtable's accessor API that wakes up waiters
465  * on a bit. For instance, if one were to have waiters on a bitflag,
466  * one would call wake_up_bit() after clearing the bit.
467  *
468  * In order for this to function properly, as it uses waitqueue_active()
469  * internally, some kind of memory barrier must be done prior to calling
470  * this. Typically, this will be smp_mb__after_atomic(), but in some
471  * cases where bitflags are manipulated non-atomically under a lock, one
472  * may need to use a less regular barrier, such fs/inode.c's smp_mb(),
473  * because spin_unlock() does not guarantee a memory barrier.
474  */
475 void wake_up_bit(void *word, int bit)
476 {
477         __wake_up_bit(bit_waitqueue(word, bit), word, bit);
478 }
479 EXPORT_SYMBOL(wake_up_bit);
480
481 wait_queue_head_t *bit_waitqueue(void *word, int bit)
482 {
483         const int shift = BITS_PER_LONG == 32 ? 5 : 6;
484         const struct zone *zone = page_zone(virt_to_page(word));
485         unsigned long val = (unsigned long)word << shift | bit;
486
487         return &zone->wait_table[hash_long(val, zone->wait_table_bits)];
488 }
489 EXPORT_SYMBOL(bit_waitqueue);
490
491 /*
492  * Manipulate the atomic_t address to produce a better bit waitqueue table hash
493  * index (we're keying off bit -1, but that would produce a horrible hash
494  * value).
495  */
496 static inline wait_queue_head_t *atomic_t_waitqueue(atomic_t *p)
497 {
498         if (BITS_PER_LONG == 64) {
499                 unsigned long q = (unsigned long)p;
500                 return bit_waitqueue((void *)(q & ~1), q & 1);
501         }
502         return bit_waitqueue(p, 0);
503 }
504
505 static int wake_atomic_t_function(wait_queue_t *wait, unsigned mode, int sync,
506                                   void *arg)
507 {
508         struct wait_bit_key *key = arg;
509         struct wait_bit_queue *wait_bit
510                 = container_of(wait, struct wait_bit_queue, wait);
511         atomic_t *val = key->flags;
512
513         if (wait_bit->key.flags != key->flags ||
514             wait_bit->key.bit_nr != key->bit_nr ||
515             atomic_read(val) != 0)
516                 return 0;
517         return autoremove_wake_function(wait, mode, sync, key);
518 }
519
520 /*
521  * To allow interruptible waiting and asynchronous (i.e. nonblocking) waiting,
522  * the actions of __wait_on_atomic_t() are permitted return codes.  Nonzero
523  * return codes halt waiting and return.
524  */
525 static __sched
526 int __wait_on_atomic_t(wait_queue_head_t *wq, struct wait_bit_queue *q,
527                        int (*action)(atomic_t *), unsigned mode)
528 {
529         atomic_t *val;
530         int ret = 0;
531
532         do {
533                 prepare_to_wait(wq, &q->wait, mode);
534                 val = q->key.flags;
535                 if (atomic_read(val) == 0)
536                         break;
537                 ret = (*action)(val);
538         } while (!ret && atomic_read(val) != 0);
539         finish_wait(wq, &q->wait);
540         return ret;
541 }
542
543 #define DEFINE_WAIT_ATOMIC_T(name, p)                                   \
544         struct wait_bit_queue name = {                                  \
545                 .key = __WAIT_ATOMIC_T_KEY_INITIALIZER(p),              \
546                 .wait   = {                                             \
547                         .private        = current,                      \
548                         .func           = wake_atomic_t_function,       \
549                         .task_list      =                               \
550                                 LIST_HEAD_INIT((name).wait.task_list),  \
551                 },                                                      \
552         }
553
554 __sched int out_of_line_wait_on_atomic_t(atomic_t *p, int (*action)(atomic_t *),
555                                          unsigned mode)
556 {
557         wait_queue_head_t *wq = atomic_t_waitqueue(p);
558         DEFINE_WAIT_ATOMIC_T(wait, p);
559
560         return __wait_on_atomic_t(wq, &wait, action, mode);
561 }
562 EXPORT_SYMBOL(out_of_line_wait_on_atomic_t);
563
564 /**
565  * wake_up_atomic_t - Wake up a waiter on a atomic_t
566  * @p: The atomic_t being waited on, a kernel virtual address
567  *
568  * Wake up anyone waiting for the atomic_t to go to zero.
569  *
570  * Abuse the bit-waker function and its waitqueue hash table set (the atomic_t
571  * check is done by the waiter's wake function, not the by the waker itself).
572  */
573 void wake_up_atomic_t(atomic_t *p)
574 {
575         __wake_up_bit(atomic_t_waitqueue(p), p, WAIT_ATOMIC_T_BIT_NR);
576 }
577 EXPORT_SYMBOL(wake_up_atomic_t);
578
579 __sched int bit_wait(struct wait_bit_key *word)
580 {
581         if (signal_pending_state(current->state, current))
582                 return 1;
583         schedule();
584         return 0;
585 }
586 EXPORT_SYMBOL(bit_wait);
587
588 __sched int bit_wait_io(struct wait_bit_key *word)
589 {
590         if (signal_pending_state(current->state, current))
591                 return 1;
592         io_schedule();
593         return 0;
594 }
595 EXPORT_SYMBOL(bit_wait_io);
596
597 __sched int bit_wait_timeout(struct wait_bit_key *word)
598 {
599         unsigned long now = ACCESS_ONCE(jiffies);
600         if (signal_pending_state(current->state, current))
601                 return 1;
602         if (time_after_eq(now, word->timeout))
603                 return -EAGAIN;
604         schedule_timeout(word->timeout - now);
605         return 0;
606 }
607 EXPORT_SYMBOL_GPL(bit_wait_timeout);
608
609 __sched int bit_wait_io_timeout(struct wait_bit_key *word)
610 {
611         unsigned long now = ACCESS_ONCE(jiffies);
612         if (signal_pending_state(current->state, current))
613                 return 1;
614         if (time_after_eq(now, word->timeout))
615                 return -EAGAIN;
616         io_schedule_timeout(word->timeout - now);
617         return 0;
618 }
619 EXPORT_SYMBOL_GPL(bit_wait_io_timeout);