Home | History | Annotate | Download | only in heap 
      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>
     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       : 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 
     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>
    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.
    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 
    163   bool IsValidIterabilitySpace(AllocationSpace space) {
    164     return space == NEW_SPACE || space == RO_SPACE;
    165   }
    166 
    167   static bool IsValidSweepingSpace(AllocationSpace space) {
    168     return space >= FIRST_GROWABLE_PAGED_SPACE &&
    169            space <= LAST_GROWABLE_PAGED_SPACE;
    170   }
    171 
    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   std::atomic<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