****************************************
-CDSChecker Readme
+ CDSChecker Readme
****************************************
+Copyright (c) 2013 Regents of the University of California. All rights reserved.
+
CDSChecker is distributed under the GPL v2.
+This README is divided into sections as follows:
+
+ I. Overview
+ II. Reading an execution trace
+ A. References
+
+----------------------------------------
+ I. Overview
+----------------------------------------
+
CDSChecker compiles as a dynamically-linked shared library by simply running
'make'. It should compile on Linux and Mac OSX, and has been tested with LLVM
(clang/clang++) and GCC.
$ export LD_LIBRARY_PATH=.
$ ./test/userprog.o # Runs simple test program
$ ./test/userprog.o -h # Prints help information
-Usage: <program name> [MC_OPTIONS] -- [PROGRAM ARGUMENTS]
-
-Options:
--h Display this help message and exit
--m Maximum times a thread can read from the same write
- while other writes exist. Default: 0
--M Maximum number of future values that can be sent to
- the same read. Default: 0
--s Maximum actions that the model checker will wait for
- a write from the future past the expected number of
- actions. Default: 100
--S Future value expiration sloppiness. Default: 10
--f Specify a fairness window in which actions that are
- enabled sufficiently many times should receive
- priority for execution. Default: 0
--e Enabled count. Default: 1
--b Upper length bound. Default: 0
--v Print verbose execution information.
--y CHESS like yield based fairness. Default: 0
--- Program arguments follow.
+Copyright (c) 2013 Regents of the University of California. All rights reserved.
+Distributed under the GPLv2
+Written by Brian Norris and Brian Demsky
+
+Usage: ./test/userprog.o [MODEL-CHECKER OPTIONS] -- [PROGRAM ARGS]
+
+MODEL-CHECKER OPTIONS can be any of the model-checker options listed below. Arguments
+provided after the `--' (the PROGRAM ARGS) are passed to the user program.
+
+Model-checker options:
+-h, --help Display this help message and exit
+-m, --liveness=NUM Maximum times a thread can read from the same write
+ while other writes exist.
+ Default: 0
+-M, --maxfv=NUM Maximum number of future values that can be sent to
+ the same read.
+ Default: 0
+-s, --maxfvdelay=NUM Maximum actions that the model checker will wait for
+ a write from the future past the expected number
+ of actions.
+ Default: 6
+-S, --fvslop=NUM Future value expiration sloppiness.
+ Default: 4
+-y, --yield Enable CHESS-like yield-based fairness support.
+ Default: disabled
+-Y, --yieldblock Prohibit an execution from running a yield.
+ Default: disabled
+-f, --fairness=WINDOW Specify a fairness window in which actions that are
+ enabled sufficiently many times should receive
+ priority for execution (not recommended).
+ Default: 0
+-e, --enabled=COUNT Enabled count.
+ Default: 1
+-b, --bound=MAX Upper length bound.
+ Default: 0
+-v, --verbose Print verbose execution information.
+-u, --uninitialized=VALUE Return VALUE any load which may read from an
+ uninitialized atomic.
+ Default: 0
+-t, --analysis=NAME Use Analysis Plugin.
+-o, --options=NAME Option for previous analysis plugin.
+ -o help for a list of options
+ -- Program arguments follow.
Note that we also provide a series of benchmarks (distributed separately),
cd benchmarks
make
- ./run.sh barrier/barrier -f 10 -m 2 # runs barrier test with fairness/memory liveness
- ./bench.sh <dir> # run all benchmarks twice, with timing results; all logged to <dir>
+ ./run.sh barrier/barrier -y -m 2 # runs barrier test with fairness/memory liveness
+ ./bench.sh # run all benchmarks twice, with timing results
+
+
+----------------------------------------
+ II. Reading an execution trace
+----------------------------------------
+
+When CDSChecker detects a bug in your program (or when run with the --verbose
+flag), it prints the output of the program run (STDOUT) along with some summary
+trace information. The trace is given as a sequence of lines, where each line
+represents an operation in the execution trace. These lines are ordered by the
+order in which they were run by CDSChecker (i.e., the "execution order"), which
+does not necessarily align with the "order" of the values observed (i.e., the
+modification order and the reads-from relation).
+
+Columns:
+
+ o #: The sequence number within the execution. That is, sequence number "9"
+ means the operation was the 9th operation executed by CDSChecker. Note that
+ this represents the execution order, not necessarily any other order (e.g.,
+ modification order or reads-from).
+
+ o t: The thread number
+
+ o Action type: The type of operation performed
+
+ o MO: The memory-order for this operation (i.e., memory_order_XXX, where XXX is
+ relaxed, release, acquire, rel_acq, or seq_cst)
+
+ o Location: The memory location on which this operation is operating. This is
+ well-defined for atomic write/read/RMW, but other operations are subject to
+ CDSChecker implementation details.
+
+ o Value: For reads/writes/RMW, the value returned by the operation. Note that
+ for RMW, this is the value that is *read*, not the value that was *written*.
+ For other operations, 'value' may have some CDSChecker-internal meaning.
+
+ o Rf: For reads, the sequence number of the operation from which it reads.
+ [Note: If the execution is a partial, infeasible trace (labeled INFEASIBLE),
+ as printed during --verbose execution, reads may not be resolved and so may
+ have Rf=? or Rf=Px, where x is a promised future value.]
+
+ o CV: The clock vector, encapsulating the happens-before relation (see our
+ paper, or the C/C++ memory model itself). We use a Lamport-style clock vector
+ similar to [1]. The "clock" is just the sequence number (#). The clock vector
+ can be read as follows:
+
+ Each entry is indexed as CV[i], where
+
+ i = 0, 1, 2, ..., <number of threads>
+
+ So for any thread i, we say CV[i] is the sequence number of the most recent
+ operation in thread i such that operation i happens-before this operation.
+ Notably, thread 0 is reserved as a dummy thread for certain CDSChecker
+ operations.
+
+See the following example trace:
+
+------------------------------------------------------------------------------------
+# t Action type MO Location Value Rf CV
+------------------------------------------------------------------------------------
+1 1 thread start seq_cst 0x7f68ff11e7c0 0xdeadbeef ( 0, 1)
+2 1 init atomic relaxed 0x601068 0 ( 0, 2)
+3 1 init atomic relaxed 0x60106c 0 ( 0, 3)
+4 1 thread create seq_cst 0x7f68fe51c710 0x7f68fe51c6e0 ( 0, 4)
+5 2 thread start seq_cst 0x7f68ff11ebc0 0xdeadbeef ( 0, 4, 5)
+6 2 atomic read relaxed 0x60106c 0 3 ( 0, 4, 6)
+7 1 thread create seq_cst 0x7f68fe51c720 0x7f68fe51c6e0 ( 0, 7)
+8 3 thread start seq_cst 0x7f68ff11efc0 0xdeadbeef ( 0, 7, 0, 8)
+9 2 atomic write relaxed 0x601068 0 ( 0, 4, 9)
+10 3 atomic read relaxed 0x601068 0 2 ( 0, 7, 0, 10)
+11 2 thread finish seq_cst 0x7f68ff11ebc0 0xdeadbeef ( 0, 4, 11)
+12 3 atomic write relaxed 0x60106c 0x2a ( 0, 7, 0, 12)
+13 1 thread join seq_cst 0x7f68ff11ebc0 0x2 ( 0, 13, 11)
+14 3 thread finish seq_cst 0x7f68ff11efc0 0xdeadbeef ( 0, 7, 0, 14)
+15 1 thread join seq_cst 0x7f68ff11efc0 0x3 ( 0, 15, 11, 14)
+16 1 thread finish seq_cst 0x7f68ff11e7c0 0xdeadbeef ( 0, 16, 11, 14)
+HASH 4073708854
+------------------------------------------------------------------------------------
+
+Now consider, for example, operation 10:
+
+This is the 10th operation in the execution order. It is an atomic read-relaxed
+operation performed by thread 3 at memory address 0x601068. It reads the value
+"0", which was written by the 2nd operation in the execution order. Its clock
+vector consists of the following values:
+
+ CV[0] = 0, CV[1] = 7, CV[2] = 0, CV[3] = 10
+
+
+----------------------------------------
+ A. References
+----------------------------------------
+
+[1] L. Lamport. Time, clocks, and the ordering of events in a distributed
+ system. CACM, 21(7):558–565, July 1978.