HDK
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros 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 #ifndef __UT_TASKSTATE_H_INCLUDED__
12 #define __UT_TASKSTATE_H_INCLUDED__
13 
14 #include "UT_API.h"
15 
16 #include "UT_Task.h"
17 #include <SYS/SYS_AtomicInt.h>
18 #include <SYS/SYS_AtomicPtr.h>
19 
20 // A task representing a wait for completion of a task by another thread.
21 // We maintain a thread-safe linked list of these objects in UT_TaskState.
23 {
24 public:
26  : myNext(NULL)
27  {
28  }
29 
30 private:
31  UT_TaskStateProxy *myNext;
32 
33  friend class UT_TaskState;
34 };
35 
36 // A task node for managing which thread is currently working on a given task
38 {
39  /// Special value used to indicate that myWaitingTasks is not accepting
40  /// additions.
41  ///
42  /// When the task state is "unplugged", it means that it's still accepting
43  /// compute or wait tasks. When it's "plugged" it no longer accepts tasks.
44  static UT_TaskStateProxy *plugged()
45  { return (UT_TaskStateProxy *)uintptr_t(-1); }
46 
47 public:
49  {
50  FREE, /// Thread has acquired responsibility to evaluate node.
51  BUSY, /// Another thread is busy evaluating the node.
52  DONE /// The node has been evaluated.
53  };
54 
56  {
57  reset();
58  }
59 
60  /// Set the state to be "free" with no waiting tasks.
61  /// This cannot be called from within threaded code.
62  void
64  {
65  myStatus.exchange(FREE);
66  myWaitingTasks.exchange(NULL);
67  }
68 
69  /// Test whether the task state is marked as DONE.
70  bool isDone() const
71  {
72  return myStatus.load() == DONE;
73  }
74 
75  /// Attempt to claim this node for the calling thread, returning the
76  /// current status.
77  TaskStatus
79  {
80  // If we're currently FREE, only allow one thread to change the status
81  // to BUSY. Otherwise, return the BUSY/DONE state.
82  auto state = myStatus.relaxedLoad();
83  if (state == FREE)
84  state = myStatus.compare_swap(FREE, BUSY);
85  return (TaskStatus)state;
86  }
87  /// Assuming that we're done, claim the node for the calling thread.
88  /// Returns FREE if succeeded, BUSY if failed.
89  TaskStatus
91  {
92  UT_ASSERT(myWaitingTasks == plugged());
93  if (myStatus.compare_swap(DONE, BUSY) == DONE)
94  {
95  myWaitingTasks.exchange(NULL);
96  return FREE;
97  }
98  return BUSY;
99  }
100  /// Assuming that we're busy, add a waiting task to be spawned when we're
101  /// free again. This is done a lock-free linked-list style.
102  void
103  addWaitingTask(UT_Task &parent_task)
104  {
105  UT_TaskStateProxy * proxy;
106  UT_TaskStateProxy * old;
107 
108  proxy = new (parent_task.allocate_child()) UT_TaskStateProxy();
109 
110  do
111  {
112  old = myWaitingTasks;
113  if (old == plugged())
114  {
115  // List was plugged by markAsDone() after we checked it in
116  // tryMarkAsBusy() before we got here.
117  //
118  // In tryMarkAsBusyFromDone(), it's possible myWaitingTasks is
119  // still plugged() when a separate thread adds a waiting task.
120  // Therefore, the task which adds waiting tasks should always
121  // recycle themselves after adding waiting tasks.
122  parent_task.spawnChild(*proxy);
123  return;
124  }
125  proxy->myNext = old;
126 
127  SYSstoreFence(); // Ensure the task state memory is stored
128  }
129  while (myWaitingTasks.compare_swap(old, proxy) != old);
130  }
131  /// Mark this node as being free. We walk through our waiting tasks and
132  /// spawn them. Since the proxy tasks are just empty tasks, they will
133  /// complete immediately and decrement the ref count of their parent task.
134  /// If the ref count of the parent task goes down to 0, then it will then
135  /// be runnable in the task scheduler.
136  void
137  markAsDone(UT_Task &parent_task)
138  {
139  // Plug myWaitingTasks so that we move into the DONE state
140  UT_TaskStateProxy *proxy = myWaitingTasks.exchange(plugged());
141 
142  // Spawn off any tasks that we're waiting while we were busy
143  while (proxy != NULL)
144  {
145  UT_TaskStateProxy *next = proxy->myNext;
146  parent_task.spawnChild(*proxy);
147  proxy = next;
148  }
149 
150  // Set myStatus to DONE so others can reclaim us.
151  myStatus.exchange(DONE);
152  }
153 
154  /// Non-threaded version of marking as done.
155  void
157  {
158  // Plug myWaitingTasks so that we move into the DONE state.
159  // We should have no proxy tasks in this case!
160  UT_VERIFY(myWaitingTasks.exchange(plugged()) == NULL);
161 
162  // Clear myStatus so that others can reclaim us.
163  myStatus.exchange(DONE);
164  }
165 
166  /// This does a fast (non-atomic) check of the status.
167  TaskStatus
169  {
170  return (TaskStatus)myStatus.relaxedLoad();
171  }
172 private:
173  SYS_AtomicInt32 myStatus;
174  SYS_AtomicPtr<UT_TaskStateProxy> myWaitingTasks;
175 };
176 
177 #endif // __UT_TASKSTATE_H_INCLUDED__
void markAsDoneNoThread()
Non-threaded version of marking as done.
Definition: UT_TaskState.h:156
#define UT_API
Definition: UT_API.h:12
void markAsDone(UT_Task &parent_task)
Definition: UT_TaskState.h:137
void reset()
Definition: UT_TaskState.h:63
#define UT_ASSERT(ZZ)
Definition: UT_Assert.h:102
Thread has acquired responsibility to evaluate node.
Definition: UT_TaskState.h:51
#define SYSstoreFence()
void spawnChild(UT_Task &task)
Definition: UT_Task.h:68
bool isDone() const
Test whether the task state is marked as DONE.
Definition: UT_TaskState.h:70
#define UT_VERIFY(expr)
Definition: UT_Assert.h:148
TaskStatus tryMarkAsBusy()
Definition: UT_TaskState.h:78
void addWaitingTask(UT_Task &parent_task)
Definition: UT_TaskState.h:103
TaskStatus relaxedLoadStatus() const
This does a fast (non-atomic) check of the status.
Definition: UT_TaskState.h:168
TaskStatus tryMarkAsBusyFromDone()
Definition: UT_TaskState.h:90