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;
Marker(uptr V,uptr C,Kind S)23 Marker(uptr V, uptr C, Kind S) : Value(V), Count(C), K(S) {}
24
25 public:
Marker(uptr V,uptr C)26 Marker(uptr V, uptr C) : Marker(V, C, Kind::Value) {}
27
split(uptr V)28 static Marker split(uptr V) { return Marker(V, 0, Kind::Split); }
term()29 static Marker term() { return Marker(0, 0, Kind::End); }
30
isSplit() const31 bool isSplit() const { return K == Kind::Split; }
isTerm() const32 bool isTerm() const { return K == Kind::End; }
isVal() const33 bool isVal() const { return K == Kind::Value; }
34
operator ==(const Marker & M) const35 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.
getFctStartAddr(uptr CallsiteAddress) const42 uptr getFctStartAddr(uptr CallsiteAddress) const override {
43 return (CallsiteAddress / 100) * 100;
44 }
45
popAndCheck(ArrayRef<Marker> & Preorder,Marker M)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
checkSameImpl(const Trie & T,ArrayRef<Marker> & Preorder)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:
checkSame(ArrayRef<Marker> Preorder) const70 void checkSame(ArrayRef<Marker> Preorder) const {
71 checkSameImpl(TheTrie, Preorder);
72 ASSERT_THAT(Preorder, IsEmpty());
73 }
74 };
75
TEST(PerThreadCallsiteTrieTest,Insert)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
TEST(PerThreadCallsiteTrieTest,DetectRoots)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
TEST(PerThreadCallsiteTrieTest,DetectRootsNoBranches)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
TEST(PerThreadCallsiteTrieTest,DetectRootsUnknownFct)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