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 |