aboutsummaryrefslogtreecommitdiff
path: root/build2/algorithm.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'build2/algorithm.cxx')
-rw-r--r--build2/algorithm.cxx158
1 files changed, 122 insertions, 36 deletions
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