praveenmunagapati / cds Goto Github PK

CDS (Concurrent Data Structures) C++ library

CDS library is (mostly) header-only template library. The shared library contains only garbage collector's core implementation.
CDS contains implementation of some well-known lock-free and fine-grained data structures:

Stack:
    TreiberStack
        [1986] R. K. Treiber. Systems programming: Coping with parallelism. Technical Report RJ 5118, IBM Almaden Research Center, April 1986.
        
Queue:
    BasketQueue
        [2007] Moshe Hoffman, Ori Shalev, Nir Shavit "The Baskets Queue"
    MSQueue
        [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
        [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-free objects using atomic reads and writes"
        [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
    RWQueue
        [1998] Maged Michael, Michael Scott "Simple, fast, and practical non-blocking and blocking concurrent queue algorithms"
    MoirQueue
        [2000] Simon Doherty, Lindsay Groves, Victor Luchangco, Mark Moir "Formal Verification of a practical lock-free queue algorithm"
    OptimisticQueue
        [2008] Edya Ladan-Mozes, Nir Shavit "An Optimistic Approach to Lock-Free FIFO Queues"
    TsigasCycleQueue
        [2000] Philippas Tsigas, Yi Zhang "A Simple, Fast and Scalable Non-Blocking Concurrent FIFO Queue for Shared Memory Multiprocessor Systems"
    VyukovMPMCCycleQueue
        Dmitry Vyukov (see http://www.1024cores.net)

Deque:
    MichaelDeque
        [2003] Maged Michael "CAS-based Lock-free Algorithm for Shared Deque"

Map, set:
    MichaelHashMap
        [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"
    SplitOrderedList
        [2003] Ori Shalev, Nir Shavit "Split-Ordered Lists - Lock-free Resizable Hash Tables"
    StripedMap, StripedSet
        [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
    CuckooMap, CuckooSet
        [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
    SkipListMap, SkipListSet
        [2008] Maurice Herlihy, Nir Shavit "The Art of Multiprocessor Programming"
        
Ordered single-linked list (buckets for the map):
    LazyList
        [2005] Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer III, and Nir Shavit "A Lazy Concurrent List-Based Set Algorithm"
    MichaelList
        [2002] Maged Michael "High performance dynamic lock-free hash tables and list-based sets"

Garbage collection:
    Hazard Pointers
        [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
        [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
        [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
    Hazard pointers with reference counting
        [2006] A.Gidenstam "Algorithms for synchronization and consistency in concurrent system services", Chapter 5 "Lock-Free Memory Reclamation" Thesis for the degree of Doctor	of Philosophy 
        [2005] Anders Gidenstam, Marina Papatriantafilou and Philippas Tsigas "Allocating memory in a lock-free manner", Proceedings of the 13th Annual European Symposium on Algorithms (ESA 2005), Lecture Notes in Computer Science Vol. 3669, pages 229 – 242, Springer-Verlag, 2005
    Pass-the-Buck
        [2002] M. Herlihy, V. Luchangco, and M. Moir. The repeat offender problem: A mechanism for supporting
               dynamic-sized lockfree data structures. Technical Report TR-2002-112, Sun Microsystems Laboratories, 2002
        [2002] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Dynamic-sized Lockfree Data Structures. 
               Technical Report TR-2002-110, Sun Microsystems Laboratories, 2002
        [2005] M. Herlihy, V. Luchangco, P. Martin, and M. Moir. Nonblocking Memory Management Support
               for Dynamic_Sized Data Structures. ACM Transactions on Computer Systems, Vol.23, No.2, May 2005
    User-space RCU
        [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis,
               Chapter 6 "User-Level Implementations of Read-Copy Update"
        [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level
               Implementations of Read-Copy Update"

Memory allocation:
    [2004] M.Michael "Scalable Lock-free Dynamic Memory Allocation"
    
Supported platforms and compilers
---------------------------------

GCC: 4.3 and above
MS Visual C++: 9 (2008) and above
Clang: 3.0 and above

The library was tested on following server platforms:
GNU GCC 4.3.3:
    x86 RedHat Linux 4.0, 5.0
    amd64 (x86-64) RedHat Linux 4.0, 5.0
    ia64 (itanium) RedHat Linux 4.0
    ia64 (itanium) HP-UX 11.23 and HP-UX 11.31
    sparc (ultrasparc-IV and Niagara) Sun Solaris 2.10

    also tested by GCC 4.4+ on amd64 Ubuntu 10.10, amd64 FreeBSD 8.1

Microsoft Visual C++ 2008 :
    x86 Windows7
    amd64 (x86-64) Windows7
    
Clang:
    amd64 Linux Ubuntu 10.10

How to build
------------

The CDS library is depend on boost header-only libraries (tested with boost 1.39 and later). 
The regression tests in tests directory also depends on boost_thread dynamic library. 
You should build boost_thread library before building CDS test.

Windows
    Use Visual C++ 2008 solution projects\Win\vc9\cds.sln.
    The solution depends on BOOST_PATH environment variable that contains the path to boost root directory. 
    The CDS tests also depends on boost_thread library in %BOOST_PATH%\stage\lib or %BOOST_PATH%\bin.

Unix 
    GCC compiler supported (4.3 and above) and Clang 3.0 and above for Linux
    Use script build/build.sh that builds release and debug libcds.so and tests executable. Please,
    do not try to call 'make' directly, - build.sh script sets necessary vars for make.
    See examples in build/sample directory.

    build.sh main options:
    -x compiler     C++ compiler name (g++, gcc, clang; default g++)
    -p arch         Processor architecture. Possible values are:  x86, amd64, x86_64, sparc, ia64
    -o os_family    OS family. Possible values are: linux, sunos, solaris, hpux
    -b bits         Bits to build (32 or 64)
    -l options      Extra linker options
    -x options      Extra compiler options
    --with-boost path   Path to boost root
    --clean         Clean all before building

    For more options use build.sh -h

Warnings
    GCC: compile CDS library and all projects that depends on libcds with -fno-strict-aliasing flag!
    
Test suite
----------
    Note the duration of full test set is up to 12 hours (depending on your hardware and test configuration)