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