promise: use id_to_int()

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.

action: bugfix - initialize member

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.

model: remove argument from mo_check_promises

cyclegraph: possible optimization

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.

model: add read-write coherence for promise nodes

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

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

cyclegraph: expand template usage

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

model: refactor to use a helper function

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.

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.

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.

cyclegraph: refactor for indentation

Makefile / git: cleanup generated .dot and .pdf files

cyclegraph: add wrappers for some common functionality

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.

model: cosmetic improvements to resolve_promises()

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

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.

cyclegraph: template-ize addRMWEdge()

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.

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.

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.

promise: add const

model: utilize CycleGraph 'addEdge()' status

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

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.

cyclegraph: add documentation

cyclegraph: bugfix - only use concrete writes to eliminate threads

cyclegraph: edit template for checkReachable

cyclegraph: edit template for addEdge

cyclegraph: add overloaded getNode_noCreate()

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

model: add promise-node edges for 'read' actions

cyclegraph: template-ize checkReachable()

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

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.

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.

action: store Promise in ModelAction

cyclegraph: add full promise resolution, node merging

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

cyclegraph: add CycleNode::resolvePromise(), CycleNode::getPromise()

promise: add is_compatible()

cyclegraph: map Promises to Promise nodes

cyclegraph: template for addEdge()

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

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.

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.

cyclegraph: add Promise CycleNode

A very bare-bones constructor.

cyclegraph: trivial shortening

Makfile: add 'make pdfs' target to build PDF from .dot graph

model: don't print scheduler randomly

action: fix incorrect comment

Doxyfile: don't recurse into all directories

cyclegraph: use vector empty() and clear()

nodestack/model: spacing

promise: update names/comments

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

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.

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

cyclegraph: separate an 'addEdge(CycleNode *, CycleNode *) function

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

model: remove ModelChecker::is_infeasible_ignoreRMW()

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

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.

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.

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.

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.

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.

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.

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.

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.

model: add const to get_thread(ModelAction *act)

model: fixup indentation, spelling in comment

model: style

model: remove local variable

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.

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.

promise: move thread_is_eliminated()

Should be in the implementation file, not the header.

promise: rename has_sync_thread() -> thread_is_eliminated()

This function doesn't actually check for synchronization; there are
numerous ways to be eliminated.

promise: rename check_promise() -> has_failed()

The name "check_promise" doesn't really tell what this function is
doing. It is actually checking if the promise is unresolvable.

promise: refactor eliminate_thread()/check_promise()

eliminate_thread() and check_promise() have near-duplicate code, for
checking if the promise has failed. This change makes them consistent
(check_promise() now knows to eliminate its own thread immediately) and
allows one function to simply call the other.

promise: rename increment_threads() -> eliminate_thread()

This function name really doesn't describe what it does, in my opinion.
Update the name and add a description.

nodestack: add const

promise: construct with a 'future_value' struct

Don't pass a bunch of parameters individually; just pass the struct.

nodestack/promise: move future_value struct, update headers

struct future_value will be used more closely with class Promise, so put
it in the promise.h header. This requires some updates to other header
inclusions.

nodestack: pass writer ModelAction to add_future_value()

NodeStack will have to know a little more about who wrote the future
value, so just pass the ModelAction as a parameter.

nodestack: eliminate get_future_value_expiration()

We don't need separate accessors for each member of 'struct
future_value'. Just pass the entire struct.

nodestack: remove extra blank lines

remove #include <list>

STL lists aren't used here anymore.

nodestack: improve debug print() method

Print the contents of the future values and may-read-from set, if we're
printing the NodeStack for debugging purposes.

fix bug in promise handling code...

if any promise for a thread resolved, we assumed that the corresponding
write happened after all promises for that threads...clearly doesn't
need to be the case...

[Brian Norris:] This fixes some bugs where we don't see all the expected
behaviors: e.g., with

  ./run.sh test/rmwprog.o -- 3

Now we see all 20 behaviors.

promise: fixup style

test: rmwprog: support command-line argument

This test can easily be extended to allow more than 2 atomic increments
per thread. For instance, it's interesting to see the model-checker
behavior for 4 increments per thread. Now, you can do this with a simple
numeric command-line argument that gets passed to the user program.

Example - run rmwprog with 4 increments per thread, viewing the
execution traces verbosely:

  ./run.sh test/rmwprog.o -v -- 4

nodestack: improve debug prints

schedule: improve scheduler printing

Print more detailed, informative info about the Scheduler, still on a
single line.

schedule: allow Schedule::print() even in non-DEBUG build

For instance, printing from w/in gdb

model: bugfix - sleep sets are NOT directly compatible with DPOR

We failed to incorporate changes from the POPL'05 DPOR paper's addendum,
preventing us from seeing all behaviors in some test programs. This
fixes that.

litmus: iriw: allow command-line switch 's' for seq_cst

The IRIW litmus test fails if we make it seq_cst; we don't see all 15
potential behaviors. Run with:

  # release/acquire litmus test
  ./run.sh test/litmus/iriw.o -v

  # seq_cst litmus test
  ./run.sh test/litmus/iriw.o -v -- s

litmus: iriw: use release/acquire, not release/relaxed

tests: litmus: link up Makefile properly

Now this builds the litmus tests properly.

test: litmus: add litmus tests from Nitpicking C++

This adds most of the litmus tests from Nitpicking C++ Concurrency. Note
that it leaves out the 'consume' tests (replacing it with the
also-mentioned release/acquire test). It doesn't test the seq_cst
results, although I could provide command-line switches to do so...

test: Makefile: add $(BASE) variable

Makes this Makefile a little more flexible

model: reformat execution trace prints

Bring the "INFEASIBLE" message together with the "Execution #" message,
to make the log more compact and readable (e.g., grep for "Execution"
will give you some regularly-patterned, useful information).

model: spelling mistake

model: fixup "infeasible" messages

These messages should be much more compact and targeted. Currently, we
either get no infeasibility messages (when verbose=0) or we get messages
every time is_infeasible() is executed. Neither is helpful for debugging,
since the infeasibility may be temporary, as we choose a new path for
execution on the fly. So instead, just print the infeasibility message
at the end of infeasible executions.

Also, rather than spread the messages across multiple lines, just put
them together into a single string.

cyclegraph: add documentation