1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
|
/*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
*/
/* Use a define instead of `#pragma once` because of `bmesh_iterators_inline.h` */
#ifndef __BLI_TASK_H__
#define __BLI_TASK_H__
#include <string.h> /* for memset() */
struct ListBase;
/** \file
* \ingroup bli
*/
#include "BLI_threads.h"
#include "BLI_utildefines.h"
#ifdef __cplusplus
extern "C" {
#endif
struct BLI_mempool;
/* Task Scheduler
*
* Central scheduler that holds running threads ready to execute tasks. A single
* queue holds the task from all pools.
*
* Init/exit must be called before/after any task pools are created/freed, and
* must be called from the main threads. All other scheduler and pool functions
* are thread-safe. */
void BLI_task_scheduler_init(void);
void BLI_task_scheduler_exit(void);
int BLI_task_scheduler_num_threads(void);
/* Task Pool
*
* Pool of tasks that will be executed by the central task scheduler. For each
* pool, we can wait for all tasks to be done, or cancel them before they are
* done.
*
* Running tasks may spawn new tasks.
*
* Pools may be nested, i.e. a thread running a task can create another task
* pool with smaller tasks. When other threads are busy they will continue
* working on their own tasks, if not they will join in, no new threads will
* be launched.
*/
typedef enum TaskPriority {
TASK_PRIORITY_LOW,
TASK_PRIORITY_HIGH,
} TaskPriority;
/**
* Task isolation helps avoid unexpected task scheduling decisions that can lead to bugs if wrong
* assumptions were made. Typically that happens when doing "nested threading", i.e. one thread
* schedules a bunch of main-tasks and those spawn new sub-tasks.
*
* What can happen is that when a main-task waits for its sub-tasks to complete on other threads,
* another main-task is scheduled within the already running main-task. Generally, this is good,
* because it leads to better performance. However, sometimes code (often unintentionally) makes
* the assumption that at most one main-task runs on a thread at a time.
*
* The bugs often show themselves in two ways:
* - Deadlock, when a main-task holds a mutex while waiting for its sub-tasks to complete.
* - Data corruption, when a main-task makes wrong assumptions about a thread-local variable.
*
* Task isolation can avoid these bugs by making sure that a main-task does not start executing
* another main-task while waiting for its sub-tasks. More precisely, a function that runs in an
* isolated region is only allowed to run sub-tasks that were spawned in the same isolated region.
*
* Unfortunately, incorrect use of task isolation can lead to deadlocks itself. This can happen
* when threading primitives are used that separate spawning tasks from executing them. The problem
* occurs when a task is spawned in one isolated region while the tasks are waited for in another
* isolated region. In this setup, the thread that is waiting for the spawned tasks to complete
* cannot run the tasks itself. On a single thread, that causes a deadlock already. When there are
* multiple threads, another thread will typically run the task and avoid the deadlock. However, if
* this situation happens on all threads at the same time, all threads will deadlock. This happened
* in T88598.
*/
typedef enum TaskIsolation {
/* Do not use task isolation. Always use this when tasks are pushed recursively. */
TASK_ISOLATION_OFF,
/* Run each task in its own isolated region. */
TASK_ISOLATION_ON,
} TaskIsolation;
typedef struct TaskPool TaskPool;
typedef void (*TaskRunFunction)(TaskPool *__restrict pool, void *taskdata);
typedef void (*TaskFreeFunction)(TaskPool *__restrict pool, void *taskdata);
/* Regular task pool that immediately starts executing tasks as soon as they
* are pushed, either on the current or another thread. */
TaskPool *BLI_task_pool_create(void *userdata,
TaskPriority priority,
TaskIsolation task_isolation);
/* Background: always run tasks in a background thread, never immediately
* execute them. For running background jobs. */
TaskPool *BLI_task_pool_create_background(void *userdata,
TaskPriority priority,
TaskIsolation task_isolation);
/* Background Serial: run tasks one after the other in the background,
* without parallelization between the tasks. */
TaskPool *BLI_task_pool_create_background_serial(void *userdata, TaskPriority priority);
/* Suspended: don't execute tasks until work_and_wait is called. This is slower
* as threads can't immediately start working. But it can be used if the data
* structures the threads operate on are not fully initialized until all tasks
* are created. */
TaskPool *BLI_task_pool_create_suspended(void *userdata,
TaskPriority priority,
TaskIsolation task_isolation);
/* No threads: immediately executes tasks on the same thread. For debugging. */
TaskPool *BLI_task_pool_create_no_threads(void *userdata);
void BLI_task_pool_free(TaskPool *pool);
void BLI_task_pool_push(TaskPool *pool,
TaskRunFunction run,
void *taskdata,
bool free_taskdata,
TaskFreeFunction freedata);
/* work and wait until all tasks are done */
void BLI_task_pool_work_and_wait(TaskPool *pool);
/* cancel all tasks, keep worker threads running */
void BLI_task_pool_cancel(TaskPool *pool);
/* for worker threads, test if current task pool canceled. this function may
* only be called from worker threads and pool must be the task pool that the
* thread is currently executing a task from. */
bool BLI_task_pool_current_canceled(TaskPool *pool);
/* optional userdata pointer to pass along to run function */
void *BLI_task_pool_user_data(TaskPool *pool);
/* optional mutex to use from run function */
ThreadMutex *BLI_task_pool_user_mutex(TaskPool *pool);
/* Parallel for routines */
/* Per-thread specific data passed to the callback. */
typedef struct TaskParallelTLS {
/* Copy of user-specifier chunk, which is copied from original chunk to all
* worker threads. This is similar to OpenMP's firstprivate.
*/
void *userdata_chunk;
} TaskParallelTLS;
typedef void (*TaskParallelRangeFunc)(void *__restrict userdata,
const int iter,
const TaskParallelTLS *__restrict tls);
typedef void (*TaskParallelReduceFunc)(const void *__restrict userdata,
void *__restrict chunk_join,
void *__restrict chunk);
typedef void (*TaskParallelFreeFunc)(const void *__restrict userdata, void *__restrict chunk);
typedef struct TaskParallelSettings {
/* Whether caller allows to do threading of the particular range.
* Usually set by some equation, which forces threading off when threading
* overhead becomes higher than speed benefit.
* BLI_task_parallel_range() by itself will always use threading when range
* is higher than a chunk size. As in, threading will always be performed.
*/
bool use_threading;
/* Each instance of looping chunks will get a copy of this data
* (similar to OpenMP's firstprivate).
*/
void *userdata_chunk; /* Pointer to actual data. */
size_t userdata_chunk_size; /* Size of that data. */
/* Function called from calling thread once whole range have been
* processed.
*/
/* Function called to join user data chunk into another, to reduce
* the result to the original userdata_chunk memory.
* The reduce functions should have no side effects, so that they
* can be run on any thread. */
TaskParallelReduceFunc func_reduce;
/* Function called to free data created by TaskParallelRangeFunc. */
TaskParallelFreeFunc func_free;
/* Minimum allowed number of range iterators to be handled by a single
* thread. This allows to achieve following:
* - Reduce amount of threading overhead.
* - Partially occupy thread pool with ranges which are computationally
* expensive, but which are smaller than amount of available threads.
* For example, it's possible to multi-thread [0 .. 64] range into 4
* thread which will be doing 16 iterators each.
* This is a preferred way to tell scheduler when to start threading than
* having a global use_threading switch based on just range size.
*/
int min_iter_per_thread;
} TaskParallelSettings;
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings);
void BLI_task_parallel_range(const int start,
const int stop,
void *userdata,
TaskParallelRangeFunc func,
const TaskParallelSettings *settings);
/* This data is shared between all tasks, its access needs thread lock or similar protection.
*/
typedef struct TaskParallelIteratorStateShared {
/* Maximum amount of items to acquire at once. */
int chunk_size;
/* Next item to be acquired. */
void *next_item;
/* Index of the next item to be acquired. */
int next_index;
/* Indicates that end of iteration has been reached. */
bool is_finished;
/* Helper lock to protect access to this data in iterator getter callback,
* can be ignored (if the callback implements its own protection system, using atomics e.g.).
* Will be NULL when iterator is actually processed in a single thread. */
SpinLock *spin_lock;
} TaskParallelIteratorStateShared;
typedef void (*TaskParallelIteratorIterFunc)(void *__restrict userdata,
const TaskParallelTLS *__restrict tls,
void **r_next_item,
int *r_next_index,
bool *r_do_abort);
typedef void (*TaskParallelIteratorFunc)(void *__restrict userdata,
void *item,
int index,
const TaskParallelTLS *__restrict tls);
void BLI_task_parallel_iterator(void *userdata,
TaskParallelIteratorIterFunc iter_func,
void *init_item,
const int init_index,
const int tot_items,
TaskParallelIteratorFunc func,
const TaskParallelSettings *settings);
void BLI_task_parallel_listbase(struct ListBase *listbase,
void *userdata,
TaskParallelIteratorFunc func,
const TaskParallelSettings *settings);
typedef struct MempoolIterData MempoolIterData;
typedef void (*TaskParallelMempoolFunc)(void *userdata,
MempoolIterData *iter,
const TaskParallelTLS *__restrict tls);
void BLI_task_parallel_mempool(struct BLI_mempool *mempool,
void *userdata,
TaskParallelMempoolFunc func,
const TaskParallelSettings *settings);
/* TODO(sergey): Think of a better place for this. */
BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *settings)
{
memset(settings, 0, sizeof(*settings));
settings->use_threading = true;
/* Use default heuristic to define actual chunk size. */
settings->min_iter_per_thread = 0;
}
BLI_INLINE void BLI_parallel_mempool_settings_defaults(TaskParallelSettings *settings)
{
memset(settings, 0, sizeof(*settings));
settings->use_threading = true;
}
/* Don't use this, store any thread specific data in tls->userdata_chunk instead.
* Only here for code to be removed. */
int BLI_task_parallel_thread_id(const TaskParallelTLS *tls);
/* Task Graph Scheduling */
/* Task Graphs can be used to create a forest of directional trees and schedule work to any tree.
* The nodes in the graph can be run in separate threads.
*
* +---- [root] ----+
* | |
* v v
* [node_1] +---- [node_2] ----+
* | |
* v v
* [node_3] [node_4]
*
* TaskGraph *task_graph = BLI_task_graph_create();
* TaskNode *root = BLI_task_graph_node_create(task_graph, root_exec, NULL, NULL);
* TaskNode *node_1 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
* TaskNode *node_2 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
* TaskNode *node_3 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
* TaskNode *node_4 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL);
*
* BLI_task_graph_edge_create(root, node_1);
* BLI_task_graph_edge_create(root, node_2);
* BLI_task_graph_edge_create(node_2, node_3);
* BLI_task_graph_edge_create(node_2, node_4);
*
* Any node can be triggered to start a chain of tasks. Normally you would trigger a root node but
* it is supported to start the chain of tasks anywhere in the forest or tree. When a node
* completes, the execution flow is forwarded via the created edges.
* When a child node has multiple parents the child node will be triggered once for each parent.
*
* BLI_task_graph_node_push_work(root);
*
* In this example After `root` is finished, `node_1` and `node_2` will be started.
* Only after `node_2` is finished `node_3` and `node_4` will be started.
*
* After scheduling work we need to wait until all the tasks have been finished.
*
* BLI_task_graph_work_and_wait();
*
* When finished you can clean up all the resources by freeing the task_graph. Nodes are owned by
* the graph and are freed task_data will only be freed if a free_func was given.
*
* BLI_task_graph_free(task_graph);
*
* Work can enter a tree on any node. Normally this would be the root_node.
* A `task_graph` can be reused, but the caller needs to make sure the task_data is reset.
*
* ** Task-Data **
*
* Typically you want give a task data to work on.
* Task data can be shared with other nodes, but be careful not to free the data multiple times.
* Task data is freed when calling `BLI_task_graph_free`.
*
* MyData *task_data = MEM_callocN(sizeof(MyData), __func__);
* TaskNode *root = BLI_task_graph_node_create(task_graph, root_exec, task_data, MEM_freeN);
* TaskNode *node_1 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
* TaskNode *node_2 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
* TaskNode *node_3 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
* TaskNode *node_4 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL);
*
*/
struct TaskGraph;
struct TaskNode;
typedef void (*TaskGraphNodeRunFunction)(void *__restrict task_data);
typedef void (*TaskGraphNodeFreeFunction)(void *task_data);
struct TaskGraph *BLI_task_graph_create(void);
void BLI_task_graph_work_and_wait(struct TaskGraph *task_graph);
void BLI_task_graph_free(struct TaskGraph *task_graph);
struct TaskNode *BLI_task_graph_node_create(struct TaskGraph *task_graph,
TaskGraphNodeRunFunction run,
void *user_data,
TaskGraphNodeFreeFunction free_func);
bool BLI_task_graph_node_push_work(struct TaskNode *task_node);
void BLI_task_graph_edge_create(struct TaskNode *from_node, struct TaskNode *to_node);
#ifdef __cplusplus
}
#endif
#endif
|