From 5cefca444f7062c61cc9d118ffea5901e05186fd Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Wed, 8 Feb 2017 07:42:41 +0200 Subject: Implement parallel operation execution --- build2/algorithm | 84 ++++++++++++++----- build2/algorithm.cxx | 190 +++++++++++++++++++++++++++++++++++++------ build2/algorithm.ixx | 37 +++++++++ build2/bin/rule.cxx | 17 +--- build2/cc/compile.cxx | 7 +- build2/config/operation.cxx | 4 +- build2/dist/operation.cxx | 2 +- build2/install/rule.cxx | 2 +- build2/operation | 2 +- build2/operation.cxx | 59 +++++--------- build2/scheduler.cxx | 8 +- build2/target | 42 +++++----- build2/target.ixx | 33 ++++++++ build2/test/rule.cxx | 13 +-- build2/test/script/regex.cxx | 6 +- build2/utility | 1 + 16 files changed, 363 insertions(+), 144 deletions(-) diff --git a/build2/algorithm b/build2/algorithm index 5bfa1e0..2243c47 100644 --- a/build2/algorithm +++ b/build2/algorithm @@ -147,38 +147,47 @@ namespace build2 fsdir* inject_fsdir (slock&, action, target&, bool parent = true); - // Execute the action on target, assuming a rule has been matched - // and the recipe for this action has been set. This is the default - // executor implementation. Decrements the dependents count. + // Execute the action on target, assuming a rule has been matched and the + // recipe for this action has been set. This is the synchrounous executor + // implementation (but may still return target_state::busy is the target + // is already being executed). Decrements the dependents count. // target_state execute (action, const target&); - // Execute the recipe obtained with match_delegate(). Note that - // the target's state is neither checked nor updated by this - // function. In other words, the appropriate usage is to call - // this function from another recipe and to factor the obtained - // state into the one returned. + // As above but start asynchronous execution. Return target_state::unknown + // if the asynchrounous execution has been started and target_state::busy if + // the target has already been busy. + // + target_state + execute_async (action, const target&, + size_t start_count, atomic_count& task_count); + + // Execute the recipe obtained with match_delegate(). Note that the target's + // state is neither checked nor updated by this function. In other words, + // the appropriate usage is to call this function from another recipe and to + // factor the obtained state into the one returned. // target_state execute_delegate (const recipe&, action, const target&); - // A special version of the above that should be used for "direct" - // and "now" execution, that is, side-stepping the normal target- - // prerequisite relationship (so no dependents count is decremented) - // and execution order (so this function will never return postponed - // target state). It will also wait for the completion if the target - // is busy. + // A special version of the above that should be used for "direct" and "now" + // execution, that is, side-stepping the normal target- prerequisite + // relationship (so no dependents count is decremented) and execution order + // (so this function will never return postponed target state). It will also + // wait for the completion if the target is busy. // target_state execute_direct (action, const target&); - // The default prerequisite execute implementation. It calls execute() - // on each non-ignored (non-NULL) prerequisite target in a loop. If this - // target is a member of a group, then it first does this to the group's - // prerequisites. Returns target_state::changed if any of them were - // changed and target_state::unchanged otherwise. Note that this - // function can be used as a recipe. + // The default prerequisite execute implementation. Call execute_async() on + // each non-ignored (non-NULL) prerequisite target in a loop and then wait + // for their completion. Return target_state::changed if any of them were + // changed and target_state::unchanged otherwise. If a prerequisite's + // execution is postponed, then set its pointer in prerequisite_targets to + // NULL (since its state cannot be queried MT-safely). + // + // Note that this function can be used as a recipe. // target_state execute_prerequisites (action, const target&); @@ -240,6 +249,41 @@ namespace build2 const timestamp&, const prerequisite_filter& = nullptr); + // Execute members of a group or similar prerequisite-like dependencies. + // Similar in semantics to execute_prerequisites(). + // + target_state + straight_execute_members (action, const target&, const target*[], size_t); + + target_state + reverse_execute_members (action, const target&, const target*[], size_t); + + // Call straight or reverse depending on the current mode. + // + target_state + execute_members (action, const target&, const target*[], size_t); + + template + inline target_state + straight_execute_members (action a, const target& t, const target* (&ts)[N]) + { + return straight_execute_members (a, t, ts, N); + } + + template + inline target_state + reverse_execute_members (action a, const target& t, const target* (&ts)[N]) + { + return reverse_execute_members (a, t, ts, N); + } + + template + inline target_state + execute_members (action a, const target& t, const target* (&ts)[N]) + { + return execute_members (a, t, ts, N); + } + // Return noop_recipe instead of using this function directly. // target_state diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx index 74e7d7d..1ede115 100644 --- a/build2/algorithm.cxx +++ b/build2/algorithm.cxx @@ -422,18 +422,19 @@ namespace build2 } target_state - execute (action a, const target& ct) + execute (action a, + const target& ct, + size_t start_count, + atomic_count* task_count) { target& t (const_cast (ct)); // MT-aware. // text << "E " << t << ": " << t.dependents << " " << dependency_count; - size_t d (0); - if (dependency_count != 0) // Re-examination of a postponed target? + // Update dependency counts and make sure they are not skew. + // + size_t d; { - // Note that re-examination only happens during serial execution so - // dependency_count can only become 0 if we have skew counts. - // // Note: memory order can probably be relaxed. // size_t g (dependency_count--); @@ -483,14 +484,27 @@ namespace build2 if (t.task_count.compare_exchange_strong (tc, target::count_executing) || (tc == target::count_postponed && t.task_count.compare_exchange_strong (tc, target::count_executing))) - return execute_impl (a, t); + { + if (task_count == nullptr) + return execute_impl (a, t); + + sched.async (start_count, + *task_count, + [a] (target& t) + { + execute_impl (a, t); // @@ MT exception handling. + }, + ref (t)); + + return target_state::unknown; + } } switch (tc) { case target::count_unexecuted: assert (false); case target::count_postponed: return target_state::postponed; - case target::count_executed: return t.state (); + case target::count_executed: return t.synchronized_state (); default: return target_state::busy; } } @@ -515,36 +529,136 @@ namespace build2 t.task_count); } - return t.state (); + return t.synchronized_state (); + } + + // We use the last bit of a pointer to target in prerequisite_targets as a + // flag to indicate whether the target was already busy. Probably not worth + // it (we are saving an atomic load), but what the hell. + // + // VC15 doesn't like if we use (abstract) target here. + // + static_assert (alignof (file) % 2 == 0, "unexpected target alignment"); + + static inline void + set_busy (const target*& p) + { + uintptr_t i (reinterpret_cast (p)); + i |= 0x01; + p = reinterpret_cast (i); + } + + static inline bool + get_busy (const target*& p) + { + uintptr_t i (reinterpret_cast (p)); + + if ((i & 0x01) != 0) + { + i &= ~uintptr_t (0x01); + p = reinterpret_cast (i); + return true; + } + + return false; } target_state - execute_prerequisites (action a, const target& t) + straight_execute_members (action a, + const target& t, + const target* ts[], + size_t n) { target_state r (target_state::unchanged); - for (const target* pt: t.prerequisite_targets) + // Start asynchronous execution of prerequisites. + // + for (size_t i (0); i != n; ++i) { - if (pt == nullptr) // Skipped. + const target*& mt (ts[i]); + + if (mt == nullptr) // Skipped. continue; - r |= execute (a, *pt); + target_state s ( + execute_async ( + a, *mt, target::count_executing, t.task_count)); + + if (s == target_state::postponed) + { + r |= s; + mt = nullptr; + } + else if (s == target_state::busy) + set_busy (mt); + } + sched.wait (target::count_executing, t.task_count); + + // Now all the targets in prerequisite_targets must be executed and + // synchronized (and we have blanked out all the postponed ones). + // + for (size_t i (0); i != n; ++i) + { + const target*& mt (ts[i]); + + if (mt == nullptr) + continue; + + // If the target was already busy, wait for its completion. + // + if (get_busy (mt)) + sched.wait (target::count_executed, mt->task_count); + + r |= mt->synchronized_state (); } return r; } target_state - reverse_execute_prerequisites (action a, const target& t) + reverse_execute_members (action a, + const target& t, + const target* ts[], + size_t n) { + // Pretty much as straight_execute_members() but in reverse order. + // target_state r (target_state::unchanged); - for (const target* pt: reverse_iterate (t.prerequisite_targets)) + for (size_t i (n); i != 0; --i) { - if (pt == nullptr) // Skipped. + const target*& mt (ts[i - 1]); + + if (mt == nullptr) continue; - r |= execute (a, *pt); + target_state s ( + execute_async ( + a, *mt, target::count_executing, t.task_count)); + + if (s == target_state::postponed) + { + r |= s; + mt = nullptr; + } + else if (s == target_state::busy) + set_busy (mt); + } + sched.wait (target::count_executing, t.task_count); + + for (size_t i (n); i != 0; --i) + { + const target*& mt (ts[i - 1]); + + if (mt == nullptr) + continue; + + // If the target was already busy, wait for its completion. + // + if (get_busy (mt)) + sched.wait (target::count_executed, mt->task_count); + + r |= mt->synchronized_state (); } return r; @@ -555,18 +669,44 @@ namespace build2 action a, const target& t, const timestamp& mt, const prerequisite_filter& pf) { - bool e (mt == timestamp_nonexistent); + // Pretty much as straight_execute_members() but hairier. + // + target_state rs (target_state::unchanged); + + for (const target*& pt: t.prerequisite_targets) + { + if (pt == nullptr) // Skipped. + continue; + target_state s ( + execute_async ( + a, *pt, target::count_executing, t.task_count)); + + if (s == target_state::postponed) + { + rs |= s; + pt = nullptr; + } + else if (s == target_state::busy) + set_busy (pt); + } + sched.wait (target::count_executing, t.task_count); + + bool e (mt == timestamp_nonexistent); const target* rt (tt != nullptr ? nullptr : &t); - target_state rs (target_state::unchanged); - for (const target* pt: t.prerequisite_targets) + for (const target*& pt: t.prerequisite_targets) { - if (pt == nullptr) // Skip ignored. + if (pt == nullptr) continue; - target_state ts (execute (a, *pt)); - rs |= ts; + // If the target was already busy, wait for its completion. + // + if (get_busy (pt)) + sched.wait (target::count_executed, pt->task_count); + + target_state s (pt->synchronized_state ()); + rs |= s; // Should we compare the timestamp to this target's? // @@ -581,14 +721,14 @@ namespace build2 // The same logic as in mtime_target::newer() (but avoids a call to // state()). // - if (mt < mp || (mt == mp && ts == target_state::changed)) + if (mt < mp || (mt == mp && s == target_state::changed)) e = true; } else { // Otherwise we assume the prerequisite is newer if it was changed. // - if (ts == target_state::changed) + if (s == target_state::changed) e = true; } } diff --git a/build2/algorithm.ixx b/build2/algorithm.ixx index b8c33d4..9ff56f8 100644 --- a/build2/algorithm.ixx +++ b/build2/algorithm.ixx @@ -172,12 +172,41 @@ namespace build2 search_and_match_prerequisite_members (ml, a, t, &s); } + target_state + execute (action, const target&, size_t, atomic_count*); + + inline target_state + execute (action a, const target& t) + { + return execute (a, t, 0, nullptr); + } + + inline target_state + execute_async (action a, const target& t, size_t sc, atomic_count& tc) + { + return execute (a, t, sc, &tc); + } + inline target_state execute_delegate (const recipe& r, action a, const target& t) { return r (a, t); } + inline target_state + execute_prerequisites (action a, const target& t) + { + auto& p (t.prerequisite_targets); + return straight_execute_members (a, t, p.data (), p.size ()); + } + + inline target_state + reverse_execute_prerequisites (action a, const target& t) + { + auto& p (t.prerequisite_targets); + return reverse_execute_members (a, t, p.data (), p.size ()); + } + // If the first argument is NULL, then the result is treated as a boolean // value. // @@ -220,4 +249,12 @@ namespace build2 auto p (execute_prerequisites (tt, a, t, mt, pf)); return make_pair (static_cast (p.first), p.second); } + + inline target_state + execute_members (action a, const target& t, const target* ts[], size_t n) + { + return current_mode == execution_mode::first + ? straight_execute_members (a, t, ts, n) + : reverse_execute_members (a, t, ts, n); + } } diff --git a/build2/bin/rule.cxx b/build2/bin/rule.cxx index 9adb692..ea84971 100644 --- a/build2/bin/rule.cxx +++ b/build2/bin/rule.cxx @@ -134,21 +134,8 @@ namespace build2 bool a (type == "static" || type == "both"); bool s (type == "shared" || type == "both"); - target* m1 (a ? t.a : nullptr); - target* m2 (s ? t.s : nullptr); - - if (current_mode == execution_mode::last) - swap (m1, m2); - - target_state r (target_state::unchanged); - - if (m1 != nullptr) - r |= execute (act, *m1); - - if (m2 != nullptr) - r |= execute (act, *m2); - - return r; + const target* m[] = {a ? t.a : nullptr, s ? t.s : nullptr}; + return execute_members (act, t, m); } } } diff --git a/build2/cc/compile.cxx b/build2/cc/compile.cxx index 5090f11..e08b40b 100644 --- a/build2/cc/compile.cxx +++ b/build2/cc/compile.cxx @@ -891,14 +891,17 @@ namespace build2 // auto update = [&trace, a] (path_target& pt, timestamp ts) -> bool { - if (pt.state () != target_state::unchanged) + //@@ MT extenal modification sync. + + target_state os (pt.atomic_state ()); //@@ MT: do we need atomic? + + if (os != target_state::unchanged) { // We only want to restart if our call to execute() actually // caused an update. In particular, the target could already // have been in target_state::changed because of a dependency // extraction run for some other source file. // - target_state os (pt.state ()); target_state ns (execute_direct (a, pt)); if (ns != os && ns != target_state::unchanged) diff --git a/build2/config/operation.cxx b/build2/config/operation.cxx index d534dab..7bed621 100644 --- a/build2/config/operation.cxx +++ b/build2/config/operation.cxx @@ -353,7 +353,7 @@ namespace build2 } static void - configure_execute (action a, const action_targets& ts, bool) + configure_execute (action a, action_targets& ts, bool) { // Match rules to configure every operation supported by each // project. Note that we are not calling operation_pre/post() @@ -589,7 +589,7 @@ namespace build2 } static void - disfigure_execute (action a, const action_targets& ts, bool quiet) + disfigure_execute (action a, action_targets& ts, bool quiet) { tracer trace ("disfigure_execute"); diff --git a/build2/dist/operation.cxx b/build2/dist/operation.cxx index 1f9fbbd..df0c7dd 100644 --- a/build2/dist/operation.cxx +++ b/build2/dist/operation.cxx @@ -55,7 +55,7 @@ namespace build2 } static void - dist_execute (action, const action_targets& ts, bool) + dist_execute (action, action_targets& ts, bool) { tracer trace ("dist_execute"); diff --git a/build2/install/rule.cxx b/build2/install/rule.cxx index 3a5bd3d..45e4710 100644 --- a/build2/install/rule.cxx +++ b/build2/install/rule.cxx @@ -181,7 +181,7 @@ namespace build2 // will help a lot in case of any static installable content // (headers, documentation, etc). // - if (pt->state () != target_state::unchanged) + if (pt->synchronized_state () != target_state::unchanged) //@@ MT? t.prerequisite_targets.push_back (pt); else unmatch (a, *pt); // No intent to execute. diff --git a/build2/operation b/build2/operation index 4af306d..700ee7e 100644 --- a/build2/operation +++ b/build2/operation @@ -211,7 +211,7 @@ namespace build2 void (*match) (action, action_targets&); - void (*execute) (action, const action_targets&, bool quiet); + void (*execute) (action, action_targets&, bool quiet); void (*operation_post) (operation_id); // End of operation batch. void (*meta_operation_post) (); // End of meta-operation batch. diff --git a/build2/operation.cxx b/build2/operation.cxx index 01f469e..f37d642 100644 --- a/build2/operation.cxx +++ b/build2/operation.cxx @@ -124,60 +124,41 @@ namespace build2 } void - execute (action a, const action_targets& ts, bool quiet) + execute (action a, action_targets& ts, bool quiet) { tracer trace ("execute"); + // Reverse the order of targets if the execution mode is 'last'. + // + if (current_mode == execution_mode::last) + reverse (ts.begin (), ts.end ()); + phase_guard pg (run_phase::execute); - // Execute collecting postponed targets (to be re-examined later). - // Do it in reverse order if the execution mode is 'last'. + // Similar logic to execute_members(): first start asynchronous execution + // of all the top-level targets. // - vector> psp; - - auto body = [a, quiet, &psp, &trace] (const void* v) + atomic_count task_count (0); + for (const void* v: ts) { const target& t (*static_cast (v)); l5 ([&]{trace << diag_doing (a, t);}); - switch (execute (a, t)) - { - case target_state::unchanged: - { - if (!quiet) - info << diag_done (a, t); - break; - } - case target_state::postponed: - psp.push_back (t); - break; - case target_state::changed: - break; - case target_state::failed: - //@@ This could probably happen in a parallel build. - default: - assert (false); - } - }; - - if (current_mode == execution_mode::first) - for (const void* v: ts) body (v); - else - for (const void* v: reverse_iterate (ts)) body (v); + execute_async (a, t, 0, task_count); + } + sched.wait (task_count); - // We should have executed every target that we matched. + // We are now running serially and we should have executed every target + // that we matched. // assert (dependency_count == 0); - // Re-examine postponed targets. This is the only reliable way to - // find out whether the target has changed. - // - // Note: must be serial. - // - for (const target& t: psp) + for (const void* v: ts) { - switch (execute (a, t)) + const target& t (*static_cast (v)); + + switch (t.synchronized_state ()) { case target_state::unchanged: { @@ -190,7 +171,7 @@ namespace build2 case target_state::postponed: assert (false); case target_state::failed: - //@@ This could probably happen in a parallel build. + //@@ MT: This could probably happen in a parallel build. default: assert (false); } diff --git a/build2/scheduler.cxx b/build2/scheduler.cxx index edfa02c..244f6b8 100644 --- a/build2/scheduler.cxx +++ b/build2/scheduler.cxx @@ -84,11 +84,11 @@ namespace build2 // s.tcount = &tc; - // Since we use a mutex for synchronization, we can relax the atomic - // access. + // We could probably relax the atomic access since we use a mutex for + // synchronization though this has a different tradeoff (calling wait + // because we don't see the count). // - while (!(s.shutdown || - tc.load (std::memory_order_relaxed) <= start_count)) + while (!(s.shutdown || tc <= start_count)) s.condv.wait (l); s.waiters--; diff --git a/build2/target b/build2/target index 48c80e7..90aaeec 100644 --- a/build2/target +++ b/build2/target @@ -410,40 +410,35 @@ namespace build2 // subset of the target's state as well as the number of its sub-tasks // (execution of prerequisites). // - // The task starts unexecuted and can then transition to postponed or + // The count starts unexecuted and can then transition to postponed or // executing. Postponed can transition to executing. And executing // transitions (via a decrement) to executed. Once it is executed, then // state_ becomes immutable. // + // The target is said to be synchronized (in this thread) if we have + // either observed the task count to reach count_executed or we have + // successfully changed it (via compare_exchange) to count_executing. + // If the target is synchronized, then we can access and modify (second + // case) its state, mtime, etc. + // static const size_t count_unexecuted = 0; static const size_t count_postponed = 1; static const size_t count_executed = 2; static const size_t count_executing = 3; - atomic_count task_count; + mutable atomic_count task_count; - // @@ MT TODO: when can be called. + // Return the "stapshot" of the target state. That is, unless the target + // has been executed, its state can change asynchronously. // target_state - state () const - { - // We go an extra step and short-circuit to the target state even if the - // raw state is not group provided the recipe is group_recipe. - - if (state_ == target_state::group) - return group->state_; + atomic_state () const; - if (group == nullptr) - return state_; - - if (recipe_function* const* f = recipe_.target ()) - { - if (*f == &group_action) - return group->state_; - } - - return state_; - } + // During execution this function can only be called if we have observed + // (synchronization-wise) that this target has been executed. + // + target_state + synchronized_state () const; // Number of direct targets that depend on this target in the current // action. It is incremented during the match phase and then decremented @@ -1176,6 +1171,8 @@ namespace build2 // Return true if this target is newer than the specified timestamp. // + // Note: can only be called on a synchronized target. + // bool newer (timestamp mt) const { @@ -1186,7 +1183,8 @@ namespace build2 // much we can do here except detect the case where the target was // changed on this run. // - return mt < mp || (mt == mp && state () == target_state::changed); + return mt < mp || (mt == mp && + synchronized_state () == target_state::changed); } protected: diff --git a/build2/target.ixx b/build2/target.ixx index 19e0dfa..68a683a 100644 --- a/build2/target.ixx +++ b/build2/target.ixx @@ -25,6 +25,39 @@ namespace build2 e != nullptr ? optional (*e) : nullopt}; } + inline target_state target:: + atomic_state () const + { + switch (task_count) + { + case target::count_unexecuted: return target_state::unknown; + case target::count_postponed: return target_state::postponed; + case target::count_executed: return synchronized_state (); + default: return target_state::busy; + } + } + + inline target_state target:: + synchronized_state () const + { + // We go an extra step and short-circuit to the target state even if the + // raw state is not group provided the recipe is group_recipe. + + if (state_ == target_state::group) + return group->state_; + + if (group == nullptr) + return state_; + + if (recipe_function* const* f = recipe_.target ()) + { + if (*f == &group_action) + return group->state_; + } + + return state_; + } + // prerequisite_member // inline prerequisite prerequisite_member:: diff --git a/build2/test/rule.cxx b/build2/test/rule.cxx index 35302e1..9dc24cd 100644 --- a/build2/test/rule.cxx +++ b/build2/test/rule.cxx @@ -291,7 +291,7 @@ namespace build2 { build2::match (ml, a, *it); - if (it->state () == target_state::unchanged) + if (it->synchronized_state () == target_state::unchanged) //@@ TM? { unmatch (a, *it); it = nullptr; @@ -304,7 +304,7 @@ namespace build2 { build2::match (ml, a, *ot); - if (ot->state () == target_state::unchanged) + if (ot->synchronized_state () == target_state::unchanged) //@@ MT? { unmatch (a, *ot); ot = nullptr; @@ -337,13 +337,8 @@ namespace build2 // target_state r (execute_delegate (dr, a, t)); - if (it != nullptr) - r |= execute (a, *it); - - if (ot != nullptr) - r |= execute (a, *ot); - - return r; + const target* ts[] = {it, ot}; + return r |= straight_execute_members (a, t, ts); }; } else diff --git a/build2/test/script/regex.cxx b/build2/test/script/regex.cxx index 48e1eeb..b77f8a5 100644 --- a/build2/test/script/regex.cxx +++ b/build2/test/script/regex.cxx @@ -17,13 +17,13 @@ namespace build2 namespace regex { static_assert (alignof (char_string) % 4 == 0, - "inappropriate allignment for char_string"); + "unexpected char_string alignment"); static_assert (alignof (char_regex) % 4 == 0, - "inappropriate allignment for char_regex"); + "unexpected char_regex alignment"); static_assert (sizeof (uintptr_t) > sizeof (int16_t), - "inappropriate uintptr_t size"); + "unexpected uintptr_t size"); const line_char line_char::nul (0); const line_char line_char::eof (-1); diff --git a/build2/utility b/build2/utility index 08971f1..aec3806 100644 --- a/build2/utility +++ b/build2/utility @@ -11,6 +11,7 @@ #include // move(), forward(), declval(), make_pair() #include // assert() #include // make_move_iterator() +#include // * #include // ref(), cref() #include -- cgit v1.1