OLD | NEW |
(Empty) | |
| 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_SEQUENTIAL_MARKING_DEQUE_ |
| 6 #define V8_HEAP_SEQUENTIAL_MARKING_DEQUE_ |
| 7 |
| 8 #include <deque> |
| 9 |
| 10 #include "src/base/platform/mutex.h" |
| 11 #include "src/base/platform/platform.h" |
| 12 #include "src/cancelable-task.h" |
| 13 |
| 14 namespace v8 { |
| 15 namespace internal { |
| 16 |
| 17 class Heap; |
| 18 class Isolate; |
| 19 class HeapObject; |
| 20 |
| 21 // ---------------------------------------------------------------------------- |
| 22 // Marking deque for tracing live objects. |
| 23 class SequentialMarkingDeque { |
| 24 public: |
| 25 explicit SequentialMarkingDeque(Heap* heap) |
| 26 : backing_store_(nullptr), |
| 27 backing_store_committed_size_(0), |
| 28 array_(nullptr), |
| 29 top_(0), |
| 30 bottom_(0), |
| 31 mask_(0), |
| 32 overflowed_(false), |
| 33 in_use_(false), |
| 34 uncommit_task_pending_(false), |
| 35 heap_(heap) {} |
| 36 |
| 37 void SetUp(); |
| 38 void TearDown(); |
| 39 |
| 40 // Ensures that the marking deque is committed and will stay committed until |
| 41 // StopUsing() is called. |
| 42 void StartUsing(); |
| 43 void StopUsing(); |
| 44 void Clear(); |
| 45 |
| 46 inline bool IsFull() { return ((top_ + 1) & mask_) == bottom_; } |
| 47 |
| 48 inline bool IsEmpty() { return top_ == bottom_; } |
| 49 |
| 50 bool overflowed() const { return overflowed_; } |
| 51 |
| 52 void ClearOverflowed() { overflowed_ = false; } |
| 53 |
| 54 void SetOverflowed() { overflowed_ = true; } |
| 55 |
| 56 // Push the object on the marking stack if there is room, otherwise mark the |
| 57 // deque as overflowed and wait for a rescan of the heap. |
| 58 INLINE(bool Push(HeapObject* object)) { |
| 59 if (IsFull()) { |
| 60 SetOverflowed(); |
| 61 return false; |
| 62 } else { |
| 63 array_[top_] = object; |
| 64 top_ = ((top_ + 1) & mask_); |
| 65 return true; |
| 66 } |
| 67 } |
| 68 |
| 69 INLINE(HeapObject* Pop()) { |
| 70 DCHECK(!IsEmpty()); |
| 71 top_ = ((top_ - 1) & mask_); |
| 72 HeapObject* object = array_[top_]; |
| 73 return object; |
| 74 } |
| 75 |
| 76 // Unshift the object into the marking stack if there is room, otherwise mark |
| 77 // the deque as overflowed and wait for a rescan of the heap. |
| 78 INLINE(bool Unshift(HeapObject* object)) { |
| 79 if (IsFull()) { |
| 80 SetOverflowed(); |
| 81 return false; |
| 82 } else { |
| 83 bottom_ = ((bottom_ - 1) & mask_); |
| 84 array_[bottom_] = object; |
| 85 return true; |
| 86 } |
| 87 } |
| 88 |
| 89 template <typename Callback> |
| 90 void Iterate(Callback callback) { |
| 91 int i = bottom_; |
| 92 while (i != top_) { |
| 93 callback(array_[i]); |
| 94 i = (i + 1) & mask_; |
| 95 } |
| 96 } |
| 97 |
| 98 HeapObject** array() { return array_; } |
| 99 int bottom() { return bottom_; } |
| 100 int top() { return top_; } |
| 101 int mask() { return mask_; } |
| 102 void set_top(int top) { top_ = top; } |
| 103 |
| 104 private: |
| 105 // This task uncommits the marking_deque backing store if |
| 106 // markin_deque->in_use_ is false. |
| 107 class UncommitTask : public CancelableTask { |
| 108 public: |
| 109 explicit UncommitTask(Isolate* isolate, |
| 110 SequentialMarkingDeque* marking_deque) |
| 111 : CancelableTask(isolate), marking_deque_(marking_deque) {} |
| 112 |
| 113 private: |
| 114 // CancelableTask override. |
| 115 void RunInternal() override { |
| 116 base::LockGuard<base::Mutex> guard(&marking_deque_->mutex_); |
| 117 if (!marking_deque_->in_use_) { |
| 118 marking_deque_->Uncommit(); |
| 119 } |
| 120 marking_deque_->uncommit_task_pending_ = false; |
| 121 } |
| 122 |
| 123 SequentialMarkingDeque* marking_deque_; |
| 124 DISALLOW_COPY_AND_ASSIGN(UncommitTask); |
| 125 }; |
| 126 |
| 127 static const size_t kMaxSize = 4 * MB; |
| 128 static const size_t kMinSize = 256 * KB; |
| 129 |
| 130 // Must be called with mutex lock. |
| 131 void EnsureCommitted(); |
| 132 |
| 133 // Must be called with mutex lock. |
| 134 void Uncommit(); |
| 135 |
| 136 // Must be called with mutex lock. |
| 137 void StartUncommitTask(); |
| 138 |
| 139 base::Mutex mutex_; |
| 140 |
| 141 base::VirtualMemory* backing_store_; |
| 142 size_t backing_store_committed_size_; |
| 143 HeapObject** array_; |
| 144 // array_[(top - 1) & mask_] is the top element in the deque. The Deque is |
| 145 // empty when top_ == bottom_. It is full when top_ + 1 == bottom |
| 146 // (mod mask + 1). |
| 147 int top_; |
| 148 int bottom_; |
| 149 int mask_; |
| 150 bool overflowed_; |
| 151 // in_use_ == true after taking mutex lock implies that the marking deque is |
| 152 // committed and will stay committed at least until in_use_ == false. |
| 153 bool in_use_; |
| 154 bool uncommit_task_pending_; |
| 155 Heap* heap_; |
| 156 |
| 157 DISALLOW_COPY_AND_ASSIGN(SequentialMarkingDeque); |
| 158 }; |
| 159 |
| 160 } // namespace internal |
| 161 } // namespace v8 |
| 162 |
| 163 #endif // V8_SEQUENTIAL_MARKING_DEQUE_ |
OLD | NEW |