1 /*
2 * Copyright (C) 2015 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 "thread_tree.h"
18
19 #include <limits>
20
21 #include <android-base/logging.h>
22
23 #include "environment.h"
24 #include "perf_event.h"
25 #include "record.h"
26
27 namespace simpleperf {
28
operator ()(const MapEntry * map1,const MapEntry * map2) const29 bool MapComparator::operator()(const MapEntry* map1, const MapEntry* map2) const {
30 if (map1->start_addr != map2->start_addr) {
31 return map1->start_addr < map2->start_addr;
32 }
33 // Compare map->len instead of map->get_end_addr() here. Because we set map's len
34 // to std::numeric_limits<uint64_t>::max() in FindMapByAddr(), which makes
35 // map->get_end_addr() overflow.
36 if (map1->len != map2->len) {
37 return map1->len < map2->len;
38 }
39 if (map1->time != map2->time) {
40 return map1->time < map2->time;
41 }
42 return false;
43 }
44
AddThread(int pid,int tid,const std::string & comm)45 void ThreadTree::AddThread(int pid, int tid, const std::string& comm) {
46 auto it = thread_tree_.find(tid);
47 if (it == thread_tree_.end()) {
48 ThreadEntry* thread = new ThreadEntry{
49 pid, tid,
50 "unknown", // comm
51 std::set<MapEntry*, MapComparator>(), // maps
52 };
53 auto pair = thread_tree_.insert(std::make_pair(tid, std::unique_ptr<ThreadEntry>(thread)));
54 CHECK(pair.second);
55 it = pair.first;
56 }
57 thread_comm_storage_.push_back(std::unique_ptr<std::string>(new std::string(comm)));
58 it->second->comm = thread_comm_storage_.back()->c_str();
59 }
60
ForkThread(int pid,int tid,int ppid,int ptid)61 void ThreadTree::ForkThread(int pid, int tid, int ppid, int ptid) {
62 ThreadEntry* parent = FindThreadOrNew(ppid, ptid);
63 ThreadEntry* child = FindThreadOrNew(pid, tid);
64 child->comm = parent->comm;
65 child->maps = parent->maps;
66 }
67
FindThreadOrNew(int pid,int tid)68 ThreadEntry* ThreadTree::FindThreadOrNew(int pid, int tid) {
69 auto it = thread_tree_.find(tid);
70 if (it == thread_tree_.end()) {
71 AddThread(pid, tid, "unknown");
72 it = thread_tree_.find(tid);
73 } else {
74 if (pid != it->second.get()->pid) {
75 // TODO: b/22185053.
76 LOG(DEBUG) << "unexpected (pid, tid) pair: expected (" << it->second.get()->pid << ", " << tid
77 << "), actual (" << pid << ", " << tid << ")";
78 }
79 }
80 return it->second.get();
81 }
82
AddKernelMap(uint64_t start_addr,uint64_t len,uint64_t pgoff,uint64_t time,const std::string & filename)83 void ThreadTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
84 const std::string& filename) {
85 // kernel map len can be 0 when record command is not run in supervisor mode.
86 if (len == 0) {
87 return;
88 }
89 Dso* dso = FindKernelDsoOrNew(filename);
90 MapEntry* map = AllocateMap(MapEntry(start_addr, len, pgoff, time, dso));
91 FixOverlappedMap(&kernel_map_tree_, map);
92 auto pair = kernel_map_tree_.insert(map);
93 CHECK(pair.second);
94 }
95
FindKernelDsoOrNew(const std::string & filename)96 Dso* ThreadTree::FindKernelDsoOrNew(const std::string& filename) {
97 if (filename == DEFAULT_KERNEL_MMAP_NAME) {
98 if (kernel_dso_ == nullptr) {
99 kernel_dso_ = Dso::CreateDso(DSO_KERNEL);
100 }
101 return kernel_dso_.get();
102 }
103 auto it = module_dso_tree_.find(filename);
104 if (it == module_dso_tree_.end()) {
105 module_dso_tree_[filename] = Dso::CreateDso(DSO_KERNEL_MODULE, filename);
106 it = module_dso_tree_.find(filename);
107 }
108 return it->second.get();
109 }
110
AddThreadMap(int pid,int tid,uint64_t start_addr,uint64_t len,uint64_t pgoff,uint64_t time,const std::string & filename)111 void ThreadTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
112 uint64_t time, const std::string& filename) {
113 ThreadEntry* thread = FindThreadOrNew(pid, tid);
114 Dso* dso = FindUserDsoOrNew(filename);
115 MapEntry* map = AllocateMap(MapEntry(start_addr, len, pgoff, time, dso));
116 FixOverlappedMap(&thread->maps, map);
117 auto pair = thread->maps.insert(map);
118 CHECK(pair.second);
119 }
120
FindUserDsoOrNew(const std::string & filename)121 Dso* ThreadTree::FindUserDsoOrNew(const std::string& filename) {
122 auto it = user_dso_tree_.find(filename);
123 if (it == user_dso_tree_.end()) {
124 user_dso_tree_[filename] = Dso::CreateDso(DSO_ELF_FILE, filename);
125 it = user_dso_tree_.find(filename);
126 }
127 return it->second.get();
128 }
129
AllocateMap(const MapEntry & value)130 MapEntry* ThreadTree::AllocateMap(const MapEntry& value) {
131 MapEntry* map = new MapEntry(value);
132 map_storage_.push_back(std::unique_ptr<MapEntry>(map));
133 return map;
134 }
135
FixOverlappedMap(std::set<MapEntry *,MapComparator> * map_set,const MapEntry * map)136 void ThreadTree::FixOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
137 for (auto it = map_set->begin(); it != map_set->end();) {
138 if ((*it)->start_addr >= map->get_end_addr()) {
139 // No more overlapped maps.
140 break;
141 }
142 if ((*it)->get_end_addr() <= map->start_addr) {
143 ++it;
144 } else {
145 MapEntry* old = *it;
146 if (old->start_addr < map->start_addr) {
147 MapEntry* before = AllocateMap(MapEntry(old->start_addr, map->start_addr - old->start_addr,
148 old->pgoff, old->time, old->dso));
149 map_set->insert(before);
150 }
151 if (old->get_end_addr() > map->get_end_addr()) {
152 MapEntry* after = AllocateMap(
153 MapEntry(map->get_end_addr(), old->get_end_addr() - map->get_end_addr(),
154 map->get_end_addr() - old->start_addr + old->pgoff, old->time, old->dso));
155 map_set->insert(after);
156 }
157
158 it = map_set->erase(it);
159 }
160 }
161 }
162
IsAddrInMap(uint64_t addr,const MapEntry * map)163 static bool IsAddrInMap(uint64_t addr, const MapEntry* map) {
164 return (addr >= map->start_addr && addr < map->get_end_addr());
165 }
166
FindMapByAddr(const std::set<MapEntry *,MapComparator> & maps,uint64_t addr)167 static MapEntry* FindMapByAddr(const std::set<MapEntry*, MapComparator>& maps, uint64_t addr) {
168 // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
169 MapEntry find_map(addr, std::numeric_limits<uint64_t>::max(), 0,
170 std::numeric_limits<uint64_t>::max(), nullptr);
171 auto it = maps.upper_bound(&find_map);
172 if (it != maps.begin() && IsAddrInMap(addr, *--it)) {
173 return *it;
174 }
175 return nullptr;
176 }
177
FindMap(const ThreadEntry * thread,uint64_t ip,bool in_kernel)178 const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel) {
179 MapEntry* result = nullptr;
180 if (!in_kernel) {
181 result = FindMapByAddr(thread->maps, ip);
182 } else {
183 result = FindMapByAddr(kernel_map_tree_, ip);
184 }
185 return result != nullptr ? result : &unknown_map_;
186 }
187
FindSymbol(const MapEntry * map,uint64_t ip)188 const Symbol* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip) {
189 uint64_t vaddr_in_file;
190 if (map->dso == kernel_dso_.get()) {
191 vaddr_in_file = ip;
192 } else {
193 vaddr_in_file = ip - map->start_addr + map->dso->MinVirtualAddress();
194 }
195 const Symbol* symbol = map->dso->FindSymbol(vaddr_in_file);
196 if (symbol == nullptr) {
197 symbol = &unknown_symbol_;
198 }
199 return symbol;
200 }
201
Clear()202 void ThreadTree::Clear() {
203 thread_tree_.clear();
204 thread_comm_storage_.clear();
205 kernel_map_tree_.clear();
206 map_storage_.clear();
207 kernel_dso_.reset();
208 module_dso_tree_.clear();
209 user_dso_tree_.clear();
210 }
211
212 } // namespace simpleperf
213
BuildThreadTree(const Record & record,ThreadTree * thread_tree)214 void BuildThreadTree(const Record& record, ThreadTree* thread_tree) {
215 if (record.header.type == PERF_RECORD_MMAP) {
216 const MmapRecord& r = *static_cast<const MmapRecord*>(&record);
217 if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
218 thread_tree->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
219 r.filename);
220 } else {
221 thread_tree->AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
222 r.sample_id.time_data.time, r.filename);
223 }
224 } else if (record.header.type == PERF_RECORD_MMAP2) {
225 const Mmap2Record& r = *static_cast<const Mmap2Record*>(&record);
226 if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
227 thread_tree->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
228 r.filename);
229 } else {
230 std::string filename =
231 (r.filename == DEFAULT_EXECNAME_FOR_THREAD_MMAP) ? "[unknown]" : r.filename;
232 thread_tree->AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
233 r.sample_id.time_data.time, filename);
234 }
235 } else if (record.header.type == PERF_RECORD_COMM) {
236 const CommRecord& r = *static_cast<const CommRecord*>(&record);
237 thread_tree->AddThread(r.data.pid, r.data.tid, r.comm);
238 } else if (record.header.type == PERF_RECORD_FORK) {
239 const ForkRecord& r = *static_cast<const ForkRecord*>(&record);
240 thread_tree->ForkThread(r.data.pid, r.data.tid, r.data.ppid, r.data.ptid);
241 }
242 }
243