model-checker.git
11 years agomodel: document get_last{,_fence}_conflict()
Brian Norris [Wed, 20 Feb 2013 22:58:21 +0000 (14:58 -0800)]
model: document get_last{,_fence}_conflict()

11 years agomodel: schedule appropriate fence backtracking points
Brian Norris [Wed, 20 Feb 2013 02:28:41 +0000 (18:28 -0800)]
model: schedule appropriate fence backtracking points

This patch calculates the most recent backtracking point which may be a
fence. We require a separate function for computing this because a fence
"conflict" is much different than other conflicts; fences do not have a
memory location, but instead, they trigger release/acquire backtracking
in the presence of other stores/loads.

Left out of this patch:
(1) Sleep-set waking: even if we backtrack, we don't yet wake up our
    thread properly, yielding a "redundant" trace instead of a
    productive one
(2) memory_order_seq_cst: I have yet to determine how (if at all) we
    need to add additional backtracking in the presence of seq_cst
    fences
(3) documentation: need to describe get_last_fence_conflict() better

11 years agomodel: convert while-loops to for-loops
Brian Norris [Thu, 21 Feb 2013 00:27:45 +0000 (16:27 -0800)]
model: convert while-loops to for-loops

Make the loop-termination condition more clear.

11 years agomodel: add 'const'
Brian Norris [Wed, 20 Feb 2013 02:03:56 +0000 (18:03 -0800)]
model: add 'const'

11 years agoinclude: fixup header inclusion
Brian Norris [Wed, 20 Feb 2013 23:03:24 +0000 (15:03 -0800)]
include: fixup header inclusion

11 years agodon't include action.h from model.h
Brian Norris [Wed, 20 Feb 2013 07:37:12 +0000 (23:37 -0800)]
don't include action.h from model.h

11 years agomodel/action: move action_list_t to model.h
Brian Norris [Wed, 20 Feb 2013 07:30:31 +0000 (23:30 -0800)]
model/action: move action_list_t to model.h

action_list_t is only used by the ModelChecker class

11 years agopromise: move constructor out of header
Brian Norris [Wed, 20 Feb 2013 07:29:42 +0000 (23:29 -0800)]
promise: move constructor out of header

11 years agoscheduler: refactor round-robin loop
Brian Norris [Sat, 16 Feb 2013 02:22:49 +0000 (18:22 -0800)]
scheduler: refactor round-robin loop

This is the same computation, represented more clearly as a for loop
which, if it reaches the completion condition, means that it did not
find an enabled thread.

11 years agomodel: end-of-execution print
Brian Norris [Sat, 16 Feb 2013 02:09:03 +0000 (18:09 -0800)]
model: end-of-execution print

For readability of a "verbose" execution log (and even for the shorter,
non-verbose log), it helps to visually separate the final statistics
from any previously-printed statistics. For instance, in the following
verbose snippet from the end of an execution history, it's confusing why
there are two identical copies of the statistics:

... <other execution history> ...
Number of complete, bug-free executions: 4
Number of redundant executions: 0
Number of buggy executions: 0
Number of infeasible executions: 5
Total executions: 9
Total nodes created: 48

Execution 9:
---------------------------------------------------------------------
... <snipped trace info> ...
---------------------------------------------------------------------

Number of complete, bug-free executions: 4
Number of redundant executions: 0
Number of buggy executions: 0
Number of infeasible executions: 5
Total executions: 9
Total nodes created: 48

11 years agomodel: improve get_next_thread() comments
Brian Norris [Sat, 16 Feb 2013 02:08:09 +0000 (18:08 -0800)]
model: improve get_next_thread() comments

It's curious that get_next_thread() needs the current ModelAction as a
parameter. It helps to clarify that this argument is somwhat "optional."

11 years agoschedule: simplify Scheduler::select_next_thread()
Brian Norris [Fri, 15 Feb 2013 23:53:13 +0000 (15:53 -0800)]
schedule: simplify Scheduler::select_next_thread()

Now that the "select next thread" vs. "set_current_thread" is clear, we
don't actually need to set the value of 'current' in
select_next_thread().

11 years agomodel: pull scheduler's thread selection into get_next_thread()
Brian Norris [Fri, 15 Feb 2013 23:42:14 +0000 (15:42 -0800)]
model: pull scheduler's thread selection into get_next_thread()

The code makes more logical sense if ModelChecker::get_next_thread()
handles all of the thread selection decisions.

11 years agoschedule: split Scheduler::next_thread() into separate functions
Brian Norris [Fri, 15 Feb 2013 23:33:11 +0000 (15:33 -0800)]
schedule: split Scheduler::next_thread() into separate functions

next_thread() is basically overloaded to perform two different
functions, depending on the parameters. In one case, a caller might pass
a NULL thread, which meant that Scheduler is free to select its own next
thread. In another case, a caller will pass a non-NULL thread, which
meant that the caller is simply informing the Scheduler of the next
thread to execute (i.e., which one is "currently running").

These separate functionalities are now separate functions:

  Scheduler::select_next_thread()
  Scheduler::set_current_thread(Thread *)

11 years agomodel: factor out a 'switch_from_master()' function
Brian Norris [Fri, 15 Feb 2013 23:19:45 +0000 (15:19 -0800)]
model: factor out a 'switch_from_master()' function

This snippet of code is important and somewhat subtle. Although we only
use it once, let's make it a function to give it a higher-level
abstraction.

11 years agomodel: rework the release sequence fixups
Brian Norris [Fri, 15 Feb 2013 20:54:25 +0000 (12:54 -0800)]
model: rework the release sequence fixups

It makes more sense to pull the release sequence fixups out of the main
execution loop and only perform them after all other actions are
complete.

There's still some more cleanup to be done here, but it appears that
end-of-execution release sequence fixups are functional again.

11 years agomodel: simple refactoring
Brian Norris [Fri, 15 Feb 2013 20:17:06 +0000 (12:17 -0800)]
model: simple refactoring

This condition is useless. We can just return next_thrd directly.

11 years agomodel/threads: add documentation comments
Brian Norris [Fri, 15 Feb 2013 19:54:11 +0000 (11:54 -0800)]
model/threads: add documentation comments

Document {get,set}_pending(), has_asserted()/set_assert(), etc.

11 years agomodel: fix leaking "pending actions"
Brian Norris [Fri, 15 Feb 2013 19:02:05 +0000 (11:02 -0800)]
model: fix leaking "pending actions"

ModelActions that are "pending" for each thread are not automatically
freed when we rollback; we keep most of the active ModelActions on the
NodeStack, then we free them from there when we explore a new branch of
the state space.

This fix causes all the pending actions to be freed on any rollback.
This is safe for now, since we always roll back to the beginning of the
execution. If we roll back to an intermediate point, though, we need to
retain those pending actions which were also pending before the rollback
point. Hence the FIXME notice included in reset_to_initial_state().

11 years agomodel: add 'pending' assertion
Brian Norris [Wed, 13 Feb 2013 02:12:17 +0000 (18:12 -0800)]
model: add 'pending' assertion

We don't want to clobber a pending action.

11 years agomodel: stash all pending actions immediately
Brian Norris [Wed, 13 Feb 2013 01:56:13 +0000 (17:56 -0800)]
model: stash all pending actions immediately

11 years agomodel: pull 'has_asserted()' check out of take_step()
Brian Norris [Wed, 13 Feb 2013 01:24:31 +0000 (17:24 -0800)]
model: pull 'has_asserted()' check out of take_step()

Checks for mid-execution assertions should occur before take_step().
This can catch a mid-step bug (e.g., data race or user-assertion) that
happens between ModelAction steps.

11 years agothreads: bugfix - do not call thread_current() from model-checker
Brian Norris [Wed, 13 Feb 2013 00:54:38 +0000 (16:54 -0800)]
threads: bugfix - do not call thread_current() from model-checker

thread_current() was designed for use in the user context. It is not
guaranteed to provide a reliable result in the model-checker context,
since we may perform context switches as needed, such that the "last
executed user thread" may not be the thread that we are checking at the
time.

This change is made to clear up future changes that will modify the
scheduling patterns.

11 years agomodel: stash actions in each thread
Brian Norris [Wed, 13 Feb 2013 00:39:33 +0000 (16:39 -0800)]
model: stash actions in each thread

We don't want a global 'current_action' for saving the next action to
run; we want to stash the 'current action' for each thread. So just use
the 'pending' action in each Thread.

Note that this kinda breaks sleep sets for now. We'll have to redo this.

11 years agomodel: return next thread from take_step()
Brian Norris [Wed, 13 Feb 2013 00:33:40 +0000 (16:33 -0800)]
model: return next thread from take_step()

Note that this intentionally breaks release sequence fixups for now.

11 years agothreads/model: allocate Thread from w/in ModelChecker
Brian Norris [Wed, 19 Dec 2012 01:46:40 +0000 (17:46 -0800)]
threads/model: allocate Thread from w/in ModelChecker

It adds scheduling difficulties if we allocate/schedule a Thread from
the user-context (i.e., directly from the thrd_create() interface)
because then it is not necessarily atomic. For example, if we run a
thread up to its context switch for a THREAD_CREATE then switch to
another thread before the THREAD_CREATE is processed, then we will
already have constructed a Thread from the first thread (and prepared it
for scheduling) without processing it in the ModelChecker appropriately.
For instance, the following schedule might appear, causing problems:

 TID    ACTION
 ---    ------
    ...
  1     ATOMIC_READ         <--- Next action is THREAD_CREATE
 (1)    (construct Thread 3)
 (1)    (prepare new Thread for Scheduling)
  2     ATOMIC_READ
  3     THREAD_START        <--- Before its CREATE event??
  1     THREAD_CREATE

Note that this scheduling does not yet happen, as we always execute
the "lead-in" to THREAD_CREATE atomically. This may change, though.

11 years agoschedule: assert that model-checker thread doesn't enter scheduler
Brian Norris [Thu, 14 Feb 2013 20:23:48 +0000 (12:23 -0800)]
schedule: assert that model-checker thread doesn't enter scheduler

11 years agomodel: set thread state during 'swap' calls
Brian Norris [Tue, 12 Feb 2013 20:53:20 +0000 (12:53 -0800)]
model: set thread state during 'swap' calls

Rather than setting thread-state from subtle places within ModelChecker,
it makes more logical sense to set it from withing the Thread::swap
functions.

11 years agoMerge branch 'fences'
Brian Norris [Tue, 12 Feb 2013 19:48:41 +0000 (11:48 -0800)]
Merge branch 'fences'

11 years agopromise: use id_to_int()
Brian Norris [Tue, 12 Feb 2013 19:35:45 +0000 (11:35 -0800)]
promise: use id_to_int()

11 years agomodel: prune may-read-from set early
Brian Norris [Tue, 12 Feb 2013 18:42:17 +0000 (10:42 -0800)]
model: prune may-read-from set early

It helps to prune the may-read-from set (according to modification order
constraints) as we build it. This prevents unnecessary backtracking and
provides a significant (linear) speedup in model-checking speed.

Note that this now allows us to assume that at any point in an
execution, any selection from the may-read-from set is feasible.

11 years agoaction: bugfix - initialize member
Brian Norris [Tue, 12 Feb 2013 18:26:10 +0000 (10:26 -0800)]
action: bugfix - initialize member

11 years agomodel: rewrite mo_check_promises
Brian Norris [Sat, 9 Feb 2013 01:08:47 +0000 (17:08 -0800)]
model: rewrite mo_check_promises

Rather than use some special logic that was devised when we didn't
include promises in the mo-graph, we can simplify our mo_check_promises
code by querying the mo-graph for reachability. This *should* be at
least as good of a 'check' as the previous code, and much less cryptic.

11 years agomodel: remove argument from mo_check_promises
Brian Norris [Sat, 9 Feb 2013 01:08:33 +0000 (17:08 -0800)]
model: remove argument from mo_check_promises

11 years agocyclegraph: possible optimization
Brian Norris [Sat, 9 Feb 2013 00:34:33 +0000 (16:34 -0800)]
cyclegraph: possible optimization

11 years agomodel: rename according to the comments
Brian Norris [Fri, 8 Feb 2013 23:23:41 +0000 (15:23 -0800)]
model: rename according to the comments

The documentation mentions 'pread' and 'pwrite'. Those names aren't
actually used in the code, though, so change that.

11 years agomodel: add read-write coherence for promise nodes
Brian Norris [Thu, 7 Feb 2013 00:39:52 +0000 (16:39 -0800)]
model: add read-write coherence for promise nodes

Promises must be ordered after any other loads from the same thread.

11 years agopromise: update comments/names to reflect usage
Brian Norris [Thu, 7 Feb 2013 00:51:12 +0000 (16:51 -0800)]
promise: update comments/names to reflect usage

is_compatible() and is_compatible_exclusive() do not require a store as
an argument; they can just as well use a load

11 years agocyclegraph: expand template usage
Brian Norris [Thu, 7 Feb 2013 00:39:15 +0000 (16:39 -0800)]
cyclegraph: expand template usage

checkReachable() and addEdge() will be used in more forms. Add template
instantiations.

11 years agomodel: refactor to use a helper function
Brian Norris [Wed, 6 Feb 2013 23:46:23 +0000 (15:46 -0800)]
model: refactor to use a helper function

11 years agocyclegraph: don't delete promise nodes
Brian Norris [Wed, 6 Feb 2013 22:46:21 +0000 (14:46 -0800)]
cyclegraph: don't delete promise nodes

Merging can fail partway, leaving a somewhat inconsistent graph. This is
safe, since an inconsistent graph must be discarded as infeasible. But
this is a problem when dumping the modification order graph, since we
may dereference freed nodes. So for now, just don't free them.

11 years agocyclegraph: fixup support for dumping the modification order graph
Brian Norris [Wed, 6 Feb 2013 22:43:39 +0000 (14:43 -0800)]
cyclegraph: fixup support for dumping the modification order graph

We need to include promises in the modification order graph if we plan
on dumping it to a .dot file. This hacks it together so that it works
for now.

11 years agocyclegraph: mergeNodes(): return early if we violate RMW
Brian Norris [Wed, 6 Feb 2013 22:42:00 +0000 (14:42 -0800)]
cyclegraph: mergeNodes(): return early if we violate RMW

To be consistent, and to prevent unecessary merging work, we should
simply return from the mergeNodes() function as soon as we know it has
failed.

11 years agocyclegraph: refactor for indentation
Brian Norris [Wed, 6 Feb 2013 22:41:12 +0000 (14:41 -0800)]
cyclegraph: refactor for indentation

11 years agoMakefile / git: cleanup generated .dot and .pdf files
Brian Norris [Wed, 6 Feb 2013 22:00:05 +0000 (14:00 -0800)]
Makefile / git: cleanup generated .dot and .pdf files

11 years agocyclegraph: add wrappers for some common functionality
Brian Norris [Wed, 6 Feb 2013 02:27:35 +0000 (18:27 -0800)]
cyclegraph: add wrappers for some common functionality

11 years agomodel: fully utilize Promise nodes in CycleGraph
Brian Norris [Wed, 6 Feb 2013 01:45:31 +0000 (17:45 -0800)]
model: fully utilize Promise nodes in CycleGraph

We can eliminate the post-promise-resolution computations now that
mo_graph is built up to include Promise nodes.

11 years agomodel: cosmetic improvements to resolve_promises()
Brian Norris [Wed, 6 Feb 2013 01:39:36 +0000 (17:39 -0800)]
model: cosmetic improvements to resolve_promises()

Rename 'resolved' to 'haveResolved', since we will use the 'resolved'
name for something else.

11 years agocyclegraph: move function definitions out of header
Brian Norris [Wed, 6 Feb 2013 01:36:05 +0000 (17:36 -0800)]
cyclegraph: move function definitions out of header

I found out how to instantiate these functions from within the
implementation file (rather than the header). I can specifically list
those implementations that I want available.

11 years agocyclegraph: template-ize addRMWEdge()
Brian Norris [Wed, 6 Feb 2013 01:13:28 +0000 (17:13 -0800)]
cyclegraph: template-ize addRMWEdge()

11 years agocyclegraph: bugfix - pop edges properly
Brian Norris [Tue, 5 Feb 2013 22:26:24 +0000 (14:26 -0800)]
cyclegraph: bugfix - pop edges properly

Now that CycleNode's have back-edges, we need to properly remove *both*
the forward and back edges when doing roll-back.

11 years agomodel: add write-to-promise edges
Brian Norris [Tue, 5 Feb 2013 22:10:06 +0000 (14:10 -0800)]
model: add write-to-promise edges

Assume that any time a promise exists, is compatible with a store, and
is exclusive to the same thread as the store, that it is mod-ordered
after that store. This should never produce cycles, until we decide to
begin satisfying promises. At that point, if there's a cycle, then we
must either merge nodes (i.e., the store must satisfy that promise) or
else we discard the execution for the moment and perform the
satisfaction at a later point in the search space.

11 years agopromise: add is_compatible_exclusive()
Brian Norris [Tue, 5 Feb 2013 22:03:28 +0000 (14:03 -0800)]
promise: add is_compatible_exclusive()

Check if a Promise is both compatible *and* exclusive to a particular
thread. This allows ordering optimizations when we can guarantee that a
particular thread must fulfill the promise.

11 years agopromise: add const
Brian Norris [Tue, 5 Feb 2013 22:01:34 +0000 (14:01 -0800)]
promise: add const

11 years agomodel: utilize CycleGraph 'addEdge()' status
Brian Norris [Tue, 5 Feb 2013 21:47:20 +0000 (13:47 -0800)]
model: utilize CycleGraph 'addEdge()' status

The mo_graph is only modified if addEdge() returns true. Utilize this
information.

11 years agocyclegraph: return 'added' status for addEdge()
Brian Norris [Tue, 5 Feb 2013 21:44:32 +0000 (13:44 -0800)]
cyclegraph: return 'added' status for addEdge()

The ModelChecker would like to know if it's adding a new edge, or just
and existing edge. If the edge is not new, then there are fewer
resulting update checks needed.

11 years agocyclegraph: add documentation
Brian Norris [Tue, 5 Feb 2013 06:50:45 +0000 (22:50 -0800)]
cyclegraph: add documentation

11 years agocyclegraph: bugfix - only use concrete writes to eliminate threads
Brian Norris [Tue, 5 Feb 2013 01:12:11 +0000 (17:12 -0800)]
cyclegraph: bugfix - only use concrete writes to eliminate threads

11 years agocyclegraph: edit template for checkReachable
Brian Norris [Tue, 5 Feb 2013 00:24:36 +0000 (16:24 -0800)]
cyclegraph: edit template for checkReachable

11 years agocyclegraph: edit template for addEdge
Brian Norris [Tue, 5 Feb 2013 00:24:21 +0000 (16:24 -0800)]
cyclegraph: edit template for addEdge

11 years agocyclegraph: add overloaded getNode_noCreate()
Brian Norris [Tue, 5 Feb 2013 00:22:03 +0000 (16:22 -0800)]
cyclegraph: add overloaded getNode_noCreate()

Need a generic way to map a ModelAction/Promise to a CycleNode.

11 years agomodel: add promise-node edges for 'read' actions
Brian Norris [Sat, 2 Feb 2013 01:51:56 +0000 (17:51 -0800)]
model: add promise-node edges for 'read' actions

11 years agocyclegraph: template-ize checkReachable()
Brian Norris [Sat, 2 Feb 2013 01:47:57 +0000 (17:47 -0800)]
cyclegraph: template-ize checkReachable()

ModelChecker will need to query the mo_graph regarding the modification
order of promised future writes.

11 years agomodel: template-ize 'r_modification_order'
Brian Norris [Sat, 2 Feb 2013 00:44:22 +0000 (16:44 -0800)]
model: template-ize 'r_modification_order'

We will need to add "read modification order" edges when 'rf' is either
a ModelAction or a Promise. This function works nicely with a template.

11 years agoaction: fixup printing for RMW/RMWR
Brian Norris [Fri, 1 Feb 2013 23:33:38 +0000 (15:33 -0800)]
action: fixup printing for RMW/RMWR

Some read actions didn't really have a correct 'value' saved in the
ModelAction. Now that we have the 'promise' recorded, always retrieve
the value from reads_from or reads_from_promise.

11 years agoaction: store Promise in ModelAction
Brian Norris [Fri, 1 Feb 2013 23:27:32 +0000 (15:27 -0800)]
action: store Promise in ModelAction

11 years agocyclegraph: add full promise resolution, node merging
Brian Norris [Fri, 1 Feb 2013 23:11:13 +0000 (15:11 -0800)]
cyclegraph: add full promise resolution, node merging

We now support the interfaces needed for tracking Promise constraints in
CycleGraph.

11 years agocyclegraph: add CycleNode::resolvePromise(), CycleNode::getPromise()
Brian Norris [Fri, 1 Feb 2013 23:09:07 +0000 (15:09 -0800)]
cyclegraph: add CycleNode::resolvePromise(), CycleNode::getPromise()

11 years agopromise: add is_compatible()
Brian Norris [Fri, 1 Feb 2013 23:07:56 +0000 (15:07 -0800)]
promise: add is_compatible()

11 years agocyclegraph: map Promises to Promise nodes
Brian Norris [Tue, 29 Jan 2013 02:48:46 +0000 (18:48 -0800)]
cyclegraph: map Promises to Promise nodes

11 years agocyclegraph: template for addEdge()
Brian Norris [Tue, 29 Jan 2013 02:39:23 +0000 (18:39 -0800)]
cyclegraph: template for addEdge()

This function will be identical for all combinations of ModelAction /
Promise. So just make it a template.

11 years agocyclegraph: rename addEdge() to addNodeEdge()
Brian Norris [Tue, 29 Jan 2013 02:30:28 +0000 (18:30 -0800)]
cyclegraph: rename addEdge() to addNodeEdge()

This is a "low-level" internal function, where the other addEdge()
implementations will be high-level, external interfaces. Differentiate
the names, then.

11 years agocyclegraph: add removeEdge(), removeBackEdge()
Brian Norris [Sat, 26 Jan 2013 00:41:27 +0000 (16:41 -0800)]
cyclegraph: add removeEdge(), removeBackEdge()

For popping edges of a node that's about to be merged with another one.

Note that if using these functions, a user has to manage the
'CycleGraph::hasCycles' state. This only handles the inter-Node edge
lists.

11 years agocyclegraph: add Promise CycleNode
Brian Norris [Sat, 26 Jan 2013 01:19:55 +0000 (17:19 -0800)]
cyclegraph: add Promise CycleNode

A very bare-bones constructor.

11 years agocyclegraph: trivial shortening
Brian Norris [Wed, 6 Feb 2013 21:42:24 +0000 (13:42 -0800)]
cyclegraph: trivial shortening

11 years agoMakfile: add 'make pdfs' target to build PDF from .dot graph
Brian Norris [Tue, 5 Feb 2013 23:16:03 +0000 (15:16 -0800)]
Makfile: add 'make pdfs' target to build PDF from .dot graph

11 years agomodel: don't print scheduler randomly
Brian Norris [Wed, 6 Feb 2013 03:31:57 +0000 (19:31 -0800)]
model: don't print scheduler randomly

11 years agoaction: fix incorrect comment
Brian Norris [Sat, 2 Feb 2013 02:08:39 +0000 (18:08 -0800)]
action: fix incorrect comment

11 years agoDoxyfile: don't recurse into all directories
Brian Norris [Sat, 2 Feb 2013 01:18:32 +0000 (17:18 -0800)]
Doxyfile: don't recurse into all directories

11 years agocyclegraph: use vector empty() and clear()
Brian Norris [Wed, 30 Jan 2013 18:19:21 +0000 (10:19 -0800)]
cyclegraph: use vector empty() and clear()

11 years agonodestack/model: spacing
Brian Norris [Tue, 29 Jan 2013 18:15:44 +0000 (10:15 -0800)]
nodestack/model: spacing

11 years agopromise: update names/comments
Brian Norris [Sat, 26 Jan 2013 00:59:16 +0000 (16:59 -0800)]
promise: update names/comments

Make it more clear what 'act' is (it's a 'read' action).

11 years agocyclegraph: RMW atomicity violation must flag a cycle
Brian Norris [Fri, 25 Jan 2013 21:35:38 +0000 (13:35 -0800)]
cyclegraph: RMW atomicity violation must flag a cycle

Because we've removed some of the special-casing for RMW atomicity
violations, we don't need the separate 'hasRMWViolation' condition;
instead, we should explicitly flag atomicity violations as a cycle.
Previously, there was a subtle bug related to this issue, where cycles
were flagged only as RMW violations and did not show up to the
model-checker at the appropriate points.

11 years agocyclegraph: reformat, improve 'addRMWEdge' comments
Brian Norris [Fri, 25 Jan 2013 01:29:58 +0000 (17:29 -0800)]
cyclegraph: reformat, improve 'addRMWEdge' comments

Make it slightly clearer what this function's intent is. (It's only used
for the introduction of the first edge between 'from' and 'rmw' s.t.:

  from->is_write() && rmw->is_rmw() && from --rf-> rmw

11 years agocyclegraph: separate an 'addEdge(CycleNode *, CycleNode *) function
Brian Norris [Fri, 25 Jan 2013 01:26:28 +0000 (17:26 -0800)]
cyclegraph: separate an 'addEdge(CycleNode *, CycleNode *) function

We need to represent edge addition as a low-level operation on
CycleNodes, not just on ModelActions.

11 years agomodel: remove ModelChecker::is_infeasible_ignoreRMW()
Brian Norris [Fri, 25 Jan 2013 01:18:06 +0000 (17:18 -0800)]
model: remove ModelChecker::is_infeasible_ignoreRMW()

We don't make any special exceptions for this condition anymore, so drop
the function.

11 years agomodel: add immediate future value for RMW reordering
Brian Norris [Thu, 10 Jan 2013 01:39:24 +0000 (17:39 -0800)]
model: add immediate future value for RMW reordering

When RMW atomicity would otherwise rule an execution infeasible, we may
need to pass a future value back 'immediately,' to allow the
model-checker to effectively reorder the RMW's. For such cases, we don't
wait for all current promises to be resolved.

11 years agocyclegraph: detect cycles immediately
Brian Norris [Wed, 9 Jan 2013 23:26:47 +0000 (15:26 -0800)]
cyclegraph: detect cycles immediately

Previously, we have used a special case in CycleGraph to delay detection
of a mo-cycle (actually, an RMW atomicity violation) long enough so that
a RMW can "reorder" across another RMW by passing its future value.
Unfortunately, this only works some of the time, as the execution
*may or may not* be a feasible prefix which allows the sending of the
future value.

Instead, we need to pull this special case out of CycleGraph and (in
subsequent commits) will add a more proper solution in model.cc.

11 years agopromise: bugfix - a disabled thread should not be eliminated
Brian Norris [Thu, 24 Jan 2013 03:00:49 +0000 (19:00 -0800)]
promise: bugfix - a disabled thread should not be eliminated

Because we now only consider a subset of threads for satisfying
promises, we can have a disabled thread that still may satisfy a
promise; it could simply synchronize with another unrelated thread, then
continue to generate a write that can resolve the promise.

As a side effect, this change makes "has_failed()" much simpler.

11 years agomodel: modify promises on THREAD_{CREATE,FINISH}
Brian Norris [Thu, 24 Jan 2013 02:47:53 +0000 (18:47 -0800)]
model: modify promises on THREAD_{CREATE,FINISH}

When a thread is created it *must* pass its promise satisfiability to
its children.

When a thread finishes, we should remove it from all promises. This can
help prune a search early, if some read was depending only on the
finishing thread: we can then declare an unresolved promise.

11 years agopromise: associate Promises with a set of threads
Brian Norris [Thu, 24 Jan 2013 02:43:14 +0000 (18:43 -0800)]
promise: associate Promises with a set of threads

A Promise can be associated with a set of threads, so that we can
perform elimination more efficiently and precisely.

11 years agoaction: record future value
Brian Norris [Thu, 24 Jan 2013 02:05:28 +0000 (18:05 -0800)]
action: record future value

Future values don't currently show up in ModelAction (e.g., when
printing). We should set the value when we choose to read from a future
value.

11 years agofuture_value: add thread ID parameter
Brian Norris [Thu, 24 Jan 2013 01:33:23 +0000 (17:33 -0800)]
future_value: add thread ID parameter

This just records the parameter for now, and makes it a distinction
between future values. Shouldn't affect model-checker behavior, except
for the introduction of extra future values: one for each thread which
writes the same value.

We calculate whether the writing thread exists at the time of the future
value and if not, find an ancestor thread which does.

11 years agonodestack: pass 'struct future_value' to add_future_value()
Brian Norris [Thu, 24 Jan 2013 01:24:11 +0000 (17:24 -0800)]
nodestack: pass 'struct future_value' to add_future_value()

This makes more sense than passing individual parameters. This way, we
construct our future_value in ModelChecker, then simply pass it to the
NodeStack.

11 years agomodel: add const to get_thread(ModelAction *act)
Brian Norris [Thu, 24 Jan 2013 01:21:19 +0000 (17:21 -0800)]
model: add const to get_thread(ModelAction *act)

11 years agomodel: fixup indentation, spelling in comment
Brian Norris [Thu, 24 Jan 2013 01:02:46 +0000 (17:02 -0800)]
model: fixup indentation, spelling in comment

11 years agomodel: style
Brian Norris [Thu, 24 Jan 2013 00:51:39 +0000 (16:51 -0800)]
model: style

11 years agomodel: remove local variable
Brian Norris [Thu, 24 Jan 2013 00:34:00 +0000 (16:34 -0800)]
model: remove local variable

11 years agopromise: SnapshotAlloc for vector
Brian Norris [Wed, 23 Jan 2013 20:56:01 +0000 (12:56 -0800)]
promise: SnapshotAlloc for vector

We must ensure that any new memory allocated by the model-checker uses
our private snapshotting heap, not the user program's heap.

11 years agopromise: refactor has_failed()
Brian Norris [Wed, 23 Jan 2013 20:50:57 +0000 (12:50 -0800)]
promise: refactor has_failed()

has_failed() can simply call the thread_is_eliminated() function which
does much of the same computation already. We can drop the
'((int)i != promise_tid)' clause, since the 'promise_tid' thread must
already be eliminated.