The Lock-Free Library
 =====================


1. Building
-----------
Edit the Makefile and set ARCH to the appropriate value.
Type 'make'.


2. What you get
---------------
'stm_fraser.c' is an object-based STM with the programming API defined
in 'stm.h'. 'mcas.c' is an implementation of multi-word
compare-and-swap.

These are used to build a number of search structures: skip lists,
binary search trees, and red-black trees. The executables are named as
follows:

 bst_lock_fraser      --- BST implementation using per-node locks.
                          No locking for read operations.
 bst_lock_kung        --- BST implementation using per-node locks.
                          No locking for read operations.
 bst_lock_manber      --- BST implementation using per-node locks.
                          No locking for read operations.
 bst_mcas             --- BST implementation based on MCAS.

 rb_lock_concurrentwriters --- Red-black trees with concurrent writers.
                               Based on MCS multi-reader locks.
 rb_lock_serialisedwriters --- Red-black trees with serialised writers.
                               Based on MCS multi-reader locks.
 rb_lock_mutex        --- Red-black trees with concurrent writers, and
                          no locking for read operations. Very fast!
 rb_stm_fraser        --- Red-black trees using Fraser's STM.
 rb_stm_herlihy       --- Red-black trees using Herlihy et al's STM.
 rb_stm_lock          --- Red-black trees using 2-phase-locking STM.

 skip_lock_perlist    --- Skip lists with a single global lock.
                          No locking for read operations.
 skip_lock_pernode    --- Skip lists with a lock per node.
                          No locking for read operations.
 skip_lock_perpointer --- Skip lists with a lock per pointer.
                          No locking for read operations.
 skip_cas             --- Skip lists built directly from CAS.
 skip_mcas            --- Skip lists based on MCAS.
 skip_stm_fraser      --- Skip lists using Fraser's STM.
 skip_stm_herlihy     --- Skip lists using Herlihy et al's STM.
 skip_stm_lock        --- Skip lists using 2-phase-locking STM.

Each executable is run as:
 <executable> <num_threads> <read_proportion> <key power>

'executable' is one of the above implementations.

'num_threads' indicates the degree of parallelism.

'read_proportion' determines what proportion of the random workload is
lookups as opposed to updates or removals. The proportion is out of 256.

'key_power' indicates the key range. Key range is 2 ^ 'key_power'.
Since updates and removals are equally probable, the mean set size
will be 2 ^ ('key power' - 1).


3. Verifying correctness
------------------------
To check that each implementation correctly behaves as a 'set' ought
to, you can define DO_WRITE_LOG in 'set_harness.c'. This will cause
each implementation to produce a log describing each operation that
was executed, and its result.

This can be run through 'replay' which will serach for a linearisable
schedule.


4. Distribution license
-----------------------
The license is GPL. See the file COPYING for details.


 -- Keir Fraser, 25th September 2003


****

This software has been released by its original author, Keir Fraser,
with permission from his advisors, under a BSD license.  For details,
please see README.LICENSE.

 -- Matt Benjamin, 07/24/2009