From 3a71bffd5680d64d19c914aa9dbf1a8fc9f094ef Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 1 Jun 2023 08:49:34 +0200 Subject: Resolve (but disable for now) target_count issue in resolve_members() --- libbuild2/adhoc-rule-buildscript.cxx | 2 + libbuild2/algorithm.cxx | 72 +++++++++---- libbuild2/algorithm.hxx | 6 +- libbuild2/algorithm.ixx | 9 +- libbuild2/context.hxx | 3 +- libbuild2/operation.cxx | 194 ++++++++++++++++++++++++++++++----- libbuild2/target.hxx | 33 +++--- 7 files changed, 249 insertions(+), 70 deletions(-) diff --git a/libbuild2/adhoc-rule-buildscript.cxx b/libbuild2/adhoc-rule-buildscript.cxx index 5f8a6b9..fa5100c 100644 --- a/libbuild2/adhoc-rule-buildscript.cxx +++ b/libbuild2/adhoc-rule-buildscript.cxx @@ -1904,6 +1904,8 @@ namespace build2 // // See also environment::set_special_variables(). // + // See also perform_execute() which has to deal with these shenanigans. + // optional adhoc_buildscript_rule:: execute_update_prerequisites (action a, const target& t, timestamp mt) const { diff --git a/libbuild2/algorithm.cxx b/libbuild2/algorithm.cxx index 670355c..a2e1b57 100644 --- a/libbuild2/algorithm.cxx +++ b/libbuild2/algorithm.cxx @@ -1270,6 +1270,8 @@ namespace build2 static group_view resolve_members_impl (action a, const target& g, target_lock&& l) { + assert (a.inner ()); + // Note that we will be unlocked if the target is already applied. // group_view r; @@ -1296,27 +1298,6 @@ namespace build2 // Fall through. case target::offset_matched: { - // @@ Doing match without execute messes up our target_count. Does - // not seem like it will be easy to fix (we don't know whether - // someone else will execute this target). - // - // What if we always do match & execute together? After all, - // if a group can be resolved in apply(), then it can be - // resolved in match()! Feels a bit drastic. - // - // But, this won't be a problem if the target returns noop_recipe. - // And perhaps it's correct to fail if it's not noop_recipe but - // nobody executed it? Maybe not. - // - // Another option would be to have a count for such "matched but - // may not be executed" targets and then make sure target_count - // is less than that at the end. Though this definitelt makes it - // less exact (since we can end up executed this target but not - // some other). Maybe we can increment and decrement such targets - // in a separate count (i.e., mark their recipe as special or some - // such). - // - // Apply (locked). // pair s (match_impl (l, true /* step */)); @@ -1333,7 +1314,40 @@ namespace build2 if ((r = g.group_members (a)).members != nullptr) { - g.ctx.resolve_count.fetch_add (1, memory_order_relaxed); + // Doing match without execute messes up our target_count. There + // doesn't seem to be a clean way to solve this. Well, just always + // executing if we've done the match would have been clean but quite + // heavy-handed (it would be especially surprising if otherwise + // there is nothing else to do, which can happen, for example, + // during update-for-test when there are no tests to run). + // + // So our solution is as follows: + // + // 1. Keep track both of the targets that ended up in this situation + // (the target::resolve_counted flag) as well as their total + // count (the context::resolve_count member). Only do this if + // set_recipe() (called by match_impl()) would have incremented + // target_count. + // + // 2. If we happen to execute such a target (common case), then + // clear the flag and decrement the count. + // + // 3. When it's time to assert that target_count==0 (i.e., all the + // matched targets have been executed), check if resolve_count is + // 0. If it's not, then find every target with the flag set, + // pretend-execute it, and decrement both counts. See + // perform_execute() for further details on this step. + // + if (s.second != target_state::unchanged) + { + target::opstate& s (l.target->state[a]); // Inner. + + if (!s.recipe_group_action) + { + s.resolve_counted = true; + g.ctx.resolve_count.fetch_add (1, memory_order_relaxed); + } + } break; } @@ -1409,6 +1423,8 @@ namespace build2 void resolve_group_impl (action a, const target& t, target_lock&& l) { + assert (a.inner ()); + pair r ( match_impl (l, true /* step */, true /* try_match */)); @@ -2496,7 +2512,17 @@ namespace build2 // postponment logic (see excute_recipe() for details). // if (a.inner () && !s.recipe_group_action) + { + // See resolve_members_impl() for background. + // + if (s.resolve_counted) + { + s.resolve_counted = false; + ctx.resolve_count.fetch_sub (1, memory_order_relaxed); + } + ctx.target_count.fetch_sub (1, memory_order_relaxed); + } // Decrement the task count (to count_executed) and wake up any threads // that might be waiting for this target. @@ -2516,6 +2542,8 @@ namespace build2 size_t start_count, atomic_count* task_count) { + // NOTE: see also pretend_execute lambda in perform_execute(). + target& t (const_cast (ct)); // MT-aware. target::opstate& s (t[a]); diff --git a/libbuild2/algorithm.hxx b/libbuild2/algorithm.hxx index aa0ec44..93a609f 100644 --- a/libbuild2/algorithm.hxx +++ b/libbuild2/algorithm.hxx @@ -508,9 +508,9 @@ namespace build2 // ((prerequisite_target::include & mask) == value) condition. // LIBBUILD2_SYMEXPORT void - match_members (action a, - const target& t, - prerequisite_targets& ts, + match_members (action, + const target&, + prerequisite_targets&, size_t start = 0, pair include = {0, 0}); diff --git a/libbuild2/algorithm.ixx b/libbuild2/algorithm.ixx index d2cd018..6fcc1e9 100644 --- a/libbuild2/algorithm.ixx +++ b/libbuild2/algorithm.ixx @@ -535,9 +535,12 @@ namespace build2 inline void clear_target (action a, target& t) { - t[a].vars.clear (); + target::opstate& s (t.state[a]); + s.recipe = nullptr; + s.recipe_keep = false; + s.resolve_counted = false; + s.vars.clear (); t.prerequisite_targets[a].clear (); - t.clear_data (a); } LIBBUILD2_SYMEXPORT void @@ -842,7 +845,7 @@ namespace build2 } inline target_state - execute_inner (action a, const target& t) + execute_inner (action a, const target& t) // @@ TMP Why inline (used as recipe)? { assert (a.outer ()); return execute_sync (a.inner_action (), t); diff --git a/libbuild2/context.hxx b/libbuild2/context.hxx index a54d010..8898c92 100644 --- a/libbuild2/context.hxx +++ b/libbuild2/context.hxx @@ -406,7 +406,8 @@ namespace build2 // skipped executing the operation, then it should increment the skip // count. These two counters are used for progress monitoring and // diagnostics. The resolve count keeps track of the number of targets - // matched but not executed as a result of the resolve_members() calls. + // matched but not executed as a result of the resolve_members() calls + // (see also target::resolve_counted). // atomic_count dependency_count; atomic_count target_count; diff --git a/libbuild2/operation.cxx b/libbuild2/operation.cxx index 7355f38..1c3493c 100644 --- a/libbuild2/operation.cxx +++ b/libbuild2/operation.cxx @@ -18,6 +18,10 @@ #include #include +#if 0 +#include // @@ For a hack below. +#endif + using namespace std; using namespace butl; @@ -762,53 +766,189 @@ namespace build2 throw failed (); #ifndef NDEBUG + size_t base (ctx.count_base ()); + // For now we disable these checks if we've performed any group member // resolutions that required a match (with apply()) but not execute. // - if (ctx.resolve_count.load (memory_order_relaxed) == 0) + if (ctx.target_count.load (memory_order_relaxed) != 0 && + ctx.resolve_count.load (memory_order_relaxed) != 0) { - // We should have executed every target that we matched, provided we - // haven't failed (in which case we could have bailed out early). + // These counts are only tracked for the inner operation. // - assert (ctx.target_count.load (memory_order_relaxed) == 0); - - if (ctx.dependency_count.load (memory_order_relaxed) != 0) + action ia (a.outer () ? a.inner_action () : a); + + // While it may seem that just decrementing the counters for every + // target with the resolve_counted flag set should be enough, this will + // miss any prerequisites that this target has matched but did not + // execute, which may affect both task_count and dependency_count. Note + // that this applies recursively and we effectively need to pretend to + // execute this target and all its prerequisites, recursively without + // actually executing any of their recepies. + // + // That last bit means we must be able to interpret the populated + // prerequisite_targets generically, which is a requirement we place on + // rules that resolve groups in apply (see target::group_members() for + // details). It so happens that our own adhoc_buildscript_rule doesn't + // follow this rule (see execute_update_prerequisites()) so we detect + // and handle this with a hack. + // + // @@ Hm, but there is no guarantee that this holds recursively since + // prerequisites may not be see-through groups. For this to work we + // would have to impose this restriction globally. Which we could + // probably do, just need to audit things carefully (especially + // cc::link_rule). But we already sort of rely on that for dump! Maybe + // should just require it everywhere and fix adhoc_buildscript_rule. + // + // @@ There are special recipes that don't populate prerequisite_targets + // like group_recipe! Are we banning any user-defined such recipes? + // Need to actually look if we have anything else like this. There + // is also execute_inner, though doesn't apply here (only for outer). + // + // @@ TMP: do and enable after the 0.16.0 release. + // + // Note: recursive lambda. + // +#if 0 + auto pretend_execute = [base, ia] (target& t, + const auto& pretend_execute) -> void { - auto dependents = [base = ctx.count_base ()] (action a, - const target& t) + context& ctx (t.ctx); + + // Note: tries to emulate the execute_impl() functions semantics. + // + auto execute_impl = [base, ia, &ctx, &pretend_execute] (target& t) { - const target::opstate& s (t.state[a]); + target::opstate& s (t.state[ia]); - // Only consider targets that have been matched for this operation - // (since matching is what causes the dependents count reset). - // - size_t c (s.task_count.load (memory_order_relaxed) - base); + 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); - return (c >= target::offset_applied - ? s.dependents.load (memory_order_relaxed) - : 0); + // Execute unless already executed. + // + if (s.task_count.load (memory_order_relaxed) - base != + target::offset_executed) + pretend_execute (t, pretend_execute); }; - diag_record dr; - dr << info << "detected unexecuted matched targets:"; + target::opstate& s (t.state[ia]); - for (const auto& pt: ctx.targets) + if (s.state != target_state::unchanged) // Noop recipe. { - const target& t (*pt); + if (s.recipe_group_action) + { + execute_impl (const_cast (*t.group)); + } + else + { + // @@ Special hack for adhoc_buildscript_rule (remember to drop + // include above if getting rid of). + // + bool adhoc ( + ia == perform_update_id && + s.rule != nullptr && + dynamic_cast ( + &s.rule->second.get ()) != nullptr); - if (size_t n = dependents (a, t)) - dr << text << t << ' ' << n; + for (const prerequisite_target& p: t.prerequisite_targets[ia]) + { + const target* pt; - if (a.outer ()) - { - if (size_t n = dependents (a.inner_action (), t)) - dr << text << t << ' ' << n; + if (adhoc) + pt = (p.target != nullptr ? p.target : + p.adhoc () ? reinterpret_cast (p.data) : + nullptr); + else + pt = p.target; + + if (pt != nullptr) + execute_impl (const_cast (*pt)); + } + + ctx.target_count.fetch_sub (1, memory_order_relaxed); + if (s.resolve_counted) + { + s.resolve_counted = false; + ctx.resolve_count.fetch_sub (1, memory_order_relaxed); + } } + + s.state = target_state::changed; + } + + s.task_count.store (base + target::offset_executed, + memory_order_relaxed); + }; +#endif + + for (const auto& pt: ctx.targets) + { + target& t (*pt); + target::opstate& s (t.state[ia]); + + // We are only interested in the targets that have been matched for + // this operation and are in the applied state. + // + if (s.task_count.load (memory_order_relaxed) - base != + target::offset_applied) + continue; + + if (s.resolve_counted) + { +#if 0 + pretend_execute (t, pretend_execute); + + if (ctx.resolve_count.load (memory_order_relaxed) == 0) + break; +#else + return; // Skip all the below checks. +#endif } } + } + + // We should have executed every target that we have matched, provided we + // haven't failed (in which case we could have bailed out early). + // + assert (ctx.target_count.load (memory_order_relaxed) == 0); + assert (ctx.resolve_count.load (memory_order_relaxed) == 0); // Sanity check. - assert (ctx.dependency_count.load (memory_order_relaxed) == 0); + if (ctx.dependency_count.load (memory_order_relaxed) != 0) + { + auto dependents = [base] (action a, const target& t) + { + const target::opstate& s (t.state[a]); + + // Only consider targets that have been matched for this operation + // (since matching is what causes the dependents count reset). + // + size_t c (s.task_count.load (memory_order_relaxed) - base); + + return (c >= target::offset_applied + ? s.dependents.load (memory_order_relaxed) + : 0); + }; + + diag_record dr; + dr << info << "detected unexecuted matched targets:"; + + for (const auto& pt: ctx.targets) + { + const target& t (*pt); + + if (size_t n = dependents (a, t)) + dr << text << t << ' ' << n; + + if (a.outer ()) + { + if (size_t n = dependents (a.inner_action (), t)) + dr << text << t << ' ' << n; + } + } } + + assert (ctx.dependency_count.load (memory_order_relaxed) == 0); #endif } diff --git a/libbuild2/target.hxx b/libbuild2/target.hxx index c7b1131..c33893f 100644 --- a/libbuild2/target.hxx +++ b/libbuild2/target.hxx @@ -479,7 +479,8 @@ namespace build2 public: // Normally you should not call this function directly and rather use - // resolve_members() from . + // resolve_members() from . Note that action + // is always inner. // virtual group_view group_members (action) const; @@ -779,6 +780,12 @@ namespace build2 // target_state state; + // Set to true (only for the inner action) if this target has been + // matched but not executed as a result of the resolve_members() call. + // See also context::resolve_count. + // + bool resolve_counted; + // Rule-specific variables. // // The rule (for this action) has to be matched before these variables @@ -922,12 +929,18 @@ namespace build2 // NULL means the target should be skipped (or the rule may simply not add // such a target to the list). // - // Note also that it is possible the target can vary from action to - // action, just like recipes. We don't need to keep track of the action - // here since the targets will be updated if the recipe is updated, - // normally as part of rule::apply(). + // A rule should make sure that the target's prerequisite_targets are in + // the "canonical" form (that is, all the prerequisites that need to be + // executed are present with prerequisite_target::target pointing to the + // corresponding target). This is relied upon in a number of places, + // including in dump and to be able to pretend-execute the operation on + // this target without actually calling the recipe (see perform_execute(), + // resolve_members_impl() for background). Note that a rule should not + // store targets that are semantically prerequisites in an ad hoc manner + // (e.g., in match data) with a few well-known execeptions (see + // group_action and execute_inner). // - // Note that the recipe may modify this list. + // Note that the recipe may modify this list. @@ TMP TSAN issue // mutable action_state prerequisite_targets; @@ -1082,14 +1095,6 @@ namespace build2 return *state[a].recipe.target (); } - void - clear_data (action a) const - { - const opstate& s (state[a]); - s.recipe = nullptr; - s.recipe_keep = false; - } - // Target type info and casting. // public: -- cgit v1.1