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#ifndef V8_HEAP_SWEEPER_H_
6#define V8_HEAP_SWEEPER_H_
7
8#include <deque>
9#include <vector>
10
11#include "src/base/platform/semaphore.h"
12#include "src/cancelable-task.h"
13#include "src/globals.h"
14
15namespace v8 {
16namespace internal {
17
18class MajorNonAtomicMarkingState;
19class Page;
20class PagedSpace;
21
22enum FreeSpaceTreatmentMode { IGNORE_FREE_SPACE, ZAP_FREE_SPACE };
23
24class Sweeper {
25 public:
26 using IterabilityList = std::vector<Page*>;
27 using SweepingList = std::deque<Page*>;
28 using SweptList = std::vector<Page*>;
29
30 // Pauses the sweeper tasks or completes sweeping.
31 class PauseOrCompleteScope final {
32 public:
33 explicit PauseOrCompleteScope(Sweeper* sweeper);
34 ~PauseOrCompleteScope();
35
36 private:
37 Sweeper* const sweeper_;
38 };
39
40 // Temporary filters old space sweeping lists. Requires the concurrent
41 // sweeper to be paused. Allows for pages to be added to the sweeper while
42 // in this scope. Note that the original list of sweeping pages is restored
43 // after exiting this scope.
44 class FilterSweepingPagesScope final {
45 public:
46 explicit FilterSweepingPagesScope(
47 Sweeper* sweeper, const PauseOrCompleteScope& pause_or_complete_scope);
48 ~FilterSweepingPagesScope();
49
50 template <typename Callback>
51 void FilterOldSpaceSweepingPages(Callback callback) {
52 if (!sweeping_in_progress_) return;
53
54 SweepingList* sweeper_list =
55 &sweeper_->sweeping_list_[GetSweepSpaceIndex(OLD_SPACE)];
56 // Iteration here is from most free space to least free space.
57 for (auto it = old_space_sweeping_list_.begin();
58 it != old_space_sweeping_list_.end(); it++) {
59 if (callback(*it)) {
60 sweeper_list->push_back(*it);
61 }
62 }
63 }
64
65 private:
66 Sweeper* const sweeper_;
67 SweepingList old_space_sweeping_list_;
68 const PauseOrCompleteScope& pause_or_complete_scope_;
69 bool sweeping_in_progress_;
70 };
71
72 enum FreeListRebuildingMode { REBUILD_FREE_LIST, IGNORE_FREE_LIST };
73 enum ClearOldToNewSlotsMode {
74 DO_NOT_CLEAR,
75 CLEAR_REGULAR_SLOTS,
76 CLEAR_TYPED_SLOTS
77 };
78 enum AddPageMode { REGULAR, READD_TEMPORARY_REMOVED_PAGE };
79
80 Sweeper(Heap* heap, MajorNonAtomicMarkingState* marking_state);
81
82 bool sweeping_in_progress() const { return sweeping_in_progress_; }
83
84 void AddPage(AllocationSpace space, Page* page, AddPageMode mode);
85
86 int ParallelSweepSpace(AllocationSpace identity, int required_freed_bytes,
87 int max_pages = 0);
88 int ParallelSweepPage(Page* page, AllocationSpace identity);
89
90 void ScheduleIncrementalSweepingTask();
91
92 int RawSweep(Page* p, FreeListRebuildingMode free_list_mode,
93 FreeSpaceTreatmentMode free_space_mode);
94
95 // After calling this function sweeping is considered to be in progress
96 // and the main thread can sweep lazily, but the background sweeper tasks
97 // are not running yet.
98 void StartSweeping();
99 V8_EXPORT_PRIVATE void StartSweeperTasks();
100 void EnsureCompleted();
101 bool AreSweeperTasksRunning();
102
103 Page* GetSweptPageSafe(PagedSpace* space);
104
105 void EnsurePageIsIterable(Page* page);
106
107 void AddPageForIterability(Page* page);
108 void StartIterabilityTasks();
109 void EnsureIterabilityCompleted();
110
111 private:
112 class IncrementalSweeperTask;
113 class IterabilityTask;
114 class SweeperTask;
115
116 static const int kNumberOfSweepingSpaces =
117 LAST_GROWABLE_PAGED_SPACE - FIRST_GROWABLE_PAGED_SPACE + 1;
118 static const int kMaxSweeperTasks = 3;
119
120 template <typename Callback>
121 void ForAllSweepingSpaces(Callback callback) const {
122 callback(OLD_SPACE);
123 callback(CODE_SPACE);
124 callback(MAP_SPACE);
125 }
126
127 // Can only be called on the main thread when no tasks are running.
128 bool IsDoneSweeping() const {
129 bool is_done = true;
130 ForAllSweepingSpaces([this, &is_done](AllocationSpace space) {
131 if (!sweeping_list_[GetSweepSpaceIndex(space)].empty()) is_done = false;
132 });
133 return is_done;
134 }
135
136 void SweepSpaceFromTask(AllocationSpace identity);
137
138 // Sweeps incrementally one page from the given space. Returns true if
139 // there are no more pages to sweep in the given space.
140 bool SweepSpaceIncrementallyFromTask(AllocationSpace identity);
141
142 void AbortAndWaitForTasks();
143
144 Page* GetSweepingPageSafe(AllocationSpace space);
145
146 void PrepareToBeSweptPage(AllocationSpace space, Page* page);
147
148 void SweepOrWaitUntilSweepingCompleted(Page* page);
149
150 void MakeIterable(Page* page);
151
152 bool IsValidIterabilitySpace(AllocationSpace space) {
153 return space == NEW_SPACE || space == RO_SPACE;
154 }
155
156 static bool IsValidSweepingSpace(AllocationSpace space) {
157 return space >= FIRST_GROWABLE_PAGED_SPACE &&
158 space <= LAST_GROWABLE_PAGED_SPACE;
159 }
160
161 static int GetSweepSpaceIndex(AllocationSpace space) {
162 DCHECK(IsValidSweepingSpace(space));
163 return space - FIRST_GROWABLE_PAGED_SPACE;
164 }
165
166 Heap* const heap_;
167 MajorNonAtomicMarkingState* marking_state_;
168 int num_tasks_;
169 CancelableTaskManager::Id task_ids_[kNumberOfSweepingSpaces];
170 base::Semaphore pending_sweeper_tasks_semaphore_;
171 base::Mutex mutex_;
172 SweptList swept_list_[kNumberOfSweepingSpaces];
173 SweepingList sweeping_list_[kNumberOfSweepingSpaces];
174 bool incremental_sweeper_pending_;
175 bool sweeping_in_progress_;
176 // Counter is actively maintained by the concurrent tasks to avoid querying
177 // the semaphore for maintaining a task counter on the main thread.
178 std::atomic<intptr_t> num_sweeping_tasks_;
179 // Used by PauseOrCompleteScope to signal early bailout to tasks.
180 std::atomic<bool> stop_sweeper_tasks_;
181
182 // Pages that are only made iterable but have their free lists ignored.
183 IterabilityList iterability_list_;
184 CancelableTaskManager::Id iterability_task_id_;
185 base::Semaphore iterability_task_semaphore_;
186 bool iterability_in_progress_;
187 bool iterability_task_started_;
188 bool should_reduce_memory_;
189};
190
191} // namespace internal
192} // namespace v8
193
194#endif // V8_HEAP_SWEEPER_H_
195