1 //===-- sanitizer_stack_store_test.cpp --------------------------*- C++ -*-===// 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 #include "sanitizer_common/sanitizer_stack_store.h" 9 10 #include <algorithm> 11 #include <numeric> 12 #include <vector> 13 14 #include "gtest/gtest.h" 15 #include "sanitizer_atomic.h" 16 #include "sanitizer_hash.h" 17 #include "sanitizer_stacktrace.h" 18 19 namespace __sanitizer { 20 21 class StackStoreTest : public testing::Test { 22 protected: 23 void SetUp() override {} 24 void TearDown() override { store_.TestOnlyUnmap(); } 25 26 template <typename Fn> 27 void ForEachTrace(Fn fn, uptr n = 1000000) { 28 std::vector<uptr> frames(kStackTraceMax); 29 std::iota(frames.begin(), frames.end(), 0x100000); 30 MurMur2HashBuilder h(0); 31 for (uptr i = 0; i < n; ++i) { 32 h.add(i); 33 u32 size = h.get() % kStackTraceMax; 34 h.add(i); 35 uptr tag = h.get() % 256; 36 StackTrace s(frames.data(), size, tag); 37 if (!s.size && !s.tag) 38 continue; 39 fn(s); 40 if (HasFailure()) 41 return; 42 std::next_permutation(frames.begin(), frames.end()); 43 }; 44 } 45 46 using BlockInfo = StackStore::BlockInfo; 47 48 uptr GetTotalFramesCount() const { 49 return atomic_load_relaxed(&store_.total_frames_); 50 } 51 52 uptr CountReadyToPackBlocks() { 53 uptr res = 0; 54 for (BlockInfo& b : store_.blocks_) res += b.Stored(0); 55 return res; 56 } 57 58 uptr CountPackedBlocks() const { 59 uptr res = 0; 60 for (const BlockInfo& b : store_.blocks_) res += b.IsPacked(); 61 return res; 62 } 63 64 uptr IdToOffset(StackStore::Id id) const { return store_.IdToOffset(id); } 65 66 static constexpr uptr kBlockSizeFrames = StackStore::kBlockSizeFrames; 67 static constexpr uptr kBlockSizeBytes = StackStore::kBlockSizeBytes; 68 69 StackStore store_ = {}; 70 }; 71 72 TEST_F(StackStoreTest, Empty) { 73 uptr before = store_.Allocated(); 74 uptr pack = 0; 75 EXPECT_EQ(0u, store_.Store({}, &pack)); 76 uptr after = store_.Allocated(); 77 EXPECT_EQ(before, after); 78 } 79 80 TEST_F(StackStoreTest, Basic) { 81 std::vector<StackStore::Id> ids; 82 ForEachTrace([&](const StackTrace& s) { 83 uptr pack = 0; 84 ids.push_back(store_.Store(s, &pack)); 85 }); 86 87 auto id = ids.begin(); 88 ForEachTrace([&](const StackTrace& s) { 89 StackTrace trace = store_.Load(*(id++)); 90 EXPECT_EQ(s.size, trace.size); 91 EXPECT_EQ(s.tag, trace.tag); 92 EXPECT_EQ(std::vector<uptr>(s.trace, s.trace + s.size), 93 std::vector<uptr>(trace.trace, trace.trace + trace.size)); 94 }); 95 } 96 97 TEST_F(StackStoreTest, Allocated) { 98 EXPECT_LE(store_.Allocated(), 0x100000u); 99 std::vector<StackStore::Id> ids; 100 ForEachTrace([&](const StackTrace& s) { 101 uptr pack = 0; 102 ids.push_back(store_.Store(s, &pack)); 103 }); 104 EXPECT_NEAR(store_.Allocated(), FIRST_32_SECOND_64(500000000u, 1000000000u), 105 FIRST_32_SECOND_64(50000000u, 100000000u)); 106 store_.TestOnlyUnmap(); 107 EXPECT_LE(store_.Allocated(), 0x100000u); 108 } 109 110 TEST_F(StackStoreTest, ReadyToPack) { 111 uptr next_pack = kBlockSizeFrames; 112 uptr total_ready = 0; 113 ForEachTrace( 114 [&](const StackTrace& s) { 115 uptr pack = 0; 116 StackStore::Id id = store_.Store(s, &pack); 117 uptr end_idx = IdToOffset(id) + 1 + s.size; 118 if (end_idx >= next_pack) { 119 EXPECT_EQ(1u, pack); 120 next_pack += kBlockSizeFrames; 121 } else { 122 EXPECT_EQ(0u, pack); 123 } 124 total_ready += pack; 125 EXPECT_EQ(CountReadyToPackBlocks(), total_ready); 126 }, 127 100000); 128 EXPECT_EQ(GetTotalFramesCount() / kBlockSizeFrames, total_ready); 129 } 130 131 struct StackStorePackTest : public StackStoreTest, 132 public ::testing::WithParamInterface< 133 std::pair<StackStore::Compression, uptr>> {}; 134 135 INSTANTIATE_TEST_SUITE_P( 136 PackUnpacks, StackStorePackTest, 137 ::testing::ValuesIn({ 138 StackStorePackTest::ParamType(StackStore::Compression::Delta, 139 FIRST_32_SECOND_64(2, 6)), 140 StackStorePackTest::ParamType(StackStore::Compression::LZW, 141 FIRST_32_SECOND_64(60, 130)), 142 })); 143 144 TEST_P(StackStorePackTest, PackUnpack) { 145 std::vector<StackStore::Id> ids; 146 StackStore::Compression type = GetParam().first; 147 uptr expected_ratio = GetParam().second; 148 ForEachTrace([&](const StackTrace& s) { 149 uptr pack = 0; 150 ids.push_back(store_.Store(s, &pack)); 151 if (pack) { 152 uptr before = store_.Allocated(); 153 uptr diff = store_.Pack(type); 154 uptr after = store_.Allocated(); 155 EXPECT_EQ(before - after, diff); 156 EXPECT_LT(after, before); 157 EXPECT_GE(kBlockSizeBytes / (kBlockSizeBytes - (before - after)), 158 expected_ratio); 159 } 160 }); 161 uptr packed_blocks = CountPackedBlocks(); 162 // Unpack random block. 163 store_.Load(kBlockSizeFrames * 7 + 123); 164 EXPECT_EQ(packed_blocks - 1, CountPackedBlocks()); 165 166 // Unpack all blocks. 167 auto id = ids.begin(); 168 ForEachTrace([&](const StackTrace& s) { 169 StackTrace trace = store_.Load(*(id++)); 170 EXPECT_EQ(s.size, trace.size); 171 EXPECT_EQ(s.tag, trace.tag); 172 EXPECT_EQ(std::vector<uptr>(s.trace, s.trace + s.size), 173 std::vector<uptr>(trace.trace, trace.trace + trace.size)); 174 }); 175 EXPECT_EQ(0u, CountPackedBlocks()); 176 177 EXPECT_EQ(0u, store_.Pack(type)); 178 EXPECT_EQ(0u, CountPackedBlocks()); 179 } 180 181 TEST_P(StackStorePackTest, Failed) { 182 MurMur2Hash64Builder h(0); 183 StackStore::Compression type = GetParam().first; 184 std::vector<uptr> frames(200); 185 for (uptr i = 0; i < kBlockSizeFrames * 4 / frames.size(); ++i) { 186 for (uptr& f : frames) { 187 h.add(1); 188 // Make it difficult to pack. 189 f = h.get(); 190 } 191 uptr pack = 0; 192 store_.Store(StackTrace(frames.data(), frames.size()), &pack); 193 if (pack) 194 EXPECT_EQ(0u, store_.Pack(type)); 195 } 196 197 EXPECT_EQ(0u, CountPackedBlocks()); 198 } 199 200 } // namespace __sanitizer 201