1 // Copyright 2020 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_ALLOCATOR_PARTITION_ALLOCATOR_STARSCAN_PCSCAN_H_
6 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_STARSCAN_PCSCAN_H_
7
8 #include <atomic>
9
10 #include "base/allocator/partition_allocator/page_allocator.h"
11 #include "base/allocator/partition_allocator/partition_alloc_base/compiler_specific.h"
12 #include "base/allocator/partition_allocator/partition_alloc_base/component_export.h"
13 #include "base/allocator/partition_allocator/partition_alloc_config.h"
14 #include "base/allocator/partition_allocator/partition_alloc_forward.h"
15 #include "base/allocator/partition_allocator/partition_direct_map_extent.h"
16 #include "base/allocator/partition_allocator/partition_page.h"
17 #include "base/allocator/partition_allocator/starscan/pcscan_scheduling.h"
18 #include "base/allocator/partition_allocator/tagging.h"
19
20 namespace partition_alloc {
21
22 class StatsReporter;
23
24 namespace internal {
25
26 [[noreturn]] PA_NOINLINE PA_NOT_TAIL_CALLED
27 PA_COMPONENT_EXPORT(PARTITION_ALLOC) void DoubleFreeAttempt();
28
29 // PCScan (Probabilistic Conservative Scanning) is the algorithm that eliminates
30 // use-after-free bugs by verifying that there are no pointers in memory which
31 // point to explicitly freed objects before actually releasing their memory. If
32 // PCScan is enabled for a partition, freed objects are not immediately returned
33 // to the allocator, but are stored in a quarantine. When the quarantine reaches
34 // a certain threshold, a concurrent PCScan task gets posted. The task scans the
35 // entire heap, looking for dangling pointers (those that point to the
36 // quarantine entries). After scanning, the unvisited quarantine entries are
37 // unreachable and therefore can be safely reclaimed.
38 //
39 // The driver class encapsulates the entire PCScan infrastructure.
PA_COMPONENT_EXPORT(PARTITION_ALLOC)40 class PA_COMPONENT_EXPORT(PARTITION_ALLOC) PCScan final {
41 public:
42 using Root = PartitionRoot<ThreadSafe>;
43 using SlotSpan = SlotSpanMetadata<ThreadSafe>;
44
45 enum class InvocationMode {
46 kBlocking,
47 kNonBlocking,
48 kForcedBlocking,
49 kScheduleOnlyForTesting,
50 };
51
52 enum class ClearType : uint8_t {
53 // Clear in the scanning task.
54 kLazy,
55 // Eagerly clear quarantined objects on MoveToQuarantine().
56 kEager,
57 };
58
59 // Parameters used to initialize *Scan.
60 struct InitConfig {
61 // Based on the provided mode, PCScan will try to use a certain
62 // WriteProtector, if supported by the system.
63 enum class WantedWriteProtectionMode : uint8_t {
64 kDisabled,
65 kEnabled,
66 } write_protection = WantedWriteProtectionMode::kDisabled;
67
68 // Flag that enables safepoints that stop mutator execution and help
69 // scanning.
70 enum class SafepointMode : uint8_t {
71 kDisabled,
72 kEnabled,
73 } safepoint = SafepointMode::kDisabled;
74 };
75
76 PCScan(const PCScan&) = delete;
77 PCScan& operator=(const PCScan&) = delete;
78
79 // Initializes PCScan and prepares internal data structures.
80 static void Initialize(InitConfig);
81 static bool IsInitialized();
82
83 // Disable/reenable PCScan. Temporal disabling can be useful in CPU demanding
84 // contexts.
85 static void Disable();
86 static void Reenable();
87 // Query if PCScan is enabled.
88 static bool IsEnabled();
89
90 // Registers a root for scanning.
91 static void RegisterScannableRoot(Root* root);
92 // Registers a root that doesn't need to be scanned but still contains
93 // quarantined objects.
94 static void RegisterNonScannableRoot(Root* root);
95
96 // Registers a newly allocated super page for |root|.
97 static void RegisterNewSuperPage(Root* root, uintptr_t super_page_base);
98
99 PA_ALWAYS_INLINE static void MoveToQuarantine(void* object,
100 size_t usable_size,
101 uintptr_t slot_start,
102 size_t slot_size);
103
104 // Performs scanning unconditionally.
105 static void PerformScan(InvocationMode invocation_mode);
106 // Performs scanning only if a certain quarantine threshold was reached.
107 static void PerformScanIfNeeded(InvocationMode invocation_mode);
108 // Performs scanning with specified delay.
109 static void PerformDelayedScan(int64_t delay_in_microseconds);
110
111 // Enables safepoints in mutator threads.
112 PA_ALWAYS_INLINE static void EnableSafepoints();
113 // Join scan from safepoint in mutator thread. As soon as PCScan is scheduled,
114 // mutators can join PCScan helping out with clearing and scanning.
115 PA_ALWAYS_INLINE static void JoinScanIfNeeded();
116
117 // Checks if there is a PCScan task currently in progress.
118 PA_ALWAYS_INLINE static bool IsInProgress();
119
120 // Sets process name (used for histograms). |name| must be a string literal.
121 static void SetProcessName(const char* name);
122
123 static void EnableStackScanning();
124 static void DisableStackScanning();
125 static bool IsStackScanningEnabled();
126
127 static void EnableImmediateFreeing();
128
129 // Notify PCScan that a new thread was created/destroyed. Can be called for
130 // uninitialized PCScan (before Initialize()).
131 static void NotifyThreadCreated(void* stack_top);
132 static void NotifyThreadDestroyed();
133
134 // Define when clearing should happen (on free() or in scanning task).
135 static void SetClearType(ClearType);
136
137 static void UninitForTesting();
138
139 static inline PCScanScheduler& scheduler();
140
141 // Registers reporting class.
142 static void RegisterStatsReporter(partition_alloc::StatsReporter* reporter);
143
144 private:
145 class PCScanThread;
146 friend class PCScanTask;
147 friend class PartitionAllocPCScanTestBase;
148 friend class PCScanInternal;
149
150 enum class State : uint8_t {
151 // PCScan task is not scheduled.
152 kNotRunning,
153 // PCScan task is being started and about to be scheduled.
154 kScheduled,
155 // PCScan task is scheduled and can be scanning (or clearing).
156 kScanning,
157 // PCScan task is sweeping or finalizing.
158 kSweepingAndFinishing
159 };
160
161 PA_ALWAYS_INLINE static PCScan& Instance();
162
163 PA_ALWAYS_INLINE bool IsJoinable() const;
164 PA_ALWAYS_INLINE void SetJoinableIfSafepointEnabled(bool);
165
166 inline constexpr PCScan();
167
168 // Joins scan unconditionally.
169 static void JoinScan();
170
171 // Finish scan as scanner thread.
172 static void FinishScanForTesting();
173
174 // Reinitialize internal structures (e.g. card table).
175 static void ReinitForTesting(InitConfig);
176
177 size_t epoch() const { return scheduler_.epoch(); }
178
179 // PA_CONSTINIT for fast access (avoiding static thread-safe initialization).
180 static PCScan instance_ PA_CONSTINIT;
181
182 PCScanScheduler scheduler_{};
183 std::atomic<State> state_{State::kNotRunning};
184 std::atomic<bool> is_joinable_{false};
185 bool is_safepoint_enabled_{false};
186 ClearType clear_type_{ClearType::kLazy};
187 };
188
189 // To please Chromium's clang plugin.
190 constexpr PCScan::PCScan() = default;
191
Instance()192 PA_ALWAYS_INLINE PCScan& PCScan::Instance() {
193 // The instance is declared as a static member, not static local. The reason
194 // is that we want to use the require_constant_initialization attribute to
195 // avoid double-checked-locking which would otherwise have been introduced
196 // by the compiler for thread-safe dynamic initialization (see constinit
197 // from C++20).
198 return instance_;
199 }
200
IsInProgress()201 PA_ALWAYS_INLINE bool PCScan::IsInProgress() {
202 const PCScan& instance = Instance();
203 return instance.state_.load(std::memory_order_relaxed) != State::kNotRunning;
204 }
205
IsJoinable()206 PA_ALWAYS_INLINE bool PCScan::IsJoinable() const {
207 // This has acquire semantics since a mutator relies on the task being set up.
208 return is_joinable_.load(std::memory_order_acquire);
209 }
210
SetJoinableIfSafepointEnabled(bool value)211 PA_ALWAYS_INLINE void PCScan::SetJoinableIfSafepointEnabled(bool value) {
212 if (!is_safepoint_enabled_) {
213 PA_DCHECK(!is_joinable_.load(std::memory_order_relaxed));
214 return;
215 }
216 // Release semantics is required to "publish" the change of the state so that
217 // the mutators can join scanning and expect the consistent state.
218 is_joinable_.store(value, std::memory_order_release);
219 }
220
EnableSafepoints()221 PA_ALWAYS_INLINE void PCScan::EnableSafepoints() {
222 PCScan& instance = Instance();
223 instance.is_safepoint_enabled_ = true;
224 }
225
JoinScanIfNeeded()226 PA_ALWAYS_INLINE void PCScan::JoinScanIfNeeded() {
227 PCScan& instance = Instance();
228 if (PA_UNLIKELY(instance.IsJoinable()))
229 instance.JoinScan();
230 }
231
MoveToQuarantine(void * object,size_t usable_size,uintptr_t slot_start,size_t slot_size)232 PA_ALWAYS_INLINE void PCScan::MoveToQuarantine(void* object,
233 size_t usable_size,
234 uintptr_t slot_start,
235 size_t slot_size) {
236 PCScan& instance = Instance();
237 if (instance.clear_type_ == ClearType::kEager) {
238 // We need to distinguish between usable_size and slot_size in this context:
239 // - for large buckets usable_size can be noticeably smaller than slot_size;
240 // - usable_size is safe as it doesn't cover extras as opposed to slot_size.
241 // TODO(bikineev): If we start protecting quarantine memory, we can lose
242 // double-free coverage (the check below). Consider performing the
243 // double-free check before protecting if eager clearing becomes default.
244 SecureMemset(object, 0, usable_size);
245 }
246
247 auto* state_bitmap = StateBitmapFromAddr(slot_start);
248
249 // Mark the state in the state bitmap as quarantined. Make sure to do it after
250 // the clearing to avoid racing with *Scan Sweeper.
251 [[maybe_unused]] const bool succeeded =
252 state_bitmap->Quarantine(slot_start, instance.epoch());
253 #if PA_CONFIG(STARSCAN_EAGER_DOUBLE_FREE_DETECTION_ENABLED)
254 if (PA_UNLIKELY(!succeeded))
255 DoubleFreeAttempt();
256 #else
257 // The compiler is able to optimize cmpxchg to a lock-prefixed and.
258 #endif // PA_CONFIG(STARSCAN_EAGER_DOUBLE_FREE_DETECTION_ENABLED)
259
260 const bool is_limit_reached = instance.scheduler_.AccountFreed(slot_size);
261 if (PA_UNLIKELY(is_limit_reached)) {
262 // Perform a quick check if another scan is already in progress.
263 if (instance.IsInProgress())
264 return;
265 // Avoid blocking the current thread for regular scans.
266 instance.PerformScan(InvocationMode::kNonBlocking);
267 }
268 }
269
scheduler()270 inline PCScanScheduler& PCScan::scheduler() {
271 PCScan& instance = Instance();
272 return instance.scheduler_;
273 }
274
275 } // namespace internal
276 } // namespace partition_alloc
277
278 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_STARSCAN_PCSCAN_H_
279