[hwasan] Fix Thread reuse (try 2).

[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 with 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.

[eugenis]

This time with a better test using pthread barriers.

[vitalybuka]

compiler-rt/lib/hwasan/hwasan_thread_list.h

113

maybe you can just flip some the t->dead = true
and do some garbage collection when e.g. live_list_ contains 50% of dead?

115

t2 = live_list_.back();
live_list_.pop_back();

[eugenis]

compiler-rt/lib/hwasan/hwasan_thread_list.h

113

this sounds like a premature optimization, and it would increase RAM by decreasing CPU use, which is not the direction we want to move on mobile

115

This would remove the last element, why?

[vitalybuka]

compiler-rt/lib/hwasan/hwasan_thread_list.h

115

no, the last element in t2 position now.
to avoid moving memory by live_list_.erase(&t2);

[eugenis]

compiler-rt/lib/hwasan/hwasan_thread_list.h

115

that's a really good idea, I can't believe I missed it

[eugenis]

faster live list removal

[eugenis]

Remove the implementation of erase(), which is no longer necessary.
PTAL.

[hctim]

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

42

Nit: why create 4 threads if we only check that 2 of them are reused? Why not check 4 or only create 2?

[eugenis]

reduced the number of threads in the test to 2

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) {
+        // To remove t2, copy the last element of the list in t2's position, and
+        // pop_back(). This works even if t2 is itself the last element.
+        t2 = live_list_.back();
+        live_list_.pop_back();
+        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/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_barrier_t bar;
+
+void *threadfn(void *) {
+  pthread_barrier_wait(UNTAG(&bar));
+  return nullptr;
+}
+
+void start_stop_threads() {
+  constexpr int N = 4;
+  pthread_t threads[N];
+
+  pthread_barrier_init(UNTAG(&bar), nullptr, N + 1);
+  for (auto &t : threads)
+    pthread_create(&t, nullptr, threadfn, nullptr);
+
+  pthread_barrier_wait(UNTAG(&bar));
+
+  for (auto &t : threads)
+    pthread_join(t, nullptr);
+  pthread_barrier_destroy(UNTAG(&bar));
+}
+
+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();