LCOV - code coverage report
Current view: top level - src/heap - remembered-set.h (source / functions) Hit Total Coverage
Test: app.info Lines: 114 133 85.7 %
Date: 2017-04-26 Functions: 32 53 60.4 %

          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

Generated by: LCOV version 1.10