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

cyclegraph: remove redundant code

The edgeCreatesCycle() function can simply be reduced to
checkReachable(), since checkReachable() will detect "to == from".

cyclegraph: add edgeCreatesCycle() function

This is repeated code, so make it a function.

cyclegraph: add const

model: add 'add_future_value()' wrapper

Encapsulate a little logic in a function here, so we can reuse this in
other places.

model: add PendingFutureValue constructor

new test case

cyclegraph: add back edges to CycleNode

hashtable: style

cyclegraph: add putNode() helper

hashtable: style

promise: style fixup

cyclegraph: fix insignificant memory leak

cyclegraph: small cleanup

hashtable: add const

hashtable: fixup style

snapshot: more renaming

snapshot-interface: bugfix - reorder constructor params

The snapshot_id should come first.

snapshot-interface: rename, clean up

snapshot-interface: change hand-coded stack to vector

The logic, etc., is much simpler when using C++ vectors and constructors
here.

snapshot: turn C++ interface into C interface

We don't need all this 'class' structure exposed as an interface; we
only use 3 simple functions (one of which probably can be removed).

fixup style

snapshot: more renaming

addMemoryRegionToSnapShot -> snapshot_add_memory_region
rollBack                  -> snapshot_roll_back
takeSnapshot              -> take_snapshot

snapshot: add (unused) mprot_snapshotter destructor

snapshot: rename HandlePF -> mprot_handle_pf

snapshot: add constructor for mprot_snapshotter

snapshot: separate struct SnapShot naming

The "struct SnapShot snapshotrecord;" structure is very uninformative in
naming and is distinctly different for mprotect-based and fork-based
snapshotting. This renames the struct in order to more clearly separate
its usage in the different implementations.

snapshot: edit capitalization in comment

snapshot: combine public interfaces

Implement the public "API" interfaces once, with separate calls made out
to "fork_*" and "mprotect_*" versions. This should make things a little
clearer, and potentially remove the #if's eventually.

snapshot: split up fork-based and mprotect-based snapshotting

The code is kind of cluttered with #if's and intermixed implementations.
Now, snapshot.cc is split into two halves, where the first half
implements mprotect-based snapshotting and the latter half implements
fork-based snapshotting.

snapshot: remove SSDEBUG

We don't need a separate snapshotting DEBUG() macro.

dissolve snapshotimp.h

snapshotimp.h was being used as a way to expose some of the snapshotting
implementation to mymemory.cc, just for fork-based snapshotting. I've
removed that exposure, so now I can pull the entire header into
snapshot.cc.

mymemory/snapshot: rearrange snapshot implementation

Move some implementation details back to snapshot.cc.

snapshotimp: move macros to fork-based

These macros are only used for fork-based snapshotting.

snapshot: change 'struct SnapShotPage' to a simple typedef

The struct SnapShotPage was being used improperly; it was accessed as
simply an array of data, instead of explicitly accessing its member
variable (which itself was an array). So just make this more
straightforward as a typedef'd array.

This also corrects a pointer cast to use (void *) when appropriate.

fixup style

threads: change thrd_t to store Thread pointer

I need to make some bigger changes to Thread allocation, so we'll need
to modify the storage of thrd_t.

action: add get_thread_operand() method

Instead of guessing at the (type-unsafe) storage within
THREAD_{CREATE,JOIN} ModelActions, we can at least code this within a
single method. Note that this method may get more complex, particularly
for THREAD_CREATE.

model: use get_thread(curr) instead of get_current_thread()

The former is more accurate; the latter is only intended for use while
in user-thread context, where we are sure that Scheduler is in the
appropriate state.

test: don't relay on thrd_current() returning an int

The C11 spec doesn't require thrd_t to be a particular object
format/type. I will need to change this type, I think, so don't assume
it's an int.

nodestack: refactor Node constructor

action: fixup style

model: refactor check_current_action, next thread computation

Pulling the 'get_next_thread()' computation out of
check_current_action() so that I can restructure the model-checker
execution a little.

threads: assert completion is only called once

We don't need to support the case that Thread::complete() is called
multiple times. We should instead ensure (ASSERT()) that it is only
called when the Thread is not already completed (and cleaned up).

threads: assert THREAD_COMPLETED is immutable

clean up some DEBUG() messages

We were printing may_read_from info twice.

Printing the current action when we get to check_current_action() is
helpful.

Printing scheduling based on priority is also useful, as we recently had
a "bug" involving fairness/priority.

Include the file name in DEBUG() prints, since we may have the same
function names in different files/classes.

nodestack: style

nodestack: add const

nodestack: do not allow Node with act == NULL

Since I removed the root 'NULL' Node, all Nodes will have a
corresponding action. Now, just ASSERT this in the constructor.

nodestack: don't create empty base node

We don't actually need an empty base node, since the first thread will
never be backtracked. But it does mean that we no longer assume that
every newly-constructed Node has a parent.

Note that this changes the number of executions performed for some
programs. Even though the model-checker should be deterministic, this is
not a bug, AFAICT. The discrepancy seems to come from a change in
scheduling, where the scheduler order may differ after reaching a
divergence point. This is caused by the fairness support which is hacked
into Node creation, so threads may gain priority sooner in the presence
of a useless Node. In fact, before this change, (almost?) every
execution caused a thread (typically thread 1) to gain priority due to
fairness. Now, we reach this condition much more occasionally.

I made measurements of the scheduling decisions based on priority for
the execution of:

 # ./run.sh test/linuxrwlocks.o -f 10 -m 2

Previously, threads gained priority 10042 times in 7906 executions (9947
of those were for thread 1, when it would shortly become disabled).

Now, threads gain priority 68 times in 8396 executions (thread 1 never
gains priority).

model: check for NULL parent Node

I'm editing the NodeStack to eliminate the empty Node. So we should
check to ensure that the Node has a parent before using it.

model: use helper 'get_thread()'

nodestack: print extra backtracking info

If we ever use the Node::print() method, print some extra info about
backtracking.

model: style fixups

model: add 'set_latest_backtrack()'

model: print bug reports only for feasible executions

We can assert a bug (e.g., uninitialized load) without having a feasible
exeuction. If this execution is later ruled infeasible, we don't need to
print the trace info.

test: uninit: remove @todo (bug fixed)

The previous bugfix allows this example to run properly, so remove the
@todo.

model: bugfix - mo_may_allow was too restrictive

This bugfix has the same rationale as with the following commit:

commit c2d7fa973e562c194eb732d8dc58ab7659b7a2ee

We do not want the potential reader to disqualify itself from reading a
future value; previously, this was fixed only for reads (not RMW's). But
we can experience the same problem with RMW's, which are both read and
write.

So, instead of using 'act != reader' as a special case for the is_read()
case, just use it as a breaking condition in addition to

   !(reader --hb-> act)

This is really intended anyway, since our happens-before is reflexive,
whereas it is irreflexive in the specification.

model: make dumpGraph 'const'

SUPPORT_MOD_ORDER_DUMP can't compile if dumpGraph() isn't const.

nodestack: fixup style