Maxwell Pirtle [Tue, 9 May 2023 11:57:07 +0000 (13:57 +0200)]
Fix MANIFEST.in
We should note that the Execution that's a part of
both ODPOR and SDPOR is now contained in DFSExplorer
even in stateless execution. This will likely eventually
be true also for ODPOR; hence, the ODPOR sources
have been added to the SRC_MC_STATELESS portion as
needed
Maxwell Pirtle [Tue, 9 May 2023 08:36:13 +0000 (10:36 +0200)]
Integrate SDPOR into `model-check/reduction` flag
SDPOR and ODPOR can be used as part of the
DFSExplorer (ODPOR should integrate with some
minor details in the DFS implementation, but that's
for a later PR). This commit replaces the simple
`with_dpor` boolean flag used to control the
reduction with the more precise `ReductionMode`
that is newly extracted from within `DFSExplorer`
and is instead made "public"
Maxwell Pirtle [Fri, 5 May 2023 12:21:17 +0000 (14:21 +0200)]
Fix ObjectAccess dependency check
The ObjectAccess transition should defer
dependency computation to the ActorJoin action.
Previously, it only decided dependency by
simply checking if the `other` transition
were simply another object access on the
same object
Maxwell Pirtle [Fri, 5 May 2023 09:16:07 +0000 (11:16 +0200)]
Fix subtlety with SDPOR/ODPOR initials
Computing initials for SDPOR/ODPOR requires
extending a search with respect to
a prefix of an execution. Previously, events
added to the extension were referred to by
their location within the larger execution
from which the prefix was taken. The problem
is that the new events need to be referred
to by their position relative to the
*extension* of the prefix; otherwise,
asking about "happens-before" in the extension
while using their handles in the full execution
will give incorrect results
Maxwell Pirtle [Fri, 5 May 2023 08:29:02 +0000 (10:29 +0200)]
Fix two off-by-one errors with clock vectors
Two errors were identified with managing clock
vectors in the Execution class. The index
assigned to the new transition was previously
`size() + 1` when it should have read `size()`.
Furthermore, the loop for checking "happens-between"
events excluded event 0. Both issues are now resolved
and a test with a race at the beginning was added
as verification
Maxwell Pirtle [Fri, 5 May 2023 06:53:47 +0000 (08:53 +0200)]
Mark `ActorJoin` dependent with `target_`
The `ActorJoin` transition was previously
labeled as independent with all other
transitions, including those of the actor
upon which the join acted. However, this
assumption was faulty: the join action is
instead dependent with ANY transition executed
by the actor joined upon, as the action
BECOMES enabled only as soon as the last action
run by the actor is executed.
Maxwell Pirtle [Fri, 5 May 2023 06:46:09 +0000 (08:46 +0200)]
Prevent adding outgoing transition for top-most state
The outgoing transition for the top-most
state of the state stack in the DFSExplorer refers
to that which was taken as part of the last
trace explored by the algorithm. Thus, only the
sequence of transitions leading up to, but
not including, the last state must be included
when reconstructing the Exploration for SDPOR.
Maxwell Pirtle [Thu, 4 May 2023 12:29:44 +0000 (14:29 +0200)]
Add workaround for subtlety with state regeneration
Regeneration of the Execution inside DFSExplorer
should be as simple as choosing the prefix relative
to the appropriate backtracking point. However,
it did not appear to function so simple. After
a good amount of debugging, it appears that
the stack contents can change unexpectedly so
(e.g. a transition "in the middle" of the stack
seemingly switches arbitrarily). Until we can
pinpoint the true cause here, we simple resort
to rebuilding the execution based off the new
stack each time we decide to backtrack. The
downside is that all clock vectors have to be
recomputed after each backtrack. For now,
this is something that's OK to live with,
especially considering that this certainly
won't be a bottle neck in performance
Maxwell Pirtle [Thu, 4 May 2023 07:33:25 +0000 (09:33 +0200)]
Add first tests for "happens-before"
The happens-before relation is used
extensively by SDPOR and ODPOR during
their computations for determining what
executions should be searched next. This
commit introduces the first round of tests
for the happens-before relation on
artificially constructed executions
Maxwell Pirtle [Wed, 3 May 2023 09:35:01 +0000 (11:35 +0200)]
Move SDPOR core computation into a method
The core component of SDPOR involves selecting
an "initial" for a hypothetical computation
extending from a prefix of the current execution
that results in the reversal of the reversible
race SDPOR detected. This comomit moves that
computation as much as possible into the
`Execution` class itself to make the SDPOR
implementation easier to read
Maxwell Pirtle [Wed, 3 May 2023 07:34:12 +0000 (09:34 +0200)]
Add tentatively-working SDPOR implementation
This commit introduces SDPOR into SimGrid
(well, mostly). The current implementation
will be improved upon by cleaning up some
of the code that was added to improve
its testability
Maxwell Pirtle [Tue, 2 May 2023 10:38:43 +0000 (12:38 +0200)]
Add initial outline of SDPOR implementation
The SDPOR algorithm is nearing an implementation
into SimGrid (sans a few technical details and
code clean ups that will be nice to add). The
algorithm largely builds off the existing
infrastructure of DFSExplorer fortunately.
Add `Execution` to represent series of transitions
The Execution class represents a series of transitions
taken by a process. An execution importantly also encodes
the happens-before relation among the series of steps
represented. The eventual implementation will leverage
clock vectors to compute the relation between events.
A more refined happens-before relation is left for
as a future (complicated) exercise...
Add class for eventual "happens-before" computations
Computing the "happens-before" relation over
a sequence of executions is an important step
in determining whether or not DPOR (and SDPOR
alike) needs to add a backtracking point.
This commit introduces the "ClockVector"
class which acts effectively as a light
wrapping around an `unordered_map` mapping
actor ids to integer values.
The essential component of the ClockVector
class is that its contents are "implicit"
in the sense that actors for which no
value is explicitly contained in the map
are assigned to the value `0` by default.
This allows clock vectors to be flexible
enough to support the creation of new
actors and the enabling/disabling of old
actors as they come and go.
Arnaud Giersch [Thu, 4 May 2023 13:13:45 +0000 (15:13 +0200)]
Misc Sonar issues.
* declare functions "const"
* use pointer-to-const or reference-to-const
* use structured bindings
* extract assignment from expression
* mark constructors "explicit"
* pass large object parameters by reference-to-const
* use default implementation constructor
* explicitly capture required variables in lambdas
Martin Quinson [Thu, 27 Apr 2023 13:41:03 +0000 (15:41 +0200)]
Lazily compute the recipe of a state, on need only
This will be useful when leveraging intermediate states during
backtracks. In that case, we need to compute partial recipes, up to
the advanced restaure point.
Martin Quinson [Thu, 27 Apr 2023 11:48:19 +0000 (13:48 +0200)]
MC: give each state an incoming transition too
Using the parent's outgoing transition is not reliable anymore now
that we don't always explore the tree in order, but rather following
the exploration strategies.
Martin Quinson [Mon, 17 Apr 2023 08:01:01 +0000 (10:01 +0200)]
sonar fixes
- Undefined return value (that would happen on a platform without any host)
- Local variable shadowing
- Automatic memory management
- const, explicit, etc.