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 <map> 10 #include <vector> 11 12 #include "src/base/platform/semaphore.h" 13 #include "src/common/globals.h" 14 #include "src/tasks/cancelable-task.h" 15 16 namespace v8 { 17 namespace internal { 18 19 class InvalidatedSlotsCleanup; 20 class MajorNonAtomicMarkingState; 21 class Page; 22 class PagedSpace; 23 class Space; 24 25 enum FreeSpaceTreatmentMode { IGNORE_FREE_SPACE, ZAP_FREE_SPACE }; 26 27 class Sweeper { 28 public: 29 using IterabilityList = std::vector<Page*>; 30 using SweepingList = std::vector<Page*>; 31 using SweptList = std::vector<Page*>; 32 using FreeRangesMap = std::map<uint32_t, uint32_t>; 33 34 // Pauses the sweeper tasks or completes sweeping. 35 class PauseOrCompleteScope final { 36 public: 37 explicit PauseOrCompleteScope(Sweeper* sweeper); 38 ~PauseOrCompleteScope(); 39 40 private: 41 Sweeper* const sweeper_; 42 }; 43 44 // Temporary filters old space sweeping lists. Requires the concurrent 45 // sweeper to be paused. Allows for pages to be added to the sweeper while 46 // in this scope. Note that the original list of sweeping pages is restored 47 // after exiting this scope. 48 class FilterSweepingPagesScope final { 49 public: 50 FilterSweepingPagesScope( 51 Sweeper* sweeper, const PauseOrCompleteScope& pause_or_complete_scope); 52 ~FilterSweepingPagesScope(); 53 54 template <typename Callback> FilterOldSpaceSweepingPages(Callback callback)55 void FilterOldSpaceSweepingPages(Callback callback) { 56 if (!sweeping_in_progress_) return; 57 58 SweepingList* sweeper_list = 59 &sweeper_->sweeping_list_[GetSweepSpaceIndex(OLD_SPACE)]; 60 // Iteration here is from most free space to least free space. 61 for (auto it = old_space_sweeping_list_.begin(); 62 it != old_space_sweeping_list_.end(); it++) { 63 if (callback(*it)) { 64 sweeper_list->push_back(*it); 65 } 66 } 67 } 68 69 private: 70 Sweeper* const sweeper_; 71 SweepingList old_space_sweeping_list_; 72 const PauseOrCompleteScope& pause_or_complete_scope_; 73 bool sweeping_in_progress_; 74 }; 75 76 enum FreeListRebuildingMode { REBUILD_FREE_LIST, IGNORE_FREE_LIST }; 77 enum AddPageMode { REGULAR, READD_TEMPORARY_REMOVED_PAGE }; 78 enum class FreeSpaceMayContainInvalidatedSlots { kYes, kNo }; 79 80 Sweeper(Heap* heap, MajorNonAtomicMarkingState* marking_state); 81 sweeping_in_progress()82 bool sweeping_in_progress() const { return sweeping_in_progress_; } 83 84 void AddPage(AllocationSpace space, Page* page, AddPageMode mode); 85 86 int ParallelSweepSpace( 87 AllocationSpace identity, int required_freed_bytes, int max_pages = 0, 88 FreeSpaceMayContainInvalidatedSlots invalidated_slots_in_free_space = 89 FreeSpaceMayContainInvalidatedSlots::kNo); 90 int ParallelSweepPage( 91 Page* page, AllocationSpace identity, 92 FreeSpaceMayContainInvalidatedSlots invalidated_slots_in_free_space = 93 FreeSpaceMayContainInvalidatedSlots::kNo); 94 95 void ScheduleIncrementalSweepingTask(); 96 97 int RawSweep( 98 Page* p, FreeListRebuildingMode free_list_mode, 99 FreeSpaceTreatmentMode free_space_mode, 100 FreeSpaceMayContainInvalidatedSlots invalidated_slots_in_free_space, 101 const base::MutexGuard& page_guard); 102 103 // After calling this function sweeping is considered to be in progress 104 // and the main thread can sweep lazily, but the background sweeper tasks 105 // are not running yet. 106 void StartSweeping(); 107 V8_EXPORT_PRIVATE void StartSweeperTasks(); 108 void EnsureCompleted(); 109 void DrainSweepingWorklists(); 110 void DrainSweepingWorklistForSpace(AllocationSpace space); 111 bool AreSweeperTasksRunning(); 112 113 // Support concurrent sweepers from main thread 114 void SupportConcurrentSweeping(); 115 116 Page* GetSweptPageSafe(PagedSpace* space); 117 118 void AddPageForIterability(Page* page); 119 void StartIterabilityTasks(); 120 void EnsureIterabilityCompleted(); 121 void MergeOldToNewRememberedSetsForSweptPages(); 122 123 private: 124 class IncrementalSweeperTask; 125 class IterabilityTask; 126 class SweeperTask; 127 128 static const int kNumberOfSweepingSpaces = 129 LAST_GROWABLE_PAGED_SPACE - FIRST_GROWABLE_PAGED_SPACE + 1; 130 static const int kMaxSweeperTasks = 3; 131 132 template <typename Callback> ForAllSweepingSpaces(Callback callback)133 void ForAllSweepingSpaces(Callback callback) const { 134 callback(OLD_SPACE); 135 callback(CODE_SPACE); 136 callback(MAP_SPACE); 137 } 138 139 // Helper function for RawSweep. Depending on the FreeListRebuildingMode and 140 // FreeSpaceTreatmentMode this function may add the free memory to a free 141 // list, make the memory iterable, clear it, and return the free memory to 142 // the operating system. 143 size_t FreeAndProcessFreedMemory(Address free_start, Address free_end, 144 Page* page, Space* space, 145 bool non_empty_typed_slots, 146 FreeListRebuildingMode free_list_mode, 147 FreeSpaceTreatmentMode free_space_mode); 148 149 // Helper function for RawSweep. Handle remembered set entries in the freed 150 // memory which require clearing. 151 void CleanupRememberedSetEntriesForFreedMemory( 152 Address free_start, Address free_end, Page* page, 153 bool non_empty_typed_slots, FreeRangesMap* free_ranges_map, 154 InvalidatedSlotsCleanup* old_to_new_cleanup); 155 156 // Helper function for RawSweep. Clears invalid typed slots in the given free 157 // ranges. 158 void CleanupInvalidTypedSlotsOfFreeRanges( 159 Page* page, const FreeRangesMap& free_ranges_map); 160 161 // Helper function for RawSweep. Clears the mark bits and ensures consistency 162 // of live bytes. 163 void ClearMarkBitsAndHandleLivenessStatistics( 164 Page* page, size_t live_bytes, FreeListRebuildingMode free_list_mode); 165 166 // Can only be called on the main thread when no tasks are running. IsDoneSweeping()167 bool IsDoneSweeping() const { 168 bool is_done = true; 169 ForAllSweepingSpaces([this, &is_done](AllocationSpace space) { 170 if (!sweeping_list_[GetSweepSpaceIndex(space)].empty()) is_done = false; 171 }); 172 return is_done; 173 } 174 175 void SweepSpaceFromTask(AllocationSpace identity); 176 177 // Sweeps incrementally one page from the given space. Returns true if 178 // there are no more pages to sweep in the given space. 179 bool SweepSpaceIncrementallyFromTask(AllocationSpace identity); 180 181 void AbortAndWaitForTasks(); 182 183 Page* GetSweepingPageSafe(AllocationSpace space); 184 185 void PrepareToBeSweptPage(AllocationSpace space, Page* page); 186 187 void MakeIterable(Page* page); 188 IsValidIterabilitySpace(AllocationSpace space)189 bool IsValidIterabilitySpace(AllocationSpace space) { 190 return space == NEW_SPACE || space == RO_SPACE; 191 } 192 IsValidSweepingSpace(AllocationSpace space)193 static bool IsValidSweepingSpace(AllocationSpace space) { 194 return space >= FIRST_GROWABLE_PAGED_SPACE && 195 space <= LAST_GROWABLE_PAGED_SPACE; 196 } 197 GetSweepSpaceIndex(AllocationSpace space)198 static int GetSweepSpaceIndex(AllocationSpace space) { 199 DCHECK(IsValidSweepingSpace(space)); 200 return space - FIRST_GROWABLE_PAGED_SPACE; 201 } 202 203 Heap* const heap_; 204 MajorNonAtomicMarkingState* marking_state_; 205 int num_tasks_; 206 CancelableTaskManager::Id task_ids_[kNumberOfSweepingSpaces]; 207 base::Semaphore pending_sweeper_tasks_semaphore_; 208 base::Mutex mutex_; 209 SweptList swept_list_[kNumberOfSweepingSpaces]; 210 SweepingList sweeping_list_[kNumberOfSweepingSpaces]; 211 bool incremental_sweeper_pending_; 212 // Main thread can finalize sweeping, while background threads allocation slow 213 // path checks this flag to see whether it could support concurrent sweeping. 214 std::atomic<bool> sweeping_in_progress_; 215 // Counter is actively maintained by the concurrent tasks to avoid querying 216 // the semaphore for maintaining a task counter on the main thread. 217 std::atomic<intptr_t> num_sweeping_tasks_; 218 // Used by PauseOrCompleteScope to signal early bailout to tasks. 219 std::atomic<bool> stop_sweeper_tasks_; 220 221 // Pages that are only made iterable but have their free lists ignored. 222 IterabilityList iterability_list_; 223 CancelableTaskManager::Id iterability_task_id_; 224 base::Semaphore iterability_task_semaphore_; 225 bool iterability_in_progress_; 226 bool iterability_task_started_; 227 bool should_reduce_memory_; 228 }; 229 230 } // namespace internal 231 } // namespace v8 232 233 #endif // V8_HEAP_SWEEPER_H_ 234