Whenever reasonable, merge ASAN quarantine batches to save memory.

[alekseyshl]

Summary

There are cases when thread local quarantine drains almost empty
quarantine batches into the global quarantine. The current approach leaves
them almost empty, which might create a huge memory overhead (each batch
is 4K/8K, depends on bitness).

[eugenis]

LGTM

lib/sanitizer_common/sanitizer_quarantine.h

180

nullptr

196

DequeueBatch unnecessarily updates from_cache size. Could you use from_cache->list_.front() instead?

[alekseyshl]

• Address comments.

[alekseyshl]

PTAL

[eugenis]

LGTM, but please wait for a review from Kostya

[kcc]

Is there any noticeable gain from this change other than in the case where quarantine_size_mb is 0?
I don't want to introduce this extra complexity unless there is a real gain.
And quarantine_size_mb=0 should simply bypass the quarantine (if we care about this corner case)

[eugenis]

As I understand, small-but-not-zero local quarantine cache size would trigger the bad behavior without this change.

[alekseyshl]

• Address comments.
• Add a test to verify "one allocation per thread" scenario.

[alekseyshl]

Not just the small thread local quarantine size can create a lot of almost empty quarantine blocks, it can also happen joining a lot of threads which happen to make only a few allocations during their lifetime.

[kcc]

lib/sanitizer_common/sanitizer_quarantine.h

181

is it possible to make a separate function for this part of code and then unit test it?
(Something like bool Merge(QuarantineBatch *into, QuarantineBatch *from))

test/asan/TestCases/Linux/thread_local_quarantine_size_kb.cc

1

I would suggest to leave this test (mostly?) unchanged and create a new one.

[alekseyshl]

• Address comments.
• Add a test to verify "one allocation per thread" scenario.
• Add unit test for SanitizerQuarantine batch transfers.

[alekseyshl]

Done

[alekseyshl]

• Add dropped out line back.

[alekseyshl]

• Address comments.
• Add a test to verify "one allocation per thread" scenario.
• Add unit test for SanitizerQuarantine batch transfers.
• Add dropped out line back.
• Merge quarantine blocks on Recycle, not on Put.

[alekseyshl]

PTAL

Doing even minimal work under cache spin lock on Put proven to be too slow in certain conditions (many threads, many allocations). The spin lock contention hits slow path (__sanitizer::internal_sched_yield()) and context switch results in dramatically slower execution (up to 20x slowdown observed in tests).

[eugenis]

lib/sanitizer_common/sanitizer_quarantine.h

38

would it make the code simpler if we removed sizeof(QuarantineBatch) from here?

109

s/options/limits

[alekseyshl]

lib/sanitizer_common/sanitizer_quarantine.h

38

I guess, you mean to do not account for the quarantine batch size here and calculate the overhead every time we check whether the quarantine limit is reached? It will simplify the code a little bit, but we will have to perform this calculation on every Put() call or, if we still going to roll it into size_, EnqueueBatch, DequeueBatch and MergeBatches will have to be aware of it (not that great too).

[alekseyshl]

• Message text changes

[eugenis]

LGTM

lib/sanitizer_common/sanitizer_quarantine.h

38

OK. Does not really matter.

lib/sanitizer_common/sanitizer_quarantine.h

 template<typename Node> class QuarantineCache;
 
 struct QuarantineBatch {
   static const uptr kSize = 1021;
   QuarantineBatch *next;
   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.
 
 // The callback interface is:
 // void Callback::Recycle(Node *ptr);
 // void *cb.Allocate(uptr size);
 // void cb.Deallocate(void *ptr);
public:
 
   void Put(Cache *c, Callback cb, Node *ptr, uptr size) {
     c->Enqueue(cb, ptr, size);
     if (c->Size() > max_cache_size_)
       Drain(c, cb);
   }
 
   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);
   }
 
  private:
   // Read-only data.
   char pad0_[kCacheLineSize];
   atomic_uintptr_t max_size_;
   atomic_uintptr_t min_size_;
   uptr max_cache_size_;
   char pad1_[kCacheLineSize];
   SpinMutex cache_mutex_;
   SpinMutex recycle_mutex_;
public:
   }
 
   uptr Size() const {
     return atomic_load(&size_, memory_order_relaxed);
   }
 
   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 = list_.back();
+      QuarantineBatch *b = (QuarantineBatch *)cb.Allocate(sizeof(*b));
       CHECK(b);
-    b->batch[b->count++] = ptr;
-    b->size += size;
+      b->init(ptr, size);
+      EnqueueBatch(b);
+    } else {
+      list_.back()->push_back(ptr, 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) {
     list_.push_back(b);
     SizeAdd(b->size);
   }
 
   QuarantineBatch *DequeueBatch() {
private:
   atomic_uintptr_t size_;
 
   void SizeAdd(uptr add) {
     atomic_store(&size_, Size() + add, memory_order_relaxed);
   }
   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
 
 #endif // SANITIZER_QUARANTINE_H

lib/sanitizer_common/tests/CMakeLists.txt

set(SANITIZER_UNITTESTS
   sanitizer_libc_test.cc
   sanitizer_linux_test.cc
   sanitizer_list_test.cc
   sanitizer_mutex_test.cc
   sanitizer_nolibc_test.cc
   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
   sanitizer_stoptheworld_test.cc
   sanitizer_suppressions_test.cc
   sanitizer_symbolizer_test.cc
   sanitizer_test_main.cc
   sanitizer_thread_registry_test.cc)

lib/sanitizer_common/tests/sanitizer_quarantine_test.cc

+//===-- 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 <stdlib.h>
+
+namespace __sanitizer {
+
+struct QuarantineCallback {
+  void Recycle(void *m) {}
+  void *Allocate(uptr size) {
+    return malloc(size);
+  }
+  void Deallocate(void *p) {
+    free(p);
+  }
+};
+
+typedef QuarantineCache<QuarantineCallback> Cache;
+
+static void* kFakePtr = reinterpret_cast<void*>(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

test/asan/TestCases/Linux/thread_local_quarantine_pthread_join.cc

+// 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 <pthread.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sanitizer/allocator_interface.h>
+
+// 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

test/asan/TestCases/Linux/thread_local_quarantine_size_kb.cc

 // 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 <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <sanitizer/allocator_interface.h>
 
-// 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