From e1eeb026e66c38add2a1f8f1271e1f618c2f7a72 Mon Sep 17 00:00:00 2001 From: Evgenii Stepanov Date: Tue, 10 Nov 2020 14:15:47 -0800 Subject: [PATCH] [hwasan] Fix Thread reuse. 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. Differential Revision: https://reviews.llvm.org/D91208 --- compiler-rt/lib/hwasan/hwasan_thread.h | 2 - compiler-rt/lib/hwasan/hwasan_thread_list.h | 60 +++++++--------------- .../lib/sanitizer_common/sanitizer_common.h | 6 +++ .../tests/sanitizer_common_test.cpp | 26 +++++++++- .../test/hwasan/TestCases/Linux/reuse-threads.cpp | 54 +++++++++++++++++++ compiler-rt/test/hwasan/TestCases/thread-uaf.c | 4 +- 6 files changed, 105 insertions(+), 47 deletions(-) create mode 100644 compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp diff --git a/compiler-rt/lib/hwasan/hwasan_thread.h b/compiler-rt/lib/hwasan/hwasan_thread.h index ebcdb79..88958da 100644 --- a/compiler-rt/lib/hwasan/hwasan_thread.h +++ b/compiler-rt/lib/hwasan/hwasan_thread.h @@ -74,8 +74,6 @@ class Thread { 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. diff --git a/compiler-rt/lib/hwasan/hwasan_thread_list.h b/compiler-rt/lib/hwasan/hwasan_thread_list.h index 914b632..b1ec368 100644 --- a/compiler-rt/lib/hwasan/hwasan_thread_list.h +++ b/compiler-rt/lib/hwasan/hwasan_thread_list.h @@ -66,40 +66,6 @@ static uptr RingBufferSize() { 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 - void ForEach(CB cb) { - Thread *t = list_; - while (t) { - cb(t); - t = t->next_; - } - } -}; - struct ThreadStats { uptr n_live_threads; uptr total_stack_size; @@ -123,14 +89,15 @@ class HwasanThreadList { 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); @@ -142,12 +109,21 @@ class HwasanThreadList { 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); } @@ -166,7 +142,7 @@ class HwasanThreadList { template void VisitAllLiveThreads(CB cb) { SpinMutexLock l(&list_mutex_); - live_list_.ForEach(cb); + for (Thread *t : live_list_) cb(t); } void AddThreadStats(Thread *t) { @@ -201,8 +177,8 @@ class HwasanThreadList { uptr ring_buffer_size_; uptr thread_alloc_size_; - ThreadListHead free_list_; - ThreadListHead live_list_; + InternalMmapVector free_list_; + InternalMmapVector live_list_; SpinMutex list_mutex_; ThreadStats stats_; diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common.h b/compiler-rt/lib/sanitizer_common/sanitizer_common.h index bce24d6..88f1290 100644 --- a/compiler-rt/lib/sanitizer_common/sanitizer_common.h +++ b/compiler-rt/lib/sanitizer_common/sanitizer_common.h @@ -543,6 +543,12 @@ class InternalMmapVectorNoCtor { 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); diff --git a/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cpp b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cpp index 259bd99..422e9d3 100644 --- a/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cpp +++ b/compiler-rt/lib/sanitizer_common/tests/sanitizer_common_test.cpp @@ -93,7 +93,7 @@ TEST(SanitizerCommon, InternalMmapVectorRoundUpCapacity) { CHECK_EQ(v.capacity(), GetPageSizeCached() / sizeof(uptr)); } -TEST(SanitizerCommon, InternalMmapVectorReize) { +TEST(SanitizerCommon, InternalMmapVectorResize) { InternalMmapVector v; CHECK_EQ(0U, v.size()); CHECK_GE(v.capacity(), v.size()); @@ -176,6 +176,30 @@ TEST(SanitizerCommon, InternalMmapVectorSwap) { EXPECT_EQ(vector1, vector4); } +TEST(SanitizerCommon, InternalMmapVectorErase) { + InternalMmapVector v; + std::vector 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; diff --git a/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp b/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp new file mode 100644 index 0000000..46e9b86 --- /dev/null +++ b/compiler-rt/test/hwasan/TestCases/Linux/reuse-threads.cpp @@ -0,0 +1,54 @@ +// 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 +#include +#include +#include +#include +#include + +#include + +#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; +} diff --git a/compiler-rt/test/hwasan/TestCases/thread-uaf.c b/compiler-rt/test/hwasan/TestCases/thread-uaf.c index f091167..7051b26 100644 --- a/compiler-rt/test/hwasan/TestCases/thread-uaf.c +++ b/compiler-rt/test/hwasan/TestCases/thread-uaf.c @@ -34,8 +34,8 @@ void *Use(void *arg) { // 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); -- 2.7.4