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