simpleperf/sample_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 "sample_tree.h"
  18
  19 #include <base/logging.h>
  20
  21 #include "environment.h"
  22
  23 bool MapComparator::operator()(const MapEntry* map1, const MapEntry* map2) const {
  24   if (map1->start_addr != map2->start_addr) {
  25     return map1->start_addr < map2->start_addr;
  26   }
  27   if (map1->len != map2->len) {
  28     return map1->len < map2->len;
  29   }
  30   if (map1->time != map2->time) {
  31     return map1->time < map2->time;
  32   }
  33   return false;
  34 }
  35
  36 void SampleTree::AddThread(int pid, int tid, const std::string& comm) {
  37   auto it = thread_tree_.find(tid);
  38   if (it == thread_tree_.end()) {
  39     ThreadEntry* thread = new ThreadEntry{
  40         pid, tid,
  41         "unknown",                             // comm
  42         std::set<MapEntry*, MapComparator>(),  // maps
  43     };
  44     auto pair = thread_tree_.insert(std::make_pair(tid, std::unique_ptr<ThreadEntry>(thread)));
  45     CHECK(pair.second);
  46     it = pair.first;
  47   }
  48   thread_comm_storage_.push_back(std::unique_ptr<std::string>(new std::string(comm)));
  49   it->second->comm = thread_comm_storage_.back()->c_str();
  50 }
  51
  52 void SampleTree::ForkThread(int pid, int tid, int ppid, int ptid) {
  53   ThreadEntry* parent = FindThreadOrNew(ppid, ptid);
  54   ThreadEntry* child = FindThreadOrNew(pid, tid);
  55   child->comm = parent->comm;
  56   child->maps = parent->maps;
  57 }
  58
  59 static void RemoveOverlappedMap(std::set<MapEntry*, MapComparator>* map_set, const MapEntry* map) {
  60   for (auto it = map_set->begin(); it != map_set->end();) {
  61     if ((*it)->start_addr >= map->start_addr + map->len) {
  62       break;
  63     }
  64     if ((*it)->start_addr + (*it)->len <= map->start_addr) {
  65       ++it;
  66     } else {
  67       it = map_set->erase(it);
  68     }
  69   }
  70 }
  71
  72 void SampleTree::AddKernelMap(uint64_t start_addr, uint64_t len, uint64_t pgoff, uint64_t time,
  73                               const std::string& filename) {
  74   // kernel map len can be 0 when record command is not run in supervisor mode.
  75   if (len == 0) {
  76     return;
  77   }
  78   DsoEntry* dso = FindKernelDsoOrNew(filename);
  79   MapEntry* map = new MapEntry{
  80       start_addr, len, pgoff, time, dso,
  81   };
  82   map_storage_.push_back(std::unique_ptr<MapEntry>(map));
  83   RemoveOverlappedMap(&kernel_map_tree_, map);
  84   auto pair = kernel_map_tree_.insert(map);
  85   CHECK(pair.second);
  86 }
  87
  88 DsoEntry* SampleTree::FindKernelDsoOrNew(const std::string& filename) {
  89   if (filename == DEFAULT_KERNEL_MMAP_NAME) {
  90     if (kernel_dso_ == nullptr) {
  91       kernel_dso_ = DsoFactory::GetInstance()->LoadKernel();
  92     }
  93     return kernel_dso_.get();
  94   }
  95   auto it = module_dso_tree_.find(filename);
  96   if (it == module_dso_tree_.end()) {
  97     module_dso_tree_[filename] = DsoFactory::GetInstance()->LoadKernelModule(filename);
  98     it = module_dso_tree_.find(filename);
  99   }
 100   return it->second.get();
 101 }
 102
 103 void SampleTree::AddThreadMap(int pid, int tid, uint64_t start_addr, uint64_t len, uint64_t pgoff,
 104                               uint64_t time, const std::string& filename) {
 105   ThreadEntry* thread = FindThreadOrNew(pid, tid);
 106   DsoEntry* dso = FindUserDsoOrNew(filename);
 107   MapEntry* map = new MapEntry{
 108       start_addr, len, pgoff, time, dso,
 109   };
 110   map_storage_.push_back(std::unique_ptr<MapEntry>(map));
 111   RemoveOverlappedMap(&thread->maps, map);
 112   auto pair = thread->maps.insert(map);
 113   CHECK(pair.second);
 114 }
 115
 116 ThreadEntry* SampleTree::FindThreadOrNew(int pid, int tid) {
 117   auto it = thread_tree_.find(tid);
 118   if (it == thread_tree_.end()) {
 119     AddThread(pid, tid, "unknown");
 120     it = thread_tree_.find(tid);
 121   } else {
 122     CHECK_EQ(pid, it->second.get()->pid) << "tid = " << tid;
 123   }
 124   return it->second.get();
 125 }
 126
 127 DsoEntry* SampleTree::FindUserDsoOrNew(const std::string& filename) {
 128   auto it = user_dso_tree_.find(filename);
 129   if (it == user_dso_tree_.end()) {
 130     user_dso_tree_[filename] = DsoFactory::GetInstance()->LoadDso(filename);
 131     it = user_dso_tree_.find(filename);
 132   }
 133   return it->second.get();
 134 }
 135
 136 static bool IsIpInMap(uint64_t ip, const MapEntry* map) {
 137   return (map->start_addr <= ip && map->start_addr + map->len > ip);
 138 }
 139
 140 const MapEntry* SampleTree::FindMap(const ThreadEntry* thread, uint64_t ip, bool in_kernel) {
 141   // Construct a map_entry which is strictly after the searched map_entry, based on MapComparator.
 142   MapEntry find_map = {
 143       ip,          // start_addr
 144       ULLONG_MAX,  // len
 145       0,           // pgoff
 146       ULLONG_MAX,  // time
 147       nullptr,     // dso
 148   };
 149   if (!in_kernel) {
 150     auto it = thread->maps.upper_bound(&find_map);
 151     if (it != thread->maps.begin() && IsIpInMap(ip, *--it)) {
 152       return *it;
 153     }
 154   } else {
 155     auto it = kernel_map_tree_.upper_bound(&find_map);
 156     if (it != kernel_map_tree_.begin() && IsIpInMap(ip, *--it)) {
 157       return *it;
 158     }
 159   }
 160   return &unknown_map_;
 161 }
 162
 163 SampleEntry* SampleTree::AddSample(int pid, int tid, uint64_t ip, uint64_t time, uint64_t period,
 164                                    bool in_kernel) {
 165   const ThreadEntry* thread = FindThreadOrNew(pid, tid);
 166   const MapEntry* map = FindMap(thread, ip, in_kernel);
 167   const SymbolEntry* symbol = FindSymbol(map, ip);
 168
 169   SampleEntry value(ip, time, period, 0, 1, thread, map, symbol);
 170
 171   return InsertSample(value);
 172 }
 173
 174 void SampleTree::AddBranchSample(int pid, int tid, uint64_t from_ip, uint64_t to_ip,
 175                                  uint64_t branch_flags, uint64_t time, uint64_t period) {
 176   const ThreadEntry* thread = FindThreadOrNew(pid, tid);
 177   const MapEntry* from_map = FindMap(thread, from_ip, false);
 178   if (from_map == &unknown_map_) {
 179     from_map = FindMap(thread, from_ip, true);
 180   }
 181   const SymbolEntry* from_symbol = FindSymbol(from_map, from_ip);
 182   const MapEntry* to_map = FindMap(thread, to_ip, false);
 183   if (to_map == &unknown_map_) {
 184     to_map = FindMap(thread, to_ip, true);
 185   }
 186   const SymbolEntry* to_symbol = FindSymbol(to_map, to_ip);
 187
 188   SampleEntry value(to_ip, time, period, 0, 1, thread, to_map, to_symbol);
 189   value.branch_from.ip = from_ip;
 190   value.branch_from.map = from_map;
 191   value.branch_from.symbol = from_symbol;
 192   value.branch_from.flags = branch_flags;
 193
 194   InsertSample(value);
 195 }
 196
 197 SampleEntry* SampleTree::AddCallChainSample(int pid, int tid, uint64_t ip, uint64_t time,
 198                                             uint64_t period, bool in_kernel,
 199                                             const std::vector<SampleEntry*>& callchain) {
 200   const ThreadEntry* thread = FindThreadOrNew(pid, tid);
 201   const MapEntry* map = FindMap(thread, ip, in_kernel);
 202   const SymbolEntry* symbol = FindSymbol(map, ip);
 203
 204   SampleEntry value(ip, time, 0, period, 0, thread, map, symbol);
 205
 206   auto it = sample_tree_.find(&value);
 207   if (it != sample_tree_.end()) {
 208     SampleEntry* sample = *it;
 209     // Process only once for recursive function call.
 210     if (std::find(callchain.begin(), callchain.end(), sample) != callchain.end()) {
 211       return sample;
 212     }
 213   }
 214   return InsertSample(value);
 215 }
 216
 217 SampleEntry* SampleTree::InsertSample(SampleEntry& value) {
 218   SampleEntry* result;
 219   auto it = sample_tree_.find(&value);
 220   if (it == sample_tree_.end()) {
 221     result = AllocateSample(value);
 222     auto pair = sample_tree_.insert(result);
 223     CHECK(pair.second);
 224   } else {
 225     result = *it;
 226     result->period += value.period;
 227     result->accumulated_period += value.accumulated_period;
 228     result->sample_count += value.sample_count;
 229   }
 230   total_samples_ += value.sample_count;
 231   total_period_ += value.period;
 232   return result;
 233 }
 234
 235 SampleEntry* SampleTree::AllocateSample(SampleEntry& value) {
 236   SampleEntry* sample = new SampleEntry(std::move(value));
 237   sample_storage_.push_back(std::unique_ptr<SampleEntry>(sample));
 238   return sample;
 239 }
 240
 241 const SymbolEntry* SampleTree::FindSymbol(const MapEntry* map, uint64_t ip) {
 242   uint64_t offset_in_file;
 243   if (map->dso == kernel_dso_.get()) {
 244     offset_in_file = ip;
 245   } else {
 246     offset_in_file = ip - map->start_addr + map->pgoff;
 247   }
 248   const SymbolEntry* symbol = map->dso->FindSymbol(offset_in_file);
 249   if (symbol == nullptr) {
 250     symbol = &unknown_symbol_;
 251   }
 252   return symbol;
 253 }
 254
 255 void SampleTree::InsertCallChainForSample(SampleEntry* sample,
 256                                           const std::vector<SampleEntry*>& callchain,
 257                                           uint64_t period) {
 258   sample->callchain.AddCallChain(callchain, period);
 259 }
 260
 261 void SampleTree::VisitAllSamples(std::function<void(const SampleEntry&)> callback) {
 262   if (sorted_sample_tree_.size() != sample_tree_.size()) {
 263     sorted_sample_tree_.clear();
 264     for (auto& sample : sample_tree_) {
 265       sample->callchain.SortByPeriod();
 266       sorted_sample_tree_.insert(sample);
 267     }
 268   }
 269   for (auto& sample : sorted_sample_tree_) {
 270     callback(*sample);
 271   }
 272 }