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