1 // Copyright 2021 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_SCHEDULING_H_
6 #define BASE_ALLOCATOR_PARTITION_ALLOCATOR_STARSCAN_PCSCAN_SCHEDULING_H_
7
8 #include <atomic>
9 #include <cstdint>
10
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_base/thread_annotations.h"
14 #include "base/allocator/partition_allocator/partition_alloc_base/time/time.h"
15 #include "base/allocator/partition_allocator/partition_lock.h"
16
17 namespace partition_alloc::internal {
18
19 class PCScanScheduler;
20
21 struct QuarantineData final {
22 static constexpr size_t kQuarantineSizeMinLimit = 1 * 1024 * 1024;
23
24 inline constexpr QuarantineData();
25
MinimumScanningThresholdReachedfinal26 bool MinimumScanningThresholdReached() const {
27 return current_size.load(std::memory_order_relaxed) >
28 kQuarantineSizeMinLimit;
29 }
30
31 std::atomic<size_t> current_size{0u};
32 std::atomic<size_t> size_limit{kQuarantineSizeMinLimit};
33 std::atomic<size_t> epoch{0u};
34 };
35
PA_COMPONENT_EXPORT(PARTITION_ALLOC)36 class PA_COMPONENT_EXPORT(PARTITION_ALLOC) PCScanSchedulingBackend {
37 public:
38 inline constexpr explicit PCScanSchedulingBackend(PCScanScheduler&);
39 // No virtual destructor to allow constant initialization of PCScan as
40 // static global which directly embeds LimitBackend as default backend.
41
42 PCScanSchedulingBackend(const PCScanSchedulingBackend&) = delete;
43 PCScanSchedulingBackend& operator=(const PCScanSchedulingBackend&) = delete;
44
45 void DisableScheduling();
46 void EnableScheduling();
47
48 bool is_scheduling_enabled() const {
49 return scheduling_enabled_.load(std::memory_order_relaxed);
50 }
51
52 inline QuarantineData& GetQuarantineData();
53
54 // Invoked when the limit in PCScanScheduler is reached. Returning true
55 // signals the caller to invoke a scan.
56 virtual bool LimitReached() = 0;
57
58 // Invoked on starting a scan. Returns current quarantine size.
59 virtual size_t ScanStarted();
60
61 // Invoked at the end of a scan to compute a new limit.
62 virtual void UpdateScheduleAfterScan(size_t survived_bytes,
63 base::TimeDelta time_spent_in_scan,
64 size_t heap_size) = 0;
65
66 // Invoked by PCScan to ask for a new timeout for a scheduled PCScan task.
67 // Only invoked if scheduler requests a delayed scan at some point.
68 virtual base::TimeDelta UpdateDelayedSchedule();
69
70 protected:
71 inline bool SchedulingDisabled() const;
72
73 virtual bool NeedsToImmediatelyScan() = 0;
74
75 PCScanScheduler& scheduler_;
76 std::atomic<bool> scheduling_enabled_{true};
77 };
78
79 // Scheduling backend that just considers a single hard limit.
PA_COMPONENT_EXPORT(PARTITION_ALLOC)80 class PA_COMPONENT_EXPORT(PARTITION_ALLOC) LimitBackend final
81 : public PCScanSchedulingBackend {
82 public:
83 static constexpr double kQuarantineSizeFraction = 0.1;
84
85 inline constexpr explicit LimitBackend(PCScanScheduler&);
86
87 bool LimitReached() final;
88 void UpdateScheduleAfterScan(size_t, base::TimeDelta, size_t) final;
89
90 private:
91 bool NeedsToImmediatelyScan() final;
92 };
93
94 // Task based backend that is aware of a target mutator utilization that
95 // specifies how much percent of the execution should be reserved for the
96 // mutator. I.e., the MU-aware scheduler ensures that scans are limit and
97 // there is enough time left for the mutator to execute the actual application
98 // workload.
99 //
100 // See constants below for trigger mechanisms.
PA_COMPONENT_EXPORT(PARTITION_ALLOC)101 class PA_COMPONENT_EXPORT(PARTITION_ALLOC) MUAwareTaskBasedBackend final
102 : public PCScanSchedulingBackend {
103 public:
104 using ScheduleDelayedScanFunc = void (*)(int64_t delay_in_microseconds);
105
106 MUAwareTaskBasedBackend(PCScanScheduler&, ScheduleDelayedScanFunc);
107 ~MUAwareTaskBasedBackend();
108
109 bool LimitReached() final;
110 size_t ScanStarted() final;
111 void UpdateScheduleAfterScan(size_t, base::TimeDelta, size_t) final;
112 base::TimeDelta UpdateDelayedSchedule() final;
113
114 private:
115 // Limit triggering the scheduler. If `kTargetMutatorUtilizationPercent` is
116 // satisfied at this point then a scan is triggered immediately.
117 static constexpr double kSoftLimitQuarantineSizePercent = 0.1;
118 // Hard limit at which a scan is triggered in any case. Avoids blowing up the
119 // heap completely.
120 static constexpr double kHardLimitQuarantineSizePercent = 0.5;
121 // Target mutator utilization that is respected when invoking a scan.
122 // Specifies how much percent of walltime should be spent in the mutator.
123 // Inversely, specifies how much walltime (indirectly CPU) is spent on
124 // memory management in scan.
125 static constexpr double kTargetMutatorUtilizationPercent = 0.90;
126
127 bool NeedsToImmediatelyScan() final;
128
129 // Callback to schedule a delayed scan.
130 const ScheduleDelayedScanFunc schedule_delayed_scan_;
131
132 Lock scheduler_lock_;
133 size_t hard_limit_ PA_GUARDED_BY(scheduler_lock_){0};
134 base::TimeTicks earliest_next_scan_time_ PA_GUARDED_BY(scheduler_lock_);
135
136 friend class PartitionAllocPCScanMUAwareTaskBasedBackendTest;
137 };
138
139 // The scheduler that is embedded in the PCSCan frontend which requires a fast
140 // path for freeing objects. The scheduler holds data needed to invoke a
141 // `PCScanSchedulingBackend` upon hitting a limit. The backend implements
142 // the actual scheduling strategy and is in charge of maintaining limits.
PA_COMPONENT_EXPORT(PARTITION_ALLOC)143 class PA_COMPONENT_EXPORT(PARTITION_ALLOC) PCScanScheduler final {
144 public:
145 inline constexpr PCScanScheduler();
146
147 PCScanScheduler(const PCScanScheduler&) = delete;
148 PCScanScheduler& operator=(const PCScanScheduler&) = delete;
149
150 // Account freed `bytes`. Returns true if scan should be triggered
151 // immediately, and false otherwise.
152 PA_ALWAYS_INLINE bool AccountFreed(size_t bytes);
153
154 size_t epoch() const {
155 return quarantine_data_.epoch.load(std::memory_order_relaxed);
156 }
157
158 // Sets a new scheduling backend that should be used by the scanner.
159 void SetNewSchedulingBackend(PCScanSchedulingBackend&);
160
161 PCScanSchedulingBackend& scheduling_backend() { return *backend_; }
162 const PCScanSchedulingBackend& scheduling_backend() const {
163 return *backend_;
164 }
165
166 private:
167 QuarantineData quarantine_data_{};
168 // The default backend used is a simple LimitBackend that just triggers scan
169 // on reaching a hard limit.
170 LimitBackend default_scheduling_backend_{*this};
171 PCScanSchedulingBackend* backend_ = &default_scheduling_backend_;
172
173 friend PCScanSchedulingBackend;
174 };
175
176 // To please Chromium's clang plugin.
177 constexpr PCScanScheduler::PCScanScheduler() = default;
178 constexpr QuarantineData::QuarantineData() = default;
179
PCScanSchedulingBackend(PCScanScheduler & scheduler)180 constexpr PCScanSchedulingBackend::PCScanSchedulingBackend(
181 PCScanScheduler& scheduler)
182 : scheduler_(scheduler) {}
183
GetQuarantineData()184 QuarantineData& PCScanSchedulingBackend::GetQuarantineData() {
185 return scheduler_.quarantine_data_;
186 }
187
LimitBackend(PCScanScheduler & scheduler)188 constexpr LimitBackend::LimitBackend(PCScanScheduler& scheduler)
189 : PCScanSchedulingBackend(scheduler) {}
190
AccountFreed(size_t size)191 PA_ALWAYS_INLINE bool PCScanScheduler::AccountFreed(size_t size) {
192 const size_t size_before =
193 quarantine_data_.current_size.fetch_add(size, std::memory_order_relaxed);
194 return (size_before + size >
195 quarantine_data_.size_limit.load(std::memory_order_relaxed)) &&
196 backend_->LimitReached();
197 }
198
199 } // namespace partition_alloc::internal
200
201 #endif // BASE_ALLOCATOR_PARTITION_ALLOCATOR_STARSCAN_PCSCAN_SCHEDULING_H_
202