aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorBoris Kolpackov <boris@codesynthesis.com>2017-02-06 10:44:49 +0200
committerBoris Kolpackov <boris@codesynthesis.com>2017-02-13 12:42:42 +0200
commit03c02a746ceef003366d3fb928499c327e8da69a (patch)
treef2aad3a30b75835dcc26e6952724491d724b02c8
parent74d54ca37f8e16abb93b35617b6121ae19cc8028 (diff)
Introduce target::task_count
-rw-r--r--build2/algorithm3
-rw-r--r--build2/algorithm.cxx158
-rw-r--r--build2/algorithm.ixx72
-rw-r--r--build2/context2
-rw-r--r--build2/context.cxx2
-rw-r--r--build2/operation.cxx2
-rw-r--r--build2/target64
-rw-r--r--build2/target.cxx22
-rw-r--r--build2/types3
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)