1 #include "../RootAutoDetector.h" 2 #include "sanitizer_common/sanitizer_array_ref.h" 3 #include "gmock/gmock.h" 4 #include "gtest/gtest.h" 5 6 using namespace __ctx_profile; 7 using ::testing::IsEmpty; 8 using ::testing::Not; 9 using ::testing::SizeIs; 10 11 // Utility for describing a preorder traversal. By default it captures the 12 // address and count at a callsite node. Implicitly nodes are expected to have 1 13 // child. If they have none, we place a Marker::term and if they have more than 14 // one, we place a Marker::split(nr_of_children) For example, using a list 15 // notation, and letters to denote a pair of address and count: 16 // (A (B C) (D (E F))) is a list of markers: A, split(2), B, term, C, 17 // term, D, split(2), E, term, F, term 18 class Marker { 19 enum class Kind { End, Value, Split }; 20 const uptr Value; 21 const uptr Count; 22 const Kind K; 23 Marker(uptr V, uptr C, Kind S) : Value(V), Count(C), K(S) {} 24 25 public: 26 Marker(uptr V, uptr C) : Marker(V, C, Kind::Value) {} 27 28 static Marker split(uptr V) { return Marker(V, 0, Kind::Split); } 29 static Marker term() { return Marker(0, 0, Kind::End); } 30 31 bool isSplit() const { return K == Kind::Split; } 32 bool isTerm() const { return K == Kind::End; } 33 bool isVal() const { return K == Kind::Value; } 34 35 bool operator==(const Marker &M) const { 36 return Value == M.Value && Count == M.Count && K == M.K; 37 } 38 }; 39 40 class MockCallsiteTrie final : public PerThreadCallsiteTrie { 41 // Return the first multiple of 100. 42 uptr getFctStartAddr(uptr CallsiteAddress) const override { 43 return (CallsiteAddress / 100) * 100; 44 } 45 46 static void popAndCheck(ArrayRef<Marker> &Preorder, Marker M) { 47 ASSERT_THAT(Preorder, Not(IsEmpty())); 48 ASSERT_EQ(Preorder[0], M); 49 Preorder = Preorder.drop_front(); 50 } 51 52 static void checkSameImpl(const Trie &T, ArrayRef<Marker> &Preorder) { 53 popAndCheck(Preorder, {T.CallsiteAddress, T.Count}); 54 55 if (T.Children.empty()) { 56 popAndCheck(Preorder, Marker::term()); 57 return; 58 } 59 60 if (T.Children.size() > 1) 61 popAndCheck(Preorder, Marker::split(T.Children.size())); 62 63 T.Children.forEach([&](const auto &KVP) { 64 checkSameImpl(KVP.second, Preorder); 65 return true; 66 }); 67 } 68 69 public: 70 void checkSame(ArrayRef<Marker> Preorder) const { 71 checkSameImpl(TheTrie, Preorder); 72 ASSERT_THAT(Preorder, IsEmpty()); 73 } 74 }; 75 76 TEST(PerThreadCallsiteTrieTest, Insert) { 77 MockCallsiteTrie R; 78 uptr Stack1[]{4, 3, 2, 1}; 79 R.insertStack(StackTrace(Stack1, 4)); 80 R.checkSame(ArrayRef<Marker>( 81 {{0, 1}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, Marker::term()})); 82 83 uptr Stack2[]{5, 4, 3, 2, 1}; 84 R.insertStack(StackTrace(Stack2, 5)); 85 R.checkSame(ArrayRef<Marker>( 86 {{0, 2}, {1, 2}, {2, 2}, {3, 2}, {4, 2}, {5, 1}, Marker::term()})); 87 88 uptr Stack3[]{6, 3, 2, 1}; 89 R.insertStack(StackTrace(Stack3, 4)); 90 R.checkSame(ArrayRef<Marker>({{0, 3}, 91 {1, 3}, 92 {2, 3}, 93 {3, 3}, 94 Marker::split(2), 95 {4, 2}, 96 {5, 1}, 97 Marker::term(), 98 {6, 1}, 99 Marker::term()})); 100 uptr Stack4[]{7, 2, 1}; 101 R.insertStack(StackTrace(Stack4, 3)); 102 R.checkSame(ArrayRef<Marker>({{0, 4}, 103 {1, 4}, 104 {2, 4}, 105 Marker::split(2), 106 {7, 1}, 107 Marker::term(), 108 {3, 3}, 109 Marker::split(2), 110 {4, 2}, 111 {5, 1}, 112 Marker::term(), 113 {6, 1}, 114 Marker::term()})); 115 } 116 117 TEST(PerThreadCallsiteTrieTest, DetectRoots) { 118 MockCallsiteTrie T; 119 120 uptr Stack1[]{501, 302, 202, 102}; 121 uptr Stack2[]{601, 402, 203, 102}; 122 T.insertStack({Stack1, 4}); 123 T.insertStack({Stack2, 4}); 124 125 auto R = T.determineRoots(); 126 EXPECT_THAT(R, SizeIs(2U)); 127 EXPECT_TRUE(R.contains(300)); 128 EXPECT_TRUE(R.contains(400)); 129 } 130 131 TEST(PerThreadCallsiteTrieTest, DetectRootsNoBranches) { 132 MockCallsiteTrie T; 133 134 uptr Stack1[]{501, 302, 202, 102}; 135 T.insertStack({Stack1, 4}); 136 137 auto R = T.determineRoots(); 138 EXPECT_THAT(R, IsEmpty()); 139 } 140 141 TEST(PerThreadCallsiteTrieTest, DetectRootsUnknownFct) { 142 MockCallsiteTrie T; 143 144 uptr Stack1[]{501, 302, 202, 102}; 145 // The MockCallsiteTree address resolver resolves addresses over 100, so 40 146 // will be mapped to 0. 147 uptr Stack2[]{601, 40, 203, 102}; 148 T.insertStack({Stack1, 4}); 149 T.insertStack({Stack2, 4}); 150 151 auto R = T.determineRoots(); 152 ASSERT_THAT(R, SizeIs(2U)); 153 EXPECT_TRUE(R.contains(300)); 154 EXPECT_TRUE(R.contains(0)); 155 } 156