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

model: remove snapshotted 'nextThread'

The 'nextThread' field is no longer needed, since I've simplified
take_step().

model: pass current action as function argument

Diminish the use of 'priv->current_action', and instead pass it to
take_step() as an argument. At the same time, it is more obvious that we
do not need to reset priv->current_action to NULL.

model: simplify take_step()

Now that priv->current_action is always non-NULL (when reaching
take_step()), we can simplify the logic a bit. Also, rename some
variables.

model: force first thread to run immediately

Forcing the first thread to run immediately yields us our first
ModelAction, so we won't have to special-case the case that
current_action == NULL.

model: change guaranteed condition into ASSERT()

This guaranteed condition should only be included as an ASSERT(). This
gives a bonus, that the code becomes a little easier to read.

nodestack: rename 'iter' to 'head_idx'

nodestack: make 'iter' signed

iter will need to be negative when we allow the NodeStack to be empty.

schedule: spacing

nodestack: spacing

model: spacing

model: rename 'promise_index' to 'i'

The fuction looks cleaner if the loop variable is just a simple 'i'
index.

test/uninit: add an "uninit" test

This is a weird example, where we don't explicitly initialize y, but
synchronization should guarantee that it is initialized.

Right now, this example has a problem where we never see flag == 2.

model: return value from switch_to_master

action: refactor ATOMIC_READ printing

For ATOMIC_READ, we don't need a special case to print VALUE_NONE,
because any action where the value isn't explicitly set (e.g., all
ATOMIC_READ actions) default to VALUE_NONE. And if this 'default'
changes in the future, we would want to print it.

(Right now it's confusing, for instance, when we have a failed promise
execution, since the model-checker trace gives no indication of what the
promised value actually *was*. This should be fixed sometime.)

nodestack: add 'const'