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