X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=README;h=93d97236d1bab68b17e021f16800a15a0fc18438;hb=5e2995c5fd6618092e98d47e2a47396b62942959;hp=4da5694315035603dec738bb682e1885b413274a;hpb=5f861ebe39567a3bf01635bb7343ed8a8e26803f;p=model-checker.git diff --git a/README b/README index 4da5694..93d9723 100644 --- a/README +++ b/README @@ -1,8 +1,20 @@ **************************************** -CDSChecker Readme + CDSChecker Readme **************************************** -This is an evaluation-only version of CDSChecker. Please do not distribute. +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 @@ -29,25 +41,49 @@ $ make $ export LD_LIBRARY_PATH=. $ ./test/userprog.o # Runs simple test program $ ./test/userprog.o -h # Prints help information -Usage: [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. --- 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), @@ -56,5 +92,100 @@ you can build and run the benchmarks as follows: cd benchmarks make - ./run.sh barrier/barrier -f 10 -m 2 # runs barrier test with fairness/memory liveness - ./bench.sh # run all benchmarks twice, with timing results; all logged to + ./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, ..., + + 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.