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

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

avoid warning

merge
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker

Conflicts:
config.h
model.cc

optimization...don't calloc the datarace tables every single time...it is really expensive for rollback

model: remove useless special case

Why do we want to print races, etc., when exiting due to execution
length bound? If you want that, just enable debug prints.

model: don't export Scheduler

I removed any users of the get_scheduler() function.

model/promise: use ModelChecker is_enabled() interface

class Promise should not need to access Scheduler directly. Use the
ModelChecker interface.

model: is_deadlocked() (sort of) had a bug

We were comparing the boolean (is_enabled(t)) to an enum
(THREAD_DISABLED). This happened to work as we wanted to because
THREAD_DISABLED == 0 == false. But that's not really what I meant...

Anyway, this uses a proper ModelChecker::is_enabled(tid) interface.

model: add ModelChecker is_enabled() functions

We don't want all users to have to directly address the scheduler;
provide an interface.

schedule: improve is_enabled() routines

The comments don't clearly explain what is_enabled() might include
(i.e., SLEEP_SET, ENABLED, or DISABLED). Also, we need a direct accessor
keyed by thread_id_t, not just by class Thread.

model: fix spacing

model: move snapshot members out of header

This struct is only used within model.cc

README

main: change default future value sloppiness

Future value sloppiness should be set somewhat in proportion to
maxfuturedelay, and we need a value higher than 2. Set to 10 for now,
although we may change this later.

nodestack: implement expiration sloppiness parameter

Now, a previously-explored, repeated future value will only generate a
new future-value/expiration pair if the expiration is higher than the
previous expiration + sloppiness. This prevents executions where we
continue to step up the future value expiration by a small increment,
creating the same execution.

This also rewrites the add_future_value() logic just a bit so that it is
a little bit more clear.

main/model: add future value expiration sloppiness parameter

Functionality not implemented yet

nodestack: limit the number of future values per read

Not tested very thoroughly, but it seems to limit the future values set
as intended.

main: add maxfuturevalues parameter (-M)

Not implemented yet

common: early quit on MODEL_ASSERT()

If a user program hits an assertion, we should quit before executing any
further. i.e., don't even wait for the next atomic action, since the
assertion might trigger more bugs that have unintended/unforseen
consequences.

model-assert: add MODEL_ASSERT() for user programs

model: refactor build_reads_from_past

A couple of if-else conditions can be merged to a single if block.

Also, I move the DBG prints for the may_read_from set into the correct
part of the if, to avoid printing false messages about the may_read_from
set.

common/config: allow enable/disable ASSERT() easily

Now, assertions (ASSERT()) are only checked if the CONFIG_ASSERT macro
is defined. We leave this enabled for all builds for now.

race: where possible, use "const void *" for addresses

This allows more flexible use for read-only objects.