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

150

nullptr

166

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

151

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?

79

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

struct QuarantineBatch {
   QuarantineBatch *next;
   uptr size;
   uptr count;
   void *batch[kSize];
 };
 
 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);
 template<typename Callback, typename Node>
 class Quarantine {
  public:
   typedef QuarantineCache<Callback> Cache;
 
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_;
void Enqueue(Callback cb, void *ptr, uptr 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 ||
+        from_cache->list_.front()->count + list_.back()->count >
+            QuarantineBatch::kSize) {
+      // 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.
+      QuarantineBatch *from_batch = from_cache->list_.front();
+      from_cache->list_.pop_front();
+      QuarantineBatch *to_batch = list_.back();
+      for (uptr i = 0; i < from_batch->count; ++i)
+        to_batch->batch[to_batch->count + i] = from_batch->batch[i];
+      to_batch->count += from_batch->count;
+      CHECK_GT(from_batch->size, sizeof(QuarantineBatch));
+      uptr transferred_nodes_size = from_batch->size - sizeof(QuarantineBatch);
+      to_batch->size += transferred_nodes_size;
+      SizeAdd(transferred_nodes_size);
+      batch_to_deallocate = from_batch;
+    }
+    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() {

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 <pthread.h>
 #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.
+static const size_t kHeapSizeIncrementLimit = 10 << 20;
+
+void AllocateUseAndFree(size_t size_bytes) {
+  char *temp = new char[size_bytes];
+  memset(temp, -1, size_bytes);
+  delete [] (temp);
+}
+
+// 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.
-static const int kNumAllocs = 20000;
-static const int kAllocSize = 256;
-static const size_t kHeapSizeLimit = 12 << 20;
+// The zero sized thread local cache is specifically tested since it used to
+// generate a huge overhead of almost empty quarantine batches.
+void AllocateALotOfSmallBloksInTheSameThread() {
+  for (int i = 0; i < 20000; i++)
+    AllocateUseAndFree(256);
+}
 
-int main() {
-  size_t old_heap_size = __sanitizer_get_heap_size();
-  for (int i = 0; i < kNumAllocs; i++) {
-    char *g = new char[kAllocSize];
-    memset(g, -1, kAllocSize);
-    delete [] (g);
-  }
+// 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 the same 5Mb of user
+// memory total.
+void *ThreadFn(void *unused) {
+  AllocateUseAndFree(5000);
+  return NULL;
+}
+
+void ALotOfThreadsOneAllocationPerThread() {
+  for (int i = 0; i < 1000; i++) {
+    pthread_t t;
+    pthread_create(&t, 0, ThreadFn, 0);
+    pthread_join(t, 0);
+  }
+
+int main() {
+  size_t heap_size = __sanitizer_get_heap_size();
+  fprintf(stderr, "Heap size: %zd\n", heap_size);
+
+  AllocateALotOfSmallBloksInTheSameThread();
   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 size increment limit exceeded: %zd\n", new_heap_size);
+  heap_size = new_heap_size;
+
+  ALotOfThreadsOneAllocationPerThread();
+  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 size increment limit exceeded: %zd\n", new_heap_size);
+  heap_size = new_heap_size;
 }
 
-// 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-NOT: Heap size increment limit exceeded
+// CHECK-NO-LOCAL-CACHE-SMALL-OVERHEAD-NOT: Heap size increment limit exceeded