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, const std::vector<uint64_t>& input_ip,
27 const std::vector<uint64_t>& input_sp,
28 const std::vector<uint64_t>& expected_output_ip,
29 const std::vector<uint64_t>& expected_output_sp) {
30 std::vector<uint64_t> tmp_ip = input_ip;
31 std::vector<uint64_t> tmp_sp = input_sp;
32 cache.AddCallChain(tid, tmp_ip, tmp_sp);
33 return tmp_ip == expected_output_ip && tmp_sp == expected_output_sp;
34 }
35
36 // @CddTest = 6.1/C-0-2
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
69 // @CddTest = 6.1/C-0-2
TEST(LRUCache,extend_chains)70 TEST(LRUCache, extend_chains) {
71 // matched_node_count_to_extend_callchain = 1
72 // c -> b
73 // b -> a => c -> b -> a
74 LRUCache cache1(sizeof(CacheNode) * 4, 1);
75 ASSERT_TRUE(JoinCallChain(cache1, 0, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}));
76 ASSERT_TRUE(JoinCallChain(cache1, 0, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc}));
77 ASSERT_EQ(cache1.Stat().used_node_count, 3u);
78
79 // matched_node_count_to_extend_callchain = 2
80 // c -> b
81 // b -> a
82 LRUCache cache2(sizeof(CacheNode) * 4, 2);
83 ASSERT_TRUE(JoinCallChain(cache2, 0, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}));
84 ASSERT_TRUE(JoinCallChain(cache2, 0, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb}));
85 ASSERT_EQ(cache2.Stat().used_node_count, 3u);
86
87 // matched_node_count_to_extend_callchain = 2
88 // d -> c -> b
89 // c -> b -> a => d -> c -> b -> a
90 LRUCache cache3(sizeof(CacheNode) * 4, 2);
91 ASSERT_TRUE(
92 JoinCallChain(cache3, 0, {0xb, 0xc, 0xd}, {0xb, 0xc, 0xd}, {0xb, 0xc, 0xd}, {0xb, 0xc, 0xd}));
93 ASSERT_TRUE(JoinCallChain(cache3, 0, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc, 0xd},
94 {0xa, 0xb, 0xc, 0xd}));
95 ASSERT_EQ(cache3.Stat().used_node_count, 4u);
96 }
97
98 // @CddTest = 6.1/C-0-2
TEST(LRUCache,avoid_ip_sp_loop)99 TEST(LRUCache, avoid_ip_sp_loop) {
100 LRUCache cache(sizeof(CacheNode) * 2, 1);
101 std::vector<uint64_t> ip = {0xa, 0xb};
102 std::vector<uint64_t> sp = {1, 1};
103 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
104 ip = {0xb, 0xa};
105 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
106 ASSERT_EQ(cache.Stat().used_node_count, 2u);
107 ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
108 }
109
110 // @CddTest = 6.1/C-0-2
TEST(LRUCache,one_chain)111 TEST(LRUCache, one_chain) {
112 LRUCache cache(sizeof(CacheNode) * 4, 1);
113 ASSERT_EQ(cache.Stat().max_node_count, 4u);
114 std::vector<uint64_t> ip;
115 std::vector<uint64_t> sp;
116 for (size_t i = 1u; i <= 4u; ++i) {
117 ip.push_back(i);
118 sp.push_back(i);
119 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
120 }
121 std::vector<uint64_t> origin_ip = ip;
122 std::vector<uint64_t> origin_sp = sp;
123 for (size_t i = ip.size(); i > 1; --i) {
124 ip.pop_back();
125 sp.pop_back();
126 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, origin_ip, origin_sp));
127 }
128 ASSERT_EQ(cache.Stat().used_node_count, 4u);
129 ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
130 }
131
132 // @CddTest = 6.1/C-0-2
TEST(LRUCache,many_chains)133 TEST(LRUCache, many_chains) {
134 LRUCache cache(sizeof(CacheNode) * 12, 1);
135 // 4 -> 3 -> 2 -> 1
136 // 8 -> 7 -> 6 -> 5
137 // d -> c -> b -> a
138 std::vector<uint64_t> ip = {1, 2, 3, 4};
139 std::vector<uint64_t> sp = {1, 2, 3, 4};
140 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
141 ip = {5, 6, 7, 8};
142 sp = {5, 6, 7, 8};
143 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
144 ip = {0xa, 0xb, 0xc, 0xd};
145 sp = {0xa, 0xb, 0xc, 0xd};
146 ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
147 ASSERT_EQ(cache.Stat().used_node_count, 12u);
148 ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
149 ASSERT_TRUE(JoinCallChain(cache, 0, {1}, {1}, {1, 2, 3, 4}, {1, 2, 3, 4}));
150 ASSERT_TRUE(JoinCallChain(cache, 0, {5, 6}, {5, 6}, {5, 6, 7, 8}, {5, 6, 7, 8}));
151 ASSERT_TRUE(JoinCallChain(cache, 0, {0xa}, {0xb}, {0xa}, {0xb}));
152 ASSERT_EQ(cache.Stat().used_node_count, 12u);
153 ASSERT_EQ(cache.Stat().recycled_node_count, 1u);
154 ASSERT_EQ(cache.FindNode(0, 0xa, 0xa), nullptr);
155 }
156
157 // @CddTest = 6.1/C-0-2
158 class CallChainJoinerTest : public ::testing::Test {
159 protected:
SetUp()160 void SetUp() override {
161 #if defined(__ANDROID__)
162 std::string tmpdir = "/data/local/tmp";
163 #else
164 std::string tmpdir = "/tmp";
165 #endif
166 scoped_temp_files_ = ScopedTempFiles::Create(tmpdir);
167 }
168
169 private:
170 std::unique_ptr<ScopedTempFiles> scoped_temp_files_;
171 };
172
173 // @CddTest = 6.1/C-0-2
TEST_F(CallChainJoinerTest,smoke)174 TEST_F(CallChainJoinerTest, smoke) {
175 CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, true);
176 for (pid_t pid = 0; pid < 10; ++pid) {
177 ASSERT_TRUE(
178 joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_OFFLINE, {1, 2, 3}, {1, 2, 3}));
179 ASSERT_TRUE(
180 joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_REMOTE, {3, 4, 5}, {3, 4, 5}));
181 ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_OFFLINE, {1, 4}, {1, 4}));
182 }
183 ASSERT_TRUE(joiner.JoinCallChains());
184 pid_t pid;
185 pid_t tid;
186 CallChainJoiner::ChainType type;
187 std::vector<uint64_t> ips;
188 std::vector<uint64_t> sps;
189 for (pid_t expected_pid = 0; expected_pid < 10; ++expected_pid) {
190 for (size_t i = 0; i < 2u; ++i) {
191 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
192 ASSERT_EQ(pid, expected_pid);
193 ASSERT_EQ(tid, expected_pid);
194 if (i == 0u) {
195 ASSERT_EQ(type, CallChainJoiner::ORIGINAL_OFFLINE);
196 ASSERT_EQ(ips, std::vector<uint64_t>({1, 2, 3}));
197 ASSERT_EQ(sps, std::vector<uint64_t>({1, 2, 3}));
198 } else {
199 ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE);
200 ASSERT_EQ(ips, std::vector<uint64_t>({1, 2, 3, 4, 5}));
201 ASSERT_EQ(sps, std::vector<uint64_t>({1, 2, 3, 4, 5}));
202 }
203 }
204 for (size_t i = 0; i < 2u; ++i) {
205 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
206 ASSERT_EQ(pid, expected_pid);
207 ASSERT_EQ(tid, expected_pid);
208 ASSERT_EQ(type, i == 0u ? CallChainJoiner::ORIGINAL_REMOTE : CallChainJoiner::JOINED_REMOTE);
209 ASSERT_EQ(ips, std::vector<uint64_t>({3, 4, 5}));
210 ASSERT_EQ(sps, std::vector<uint64_t>({3, 4, 5}));
211 }
212 for (size_t i = 0; i < 2u; ++i) {
213 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
214 ASSERT_EQ(pid, expected_pid);
215 ASSERT_EQ(tid, expected_pid);
216 if (i == 0u) {
217 ASSERT_EQ(type, CallChainJoiner::ORIGINAL_OFFLINE);
218 ASSERT_EQ(ips, std::vector<uint64_t>({1, 4}));
219 ASSERT_EQ(sps, std::vector<uint64_t>({1, 4}));
220 } else {
221 ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE);
222 ASSERT_EQ(ips, std::vector<uint64_t>({1, 4, 5}));
223 ASSERT_EQ(sps, std::vector<uint64_t>({1, 4, 5}));
224 }
225 }
226 }
227 ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
228 joiner.DumpStat();
229 ASSERT_EQ(joiner.GetCacheStat().cache_size, sizeof(CacheNode) * 1024);
230 ASSERT_EQ(joiner.GetCacheStat().matched_node_count_to_extend_callchain, 1u);
231 ASSERT_EQ(joiner.GetCacheStat().max_node_count, 1024u);
232 ASSERT_EQ(joiner.GetCacheStat().used_node_count, 50u);
233 ASSERT_EQ(joiner.GetCacheStat().recycled_node_count, 0u);
234 ASSERT_EQ(joiner.GetStat().chain_count, 30u);
235 ASSERT_EQ(joiner.GetStat().before_join_node_count, 80u);
236 ASSERT_EQ(joiner.GetStat().after_join_node_count, 110u);
237 ASSERT_EQ(joiner.GetStat().after_join_max_chain_length, 5u);
238 }
239
240 // @CddTest = 6.1/C-0-2
TEST_F(CallChainJoinerTest,no_original_chains)241 TEST_F(CallChainJoinerTest, no_original_chains) {
242 CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, false);
243 ASSERT_TRUE(joiner.AddCallChain(0, 0, CallChainJoiner::ORIGINAL_OFFLINE, {1}, {1}));
244 ASSERT_TRUE(joiner.JoinCallChains());
245 pid_t pid;
246 pid_t tid;
247 CallChainJoiner::ChainType type;
248 std::vector<uint64_t> ips;
249 std::vector<uint64_t> sps;
250 ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
251 ASSERT_EQ(pid, 0);
252 ASSERT_EQ(tid, 0);
253 ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE);
254 ASSERT_EQ(ips, std::vector<uint64_t>({1}));
255 ASSERT_EQ(sps, std::vector<uint64_t>({1}));
256 ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
257 joiner.DumpStat();
258 }
259
260 // @CddTest = 6.1/C-0-2
TEST_F(CallChainJoinerTest,no_chains)261 TEST_F(CallChainJoinerTest, no_chains) {
262 CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, false);
263 ASSERT_TRUE(joiner.JoinCallChains());
264 pid_t pid;
265 pid_t tid;
266 CallChainJoiner::ChainType type;
267 std::vector<uint64_t> ips;
268 std::vector<uint64_t> sps;
269 ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
270 joiner.DumpStat();
271 }
272