thread_tree.cpp revision 78fddd140931adf704061f82e3c9fcb03362f8d0 
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 <inttypes.h>
20
21#include <limits>
22
23#include <android-base/logging.h>
24#include <android-base/stringprintf.h>
25
26#include "perf_event.h"
27#include "record.h"
28
29namespace simpleperf {
30
31bool MapComparator::operator()(const MapEntry* map1,
32                               const MapEntry* map2) const {
33  if (map1->start_addr != map2->start_addr) {
34    return map1->start_addr < map2->start_addr;
35  }
36  // Compare map->len instead of map->get_end_addr() here. Because we set map's
37  // len to std::numeric_limits<uint64_t>::max() in FindMapByAddr(), which makes
38  // map->get_end_addr() overflow.
39  if (map1->len != map2->len) {
40    return map1->len < map2->len;
41  }
42  if (map1->time != map2->time) {
43    return map1->time < map2->time;
44  }
45  return false;
46}
47
48void ThreadTree::AddThread(int pid, int tid, const std::string& comm) {
49  auto it = thread_tree_.find(tid);
50  if (it == thread_tree_.end()) {
51    ThreadEntry* thread = new ThreadEntry{
52        pid, tid,
53        "unknown",                             // comm
54        std::set<MapEntry*, MapComparator>(),  // maps
55    };
56    auto pair = thread_tree_.insert(
57        std::make_pair(tid, std::unique_ptr<ThreadEntry>(thread)));
58    CHECK(pair.second);
59    it = pair.first;
60  }
61  if (comm != it->second->comm) {
62    thread_comm_storage_.push_back(
63        std::unique_ptr<std::string>(new std::string(comm)));
64    it->second->comm = thread_comm_storage_.back()->c_str();
65  }
66}
67
68void ThreadTree::ForkThread(int pid, int tid, int ppid, int ptid) {
69  ThreadEntry* parent = FindThreadOrNew(ppid, ptid);
70  ThreadEntry* child = FindThreadOrNew(pid, tid);
71  child->comm = parent->comm;
72  child->maps = parent->maps;
73}
74
75ThreadEntry* ThreadTree::FindThreadOrNew(int pid, int tid) {
76  auto it = thread_tree_.find(tid);
77  if (it == thread_tree_.end()) {
78    AddThread(pid, tid, "unknown");
79    it = thread_tree_.find(tid);
80  } else {
81    if (pid != it->second.get()->pid) {
82      // TODO: b/22185053.
83      LOG(DEBUG) << "unexpected (pid, tid) pair: expected ("
84                 << it->second.get()->pid << ", " << tid << "), actual (" << pid
85                 << ", " << tid << ")";
86    }
87  }
88  return it->second.get();
89}
90
91void ThreadTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff,
92                              uint64_t time, const std::string& filename) {
93  // kernel map len can be 0 when record command is not run in supervisor mode.
94  if (len == 0) {
95    return;
96  }
97  Dso* dso = FindKernelDsoOrNew(filename);
98  MapEntry* map =
99      AllocateMap(MapEntry(start_addr, len, pgoff, time, dso, true));
100  FixOverlappedMap(&kernel_map_tree_, map);
101  auto pair = kernel_map_tree_.insert(map);
102  CHECK(pair.second);
103}
104
105Dso* ThreadTree::FindKernelDsoOrNew(const std::string& filename) {
106  if (filename == DEFAULT_KERNEL_MMAP_NAME) {
107    return kernel_dso_.get();
108  }
109  auto it = module_dso_tree_.find(filename);
110  if (it == module_dso_tree_.end()) {
111    module_dso_tree_[filename] = Dso::CreateDso(DSO_KERNEL_MODULE, filename);
112    it = module_dso_tree_.find(filename);
113  }
114  return it->second.get();
115}
116
117void ThreadTree::AddThreadMap(int pid, int tid, uint64_t start_addr,
118                              uint64_t len, uint64_t pgoff, uint64_t time,
119                              const std::string& filename) {
120  ThreadEntry* thread = FindThreadOrNew(pid, tid);
121  Dso* dso = FindUserDsoOrNew(filename);
122  MapEntry* map =
123      AllocateMap(MapEntry(start_addr, len, pgoff, time, dso, false));
124  FixOverlappedMap(&thread->maps, map);
125  auto pair = thread->maps.insert(map);
126  CHECK(pair.second);
127}
128
129Dso* ThreadTree::FindUserDsoOrNew(const std::string& filename) {
130  auto it = user_dso_tree_.find(filename);
131  if (it == user_dso_tree_.end()) {
132    user_dso_tree_[filename] = Dso::CreateDso(DSO_ELF_FILE, filename);
133    it = user_dso_tree_.find(filename);
134  }
135  return it->second.get();
136}
137
138MapEntry* ThreadTree::AllocateMap(const MapEntry& value) {
139  MapEntry* map = new MapEntry(value);
140  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
141  return map;
142}
143
144void ThreadTree::FixOverlappedMap(std::set<MapEntry*, MapComparator>* map_set,
145                                  const MapEntry* map) {
146  for (auto it = map_set->begin(); it != map_set->end();) {
147    if ((*it)->start_addr >= map->get_end_addr()) {
148      // No more overlapped maps.
149      break;
150    }
151    if ((*it)->get_end_addr() <= map->start_addr) {
152      ++it;
153    } else {
154      MapEntry* old = *it;
155      if (old->start_addr < map->start_addr) {
156        MapEntry* before = AllocateMap(
157            MapEntry(old->start_addr, map->start_addr - old->start_addr,
158                     old->pgoff, old->time, old->dso, old->in_kernel));
159        map_set->insert(before);
160      }
161      if (old->get_end_addr() > map->get_end_addr()) {
162        MapEntry* after = AllocateMap(MapEntry(
163            map->get_end_addr(), old->get_end_addr() - map->get_end_addr(),
164            map->get_end_addr() - old->start_addr + old->pgoff, old->time,
165            old->dso, old->in_kernel));
166        map_set->insert(after);
167      }
168
169      it = map_set->erase(it);
170    }
171  }
172}
173
174static bool IsAddrInMap(uint64_t addr, const MapEntry* map) {
175  return (addr >= map->start_addr && addr < map->get_end_addr());
176}
177
178static MapEntry* FindMapByAddr(const std::set<MapEntry*, MapComparator>& maps,
179                               uint64_t addr) {
180  // Construct a map_entry which is strictly after the searched map_entry, based
181  // on MapComparator.
182  MapEntry find_map(addr, std::numeric_limits<uint64_t>::max(), 0,
183                    std::numeric_limits<uint64_t>::max(), nullptr, false);
184  auto it = maps.upper_bound(&find_map);
185  if (it != maps.begin() && IsAddrInMap(addr, *--it)) {
186    return *it;
187  }
188  return nullptr;
189}
190
191const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip,
192                                    bool in_kernel) {
193  MapEntry* result = nullptr;
194  if (!in_kernel) {
195    result = FindMapByAddr(thread->maps, ip);
196  } else {
197    result = FindMapByAddr(kernel_map_tree_, ip);
198  }
199  return result != nullptr ? result : &unknown_map_;
200}
201
202const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip) {
203  MapEntry* result = FindMapByAddr(thread->maps, ip);
204  if (result != nullptr) {
205    return result;
206  }
207  result = FindMapByAddr(kernel_map_tree_, ip);
208  return result != nullptr ? result : &unknown_map_;
209}
210
211const Symbol* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip,
212                                     uint64_t* pvaddr_in_file) {
213  uint64_t vaddr_in_file;
214  Dso* dso = map->dso;
215  if (dso == kernel_dso_.get()) {
216    vaddr_in_file = ip;
217  } else {
218    vaddr_in_file = ip - map->start_addr + map->dso->MinVirtualAddress();
219  }
220  const Symbol* symbol = dso->FindSymbol(vaddr_in_file);
221  if (symbol == nullptr && map->in_kernel && dso != kernel_dso_.get()) {
222    // It is in a kernel module, but we can't find the kernel module file, or
223    // the kernel module file contains no symbol. Try finding the symbol in
224    // /proc/kallsyms.
225    vaddr_in_file = ip;
226    dso = kernel_dso_.get();
227    symbol = dso->FindSymbol(vaddr_in_file);
228  }
229  if (symbol == nullptr) {
230    if (show_ip_for_unknown_symbol_) {
231      std::string name = android::base::StringPrintf(
232          "%s%s[+%" PRIx64 "]", (show_mark_for_unknown_symbol_ ? "*" : ""),
233          dso->FileName().c_str(), vaddr_in_file);
234      dso->InsertSymbol(Symbol(name, vaddr_in_file, 1));
235      symbol = dso->FindSymbol(vaddr_in_file);
236      CHECK(symbol != nullptr);
237    } else {
238      symbol = &unknown_symbol_;
239    }
240  }
241  if (pvaddr_in_file != nullptr) {
242    *pvaddr_in_file = vaddr_in_file;
243  }
244  return symbol;
245}
246
247const Symbol* ThreadTree::FindKernelSymbol(uint64_t ip) {
248  const MapEntry* map = FindMap(nullptr, ip, true);
249  return FindSymbol(map, ip, nullptr);
250}
251
252void ThreadTree::ClearThreadAndMap() {
253  thread_tree_.clear();
254  thread_comm_storage_.clear();
255  kernel_map_tree_.clear();
256  map_storage_.clear();
257}
258
259void ThreadTree::Update(const Record& record) {
260  if (record.type() == PERF_RECORD_MMAP) {
261    const MmapRecord& r = *static_cast<const MmapRecord*>(&record);
262    if (r.InKernel()) {
263      AddKernelMap(r.data->addr, r.data->len, r.data->pgoff,
264                   r.sample_id.time_data.time, r.filename);
265    } else {
266      AddThreadMap(r.data->pid, r.data->tid, r.data->addr, r.data->len,
267                   r.data->pgoff, r.sample_id.time_data.time, r.filename);
268    }
269  } else if (record.type() == PERF_RECORD_MMAP2) {
270    const Mmap2Record& r = *static_cast<const Mmap2Record*>(&record);
271    if (r.InKernel()) {
272      AddKernelMap(r.data->addr, r.data->len, r.data->pgoff,
273                   r.sample_id.time_data.time, r.filename);
274    } else {
275      std::string filename = (r.filename == DEFAULT_EXECNAME_FOR_THREAD_MMAP)
276                                 ? "[unknown]"
277                                 : r.filename;
278      AddThreadMap(r.data->pid, r.data->tid, r.data->addr, r.data->len,
279                   r.data->pgoff, r.sample_id.time_data.time, filename);
280    }
281  } else if (record.type() == PERF_RECORD_COMM) {
282    const CommRecord& r = *static_cast<const CommRecord*>(&record);
283    AddThread(r.data->pid, r.data->tid, r.comm);
284  } else if (record.type() == PERF_RECORD_FORK) {
285    const ForkRecord& r = *static_cast<const ForkRecord*>(&record);
286    ForkThread(r.data->pid, r.data->tid, r.data->ppid, r.data->ptid);
287  } else if (record.type() == SIMPLE_PERF_RECORD_KERNEL_SYMBOL) {
288    const auto& r = *static_cast<const KernelSymbolRecord*>(&record);
289    Dso::SetKallsyms(std::move(r.kallsyms));
290  } else if (record.type() == SIMPLE_PERF_RECORD_DSO) {
291    auto& r = *static_cast<const DsoRecord*>(&record);
292    Dso* dso = nullptr;
293    if (r.dso_type == DSO_KERNEL || r.dso_type == DSO_KERNEL_MODULE) {
294      dso = FindKernelDsoOrNew(r.dso_name);
295    } else {
296      dso = FindUserDsoOrNew(r.dso_name);
297    }
298    dso->SetMinVirtualAddress(r.min_vaddr);
299    dso_id_to_dso_map_[r.dso_id] = dso;
300  } else if (record.type() == SIMPLE_PERF_RECORD_SYMBOL) {
301    auto& r = *static_cast<const SymbolRecord*>(&record);
302    Dso* dso = dso_id_to_dso_map_[r.dso_id];
303    CHECK(dso != nullptr);
304    dso->InsertSymbol(Symbol(r.name, r.addr, r.len));
305  }
306}
307
308std::vector<Dso*> ThreadTree::GetAllDsos() const {
309  std::vector<Dso*> result;
310  result.push_back(kernel_dso_.get());
311  for (auto& p : module_dso_tree_) {
312    result.push_back(p.second.get());
313  }
314  for (auto& p : user_dso_tree_) {
315    result.push_back(p.second.get());
316  }
317  return result;
318}
319
320}  // namespace simpleperf
321