Add data structures with bugs that tsan11/tsan11rec cannot detect

diff --git a/tsan11-missingbug/Makefile b/tsan11-missingbug/Makefile
new file mode 100644 (file)
index 0000000..8f855e8
--- /dev/null
+++ b/tsan11-missingbug/Makefile
@@ -0,0 +1,18 @@
+CC=../clang
+CXX=../clang++
+
+CXXFLAGS=-std=c++11 -pthread -Wall -g
+
+SEQLOCK = seqlock-test
+RWLOCK = rwlock-test
+
+all: $(SEQLOCK) $(RWLOCK)
+
+$(SEQLOCK): $(SEQLOCK).cc
+       $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS)
+
+$(RWLOCK): $(RWLOCK).cc
+       $(CXX) -o $@ $< $(CXXFLAGS) $(LDFLAGS)
+
+clean:
+       rm -f $(SEQLOCK) $(RWLOCK) *.o

diff --git a/tsan11-missingbug/rwlock-test b/tsan11-missingbug/rwlock-test
new file mode 100755 (executable)
index 0000000..3c4df40
Binary files /dev/null and b/tsan11-missingbug/rwlock-test differ

diff --git a/tsan11-missingbug/rwlock-test.cc b/tsan11-missingbug/rwlock-test.cc
new file mode 100644 (file)
index 0000000..560f53d
--- /dev/null
+++ b/tsan11-missingbug/rwlock-test.cc
@@ -0,0 +1,92 @@
+#include <stdio.h>
+#include <atomic>
+#include <pthread.h>
+#include <assert.h>
+// #include <stdatomic.h>
+
+using namespace std;
+
+#define RW_LOCK_BIAS       0x00100000
+#define WRITE_LOCK_CMP   RW_LOCK_BIAS
+
+/** Example implementation of linux rw lock along with 2 thread test
+ *  driver... */
+
+typedef union {
+       atomic_int lock;
+} rwlock_t;
+
+static inline void read_lock(rwlock_t *rw)
+{
+       int priorvalue = rw->lock.fetch_sub(1, memory_order_acquire);
+       while (priorvalue <= 0) {
+               rw->lock.fetch_add(1, memory_order_relaxed);
+               while (rw->lock.load(memory_order_relaxed) <= 0) {
+                       pthread_yield();
+               }
+               priorvalue = rw->lock.fetch_sub(1, memory_order_acquire);
+       }
+}
+
+// Injected bug for the two fetch_sub ***
+static inline void write_lock(rwlock_t *rw)
+{
+       int priorvalue = rw->lock.fetch_sub(RW_LOCK_BIAS, memory_order_relaxed);        // Should be acquire
+       while (priorvalue != RW_LOCK_BIAS) {
+               rw->lock.fetch_add(RW_LOCK_BIAS, memory_order_relaxed);
+               while (rw->lock.load(memory_order_relaxed) != RW_LOCK_BIAS) {
+                       pthread_yield();
+               }
+               priorvalue = rw->lock.fetch_sub(RW_LOCK_BIAS, memory_order_relaxed);    // Should be acquire
+       }
+}
+
+static inline void read_unlock(rwlock_t *rw)
+{
+       rw->lock.fetch_add(1, memory_order_release);
+}
+
+static inline void write_unlock(rwlock_t *rw)
+{
+       rw->lock.fetch_add(RW_LOCK_BIAS, memory_order_release);
+}
+
+rwlock_t mylock;
+atomic_int data1, data2;
+
+void * a(void *obj)
+{
+       int i;
+       for(i = 0; i < 4; i++) {
+               if ((i % 2) == 0) {
+                       read_lock(&mylock);
+                       int d1 = data1.load(memory_order_relaxed);
+                       int d2 = data2.load(memory_order_relaxed);
+                       assert(d1 == d2);
+                       read_unlock(&mylock);
+               } else {
+                       write_lock(&mylock);
+                       data1.store(i, memory_order_relaxed);
+                       data2.store(i, memory_order_relaxed);
+                       write_unlock(&mylock);
+               }
+       }
+
+       return NULL;
+}
+
+int main(int argc, char **argv)
+{
+       pthread_t t1, t2, t3;
+       mylock.lock.store(RW_LOCK_BIAS);
+
+       pthread_create(&t1, NULL, &a, NULL);
+       pthread_create(&t2, NULL, &a, NULL);
+       pthread_create(&t3, NULL, &a, NULL);
+
+       pthread_join(t1, NULL);
+       pthread_join(t2, NULL);
+       pthread_join(t3, NULL);
+
+       return 0;
+}

diff --git a/tsan11-missingbug/seqlock-test b/tsan11-missingbug/seqlock-test
new file mode 100755 (executable)
index 0000000..1b88369
Binary files /dev/null and b/tsan11-missingbug/seqlock-test differ

diff --git a/tsan11-missingbug/seqlock-test.cc b/tsan11-missingbug/seqlock-test.cc
new file mode 100644 (file)
index 0000000..7d5d0d1
--- /dev/null
+++ b/tsan11-missingbug/seqlock-test.cc
@@ -0,0 +1,87 @@
+#include <pthread.h>
+#include <atomic>
+#include <assert.h>
+//#include <threads.h>
+
+using namespace std;
+
+typedef struct seqlock {
+       // Sequence for reader consistency check
+       atomic_int _seq;
+       // It needs to be atomic to avoid data races
+       atomic_int _data1;
+       atomic_int _data2;
+
+       seqlock() {
+        _seq.store(0);
+        _data1.store(0);
+        _data2.store(0);
+       }
+
+       void read(int * d1, int *d2) {
+               while (true) {
+                       int old_seq = _seq.load(memory_order_acquire);
+                       if (old_seq % 2 == 1) continue;
+
+                       *d1 = _data1.load(memory_order_acquire);
+                       *d2 = _data2.load(memory_order_acquire);
+                       if (_seq.load(memory_order_relaxed) == old_seq) {
+                               return;
+                       }
+               }
+       }
+
+       void write(int new_data, int new_data2) {
+               while (true) {
+                       int old_seq = _seq.load(memory_order_relaxed); // Injected bug: should be acquire
+                       if (old_seq % 2 == 1)
+                               continue; // Retry
+
+                       if (_seq.compare_exchange_strong(old_seq, old_seq + 1,
+                               memory_order_relaxed, memory_order_relaxed))
+                               break;
+               }
+
+               // Update the data
+               _data1.store(new_data, memory_order_release);
+               _data2.store(new_data, memory_order_release);
+
+               _seq.fetch_add(1, memory_order_release);
+       }
+
+} seqlock_t;
+
+
+seqlock_t *lock;
+
+void * a(void *obj) {
+       lock->write(3,3);
+       return NULL;
+}
+
+void * b(void *obj) {
+       lock->write(2,2);
+       return NULL;
+}
+
+void * c(void *obj) {
+       int r1, r2;
+       lock->read(&r1, &r2);
+       assert(r1 == r2);
+       return NULL;
+}
+
+int main(int argc, char **argv) {
+       lock = new seqlock_t();
+
+       pthread_t t1, t2, t3;
+       pthread_create(&t1, NULL, &a, NULL);
+       pthread_create(&t2, NULL, &b, NULL);
+       pthread_create(&t3, NULL, &c, NULL);
+
+       pthread_join(t1, NULL);
+       pthread_join(t2, NULL);
+       pthread_join(t3, NULL);
+
+       return 0;
+}

diff --git a/tsan11-missingbug/test.sh b/tsan11-missingbug/test.sh
new file mode 100755 (executable)
index 0000000..17a5f3c
--- /dev/null
+++ b/tsan11-missingbug/test.sh
@@ -0,0 +1,33 @@
+#!/bin/bash
+
+EXE=$1
+TOTAL_RUN=1000
+CDSLIB="/home/vagrant/c11tester"
+export LD_LIBRARY_PATH=${CDSLIB}
+export C11TESTER='-x1'
+
+COUNT_ASSERT=0
+COUNT_TIME=0
+
+for i in `seq 1 1 $TOTAL_RUN` ; do
+  OUTPUT="$(/usr/bin/time -f "time: %U %S" $EXE 2>&1)"
+  ASSERT="$(echo "$OUTPUT" | grep "Assertion")"
+  if [ -n "$ASSERT" ] ; then
+    ((++COUNT_ASSERT))
+  fi
+
+  TIME="$(echo "$OUTPUT" | grep -o "time: .\... .\...")"
+  TIME_USER_S="$(echo "$TIME" | cut -d' ' -f2 | cut -d'.' -f1)"
+  TIME_USER_CS="$(echo "$TIME" | cut -d' ' -f2 | cut -d'.' -f2)"
+  TIME_SYSTEM_S="$(echo "$TIME" | cut -d' ' -f3 | cut -d'.' -f1)"
+  TIME_SYSTEM_CS="$(echo "$TIME" | cut -d' ' -f3 | cut -d'.' -f2)"
+
+  TIME_EXE=$((10#$TIME_USER_S * 1000 + 10#$TIME_USER_CS * 10 + 10#$TIME_SYSTEM_S * 1000 + 10#$TIME_SYSTEM_CS * 10))
+  COUNT_TIME=$((COUNT_TIME + TIME_EXE))
+done
+
+AVG_ASSERT=$(echo "${COUNT_ASSERT} * 100 / ${TOTAL_RUN}" | bc -l | xargs printf "%.1f")
+
+# -3 / log(1 - p) < n
+echo "Runs: $TOTAL_RUN | Assertions: $COUNT_ASSERT | Total time: ${COUNT_TIME}ms | Assert rate: ${AVG_ASSERT}%"
+rm C11FuzzerTmp*  2> /dev/null

diff --git a/tsan11-missingbug/test_all.sh b/tsan11-missingbug/test_all.sh
new file mode 100755 (executable)
index 0000000..6a5701a
--- /dev/null
+++ b/tsan11-missingbug/test_all.sh
@@ -0,0 +1,11 @@
+#!/bin/bash
+set -e
+set -u
+
+# Paul: skip `spsc-queue` as it deadlocks.
+
+for t in seqlock-test rwlock-test; do
+  echo -n "$t " 
+  ./test.sh ./$t
+done
+