[hwasan] Fix Thread reuse.

[eugenis]

Summary

HwasanThreadList::DontNeedThread clobbers Thread::next_, breaking the
freelist. As a result, only the top of the freelist ever gets reused,
and the rest of it is lost.

Since the Thread object its associated ring buffer is only 8Kb, this is
typically only noticable in long running processes, such as fuzzers.

Fix the problem by switching from an intrusive linked list to a vector.

[pcc]

LGTM

[thakis]

This test is failing on our clang packaging bots: https://logs.chromium.org/logs/chromium/buildbucket/cr-buildbucket.appspot.com/8863946222064502624/+/steps/package_clang/0/stdout?format=raw

Testing:  0.. 10.. 20.. 30.. 40.
 FAIL: HWAddressSanitizer-x86_64 :: TestCases/Linux/reuse-threads.cpp (36788 of 78839)
 ******************** TEST 'HWAddressSanitizer-x86_64 :: TestCases/Linux/reuse-threads.cpp' FAILED ********************
 Script:
 --
 : 'RUN: at line 2';      /b/s/w/ir/cache/builder/src/third_party/llvm-build/Release+Asserts/./bin/clang  --driver-mode=g++  -m64  -gline-tables-only -fsanitize=hwaddress -fuse-ld=lld -mcmodel=large -mllvm -hwasan-globals -mllvm -hwasan-use-short-granules -mllvm -hwasan-instrument-landing-pads=0 -mllvm -hwasan-instrument-personality-functions -mllvm -hwasan-instrument-stack=0 /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp -o /b/s/w/ir/cache/builder/src/third_party/llvm-build/Release+Asserts/projects/compiler-rt/test/hwasan/X86_64/TestCases/Linux/Output/reuse-threads.cpp.tmp && env HWASAN_OPTIONS=disable_allocator_tagging=1:random_tags=0:verbose_threads=1  /b/s/w/ir/cache/builder/src/third_party/llvm-build/Release+Asserts/projects/compiler-rt/test/hwasan/X86_64/TestCases/Linux/Output/reuse-threads.cpp.tmp 2>&1 | FileCheck /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp
 --
 Exit Code: 1
 
 Command Output (stderr):
 --
 /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp:49:16: error: CHECK-DAG: expected string not found in input
  // CHECK-DAG: Creating : T{{[0-9]+}} [[A]] stack:
                ^
 <stdin>:26:38: note: scanning from here
 Creating : T12 0x770000006000 stack: [0x7f017d89f000,0x7f017e09ef80) sz: 8388480 tls: [0x7f017e09ef80,0x7f017e0a0000)
                                      ^
 <stdin>:26:38: note: with "A" equal to "0x770000006000"
 Creating : T12 0x770000006000 stack: [0x7f017d89f000,0x7f017e09ef80) sz: 8388480 tls: [0x7f017e09ef80,0x7f017e0a0000)
                                      ^
 <stdin>:27:10: note: possible intended match here
 Destroying: T12 0x770000006000 stack: [0x7f017d89f000,0x7f017e09ef80) sz: 8388480 tls: [0x7f017e09ef80,0x7f017e0a0000)
          ^
 
 Input file: <stdin>
 Check file: /b/s/w/ir/cache/builder/src/third_party/llvm/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp
 
 -dump-input=help explains the following input dump.
 
 Input was:
 <<<<<<
           .
           .
           .
          21: Destroying: T9 0x77000000a000 stack: [0x7f017f0a2000,0x7f017f8a1f80) sz: 8388480 tls: [0x7f017f8a1f80,0x7f017f8a3000)
          22: Creating : T10 0x770000012000 stack: [0x7f017e8a1000,0x7f017f0a0f80) sz: 8388480 tls: [0x7f017f0a0f80,0x7f017f0a2000)
          23: Destroying: T10 0x770000012000 stack: [0x7f017e8a1000,0x7f017f0a0f80) sz: 8388480 tls: [0x7f017f0a0f80,0x7f017f0a2000)
          24: Creating : T11 0x77000000e000 stack: [0x7f017e0a0000,0x7f017e89ff80) sz: 8388480 tls: [0x7f017e89ff80,0x7f017e8a1000)
          25: Destroying: T11 0x77000000e000 stack: [0x7f017e0a0000,0x7f017e89ff80) sz: 8388480 tls: [0x7f017e89ff80,0x7f017e8a1000)
          26: Creating : T12 0x770000006000 stack: [0x7f017d89f000,0x7f017e09ef80) sz: 8388480 tls: [0x7f017e09ef80,0x7f017e0a0000)
 dag:49'0                                          X~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ error: no match found
 dag:49'1                                                                                                                           with "A" equal to "0x770000006000"
          27: Destroying: T12 0x770000006000 stack: [0x7f017d89f000,0x7f017e09ef80) sz: 8388480 tls: [0x7f017e09ef80,0x7f017e0a0000)
 dag:49'0     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 dag:49'2              ?                                                                                                             possible intended match
 >>>>>>
 
 --
 
 ********************
 Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
 ********************
 Failed Tests (1):
   HWAddressSanitizer-x86_64 :: TestCases/Linux/reuse-threads.cpp

PTAL!

[thakis]

Reverted in 6ab31eeb62612fc7f488811f3fdda95d9caa9350 for now.

[thakis]

Also failing on other bots, but not all the time: http://45.33.8.238/linux/32598/step_10.txt

compiler-rt/lib/hwasan/hwasan_thread.h

private:
 
   u32 random_state_;
   u32 random_buffer_;
 
   AllocatorCache allocator_cache_;
   HeapAllocationsRingBuffer *heap_allocations_;
   StackAllocationsRingBuffer *stack_allocations_;
 
-  Thread *next_;  // All live threads form a linked list.
-
   u64 unique_id_;  // counting from zero.
 
   u32 tagging_disabled_;  // if non-zero, malloc uses zero tag in this thread.
 
   bool announced_;
 
   friend struct ThreadListHead;
 };

compiler-rt/lib/hwasan/hwasan_thread_list.h

for (int shift = 1; shift < 7; ++shift) {
     if (size >= desired_bytes)
       return size;
   }
   Printf("stack history size too large: %d\n", flags()->stack_history_size);
   CHECK(0);
   return 0;
 }
 
-struct ThreadListHead {
-  Thread *list_;
-
-  ThreadListHead() : list_(nullptr) {}
-
-  void Push(Thread *t) {
-    t->next_ = list_;
-    list_ = t;
-  }
-
-  Thread *Pop() {
-    Thread *t = list_;
-    if (t)
-      list_ = t->next_;
-    return t;
-  }
-
-  void Remove(Thread *t) {
-    Thread **cur = &list_;
-    while (*cur != t) cur = &(*cur)->next_;
-    CHECK(*cur && "thread not found");
-    *cur = (*cur)->next_;
-  }
-
-  template <class CB>
-  void ForEach(CB cb) {
-    Thread *t = list_;
-    while (t) {
-      cb(t);
-      t = t->next_;
-    }
-  }
-};
-
 struct ThreadStats {
   uptr n_live_threads;
   uptr total_stack_size;
 };
 
 class HwasanThreadList {
  public:
   HwasanThreadList(uptr storage, uptr size)
       : free_space_(storage), free_space_end_(storage + size) {
     // [storage, storage + size) is used as a vector of
     // thread_alloc_size_-sized, ring_buffer_size_*2-aligned elements.
     // Each element contains
     // * a ring buffer at offset 0,
     // * a Thread object at offset ring_buffer_size_.
     ring_buffer_size_ = RingBufferSize();
     thread_alloc_size_ =
         RoundUpTo(ring_buffer_size_ + sizeof(Thread), ring_buffer_size_ * 2);
   }
 
   Thread *CreateCurrentThread() {
     Thread *t;
     {
       SpinMutexLock l(&list_mutex_);
-      t = free_list_.Pop();
-      if (t) {
+      if (!free_list_.empty()) {
+        t = free_list_.back();
+        free_list_.pop_back();
         uptr start = (uptr)t - ring_buffer_size_;
         internal_memset((void *)start, 0, ring_buffer_size_ + sizeof(Thread));
       } else {
         t = AllocThread();
       }
-      live_list_.Push(t);
+      live_list_.push_back(t);
     }
     t->Init((uptr)t - ring_buffer_size_, ring_buffer_size_);
     AddThreadStats(t);
     return t;
   }
 
   void DontNeedThread(Thread *t) {
     uptr start = (uptr)t - ring_buffer_size_;
     ReleaseMemoryPagesToOS(start, start + thread_alloc_size_);
   }
 
+  void RemoveThreadFromLiveList(Thread *t) {
+    for (Thread *&t2 : live_list_)
+      if (t2 == t) {
+        live_list_.erase(&t2);
+        return;
+      }
+    CHECK(0 && "thread not found in live list");
+  }
+
   void ReleaseThread(Thread *t) {
     RemoveThreadStats(t);
     t->Destroy();
     SpinMutexLock l(&list_mutex_);
-    live_list_.Remove(t);
-    free_list_.Push(t);
+    RemoveThreadFromLiveList(t);
+    free_list_.push_back(t);
     DontNeedThread(t);
   }
 
   Thread *GetThreadByBufferAddress(uptr p) {
     return (Thread *)(RoundDownTo(p, ring_buffer_size_ * 2) +
                       ring_buffer_size_);
   }
 
   uptr MemoryUsedPerThread() {
     uptr res = sizeof(Thread) + ring_buffer_size_;
     if (auto sz = flags()->heap_history_size)
       res += HeapAllocationsRingBuffer::SizeInBytes(sz);
     return res;
   }
 
   template <class CB>
   void VisitAllLiveThreads(CB cb) {
     SpinMutexLock l(&list_mutex_);
-    live_list_.ForEach(cb);
+    for (Thread *t : live_list_) cb(t);
   }
 
   void AddThreadStats(Thread *t) {
     SpinMutexLock l(&stats_mutex_);
     stats_.n_live_threads++;
     stats_.total_stack_size += t->stack_size();
   }
 
Thread *AllocThread() {
     return t;
   }
 
   uptr free_space_;
   uptr free_space_end_;
   uptr ring_buffer_size_;
   uptr thread_alloc_size_;
 
-  ThreadListHead free_list_;
-  ThreadListHead live_list_;
+  InternalMmapVector<Thread *> free_list_;
+  InternalMmapVector<Thread *> live_list_;
   SpinMutex list_mutex_;
 
   ThreadStats stats_;
   SpinMutex stats_mutex_;
 };
 
 void InitThreadList(uptr storage, uptr size);
 HwasanThreadList &hwasanThreadList();
 
 } // namespace

compiler-rt/lib/sanitizer_common/sanitizer_common.h

public:
   }
 
   void swap(InternalMmapVectorNoCtor &other) {
     Swap(data_, other.data_);
     Swap(capacity_bytes_, other.capacity_bytes_);
     Swap(size_, other.size_);
   }
 
+  void erase(T *t) {
+    if (t + 1 < end())
+      internal_memmove(t, t + 1, (end() - t - 1) * sizeof(T));
+    --size_;
+  }
+
  private:
   void Realloc(uptr new_capacity) {
     CHECK_GT(new_capacity, 0);
     CHECK_LE(size_, new_capacity);
     uptr new_capacity_bytes =
         RoundUpTo(new_capacity * sizeof(T), GetPageSizeCached());
     T *new_data = (T *)MmapOrDie(new_capacity_bytes, "InternalMmapVector");
     internal_memcpy(new_data, data_, size_ * sizeof(T));

compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cpp

 }
 
 TEST(SanitizerCommon, InternalMmapVectorRoundUpCapacity) {
   InternalMmapVector<uptr> v;
   v.reserve(1);
   CHECK_EQ(v.capacity(), GetPageSizeCached() / sizeof(uptr));
 }
 
-TEST(SanitizerCommon, InternalMmapVectorReize) {
+TEST(SanitizerCommon, InternalMmapVectorResize) {
   InternalMmapVector<uptr> v;
   CHECK_EQ(0U, v.size());
   CHECK_GE(v.capacity(), v.size());
 
   v.reserve(1000);
   CHECK_EQ(0U, v.size());
   CHECK_GE(v.capacity(), 1000U);
 
TEST(SanitizerCommon, InternalMmapVectorSwap) {
   }
   EXPECT_NE(vector2, vector3);
   EXPECT_NE(vector1, vector4);
   vector1.swap(vector3);
   EXPECT_EQ(vector2, vector3);
   EXPECT_EQ(vector1, vector4);
 }
 
+TEST(SanitizerCommon, InternalMmapVectorErase) {
+  InternalMmapVector<uptr> v;
+  std::vector<uptr> r;
+  for (uptr i = 0; i < 10; i++) {
+    v.push_back(i);
+    r.push_back(i);
+  }
+
+  v.erase(&v[9]);
+  r.erase(r.begin() + 9);
+  EXPECT_EQ(r.size(), v.size());
+  for (uptr i = 0; i < r.size(); i++) EXPECT_EQ(r[i], v[i]);
+
+  v.erase(&v[3]);
+  r.erase(r.begin() + 3);
+  EXPECT_EQ(r.size(), v.size());
+  for (uptr i = 0; i < r.size(); i++) EXPECT_EQ(r[i], v[i]);
+
+  v.erase(&v[0]);
+  r.erase(r.begin());
+  EXPECT_EQ(r.size(), v.size());
+  for (uptr i = 0; i < r.size(); i++) EXPECT_EQ(r[i], v[i]);
+}
+
 void TestThreadInfo(bool main) {
   uptr stk_addr = 0;
   uptr stk_size = 0;
   uptr tls_addr = 0;
   uptr tls_size = 0;
   GetThreadStackAndTls(main, &stk_addr, &stk_size, &tls_addr, &tls_size);
 
   int stack_var;

compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp

+// Test that Thread objects are reused.
+// RUN: %clangxx_hwasan -mllvm -hwasan-instrument-stack=0 %s -o %t && %env_hwasan_opts=verbose_threads=1 %run %t 2>&1 | FileCheck %s
+
+#include <assert.h>
+#include <fcntl.h>
+#include <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include <sanitizer/hwasan_interface.h>
+
+#include "../utils.h"
+
+pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;
+
+void *threadfn(void *) {
+  pthread_mutex_lock(UNTAG(&mu));
+  pthread_mutex_unlock(UNTAG(&mu));
+  return nullptr;
+}
+
+void start_stop_threads() {
+  constexpr int N = 4;
+  pthread_t threads[N];
+
+  pthread_mutex_lock(UNTAG(&mu));
+  for (auto &t : threads)
+    pthread_create(&t, nullptr, threadfn, nullptr);
+  pthread_mutex_unlock(UNTAG(&mu));
+
+  for (auto &t : threads)
+    pthread_join(t, nullptr);
+}
+
+int main() {
+  // Cut off initial threads.
+  // CHECK: === test start ===
+  untag_fprintf(stderr, "=== test start ===\n");
+
+  // CHECK: Creating  : T{{[0-9]+}} [[A:0x[0-9a-f]+]] stack:
+  // CHECK: Creating  : T{{[0-9]+}} [[B:0x[0-9a-f]+]] stack:
+  start_stop_threads();
+
+  // CHECK-DAG: Creating  : T{{[0-9]+}} [[A]] stack:
+  // CHECK-DAG: Creating  : T{{[0-9]+}} [[B]] stack:
+  start_stop_threads();
+
+  // CHECK-DAG: Creating  : T{{[0-9]+}} [[A]] stack:
+  // CHECK-DAG: Creating  : T{{[0-9]+}} [[B]] stack:
+  start_stop_threads();
+
+  return 0;
+}

compiler-rt/test/hwasan/TestCases/thread-uaf.c

void *Use(void *arg) {
   x[5] = 42;
   // CHECK: ERROR: HWAddressSanitizer: tag-mismatch on address
   // CHECK: WRITE of size 1 {{.*}} in thread T3
   // CHECK: thread-uaf.c:[[@LINE-3]]
   // CHECK: freed by thread T2 here
   // CHECK: in Deallocate
   // CHECK: previously allocated here:
   // CHECK: in Allocate
-  // CHECK: Thread: T2 0x
-  // CHECK: Thread: T3 0x
+  // CHECK-DAG: Thread: T2 0x
+  // CHECK-DAG: Thread: T3 0x
   // CHECK-DAG: Thread: T0 0x
   // CHECK-DAG: Thread: T1 0x
   __sync_fetch_and_add(&state, 1);
   return NULL;
 }
 
 int main() {
   __hwasan_enable_allocator_tagging();