• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2012 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_MARK_COMPACT_INL_H_
6 #define V8_HEAP_MARK_COMPACT_INL_H_
7 
8 #include "src/base/bits.h"
9 #include "src/codegen/assembler-inl.h"
10 #include "src/heap/heap-inl.h"
11 #include "src/heap/incremental-marking.h"
12 #include "src/heap/mark-compact.h"
13 #include "src/heap/marking-worklist-inl.h"
14 #include "src/heap/marking-worklist.h"
15 #include "src/heap/objects-visiting-inl.h"
16 #include "src/heap/remembered-set-inl.h"
17 #include "src/objects/js-collection-inl.h"
18 #include "src/objects/js-weak-refs-inl.h"
19 #include "src/objects/slots-inl.h"
20 #include "src/objects/transitions.h"
21 
22 namespace v8 {
23 namespace internal {
24 
MarkObject(HeapObject host,HeapObject obj)25 void MarkCompactCollector::MarkObject(HeapObject host, HeapObject obj) {
26   if (marking_state()->WhiteToGrey(obj)) {
27     local_marking_worklists()->Push(obj);
28     if (V8_UNLIKELY(FLAG_track_retaining_path)) {
29       heap_->AddRetainer(host, obj);
30     }
31   }
32 }
33 
MarkRootObject(Root root,HeapObject obj)34 void MarkCompactCollector::MarkRootObject(Root root, HeapObject obj) {
35   if (marking_state()->WhiteToGrey(obj)) {
36     local_marking_worklists()->Push(obj);
37     if (V8_UNLIKELY(FLAG_track_retaining_path)) {
38       heap_->AddRetainingRoot(root, obj);
39     }
40   }
41 }
42 
MarkRootObject(HeapObject obj)43 void MinorMarkCompactCollector::MarkRootObject(HeapObject obj) {
44   if (Heap::InYoungGeneration(obj) &&
45       non_atomic_marking_state_.WhiteToGrey(obj)) {
46     main_thread_worklist_local_.Push(obj);
47   }
48 }
49 
MarkExternallyReferencedObject(HeapObject obj)50 void MarkCompactCollector::MarkExternallyReferencedObject(HeapObject obj) {
51   if (marking_state()->WhiteToGrey(obj)) {
52     local_marking_worklists()->Push(obj);
53     if (V8_UNLIKELY(FLAG_track_retaining_path)) {
54       heap_->AddRetainingRoot(Root::kWrapperTracing, obj);
55     }
56   }
57 }
58 
RecordSlot(HeapObject object,ObjectSlot slot,HeapObject target)59 void MarkCompactCollector::RecordSlot(HeapObject object, ObjectSlot slot,
60                                       HeapObject target) {
61   RecordSlot(object, HeapObjectSlot(slot), target);
62 }
63 
RecordSlot(HeapObject object,HeapObjectSlot slot,HeapObject target)64 void MarkCompactCollector::RecordSlot(HeapObject object, HeapObjectSlot slot,
65                                       HeapObject target) {
66   MemoryChunk* source_page = MemoryChunk::FromHeapObject(object);
67   if (!source_page->ShouldSkipEvacuationSlotRecording()) {
68     RecordSlot(source_page, slot, target);
69   }
70 }
71 
RecordSlot(MemoryChunk * source_page,HeapObjectSlot slot,HeapObject target)72 void MarkCompactCollector::RecordSlot(MemoryChunk* source_page,
73                                       HeapObjectSlot slot, HeapObject target) {
74   BasicMemoryChunk* target_page = BasicMemoryChunk::FromHeapObject(target);
75   if (target_page->IsEvacuationCandidate()) {
76     if (V8_EXTERNAL_CODE_SPACE_BOOL &&
77         target_page->IsFlagSet(MemoryChunk::IS_EXECUTABLE)) {
78       RememberedSet<OLD_TO_CODE>::Insert<AccessMode::ATOMIC>(source_page,
79                                                              slot.address());
80     } else {
81       RememberedSet<OLD_TO_OLD>::Insert<AccessMode::ATOMIC>(source_page,
82                                                             slot.address());
83     }
84   }
85 }
86 
AddTransitionArray(TransitionArray array)87 void MarkCompactCollector::AddTransitionArray(TransitionArray array) {
88   local_weak_objects()->transition_arrays_local.Push(array);
89 }
90 
91 template <typename MarkingState>
92 template <typename T, typename TBodyDescriptor>
VisitJSObjectSubclass(Map map,T object)93 int MainMarkingVisitor<MarkingState>::VisitJSObjectSubclass(Map map, T object) {
94   if (!this->ShouldVisit(object)) return 0;
95   this->VisitMapPointer(object);
96   int size = TBodyDescriptor::SizeOf(map, object);
97   TBodyDescriptor::IterateBody(map, object, size, this);
98   return size;
99 }
100 
101 template <typename MarkingState>
102 template <typename T>
VisitLeftTrimmableArray(Map map,T object)103 int MainMarkingVisitor<MarkingState>::VisitLeftTrimmableArray(Map map,
104                                                               T object) {
105   if (!this->ShouldVisit(object)) return 0;
106   int size = T::SizeFor(object.length());
107   this->VisitMapPointer(object);
108   T::BodyDescriptor::IterateBody(map, object, size, this);
109   return size;
110 }
111 
112 template <typename MarkingState>
113 template <typename TSlot>
RecordSlot(HeapObject object,TSlot slot,HeapObject target)114 void MainMarkingVisitor<MarkingState>::RecordSlot(HeapObject object, TSlot slot,
115                                                   HeapObject target) {
116   MarkCompactCollector::RecordSlot(object, slot, target);
117 }
118 
119 template <typename MarkingState>
RecordRelocSlot(Code host,RelocInfo * rinfo,HeapObject target)120 void MainMarkingVisitor<MarkingState>::RecordRelocSlot(Code host,
121                                                        RelocInfo* rinfo,
122                                                        HeapObject target) {
123   MarkCompactCollector::RecordRelocSlot(host, rinfo, target);
124 }
125 
126 template <LiveObjectIterationMode mode>
iterator(const MemoryChunk * chunk,Bitmap * bitmap,Address start)127 LiveObjectRange<mode>::iterator::iterator(const MemoryChunk* chunk,
128                                           Bitmap* bitmap, Address start)
129     : chunk_(chunk),
130       one_word_filler_map_(
131           ReadOnlyRoots(chunk->heap()).one_pointer_filler_map()),
132       two_word_filler_map_(
133           ReadOnlyRoots(chunk->heap()).two_pointer_filler_map()),
134       free_space_map_(ReadOnlyRoots(chunk->heap()).free_space_map()),
135       it_(chunk, bitmap) {
136   it_.Advance(Bitmap::IndexToCell(
137       Bitmap::CellAlignIndex(chunk_->AddressToMarkbitIndex(start))));
138   if (!it_.Done()) {
139     cell_base_ = it_.CurrentCellBase();
140     current_cell_ = *it_.CurrentCell();
141     AdvanceToNextValidObject();
142   }
143 }
144 
145 template <LiveObjectIterationMode mode>
146 typename LiveObjectRange<mode>::iterator& LiveObjectRange<mode>::iterator::
147 operator++() {
148   AdvanceToNextValidObject();
149   return *this;
150 }
151 
152 template <LiveObjectIterationMode mode>
153 typename LiveObjectRange<mode>::iterator LiveObjectRange<mode>::iterator::
154 operator++(int) {
155   iterator retval = *this;
156   ++(*this);
157   return retval;
158 }
159 
160 template <LiveObjectIterationMode mode>
AdvanceToNextValidObject()161 void LiveObjectRange<mode>::iterator::AdvanceToNextValidObject() {
162   PtrComprCageBase cage_base(chunk_->heap()->isolate());
163   while (!it_.Done()) {
164     HeapObject object;
165     int size = 0;
166     while (current_cell_ != 0) {
167       uint32_t trailing_zeros = base::bits::CountTrailingZeros(current_cell_);
168       Address addr = cell_base_ + trailing_zeros * kTaggedSize;
169 
170       // Clear the first bit of the found object..
171       current_cell_ &= ~(1u << trailing_zeros);
172 
173       uint32_t second_bit_index = 0;
174       if (trailing_zeros >= Bitmap::kBitIndexMask) {
175         second_bit_index = 0x1;
176         // The overlapping case; there has to exist a cell after the current
177         // cell.
178         // However, if there is a black area at the end of the page, and the
179         // last word is a one word filler, we are not allowed to advance. In
180         // that case we can return immediately.
181         if (!it_.Advance()) {
182           DCHECK(HeapObject::FromAddress(addr).map() == one_word_filler_map_);
183           current_object_ = HeapObject();
184           return;
185         }
186         cell_base_ = it_.CurrentCellBase();
187         current_cell_ = *it_.CurrentCell();
188       } else {
189         second_bit_index = 1u << (trailing_zeros + 1);
190       }
191 
192       Map map;
193       if (current_cell_ & second_bit_index) {
194         // We found a black object. If the black object is within a black area,
195         // make sure that we skip all set bits in the black area until the
196         // object ends.
197         HeapObject black_object = HeapObject::FromAddress(addr);
198         map = black_object.map(cage_base, kAcquireLoad);
199         // Map might be forwarded during GC.
200         DCHECK(MarkCompactCollector::IsMapOrForwardedMap(map));
201         size = black_object.SizeFromMap(map);
202         CHECK_LE(addr + size, chunk_->area_end());
203         Address end = addr + size - kTaggedSize;
204         // One word filler objects do not borrow the second mark bit. We have
205         // to jump over the advancing and clearing part.
206         // Note that we know that we are at a one word filler when
207         // object_start + object_size - kTaggedSize == object_start.
208         if (addr != end) {
209           DCHECK_EQ(chunk_, BasicMemoryChunk::FromAddress(end));
210           uint32_t end_mark_bit_index = chunk_->AddressToMarkbitIndex(end);
211           unsigned int end_cell_index =
212               end_mark_bit_index >> Bitmap::kBitsPerCellLog2;
213           MarkBit::CellType end_index_mask =
214               1u << Bitmap::IndexInCell(end_mark_bit_index);
215           if (it_.Advance(end_cell_index)) {
216             cell_base_ = it_.CurrentCellBase();
217             current_cell_ = *it_.CurrentCell();
218           }
219 
220           // Clear all bits in current_cell, including the end index.
221           current_cell_ &= ~(end_index_mask + end_index_mask - 1);
222         }
223 
224         if (mode == kBlackObjects || mode == kAllLiveObjects) {
225           object = black_object;
226         }
227       } else if ((mode == kGreyObjects || mode == kAllLiveObjects)) {
228         object = HeapObject::FromAddress(addr);
229         Object map_object = object.map(cage_base, kAcquireLoad);
230         CHECK(map_object.IsMap(cage_base));
231         map = Map::cast(map_object);
232         DCHECK(map.IsMap(cage_base));
233         size = object.SizeFromMap(map);
234         CHECK_LE(addr + size, chunk_->area_end());
235       }
236 
237       // We found a live object.
238       if (!object.is_null()) {
239         // Do not use IsFreeSpaceOrFiller() here. This may cause a data race for
240         // reading out the instance type when a new map concurrently is written
241         // into this object while iterating over the object.
242         if (map == one_word_filler_map_ || map == two_word_filler_map_ ||
243             map == free_space_map_) {
244           // There are two reasons why we can get black or grey fillers:
245           // 1) Black areas together with slack tracking may result in black one
246           // word filler objects.
247           // 2) Left trimming may leave black or grey fillers behind because we
248           // do not clear the old location of the object start.
249           // We filter these objects out in the iterator.
250           object = HeapObject();
251         } else {
252           break;
253         }
254       }
255     }
256 
257     if (current_cell_ == 0) {
258       if (it_.Advance()) {
259         cell_base_ = it_.CurrentCellBase();
260         current_cell_ = *it_.CurrentCell();
261       }
262     }
263     if (!object.is_null()) {
264       current_object_ = object;
265       current_size_ = size;
266       return;
267     }
268   }
269   current_object_ = HeapObject();
270 }
271 
272 template <LiveObjectIterationMode mode>
begin()273 typename LiveObjectRange<mode>::iterator LiveObjectRange<mode>::begin() {
274   return iterator(chunk_, bitmap_, start_);
275 }
276 
277 template <LiveObjectIterationMode mode>
end()278 typename LiveObjectRange<mode>::iterator LiveObjectRange<mode>::end() {
279   return iterator(chunk_, bitmap_, end_);
280 }
281 
isolate()282 Isolate* MarkCompactCollectorBase::isolate() { return heap()->isolate(); }
283 
284 }  // namespace internal
285 }  // namespace v8
286 
287 #endif  // V8_HEAP_MARK_COMPACT_INL_H_
288