156 lines · cpp
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 the12// address and count at a callsite node. Implicitly nodes are expected to have 113// child. If they have none, we place a Marker::term and if they have more than14// one, we place a Marker::split(nr_of_children) For example, using a list15// 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, term18class 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, {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 69public:70 void checkSame(ArrayRef<Marker> Preorder) const {71 checkSameImpl(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(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 117TEST(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 131TEST(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 141TEST(PerThreadCallsiteTrieTest, DetectRootsUnknownFct) {142 MockCallsiteTrie T;143 144 uptr Stack1[]{501, 302, 202, 102};145 // The MockCallsiteTree address resolver resolves addresses over 100, so 40146 // 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