| OLD | NEW |
| 1 // Copyright 2016 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #ifndef V8_REMEMBERED_SET_H | 5 #ifndef V8_REMEMBERED_SET_H |
| 6 #define V8_REMEMBERED_SET_H | 6 #define V8_REMEMBERED_SET_H |
| 7 | 7 |
| 8 #include "src/assembler.h" | 8 #include "src/assembler.h" |
| 9 #include "src/heap/heap.h" | 9 #include "src/heap/heap.h" |
| 10 #include "src/heap/slot-set.h" | 10 #include "src/heap/slot-set.h" |
| 11 #include "src/heap/spaces.h" | 11 #include "src/heap/spaces.h" |
| 12 | 12 |
| 13 namespace v8 { | 13 namespace v8 { |
| 14 namespace internal { | 14 namespace internal { |
| 15 | 15 |
| 16 enum PointerDirection { OLD_TO_OLD, OLD_TO_NEW }; |
| 17 |
| 16 // TODO(ulan): Investigate performance of de-templatizing this class. | 18 // TODO(ulan): Investigate performance of de-templatizing this class. |
| 17 template <RememberedSetType type> | 19 template <PointerDirection direction> |
| 18 class RememberedSet : public AllStatic { | 20 class RememberedSet : public AllStatic { |
| 19 public: | 21 public: |
| 20 // Given a page and a slot in that page, this function adds the slot to the | 22 // Given a page and a slot in that page, this function adds the slot to the |
| 21 // remembered set. | 23 // remembered set. |
| 22 static void Insert(MemoryChunk* chunk, Address slot_addr) { | 24 static void Insert(MemoryChunk* chunk, Address slot_addr) { |
| 23 DCHECK(chunk->Contains(slot_addr)); | 25 DCHECK(chunk->Contains(slot_addr)); |
| 24 SlotSet* slot_set = chunk->slot_set<type>(); | 26 SlotSet* slot_set = GetSlotSet(chunk); |
| 25 if (slot_set == nullptr) { | 27 if (slot_set == nullptr) { |
| 26 slot_set = chunk->AllocateSlotSet<type>(); | 28 slot_set = AllocateSlotSet(chunk); |
| 27 } | 29 } |
| 28 uintptr_t offset = slot_addr - chunk->address(); | 30 uintptr_t offset = slot_addr - chunk->address(); |
| 29 slot_set[offset / Page::kPageSize].Insert(offset % Page::kPageSize); | 31 slot_set[offset / Page::kPageSize].Insert(offset % Page::kPageSize); |
| 30 } | 32 } |
| 31 | 33 |
| 32 // Given a page and a slot in that page, this function returns true if | 34 // Given a page and a slot in that page, this function returns true if |
| 33 // the remembered set contains the slot. | 35 // the remembered set contains the slot. |
| 34 static bool Contains(MemoryChunk* chunk, Address slot_addr) { | 36 static bool Contains(MemoryChunk* chunk, Address slot_addr) { |
| 35 DCHECK(chunk->Contains(slot_addr)); | 37 DCHECK(chunk->Contains(slot_addr)); |
| 36 SlotSet* slot_set = chunk->slot_set<type>(); | 38 SlotSet* slot_set = GetSlotSet(chunk); |
| 37 if (slot_set == nullptr) { | 39 if (slot_set == nullptr) { |
| 38 return false; | 40 return false; |
| 39 } | 41 } |
| 40 uintptr_t offset = slot_addr - chunk->address(); | 42 uintptr_t offset = slot_addr - chunk->address(); |
| 41 return slot_set[offset / Page::kPageSize].Contains(offset % | 43 return slot_set[offset / Page::kPageSize].Contains(offset % |
| 42 Page::kPageSize); | 44 Page::kPageSize); |
| 43 } | 45 } |
| 44 | 46 |
| 45 // Given a page and a slot in that page, this function removes the slot from | 47 // Given a page and a slot in that page, this function removes the slot from |
| 46 // the remembered set. | 48 // the remembered set. |
| 47 // If the slot was never added, then the function does nothing. | 49 // If the slot was never added, then the function does nothing. |
| 48 static void Remove(MemoryChunk* chunk, Address slot_addr) { | 50 static void Remove(MemoryChunk* chunk, Address slot_addr) { |
| 49 DCHECK(chunk->Contains(slot_addr)); | 51 DCHECK(chunk->Contains(slot_addr)); |
| 50 SlotSet* slot_set = chunk->slot_set<type>(); | 52 SlotSet* slot_set = GetSlotSet(chunk); |
| 51 if (slot_set != nullptr) { | 53 if (slot_set != nullptr) { |
| 52 uintptr_t offset = slot_addr - chunk->address(); | 54 uintptr_t offset = slot_addr - chunk->address(); |
| 53 slot_set[offset / Page::kPageSize].Remove(offset % Page::kPageSize); | 55 slot_set[offset / Page::kPageSize].Remove(offset % Page::kPageSize); |
| 54 } | 56 } |
| 55 } | 57 } |
| 56 | 58 |
| 57 // Given a page and a range of slots in that page, this function removes the | 59 // Given a page and a range of slots in that page, this function removes the |
| 58 // slots from the remembered set. | 60 // slots from the remembered set. |
| 59 static void RemoveRange(MemoryChunk* chunk, Address start, Address end, | 61 static void RemoveRange(MemoryChunk* chunk, Address start, Address end, |
| 60 SlotSet::EmptyBucketMode mode) { | 62 SlotSet::EmptyBucketMode mode) { |
| 61 SlotSet* slot_set = chunk->slot_set<type>(); | 63 SlotSet* slot_set = GetSlotSet(chunk); |
| 62 if (slot_set != nullptr) { | 64 if (slot_set != nullptr) { |
| 63 uintptr_t start_offset = start - chunk->address(); | 65 uintptr_t start_offset = start - chunk->address(); |
| 64 uintptr_t end_offset = end - chunk->address(); | 66 uintptr_t end_offset = end - chunk->address(); |
| 65 DCHECK_LT(start_offset, end_offset); | 67 DCHECK_LT(start_offset, end_offset); |
| 66 if (end_offset < static_cast<uintptr_t>(Page::kPageSize)) { | 68 if (end_offset < static_cast<uintptr_t>(Page::kPageSize)) { |
| 67 slot_set->RemoveRange(static_cast<int>(start_offset), | 69 slot_set->RemoveRange(static_cast<int>(start_offset), |
| 68 static_cast<int>(end_offset), mode); | 70 static_cast<int>(end_offset), mode); |
| 69 } else { | 71 } else { |
| 70 // The large page has multiple slot sets. | 72 // The large page has multiple slot sets. |
| 71 // Compute slot set indicies for the range [start_offset, end_offset). | 73 // Compute slot set indicies for the range [start_offset, end_offset). |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 103 heap, [callback](MemoryChunk* chunk) { Iterate(chunk, callback); }); | 105 heap, [callback](MemoryChunk* chunk) { Iterate(chunk, callback); }); |
| 104 } | 106 } |
| 105 | 107 |
| 106 // Iterates over all memory chunks that contains non-empty slot sets. | 108 // Iterates over all memory chunks that contains non-empty slot sets. |
| 107 // The callback should take (MemoryChunk* chunk) and return void. | 109 // The callback should take (MemoryChunk* chunk) and return void. |
| 108 template <typename Callback> | 110 template <typename Callback> |
| 109 static void IterateMemoryChunks(Heap* heap, Callback callback) { | 111 static void IterateMemoryChunks(Heap* heap, Callback callback) { |
| 110 MemoryChunkIterator it(heap); | 112 MemoryChunkIterator it(heap); |
| 111 MemoryChunk* chunk; | 113 MemoryChunk* chunk; |
| 112 while ((chunk = it.next()) != nullptr) { | 114 while ((chunk = it.next()) != nullptr) { |
| 113 SlotSet* slots = chunk->slot_set<type>(); | 115 SlotSet* slots = GetSlotSet(chunk); |
| 114 TypedSlotSet* typed_slots = chunk->typed_slot_set<type>(); | 116 TypedSlotSet* typed_slots = GetTypedSlotSet(chunk); |
| 115 if (slots != nullptr || typed_slots != nullptr) { | 117 if (slots != nullptr || typed_slots != nullptr) { |
| 116 callback(chunk); | 118 callback(chunk); |
| 117 } | 119 } |
| 118 } | 120 } |
| 119 } | 121 } |
| 120 | 122 |
| 121 // Iterates and filters the remembered set in the given memory chunk with | 123 // Iterates and filters the remembered set in the given memory chunk with |
| 122 // the given callback. The callback should take (Address slot) and return | 124 // the given callback. The callback should take (Address slot) and return |
| 123 // SlotCallbackResult. | 125 // SlotCallbackResult. |
| 124 template <typename Callback> | 126 template <typename Callback> |
| 125 static void Iterate(MemoryChunk* chunk, Callback callback) { | 127 static void Iterate(MemoryChunk* chunk, Callback callback) { |
| 126 SlotSet* slots = chunk->slot_set<type>(); | 128 SlotSet* slots = GetSlotSet(chunk); |
| 127 if (slots != nullptr) { | 129 if (slots != nullptr) { |
| 128 size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize; | 130 size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize; |
| 129 int new_count = 0; | 131 int new_count = 0; |
| 130 for (size_t page = 0; page < pages; page++) { | 132 for (size_t page = 0; page < pages; page++) { |
| 131 new_count += | 133 new_count += |
| 132 slots[page].Iterate(callback, SlotSet::PREFREE_EMPTY_BUCKETS); | 134 slots[page].Iterate(callback, SlotSet::PREFREE_EMPTY_BUCKETS); |
| 133 } | 135 } |
| 134 // Only old-to-old slot sets are released eagerly. Old-new-slot sets are | 136 // Only old-to-old slot sets are released eagerly. Old-new-slot sets are |
| 135 // released by the sweeper threads. | 137 // released by the sweeper threads. |
| 136 if (type == OLD_TO_OLD && new_count == 0) { | 138 if (direction == OLD_TO_OLD && new_count == 0) { |
| 137 chunk->ReleaseSlotSet<OLD_TO_OLD>(); | 139 chunk->ReleaseOldToOldSlots(); |
| 138 } | 140 } |
| 139 } | 141 } |
| 140 } | 142 } |
| 141 | 143 |
| 142 // Given a page and a typed slot in that page, this function adds the slot | 144 // Given a page and a typed slot in that page, this function adds the slot |
| 143 // to the remembered set. | 145 // to the remembered set. |
| 144 static void InsertTyped(Page* page, Address host_addr, SlotType slot_type, | 146 static void InsertTyped(Page* page, Address host_addr, SlotType slot_type, |
| 145 Address slot_addr) { | 147 Address slot_addr) { |
| 146 TypedSlotSet* slot_set = page->typed_slot_set<type>(); | 148 TypedSlotSet* slot_set = GetTypedSlotSet(page); |
| 147 if (slot_set == nullptr) { | 149 if (slot_set == nullptr) { |
| 148 slot_set = page->AllocateTypedSlotSet<type>(); | 150 AllocateTypedSlotSet(page); |
| 151 slot_set = GetTypedSlotSet(page); |
| 149 } | 152 } |
| 150 if (host_addr == nullptr) { | 153 if (host_addr == nullptr) { |
| 151 host_addr = page->address(); | 154 host_addr = page->address(); |
| 152 } | 155 } |
| 153 uintptr_t offset = slot_addr - page->address(); | 156 uintptr_t offset = slot_addr - page->address(); |
| 154 uintptr_t host_offset = host_addr - page->address(); | 157 uintptr_t host_offset = host_addr - page->address(); |
| 155 DCHECK_LT(offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset)); | 158 DCHECK_LT(offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset)); |
| 156 DCHECK_LT(host_offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset)); | 159 DCHECK_LT(host_offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset)); |
| 157 slot_set->Insert(slot_type, static_cast<uint32_t>(host_offset), | 160 slot_set->Insert(slot_type, static_cast<uint32_t>(host_offset), |
| 158 static_cast<uint32_t>(offset)); | 161 static_cast<uint32_t>(offset)); |
| 159 } | 162 } |
| 160 | 163 |
| 161 // Given a page and a range of typed slots in that page, this function removes | 164 // Given a page and a range of typed slots in that page, this function removes |
| 162 // the slots from the remembered set. | 165 // the slots from the remembered set. |
| 163 static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) { | 166 static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) { |
| 164 TypedSlotSet* slots = page->typed_slot_set<type>(); | 167 TypedSlotSet* slots = GetTypedSlotSet(page); |
| 165 if (slots != nullptr) { | 168 if (slots != nullptr) { |
| 166 slots->Iterate( | 169 slots->Iterate( |
| 167 [start, end](SlotType slot_type, Address host_addr, | 170 [start, end](SlotType slot_type, Address host_addr, |
| 168 Address slot_addr) { | 171 Address slot_addr) { |
| 169 return start <= slot_addr && slot_addr < end ? REMOVE_SLOT | 172 return start <= slot_addr && slot_addr < end ? REMOVE_SLOT |
| 170 : KEEP_SLOT; | 173 : KEEP_SLOT; |
| 171 }, | 174 }, |
| 172 TypedSlotSet::PREFREE_EMPTY_CHUNKS); | 175 TypedSlotSet::PREFREE_EMPTY_CHUNKS); |
| 173 } | 176 } |
| 174 } | 177 } |
| 175 | 178 |
| 176 // Iterates and filters the remembered set with the given callback. | 179 // Iterates and filters the remembered set with the given callback. |
| 177 // The callback should take (SlotType slot_type, SlotAddress slot) and return | 180 // The callback should take (SlotType slot_type, SlotAddress slot) and return |
| 178 // SlotCallbackResult. | 181 // SlotCallbackResult. |
| 179 template <typename Callback> | 182 template <typename Callback> |
| 180 static void IterateTyped(Heap* heap, Callback callback) { | 183 static void IterateTyped(Heap* heap, Callback callback) { |
| 181 IterateMemoryChunks(heap, [callback](MemoryChunk* chunk) { | 184 IterateMemoryChunks(heap, [callback](MemoryChunk* chunk) { |
| 182 IterateTyped(chunk, callback); | 185 IterateTyped(chunk, callback); |
| 183 }); | 186 }); |
| 184 } | 187 } |
| 185 | 188 |
| 186 // Iterates and filters typed old to old pointers in the given memory chunk | 189 // Iterates and filters typed old to old pointers in the given memory chunk |
| 187 // with the given callback. The callback should take (SlotType slot_type, | 190 // with the given callback. The callback should take (SlotType slot_type, |
| 188 // Address slot_addr) and return SlotCallbackResult. | 191 // Address slot_addr) and return SlotCallbackResult. |
| 189 template <typename Callback> | 192 template <typename Callback> |
| 190 static void IterateTyped(MemoryChunk* chunk, Callback callback) { | 193 static void IterateTyped(MemoryChunk* chunk, Callback callback) { |
| 191 TypedSlotSet* slots = chunk->typed_slot_set<type>(); | 194 TypedSlotSet* slots = GetTypedSlotSet(chunk); |
| 192 if (slots != nullptr) { | 195 if (slots != nullptr) { |
| 193 int new_count = slots->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS); | 196 int new_count = slots->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS); |
| 194 if (new_count == 0) { | 197 if (new_count == 0) { |
| 195 chunk->ReleaseTypedSlotSet<type>(); | 198 ReleaseTypedSlotSet(chunk); |
| 196 } | 199 } |
| 197 } | 200 } |
| 198 } | 201 } |
| 199 | 202 |
| 200 // Clear all old to old slots from the remembered set. | 203 // Clear all old to old slots from the remembered set. |
| 201 static void ClearAll(Heap* heap) { | 204 static void ClearAll(Heap* heap) { |
| 202 STATIC_ASSERT(type == OLD_TO_OLD); | 205 STATIC_ASSERT(direction == OLD_TO_OLD); |
| 203 MemoryChunkIterator it(heap); | 206 MemoryChunkIterator it(heap); |
| 204 MemoryChunk* chunk; | 207 MemoryChunk* chunk; |
| 205 while ((chunk = it.next()) != nullptr) { | 208 while ((chunk = it.next()) != nullptr) { |
| 206 chunk->ReleaseSlotSet<OLD_TO_OLD>(); | 209 chunk->ReleaseOldToOldSlots(); |
| 207 chunk->ReleaseTypedSlotSet<OLD_TO_OLD>(); | 210 chunk->ReleaseTypedOldToOldSlots(); |
| 208 } | 211 } |
| 209 } | 212 } |
| 210 | 213 |
| 211 // Eliminates all stale slots from the remembered set, i.e. | 214 // Eliminates all stale slots from the remembered set, i.e. |
| 212 // slots that are not part of live objects anymore. This method must be | 215 // slots that are not part of live objects anymore. This method must be |
| 213 // called after marking, when the whole transitive closure is known and | 216 // called after marking, when the whole transitive closure is known and |
| 214 // must be called before sweeping when mark bits are still intact. | 217 // must be called before sweeping when mark bits are still intact. |
| 215 static void ClearInvalidTypedSlots(Heap* heap, MemoryChunk* chunk); | 218 static void ClearInvalidTypedSlots(Heap* heap, MemoryChunk* chunk); |
| 216 | 219 |
| 217 private: | 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 |
| 218 static bool IsValidSlot(Heap* heap, MemoryChunk* chunk, Object** slot); | 263 static bool IsValidSlot(Heap* heap, MemoryChunk* chunk, Object** slot); |
| 219 }; | 264 }; |
| 220 | 265 |
| 221 class UpdateTypedSlotHelper { | 266 class UpdateTypedSlotHelper { |
| 222 public: | 267 public: |
| 223 // Updates a cell slot using an untyped slot callback. | 268 // Updates a cell slot using an untyped slot callback. |
| 224 // The callback accepts Object** and returns SlotCallbackResult. | 269 // The callback accepts Object** and returns SlotCallbackResult. |
| 225 template <typename Callback> | 270 template <typename Callback> |
| 226 static SlotCallbackResult UpdateCell(RelocInfo* rinfo, Callback callback) { | 271 static SlotCallbackResult UpdateCell(RelocInfo* rinfo, Callback callback) { |
| 227 DCHECK(rinfo->rmode() == RelocInfo::CELL); | 272 DCHECK(rinfo->rmode() == RelocInfo::CELL); |
| (...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 347 return DEBUG_TARGET_SLOT; | 392 return DEBUG_TARGET_SLOT; |
| 348 } | 393 } |
| 349 UNREACHABLE(); | 394 UNREACHABLE(); |
| 350 return CLEARED_SLOT; | 395 return CLEARED_SLOT; |
| 351 } | 396 } |
| 352 | 397 |
| 353 } // namespace internal | 398 } // namespace internal |
| 354 } // namespace v8 | 399 } // namespace v8 |
| 355 | 400 |
| 356 #endif // V8_REMEMBERED_SET_H | 401 #endif // V8_REMEMBERED_SET_H |
| OLD | NEW |