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

changes to allow running programs with racing initialization...

check in test

add test from nitpick paper...

embarrassing bug...fixed...

model: fix - RMW cannot break release sequences

I misinterpreted the spec's description of release sequences.

Doxygen: document subdirectories

Document include/, but ignore doc/, benchmarks/, and test/.

thread_id_t: add comments

fixup 'int' vs. 'thread_id_t' usage

modeltypes: move to include/ dir, for now

The <mutex> header uses some small amount of private model-checker
information, so just move the common typedefs to our external include/
directory.

mutex: define empty destructor

I don't think we really need the destructor. It causes undefined
reference compilation errors though:

  ... undefined reference to `std::mutex::~mutex()'

condition_variable: move header

Move from "conditionvariable.h" to "include/condition_variable". This
allows the normal C++11 #include syntax of:

  #include <condition_variable>

add two test cases

forgot to add two files...
bug fixes...

commit untested condvar code

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

move other interface headers to include/

We want all external interface headers (i.e., any #include'd in user
programs) to be in the include/ directory.

compiles with condition variables file added...
still need model checker support

mutex: move mutex.h to standard name/location

The important exported interfaces should be in the include/ dir. Also,
C++11 programs should use this header as:

    #include <mutex>

include/: add small header comments

impatomic: add multiple-inclusion guards

action: improve printing

The 'value' field of a ModelAction might actually represent a signed
number, a pointer, or something else entirely, so values look very huge
and uninformative when printed, especially in decimal. Hexadecimal
representation makes everything a little more readable, I think.

While I'm at it, I adjust the spacing a little and make VALUE_NONE into
a different magic number which is more recognizable in hex.

Makefile: add benchmarks to top-level

segfault file/line breakpoint info

This can give easy info for using gdb. e.g.:

    For debugging, place breakpoint at: snapshot.cc:92

Merge remote-tracking branch 'origin/master'

impatomic: add strong/weak compare_exchange

According to n2748.html, there was a change to allow spurious failure of
compare_exchange operations. Thus, there is no longer a
compare_exchange() operation, but rather a pair of
compare_exchange_{strong,weak)(). I resolve this for compilation
purposes now by editing the impatomic header (mostly with Vim macros for
patterned copy-paste-substitute) and adding an _ATOMIC_CMPSWP_WEAK_
macro, which is just an alias for _ATOMIC_CMPSWP_. Thus, we don't
simulate spurious failure yet.

See:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2748.html

make scheduler choose fair schedules when threads with priority are sleeping...

action: add NULL dereference assertion

In user programs, we might find a NULL atomic object being dereferenced,
causing strange model-checker behavior which will track memory address 0
as an atomic object. This may result in apparently-uninitialized
variables, for instance.

So, just nip these in the bud with an assertion. Perhaps these things
can transformed into some more informative type of warning in the
future, where user-visible bugs might print helpful messages.

threads: correct 'thrd_yield()'

The C11 thrd_yield() interface should return void. Also, it doesn't need
to do anything in our model-checker for now. I'm leaving its
implementation commented out for now, in case we find it helps for
fairness, for instance. Note that I made its location parameter non-NULL
now, too, so that we can identify the Thread, if we ever use it.

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

make linux_rw locks work again

Merge remote-tracking branch 'origin/master'

impatomic: rename all 'swap' to 'exchange'

n2427.html seems to have some very old definitions. I think this all
should be 'exchange', not 'swap'.

Note that there are other issues where we don't have the correct
function names available. But this fixes some of the problems.

fix some of the bugs related to barrier example...

include: add multiple-inclusion guards

.gitignore: ignore 'benchmarks' folder

Now, you can clone the benchmarks repository under the name 'benchmarks'
and have it compile-ready (but ignored by this repository) with:

  git clone <URI/model-checker-benchmarks.git> benchmarks
  cd benchmarks
  make

Future updates can be pulled in via a 'git pull' from that directory:

  cd benchmarks
  git pull

tests: use <stdatomic.h>

While I'm at it, rearrange the header listings.

move libthreads.h -> include/threads.h

Helps user programs to be able to just use C11 <threads.h>

rename threads.h -> threads-model.h

There's a name conflict with the C11 <threads.h>
We might as well just avoid the conflict entirely

include: add <atomic> header

did a little more looking at infeasible executions...
another obvious property we missed...kills about 1/3 of the infeasible executions...

model: JOIN/LOCK unification

Make join and lock actions use similar code paths.

This used to trigger a bug, due to the lack of a private snapshotting
heap.

datarace: reformat datarace printing

threads: allocate on user's snapshotting heap

The following comment is included in threads.h to explain this choice:

  Intentionally NOT allocated with MODELALLOC or SNAPSHOTALLOC. Threads
  should be allocated on the user's normal (snapshotting) heap to allow
  their allocation/deallocation to follow the same pattern as the rest
  of the backtracked/replayed program.

This fix solves problems seen in certain test programs regarding a
Thread being allocated in different locations for different executions.

schedule: bugfix - fix typo in wake

The Thread should be re-enabled, not disabled, when waking up.

user_main: pass remaining arguments to the user program

main: rename 'real_main()' to 'model_main()'

mistake

be much more careful about sending values backwards...

also implement hashing for traces...just an easy way to confirm whether we lose new traces...

be even more aggressive about sleep sets...
if an action was sleeping, it should only read from a value that could potentially result in synchronization with a release done while it was sleeping

mymemory: re-indent

model: stack-allocated vector should use ModelAlloc

utilize SnapshotAlloc STL allocator

mymemory: add SnapshotAlloc STL allocator

Now, we just need to go through the tedious process of rewriting all our
STL definitions

mymemory: implement snapshot_*() allocations on model-checker's heap

mymemory: add basic model_snapshot_space

I will begin to utilize the 'model_snapshot_space' as the
model-checker's private snapshotting heap.

rename again (snapshot_space -> user_snapshot_space)

I will be adding a separate model_snapshot_space

mymemory: kill system_malloc()

Not needed

snapshot: use snapshot_space only in mprotect-based

We don't need this heap for fork-based snapshotting, so clearly separate
the functionality here.

This also makes PageAlignedAdressUpdate() available only for
mprotect-based snapshotting.

snapshot: don't need any snapshotting space for fork-based

I have no idea why this was here in the first place. Somebody didn't
know what they were doing...

rename 'mySpace' to 'snapshot_space'

mymemory: make DontFree() static

mymemory: reformat spacing

mymemory: kill system_free()

This function is not used

snapshot: remove global 'basemySpace'

Why was this here?

test: linuxrwlocks: fixup spacing

model: remove todo

merge massive speedup with release sequence support...

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

Conflicts:
schedule.cc
schedule.h

add support for sleep sets...

test: add "double release sequence" test

This test uses two separate load-acquire's to establish the same release
sequence. This can cause problems with the current release sequence
fixups, so that we find an execution where one synchronizes and the
other doesn't, even when reading from the same sequence.

Merge branch 'norris'

model: add todo synchronization comment

model: be sure trace is "final feasible" before continuing to fixup

Release sequences fixup can break pretty badly if there are outstanding
promises. Solution: check for final-feasible traces before continuing to
fixup.

tests: add some normal loads/stores to test data races

These tests had become less useful, since the model-checker would ignore
release sequence fixup in the absence of pending data races. So add some
normal loads and stores to our tests, inducing some data races and some
proper synchronization.

model: check data races during release sequence fixup

This solves two problems:

1. I wasn't even checking for resolved data races after fixing up
   release sequence(s)

2. Launching of release sequence fixups now requires that there be
   pending data races

model: add release sequence model_thread ASSERT()

This ASSERT() should ensure that model-checker threads are always
'future_ordered'.

model: launch release sequence fixup actions when necessary

This should complete the "release sequence fixup" step. The ModelChecker
will launch new fixup actions, associating them with the special
'model_thread'.

model: add special model-checker Thread to ModelChecker

Note the change in take_step(), so that we base the "current thread" off
of the provided ModelAction, rather than thread_current() (i.e., the
Scheduler). This is because the Scheduler will never run the
model-checker thread.

schedule: do not allow model-checker thread to enter scheduler

threads: add constructor for model-checker thread

This thread will never have its own stack, and it should never be
inserted into the Scheduler.

threads: add flag for a special type of "model-checker thread"

Special model-checker thread(s) might be needed when producing special
model-checker ModelActions.

action: add Thread parameter to constructor

We will need to create ModelActions that are forced to associate with a
specific Thread (contrary to the Scheduler's knowledge), so add a
constructor parameter.

model: add process_relseq_fixup()

This performs the bulk of the release sequence finalization step.

common: improve backtrace function

Utilize freely-available backtrace function that helps make output more
readable. Previous implementation is kept for now, as it is simpler and
more well-tested.

add stacktrace header, under WTFPL

Download:
http://idlebox.net/2008/0901-stacktrace-demangled/stacktrace.h

WTFPL:
http://sam.zoy.org/wtfpl/

model: wire up rest of release seq. resolution backtracking

I still need to actually initiate the special ModelAction fixups.

nodestack: add release sequence breakage backtracking

End-of-execution resolution of release sequences requires a search
procedure in which we test various attempts at breaking our pending
release sequences. This provides the NodeStack infrastructure.

action: add MODEL_FIXUP_RELSEQ action_type

This type will be used as a special model-checker action for fixing up
release sequences. Each action corresponds to "finalizing" one release
sequence: either force a particular write to break the sequence or else
allow the synchronization to occur.

Currently, this action_type won't do anything, as it's not hooked up in
ModelChecker.

model: disabled threads are "future ordered"

If a Thread is not currently enabled, then it will synchronize with
another (currently-enabled) Thread if/when it wakes up. Thus, it
qualifies as "future ordered" within the release sequence code: it
cannot contribute future writes that will break current pending release
sequences.

model: use proper size_t printf format

schedule: add is_enabled() function

The release sequence functionality needs to check whether a Thread is
currently enabled (rather than finding this information in a particular
Node).

Also, rename the (private) 'is_enabled' field to avoid a name conflict.

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

create enumeration for enabled information...switch from bools to the enumeration