MADNESS  0.10.1
dependency_interface.h
Go to the documentation of this file.
1 /*
2  This file is part of MADNESS.
3 
4  Copyright (C) 2007,2010 Oak Ridge National Laboratory
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10 
11  This program is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  GNU General Public License for more details.
15 
16  You should have received a copy of the GNU General Public License
17  along with this program; if not, write to the Free Software
18  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 
20  For more information please contact:
21 
22  Robert J. Harrison
23  Oak Ridge National Laboratory
24  One Bethel Valley Road
25  P.O. Box 2008, MS-6367
26 
27  email: harrisonrj@ornl.gov
28  tel: 865-241-3937
29  fax: 865-572-0680
30 */
31 
32 /**
33  \file dependency_interface.h
34  \brief Defines \c DependencyInterface and \c CallbackInterface.
35  \ingroup world
36 */
37 
38 #ifndef MADNESS_WORLD_DEPENDENCY_INTERFACE_H__INCLUDED
39 #define MADNESS_WORLD_DEPENDENCY_INTERFACE_H__INCLUDED
40 
41 #include <atomic>
42 #include <cassert>
43 #include <typeinfo>
44 
45 #include <madness/world/stack.h>
48 #include <madness/world/world.h>
49 #include <madness/world/print.h>
50 
51 #include <cassert>
52 #include <iterator>
53 #include <numeric>
54 #include <mutex>
55 #include <typeinfo>
56 #include <unordered_map>
57 
58 namespace madness {
59 
60  /// The class used for callbacks (e.g., dependency tracking).
62  public:
63  /// Invoked by the callback to notify when a dependency is satisfied.
64  virtual void notify() = 0;
65 
66  /// Same as notify(), but tracks how many times called from each \c caller
67  virtual void notify_debug(const char* caller) {
68  notify_debug_impl(caller);
69  this->notify();
70  }
71 
72 // virtual ~CallbackInterface() = default;
73  virtual ~CallbackInterface() {}
74 
75  protected:
76  virtual void notify_debug_impl(const char* caller) {
77 #ifdef MADNESS_TASK_DEBUG_TRACE
78  {
79  mx_.lock();
80  const auto caller_str = caller;
81  auto it = callers_.find(caller_str);
82  if (it != callers_.end())
83  it->second += 1;
84  else
85  callers_[caller] = 1;
86  mx_.unlock();
87  }
88 #endif
89  }
90 
91  private:
92 #ifdef MADNESS_TASK_DEBUG_TRACE
93  std::unordered_map<std::string,int> callers_;
94  std::mutex mx_;
95 #endif
96  };
97 
98 
99  /// Provides an interface for tracking dependencies.
101  private:
102  // Dependency counter is still atomic to allow fast(er) probing from outside critical sections
103  // note that all *updates* to this counter will occur from critical sections
104  // thus this is for lock-free probing only
105  std::atomic<int> ndepend; ///< Counts dependencies. For a valid object \c ndepend >= 0, after the final callback is executed ndepend is set to a negative value and the object becomes invalid.
106 
107  static const int MAXCALLBACKS = 8; ///< Maximum number of callbacks.
108  using callbackT = Stack<CallbackInterface*,MAXCALLBACKS>; ///< \todo Brief description needed.
109  mutable volatile callbackT callbacks; ///< Called ONCE by \c dec() when `ndepend==0`.
110 
111  mutable volatile CallbackInterface* final_callback; ///< The "final" callback can destroy the task, always invoked last, the object is in an invalid state (ndepend set to -1) after its execution
112 #ifdef MADNESS_TASK_DEBUG_TRACE
113  volatile int max_ndepend; ///< max value of \c ndepend
114  constexpr static const bool print_debug = false; // change to true to log state changes in {inc,dec,notify}_debug, (debug) ctor, and dtor
115 #endif
116 
117  /// \todo Brief description needed.
118 
119  /// Main design point is that, because a callback might destroy this
120  /// object, when callbacks are invoked we cannot be holding the lock
121  /// and all necessary data must be on the stack (i.e., not from the
122  /// object state).
123  /// \todo Parameter description needed.
124  /// \param[in,out] cb Description needed.
125  void do_callbacks(callbackT& cb) const {
126  while (!cb.empty()) {
127  cb.top()->notify();
128  cb.pop();
129  }
130  }
131 
132  public:
133  /// \todo Constructor that...
134 
135  /// \param[in] ndep The number of unsatisfied dependencies.
137  MADNESS_ASSERT(ndepend >= 0);
138  }
139 
140  /// Same as ctor above, but keeps track of \c caller . If a given object was constructed
141  /// via this ctor, or DependencyInterface::inc_debug() had been called once, debugging variants
142  /// of mutating calls ( \c {inc/dec/notify}_debug ) must be used for the rest of this object's lifetime.
143  /// \param[in] ndep The number of unsatisfied dependencies.
144  DependencyInterface(int ndep, const char* caller) : ndepend(ndep), final_callback(nullptr)
145 #ifdef MADNESS_TASK_DEBUG_TRACE
146  , max_ndepend(ndep)
147 #endif
148  {
149  MADNESS_ASSERT(ndepend >= 0);
150 #ifdef MADNESS_TASK_DEBUG_TRACE
151  callers_[caller] = ndep;
152  if (print_debug)
153  print("DependencyInterface debug ctor: this=", this, " caller=", caller, " ndepend=", ndepend);
154 #endif
155  }
156 
157  /// Returns the number of unsatisfied dependencies.
158 
159  /// \return The number of unsatisfied dependencies.
160  int ndep() const {
161  MADNESS_ASSERT(ndepend >= 0); // ensure we are valid
162  return ndepend;
163  }
164 
165 #ifdef MADNESS_TASK_DEBUG_TRACE
166  /// Returns the number of unsatisfied dependencies tracked by the debugging instrumentation.
167 
168  /// \return The number of unsatisfied dependencies tracked via _debug calls (or debug ctor).
169  int ndep_debug() const {
170  return std::accumulate(begin(callers_), end(callers_), 0,
171  [](int partial_sum, auto& x) { return partial_sum + x.second; });
172  }
173 #endif
174 
175  /// Returns true if `ndepend == 0` (no unsatisfied dependencies).
176 
177  /// \return True if there are no unsatisfied dependencies.
178  bool probe() const {
179  return ndep() == 0;
180  }
181 
182  /// Invoked by callbacks to notify of dependencies being satisfied.
183  void notify() {
184  MADNESS_ASSERT(ndepend >= 0); // ensure we are valid
185  dec();
186  }
187 
188  /// Overload of CallbackInterface::notify_debug(), updates dec()
189  void notify_debug(const char* caller) {
190  MADNESS_ASSERT(ndepend >= 0);
191 #ifdef MADNESS_TASK_DEBUG_TRACE
193 #endif
194  this->dec_debug(caller);
195  }
196 
197  /// \brief Registers a callback that will be executed when `ndepend==0`; immediately invoked
198  /// if `ndepend==0`.
199 
200  /// \param[in] callback The callback to use.
202  callbackT cb;
203  {
204  ScopedMutex<Spinlock> obolus(this);
205  MADNESS_ASSERT(ndepend >= 0); // ensure we are valid
206 #ifdef MADNESS_TASK_DEBUG_TRACE
207  if (print_debug && !callers_.empty())
208  print("DependencyInterface::register_callback: this=", this, " ndepend=", ndepend);
209 #endif
210  const_cast<callbackT&>(callbacks).push(callback);
211  if (probe()) {
212  cb = std::move(const_cast<callbackT&>(callbacks));
213  if (final_callback) {
215  ndepend = -1;
216  }
217  }
218  }
219  do_callbacks(cb);
220  }
221 
222 
223  /// \brief Registers the final callback to be executed when `ndepend==0`; immediately invoked
224  /// if `ndepend==0`.
225 
226  /// No additional callbacks can be registered after this call since execution
227  /// of the final callback can cause destruction of this object.
228  /// \param[in] callback The callback to use.
230  callbackT cb;
231  {
232  ScopedMutex<Spinlock> obolus(this);
233  MADNESS_ASSERT(ndepend >= 0); // ensure we are valid
234  MADNESS_ASSERT(final_callback == nullptr);
235 #ifdef MADNESS_TASK_DEBUG_TRACE
236  if (print_debug && !callers_.empty())
237  print("DependencyInterface::register_final_callback: this=", this, " ndepend=", ndepend);
238 #endif
239  final_callback = callback;
240  if (probe()) {
241  cb = std::move(const_cast<callbackT&>(callbacks));
243  // make object invalid
244  ndepend = -1;
245  }
246  }
247  do_callbacks(cb);
248  }
249 
250  /// Increment the number of dependencies.
251  void inc() {
252  ScopedMutex<Spinlock> obolus(this);
253  MADNESS_ASSERT(ndepend >= 0); // ensure we are valid
254 #ifdef MADNESS_TASK_DEBUG_TRACE
255  if (!callers_.empty())
256  error("DependencyInterface::inc() called for an object that is being debugged", "");
257 #endif
258  ++ndepend;
259  }
260 
261  /// Decrement the number of dependencies and invoke the callback if `ndepend==0`.
262  void dec() {
263  callbackT cb;
264  {
265  ScopedMutex<Spinlock> obolus(this);
266  MADNESS_ASSERT(ndepend > 0); // ensure we are valid and decrement can succeed
267 #ifdef MADNESS_TASK_DEBUG_TRACE
268  if (!callers_.empty())
269  error("DependencyInterface::dec() called for an object that is being debugged", "");
270 #endif
271  if (ndepend == 1) {
272  cb = std::move(const_cast<callbackT&>(callbacks));
273  if (final_callback) {
275  // make object invalid by setting ndepend to -1
276  ndepend = -1;
277  }
278  }
279  // NB safe to update ndepend now, was not safe to do that before since that makes it observable and
280  // e.g. result in its destruction before all changes to state are done
281  --ndepend;
282  }
283  do_callbacks(cb);
284  }
285 
286  /// Same as inc(), but keeps track of \c caller; calling dec_debug() will signal error if no matching inc_debug() had been invoked
287  void inc_debug(const char* caller) {
288  ScopedMutex<Spinlock> obolus(this);
289  MADNESS_ASSERT(ndepend >= 0); // ensure we are valid
290  ++ndepend;
291 #ifdef MADNESS_TASK_DEBUG_TRACE
292  const auto caller_str = caller;
293  auto it = callers_.find(caller_str);
294  if (it != callers_.end())
295  it->second += 1;
296  else
297  callers_[caller] = 1;
298  max_ndepend = std::max(static_cast<int>(max_ndepend), static_cast<int>(ndepend));
299  if (ndep() != ndep_debug())
300  error("DependencyInterface::inc_debug(): ndepend != ndepend_debug, caller = ", caller);
301  if (print_debug)
302  print("DependencyInterface::inc_debug: this=", this, " caller=", caller, " ndep=", callers_[caller], " ndepend=", ndepend);
303 #endif
304  }
305 
306  void dec_debug(const char* caller) {
307  callbackT cb;
308  {
309  ScopedMutex<Spinlock> obolus(this);
310  MADNESS_ASSERT(ndepend > 0); // ensure we are valid and decrement can succeed
311 #ifdef MADNESS_TASK_DEBUG_TRACE
312  const auto caller_str = caller;
313  auto it = callers_.find(caller_str);
314  if (it != callers_.end()) {
315  MADNESS_ASSERT(it->second > 0);
316  }
317  else {
318  assert(false && "DependencyInterface::dec_debug() called without matching inc_debug()");
319  }
320 #endif
321  if (ndepend == 1) {
322  cb = std::move(const_cast<callbackT&>(callbacks));
323 #ifdef MADNESS_TASK_DEBUG_TRACE
324  if (ndep() != ndep_debug())
325  error("DependencyInterface::dec_debug(): ndepend != ndepend_debug, caller = ", caller);
326  if (print_debug)
327  print("DependencyInterface::dec_debug: callback spawned, this=", this, " caller=", caller, " ndep=", it->second-1, " ndepend=", ndepend-1);
328 #endif
329  if (final_callback) {
331  // make object invalid
332  ndepend = -1;
333  }
334  }
335 #ifdef MADNESS_TASK_DEBUG_TRACE
336  else {
337  if (print_debug)
338  print("DependencyInterface::dec_debug: this=", this, " caller=", caller, " ndep=", it->second-1, " ndepend=", ndepend-1);
339  }
340 #endif
341  // NB safe to update ndepend now, was not safe to do that before since that makes it observable and
342  // e.g. result in its destruction before all changes to state are done
343 #ifdef MADNESS_TASK_DEBUG_TRACE
344  it->second -= 1;
345 #endif
346  --ndepend;
347  }
348  do_callbacks(cb);
349  }
350 
351  /// Destructor.
353 #ifdef MADNESS_ASSERTIONS_THROW
354  if(ndepend > 0)
355  error("DependencyInterface::~DependencyInterface(): ndepend =", ndepend);
356 #else
357  MADNESS_ASSERT(ndepend <= 0); // ensure no outstanding dependencies
358 #endif
359 #ifdef MADNESS_TASK_DEBUG_TRACE
360  if (!callers_.empty()) {
361  MADNESS_ASSERT(max_ndepend > 0);
362  if (print_debug)
363  print("DependencyInterface dtor: this=", this, " max_ndepend=", max_ndepend);
364  }
365 #endif
366 #ifdef MADNESS_TASK_DEBUG_TRACE
367  for(const auto& c: callers_) {
368  if (c.second != 0) {
369  const auto error_msg = std::string("ndepend=") + std::to_string(c.second) + " for caller " + c.first;
370  error("DependencyInterface::~DependencyInterface(): ", error_msg);
371  }
372  }
373 #endif
374  }
375 
376 private:
377 #ifdef MADNESS_TASK_DEBUG_TRACE
378  std::unordered_map<std::string, int> callers_;
379 #endif
380  };
381 }
382 #endif // MADNESS_WORLD_DEPENDENCY_INTERFACE_H__INCLUDED
Implements AtomicInt.
The class used for callbacks (e.g., dependency tracking).
Definition: dependency_interface.h:61
virtual void notify()=0
Invoked by the callback to notify when a dependency is satisfied.
virtual void notify_debug(const char *caller)
Same as notify(), but tracks how many times called from each caller.
Definition: dependency_interface.h:67
virtual void notify_debug_impl(const char *caller)
Definition: dependency_interface.h:76
virtual ~CallbackInterface()
Definition: dependency_interface.h:73
Provides an interface for tracking dependencies.
Definition: dependency_interface.h:100
int ndep() const
Returns the number of unsatisfied dependencies.
Definition: dependency_interface.h:160
void inc()
Increment the number of dependencies.
Definition: dependency_interface.h:251
void register_final_callback(CallbackInterface *callback)
Registers the final callback to be executed when ndepend==0; immediately invoked if ndepend==0.
Definition: dependency_interface.h:229
virtual ~DependencyInterface()
Destructor.
Definition: dependency_interface.h:352
void dec()
Decrement the number of dependencies and invoke the callback if ndepend==0.
Definition: dependency_interface.h:262
bool probe() const
Returns true if ndepend == 0 (no unsatisfied dependencies).
Definition: dependency_interface.h:178
void register_callback(CallbackInterface *callback)
Registers a callback that will be executed when ndepend==0; immediately invoked if ndepend==0.
Definition: dependency_interface.h:201
void dec_debug(const char *caller)
Definition: dependency_interface.h:306
volatile callbackT callbacks
Called ONCE by dec() when ndepend==0.
Definition: dependency_interface.h:109
std::atomic< int > ndepend
Counts dependencies. For a valid object ndepend >= 0, after the final callback is executed ndepend is...
Definition: dependency_interface.h:105
volatile CallbackInterface * final_callback
The "final" callback can destroy the task, always invoked last, the object is in an invalid state (nd...
Definition: dependency_interface.h:111
void notify()
Invoked by callbacks to notify of dependencies being satisfied.
Definition: dependency_interface.h:183
static const int MAXCALLBACKS
Maximum number of callbacks.
Definition: dependency_interface.h:107
void inc_debug(const char *caller)
Same as inc(), but keeps track of caller; calling dec_debug() will signal error if no matching inc_de...
Definition: dependency_interface.h:287
void do_callbacks(callbackT &cb) const
Definition: dependency_interface.h:125
void notify_debug(const char *caller)
Overload of CallbackInterface::notify_debug(), updates dec()
Definition: dependency_interface.h:189
DependencyInterface(int ndep=0)
Definition: dependency_interface.h:136
DependencyInterface(int ndep, const char *caller)
Definition: dependency_interface.h:144
Mutex that is applied/released at start/end of a scope.
Definition: worldmutex.h:239
Spinlock using pthread spinlock operations.
Definition: worldmutex.h:253
Dynamically sized Stack with small stack size optimization.
Definition: stack.h:154
bool empty() const
Check if the stack is empty.
Definition: stack.h:387
reference top()
Get the last item pushed onto the stack.
Definition: stack.h:355
void push(const_reference value)
Push a new item onto the stack.
Definition: stack.h:318
void pop()
Pop an item off of the stack.
Definition: stack.h:345
#define max(a, b)
Definition: lda.h:51
#define MADNESS_ASSERT(condition)
Assert a condition that should be free of side-effects since in release builds this might be a no-op.
Definition: madness_exception.h:134
File holds all helper structures necessary for the CC_Operator and CC2 class.
Definition: DFParameters.h:10
void print(const T &t, const Ts &... ts)
Print items to std::cout (items separated by spaces) and terminate with a new line.
Definition: print.h:225
void error(const char *msg)
Definition: world.cc:139
Defines simple templates for printing to std::cout "a la Python".
static const double c
Definition: relops.cc:10
Implement Stack for a fixed-size stack container.
Declares the World class for the parallel runtime environment.
Implements Mutex, MutexFair, Spinlock, ConditionVariable.