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.

test: add AB/BA deadlock test

model: add deadlock detection

This is only a simple end-of-execution deadlock detection. If we have a
true deadlock, and no other threads are spinning, then our execution
will exit --- we can recognize this state.

For more complicated deadlocks involving other spinning threads, we need
to perform some sort of depth-first-search cycle detection.

model: get_num_threads() should be const

snapshot: find the correct binary name

This is somewhat of a neutral change; the existing /proc/*/maps check
works because our path name usually has the word 'model' in it. But
really, we should find the true, full path of the user program.

This should be extended to find more maps (e.g., for other libraries),
and it should be extended for Mac OSX too.

snapshot: read from /proc/self/maps

We don't need to get the PID

main: fixup parameter parsing for user program

The user program expects 'optind' to be reset and for 'argv' and 'argc'
to include the program name as the first argument variable.

Note: our mmap()/mprotect()-based snapshotting does not snapshot this
'optind' global, so user-progs that use optarg() functionality might
fail.

test: add AB/BA deadlock test

model: add deadlock detection

This is only a simple end-of-execution deadlock detection. If we have a
true deadlock, and no other threads are spinning, then our execution
will exit --- we can recognize this state.

For more complicated deadlocks involving other spinning threads, we need
to perform some sort of depth-first-search cycle detection.

model: get_num_threads() should be const

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

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.

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

Merge branch 'master' into pldi13

main: always ensure defaults when printing

If one or more arguments have been parsed by the time we print a help
message, we may print the wrong defaults. Fix: always reset to defaults
before printing.

model: fix some whitespace

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

snapshot: find the correct binary name

This is somewhat of a neutral change; the existing /proc/*/maps check
works because our path name usually has the word 'model' in it. But
really, we should find the true, full path of the user program.

This should be extended to find more maps (e.g., for other libraries),
and it should be extended for Mac OSX too.

Merge remote-tracking branch 'origin/master' into pldi13

annoying bug...  Optimization was originally intended for the following insight:
if you have a unresolved read and a write w that is mod ordered after whatever that read sees, then any writes that are mo past w should not send their future values back to the unresolved read.  So we begin by looking for operations that happen after the unresolved read and if they are a write we have our w, and if they are a read then its reads_from is our w.
The case I missed was we don't want to consider the write that the read we want to send the value to is currently reading...  It won't cause a mo problem because it will be gone if we send a future value back to that read.

snapshot: read from /proc/self/maps

We don't need to get the PID

Merge remote-tracking branch 'origin/master' into pldi13

promise: fix signed/unsigned warning

clean up check code

optimization - a given write can resolve at most one promise from a rmw

various fixes.  linux rw locks should work again with -m 1

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

fix two bugs in model.cc...mainly don't print bogus data race messages...

this is the bad line...

previous synchronization was weird...

Merge remote-tracking branch 'origin/master' into pldi13

fix bugs with promise check...

changes to fix at least a bug

main: fixup parameter parsing for user program

The user program expects 'optind' to be reset and for 'argv' and 'argc'
to include the program name as the first argument variable.

Note: our mmap()/mprotect()-based snapshotting does not snapshot this
'optind' global, so user-progs that use optarg() functionality might
fail.

common/config: disable ASSERT() by default

fix norris bugs

model: totally destroy 'curr' within initialize_curr_action()

We don't really want 'curr' and 'newcurr' to hang around together. So
convert initialize_curr_action() to have two "return" parameters; it
overwrites the 'curr' pointer as a return value and it returns a status
boolean to show that it overwrote it. This may help prevent some future
bugs.

clockvector: remove old include

We don't use std::max anymore.

found the bug

realloc doesn't guarantee zeroing...

bug

fix new bug
norris's makefile change breaks compile on mac

clockvector: bugfix - bad clock merge

The clock merge function had a really bad bug, where it would copy
garbage into the new clock vector, if the earlier clock vector (cv) was
"wider" than the current clock vector (this).

Now, ClockVector::merge is much simpler and much less buggy.

nodestack: improve bounds-checking assertion

I have a test case where future_index == -1 in get_future_value(). It
passes the ASSERT() and instead triggers a fault when accessing the
vector.

With the benchmarks at this commit:

    commit 40b27f40998eed81640b016094bacf79df96d377
    mpmc-queue: run more producer/consumer threads

I can trigger a model-checker bug by running:

  # ./run.sh mpmc-queue/mpmc-queue -f 4 -m 1
  ...
  Error: assertion failed in nodestack.cc at line 319
  stack trace:
    ../libmodel.so : Node::get_future_value()+0x56
    ../libmodel.so : ModelChecker::process_read(ModelAction*, bool)+0x141
    ../libmodel.so :
  ModelChecker::check_current_action(ModelAction*)+0x2ff
    ../libmodel.so : ModelChecker::take_step()+0x6c
    ../libmodel.so : ModelChecker::finish_execution()+0x10
    ../libmodel.so : ()+0x16a8a
    ../libmodel.so : main()+0x37
    /lib/x86_64-linux-gnu/libc.so.6 : __libc_start_main()+0xed
    mpmc-queue/mpmc-queue() [0x400f59]
  ...

common.mk: build with -O3 (except for Mac OSX)

model: silence "uninitialized" warning

model: update mo_may_allow restrictions

For future values, we can enforce the following rule:

  If X --hb-> Y --mo-> Z, then X should not read from Z.

This a change from previous behavior, where we used 'sb' instead of
'hb'.

Tested with linuxrwlocks example:

  ./run.sh test/linuxrwlocks.o -f 4 -m 1

No difference in number of executions (feasible or infeasible); HASH
values were exactly the same.

tests: add thinair test

Makefile/malloc: don't warn for self-assign

Makefile: use -rdyanmic only for linking

I ignored this part of the GCC manpage:

  "Pass the flag -export-dynamic to the ELF linker..."

tests: use signed printf format