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

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.

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