1 // Copyright 2018 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/profiler/module_cache.h"
6
7 #include <iterator>
8 #include <utility>
9
10 #include "base/ranges/algorithm.h"
11
12 namespace base {
13
14 namespace {
15
16 // Supports heterogeneous comparisons on modules and addresses, for use in
17 // binary searching modules sorted by range for a contained address.
18 struct ModuleAddressCompare {
operator ()base::__anon9c586b6e0111::ModuleAddressCompare19 bool operator()(const std::unique_ptr<const ModuleCache::Module>& module,
20 uintptr_t address) const {
21 return module->GetBaseAddress() + module->GetSize() <= address;
22 }
23
operator ()base::__anon9c586b6e0111::ModuleAddressCompare24 bool operator()(
25 uintptr_t address,
26 const std::unique_ptr<const ModuleCache::Module>& module) const {
27 return address < module->GetBaseAddress();
28 }
29 };
30
31 } // namespace
32
33 ModuleCache::ModuleCache() = default;
34 ModuleCache::~ModuleCache() = default;
35
GetModuleForAddress(uintptr_t address)36 const ModuleCache::Module* ModuleCache::GetModuleForAddress(uintptr_t address) {
37 if (const ModuleCache::Module* module = GetExistingModuleForAddress(address))
38 return module;
39
40 std::unique_ptr<const Module> new_module = CreateModuleForAddress(address);
41 if (!new_module)
42 return nullptr;
43 const auto result = native_modules_.insert(std::move(new_module));
44 // TODO(https://crbug.com/1131769): Reintroduce DCHECK(result.second) after
45 // fixing the issue that is causing it to fail.
46 return result.first->get();
47 }
48
GetModules() const49 std::vector<const ModuleCache::Module*> ModuleCache::GetModules() const {
50 std::vector<const Module*> result;
51 result.reserve(native_modules_.size());
52 for (const std::unique_ptr<const Module>& module : native_modules_)
53 result.push_back(module.get());
54 for (const std::unique_ptr<const Module>& module : non_native_modules_)
55 result.push_back(module.get());
56 return result;
57 }
58
UpdateNonNativeModules(const std::vector<const Module * > & defunct_modules,std::vector<std::unique_ptr<const Module>> new_modules)59 void ModuleCache::UpdateNonNativeModules(
60 const std::vector<const Module*>& defunct_modules,
61 std::vector<std::unique_ptr<const Module>> new_modules) {
62 // Insert the modules to remove into a set to support O(log(n)) lookup below.
63 flat_set<const Module*> defunct_modules_set(defunct_modules.begin(),
64 defunct_modules.end());
65
66 // Reorder the modules to be removed to the last slots in the set, then move
67 // them to the inactive modules, then erase the moved-from modules from the
68 // set. This is a variation on the standard erase-remove idiom, which is
69 // explicitly endorsed for implementing erase behavior on flat_sets.
70 //
71 // stable_partition is O(m*log(r)) where m is the number of current modules
72 // and r is the number of modules to remove. insert and erase are both O(r).
73 auto first_module_defunct_modules = ranges::stable_partition(
74 non_native_modules_,
75 [&defunct_modules_set](const std::unique_ptr<const Module>& module) {
76 return defunct_modules_set.find(module.get()) ==
77 defunct_modules_set.end();
78 });
79 // All modules requested to be removed should have been found.
80 DCHECK_EQ(
81 static_cast<ptrdiff_t>(defunct_modules.size()),
82 std::distance(first_module_defunct_modules, non_native_modules_.end()));
83 inactive_non_native_modules_.insert(
84 inactive_non_native_modules_.end(),
85 std::make_move_iterator(first_module_defunct_modules),
86 std::make_move_iterator(non_native_modules_.end()));
87 non_native_modules_.erase(first_module_defunct_modules,
88 non_native_modules_.end());
89
90 // Insert the modules to be added. This operation is O((m + a) + a*log(a))
91 // where m is the number of current modules and a is the number of modules to
92 // be added.
93 const size_t prior_non_native_modules_size = non_native_modules_.size();
94 non_native_modules_.insert(std::make_move_iterator(new_modules.begin()),
95 std::make_move_iterator(new_modules.end()));
96 // Every module in |new_modules| should have been moved into
97 // |non_native_modules_|. This guards against use-after-frees if |new_modules|
98 // were to contain any modules equivalent to what's already in
99 // |non_native_modules_|, in which case the module would remain in
100 // |new_modules| and be deleted on return from the function. While this
101 // scenario would be a violation of the API contract, it would present a
102 // difficult-to-track-down crash scenario.
103 CHECK_EQ(prior_non_native_modules_size + new_modules.size(),
104 non_native_modules_.size());
105 }
106
AddCustomNativeModule(std::unique_ptr<const Module> module)107 void ModuleCache::AddCustomNativeModule(std::unique_ptr<const Module> module) {
108 const bool was_inserted = native_modules_.insert(std::move(module)).second;
109 // |module| should have been inserted into |native_modules_|, indicating that
110 // there was no equivalent module already present. While this scenario would
111 // be a violation of the API contract, it would present a
112 // difficult-to-track-down crash scenario.
113 CHECK(was_inserted);
114 }
115
GetExistingModuleForAddress(uintptr_t address) const116 const ModuleCache::Module* ModuleCache::GetExistingModuleForAddress(
117 uintptr_t address) const {
118 const auto non_native_module_loc = non_native_modules_.find(address);
119 if (non_native_module_loc != non_native_modules_.end())
120 return non_native_module_loc->get();
121
122 const auto native_module_loc = native_modules_.find(address);
123 if (native_module_loc != native_modules_.end())
124 return native_module_loc->get();
125
126 return nullptr;
127 }
128
operator ()(const std::unique_ptr<const Module> & m1,const std::unique_ptr<const Module> & m2) const129 bool ModuleCache::ModuleAndAddressCompare::operator()(
130 const std::unique_ptr<const Module>& m1,
131 const std::unique_ptr<const Module>& m2) const {
132 return m1->GetBaseAddress() < m2->GetBaseAddress();
133 }
134
operator ()(const std::unique_ptr<const Module> & m1,uintptr_t address) const135 bool ModuleCache::ModuleAndAddressCompare::operator()(
136 const std::unique_ptr<const Module>& m1,
137 uintptr_t address) const {
138 return m1->GetBaseAddress() + m1->GetSize() <= address;
139 }
140
operator ()(uintptr_t address,const std::unique_ptr<const Module> & m2) const141 bool ModuleCache::ModuleAndAddressCompare::operator()(
142 uintptr_t address,
143 const std::unique_ptr<const Module>& m2) const {
144 return address < m2->GetBaseAddress();
145 }
146
147 } // namespace base
148