1 // Copyright 2017 the V8 project 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 "src/heap/array-buffer-sweeper.h"
6
7 #include <atomic>
8 #include <memory>
9
10 #include "src/heap/gc-tracer-inl.h"
11 #include "src/heap/gc-tracer.h"
12 #include "src/heap/heap-inl.h"
13 #include "src/heap/heap.h"
14 #include "src/objects/js-array-buffer.h"
15 #include "src/tasks/cancelable-task.h"
16 #include "src/tasks/task-utils.h"
17
18 namespace v8 {
19 namespace internal {
20
Append(ArrayBufferExtension * extension)21 void ArrayBufferList::Append(ArrayBufferExtension* extension) {
22 if (head_ == nullptr) {
23 DCHECK_NULL(tail_);
24 head_ = tail_ = extension;
25 } else {
26 tail_->set_next(extension);
27 tail_ = extension;
28 }
29
30 const size_t accounting_length = extension->accounting_length();
31 DCHECK_GE(bytes_ + accounting_length, bytes_);
32 bytes_ += accounting_length;
33 extension->set_next(nullptr);
34 }
35
Append(ArrayBufferList * list)36 void ArrayBufferList::Append(ArrayBufferList* list) {
37 if (head_ == nullptr) {
38 DCHECK_NULL(tail_);
39 head_ = list->head_;
40 tail_ = list->tail_;
41 } else if (list->head_) {
42 DCHECK_NOT_NULL(list->tail_);
43 tail_->set_next(list->head_);
44 tail_ = list->tail_;
45 } else {
46 DCHECK_NULL(list->tail_);
47 }
48
49 bytes_ += list->ApproximateBytes();
50 *list = ArrayBufferList();
51 }
52
ContainsSlow(ArrayBufferExtension * extension) const53 bool ArrayBufferList::ContainsSlow(ArrayBufferExtension* extension) const {
54 for (ArrayBufferExtension* current = head_; current;
55 current = current->next()) {
56 if (current == extension) return true;
57 }
58 return false;
59 }
60
BytesSlow() const61 size_t ArrayBufferList::BytesSlow() const {
62 ArrayBufferExtension* current = head_;
63 size_t sum = 0;
64 while (current) {
65 sum += current->accounting_length();
66 current = current->next();
67 }
68 DCHECK_GE(sum, ApproximateBytes());
69 return sum;
70 }
71
IsEmpty() const72 bool ArrayBufferList::IsEmpty() const {
73 DCHECK_IMPLIES(head_, tail_);
74 DCHECK_IMPLIES(!head_, bytes_ == 0);
75 return head_ == nullptr;
76 }
77
78 struct ArrayBufferSweeper::SweepingJob final {
SweepingJobv8::internal::ArrayBufferSweeper::SweepingJob79 SweepingJob(ArrayBufferList young, ArrayBufferList old, SweepingType type)
80 : state_(SweepingState::kInProgress),
81 young_(std::move(young)),
82 old_(std::move(old)),
83 type_(type) {}
84
85 void Sweep();
86 void SweepYoung();
87 void SweepFull();
88 ArrayBufferList SweepListFull(ArrayBufferList* list);
89
90 private:
91 CancelableTaskManager::Id id_ = CancelableTaskManager::kInvalidTaskId;
92 std::atomic<SweepingState> state_;
93 ArrayBufferList young_;
94 ArrayBufferList old_;
95 const SweepingType type_;
96 std::atomic<size_t> freed_bytes_{0};
97
98 friend class ArrayBufferSweeper;
99 };
100
ArrayBufferSweeper(Heap * heap)101 ArrayBufferSweeper::ArrayBufferSweeper(Heap* heap) : heap_(heap) {}
102
~ArrayBufferSweeper()103 ArrayBufferSweeper::~ArrayBufferSweeper() {
104 EnsureFinished();
105 ReleaseAll(&old_);
106 ReleaseAll(&young_);
107 }
108
EnsureFinished()109 void ArrayBufferSweeper::EnsureFinished() {
110 if (!sweeping_in_progress()) return;
111
112 TRACE_GC(heap_->tracer(), GCTracer::Scope::MC_COMPLETE_SWEEP_ARRAY_BUFFERS);
113 TryAbortResult abort_result =
114 heap_->isolate()->cancelable_task_manager()->TryAbort(job_->id_);
115
116 switch (abort_result) {
117 case TryAbortResult::kTaskAborted:
118 // Task has not run, so we need to run it synchronously here.
119 job_->Sweep();
120 break;
121 case TryAbortResult::kTaskRemoved:
122 // Task was removed, but did actually run, just ensure we are in the right
123 // state.
124 CHECK_EQ(SweepingState::kDone, job_->state_);
125 break;
126 case TryAbortResult::kTaskRunning: {
127 // Task is running. Wait until task is finished with its work.
128 base::MutexGuard guard(&sweeping_mutex_);
129 while (job_->state_ != SweepingState::kDone) {
130 job_finished_.Wait(&sweeping_mutex_);
131 }
132 break;
133 }
134 }
135
136 Finalize();
137 DCHECK_LE(heap_->backing_store_bytes(), SIZE_MAX);
138 DCHECK(!sweeping_in_progress());
139 }
140
FinishIfDone()141 void ArrayBufferSweeper::FinishIfDone() {
142 if (sweeping_in_progress()) {
143 DCHECK(job_);
144 if (job_->state_ == SweepingState::kDone) {
145 Finalize();
146 }
147 }
148 }
149
RequestSweep(SweepingType type)150 void ArrayBufferSweeper::RequestSweep(SweepingType type) {
151 DCHECK(!sweeping_in_progress());
152
153 if (young_.IsEmpty() && (old_.IsEmpty() || type == SweepingType::kYoung))
154 return;
155
156 Prepare(type);
157 if (!heap_->IsTearingDown() && !heap_->ShouldReduceMemory() &&
158 FLAG_concurrent_array_buffer_sweeping) {
159 auto task = MakeCancelableTask(heap_->isolate(), [this, type] {
160 GCTracer::Scope::ScopeId scope_id =
161 type == SweepingType::kYoung
162 ? GCTracer::Scope::BACKGROUND_YOUNG_ARRAY_BUFFER_SWEEP
163 : GCTracer::Scope::BACKGROUND_FULL_ARRAY_BUFFER_SWEEP;
164 TRACE_GC_EPOCH(heap_->tracer(), scope_id, ThreadKind::kBackground);
165 base::MutexGuard guard(&sweeping_mutex_);
166 job_->Sweep();
167 job_finished_.NotifyAll();
168 });
169 job_->id_ = task->id();
170 V8::GetCurrentPlatform()->CallOnWorkerThread(std::move(task));
171 } else {
172 job_->Sweep();
173 Finalize();
174 }
175 }
176
Prepare(SweepingType type)177 void ArrayBufferSweeper::Prepare(SweepingType type) {
178 DCHECK(!sweeping_in_progress());
179 switch (type) {
180 case SweepingType::kYoung: {
181 job_ = std::make_unique<SweepingJob>(std::move(young_), ArrayBufferList(),
182 type);
183 young_ = ArrayBufferList();
184 } break;
185 case SweepingType::kFull: {
186 job_ = std::make_unique<SweepingJob>(std::move(young_), std::move(old_),
187 type);
188 young_ = ArrayBufferList();
189 old_ = ArrayBufferList();
190 } break;
191 }
192 DCHECK(sweeping_in_progress());
193 }
194
Finalize()195 void ArrayBufferSweeper::Finalize() {
196 DCHECK(sweeping_in_progress());
197 CHECK_EQ(job_->state_, SweepingState::kDone);
198 young_.Append(&job_->young_);
199 old_.Append(&job_->old_);
200 const size_t freed_bytes =
201 job_->freed_bytes_.exchange(0, std::memory_order_relaxed);
202 DecrementExternalMemoryCounters(freed_bytes);
203 job_.reset();
204 DCHECK(!sweeping_in_progress());
205 }
206
ReleaseAll(ArrayBufferList * list)207 void ArrayBufferSweeper::ReleaseAll(ArrayBufferList* list) {
208 ArrayBufferExtension* current = list->head_;
209 while (current) {
210 ArrayBufferExtension* next = current->next();
211 delete current;
212 current = next;
213 }
214 *list = ArrayBufferList();
215 }
216
Append(JSArrayBuffer object,ArrayBufferExtension * extension)217 void ArrayBufferSweeper::Append(JSArrayBuffer object,
218 ArrayBufferExtension* extension) {
219 size_t bytes = extension->accounting_length();
220
221 FinishIfDone();
222
223 if (Heap::InYoungGeneration(object)) {
224 young_.Append(extension);
225 } else {
226 old_.Append(extension);
227 }
228
229 IncrementExternalMemoryCounters(bytes);
230 }
231
Detach(JSArrayBuffer object,ArrayBufferExtension * extension)232 void ArrayBufferSweeper::Detach(JSArrayBuffer object,
233 ArrayBufferExtension* extension) {
234 size_t bytes = extension->ClearAccountingLength();
235
236 // We cannot free the extension eagerly here, since extensions are tracked in
237 // a singly linked list. The next GC will remove it automatically.
238
239 FinishIfDone();
240
241 if (!sweeping_in_progress()) {
242 // If concurrent sweeping isn't running at the moment, we can also adjust
243 // the respective bytes in the corresponding ArraybufferLists as they are
244 // only approximate.
245 if (Heap::InYoungGeneration(object)) {
246 DCHECK_GE(young_.bytes_, bytes);
247 young_.bytes_ -= bytes;
248 } else {
249 DCHECK_GE(old_.bytes_, bytes);
250 old_.bytes_ -= bytes;
251 }
252 }
253
254 DecrementExternalMemoryCounters(bytes);
255 }
256
IncrementExternalMemoryCounters(size_t bytes)257 void ArrayBufferSweeper::IncrementExternalMemoryCounters(size_t bytes) {
258 if (bytes == 0) return;
259 heap_->IncrementExternalBackingStoreBytes(
260 ExternalBackingStoreType::kArrayBuffer, bytes);
261 reinterpret_cast<v8::Isolate*>(heap_->isolate())
262 ->AdjustAmountOfExternalAllocatedMemory(static_cast<int64_t>(bytes));
263 }
264
DecrementExternalMemoryCounters(size_t bytes)265 void ArrayBufferSweeper::DecrementExternalMemoryCounters(size_t bytes) {
266 if (bytes == 0) return;
267 heap_->DecrementExternalBackingStoreBytes(
268 ExternalBackingStoreType::kArrayBuffer, bytes);
269 // Unlike IncrementExternalMemoryCounters we don't use
270 // AdjustAmountOfExternalAllocatedMemory such that we never start a GC here.
271 heap_->update_external_memory(-static_cast<int64_t>(bytes));
272 }
273
Sweep()274 void ArrayBufferSweeper::SweepingJob::Sweep() {
275 CHECK_EQ(state_, SweepingState::kInProgress);
276 switch (type_) {
277 case SweepingType::kYoung:
278 SweepYoung();
279 break;
280 case SweepingType::kFull:
281 SweepFull();
282 break;
283 }
284 state_ = SweepingState::kDone;
285 }
286
SweepFull()287 void ArrayBufferSweeper::SweepingJob::SweepFull() {
288 DCHECK_EQ(SweepingType::kFull, type_);
289 ArrayBufferList promoted = SweepListFull(&young_);
290 ArrayBufferList survived = SweepListFull(&old_);
291
292 old_ = std::move(promoted);
293 old_.Append(&survived);
294 }
295
SweepListFull(ArrayBufferList * list)296 ArrayBufferList ArrayBufferSweeper::SweepingJob::SweepListFull(
297 ArrayBufferList* list) {
298 ArrayBufferExtension* current = list->head_;
299 ArrayBufferList survivor_list;
300
301 while (current) {
302 ArrayBufferExtension* next = current->next();
303
304 if (!current->IsMarked()) {
305 const size_t bytes = current->accounting_length();
306 delete current;
307 if (bytes) freed_bytes_.fetch_add(bytes, std::memory_order_relaxed);
308 } else {
309 current->Unmark();
310 survivor_list.Append(current);
311 }
312
313 current = next;
314 }
315
316 *list = ArrayBufferList();
317 return survivor_list;
318 }
319
SweepYoung()320 void ArrayBufferSweeper::SweepingJob::SweepYoung() {
321 DCHECK_EQ(SweepingType::kYoung, type_);
322 ArrayBufferExtension* current = young_.head_;
323
324 ArrayBufferList new_young;
325 ArrayBufferList new_old;
326
327 while (current) {
328 ArrayBufferExtension* next = current->next();
329
330 if (!current->IsYoungMarked()) {
331 size_t bytes = current->accounting_length();
332 delete current;
333 if (bytes) freed_bytes_.fetch_add(bytes, std::memory_order_relaxed);
334 } else if (current->IsYoungPromoted()) {
335 current->YoungUnmark();
336 new_old.Append(current);
337 } else {
338 current->YoungUnmark();
339 new_young.Append(current);
340 }
341
342 current = next;
343 }
344
345 old_ = new_old;
346 young_ = new_young;
347 }
348
349 } // namespace internal
350 } // namespace v8
351