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
18namespace v8 {
19namespace internal {
20
21void 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
36void 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
53bool 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
61size_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
72bool ArrayBufferList::IsEmpty() const {
73  DCHECK_IMPLIES(head_, tail_);
74  DCHECK_IMPLIES(!head_, bytes_ == 0);
75  return head_ == nullptr;
76}
77
78struct ArrayBufferSweeper::SweepingJob final {
79  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
101ArrayBufferSweeper::ArrayBufferSweeper(Heap* heap) : heap_(heap) {}
102
103ArrayBufferSweeper::~ArrayBufferSweeper() {
104  EnsureFinished();
105  ReleaseAll(&old_);
106  ReleaseAll(&young_);
107}
108
109void 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
141void ArrayBufferSweeper::FinishIfDone() {
142  if (sweeping_in_progress()) {
143    DCHECK(job_);
144    if (job_->state_ == SweepingState::kDone) {
145      Finalize();
146    }
147  }
148}
149
150void 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
177void 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
195void 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
207void 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
217void 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
232void 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
257void 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
265void 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
274void 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
287void 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
296ArrayBufferList 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
320void 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