afsmonitor: avoid double free on exit
[openafs.git] / src / mcas / README
1  The Lock-Free Library
2  =====================
3
4
5 1. Building
6 -----------
7 Edit the Makefile and set ARCH to the appropriate value.
8 Type 'make'.
9
10
11 2. What you get
12 ---------------
13 'stm_fraser.c' is an object-based STM with the programming API defined
14 in 'stm.h'. 'mcas.c' is an implementation of multi-word
15 compare-and-swap.
16
17 These are used to build a number of search structures: skip lists,
18 binary search trees, and red-black trees. The executables are named as
19 follows:
20
21  bst_lock_fraser      --- BST implementation using per-node locks.
22                           No locking for read operations.
23  bst_lock_kung        --- BST implementation using per-node locks.
24                           No locking for read operations.
25  bst_lock_manber      --- BST implementation using per-node locks.
26                           No locking for read operations.
27  bst_mcas             --- BST implementation based on MCAS.
28
29  rb_lock_concurrentwriters --- Red-black trees with concurrent writers.
30                                Based on MCS multi-reader locks.
31  rb_lock_serialisedwriters --- Red-black trees with serialised writers.
32                                Based on MCS multi-reader locks.
33  rb_lock_mutex        --- Red-black trees with concurrent writers, and
34                           no locking for read operations. Very fast!
35  rb_stm_fraser        --- Red-black trees using Fraser's STM.
36  rb_stm_herlihy       --- Red-black trees using Herlihy et al's STM.
37  rb_stm_lock          --- Red-black trees using 2-phase-locking STM.
38
39  skip_lock_perlist    --- Skip lists with a single global lock.
40                           No locking for read operations.
41  skip_lock_pernode    --- Skip lists with a lock per node.
42                           No locking for read operations.
43  skip_lock_perpointer --- Skip lists with a lock per pointer.
44                           No locking for read operations.
45  skip_cas             --- Skip lists built directly from CAS.
46  skip_mcas            --- Skip lists based on MCAS.
47  skip_stm_fraser      --- Skip lists using Fraser's STM.
48  skip_stm_herlihy     --- Skip lists using Herlihy et al's STM.
49  skip_stm_lock        --- Skip lists using 2-phase-locking STM.
50
51 Each executable is run as:
52  <executable> <num_threads> <read_proportion> <key power>
53
54 'executable' is one of the above implementations.
55
56 'num_threads' indicates the degree of parallelism.
57
58 'read_proportion' determines what proportion of the random workload is
59 lookups as opposed to updates or removals. The proportion is out of 256.
60
61 'key_power' indicates the key range. Key range is 2 ^ 'key_power'.
62 Since updates and removals are equally probable, the mean set size
63 will be 2 ^ ('key power' - 1).
64
65
66 3. Verifying correctness
67 ------------------------
68 To check that each implementation correctly behaves as a 'set' ought
69 to, you can define DO_WRITE_LOG in 'set_harness.c'. This will cause
70 each implementation to produce a log describing each operation that
71 was executed, and its result.
72
73 This can be run through 'replay' which will serach for a linearisable
74 schedule.
75
76
77 4. Distribution license
78 -----------------------
79 The license is GPL. See the file COPYING for details.
80
81
82  -- Keir Fraser, 25th September 2003
83
84
85 ****
86
87 This software has been released by its original author, Keir Fraser,
88 with permission from his advisors, under a BSD license.  For details,
89 please see README.LICENSE.
90
91  -- Matt Benjamin, 07/24/2009