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 
15 namespace v8 {
16 namespace internal {
17 
18 class MajorNonAtomicMarkingState;
19 class Page;
20 class PagedSpace;
21 
22 enum FreeSpaceTreatmentMode { IGNORE_FREE_SPACE, ZAP_FREE_SPACE };
23 
24 class Sweeper {
25  public:
26   typedef std::vector<Page*> IterabilityList;
27   typedef std::deque<Page*> SweepingList;
28   typedef std::vector<Page*> SweptList;
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>
FilterOldSpaceSweepingPages(Callback 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 
Sweeper(Heap * heap,MajorNonAtomicMarkingState * marking_state)80   Sweeper(Heap* heap, MajorNonAtomicMarkingState* marking_state)
81       : heap_(heap),
82         marking_state_(marking_state),
83         num_tasks_(0),
84         pending_sweeper_tasks_semaphore_(0),
85         incremental_sweeper_pending_(false),
86         sweeping_in_progress_(false),
87         num_sweeping_tasks_(0),
88         stop_sweeper_tasks_(false),
89         iterability_task_semaphore_(0),
90         iterability_in_progress_(false),
91         iterability_task_started_(false) {}
92 
sweeping_in_progress()93   bool sweeping_in_progress() const { return sweeping_in_progress_; }
94 
95   void AddPage(AllocationSpace space, Page* page, AddPageMode mode);
96 
97   int ParallelSweepSpace(AllocationSpace identity, int required_freed_bytes,
98                          int max_pages = 0);
99   int ParallelSweepPage(Page* page, AllocationSpace identity);
100 
101   void ScheduleIncrementalSweepingTask();
102 
103   int RawSweep(Page* p, FreeListRebuildingMode free_list_mode,
104                FreeSpaceTreatmentMode free_space_mode);
105 
106   // After calling this function sweeping is considered to be in progress
107   // and the main thread can sweep lazily, but the background sweeper tasks
108   // are not running yet.
109   void StartSweeping();
110   void StartSweeperTasks();
111   void EnsureCompleted();
112   bool AreSweeperTasksRunning();
113 
114   Page* GetSweptPageSafe(PagedSpace* space);
115 
116   void EnsurePageIsIterable(Page* page);
117 
118   void AddPageForIterability(Page* page);
119   void StartIterabilityTasks();
120   void EnsureIterabilityCompleted();
121 
122  private:
123   class IncrementalSweeperTask;
124   class IterabilityTask;
125   class SweeperTask;
126 
127   static const int kNumberOfSweepingSpaces =
128       LAST_GROWABLE_PAGED_SPACE - FIRST_GROWABLE_PAGED_SPACE + 1;
129   static const int kMaxSweeperTasks = 3;
130 
131   template <typename Callback>
ForAllSweepingSpaces(Callback callback)132   void ForAllSweepingSpaces(Callback callback) const {
133     callback(OLD_SPACE);
134     callback(CODE_SPACE);
135     callback(MAP_SPACE);
136   }
137 
138   // Can only be called on the main thread when no tasks are running.
IsDoneSweeping()139   bool IsDoneSweeping() const {
140     bool is_done = true;
141     ForAllSweepingSpaces([this, &is_done](AllocationSpace space) {
142       if (!sweeping_list_[GetSweepSpaceIndex(space)].empty()) is_done = false;
143     });
144     return is_done;
145   }
146 
147   void SweepSpaceFromTask(AllocationSpace identity);
148 
149   // Sweeps incrementally one page from the given space. Returns true if
150   // there are no more pages to sweep in the given space.
151   bool SweepSpaceIncrementallyFromTask(AllocationSpace identity);
152 
153   void AbortAndWaitForTasks();
154 
155   Page* GetSweepingPageSafe(AllocationSpace space);
156 
157   void PrepareToBeSweptPage(AllocationSpace space, Page* page);
158 
159   void SweepOrWaitUntilSweepingCompleted(Page* page);
160 
161   void MakeIterable(Page* page);
162 
IsValidIterabilitySpace(AllocationSpace space)163   bool IsValidIterabilitySpace(AllocationSpace space) {
164     return space == NEW_SPACE || space == RO_SPACE;
165   }
166 
IsValidSweepingSpace(AllocationSpace space)167   static bool IsValidSweepingSpace(AllocationSpace space) {
168     return space >= FIRST_GROWABLE_PAGED_SPACE &&
169            space <= LAST_GROWABLE_PAGED_SPACE;
170   }
171 
GetSweepSpaceIndex(AllocationSpace space)172   static int GetSweepSpaceIndex(AllocationSpace space) {
173     DCHECK(IsValidSweepingSpace(space));
174     return space - FIRST_GROWABLE_PAGED_SPACE;
175   }
176 
177   Heap* const heap_;
178   MajorNonAtomicMarkingState* marking_state_;
179   int num_tasks_;
180   CancelableTaskManager::Id task_ids_[kNumberOfSweepingSpaces];
181   base::Semaphore pending_sweeper_tasks_semaphore_;
182   base::Mutex mutex_;
183   SweptList swept_list_[kNumberOfSweepingSpaces];
184   SweepingList sweeping_list_[kNumberOfSweepingSpaces];
185   bool incremental_sweeper_pending_;
186   bool sweeping_in_progress_;
187   // Counter is actively maintained by the concurrent tasks to avoid querying
188   // the semaphore for maintaining a task counter on the main thread.
189   std::atomic<intptr_t> num_sweeping_tasks_;
190   // Used by PauseOrCompleteScope to signal early bailout to tasks.
191   base::AtomicValue<bool> stop_sweeper_tasks_;
192 
193   // Pages that are only made iterable but have their free lists ignored.
194   IterabilityList iterability_list_;
195   CancelableTaskManager::Id iterability_task_id_;
196   base::Semaphore iterability_task_semaphore_;
197   bool iterability_in_progress_;
198   bool iterability_task_started_;
199 };
200 
201 }  // namespace internal
202 }  // namespace v8
203 
204 #endif  // V8_HEAP_SWEEPER_H_
205