1 // Copyright 2016 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_REMEMBERED_SET_H_
6 #define V8_HEAP_REMEMBERED_SET_H_
7
8 #include <memory>
9
10 #include "src/base/bounds.h"
11 #include "src/base/memory.h"
12 #include "src/codegen/reloc-info.h"
13 #include "src/common/globals.h"
14 #include "src/heap/heap.h"
15 #include "src/heap/memory-chunk.h"
16 #include "src/heap/paged-spaces.h"
17 #include "src/heap/slot-set.h"
18 #include "src/heap/spaces.h"
19 #include "src/heap/worklist.h"
20
21 namespace v8 {
22 namespace internal {
23
24 enum RememberedSetIterationMode { SYNCHRONIZED, NON_SYNCHRONIZED };
25
26 class RememberedSetOperations {
27 public:
28 // Given a page and a slot in that page, this function adds the slot to the
29 // remembered set.
30 template <AccessMode access_mode>
Insert(SlotSet * slot_set,MemoryChunk * chunk,Address slot_addr)31 static void Insert(SlotSet* slot_set, MemoryChunk* chunk, Address slot_addr) {
32 DCHECK(chunk->Contains(slot_addr));
33 uintptr_t offset = slot_addr - chunk->address();
34 slot_set->Insert<access_mode>(offset);
35 }
36
37 template <typename Callback>
Iterate(SlotSet * slot_set,MemoryChunk * chunk,Callback callback,SlotSet::EmptyBucketMode mode)38 static int Iterate(SlotSet* slot_set, MemoryChunk* chunk, Callback callback,
39 SlotSet::EmptyBucketMode mode) {
40 int slots = 0;
41 if (slot_set != nullptr) {
42 slots += slot_set->Iterate(chunk->address(), 0, chunk->buckets(),
43 callback, mode);
44 }
45 return slots;
46 }
47
Remove(SlotSet * slot_set,MemoryChunk * chunk,Address slot_addr)48 static void Remove(SlotSet* slot_set, MemoryChunk* chunk, Address slot_addr) {
49 if (slot_set != nullptr) {
50 uintptr_t offset = slot_addr - chunk->address();
51 slot_set->Remove(offset);
52 }
53 }
54
RemoveRange(SlotSet * slot_set,MemoryChunk * chunk,Address start,Address end,SlotSet::EmptyBucketMode mode)55 static void RemoveRange(SlotSet* slot_set, MemoryChunk* chunk, Address start,
56 Address end, SlotSet::EmptyBucketMode mode) {
57 if (slot_set != nullptr) {
58 uintptr_t start_offset = start - chunk->address();
59 uintptr_t end_offset = end - chunk->address();
60 DCHECK_LT(start_offset, end_offset);
61 slot_set->RemoveRange(static_cast<int>(start_offset),
62 static_cast<int>(end_offset), chunk->buckets(),
63 mode);
64 }
65 }
66
CheckNoneInRange(SlotSet * slot_set,MemoryChunk * chunk,Address start,Address end)67 static void CheckNoneInRange(SlotSet* slot_set, MemoryChunk* chunk,
68 Address start, Address end) {
69 if (slot_set != nullptr) {
70 size_t start_bucket = SlotSet::BucketForSlot(start - chunk->address());
71 // Both 'end' and 'end_bucket' are exclusive limits, so do some index
72 // juggling to make sure we get the right bucket even if the end address
73 // is at the start of a bucket.
74 size_t end_bucket =
75 SlotSet::BucketForSlot(end - chunk->address() - kTaggedSize) + 1;
76 slot_set->Iterate(
77 chunk->address(), start_bucket, end_bucket,
78 [start, end](MaybeObjectSlot slot) {
79 CHECK(!base::IsInRange(slot.address(), start, end + 1));
80 return KEEP_SLOT;
81 },
82 SlotSet::KEEP_EMPTY_BUCKETS);
83 }
84 }
85 };
86
87 // TODO(ulan): Investigate performance of de-templatizing this class.
88 template <RememberedSetType type>
89 class RememberedSet : public AllStatic {
90 public:
91 // Given a page and a slot in that page, this function adds the slot to the
92 // remembered set.
93 template <AccessMode access_mode>
Insert(MemoryChunk * chunk,Address slot_addr)94 static void Insert(MemoryChunk* chunk, Address slot_addr) {
95 DCHECK(chunk->Contains(slot_addr));
96 SlotSet* slot_set = chunk->slot_set<type, access_mode>();
97 if (slot_set == nullptr) {
98 slot_set = chunk->AllocateSlotSet<type>();
99 }
100 RememberedSetOperations::Insert<access_mode>(slot_set, chunk, slot_addr);
101 }
102
103 // Given a page and a slot in that page, this function returns true if
104 // the remembered set contains the slot.
Contains(MemoryChunk * chunk,Address slot_addr)105 static bool Contains(MemoryChunk* chunk, Address slot_addr) {
106 DCHECK(chunk->Contains(slot_addr));
107 SlotSet* slot_set = chunk->slot_set<type>();
108 if (slot_set == nullptr) {
109 return false;
110 }
111 uintptr_t offset = slot_addr - chunk->address();
112 return slot_set->Contains(offset);
113 }
114
CheckNoneInRange(MemoryChunk * chunk,Address start,Address end)115 static void CheckNoneInRange(MemoryChunk* chunk, Address start, Address end) {
116 SlotSet* slot_set = chunk->slot_set<type>();
117 RememberedSetOperations::CheckNoneInRange(slot_set, chunk, start, end);
118 }
119
120 // Given a page and a slot in that page, this function removes the slot from
121 // the remembered set.
122 // If the slot was never added, then the function does nothing.
Remove(MemoryChunk * chunk,Address slot_addr)123 static void Remove(MemoryChunk* chunk, Address slot_addr) {
124 DCHECK(chunk->Contains(slot_addr));
125 SlotSet* slot_set = chunk->slot_set<type>();
126 RememberedSetOperations::Remove(slot_set, chunk, slot_addr);
127 }
128
129 // Given a page and a range of slots in that page, this function removes the
130 // slots from the remembered set.
RemoveRange(MemoryChunk * chunk,Address start,Address end,SlotSet::EmptyBucketMode mode)131 static void RemoveRange(MemoryChunk* chunk, Address start, Address end,
132 SlotSet::EmptyBucketMode mode) {
133 SlotSet* slot_set = chunk->slot_set<type>();
134 RememberedSetOperations::RemoveRange(slot_set, chunk, start, end, mode);
135 }
136
137 // Iterates and filters the remembered set with the given callback.
138 // The callback should take (Address slot) and return SlotCallbackResult.
139 template <typename Callback>
Iterate(Heap * heap,RememberedSetIterationMode mode,Callback callback)140 static void Iterate(Heap* heap, RememberedSetIterationMode mode,
141 Callback callback) {
142 IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) {
143 if (mode == SYNCHRONIZED) chunk->mutex()->Lock();
144 Iterate(chunk, callback);
145 if (mode == SYNCHRONIZED) chunk->mutex()->Unlock();
146 });
147 }
148
149 // Iterates over all memory chunks that contains non-empty slot sets.
150 // The callback should take (MemoryChunk* chunk) and return void.
151 template <typename Callback>
IterateMemoryChunks(Heap * heap,Callback callback)152 static void IterateMemoryChunks(Heap* heap, Callback callback) {
153 OldGenerationMemoryChunkIterator it(heap);
154 MemoryChunk* chunk;
155 while ((chunk = it.next()) != nullptr) {
156 SlotSet* slot_set = chunk->slot_set<type>();
157 SlotSet* sweeping_slot_set =
158 type == OLD_TO_NEW ? chunk->sweeping_slot_set() : nullptr;
159 TypedSlotSet* typed_slot_set = chunk->typed_slot_set<type>();
160 if (slot_set != nullptr || sweeping_slot_set != nullptr ||
161 typed_slot_set != nullptr ||
162 chunk->invalidated_slots<type>() != nullptr) {
163 callback(chunk);
164 }
165 }
166 }
167
168 // Iterates and filters the remembered set in the given memory chunk with
169 // the given callback. The callback should take (Address slot) and return
170 // SlotCallbackResult.
171 //
172 // Notice that |mode| can only be of FREE* or PREFREE* if there are no other
173 // threads concurrently inserting slots.
174 template <typename Callback>
Iterate(MemoryChunk * chunk,Callback callback,SlotSet::EmptyBucketMode mode)175 static int Iterate(MemoryChunk* chunk, Callback callback,
176 SlotSet::EmptyBucketMode mode) {
177 SlotSet* slot_set = chunk->slot_set<type>();
178 return RememberedSetOperations::Iterate(slot_set, chunk, callback, mode);
179 }
180
181 template <typename Callback>
IterateAndTrackEmptyBuckets(MemoryChunk * chunk,Callback callback,Worklist<MemoryChunk *,64>::View empty_chunks)182 static int IterateAndTrackEmptyBuckets(
183 MemoryChunk* chunk, Callback callback,
184 Worklist<MemoryChunk*, 64>::View empty_chunks) {
185 SlotSet* slot_set = chunk->slot_set<type>();
186 int slots = 0;
187 if (slot_set != nullptr) {
188 PossiblyEmptyBuckets* possibly_empty_buckets =
189 chunk->possibly_empty_buckets();
190 slots += slot_set->IterateAndTrackEmptyBuckets(chunk->address(), 0,
191 chunk->buckets(), callback,
192 possibly_empty_buckets);
193 if (!possibly_empty_buckets->IsEmpty()) empty_chunks.Push(chunk);
194 }
195 return slots;
196 }
197
FreeEmptyBuckets(MemoryChunk * chunk)198 static void FreeEmptyBuckets(MemoryChunk* chunk) {
199 DCHECK(type == OLD_TO_NEW);
200 SlotSet* slot_set = chunk->slot_set<type>();
201 if (slot_set != nullptr && slot_set->FreeEmptyBuckets(chunk->buckets())) {
202 chunk->ReleaseSlotSet<type>();
203 }
204 }
205
CheckPossiblyEmptyBuckets(MemoryChunk * chunk)206 static bool CheckPossiblyEmptyBuckets(MemoryChunk* chunk) {
207 DCHECK(type == OLD_TO_NEW);
208 SlotSet* slot_set = chunk->slot_set<type, AccessMode::NON_ATOMIC>();
209 if (slot_set != nullptr &&
210 slot_set->CheckPossiblyEmptyBuckets(chunk->buckets(),
211 chunk->possibly_empty_buckets())) {
212 chunk->ReleaseSlotSet<type>();
213 return true;
214 }
215
216 return false;
217 }
218
219 // Given a page and a typed slot in that page, this function adds the slot
220 // to the remembered set.
InsertTyped(MemoryChunk * memory_chunk,SlotType slot_type,uint32_t offset)221 static void InsertTyped(MemoryChunk* memory_chunk, SlotType slot_type,
222 uint32_t offset) {
223 TypedSlotSet* slot_set = memory_chunk->typed_slot_set<type>();
224 if (slot_set == nullptr) {
225 slot_set = memory_chunk->AllocateTypedSlotSet<type>();
226 }
227 slot_set->Insert(slot_type, offset);
228 }
229
MergeTyped(MemoryChunk * page,std::unique_ptr<TypedSlots> other)230 static void MergeTyped(MemoryChunk* page, std::unique_ptr<TypedSlots> other) {
231 TypedSlotSet* slot_set = page->typed_slot_set<type>();
232 if (slot_set == nullptr) {
233 slot_set = page->AllocateTypedSlotSet<type>();
234 }
235 slot_set->Merge(other.get());
236 }
237
238 // Given a page and a range of typed slots in that page, this function removes
239 // the slots from the remembered set.
RemoveRangeTyped(MemoryChunk * page,Address start,Address end)240 static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) {
241 TypedSlotSet* slot_set = page->typed_slot_set<type>();
242 if (slot_set != nullptr) {
243 slot_set->Iterate(
244 [=](SlotType slot_type, Address slot_addr) {
245 return start <= slot_addr && slot_addr < end ? REMOVE_SLOT
246 : KEEP_SLOT;
247 },
248 TypedSlotSet::FREE_EMPTY_CHUNKS);
249 }
250 }
251
252 // Iterates and filters the remembered set with the given callback.
253 // The callback should take (SlotType slot_type, Address addr) and return
254 // SlotCallbackResult.
255 template <typename Callback>
IterateTyped(Heap * heap,RememberedSetIterationMode mode,Callback callback)256 static void IterateTyped(Heap* heap, RememberedSetIterationMode mode,
257 Callback callback) {
258 IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) {
259 if (mode == SYNCHRONIZED) chunk->mutex()->Lock();
260 IterateTyped(chunk, callback);
261 if (mode == SYNCHRONIZED) chunk->mutex()->Unlock();
262 });
263 }
264
265 // Iterates and filters typed pointers in the given memory chunk with the
266 // given callback. The callback should take (SlotType slot_type, Address addr)
267 // and return SlotCallbackResult.
268 template <typename Callback>
IterateTyped(MemoryChunk * chunk,Callback callback)269 static void IterateTyped(MemoryChunk* chunk, Callback callback) {
270 TypedSlotSet* slot_set = chunk->typed_slot_set<type>();
271 if (slot_set != nullptr) {
272 int new_count =
273 slot_set->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS);
274 if (new_count == 0) {
275 chunk->ReleaseTypedSlotSet<type>();
276 }
277 }
278 }
279
280 // Clear all old to old slots from the remembered set.
ClearAll(Heap * heap)281 static void ClearAll(Heap* heap) {
282 STATIC_ASSERT(type == OLD_TO_OLD);
283 OldGenerationMemoryChunkIterator it(heap);
284 MemoryChunk* chunk;
285 while ((chunk = it.next()) != nullptr) {
286 chunk->ReleaseSlotSet<OLD_TO_OLD>();
287 chunk->ReleaseTypedSlotSet<OLD_TO_OLD>();
288 chunk->ReleaseInvalidatedSlots<OLD_TO_OLD>();
289 }
290 }
291 };
292
293 class UpdateTypedSlotHelper {
294 public:
295 // Updates a typed slot using an untyped slot callback where |addr| depending
296 // on slot type represents either address for respective RelocInfo or address
297 // of the uncompressed constant pool entry.
298 // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
299 template <typename Callback>
300 static SlotCallbackResult UpdateTypedSlot(Heap* heap, SlotType slot_type,
301 Address addr, Callback callback);
302
303 private:
304 // Updates a code entry slot using an untyped slot callback.
305 // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
306 template <typename Callback>
UpdateCodeEntry(Address entry_address,Callback callback)307 static SlotCallbackResult UpdateCodeEntry(Address entry_address,
308 Callback callback) {
309 Code code = Code::GetObjectFromEntryAddress(entry_address);
310 Code old_code = code;
311 SlotCallbackResult result = callback(FullMaybeObjectSlot(&code));
312 DCHECK(!HasWeakHeapObjectTag(code));
313 if (code != old_code) {
314 base::Memory<Address>(entry_address) = code.entry();
315 }
316 return result;
317 }
318
319 // Updates a code target slot using an untyped slot callback.
320 // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
321 template <typename Callback>
UpdateCodeTarget(RelocInfo * rinfo,Callback callback)322 static SlotCallbackResult UpdateCodeTarget(RelocInfo* rinfo,
323 Callback callback) {
324 DCHECK(RelocInfo::IsCodeTargetMode(rinfo->rmode()));
325 Code old_target = Code::GetCodeFromTargetAddress(rinfo->target_address());
326 Code new_target = old_target;
327 SlotCallbackResult result = callback(FullMaybeObjectSlot(&new_target));
328 DCHECK(!HasWeakHeapObjectTag(new_target));
329 if (new_target != old_target) {
330 rinfo->set_target_address(Code::cast(new_target).raw_instruction_start());
331 }
332 return result;
333 }
334
335 // Updates an embedded pointer slot using an untyped slot callback.
336 // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
337 template <typename Callback>
UpdateEmbeddedPointer(Heap * heap,RelocInfo * rinfo,Callback callback)338 static SlotCallbackResult UpdateEmbeddedPointer(Heap* heap, RelocInfo* rinfo,
339 Callback callback) {
340 DCHECK(RelocInfo::IsEmbeddedObjectMode(rinfo->rmode()));
341 HeapObject old_target = rinfo->target_object_no_host(heap->isolate());
342 HeapObject new_target = old_target;
343 SlotCallbackResult result = callback(FullMaybeObjectSlot(&new_target));
344 DCHECK(!HasWeakHeapObjectTag(new_target));
345 if (new_target != old_target) {
346 rinfo->set_target_object(heap, HeapObject::cast(new_target));
347 }
348 return result;
349 }
350 };
351
352 class RememberedSetSweeping {
353 public:
354 template <AccessMode access_mode>
Insert(MemoryChunk * chunk,Address slot_addr)355 static void Insert(MemoryChunk* chunk, Address slot_addr) {
356 DCHECK(chunk->Contains(slot_addr));
357 SlotSet* slot_set = chunk->sweeping_slot_set<access_mode>();
358 if (slot_set == nullptr) {
359 slot_set = chunk->AllocateSweepingSlotSet();
360 }
361 RememberedSetOperations::Insert<access_mode>(slot_set, chunk, slot_addr);
362 }
363
Remove(MemoryChunk * chunk,Address slot_addr)364 static void Remove(MemoryChunk* chunk, Address slot_addr) {
365 DCHECK(chunk->Contains(slot_addr));
366 SlotSet* slot_set = chunk->sweeping_slot_set<AccessMode::ATOMIC>();
367 RememberedSetOperations::Remove(slot_set, chunk, slot_addr);
368 }
369
370 // Given a page and a range of slots in that page, this function removes the
371 // slots from the remembered set.
RemoveRange(MemoryChunk * chunk,Address start,Address end,SlotSet::EmptyBucketMode mode)372 static void RemoveRange(MemoryChunk* chunk, Address start, Address end,
373 SlotSet::EmptyBucketMode mode) {
374 SlotSet* slot_set = chunk->sweeping_slot_set();
375 RememberedSetOperations::RemoveRange(slot_set, chunk, start, end, mode);
376 }
377
378 // Iterates and filters the remembered set in the given memory chunk with
379 // the given callback. The callback should take (Address slot) and return
380 // SlotCallbackResult.
381 //
382 // Notice that |mode| can only be of FREE* or PREFREE* if there are no other
383 // threads concurrently inserting slots.
384 template <typename Callback>
Iterate(MemoryChunk * chunk,Callback callback,SlotSet::EmptyBucketMode mode)385 static int Iterate(MemoryChunk* chunk, Callback callback,
386 SlotSet::EmptyBucketMode mode) {
387 SlotSet* slot_set = chunk->sweeping_slot_set();
388 return RememberedSetOperations::Iterate(slot_set, chunk, callback, mode);
389 }
390 };
391
SlotTypeForRelocInfoMode(RelocInfo::Mode rmode)392 inline SlotType SlotTypeForRelocInfoMode(RelocInfo::Mode rmode) {
393 if (RelocInfo::IsCodeTargetMode(rmode)) {
394 return CODE_TARGET_SLOT;
395 } else if (RelocInfo::IsFullEmbeddedObject(rmode)) {
396 return FULL_EMBEDDED_OBJECT_SLOT;
397 } else if (RelocInfo::IsCompressedEmbeddedObject(rmode)) {
398 return COMPRESSED_EMBEDDED_OBJECT_SLOT;
399 }
400 UNREACHABLE();
401 }
402
403 } // namespace internal
404 } // namespace v8
405
406 #endif // V8_HEAP_REMEMBERED_SET_H_
407