1 // (C) Copyright 2013-2015 Steven R. Brandt 2 // 3 // Distributed under the Boost Software License, Version 1.0. (See accompanying 4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 5 // 6 // How do guards work: 7 // Pythonesque pseudocode 8 // 9 // class guard: 10 // task # an atomic pointer to a guard_task 11 // 12 // class guard_task: 13 // run # a function pointer of some kind 14 // next # an atomic pointer to another guard task 15 // 16 // def run_guarded(g,func): 17 // n = new guard_task 18 // n.run = func 19 // t = g.task.exchange(n) 20 // if t == nullptr: 21 // run_task(n) 22 // else: 23 // zero = nullptr 24 // if t.next.compare_exchange_strong(zero,n): 25 // pass 26 // else: 27 // run_task(n) 28 // delete t 29 // 30 // def run_task(t): 31 // t.run() // call the task 32 // zero = nullptr 33 // if t.next.compare_exchange_strong(zero,t): 34 // pass 35 // else: 36 // run_task(zero) 37 // delete t 38 // 39 // Consider cases. Thread A, B, and C on guard g. 40 // Case 1: 41 // Thread A runs on guard g, gets t == nullptr and runs to completion. 42 // Thread B starts, gets t != null, compare_exchange_strong fails, 43 // it runs to completion and deletes t 44 // Thread C starts, gets t != null, compare_exchange_strong fails, 45 // it runs to completion and deletes t 46 // 47 // Case 2: 48 // Thread A runs on guard g, gets t == nullptr, 49 // but before it completes, thread B starts. 50 // Thread B runs on guard g, gets t != nullptr, 51 // compare_exchange_strong succeeds. It does nothing further. 52 // Thread A resumes and finishes, compare_exchange_strong fails, 53 // it runs B's task to completion. 54 // Thread C starts, gets t != null, compare_exchange_strong fails, 55 // it runs to completion and deletes t 56 // 57 // Case 3: 58 // Thread A runs on guard g, gets t == nullptr, 59 // but before it completes, thread B starts. 60 // Thread B runs on guard g, gets t != nullptr, 61 // compare_exchange_strong succeeds, It does nothing further. 62 // Thread C runs on guard g, gets t != nullptr, 63 // compare_exchange_strong succeeds, It does nothing further. 64 // Thread A resumes and finishes, compare_exchange_strong fails, 65 // it runs B's task to completion. 66 // Thread B does compare_exchange_strong fails, 67 // it runs C's task to completion. 68 // 69 // def destructor guard: 70 // t = g.load() 71 // if t == nullptr: 72 // pass 73 // else: 74 // zero = nullptr 75 // if t.next.compare_exchange_strong(zero,empty): 76 // pass 77 // else: 78 // delete t 79 80 #ifndef HPX_LCOS_LOCAL_COMPOSABLE_GUARD_HPP 81 #define HPX_LCOS_LOCAL_COMPOSABLE_GUARD_HPP 82 83 #include <hpx/config.hpp> 84 #include <hpx/util/assert.hpp> 85 #include <hpx/util/deferred_call.hpp> 86 #include <hpx/util/unique_function.hpp> 87 #include <hpx/util_fwd.hpp> 88 #include <hpx/lcos/local/packaged_task.hpp> 89 90 #include <atomic> 91 #include <cstddef> 92 #include <memory> 93 #include <utility> 94 #include <vector> 95 96 namespace hpx { namespace lcos { namespace local 97 { 98 namespace detail 99 { 100 struct debug_object 101 { 102 #ifdef HPX_DEBUG 103 HPX_STATIC_CONSTEXPR int debug_magic = 0x2cab; 104 105 int magic; 106 debug_objecthpx::lcos::local::detail::debug_object107 debug_object() 108 : magic(debug_magic) 109 {} 110 ~debug_objecthpx::lcos::local::detail::debug_object111 ~debug_object() { 112 check_(); 113 magic = ~debug_magic; 114 } 115 check_hpx::lcos::local::detail::debug_object116 void check_() { 117 HPX_ASSERT(magic != ~debug_magic); 118 HPX_ASSERT(magic == debug_magic); 119 } 120 #else 121 void check_() {} 122 #endif 123 }; 124 125 struct guard_task; 126 127 typedef std::atomic<guard_task*> guard_atomic; 128 129 HPX_API_EXPORT void free(guard_task* task); 130 131 typedef util::unique_function_nonser<void()> guard_function; 132 } 133 134 class guard : public detail::debug_object 135 { 136 public: 137 detail::guard_atomic task; 138 guard()139 guard() : task(nullptr) {} 140 HPX_API_EXPORT ~guard(); 141 }; 142 143 class guard_set : public detail::debug_object 144 { 145 std::vector<std::shared_ptr<guard> > guards; 146 // the guards need to be sorted, but we don't 147 // want to sort them more often than necessary 148 bool sorted; 149 150 void sort(); 151 152 public: guard_set()153 guard_set() : guards(), sorted(true) {} ~guard_set()154 ~guard_set() {} 155 get(std::size_t i)156 std::shared_ptr<guard> get(std::size_t i) { return guards[i]; } 157 add(std::shared_ptr<guard> const & guard_ptr)158 void add(std::shared_ptr<guard> const& guard_ptr) { 159 HPX_ASSERT(guard_ptr.get() != nullptr); 160 guards.push_back(guard_ptr); 161 sorted = false; 162 } 163 size()164 std::size_t size() { 165 return guards.size(); 166 } 167 168 friend HPX_API_EXPORT void run_guarded( 169 guard_set& guards, detail::guard_function task); 170 }; 171 172 /// Conceptually, a guard acts like a mutex on an asynchronous task. The 173 /// mutex is locked before the task runs, and unlocked afterwards. 174 HPX_API_EXPORT void run_guarded(guard& guard, detail::guard_function task); 175 176 template <typename F, typename ...Args> run_guarded(guard & guard,F && f,Args &&...args)177 void run_guarded(guard& guard, F&& f, Args&&... args) 178 { 179 return run_guarded(guard, detail::guard_function( 180 util::deferred_call(std::forward<F>(f), std::forward<Args>(args)...))); 181 } 182 183 /// Conceptually, a guard_set acts like a set of mutexes on an asynchronous task. 184 /// The mutexes are locked before the task runs, and unlocked afterwards. 185 HPX_API_EXPORT void run_guarded(guard_set& guards, detail::guard_function task); 186 187 template <typename F, typename ...Args> run_guarded(guard_set & guards,F && f,Args &&...args)188 void run_guarded(guard_set& guards, F&& f, Args&&... args) 189 { 190 return run_guarded(guards, detail::guard_function( 191 util::deferred_call(std::forward<F>(f), std::forward<Args>(args)...))); 192 } 193 }}} 194 195 #endif /*HPX_LCOS_LOCAL_COMPOSABLE_GUARD_HPP*/ 196