HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UT_TaskState.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_TaskState.h (UT Library, C++)
7  *
8  * COMMENTS:
9  */
10 
11 #pragma once
12 
13 #ifndef __UT_TASKSTATE_H_INCLUDED__
14 #define __UT_TASKSTATE_H_INCLUDED__
15 
16 #ifndef __TBB_show_deprecation_message_task_H
17  #define __TBB_show_deprecation_message_task_H
18  #define UT_TASK_STATE_RESTORE_DEPRECATION_MESSAGE
19 #endif
20 
21 #include "UT_API.h"
22 #include "UT_Task.h"
23 #include "UT_TaskArena.h"
24 #include "UT_TaskGroup.h"
25 #include "UT_Thread.h"
26 #include <SYS/SYS_AtomicInt.h>
27 #include <SYS/SYS_AtomicPtr.h>
28 #include <utility>
29 
30 /// A task representing a wait for completion of a task by another thread.
31 /// We maintain a thread-safe linked list of these objects in UT_TaskState.
33 {
34 public:
36  : myNext(nullptr)
37  {
38  }
39 
40 private:
41  UT_TaskStateProxy *myNext;
42 
43  friend class UT_TaskState;
44 };
45 
46 /// A task node for managing which thread is currently working on a given task
48 {
49  /// Special value used to indicate that myWaitingTasks is not accepting
50  /// additions.
51  ///
52  /// When the task state is "unplugged", it means that it's still accepting
53  /// compute or wait tasks. When it's "plugged" it no longer accepts tasks.
54  static UT_TaskStateProxy *plugged()
55  { return (UT_TaskStateProxy *)uintptr_t(-1); }
56 
57 public:
59  {
60  FREE, /// Thread has acquired responsibility to evaluate node.
61  BUSY_WITH_ARENA,/// Another thread is busy evaluating the node with an arena.
62  BUSY_NO_ARENA, /// Another thread is busy evaluating the node without an arena.
63  DONE_WITH_ARENA,/// The node has been evaluated with an arena.
64  DONE_NO_ARENA /// The node has been evaluated without an arena.
65  };
66 
68  : myArenaAndGroupRefCount(0)
69  {
70  SYS_STATIC_ASSERT_MSG(sizeof(UT_TaskState) == 2*sizeof(SYS_AtomicInt32) + sizeof(void*),
71  "This is just to check that the union is putting the two pointers "
72  "in the same place.");
73 
74  reset();
75  }
77  {
78  UT_ASSERT_P(myArenaAndGroupRefCount.relaxedLoad() == 0);
79  UT_ASSERT_P(myArenaAndGroup.relaxedLoad() == nullptr || myWaitingTasks.relaxedLoad() == plugged());
80  }
81 
82  /// Set the state to be "free" with no waiting tasks.
83  /// This cannot be called from within threaded code.
84  void
86  {
87  myStatus.relaxedStore(FREE);
88  UT_ASSERT_P(myArenaAndGroupRefCount.relaxedLoad() == 0);
89  // This will also assign nullptr to myWaitingTasks.
90  // It doesn't need to be atomic, because nothing else is allowed to
91  // access it while we're resetting.
92  myArenaAndGroup.relaxedStore(nullptr);
93  }
94 
95  /// Test whether the task state is marked as DONE.
96  bool isDone() const
97  {
98  auto state = myStatus.relaxedLoad();
99  return state == DONE_NO_ARENA || state == DONE_WITH_ARENA;
100  }
101 
102  /// Attempt to claim this node for the calling thread, returning the
103  /// current status.
104  TaskStatus
105  tryMarkAsBusy(bool run_in_task_arena=false)
106  {
107  auto state = myStatus.relaxedLoad();
108  if (state == DONE_WITH_ARENA || state == DONE_NO_ARENA || state == BUSY_NO_ARENA)
109  return (TaskStatus)state;
110 
111  // Increment the reference count before checking myStatus again,
112  // to avoid a race condition where a thread might delete it
113  // early. We decrement after if it turned out that we don't need
114  // the reference after all. Just in case run_in_task_arena is set
115  // inconsistently between threads, we need the same increment
116  // regardless of whether run_in_task_arena is true, and regardless
117  // of whether state was already BUSY_WITH_ARENA.
118  myArenaAndGroupRefCount.add(1);
119 
120  // If we're currently FREE, only allow one thread to change the status
121  // to BUSY. Otherwise, return the BUSY/DONE state.
122  state = myStatus.compare_swap(FREE, run_in_task_arena ? BUSY_WITH_ARENA : BUSY_NO_ARENA);
123 
124  if (state == DONE_NO_ARENA || state == BUSY_NO_ARENA || (!run_in_task_arena && state == FREE))
125  myArenaAndGroupRefCount.add(-1);
126  else if (state == DONE_WITH_ARENA)
127  decrefArenaGroup();
128 
129  return (TaskStatus)state;
130  }
131  /// Assuming that we're done, claim the node for the calling thread.
132  /// Returns FREE if succeeded, BUSY if failed.
133  TaskStatus
135  {
136  UT_ASSERT_MSG(0, "This is untested code. Note that calling code in the build is now unused."
137  " If myArenaAndGroup was used before, it must be used on subsequent executes.");
138  if (myStatus.compare_swap(DONE_NO_ARENA, BUSY_NO_ARENA) == DONE_NO_ARENA)
139  {
140  // If myWaitingTasks is plugged(), we need to clear it to null,
141  // but if we're using a task arena, myArenaAndGroupRefCount may
142  // still be non-zero, depending on how this functions is supposed
143  // to be used. If it is non-zero, this code is wrong.
144  UT_ASSERT(myArenaAndGroupRefCount.relaxedLoad() == 0);
145  myArenaAndGroup.relaxedStore(nullptr);
146  return FREE;
147  }
148  return BUSY_NO_ARENA;
149  }
150  /// Assuming that we're busy, add a waiting task to be spawned when we're
151  /// free again. This is done a lock-free linked-list style.
152  void
153  addWaitingTask(UT_Task &parent_task)
154  {
155  UT_ASSERT_P(myStatus.relaxedLoad() == BUSY_NO_ARENA || myStatus.relaxedLoad() == DONE_NO_ARENA);
156 
157  UT_TaskStateProxy *proxy = new (parent_task.allocate_child()) UT_TaskStateProxy();
158 
159  UT_TaskStateProxy *old;
160  do
161  {
162  old = myWaitingTasks;
163  if (old == plugged())
164  {
165  // List was plugged by markAsDone() after we checked it in
166  // tryMarkAsBusy() before we got here.
167  //
168  // In tryMarkAsBusyFromDone(), it's possible myWaitingTasks is
169  // still plugged() when a separate thread adds a waiting task.
170  // Therefore, the task which adds waiting tasks should always
171  // recycle themselves after adding waiting tasks.
172  parent_task.spawnChild(*proxy);
173  return;
174  }
175  proxy->myNext = old;
176 
177  SYSstoreFence(); // Ensure the task state memory is stored
178  }
179  while (myWaitingTasks.compare_swap(old, proxy) != old);
180  }
181  /// Mark this node as being free. We walk through our waiting tasks and
182  /// spawn them. Since the proxy tasks are just empty tasks, they will
183  /// complete immediately and decrement the ref count of their parent task.
184  /// If the ref count of the parent task goes down to 0, then it will then
185  /// be runnable in the task scheduler.
186  void
187  markAsDone(UT_Task *parent_task, bool run_in_task_arena)
188  {
189  if (parent_task)
190  {
191  // Plug myWaitingTasks so that we move into the DONE state
192  UT_TaskStateProxy *proxy = myWaitingTasks.exchange(plugged());
193 
194  // Spawn off any tasks that we're waiting while we were busy
195  while (proxy != nullptr)
196  {
197  UT_TaskStateProxy *next = proxy->myNext;
198  parent_task->spawnChild(*proxy);
199  proxy = next;
200  }
201  // Set myStatus to DONE so others can reclaim us.
202  myStatus.exchange(DONE_NO_ARENA);
203  }
204  else
205  {
206  // Set myStatus to DONE so others can reclaim us.
207  myStatus.exchange(run_in_task_arena ? DONE_WITH_ARENA : DONE_NO_ARENA);
208  }
209  }
210 
211  /// Non-threaded version of marking as done.
212  void
214  {
215  // Plug myWaitingTasks so that we move into the DONE state.
216  // We should have no proxy tasks in this case!
217  UT_VERIFY(myWaitingTasks.exchange(plugged()) == nullptr);
218 
219  // Clear myStatus so that others can reclaim us.
220  myStatus.exchange(DONE_NO_ARENA);
221  }
222 
223  /// This does a fast (non-atomic) check of the status.
224  TaskStatus
226  {
227  return (TaskStatus)myStatus.relaxedLoad();
228  }
229 
230  using ArenaAndGroup = std::pair<UT_TaskArena,UT_TaskGroup>;
231 
233  {
234  UT_ASSERT_P(myArenaAndGroupRefCount.relaxedLoad() > 0 &&
235  (myStatus.relaxedLoad() == BUSY_WITH_ARENA || myStatus.relaxedLoad() == DONE_WITH_ARENA));
236  myArenaAndGroup.relaxedStore(p);
237  }
239  {
240  UT_ASSERT_P(myArenaAndGroupRefCount.relaxedLoad() > 0 &&
241  (myStatus.relaxedLoad() == BUSY_WITH_ARENA || myStatus.relaxedLoad() == DONE_WITH_ARENA));
242  return myArenaAndGroup.relaxedLoad();
243  }
244  /// Decrements the reference count for myArenaAndGroup
245  /// and deletes it if the reference count reaches zero.
247  {
248  UT_ASSERT_P(myStatus.relaxedLoad() == DONE_WITH_ARENA);
249  if (myArenaAndGroupRefCount.add(-1) == 0)
250  {
251  // NOTE: This must be an atomic exchange, since
252  // there is a race condition where two threads
253  // can both get a ref count of zero, (one of which
254  // incremented and immediately decremented in
255  // tryMarkAsBusy()).
256  auto *arena_group = myArenaAndGroup.exchange(nullptr);
257  delete arena_group;
258  }
259  }
260 private:
261  SYS_AtomicInt32 myStatus;
262  SYS_AtomicInt32 myArenaAndGroupRefCount;
263  union {
266  };
267 };
268 
269 #ifdef UT_TASK_STATE_RESTORE_DEPRECATION_MESSAGE
270  #undef __TBB_show_deprecation_message_task_H
271  #undef UT_TASK_STATE_RESTORE_DEPRECATION_MESSAGE
272 #endif
273 
274 #endif // __UT_TASKSTATE_H_INCLUDED__
Thread has acquired responsibility to evaluate node.
Definition: UT_TaskState.h:61
void markAsDoneNoThread()
Non-threaded version of marking as done.
Definition: UT_TaskState.h:213
#define SYS_STATIC_ASSERT_MSG(expr, msg)
A task node for managing which thread is currently working on a given task.
Definition: UT_TaskState.h:47
fallback_uintptr uintptr_t
Definition: format.h:295
void decrefArenaGroup()
Definition: UT_TaskState.h:246
#define UT_API
Definition: UT_API.h:14
ArenaAndGroup * getArenaGroup() const
Definition: UT_TaskState.h:238
void markAsDone(UT_Task *parent_task, bool run_in_task_arena)
Definition: UT_TaskState.h:187
SYS_AtomicPtr< UT_TaskStateProxy > myWaitingTasks
Definition: UT_TaskState.h:265
void reset()
Definition: UT_TaskState.h:85
#define UT_ASSERT_MSG(ZZ,...)
Definition: UT_Assert.h:159
TaskStatus tryMarkAsBusy(bool run_in_task_arena=false)
Definition: UT_TaskState.h:105
GLboolean reset
Definition: glad.h:5138
#define UT_ASSERT_P(ZZ)
Definition: UT_Assert.h:155
#define SYSstoreFence()
void spawnChild(UT_Task &task)
Definition: UT_Task.h:75
bool isDone() const
Test whether the task state is marked as DONE.
Definition: UT_TaskState.h:96
#define UT_VERIFY(expr)
Definition: UT_Assert.h:202
void setAndRetainArenaGroup(ArenaAndGroup *p)
Definition: UT_TaskState.h:232
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
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:156
void addWaitingTask(UT_Task &parent_task)
Definition: UT_TaskState.h:153
SYS_AtomicPtr< ArenaAndGroup > myArenaAndGroup
Definition: UT_TaskState.h:264
TaskStatus relaxedLoadStatus() const
This does a fast (non-atomic) check of the status.
Definition: UT_TaskState.h:225
TaskStatus tryMarkAsBusyFromDone()
Definition: UT_TaskState.h:134