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, M: {T.CallsiteAddress, T.Count}); |
54 | |
55 | if (T.Children.empty()) { |
56 | popAndCheck(Preorder, M: Marker::term()); |
57 | return; |
58 | } |
59 | |
60 | if (T.Children.size() > 1) |
61 | popAndCheck(Preorder, M: Marker::split(V: T.Children.size())); |
62 | |
63 | T.Children.forEach(fn: [&](const auto &KVP) { |
64 | checkSameImpl(T: KVP.second, Preorder); |
65 | return true; |
66 | }); |
67 | } |
68 | |
69 | public: |
70 | void checkSame(ArrayRef<Marker> Preorder) const { |
71 | checkSameImpl(T: 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(ST: StackTrace(Stack1, 4)); |
80 | R.checkSame(Preorder: 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(ST: StackTrace(Stack2, 5)); |
85 | R.checkSame(Preorder: 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(ST: StackTrace(Stack3, 4)); |
90 | R.checkSame(Preorder: ArrayRef<Marker>({{0, 3}, |
91 | {1, 3}, |
92 | {2, 3}, |
93 | {3, 3}, |
94 | Marker::split(V: 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(ST: StackTrace(Stack4, 3)); |
102 | R.checkSame(Preorder: ArrayRef<Marker>({{0, 4}, |
103 | {1, 4}, |
104 | {2, 4}, |
105 | Marker::split(V: 2), |
106 | {7, 1}, |
107 | Marker::term(), |
108 | {3, 3}, |
109 | Marker::split(V: 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(ST: {Stack1, 4}); |
123 | T.insertStack(ST: {Stack2, 4}); |
124 | |
125 | auto R = T.determineRoots(); |
126 | EXPECT_THAT(R, SizeIs(2U)); |
127 | EXPECT_TRUE(R.contains(Key: 300)); |
128 | EXPECT_TRUE(R.contains(Key: 400)); |
129 | } |
130 | |
131 | TEST(PerThreadCallsiteTrieTest, DetectRootsNoBranches) { |
132 | MockCallsiteTrie T; |
133 | |
134 | uptr Stack1[]{501, 302, 202, 102}; |
135 | T.insertStack(ST: {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(ST: {Stack1, 4}); |
149 | T.insertStack(ST: {Stack2, 4}); |
150 | |
151 | auto R = T.determineRoots(); |
152 | ASSERT_THAT(R, SizeIs(2U)); |
153 | EXPECT_TRUE(R.contains(Key: 300)); |
154 | EXPECT_TRUE(R.contains(Key: 0)); |
155 | } |
156 | |