/*
* Copyright (C) 2017 The Android Open Source Project
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
#include "CallChainJoiner.h"
#include <gtest/gtest.h>
#include <environment.h>
using namespace simpleperf;
using namespace simpleperf::call_chain_joiner_impl;
static bool 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) {
std::vector<uint64_t> tmp_ip = input_ip;
std::vector<uint64_t> tmp_sp = input_sp;
cache.AddCallChain(tid, tmp_ip, tmp_sp);
return tmp_ip == expected_output_ip && tmp_sp == expected_output_sp;
}
TEST(LRUCache, different_nodes) {
LRUCache cache(sizeof(CacheNode) * 2, 1);
ASSERT_EQ(cache.Stat().max_node_count, 2u);
// different tids
std::vector<uint64_t> ip = {0x1};
std::vector<uint64_t> sp = {0x1};
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
ASSERT_TRUE(JoinCallChain(cache, 1, ip, sp, ip, sp));
ASSERT_EQ(cache.Stat().used_node_count, 2u);
ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
ASSERT_NE(cache.FindNode(0, ip[0], sp[0]), nullptr);
ASSERT_NE(cache.FindNode(1, ip[0], sp[0]), nullptr);
// different ips
std::vector<uint64_t> ip2 = {0x2};
ASSERT_TRUE(JoinCallChain(cache, 0, ip2, sp, ip2, sp));
ASSERT_EQ(cache.Stat().used_node_count, 2u);
ASSERT_EQ(cache.Stat().recycled_node_count, 1u);
ASSERT_EQ(cache.FindNode(0, ip[0], sp[0]), nullptr);
ASSERT_NE(cache.FindNode(0, ip2[0], sp[0]), nullptr);
ASSERT_NE(cache.FindNode(1, ip[0], sp[0]), nullptr);
// different sps
std::vector<uint64_t> sp2 = {0x2};
ASSERT_TRUE(JoinCallChain(cache, 1, ip, sp2, ip, sp2));
ASSERT_EQ(cache.Stat().used_node_count, 2u);
ASSERT_EQ(cache.Stat().recycled_node_count, 2u);
ASSERT_EQ(cache.FindNode(1, ip[0], sp[0]), nullptr);
ASSERT_NE(cache.FindNode(0, ip2[0], sp[0]), nullptr);
ASSERT_NE(cache.FindNode(1, ip[0], sp2[0]), nullptr);
}
TEST(LRUCache, extend_chains) {
// matched_node_count_to_extend_callchain = 1
// c -> b
// b -> a => c -> b -> a
LRUCache cache1(sizeof(CacheNode) * 4, 1);
ASSERT_TRUE(JoinCallChain(cache1, 0, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}));
ASSERT_TRUE(JoinCallChain(cache1, 0, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc}));
ASSERT_EQ(cache1.Stat().used_node_count, 3u);
// matched_node_count_to_extend_callchain = 2
// c -> b
// b -> a
LRUCache cache2(sizeof(CacheNode) * 4, 2);
ASSERT_TRUE(JoinCallChain(cache2, 0, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}, {0xb, 0xc}));
ASSERT_TRUE(JoinCallChain(cache2, 0, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb}, {0xa, 0xb}));
ASSERT_EQ(cache2.Stat().used_node_count, 3u);
// matched_node_count_to_extend_callchain = 2
// d -> c -> b
// c -> b -> a => d -> c -> b -> a
LRUCache cache3(sizeof(CacheNode) * 4, 2);
ASSERT_TRUE(JoinCallChain(cache3, 0, {0xb, 0xc, 0xd}, {0xb, 0xc, 0xd},
{0xb, 0xc, 0xd}, {0xb, 0xc, 0xd}));
ASSERT_TRUE(JoinCallChain(cache3, 0, {0xa, 0xb, 0xc}, {0xa, 0xb, 0xc},
{0xa, 0xb, 0xc, 0xd}, {0xa, 0xb, 0xc, 0xd}));
ASSERT_EQ(cache3.Stat().used_node_count, 4u);
}
TEST(LRUCache, avoid_ip_sp_loop) {
LRUCache cache(sizeof(CacheNode) * 2, 1);
std::vector<uint64_t> ip = {0xa, 0xb};
std::vector<uint64_t> sp = {1, 1};
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
ip = {0xb, 0xa};
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
ASSERT_EQ(cache.Stat().used_node_count, 2u);
ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
}
TEST(LRUCache, one_chain) {
LRUCache cache(sizeof(CacheNode) * 4, 1);
ASSERT_EQ(cache.Stat().max_node_count, 4u);
std::vector<uint64_t> ip;
std::vector<uint64_t> sp;
for (size_t i = 1u; i <= 4u; ++i) {
ip.push_back(i);
sp.push_back(i);
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
}
std::vector<uint64_t> origin_ip = ip;
std::vector<uint64_t> origin_sp = sp;
for (size_t i = ip.size(); i > 1; --i) {
ip.pop_back();
sp.pop_back();
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, origin_ip, origin_sp));
}
ASSERT_EQ(cache.Stat().used_node_count, 4u);
ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
}
TEST(LRUCache, many_chains) {
LRUCache cache(sizeof(CacheNode) * 12, 1);
// 4 -> 3 -> 2 -> 1
// 8 -> 7 -> 6 -> 5
// d -> c -> b -> a
std::vector<uint64_t> ip = {1, 2, 3, 4};
std::vector<uint64_t> sp = {1, 2, 3, 4};
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
ip = {5, 6, 7, 8};
sp = {5, 6, 7, 8};
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
ip = {0xa, 0xb, 0xc, 0xd};
sp = {0xa, 0xb, 0xc, 0xd};
ASSERT_TRUE(JoinCallChain(cache, 0, ip, sp, ip, sp));
ASSERT_EQ(cache.Stat().used_node_count, 12u);
ASSERT_EQ(cache.Stat().recycled_node_count, 0u);
ASSERT_TRUE(JoinCallChain(cache, 0, {1}, {1}, {1, 2, 3, 4}, {1, 2, 3, 4}));
ASSERT_TRUE(JoinCallChain(cache, 0, {5, 6}, {5, 6}, {5, 6, 7, 8}, {5, 6, 7, 8}));
ASSERT_TRUE(JoinCallChain(cache, 0, {0xa}, {0xb}, {0xa}, {0xb}));
ASSERT_EQ(cache.Stat().used_node_count, 12u);
ASSERT_EQ(cache.Stat().recycled_node_count, 1u);
ASSERT_EQ(cache.FindNode(0, 0xa, 0xa), nullptr);
}
class CallChainJoinerTest : public ::testing::Test {
protected:
void SetUp() override {
#if defined(__ANDROID__)
std::string tmpdir = "/data/local/tmp";
#else
std::string tmpdir = "/tmp";
#endif
scoped_temp_files_.reset(new ScopedTempFiles(tmpdir));
}
private:
std::unique_ptr<ScopedTempFiles> scoped_temp_files_;
};
TEST_F(CallChainJoinerTest, smoke) {
CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, true);
for (pid_t pid = 0; pid < 10; ++pid) {
ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_OFFLINE,
{1, 2, 3}, {1, 2, 3}));
ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_REMOTE,
{3, 4, 5}, {3, 4, 5}));
ASSERT_TRUE(joiner.AddCallChain(pid, pid, CallChainJoiner::ORIGINAL_OFFLINE,
{1, 4}, {1, 4}));
}
ASSERT_TRUE(joiner.JoinCallChains());
pid_t pid;
pid_t tid;
CallChainJoiner::ChainType type;
std::vector<uint64_t> ips;
std::vector<uint64_t> sps;
for (pid_t expected_pid = 0; expected_pid < 10; ++expected_pid) {
for (size_t i = 0; i < 2u; ++i) {
ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
ASSERT_EQ(pid, expected_pid);
ASSERT_EQ(tid, expected_pid);
if (i == 0u) {
ASSERT_EQ(type, CallChainJoiner::ORIGINAL_OFFLINE);
ASSERT_EQ(ips, std::vector<uint64_t>({1, 2, 3}));
ASSERT_EQ(sps, std::vector<uint64_t>({1, 2, 3}));
} else {
ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE);
ASSERT_EQ(ips, std::vector<uint64_t>({1, 2, 3, 4, 5}));
ASSERT_EQ(sps, std::vector<uint64_t>({1, 2, 3, 4, 5}));
}
}
for (size_t i = 0; i < 2u; ++i) {
ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
ASSERT_EQ(pid, expected_pid);
ASSERT_EQ(tid, expected_pid);
ASSERT_EQ(type, i == 0u ? CallChainJoiner::ORIGINAL_REMOTE
: CallChainJoiner::JOINED_REMOTE);
ASSERT_EQ(ips, std::vector<uint64_t>({3, 4, 5}));
ASSERT_EQ(sps, std::vector<uint64_t>({3, 4, 5}));
}
for (size_t i = 0; i < 2u; ++i) {
ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
ASSERT_EQ(pid, expected_pid);
ASSERT_EQ(tid, expected_pid);
if (i == 0u) {
ASSERT_EQ(type, CallChainJoiner::ORIGINAL_OFFLINE);
ASSERT_EQ(ips, std::vector<uint64_t>({1, 4}));
ASSERT_EQ(sps, std::vector<uint64_t>({1, 4}));
} else {
ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE);
ASSERT_EQ(ips, std::vector<uint64_t>({1, 4, 5}));
ASSERT_EQ(sps, std::vector<uint64_t>({1, 4, 5}));
}
}
}
ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
joiner.DumpStat();
ASSERT_EQ(joiner.GetCacheStat().cache_size, sizeof(CacheNode) * 1024);
ASSERT_EQ(joiner.GetCacheStat().matched_node_count_to_extend_callchain, 1u);
ASSERT_EQ(joiner.GetCacheStat().max_node_count, 1024u);
ASSERT_EQ(joiner.GetCacheStat().used_node_count, 50u);
ASSERT_EQ(joiner.GetCacheStat().recycled_node_count, 0u);
ASSERT_EQ(joiner.GetStat().chain_count, 30u);
ASSERT_EQ(joiner.GetStat().before_join_node_count, 80u);
ASSERT_EQ(joiner.GetStat().after_join_node_count, 110u);
ASSERT_EQ(joiner.GetStat().after_join_max_chain_length, 5u);
}
TEST_F(CallChainJoinerTest, no_original_chains) {
CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, false);
ASSERT_TRUE(joiner.AddCallChain(0, 0, CallChainJoiner::ORIGINAL_OFFLINE, {1}, {1}));
ASSERT_TRUE(joiner.JoinCallChains());
pid_t pid;
pid_t tid;
CallChainJoiner::ChainType type;
std::vector<uint64_t> ips;
std::vector<uint64_t> sps;
ASSERT_TRUE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
ASSERT_EQ(pid, 0);
ASSERT_EQ(tid, 0);
ASSERT_EQ(type, CallChainJoiner::JOINED_OFFLINE);
ASSERT_EQ(ips, std::vector<uint64_t>({1}));
ASSERT_EQ(sps, std::vector<uint64_t>({1}));
ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
joiner.DumpStat();
}
TEST_F(CallChainJoinerTest, no_chains) {
CallChainJoiner joiner(sizeof(CacheNode) * 1024, 1, false);
ASSERT_TRUE(joiner.JoinCallChains());
pid_t pid;
pid_t tid;
CallChainJoiner::ChainType type;
std::vector<uint64_t> ips;
std::vector<uint64_t> sps;
ASSERT_FALSE(joiner.GetNextCallChain(pid, tid, type, ips, sps));
joiner.DumpStat();
}