ms-queue: fixup initialization and free lists

There are a few things we fix:

1) We shouldn't initialize node[0].next, since node[0] is the 'NULL'
pointer and should never be accessed.

2) The per-thread free list is too restrictive. Now, we generate a list
of free nodes for each thread that can contain up to 4 node indexes.
We only initialize this list with 2 nodes each (so each thread can
expand its free list, if needed). There is some minimal assertion
framework and race detection performed on these lists, just in case.

3) We only initialize those nodes that are placed in the free list.
Accesses to other nodes' 'next' pointer should trigger an uninitialized
loads assertion.

ms-queue: don't initialize node 0

Node zero *should* be unused, since "0" is the NULL pointer index.
Removing this init will help catch bugs.

ms-queue: we should never dequeue 0

The test driver is written so that we should never dequeue 0.

ms-queue: revert Brian D. changes

On second (or third or fourth) thought, these changes were ill-advised.
We will make a different set of tweaks shortly.

This reverts commits 647601d3f341bb2a2a79534b3d044c039695839d and
fad3891f3158a4285984bb60415c1e4ebc2b767b.

wow...  i think this version is correct...

my changes

ms-queue: relax the second load of head/tail

ms-queue: strip down test driver

+ a few assertions

ms-queue: relax the queue loads/stores/CAS

Makefile: build ms-queue

deque: re-insert deleted MODEL_ASSERT()

deque: #include's

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

ms-queue: begin relaxing

Not functioning yet.

do merge...push right code
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker-benchmarks

Conflicts:
chase-lev-deque/main.c

ms-queue: add initialization

deque: fix bugs in assertion code and move up 3 variables...

deque: add MODEL_ASSERT(), fixup #include's

deque: wrong bug fix before...now the correct one

deque: bug fix...method could return empty

deque: add test driver, add print messages for now for resize method and if we pull the wrong values

test case exposes model checker bugs :(

fix bug

ms-queue: relax the initializations

add make file, header, and extra code to deque

ms-queue: fixups, add simple race detection

ms-queue: bugfix - get_ptr() and get_count() were switched

I ported the implementation wrong, so that we were extracting bits from
the wrong field.

ms-queue: cleanups

ms-queue: remove more externs and unintended shared data

ms-queue: more cleanup

ms-queue: cleanups, convert to C11 atomics

This converts the "pointer" to a 64-bit type (unsigned long long, or
'pointer') divided into two 32-bit halves (ptr and count), instead of
using a union of a struct and an 'unsigned long'.

All atomics are seq_cst for now. Once the code all looks a little
better, I'll relax these to reasonable memory orderings.

mcs-queue -> ms-queue

This queue is by Michael and Scott; hence, "M&S".

mcs-queue: a few changes

mcs-queue: add Makefile

mcs-queue: modifications for compiling

Remove backoff, shmem, fork, etc.

Moving closer to something that can compile.

msc-queue: indentation, etc.

mcs-queue: initial checkin

The "new" queue (i.e., "MCS Queue") code directly from:

  ftp://ftp.cs.rochester.edu/pub/packages/sched_conscious_synch/concurrent_queues/concurrent_queues.tar.gz

Except for the MIPS assembly implementation files and Makefile.

From README:

The compressed tar file in this directory conatins the C code for
the algorithms implemented for the paper

%A Maged M. Michael
%A Michael L. Scott
%T Simple, Fast, and Practical Non-Blocking and Blocking
Concurrent Queue Algorithms
%J PROC of the Fifteenth PODC
%C Philadelphia, PA
%D May 1996
%X 23-26 May 1996
%K tr600
%O Earlier version available as
TR 600,
URCSD,
December 1995

deque: use atomic_uintptr_t

'Atomic(Array *)' seems to be a pseudocode type. Just use
atomic_uintptr_t and allow the warnings for now (we could alternatively
use a cast every time).

deque: improve compile-ability

Add appropriate C headers.
Re-introduce atomic_* and memory_order_* prefixes.

deque: add "proven correct" work-stealing Chase-Lev deque

From the PPoPP 2013 paper "Correct and efficient work-stealing for weak
memory models"

By:

  Nhat Minh Lê
  Antoniu Pop
  Albert Cohen
  Francesco Zappa Nardelli

Citation URL:

  http://dl.acm.org/citation.cfm?id=2442524

bench.sh: add dekker-fences to benchmark runs

bench.sh: log more information

We want the whole timing information and git-log info in our log files.

bench.sh: don't run tests twice

Now that we don't print so much garbage by default, we don't need to run
our tests twice (once with log and once without).

bench.sh: don't 'grep' output

Model-checker output is concise now, so don't trim it.

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.