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: I6fc3865cbf4b9e8c5dd6ad4222eac2085a612b51
Signed-off-by: Andrey Drobyshev <a.drobyshev@samsung.com>

4 files changed, 147 insertions, 1 deletions

diff --git a/libsanitizer/asan/asan_memory_profile.cc b/libsanitizer/asan/asan_memory_profile.cc
index 8a8ae221c14..9671fdffa59 100644
--- a/libsanitizer/asan/asan_memory_profile.cc
+++ b/libsanitizer/asan/asan_memory_profile.cc
@@ -30,6 +30,11 @@
 #include <time.h>
 #endif
 
+namespace __sanitizer {
+  // provided by sanitizer_common_libcdep.cc
+  extern SleepInterval last_sleep_int;
+}
+
 namespace __asan {
 
 class HeapProfile;                      // Pointer to the global object
@@ -116,6 +121,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:
@@ -363,6 +378,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) {
     __sanitizer::StopTheWorld(__asan::MemoryProfileCB, (void*)top_percent);
diff --git a/libsanitizer/sanitizer_common/sanitizer_common.h b/libsanitizer/sanitizer_common/sanitizer_common.h
index 3c1d1a56fd4..fb06aa45109 100644
--- a/libsanitizer/sanitizer_common/sanitizer_common.h
+++ b/libsanitizer/sanitizer_common/sanitizer_common.h
@@ -765,6 +765,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.cc b/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cc
index 3c429117c9c..656552fe177 100644
--- a/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cc
+++ b/libsanitizer/sanitizer_common/sanitizer_common_libcdep.cc
@@ -23,6 +23,9 @@
 
 namespace __sanitizer {
 
+// Used externally
+SleepInterval last_sleep_int = {common_flags()->bgthread_min_sleep_ms, true};
+
 bool ReportFile::SupportsColors() {
   SpinMutexLock l(mu);
   ReopenIfNecessary();
@@ -68,6 +71,123 @@ void SetSoftRssLimitExceededCallback(void (*Callback)(bool exceeded)) {
   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_GO
 void BackgroundThread(void *arg) {
   uptr hard_rss_limit_mb = common_flags()->hard_rss_limit_mb;
@@ -78,7 +198,7 @@ void BackgroundThread(void *arg) {
   bool reached_soft_rss_limit = false;
 
   while (true) {
-    SleepForMillis(100);
+    SleepForMillis(CalcNewSleepInterval());
     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 836f872847c..47f812a81e8 100644
--- a/libsanitizer/sanitizer_common/sanitizer_flags.inc
+++ b/libsanitizer/sanitizer_common/sanitizer_flags.inc
@@ -121,6 +121,10 @@ 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(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,