// Copyright 2016 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. #ifndef V8_HEAP_REMEMBERED_SET_H_ #define V8_HEAP_REMEMBERED_SET_H_ #include <memory> #include "src/base/bounds.h" #include "src/base/memory.h" #include "src/codegen/reloc-info.h" #include "src/common/globals.h" #include "src/heap/heap.h" #include "src/heap/memory-chunk.h" #include "src/heap/paged-spaces.h" #include "src/heap/slot-set.h" #include "src/heap/spaces.h" #include "src/heap/worklist.h" namespace v8 { namespace internal { enum RememberedSetIterationMode { SYNCHRONIZED, NON_SYNCHRONIZED }; class RememberedSetOperations { public: // Given a page and a slot in that page, this function adds the slot to the // remembered set. template <AccessMode access_mode> static void Insert(SlotSet* slot_set, MemoryChunk* chunk, Address slot_addr) { DCHECK(chunk->Contains(slot_addr)); uintptr_t offset = slot_addr - chunk->address(); slot_set->Insert<access_mode>(offset); } template <typename Callback> static int Iterate(SlotSet* slot_set, MemoryChunk* chunk, Callback callback, SlotSet::EmptyBucketMode mode) { int slots = 0; if (slot_set != nullptr) { slots += slot_set->Iterate(chunk->address(), 0, chunk->buckets(), callback, mode); } return slots; } static void Remove(SlotSet* slot_set, MemoryChunk* chunk, Address slot_addr) { if (slot_set != nullptr) { uintptr_t offset = slot_addr - chunk->address(); slot_set->Remove(offset); } } static void RemoveRange(SlotSet* slot_set, MemoryChunk* chunk, Address start, Address end, SlotSet::EmptyBucketMode mode) { if (slot_set != nullptr) { uintptr_t start_offset = start - chunk->address(); uintptr_t end_offset = end - chunk->address(); DCHECK_LT(start_offset, end_offset); slot_set->RemoveRange(static_cast<int>(start_offset), static_cast<int>(end_offset), chunk->buckets(), mode); } } static void CheckNoneInRange(SlotSet* slot_set, MemoryChunk* chunk, Address start, Address end) { if (slot_set != nullptr) { size_t start_bucket = SlotSet::BucketForSlot(start - chunk->address()); // Both 'end' and 'end_bucket' are exclusive limits, so do some index // juggling to make sure we get the right bucket even if the end address // is at the start of a bucket. size_t end_bucket = SlotSet::BucketForSlot(end - chunk->address() - kTaggedSize) + 1; slot_set->Iterate( chunk->address(), start_bucket, end_bucket, [start, end](MaybeObjectSlot slot) { CHECK(!base::IsInRange(slot.address(), start, end + 1)); return KEEP_SLOT; }, SlotSet::KEEP_EMPTY_BUCKETS); } } }; // TODO(ulan): Investigate performance of de-templatizing this class. template <RememberedSetType type> class RememberedSet : public AllStatic { public: // Given a page and a slot in that page, this function adds the slot to the // remembered set. template <AccessMode access_mode> static void Insert(MemoryChunk* chunk, Address slot_addr) { DCHECK(chunk->Contains(slot_addr)); SlotSet* slot_set = chunk->slot_set<type, access_mode>(); if (slot_set == nullptr) { slot_set = chunk->AllocateSlotSet<type>(); } RememberedSetOperations::Insert<access_mode>(slot_set, chunk, slot_addr); } // Given a page and a slot in that page, this function returns true if // the remembered set contains the slot. static bool Contains(MemoryChunk* chunk, Address slot_addr) { DCHECK(chunk->Contains(slot_addr)); SlotSet* slot_set = chunk->slot_set<type>(); if (slot_set == nullptr) { return false; } uintptr_t offset = slot_addr - chunk->address(); return slot_set->Contains(offset); } static void CheckNoneInRange(MemoryChunk* chunk, Address start, Address end) { SlotSet* slot_set = chunk->slot_set<type>(); RememberedSetOperations::CheckNoneInRange(slot_set, chunk, start, end); } // Given a page and a slot in that page, this function removes the slot from // the remembered set. // If the slot was never added, then the function does nothing. static void Remove(MemoryChunk* chunk, Address slot_addr) { DCHECK(chunk->Contains(slot_addr)); SlotSet* slot_set = chunk->slot_set<type>(); RememberedSetOperations::Remove(slot_set, chunk, slot_addr); } // Given a page and a range of slots in that page, this function removes the // slots from the remembered set. static void RemoveRange(MemoryChunk* chunk, Address start, Address end, SlotSet::EmptyBucketMode mode) { SlotSet* slot_set = chunk->slot_set<type>(); RememberedSetOperations::RemoveRange(slot_set, chunk, start, end, mode); } // Iterates and filters the remembered set with the given callback. // The callback should take (Address slot) and return SlotCallbackResult. template <typename Callback> static void Iterate(Heap* heap, RememberedSetIterationMode mode, Callback callback) { IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) { if (mode == SYNCHRONIZED) chunk->mutex()->Lock(); Iterate(chunk, callback); if (mode == SYNCHRONIZED) chunk->mutex()->Unlock(); }); } // Iterates over all memory chunks that contains non-empty slot sets. // The callback should take (MemoryChunk* chunk) and return void. template <typename Callback> static void IterateMemoryChunks(Heap* heap, Callback callback) { OldGenerationMemoryChunkIterator it(heap); MemoryChunk* chunk; while ((chunk = it.next()) != nullptr) { SlotSet* slot_set = chunk->slot_set<type>(); SlotSet* sweeping_slot_set = type == OLD_TO_NEW ? chunk->sweeping_slot_set() : nullptr; TypedSlotSet* typed_slot_set = chunk->typed_slot_set<type>(); if (slot_set != nullptr || sweeping_slot_set != nullptr || typed_slot_set != nullptr || chunk->invalidated_slots<type>() != nullptr) { callback(chunk); } } } // Iterates and filters the remembered set in the given memory chunk with // the given callback. The callback should take (Address slot) and return // SlotCallbackResult. // // Notice that |mode| can only be of FREE* or PREFREE* if there are no other // threads concurrently inserting slots. template <typename Callback> static int Iterate(MemoryChunk* chunk, Callback callback, SlotSet::EmptyBucketMode mode) { SlotSet* slot_set = chunk->slot_set<type>(); return RememberedSetOperations::Iterate(slot_set, chunk, callback, mode); } template <typename Callback> static int IterateAndTrackEmptyBuckets( MemoryChunk* chunk, Callback callback, Worklist<MemoryChunk*, 64>::View empty_chunks) { SlotSet* slot_set = chunk->slot_set<type>(); int slots = 0; if (slot_set != nullptr) { PossiblyEmptyBuckets* possibly_empty_buckets = chunk->possibly_empty_buckets(); slots += slot_set->IterateAndTrackEmptyBuckets(chunk->address(), 0, chunk->buckets(), callback, possibly_empty_buckets); if (!possibly_empty_buckets->IsEmpty()) empty_chunks.Push(chunk); } return slots; } static void FreeEmptyBuckets(MemoryChunk* chunk) { DCHECK(type == OLD_TO_NEW); SlotSet* slot_set = chunk->slot_set<type>(); if (slot_set != nullptr && slot_set->FreeEmptyBuckets(chunk->buckets())) { chunk->ReleaseSlotSet<type>(); } } static bool CheckPossiblyEmptyBuckets(MemoryChunk* chunk) { DCHECK(type == OLD_TO_NEW); SlotSet* slot_set = chunk->slot_set<type, AccessMode::NON_ATOMIC>(); if (slot_set != nullptr && slot_set->CheckPossiblyEmptyBuckets(chunk->buckets(), chunk->possibly_empty_buckets())) { chunk->ReleaseSlotSet<type>(); return true; } return false; } // Given a page and a typed slot in that page, this function adds the slot // to the remembered set. static void InsertTyped(MemoryChunk* memory_chunk, SlotType slot_type, uint32_t offset) { TypedSlotSet* slot_set = memory_chunk->typed_slot_set<type>(); if (slot_set == nullptr) { slot_set = memory_chunk->AllocateTypedSlotSet<type>(); } slot_set->Insert(slot_type, offset); } static void MergeTyped(MemoryChunk* page, std::unique_ptr<TypedSlots> other) { TypedSlotSet* slot_set = page->typed_slot_set<type>(); if (slot_set == nullptr) { slot_set = page->AllocateTypedSlotSet<type>(); } slot_set->Merge(other.get()); } // Given a page and a range of typed slots in that page, this function removes // the slots from the remembered set. static void RemoveRangeTyped(MemoryChunk* page, Address start, Address end) { TypedSlotSet* slot_set = page->typed_slot_set<type>(); if (slot_set != nullptr) { slot_set->Iterate( [=](SlotType slot_type, Address slot_addr) { return start <= slot_addr && slot_addr < end ? REMOVE_SLOT : KEEP_SLOT; }, TypedSlotSet::FREE_EMPTY_CHUNKS); } } // Iterates and filters the remembered set with the given callback. // The callback should take (SlotType slot_type, Address addr) and return // SlotCallbackResult. template <typename Callback> static void IterateTyped(Heap* heap, RememberedSetIterationMode mode, Callback callback) { IterateMemoryChunks(heap, [mode, callback](MemoryChunk* chunk) { if (mode == SYNCHRONIZED) chunk->mutex()->Lock(); IterateTyped(chunk, callback); if (mode == SYNCHRONIZED) chunk->mutex()->Unlock(); }); } // Iterates and filters typed pointers in the given memory chunk with the // given callback. The callback should take (SlotType slot_type, Address addr) // and return SlotCallbackResult. template <typename Callback> static void IterateTyped(MemoryChunk* chunk, Callback callback) { TypedSlotSet* slot_set = chunk->typed_slot_set<type>(); if (slot_set != nullptr) { int new_count = slot_set->Iterate(callback, TypedSlotSet::KEEP_EMPTY_CHUNKS); if (new_count == 0) { chunk->ReleaseTypedSlotSet<type>(); } } } // Clear all old to old slots from the remembered set. static void ClearAll(Heap* heap) { STATIC_ASSERT(type == OLD_TO_OLD); OldGenerationMemoryChunkIterator it(heap); MemoryChunk* chunk; while ((chunk = it.next()) != nullptr) { chunk->ReleaseSlotSet<OLD_TO_OLD>(); chunk->ReleaseTypedSlotSet<OLD_TO_OLD>(); chunk->ReleaseInvalidatedSlots<OLD_TO_OLD>(); } } }; class UpdateTypedSlotHelper { public: // Updates a typed slot using an untyped slot callback where |addr| depending // on slot type represents either address for respective RelocInfo or address // of the uncompressed constant pool entry. // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult. template <typename Callback> static SlotCallbackResult UpdateTypedSlot(Heap* heap, SlotType slot_type, Address addr, Callback callback); private: // Updates a code entry slot using an untyped slot callback. // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult. template <typename Callback> static SlotCallbackResult UpdateCodeEntry(Address entry_address, Callback callback) { Code code = Code::GetObjectFromEntryAddress(entry_address); Code old_code = code; SlotCallbackResult result = callback(FullMaybeObjectSlot(&code)); DCHECK(!HasWeakHeapObjectTag(code)); if (code != old_code) { base::Memory<Address>(entry_address) = code.entry(); } return result; } // Updates a code target slot using an untyped slot callback. // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult. template <typename Callback> static SlotCallbackResult UpdateCodeTarget(RelocInfo* rinfo, Callback callback) { DCHECK(RelocInfo::IsCodeTargetMode(rinfo->rmode())); Code old_target = Code::GetCodeFromTargetAddress(rinfo->target_address()); Code new_target = old_target; SlotCallbackResult result = callback(FullMaybeObjectSlot(&new_target)); DCHECK(!HasWeakHeapObjectTag(new_target)); if (new_target != old_target) { rinfo->set_target_address(Code::cast(new_target).raw_instruction_start()); } return result; } // Updates an embedded pointer slot using an untyped slot callback. // The callback accepts FullMaybeObjectSlot and returns SlotCallbackResult. template <typename Callback> static SlotCallbackResult UpdateEmbeddedPointer(Heap* heap, RelocInfo* rinfo, Callback callback) { DCHECK(RelocInfo::IsEmbeddedObjectMode(rinfo->rmode())); HeapObject old_target = rinfo->target_object_no_host(heap->isolate()); HeapObject new_target = old_target; SlotCallbackResult result = callback(FullMaybeObjectSlot(&new_target)); DCHECK(!HasWeakHeapObjectTag(new_target)); if (new_target != old_target) { rinfo->set_target_object(heap, HeapObject::cast(new_target)); } return result; } }; class RememberedSetSweeping { public: template <AccessMode access_mode> static void Insert(MemoryChunk* chunk, Address slot_addr) { DCHECK(chunk->Contains(slot_addr)); SlotSet* slot_set = chunk->sweeping_slot_set<access_mode>(); if (slot_set == nullptr) { slot_set = chunk->AllocateSweepingSlotSet(); } RememberedSetOperations::Insert<access_mode>(slot_set, chunk, slot_addr); } static void Remove(MemoryChunk* chunk, Address slot_addr) { DCHECK(chunk->Contains(slot_addr)); SlotSet* slot_set = chunk->sweeping_slot_set<AccessMode::ATOMIC>(); RememberedSetOperations::Remove(slot_set, chunk, slot_addr); } // Given a page and a range of slots in that page, this function removes the // slots from the remembered set. static void RemoveRange(MemoryChunk* chunk, Address start, Address end, SlotSet::EmptyBucketMode mode) { SlotSet* slot_set = chunk->sweeping_slot_set(); RememberedSetOperations::RemoveRange(slot_set, chunk, start, end, mode); } // Iterates and filters the remembered set in the given memory chunk with // the given callback. The callback should take (Address slot) and return // SlotCallbackResult. // // Notice that |mode| can only be of FREE* or PREFREE* if there are no other // threads concurrently inserting slots. template <typename Callback> static int Iterate(MemoryChunk* chunk, Callback callback, SlotSet::EmptyBucketMode mode) { SlotSet* slot_set = chunk->sweeping_slot_set(); return RememberedSetOperations::Iterate(slot_set, chunk, callback, mode); } }; inline SlotType SlotTypeForRelocInfoMode(RelocInfo::Mode rmode) { if (RelocInfo::IsCodeTargetMode(rmode)) { return CODE_TARGET_SLOT; } else if (RelocInfo::IsFullEmbeddedObject(rmode)) { return FULL_EMBEDDED_OBJECT_SLOT; } else if (RelocInfo::IsCompressedEmbeddedObject(rmode)) { return COMPRESSED_EMBEDDED_OBJECT_SLOT; } UNREACHABLE(); } } // namespace internal } // namespace v8 #endif // V8_HEAP_REMEMBERED_SET_H_