1 ============================================== 1 ================================================
2 Completions - "wait for completion" barrier AP 2 Completions - "wait for completion" barrier APIs
3 ============================================== 3 ================================================
4 4
5 Introduction: 5 Introduction:
6 ------------- 6 -------------
7 7
8 If you have one or more threads that must wait 8 If you have one or more threads that must wait for some kernel activity
9 to have reached a point or a specific state, c 9 to have reached a point or a specific state, completions can provide a
10 race-free solution to this problem. Semantical 10 race-free solution to this problem. Semantically they are somewhat like a
11 pthread_barrier() and have similar use-cases. 11 pthread_barrier() and have similar use-cases.
12 12
13 Completions are a code synchronization mechani 13 Completions are a code synchronization mechanism which is preferable to any
14 misuse of locks/semaphores and busy-loops. Any 14 misuse of locks/semaphores and busy-loops. Any time you think of using
15 yield() or some quirky msleep(1) loop to allow 15 yield() or some quirky msleep(1) loop to allow something else to proceed,
16 you probably want to look into using one of th 16 you probably want to look into using one of the wait_for_completion*()
17 calls and complete() instead. 17 calls and complete() instead.
18 18
19 The advantage of using completions is that the 19 The advantage of using completions is that they have a well defined, focused
20 purpose which makes it very easy to see the in 20 purpose which makes it very easy to see the intent of the code, but they
21 also result in more efficient code as all thre 21 also result in more efficient code as all threads can continue execution
22 until the result is actually needed, and both 22 until the result is actually needed, and both the waiting and the signalling
23 is highly efficient using low level scheduler 23 is highly efficient using low level scheduler sleep/wakeup facilities.
24 24
25 Completions are built on top of the waitqueue 25 Completions are built on top of the waitqueue and wakeup infrastructure of
26 the Linux scheduler. The event the threads on 26 the Linux scheduler. The event the threads on the waitqueue are waiting for
27 is reduced to a simple flag in 'struct complet 27 is reduced to a simple flag in 'struct completion', appropriately called "done".
28 28
29 As completions are scheduling related, the cod 29 As completions are scheduling related, the code can be found in
30 kernel/sched/completion.c. 30 kernel/sched/completion.c.
31 31
32 32
33 Usage: 33 Usage:
34 ------ 34 ------
35 35
36 There are three main parts to using completion 36 There are three main parts to using completions:
37 37
38 - the initialization of the 'struct completio 38 - the initialization of the 'struct completion' synchronization object
39 - the waiting part through a call to one of t 39 - the waiting part through a call to one of the variants of wait_for_completion(),
40 - the signaling side through a call to comple 40 - the signaling side through a call to complete() or complete_all().
41 41
42 There are also some helper functions for check 42 There are also some helper functions for checking the state of completions.
43 Note that while initialization must happen fir 43 Note that while initialization must happen first, the waiting and signaling
44 part can happen in any order. I.e. it's entire 44 part can happen in any order. I.e. it's entirely normal for a thread
45 to have marked a completion as 'done' before a 45 to have marked a completion as 'done' before another thread checks whether
46 it has to wait for it. 46 it has to wait for it.
47 47
48 To use completions you need to #include <linux 48 To use completions you need to #include <linux/completion.h> and
49 create a static or dynamic variable of type 's 49 create a static or dynamic variable of type 'struct completion',
50 which has only two fields:: 50 which has only two fields::
51 51
52 struct completion { 52 struct completion {
53 unsigned int done; 53 unsigned int done;
54 wait_queue_head_t wait; 54 wait_queue_head_t wait;
55 }; 55 };
56 56
57 This provides the ->wait waitqueue to place ta 57 This provides the ->wait waitqueue to place tasks on for waiting (if any), and
58 the ->done completion flag for indicating whet 58 the ->done completion flag for indicating whether it's completed or not.
59 59
60 Completions should be named to refer to the ev 60 Completions should be named to refer to the event that is being synchronized on.
61 A good example is:: 61 A good example is::
62 62
63 wait_for_completion(&early_console_add 63 wait_for_completion(&early_console_added);
64 64
65 complete(&early_console_added); 65 complete(&early_console_added);
66 66
67 Good, intuitive naming (as always) helps code 67 Good, intuitive naming (as always) helps code readability. Naming a completion
68 'complete' is not helpful unless the purpose i 68 'complete' is not helpful unless the purpose is super obvious...
69 69
70 70
71 Initializing completions: 71 Initializing completions:
72 ------------------------- 72 -------------------------
73 73
74 Dynamically allocated completion objects shoul 74 Dynamically allocated completion objects should preferably be embedded in data
75 structures that are assured to be alive for th 75 structures that are assured to be alive for the life-time of the function/driver,
76 to prevent races with asynchronous complete() 76 to prevent races with asynchronous complete() calls from occurring.
77 77
78 Particular care should be taken when using the 78 Particular care should be taken when using the _timeout() or _killable()/_interruptible()
79 variants of wait_for_completion(), as it must 79 variants of wait_for_completion(), as it must be assured that memory de-allocation
80 does not happen until all related activities ( 80 does not happen until all related activities (complete() or reinit_completion())
81 have taken place, even if these wait functions 81 have taken place, even if these wait functions return prematurely due to a timeout
82 or a signal triggering. 82 or a signal triggering.
83 83
84 Initializing of dynamically allocated completi 84 Initializing of dynamically allocated completion objects is done via a call to
85 init_completion():: 85 init_completion()::
86 86
87 init_completion(&dynamic_object->done) 87 init_completion(&dynamic_object->done);
88 88
89 In this call we initialize the waitqueue and s 89 In this call we initialize the waitqueue and set ->done to 0, i.e. "not completed"
90 or "not done". 90 or "not done".
91 91
92 The re-initialization function, reinit_complet 92 The re-initialization function, reinit_completion(), simply resets the
93 ->done field to 0 ("not done"), without touchi 93 ->done field to 0 ("not done"), without touching the waitqueue.
94 Callers of this function must make sure that t 94 Callers of this function must make sure that there are no racy
95 wait_for_completion() calls going on in parall 95 wait_for_completion() calls going on in parallel.
96 96
97 Calling init_completion() on the same completi 97 Calling init_completion() on the same completion object twice is
98 most likely a bug as it re-initializes the que 98 most likely a bug as it re-initializes the queue to an empty queue and
99 enqueued tasks could get "lost" - use reinit_c 99 enqueued tasks could get "lost" - use reinit_completion() in that case,
100 but be aware of other races. 100 but be aware of other races.
101 101
102 For static declaration and initialization, mac 102 For static declaration and initialization, macros are available.
103 103
104 For static (or global) declarations in file sc 104 For static (or global) declarations in file scope you can use
105 DECLARE_COMPLETION():: 105 DECLARE_COMPLETION()::
106 106
107 static DECLARE_COMPLETION(setup_done); 107 static DECLARE_COMPLETION(setup_done);
108 DECLARE_COMPLETION(setup_done); 108 DECLARE_COMPLETION(setup_done);
109 109
110 Note that in this case the completion is boot 110 Note that in this case the completion is boot time (or module load time)
111 initialized to 'not done' and doesn't require 111 initialized to 'not done' and doesn't require an init_completion() call.
112 112
113 When a completion is declared as a local varia 113 When a completion is declared as a local variable within a function,
114 then the initialization should always use DECL 114 then the initialization should always use DECLARE_COMPLETION_ONSTACK()
115 explicitly, not just to make lockdep happy, bu 115 explicitly, not just to make lockdep happy, but also to make it clear
116 that limited scope had been considered and is 116 that limited scope had been considered and is intentional::
117 117
118 DECLARE_COMPLETION_ONSTACK(setup_done) 118 DECLARE_COMPLETION_ONSTACK(setup_done)
119 119
120 Note that when using completion objects as loc 120 Note that when using completion objects as local variables you must be
121 acutely aware of the short life time of the fu 121 acutely aware of the short life time of the function stack: the function
122 must not return to a calling context until all 122 must not return to a calling context until all activities (such as waiting
123 threads) have ceased and the completion object 123 threads) have ceased and the completion object is completely unused.
124 124
125 To emphasise this again: in particular when us 125 To emphasise this again: in particular when using some of the waiting API variants
126 with more complex outcomes, such as the timeou 126 with more complex outcomes, such as the timeout or signalling (_timeout(),
127 _killable() and _interruptible()) variants, th 127 _killable() and _interruptible()) variants, the wait might complete
128 prematurely while the object might still be in 128 prematurely while the object might still be in use by another thread - and a return
129 from the wait_on_completion*() caller function 129 from the wait_on_completion*() caller function will deallocate the function
130 stack and cause subtle data corruption if a co 130 stack and cause subtle data corruption if a complete() is done in some
131 other thread. Simple testing might not trigger 131 other thread. Simple testing might not trigger these kinds of races.
132 132
133 If unsure, use dynamically allocated completio 133 If unsure, use dynamically allocated completion objects, preferably embedded
134 in some other long lived object that has a bor 134 in some other long lived object that has a boringly long life time which
135 exceeds the life time of any helper threads us 135 exceeds the life time of any helper threads using the completion object,
136 or has a lock or other synchronization mechani 136 or has a lock or other synchronization mechanism to make sure complete()
137 is not called on a freed object. 137 is not called on a freed object.
138 138
139 A naive DECLARE_COMPLETION() on the stack trig 139 A naive DECLARE_COMPLETION() on the stack triggers a lockdep warning.
140 140
141 Waiting for completions: 141 Waiting for completions:
142 ------------------------ 142 ------------------------
143 143
144 For a thread to wait for some concurrent activ 144 For a thread to wait for some concurrent activity to finish, it
145 calls wait_for_completion() on the initialized 145 calls wait_for_completion() on the initialized completion structure::
146 146
147 void wait_for_completion(struct comple 147 void wait_for_completion(struct completion *done)
148 148
149 A typical usage scenario is:: 149 A typical usage scenario is::
150 150
151 CPU#1 151 CPU#1 CPU#2
152 152
153 struct completion setup_done; 153 struct completion setup_done;
154 154
155 init_completion(&setup_done); 155 init_completion(&setup_done);
156 initialize_work(...,&setup_done,...); 156 initialize_work(...,&setup_done,...);
157 157
158 /* run non-dependent code */ 158 /* run non-dependent code */ /* do setup */
159 159
160 wait_for_completion(&setup_done); 160 wait_for_completion(&setup_done); complete(&setup_done);
161 161
162 This is not implying any particular order betw 162 This is not implying any particular order between wait_for_completion() and
163 the call to complete() - if the call to comple 163 the call to complete() - if the call to complete() happened before the call
164 to wait_for_completion() then the waiting side 164 to wait_for_completion() then the waiting side simply will continue
165 immediately as all dependencies are satisfied; 165 immediately as all dependencies are satisfied; if not, it will block until
166 completion is signaled by complete(). 166 completion is signaled by complete().
167 167
168 Note that wait_for_completion() is calling spi 168 Note that wait_for_completion() is calling spin_lock_irq()/spin_unlock_irq(),
169 so it can only be called safely when you know 169 so it can only be called safely when you know that interrupts are enabled.
170 Calling it from IRQs-off atomic contexts will 170 Calling it from IRQs-off atomic contexts will result in hard-to-detect
171 spurious enabling of interrupts. 171 spurious enabling of interrupts.
172 172
173 The default behavior is to wait without a time 173 The default behavior is to wait without a timeout and to mark the task as
174 uninterruptible. wait_for_completion() and its 174 uninterruptible. wait_for_completion() and its variants are only safe
175 in process context (as they can sleep) but not 175 in process context (as they can sleep) but not in atomic context,
176 interrupt context, with disabled IRQs, or pree 176 interrupt context, with disabled IRQs, or preemption is disabled - see also
177 try_wait_for_completion() below for handling c 177 try_wait_for_completion() below for handling completion in atomic/interrupt
178 context. 178 context.
179 179
180 As all variants of wait_for_completion() can ( 180 As all variants of wait_for_completion() can (obviously) block for a long
181 time depending on the nature of the activity t 181 time depending on the nature of the activity they are waiting for, so in
182 most cases you probably don't want to call thi 182 most cases you probably don't want to call this with held mutexes.
183 183
184 184
185 wait_for_completion*() variants available: 185 wait_for_completion*() variants available:
186 ------------------------------------------ 186 ------------------------------------------
187 187
188 The below variants all return status and this 188 The below variants all return status and this status should be checked in
189 most(/all) cases - in cases where the status i 189 most(/all) cases - in cases where the status is deliberately not checked you
190 probably want to make a note explaining this ( 190 probably want to make a note explaining this (e.g. see
191 arch/arm/kernel/smp.c:__cpu_up()). 191 arch/arm/kernel/smp.c:__cpu_up()).
192 192
193 A common problem that occurs is to have unclea 193 A common problem that occurs is to have unclean assignment of return types,
194 so take care to assign return-values to variab 194 so take care to assign return-values to variables of the proper type.
195 195
196 Checking for the specific meaning of return va 196 Checking for the specific meaning of return values also has been found
197 to be quite inaccurate, e.g. constructs like:: 197 to be quite inaccurate, e.g. constructs like::
198 198
199 if (!wait_for_completion_interruptible 199 if (!wait_for_completion_interruptible_timeout(...))
200 200
201 ... would execute the same code path for succe 201 ... would execute the same code path for successful completion and for the
202 interrupted case - which is probably not what 202 interrupted case - which is probably not what you want::
203 203
204 int wait_for_completion_interruptible( 204 int wait_for_completion_interruptible(struct completion *done)
205 205
206 This function marks the task TASK_INTERRUPTIBL 206 This function marks the task TASK_INTERRUPTIBLE while it is waiting.
207 If a signal was received while waiting it will 207 If a signal was received while waiting it will return -ERESTARTSYS; 0 otherwise::
208 208
209 unsigned long wait_for_completion_time 209 unsigned long wait_for_completion_timeout(struct completion *done, unsigned long timeout)
210 210
211 The task is marked as TASK_UNINTERRUPTIBLE and 211 The task is marked as TASK_UNINTERRUPTIBLE and will wait at most 'timeout'
212 jiffies. If a timeout occurs it returns 0, els 212 jiffies. If a timeout occurs it returns 0, else the remaining time in
213 jiffies (but at least 1). 213 jiffies (but at least 1).
214 214
215 Timeouts are preferably calculated with msecs_ 215 Timeouts are preferably calculated with msecs_to_jiffies() or usecs_to_jiffies(),
216 to make the code largely HZ-invariant. 216 to make the code largely HZ-invariant.
217 217
218 If the returned timeout value is deliberately 218 If the returned timeout value is deliberately ignored a comment should probably explain
219 why (e.g. see drivers/mfd/wm8350-core.c wm8350 219 why (e.g. see drivers/mfd/wm8350-core.c wm8350_read_auxadc())::
220 220
221 long wait_for_completion_interruptible 221 long wait_for_completion_interruptible_timeout(struct completion *done, unsigned long timeout)
222 222
223 This function passes a timeout in jiffies and 223 This function passes a timeout in jiffies and marks the task as
224 TASK_INTERRUPTIBLE. If a signal was received i 224 TASK_INTERRUPTIBLE. If a signal was received it will return -ERESTARTSYS;
225 otherwise it returns 0 if the completion timed 225 otherwise it returns 0 if the completion timed out, or the remaining time in
226 jiffies if completion occurred. 226 jiffies if completion occurred.
227 227
228 Further variants include _killable which uses 228 Further variants include _killable which uses TASK_KILLABLE as the
229 designated tasks state and will return -ERESTA 229 designated tasks state and will return -ERESTARTSYS if it is interrupted,
230 or 0 if completion was achieved. There is a _ 230 or 0 if completion was achieved. There is a _timeout variant as well::
231 231
232 long wait_for_completion_killable(stru 232 long wait_for_completion_killable(struct completion *done)
233 long wait_for_completion_killable_time 233 long wait_for_completion_killable_timeout(struct completion *done, unsigned long timeout)
234 234
235 The _io variants wait_for_completion_io() beha 235 The _io variants wait_for_completion_io() behave the same as the non-_io
236 variants, except for accounting waiting time a 236 variants, except for accounting waiting time as 'waiting on IO', which has
237 an impact on how the task is accounted in sche 237 an impact on how the task is accounted in scheduling/IO stats::
238 238
239 void wait_for_completion_io(struct com 239 void wait_for_completion_io(struct completion *done)
240 unsigned long wait_for_completion_io_t 240 unsigned long wait_for_completion_io_timeout(struct completion *done, unsigned long timeout)
241 241
242 242
243 Signaling completions: 243 Signaling completions:
244 ---------------------- 244 ----------------------
245 245
246 A thread that wants to signal that the conditi 246 A thread that wants to signal that the conditions for continuation have been
247 achieved calls complete() to signal exactly on 247 achieved calls complete() to signal exactly one of the waiters that it can
248 continue:: 248 continue::
249 249
250 void complete(struct completion *done) 250 void complete(struct completion *done)
251 251
252 ... or calls complete_all() to signal all curr 252 ... or calls complete_all() to signal all current and future waiters::
253 253
254 void complete_all(struct completion *d 254 void complete_all(struct completion *done)
255 255
256 The signaling will work as expected even if co 256 The signaling will work as expected even if completions are signaled before
257 a thread starts waiting. This is achieved by t 257 a thread starts waiting. This is achieved by the waiter "consuming"
258 (decrementing) the done field of 'struct compl 258 (decrementing) the done field of 'struct completion'. Waiting threads
259 wakeup order is the same in which they were en 259 wakeup order is the same in which they were enqueued (FIFO order).
260 260
261 If complete() is called multiple times then th 261 If complete() is called multiple times then this will allow for that number
262 of waiters to continue - each call to complete 262 of waiters to continue - each call to complete() will simply increment the
263 done field. Calling complete_all() multiple ti 263 done field. Calling complete_all() multiple times is a bug though. Both
264 complete() and complete_all() can be called in 264 complete() and complete_all() can be called in IRQ/atomic context safely.
265 265
266 There can only be one thread calling complete( 266 There can only be one thread calling complete() or complete_all() on a
267 particular 'struct completion' at any time - s 267 particular 'struct completion' at any time - serialized through the wait
268 queue spinlock. Any such concurrent calls to c 268 queue spinlock. Any such concurrent calls to complete() or complete_all()
269 probably are a design bug. 269 probably are a design bug.
270 270
271 Signaling completion from IRQ context is fine 271 Signaling completion from IRQ context is fine as it will appropriately
272 lock with spin_lock_irqsave()/spin_unlock_irqr 272 lock with spin_lock_irqsave()/spin_unlock_irqrestore() and it will never
273 sleep. 273 sleep.
274 274
275 275
276 try_wait_for_completion()/completion_done(): 276 try_wait_for_completion()/completion_done():
277 -------------------------------------------- 277 --------------------------------------------
278 278
279 The try_wait_for_completion() function will no 279 The try_wait_for_completion() function will not put the thread on the wait
280 queue but rather returns false if it would nee 280 queue but rather returns false if it would need to enqueue (block) the thread,
281 else it consumes one posted completion and ret 281 else it consumes one posted completion and returns true::
282 282
283 bool try_wait_for_completion(struct co 283 bool try_wait_for_completion(struct completion *done)
284 284
285 Finally, to check the state of a completion wi 285 Finally, to check the state of a completion without changing it in any way,
286 call completion_done(), which returns false if 286 call completion_done(), which returns false if there are no posted
287 completions that were not yet consumed by wait 287 completions that were not yet consumed by waiters (implying that there are
288 waiters) and true otherwise:: 288 waiters) and true otherwise::
289 289
290 bool completion_done(struct completion 290 bool completion_done(struct completion *done)
291 291
292 Both try_wait_for_completion() and completion_ 292 Both try_wait_for_completion() and completion_done() are safe to be called in
293 IRQ or atomic context. 293 IRQ or atomic context.
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.