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