cds/readme at master · avis/cds · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
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)