Commit | Line | Data |
---|---|---|
e7f08ffb | 1 | ==================================== |
c54fce6e | 2 | Concurrency Managed Workqueue (cmwq) |
e7f08ffb | 3 | ==================================== |
c54fce6e | 4 | |
e7f08ffb SF |
5 | :Date: September, 2010 |
6 | :Author: Tejun Heo <tj@kernel.org> | |
7 | :Author: Florian Mickler <florian@mickler.org> | |
c54fce6e TH |
8 | |
9 | ||
e7f08ffb SF |
10 | Introduction |
11 | ============ | |
c54fce6e TH |
12 | |
13 | There are many cases where an asynchronous process execution context | |
14 | is needed and the workqueue (wq) API is the most commonly used | |
15 | mechanism for such cases. | |
16 | ||
17 | When such an asynchronous execution context is needed, a work item | |
18 | describing which function to execute is put on a queue. An | |
19 | independent thread serves as the asynchronous execution context. The | |
20 | queue is called workqueue and the thread is called worker. | |
21 | ||
22 | While there are work items on the workqueue the worker executes the | |
23 | functions associated with the work items one after the other. When | |
24 | there is no work item left on the workqueue the worker becomes idle. | |
25 | When a new work item gets queued, the worker begins executing again. | |
26 | ||
27 | ||
e7f08ffb SF |
28 | Why cmwq? |
29 | ========= | |
c54fce6e TH |
30 | |
31 | In the original wq implementation, a multi threaded (MT) wq had one | |
32 | worker thread per CPU and a single threaded (ST) wq had one worker | |
33 | thread system-wide. A single MT wq needed to keep around the same | |
34 | number of workers as the number of CPUs. The kernel grew a lot of MT | |
35 | wq users over the years and with the number of CPU cores continuously | |
36 | rising, some systems saturated the default 32k PID space just booting | |
37 | up. | |
38 | ||
39 | Although MT wq wasted a lot of resource, the level of concurrency | |
40 | provided was unsatisfactory. The limitation was common to both ST and | |
41 | MT wq albeit less severe on MT. Each wq maintained its own separate | |
47684e11 RD |
42 | worker pool. An MT wq could provide only one execution context per CPU |
43 | while an ST wq one for the whole system. Work items had to compete for | |
c54fce6e TH |
44 | those very limited execution contexts leading to various problems |
45 | including proneness to deadlocks around the single execution context. | |
46 | ||
47 | The tension between the provided level of concurrency and resource | |
48 | usage also forced its users to make unnecessary tradeoffs like libata | |
49 | choosing to use ST wq for polling PIOs and accepting an unnecessary | |
50 | limitation that no two polling PIOs can progress at the same time. As | |
51 | MT wq don't provide much better concurrency, users which require | |
52 | higher level of concurrency, like async or fscache, had to implement | |
53 | their own thread pool. | |
54 | ||
55 | Concurrency Managed Workqueue (cmwq) is a reimplementation of wq with | |
56 | focus on the following goals. | |
57 | ||
58 | * Maintain compatibility with the original workqueue API. | |
59 | ||
60 | * Use per-CPU unified worker pools shared by all wq to provide | |
61 | flexible level of concurrency on demand without wasting a lot of | |
62 | resource. | |
63 | ||
64 | * Automatically regulate worker pool and level of concurrency so that | |
65 | the API users don't need to worry about such details. | |
66 | ||
67 | ||
e7f08ffb SF |
68 | The Design |
69 | ========== | |
c54fce6e TH |
70 | |
71 | In order to ease the asynchronous execution of functions a new | |
72 | abstraction, the work item, is introduced. | |
73 | ||
74 | A work item is a simple struct that holds a pointer to the function | |
75 | that is to be executed asynchronously. Whenever a driver or subsystem | |
76 | wants a function to be executed asynchronously it has to set up a work | |
77 | item pointing to that function and queue that work item on a | |
78 | workqueue. | |
79 | ||
80 | Special purpose threads, called worker threads, execute the functions | |
81 | off of the queue, one after the other. If no work is queued, the | |
82 | worker threads become idle. These worker threads are managed in so | |
546d30c4 | 83 | called worker-pools. |
c54fce6e TH |
84 | |
85 | The cmwq design differentiates between the user-facing workqueues that | |
86 | subsystems and drivers queue work items on and the backend mechanism | |
546d30c4 | 87 | which manages worker-pools and processes the queued work items. |
c54fce6e | 88 | |
546d30c4 L |
89 | There are two worker-pools, one for normal work items and the other |
90 | for high priority ones, for each possible CPU and some extra | |
91 | worker-pools to serve work items queued on unbound workqueues - the | |
92 | number of these backing pools is dynamic. | |
c54fce6e TH |
93 | |
94 | Subsystems and drivers can create and queue work items through special | |
95 | workqueue API functions as they see fit. They can influence some | |
96 | aspects of the way the work items are executed by setting flags on the | |
97 | workqueue they are putting the work item on. These flags include | |
12076373 TH |
98 | things like CPU locality, concurrency limits, priority and more. To |
99 | get a detailed overview refer to the API description of | |
e7f08ffb | 100 | ``alloc_workqueue()`` below. |
c54fce6e | 101 | |
546d30c4 L |
102 | When a work item is queued to a workqueue, the target worker-pool is |
103 | determined according to the queue parameters and workqueue attributes | |
104 | and appended on the shared worklist of the worker-pool. For example, | |
105 | unless specifically overridden, a work item of a bound workqueue will | |
106 | be queued on the worklist of either normal or highpri worker-pool that | |
107 | is associated to the CPU the issuer is running on. | |
c54fce6e TH |
108 | |
109 | For any worker pool implementation, managing the concurrency level | |
110 | (how many execution contexts are active) is an important issue. cmwq | |
111 | tries to keep the concurrency at a minimal but sufficient level. | |
112 | Minimal to save resources and sufficient in that the system is used at | |
113 | its full capacity. | |
114 | ||
546d30c4 L |
115 | Each worker-pool bound to an actual CPU implements concurrency |
116 | management by hooking into the scheduler. The worker-pool is notified | |
3270476a TH |
117 | whenever an active worker wakes up or sleeps and keeps track of the |
118 | number of the currently runnable workers. Generally, work items are | |
119 | not expected to hog a CPU and consume many cycles. That means | |
120 | maintaining just enough concurrency to prevent work processing from | |
121 | stalling should be optimal. As long as there are one or more runnable | |
546d30c4 | 122 | workers on the CPU, the worker-pool doesn't start execution of a new |
3270476a TH |
123 | work, but, when the last running worker goes to sleep, it immediately |
124 | schedules a new worker so that the CPU doesn't sit idle while there | |
125 | are pending work items. This allows using a minimal number of workers | |
126 | without losing execution bandwidth. | |
c54fce6e TH |
127 | |
128 | Keeping idle workers around doesn't cost other than the memory space | |
129 | for kthreads, so cmwq holds onto idle ones for a while before killing | |
130 | them. | |
131 | ||
546d30c4 L |
132 | For unbound workqueues, the number of backing pools is dynamic. |
133 | Unbound workqueue can be assigned custom attributes using | |
e7f08ffb | 134 | ``apply_workqueue_attrs()`` and workqueue will automatically create |
546d30c4 L |
135 | backing worker pools matching the attributes. The responsibility of |
136 | regulating concurrency level is on the users. There is also a flag to | |
137 | mark a bound wq to ignore the concurrency management. Please refer to | |
138 | the API section for details. | |
c54fce6e TH |
139 | |
140 | Forward progress guarantee relies on that workers can be created when | |
141 | more execution contexts are necessary, which in turn is guaranteed | |
142 | through the use of rescue workers. All work items which might be used | |
143 | on code paths that handle memory reclaim are required to be queued on | |
144 | wq's that have a rescue-worker reserved for execution under memory | |
546d30c4 | 145 | pressure. Else it is possible that the worker-pool deadlocks waiting |
c54fce6e TH |
146 | for execution contexts to free up. |
147 | ||
148 | ||
e7f08ffb SF |
149 | Application Programming Interface (API) |
150 | ======================================= | |
c54fce6e | 151 | |
e7f08ffb SF |
152 | ``alloc_workqueue()`` allocates a wq. The original |
153 | ``create_*workqueue()`` functions are deprecated and scheduled for | |
47684e11 | 154 | removal. ``alloc_workqueue()`` takes three arguments - ``@name``, |
e7f08ffb SF |
155 | ``@flags`` and ``@max_active``. ``@name`` is the name of the wq and |
156 | also used as the name of the rescuer thread if there is one. | |
c54fce6e TH |
157 | |
158 | A wq no longer manages execution resources but serves as a domain for | |
e7f08ffb SF |
159 | forward progress guarantee, flush and work item attributes. ``@flags`` |
160 | and ``@max_active`` control how work items are assigned execution | |
c54fce6e TH |
161 | resources, scheduled and executed. |
162 | ||
c54fce6e | 163 | |
e7f08ffb SF |
164 | ``flags`` |
165 | --------- | |
166 | ||
167 | ``WQ_UNBOUND`` | |
168 | Work items queued to an unbound wq are served by the special | |
169 | worker-pools which host workers which are not bound to any | |
170 | specific CPU. This makes the wq behave as a simple execution | |
171 | context provider without concurrency management. The unbound | |
172 | worker-pools try to start execution of work items as soon as | |
173 | possible. Unbound wq sacrifices locality but is useful for | |
174 | the following cases. | |
175 | ||
176 | * Wide fluctuation in the concurrency level requirement is | |
177 | expected and using bound wq may end up creating large number | |
178 | of mostly unused workers across different CPUs as the issuer | |
179 | hops through different CPUs. | |
180 | ||
181 | * Long running CPU intensive workloads which can be better | |
182 | managed by the system scheduler. | |
183 | ||
184 | ``WQ_FREEZABLE`` | |
185 | A freezable wq participates in the freeze phase of the system | |
186 | suspend operations. Work items on the wq are drained and no | |
187 | new work item starts execution until thawed. | |
188 | ||
189 | ``WQ_MEM_RECLAIM`` | |
190 | All wq which might be used in the memory reclaim paths **MUST** | |
191 | have this flag set. The wq is guaranteed to have at least one | |
192 | execution context regardless of memory pressure. | |
193 | ||
194 | ``WQ_HIGHPRI`` | |
195 | Work items of a highpri wq are queued to the highpri | |
196 | worker-pool of the target cpu. Highpri worker-pools are | |
197 | served by worker threads with elevated nice level. | |
198 | ||
199 | Note that normal and highpri worker-pools don't interact with | |
47684e11 | 200 | each other. Each maintains its separate pool of workers and |
e7f08ffb SF |
201 | implements concurrency management among its workers. |
202 | ||
203 | ``WQ_CPU_INTENSIVE`` | |
204 | Work items of a CPU intensive wq do not contribute to the | |
205 | concurrency level. In other words, runnable CPU intensive | |
206 | work items will not prevent other work items in the same | |
207 | worker-pool from starting execution. This is useful for bound | |
208 | work items which are expected to hog CPU cycles so that their | |
209 | execution is regulated by the system scheduler. | |
210 | ||
211 | Although CPU intensive work items don't contribute to the | |
212 | concurrency level, start of their executions is still | |
213 | regulated by the concurrency management and runnable | |
214 | non-CPU-intensive work items can delay execution of CPU | |
215 | intensive work items. | |
216 | ||
217 | This flag is meaningless for unbound wq. | |
218 | ||
219 | Note that the flag ``WQ_NON_REENTRANT`` no longer exists as all | |
220 | workqueues are now non-reentrant - any work item is guaranteed to be | |
221 | executed by at most one worker system-wide at any given time. | |
222 | ||
223 | ||
224 | ``max_active`` | |
225 | -------------- | |
226 | ||
227 | ``@max_active`` determines the maximum number of execution contexts | |
228 | per CPU which can be assigned to the work items of a wq. For example, | |
229 | with ``@max_active`` of 16, at most 16 work items of the wq can be | |
c54fce6e TH |
230 | executing at the same time per CPU. |
231 | ||
e7f08ffb SF |
232 | Currently, for a bound wq, the maximum limit for ``@max_active`` is |
233 | 512 and the default value used when 0 is specified is 256. For an | |
234 | unbound wq, the limit is higher of 512 and 4 * | |
235 | ``num_possible_cpus()``. These values are chosen sufficiently high | |
236 | such that they are not the limiting factor while providing protection | |
237 | in runaway cases. | |
c54fce6e TH |
238 | |
239 | The number of active work items of a wq is usually regulated by the | |
240 | users of the wq, more specifically, by how many work items the users | |
241 | may queue at the same time. Unless there is a specific need for | |
242 | throttling the number of active work items, specifying '0' is | |
243 | recommended. | |
244 | ||
245 | Some users depend on the strict execution ordering of ST wq. The | |
0e0cafcd AP |
246 | combination of ``@max_active`` of 1 and ``WQ_UNBOUND`` used to |
247 | achieve this behavior. Work items on such wq were always queued to the | |
248 | unbound worker-pools and only one work item could be active at any given | |
e7f08ffb | 249 | time thus achieving the same ordering property as ST wq. |
c54fce6e | 250 | |
0e0cafcd | 251 | In the current implementation the above configuration only guarantees |
47684e11 RD |
252 | ST behavior within a given NUMA node. Instead ``alloc_ordered_queue()`` should |
253 | be used to achieve system-wide ST behavior. | |
0e0cafcd | 254 | |
c54fce6e | 255 | |
e7f08ffb SF |
256 | Example Execution Scenarios |
257 | =========================== | |
c54fce6e TH |
258 | |
259 | The following example execution scenarios try to illustrate how cmwq | |
260 | behave under different configurations. | |
261 | ||
262 | Work items w0, w1, w2 are queued to a bound wq q0 on the same CPU. | |
263 | w0 burns CPU for 5ms then sleeps for 10ms then burns CPU for 5ms | |
264 | again before finishing. w1 and w2 burn CPU for 5ms then sleep for | |
265 | 10ms. | |
266 | ||
267 | Ignoring all other tasks, works and processing overhead, and assuming | |
268 | simple FIFO scheduling, the following is one highly simplified version | |
e7f08ffb | 269 | of possible sequences of events with the original wq. :: |
c54fce6e TH |
270 | |
271 | TIME IN MSECS EVENT | |
272 | 0 w0 starts and burns CPU | |
273 | 5 w0 sleeps | |
274 | 15 w0 wakes up and burns CPU | |
275 | 20 w0 finishes | |
276 | 20 w1 starts and burns CPU | |
277 | 25 w1 sleeps | |
278 | 35 w1 wakes up and finishes | |
279 | 35 w2 starts and burns CPU | |
280 | 40 w2 sleeps | |
281 | 50 w2 wakes up and finishes | |
282 | ||
e7f08ffb | 283 | And with cmwq with ``@max_active`` >= 3, :: |
c54fce6e TH |
284 | |
285 | TIME IN MSECS EVENT | |
286 | 0 w0 starts and burns CPU | |
287 | 5 w0 sleeps | |
288 | 5 w1 starts and burns CPU | |
289 | 10 w1 sleeps | |
290 | 10 w2 starts and burns CPU | |
291 | 15 w2 sleeps | |
292 | 15 w0 wakes up and burns CPU | |
293 | 20 w0 finishes | |
294 | 20 w1 wakes up and finishes | |
295 | 25 w2 wakes up and finishes | |
296 | ||
e7f08ffb | 297 | If ``@max_active`` == 2, :: |
c54fce6e TH |
298 | |
299 | TIME IN MSECS EVENT | |
300 | 0 w0 starts and burns CPU | |
301 | 5 w0 sleeps | |
302 | 5 w1 starts and burns CPU | |
303 | 10 w1 sleeps | |
304 | 15 w0 wakes up and burns CPU | |
305 | 20 w0 finishes | |
306 | 20 w1 wakes up and finishes | |
307 | 20 w2 starts and burns CPU | |
308 | 25 w2 sleeps | |
309 | 35 w2 wakes up and finishes | |
310 | ||
311 | Now, let's assume w1 and w2 are queued to a different wq q1 which has | |
e7f08ffb | 312 | ``WQ_CPU_INTENSIVE`` set, :: |
c54fce6e TH |
313 | |
314 | TIME IN MSECS EVENT | |
315 | 0 w0 starts and burns CPU | |
316 | 5 w0 sleeps | |
317 | 5 w1 and w2 start and burn CPU | |
318 | 10 w1 sleeps | |
319 | 15 w2 sleeps | |
320 | 15 w0 wakes up and burns CPU | |
321 | 20 w0 finishes | |
322 | 20 w1 wakes up and finishes | |
323 | 25 w2 wakes up and finishes | |
324 | ||
325 | ||
e7f08ffb SF |
326 | Guidelines |
327 | ========== | |
c54fce6e | 328 | |
e7f08ffb SF |
329 | * Do not forget to use ``WQ_MEM_RECLAIM`` if a wq may process work |
330 | items which are used during memory reclaim. Each wq with | |
331 | ``WQ_MEM_RECLAIM`` set has an execution context reserved for it. If | |
332 | there is dependency among multiple work items used during memory | |
333 | reclaim, they should be queued to separate wq each with | |
334 | ``WQ_MEM_RECLAIM``. | |
c54fce6e TH |
335 | |
336 | * Unless strict ordering is required, there is no need to use ST wq. | |
337 | ||
338 | * Unless there is a specific need, using 0 for @max_active is | |
339 | recommended. In most use cases, concurrency level usually stays | |
340 | well under the default limit. | |
341 | ||
6370a6ad | 342 | * A wq serves as a domain for forward progress guarantee |
e7f08ffb SF |
343 | (``WQ_MEM_RECLAIM``, flush and work item attributes. Work items |
344 | which are not involved in memory reclaim and don't need to be | |
345 | flushed as a part of a group of work items, and don't require any | |
346 | special attribute, can use one of the system wq. There is no | |
347 | difference in execution characteristics between using a dedicated wq | |
348 | and a system wq. | |
c54fce6e TH |
349 | |
350 | * Unless work items are expected to consume a huge amount of CPU | |
351 | cycles, using a bound wq is usually beneficial due to the increased | |
352 | level of locality in wq operations and work item execution. | |
e2de9e08 FM |
353 | |
354 | ||
e7f08ffb SF |
355 | Debugging |
356 | ========= | |
e2de9e08 FM |
357 | |
358 | Because the work functions are executed by generic worker threads | |
359 | there are a few tricks needed to shed some light on misbehaving | |
360 | workqueue users. | |
361 | ||
e7f08ffb | 362 | Worker threads show up in the process list as: :: |
e2de9e08 | 363 | |
e7f08ffb SF |
364 | root 5671 0.0 0.0 0 0 ? S 12:07 0:00 [kworker/0:1] |
365 | root 5672 0.0 0.0 0 0 ? S 12:07 0:00 [kworker/1:2] | |
366 | root 5673 0.0 0.0 0 0 ? S 12:12 0:00 [kworker/0:0] | |
367 | root 5674 0.0 0.0 0 0 ? S 12:13 0:00 [kworker/1:0] | |
e2de9e08 FM |
368 | |
369 | If kworkers are going crazy (using too much cpu), there are two types | |
370 | of possible problems: | |
371 | ||
6888c6f2 | 372 | 1. Something being scheduled in rapid succession |
e2de9e08 FM |
373 | 2. A single work item that consumes lots of cpu cycles |
374 | ||
e7f08ffb | 375 | The first one can be tracked using tracing: :: |
e2de9e08 FM |
376 | |
377 | $ echo workqueue:workqueue_queue_work > /sys/kernel/debug/tracing/set_event | |
378 | $ cat /sys/kernel/debug/tracing/trace_pipe > out.txt | |
379 | (wait a few secs) | |
380 | ^C | |
381 | ||
382 | If something is busy looping on work queueing, it would be dominating | |
383 | the output and the offender can be determined with the work item | |
384 | function. | |
385 | ||
386 | For the second type of problems it should be possible to just check | |
e7f08ffb | 387 | the stack trace of the offending worker thread. :: |
e2de9e08 FM |
388 | |
389 | $ cat /proc/THE_OFFENDING_KWORKER/stack | |
390 | ||
391 | The work item's function should be trivially visible in the stack | |
392 | trace. | |
e7f08ffb SF |
393 | |
394 | ||
395 | Kernel Inline Documentations Reference | |
396 | ====================================== | |
397 | ||
398 | .. kernel-doc:: include/linux/workqueue.h |