libsanitizer: add filtering of sleep intervals for BackgroundThread.

Previously sleep interval length of BackgroundThread was determined by a
hardcoded value, thus limiting time resolution of dependent tools, such
as Heap Profiler.  This commit implements simple algorithm which
remembers last several sleeps (namely 2), their durations and whether or
not they were followed by some interesting events (i.e. delivery of some
memory usage statistics).  Then it tries to predict an optimal sleep
length for the next time, changing it dynamically.

Change-Id: Ia95cc5ac60ff9ac9edaa8b7b99e319c0bce80ea7
Signed-off-by: Andrey Drobyshev <a.drobyshev@samsung.com>
Signed-off-by: Slava Barinov <v.barinov@samsung.com>
Signed-off-by: yaroslav <y.yamshchiko@samsung.com>

4 files changed, 153 insertions, 1 deletions

diff --git a/libsanitizer/asan/asan_memory_profile.cpp b/libsanitizer/asan/asan_memory_profile.cpp
index 38855c755e7..0c36a53d96f 100644
--- a/libsanitizer/asan/asan_memory_profile.cpp
+++ b/libsanitizer/asan/asan_memory_profile.cpp
@@ -32,6 +32,11 @@
 #include <time.h>
 #endif
 
+namespace __sanitizer {
+  // provided by sanitizer_common_libcdep.cpp
+  extern SleepInterval last_sleep_int;
+}
+
 namespace __asan {
 
 class HeapProfile;                      // Pointer to the global object
@@ -119,6 +124,16 @@ class HeapProfile {
     return res;
   }
 
+  void HPUpdateSleepInt(HPProfileType hp_prof_type) {
+    switch(hp_prof_type) {
+    case HPProfileType::NONE:
+      break;
+    case HPProfileType::SHORT:
+    case HPProfileType::FULL:
+      __sanitizer::last_sleep_int.ends_with_event = true;
+    }
+  }
+
   void HPPrintHeader(HPProfileType hp_prof_type) {
     switch (hp_prof_type) {
     case HPProfileType::NONE:
@@ -391,6 +406,7 @@ void __sanitizer_print_memory_profile(uptr top_percent,
 
   __asan::HeapProfile::HPProfileType hp_prof_type =
                               __asan::heap_profile->NeededProfileType();
+  __asan::heap_profile->HPUpdateSleepInt(hp_prof_type);
   __asan::heap_profile->HPPrintHeader(hp_prof_type);
   if (hp_prof_type == __asan::HeapProfile::HPProfileType::FULL) {
     __asan::MemoryProfileCB(top_percent, max_number_of_contexts);
diff --git a/libsanitizer/sanitizer_common/sanitizer_common.h b/libsanitizer/sanitizer_common/sanitizer_common.h
index c79f754c1d1..d5e2996cdeb 100644
--- a/libsanitizer/sanitizer_common/sanitizer_common.h
+++ b/libsanitizer/sanitizer_common/sanitizer_common.h
@@ -971,6 +971,12 @@ inline uptr GetPthreadDestructorIterations() {
 #endif
 }
 
+// Used for tweaking sleep duration
+struct SleepInterval {
+  int duration_ms;
+  bool ends_with_event;
+};
+
 void *internal_start_thread(void *(*func)(void*), void *arg);
 void internal_join_thread(void *th);
 void MaybeStartBackgroudThread();
diff --git a/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cpp b/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cpp
index 7324189c986..9b3292d861d 100644
--- a/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cpp
+++ b/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cpp
@@ -20,6 +20,132 @@
 
 namespace __sanitizer {
 
+// Used externally
+SleepInterval last_sleep_int = {common_flags()->bgthread_min_sleep_ms, true};
+
+static void (*SoftRssLimitExceededCallback)(bool exceeded);
+void SetSoftRssLimitExceededCallback(void (*Callback)(bool exceeded)) {
+  CHECK_EQ(SoftRssLimitExceededCallback, nullptr);
+  SoftRssLimitExceededCallback = Callback;
+}
+
+static int MinNonZeroTimeout(void)
+{
+  int T = Max(common_flags()->heap_profile_full_out_time,
+                common_flags()->heap_profile_short_out_time);
+  int t = Min(common_flags()->heap_profile_full_out_time,
+                common_flags()->heap_profile_short_out_time);
+  return t > 0 ? t : T;
+}
+
+static int Mid(uptr a, uptr b)
+{
+  int m = Min(a, b);
+  int M = Max(a, b);
+  return m + (M - m + 1) / 2;
+}
+
+// Calculate new BackgroundThread sleep duration based on previous
+// sleep intervals.
+//
+// This algorithm remembers the last several sleeps (namely 2), their
+// durations and whether or not they were followed by some interesting
+// events (i.e. delivery of memory usage statistics). Based on that criteria,
+// it considers every interval to be either interesting or uninteresting.
+// If the last sleeping interval was interesting, then we probably need to
+// sleep less, and vice versa. How much less (or more) is determined by
+// "reference points":
+//
+//   * if last and last but one intervals have different
+//     interesting/uninteresting attributes, then change is considered to be
+//     smooth, and duration of last but one interval will serve as a reference
+//     point:
+//  0                 low_ref       new                            duration, ms
+// -|------|-------------|-----------|------------|-------------|-------->
+//    low_thrhold    last_but_one               last       high_thrhold
+//                 (uninteresting)          (interesting)
+//
+//   * if 2 last intervals are both interesting (both uninteresting), then
+//     change is considered to be rapid, and low/high threshold will serve
+//     as a reference point:
+//  0                                             new    high_ref  duration, ms
+// -|------|-------------|---------------|---------|---------|----------->
+//    low_thrhold   last_but_one       last             high_thrhold
+//                (uninteresting) (uninteresting)
+//
+// High/low thresholds, in turn, are determined by both
+// bgthread_min/max_sleep_ms values and profiler timeouts (if the user wants
+// us to gather statistics every Tms, there's no sense in sleeping longer
+// than Tms).
+//
+// The algorithm also tries not to change interval duration too rapidly,
+// thus multiplying/dividing it by factor of 2 together with calculating
+// Mid() value with high/low reference points and choosing more "smooth"
+// option.
+static int CalcNewSleepInterval(void)
+{
+  static SleepInterval last_but_one_sleep_int =
+                        {common_flags()->bgthread_min_sleep_ms, true};
+
+  static const int wanted_timeout = MinNonZeroTimeout();
+  static const int high_threshold = wanted_timeout > 0 ?
+                               Min(common_flags()->bgthread_max_sleep_ms,
+                                   wanted_timeout) :
+                               common_flags()->bgthread_max_sleep_ms;
+  static const int low_threshold  = wanted_timeout > 0 ?
+                               Min(common_flags()->bgthread_min_sleep_ms,
+                                   wanted_timeout) :
+                               common_flags()->bgthread_min_sleep_ms;
+
+  static int last_eventful_dur  = high_threshold;
+  static int last_eventless_dur = low_threshold;
+
+  int new_sleep_dur;
+
+  if (!last_sleep_int.ends_with_event) {
+    // Increase sleep interval length
+    last_eventless_dur = last_sleep_int.duration_ms;
+    if (last_eventful_dur <= last_sleep_int.duration_ms) {
+      last_eventful_dur = high_threshold;
+    }
+
+    int high_ref;
+    if (!last_but_one_sleep_int.ends_with_event ||
+        last_but_one_sleep_int.duration_ms <= last_sleep_int.duration_ms) {
+      high_ref = high_threshold;
+    } else {
+      high_ref = last_but_one_sleep_int.duration_ms;
+    }
+
+    new_sleep_dur = Min(Min(last_sleep_int.duration_ms * 2,
+                            Mid(last_sleep_int.duration_ms, high_ref)),
+                        last_eventful_dur);
+  } else {
+    // Decrease sleep interval length
+    last_eventful_dur = last_sleep_int.duration_ms;
+    if (last_eventless_dur >= last_sleep_int.duration_ms) {
+      last_eventless_dur = low_threshold;
+    }
+
+    int low_ref;
+    if (last_but_one_sleep_int.ends_with_event ||
+        last_but_one_sleep_int.duration_ms >= last_sleep_int.duration_ms) {
+      low_ref = low_threshold;
+    } else  {
+      low_ref = last_but_one_sleep_int.duration_ms;
+    }
+
+    new_sleep_dur = Max(Max(last_sleep_int.duration_ms / 2,
+                            Mid(last_sleep_int.duration_ms, low_ref)),
+                        last_eventless_dur);
+  }
+
+  last_but_one_sleep_int = last_sleep_int;
+  last_sleep_int = {new_sleep_dur, false};
+
+  return new_sleep_dur;
+}
+
 #if (SANITIZER_LINUX || SANITIZER_NETBSD) && !SANITIZER_GO
 // Weak default implementation for when sanitizer_stackdepot is not linked in.
 SANITIZER_WEAK_ATTRIBUTE StackDepotStats StackDepotGetStats() { return {}; }
@@ -34,7 +160,7 @@ void *BackgroundThread(void *arg) {
   bool reached_soft_rss_limit = false;
 
   while (true) {
-    SleepForMillis(100);
+    SleepForMillis(CalcNewSleepInterval());
     const uptr current_rss_mb = GetRSS() >> 20;
     if (Verbosity()) {
       // If RSS has grown 10% since last time, print some information.
diff --git a/libsanitizer/sanitizer_common/sanitizer_flags.inc b/libsanitizer/sanitizer_common/sanitizer_flags.inc
index 0224b28aa63..3a7de625191 100644
--- a/libsanitizer/sanitizer_common/sanitizer_flags.inc
+++ b/libsanitizer/sanitizer_common/sanitizer_flags.inc
@@ -146,6 +146,10 @@ COMMON_FLAG(uptr, soft_rss_limit_mb, 0,
 COMMON_FLAG(uptr, max_allocation_size_mb, 0,
             "If non-zero, malloc/new calls larger than this size will return "
             "nullptr (or crash if allocator_may_return_null=false).")
+COMMON_FLAG(int, bgthread_min_sleep_ms, 2,
+            "Lower bound for background thread sleeping interval.")
+COMMON_FLAG(int, bgthread_max_sleep_ms, 100,
+            "Upper bound for background thread sleeping interval.")
 COMMON_FLAG(bool, heap_profile, false,
             "Experimental. Enables heap profiler (asan-only).")
 COMMON_FLAG(bool, heap_profile_timestamp, false,