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'

impatomic: add C++ atomic_init()

According to N337, C++ has a C-like atomic_init() function, which was
left out of our impatomic header.

cyclegraph: uniform spacing, style

cyclegraph: bugfix - more SnapshotAlloc

common: bugfix - always display backtrace output

The stacktrace can be hidden if it doesn't go to 'model_out', instead of
'stdout'.

cyclegraph: bugfix - use model-checker's allocater for CycleNode::edges

This vector should use our SnapshotAlloc allocator, to avoid polluting
the user's memory allocator.

This solves an annoying bug that causes us to hit an ASSERT() when a
user's threads aren't allocated in the same location every execution.

cyclegraph: don't export CycleNode::edges directly, use accessors

The CycleNode::edges vector shouldn't be accessed directly; it should be
used through accessors, to hide implementation details. (Really, there's
a bug in the CycleNode that I need to fix, so I'm fixing this first.)

include the correct standard headers

Our own headers are including several of the wrong headers in the wrong
places. Move a few to place them more closely to their actual usage
location, and remove some others that are unused (e.g., <iostream>,
<cassert>, <csignal>).

spacing

model: don't create UNINIT actions for Threads, mutexes, etc.

ModelActions may be associated with fences, mutexes, threads, etc., all
of which never hit the "uninitialized" case. So, we shouldn't create
these UNINIT actions.

action: add is_atomic_var()

To check if a ModelAction is for a C/C++ atomic variable (vs. a Thread
action, a fake ModelChecker action, a mutex, a condition variable, etc.)

model/action: bugfix - UNINIT actions do not have a Node

Fix the one place where ModelChecker looks for a Node in an UNINIT
action.

This also adds an ASSERT() within ModelAction to prevent calling
get_node() on an UNINIT action. It is technically OK to call get_node()
in this case, but most callers don't check for NULL, so it's better to
just catch the ASSERT() for this unwanted special case.

model: remove old "uninitialized" bug check

The previously-existing bug check is not fully correct and has been
replaced with explicit UNINIT actions that, when read from, trigger a
bug assertion.

model: generate UNINIT actions as new atomic operations form

The first time an atomic variable is accessed, we need to add an
appropriate UNINIT action to the ModelChecker data structures. We assign
these ModelActions to the special model-checker thread (Thread 0). Note
that these actions will *not* appear in the NodeStack and will not be
explored in check_current_action, etc.

action: move ModelAction::get_node to action.cc

This function needs to expand a bit, so move it to the implementation
file.

model: add helper for allocating new UNINIT actions

These UNINIT actions will be special; they won't enter the NodeStack,
and so they need to be snapshot-allocated. That way, they will roll-back
with the execution, instead of requiring manual deletion.

mymemory: add placement new

I will need to use the placement new operator, if I want to allocate an
object with an allocator other than the one I established (SNAPSHOTALLOC
vs. MODELALLOC).

model: clear a ModelAction's reads-from properly

action: add ATOMIC_UNINIT type

Adding a new type of "uninitialized atomic" action, to serve as a store
which, if any load is able to "see" this store, constitutes an
uninitialized load - a bug in the user program. It has to act like a
store operation, but it triggers a bug (ModelChecker::assert_bug) if any
load tries to read from it.

Makefile: build dependencies in .*.o.d files

My previous attempts at fixing dependency generation actually cause
full recompilation every time a file is changed. Apparently, it'll work
best if each target object has its own dependency file. i.e., target
'model.o' has a corresponding '.model.o.d' which holds its dependency
information.

Makefile: rename variable to be more clear

model: refactoring + spacing

schedule: add is_sleep_set(thread)

schedule: add const

threads: add const

notes: fence: replace variables to match 29.8

I had some remaining edits to do for my notes 29.8, to match back with
the specification's variables (X, Y, A, B).

notes: fence: rename variables to match spec better

Originally, I purposely renamed these since I needed to introduce more
variables than were in the spec. But it turns out I can make this match
the spec pretty well.

Now: A, B, X, and Y fulfill the same roles as in the original C++
specification statements. I only introduce my new variable as W, when
needed. This also makes sense because W is a Write.

Also, I delete an extraneous paragraph that duplicated a piece of the
spec.

notes: fence: add release/acquire fence notes

I remove the copied-and-pasted algorithm pseudocode, since I didn't feel
like it was necessary to tweak the pseudocode to include fences. I might
change my mind later.

notes: fence: more updates

doc: notes: fence: update fence notes

The backtracking and seq-cst/MO constraints are complete, but the
release/acquire, etc.

model: stop thread-trace search once edge is added

Once an edge has been added from 'act' to the current thread (or the
'rf' thread), we don't need to continue to search for more edges.

doc: notes: add fences note

This note is incomplete.

model: fix bugs in fence-acquire synchronization

(1) In the fence-acquire search, we can't stop searching for prior loads
    when we reach the current action; we must continue to search until
    we find a *different* fence-acquire (or the beginning of the thread)

(2) The load action does not synchronize in fence-acquire
    synchronization: the fence should synchronize. This was just a typo
    (act vs. curr).

impatomic: move atomic_{thread,signal}_fence() to namespace std

run.sh: print the command that runs

This will help understanding typos, script bugs, etc.

model: add process_fence()

process_fence() will only handle fence-acquire. Fence-relaxed is a
no-op; fence-release is only logged for later use; and fence-seq-cst
takes release/acquire semantics, plus some mo-graph rules which apply to
reads/reads (see {r,w}_modification_order).

model: distinguish between 'read' and 'acquire' in release sequences

When using fences, we may have a fence-acquire preceded by a non-acquire
load, where the load takes part in a "hypothetical release sequence" (as
named by Mathematizing C++). So, I add a parameter to
get_release_seq_heads() and to struct release_seq so that we record the
'acquire' operation separately from the 'read'.

For our traditional release sequences, 'acquire' and 'read' will be the
same ModelAction. But fence-acquire support will utilize distinct
actions.

model: add read-acquire/fence-release support

C++ Section 29.8, statement 3: gives conditions under which a
read-acquire and fence-release might synchronize. It's easy enough to
integrate into our existing release sequence code.

action: add is_thread_start()

model: privatize a few interfaces

These functions were only public for ModelAction::read_from, which has
now been internalized into ModelChecker.

model/action: move complicated read_from logic into model.cc

The release sequence wrapper logic will only get more complicated, so
rather than spreading across two files and exporting more interfaces,
just integrate into ModelChecker.

model: record last fence-release from each thread

action: record last fence release from the current thread

model: remove extraneous copy-and-paste

model: add seq-cst fence rules

Add mo_graph constraints, from statements 4-6 in C++ Section 29.3. There
are probably more constraints we can choose for building may-read-from /
future values.

action/model: backtrack for seq-cst and release/acquire fences

Extends backtracking support to explore all interleavings of conflicting
seq-cst fences and potentially-synchronizing write/read/fence pairs.

action: allow fence ModelActions to have location == NULL

model: refactor build_reads_from_past

Just rearrange the logic a little, to prepare for some other additions.

model: add get_last_seq_cst_fence

model: rename last_seq_cst -> last_sc_write

model: rename get_last_seq_cst -> get_last_seq_cst_write

impatomic: add atomic_{thread,signal}_fence() definitions

The impatomic.h header is outdated. Additional information from the ISO
papers N2633, N2731, and N2752 have limited the "fence()" support to
just these two functions.

impatomic: remove fence member functions

Recent C/C++ drafts do not include fence() as a member function for any
object. All fences apply globally (not to any particular object).

[ These changes came in the ISO papers N2633, N2731, N2752 ]

So, I discard any reference to a fence that is associated with an object
(i.e., as a member of an object or with an object parameter).

I will implement a replacement shortly, which just uses the
_ATOMIC_FENCE_(order) macro.

Makefile: fix dependency generation

- Don't regenerate make.deps for 'make clean' target
- Place the dependency on make.deps at the correct level; all "%.o"
  generations depend on it, not the top-level 'all' target

model: remove <list> include

model: add const

schedule: rename get_enabled() -> get_enabled_array()

This function actually returns the array, not a single "enabled" status.
(There's a separate get_enabled() method for getting a single status.)

model: rename isfinalfeasible -> is_feasible_prefix_ignore_relseq

This more accurately reflects its use case and the fact that it is a
slightly-weaker version of isfeasibleprefix(). Also, I integrate it into
isfeasibleprefix(), to avoid re-writing the same conditions.

model: replace isfinalfeasible() with stronger check

The stronger isfeasibleprefix() check is not strictly necessary in these
cases, since we can ensure that promises are resolved before executing
these, but it make sense to have a well-defined "strength" to these
feasibility properties, then use the strongest strength that is useful.

model: privatize, move isfinalfeasible()

This function should go with all the other "feasible" functions.

model: rename some 'isfeasible...' functions to 'is_infeasible...'

These functions can be more accurately described as checking
*infeasibility*, not necessarily feasibility. This helps clarify their
purpose, at least for my understanding.

model: privatize some functions

Just kill finish_execution() while we're at it.

main: remove #include's

main: remove "pass-by-reference" editing in parse_options()

parse_options() can simply pass the argc/argv variables through the
model_checker_params struct now.

Also, document a few things.

threads: remove todo (long overdue)

main/model: move full user-program execution to ModelChecker::run

We don't really need the top-level ModelChecker execution loop to be in
main.cc; it should be exposed simply as a run() method.

model/main: add argc/argv parameter

ModelChecker will take care of launching the user program soon.

model: move flags to private 'model_snapshot_members'

model: add model_snapshot_members constructor/destructor

model: privatize set_assert()

run.sh: rewrite script to handle options more gracefully

Now you can do:

  ./run.sh [OPTIONS]

without having to specify a particular program (defaults to
./test/userprog.o).

output: don't redirect any output for DEBUG builds

README: add verbose (-v) argument

model: optimize get_last_conflict() search

Relaxed operations should never require backtracking, so don't even
bother with searching the list in such cases. I ran some simple
benchmarking tests with linuxrwlocks (timing results below). Also, perf
shows a significant decrease in % time spent in
ModelAction::could_synchronize_with.

------------
Before:
------------

$ time ./run.sh test/linuxrwlocks.o -f 10 -m 10
Number of complete, bug-free executions: 7110
Number of redundant executions: 29
Number of buggy executions: 0
Number of infeasible executions: 43578
Total executions: 50717
Total nodes created: 63463

real 0m7.274s
user 0m6.596s
sys 0m0.652s

2.10%  linuxrwlocks.o  libmodel.so          [.] ModelAction::could_synchronize_with(ModelAction const*) const

------------
After:
------------

$ time ./run.sh test/linuxrwlocks.o -f 10 -m 10
Number of complete, bug-free executions: 7110
Number of redundant executions: 29
Number of buggy executions: 0
Number of infeasible executions: 43578
Total executions: 50717
Total nodes created: 63463

real 0m6.690s
user 0m6.000s
sys 0m0.664s

0.73%  linuxrwlocks.o  libmodel.so          [.] ModelAction::could_synchronize_with(ModelAction const*) const

action: add is_relaxed() function