LCOV - code coverage report
Current view: top level - src/heap - remembered-set.h (source / functions) Hit Total Coverage
Test: app.info Lines: 99 119 83.2 %
Date: 2019-02-19 Functions: 35 56 62.5 %

          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_HEAP_REMEMBERED_SET_H_
       6             : #define V8_HEAP_REMEMBERED_SET_H_
       7             : 
       8             : #include "src/heap/heap.h"
       9             : #include "src/heap/slot-set.h"
      10             : #include "src/heap/spaces.h"
      11             : #include "src/reloc-info.h"
      12             : #include "src/v8memory.h"
      13             : 
      14             : namespace v8 {
      15             : namespace internal {
      16             : 
      17             : enum RememberedSetIterationMode { SYNCHRONIZED, NON_SYNCHRONIZED };
      18             : 
      19             : // TODO(ulan): Investigate performance of de-templatizing this class.
      20             : template <RememberedSetType type>
      21             : class RememberedSet : public AllStatic {
      22             :  public:
      23             :   // Given a page and a slot in that page, this function adds the slot to the
      24             :   // remembered set.
      25             :   template <AccessMode access_mode = AccessMode::ATOMIC>
      26   198165249 :   static void Insert(MemoryChunk* chunk, Address slot_addr) {
      27             :     DCHECK(chunk->Contains(slot_addr));
      28             :     SlotSet* slot_set = chunk->slot_set<type, access_mode>();
      29   198165249 :     if (slot_set == nullptr) {
      30       93887 :       slot_set = chunk->AllocateSlotSet<type>();
      31             :     }
      32   198165250 :     uintptr_t offset = slot_addr - chunk->address();
      33   198165250 :     slot_set[offset / Page::kPageSize].Insert<access_mode>(offset %
      34             :                                                            Page::kPageSize);
      35   198278821 :   }
      36             : 
      37             :   // Given a page and a slot in that page, this function returns true if
      38             :   // the remembered set contains the slot.
      39             :   static bool Contains(MemoryChunk* chunk, Address slot_addr) {
      40             :     DCHECK(chunk->Contains(slot_addr));
      41             :     SlotSet* slot_set = chunk->slot_set<type>();
      42             :     if (slot_set == nullptr) {
      43             :       return false;
      44             :     }
      45             :     uintptr_t offset = slot_addr - chunk->address();
      46             :     return slot_set[offset / Page::kPageSize].Contains(offset %
      47             :                                                        Page::kPageSize);
      48             :   }
      49             : 
      50             :   // Given a page and a slot in that page, this function removes the slot from
      51             :   // the remembered set.
      52             :   // If the slot was never added, then the function does nothing.
      53         982 :   static void Remove(MemoryChunk* chunk, Address slot_addr) {
      54             :     DCHECK(chunk->Contains(slot_addr));
      55             :     SlotSet* slot_set = chunk->slot_set<type>();
      56         982 :     if (slot_set != nullptr) {
      57         668 :       uintptr_t offset = slot_addr - chunk->address();
      58         668 :       slot_set[offset / Page::kPageSize].Remove(offset % Page::kPageSize);
      59             :     }
      60         982 :   }
      61             : 
      62             :   // Given a page and a range of slots in that page, this function removes the
      63             :   // slots from the remembered set.
      64    41424352 :   static void RemoveRange(MemoryChunk* chunk, Address start, Address end,
      65             :                           SlotSet::EmptyBucketMode mode) {
      66             :     SlotSet* slot_set = chunk->slot_set<type>();
      67    41424352 :     if (slot_set != nullptr) {
      68    20203327 :       uintptr_t start_offset = start - chunk->address();
      69    20203327 :       uintptr_t end_offset = end - chunk->address();
      70             :       DCHECK_LT(start_offset, end_offset);
      71    20203327 :       if (end_offset < static_cast<uintptr_t>(Page::kPageSize)) {
      72    19993401 :         slot_set->RemoveRange(static_cast<int>(start_offset),
      73    19993401 :                               static_cast<int>(end_offset), mode);
      74             :       } else {
      75             :         // The large page has multiple slot sets.
      76             :         // Compute slot set indicies for the range [start_offset, end_offset).
      77      209926 :         int start_chunk = static_cast<int>(start_offset / Page::kPageSize);
      78      209926 :         int end_chunk = static_cast<int>((end_offset - 1) / Page::kPageSize);
      79             :         int offset_in_start_chunk =
      80      209926 :             static_cast<int>(start_offset % Page::kPageSize);
      81             :         // Note that using end_offset % Page::kPageSize would be incorrect
      82             :         // because end_offset is one beyond the last slot to clear.
      83             :         int offset_in_end_chunk = static_cast<int>(
      84      209926 :             end_offset - static_cast<uintptr_t>(end_chunk) * Page::kPageSize);
      85      209926 :         if (start_chunk == end_chunk) {
      86      209914 :           slot_set[start_chunk].RemoveRange(offset_in_start_chunk,
      87      209914 :                                             offset_in_end_chunk, mode);
      88             :         } else {
      89             :           // Clear all slots from start_offset to the end of first chunk.
      90          12 :           slot_set[start_chunk].RemoveRange(offset_in_start_chunk,
      91          12 :                                             Page::kPageSize, mode);
      92             :           // Clear all slots in intermediate chunks.
      93          13 :           for (int i = start_chunk + 1; i < end_chunk; i++) {
      94           1 :             slot_set[i].RemoveRange(0, Page::kPageSize, mode);
      95             :           }
      96             :           // Clear slots from the beginning of the last page to end_offset.
      97          12 :           slot_set[end_chunk].RemoveRange(0, offset_in_end_chunk, mode);
      98             :         }
      99             :       }
     100             :     }
     101    41455896 :   }
     102             : 
     103             :   // Iterates and filters the remembered set with the given callback.
     104             :   // The callback should take (Address slot) and return SlotCallbackResult.
     105             :   template <typename Callback>
     106             :   static void Iterate(Heap* heap, RememberedSetIterationMode mode,
     107             :                       Callback callback) {
     108             :     IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) {
     109             :       if (mode == SYNCHRONIZED) chunk->mutex()->Lock();
     110             :       Iterate(chunk, callback);
     111             :       if (mode == SYNCHRONIZED) chunk->mutex()->Unlock();
     112             :     });
     113             :   }
     114             : 
     115             :   // Iterates over all memory chunks that contains non-empty slot sets.
     116             :   // The callback should take (MemoryChunk* chunk) and return void.
     117             :   template <typename Callback>
     118       46980 :   static void IterateMemoryChunks(Heap* heap, Callback callback) {
     119             :     OldGenerationMemoryChunkIterator it(heap);
     120      632253 :     MemoryChunk* chunk;
     121      901033 :     while ((chunk = it.next()) != nullptr) {
     122             :       SlotSet* slots = chunk->slot_set<type>();
     123             :       TypedSlotSet* typed_slots = chunk->typed_slot_set<type>();
     124     1486306 :       if (slots != nullptr || typed_slots != nullptr ||
     125             :           chunk->invalidated_slots() != nullptr) {
     126      221800 :         callback(chunk);
     127             :       }
     128             :     }
     129       46980 :   }
     130             : 
     131             :   // Iterates and filters the remembered set in the given memory chunk with
     132             :   // the given callback. The callback should take (Address slot) and return
     133             :   // SlotCallbackResult.
     134             :   //
     135             :   // Notice that |mode| can only be of FREE* or PREFREE* if there are no other
     136             :   // threads concurrently inserting slots.
     137             :   template <typename Callback>
     138      864356 :   static void Iterate(MemoryChunk* chunk, Callback callback,
     139             :                       SlotSet::EmptyBucketMode mode) {
     140             :     SlotSet* slots = chunk->slot_set<type>();
     141      433076 :     if (slots != nullptr) {
     142      431280 :       size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize;
     143             :       int new_count = 0;
     144      867847 :       for (size_t page = 0; page < pages; page++) {
     145      435823 :         new_count += slots[page].Iterate(callback, mode);
     146             :       }
     147             :       // Only old-to-old slot sets are released eagerly. Old-new-slot sets are
     148             :       // released by the sweeper threads.
     149       17942 :       if (type == OLD_TO_OLD && new_count == 0) {
     150       17941 :         chunk->ReleaseSlotSet<OLD_TO_OLD>();
     151             :       }
     152             :     }
     153      433823 :   }
     154             : 
     155          20 :   static int NumberOfPreFreedEmptyBuckets(MemoryChunk* chunk) {
     156             :     DCHECK(type == OLD_TO_NEW);
     157             :     int result = 0;
     158             :     SlotSet* slots = chunk->slot_set<type>();
     159          10 :     if (slots != nullptr) {
     160          10 :       size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize;
     161          20 :       for (size_t page = 0; page < pages; page++) {
     162          10 :         result += slots[page].NumberOfPreFreedEmptyBuckets();
     163             :       }
     164             :     }
     165          10 :     return result;
     166             :   }
     167             : 
     168         786 :   static void PreFreeEmptyBuckets(MemoryChunk* chunk) {
     169             :     DCHECK(type == OLD_TO_NEW);
     170             :     SlotSet* slots = chunk->slot_set<type>();
     171         393 :     if (slots != nullptr) {
     172         393 :       size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize;
     173         786 :       for (size_t page = 0; page < pages; page++) {
     174         393 :         slots[page].PreFreeEmptyBuckets();
     175             :       }
     176             :     }
     177         393 :   }
     178             : 
     179      302182 :   static void FreeEmptyBuckets(MemoryChunk* chunk) {
     180             :     DCHECK(type == OLD_TO_NEW);
     181             :     SlotSet* slots = chunk->slot_set<type>();
     182      191894 :     if (slots != nullptr) {
     183      110288 :       size_t pages = (chunk->size() + Page::kPageSize - 1) / Page::kPageSize;
     184      223477 :       for (size_t page = 0; page < pages; page++) {
     185      113189 :         slots[page].FreeEmptyBuckets();
     186      113189 :         slots[page].FreeToBeFreedBuckets();
     187             :       }
     188             :     }
     189      191894 :   }
     190             : 
     191             :   // Given a page and a typed slot in that page, this function adds the slot
     192             :   // to the remembered set.
     193      352372 :   static void InsertTyped(MemoryChunk* memory_chunk, SlotType slot_type,
     194             :                           uint32_t offset) {
     195             :     TypedSlotSet* slot_set = memory_chunk->typed_slot_set<type>();
     196      352372 :     if (slot_set == nullptr) {
     197        9031 :       slot_set = memory_chunk->AllocateTypedSlotSet<type>();
     198             :     }
     199      352372 :     slot_set->Insert(slot_type, offset);
     200      352372 :   }
     201             : 
     202         562 :   static void MergeTyped(MemoryChunk* page, std::unique_ptr<TypedSlots> slots) {
     203             :     TypedSlotSet* slot_set = page->typed_slot_set<type>();
     204         562 :     if (slot_set == nullptr) {
     205         286 :       slot_set = page->AllocateTypedSlotSet<type>();
     206             :     }
     207         562 :     slot_set->Merge(slots.get());
     208         562 :   }
     209             : 
     210             :   // Given a page and a range of typed slots in that page, this function removes
     211             :   // the slots from the remembered set.
     212         131 :   static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) {
     213             :     TypedSlotSet* slots = page->typed_slot_set<type>();
     214         131 :     if (slots != nullptr) {
     215           0 :       slots->Iterate(
     216             :           [=](SlotType slot_type, Address slot_addr) {
     217             :             return start <= slot_addr && slot_addr < end ? REMOVE_SLOT
     218             :                                                          : KEEP_SLOT;
     219           0 :           },
     220             :           TypedSlotSet::PREFREE_EMPTY_CHUNKS);
     221             :     }
     222         131 :   }
     223             : 
     224             :   // Iterates and filters the remembered set with the given callback.
     225             :   // The callback should take (SlotType slot_type, Address addr) and return
     226             :   // SlotCallbackResult.
     227             :   template <typename Callback>
     228             :   static void IterateTyped(Heap* heap, RememberedSetIterationMode mode,
     229             :                            Callback callback) {
     230             :     IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) {
     231             :       if (mode == SYNCHRONIZED) chunk->mutex()->Lock();
     232             :       IterateTyped(chunk, callback);
     233             :       if (mode == SYNCHRONIZED) chunk->mutex()->Unlock();
     234             :     });
     235             :   }
     236             : 
     237             :   // Iterates and filters typed old to old pointers in the given memory chunk
     238             :   // with the given callback. The callback should take (SlotType slot_type,
     239             :   // Address addr) and return SlotCallbackResult.
     240             :   template <typename Callback>
     241      113159 :   static void IterateTyped(MemoryChunk* chunk, Callback callback) {
     242             :     TypedSlotSet* slots = chunk->typed_slot_set<type>();
     243      113159 :     if (slots != nullptr) {
     244        4399 :       int new_count = slots->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS);
     245        4399 :       if (new_count == 0) {
     246        2489 :         chunk->ReleaseTypedSlotSet<type>();
     247             :       }
     248             :     }
     249      113159 :   }
     250             : 
     251             :   // Clear all old to old slots from the remembered set.
     252          35 :   static void ClearAll(Heap* heap) {
     253             :     STATIC_ASSERT(type == OLD_TO_OLD);
     254             :     OldGenerationMemoryChunkIterator it(heap);
     255             :     MemoryChunk* chunk;
     256         669 :     while ((chunk = it.next()) != nullptr) {
     257         634 :       chunk->ReleaseSlotSet<OLD_TO_OLD>();
     258         634 :       chunk->ReleaseTypedSlotSet<OLD_TO_OLD>();
     259         634 :       chunk->ReleaseInvalidatedSlots();
     260             :     }
     261          35 :   }
     262             : 
     263             :  private:
     264             :   static bool IsValidSlot(Heap* heap, MemoryChunk* chunk, ObjectSlot slot);
     265             : };
     266             : 
     267             : class UpdateTypedSlotHelper {
     268             :  public:
     269             :   // Updates a typed slot using an untyped slot callback.
     270             :   // The callback accepts MaybeObjectSlot and returns SlotCallbackResult.
     271             :   template <typename Callback>
     272      463021 :   static SlotCallbackResult UpdateTypedSlot(Heap* heap, SlotType slot_type,
     273             :                                             Address addr, Callback callback) {
     274      463021 :     switch (slot_type) {
     275             :       case CODE_TARGET_SLOT: {
     276             :         RelocInfo rinfo(addr, RelocInfo::CODE_TARGET, 0, Code());
     277           0 :         return UpdateCodeTarget(&rinfo, callback);
     278             :       }
     279             :       case CODE_ENTRY_SLOT: {
     280           0 :         return UpdateCodeEntry(addr, callback);
     281             :       }
     282             :       case EMBEDDED_OBJECT_SLOT: {
     283             :         RelocInfo rinfo(addr, RelocInfo::EMBEDDED_OBJECT, 0, Code());
     284      463021 :         return UpdateEmbeddedPointer(heap, &rinfo, callback);
     285             :       }
     286             :       case OBJECT_SLOT: {
     287             :         // TODO(ishell): the incoming addr represents MaybeObjectSlot(addr).
     288             :         STATIC_ASSERT(kTaggedSize == kSystemPointerSize);
     289           0 :         return callback(FullMaybeObjectSlot(addr));
     290             :       }
     291             :       case CLEARED_SLOT:
     292             :         break;
     293             :     }
     294           0 :     UNREACHABLE();
     295             :   }
     296             : 
     297             :  private:
     298             :   // Updates a code entry slot using an untyped slot callback.
     299             :   // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
     300             :   template <typename Callback>
     301           0 :   static SlotCallbackResult UpdateCodeEntry(Address entry_address,
     302             :                                             Callback callback) {
     303           0 :     Code code = Code::GetObjectFromEntryAddress(entry_address);
     304             :     Code old_code = code;
     305           0 :     SlotCallbackResult result = callback(FullMaybeObjectSlot(&code));
     306             :     DCHECK(!HasWeakHeapObjectTag(code.ptr()));
     307           0 :     if (code != old_code) {
     308           0 :       Memory<Address>(entry_address) = code->entry();
     309             :     }
     310           0 :     return result;
     311             :   }
     312             : 
     313             :   // Updates a code target slot using an untyped slot callback.
     314             :   // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
     315             :   template <typename Callback>
     316           0 :   static SlotCallbackResult UpdateCodeTarget(RelocInfo* rinfo,
     317             :                                              Callback callback) {
     318             :     DCHECK(RelocInfo::IsCodeTargetMode(rinfo->rmode()));
     319           0 :     Code old_target = Code::GetCodeFromTargetAddress(rinfo->target_address());
     320           0 :     Code new_target = old_target;
     321           0 :     SlotCallbackResult result = callback(FullMaybeObjectSlot(&new_target));
     322             :     DCHECK(!HasWeakHeapObjectTag(new_target.ptr()));
     323           0 :     if (new_target != old_target) {
     324           0 :       rinfo->set_target_address(
     325             :           Code::cast(new_target)->raw_instruction_start());
     326             :     }
     327           0 :     return result;
     328             :   }
     329             : 
     330             :   // Updates an embedded pointer slot using an untyped slot callback.
     331             :   // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult.
     332             :   template <typename Callback>
     333      463023 :   static SlotCallbackResult UpdateEmbeddedPointer(Heap* heap, RelocInfo* rinfo,
     334             :                                                   Callback callback) {
     335             :     DCHECK(rinfo->rmode() == RelocInfo::EMBEDDED_OBJECT);
     336             :     HeapObject old_target = rinfo->target_object();
     337      463010 :     HeapObject new_target = old_target;
     338      322815 :     SlotCallbackResult result = callback(FullMaybeObjectSlot(&new_target));
     339             :     DCHECK(!HasWeakHeapObjectTag(new_target->ptr()));
     340      463025 :     if (new_target != old_target) {
     341             :       rinfo->set_target_object(heap, HeapObject::cast(new_target));
     342             :     }
     343      463032 :     return result;
     344             :   }
     345             : };
     346             : 
     347             : inline SlotType SlotTypeForRelocInfoMode(RelocInfo::Mode rmode) {
     348      539965 :   if (RelocInfo::IsCodeTargetMode(rmode)) {
     349             :     return CODE_TARGET_SLOT;
     350      539996 :   } else if (RelocInfo::IsEmbeddedObject(rmode)) {
     351             :     return EMBEDDED_OBJECT_SLOT;
     352             :   }
     353           0 :   UNREACHABLE();
     354             : }
     355             : 
     356             : }  // namespace internal
     357             : }  // namespace v8
     358             : 
     359             : #endif  // V8_HEAP_REMEMBERED_SET_H_

Generated by: LCOV version 1.10