simpleperf/thread_tree.cpp

   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
  27 namespace simpleperf {
  28
  29 bool 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
  45 void 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
  61 void 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
  68 ThreadEntry* 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
  83 void 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));
  91   FixOverlappedMap(&kernel_map_tree_, map);
  92   auto pair = kernel_map_tree_.insert(map);
  93   CHECK(pair.second);
  94 }
  95
  96 Dso* ThreadTree::FindKernelDsoOrNew(const std::string& filename) {
  97   if (filename == DEFAULT_KERNEL_MMAP_NAME) {
  98     if (kernel_dso_ == nullptr) {
  99       kernel_dso_ = Dso::CreateDso(DSO_KERNEL);
 100     }
 101     return kernel_dso_.get();
 102   }
 103   auto it = module_dso_tree_.find(filename);
 104   if (it == module_dso_tree_.end()) {
 105     module_dso_tree_[filename] = Dso::CreateDso(DSO_KERNEL_MODULE, filename);
 106     it = module_dso_tree_.find(filename);
 107   }
 108   return it->second.get();
 109 }
 110
 111 void ThreadTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
 112                               uint64_t time, const std::string& filename) {
 113   ThreadEntry* thread = FindThreadOrNew(pid, tid);
 114   Dso* dso = FindUserDsoOrNew(filename);
 115   MapEntry* map = AllocateMap(MapEntry(start_addr, len, pgoff, time, dso));
 116   FixOverlappedMap(&thread->maps, map);
 117   auto pair = thread->maps.insert(map);
 118   CHECK(pair.second);
 119 }
 120
 121 Dso* ThreadTree::FindUserDsoOrNew(const std::string& filename) {
 122   auto it = user_dso_tree_.find(filename);
 123   if (it == user_dso_tree_.end()) {
 124     user_dso_tree_[filename] = Dso::CreateDso(DSO_ELF_FILE, filename);
 125     it = user_dso_tree_.find(filename);
 126   }
 127   return it->second.get();
 128 }
 129
 130 MapEntry* ThreadTree::AllocateMap(const MapEntry& value) {
 131   MapEntry* map = new MapEntry(value);
 132   map_storage_.push_back(std::unique_ptr<MapEntry>(map));
 133   return map;
 134 }
 135
 136 void ThreadTree::FixOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
 137   for (auto it = map_set->begin(); it != map_set->end();) {
 138     if ((*it)->start_addr >= map->get_end_addr()) {
 139       // No more overlapped maps.
 140       break;
 141     }
 142     if ((*it)->get_end_addr() <= map->start_addr) {
 143       ++it;
 144     } else {
 145       MapEntry* old = *it;
 146       if (old->start_addr < map->start_addr) {
 147         MapEntry* before = AllocateMap(MapEntry(old->start_addr, map->start_addr - old->start_addr,
 148                                                 old->pgoff, old->time, old->dso));
 149         map_set->insert(before);
 150       }
 151       if (old->get_end_addr() > map->get_end_addr()) {
 152         MapEntry* after = AllocateMap(
 153             MapEntry(map->get_end_addr(), old->get_end_addr() - map->get_end_addr(),
 154                      map->get_end_addr() - old->start_addr + old->pgoff, old->time, old->dso));
 155         map_set->insert(after);
 156       }
 157
 158       it = map_set->erase(it);
 159     }
 160   }
 161 }
 162
 163 static bool IsAddrInMap(uint64_t addr, const MapEntry* map) {
 164   return (addr >= map->start_addr && addr < map->get_end_addr());
 165 }
 166
 167 static MapEntry* FindMapByAddr(const std::set<MapEntry*, MapComparator>& maps, uint64_t addr) {
 168   // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
 169   MapEntry find_map(addr, std::numeric_limits<uint64_t>::max(), 0,
 170                     std::numeric_limits<uint64_t>::max(), nullptr);
 171   auto it = maps.upper_bound(&find_map);
 172   if (it != maps.begin() && IsAddrInMap(addr, *--it)) {
 173     return *it;
 174   }
 175   return nullptr;
 176 }
 177
 178 const MapEntry* ThreadTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel) {
 179   MapEntry* result = nullptr;
 180   if (!in_kernel) {
 181     result = FindMapByAddr(thread->maps, ip);
 182   } else {
 183     result = FindMapByAddr(kernel_map_tree_, ip);
 184   }
 185   return result != nullptr ? result : &unknown_map_;
 186 }
 187
 188 const Symbol* ThreadTree::FindSymbol(const MapEntry* map, uint64_t ip) {
 189   uint64_t vaddr_in_file;
 190   if (map->dso == kernel_dso_.get()) {
 191     vaddr_in_file = ip;
 192   } else {
 193     vaddr_in_file = ip - map->start_addr + map->dso->MinVirtualAddress();
 194   }
 195   const Symbol* symbol = map->dso->FindSymbol(vaddr_in_file);
 196   if (symbol == nullptr) {
 197     symbol = &unknown_symbol_;
 198   }
 199   return symbol;
 200 }
 201
 202 void ThreadTree::Clear() {
 203   thread_tree_.clear();
 204   thread_comm_storage_.clear();
 205   kernel_map_tree_.clear();
 206   map_storage_.clear();
 207   kernel_dso_.reset();
 208   module_dso_tree_.clear();
 209   user_dso_tree_.clear();
 210 }
 211
 212 }  // namespace simpleperf
 213
 214 void BuildThreadTree(const Record& record, ThreadTree* thread_tree) {
 215   if (record.header.type == PERF_RECORD_MMAP) {
 216     const MmapRecord& r = *static_cast<const MmapRecord*>(&record);
 217     if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
 218       thread_tree->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
 219                                 r.filename);
 220     } else {
 221       thread_tree->AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
 222                                 r.sample_id.time_data.time, r.filename);
 223     }
 224   } else if (record.header.type == PERF_RECORD_MMAP2) {
 225     const Mmap2Record& r = *static_cast<const Mmap2Record*>(&record);
 226     if ((r.header.misc & PERF_RECORD_MISC_CPUMODE_MASK) == PERF_RECORD_MISC_KERNEL) {
 227       thread_tree->AddKernelMap(r.data.addr, r.data.len, r.data.pgoff, r.sample_id.time_data.time,
 228                                 r.filename);
 229     } else {
 230       std::string filename =
 231           (r.filename == DEFAULT_EXECNAME_FOR_THREAD_MMAP) ? "[unknown]" : r.filename;
 232       thread_tree->AddThreadMap(r.data.pid, r.data.tid, r.data.addr, r.data.len, r.data.pgoff,
 233                                 r.sample_id.time_data.time, filename);
 234     }
 235   } else if (record.header.type == PERF_RECORD_COMM) {
 236     const CommRecord& r = *static_cast<const CommRecord*>(&record);
 237     thread_tree->AddThread(r.data.pid, r.data.tid, r.comm);
 238   } else if (record.header.type == PERF_RECORD_FORK) {
 239     const ForkRecord& r = *static_cast<const ForkRecord*>(&record);
 240     thread_tree->ForkThread(r.data.pid, r.data.tid, r.data.ppid, r.data.ptid);
 241   }
 242 }