[lsan] Ignore inderect leaks referenced by suppressed blocks

[vitalybuka]

Summary

This makes suppression list to work similar to __lsan_ignore_object.

Existing behavior was inconsistent and very inconvenient for complex
data structures.

Example:

struct B;
struct A { B* ptr; };
A* t = makeA();
t->ptr = makeB();

Before the patch: if makeA suppressed by suppression file, lsan will
still report the makeB() leak, so we need two suppressions.

After the patch: a single makeA suppression is enough (the same as a
single __lsan_ignore_object(t)).

[eugenis]

compiler-rt/lib/lsan/lsan_common.cpp

738

If you run ApplySuppressions multiple times, would this not inflate the suppression weights (i.e. match counts)?

741

Some indication in the output that we might have failed to apply all suppressions would be good.

I hate that the algorithm may fail, but I can't offer a better idea. We could temporarily unlock the allocator while the world is stopped, symbolize all leak candidates and rerun the flood fill algorithm, but that seems dangerous.

[vitalybuka]

update

compiler-rt/lib/lsan/lsan_common.cpp

738

no, the second time suppressed will have tag ignored instead of suppressed.

741

Done.

I believe you need very artificial test to hit this limit.
between each iteration program must not just leak, but also leak with unique stack which matches suppression.

[vitalybuka]

avoid function local static

[eugenis]

LGTM

compiler-rt/lib/lsan/lsan_common.h

 // Aggregates leaks by stack trace prefix.
 class LeakReport {
  public:
   LeakReport() {}
   void AddLeakedChunk(uptr chunk, u32 stack_trace_id, uptr leaked_size,
                       ChunkTag tag);
   void ReportTopLeaks(uptr max_leaks);
   void PrintSummary();
-  void ApplySuppressions();
+  uptr ApplySuppressions();
   uptr UnsuppressedLeakCount();
+  uptr IndirectUnsuppressedLeakCount();
 
  private:
   void PrintReportForLeak(uptr index);
   void PrintLeakedObjectsForLeak(uptr index);
 
   u32 next_id_ = 0;
   InternalMmapVector<Leak> leaks_;
   InternalMmapVector<LeakedObject> leaked_objects_;

compiler-rt/lib/lsan/lsan_common.cpp

 #define LOG_THREADS(...)                           \
   do {                                             \
     if (flags()->log_threads) Report(__VA_ARGS__); \
   } while (0)
 
 class LeakSuppressionContext {
   bool parsed = false;
   SuppressionContext context;
+  bool suppressed_stacks_sorted = true;
+  InternalMmapVector<u32> suppressed_stacks;
 
   Suppression *GetSuppressionForAddr(uptr addr);
-  void LazyParse();
+  void LazyInit();
 
  public:
   LeakSuppressionContext(const char *supprression_types[],
                          int suppression_types_num)
       : context(supprression_types, suppression_types_num) {}
 
   Suppression *GetSuppressionForStack(u32 stack_trace_id);
+
+  const InternalMmapVector<u32> &GetSortedSuppressedStacks() {
+    if (!suppressed_stacks_sorted) {
+      suppressed_stacks_sorted = true;
+      SortAndDedup(suppressed_stacks);
+    }
+    return suppressed_stacks;
+  }
   void PrintMatchedSuppressions();
 };
 
 ALIGNED(64) static char suppression_placeholder[sizeof(LeakSuppressionContext)];
 static LeakSuppressionContext *suppression_ctx = nullptr;
 static const char kSuppressionLeak[] = "leak";
 static const char *kSuppressionTypes[] = { kSuppressionLeak };
 static const char kStdSuppressions[] =
#endif
     "leak:*tls_get_addr*\n";
 
 void InitializeSuppressions() {
   CHECK_EQ(nullptr, suppression_ctx);
   suppression_ctx = new (suppression_placeholder)
       LeakSuppressionContext(kSuppressionTypes, ARRAY_SIZE(kSuppressionTypes));
 }
 
-void LeakSuppressionContext::LazyParse() {
+void LeakSuppressionContext::LazyInit() {
   if (!parsed) {
     parsed = true;
     context.ParseFromFile(flags()->suppressions);
     if (&__lsan_default_suppressions)
       context.Parse(__lsan_default_suppressions());
     context.Parse(kStdSuppressions);
   }
 }
static void MarkIndirectlyLeakedCb(uptr chunk, void *arg) {
   chunk = GetUserBegin(chunk);
   LsanMetadata m(chunk);
   if (m.allocated() && m.tag() != kReachable) {
     ScanRangeForPointers(chunk, chunk + m.requested_size(),
                          /* frontier */ nullptr, "HEAP", kIndirectlyLeaked);
   }
 }
 
+static void IgnoredSuppressedCb(uptr chunk, void *arg) {
+  CHECK(arg);
+  chunk = GetUserBegin(chunk);
+  LsanMetadata m(chunk);
+  if (!m.allocated() || m.tag() == kIgnored)
+    return;
+
+  const InternalMmapVector<u32> &suppressed =
+      *static_cast<const InternalMmapVector<u32> *>(arg);
+  uptr idx = InternalLowerBound(suppressed, m.stack_trace_id());
+  if (idx >= suppressed.size() || m.stack_trace_id() != suppressed[idx])
+    return;
+
+  LOG_POINTERS("Suppressed: chunk %p-%p of size %zu.\n", chunk,
+               chunk + m.requested_size(), m.requested_size());
+  m.set_tag(kIgnored);
+}
+
 // ForEachChunk callback. If chunk is marked as ignored, adds its address to
 // frontier.
 static void CollectIgnoredCb(uptr chunk, void *arg) {
   CHECK(arg);
   chunk = GetUserBegin(chunk);
   LsanMetadata m(chunk);
   if (m.allocated() && m.tag() == kIgnored) {
     LOG_POINTERS("Ignored: chunk %p-%p of size %zu.\n",
void ProcessPC(Frontier *frontier) {
   arg.skip_linker_allocations =
       flags()->use_tls && flags()->use_ld_allocations && GetLinker() != nullptr;
   ForEachChunk(MarkInvalidPCCb, &arg);
 }
 
 // Sets the appropriate tag on each chunk.
 static void ClassifyAllChunks(SuspendedThreadsList const &suspended_threads,
                               Frontier *frontier) {
+  const InternalMmapVector<u32> &suppressed_stacks =
+      GetSuppressionContext()->GetSortedSuppressedStacks();
+  if (!suppressed_stacks.empty()) {
+    ForEachChunk(IgnoredSuppressedCb,
+                 const_cast<InternalMmapVector<u32> *>(&suppressed_stacks));
+  }
   ForEachChunk(CollectIgnoredCb, frontier);
   ProcessGlobalRegions(frontier);
   ProcessThreads(suspended_threads, frontier);
   ProcessRootRegions(frontier);
   FloodFillTag(frontier, kReachable);
 
   CHECK_EQ(0, frontier->size());
   ProcessPC(frontier);
if (unsuppressed_count > 0) {
     return true;
   }
   return false;
 }
 
 static bool CheckForLeaks() {
   if (&__lsan_is_turned_off && __lsan_is_turned_off())
     return false;
+  // Inside LockStuffAndStopTheWorld we can't run symbolizer, so we can't match
+  // suppressions. However if a stack id was previously suppressed, it should be
+  // suppressed in future checks as well.
+  for (int i = 0;; ++i) {
     EnsureMainThreadIDIsCorrect();
     CheckForLeaksParam param;
     LockStuffAndStopTheWorld(CheckForLeaksCallback, &param);
-
     if (!param.success) {
       Report("LeakSanitizer has encountered a fatal error.\n");
       Report(
           "HINT: For debugging, try setting environment variable "
           "LSAN_OPTIONS=verbosity=1:log_threads=1\n");
       Report(
-        "HINT: LeakSanitizer does not work under ptrace (strace, gdb, etc)\n");
+          "HINT: LeakSanitizer does not work under ptrace (strace, gdb, "
+          "etc)\n");
       Die();
     }
-  param.leak_report.ApplySuppressions();
+    // No new suppressions stacks, so rerun will not help and we can report.
+    if (!param.leak_report.ApplySuppressions())
       return PrintResults(param.leak_report);
+
+    // No indirect leaks to report, so we are done here.
+    if (!param.leak_report.IndirectUnsuppressedLeakCount())
+      return PrintResults(param.leak_report);
+
+    if (i >= 8) {
+      Report("WARNING: LeakSanitizer gave up on indirect leaks suppression.\n");
+      return PrintResults(param.leak_report);
+    }
+
+    // We found a new previously unseen suppressed call stack. Rerun to make
+    // sure it does not hold indirect leaks.
+    VReport(1, "Rerun with %zu suppressed stacks.",
+            GetSuppressionContext()->GetSortedSuppressedStacks().size());
+  }
 }
 
 static bool has_reported_leaks = false;
 bool HasReportedLeaks() { return has_reported_leaks; }
 
 void DoLeakCheck() {
   BlockingMutexLock l(&global_mutex);
   static bool already_done;
   if (already_done) return;
   already_done = true;
   has_reported_leaks = CheckForLeaks();
   if (has_reported_leaks) HandleLeaks();
 }
 
 static int DoRecoverableLeakCheck() {
   BlockingMutexLock l(&global_mutex);
   bool have_leaks = CheckForLeaks();
   return have_leaks ? 1 : 0;
 }
 
 void DoRecoverableLeakCheckVoid() { DoRecoverableLeakCheck(); }
 
 Suppression *LeakSuppressionContext::GetSuppressionForAddr(uptr addr) {
   Suppression *s = nullptr;
 
   // Suppress by module name.
   if (const char *module_name =
           Symbolizer::GetOrInit()->GetModuleNameForPc(addr))
     if (context.Match(module_name, kSuppressionLeak, &s))
       return s;
 
   // Suppress by file or function name.
   SymbolizedStack *frames = Symbolizer::GetOrInit()->SymbolizePC(addr);
   for (SymbolizedStack *cur = frames; cur; cur = cur->next) {
     if (context.Match(cur->info.function, kSuppressionLeak, &s) ||
         context.Match(cur->info.file, kSuppressionLeak, &s)) {
       break;
     }
   }
   frames->ClearAll();
   return s;
 }
 
 Suppression *LeakSuppressionContext::GetSuppressionForStack(
     u32 stack_trace_id) {
-  LazyParse();
+  LazyInit();
   StackTrace stack = StackDepotGet(stack_trace_id);
   for (uptr i = 0; i < stack.size; i++) {
     Suppression *s = GetSuppressionForAddr(
         StackTrace::GetPreviousInstructionPc(stack.trace[i]));
-    if (s)
+    if (s) {
+      suppressed_stacks_sorted = false;
+      suppressed_stacks.push_back(stack_trace_id);
       return s;
     }
+  }
   return nullptr;
 }
 
 ///// LeakReport implementation. /////
 
 // A hard limit on the number of distinct leaks, to avoid quadratic complexity
 // in LeakReport::AddLeakedChunk(). We don't expect to ever see this many leaks
 // in real-world applications.
for (uptr i = 0; i < leaks_.size(); i++) {
       allocations += leaks_[i].hit_count;
   }
   InternalScopedString summary(kMaxSummaryLength);
   summary.append("%zu byte(s) leaked in %zu allocation(s).", bytes,
                  allocations);
   ReportErrorSummary(summary.data());
 }
 
-void LeakReport::ApplySuppressions() {
+uptr LeakReport::ApplySuppressions() {
   LeakSuppressionContext *suppressions = GetSuppressionContext();
+  uptr new_suppressions = false;
   for (uptr i = 0; i < leaks_.size(); i++) {
     Suppression *s =
         suppressions->GetSuppressionForStack(leaks_[i].stack_trace_id);
     if (s) {
       s->weight += leaks_[i].total_size;
       atomic_store_relaxed(&s->hit_count, atomic_load_relaxed(&s->hit_count) +
           leaks_[i].hit_count);
       leaks_[i].is_suppressed = true;
+      ++new_suppressions;
     }
   }
+  return new_suppressions;
 }
 
 uptr LeakReport::UnsuppressedLeakCount() {
   uptr result = 0;
   for (uptr i = 0; i < leaks_.size(); i++)
     if (!leaks_[i].is_suppressed) result++;
   return result;
 }
 
+uptr LeakReport::IndirectUnsuppressedLeakCount() {
+  uptr result = 0;
+  for (uptr i = 0; i < leaks_.size(); i++)
+    if (!leaks_[i].is_suppressed && !leaks_[i].is_directly_leaked)
+      result++;
+  return result;
+}
+
 } // namespace __lsan
 #else // CAN_SANITIZE_LEAKS
 namespace __lsan {
 void InitCommonLsan() { }
 void DoLeakCheck() { }
 void DoRecoverableLeakCheckVoid() { }
 void DisableInThisThread() { }
 void EnableInThisThread() { }

compiler-rt/test/lsan/TestCases/suppressions_file.cpp

 //
 // RUN: echo "leak:%t" > %t.supp
 // RUN: %push_to_device  %t.supp %device_rundir/%t.supp
 // RUN: %env_lsan_opts="$LSAN_BASE:suppressions='%device_rundir/%t.supp':symbolize=false" %run %t
 
 #include <stdio.h>
 #include <stdlib.h>
 
-void* LSanTestLeakingFunc() {
+void *LSanTestLeakingFunc() {
   void *p = malloc(666);
   fprintf(stderr, "Test alloc: %p.\n", p);
   return p;
 }
 
 void LSanTestUnsuppressedLeakingFunc() {
-  void** p = (void**)LSanTestLeakingFunc();
-  // FIXME: This must be suppressed as well.
+  void **p = (void **)LSanTestLeakingFunc();
   *p = malloc(777);
   fprintf(stderr, "Test alloc: %p.\n", *p);
 }
 
 int main() {
   LSanTestUnsuppressedLeakingFunc();
   void *q = malloc(1337);
   fprintf(stderr, "Test alloc: %p.\n", q);
   return 0;
 }
 // CHECK: Suppressions used:
 // CHECK: 1 666 *LSanTestLeakingFunc*
-// CHECK: SUMMARY: {{(Leak|Address)}}Sanitizer: 2114 byte(s) leaked in 2 allocation(s)
+// CHECK: SUMMARY: {{(Leak|Address)}}Sanitizer: 1337 byte(s) leaked in 1 allocation(s)
 
 // NOSUPP: SUMMARY: {{(Leak|Address)}}Sanitizer: 2780 byte(s) leaked in 3 allocation(s).