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