1//===-- sanitizer_stackdepot_test.cpp -------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file is a part of ThreadSanitizer/AddressSanitizer runtime.
10//
11//===----------------------------------------------------------------------===//
12#include "sanitizer_common/sanitizer_stackdepot.h"
13
14#include <algorithm>
15#include <atomic>
16#include <numeric>
17#include <regex>
18#include <sstream>
19#include <string>
20#include <thread>
21
22#include "gtest/gtest.h"
23#include "sanitizer_common/sanitizer_internal_defs.h"
24#include "sanitizer_common/sanitizer_libc.h"
25
26namespace __sanitizer {
27
28class StackDepotTest : public testing::Test {
29 protected:
30 void SetUp() override { StackDepotTestOnlyUnmap(); }
31 void TearDown() override {
32 StackDepotStats stack_depot_stats = StackDepotGetStats();
33 Printf(format: "StackDepot: %zd ids; %zdM allocated\n",
34 stack_depot_stats.n_uniq_ids, stack_depot_stats.allocated >> 20);
35 StackDepotTestOnlyUnmap();
36 }
37};
38
39TEST_F(StackDepotTest, Basic) {
40 uptr array[] = {1, 2, 3, 4, 5};
41 StackTrace s1(array, ARRAY_SIZE(array));
42 u32 i1 = StackDepotPut(stack: s1);
43 StackTrace stack = StackDepotGet(id: i1);
44 EXPECT_NE(stack.trace, (uptr*)0);
45 EXPECT_EQ(ARRAY_SIZE(array), stack.size);
46 EXPECT_EQ(0, internal_memcmp(s1: stack.trace, s2: array, n: sizeof(array)));
47}
48
49TEST_F(StackDepotTest, Absent) {
50 StackTrace stack = StackDepotGet(id: (1 << 30) - 1);
51 EXPECT_EQ((uptr*)0, stack.trace);
52}
53
54TEST_F(StackDepotTest, EmptyStack) {
55 u32 i1 = StackDepotPut(stack: StackTrace());
56 StackTrace stack = StackDepotGet(id: i1);
57 EXPECT_EQ((uptr*)0, stack.trace);
58}
59
60TEST_F(StackDepotTest, ZeroId) {
61 StackTrace stack = StackDepotGet(id: 0);
62 EXPECT_EQ((uptr*)0, stack.trace);
63}
64
65TEST_F(StackDepotTest, Same) {
66 uptr array[] = {1, 2, 3, 4, 6};
67 StackTrace s1(array, ARRAY_SIZE(array));
68 u32 i1 = StackDepotPut(stack: s1);
69 u32 i2 = StackDepotPut(stack: s1);
70 EXPECT_EQ(i1, i2);
71 StackTrace stack = StackDepotGet(id: i1);
72 EXPECT_NE(stack.trace, (uptr*)0);
73 EXPECT_EQ(ARRAY_SIZE(array), stack.size);
74 EXPECT_EQ(0, internal_memcmp(s1: stack.trace, s2: array, n: sizeof(array)));
75}
76
77TEST_F(StackDepotTest, Several) {
78 uptr array1[] = {1, 2, 3, 4, 7};
79 StackTrace s1(array1, ARRAY_SIZE(array1));
80 u32 i1 = StackDepotPut(stack: s1);
81 uptr array2[] = {1, 2, 3, 4, 8, 9};
82 StackTrace s2(array2, ARRAY_SIZE(array2));
83 u32 i2 = StackDepotPut(stack: s2);
84 EXPECT_NE(i1, i2);
85}
86
87TEST_F(StackDepotTest, Print) {
88 uptr array1[] = {0x111, 0x222, 0x333, 0x444, 0x777};
89 StackTrace s1(array1, ARRAY_SIZE(array1));
90 u32 i1 = StackDepotPut(stack: s1);
91 uptr array2[] = {0x1111, 0x2222, 0x3333, 0x4444, 0x8888, 0x9999};
92 StackTrace s2(array2, ARRAY_SIZE(array2));
93 u32 i2 = StackDepotPut(stack: s2);
94 EXPECT_NE(i1, i2);
95
96 auto fix_regex = [](const std::string& s) -> std::string {
97 if (!SANITIZER_WINDOWS)
98 return s;
99 return std::regex_replace(s, std::regex("\\.\\*"), ".*\\n.*");
100 };
101 EXPECT_EXIT(
102 (StackDepotPrintAll(), exit(0)), ::testing::ExitedWithCode(0),
103 fix_regex(
104 "Stack for id .*#0 0x0*1.*#1 0x0*2.*#2 0x0*3.*#3 0x0*4.*#4 0x0*7.*"));
105 EXPECT_EXIT((StackDepotPrintAll(), exit(0)), ::testing::ExitedWithCode(0),
106 fix_regex("Stack for id .*#0 0x0*1.*#1 0x0*2.*#2 0x0*3.*#3 "
107 "0x0*4.*#4 0x0*8.*#5 0x0*9.*"));
108}
109
110TEST_F(StackDepotTest, PrintNoLock) {
111 u32 n = 2000;
112 std::vector<u32> idx2id(n);
113 for (u32 i = 0; i < n; ++i) {
114 uptr array[] = {0x111, 0x222, i, 0x444, 0x777};
115 StackTrace s(array, ARRAY_SIZE(array));
116 idx2id[i] = StackDepotPut(s);
117 }
118 StackDepotPrintAll();
119 for (u32 i = 0; i < n; ++i) {
120 uptr array[] = {0x111, 0x222, i, 0x444, 0x777};
121 StackTrace s(array, ARRAY_SIZE(array));
122 CHECK_EQ(idx2id[i], StackDepotPut(s));
123 }
124}
125
126static struct StackDepotBenchmarkParams {
127 int UniqueStacksPerThread;
128 int RepeatPerThread;
129 int Threads;
130 bool UniqueThreads;
131 bool UseCount;
132} params[] = {
133 // All traces are unique, very unusual.
134 {.UniqueStacksPerThread: 10000000, .RepeatPerThread: 1, .Threads: 1, .UniqueThreads: false, .UseCount: false},
135 {.UniqueStacksPerThread: 8000000, .RepeatPerThread: 1, .Threads: 4, .UniqueThreads: false, .UseCount: false},
136 {.UniqueStacksPerThread: 8000000, .RepeatPerThread: 1, .Threads: 16, .UniqueThreads: false, .UseCount: false},
137 // Probably most realistic sets.
138 {.UniqueStacksPerThread: 3000000, .RepeatPerThread: 10, .Threads: 1, .UniqueThreads: false, .UseCount: false},
139 {.UniqueStacksPerThread: 3000000, .RepeatPerThread: 10, .Threads: 4, .UniqueThreads: false, .UseCount: false},
140 {.UniqueStacksPerThread: 3000000, .RepeatPerThread: 10, .Threads: 16, .UniqueThreads: false, .UseCount: false},
141 // Update use count as msan/dfsan.
142 {.UniqueStacksPerThread: 3000000, .RepeatPerThread: 10, .Threads: 1, .UniqueThreads: false, .UseCount: true},
143 {.UniqueStacksPerThread: 3000000, .RepeatPerThread: 10, .Threads: 4, .UniqueThreads: false, .UseCount: true},
144 {.UniqueStacksPerThread: 3000000, .RepeatPerThread: 10, .Threads: 16, .UniqueThreads: false, .UseCount: true},
145 // Unrealistic, as above, but traces are unique inside of thread.
146 {.UniqueStacksPerThread: 4000000, .RepeatPerThread: 1, .Threads: 4, .UniqueThreads: true, .UseCount: false},
147 {.UniqueStacksPerThread: 2000000, .RepeatPerThread: 1, .Threads: 16, .UniqueThreads: true, .UseCount: false},
148 {.UniqueStacksPerThread: 2000000, .RepeatPerThread: 10, .Threads: 4, .UniqueThreads: true, .UseCount: false},
149 {.UniqueStacksPerThread: 500000, .RepeatPerThread: 10, .Threads: 16, .UniqueThreads: true, .UseCount: false},
150 {.UniqueStacksPerThread: 1500000, .RepeatPerThread: 10, .Threads: 4, .UniqueThreads: true, .UseCount: true},
151 {.UniqueStacksPerThread: 800000, .RepeatPerThread: 10, .Threads: 16, .UniqueThreads: true, .UseCount: true},
152 // Go crazy, and create too many unique stacks, such that StackStore runs
153 // out of space.
154 {.UniqueStacksPerThread: 1000000, .RepeatPerThread: 1, .Threads: 128, .UniqueThreads: true, .UseCount: true},
155 {.UniqueStacksPerThread: 100000000, .RepeatPerThread: 1, .Threads: 1, .UniqueThreads: true, .UseCount: true},
156};
157
158static std::string PrintStackDepotBenchmarkParams(
159 const testing::TestParamInfo<StackDepotBenchmarkParams>& info) {
160 std::stringstream name;
161 name << info.param.UniqueStacksPerThread << "_" << info.param.RepeatPerThread
162 << "_" << info.param.Threads << (info.param.UseCount ? "_UseCount" : "")
163 << (info.param.UniqueThreads ? "_UniqueThreads" : "");
164 return name.str();
165}
166
167class StackDepotBenchmark
168 : public StackDepotTest,
169 public testing::WithParamInterface<StackDepotBenchmarkParams> {};
170
171// Test which can be used as a simple benchmark. It's disabled to avoid slowing
172// down check-sanitizer.
173// Usage: Sanitizer-<ARCH>-Test --gtest_also_run_disabled_tests \
174// '--gtest_filter=*Benchmark*'
175TEST_P(StackDepotBenchmark, DISABLED_Benchmark) {
176 auto Param = GetParam();
177 std::atomic<unsigned int> here = {};
178
179 auto thread = [&](int idx) {
180 here++;
181 while (here < Param.UniqueThreads) std::this_thread::yield();
182
183 std::vector<uptr> frames(64);
184 for (int r = 0; r < Param.RepeatPerThread; ++r) {
185 std::iota(frames.begin(), frames.end(), idx + 1);
186 for (int i = 0; i < Param.UniqueStacksPerThread; ++i) {
187 StackTrace s(frames.data(), frames.size());
188 auto h = StackDepotPut_WithHandle(stack: s);
189 if (Param.UseCount)
190 h.inc_use_count_unsafe();
191 std::next_permutation(frames.begin(), frames.end());
192 };
193 }
194 };
195
196 std::vector<std::thread> threads;
197 for (int i = 0; i < Param.Threads; ++i)
198 threads.emplace_back(thread, Param.UniqueThreads * i);
199 for (auto& t : threads) t.join();
200}
201
202INSTANTIATE_TEST_SUITE_P(StackDepotBenchmarkSuite, StackDepotBenchmark,
203 testing::ValuesIn(params),
204 PrintStackDepotBenchmarkParams);
205
206} // namespace __sanitizer
207

source code of compiler-rt/lib/sanitizer_common/tests/sanitizer_stackdepot_test.cpp