1#include "../RootAutoDetector.h"
2#include "sanitizer_common/sanitizer_array_ref.h"
3#include "gmock/gmock.h"
4#include "gtest/gtest.h"
5
6using namespace __ctx_profile;
7using ::testing::IsEmpty;
8using ::testing::Not;
9using ::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
18class 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
25public:
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
40class 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
69public:
70 void checkSame(ArrayRef<Marker> Preorder) const {
71 checkSameImpl(T: TheTrie, Preorder);
72 ASSERT_THAT(Preorder, IsEmpty());
73 }
74};
75
76TEST(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
117TEST(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
131TEST(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
141TEST(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

source code of compiler-rt/lib/ctx_profile/tests/RootAutoDetectorTest.cpp