From b37f1aa6398065be806e6605a023189685669885 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Wed, 15 Feb 2017 03:55:15 +0200 Subject: Implement parallel match --- build2/algorithm.ixx | 277 ++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 210 insertions(+), 67 deletions(-) (limited to 'build2/algorithm.ixx') diff --git a/build2/algorithm.ixx b/build2/algorithm.ixx index 6bbe4bb..83aa050 100644 --- a/build2/algorithm.ixx +++ b/build2/algorithm.ixx @@ -7,18 +7,29 @@ namespace build2 { - inline target& - search (prerequisite& p) + inline const target& + search (const prerequisite& p) { - assert (phase == run_phase::search_match); + assert (phase == run_phase::match); - if (p.target == nullptr) - p.target = &search (p.key ()); + const target* r (p.target.load (memory_order_consume)); - return *p.target; + if (r == nullptr) + { + r = &search (p.key ()); + + const target* e (nullptr); + if (!p.target.compare_exchange_strong ( + e, r, + memory_order_release, + memory_order_consume)) + assert (e == r); + } + + return *r; } - inline target& + inline const target& search (const target_type& t, const prerequisite_key& k) { return search ( @@ -26,7 +37,7 @@ namespace build2 k.proj, {&t, k.tk.dir, k.tk.out, k.tk.name, k.tk.ext}, k.scope}); } - inline target& + inline const target& search (const target_type& type, const dir_path& dir, const dir_path& out, @@ -49,7 +60,7 @@ namespace build2 } template - inline T& + inline const T& search (const dir_path& dir, const dir_path& out, const string& name, @@ -60,110 +71,235 @@ namespace build2 T::static_type, dir, out, name, ext, scope).template as (); } - pair - match_impl (slock&, action, target&, bool apply, const rule* skip = nullptr); + target_lock + lock_impl (action, const target&, optional); - inline bool - match (slock& ml, action a, target& t) + void + unlock_impl (target&, size_t); + + inline void target_lock:: + unlock () + { + if (target != nullptr) + { + unlock_impl (*target, offset); + target = nullptr; + } + } + + inline target* target_lock:: + release () + { + target_type* r (target); + target = nullptr; + return r; + } + + inline target_lock:: + ~target_lock () + { + unlock (); + } + + inline target_lock:: + target_lock (target_lock&& x) + : target (x.release ()), offset (x.offset) + { + } + + inline target_lock& target_lock:: + operator= (target_lock&& x) + { + if (this != &x) + { + unlock (); + target = x.release (); + offset = x.offset; + } + return *this; + } + + inline target_lock + lock (action a, const target& t) + { + // We don't allow locking a target that has already been matched. + // + target_lock r (lock_impl (a, t, scheduler::work_none)); + assert (!r || r.offset == target::offset_touched); + return r; + } + + pair>&, action> + match_impl (action, target&, const rule* skip); + + recipe + apply_impl (target&, + const pair>&, + action); + + target_state + match (action, const target&, size_t, atomic_count*); + + inline target_state + match (action a, const target& t, bool fail) { - assert (phase == run_phase::search_match); + assert (phase == run_phase::match); + + target_state s (match (a, t, 0, nullptr)); - if (!t.recipe (a)) - match_impl (ml, a, t, true); + if (fail && s == target_state::failed) + throw failed (); - dependency_count.fetch_add (1, std::memory_order_release); - bool r (t.dependents++ != 0); // Safe if someone else is also a dependent. + dependency_count.fetch_add (1, memory_order_release); + t.dependents.fetch_add (1, memory_order_release); - // text << "M " << t << ": " << t.dependents << " " << dependency_count; + return s; + } + + inline bool + match (action a, const target& t, unmatch um) + { + assert (phase == run_phase::match); + + target_state s (match (a, t, 0, nullptr)); + + if (s == target_state::failed) + throw failed (); + + switch (um) + { + case unmatch::none: break; + case unmatch::unchanged: + { + if (s == target_state::unchanged) + return true; + + break; + } + case unmatch::safe: + { + // Safe if unchanged or someone else is also a dependent. + // + if (s == target_state::unchanged || + t.dependents.load (memory_order_consume) != 0) + return true; + + break; + } + } + + dependency_count.fetch_add (1, memory_order_release); + t.dependents.fetch_add (1, memory_order_release); + + return false; + } + + inline target_state + match_async (action a, const target& t, + size_t sc, atomic_count& tc, + bool fail) + { + assert (phase == run_phase::match); + target_state r (match (a, t, sc, &tc)); + + if (fail && !keep_going && r == target_state::failed) + throw failed (); return r; } inline void - unmatch (action, target& t) + match_recipe (target_lock& l, recipe r) { - // text << "U " << t << ": " << t.dependents << " " << dependency_count; - - assert (phase == run_phase::search_match); - -#ifndef NDEBUG - size_t td (t.dependents--); - size_t gd (dependency_count--); - assert (td != 0 && gd != 0); -#else - t.dependents.fetch_sub (1, std::memory_order_release); - dependency_count.fetch_sub (1, std::memory_order_release); -#endif + assert (phase == run_phase::match && l.target != nullptr); + + target& t (*l.target); + t.rule = nullptr; // No rule. + t.recipe (move (r)); + l.offset = target::offset_applied; } inline pair - match_delegate (slock& ml, action a, target& t, const rule& r) + match_delegate (action a, target& t, const rule& r) { - assert (phase == run_phase::search_match); - - auto rp (match_impl (ml, a, t, false, &r)); - const match_result& mr (rp.second); - return make_pair (rp.first->apply (ml, mr.recipe_action, t), - mr.recipe_action); + assert (phase == run_phase::match); + auto mr (match_impl (a, t, &r)); + return make_pair (apply_impl (t, mr.first, mr.second), mr.second); } group_view - resolve_group_members_impl (slock& ml, action, target&); + resolve_group_members_impl (action, const target&, target_lock); inline group_view - resolve_group_members (slock& ml, action a, target& g) + resolve_group_members (action a, const target& g) { - assert (phase == run_phase::search_match); + group_view r; + + // We can be called during execute though everything should have been + // already resolved. + // + switch (phase) + { + case run_phase::match: + { + // Grab a target lock to make sure the group state is synchronized. + // + target_lock l (lock_impl (a, g, scheduler::work_none)); + r = g.group_members (a); + + // If the group members are alrealy known or there is nothing else + // we can do, then unlock and return. + // + if (r.members == nullptr && l.offset != target::offset_executed) + r = resolve_group_members_impl (a, g, move (l)); + + break; + } + case run_phase::execute: r = g.group_members (a); break; + case run_phase::load: assert (false); + } - group_view r (g.group_members (a)); - return r.members != nullptr ? r : resolve_group_members_impl (ml, a, g); + return r; } void - search_and_match_prerequisites (slock&, action, target&, const scope*); + match_prerequisites (action, target&, const scope*); void - search_and_match_prerequisite_members (slock&, action, target&, const scope*); + match_prerequisite_members (action, target&, const scope*); inline void - search_and_match_prerequisites (slock& ml, action a, target& t) + match_prerequisites (action a, target& t) { - search_and_match_prerequisites ( - ml, + match_prerequisites ( a, t, (a.operation () != clean_id ? nullptr : &t.root_scope ())); } inline void - search_and_match_prerequisite_members (slock& ml, action a, target& t) + match_prerequisite_members (action a, target& t) { if (a.operation () != clean_id) - search_and_match_prerequisite_members (ml, a, t, nullptr); + match_prerequisite_members (a, t, nullptr); else // Note that here we don't iterate over members even for see- // through groups since the group target should clean eveything // up. A bit of an optimization. // - search_and_match_prerequisites (ml, a, t, &t.root_scope ()); + match_prerequisites (a, t, &t.root_scope ()); } inline void - search_and_match_prerequisites (slock& ml, - action a, - target& t, - const scope& s) + match_prerequisites (action a, target& t, const scope& s) { - search_and_match_prerequisites (ml, a, t, &s); + match_prerequisites (a, t, &s); } inline void - search_and_match_prerequisite_members (slock& ml, - action a, - target& t, - const scope& s) + match_prerequisite_members (action a, target& t, const scope& s) { - search_and_match_prerequisite_members (ml, a, t, &s); + match_prerequisite_members (a, t, &s); } target_state @@ -176,9 +312,16 @@ namespace build2 } inline target_state - execute_async (action a, const target& t, size_t sc, atomic_count& tc) + execute_async (action a, const target& t, + size_t sc, atomic_count& tc, + bool fail) { - return execute (a, t, sc, &tc); + target_state r (execute (a, t, sc, &tc)); + + if (fail && !keep_going && r == target_state::failed) + throw failed (); + + return r; } inline target_state @@ -190,21 +333,21 @@ namespace build2 inline target_state straight_execute_prerequisites (action a, const target& t) { - auto& p (t.prerequisite_targets); + auto& p (const_cast (t).prerequisite_targets); // MT-aware. 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); + auto& p (const_cast (t).prerequisite_targets); // MT-aware. return reverse_execute_members (a, t, p.data (), p.size ()); } inline target_state execute_prerequisites (action a, const target& t) { - auto& p (t.prerequisite_targets); + auto& p (const_cast (t).prerequisite_targets); // MT-aware. return execute_members (a, t, p.data (), p.size ()); } -- cgit v1.1