sched/wait: Break up long wake list walk
[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 /**
169  * __wake_up_sync_key - wake up threads blocked on a waitqueue.
170  * @wq_head: the waitqueue
171  * @mode: which threads
172  * @nr_exclusive: how many wake-one or wake-many threads to wake up
173  * @key: opaque value to be passed to wakeup targets
174  *
175  * The sync wakeup differs that the waker knows that it will schedule
176  * away soon, so while the target thread will be woken up, it will not
177  * be migrated to another CPU - ie. the two threads are 'synchronized'
178  * with each other. This can prevent needless bouncing between CPUs.
179  *
180  * On UP it can prevent extra preemption.
181  *
182  * It may be assumed that this function implies a write memory barrier before
183  * changing the task state if and only if any tasks are woken up.
184  */
185 void __wake_up_sync_key(struct wait_queue_head *wq_head, unsigned int mode,
186                         int nr_exclusive, void *key)
187 {
188         int wake_flags = 1; /* XXX WF_SYNC */
189
190         if (unlikely(!wq_head))
191                 return;
192
193         if (unlikely(nr_exclusive != 1))
194                 wake_flags = 0;
195
196         __wake_up_common_lock(wq_head, mode, nr_exclusive, wake_flags, key);
197 }
198 EXPORT_SYMBOL_GPL(__wake_up_sync_key);
199
200 /*
201  * __wake_up_sync - see __wake_up_sync_key()
202  */
203 void __wake_up_sync(struct wait_queue_head *wq_head, unsigned int mode, int nr_exclusive)
204 {
205         __wake_up_sync_key(wq_head, mode, nr_exclusive, NULL);
206 }
207 EXPORT_SYMBOL_GPL(__wake_up_sync);      /* For internal use only */
208
209 /*
210  * Note: we use "set_current_state()" _after_ the wait-queue add,
211  * because we need a memory barrier there on SMP, so that any
212  * wake-function that tests for the wait-queue being active
213  * will be guaranteed to see waitqueue addition _or_ subsequent
214  * tests in this thread will see the wakeup having taken place.
215  *
216  * The spin_unlock() itself is semi-permeable and only protects
217  * one way (it only protects stuff inside the critical region and
218  * stops them from bleeding out - it would still allow subsequent
219  * loads to move into the critical region).
220  */
221 void
222 prepare_to_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
223 {
224         unsigned long flags;
225
226         wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
227         spin_lock_irqsave(&wq_head->lock, flags);
228         if (list_empty(&wq_entry->entry))
229                 __add_wait_queue(wq_head, wq_entry);
230         set_current_state(state);
231         spin_unlock_irqrestore(&wq_head->lock, flags);
232 }
233 EXPORT_SYMBOL(prepare_to_wait);
234
235 void
236 prepare_to_wait_exclusive(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
237 {
238         unsigned long flags;
239
240         wq_entry->flags |= WQ_FLAG_EXCLUSIVE;
241         spin_lock_irqsave(&wq_head->lock, flags);
242         if (list_empty(&wq_entry->entry))
243                 __add_wait_queue_entry_tail(wq_head, wq_entry);
244         set_current_state(state);
245         spin_unlock_irqrestore(&wq_head->lock, flags);
246 }
247 EXPORT_SYMBOL(prepare_to_wait_exclusive);
248
249 void init_wait_entry(struct wait_queue_entry *wq_entry, int flags)
250 {
251         wq_entry->flags = flags;
252         wq_entry->private = current;
253         wq_entry->func = autoremove_wake_function;
254         INIT_LIST_HEAD(&wq_entry->entry);
255 }
256 EXPORT_SYMBOL(init_wait_entry);
257
258 long prepare_to_wait_event(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
259 {
260         unsigned long flags;
261         long ret = 0;
262
263         spin_lock_irqsave(&wq_head->lock, flags);
264         if (unlikely(signal_pending_state(state, current))) {
265                 /*
266                  * Exclusive waiter must not fail if it was selected by wakeup,
267                  * it should "consume" the condition we were waiting for.
268                  *
269                  * The caller will recheck the condition and return success if
270                  * we were already woken up, we can not miss the event because
271                  * wakeup locks/unlocks the same wq_head->lock.
272                  *
273                  * But we need to ensure that set-condition + wakeup after that
274                  * can't see us, it should wake up another exclusive waiter if
275                  * we fail.
276                  */
277                 list_del_init(&wq_entry->entry);
278                 ret = -ERESTARTSYS;
279         } else {
280                 if (list_empty(&wq_entry->entry)) {
281                         if (wq_entry->flags & WQ_FLAG_EXCLUSIVE)
282                                 __add_wait_queue_entry_tail(wq_head, wq_entry);
283                         else
284                                 __add_wait_queue(wq_head, wq_entry);
285                 }
286                 set_current_state(state);
287         }
288         spin_unlock_irqrestore(&wq_head->lock, flags);
289
290         return ret;
291 }
292 EXPORT_SYMBOL(prepare_to_wait_event);
293
294 /*
295  * Note! These two wait functions are entered with the
296  * wait-queue lock held (and interrupts off in the _irq
297  * case), so there is no race with testing the wakeup
298  * condition in the caller before they add the wait
299  * entry to the wake queue.
300  */
301 int do_wait_intr(wait_queue_head_t *wq, wait_queue_entry_t *wait)
302 {
303         if (likely(list_empty(&wait->entry)))
304                 __add_wait_queue_entry_tail(wq, wait);
305
306         set_current_state(TASK_INTERRUPTIBLE);
307         if (signal_pending(current))
308                 return -ERESTARTSYS;
309
310         spin_unlock(&wq->lock);
311         schedule();
312         spin_lock(&wq->lock);
313         return 0;
314 }
315 EXPORT_SYMBOL(do_wait_intr);
316
317 int do_wait_intr_irq(wait_queue_head_t *wq, wait_queue_entry_t *wait)
318 {
319         if (likely(list_empty(&wait->entry)))
320                 __add_wait_queue_entry_tail(wq, wait);
321
322         set_current_state(TASK_INTERRUPTIBLE);
323         if (signal_pending(current))
324                 return -ERESTARTSYS;
325
326         spin_unlock_irq(&wq->lock);
327         schedule();
328         spin_lock_irq(&wq->lock);
329         return 0;
330 }
331 EXPORT_SYMBOL(do_wait_intr_irq);
332
333 /**
334  * finish_wait - clean up after waiting in a queue
335  * @wq_head: waitqueue waited on
336  * @wq_entry: wait descriptor
337  *
338  * Sets current thread back to running state and removes
339  * the wait descriptor from the given waitqueue if still
340  * queued.
341  */
342 void finish_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
343 {
344         unsigned long flags;
345
346         __set_current_state(TASK_RUNNING);
347         /*
348          * We can check for list emptiness outside the lock
349          * IFF:
350          *  - we use the "careful" check that verifies both
351          *    the next and prev pointers, so that there cannot
352          *    be any half-pending updates in progress on other
353          *    CPU's that we haven't seen yet (and that might
354          *    still change the stack area.
355          * and
356          *  - all other users take the lock (ie we can only
357          *    have _one_ other CPU that looks at or modifies
358          *    the list).
359          */
360         if (!list_empty_careful(&wq_entry->entry)) {
361                 spin_lock_irqsave(&wq_head->lock, flags);
362                 list_del_init(&wq_entry->entry);
363                 spin_unlock_irqrestore(&wq_head->lock, flags);
364         }
365 }
366 EXPORT_SYMBOL(finish_wait);
367
368 int autoremove_wake_function(struct wait_queue_entry *wq_entry, unsigned mode, int sync, void *key)
369 {
370         int ret = default_wake_function(wq_entry, mode, sync, key);
371
372         if (ret)
373                 list_del_init(&wq_entry->entry);
374         return ret;
375 }
376 EXPORT_SYMBOL(autoremove_wake_function);
377
378 static inline bool is_kthread_should_stop(void)
379 {
380         return (current->flags & PF_KTHREAD) && kthread_should_stop();
381 }
382
383 /*
384  * DEFINE_WAIT_FUNC(wait, woken_wake_func);
385  *
386  * add_wait_queue(&wq_head, &wait);
387  * for (;;) {
388  *     if (condition)
389  *         break;
390  *
391  *     p->state = mode;                         condition = true;
392  *     smp_mb(); // A                           smp_wmb(); // C
393  *     if (!wq_entry->flags & WQ_FLAG_WOKEN)    wq_entry->flags |= WQ_FLAG_WOKEN;
394  *         schedule()                           try_to_wake_up();
395  *     p->state = TASK_RUNNING;             ~~~~~~~~~~~~~~~~~~
396  *     wq_entry->flags &= ~WQ_FLAG_WOKEN;               condition = true;
397  *     smp_mb() // B                            smp_wmb(); // C
398  *                                              wq_entry->flags |= WQ_FLAG_WOKEN;
399  * }
400  * remove_wait_queue(&wq_head, &wait);
401  *
402  */
403 long wait_woken(struct wait_queue_entry *wq_entry, unsigned mode, long timeout)
404 {
405         set_current_state(mode); /* A */
406         /*
407          * The above implies an smp_mb(), which matches with the smp_wmb() from
408          * woken_wake_function() such that if we observe WQ_FLAG_WOKEN we must
409          * also observe all state before the wakeup.
410          */
411         if (!(wq_entry->flags & WQ_FLAG_WOKEN) && !is_kthread_should_stop())
412                 timeout = schedule_timeout(timeout);
413         __set_current_state(TASK_RUNNING);
414
415         /*
416          * The below implies an smp_mb(), it too pairs with the smp_wmb() from
417          * woken_wake_function() such that we must either observe the wait
418          * condition being true _OR_ WQ_FLAG_WOKEN such that we will not miss
419          * an event.
420          */
421         smp_store_mb(wq_entry->flags, wq_entry->flags & ~WQ_FLAG_WOKEN); /* B */
422
423         return timeout;
424 }
425 EXPORT_SYMBOL(wait_woken);
426
427 int woken_wake_function(struct wait_queue_entry *wq_entry, unsigned mode, int sync, void *key)
428 {
429         /*
430          * Although this function is called under waitqueue lock, LOCK
431          * doesn't imply write barrier and the users expects write
432          * barrier semantics on wakeup functions.  The following
433          * smp_wmb() is equivalent to smp_wmb() in try_to_wake_up()
434          * and is paired with smp_store_mb() in wait_woken().
435          */
436         smp_wmb(); /* C */
437         wq_entry->flags |= WQ_FLAG_WOKEN;
438
439         return default_wake_function(wq_entry, mode, sync, key);
440 }
441 EXPORT_SYMBOL(woken_wake_function);