POPL2017 artifact for "Dynamic Race Detection For C++11"
========================================================


1. Introduction
2. ThreadSanitizer
3. Litmus tests
4. CDSChecker tests
5. Firefox
6. Chromium
7. Browser Experiments
8. Notes on running browser experiments


1. Introduction:

With this artifact, we provide the reviewers with the ability to compile
programs with either tsan03 (the version of tsan prior to our work) or tsan11
(the new practical contribution of our paper); we provide litmus tests ready to
be compiled with both tsan03 and tsan11; and we provide CDSChecker tests
pre-built with tsan03 and tsan11. (For technical reasons specific to the
CDSChecker tests we could not get them to compile in the VM, hence them being
pre-built; their source code is available for inspection, however).

The paper also presents experimental results for the Firefox and Chromium web
browsers. It was not possible within the time-frame to provide pre-compiled
versions these in the VM, and thus we do not expect this aspect of our work to
be reviewed. However, if the reviewers are curious and can commit the time, we
provide instructions on how to download the browser source code and build it
from source.

The VM we provide contains a pre-built tsan03, tsan11, CDSChecker tests
pre-built with tsan03 and tsan11 (with no way of recompiling them) and litmus
tests that can be compiled with either. The username, password and su password
to the machine is "popl2017".

2. ThreadSanitizer:

ThreadSanitizer (tsan) comes in two parts, both of which are a part of LLVM.
  - A runtime library (RTL) that instruments the code. This is in a subdirectory
    of LLVM (projects/compiler-rt/lib/tsan/rtl). This is built as a static
    library and linked to each executable at link time. It tracks properties of
    the program, such as happens-before and previous writes.
  - A pass that goes through the code and inserts call to the RTL. This happens
    at compile time. For example:

User code:                              Object code (simplified):

  std::atomic<int> flag(0);               push &flag
                                          push 0
                                          call __tsan_write_4
                                          push 0
                                          call __std_atomic_atomic

The instrumented code (i.e. the compiled source files with the calls to the RTL
added) has not been changed, thus, to switch between tsan03 and tsan11, only the
executable must be rebuilt, the source files do not need to be recompiled. Both
of these staged are performed by clang.

We provide a diff of tsan11, that can be applied to LLVM to give tsan11
(discussed in S7). An overview of how parts of the paper has been implemented in
tsan is as follows:

  - tsan_relaxed.{cc,h} (paper S4):
    Contains the store buffer, and the code which controls which stores loads
    can read from.
  - tsan_clock.cc (around :500 and after) (paper S3):
    Contains the VVC code and some extra VC code for fences and relaxed atomics.
  - tsan_rtl_mutex.cc:512-526 (S4.5):
    Contains the SC fence functionality.
  - tsan_interface_atomic.cc:224-560:
    Functions that the interceptors call into. These contain high level code on
    how to handle the functions.
  - tsan_rtl_mutex.cc:362-510:
    These are called by the high level functions above and control how the state
    of the RTL is updated.

We have included a build of both tsan03 and tsan11. The "active" build is the
one linked to from /data/cdl110/llvm/build. To activate them, do the following:

  - tsan03:
    rm /data/cdl110/llvm/build && \
    ln -s /data/cdl110/llvm-normal/build /data/cdl110/llvm/build
  - tsan11:
    rm /data/cdl110/llvm/build && \
    ln -s /data/cdl110/llvm/build272792 /data/cdl110/llvm/build

Using tsan now simply requires compiling and linking with
/data/cdl110/llvm/build/bin/clang++. Both tsan03 and tsan11 are already compiled,
if you want to change any part of them and need to recompile, do the following
(change the parameter to the -j flag to the number of processors - 1):

  - tsan03:
    cd /data/cdl110/llvm-normal/build && make -j7
  - tsan11:
    cd /data/cdl110/llvm/build272792 && make -j7


3. Litmus Tests:

There are about 60 small and highly specific C++ litmus tests found in
/data/cdl110/litmus_tests. These aim to to test specific parts of the memory
model. For example, rs_* tests exhibit interesting release sequences, while
rmw_* tests force tsan to use VVC. To compile:

  cd /data/cdl110/litmus_tests && make -j7

To see what the expected behaviour of each one is, refer to tsan_stats.txt in
the same directory. As the sceduling and choice of reads is entirely random,
races can take several runs to to appear. We recommend running about 20 times:

  for i in `seq 1 1 20` ; do ./test_name ; done

To write your own tests, simply make a new file in the same directory with
extension .cpp and run make.


4. CDSChecker tests:

The CDSChecker tests are found in /data/cdl110/cdschecker/ in a subfolder for
their name. Each test has a script that will run the test a thousand times,
reporting the race rate and average time. For example, to run dekker-fences:

  cd /data/cdl110/cdschecker/dekker-fences && ./test.sh ./dekker-fences

Not that some tests have multiple executables for different parameters, or will
call the executable "main" instead. Note that we could not figure out how to
move the build environment, thus they are biult but cannot be rebuilt. We also
cannot reproduce table 1 in the paper completely, as some tests give different
race results in the VM. To run all of the experiments as found in the paper, run
the following:

  for t in barrier chase-lev-deque dekker-fences linuxrwlocks mcs-lock mpmc-queue ms-queue spsc-queue ; do \
    pushd $t && ./test.sh ./$t && popd \
  done

Some of the tests have short sleep durations to help encourage different
schedulings, otherwise they do the same instruction interleaving on every run.
This short sleep duration has been excluded from the times.


5. Building tsan11:

Follow the instrucitons:

  mkdir /data/cdl110 && cd /data/cdl110
  svn checkout http://llvm.org/svn/llvm-project/llvm/trunk llvm
  cd /data/cdl110/llvm/tools
  svn checkout http://llvm.org/svn/llvm-project/cfe/trunk clang
  cd /data/cdl110/llvm/projects
  svn checkout --revision 272792 http://llvm.org/svn/llvm-project/compiler-rt/trunk compiler-rt
  svn checkout http://llvm.org/svn/llvm-project/libcxx/trunk libcxx
  svn checkout http://llvm.org/svn/llvm-project/libcxxabi/trunk libcxxabi
  cd /data/cdl110/llvm/projects/compiler-rt/lib/tsan
  wget http://multicore.doc.ic.ac.uk/tools/tsan11/POPL17/tsan11.diff
  svn patch tsan11.diff
  mkdir /data/cdl110/llvm/build272792 && cd /data/cdl110/llvm/build272792
  cmake -G "Unix Makefiles" -DCMAKE_BUILD_TYPE=Release ..
  make -j7
  ln -s /data/cdl110/llvm/build272792 /data/cdl110/llvm/build

You can now invoke clang and build with tsan11 by running:

  /data/cdl110/llvm/build/bin/clang++ -std=c++0x -pthread -Wall -fsanitize=thread -g <prog.cc> -o prog

If you want to print the staticstics on the use of atomic operations, uncomment
/data/cdl110/llvm/projects/compiler-rt/lib/tsan/rtl/tsan_stat.h:16,
unfortunately there is no present way to do this at runtime. These numbers were
not reported on in the paper, but they may be of interest to the reviewers.


6. Firefox:

As mentioned, simply copying the firefox executables, nor the entire codebase
has been successful. Therefore, we give instructions on how to build Firefox
with tsan. This process takes a long time, but once built, you can switch
between tsan03 and tsan11 by simply relinking the executable.

  mkdir /data/cdl110 && cd /data/cdl110
  hg clone https://hg.mozilla.org/mozilla-central/ mozilla-central
  cd /data/cdl110/firefox
  wget http://multicore.doc.ic.ac.uk/tools/tsan11/POPL17/mozconfig
  make -f client.mk

You can now run Firefox as follows (make sure no instance of Firefox is already
running):

  /data/cdl110/mozilla-central/objdir-ff-tsan/dist/bin/firefox


7. Chromium:

Again, due to the complicated nature of the codebase, we only provide
instructions on how to build Chromium with tsan.

  mkdir /data/cdl110/chromium && cd /data/cdl110/chromium
  fetch --no-history chromium
  cd /data/cdl110/chromium/src
  build/install/build/deps.sh
  gn gen out/tsan && gn args out/tsan

In the rsulting editor, enter the following:

  is_tsan = true
  enable_nacl = false
  is_debug = false

Chromium come bundled with clang, thus building either requires us to spend a
very long time understanding the build system, or just replace their clang with
ours. Replace their stuff by doing the following:

  cd /data/cdl110/chromium/src/third_party/llvm-build/Release+Asserts/bin
  rm -rf *
  cp -r /data/cdl110/llvm/build/bin/clang* .
  cp -r /data/cdl110/llvm/build/bin/llvm-symbolizer .

If building or running fails, you may also need to replace to files in
/data/cdl110/chromium/src/third_party/llvm-build/Release+Asserts/bin/clang in
the same way.

Now build as follows:

  cd /data/cdl110/chromium/src
  ninja -C out/tsan chrome

Run the browser as follows:

  export TSAN_OPTIONS="external_symbolizer_path=third_party/llvm-build/Release+Asserts/bin/llvm-symbolizer"
  out/tsan/chrome --no-sandbox


8. Notes on running browser experiments

We give some guidance on running experiments with the browsers using tsan11, as
described in S7.3 of the paper.

Running these browsers with tsan11 is very resource intensive, easily maxing out
the memory on a non-VM Ubuntu machine with 16GB. If you cannot run them, we
suggest reducing the size of the store buffers. You must change the value of
/data/cdl110/llvm/projects/compiler-rt/lib/tsan/rtl/tsan_relaxed:109 to a
smaller value (say, half of the initial value). You must then recompile tsan11
and Firefox as shown above (and avoid Chromium as stated before).

Note that, as with the CDSChecker tests, the experiment results shown in the
paper cannot be reproduced exactly, we suggest instead running the browsers with
JSBench, which we plan to include in the final version of the paper at the
suggestion of the paper reviewers. Simply direct the browser to
http://plg.uwaterloo.ca/~dynjs/jsbench/suite/jsbench-2013.1/harness.html to run
the benchmarks. Note that these experiments can cause the browser to crash,
even with tsan03, and is not related to our work. Simply restart the browser if
this happens and try again.

In order to examine the results, pipe the browser output to a log file. Example:

  /data/cdl110/mozilla-central/objdir-ff-tsan/dist/bin/firefox 2>~/firefox.log

Any data races that tsan detects will be printed with a header stating:

  WARNING: ThreadSanitizer: data race (pid=X)

Followed by the stack traces of the two threads when they raced, the location of
the race, and the stack traces of the threads that created the racing threads.
To look at the data races, simply search through the file for the above string
(without the pid part).