[rtsan] Only print out unique stack traces #110028

cjappl · 2024-09-25T19:18:06Z

Why?

In real-time programming, you often have a process or dispatch loop that is called many, many, many times. Without de-duplication the user will be drowning in errors.

Introduce a way to only print the stacks one time only, if they have been seen before

What is unique?

Unique in our case is absolutely unique in every stack frame

If you have:
Main->foo->bar
and
Main->baz->foo->bar

These are considered unique in this implementation, even though there are some similarities. This is both the simplest method to use, and the most complete, as stacks will be universally unique

How?

There is a clever construct called a StackDepot, seemingly made for this purpose, in use by the other sanitizers. It is essentially a hash table of stacks, where a unique ID is mapped to a stack. This data structure is designed to be multithreaded, and seems highly optimized for this purpose.

It is worth checking out the put function to understand the runtime costs. If the stack already exists, it amounts to an atomic check and early return, if the stack is new, a lock is locked before inserting it into the data structure.

llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

Line 115 in 1911a50

u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,

What to look out for

I have introduced "Unique Errors" and "Total Errors", which are hopefully self explanatory. Happy to change the terminology and UI if people want.

I have deleted our stack printer helper, the stack is now used for multiple purposes, so we can print it when we want

Questions

Do we want to allow people to opt-in/out of deduplication? flags().print_duplicate_stacks. My initial gut is "no" but open to discussion

cjappl · 2024-09-25T19:18:28Z

CC for review @davidtrevelyan

llvmbot · 2024-09-25T19:18:44Z

@llvm/pr-subscribers-compiler-rt-sanitizer

Author: Chris Apple (cjappl)

Changes

Why?

In real-time programming, you often have a process or dispatch loop that is called many, many, many times. Without de-duplication the user will be drowning in errors.

Introduce a way to only print the stacks one time only, if they have been seen before

How?

There is a clever construct called a StackDepot, seemingly made for this purpose, in use by the other sanitizers. It is essentially a hash table of stacks, where a unique ID is mapped to a stack. This data structure is designed to be multithreaded, and seems highly optimized for this purpose.

It is worth checking out the put function to understand the runtime costs. If the stack already exists, it amounts to an atomic check and early return, if the stack is new, a lock is locked before inserting it into the data structure.

llvm-project/compiler-rt/lib/sanitizer_common/sanitizer_stackdepotbase.h

Line 115 in 1911a50

u32 StackDepotBase<Node, kReservedBits, kTabSizeLog>::Put(args_type args,

What to look out for

I have introduced "Unique Errors" and "Total Errors", which are hopefully self explanatory. Happy to change the terminology and UI if people want.

I have deleted our stack printer helper, the stack is now used for multiple purposes, so we can print it when we want

Questions

Do we want to allow people to opt-in/out of deduplication? flags().print_duplicate_stacks. My initial gut is "no" but open to discussion

Full diff: https://github.com/llvm/llvm-project/pull/110028.diff

6 Files Affected:

(modified) compiler-rt/lib/rtsan/rtsan.cpp (+16-1)
(modified) compiler-rt/lib/rtsan/rtsan_diagnostics.cpp (-8)
(modified) compiler-rt/lib/rtsan/rtsan_stats.cpp (+10)
(modified) compiler-rt/lib/rtsan/rtsan_stats.h (+1)
(added) compiler-rt/test/rtsan/deduplicate_errors.cpp (+37)
(modified) compiler-rt/test/rtsan/exit_stats.cpp (+1)

diff --git a/compiler-rt/lib/rtsan/rtsan.cpp b/compiler-rt/lib/rtsan/rtsan.cpp
index 87c3611935ee5f..2a6cf325b02d54 100644
--- a/compiler-rt/lib/rtsan/rtsan.cpp
+++ b/compiler-rt/lib/rtsan/rtsan.cpp
@@ -18,6 +18,7 @@
 #include "sanitizer_common/sanitizer_atomic.h"
 #include "sanitizer_common/sanitizer_common.h"
 #include "sanitizer_common/sanitizer_mutex.h"
+#include "sanitizer_common/sanitizer_stackdepot.h"
 #include "sanitizer_common/sanitizer_stacktrace.h"
 
 using namespace __rtsan;
@@ -49,7 +50,21 @@ static auto OnViolationAction(DiagnosticsInfo info) {
   return [info]() {
     IncrementTotalErrorCount();
 
-    PrintDiagnostics(info);
+    BufferedStackTrace stack;
+    stack.Unwind(info.pc, info.bp, nullptr,
+                 /*request_fast*/ true);
+
+    StackDepotHandle handle = StackDepotPut_WithHandle(stack);
+
+    const bool is_stack_novel = handle.use_count() == 0;
+    if (UNLIKELY(is_stack_novel)) {
+      IncrementUniqueErrorCount();
+
+      PrintDiagnostics(info);
+      stack.Print();
+
+      handle.inc_use_count_unsafe();
+    }
 
     if (flags().halt_on_error)
       Die();
diff --git a/compiler-rt/lib/rtsan/rtsan_diagnostics.cpp b/compiler-rt/lib/rtsan/rtsan_diagnostics.cpp
index f82001f5b2057c..cfe71481d3dc78 100644
--- a/compiler-rt/lib/rtsan/rtsan_diagnostics.cpp
+++ b/compiler-rt/lib/rtsan/rtsan_diagnostics.cpp
@@ -39,13 +39,6 @@ class Decorator : public __sanitizer::SanitizerCommonDecorator {
 };
 } // namespace
 
-static void PrintStackTrace(uptr pc, uptr bp) {
-  BufferedStackTrace stack{};
-
-  stack.Unwind(pc, bp, nullptr, common_flags()->fast_unwind_on_fatal);
-  stack.Print();
-}
-
 static void PrintError(const Decorator &decorator,
                        const DiagnosticsInfo &info) {
   const auto ErrorTypeStr = [&info]() -> const char * {
@@ -91,5 +84,4 @@ void __rtsan::PrintDiagnostics(const DiagnosticsInfo &info) {
   PrintError(d, info);
   PrintReason(d, info);
   Printf("%s", d.Default());
-  PrintStackTrace(info.pc, info.bp);
 }
diff --git a/compiler-rt/lib/rtsan/rtsan_stats.cpp b/compiler-rt/lib/rtsan/rtsan_stats.cpp
index 7c1ccf2876f081..dac7b23c3ef520 100644
--- a/compiler-rt/lib/rtsan/rtsan_stats.cpp
+++ b/compiler-rt/lib/rtsan/rtsan_stats.cpp
@@ -19,17 +19,27 @@ using namespace __sanitizer;
 using namespace __rtsan;
 
 static atomic_uint32_t rtsan_total_error_count{0};
+static atomic_uint32_t rtsan_unique_error_count{0};
 
 void __rtsan::IncrementTotalErrorCount() {
   atomic_fetch_add(&rtsan_total_error_count, 1, memory_order_relaxed);
 }
 
+void __rtsan::IncrementUniqueErrorCount() {
+  atomic_fetch_add(&rtsan_unique_error_count, 1, memory_order_relaxed);
+}
+
 static u32 GetTotalErrorCount() {
   return atomic_load(&rtsan_total_error_count, memory_order_relaxed);
 }
 
+static u32 GetUniqueErrorCount() {
+  return atomic_load(&rtsan_unique_error_count, memory_order_relaxed);
+}
+
 void __rtsan::PrintStatisticsSummary() {
   ScopedErrorReportLock l;
   Printf("RealtimeSanitizer exit stats:\n");
   Printf("    Total error count: %u\n", GetTotalErrorCount());
+  Printf("    Unique error count: %u\n", GetUniqueErrorCount());
 }
diff --git a/compiler-rt/lib/rtsan/rtsan_stats.h b/compiler-rt/lib/rtsan/rtsan_stats.h
index 3aa30f6a5db76a..a72098792c89c9 100644
--- a/compiler-rt/lib/rtsan/rtsan_stats.h
+++ b/compiler-rt/lib/rtsan/rtsan_stats.h
@@ -15,6 +15,7 @@
 namespace __rtsan {
 
 void IncrementTotalErrorCount();
+void IncrementUniqueErrorCount();
 
 void PrintStatisticsSummary();
 
diff --git a/compiler-rt/test/rtsan/deduplicate_errors.cpp b/compiler-rt/test/rtsan/deduplicate_errors.cpp
new file mode 100644
index 00000000000000..224a2215ac7cb1
--- /dev/null
+++ b/compiler-rt/test/rtsan/deduplicate_errors.cpp
@@ -0,0 +1,37 @@
+// RUN: %clangxx -fsanitize=realtime %s -o %t
+// RUN: env RTSAN_OPTIONS="halt_on_error=false,print_stats_on_exit=true" %run %t 2>&1 | FileCheck %s
+// RUN: env RTSAN_OPTIONS="halt_on_error=false" %run %t 2>&1 | grep "==ERROR: RealtimeSanitizer:" | wc -l | awk '{exit $1 != 4}'
+
+// UNSUPPORTED: ios
+
+// Intent: Ensure all errors are deduplicated.
+
+#include <unistd.h>
+
+const int kNumViolations = 10;
+
+void violation() [[clang::nonblocking]] {
+  for (int i = 0; i < kNumViolations; i++)
+    usleep(1);
+}
+
+void violation2() [[clang::nonblocking]] {
+  for (int i = 0; i < kNumViolations; i++)
+    violation();
+}
+
+void double_violation() [[clang::nonblocking]] {
+  violation();
+  violation2();
+}
+
+int main() {
+  violation();        // 1 unique errors here, but 10 total
+  violation2();       // 1 unique errors here, but 100 total
+  double_violation(); // 2 unique errors here, but 110 total
+  return 0;
+}
+
+// CHECK: RealtimeSanitizer exit stats:
+// CHECK-NEXT: Total error count: 220
+// CHECK-NEXT: Unique error count: 4
diff --git a/compiler-rt/test/rtsan/exit_stats.cpp b/compiler-rt/test/rtsan/exit_stats.cpp
index b46a0fd62bac1a..4341fbb0f9cf21 100644
--- a/compiler-rt/test/rtsan/exit_stats.cpp
+++ b/compiler-rt/test/rtsan/exit_stats.cpp
@@ -21,3 +21,4 @@ int main() {
 
 // CHECK: RealtimeSanitizer exit stats:
 // CHECK-NEXT: Total error count: 10
+// CHECK-NEXT: Unique error count: 1

compiler-rt/lib/rtsan/rtsan.cpp

compiler-rt/test/rtsan/deduplicate_errors.cpp

fmayer · 2024-09-25T23:38:27Z

Thanks.

# Why? In real-time programming, you often have a process or dispatch loop that is called many, many, many times. Without de-duplication the user will be drowning in errors. Introduce a way to only print the stacks one time only, if they have been seen before

[rtsan] Only print out unique stack traces

c59ecbe

cjappl requested a review from fmayer September 25, 2024 19:18

llvmbot added compiler-rt compiler-rt:sanitizer labels Sep 25, 2024

cjappl requested review from MaskRay and vitalybuka September 25, 2024 19:18

cjappl commented Sep 25, 2024

View reviewed changes

compiler-rt/lib/rtsan/rtsan.cpp Show resolved Hide resolved

compiler-rt/lib/rtsan/rtsan.cpp Outdated Show resolved Hide resolved

fmayer reviewed Sep 25, 2024

View reviewed changes

compiler-rt/lib/rtsan/rtsan.cpp Show resolved Hide resolved

compiler-rt/lib/rtsan/rtsan.cpp Show resolved Hide resolved

cjappl added 2 commits September 25, 2024 13:10

[PR] fmayer - Add comment about UNLIKELY

0328607

[PR] fmayer - fast unwind on fatal

9a41bf7

cjappl commented Sep 25, 2024

View reviewed changes

compiler-rt/test/rtsan/deduplicate_errors.cpp Outdated Show resolved Hide resolved

fmayer approved these changes Sep 25, 2024

View reviewed changes

cjappl added 2 commits September 25, 2024 16:38

[PR] fmayer - CHECK for counting instead of wc

31d6232

[PR] ilovepi - CHECK-COUNT

831e036

vitalybuka approved these changes Sep 26, 2024

View reviewed changes

MaskRay approved these changes Sep 26, 2024

View reviewed changes

cjappl merged commit f5b95db into llvm:main Sep 26, 2024
4 checks passed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

[rtsan] Only print out unique stack traces #110028

[rtsan] Only print out unique stack traces #110028

Uh oh!

cjappl commented Sep 25, 2024 •

edited

Loading

Uh oh!

cjappl commented Sep 25, 2024

Uh oh!

llvmbot commented Sep 25, 2024

Why?

How?

What to look out for

Questions

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

fmayer commented Sep 25, 2024

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

[rtsan] Only print out unique stack traces #110028

[rtsan] Only print out unique stack traces #110028

Uh oh!

Conversation

cjappl commented Sep 25, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Why?

What is unique?

How?

What to look out for

Questions

Uh oh!

cjappl commented Sep 25, 2024

Uh oh!

llvmbot commented Sep 25, 2024

Why?

How?

What to look out for

Questions

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

fmayer commented Sep 25, 2024

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

cjappl commented Sep 25, 2024 •

edited

Loading