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
58namespace 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.
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 {
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) {
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
376private:
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
Stack< CallbackInterface *, MAXCALLBACKS > callbackT
Definition dependency_interface.h:108
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
#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
Namespace for all elements and tools of MADNESS.
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.