[asan] first attempt at releasing free-d memory back to the system using madvise. Requires quite some tuning.

llvm-svn: 279887

9 files changed, 123 insertions, 22 deletions

diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h b/compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h
index dceb64bbd3f..2c8e2a2bbd3 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_allocator_combined.h
@@ -190,6 +190,8 @@ class CombinedAllocator {
     primary_.ForceUnlock();
   }
 
+  void ReleaseToOS() { primary_.ReleaseToOS(); }
+
   // Iterate over all existing chunks.
   // The allocator must be locked when calling this function.
   void ForEachChunk(ForEachChunkCallback callback, void *arg) {
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h b/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h
index 6aec1828d2d..9e23099aec4 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary32.h
@@ -231,6 +231,10 @@ class SizeClassAllocator32 {
     return 0;
   }
 
+  // This is empty here. Currently only implemented in 64-bit allocator.
+  void ReleaseToOS() { }
+
+
   typedef SizeClassMap SizeClassMapT;
   static const uptr kNumClasses = SizeClassMap::kNumClasses;
 
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary64.h b/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary64.h
index 2af2684dac1..deaa03e31a8 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary64.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_allocator_primary64.h
@@ -61,11 +61,12 @@ class SizeClassAllocator64 {
   // When we know the size class (the region base) we can represent a pointer
   // as a 4-byte integer (offset from the region start shifted right by 4).
   typedef u32 CompactPtrT;
+  static const uptr kCompactPtrScale = 4;
   CompactPtrT PointerToCompactPtr(uptr base, uptr ptr) {
-    return static_cast<CompactPtrT>((ptr - base) >> 4);
+    return static_cast<CompactPtrT>((ptr - base) >> kCompactPtrScale);
   }
   uptr CompactPtrToPointer(uptr base, CompactPtrT ptr32) {
-    return base + (static_cast<uptr>(ptr32) << 4);
+    return base + (static_cast<uptr>(ptr32) << kCompactPtrScale);
   }
 
   void Init() {
@@ -109,6 +110,7 @@ class SizeClassAllocator64 {
     for (uptr i = 0; i < n_chunks; i++)
       free_array[old_num_chunks + i] = chunks[i];
     region->num_freed_chunks = new_num_freed_chunks;
+    region->n_freed += n_chunks;
   }
 
   NOINLINE void GetFromAllocator(AllocatorStats *stat, uptr class_id,
@@ -127,6 +129,7 @@ class SizeClassAllocator64 {
     uptr base_idx = region->num_freed_chunks;
     for (uptr i = 0; i < n_chunks; i++)
       chunks[i] = free_array[base_idx + i];
+    region->n_allocated += n_chunks;
   }
 
 
@@ -206,6 +209,21 @@ class SizeClassAllocator64 {
         stats[class_id] = rss;
   }
 
+  void PrintStats(uptr class_id, uptr rss) {
+    RegionInfo *region = GetRegionInfo(class_id);
+    if (region->mapped_user == 0) return;
+    uptr in_use = region->n_allocated - region->n_freed;
+    uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);
+    Printf(
+        "  %02zd (%zd): mapped: %zdK allocs: %zd frees: %zd inuse: %zd "
+        "num_freed_chunks %zd"
+        " avail: %zd rss: %zdK releases: %zd\n",
+        class_id, ClassIdToSize(class_id), region->mapped_user >> 10,
+        region->n_allocated, region->n_freed, in_use,
+        region->num_freed_chunks, avail_chunks, rss >> 10,
+        region->rtoi.num_releases);
+  }
+
   void PrintStats() {
     uptr total_mapped = 0;
     uptr n_allocated = 0;
@@ -223,21 +241,8 @@ class SizeClassAllocator64 {
     for (uptr class_id = 0; class_id < kNumClasses; class_id++)
       rss_stats[class_id] = SpaceBeg() + kRegionSize * class_id;
     GetMemoryProfile(FillMemoryProfile, rss_stats, kNumClasses);
-    for (uptr class_id = 1; class_id < kNumClasses; class_id++) {
-      RegionInfo *region = GetRegionInfo(class_id);
-      if (region->mapped_user == 0) continue;
-      uptr in_use = region->n_allocated - region->n_freed;
-      uptr avail_chunks = region->allocated_user / ClassIdToSize(class_id);
-      Printf("  %02zd (%zd): mapped: %zdK allocs: %zd frees: %zd inuse: %zd"
-             " avail: %zd rss: %zdK\n",
-             class_id,
-             ClassIdToSize(class_id),
-             region->mapped_user >> 10,
-             region->n_allocated,
-             region->n_freed,
-             in_use, avail_chunks,
-             rss_stats[class_id] >> 10);
-    }
+    for (uptr class_id = 1; class_id < kNumClasses; class_id++)
+      PrintStats(class_id, rss_stats[class_id]);
   }
 
   // ForceLock() and ForceUnlock() are needed to implement Darwin malloc zone
@@ -279,6 +284,11 @@ class SizeClassAllocator64 {
                      GetPageSizeCached());
   }
 
+  void ReleaseToOS() {
+    for (uptr class_id = 1; class_id < kNumClasses; class_id++)
+      ReleaseToOS(class_id);
+  }
+
   typedef SizeClassMap SizeClassMapT;
   static const uptr kNumClasses = SizeClassMap::kNumClasses;
   static const uptr kNumClassesRounded = SizeClassMap::kNumClassesRounded;
@@ -307,6 +317,13 @@ class SizeClassAllocator64 {
   static const uptr kMetaMapSize = 1 << 16;
   // Call mmap for free array memory with at least this size.
   static const uptr kFreeArrayMapSize = 1 << 16;
+  // Granularity of ReleaseToOs (aka madvise).
+  static const uptr kReleaseToOsGranularity = 1 << 12;
+
+  struct ReleaseToOsInfo {
+    uptr n_freed_at_last_release;
+    uptr num_releases;
+  };
 
   struct RegionInfo {
     BlockingMutex mutex;
@@ -318,6 +335,7 @@ class SizeClassAllocator64 {
     uptr mapped_meta;  // Bytes mapped for metadata.
     u32 rand_state; // Seed for random shuffle, used if kRandomShuffleChunks.
     uptr n_allocated, n_freed;  // Just stats.
+    ReleaseToOsInfo rtoi;
   };
   COMPILER_CHECK(sizeof(RegionInfo) >= kCacheLineSize);
 
@@ -430,6 +448,59 @@ class SizeClassAllocator64 {
       Die();
     }
   }
+
+  bool MaybeReleaseChunkRange(uptr region_beg, uptr chunk_size,
+                              CompactPtrT first, CompactPtrT last) {
+    uptr beg_ptr = CompactPtrToPointer(region_beg, first);
+    uptr end_ptr = CompactPtrToPointer(region_beg, last) + chunk_size;
+    CHECK_GE(end_ptr - beg_ptr, kReleaseToOsGranularity);
+    beg_ptr = RoundUpTo(beg_ptr, kReleaseToOsGranularity);
+    end_ptr = RoundDownTo(end_ptr, kReleaseToOsGranularity);
+    if (end_ptr == beg_ptr) return false;
+    ReleaseMemoryToOS(beg_ptr, end_ptr - beg_ptr);
+    return true;
+  }
+
+  // Releases some RAM back to OS.
+  // Algorithm:
+  // * Lock the region.
+  // * Sort the chunks.
+  // * Find ranges fully covered by free-d chunks
+  // * Release them to OS with madvise.
+  //
+  // TODO(kcc): make sure we don't do it too frequently.
+  void ReleaseToOS(uptr class_id) {
+    RegionInfo *region = GetRegionInfo(class_id);
+    uptr region_beg = GetRegionBeginBySizeClass(class_id);
+    CompactPtrT *free_array = GetFreeArray(region_beg);
+    uptr chunk_size = ClassIdToSize(class_id);
+    uptr scaled_chunk_size = chunk_size >> kCompactPtrScale;
+    const uptr kScaledGranularity = kReleaseToOsGranularity >> kCompactPtrScale;
+    BlockingMutexLock l(&region->mutex);
+    uptr n = region->num_freed_chunks;
+    if (n * chunk_size < kReleaseToOsGranularity)
+      return;   // No chance to release anything.
+    if ((region->rtoi.n_freed_at_last_release - region->n_freed) * chunk_size <
+        kReleaseToOsGranularity)
+      return;  // Nothing new to release.
+    SortArray(free_array, n);
+    uptr beg = free_array[0];
+    uptr prev = free_array[0];
+    for (uptr i = 1; i < n; i++) {
+      uptr chunk = free_array[i];
+      CHECK_GT(chunk, prev);
+      if (chunk - prev != scaled_chunk_size) {
+        CHECK_GT(chunk - prev, scaled_chunk_size);
+        if (prev + scaled_chunk_size - beg >= kScaledGranularity) {
+          MaybeReleaseChunkRange(region_beg, chunk_size, beg, prev);
+          region->rtoi.n_freed_at_last_release = region->n_freed;
+          region->rtoi.num_releases++;
+        }
+        beg = chunk;
+      }
+      prev = chunk;
+    }
+  }
 };
 
 
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common.cc b/compiler-rt/lib/sanitizer_common/sanitizer_common.cc
index 79fcbb1183f..de179be5fa4 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_common.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common.cc
@@ -157,6 +157,7 @@ bool ReadFileToBuffer(const char *file_name, char **buff, uptr *buff_size,
 }
 
 typedef bool UptrComparisonFunction(const uptr &a, const uptr &b);
+typedef bool U32ComparisonFunction(const u32 &a, const u32 &b);
 
 template<class T>
 static inline bool CompareLess(const T &a, const T &b) {
@@ -167,6 +168,10 @@ void SortArray(uptr *array, uptr size) {
   InternalSort<uptr*, UptrComparisonFunction>(&array, size, CompareLess);
 }
 
+void SortArray(u32 *array, uptr size) {
+  InternalSort<u32*, U32ComparisonFunction>(&array, size, CompareLess);
+}
+
 const char *StripPathPrefix(const char *filepath,
                             const char *strip_path_prefix) {
   if (!filepath) return nullptr;
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common.h b/compiler-rt/lib/sanitizer_common/sanitizer_common.h
index 6c1d6a00a10..0df4b79d51e 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_common.h
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common.h
@@ -100,7 +100,7 @@ bool MprotectReadOnly(uptr addr, uptr size);
 
 // Used to check if we can map shadow memory to a fixed location.
 bool MemoryRangeIsAvailable(uptr range_start, uptr range_end);
-void FlushUnneededShadowMemory(uptr addr, uptr size);
+void ReleaseMemoryToOS(uptr addr, uptr size);
 void IncreaseTotalMmap(uptr size);
 void DecreaseTotalMmap(uptr size);
 uptr GetRSS();
@@ -330,6 +330,7 @@ void SleepForMillis(int millis);
 u64 NanoTime();
 int Atexit(void (*function)(void));
 void SortArray(uptr *array, uptr size);
+void SortArray(u32 *array, uptr size);
 bool TemplateMatch(const char *templ, const char *str);
 
 // Exit
@@ -371,6 +372,12 @@ void SetCheckFailedCallback(CheckFailedCallbackType callback);
 // The callback should be registered once at the tool init time.
 void SetSoftRssLimitExceededCallback(void (*Callback)(bool exceeded));
 
+// Callback to be called when we want to try releasing unused allocator memory
+// back to the OS.
+typedef void (*AllocatorReleaseToOSCallback)();
+// The callback should be registered once at the tool init time.
+void SetAllocatorReleaseToOSCallback(AllocatorReleaseToOSCallback Callback);
+
 // Functions related to signal handling.
 typedef void (*SignalHandlerType)(int, void *, void *);
 bool IsHandledDeadlySignal(int signum);
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_common_libcdep.cc b/compiler-rt/lib/sanitizer_common/sanitizer_common_libcdep.cc
index 596f5bcd317..1727f24c31a 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_common_libcdep.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_common_libcdep.cc
@@ -69,9 +69,16 @@ void SetSoftRssLimitExceededCallback(void (*Callback)(bool exceeded)) {
   SoftRssLimitExceededCallback = Callback;
 }
 
+static AllocatorReleaseToOSCallback ReleseCallback;
+void SetAllocatorReleaseToOSCallback(AllocatorReleaseToOSCallback Callback) {
+  CHECK_EQ(ReleseCallback, nullptr);
+  ReleseCallback = Callback;
+}
+
 void BackgroundThread(void *arg) {
   uptr hard_rss_limit_mb = common_flags()->hard_rss_limit_mb;
   uptr soft_rss_limit_mb = common_flags()->soft_rss_limit_mb;
+  bool allocator_release_to_os = common_flags()->allocator_release_to_os;
   uptr prev_reported_rss = 0;
   uptr prev_reported_stack_depot_size = 0;
   bool reached_soft_rss_limit = false;
@@ -116,6 +123,7 @@ void BackgroundThread(void *arg) {
           SoftRssLimitExceededCallback(false);
       }
     }
+    if (allocator_release_to_os && ReleseCallback) ReleseCallback();
   }
 }
 
@@ -142,7 +150,8 @@ void MaybeStartBackgroudThread() {
     !SANITIZER_GO  // Need to implement/test on other platforms.
   // Start the background thread if one of the rss limits is given.
   if (!common_flags()->hard_rss_limit_mb &&
-      !common_flags()->soft_rss_limit_mb) return;
+      !common_flags()->soft_rss_limit_mb &&
+      !common_flags()->allocator_release_to_os) return;
   if (!&real_pthread_create) return;  // Can't spawn the thread anyway.
   internal_start_thread(BackgroundThread, nullptr);
 #endif
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_flags.inc b/compiler-rt/lib/sanitizer_common/sanitizer_flags.inc
index 3fcfb83e1ab..d3c60c5fc4e 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_flags.inc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_flags.inc
@@ -118,6 +118,9 @@ COMMON_FLAG(uptr, soft_rss_limit_mb, 0,
             " until the RSS goes below the soft limit."
             " This limit does not affect memory allocations other than"
             " malloc/new.")
+COMMON_FLAG(bool, allocator_release_to_os, false,
+            "Experimental. If true, try to periodically release unused"
+            " memory to the OS.\n")
 COMMON_FLAG(bool, can_use_proc_maps_statm, true,
             "If false, do not attempt to read /proc/maps/statm."
             " Mostly useful for testing sanitizers.")
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_posix_libcdep.cc b/compiler-rt/lib/sanitizer_common/sanitizer_posix_libcdep.cc
index f1e8b50a2cf..a1c26e47f59 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_posix_libcdep.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_posix_libcdep.cc
@@ -54,7 +54,7 @@ uptr GetThreadSelf() {
   return (uptr)pthread_self();
 }
 
-void FlushUnneededShadowMemory(uptr addr, uptr size) {
+void ReleaseMemoryToOS(uptr addr, uptr size) {
   madvise((void*)addr, size, MADV_DONTNEED);
 }
 
diff --git a/compiler-rt/lib/sanitizer_common/sanitizer_win.cc b/compiler-rt/lib/sanitizer_common/sanitizer_win.cc
index cdb2948214a..04e1e11bbec 100644
--- a/compiler-rt/lib/sanitizer_common/sanitizer_win.cc
+++ b/compiler-rt/lib/sanitizer_common/sanitizer_win.cc
@@ -235,13 +235,13 @@ bool MprotectNoAccess(uptr addr, uptr size) {
 }
 
 
-void FlushUnneededShadowMemory(uptr addr, uptr size) {
+void ReleaseMemoryToOS(uptr addr, uptr size) {
   // This is almost useless on 32-bits.
   // FIXME: add madvise-analog when we move to 64-bits.
 }
 
 void NoHugePagesInRegion(uptr addr, uptr size) {
-  // FIXME: probably similar to FlushUnneededShadowMemory.
+  // FIXME: probably similar to ReleaseMemoryToOS.
 }
 
 void DontDumpShadowMemory(uptr addr, uptr length) {