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
JoinCallChain(LRUCache & cache,uint32_t tid,const std::vector<uint64_t> & input_ip,const std::vector<uint64_t> & input_sp,const std::vector<uint64_t> & expected_output_ip,const std::vector<uint64_t> & expected_output_sp)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
TEST(LRUCache,different_nodes)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
TEST(LRUCache,extend_chains)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
TEST(LRUCache,avoid_ip_sp_loop)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
TEST(LRUCache,one_chain)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
TEST(LRUCache,many_chains)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:
SetUp()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
TEST_F(CallChainJoinerTest,smoke)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
TEST_F(CallChainJoinerTest,no_original_chains)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
TEST_F(CallChainJoinerTest,no_chains)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