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

common: update comment

model: add "# redundant" stat

model: refactor end-of-execution output

model: print_summary() should be const

model/main: disable most printing by default, add verbosity

Adds a '-v' parameter for printing verbose info on a non-DEBUG build.
This effectively creates 3 classes of runs:

 - Default build, no -v: only prints info when discovering a buggy
   execution
 - Default build, -v: prints more verbose information, on all feasible
   executions (buggy or non-buggy)
 - Debug build: Built with 'make debug'. Most verbose; prints everything
   for every execution, including infeasible executions. Also prints
   DEBUG() prints (as usual).

output redirection

model: print execution # with trace

Since stats won't be printed regularly, we still want a measure of
"how many executions have run" when we print a summary trace.

print stats only at end of execution

printf -> model_print

As we move toward redirecting program output, we will need a special
printf function for model-checking prints. Just define a simple
model_print() for now.

model: correct plural ("bug" or "bugs")

model: rework assert_bug() and assert_user_bug() interfaces

We don't need assert_bug_immediate(), and we don't need some of the
optional parameters in assert_bug(). Just simplify down to two
interfaces:

    assert_bug()
    assert_user_bug()

The former is useful for all bugs triggered from model-checker threads,
and the latter is useful from a user-thread context, so that you can
immediately switch to the model-checking context and exit the program -
but *only if* the trace is currently-feasible.

dataraces: don't print an uninformative "Data race" bug msg

Now that checkDataRaces() handles all bug reporting and assertions on
its own, we don't need an additional bug report message printed by the
caller. In some cases, this means the caller doesn't have any action to
take. In one case (a race immediately-realized from a user thread), we
still need to "bail out" to the model-checker.

datarace: redirect "Data race @ ..." messages to model-checker bug list

Data race information was previously printed in multiple ways: through
the datarace.cc printRace() method and through the model-checker
assert_bug() method. Start unifying that.

Other notes:
- Data race objects probably should be freed (even though they are
  snapshotted). I fix this.
- Races could be printed more than once previously, since the
  unrealizedraces vector was never cleared of realized races. Now, we
  clear this vector every time we process it (in a feasible execution),
  either stashing a bug message or dropping the race entirely.

datarace: change "Datarace" to "Data race"

model: restructure statistics records

model: annotate SNAPSHOT for bug_message

Since we use operator new with bug_message, it needs to be marked
SNAPSHOTALLOC.

model: temporary fix for uninitialized loads

This patch does two things:

(1) Convert 'set_assert()' to 'assert_bug()' to provide:
    - More unified bug printing
    - Only printing the bug for a feasible prefix
(2) Avoids the work_queue loop if a bug was asserted

Part (1) mostly provides some cosmetic fixes.
Part (2) prevents an ASSERT() from being thrown in future values, since
we don't abort the trace early enough when there's nothing to read from.

This all needs better treatment of uninitialized loads, as there are
some loose ends.

assert bugs through common interface

- User-provied assertions (MODEL_ASSERT())
- Data races
- Deadlocks
- Unlock before lock

Notably, I have not yet converted the "uninitialized load" bug, because
it actually isn't correct yet. It needs to handle future values and lazy
synchronization better.

model: print bug reports at end of each execution

This ensures:
- that bug reports are printed only at the end of feasible executions
- that execution summaries are printed only for complete (or halted and
  buggy) executions that are feasible
- that all bug reports will have the same formatting (at least, ones
  that use the 'assert_bug()' function)

Note that deadlocks are the only bugs reported this way right now. I'll
fix that up soon.

model: add bug reporting framework

This will help clean up bug reporting so that bugs are only printed for
complete, valid executions.

model: remove unnecessary DEBUG()

model: use snapshot_calloc()

Also, might as well free priv on destruction.

model: add 'const'

model: routine to check if execution is complete

Not used yet.

make compile on linux...needed string.h

Merge branch 'master' of /home/git/model-checker

optimize hashtable so we don't always build new ones for cyclegraph check

remove hashtable functionality

make hashtables only contain primitive types or pointers