tsan: add new vector clock

[dvyukov]

Summary

Add new fixed-size vector clock for the new tsan runtime.
For now it's unused.

[dvyukov]

added some comments

[melver]

Review incomplete -- I'll need to look a bit at the rest of the (uncommitted) changes to understand the requirements. But if there are special requirements that aren't obvious, do let us know.

Trying to review the SSE code as well.

compiler-rt/lib/tsan/rtl/tsan_defs.h

59

Any overloaded operators / helpers for these that should be pulled into this patch?

compiler-rt/lib/tsan/rtl/tsan_vector_clock.h

35

Is this the only required operator?
No operator==, operator<, or such required?

[dvyukov]

But if there are special requirements that aren't obvious, do let us know.

Humm... I can't think of any.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_defs.h

59

I don't have any in the larger PR.

compiler-rt/lib/tsan/rtl/tsan_vector_clock.h

35

Is this the only required operator?

Yes.

No operator==, operator<, or such required?

No.

[melver]

compiler-rt/lib/tsan/rtl/tsan_defs.h

56

I infer that this is not actually max Sid (!= 255), because if this were to be stored in Sid it'd overflow. (Since kMaxSid and Sid are incompatible types my guess is that's not happening right now.)

kMaxThreadSlots ?

compiler-rt/lib/tsan/rtl/tsan_vector_clock.cpp

69

Would be good to make clang-tidy happy unless there's a performance benefit to not have it return *this.

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_defs.h

56

Right, it's not "max", it's "count".
kThreadSlotCount?

[melver]

compiler-rt/lib/tsan/rtl/tsan_defs.h

56

Sounds good. That name to me suggests that there are always kThreadSlotCount slots (no more no less), right?

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_defs.h

56

Yes, my current prototype uses fixed number of slots always.

[dvyukov]

rename kMaxSid to kThreadSlotCount
fixed operator= signature

[vitalybuka]

compiler-rt/lib/tsan/rtl/tsan_defs.h

55

Why this is "enum class"?

[dvyukov]

compiler-rt/lib/tsan/rtl/tsan_defs.h

55

Is you mean "instead of typedef", enum class won't convert to any other types implicitly and gives much stronger type safety.

compiler-rt/lib/tsan/CMakeLists.txt

set(TSAN_SOURCES
   rtl/tsan_rtl_mutex.cpp
   rtl/tsan_rtl_proc.cpp
   rtl/tsan_rtl_report.cpp
   rtl/tsan_rtl_thread.cpp
   rtl/tsan_stack_trace.cpp
   rtl/tsan_suppressions.cpp
   rtl/tsan_symbolize.cpp
   rtl/tsan_sync.cpp
+  rtl/tsan_vector_clock.cpp
   )
 
 set(TSAN_CXX_SOURCES
   rtl/tsan_new_delete.cpp
   )
 
 if(APPLE)
   list(APPEND TSAN_SOURCES
set(TSAN_HEADERS
   rtl/tsan_report.h
   rtl/tsan_rtl.h
   rtl/tsan_stack_trace.h
   rtl/tsan_suppressions.h
   rtl/tsan_symbolize.h
   rtl/tsan_sync.h
   rtl/tsan_trace.h
   rtl/tsan_update_shadow_word_inl.h
+  rtl/tsan_vector_clock.h
   )
 
 set(TSAN_RUNTIME_LIBRARIES)
 add_compiler_rt_component(tsan)
 
 if("${CMAKE_C_FLAGS}" MATCHES "-Wno-(error=)?unused-command-line-argument")
   set(EXTRA_CFLAGS "-Wno-error=unused-command-line-argument ${EXTRA_CFLAGS}")
 endif()

compiler-rt/lib/tsan/rtl/tsan_defs.h

 #ifndef TSAN_DEFS_H
 #define TSAN_DEFS_H
 
 #include "sanitizer_common/sanitizer_internal_defs.h"
 #include "sanitizer_common/sanitizer_libc.h"
 #include "sanitizer_common/sanitizer_mutex.h"
 #include "ubsan/ubsan_platform.h"
 
+#ifndef TSAN_VECTORIZE
+#  define TSAN_VECTORIZE __SSE4_2__
+#endif
+
+#if TSAN_VECTORIZE
+// <emmintrin.h> transitively includes <stdlib.h>,
+// and it's prohibited to include std headers into tsan runtime.
+// So we do this dirty trick.
+#  define _MM_MALLOC_H_INCLUDED
+#  define __MM_MALLOC_H
+#  include <emmintrin.h>
+#  include <smmintrin.h>
+#  define VECTOR_ALIGNED ALIGNED(16)
+typedef __m128i m128;
+#else
+#  define VECTOR_ALIGNED
+#endif
+
 // Setup defaults for compile definitions.
 #ifndef TSAN_NO_HISTORY
 # define TSAN_NO_HISTORY 0
 #endif
 
 #ifndef TSAN_CONTAINS_UBSAN
 # if CAN_SANITIZE_UB && !SANITIZER_GO
 #  define TSAN_CONTAINS_UBSAN 1
 # else
 #  define TSAN_CONTAINS_UBSAN 0
 # endif
 #endif
 
 namespace __tsan {
 
+// Thread slot ID.
+enum class Sid : u8 {};
+constexpr uptr kThreadSlotCount = 256;
+
+// Abstract time unit, vector clock element.
+enum class Epoch : u16 {};
+constexpr Epoch kEpochZero = static_cast<Epoch>(0);
+
 const int kClkBits = 42;
 const unsigned kMaxTidReuse = (1 << (64 - kClkBits)) - 1;
 
 struct ClockElem {
   u64 epoch  : kClkBits;
   u64 reused : 64 - kClkBits;  // tid reuse count
 };
 

compiler-rt/lib/tsan/rtl/tsan_rtl.cpp

 #include "tsan_defs.h"
 #include "tsan_interface.h"
 #include "tsan_mman.h"
 #include "tsan_platform.h"
 #include "tsan_suppressions.h"
 #include "tsan_symbolize.h"
 #include "ubsan/ubsan_init.h"
 
-#ifdef __SSE3__
-// <emmintrin.h> transitively includes <stdlib.h>,
-// and it's prohibited to include std headers into tsan runtime.
-// So we do this dirty trick.
-#define _MM_MALLOC_H_INCLUDED
-#define __MM_MALLOC_H
-#include <emmintrin.h>
-typedef __m128i m128;
-#endif
-
 volatile int __tsan_resumed = 0;
 
 extern "C" void __tsan_resume() {
   __tsan_resumed = 1;
 }
 
 namespace __tsan {
 
if (Shadow::Addr0AndSizeAreEqual(cur, old) &&
         old.epoch() > sync_epoch &&
         old.IsAtomic() == cur.IsAtomic() &&
         old.IsRead() <= cur.IsRead())
       return true;
   }
   return false;
 }
 
-#if defined(__SSE3__)
-#define SHUF(v0, v1, i0, i1, i2, i3) _mm_castps_si128(_mm_shuffle_ps( \
-    _mm_castsi128_ps(v0), _mm_castsi128_ps(v1), \
+#if TSAN_VECTORIZE
+#  define SHUF(v0, v1, i0, i1, i2, i3)                    \
+    _mm_castps_si128(_mm_shuffle_ps(_mm_castsi128_ps(v0), \
+                                    _mm_castsi128_ps(v1), \
                                     (i0)*1 + (i1)*4 + (i2)*16 + (i3)*64))
 ALWAYS_INLINE
 bool ContainsSameAccessFast(u64 *s, u64 a, u64 sync_epoch, bool is_write) {
   // This is an optimized version of ContainsSameAccessSlow.
   // load current access into access[0:63]
   const m128 access     = _mm_cvtsi64_si128(a);
   // duplicate high part of access in addr0:
   // addr0[0:31]        = access[32:63]
   // addr0[32:63]       = access[32:63]
bool ContainsSameAccessFast(u64 *s, u64 a, u64 sync_epoch, bool is_write) {
   // mask[15] = res[127]
   const int mask        = _mm_movemask_epi8(res);
   return mask != 0;
 }
 #endif
 
 ALWAYS_INLINE
 bool ContainsSameAccess(u64 *s, u64 a, u64 sync_epoch, bool is_write) {
-#if defined(__SSE3__)
+#if TSAN_VECTORIZE
   bool res = ContainsSameAccessFast(s, a, sync_epoch, is_write);
   // NOTE: this check can fail if the shadow is concurrently mutated
   // by other threads. But it still can be useful if you modify
   // ContainsSameAccessFast and want to ensure that it's not completely broken.
   // DCHECK_EQ(res, ContainsSameAccessSlow(s, a, sync_epoch, is_write));
   return res;
 #else
   return ContainsSameAccessSlow(s, a, sync_epoch, is_write);

compiler-rt/lib/tsan/rtl/tsan_vector_clock.h

+//===-- tsan_vector_clock.h -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer (TSan), a race detector.
+//
+//===----------------------------------------------------------------------===//
+#ifndef TSAN_VECTOR_CLOCK_H
+#define TSAN_VECTOR_CLOCK_H
+
+#include "tsan_defs.h"
+
+namespace __tsan {
+
+// Fixed-size vector clock, used both for threads and sync objects.
+class VectorClock {
+ public:
+  VectorClock();
+
+  Epoch Get(Sid sid) const;
+  void Set(Sid sid, Epoch v);
+
+  void Reset();
+  void Acquire(const VectorClock* src);
+  void Release(VectorClock** dstp) const;
+  void ReleaseStore(VectorClock** dstp) const;
+  void ReleaseStoreAcquire(VectorClock** dstp);
+  void ReleaseAcquire(VectorClock** dstp);
+
+  VectorClock& operator=(const VectorClock& other);
+
+ private:
+  Epoch clk_[kThreadSlotCount] VECTOR_ALIGNED;
+};
+
+ALWAYS_INLINE Epoch VectorClock::Get(Sid sid) const {
+  return clk_[static_cast<u8>(sid)];
+}
+
+ALWAYS_INLINE void VectorClock::Set(Sid sid, Epoch v) {
+  DCHECK_GE(v, clk_[static_cast<u8>(sid)]);
+  clk_[static_cast<u8>(sid)] = v;
+}
+
+}  // namespace __tsan
+
+#endif  // TSAN_VECTOR_CLOCK_H

compiler-rt/lib/tsan/rtl/tsan_vector_clock.cpp

+//===-- tsan_vector_clock.cpp ---------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer (TSan), a race detector.
+//
+//===----------------------------------------------------------------------===//
+#include "tsan_vector_clock.h"
+
+#include "sanitizer_common/sanitizer_placement_new.h"
+#include "tsan_mman.h"
+
+namespace __tsan {
+
+#if TSAN_VECTORIZE
+const uptr kVectorClockSize = kThreadSlotCount * sizeof(Epoch) / sizeof(m128);
+#endif
+
+VectorClock::VectorClock() { Reset(); }
+
+void VectorClock::Reset() {
+#if !TSAN_VECTORIZE
+  for (uptr i = 0; i < kMaxSid; i++) clk_[i] = kEpochZero;
+#else
+  m128 z = _mm_setzero_si128();
+  m128* vclk = reinterpret_cast<m128*>(clk_);
+  for (uptr i = 0; i < kVectorClockSize; i++) _mm_store_si128(&vclk[i], z);
+#endif
+}
+
+void VectorClock::Acquire(const VectorClock* src) {
+  if (!src)
+    return;
+#if !TSAN_VECTORIZE
+  for (uptr i = 0; i < kMaxSid; i++) clk_[i] = max(clk_[i], src->clk_[i]);
+#else
+  m128* __restrict vdst = reinterpret_cast<m128*>(clk_);
+  m128 const* __restrict vsrc = reinterpret_cast<m128 const*>(src->clk_);
+  for (uptr i = 0; i < kVectorClockSize; i++) {
+    m128 s = _mm_load_si128(&vsrc[i]);
+    m128 d = _mm_load_si128(&vdst[i]);
+    m128 m = _mm_max_epu16(s, d);
+    _mm_store_si128(&vdst[i], m);
+  }
+#endif
+}
+
+static VectorClock* AllocClock(VectorClock** dstp) {
+  if (UNLIKELY(!*dstp))
+    *dstp = New<VectorClock>();
+  return *dstp;
+}
+
+void VectorClock::Release(VectorClock** dstp) const {
+  VectorClock* dst = AllocClock(dstp);
+  dst->Acquire(this);
+}
+
+void VectorClock::ReleaseStore(VectorClock** dstp) const {
+  VectorClock* dst = AllocClock(dstp);
+  *dst = *this;
+}
+
+VectorClock& VectorClock::operator=(const VectorClock& other) {
+#if !TSAN_VECTORIZE
+  for (uptr i = 0; i < kMaxSid; i++) clk_[i] = other.clk_[i];
+#else
+  m128* __restrict vdst = reinterpret_cast<m128*>(clk_);
+  m128 const* __restrict vsrc = reinterpret_cast<m128 const*>(other.clk_);
+  for (uptr i = 0; i < kVectorClockSize; i++) {
+    m128 s = _mm_load_si128(&vsrc[i]);
+    _mm_store_si128(&vdst[i], s);
+  }
+#endif
+  return *this;
+}
+
+void VectorClock::ReleaseStoreAcquire(VectorClock** dstp) {
+  VectorClock* dst = AllocClock(dstp);
+#if !TSAN_VECTORIZE
+  for (uptr i = 0; i < kMaxSid; i++) {
+    Epoch tmp = dst->clk_[i];
+    dst->clk_[i] = clk_[i];
+    clk_[i] = max(clk_[i], tmp);
+  }
+#else
+  m128* __restrict vdst = reinterpret_cast<m128*>(dst->clk_);
+  m128* __restrict vclk = reinterpret_cast<m128*>(clk_);
+  for (uptr i = 0; i < kVectorClockSize; i++) {
+    m128 t = _mm_load_si128(&vdst[i]);
+    m128 c = _mm_load_si128(&vclk[i]);
+    m128 m = _mm_max_epu16(c, t);
+    _mm_store_si128(&vdst[i], c);
+    _mm_store_si128(&vclk[i], m);
+  }
+#endif
+}
+
+void VectorClock::ReleaseAcquire(VectorClock** dstp) {
+  VectorClock* dst = AllocClock(dstp);
+#if !TSAN_VECTORIZE
+  for (uptr i = 0; i < kMaxSid; i++) {
+    dst->clk_[i] = max(dst->clk_[i], clk_[i]);
+    clk_[i] = dst->clk_[i];
+  }
+#else
+  m128* __restrict vdst = reinterpret_cast<m128*>(dst->clk_);
+  m128* __restrict vclk = reinterpret_cast<m128*>(clk_);
+  for (uptr i = 0; i < kVectorClockSize; i++) {
+    m128 c = _mm_load_si128(&vclk[i]);
+    m128 d = _mm_load_si128(&vdst[i]);
+    m128 m = _mm_max_epu16(c, d);
+    _mm_store_si128(&vdst[i], m);
+    _mm_store_si128(&vclk[i], m);
+  }
+#endif
+}
+
+}  // namespace __tsan

compiler-rt/lib/tsan/tests/unit/CMakeLists.txt

 set(TSAN_UNIT_TEST_SOURCES
   tsan_clock_test.cpp
   tsan_dense_alloc_test.cpp
   tsan_flags_test.cpp
   tsan_ilist_test.cpp
   tsan_mman_test.cpp
   tsan_shadow_test.cpp
   tsan_stack_test.cpp
   tsan_sync_test.cpp
   tsan_unit_test_main.cpp
+  tsan_vector_clock_test.cpp
   )
 
 add_tsan_unittest(TsanUnitTest
   SOURCES ${TSAN_UNIT_TEST_SOURCES})

compiler-rt/lib/tsan/tests/unit/tsan_vector_clock_test.cpp

+//===-- tsan_clock_test.cpp -----------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file is a part of ThreadSanitizer (TSan), a race detector.
+//
+//===----------------------------------------------------------------------===//
+#include "tsan_vector_clock.h"
+
+#include "gtest/gtest.h"
+#include "tsan_rtl.h"
+
+namespace __tsan {
+
+TEST(VectorClock, GetSet) {
+  // Compiler won't ensure alignment on stack.
+  VectorClock *vc = New<VectorClock>();
+  for (uptr i = 0; i < kThreadSlotCount; i++)
+    ASSERT_EQ(vc->Get(static_cast<Sid>(i)), kEpochZero);
+  for (uptr i = 0; i < kThreadSlotCount; i++)
+    vc->Set(static_cast<Sid>(i), static_cast<Epoch>(i));
+  for (uptr i = 0; i < kThreadSlotCount; i++)
+    ASSERT_EQ(vc->Get(static_cast<Sid>(i)), static_cast<Epoch>(i));
+  vc->Reset();
+  for (uptr i = 0; i < kThreadSlotCount; i++)
+    ASSERT_EQ(vc->Get(static_cast<Sid>(i)), kEpochZero);
+  DestroyAndFree(vc);
+}
+
+TEST(VectorClock, VectorOps) {
+  VectorClock *vc1 = New<VectorClock>();
+  VectorClock *vc2 = nullptr;
+  VectorClock *vc3 = nullptr;
+
+  vc1->Acquire(vc2);
+  for (uptr i = 0; i < kThreadSlotCount; i++)
+    ASSERT_EQ(vc1->Get(static_cast<Sid>(i)), kEpochZero);
+  vc1->Release(&vc2);
+  EXPECT_NE(vc2, nullptr);
+  vc1->Acquire(vc2);
+  for (uptr i = 0; i < kThreadSlotCount; i++)
+    ASSERT_EQ(vc1->Get(static_cast<Sid>(i)), kEpochZero);
+
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    vc1->Set(static_cast<Sid>(i), static_cast<Epoch>(i));
+    vc2->Set(static_cast<Sid>(i), static_cast<Epoch>(kThreadSlotCount - i));
+  }
+  vc1->Acquire(vc2);
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    ASSERT_EQ(vc1->Get(static_cast<Sid>(i)),
+              static_cast<Epoch>(i < kThreadSlotCount / 2 ? kThreadSlotCount - i
+                                                          : i));
+    ASSERT_EQ(vc2->Get(static_cast<Sid>(i)),
+              static_cast<Epoch>(kThreadSlotCount - i));
+  }
+  vc2->ReleaseStore(&vc3);
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    ASSERT_EQ(vc3->Get(static_cast<Sid>(i)),
+              static_cast<Epoch>(kThreadSlotCount - i));
+    ASSERT_EQ(vc2->Get(static_cast<Sid>(i)),
+              static_cast<Epoch>(kThreadSlotCount - i));
+  }
+
+  vc1->Reset();
+  vc2->Reset();
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    vc1->Set(static_cast<Sid>(i), static_cast<Epoch>(i));
+    vc2->Set(static_cast<Sid>(i), static_cast<Epoch>(kThreadSlotCount - i));
+  }
+  vc1->ReleaseAcquire(&vc2);
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    Epoch expect =
+        static_cast<Epoch>(i < kThreadSlotCount / 2 ? kThreadSlotCount - i : i);
+    ASSERT_EQ(vc1->Get(static_cast<Sid>(i)), expect);
+    ASSERT_EQ(vc2->Get(static_cast<Sid>(i)), expect);
+  }
+
+  vc1->Reset();
+  vc2->Reset();
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    vc1->Set(static_cast<Sid>(i), static_cast<Epoch>(i));
+    vc2->Set(static_cast<Sid>(i), static_cast<Epoch>(kThreadSlotCount - i));
+  }
+  vc1->ReleaseStoreAcquire(&vc2);
+  for (uptr i = 0; i < kThreadSlotCount; i++) {
+    ASSERT_EQ(vc1->Get(static_cast<Sid>(i)),
+              static_cast<Epoch>(i < kThreadSlotCount / 2 ? kThreadSlotCount - i
+                                                          : i));
+    ASSERT_EQ(vc2->Get(static_cast<Sid>(i)), static_cast<Epoch>(i));
+  }
+
+  DestroyAndFree(vc1);
+  DestroyAndFree(vc2);
+  DestroyAndFree(vc3);
+}
+
+}  // namespace __tsan