thread_tree.cpp revision 767dd17947f1ae9dd3d02f738d442a23ed76f2f6 
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
27namespace simpleperf {
28
29bool 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
45void 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
61void 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
68ThreadEntry* 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
83void 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, true));
91  FixOverlappedMap(&kernel_map_tree_, map);
92  auto pair = kernel_map_tree_.insert(map);
93  CHECK(pair.second);
94}
95
96Dso* ThreadTree::FindKernelDsoOrNew(const std::string& filename) {
97  if (filename == DEFAULT_KERNEL_MMAP_NAME) {
98    return kernel_dso_.get();
99  }
100  auto it = module_dso_tree_.find(filename);
101  if (it == module_dso_tree_.end()) {
102    module_dso_tree_[filename] = Dso::CreateDso(DSO_KERNEL_MODULE, filename);
103    it = module_dso_tree_.find(filename);
104  }
105  return it->second.get();
106}
107
108void ThreadTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
109                              uint64_t time, const std::string& filename) {
110  ThreadEntry* thread = FindThreadOrNew(pid, tid);
111  Dso* dso = FindUserDsoOrNew(filename);
112  MapEntry* map = AllocateMap(MapEntry(start_addr, len, pgoff, time, dso, false));
113  FixOverlappedMap(&thread->maps, map);
114  auto pair = thread->maps.insert(map);
115  CHECK(pair.second);
116}
117
118Dso* ThreadTree::FindUserDsoOrNew(const std::string& filename) {
119  auto it = user_dso_tree_.find(filename);
120  if (it == user_dso_tree_.end()) {
121    user_dso_tree_[filename] = Dso::CreateDso(DSO_ELF_FILE, filename);
122    it = user_dso_tree_.find(filename);
123  }
124  return it->second.get();
125}
126
127MapEntry* ThreadTree::AllocateMap(const MapEntry& value) {
128  MapEntry* map = new MapEntry(value);
129  map_storage_.push_back(std::unique_ptr<MapEntry>(map));
130  return map;
131}
132
133void ThreadTree::FixOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
134  for (auto it = map_set->begin(); it != map_set->end();) {
135    if ((*it)->start_addr >= map->get_end_addr()) {
136      // No more overlapped maps.
137      break;
138    }
139    if ((*it)->get_end_addr() <= map->start_addr) {
140      ++it;
141    } else {
142      MapEntry* old = *it;
143      if (old->start_addr < map->start_addr) {
144        MapEntry* before = AllocateMap(MapEntry(old->start_addr, map->start_addr - old->start_addr,
145                                                old->pgoff, old->time, old->dso, old->in_kernel));
146        map_set->insert(before);
147      }
148      if (old->get_end_addr() > map->get_end_addr()) {
149        MapEntry* after = AllocateMap(
150            MapEntry(map->get_end_addr(), old->get_end_addr() - map->get_end_addr(),
151                     map->get_end_addr() - old->start_addr + old->pgoff, old->time, old->dso, old->in_kernel));
152        map_set->insert(after);
153      }
154
155      it = map_set->erase(it);
156    }
157  }
158}
159
160static bool IsAddrInMap(uint64_t addr, const MapEntry* map) {
161  return (addr >= map->start_addr && addr < map->get_end_addr());
162}
163
164static MapEntry* FindMapByAddr(const std::set<MapEntry*, MapComparator>& maps, uint64_t addr) {
165  // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
166  MapEntry find_map(addr, std::numeric_limits<uint64_t>::max(), 0,
167                    std::numeric_limits<uint64_t>::max(), nullptr, false);
168  auto it = maps.upper_bound(&find_map);
169  if (it != maps.begin() && IsAddrInMap(addr, *--it)) {
170    return *it;
171  }
172  return nullptr;
173}
174
175const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel) {
176  MapEntry* result = nullptr;
177  if (!in_kernel) {
178    result = FindMapByAddr(thread->maps, ip);
179  } else {
180    result = FindMapByAddr(kernel_map_tree_, ip);
181  }
182  return result != nullptr ? result : &unknown_map_;
183}
184
185const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip) {
186  MapEntry* result = FindMapByAddr(thread->maps, ip);
187  if (result != nullptr) {
188    return result;
189  }
190  result = FindMapByAddr(kernel_map_tree_, ip);
191  return result != nullptr ? result : &unknown_map_;
192}
193
194const Symbol* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip) {
195  uint64_t vaddr_in_file;
196  if (map->dso == kernel_dso_.get()) {
197    vaddr_in_file = ip;
198  } else {
199    vaddr_in_file = ip - map->start_addr + map->dso->MinVirtualAddress();
200  }
201  const Symbol* symbol = map->dso->FindSymbol(vaddr_in_file);
202  if (symbol == nullptr && map->in_kernel && map->dso != kernel_dso_.get()) {
203    // It is in a kernel module, but we can't find the kernel module file, or
204    // the kernel module file contains no symbol. Try finding the symbol in
205    // /proc/kallsyms.
206    vaddr_in_file = ip;
207    symbol = kernel_dso_->FindSymbol(vaddr_in_file);
208  }
209  if (symbol == nullptr) {
210    symbol = &unknown_symbol_;
211  }
212  return symbol;
213}
214
215void ThreadTree::ClearThreadAndMap() {
216  thread_tree_.clear();
217  thread_comm_storage_.clear();
218  kernel_map_tree_.clear();
219  map_storage_.clear();
220}
221
222void ThreadTree::Update(const Record& record) {
223  if (record.type() == PERF_RECORD_MMAP) {
224    const MmapRecord& r = *static_cast<const MmapRecord*>(&record);
225    if (r.InKernel()) {
226      AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
227                                r.filename);
228    } else {
229      AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
230                                r.sample_id.time_data.time, r.filename);
231    }
232  } else if (record.type() == PERF_RECORD_MMAP2) {
233    const Mmap2Record& r = *static_cast<const Mmap2Record*>(&record);
234    if (r.InKernel()) {
235      AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
236                                r.filename);
237    } else {
238      std::string filename =
239          (r.filename == DEFAULT_EXECNAME_FOR_THREAD_MMAP) ? "[unknown]" : r.filename;
240      AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
241                                r.sample_id.time_data.time, filename);
242    }
243  } else if (record.type() == PERF_RECORD_COMM) {
244    const CommRecord& r = *static_cast<const CommRecord*>(&record);
245    AddThread(r.data.pid, r.data.tid, r.comm);
246  } else if (record.type() == PERF_RECORD_FORK) {
247    const ForkRecord& r = *static_cast<const ForkRecord*>(&record);
248    ForkThread(r.data.pid, r.data.tid, r.data.ppid, r.data.ptid);
249  } else if (record.type() == SIMPLE_PERF_RECORD_KERNEL_SYMBOL) {
250    const auto& r = *static_cast<const KernelSymbolRecord*>(&record);
251    static std::string kallsyms;
252    kallsyms += r.kallsyms;
253    if (r.end_of_symbols) {
254      Dso::SetKallsyms(std::move(kallsyms));
255      kallsyms.clear();
256    }
257  } else if (record.type() == SIMPLE_PERF_RECORD_DSO) {
258    auto& r = *static_cast<const DsoRecord*>(&record);
259    Dso* dso = nullptr;
260    if (r.dso_type == DSO_KERNEL || r.dso_type == DSO_KERNEL_MODULE) {
261      dso = FindKernelDsoOrNew(r.dso_name);
262    } else {
263      dso = FindUserDsoOrNew(r.dso_name);
264    }
265    dso_id_to_dso_map_[r.dso_id] = dso;
266  } else if (record.type() == SIMPLE_PERF_RECORD_SYMBOL) {
267    auto& r = *static_cast<const SymbolRecord*>(&record);
268    Dso* dso = dso_id_to_dso_map_[r.dso_id];
269    CHECK(dso != nullptr);
270    dso->InsertSymbol(Symbol(r.name, r.addr, r.len));
271  }
272}
273
274}  // namespace simpleperf
275
276