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 26 namespace __sanitizer { 27 28 class StackDepotTest : public testing::Test { 29 protected: 30 void SetUp() override { StackDepotTestOnlyUnmap(); } 31 void TearDown() override { 32 StackDepotStats stack_depot_stats = StackDepotGetStats(); 33 Printf("StackDepot: %zd ids; %zdM allocated\n", 34 stack_depot_stats.n_uniq_ids, stack_depot_stats.allocated >> 20); 35 StackDepotTestOnlyUnmap(); 36 } 37 }; 38 39 TEST_F(StackDepotTest, Basic) { 40 uptr array[] = {1, 2, 3, 4, 5}; 41 StackTrace s1(array, ARRAY_SIZE(array)); 42 u32 i1 = StackDepotPut(s1); 43 StackTrace stack = StackDepotGet(i1); 44 EXPECT_NE(stack.trace, (uptr*)0); 45 EXPECT_EQ(ARRAY_SIZE(array), stack.size); 46 EXPECT_EQ(0, internal_memcmp(stack.trace, array, sizeof(array))); 47 } 48 49 TEST_F(StackDepotTest, Absent) { 50 StackTrace stack = StackDepotGet((1 << 30) - 1); 51 EXPECT_EQ((uptr*)0, stack.trace); 52 } 53 54 TEST_F(StackDepotTest, EmptyStack) { 55 u32 i1 = StackDepotPut(StackTrace()); 56 StackTrace stack = StackDepotGet(i1); 57 EXPECT_EQ((uptr*)0, stack.trace); 58 } 59 60 TEST_F(StackDepotTest, ZeroId) { 61 StackTrace stack = StackDepotGet(0); 62 EXPECT_EQ((uptr*)0, stack.trace); 63 } 64 65 TEST_F(StackDepotTest, Same) { 66 uptr array[] = {1, 2, 3, 4, 6}; 67 StackTrace s1(array, ARRAY_SIZE(array)); 68 u32 i1 = StackDepotPut(s1); 69 u32 i2 = StackDepotPut(s1); 70 EXPECT_EQ(i1, i2); 71 StackTrace stack = StackDepotGet(i1); 72 EXPECT_NE(stack.trace, (uptr*)0); 73 EXPECT_EQ(ARRAY_SIZE(array), stack.size); 74 EXPECT_EQ(0, internal_memcmp(stack.trace, array, sizeof(array))); 75 } 76 77 TEST_F(StackDepotTest, Several) { 78 uptr array1[] = {1, 2, 3, 4, 7}; 79 StackTrace s1(array1, ARRAY_SIZE(array1)); 80 u32 i1 = StackDepotPut(s1); 81 uptr array2[] = {1, 2, 3, 4, 8, 9}; 82 StackTrace s2(array2, ARRAY_SIZE(array2)); 83 u32 i2 = StackDepotPut(s2); 84 EXPECT_NE(i1, i2); 85 } 86 87 TEST_F(StackDepotTest, Print) { 88 uptr array1[] = {0x111, 0x222, 0x333, 0x444, 0x777}; 89 StackTrace s1(array1, ARRAY_SIZE(array1)); 90 u32 i1 = StackDepotPut(s1); 91 uptr array2[] = {0x1111, 0x2222, 0x3333, 0x4444, 0x8888, 0x9999}; 92 StackTrace s2(array2, ARRAY_SIZE(array2)); 93 u32 i2 = StackDepotPut(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 110 TEST_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 126 static 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 {10000000, 1, 1, false, false}, 135 {8000000, 1, 4, false, false}, 136 {8000000, 1, 16, false, false}, 137 // Probably most realistic sets. 138 {3000000, 10, 1, false, false}, 139 {3000000, 10, 4, false, false}, 140 {3000000, 10, 16, false, false}, 141 // Update use count as msan/dfsan. 142 {3000000, 10, 1, false, true}, 143 {3000000, 10, 4, false, true}, 144 {3000000, 10, 16, false, true}, 145 // Unrealistic, as above, but traces are unique inside of thread. 146 {4000000, 1, 4, true, false}, 147 {2000000, 1, 16, true, false}, 148 {2000000, 10, 4, true, false}, 149 {500000, 10, 16, true, false}, 150 {1500000, 10, 4, true, true}, 151 {800000, 10, 16, true, true}, 152 // Go crazy, and create too many unique stacks, such that StackStore runs 153 // out of space. 154 {1000000, 1, 128, true, true}, 155 {100000000, 1, 1, true, true}, 156 }; 157 158 static 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 167 class 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*' 175 TEST_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(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 202 INSTANTIATE_TEST_SUITE_P(StackDepotBenchmarkSuite, StackDepotBenchmark, 203 testing::ValuesIn(params), 204 PrintStackDepotBenchmarkParams); 205 206 } // namespace __sanitizer 207