add sanitizers dependencies

1 files changed, 225 insertions, 0 deletions

diff --git a/contrib/libs/clang14-rt/lib/sanitizer_common/sanitizer_mutex.cpp b/contrib/libs/clang14-rt/lib/sanitizer_common/sanitizer_mutex.cpp
new file mode 100644
index 0000000000..40fe566612
--- /dev/null
+++ b/contrib/libs/clang14-rt/lib/sanitizer_common/sanitizer_mutex.cpp
@@ -0,0 +1,225 @@
+//===-- sanitizer_mutex.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 shared between AddressSanitizer and ThreadSanitizer
+// run-time libraries.
+//===----------------------------------------------------------------------===//
+
+#include "sanitizer_mutex.h"
+
+#include "sanitizer_common.h"
+
+namespace __sanitizer {
+
+void StaticSpinMutex::LockSlow() {
+  for (int i = 0;; i++) {
+    if (i < 100)
+      proc_yield(1);
+    else
+      internal_sched_yield();
+    if (atomic_load(&state_, memory_order_relaxed) == 0 &&
+        atomic_exchange(&state_, 1, memory_order_acquire) == 0)
+      return;
+  }
+}
+
+void Semaphore::Wait() {
+  u32 count = atomic_load(&state_, memory_order_relaxed);
+  for (;;) {
+    if (count == 0) {
+      FutexWait(&state_, 0);
+      count = atomic_load(&state_, memory_order_relaxed);
+      continue;
+    }
+    if (atomic_compare_exchange_weak(&state_, &count, count - 1,
+                                     memory_order_acquire))
+      break;
+  }
+}
+
+void Semaphore::Post(u32 count) {
+  CHECK_NE(count, 0);
+  atomic_fetch_add(&state_, count, memory_order_release);
+  FutexWake(&state_, count);
+}
+
+#if SANITIZER_CHECK_DEADLOCKS
+// An empty mutex meta table, it effectively disables deadlock detection.
+// Each tool can override the table to define own mutex hierarchy and
+// enable deadlock detection.
+// The table defines a static mutex type hierarchy (what mutex types can be locked
+// under what mutex types). This table is checked to be acyclic and then
+// actual mutex lock/unlock operations are checked to adhere to this hierarchy.
+// The checking happens on mutex types rather than on individual mutex instances
+// because doing it on mutex instances will both significantly complicate
+// the implementation, worsen performance and memory overhead and is mostly
+// unnecessary (we almost never lock multiple mutexes of the same type recursively).
+static constexpr int kMutexTypeMax = 20;
+SANITIZER_WEAK_ATTRIBUTE MutexMeta mutex_meta[kMutexTypeMax] = {};
+SANITIZER_WEAK_ATTRIBUTE void PrintMutexPC(uptr pc) {}
+static StaticSpinMutex mutex_meta_mtx;
+static int mutex_type_count = -1;
+// Adjacency matrix of what mutexes can be locked under what mutexes.
+static bool mutex_can_lock[kMutexTypeMax][kMutexTypeMax];
+// Mutex types with MutexMulti mark.
+static bool mutex_multi[kMutexTypeMax];
+
+void DebugMutexInit() {
+  // Build adjacency matrix.
+  bool leaf[kMutexTypeMax];
+  internal_memset(&leaf, 0, sizeof(leaf));
+  int cnt[kMutexTypeMax];
+  internal_memset(&cnt, 0, sizeof(cnt));
+  for (int t = 0; t < kMutexTypeMax; t++) {
+    mutex_type_count = t;
+    if (!mutex_meta[t].name)
+      break;
+    CHECK_EQ(t, mutex_meta[t].type);
+    for (uptr j = 0; j < ARRAY_SIZE(mutex_meta[t].can_lock); j++) {
+      MutexType z = mutex_meta[t].can_lock[j];
+      if (z == MutexInvalid)
+        break;
+      if (z == MutexLeaf) {
+        CHECK(!leaf[t]);
+        leaf[t] = true;
+        continue;
+      }
+      if (z == MutexMulti) {
+        mutex_multi[t] = true;
+        continue;
+      }
+      CHECK_LT(z, kMutexTypeMax);
+      CHECK(!mutex_can_lock[t][z]);
+      mutex_can_lock[t][z] = true;
+      cnt[t]++;
+    }
+  }
+  // Indicates the array is not properly terminated.
+  CHECK_LT(mutex_type_count, kMutexTypeMax);
+  // Add leaf mutexes.
+  for (int t = 0; t < mutex_type_count; t++) {
+    if (!leaf[t])
+      continue;
+    CHECK_EQ(cnt[t], 0);
+    for (int z = 0; z < mutex_type_count; z++) {
+      if (z == MutexInvalid || t == z || leaf[z])
+        continue;
+      CHECK(!mutex_can_lock[z][t]);
+      mutex_can_lock[z][t] = true;
+    }
+  }
+  // Build the transitive closure and check that the graphs is acyclic.
+  u32 trans[kMutexTypeMax];
+  static_assert(sizeof(trans[0]) * 8 >= kMutexTypeMax,
+                "kMutexTypeMax does not fit into u32, switch to u64");
+  internal_memset(&trans, 0, sizeof(trans));
+  for (int i = 0; i < mutex_type_count; i++) {
+    for (int j = 0; j < mutex_type_count; j++)
+      if (mutex_can_lock[i][j])
+        trans[i] |= 1 << j;
+  }
+  for (int k = 0; k < mutex_type_count; k++) {
+    for (int i = 0; i < mutex_type_count; i++) {
+      if (trans[i] & (1 << k))
+        trans[i] |= trans[k];
+    }
+  }
+  for (int i = 0; i < mutex_type_count; i++) {
+    if (trans[i] & (1 << i)) {
+      Printf("Mutex %s participates in a cycle\n", mutex_meta[i].name);
+      Die();
+    }
+  }
+}
+
+struct InternalDeadlockDetector {
+  struct LockDesc {
+    u64 seq;
+    uptr pc;
+    int recursion;
+  };
+  int initialized;
+  u64 sequence;
+  LockDesc locked[kMutexTypeMax];
+
+  void Lock(MutexType type, uptr pc) {
+    if (!Initialize(type))
+      return;
+    CHECK_LT(type, mutex_type_count);
+    // Find the last locked mutex type.
+    // This is the type we will use for hierarchy checks.
+    u64 max_seq = 0;
+    MutexType max_idx = MutexInvalid;
+    for (int i = 0; i != mutex_type_count; i++) {
+      if (locked[i].seq == 0)
+        continue;
+      CHECK_NE(locked[i].seq, max_seq);
+      if (max_seq < locked[i].seq) {
+        max_seq = locked[i].seq;
+        max_idx = (MutexType)i;
+      }
+    }
+    if (max_idx == type && mutex_multi[type]) {
+      // Recursive lock of the same type.
+      CHECK_EQ(locked[type].seq, max_seq);
+      CHECK(locked[type].pc);
+      locked[type].recursion++;
+      return;
+    }
+    if (max_idx != MutexInvalid && !mutex_can_lock[max_idx][type]) {
+      Printf("%s: internal deadlock: can't lock %s under %s mutex\n", SanitizerToolName,
+             mutex_meta[type].name, mutex_meta[max_idx].name);
+      PrintMutexPC(locked[max_idx].pc);
+      CHECK(0);
+    }
+    locked[type].seq = ++sequence;
+    locked[type].pc = pc;
+    locked[type].recursion = 1;
+  }
+
+  void Unlock(MutexType type) {
+    if (!Initialize(type))
+      return;
+    CHECK_LT(type, mutex_type_count);
+    CHECK(locked[type].seq);
+    CHECK_GT(locked[type].recursion, 0);
+    if (--locked[type].recursion)
+      return;
+    locked[type].seq = 0;
+    locked[type].pc = 0;
+  }
+
+  void CheckNoLocks() {
+    for (int i = 0; i < mutex_type_count; i++) CHECK_EQ(locked[i].recursion, 0);
+  }
+
+  bool Initialize(MutexType type) {
+    if (type == MutexUnchecked || type == MutexInvalid)
+      return false;
+    CHECK_GT(type, MutexInvalid);
+    if (initialized != 0)
+      return initialized > 0;
+    initialized = -1;
+    SpinMutexLock lock(&mutex_meta_mtx);
+    if (mutex_type_count < 0)
+      DebugMutexInit();
+    initialized = mutex_type_count ? 1 : -1;
+    return initialized > 0;
+  }
+};
+
+static THREADLOCAL InternalDeadlockDetector deadlock_detector;
+
+void CheckedMutex::LockImpl(uptr pc) { deadlock_detector.Lock(type_, pc); }
+
+void CheckedMutex::UnlockImpl() { deadlock_detector.Unlock(type_); }
+
+void CheckedMutex::CheckNoLocksImpl() { deadlock_detector.CheckNoLocks(); }
+#endif
+
+}  // namespace __sanitizer