1 /* 2 * Copyright (C) 2017 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "CallChainJoiner.h" 18 19 #include <gtest/gtest.h> 20 21 #include <environment.h> 22 23 using namespace simpleperf; 24 using namespace simpleperf::call_chain_joiner_impl; 25 26 static bool JoinCallChain(LRUCache& cache, uint32_t tid, 27 const std::vector<uint64_t>& input_ip, 28 const std::vector<uint64_t>& input_sp, 29 const std::vector<uint64_t>& expected_output_ip, 30 const std::vector<uint64_t>& expected_output_sp) { 31 std::vector<uint64_t> tmp_ip = input_ip; 32 std::vector<uint64_t> tmp_sp = input_sp; 33 cache.AddCallChain(tid, tmp_ip, tmp_sp); 34 return tmp_ip == expected_output_ip && tmp_sp == expected_output_sp; 35 } 36 37 TEST(LRUCache, different_nodes) { 38 LRUCache cache(sizeof(CacheNode) * 2, 1); 39 ASSERT_EQ(cache.Stat().max_node_count, 2u); 40 // different tids 41 std::vector<uint64_t> ip = {0x1}; 42 std::vector<uint64_t> sp = {0x1}; 43 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 44 ASSERT_TRUE(JoinCallChain(cache, 1, ip, sp, ip, sp)); 45 ASSERT_EQ(cache.Stat().used_node_count, 2u); 46 ASSERT_EQ(cache.Stat().recycled_node_count, 0u); 47 ASSERT_NE(cache.FindNode(0, ip[0], sp[0]), nullptr); 48 ASSERT_NE(cache.FindNode(1, ip[0], sp[0]), nullptr); 49 50 // different ips 51 std::vector<uint64_t> ip2 = {0x2}; 52 ASSERT_TRUE(JoinCallChain(cache, 0, ip2, sp, ip2, sp)); 53 ASSERT_EQ(cache.Stat().used_node_count, 2u); 54 ASSERT_EQ(cache.Stat().recycled_node_count, 1u); 55 ASSERT_EQ(cache.FindNode(0, ip[0], sp[0]), nullptr); 56 ASSERT_NE(cache.FindNode(0, ip2[0], sp[0]), nullptr); 57 ASSERT_NE(cache.FindNode(1, ip[0], sp[0]), nullptr); 58 59 // different sps 60 std::vector<uint64_t> sp2 = {0x2}; 61 ASSERT_TRUE(JoinCallChain(cache, 1, ip, sp2, ip, sp2)); 62 ASSERT_EQ(cache.Stat().used_node_count, 2u); 63 ASSERT_EQ(cache.Stat().recycled_node_count, 2u); 64 ASSERT_EQ(cache.FindNode(1, ip[0], sp[0]), nullptr); 65 ASSERT_NE(cache.FindNode(0, ip2[0], sp[0]), nullptr); 66 ASSERT_NE(cache.FindNode(1, ip[0], sp2[0]), nullptr); 67 } 68 69 TEST(LRUCache, extend_chains) { 70 // matched_node_count_to_extend_callchain = 1 71 // c -> b 72 // b -> a => c -> b -> a 73 LRUCache cache1(sizeof(CacheNode) * 4, 1); 74 ASSERT_TRUE(JoinCallChain(cache1, 0, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc})); 75 ASSERT_TRUE(JoinCallChain(cache1, 0, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc})); 76 ASSERT_EQ(cache1.Stat().used_node_count, 3u); 77 78 // matched_node_count_to_extend_callchain = 2 79 // c -> b 80 // b -> a 81 LRUCache cache2(sizeof(CacheNode) * 4, 2); 82 ASSERT_TRUE(JoinCallChain(cache2, 0, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc})); 83 ASSERT_TRUE(JoinCallChain(cache2, 0, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb})); 84 ASSERT_EQ(cache2.Stat().used_node_count, 3u); 85 86 // matched_node_count_to_extend_callchain = 2 87 // d -> c -> b 88 // c -> b -> a => d -> c -> b -> a 89 LRUCache cache3(sizeof(CacheNode) * 4, 2); 90 ASSERT_TRUE(JoinCallChain(cache3, 0, {0xb, 0xc, 0xd}, {0xb, 0xc, 0xd}, 91 {0xb, 0xc, 0xd}, {0xb, 0xc, 0xd})); 92 ASSERT_TRUE(JoinCallChain(cache3, 0, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc}, 93 {0xa, 0xb, 0xc, 0xd}, {0xa, 0xb, 0xc, 0xd})); 94 ASSERT_EQ(cache3.Stat().used_node_count, 4u); 95 } 96 97 TEST(LRUCache, avoid_ip_sp_loop) { 98 LRUCache cache(sizeof(CacheNode) * 2, 1); 99 std::vector<uint64_t> ip = {0xa, 0xb}; 100 std::vector<uint64_t> sp = {1, 1}; 101 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 102 ip = {0xb, 0xa}; 103 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 104 ASSERT_EQ(cache.Stat().used_node_count, 2u); 105 ASSERT_EQ(cache.Stat().recycled_node_count, 0u); 106 } 107 108 TEST(LRUCache, one_chain) { 109 LRUCache cache(sizeof(CacheNode) * 4, 1); 110 ASSERT_EQ(cache.Stat().max_node_count, 4u); 111 std::vector<uint64_t> ip; 112 std::vector<uint64_t> sp; 113 for (size_t i = 1u; i <= 4u; ++i) { 114 ip.push_back(i); 115 sp.push_back(i); 116 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 117 } 118 std::vector<uint64_t> origin_ip = ip; 119 std::vector<uint64_t> origin_sp = sp; 120 for (size_t i = ip.size(); i > 1; --i) { 121 ip.pop_back(); 122 sp.pop_back(); 123 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, origin_ip, origin_sp)); 124 } 125 ASSERT_EQ(cache.Stat().used_node_count, 4u); 126 ASSERT_EQ(cache.Stat().recycled_node_count, 0u); 127 } 128 129 TEST(LRUCache, many_chains) { 130 LRUCache cache(sizeof(CacheNode) * 12, 1); 131 // 4 -> 3 -> 2 -> 1 132 // 8 -> 7 -> 6 -> 5 133 // d -> c -> b -> a 134 std::vector<uint64_t> ip = {1, 2, 3, 4}; 135 std::vector<uint64_t> sp = {1, 2, 3, 4}; 136 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 137 ip = {5, 6, 7, 8}; 138 sp = {5, 6, 7, 8}; 139 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 140 ip = {0xa, 0xb, 0xc, 0xd}; 141 sp = {0xa, 0xb, 0xc, 0xd}; 142 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp)); 143 ASSERT_EQ(cache.Stat().used_node_count, 12u); 144 ASSERT_EQ(cache.Stat().recycled_node_count, 0u); 145 ASSERT_TRUE(JoinCallChain(cache, 0, {1}, {1}, {1, 2, 3, 4}, {1, 2, 3, 4})); 146 ASSERT_TRUE(JoinCallChain(cache, 0, {5, 6}, {5, 6}, {5, 6, 7, 8}, {5, 6, 7, 8})); 147 ASSERT_TRUE(JoinCallChain(cache, 0, {0xa}, {0xb}, {0xa}, {0xb})); 148 ASSERT_EQ(cache.Stat().used_node_count, 12u); 149 ASSERT_EQ(cache.Stat().recycled_node_count, 1u); 150 ASSERT_EQ(cache.FindNode(0, 0xa, 0xa), nullptr); 151 } 152 153 class CallChainJoinerTest : public ::testing::Test { 154 protected: 155 void SetUp() override { 156 #if defined(__ANDROID__) 157 std::string tmpdir = "/data/local/tmp"; 158 #else 159 std::string tmpdir = "/tmp"; 160 #endif 161 scoped_temp_files_.reset(new ScopedTempFiles(tmpdir)); 162 } 163 164 private: 165 std::unique_ptr<ScopedTempFiles> scoped_temp_files_; 166 }; 167 168 TEST_F(CallChainJoinerTest, smoke) { 169 CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, true); 170 for (pid_t pid = 0; pid < 10; ++pid) { 171 ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_OFFLINE, 172 {1, 2, 3}, {1, 2, 3})); 173 ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_REMOTE, 174 {3, 4, 5}, {3, 4, 5})); 175 ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_OFFLINE, 176 {1, 4}, {1, 4})); 177 } 178 ASSERT_TRUE(joiner.JoinCallChains()); 179 pid_t pid; 180 pid_t tid; 181 CallChainJoiner::ChainType type; 182 std::vector<uint64_t> ips; 183 std::vector<uint64_t> sps; 184 for (pid_t expected_pid = 0; expected_pid < 10; ++expected_pid) { 185 for (size_t i = 0; i < 2u; ++i) { 186 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 187 ASSERT_EQ(pid, expected_pid); 188 ASSERT_EQ(tid, expected_pid); 189 if (i == 0u) { 190 ASSERT_EQ(type, CallChainJoiner::ORIGINAL_OFFLINE); 191 ASSERT_EQ(ips, std::vector<uint64_t>({1, 2, 3})); 192 ASSERT_EQ(sps, std::vector<uint64_t>({1, 2, 3})); 193 } else { 194 ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE); 195 ASSERT_EQ(ips, std::vector<uint64_t>({1, 2, 3, 4, 5})); 196 ASSERT_EQ(sps, std::vector<uint64_t>({1, 2, 3, 4, 5})); 197 } 198 } 199 for (size_t i = 0; i < 2u; ++i) { 200 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 201 ASSERT_EQ(pid, expected_pid); 202 ASSERT_EQ(tid, expected_pid); 203 ASSERT_EQ(type, i == 0u ? CallChainJoiner::ORIGINAL_REMOTE 204 : CallChainJoiner::JOINED_REMOTE); 205 ASSERT_EQ(ips, std::vector<uint64_t>({3, 4, 5})); 206 ASSERT_EQ(sps, std::vector<uint64_t>({3, 4, 5})); 207 } 208 for (size_t i = 0; i < 2u; ++i) { 209 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 210 ASSERT_EQ(pid, expected_pid); 211 ASSERT_EQ(tid, expected_pid); 212 if (i == 0u) { 213 ASSERT_EQ(type, CallChainJoiner::ORIGINAL_OFFLINE); 214 ASSERT_EQ(ips, std::vector<uint64_t>({1, 4})); 215 ASSERT_EQ(sps, std::vector<uint64_t>({1, 4})); 216 } else { 217 ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE); 218 ASSERT_EQ(ips, std::vector<uint64_t>({1, 4, 5})); 219 ASSERT_EQ(sps, std::vector<uint64_t>({1, 4, 5})); 220 } 221 } 222 } 223 ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 224 joiner.DumpStat(); 225 ASSERT_EQ(joiner.GetCacheStat().cache_size, sizeof(CacheNode) * 1024); 226 ASSERT_EQ(joiner.GetCacheStat().matched_node_count_to_extend_callchain, 1u); 227 ASSERT_EQ(joiner.GetCacheStat().max_node_count, 1024u); 228 ASSERT_EQ(joiner.GetCacheStat().used_node_count, 50u); 229 ASSERT_EQ(joiner.GetCacheStat().recycled_node_count, 0u); 230 ASSERT_EQ(joiner.GetStat().chain_count, 30u); 231 ASSERT_EQ(joiner.GetStat().before_join_node_count, 80u); 232 ASSERT_EQ(joiner.GetStat().after_join_node_count, 110u); 233 ASSERT_EQ(joiner.GetStat().after_join_max_chain_length, 5u); 234 } 235 236 TEST_F(CallChainJoinerTest, no_original_chains) { 237 CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, false); 238 ASSERT_TRUE(joiner.AddCallChain(0, 0, CallChainJoiner::ORIGINAL_OFFLINE, {1}, {1})); 239 ASSERT_TRUE(joiner.JoinCallChains()); 240 pid_t pid; 241 pid_t tid; 242 CallChainJoiner::ChainType type; 243 std::vector<uint64_t> ips; 244 std::vector<uint64_t> sps; 245 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 246 ASSERT_EQ(pid, 0); 247 ASSERT_EQ(tid, 0); 248 ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE); 249 ASSERT_EQ(ips, std::vector<uint64_t>({1})); 250 ASSERT_EQ(sps, std::vector<uint64_t>({1})); 251 ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 252 joiner.DumpStat(); 253 } 254 255 TEST_F(CallChainJoinerTest, no_chains) { 256 CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, false); 257 ASSERT_TRUE(joiner.JoinCallChains()); 258 pid_t pid; 259 pid_t tid; 260 CallChainJoiner::ChainType type; 261 std::vector<uint64_t> ips; 262 std::vector<uint64_t> sps; 263 ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps)); 264 joiner.DumpStat(); 265 } 266