Line data Source code
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 RememberedSetIterationMode { SYNCHRONIZED, NON_SYNCHRONIZED };
17 :
18 : // TODO(ulan): Investigate performance of de-templatizing this class.
19 : template <RememberedSetType type>
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 298637200 : static void Insert(MemoryChunk* chunk, Address slot_addr) {
25 : DCHECK(chunk->Contains(slot_addr));
26 : SlotSet* slot_set = chunk->slot_set<type>();
27 298637745 : if (slot_set == nullptr) {
28 90073 : slot_set = chunk->AllocateSlotSet<type>();
29 : }
30 298637745 : uintptr_t offset = slot_addr - chunk->address();
31 298637745 : slot_set[offset / Page::kPageSize].Insert(offset % Page::kPageSize);
32 298639225 : }
33 :
34 : // Given a page and a slot in that page, this function returns true if
35 : // the remembered set contains the slot.
36 0 : static bool Contains(MemoryChunk* chunk, Address slot_addr) {
37 : DCHECK(chunk->Contains(slot_addr));
38 : SlotSet* slot_set = chunk->slot_set<type>();
39 0 : if (slot_set == nullptr) {
40 : return false;
41 : }
42 0 : uintptr_t offset = slot_addr - chunk->address();
43 : return slot_set[offset / Page::kPageSize].Contains(offset %
44 0 : 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 5636 : static void Remove(MemoryChunk* chunk, Address slot_addr) {
51 : DCHECK(chunk->Contains(slot_addr));
52 : SlotSet* slot_set = chunk->slot_set<type>();
53 5636 : if (slot_set != nullptr) {
54 2388 : uintptr_t offset = slot_addr - chunk->address();
55 2388 : slot_set[offset / Page::kPageSize].Remove(offset % Page::kPageSize);
56 : }
57 5636 : }
58 :
59 : // Given a page and a range of slots in that page, this function removes the
60 : // slots from the remembered set.
61 33551944 : static void RemoveRange(MemoryChunk* chunk, Address start, Address end,
62 : SlotSet::EmptyBucketMode mode) {
63 : SlotSet* slot_set = chunk->slot_set<type>();
64 33546271 : if (slot_set != nullptr) {
65 33346231 : uintptr_t start_offset = start - chunk->address();
66 33346231 : uintptr_t end_offset = end - chunk->address();
67 : DCHECK_LT(start_offset, end_offset);
68 33346231 : if (end_offset < static_cast<uintptr_t>(Page::kPageSize)) {
69 33184373 : slot_set->RemoveRange(static_cast<int>(start_offset),
70 33184373 : 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 161858 : int start_chunk = static_cast<int>(start_offset / Page::kPageSize);
75 161858 : int end_chunk = static_cast<int>((end_offset - 1) / Page::kPageSize);
76 : int offset_in_start_chunk =
77 161858 : 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 161858 : end_offset - static_cast<uintptr_t>(end_chunk) * Page::kPageSize);
82 161858 : if (start_chunk == end_chunk) {
83 161844 : slot_set[start_chunk].RemoveRange(offset_in_start_chunk,
84 161844 : offset_in_end_chunk, mode);
85 : } else {
86 : // Clear all slots from start_offset to the end of first chunk.
87 14 : slot_set[start_chunk].RemoveRange(offset_in_start_chunk,
88 14 : Page::kPageSize, mode);
89 : // Clear all slots in intermediate chunks.
90 14 : for (int i = start_chunk + 1; i < end_chunk; i++) {
91 0 : slot_set[i].RemoveRange(0, Page::kPageSize, mode);
92 : }
93 : // Clear slots from the beginning of the last page to end_offset.
94 14 : slot_set[end_chunk].RemoveRange(0, offset_in_end_chunk, mode);
95 : }
96 : }
97 : }
98 33479206 : }
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, RememberedSetIterationMode mode,
104 : Callback callback) {
105 1022643 : IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) {
106 635636 : if (mode == SYNCHRONIZED) chunk->mutex()->Lock();
107 317818 : Iterate(chunk, callback);
108 635636 : if (mode == SYNCHRONIZED) chunk->mutex()->Unlock();
109 317818 : });
110 : }
111 :
112 : // Iterates over all memory chunks that contains non-empty slot sets.
113 : // The callback should take (MemoryChunk* chunk) and return void.
114 : template <typename Callback>
115 245070 : static void IterateMemoryChunks(Heap* heap, Callback callback) {
116 245070 : MemoryChunkIterator it(heap);
117 : MemoryChunk* chunk;
118 2874285 : while ((chunk = it.next()) != nullptr) {
119 : SlotSet* slots = chunk->slot_set<type>();
120 : TypedSlotSet* typed_slots = chunk->typed_slot_set<type>();
121 2384145 : if (slots != nullptr || typed_slots != nullptr) {
122 873393 : callback(chunk);
123 : }
124 : }
125 245070 : }
126 :
127 : // Iterates and filters the remembered set in the given memory chunk with
128 : // the given callback. The callback should take (Address slot) and return
129 : // SlotCallbackResult.
130 : template <typename Callback>
131 1102035 : static void Iterate(MemoryChunk* chunk, Callback callback) {
132 : SlotSet* slots = chunk->slot_set<type>();
133 555488 : if (slots != nullptr) {
134 546519 : size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize;
135 : int new_count = 0;
136 774526 : for (size_t page = 0; page < pages; page++) {
137 549900 : new_count +=
138 : slots[page].Iterate(callback, SlotSet::PREFREE_EMPTY_BUCKETS);
139 : }
140 : // Only old-to-old slot sets are released eagerly. Old-new-slot sets are
141 : // released by the sweeper threads.
142 8452 : if (type == OLD_TO_OLD && new_count == 0) {
143 8452 : chunk->ReleaseSlotSet<OLD_TO_OLD>();
144 : }
145 : }
146 555457 : }
147 :
148 : // Given a page and a typed slot in that page, this function adds the slot
149 : // to the remembered set.
150 1260650 : static void InsertTyped(Page* page, Address host_addr, SlotType slot_type,
151 : Address slot_addr) {
152 : TypedSlotSet* slot_set = page->typed_slot_set<type>();
153 1260650 : if (slot_set == nullptr) {
154 16151 : slot_set = page->AllocateTypedSlotSet<type>();
155 : }
156 1260650 : if (host_addr == nullptr) {
157 3500 : host_addr = page->address();
158 : }
159 1260650 : uintptr_t offset = slot_addr - page->address();
160 1260650 : uintptr_t host_offset = host_addr - page->address();
161 : DCHECK_LT(offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset));
162 : DCHECK_LT(host_offset, static_cast<uintptr_t>(TypedSlotSet::kMaxOffset));
163 1260650 : slot_set->Insert(slot_type, static_cast<uint32_t>(host_offset),
164 1260650 : static_cast<uint32_t>(offset));
165 1260649 : }
166 :
167 : // Given a page and a range of typed slots in that page, this function removes
168 : // the slots from the remembered set.
169 422292 : static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) {
170 : TypedSlotSet* slots = page->typed_slot_set<type>();
171 422292 : if (slots != nullptr) {
172 237402 : slots->Iterate(
173 : [start, end](SlotType slot_type, Address host_addr,
174 : Address slot_addr) {
175 : return start <= slot_addr && slot_addr < end ? REMOVE_SLOT
176 : : KEEP_SLOT;
177 27855100 : },
178 : TypedSlotSet::PREFREE_EMPTY_CHUNKS);
179 : }
180 422292 : }
181 :
182 : // Iterates and filters the remembered set with the given callback.
183 : // The callback should take (SlotType slot_type, SlotAddress slot) and return
184 : // SlotCallbackResult.
185 : template <typename Callback>
186 : static void IterateTyped(Heap* heap, RememberedSetIterationMode mode,
187 : Callback callback) {
188 1022643 : IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) {
189 635636 : if (mode == SYNCHRONIZED) chunk->mutex()->Lock();
190 317818 : IterateTyped(chunk, callback);
191 635636 : if (mode == SYNCHRONIZED) chunk->mutex()->Unlock();
192 317818 : });
193 : }
194 :
195 : // Iterates and filters typed old to old pointers in the given memory chunk
196 : // with the given callback. The callback should take (SlotType slot_type,
197 : // Address slot_addr) and return SlotCallbackResult.
198 : template <typename Callback>
199 555462 : static void IterateTyped(MemoryChunk* chunk, Callback callback) {
200 : TypedSlotSet* slots = chunk->typed_slot_set<type>();
201 555471 : if (slots != nullptr) {
202 10286 : int new_count = slots->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS);
203 10286 : if (new_count == 0) {
204 5457 : chunk->ReleaseTypedSlotSet<type>();
205 : }
206 : }
207 555471 : }
208 :
209 : // Clear all old to old slots from the remembered set.
210 4 : static void ClearAll(Heap* heap) {
211 : STATIC_ASSERT(type == OLD_TO_OLD);
212 4 : MemoryChunkIterator it(heap);
213 : MemoryChunk* chunk;
214 107 : while ((chunk = it.next()) != nullptr) {
215 99 : chunk->ReleaseSlotSet<OLD_TO_OLD>();
216 99 : chunk->ReleaseTypedSlotSet<OLD_TO_OLD>();
217 : }
218 4 : }
219 :
220 : // Eliminates all stale slots from the remembered set, i.e.
221 : // slots that are not part of live objects anymore. This method must be
222 : // called after marking, when the whole transitive closure is known and
223 : // must be called before sweeping when mark bits are still intact.
224 : static void ClearInvalidTypedSlots(Heap* heap, MemoryChunk* chunk);
225 :
226 : private:
227 : static bool IsValidSlot(Heap* heap, MemoryChunk* chunk, Object** slot);
228 : };
229 :
230 : class UpdateTypedSlotHelper {
231 : public:
232 : // Updates a cell slot using an untyped slot callback.
233 : // The callback accepts Object** and returns SlotCallbackResult.
234 : template <typename Callback>
235 299 : static SlotCallbackResult UpdateCell(RelocInfo* rinfo, Callback callback) {
236 : DCHECK(rinfo->rmode() == RelocInfo::CELL);
237 299 : Object* cell = rinfo->target_cell();
238 : Object* old_cell = cell;
239 299 : SlotCallbackResult result = callback(&cell);
240 299 : if (cell != old_cell) {
241 : rinfo->set_target_cell(reinterpret_cast<Cell*>(cell));
242 : }
243 299 : return result;
244 : }
245 :
246 : // Updates a code entry slot using an untyped slot callback.
247 : // The callback accepts Object** and returns SlotCallbackResult.
248 : template <typename Callback>
249 0 : static SlotCallbackResult UpdateCodeEntry(Address entry_address,
250 : Callback callback) {
251 1188464 : Object* code = Code::GetObjectFromEntryAddress(entry_address);
252 : Object* old_code = code;
253 1188464 : SlotCallbackResult result = callback(&code);
254 1188468 : if (code != old_code) {
255 4711 : Memory::Address_at(entry_address) =
256 4711 : reinterpret_cast<Code*>(code)->entry();
257 : }
258 0 : return result;
259 : }
260 :
261 : // Updates a code target slot using an untyped slot callback.
262 : // The callback accepts Object** and returns SlotCallbackResult.
263 : template <typename Callback>
264 35999 : static SlotCallbackResult UpdateCodeTarget(RelocInfo* rinfo,
265 : Callback callback) {
266 : DCHECK(RelocInfo::IsCodeTarget(rinfo->rmode()));
267 35999 : Code* old_target = Code::GetCodeFromTargetAddress(rinfo->target_address());
268 35999 : Object* new_target = old_target;
269 35999 : SlotCallbackResult result = callback(&new_target);
270 35999 : if (new_target != old_target) {
271 35999 : rinfo->set_target_address(old_target->GetIsolate(),
272 35999 : Code::cast(new_target)->instruction_start());
273 : }
274 35999 : return result;
275 : }
276 :
277 : // Updates an embedded pointer slot using an untyped slot callback.
278 : // The callback accepts Object** and returns SlotCallbackResult.
279 : template <typename Callback>
280 877851 : static SlotCallbackResult UpdateEmbeddedPointer(RelocInfo* rinfo,
281 : Callback callback) {
282 : DCHECK(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
283 : HeapObject* old_target = rinfo->target_object();
284 877859 : Object* new_target = old_target;
285 202146 : SlotCallbackResult result = callback(&new_target);
286 877893 : if (new_target != old_target) {
287 : rinfo->set_target_object(HeapObject::cast(new_target));
288 : }
289 877769 : return result;
290 : }
291 :
292 : // Updates a debug target slot using an untyped slot callback.
293 : // The callback accepts Object** and returns SlotCallbackResult.
294 : template <typename Callback>
295 0 : static SlotCallbackResult UpdateDebugTarget(RelocInfo* rinfo,
296 : Callback callback) {
297 : DCHECK(RelocInfo::IsDebugBreakSlot(rinfo->rmode()) &&
298 : rinfo->IsPatchedDebugBreakSlotSequence());
299 : Code* old_target =
300 0 : Code::GetCodeFromTargetAddress(rinfo->debug_call_address());
301 0 : Object* new_target = old_target;
302 0 : SlotCallbackResult result = callback(&new_target);
303 : rinfo->set_debug_call_address(old_target->GetIsolate(),
304 0 : Code::cast(new_target)->instruction_start());
305 0 : return result;
306 : }
307 :
308 : // Updates a typed slot using an untyped slot callback.
309 : // The callback accepts Object** and returns SlotCallbackResult.
310 : template <typename Callback>
311 918750 : static SlotCallbackResult UpdateTypedSlot(Isolate* isolate,
312 : SlotType slot_type, Address addr,
313 : Callback callback) {
314 918750 : switch (slot_type) {
315 : case CODE_TARGET_SLOT: {
316 : RelocInfo rinfo(addr, RelocInfo::CODE_TARGET, 0, NULL);
317 35999 : return UpdateCodeTarget(&rinfo, callback);
318 : }
319 : case CELL_TARGET_SLOT: {
320 : RelocInfo rinfo(addr, RelocInfo::CELL, 0, NULL);
321 299 : return UpdateCell(&rinfo, callback);
322 : }
323 : case CODE_ENTRY_SLOT: {
324 4613 : return UpdateCodeEntry(addr, callback);
325 : }
326 : case DEBUG_TARGET_SLOT: {
327 : RelocInfo rinfo(addr, RelocInfo::DEBUG_BREAK_SLOT_AT_POSITION, 0, NULL);
328 0 : if (rinfo.IsPatchedDebugBreakSlotSequence()) {
329 0 : return UpdateDebugTarget(&rinfo, callback);
330 : }
331 : return REMOVE_SLOT;
332 : }
333 : case EMBEDDED_OBJECT_SLOT: {
334 : RelocInfo rinfo(addr, RelocInfo::EMBEDDED_OBJECT, 0, NULL);
335 877839 : return UpdateEmbeddedPointer(&rinfo, callback);
336 : }
337 : case OBJECT_SLOT: {
338 0 : return callback(reinterpret_cast<Object**>(addr));
339 : }
340 : case CLEARED_SLOT:
341 : break;
342 : }
343 0 : UNREACHABLE();
344 : return REMOVE_SLOT;
345 : }
346 : };
347 :
348 1256037 : inline SlotType SlotTypeForRelocInfoMode(RelocInfo::Mode rmode) {
349 1256037 : if (RelocInfo::IsCodeTarget(rmode)) {
350 : return CODE_TARGET_SLOT;
351 1220038 : } else if (RelocInfo::IsCell(rmode)) {
352 : return CELL_TARGET_SLOT;
353 1219739 : } else if (RelocInfo::IsEmbeddedObject(rmode)) {
354 : return EMBEDDED_OBJECT_SLOT;
355 0 : } else if (RelocInfo::IsDebugBreakSlot(rmode)) {
356 : return DEBUG_TARGET_SLOT;
357 : }
358 0 : UNREACHABLE();
359 : return CLEARED_SLOT;
360 : }
361 :
362 : } // namespace internal
363 : } // namespace v8
364 :
365 : #endif // V8_REMEMBERED_SET_H
|
