HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_TaskExclusive.h
Go to the documentation of this file.
1 /*
2  * PROPRIETARY INFORMATION. This software is proprietary to
3  * Side Effects Software Inc., and is not to be reproduced,
4  * transmitted, or disclosed in any way without written permission.
5  *
6  * NAME: UT_TaskExclusive.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #pragma once
12 
13 #ifndef __UT_TaskExclusive__
14 #define __UT_TaskExclusive__
15 
16 #ifndef __TBB_show_deprecation_message_task_H
17  #define __TBB_show_deprecation_message_task_H
18  #define UT_TASK_EXCLUSIVE_RESTORE_DEPRECATION_MESSAGE
19 #endif
20 
21 // TODO: For oneTBB 2021, we should use isolate_task_group instead. See the TBB
22 // docs for an example.
23 
24 #include "UT_Task.h"
25 #include "UT_TaskGroup.h"
26 #include "UT_TaskScope.h"
27 #include "UT_TaskState.h"
28 #include "UT_TaskArena.h"
29 #include "UT_Thread.h"
30 #include <SYS/SYS_Deprecated.h>
31 #include <SYS/SYS_Pragma.h>
32 #include <utility>
33 
34 /// This is a lock-free implementation for exclusive task execution. That is,
35 /// a task which needs to be performed once (i.e. std::once). However, this
36 /// construct will allow TBB to recycle blocked tasks so they can be used for
37 /// other processing.
38 ///
39 /// This can be used as an alternate to a lock. If code underneath a lock
40 /// calls into TBB, this can lead to a deadlock since TBB can steal a child
41 /// task to complete a parent task outside the lock. This typically requires a
42 /// separate task arena. A lock will also block a thread, preventing it from
43 /// participating in other tasks.
44 ///
45 /// UT_TaskExclusive provides a good alternative, ensuring that only one thread
46 /// will execute the functor, and all other threads which wait for the functor
47 /// to finish will be allowed to participate in other computation (even to help
48 /// computing parallel tasks in the functor).
49 ///
50 /// The class is templated on a functor which is used to actually perform the
51 /// execution. The template functor needs to have a operator()() method.
52 ///
53 /// For example, given a single Object which has a deferredInitialize() method
54 /// that may get called from multiple threads: @code
55 /// class Object
56 /// {
57 /// UT_TaskExclusive<Object> myExclusive;
58 ///
59 /// public:
60 /// // Users call deferredInitialize when they want the object to be
61 /// // initialized. However, it's possible the object may need to be
62 /// // initialized by multiple threads. The object uses UT_TaskExclusive
63 /// // to ensure doInitialization() is only executed one time.
64 /// void deferredInitialize()
65 /// {
66 /// myExclusive.execute(*this);
67 /// }
68 /// void operator()()
69 /// {
70 /// // This method will only be called once, even if
71 /// // multiple threads invoke the deferredInitialize() method
72 /// // simultaneously.
73 /// doInitialization();
74 /// }
75 /// }
76 /// @endcode
77 /// If you have multiple methods that should only be called one time, you can
78 /// always create a nested object functor.
79 ///
80 /// If the functor is likely to create further tbb tasks, you can ensure these
81 /// tasks are run in their own task arena by setting @c run_in_task_arena to
82 /// true (the default).
84 template <class T>
86 {
87 public:
89  : myState()
90  {
91  }
92 
93  /// Execute the compute task. This will guarantee the function has been
94  /// run before the execute() function returns. However, no locking will be
95  /// done.
96  ///
97  /// If multiple threads try to call the function simultaneously, only one
98  /// function will run, while the other will yield its cycles to other
99  /// parallel tasks. When the first task completes, both threads will
100  /// return.
101  ///
102  /// If the functor is likely to create further tbb tasks, you can ensure
103  /// these tasks are run in their own task arena by setting @c
104  /// run_in_task_arena to true (the default). The primary reason for having
105  /// a separate task arena is that the if the functor creates further tasks,
106  /// and one of these tasks is also dependent on the task exclusive, this
107  /// can lead to a tbb deadlock (a tbb stack lock).
108  void execute(
109  T &func,
110  bool run_in_task_arena = true,
111  bool use_spinlock = false)
112  {
113  UT_TaskState::TaskStatus status = myState.tryMarkAsBusy(run_in_task_arena);
115  {
116  // The task has been run, so just return
117  return;
118  }
119 
120  if (run_in_task_arena && status == UT_TaskState::FREE)
121  {
122  // I win and I get to run the compute function
125  // NOTE: The arena & group must be on the heap, since this
126  // thread might have returned before all tasks in the
127  // arena, waiting on the group, have finished.
128  auto *arena_group = new UT_TaskState::ArenaAndGroup();
129  UT_TaskArena *arena = &arena_group->first;
130  const UT_TaskScope *parent_task_scope = UT_TaskScope::getCurrent();
131 
132  // execute will be called on the arena from multiple threads,
133  // but this one will always run before any others can start,
134  // so we don't need to explicitly call initialize.
135  //arena->initialize();
136  arena->execute([this,&func,arena_group,parent_task_scope]()
137  {
138  UT_TaskGroup *group = &arena_group->second;
139  group->run([this,&func,parent_task_scope]()
140  {
141  UT_TaskScope task_scope(parent_task_scope);
142  func();
143  // Can't explicitly wake up waiting tasks,
144  // so we must pass nullptr here.
145  myState.markAsDone(nullptr, true);
146  });
147  // Ensure the initialized arena and group are written out to main memory
148  // before the accessible pointer is set.
149  SYSstoreFence();
150  // The arena/group pointer must be set after run has been
151  // called on the group, to ensure that other threads,
152  // waiting for this pointer to be non-null, won't try to
153  // call wait on the group until there's a task in the group.
154  myState.setAndRetainArenaGroup(arena_group);
155 
156  // NOTE: We probably don't need a UT_TaskScope here; the one
157  // inside the lambda passed to run() should suffice.
158  group->wait();
159  });
161  myState.decrefArenaGroup();
162  }
163  else if (status == UT_TaskState::BUSY_WITH_ARENA)
164  {
165  // NOTE: Even if run_in_task_arena is false, if the first one
166  // called it with true, we need to be consistent.
167  // e.g. VGEO_MotionBlurTree was clearing myBoxes during its
168  // building, and code outside the exclusive was checking
169  // the size to determine whether to parallelize,
170  // (i.e. whether to use a task arena.)
171 
172  auto *arena_group = myState.getArenaGroup();
173  if (!arena_group)
174  {
175  // Spin until the group task gets created.
176  UT_ThreadBackoff backoff;
177  do
178  {
179  backoff.wait();
180  arena_group = myState.getArenaGroup();
181  } while (!arena_group);
182  }
183 
184  // NOTE: We probably don't need a SYSloadFence() here,
185  // because speculative reads of memory pointed to by
186  // arena_group would fail, since it was previously null.
187  // As soon as it's non-null, it's safe to read, as ensured
188  // by the SYSstoreFence() above.
189 
190  // Enter the task arena running the group task,
191  // and wait on the group.
192  UT_TaskArena *arena = &arena_group->first;
193  UT_TaskGroup *group = &arena_group->second;
194  arena->execute([group]()
195  {
196  // NOTE: This task doesn't need its own task scope,
197  // because any tasks executed during the group->wait()
198  // should have their own task scopes, which are
199  // automatically descendants of the task scope in the
200  // main compute task.
201  group->wait();
202  });
203  myState.decrefArenaGroup();
204  }
205  else if (use_spinlock)
206  {
207  if (status == UT_TaskState::FREE)
208  {
209  // If other threads will be using a spin lock, we don't
210  // need to create a new task.
211  func();
212  myState.markAsDone(nullptr, false);
213  }
214  else
215  {
216  UT_ThreadBackoff backoff;
217  do
218  {
219  backoff.wait();
220  } while (myState.relaxedLoadStatus() == UT_TaskState::BUSY_NO_ARENA);
221  }
222  }
223  else
224  {
225  if (status == UT_TaskState::FREE)
226  {
227  // We need a compute task, just so that we can specify
228  // a parent task for spawning child tasks upon completion.
229  // There might be some way to eliminate this.
230  ComputeTask *root = ComputeTask::createRoot(myState, func);
231  ComputeTask::spawnRootAndWait(*root);
232  }
233  else
234  {
235  // I lost and I have to wait for the opportunity to help.
236  DummyTask *root = DummyTask::createRoot(myState);
237  DummyTask::spawnRootAndWait(*root);
238  }
239  }
240  }
241 
242  /// Executes the compute task in this thread without any locking
243  /// or protection. Useful if the caller has already setup the
244  /// appropriate lock.
246  {
247  if (!hasRun())
248  {
249  func();
250  myState.markAsDoneNoThread();
251  }
252  }
253 
254  /// Resetting the exclusive task should only be done when there's no
255  /// possibility that any threads are trying to execute or relying on the
256  /// results of the computation.
257  void reset() { myState.reset(); }
258 
259  /// Test whether the function has been executed. This is thread-safe, but
260  /// doesn't count on other threads which may be in the process of running
261  /// it.
262  bool hasRun() const { return myState.isDone(); }
263 
264 private:
265  class ComputeTask : public UT_Task
266  {
267  public:
268  ComputeTask(UT_TaskState &state, T &func)
269  : myState(state)
270  , myFunc(func)
271  {
272  }
273  static ComputeTask *createRoot(UT_TaskState &state, T &func)
274  {
275  return new (allocate_root()) ComputeTask(state, func);
276  }
277 
278  UT_Task *run() override
279  {
280  myFunc();
281  myState.markAsDone(this, false);
282  return nullptr;
283  }
284  T &myFunc;
285  UT_TaskState &myState;
286  };
287  class DummyTask : public UT_Task
288  {
289  public:
290  DummyTask(UT_TaskState &state)
291  : myState(state)
292  {
293  }
294  static DummyTask *createRoot(UT_TaskState &state)
295  {
296  return new (allocate_root()) DummyTask(state);
297  }
298 
299  UT_Task *run() override
300  {
301  if (myState.relaxedLoadStatus() != UT_TaskState::BUSY_NO_ARENA)
302  return nullptr;
303 
304  // Someone else is performing the computation, so
305  // a) Add a child task to this task (introducing a dependency)
306  // b) Add the child task to myState so it can be run when the
307  // compute is done... The child (wait task) isn't run
308  // until the compute is complete.
309  // c) Recycle my task so that it's put back on the TBB
310  // scheduler. When the child task is complete, this task
311  // will be run again, but the state will be marked as
312  // done, so we can return.
313 
314  // Increment the reference count 2 times
315  // - Once since I have a child
316  // - Once since I'm recycling myself
319  myState.addWaitingTask(*this);
321  return nullptr;
322  }
323  UT_TaskState &myState;
324  };
325 
326  UT_TaskState myState;
327 };
329 
330 #ifdef UT_TASK_EXCLUSIVE_RESTORE_DEPRECATION_MESSAGE
331  #undef __TBB_show_deprecation_message_task_H
332  #undef UT_TASK_EXCLUSIVE_RESTORE_DEPRECATION_MESSAGE
333 #endif
334 
335 #endif
336 
Thread has acquired responsibility to evaluate node.
Definition: UT_TaskState.h:61
void execute(F &functor)
Definition: UT_TaskArena.h:60
#define SYS_PRAGMA_PUSH_WARN()
Definition: SYS_Pragma.h:34
*get result *(waiting if necessary)*A common idiom is to fire a bunch of sub tasks at the and then *wait for them to all complete We provide a helper class
Definition: thread.h:623
static const UT_TaskScope * getCurrent()
Definition: UT_TaskScope.h:96
#define SYS_DEPRECATED_PUSH_DISABLE()
A task node for managing which thread is currently working on a given task.
Definition: UT_TaskState.h:47
#define SYS_DEPRECATED_POP_DISABLE()
The node has been evaluated with an arena.
Definition: UT_TaskState.h:64
tbb::task_group_status wait()
Definition: UT_TaskGroup.h:131
void recycleAsSafeContinuation()
Definition: UT_Task.h:56
void run(F &&f)
Definition: UT_TaskGroup.h:103
void incrementRefCount()
Definition: UT_Task.h:43
#define SYSstoreFence()
#define SYS_PRAGMA_POP_WARN()
Definition: SYS_Pragma.h:35
#define SYS_PRAGMA_DISABLE_ATTRIBUTES()
Definition: SYS_Pragma.h:162
virtual UT_Task * run()=0
void executeNoThread(T &func)
GLenum func
Definition: glcorearb.h:783
Another thread is busy evaluating the node without an arena.
Definition: UT_TaskState.h:63
Another thread is busy evaluating the node with an arena.
Definition: UT_TaskState.h:62
std::pair< UT_TaskArena, UT_TaskGroup > ArenaAndGroup
Definition: UT_TaskState.h:230
bool hasRun() const
void execute(T &func, bool run_in_task_arena=true, bool use_spinlock=false)