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