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_REMEMBERED_SET_H 6 #define V8_REMEMBERED_SET_H 7 8 #include "src/assembler.h" 9 #include "src/heap/heap.h" 10 #include "src/heap/slot-set.h" 11 #include "src/heap/spaces.h" 12 13 namespace v8 { 14 namespace internal { 15 16 enum PointerDirection { OLD_TO_OLD, OLD_TO_NEW }; 17 18 // TODO(ulan): Investigate performance of de-templatizing this class. 19 template <PointerDirection direction> 20 class RememberedSet : public AllStatic { 21 public: 22 // Given a page and a slot in that page, this function adds the slot to the 23 // remembered set. 24 static void Insert(MemoryChunk* chunk, Address slot_addr) { 25 DCHECK(chunk->Contains(slot_addr)); 26 SlotSet* slot_set = GetSlotSet(chunk); 27 if (slot_set == nullptr) { 28 slot_set = AllocateSlotSet(chunk); 29 } 30 uintptr_t offset = slot_addr - chunk->address(); 31 slot_set[offset / Page::kPageSize].Insert(offset % Page::kPageSize); 32 } 33 34 // Given a page and a slot in that page, this function returns true if 35 // the remembered set contains the slot. 36 static bool Contains(MemoryChunk* chunk, Address slot_addr) { 37 DCHECK(chunk->Contains(slot_addr)); 38 SlotSet* slot_set = GetSlotSet(chunk); 39 if (slot_set == nullptr) { 40 return false; 41 } 42 uintptr_t offset = slot_addr - chunk->address(); 43 return slot_set[offset / Page::kPageSize].Contains(offset % 44 Page::kPageSize); 45 } 46 47 // Given a page and a slot in that page, this function removes the slot from 48 // the remembered set. 49 // If the slot was never added, then the function does nothing. 50 static void Remove(MemoryChunk* chunk, Address slot_addr) { 51 DCHECK(chunk->Contains(slot_addr)); 52 SlotSet* slot_set = GetSlotSet(chunk); 53 if (slot_set != nullptr) { 54 uintptr_t offset = slot_addr - chunk->address(); 55 slot_set[offset / Page::kPageSize].Remove(offset % Page::kPageSize); 56 } 57 } 58 59 // Given a page and a range of slots in that page, this function removes the 60 // slots from the remembered set. 61 static void RemoveRange(MemoryChunk* chunk, Address start, Address end, 62 SlotSet::EmptyBucketMode mode) { 63 SlotSet* slot_set = GetSlotSet(chunk); 64 if (slot_set != nullptr) { 65 uintptr_t start_offset = start - chunk->address(); 66 uintptr_t end_offset = end - chunk->address(); 67 DCHECK_LT(start_offset, end_offset); 68 if (end_offset < static_cast<uintptr_t>(Page::kPageSize)) { 69 slot_set->RemoveRange(static_cast<int>(start_offset), 70 static_cast<int>(end_offset), mode); 71 } else { 72 // The large page has multiple slot sets. 73 // Compute slot set indicies for the range [start_offset, end_offset). 74 int start_chunk = static_cast<int>(start_offset / Page::kPageSize); 75 int end_chunk = static_cast<int>((end_offset - 1) / Page::kPageSize); 76 int offset_in_start_chunk = 77 static_cast<int>(start_offset % Page::kPageSize); 78 // Note that using end_offset % Page::kPageSize would be incorrect 79 // because end_offset is one beyond the last slot to clear. 80 int offset_in_end_chunk = static_cast<int>( 81 end_offset - static_cast<uintptr_t>(end_chunk) * Page::kPageSize); 82 if (start_chunk == end_chunk) { 83 slot_set[start_chunk].RemoveRange(offset_in_start_chunk, 84 offset_in_end_chunk, mode); 85 } else { 86 // Clear all slots from start_offset to the end of first chunk. 87 slot_set[start_chunk].RemoveRange(offset_in_start_chunk, 88 Page::kPageSize, mode); 89 // Clear all slots in intermediate chunks. 90 for (int i = start_chunk + 1; i < end_chunk; i++) { 91 slot_set[i].RemoveRange(0, Page::kPageSize, mode); 92 } 93 // Clear slots from the beginning of the last page to end_offset. 94 slot_set[end_chunk].RemoveRange(0, offset_in_end_chunk, mode); 95 } 96 } 97 } 98 } 99 100 // Iterates and filters the remembered set with the given callback. 101 // The callback should take (Address slot) and return SlotCallbackResult. 102 template <typename Callback> 103 static void Iterate(Heap* heap, Callback callback) { 104 IterateMemoryChunks( 105 heap, [callback](MemoryChunk* chunk) { Iterate(chunk, callback); }); 106 } 107 108 // Iterates over all memory chunks that contains non-empty slot sets. 109 // The callback should take (MemoryChunk* chunk) and return void. 110 template <typename Callback> 111 static void IterateMemoryChunks(Heap* heap, Callback callback) { 112 MemoryChunkIterator it(heap); 113 MemoryChunk* chunk; 114 while ((chunk = it.next()) != nullptr) { 115 SlotSet* slots = GetSlotSet(chunk); 116 TypedSlotSet* typed_slots = GetTypedSlotSet(chunk); 117 if (slots != nullptr || typed_slots != nullptr) { 118 callback(chunk); 119 } 120 } 121 } 122 123 // Iterates and filters the remembered set in the given memory chunk with 124 // the given callback. The callback should take (Address slot) and return 125 // SlotCallbackResult. 126 template <typename Callback> 127 static void Iterate(MemoryChunk* chunk, Callback callback) { 128 SlotSet* slots = GetSlotSet(chunk); 129 if (slots != nullptr) { 130 size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize; 131 int new_count = 0; 132 for (size_t page = 0; page < pages; page++) { 133 new_count += 134 slots[page].Iterate(callback, SlotSet::PREFREE_EMPTY_BUCKETS); 135 } 136 // Only old-to-old slot sets are released eagerly. Old-new-slot sets are 137 // released by the sweeper threads. 138 if (direction == OLD_TO_OLD && new_count == 0) { 139 chunk->ReleaseOldToOldSlots(); 140 } 141 } 142 } 143 144 // Given a page and a typed slot in that page, this function adds the slot 145 // to the remembered set. 146 static void InsertTyped(Page* page, Address host_addr, SlotType slot_type, 147 Address slot_addr) { 148 TypedSlotSet* slot_set = GetTypedSlotSet(page); 149 if (slot_set == nullptr) { 150 AllocateTypedSlotSet(page); 151 slot_set = GetTypedSlotSet(page); 152 } 153 if (host_addr == nullptr) { 154 host_addr = page->address(); 155 } 156 uintptr_t offset = slot_addr - page->address(); 157 uintptr_t host_offset = host_addr - page->address(); 158 DCHECK_LT(offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset)); 159 DCHECK_LT(host_offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset)); 160 slot_set->Insert(slot_type, static_cast<uint32_t>(host_offset), 161 static_cast<uint32_t>(offset)); 162 } 163 164 // Given a page and a range of typed slots in that page, this function removes 165 // the slots from the remembered set. 166 static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) { 167 TypedSlotSet* slots = GetTypedSlotSet(page); 168 if (slots != nullptr) { 169 slots->Iterate( 170 [start, end](SlotType slot_type, Address host_addr, 171 Address slot_addr) { 172 return start <= slot_addr && slot_addr < end ? REMOVE_SLOT 173 : KEEP_SLOT; 174 }, 175 TypedSlotSet::PREFREE_EMPTY_CHUNKS); 176 } 177 } 178 179 // Iterates and filters the remembered set with the given callback. 180 // The callback should take (SlotType slot_type, SlotAddress slot) and return 181 // SlotCallbackResult. 182 template <typename Callback> 183 static void IterateTyped(Heap* heap, Callback callback) { 184 IterateMemoryChunks(heap, [callback](MemoryChunk* chunk) { 185 IterateTyped(chunk, callback); 186 }); 187 } 188 189 // Iterates and filters typed old to old pointers in the given memory chunk 190 // with the given callback. The callback should take (SlotType slot_type, 191 // Address slot_addr) and return SlotCallbackResult. 192 template <typename Callback> 193 static void IterateTyped(MemoryChunk* chunk, Callback callback) { 194 TypedSlotSet* slots = GetTypedSlotSet(chunk); 195 if (slots != nullptr) { 196 int new_count = slots->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS); 197 if (new_count == 0) { 198 ReleaseTypedSlotSet(chunk); 199 } 200 } 201 } 202 203 // Clear all old to old slots from the remembered set. 204 static void ClearAll(Heap* heap) { 205 STATIC_ASSERT(direction == OLD_TO_OLD); 206 MemoryChunkIterator it(heap); 207 MemoryChunk* chunk; 208 while ((chunk = it.next()) != nullptr) { 209 chunk->ReleaseOldToOldSlots(); 210 chunk->ReleaseTypedOldToOldSlots(); 211 } 212 } 213 214 // Eliminates all stale slots from the remembered set, i.e. 215 // slots that are not part of live objects anymore. This method must be 216 // called after marking, when the whole transitive closure is known and 217 // must be called before sweeping when mark bits are still intact. 218 static void ClearInvalidTypedSlots(Heap* heap, MemoryChunk* chunk); 219 220 private: 221 static SlotSet* GetSlotSet(MemoryChunk* chunk) { 222 if (direction == OLD_TO_OLD) { 223 return chunk->old_to_old_slots(); 224 } else { 225 return chunk->old_to_new_slots(); 226 } 227 } 228 229 static TypedSlotSet* GetTypedSlotSet(MemoryChunk* chunk) { 230 if (direction == OLD_TO_OLD) { 231 return chunk->typed_old_to_old_slots(); 232 } else { 233 return chunk->typed_old_to_new_slots(); 234 } 235 } 236 237 static void ReleaseTypedSlotSet(MemoryChunk* chunk) { 238 if (direction == OLD_TO_OLD) { 239 chunk->ReleaseTypedOldToOldSlots(); 240 } 241 } 242 243 static SlotSet* AllocateSlotSet(MemoryChunk* chunk) { 244 if (direction == OLD_TO_OLD) { 245 chunk->AllocateOldToOldSlots(); 246 return chunk->old_to_old_slots(); 247 } else { 248 chunk->AllocateOldToNewSlots(); 249 return chunk->old_to_new_slots(); 250 } 251 } 252 253 static TypedSlotSet* AllocateTypedSlotSet(MemoryChunk* chunk) { 254 if (direction == OLD_TO_OLD) { 255 chunk->AllocateTypedOldToOldSlots(); 256 return chunk->typed_old_to_old_slots(); 257 } else { 258 chunk->AllocateTypedOldToNewSlots(); 259 return chunk->typed_old_to_new_slots(); 260 } 261 } 262 263 static bool IsValidSlot(Heap* heap, MemoryChunk* chunk, Object** slot); 264 }; 265 266 class UpdateTypedSlotHelper { 267 public: 268 // Updates a cell slot using an untyped slot callback. 269 // The callback accepts (Heap*, Object**) and returns SlotCallbackResult. 270 template <typename Callback> 271 static SlotCallbackResult UpdateCell(RelocInfo* rinfo, Callback callback) { 272 DCHECK(rinfo->rmode() == RelocInfo::CELL); 273 Object* cell = rinfo->target_cell(); 274 Object* old_cell = cell; 275 SlotCallbackResult result = callback(&cell); 276 if (cell != old_cell) { 277 rinfo->set_target_cell(reinterpret_cast<Cell*>(cell)); 278 } 279 return result; 280 } 281 282 // Updates a code entry slot using an untyped slot callback. 283 // The callback accepts (Heap*, Object**) and returns SlotCallbackResult. 284 template <typename Callback> 285 static SlotCallbackResult UpdateCodeEntry(Address entry_address, 286 Callback callback) { 287 Object* code = Code::GetObjectFromEntryAddress(entry_address); 288 Object* old_code = code; 289 SlotCallbackResult result = callback(&code); 290 if (code != old_code) { 291 Memory::Address_at(entry_address) = 292 reinterpret_cast<Code*>(code)->entry(); 293 } 294 return result; 295 } 296 297 // Updates a code target slot using an untyped slot callback. 298 // The callback accepts (Heap*, Object**) and returns SlotCallbackResult. 299 template <typename Callback> 300 static SlotCallbackResult UpdateCodeTarget(RelocInfo* rinfo, 301 Callback callback) { 302 DCHECK(RelocInfo::IsCodeTarget(rinfo->rmode())); 303 Object* target = Code::GetCodeFromTargetAddress(rinfo->target_address()); 304 Object* old_target = target; 305 SlotCallbackResult result = callback(&target); 306 if (target != old_target) { 307 rinfo->set_target_address(Code::cast(target)->instruction_start()); 308 } 309 return result; 310 } 311 312 // Updates an embedded pointer slot using an untyped slot callback. 313 // The callback accepts (Heap*, Object**) and returns SlotCallbackResult. 314 template <typename Callback> 315 static SlotCallbackResult UpdateEmbeddedPointer(RelocInfo* rinfo, 316 Callback callback) { 317 DCHECK(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT); 318 Object* target = rinfo->target_object(); 319 Object* old_target = target; 320 SlotCallbackResult result = callback(&target); 321 if (target != old_target) { 322 rinfo->set_target_object(target); 323 } 324 return result; 325 } 326 327 // Updates a debug target slot using an untyped slot callback. 328 // The callback accepts (Heap*, Object**) and returns SlotCallbackResult. 329 template <typename Callback> 330 static SlotCallbackResult UpdateDebugTarget(RelocInfo* rinfo, 331 Callback callback) { 332 DCHECK(RelocInfo::IsDebugBreakSlot(rinfo->rmode()) && 333 rinfo->IsPatchedDebugBreakSlotSequence()); 334 Object* target = 335 Code::GetCodeFromTargetAddress(rinfo->debug_call_address()); 336 SlotCallbackResult result = callback(&target); 337 rinfo->set_debug_call_address(Code::cast(target)->instruction_start()); 338 return result; 339 } 340 341 // Updates a typed slot using an untyped slot callback. 342 // The callback accepts (Heap*, Object**) and returns SlotCallbackResult. 343 template <typename Callback> 344 static SlotCallbackResult UpdateTypedSlot(Isolate* isolate, 345 SlotType slot_type, Address addr, 346 Callback callback) { 347 switch (slot_type) { 348 case CODE_TARGET_SLOT: { 349 RelocInfo rinfo(isolate, addr, RelocInfo::CODE_TARGET, 0, NULL); 350 return UpdateCodeTarget(&rinfo, callback); 351 } 352 case CELL_TARGET_SLOT: { 353 RelocInfo rinfo(isolate, addr, RelocInfo::CELL, 0, NULL); 354 return UpdateCell(&rinfo, callback); 355 } 356 case CODE_ENTRY_SLOT: { 357 return UpdateCodeEntry(addr, callback); 358 } 359 case DEBUG_TARGET_SLOT: { 360 RelocInfo rinfo(isolate, addr, RelocInfo::DEBUG_BREAK_SLOT_AT_POSITION, 361 0, NULL); 362 if (rinfo.IsPatchedDebugBreakSlotSequence()) { 363 return UpdateDebugTarget(&rinfo, callback); 364 } 365 return REMOVE_SLOT; 366 } 367 case EMBEDDED_OBJECT_SLOT: { 368 RelocInfo rinfo(isolate, addr, RelocInfo::EMBEDDED_OBJECT, 0, NULL); 369 return UpdateEmbeddedPointer(&rinfo, callback); 370 } 371 case OBJECT_SLOT: { 372 return callback(reinterpret_cast<Object**>(addr)); 373 } 374 case CLEARED_SLOT: 375 break; 376 } 377 UNREACHABLE(); 378 return REMOVE_SLOT; 379 } 380 }; 381 382 inline SlotType SlotTypeForRelocInfoMode(RelocInfo::Mode rmode) { 383 if (RelocInfo::IsCodeTarget(rmode)) { 384 return CODE_TARGET_SLOT; 385 } else if (RelocInfo::IsCell(rmode)) { 386 return CELL_TARGET_SLOT; 387 } else if (RelocInfo::IsEmbeddedObject(rmode)) { 388 return EMBEDDED_OBJECT_SLOT; 389 } else if (RelocInfo::IsDebugBreakSlot(rmode)) { 390 return DEBUG_TARGET_SLOT; 391 } 392 UNREACHABLE(); 393 return CLEARED_SLOT; 394 } 395 396 } // namespace internal 397 } // namespace v8 398 399 #endif // V8_REMEMBERED_SET_H 400