From 2e6c3bf33ab1cd75b9936e65568a39571f279fc3 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Wed, 9 Mar 2022 11:12:12 +0200 Subject: Parallel implementation of update_during_match_prerequisites() --- libbuild2/adhoc-rule-buildscript.cxx | 5 +- libbuild2/algorithm.cxx | 118 ++++++++++++++++++++++++++++------- libbuild2/algorithm.hxx | 16 ++--- libbuild2/algorithm.ixx | 40 +++++++++++- libbuild2/cc/link-rule.cxx | 5 +- 5 files changed, 150 insertions(+), 34 deletions(-) diff --git a/libbuild2/adhoc-rule-buildscript.cxx b/libbuild2/adhoc-rule-buildscript.cxx index 25ef1b7..d91be65 100644 --- a/libbuild2/adhoc-rule-buildscript.cxx +++ b/libbuild2/adhoc-rule-buildscript.cxx @@ -459,10 +459,11 @@ namespace build2 // Note that we ignore the result and whether it renders us out of date, // leaving it to the common execute logic in perform_update_*(). // - // Note also that update_during_match() spoils prerequisite_target::data. + // Note also that update_during_match_prerequisites() spoils + // prerequisite_target::data. // if (a == perform_update_id) - update_during_match (trace, a, pts, 2 /* mask */); + update_during_match_prerequisites (trace, a, xt, 2 /* mask */); // See if this is not update or not on a file-based target. // diff --git a/libbuild2/algorithm.cxx b/libbuild2/algorithm.cxx index d72e95e..c101117 100644 --- a/libbuild2/algorithm.cxx +++ b/libbuild2/algorithm.cxx @@ -1922,7 +1922,6 @@ namespace build2 size_t gd (ctx.dependency_count.fetch_sub (1, memory_order_relaxed)); size_t td (s.dependents.fetch_sub (1, memory_order_release)); assert (td != 0 && gd != 0); - td--; // Handle the "last" execution mode. // @@ -1945,7 +1944,7 @@ namespace build2 // thread. For other threads the state will still be unknown (until they // try to execute it). // - if (ctx.current_mode == execution_mode::last && td != 0) + if (ctx.current_mode == execution_mode::last && --td != 0) return target_state::postponed; // Try to atomically change applied to busy. @@ -2007,14 +2006,17 @@ namespace build2 } target_state - execute_direct (action a, const target& ct) + execute_direct (action a, + const target& ct, + size_t start_count, + atomic_count* task_count) { context& ctx (ct.ctx); target& t (const_cast (ct)); // MT-aware. target::opstate& s (t[a]); - // Similar logic to match() above except we execute synchronously. + // Similar logic to execute() above. // size_t tc (ctx.count_applied ()); @@ -2028,7 +2030,23 @@ namespace build2 memory_order_acquire)) // Synchronize on failure. { if (s.state == target_state::unknown) - execute_impl (a, t); + { + if (task_count == nullptr) + return execute_impl (a, t); + + if (ctx.sched.async (start_count, + *task_count, + [a] (const diag_frame* ds, target& t) + { + diag_frame::stack_guard dsg (ds); + execute_impl (a, t); + }, + diag_frame::stack (), + ref (t))) + return target_state::unknown; // Queued. + + // Executed synchronously, fall through. + } else { assert (s.state == target_state::unchanged || @@ -2046,15 +2064,13 @@ namespace build2 } else { - // If the target is busy, wait for it. - // - if (tc >= busy) - ctx.sched.wait (exec, s.task_count, scheduler::work_none); - else - assert (tc == exec); + // Either busy or already executed. + // + if (tc >= busy) return target_state::busy; + else assert (tc == exec); } - return t.executed_state (a); + return t.executed_state (a, false); } bool @@ -2120,16 +2136,17 @@ namespace build2 } bool - update_during_match (tracer& trace, - action a, - prerequisite_targets& pts, - uintptr_t mask) + update_during_match_prerequisites (tracer& trace, + action a, target& t, + uintptr_t mask) { + prerequisite_targets& pts (t.prerequisite_targets[a]); + // On the first pass detect and handle unchanged tragets. Note that we // have to do it in a separate pass since we cannot call matched_state() // once we've switched the phase. // - context* ctx (nullptr); + size_t n (0); for (prerequisite_target& p: pts) { @@ -2143,9 +2160,7 @@ namespace build2 if (os != target_state::unchanged) { - if (ctx == nullptr) - ctx = &pt.ctx; - + ++n; p.data = static_cast (os); continue; } @@ -2157,13 +2172,19 @@ namespace build2 // If all unchanged, we are done. // - if (ctx == nullptr) + if (n == 0) return false; - phase_switch ps (*ctx, run_phase::execute); + context& ctx (t.ctx); + + phase_switch ps (ctx, run_phase::execute); bool r (false); + // @@ Maybe we should optimize for n == 1? + // + +#if 0 for (prerequisite_target& p: pts) { if ((p.include & mask) != 0 && p.data != 0) @@ -2184,6 +2205,59 @@ namespace build2 p.data = 0; } } +#else + + // Start asynchronous execution of prerequisites. Similar logic to + // straight_execute_members(). + // + // Note that the target's task count is expected to be busy (since this + // function is called during match). And there don't seem to be any + // problems in using it for execute. + // + atomic_count& tc (t[a].task_count); + + size_t busy (ctx.count_busy ()); + size_t exec (ctx.count_executed ()); + + wait_guard wg (ctx, busy, tc); + + for (prerequisite_target& p: pts) + { + if ((p.include & mask) != 0 && p.data != 0) + { + execute_direct_async (a, *p.target, busy, tc); + } + } + + wg.wait (); + + // Finish execution and process the result. + // + for (prerequisite_target& p: pts) + { + if ((p.include & mask) != 0 && p.data != 0) + { + const target& pt (*p.target); + + // If the target is still busy, wait for its completion. + // + ctx.sched.wait (exec, pt[a].task_count, scheduler::work_none); + + target_state os (static_cast (p.data)); + target_state ns (pt.executed_state (a)); + + if (ns != os && ns != target_state::unchanged) + { + l6 ([&]{trace << "updated " << pt + << "; old state " << os + << "; new state " << ns;}); + r = true; + } + + p.data = 0; + } + } +#endif return r; } diff --git a/libbuild2/algorithm.hxx b/libbuild2/algorithm.hxx index 788138b..f6c296e 100644 --- a/libbuild2/algorithm.hxx +++ b/libbuild2/algorithm.hxx @@ -589,12 +589,17 @@ namespace build2 // relationship (so no dependents count is decremented) and execution order // (so this function never returns the postponed target state). // - // Note: waits for the completion if the target is busy and translates - // target_state::failed to the failed exception. + // Note: the first version waits for the completion if the target is busy + // and translates target_state::failed to the failed exception. // - LIBBUILD2_SYMEXPORT target_state + target_state execute_direct (action, const target&); + target_state + execute_direct_async (action, const target&, + size_t start_count, atomic_count& task_count, + bool fail = true); + // Update the target during the match phase (by switching the phase and // calling execute_direct()). Return true if the target has changed or, if // the passed timestamp is not timestamp_unknown, it is older than the @@ -617,10 +622,7 @@ namespace build2 // for temporary storage). But it resets data to 0 once done. // LIBBUILD2_SYMEXPORT bool - update_during_match (tracer&, - action, - prerequisite_targets&, - uintptr_t mask); + update_during_match_prerequisites (tracer&, action, target&, uintptr_t mask); // The default prerequisite execute implementation. Call execute_async() on // each non-ignored (non-NULL) prerequisite target in a loop and then wait diff --git a/libbuild2/algorithm.ixx b/libbuild2/algorithm.ixx index bdf0815..29a4b59 100644 --- a/libbuild2/algorithm.ixx +++ b/libbuild2/algorithm.ixx @@ -688,6 +688,8 @@ namespace build2 inline target_state execute_wait (action a, const target& t) { + //@@ redo + if (execute (a, t) == target_state::busy) t.ctx.sched.wait (t.ctx.count_executed (), t[a].task_count, @@ -703,7 +705,43 @@ namespace build2 { target_state r (execute (a, t, sc, &tc)); - if (fail && !t.ctx.keep_going && r == target_state::failed) + if (r == target_state::failed && fail && !t.ctx.keep_going) + throw failed (); + + return r; + } + + LIBBUILD2_SYMEXPORT target_state + execute_direct (action, const target&, size_t, atomic_count*); + + inline target_state + execute_direct (action a, const target& t) + { + target_state r (execute_direct (a, t, 0, nullptr)); + + if (r == target_state::busy) + { + t.ctx.sched.wait (t.ctx.count_executed (), + t[a].task_count, + scheduler::work_none); + + r = t.executed_state (a, false); + } + + if (r == target_state::failed) + throw failed (); + + return r; + } + + inline target_state + execute_direct_async (action a, const target& t, + size_t sc, atomic_count& tc, + bool fail) + { + target_state r (execute_direct (a, t, sc, &tc)); + + if (r == target_state::failed && fail && !t.ctx.keep_going) throw failed (); return r; diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx index b72e5a0..97834fd 100644 --- a/libbuild2/cc/link-rule.cxx +++ b/libbuild2/cc/link-rule.cxx @@ -1229,10 +1229,11 @@ namespace build2 // Note that we ignore the result and whether it renders us out of date, // leaving it to the common execute logic in perform_update(). // - // Note also that update_during_match() spoils prerequisite_target::data. + // Note also that update_during_match_prerequisites() spoils + // prerequisite_target::data. // if (update_match) - update_during_match (trace, a, pts, 2 /* mask */); + update_during_match_prerequisites (trace, a, t, 2 /* mask */); // Check if we have any binful utility libraries. // -- cgit v1.1