Index: lib/sanitizer_common/sanitizer_quarantine.h =================================================================== --- lib/sanitizer_common/sanitizer_quarantine.h +++ lib/sanitizer_common/sanitizer_quarantine.h @@ -31,6 +31,36 @@ uptr size; uptr count; void *batch[kSize]; + + // Empty batches are not considered valid. + void init(void *ptr, uptr size) { + count = 1; + this->size = size + sizeof(QuarantineBatch); // Account for the batch size. + } + + // The total size of quarantined nodes recorded in this batch. + uptr quarantined_size() const { + return size - sizeof(QuarantineBatch); + } + + void push_back(void *ptr, uptr size) { + CHECK_LT(count, kSize); + batch[count++] = ptr; + this->size += size; + } + + bool can_merge(const QuarantineBatch* const from) const { + return count + from->count <= kSize; + } + + void merge(const QuarantineBatch* const from) { + CHECK_LE(count + from->count, kSize); + CHECK_GT(size, sizeof(QuarantineBatch)); + for (uptr i = 0; i < from->count; ++i) + batch[count + i] = from->batch[i]; + count += from->count; + size += from->quarantined_size(); + } }; COMPILER_CHECK(sizeof(QuarantineBatch) <= (1 << 13)); // 8Kb. @@ -65,10 +95,13 @@ } void NOINLINE Drain(Cache *c, Callback cb) { + QuarantineBatch *batch_to_deallocate = nullptr; { SpinMutexLock l(&cache_mutex_); - cache_.Transfer(c); + batch_to_deallocate = cache_.Transfer(c); } + if (batch_to_deallocate) + cb.Deallocate(batch_to_deallocate); if (cache_.Size() > GetSize() && recycle_mutex_.TryLock()) Recycle(cb); } @@ -133,20 +166,39 @@ void Enqueue(Callback cb, void *ptr, uptr size) { if (list_.empty() || list_.back()->count == QuarantineBatch::kSize) { - AllocBatch(cb); - size += sizeof(QuarantineBatch); // Count the batch in Quarantine size. + QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b)); + CHECK(b); + b->init(ptr, size); + EnqueueBatch(b); + } else { + list_.back()->push_back(ptr, size); + SizeAdd(size); } - QuarantineBatch *b = list_.back(); - CHECK(b); - b->batch[b->count++] = ptr; - b->size += size; - SizeAdd(size); } - void Transfer(QuarantineCache *c) { - list_.append_back(&c->list_); - SizeAdd(c->Size()); - atomic_store(&c->size_, 0, memory_order_relaxed); + QuarantineBatch *Transfer(QuarantineCache *from_cache) { + QuarantineBatch *batch_to_deallocate = nullptr; + if (list_.empty() || from_cache->list_.empty() || + from_cache->list_.front()->next || + !list_.back()->can_merge(from_cache->list_.front())) { + // Besides the trivial case of empty lists, there are either more than one + // batch to transfer or there're too many elements in the first batch and + // even if this cache's last batch is not full yet, it's too costly to + // move elements one by one, so we just accept memory penalty (the wasted + // space in this cache's last batch array). + // TODO(alekseyshl): consider transferring full batches and merge + // partially filled tail ones. + list_.append_back(&from_cache->list_); + SizeAdd(from_cache->Size()); + } else { + // Two tail batches can be merged maintaining batch and cache invariants. + batch_to_deallocate = from_cache->list_.front(); + from_cache->list_.pop_front(); + list_.back()->merge(batch_to_deallocate); + SizeAdd(batch_to_deallocate->quarantined_size()); + } + atomic_store(&from_cache->size_, 0, memory_order_relaxed); + return batch_to_deallocate; } void EnqueueBatch(QuarantineBatch *b) { @@ -173,15 +225,6 @@ void SizeSub(uptr sub) { atomic_store(&size_, Size() - sub, memory_order_relaxed); } - - NOINLINE QuarantineBatch* AllocBatch(Callback cb) { - QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b)); - CHECK(b); - b->count = 0; - b->size = 0; - list_.push_back(b); - return b; - } }; } // namespace __sanitizer Index: lib/sanitizer_common/tests/CMakeLists.txt =================================================================== --- lib/sanitizer_common/tests/CMakeLists.txt +++ lib/sanitizer_common/tests/CMakeLists.txt @@ -26,6 +26,7 @@ sanitizer_posix_test.cc sanitizer_printf_test.cc sanitizer_procmaps_test.cc + sanitizer_quarantine_test.cc sanitizer_stackdepot_test.cc sanitizer_stacktrace_printer_test.cc sanitizer_stacktrace_test.cc Index: lib/sanitizer_common/tests/sanitizer_quarantine_test.cc =================================================================== --- /dev/null +++ lib/sanitizer_common/tests/sanitizer_quarantine_test.cc @@ -0,0 +1,151 @@ +//===-- sanitizer_quarantine_test.cc --------------------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file is a part of ThreadSanitizer/AddressSanitizer runtime. +// +//===----------------------------------------------------------------------===// +#include "sanitizer_common/sanitizer_common.h" +#include "sanitizer_common/sanitizer_quarantine.h" +#include "gtest/gtest.h" + +#include + +namespace __sanitizer { + +struct QuarantineCallback { + void Recycle(void *m) {} + void *Allocate(uptr size) { + return malloc(size); + } + void Deallocate(void *p) { + free(p); + } +}; + +typedef QuarantineCache Cache; + +static void* kFakePtr = reinterpret_cast(0xFA83FA83); +static const size_t kBlockSize = 8; + +static QuarantineCallback cb; + +static void DeallocateCache(Cache *cache) { + while (QuarantineBatch *batch = cache->DequeueBatch()) + cb.Deallocate(batch); +} + +TEST(SanitizerCommon, QuarantineBatchMerge) { + QuarantineBatch into; + QuarantineBatch from; + + // Verify the trivial case. + into.init(kFakePtr, 4UL); + from.init(kFakePtr, 8UL); + + into.merge(&from); + + ASSERT_EQ(into.count, 2UL); + ASSERT_EQ(into.quarantined_size(), 12UL); + + // Merge the batch to the limit. + for (uptr i = 3; i < QuarantineBatch::kSize; ++i) + from.push_back(kFakePtr, 8UL); + ASSERT_TRUE(into.count + from.count == QuarantineBatch::kSize); + ASSERT_TRUE(into.can_merge(&from)); + + into.merge(&from); + ASSERT_TRUE(into.count == QuarantineBatch::kSize); + + // No more space, not for one element. + from.init(kFakePtr, 8UL); + + ASSERT_FALSE(into.can_merge(&from)); +} + +TEST(SanitizerCommon, QuarantineCacheTransferEmpty) { + Cache into; + Cache from; + + ASSERT_EQ(into.Transfer(&from), nullptr); + ASSERT_EQ(into.Size(), 0UL); + ASSERT_EQ(into.DequeueBatch(), nullptr); +} + +TEST(SanitizerCommon, QuarantineCacheTransferOneBatch) { + Cache into; + Cache from; + + from.Enqueue(cb, kFakePtr, kBlockSize); + ASSERT_EQ(kBlockSize + sizeof(QuarantineBatch), from.Size()); + + // Batch ownership is transferred, nothing to deallocate. + ASSERT_EQ(into.Transfer(&from), nullptr); + ASSERT_EQ(kBlockSize + sizeof(QuarantineBatch), into.Size()); + ASSERT_EQ(0UL, from.Size()); + + DeallocateCache(&into); +} + +TEST(SanitizerCommon, QuarantineCacheTransferMergeBatches) { + Cache into; + Cache from; + + into.Enqueue(cb, kFakePtr, kBlockSize); + from.Enqueue(cb, kFakePtr, kBlockSize); + + // Batches merged, the "from" one should be deallocated. + QuarantineBatch *b = into.Transfer(&from); + ASSERT_NE(b, nullptr); + ASSERT_EQ(kBlockSize * 2 + sizeof(QuarantineBatch), into.Size()); + ASSERT_EQ(0UL, from.Size()); + + cb.Deallocate(b); + DeallocateCache(&into); +} + +TEST(SanitizerCommon, QuarantineCacheTransferTooBigToMergeBatches) { + Cache into; + Cache from; + + for (uptr i = 0; i < QuarantineBatch::kSize - 1; ++i) { + into.Enqueue(cb, kFakePtr, kBlockSize); + from.Enqueue(cb, kFakePtr, kBlockSize); + } + + // Batches cannot be merged. + ASSERT_EQ(into.Transfer(&from), nullptr); + ASSERT_EQ(kBlockSize * (QuarantineBatch::kSize - 1) * 2 + + sizeof(QuarantineBatch) * 2, into.Size()); + ASSERT_EQ(0UL, from.Size()); + + DeallocateCache(&into); +} + +TEST(SanitizerCommon, QuarantineCacheTransferTooManyToMergeBatches) { + Cache into; + Cache from; + + into.Enqueue(cb, kFakePtr, kBlockSize); + + for (uptr i = 0; i < QuarantineBatch::kSize + 1; ++i) + from.Enqueue(cb, kFakePtr, kBlockSize); + ASSERT_EQ(kBlockSize * (QuarantineBatch::kSize + 1) + + sizeof(QuarantineBatch) * 2, from.Size()); + + // Although both tail batches contain one element only, they are not going to + // be merged. + ASSERT_EQ(into.Transfer(&from), nullptr); + ASSERT_EQ(kBlockSize * (QuarantineBatch::kSize + 2) + + sizeof(QuarantineBatch) * 3, into.Size()); + ASSERT_EQ(0UL, from.Size()); + + DeallocateCache(&into); +} + +} // namespace __sanitizer Index: test/asan/TestCases/Linux/thread_local_quarantine_pthread_join.cc =================================================================== --- /dev/null +++ test/asan/TestCases/Linux/thread_local_quarantine_pthread_join.cc @@ -0,0 +1,48 @@ +// Test how creating and joining a lot of threads making only a few allocations +// each affect total quarantine (and overall heap) size. + +// RUN: %clangxx_asan %s -o %t +// RUN: %env_asan_opts=thread_local_quarantine_size_kb=64:quarantine_size_mb=64 %run %t 2>&1 | \ +// RUN: FileCheck %s --allow-empty --check-prefix=CHECK-SMALL-LOCAL-CACHE-SMALL-OVERHEAD +// RUN: %env_asan_opts=thread_local_quarantine_size_kb=0:quarantine_size_mb=64 %run %t 2>&1 | \ +// RUN: FileCheck %s --check-prefix=CHECK-NO-LOCAL-CACHE-SMALL-OVERHEAD + +#include +#include +#include +#include +#include + +// Thread local quarantine is merged to the global one when thread exits and +// such scenario (a few allocations per thread) used to generate a huge overhead +// of practically empty quarantine batches. Allocate about 5Mb of user memory +// total. +static const size_t kHeapSizeIncrementLimit = 12 << 20; +static const int kNumThreads = 1000; +static const int kAllocSize = 5000; + +void *ThreadFn(void *unused) { + char *temp = new char[kAllocSize]; + memset(temp, -1, kAllocSize); + delete [] (temp); + return NULL; +} + +int main() { + size_t heap_size = __sanitizer_get_heap_size(); + fprintf(stderr, "Heap size: %zd\n", heap_size); + + for (int i = 0; i < kNumThreads; i++) { + pthread_t t; + pthread_create(&t, 0, ThreadFn, 0); + pthread_join(t, 0); + } + + size_t new_heap_size = __sanitizer_get_heap_size(); + fprintf(stderr, "New heap size: %zd\n", new_heap_size); + if (new_heap_size - heap_size < kHeapSizeIncrementLimit) + fprintf(stderr, "Heap growth is within limits\n"); +} + +// CHECK-SMALL-LOCAL-CACHE-SMALL-OVERHEAD: Heap growth is within limits +// CHECK-NO-LOCAL-CACHE-SMALL-OVERHEAD: Heap growth is within limits Index: test/asan/TestCases/Linux/thread_local_quarantine_size_kb.cc =================================================================== --- test/asan/TestCases/Linux/thread_local_quarantine_size_kb.cc +++ test/asan/TestCases/Linux/thread_local_quarantine_size_kb.cc @@ -1,40 +1,42 @@ // Test thread_local_quarantine_size_kb // RUN: %clangxx_asan %s -o %t -// RUN: %env_asan_opts=thread_local_quarantine_size_kb=256:verbosity=1 %run %t 2>&1 | \ -// RUN: FileCheck %s --check-prefix=CHECK-VALUE -// RUN: %env_asan_opts=thread_local_quarantine_size_kb=64:quarantine_size_mb=64 %run %t 2>&1 | \ +// RUN: %env_asan_opts=thread_local_quarantine_size_kb=64:quarantine_size_mb=64:verbosity=1 %run %t 2>&1 | \ // RUN: FileCheck %s --allow-empty --check-prefix=CHECK-SMALL-LOCAL-CACHE-SMALL-OVERHEAD // RUN: %env_asan_opts=thread_local_quarantine_size_kb=0:quarantine_size_mb=64 %run %t 2>&1 | \ -// RUN: FileCheck %s --check-prefix=CHECK-NO-LOCAL-CACHE-HUGE-OVERHEAD +// RUN: FileCheck %s --check-prefix=CHECK-NO-LOCAL-CACHE-SMALL-OVERHEAD #include #include #include #include -// The idea is allocate a lot of small blocks, totaling 5Mb of user memory -// total, and verify that quarantine does not incur too much memory overhead. +// The idea is allocate a lot of small blocks, totaling 5Mb of user memory, +// and verify that quarantine does not incur too much memory overhead. // There's always an overhead for red zones, shadow memory and such, but // quarantine accounting should not significantly contribute to that. +// The zero sized thread local cache is specifically tested since it used to +// generate a huge overhead of almost empty quarantine batches. +static const size_t kHeapSizeIncrementLimit = 12 << 20; static const int kNumAllocs = 20000; static const int kAllocSize = 256; -static const size_t kHeapSizeLimit = 12 << 20; int main() { - size_t old_heap_size = __sanitizer_get_heap_size(); + size_t heap_size = __sanitizer_get_heap_size(); + fprintf(stderr, "Heap size: %zd\n", heap_size); + for (int i = 0; i < kNumAllocs; i++) { - char *g = new char[kAllocSize]; - memset(g, -1, kAllocSize); - delete [] (g); + char *temp = new char[kAllocSize]; + memset(temp, -1, kAllocSize); + delete [] (temp); } + size_t new_heap_size = __sanitizer_get_heap_size(); - fprintf(stderr, "heap size: new: %zd old: %zd\n", new_heap_size, - old_heap_size); - if (new_heap_size - old_heap_size > kHeapSizeLimit) - fprintf(stderr, "Heap size limit exceeded"); + fprintf(stderr, "New heap size: %zd\n", new_heap_size); + if (new_heap_size - heap_size < kHeapSizeIncrementLimit) + fprintf(stderr, "Heap growth is within limits\n"); } -// CHECK-VALUE: thread_local_quarantine_size_kb=256K -// CHECK-SMALL-LOCAL-CACHE-SMALL-OVERHEAD-NOT: Heap size limit exceeded -// CHECK-NO-LOCAL-CACHE-HUGE-OVERHEAD: Heap size limit exceeded +// CHECK-SMALL-LOCAL-CACHE-SMALL-OVERHEAD: thread_local_quarantine_size_kb=64K +// CHECK-SMALL-LOCAL-CACHE-SMALL-OVERHEAD: Heap growth is within limits +// CHECK-NO-LOCAL-CACHE-SMALL-OVERHEAD: Heap growth is within limits