98feab7933c76a0d178cd7da0115376641e7bbad
[sfrench/cifs-2.6.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/signal.h>
9 #include <linux/sched/debug.h>
10 #include <linux/mm.h>
11 #include <linux/wait.h>
12 #include <linux/hash.h>
13 #include <linux/kthread.h>
14
15 void __init_waitqueue_head(struct wait_queue_head *wq_head, const char *name, struct lock_class_key *key)
16 {
17         spin_lock_init(&wq_head->lock);
18         lockdep_set_class_and_name(&wq_head->lock, key, name);
19         INIT_LIST_HEAD(&wq_head->head);
20 }
21
22 EXPORT_SYMBOL(__init_waitqueue_head);
23
24 void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
25 {
26         unsigned long flags;
27
28         wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
29         spin_lock_irqsave(&wq_head->lock, flags);
30         __add_wait_queue_entry_tail(wq_head, wq_entry);
31         spin_unlock_irqrestore(&wq_head->lock, flags);
32 }
33 EXPORT_SYMBOL(add_wait_queue);
34
35 void add_wait_queue_exclusive(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
36 {
37         unsigned long flags;
38
39         wq_entry->flags |= WQ_FLAG_EXCLUSIVE;
40         spin_lock_irqsave(&wq_head->lock, flags);
41         __add_wait_queue_entry_tail(wq_head, wq_entry);
42         spin_unlock_irqrestore(&wq_head->lock, flags);
43 }
44 EXPORT_SYMBOL(add_wait_queue_exclusive);
45
46 void remove_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
47 {
48         unsigned long flags;
49
50         spin_lock_irqsave(&wq_head->lock, flags);
51         __remove_wait_queue(wq_head, wq_entry);
52         spin_unlock_irqrestore(&wq_head->lock, flags);
53 }
54 EXPORT_SYMBOL(remove_wait_queue);
55
56 /*
57  * Scan threshold to break wait queue walk.
58  * This allows a waker to take a break from holding the
59  * wait queue lock during the wait queue walk.
60  */
61 #define WAITQUEUE_WALK_BREAK_CNT 64
62
63 /*
64  * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
65  * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
66  * number) then we wake all the non-exclusive tasks and one exclusive task.
67  *
68  * There are circumstances in which we can try to wake a task which has already
69  * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
70  * zero in this (rare) case, and we handle it by continuing to scan the queue.
71  */
72 static int __wake_up_common(struct wait_queue_head *wq_head, unsigned int mode,
73                         int nr_exclusive, int wake_flags, void *key,
74                         wait_queue_entry_t *bookmark)
75 {
76         wait_queue_entry_t *curr, *next;
77         int cnt = 0;
78
79         if (bookmark && (bookmark->flags & WQ_FLAG_BOOKMARK)) {
80                 curr = list_next_entry(bookmark, entry);
81
82                 list_del(&bookmark->entry);
83                 bookmark->flags = 0;
84         } else
85                 curr = list_first_entry(&wq_head->head, wait_queue_entry_t, entry);
86
87         if (&curr->entry == &wq_head->head)
88                 return nr_exclusive;
89
90         list_for_each_entry_safe_from(curr, next, &wq_head->head, entry) {
91                 unsigned flags = curr->flags;
92                 int ret;
93
94                 if (flags & WQ_FLAG_BOOKMARK)
95                         continue;
96
97                 ret = curr->func(curr, mode, wake_flags, key);
98                 if (ret < 0)
99                         break;
100                 if (ret && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
101                         break;
102
103                 if (bookmark && (++cnt > WAITQUEUE_WALK_BREAK_CNT) &&
104                                 (&next->entry != &wq_head->head)) {
105                         bookmark->flags = WQ_FLAG_BOOKMARK;
106                         list_add_tail(&bookmark->entry, &next->entry);
107                         break;
108                 }
109         }
110         return nr_exclusive;
111 }
112
113 static void __wake_up_common_lock(struct wait_queue_head *wq_head, unsigned int mode,
114                         int nr_exclusive, int wake_flags, void *key)
115 {
116         unsigned long flags;
117         wait_queue_entry_t bookmark;
118
119         bookmark.flags = 0;
120         bookmark.private = NULL;
121         bookmark.func = NULL;
122         INIT_LIST_HEAD(&bookmark.entry);
123
124         spin_lock_irqsave(&wq_head->lock, flags);
125         nr_exclusive = __wake_up_common(wq_head, mode, nr_exclusive, wake_flags, key, &bookmark);
126         spin_unlock_irqrestore(&wq_head->lock, flags);
127
128         while (bookmark.flags & WQ_FLAG_BOOKMARK) {
129                 spin_lock_irqsave(&wq_head->lock, flags);
130                 nr_exclusive = __wake_up_common(wq_head, mode, nr_exclusive,
131                                                 wake_flags, key, &bookmark);
132                 spin_unlock_irqrestore(&wq_head->lock, flags);
133         }
134 }
135
136 /**
137  * __wake_up - wake up threads blocked on a waitqueue.
138  * @wq_head: the waitqueue
139  * @mode: which threads
140  * @nr_exclusive: how many wake-one or wake-many threads to wake up
141  * @key: is directly passed to the wakeup function
142  *
143  * It may be assumed that this function implies a write memory barrier before
144  * changing the task state if and only if any tasks are woken up.
145  */
146 void __wake_up(struct wait_queue_head *wq_head, unsigned int mode,
147                         int nr_exclusive, void *key)
148 {
149         __wake_up_common_lock(wq_head, mode, nr_exclusive, 0, key);
150 }
151 EXPORT_SYMBOL(__wake_up);
152
153 /*
154  * Same as __wake_up but called with the spinlock in wait_queue_head_t held.
155  */
156 void __wake_up_locked(struct wait_queue_head *wq_head, unsigned int mode, int nr)
157 {
158         __wake_up_common(wq_head, mode, nr, 0, NULL, NULL);
159 }
160 EXPORT_SYMBOL_GPL(__wake_up_locked);
161
162 void __wake_up_locked_key(struct wait_queue_head *wq_head, unsigned int mode, void *key)
163 {
164         __wake_up_common(wq_head, mode, 1, 0, key, NULL);
165 }
166 EXPORT_SYMBOL_GPL(__wake_up_locked_key);
167
168 void __wake_up_locked_key_bookmark(struct wait_queue_head *wq_head,
169                 unsigned int mode, void *key, wait_queue_entry_t *bookmark)
170 {
171         __wake_up_common(wq_head, mode, 1, 0, key, bookmark);
172 }
173 EXPORT_SYMBOL_GPL(__wake_up_locked_key_bookmark);
174
175 /**
176  * __wake_up_sync_key - wake up threads blocked on a waitqueue.
177  * @wq_head: the waitqueue
178  * @mode: which threads
179  * @nr_exclusive: how many wake-one or wake-many threads to wake up
180  * @key: opaque value to be passed to wakeup targets
181  *
182  * The sync wakeup differs that the waker knows that it will schedule
183  * away soon, so while the target thread will be woken up, it will not
184  * be migrated to another CPU - ie. the two threads are 'synchronized'
185  * with each other. This can prevent needless bouncing between CPUs.
186  *
187  * On UP it can prevent extra preemption.
188  *
189  * It may be assumed that this function implies a write memory barrier before
190  * changing the task state if and only if any tasks are woken up.
191  */
192 void __wake_up_sync_key(struct wait_queue_head *wq_head, unsigned int mode,
193                         int nr_exclusive, void *key)
194 {
195         int wake_flags = 1; /* XXX WF_SYNC */
196
197         if (unlikely(!wq_head))
198                 return;
199
200         if (unlikely(nr_exclusive != 1))
201                 wake_flags = 0;
202
203         __wake_up_common_lock(wq_head, mode, nr_exclusive, wake_flags, key);
204 }
205 EXPORT_SYMBOL_GPL(__wake_up_sync_key);
206
207 /*
208  * __wake_up_sync - see __wake_up_sync_key()
209  */
210 void __wake_up_sync(struct wait_queue_head *wq_head, unsigned int mode, int nr_exclusive)
211 {
212         __wake_up_sync_key(wq_head, mode, nr_exclusive, NULL);
213 }
214 EXPORT_SYMBOL_GPL(__wake_up_sync);      /* For internal use only */
215
216 /*
217  * Note: we use "set_current_state()" _after_ the wait-queue add,
218  * because we need a memory barrier there on SMP, so that any
219  * wake-function that tests for the wait-queue being active
220  * will be guaranteed to see waitqueue addition _or_ subsequent
221  * tests in this thread will see the wakeup having taken place.
222  *
223  * The spin_unlock() itself is semi-permeable and only protects
224  * one way (it only protects stuff inside the critical region and
225  * stops them from bleeding out - it would still allow subsequent
226  * loads to move into the critical region).
227  */
228 void
229 prepare_to_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
230 {
231         unsigned long flags;
232
233         wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
234         spin_lock_irqsave(&wq_head->lock, flags);
235         if (list_empty(&wq_entry->entry))
236                 __add_wait_queue(wq_head, wq_entry);
237         set_current_state(state);
238         spin_unlock_irqrestore(&wq_head->lock, flags);
239 }
240 EXPORT_SYMBOL(prepare_to_wait);
241
242 void
243 prepare_to_wait_exclusive(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
244 {
245         unsigned long flags;
246
247         wq_entry->flags |= WQ_FLAG_EXCLUSIVE;
248         spin_lock_irqsave(&wq_head->lock, flags);
249         if (list_empty(&wq_entry->entry))
250                 __add_wait_queue_entry_tail(wq_head, wq_entry);
251         set_current_state(state);
252         spin_unlock_irqrestore(&wq_head->lock, flags);
253 }
254 EXPORT_SYMBOL(prepare_to_wait_exclusive);
255
256 void init_wait_entry(struct wait_queue_entry *wq_entry, int flags)
257 {
258         wq_entry->flags = flags;
259         wq_entry->private = current;
260         wq_entry->func = autoremove_wake_function;
261         INIT_LIST_HEAD(&wq_entry->entry);
262 }
263 EXPORT_SYMBOL(init_wait_entry);
264
265 long prepare_to_wait_event(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
266 {
267         unsigned long flags;
268         long ret = 0;
269
270         spin_lock_irqsave(&wq_head->lock, flags);
271         if (unlikely(signal_pending_state(state, current))) {
272                 /*
273                  * Exclusive waiter must not fail if it was selected by wakeup,
274                  * it should "consume" the condition we were waiting for.
275                  *
276                  * The caller will recheck the condition and return success if
277                  * we were already woken up, we can not miss the event because
278                  * wakeup locks/unlocks the same wq_head->lock.
279                  *
280                  * But we need to ensure that set-condition + wakeup after that
281                  * can't see us, it should wake up another exclusive waiter if
282                  * we fail.
283                  */
284                 list_del_init(&wq_entry->entry);
285                 ret = -ERESTARTSYS;
286         } else {
287                 if (list_empty(&wq_entry->entry)) {
288                         if (wq_entry->flags & WQ_FLAG_EXCLUSIVE)
289                                 __add_wait_queue_entry_tail(wq_head, wq_entry);
290                         else
291                                 __add_wait_queue(wq_head, wq_entry);
292                 }
293                 set_current_state(state);
294         }
295         spin_unlock_irqrestore(&wq_head->lock, flags);
296
297         return ret;
298 }
299 EXPORT_SYMBOL(prepare_to_wait_event);
300
301 /*
302  * Note! These two wait functions are entered with the
303  * wait-queue lock held (and interrupts off in the _irq
304  * case), so there is no race with testing the wakeup
305  * condition in the caller before they add the wait
306  * entry to the wake queue.
307  */
308 int do_wait_intr(wait_queue_head_t *wq, wait_queue_entry_t *wait)
309 {
310         if (likely(list_empty(&wait->entry)))
311                 __add_wait_queue_entry_tail(wq, wait);
312
313         set_current_state(TASK_INTERRUPTIBLE);
314         if (signal_pending(current))
315                 return -ERESTARTSYS;
316
317         spin_unlock(&wq->lock);
318         schedule();
319         spin_lock(&wq->lock);
320         return 0;
321 }
322 EXPORT_SYMBOL(do_wait_intr);
323
324 int do_wait_intr_irq(wait_queue_head_t *wq, wait_queue_entry_t *wait)
325 {
326         if (likely(list_empty(&wait->entry)))
327                 __add_wait_queue_entry_tail(wq, wait);
328
329         set_current_state(TASK_INTERRUPTIBLE);
330         if (signal_pending(current))
331                 return -ERESTARTSYS;
332
333         spin_unlock_irq(&wq->lock);
334         schedule();
335         spin_lock_irq(&wq->lock);
336         return 0;
337 }
338 EXPORT_SYMBOL(do_wait_intr_irq);
339
340 /**
341  * finish_wait - clean up after waiting in a queue
342  * @wq_head: waitqueue waited on
343  * @wq_entry: wait descriptor
344  *
345  * Sets current thread back to running state and removes
346  * the wait descriptor from the given waitqueue if still
347  * queued.
348  */
349 void finish_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
350 {
351         unsigned long flags;
352
353         __set_current_state(TASK_RUNNING);
354         /*
355          * We can check for list emptiness outside the lock
356          * IFF:
357          *  - we use the "careful" check that verifies both
358          *    the next and prev pointers, so that there cannot
359          *    be any half-pending updates in progress on other
360          *    CPU's that we haven't seen yet (and that might
361          *    still change the stack area.
362          * and
363          *  - all other users take the lock (ie we can only
364          *    have _one_ other CPU that looks at or modifies
365          *    the list).
366          */
367         if (!list_empty_careful(&wq_entry->entry)) {
368                 spin_lock_irqsave(&wq_head->lock, flags);
369                 list_del_init(&wq_entry->entry);
370                 spin_unlock_irqrestore(&wq_head->lock, flags);
371         }
372 }
373 EXPORT_SYMBOL(finish_wait);
374
375 int autoremove_wake_function(struct wait_queue_entry *wq_entry, unsigned mode, int sync, void *key)
376 {
377         int ret = default_wake_function(wq_entry, mode, sync, key);
378
379         if (ret)
380                 list_del_init(&wq_entry->entry);
381         return ret;
382 }
383 EXPORT_SYMBOL(autoremove_wake_function);
384
385 static inline bool is_kthread_should_stop(void)
386 {
387         return (current->flags & PF_KTHREAD) && kthread_should_stop();
388 }
389
390 /*
391  * DEFINE_WAIT_FUNC(wait, woken_wake_func);
392  *
393  * add_wait_queue(&wq_head, &wait);
394  * for (;;) {
395  *     if (condition)
396  *         break;
397  *
398  *     p->state = mode;                         condition = true;
399  *     smp_mb(); // A                           smp_wmb(); // C
400  *     if (!wq_entry->flags & WQ_FLAG_WOKEN)    wq_entry->flags |= WQ_FLAG_WOKEN;
401  *         schedule()                           try_to_wake_up();
402  *     p->state = TASK_RUNNING;             ~~~~~~~~~~~~~~~~~~
403  *     wq_entry->flags &= ~WQ_FLAG_WOKEN;               condition = true;
404  *     smp_mb() // B                            smp_wmb(); // C
405  *                                              wq_entry->flags |= WQ_FLAG_WOKEN;
406  * }
407  * remove_wait_queue(&wq_head, &wait);
408  *
409  */
410 long wait_woken(struct wait_queue_entry *wq_entry, unsigned mode, long timeout)
411 {
412         set_current_state(mode); /* A */
413         /*
414          * The above implies an smp_mb(), which matches with the smp_wmb() from
415          * woken_wake_function() such that if we observe WQ_FLAG_WOKEN we must
416          * also observe all state before the wakeup.
417          */
418         if (!(wq_entry->flags & WQ_FLAG_WOKEN) && !is_kthread_should_stop())
419                 timeout = schedule_timeout(timeout);
420         __set_current_state(TASK_RUNNING);
421
422         /*
423          * The below implies an smp_mb(), it too pairs with the smp_wmb() from
424          * woken_wake_function() such that we must either observe the wait
425          * condition being true _OR_ WQ_FLAG_WOKEN such that we will not miss
426          * an event.
427          */
428         smp_store_mb(wq_entry->flags, wq_entry->flags & ~WQ_FLAG_WOKEN); /* B */
429
430         return timeout;
431 }
432 EXPORT_SYMBOL(wait_woken);
433
434 int woken_wake_function(struct wait_queue_entry *wq_entry, unsigned mode, int sync, void *key)
435 {
436         /*
437          * Although this function is called under waitqueue lock, LOCK
438          * doesn't imply write barrier and the users expects write
439          * barrier semantics on wakeup functions.  The following
440          * smp_wmb() is equivalent to smp_wmb() in try_to_wake_up()
441          * and is paired with smp_store_mb() in wait_woken().
442          */
443         smp_wmb(); /* C */
444         wq_entry->flags |= WQ_FLAG_WOKEN;
445
446         return default_wake_function(wq_entry, mode, sync, key);
447 }
448 EXPORT_SYMBOL(woken_wake_function);