1 files changed, 113 insertions, 29 deletions

diff --git a/lib/sanitizer_common/sanitizer_quarantine.h b/lib/sanitizer_common/sanitizer_quarantine.h
index 1a0d9545b7e1..db38867ced28 100644
--- a/lib/sanitizer_common/sanitizer_quarantine.h
+++ b/lib/sanitizer_common/sanitizer_quarantine.h
@@ -31,6 +31,40 @@ struct QuarantineBatch {
   uptr size;
   uptr count;
   void *batch[kSize];
+
+  void init(void *ptr, uptr size) {
+    count = 1;
+    batch[0] = ptr;
+    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(QuarantineBatch* const from) {
+    CHECK_LE(count + from->count, kSize);
+    CHECK_GE(size, sizeof(QuarantineBatch));
+
+    for (uptr i = 0; i < from->count; ++i)
+      batch[count + i] = from->batch[i];
+    count += from->count;
+    size += from->quarantined_size();
+
+    from->count = 0;
+    from->size = sizeof(QuarantineBatch);
+  }
 };
 
 COMPILER_CHECK(sizeof(QuarantineBatch) <= (1 << 13));  // 8Kb.
@@ -69,7 +103,7 @@ class Quarantine {
     if (cache_size) {
       c->Enqueue(cb, ptr, size);
     } else {
-      // cache_size == 0 only when size == 0 (see Init).
+      // GetCacheSize() == 0 only when GetSize() == 0 (see Init).
       cb.Recycle(ptr);
     }
     // Check cache size anyway to accommodate for runtime cache_size change.
@@ -88,6 +122,8 @@ class Quarantine {
 
   void PrintStats() const {
     // It assumes that the world is stopped, just as the allocator's PrintStats.
+    Printf("Quarantine limits: global: %zdMb; thread local: %zdKb\n",
+           GetSize() >> 20, GetCacheSize() >> 10);
     cache_.PrintStats();
   }
 
@@ -108,9 +144,27 @@ class Quarantine {
     uptr min_size = atomic_load(&min_size_, memory_order_relaxed);
     {
       SpinMutexLock l(&cache_mutex_);
+      // Go over the batches and merge partially filled ones to
+      // save some memory, otherwise batches themselves (since the memory used
+      // by them is counted against quarantine limit) can overcome the actual
+      // user's quarantined chunks, which diminishes the purpose of the
+      // quarantine.
+      uptr cache_size = cache_.Size();
+      uptr overhead_size = cache_.OverheadSize();
+      CHECK_GE(cache_size, overhead_size);
+      // Do the merge only when overhead exceeds this predefined limit (might
+      // require some tuning). It saves us merge attempt when the batch list
+      // quarantine is unlikely to contain batches suitable for merge.
+      const uptr kOverheadThresholdPercents = 100;
+      if (cache_size > overhead_size &&
+          overhead_size * (100 + kOverheadThresholdPercents) >
+              cache_size * kOverheadThresholdPercents) {
+        cache_.MergeBatches(&tmp);
+      }
+      // Extract enough chunks from the quarantine to get below the max
+      // quarantine size and leave some leeway for the newly quarantined chunks.
       while (cache_.Size() > min_size) {
-        QuarantineBatch *b = cache_.DequeueBatch();
-        tmp.EnqueueBatch(b);
+        tmp.EnqueueBatch(cache_.DequeueBatch());
       }
     }
     recycle_mutex_.Unlock();
@@ -145,26 +199,33 @@ class QuarantineCache {
     list_.clear();
   }
 
+  // Total memory used, including internal accounting.
   uptr Size() const {
     return atomic_load(&size_, memory_order_relaxed);
   }
 
+  // Memory used for internal accounting.
+  uptr OverheadSize() const {
+    return list_.size() * sizeof(QuarantineBatch);
+  }
+
   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);
+  void Transfer(QuarantineCache *from_cache) {
+    list_.append_back(&from_cache->list_);
+    SizeAdd(from_cache->Size());
+
+    atomic_store(&from_cache->size_, 0, memory_order_relaxed);
   }
 
   void EnqueueBatch(QuarantineBatch *b) {
@@ -181,19 +242,51 @@ class QuarantineCache {
     return b;
   }
 
+  void MergeBatches(QuarantineCache *to_deallocate) {
+    uptr extracted_size = 0;
+    QuarantineBatch *current = list_.front();
+    while (current && current->next) {
+      if (current->can_merge(current->next)) {
+        QuarantineBatch *extracted = current->next;
+        // Move all the chunks into the current batch.
+        current->merge(extracted);
+        CHECK_EQ(extracted->count, 0);
+        CHECK_EQ(extracted->size, sizeof(QuarantineBatch));
+        // Remove the next batch from the list and account for its size.
+        list_.extract(current, extracted);
+        extracted_size += extracted->size;
+        // Add it to deallocation list.
+        to_deallocate->EnqueueBatch(extracted);
+      } else {
+        current = current->next;
+      }
+    }
+    SizeSub(extracted_size);
+  }
+
   void PrintStats() const {
     uptr batch_count = 0;
-    uptr total_quarantine_bytes = 0;
+    uptr total_overhead_bytes = 0;
+    uptr total_bytes = 0;
     uptr total_quarantine_chunks = 0;
     for (List::ConstIterator it = list_.begin(); it != list_.end(); ++it) {
       batch_count++;
-      total_quarantine_bytes += (*it).size;
+      total_bytes += (*it).size;
+      total_overhead_bytes += (*it).size - (*it).quarantined_size();
       total_quarantine_chunks += (*it).count;
     }
-    Printf("Global quarantine stats: batches: %zd; bytes: %zd; chunks: %zd "
-           "(capacity: %zd chunks)\n",
-           batch_count, total_quarantine_bytes, total_quarantine_chunks,
-           batch_count * QuarantineBatch::kSize);
+    uptr quarantine_chunks_capacity = batch_count * QuarantineBatch::kSize;
+    int chunks_usage_percent = quarantine_chunks_capacity == 0 ?
+        0 : total_quarantine_chunks * 100 / quarantine_chunks_capacity;
+    uptr total_quarantined_bytes = total_bytes - total_overhead_bytes;
+    int memory_overhead_percent = total_quarantined_bytes == 0 ?
+        0 : total_overhead_bytes * 100 / total_quarantined_bytes;
+    Printf("Global quarantine stats: batches: %zd; bytes: %zd (user: %zd); "
+           "chunks: %zd (capacity: %zd); %d%% chunks used; %d%% memory overhead"
+           "\n",
+           batch_count, total_bytes, total_quarantined_bytes,
+           total_quarantine_chunks, quarantine_chunks_capacity,
+           chunks_usage_percent, memory_overhead_percent);
   }
 
  private:
@@ -208,15 +301,6 @@ class QuarantineCache {
   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