// Copyright 2011 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_SPACES_INL_H_ #define V8_HEAP_SPACES_INL_H_ #include "src/heap/spaces.h" #include "src/base/atomic-utils.h" #include "src/base/bounded-page-allocator.h" #include "src/base/v8-fallthrough.h" #include "src/heap/heap-inl.h" #include "src/heap/incremental-marking.h" #include "src/msan.h" #include "src/objects/code-inl.h" namespace v8 { namespace internal { template <class PAGE_TYPE> PageIteratorImpl<PAGE_TYPE>& PageIteratorImpl<PAGE_TYPE>::operator++() { p_ = p_->next_page(); return *this; } template <class PAGE_TYPE> PageIteratorImpl<PAGE_TYPE> PageIteratorImpl<PAGE_TYPE>::operator++(int) { PageIteratorImpl<PAGE_TYPE> tmp(*this); operator++(); return tmp; } PageRange::PageRange(Address start, Address limit) : begin_(Page::FromAddress(start)), end_(Page::FromAllocationAreaAddress(limit)->next_page()) { #ifdef DEBUG if (begin_->InNewSpace()) { SemiSpace::AssertValidRange(start, limit); } #endif // DEBUG } // ----------------------------------------------------------------------------- // SemiSpaceIterator HeapObject SemiSpaceIterator::Next() { while (current_ != limit_) { if (Page::IsAlignedToPageSize(current_)) { Page* page = Page::FromAllocationAreaAddress(current_); page = page->next_page(); DCHECK(page); current_ = page->area_start(); if (current_ == limit_) return HeapObject(); } HeapObject object = HeapObject::FromAddress(current_); current_ += object->Size(); if (!object->IsFiller()) { return object; } } return HeapObject(); } // ----------------------------------------------------------------------------- // HeapObjectIterator HeapObject HeapObjectIterator::Next() { do { HeapObject next_obj = FromCurrentPage(); if (!next_obj.is_null()) return next_obj; } while (AdvanceToNextPage()); return HeapObject(); } HeapObject HeapObjectIterator::FromCurrentPage() { while (cur_addr_ != cur_end_) { if (cur_addr_ == space_->top() && cur_addr_ != space_->limit()) { cur_addr_ = space_->limit(); continue; } HeapObject obj = HeapObject::FromAddress(cur_addr_); const int obj_size = obj->Size(); cur_addr_ += obj_size; DCHECK_LE(cur_addr_, cur_end_); if (!obj->IsFiller()) { if (obj->IsCode()) { DCHECK_EQ(space_, space_->heap()->code_space()); DCHECK_CODEOBJECT_SIZE(obj_size, space_); } else { DCHECK_OBJECT_SIZE(obj_size); } return obj; } } return HeapObject(); } void Space::IncrementExternalBackingStoreBytes(ExternalBackingStoreType type, size_t amount) { base::CheckedIncrement(&external_backing_store_bytes_[type], amount); heap()->IncrementExternalBackingStoreBytes(type, amount); } void Space::DecrementExternalBackingStoreBytes(ExternalBackingStoreType type, size_t amount) { base::CheckedDecrement(&external_backing_store_bytes_[type], amount); heap()->DecrementExternalBackingStoreBytes(type, amount); } void Space::MoveExternalBackingStoreBytes(ExternalBackingStoreType type, Space* from, Space* to, size_t amount) { if (from == to) return; base::CheckedDecrement(&(from->external_backing_store_bytes_[type]), amount); base::CheckedIncrement(&(to->external_backing_store_bytes_[type]), amount); } // ----------------------------------------------------------------------------- // SemiSpace bool SemiSpace::Contains(HeapObject o) { MemoryChunk* memory_chunk = MemoryChunk::FromHeapObject(o); if (memory_chunk->IsLargePage()) return false; return id_ == kToSpace ? memory_chunk->IsToPage() : memory_chunk->IsFromPage(); } bool SemiSpace::Contains(Object o) { return o->IsHeapObject() && Contains(HeapObject::cast(o)); } bool SemiSpace::ContainsSlow(Address a) { for (Page* p : *this) { if (p == MemoryChunk::FromAddress(a)) return true; } return false; } // -------------------------------------------------------------------------- // NewSpace bool NewSpace::Contains(Object o) { return o->IsHeapObject() && Contains(HeapObject::cast(o)); } bool NewSpace::Contains(HeapObject o) { return MemoryChunk::FromHeapObject(o)->InNewSpace(); } bool NewSpace::ContainsSlow(Address a) { return from_space_.ContainsSlow(a) || to_space_.ContainsSlow(a); } bool NewSpace::ToSpaceContainsSlow(Address a) { return to_space_.ContainsSlow(a); } bool NewSpace::ToSpaceContains(Object o) { return to_space_.Contains(o); } bool NewSpace::FromSpaceContains(Object o) { return from_space_.Contains(o); } bool PagedSpace::Contains(Address addr) { return MemoryChunk::FromAnyPointerAddress(addr)->owner() == this; } bool PagedSpace::Contains(Object o) { if (!o.IsHeapObject()) return false; return Page::FromAddress(o.ptr())->owner() == this; } void PagedSpace::UnlinkFreeListCategories(Page* page) { DCHECK_EQ(this, page->owner()); page->ForAllFreeListCategories([this](FreeListCategory* category) { DCHECK_EQ(free_list(), category->owner()); category->set_free_list(nullptr); free_list()->RemoveCategory(category); }); } size_t PagedSpace::RelinkFreeListCategories(Page* page) { DCHECK_EQ(this, page->owner()); size_t added = 0; page->ForAllFreeListCategories([this, &added](FreeListCategory* category) { category->set_free_list(&free_list_); added += category->available(); category->Relink(); }); DCHECK_EQ(page->AvailableInFreeList(), page->AvailableInFreeListFromAllocatedBytes()); return added; } bool PagedSpace::TryFreeLast(HeapObject object, int object_size) { if (allocation_info_.top() != kNullAddress) { const Address object_address = object->address(); if ((allocation_info_.top() - object_size) == object_address) { allocation_info_.set_top(object_address); return true; } } return false; } bool MemoryChunk::HasHeaderSentinel(Address slot_addr) { Address base = BaseAddress(slot_addr); if (slot_addr < base + kHeaderSize) return false; return HeapObject::FromAddress(base) == ObjectSlot(base + kHeaderSentinelOffset).Relaxed_Load(); } MemoryChunk* MemoryChunk::FromAnyPointerAddress(Address addr) { while (!HasHeaderSentinel(addr)) { addr = BaseAddress(addr) - 1; } return FromAddress(addr); } void MemoryChunk::IncrementExternalBackingStoreBytes( ExternalBackingStoreType type, size_t amount) { base::CheckedIncrement(&external_backing_store_bytes_[type], amount); owner()->IncrementExternalBackingStoreBytes(type, amount); } void MemoryChunk::DecrementExternalBackingStoreBytes( ExternalBackingStoreType type, size_t amount) { base::CheckedDecrement(&external_backing_store_bytes_[type], amount); owner()->DecrementExternalBackingStoreBytes(type, amount); } void MemoryChunk::MoveExternalBackingStoreBytes(ExternalBackingStoreType type, MemoryChunk* from, MemoryChunk* to, size_t amount) { base::CheckedDecrement(&(from->external_backing_store_bytes_[type]), amount); base::CheckedIncrement(&(to->external_backing_store_bytes_[type]), amount); Space::MoveExternalBackingStoreBytes(type, from->owner(), to->owner(), amount); } void Page::MarkNeverAllocateForTesting() { DCHECK(this->owner()->identity() != NEW_SPACE); DCHECK(!IsFlagSet(NEVER_ALLOCATE_ON_PAGE)); SetFlag(NEVER_ALLOCATE_ON_PAGE); SetFlag(NEVER_EVACUATE); reinterpret_cast<PagedSpace*>(owner())->free_list()->EvictFreeListItems(this); } void Page::MarkEvacuationCandidate() { DCHECK(!IsFlagSet(NEVER_EVACUATE)); DCHECK_NULL(slot_set<OLD_TO_OLD>()); DCHECK_NULL(typed_slot_set<OLD_TO_OLD>()); SetFlag(EVACUATION_CANDIDATE); reinterpret_cast<PagedSpace*>(owner())->free_list()->EvictFreeListItems(this); } void Page::ClearEvacuationCandidate() { if (!IsFlagSet(COMPACTION_WAS_ABORTED)) { DCHECK_NULL(slot_set<OLD_TO_OLD>()); DCHECK_NULL(typed_slot_set<OLD_TO_OLD>()); } ClearFlag(EVACUATION_CANDIDATE); InitializeFreeListCategories(); } HeapObject LargePage::GetObject() { return HeapObject::FromAddress(area_start()); } OldGenerationMemoryChunkIterator::OldGenerationMemoryChunkIterator(Heap* heap) : heap_(heap), state_(kOldSpaceState), old_iterator_(heap->old_space()->begin()), code_iterator_(heap->code_space()->begin()), map_iterator_(heap->map_space()->begin()), lo_iterator_(heap->lo_space()->begin()), code_lo_iterator_(heap->code_lo_space()->begin()) {} MemoryChunk* OldGenerationMemoryChunkIterator::next() { switch (state_) { case kOldSpaceState: { if (old_iterator_ != heap_->old_space()->end()) return *(old_iterator_++); state_ = kMapState; V8_FALLTHROUGH; } case kMapState: { if (map_iterator_ != heap_->map_space()->end()) return *(map_iterator_++); state_ = kCodeState; V8_FALLTHROUGH; } case kCodeState: { if (code_iterator_ != heap_->code_space()->end()) return *(code_iterator_++); state_ = kLargeObjectState; V8_FALLTHROUGH; } case kLargeObjectState: { if (lo_iterator_ != heap_->lo_space()->end()) return *(lo_iterator_++); state_ = kCodeLargeObjectState; V8_FALLTHROUGH; } case kCodeLargeObjectState: { if (code_lo_iterator_ != heap_->code_lo_space()->end()) return *(code_lo_iterator_++); state_ = kFinishedState; V8_FALLTHROUGH; } case kFinishedState: return nullptr; default: break; } UNREACHABLE(); } Page* FreeList::GetPageForCategoryType(FreeListCategoryType type) { return top(type) ? top(type)->page() : nullptr; } FreeList* FreeListCategory::owner() { return free_list_; } bool FreeListCategory::is_linked() { return prev_ != nullptr || next_ != nullptr; } AllocationResult LocalAllocationBuffer::AllocateRawAligned( int size_in_bytes, AllocationAlignment alignment) { Address current_top = allocation_info_.top(); int filler_size = Heap::GetFillToAlign(current_top, alignment); Address new_top = current_top + filler_size + size_in_bytes; if (new_top > allocation_info_.limit()) return AllocationResult::Retry(); allocation_info_.set_top(new_top); if (filler_size > 0) { return heap_->PrecedeWithFiller(HeapObject::FromAddress(current_top), filler_size); } return AllocationResult(HeapObject::FromAddress(current_top)); } bool PagedSpace::EnsureLinearAllocationArea(int size_in_bytes) { if (allocation_info_.top() + size_in_bytes <= allocation_info_.limit()) { return true; } return SlowRefillLinearAllocationArea(size_in_bytes); } HeapObject PagedSpace::AllocateLinearly(int size_in_bytes) { Address current_top = allocation_info_.top(); Address new_top = current_top + size_in_bytes; DCHECK_LE(new_top, allocation_info_.limit()); allocation_info_.set_top(new_top); return HeapObject::FromAddress(current_top); } HeapObject PagedSpace::TryAllocateLinearlyAligned( int* size_in_bytes, AllocationAlignment alignment) { Address current_top = allocation_info_.top(); int filler_size = Heap::GetFillToAlign(current_top, alignment); Address new_top = current_top + filler_size + *size_in_bytes; if (new_top > allocation_info_.limit()) return HeapObject(); allocation_info_.set_top(new_top); if (filler_size > 0) { *size_in_bytes += filler_size; return heap()->PrecedeWithFiller(HeapObject::FromAddress(current_top), filler_size); } return HeapObject::FromAddress(current_top); } AllocationResult PagedSpace::AllocateRawUnaligned( int size_in_bytes, UpdateSkipList update_skip_list) { DCHECK_IMPLIES(identity() == RO_SPACE, heap()->CanAllocateInReadOnlySpace()); if (!EnsureLinearAllocationArea(size_in_bytes)) { return AllocationResult::Retry(identity()); } HeapObject object = AllocateLinearly(size_in_bytes); DCHECK(!object.is_null()); if (update_skip_list == UPDATE_SKIP_LIST && identity() == CODE_SPACE) { SkipList::Update(object->address(), size_in_bytes); } MSAN_ALLOCATED_UNINITIALIZED_MEMORY(object->address(), size_in_bytes); return object; } AllocationResult PagedSpace::AllocateRawAligned(int size_in_bytes, AllocationAlignment alignment) { DCHECK(identity() == OLD_SPACE || identity() == RO_SPACE); DCHECK_IMPLIES(identity() == RO_SPACE, heap()->CanAllocateInReadOnlySpace()); int allocation_size = size_in_bytes; HeapObject object = TryAllocateLinearlyAligned(&allocation_size, alignment); if (object.is_null()) { // We don't know exactly how much filler we need to align until space is // allocated, so assume the worst case. int filler_size = Heap::GetMaximumFillToAlign(alignment); allocation_size += filler_size; if (!EnsureLinearAllocationArea(allocation_size)) { return AllocationResult::Retry(identity()); } allocation_size = size_in_bytes; object = TryAllocateLinearlyAligned(&allocation_size, alignment); DCHECK(!object.is_null()); } MSAN_ALLOCATED_UNINITIALIZED_MEMORY(object->address(), size_in_bytes); return object; } AllocationResult PagedSpace::AllocateRaw(int size_in_bytes, AllocationAlignment alignment) { if (top_on_previous_step_ && top() < top_on_previous_step_ && SupportsInlineAllocation()) { // Generated code decreased the top() pointer to do folded allocations. // The top_on_previous_step_ can be one byte beyond the current page. DCHECK_NE(top(), kNullAddress); DCHECK_EQ(Page::FromAllocationAreaAddress(top()), Page::FromAllocationAreaAddress(top_on_previous_step_ - 1)); top_on_previous_step_ = top(); } size_t bytes_since_last = top_on_previous_step_ ? top() - top_on_previous_step_ : 0; DCHECK_IMPLIES(!SupportsInlineAllocation(), bytes_since_last == 0); #ifdef V8_HOST_ARCH_32_BIT AllocationResult result = alignment != kWordAligned ? AllocateRawAligned(size_in_bytes, alignment) : AllocateRawUnaligned(size_in_bytes); #else AllocationResult result = AllocateRawUnaligned(size_in_bytes); #endif HeapObject heap_obj; if (!result.IsRetry() && result.To(&heap_obj) && !is_local()) { AllocationStep(static_cast<int>(size_in_bytes + bytes_since_last), heap_obj->address(), size_in_bytes); StartNextInlineAllocationStep(); DCHECK_IMPLIES( heap()->incremental_marking()->black_allocation(), heap()->incremental_marking()->marking_state()->IsBlack(heap_obj)); } return result; } // ----------------------------------------------------------------------------- // NewSpace AllocationResult NewSpace::AllocateRawAligned(int size_in_bytes, AllocationAlignment alignment) { Address top = allocation_info_.top(); int filler_size = Heap::GetFillToAlign(top, alignment); int aligned_size_in_bytes = size_in_bytes + filler_size; if (allocation_info_.limit() - top < static_cast<uintptr_t>(aligned_size_in_bytes)) { // See if we can create room. if (!EnsureAllocation(size_in_bytes, alignment)) { return AllocationResult::Retry(); } top = allocation_info_.top(); filler_size = Heap::GetFillToAlign(top, alignment); aligned_size_in_bytes = size_in_bytes + filler_size; } HeapObject obj = HeapObject::FromAddress(top); allocation_info_.set_top(top + aligned_size_in_bytes); DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_); if (filler_size > 0) { obj = heap()->PrecedeWithFiller(obj, filler_size); } MSAN_ALLOCATED_UNINITIALIZED_MEMORY(obj->address(), size_in_bytes); return obj; } AllocationResult NewSpace::AllocateRawUnaligned(int size_in_bytes) { Address top = allocation_info_.top(); if (allocation_info_.limit() < top + size_in_bytes) { // See if we can create room. if (!EnsureAllocation(size_in_bytes, kWordAligned)) { return AllocationResult::Retry(); } top = allocation_info_.top(); } HeapObject obj = HeapObject::FromAddress(top); allocation_info_.set_top(top + size_in_bytes); DCHECK_SEMISPACE_ALLOCATION_INFO(allocation_info_, to_space_); MSAN_ALLOCATED_UNINITIALIZED_MEMORY(obj->address(), size_in_bytes); return obj; } AllocationResult NewSpace::AllocateRaw(int size_in_bytes, AllocationAlignment alignment) { if (top() < top_on_previous_step_) { // Generated code decreased the top() pointer to do folded allocations DCHECK_EQ(Page::FromAllocationAreaAddress(top()), Page::FromAllocationAreaAddress(top_on_previous_step_)); top_on_previous_step_ = top(); } #ifdef V8_HOST_ARCH_32_BIT return alignment != kWordAligned ? AllocateRawAligned(size_in_bytes, alignment) : AllocateRawUnaligned(size_in_bytes); #else return AllocateRawUnaligned(size_in_bytes); #endif } V8_WARN_UNUSED_RESULT inline AllocationResult NewSpace::AllocateRawSynchronized( int size_in_bytes, AllocationAlignment alignment) { base::MutexGuard guard(&mutex_); return AllocateRaw(size_in_bytes, alignment); } LocalAllocationBuffer LocalAllocationBuffer::FromResult(Heap* heap, AllocationResult result, intptr_t size) { if (result.IsRetry()) return InvalidBuffer(); HeapObject obj; bool ok = result.To(&obj); USE(ok); DCHECK(ok); Address top = HeapObject::cast(obj)->address(); return LocalAllocationBuffer(heap, LinearAllocationArea(top, top + size)); } bool LocalAllocationBuffer::TryMerge(LocalAllocationBuffer* other) { if (allocation_info_.top() == other->allocation_info_.limit()) { allocation_info_.set_top(other->allocation_info_.top()); other->allocation_info_.Reset(kNullAddress, kNullAddress); return true; } return false; } bool LocalAllocationBuffer::TryFreeLast(HeapObject object, int object_size) { if (IsValid()) { const Address object_address = object->address(); if ((allocation_info_.top() - object_size) == object_address) { allocation_info_.set_top(object_address); return true; } } return false; } } // namespace internal } // namespace v8 #endif // V8_HEAP_SPACES_INL_H_