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