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