[scudo] Quarantine overhaul

Summary:
First, some context.

The main feedback we get about the quarantine is that it's too memory hungry.
A single MB of quarantine will have an impact of 3 to 4MB of PSS/RSS, and
things quickly get out of hand in terms of memory usage, and the quarantine
ends up disabled.

The main objective of the quarantine is to protect from use-after-free
exploitation by making it harder for an attacker to reallocate a controlled
chunk in place of the targeted freed chunk. This is achieved by not making it
available to the backend right away for reuse, but holding it a little while.

Historically, what has usually been the target of such attacks was objects,
where vtable pointers or other function pointers could constitute a valuable
targeti to replace. Those are usually on the smaller side. There is barely any
advantage in putting the quarantine several megabytes of RGB data or the like.

Now for the patch.

This patch introduces a new way the Quarantine behaves in Scudo. First of all,
the size of the Quarantine will be defined in KB instead of MB, then we
introduce a new option: the size up to which (lower than or equal to) a chunk
will be quarantined. This way, we only quarantine smaller chunks, and the size
of the quarantine remains manageable. It also prevents someone from triggering
a recycle by allocating something huge. We default to 512 bytes on 32-bit and
2048 bytes on 64-bit platforms.

In details, the patches includes the following:
- introduce `QuarantineSizeKb`, but honor `QuarantineSizeMb` if set to fall
  back to the old behavior (meaning no threshold in that case);
  `QuarantineSizeMb` is described as deprecated in the options descriptios;
  documentation update will follow;
- introduce `QuarantineChunksUpToSize`, the new threshold value;
- update the `quarantine.cpp` test, and other tests using `QuarantineSizeMb`;
- remove `AllocatorOptions::copyTo`, it wasn't used;
- slightly change the logic around `quarantineOrDeallocateChunk` to accomodate
  for the new logic; rename a couple of variables there as well;

Rewriting the tests, I found a somewhat annoying bug where non-default aligned
chunks would account for more than needed when placed in the quarantine due to
`<< MinAlignment` instead of `<< MinAlignmentLog`. This is fixed and tested for
now.

Reviewers: alekseyshl, kcc

Reviewed By: alekseyshl

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D35694

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@308884 91177308-0d34-0410-b5e6-96231b3b80d8

5 files changed, 154 insertions, 65 deletions

diff --git a/lib/scudo/scudo_allocator.cpp b/lib/scudo/scudo_allocator.cpp
index 6f30ee987..38522de4d 100644
--- a/lib/scudo/scudo_allocator.cpp
+++ b/lib/scudo/scudo_allocator.cpp
@@ -161,8 +161,9 @@ ScudoChunk *getScudoChunk(uptr UserBeg) {
 }
 
 struct AllocatorOptions {
-  u32 QuarantineSizeMb;
+  u32 QuarantineSizeKb;
   u32 ThreadLocalQuarantineSizeKb;
+  u32 QuarantineChunksUpToSize;
   bool MayReturnNull;
   s32 ReleaseToOSIntervalMs;
   bool DeallocationTypeMismatch;
@@ -170,29 +171,19 @@ struct AllocatorOptions {
   bool ZeroContents;
 
   void setFrom(const Flags *f, const CommonFlags *cf);
-  void copyTo(Flags *f, CommonFlags *cf) const;
 };
 
 void AllocatorOptions::setFrom(const Flags *f, const CommonFlags *cf) {
   MayReturnNull = cf->allocator_may_return_null;
   ReleaseToOSIntervalMs = cf->allocator_release_to_os_interval_ms;
-  QuarantineSizeMb = f->QuarantineSizeMb;
+  QuarantineSizeKb = f->QuarantineSizeKb;
   ThreadLocalQuarantineSizeKb = f->ThreadLocalQuarantineSizeKb;
+  QuarantineChunksUpToSize = f->QuarantineChunksUpToSize;
   DeallocationTypeMismatch = f->DeallocationTypeMismatch;
   DeleteSizeMismatch = f->DeleteSizeMismatch;
   ZeroContents = f->ZeroContents;
 }
 
-void AllocatorOptions::copyTo(Flags *f, CommonFlags *cf) const {
-  cf->allocator_may_return_null = MayReturnNull;
-  cf->allocator_release_to_os_interval_ms = ReleaseToOSIntervalMs;
-  f->QuarantineSizeMb = QuarantineSizeMb;
-  f->ThreadLocalQuarantineSizeKb = ThreadLocalQuarantineSizeKb;
-  f->DeallocationTypeMismatch = DeallocationTypeMismatch;
-  f->DeleteSizeMismatch = DeleteSizeMismatch;
-  f->ZeroContents = ZeroContents;
-}
-
 static void initScudoInternal(const AllocatorOptions &Options);
 
 static bool ScudoInitIsRunning = false;
@@ -292,6 +283,8 @@ struct ScudoAllocator {
   ScudoQuarantineCache FallbackQuarantineCache;
   ScudoPrng FallbackPrng;
 
+  u32 QuarantineChunksUpToSize;
+
   bool DeallocationTypeMismatch;
   bool ZeroContents;
   bool DeleteSizeMismatch;
@@ -337,8 +330,9 @@ struct ScudoAllocator {
     SetAllocatorMayReturnNull(Options.MayReturnNull);
     BackendAllocator.init(Options.ReleaseToOSIntervalMs);
     AllocatorQuarantine.Init(
-        static_cast<uptr>(Options.QuarantineSizeMb) << 20,
+        static_cast<uptr>(Options.QuarantineSizeKb) << 10,
         static_cast<uptr>(Options.ThreadLocalQuarantineSizeKb) << 10);
+    QuarantineChunksUpToSize = Options.QuarantineChunksUpToSize;
     GlobalPrng.init();
     Cookie = GlobalPrng.getU64();
     BackendAllocator.initCache(&FallbackAllocatorCache);
@@ -447,18 +441,17 @@ struct ScudoAllocator {
     return UserPtr;
   }
 
-  // Place a chunk in the quarantine. In the event of a zero-sized quarantine,
-  // we directly deallocate the chunk, otherwise the flow would lead to the
-  // chunk being loaded (and checked) twice, and stored (and checksummed) once,
-  // with no additional security value.
+  // Place a chunk in the quarantine or directly deallocate it in the event of
+  // a zero-sized quarantine, or if the size of the chunk is greater than the
+  // quarantine chunk size threshold.
   void quarantineOrDeallocateChunk(ScudoChunk *Chunk, UnpackedHeader *Header,
                                    uptr Size) {
-    bool FromPrimary = Header->FromPrimary;
-    bool BypassQuarantine = (AllocatorQuarantine.GetCacheSize() == 0);
+    const bool BypassQuarantine = (AllocatorQuarantine.GetCacheSize() == 0) ||
+        (Size > QuarantineChunksUpToSize);
     if (BypassQuarantine) {
       Chunk->eraseHeader();
       void *Ptr = Chunk->getAllocBeg(Header);
-      if (FromPrimary) {
+      if (Header->FromPrimary) {
         ScudoThreadContext *ThreadContext = getThreadContextAndLock();
         if (LIKELY(ThreadContext)) {
           getBackendAllocator().deallocatePrimary(
@@ -472,6 +465,12 @@ struct ScudoAllocator {
         getBackendAllocator().deallocateSecondary(Ptr);
       }
     } else {
+      // If a small memory amount was allocated with a larger alignment, we want
+      // to take that into account. Otherwise the Quarantine would be filled
+      // with tiny chunks, taking a lot of VA memory. This is an approximation
+      // of the usable size, that allows us to not call
+      // GetActuallyAllocatedSize.
+      uptr EstimatedSize = Size + (Header->Offset << MinAlignmentLog);
       UnpackedHeader NewHeader = *Header;
       NewHeader.State = ChunkQuarantine;
       Chunk->compareExchangeHeader(&NewHeader, Header);
@@ -480,13 +479,13 @@ struct ScudoAllocator {
         AllocatorQuarantine.Put(getQuarantineCache(ThreadContext),
                                 QuarantineCallback(
                                     getAllocatorCache(ThreadContext)),
-                                Chunk, Size);
+                                Chunk, EstimatedSize);
         ThreadContext->unlock();
       } else {
         SpinMutexLock l(&FallbackMutex);
         AllocatorQuarantine.Put(&FallbackQuarantineCache,
                                 QuarantineCallback(&FallbackAllocatorCache),
-                                Chunk, Size);
+                                Chunk, EstimatedSize);
       }
     }
   }
@@ -504,37 +503,31 @@ struct ScudoAllocator {
                      "aligned at address %p\n", UserPtr);
     }
     ScudoChunk *Chunk = getScudoChunk(UserBeg);
-    UnpackedHeader OldHeader;
-    Chunk->loadHeader(&OldHeader);
-    if (UNLIKELY(OldHeader.State != ChunkAllocated)) {
+    UnpackedHeader Header;
+    Chunk->loadHeader(&Header);
+    if (UNLIKELY(Header.State != ChunkAllocated)) {
       dieWithMessage("ERROR: invalid chunk state when deallocating address "
                      "%p\n", UserPtr);
     }
     if (DeallocationTypeMismatch) {
       // The deallocation type has to match the allocation one.
-      if (OldHeader.AllocType != Type) {
+      if (Header.AllocType != Type) {
         // With the exception of memalign'd Chunks, that can be still be free'd.
-        if (OldHeader.AllocType != FromMemalign || Type != FromMalloc) {
+        if (Header.AllocType != FromMemalign || Type != FromMalloc) {
           dieWithMessage("ERROR: allocation type mismatch on address %p\n",
                          UserPtr);
         }
       }
     }
-    uptr Size = OldHeader.FromPrimary ? OldHeader.SizeOrUnusedBytes :
-        Chunk->getUsableSize(&OldHeader) - OldHeader.SizeOrUnusedBytes;
+    uptr Size = Header.FromPrimary ? Header.SizeOrUnusedBytes :
+        Chunk->getUsableSize(&Header) - Header.SizeOrUnusedBytes;
     if (DeleteSizeMismatch) {
       if (DeleteSize && DeleteSize != Size) {
         dieWithMessage("ERROR: invalid sized delete on chunk at address %p\n",
                        UserPtr);
       }
     }
-
-    // If a small memory amount was allocated with a larger alignment, we want
-    // to take that into account. Otherwise the Quarantine would be filled with
-    // tiny chunks, taking a lot of VA memory. This is an approximation of the
-    // usable size, that allows us to not call GetActuallyAllocatedSize.
-    uptr LiableSize = Size + (OldHeader.Offset << MinAlignment);
-    quarantineOrDeallocateChunk(Chunk, &OldHeader, LiableSize);
+    quarantineOrDeallocateChunk(Chunk, &Header, Size);
   }
 
   // Reallocates a chunk. We can save on a new allocation if the new requested
@@ -575,7 +568,7 @@ struct ScudoAllocator {
       uptr OldSize = OldHeader.FromPrimary ? OldHeader.SizeOrUnusedBytes :
           UsableSize - OldHeader.SizeOrUnusedBytes;
       memcpy(NewPtr, OldPtr, Min(NewSize, OldSize));
-      quarantineOrDeallocateChunk(Chunk, &OldHeader, UsableSize);
+      quarantineOrDeallocateChunk(Chunk, &OldHeader, OldSize);
     }
     return NewPtr;
   }
diff --git a/lib/scudo/scudo_flags.cpp b/lib/scudo/scudo_flags.cpp
index 90f0cbf4b..ab94afac9 100644
--- a/lib/scudo/scudo_flags.cpp
+++ b/lib/scudo/scudo_flags.cpp
@@ -67,27 +67,52 @@ void initFlags() {
 
   // Sanity checks and default settings for the Quarantine parameters.
 
-  if (f->QuarantineSizeMb < 0) {
-    const int DefaultQuarantineSizeMb = FIRST_32_SECOND_64(4, 16);
-    f->QuarantineSizeMb = DefaultQuarantineSizeMb;
+  if (f->QuarantineSizeMb >= 0) {
+    // Backward compatible logic if QuarantineSizeMb is set.
+    if (f->QuarantineSizeKb >= 0) {
+      dieWithMessage("ERROR: please use either QuarantineSizeMb (deprecated) "
+          "or QuarantineSizeKb, but not both\n");
+    }
+    if (f->QuarantineChunksUpToSize >= 0) {
+      dieWithMessage("ERROR: QuarantineChunksUpToSize cannot be used in "
+          " conjunction with the deprecated QuarantineSizeMb option\n");
+    }
+    // If everything is in order, update QuarantineSizeKb accordingly.
+    f->QuarantineSizeKb = f->QuarantineSizeMb * 1024;
+  } else {
+    // Otherwise proceed with the new options.
+    if (f->QuarantineSizeKb < 0) {
+      const int DefaultQuarantineSizeKb = FIRST_32_SECOND_64(64, 256);
+      f->QuarantineSizeKb = DefaultQuarantineSizeKb;
+    }
+    if (f->QuarantineChunksUpToSize < 0) {
+      const int DefaultQuarantineChunksUpToSize = FIRST_32_SECOND_64(512, 2048);
+      f->QuarantineChunksUpToSize = DefaultQuarantineChunksUpToSize;
+    }
   }
-  // We enforce an upper limit for the quarantine size of 4Gb.
-  if (f->QuarantineSizeMb > (4 * 1024)) {
+
+  // We enforce an upper limit for the chunk quarantine threshold of 4Mb.
+  if (f->QuarantineChunksUpToSize > (4 * 1024 * 1024)) {
+    dieWithMessage("ERROR: the chunk quarantine threshold is too large\n");
+  }
+
+  // We enforce an upper limit for the quarantine size of 32Mb.
+  if (f->QuarantineSizeKb > (32 * 1024)) {
     dieWithMessage("ERROR: the quarantine size is too large\n");
   }
+
   if (f->ThreadLocalQuarantineSizeKb < 0) {
-    const int DefaultThreadLocalQuarantineSizeKb =
-        FIRST_32_SECOND_64(64, 256);
+    const int DefaultThreadLocalQuarantineSizeKb = FIRST_32_SECOND_64(16, 64);
     f->ThreadLocalQuarantineSizeKb = DefaultThreadLocalQuarantineSizeKb;
   }
-  // And an upper limit of 128Mb for the thread quarantine cache.
-  if (f->ThreadLocalQuarantineSizeKb > (128 * 1024)) {
+  // And an upper limit of 8Mb for the thread quarantine cache.
+  if (f->ThreadLocalQuarantineSizeKb > (8 * 1024)) {
     dieWithMessage("ERROR: the per thread quarantine cache size is too "
-                   "large\n");
+        "large\n");
   }
-  if (f->ThreadLocalQuarantineSizeKb == 0 && f->QuarantineSizeMb > 0) {
+  if (f->ThreadLocalQuarantineSizeKb == 0 && f->QuarantineSizeKb > 0) {
     dieWithMessage("ERROR: ThreadLocalQuarantineSizeKb can be set to 0 only "
-                   "when QuarantineSizeMb is set to 0\n");
+        "when QuarantineSizeKb is set to 0\n");
   }
 }
 
diff --git a/lib/scudo/scudo_flags.inc b/lib/scudo/scudo_flags.inc
index 45f9ea846..f180478fd 100644
--- a/lib/scudo/scudo_flags.inc
+++ b/lib/scudo/scudo_flags.inc
@@ -15,17 +15,27 @@
 # error "Define SCUDO_FLAG prior to including this file!"
 #endif
 
-// Default value is set in scudo_flags.cpp based on architecture.
 SCUDO_FLAG(int, QuarantineSizeMb, -1,
-           "Size (in Mb) of quarantine used to delay the actual deallocation "
-           "of chunks. Lower value may reduce memory usage but decrease the "
-           "effectiveness of the mitigation.")
+           "Deprecated. Please use QuarantineSizeKb.")
+
+// Default value is set in scudo_flags.cpp based on architecture.
+SCUDO_FLAG(int, QuarantineSizeKb, -1,
+           "Size in KB of quarantine used to delay the actual deallocation of "
+           "chunks. Lower value may reduce memory usage but decrease the "
+           "effectiveness of the mitigation. Defaults to 64KB (32-bit) or "
+           "256KB (64-bit)")
 
 // Default value is set in scudo_flags.cpp based on architecture.
 SCUDO_FLAG(int, ThreadLocalQuarantineSizeKb, -1,
-          "Size (in Kb) of per-thread cache used to offload the global "
+          "Size in KB of per-thread cache used to offload the global "
           "quarantine. Lower value may reduce memory usage but might increase "
-          "the contention on the global quarantine.")
+          "the contention on the global quarantine. Defaults to 16KB (32-bit) "
+          "or 64KB (64-bit)")
+
+// Default value is set in scudo_flags.cpp based on architecture.
+SCUDO_FLAG(int, QuarantineChunksUpToSize, -1,
+          "Size in bytes up to which chunks will be quarantined (if lower than"
+          "or equal to). Defaults to 256 (32-bit) or 2048 (64-bit)")
 
 SCUDO_FLAG(bool, DeallocationTypeMismatch, true,
           "Report errors on malloc/delete, new/free, new/delete[], etc.")
diff --git a/test/scudo/overflow.cpp b/test/scudo/overflow.cpp
index d12824578..82ea10fd1 100644
--- a/test/scudo/overflow.cpp
+++ b/test/scudo/overflow.cpp
@@ -1,6 +1,6 @@
 // RUN: %clang_scudo %s -o %t
-// RUN:                                  not %run %t malloc     2>&1 | FileCheck %s
-// RUN: SCUDO_OPTIONS=QuarantineSizeMb=1 not %run %t quarantine 2>&1 | FileCheck %s
+// RUN:                                   not %run %t malloc     2>&1 | FileCheck %s
+// RUN: SCUDO_OPTIONS=QuarantineSizeKb=64 not %run %t quarantine 2>&1 | FileCheck %s
 
 // Tests that header corruption of an allocated or quarantined chunk is caught.
 
@@ -29,7 +29,7 @@ int main(int argc, char **argv)
     ((char *)p)[-(offset + 2)] ^= 1;
     // Trigger the quarantine recycle
     for (int i = 0; i < 0x100; i++) {
-      p = malloc(1U << 16);
+      p = malloc(1U << 8);
       free(p);
     }
   }
diff --git a/test/scudo/quarantine.cpp b/test/scudo/quarantine.cpp
index 39ce1bd91..cfa9aa919 100644
--- a/test/scudo/quarantine.cpp
+++ b/test/scudo/quarantine.cpp
@@ -1,10 +1,15 @@
 // RUN: %clang_scudo %s -o %t
-// RUN: SCUDO_OPTIONS="QuarantineSizeMb=0:ThreadLocalQuarantineSizeKb=0" %run %t zeroquarantine 2>&1
-// RUN: SCUDO_OPTIONS=QuarantineSizeMb=1                                 %run %t smallquarantine 2>&1
+// RUN: SCUDO_OPTIONS="QuarantineSizeMb=1:QuarantineSizeKb=64"           not %run %t unused 2>&1
+// RUN: SCUDO_OPTIONS="QuarantineSizeMb=1:QuarantineChunksUpToSize=256"  not %run %t unused 2>&1
+// RUN: SCUDO_OPTIONS="QuarantineSizeKb=0:ThreadLocalQuarantineSizeKb=0"     %run %t zeroquarantine 2>&1
+// RUN: SCUDO_OPTIONS=QuarantineSizeKb=64                                    %run %t smallquarantine 2>&1
+// RUN: SCUDO_OPTIONS=QuarantineChunksUpToSize=256                           %run %t threshold 2>&1
+// RUN: SCUDO_OPTIONS="QuarantineSizeMb=1"                                   %run %t oldquarantine 2>&1
 
 // Tests that the quarantine prevents a chunk from being reused right away.
 // Also tests that a chunk will eventually become available again for
-// allocation when the recycling criteria has been met.
+// allocation when the recycling criteria has been met. Finally, tests the
+// threshold up to which a chunk is quarantine, and the old quarantine behavior.
 
 #include <assert.h>
 #include <malloc.h>
@@ -16,9 +21,16 @@
 int main(int argc, char **argv)
 {
   void *p, *old_p;
-  size_t allocated_bytes, size = 1U << 16;
+  size_t allocated_bytes, size = 1U << 8, alignment = 1U << 8;
 
   assert(argc == 2);
+  // First, warm up the allocator for the classes used.
+  p = malloc(size);
+  assert(p);
+  free(p);
+  assert(posix_memalign(&p, alignment, size) == 0);
+  assert(p);
+  free(p);
 
   if (!strcmp(argv[1], "zeroquarantine")) {
     // Verifies that a chunk is deallocated right away when the local and
@@ -44,13 +56,62 @@ int main(int argc, char **argv)
 
     // Eventually the chunk should become available again.
     bool found = false;
-    for (int i = 0; i < 0x100 && found == false; i++) {
+    for (int i = 0; i < 0x200 && !found; i++) {
       p = malloc(size);
       assert(p);
       found = (p == old_p);
       free(p);
     }
-    assert(found == true);
+    assert(found);
+  }
+  if (!strcmp(argv[1], "threshold")) {
+    // Verifies that a chunk of size greater than the threshold will be freed
+    // right away. Alignment has no impact on the threshold.
+    allocated_bytes = __sanitizer_get_current_allocated_bytes();
+    p = malloc(size + 1);
+    assert(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() == allocated_bytes);
+    assert(posix_memalign(&p, alignment, size + 1) == 0);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() == allocated_bytes);
+    // Verifies that a chunk of size lower or equal to the threshold will be
+    // quarantined.
+    p = malloc(size);
+    assert(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    allocated_bytes = __sanitizer_get_current_allocated_bytes();
+    assert(posix_memalign(&p, alignment, size) == 0);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+  }
+  if (!strcmp(argv[1], "oldquarantine")) {
+    // Verifies that we quarantine everything if the deprecated quarantine
+    // option is specified. Alignment has no impact on the threshold.
+    allocated_bytes = __sanitizer_get_current_allocated_bytes();
+    p = malloc(size);
+    assert(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    allocated_bytes = __sanitizer_get_current_allocated_bytes();
+    assert(posix_memalign(&p, alignment, size) == 0);
+    assert(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    // Secondary backed allocation.
+    allocated_bytes = __sanitizer_get_current_allocated_bytes();
+    p = malloc(1U << 19);
+    assert(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
+    free(p);
+    assert(__sanitizer_get_current_allocated_bytes() > allocated_bytes);
   }
 
   return 0;