diff options
| -rw-r--r-- | build2/algorithm | 3 | ||||
| -rw-r--r-- | build2/algorithm.cxx | 158 | ||||
| -rw-r--r-- | build2/algorithm.ixx | 72 | ||||
| -rw-r--r-- | build2/context | 2 | ||||
| -rw-r--r-- | build2/context.cxx | 2 | ||||
| -rw-r--r-- | build2/operation.cxx | 2 | ||||
| -rw-r--r-- | build2/target | 64 | ||||
| -rw-r--r-- | build2/target.cxx | 22 | ||||
| -rw-r--r-- | build2/types | 3 |
9 files changed, 192 insertions, 136 deletions
diff --git a/build2/algorithm b/build2/algorithm index cb84231..09e0c4d 100644 --- a/build2/algorithm +++ b/build2/algorithm @@ -167,7 +167,8 @@ namespace build2 // 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). + // target state). It will also wait for the completion if the target + // is busy. // target_state execute_direct (action, target&); diff --git a/build2/algorithm.cxx b/build2/algorithm.cxx index 734c545..f173af6 100644 --- a/build2/algorithm.cxx +++ b/build2/algorithm.cxx @@ -10,6 +10,7 @@ #include <build2/file> // import() #include <build2/search> #include <build2/context> +#include <build2/scheduler> #include <build2/filesystem> #include <build2/diagnostics> #include <build2/prerequisite> @@ -386,46 +387,131 @@ namespace build2 return r; } - target_state + inline target_state execute_impl (action a, target& t) { - // Implementation with some multi-threading ideas in mind. + // Task count should be count_executing. // - switch (t.raw_state) + assert (t.state_ == target_state::unknown); + + auto g ( + make_exception_guard ( + [a, &t]() + { + t.state_ = target_state::failed; + + if (verb != 0) + info << "while " << diag_doing (a, t); + })); + + target_state ts (t.recipe (a) (a, t)); + assert (ts != target_state::unknown && ts != target_state::failed); + + t.state_ = ts; + if (ts == target_state::group) + ts = t.group->state_; + + // Decrement the task count (to count_executed) and wake up any threads + // that might be waiting for this target. + // + size_t tc (t.task_count--); + assert (tc == target::count_executing); + sched.resume (t.task_count); + + return ts; + } + + target_state + execute (action a, target& t) + { + // text << "E " << t << ": " << t.dependents << " " << dependency_count; + + size_t d (0); + if (dependency_count != 0) // Re-examination of a postponed target? { - case target_state::group: // Means group's state is unknown. - case target_state::unknown: - case target_state::postponed: - { - auto g ( - make_exception_guard ( - [a, &t]() - { - t.raw_state = target_state::failed; + // 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--); + d = t.dependents--; + assert (g != 0 && d != 0); + d--; + } - if (verb != 0) - info << "while " << diag_doing (a, t); - })); + // Handle the "last" execution mode. + // + // This gets interesting when we consider interaction with + // groups. It seem to make sense to treat group members as + // dependents of the group, so, for example, if we try to + // clean the group via three of its members, only the last + // attempt will actually execute the clean. This means that + // when we match a group member, inside we should also match + // the group in order to increment the dependents count. This + // seems to be a natural requirement: if we are delegating to + // the group, we need to find a recipe for it, just like we + // would for a prerequisite. + // + // Note that below we are going to change the group state + // to postponed. This is not a mistake: until we execute + // the recipe, we want to keep returning postponed. And + // once the recipe is executed, it will reset the state + // to group (see group_action()). To put it another way, + // the execution of this member is postponed, not of the + // group. + // + // One important invariant to keep in mind: the return + // value from execute() should always be the same as what + // would get returned by a subsequent call to state(). + // + size_t tc (target::count_unexecuted); + if (current_mode == execution_mode::last && d != 0) + { + // Try to atomically change unexecuted to postponed. + // + if (t.task_count.compare_exchange_strong (tc, target::count_postponed)) + tc = target::count_postponed; + } + else + { + // Try to atomically change unexecuted to executing. But it can also be + // postponed to executing. + // + 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); + } - target_state ts (t.recipe (a) (a, t)); - assert (ts != target_state::unknown && ts != target_state::failed); + switch (tc) + { + case target::count_unexecuted: assert (false); + case target::count_postponed: return target_state::postponed; + case target::count_executed: return t.state (); + default: return target_state::busy; + } + } - // Set the target's state unless it should be the group's state. - // - if (t.raw_state != target_state::group) - t.raw_state = ts; + target_state + execute_direct (action a, target& t) + { + size_t tc (target::count_unexecuted); + if (t.task_count.compare_exchange_strong (tc, target::count_executing)) + return execute_impl (a, t); - return ts; - } - case target_state::unchanged: - case target_state::changed: - // Should have been handled by inline execute(). - assert (false); - case target_state::failed: - break; + // If the target is busy, wait for it. + // + switch (tc) + { + case target::count_unexecuted: + case target::count_postponed: assert (false); + case target::count_executed: break; + default: sched.wait (target::count_executed, + t.task_count); } - throw failed (); + return t.state (); } target_state @@ -522,14 +608,14 @@ namespace build2 target_state group_action (action a, target& t) { - target_state r (execute (a, *t.group)); - - // Indicate to the standard execute() logic that this target's - // state comes from the group. + // If the group is busy, we wait, similar to prerequisites. // - t.raw_state = target_state::group; + if (execute (a, *t.group) == target_state::busy) + sched.wait (target::count_executed, t.group->task_count); - return r; + // Indicate to execute() that this target's state comes from the group. + // + return target_state::group; } target_state diff --git a/build2/algorithm.ixx b/build2/algorithm.ixx index f8e3191..cf234d8 100644 --- a/build2/algorithm.ixx +++ b/build2/algorithm.ixx @@ -3,7 +3,6 @@ // license : MIT; see accompanying LICENSE file #include <build2/rule> -#include <build2/prerequisite> #include <build2/context> namespace build2 @@ -173,83 +172,12 @@ namespace build2 search_and_match_prerequisite_members (ml, a, t, &s); } - target_state - execute_impl (action, target&); - - inline target_state - execute (action a, target& t) - { - // text << "E " << t << ": " << t.dependents << " " << dependency_count; - - if (dependency_count != 0) // Re-examination of a postponed target? - { - assert (t.dependents != 0); - --t.dependents; - --dependency_count; - } - - // Don't short-circuit to the group state since we need to execute the - // member's recipe to keep the dependency counts straight. - // - switch (target_state ts = t.state (false)) - { - case target_state::unchanged: - case target_state::changed: - return ts; - default: - { - // Handle the "last" execution mode. - // - // This gets interesting when we consider interaction with - // groups. It seem to make sense to treat group members as - // dependents of the group, so, for example, if we try to - // clean the group via three of its members, only the last - // attempt will actually execute the clean. This means that - // when we match a group member, inside we should also match - // the group in order to increment the dependents count. This - // seems to be a natural requirement: if we are delegating to - // the group, we need to find a recipe for it, just like we - // would for a prerequisite. - // - // Note that below we are going to change the group state - // to postponed. This is not a mistake: until we execute - // the recipe, we want to keep returning postponed. And - // once the recipe is executed, it will reset the state - // to group (see group_action()). To put it another way, - // the execution of this member is postponed, not of the - // group. - // - // One important invariant to keep in mind: the return - // value from execute() should always be the same as what - // would get returned by a subsequent call to state(). - // - if (current_mode == execution_mode::last && t.dependents != 0) - return (t.raw_state = target_state::postponed); - - return execute_impl (a, t); - } - } - } - inline target_state execute_delegate (const recipe& r, action a, target& t) { return r (a, t); } - inline target_state - execute_direct (action a, target& t) - { - // Here we don't care about the counts so short-circuit state is ok. - // - switch (target_state ts = t.state ()) - { - case target_state::unchanged: - case target_state::changed: return ts; - default: return execute_impl (a, t); - } - } - // If the first argument is NULL, then the result is treated as a boolean // value. // diff --git a/build2/context b/build2/context index d6f79af..da2ced5 100644 --- a/build2/context +++ b/build2/context @@ -243,7 +243,7 @@ namespace build2 // execution with the expectation of it reaching 0. Used as a sanity // check. // - extern uint64_t dependency_count; + extern atomic_count dependency_count; // Variable override value cache. // diff --git a/build2/context.cxx b/build2/context.cxx index e15294a..400f68c 100644 --- a/build2/context.cxx +++ b/build2/context.cxx @@ -56,7 +56,7 @@ namespace build2 execution_mode current_mode; - uint64_t dependency_count; + atomic_count dependency_count; variable_override_cache var_override_cache; diff --git a/build2/operation.cxx b/build2/operation.cxx index 5815834..19f1ff7 100644 --- a/build2/operation.cxx +++ b/build2/operation.cxx @@ -173,6 +173,8 @@ namespace build2 // Re-examine postponed targets. This is the only reliable way to // find out whether the target has changed. // + // Note: must be serial. + // for (target& t: psp) { switch (execute (a, t)) diff --git a/build2/target b/build2/target index 1a300f7..fb8fd08 100644 --- a/build2/target +++ b/build2/target @@ -33,13 +33,17 @@ namespace build2 // enum class target_state: uint8_t { - // The order of the enumerators is arranged so that their integral - // values indicate whether one "overrides" the other in the merge - // operator (see below). + // The order of the enumerators is arranged so that their integral values + // indicate whether one "overrides" the other in the "merge" operator| + // (see below). + // + // Note that postponed is "greater" than unchanged since it may result in + // the changed state. // unknown, unchanged, postponed, + busy, changed, failed, group // Target's state is the group's state. @@ -63,10 +67,8 @@ namespace build2 // though you shouldn't be returning postponed directly. If there is an // error, then the recipe should throw rather than returning failed. // - // The return value of the recipe is used to update the target state except - // if the state is set to target_state::group by the recipe. Note that in - // this case the returned by the recipe value is still used as the resulting - // target state so it should match the group's state. + // The return value of the recipe is used to update the target state. If it + // is target_state::group then the target's state is the group's state. // // Note that max size for the "small capture optimization" in std::function // ranges (in pointer sizes) from 0 (GCC prior to 5) to 2 (GCC 5) to 6 (VC @@ -394,30 +396,50 @@ namespace build2 // Target state. // + protected: + friend target_state execute_impl (action, target&); + + target_state state_; + public: - target_state raw_state = target_state::unknown; - // By default 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. - // This is normally what you want or need, as in inject_prerequisites() - // in the cc module. But sometimes not, as in execute(). + // Atomic task count that is used during execution to (atomically) track a + // 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 + // executing. Postponed can transition to executing. And executing + // transitions (via a decrement) to executed. Once it is executed, then + // state_ becomes immutable. + // + 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; + + // @@ MT TODO: when can be called. // target_state - state (bool shortcircuit = true) const + state () const { - if (raw_state == target_state::group) - return group->raw_state; + // 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 || !shortcircuit) - return raw_state; + if (group == nullptr) + return state_; if (recipe_function* const* f = recipe_.target<recipe_function*> ()) { if (*f == &group_action) - return group->raw_state; + return group->state_; } - return raw_state; + return state_; } // Number of direct targets that depend on this target in the current @@ -433,7 +455,7 @@ namespace build2 // should have been decremented to 0 naturally, as part of the previous // action execution. // - size_t dependents; + atomic_count dependents; // Auxilary data storage. // @@ -1106,7 +1128,7 @@ namespace build2 timestamp mtime (bool load = true) const { - const mtime_target* t (raw_state == target_state::group + const mtime_target* t (state_ == target_state::group ? static_cast<const mtime_target*> (group) : this); diff --git a/build2/target.cxx b/build2/target.cxx index b250597..f7387c7 100644 --- a/build2/target.cxx +++ b/build2/target.cxx @@ -31,8 +31,16 @@ namespace build2 // target_state // - static const char* const target_state_[] = { - "unknown", "unchanged", "postponed", "changed", "failed", "group"}; + static const char* const target_state_[] = + { + "unknown", + "unchanged", + "postponed", + "busy", + "changed", + "failed", + "group" + }; ostream& operator<< (ostream& os, target_state ts) @@ -99,7 +107,7 @@ namespace build2 action = a; recipe_ = move (r); - raw_state = target_state::unknown; + state_ = target_state::unknown; // If this is a noop recipe, then mark the target unchanged so that we // don't waste time executing the recipe. @@ -107,9 +115,15 @@ namespace build2 if (recipe_function** f = recipe_.target<recipe_function*> ()) { if (*f == &noop_action) - raw_state = target_state::unchanged; + state_ = target_state::unchanged; } + //@@ MT can this be a relaxed save? + // + task_count = state_ == target_state::unknown + ? count_unexecuted + : count_executed; + // This one is tricky: we don't want to reset the dependents count // if we are merely overriding with a "stronger" recipe. // diff --git a/build2/types b/build2/types index b9f3ce9..7afc24e 100644 --- a/build2/types +++ b/build2/types @@ -19,6 +19,7 @@ #include <initializer_list> #include <mutex> +#include <atomic> #include <future> #include <butl/ft/shared_mutex> @@ -78,6 +79,8 @@ namespace build2 // Concurrency. // + using atomic_count = std::atomic<size_t>; // Matches scheduler::atomic_count. + using std::future; #if defined(__cpp_lib_shared_mutex) |