run.sh: sync up run script with model-checker

I improved the model-checker.git run script, so paste over the changes.

Makefile: build dekker-fences automatically

dekker-fences: add Dekker's critical section algorithm

Now that we support fences, add a test benchmark that uses fences. This
one just uses seq-cst fences.

Downloaded from:

   http://www.justsoftwaresolutions.co.uk/threading/

Modified to avoid static construction. i.e., change:
  std::atomic<int> turn(0);
to
  std::atomic<int> turn;
  ...
  turn = 0;
And added user_main() method to launch the two threads.

bench.sh: add spsc-bugfix to benchmark runs

Makefile: build spsc-bugfix by default

spsc-bugfix: fix deadlocked signalling bug

spsc-bugfree: make Relacy run exhaustive, fair scheduler

spsc-bugfix: duplicate the (buggy) spsc-queue

Preparing to fix the deadlock bug.

unrelacy: instrument relacy-marked normal loads/stores

bench: reconfigure default tests

Now, run the "-noinit" tests for mpmc-queue (2R2W and 1R2W). Also,
switch to using '-f 10 -m 2 -e 1' model-checking parameters.

mpmc-queue: .gitignore

mpmc-queue: add "-noinit" builds

Build matching test cases where there is no initial element in the
queue.

mpmc-queue: makefile bugfix

mpmc-queue: remove duplicate source files

mpmc-queue: unify source file again

I really didn't want 3 copies of the same source file just to get around
some model-checker snapshotting limitations in argument parsing... So
now, it's a compile-time option to configure the number of reader/writer
threads.

mpmc-queue: fix make clean

spsc-queue: add spsc-relacy build

Now we can test a version of spsc-queue using Relacy. There were some
small modifications necessary, so I duplicated the source code, renamed
with "-relacy" in the name.

To use it, you need to do something like the following, from the
spsc-queue directory:

  make RELACYPATH=/path-to-relacy
  ./spsc-relacy

unrelacy: include <mutex> and <condition_variable>

Relacy expects to have these headers even if they aren't included by the
program.

spsc-queue: fix some old Relacy syntax (RL_NEW/RL_DELETE)

Relacy 2.4 doesn't even have RL_NEW and RL_DELETE, so we shouldn't use
it even if we're trying to be Relacy-compatible.

unrelacy: use new MODEL_ASSERT() macro

bench: allow log directory to be placed elsewhere

Now, you can run:

  ./bench.sh <dir>

e.g.,

  ./bench.sh /tmp

Will create a directory /tmp/run-<date-time> for the logs.

bench: send timings to stdout, not stderr

bench: add linuxrwlocks to benchmark runs

linuxrwlocks: add linux locks test

unrelacy: define the relacy ASSERT macros, fixup rl::var

bench.sh: change max-reads=2, log to directory

Pass '-m 2' argument to the model-checker

bench.sh sends all logs to a date-named directory now

bench.sh: add test script for running benchmarks

mpmc-queue: expand to 2R2W, 2R1W, 1R2W tests

I rewrote the test to allow a configurable number of readers and
writers, but then I figured out that our model-checker doesn't support
optarg() and its global optind properly, when using mmap()/mprotect()
snapshotting (it doesn't add the optarg library to be snapshotted...)

So, this test grows to 3 separate source files, at least for now. The
only change is the number of reader and writer threads.

barrier: modify to allow more than one reader

Just change the NUMREADERS macro to add more reader-threads.

Having 3 or more threads is a more interesting example, since there's
no contention if you just have one thread spin, waiting for the other.

mpmc-queue: run more producer/consumer threads

mcs-lock: add more locking tests to driver

mpmc-queue: improve driver, to read all items from queue

threadB() will now read all currently available items from the queue.

benchmarks.mk: -rdynamic is used for linking

spsc-queue: don't statically construct the queue

Our model-checker doesn't support constructors which perform
model-checking actions (e.g, atomic initialization) at load time (e.g.,
in a static execution of the constructor), since this happens before the
model-check object is created. Maybe we'll fix that in the future, but
for now, don't construct the queue at load time.

spsc-queue: compilable

benchmarks.mk: don't include base model-checker dir

All model-checker headers needed for user-program compilation should be
in $(BASE)/include now, not in $(BASE)/

spsc-queue: add Makefile, .gitignore

williams-queue: fixup header

Move the constructor lower, so that member definitions appear earlier
than it in the class definition.

Also, don't assign to members of the atomic structure directly; use a
temporary struct then assign the whole struct.

Still won't compile. Seeing linker errors, probably due to the fact that
this code uses a nonstandrad atomic template:
    std::atomic<counted_node_ptr>

Where counted_node_ptr is a struct with int and pointer members. Thus,
it has size of at least 96 bytes (32+64) and so probably isn't really
supported by atomics... I'm not sure where the author came up with this.

    $ g++ williams-queue.cc --std=c++0x
    /tmp/ccPQgiJC.o: In function `lock_free_queue<int>::lock_free_queue()': williams-queue.cc:(.text._ZN15lock_free_queueIiEC2Ev[_ZN15lock_free_queueIiEC5Ev]+0x92): undefined reference to `std::atomic<lock_free_queue<int>::counted_node_ptr>::load(std::memory_order) const'
    ...
    collect2: ld returned 1 exit status

williams-queue: add driver, Makefile, etc.

Still doesn't quite compile. I'm mostly attempting compilation with a
C++0x compiler (G++ 4.6) for now, a la:

  g++ -o williams-queue williams-queue.cc --std=c++0x

williams-queue: trim excess implementation

Trim down to a single implementation. Still doesn't compile correctly.

williams-queue: add lock-free-queue

Lock-free queue code from "C++ Concurrency in Action: Practical
Multithreading", by Anthony Williams

Code taken from:
  http://www.manning.com/williams/CCiA_SourceCode.zip
  http://www.manning.com/williams/

Note that this commit includes several implementation of pieces of the
queue. I will trim them down to a working class in the next step.

spsc-queue: use std::condition_variable

Model-checker doesn't support <condition_variable> header yet.

mcs-lock: driver bugfix (deadlocking)

I didn't notice that the guard automatically locks/unlocks the mutex on
creation/destruction, respectively.

spsc-queue: fixup atomics, mutexes, threads

spsc-queue: unrelacy

unrelacy: fixup header

spsc-queue: add new benchmark

From:
https://groups.google.com/forum/?fromgroups=#!msg/comp.programming.threads/nSSFT9vKEe0/7eD3ioDg6nEJ

mpmc-queue: driver fixes

* Initialize queue with at least one item

* Instrument some racy accesses in driver

* Print a little information to see what kind of loops we're stuck in

mpmc-queue: add top-level Makefile

fixup makefiles

benchmarks: revert back to strong/weak compare-exchange

I fixed up the model-checker header, so these will compile.

mpmc-queue: add test driver, Makefile, .gitignore

mpmc-queue: fixup compilation

* Remove "nonatomic" type template
* Don't use atomic<T>(T) constructor
* Don't use compare_exchange_weak()

mpmc-queue: unrelacy

mpmc-queue: add MPMC queue header

From first example at:
http://cbloomrants.blogspot.com/2011/07/07-30-11-look-at-some-bounded-queues.html

mcs-lock: write proper driver

mcs-lock: bugfix - didn't allocate mcs_mutex

This is a bug in the stupid driver I wrote (i.e., my fault). I was
struggling with the syntax, so I forgot to even initialize my objects.

add run.sh simple run script

.gitignore

mcs-lock: add trivial driver, link with build system

This benchmark doesn't do much yet.

mcs-lock: fixup Relacy code

Also, switch out 'compare_exchange_strong()' for 'compare_exchange()',
since we don't support the _strong syntax right now.

unrelacy: add some helpers for cleaning up relacy code

Relacy still uses a few things that I can't easily add, like a ()
operator for std::atomic<T>. We'll still have to replace some things by
hand in test cases written for Relacy.

mcs_lock: add mcs mutex

From:
http://cbloomrants.blogspot.com/2011/07/07-18-11-mcs-list-based-lock_18.html

add top-level Makefile

barrier: add .gitignore

barrier: add test driver, Makefile

My own additions to test barrier.h

benchmarks.mk: fixup linker flag

barrier: fixup atomic initialization

barrier: add hand-written barrier implementation

Grabbed from:
http://stackoverflow.com/questions/8115267/writing-a-spinning-thread-barrier-using-c11-atomics

common benchmarks makefile definitions

add "lock-free queue"

From:
http://www.codeproject.com/Articles/153898/Yet-another-implementation-of-a-lock-free-circular

License:
http://opensource.org/licenses/bsd-license.php

.gitignore