// Copyright 2020 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_MEMORY_ALLOCATOR_H_ #define V8_HEAP_MEMORY_ALLOCATOR_H_ #include <atomic> #include <memory> #include <unordered_map> #include <unordered_set> #include <vector> #include "include/v8-platform.h" #include "src/base/bounded-page-allocator.h" #include "src/base/export-template.h" #include "src/base/macros.h" #include "src/base/platform/mutex.h" #include "src/base/platform/semaphore.h" #include "src/heap/heap.h" #include "src/heap/memory-chunk.h" #include "src/heap/spaces.h" #include "src/tasks/cancelable-task.h" #include "src/utils/allocation.h" namespace v8 { namespace internal { class Heap; class Isolate; class ReadOnlyPage; // The process-wide singleton that keeps track of code range regions with the // intention to reuse free code range regions as a workaround for CFG memory // leaks (see crbug.com/870054). class CodeRangeAddressHint { public: // Returns the most recently freed code range start address for the given // size. If there is no such entry, then a random address is returned. V8_EXPORT_PRIVATE Address GetAddressHint(size_t code_range_size); V8_EXPORT_PRIVATE void NotifyFreedCodeRange(Address code_range_start, size_t code_range_size); private: base::Mutex mutex_; // A map from code range size to an array of recently freed code range // addresses. There should be O(1) different code range sizes. // The length of each array is limited by the peak number of code ranges, // which should be also O(1). std::unordered_map<size_t, std::vector<Address>> recently_freed_; }; // ---------------------------------------------------------------------------- // A space acquires chunks of memory from the operating system. The memory // allocator allocates and deallocates pages for the paged heap spaces and large // pages for large object space. class MemoryAllocator { public: // Unmapper takes care of concurrently unmapping and uncommitting memory // chunks. class Unmapper { public: class UnmapFreeMemoryTask; Unmapper(Heap* heap, MemoryAllocator* allocator) : heap_(heap), allocator_(allocator), pending_unmapping_tasks_semaphore_(0), pending_unmapping_tasks_(0), active_unmapping_tasks_(0) { chunks_[kRegular].reserve(kReservedQueueingSlots); chunks_[kPooled].reserve(kReservedQueueingSlots); } void AddMemoryChunkSafe(MemoryChunk* chunk) { if (!chunk->IsLargePage() && chunk->executable() != EXECUTABLE) { AddMemoryChunkSafe<kRegular>(chunk); } else { AddMemoryChunkSafe<kNonRegular>(chunk); } } MemoryChunk* TryGetPooledMemoryChunkSafe() { // Procedure: // (1) Try to get a chunk that was declared as pooled and already has // been uncommitted. // (2) Try to steal any memory chunk of kPageSize that would've been // unmapped. MemoryChunk* chunk = GetMemoryChunkSafe<kPooled>(); if (chunk == nullptr) { chunk = GetMemoryChunkSafe<kRegular>(); if (chunk != nullptr) { // For stolen chunks we need to manually free any allocated memory. chunk->ReleaseAllAllocatedMemory(); } } return chunk; } V8_EXPORT_PRIVATE void FreeQueuedChunks(); void CancelAndWaitForPendingTasks(); void PrepareForGC(); V8_EXPORT_PRIVATE void EnsureUnmappingCompleted(); V8_EXPORT_PRIVATE void TearDown(); size_t NumberOfCommittedChunks(); V8_EXPORT_PRIVATE int NumberOfChunks(); size_t CommittedBufferedMemory(); private: static const int kReservedQueueingSlots = 64; static const int kMaxUnmapperTasks = 4; enum ChunkQueueType { kRegular, // Pages of kPageSize that do not live in a CodeRange and // can thus be used for stealing. kNonRegular, // Large chunks and executable chunks. kPooled, // Pooled chunks, already uncommited and ready for reuse. kNumberOfChunkQueues, }; enum class FreeMode { kUncommitPooled, kReleasePooled, }; template <ChunkQueueType type> void AddMemoryChunkSafe(MemoryChunk* chunk) { base::MutexGuard guard(&mutex_); chunks_[type].push_back(chunk); } template <ChunkQueueType type> MemoryChunk* GetMemoryChunkSafe() { base::MutexGuard guard(&mutex_); if (chunks_[type].empty()) return nullptr; MemoryChunk* chunk = chunks_[type].back(); chunks_[type].pop_back(); return chunk; } bool MakeRoomForNewTasks(); template <FreeMode mode> void PerformFreeMemoryOnQueuedChunks(); void PerformFreeMemoryOnQueuedNonRegularChunks(); Heap* const heap_; MemoryAllocator* const allocator_; base::Mutex mutex_; std::vector<MemoryChunk*> chunks_[kNumberOfChunkQueues]; CancelableTaskManager::Id task_ids_[kMaxUnmapperTasks]; base::Semaphore pending_unmapping_tasks_semaphore_; intptr_t pending_unmapping_tasks_; std::atomic<intptr_t> active_unmapping_tasks_; friend class MemoryAllocator; }; enum AllocationMode { kRegular, kPooled, }; enum FreeMode { kFull, kAlreadyPooled, kPreFreeAndQueue, kPooledAndQueue, }; V8_EXPORT_PRIVATE static intptr_t GetCommitPageSize(); // Computes the memory area of discardable memory within a given memory area // [addr, addr+size) and returns the result as base::AddressRegion. If the // memory is not discardable base::AddressRegion is an empty region. V8_EXPORT_PRIVATE static base::AddressRegion ComputeDiscardMemoryArea( Address addr, size_t size); V8_EXPORT_PRIVATE MemoryAllocator(Isolate* isolate, size_t max_capacity, size_t code_range_size); V8_EXPORT_PRIVATE void TearDown(); // Allocates a Page from the allocator. AllocationMode is used to indicate // whether pooled allocation, which only works for MemoryChunk::kPageSize, // should be tried first. template <MemoryAllocator::AllocationMode alloc_mode = kRegular, typename SpaceType> EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Page* AllocatePage(size_t size, SpaceType* owner, Executability executable); LargePage* AllocateLargePage(size_t size, LargeObjectSpace* owner, Executability executable); ReadOnlyPage* AllocateReadOnlyPage(size_t size, ReadOnlySpace* owner); std::unique_ptr<::v8::PageAllocator::SharedMemoryMapping> RemapSharedPage( ::v8::PageAllocator::SharedMemory* shared_memory, Address new_address); template <MemoryAllocator::FreeMode mode = kFull> EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) void Free(MemoryChunk* chunk); void FreeReadOnlyPage(ReadOnlyPage* chunk); // Returns allocated spaces in bytes. size_t Size() const { return size_; } // Returns allocated executable spaces in bytes. size_t SizeExecutable() const { return size_executable_; } // Returns the maximum available bytes of heaps. size_t Available() const { const size_t size = Size(); return capacity_ < size ? 0 : capacity_ - size; } // Returns an indication of whether a pointer is in a space that has // been allocated by this MemoryAllocator. V8_INLINE bool IsOutsideAllocatedSpace(Address address) const { return address < lowest_ever_allocated_ || address >= highest_ever_allocated_; } // Returns a BasicMemoryChunk in which the memory region from commit_area_size // to reserve_area_size of the chunk area is reserved but not committed, it // could be committed later by calling MemoryChunk::CommitArea. V8_EXPORT_PRIVATE BasicMemoryChunk* AllocateBasicChunk( size_t reserve_area_size, size_t commit_area_size, Executability executable, BaseSpace* space); // Returns a MemoryChunk in which the memory region from commit_area_size to // reserve_area_size of the chunk area is reserved but not committed, it // could be committed later by calling MemoryChunk::CommitArea. V8_EXPORT_PRIVATE MemoryChunk* AllocateChunk(size_t reserve_area_size, size_t commit_area_size, Executability executable, BaseSpace* space); Address AllocateAlignedMemory(size_t reserve_size, size_t commit_size, size_t alignment, Executability executable, void* hint, VirtualMemory* controller); void FreeMemory(v8::PageAllocator* page_allocator, Address addr, size_t size); // Partially release |bytes_to_free| bytes starting at |start_free|. Note that // internally memory is freed from |start_free| to the end of the reservation. // Additional memory beyond the page is not accounted though, so // |bytes_to_free| is computed by the caller. void PartialFreeMemory(BasicMemoryChunk* chunk, Address start_free, size_t bytes_to_free, Address new_area_end); // Checks if an allocated MemoryChunk was intended to be used for executable // memory. bool IsMemoryChunkExecutable(MemoryChunk* chunk) { return executable_memory_.find(chunk) != executable_memory_.end(); } // Commit memory region owned by given reservation object. Returns true if // it succeeded and false otherwise. bool CommitMemory(VirtualMemory* reservation); // Uncommit memory region owned by given reservation object. Returns true if // it succeeded and false otherwise. bool UncommitMemory(VirtualMemory* reservation); // Zaps a contiguous block of memory [start..(start+size)[ with // a given zap value. void ZapBlock(Address start, size_t size, uintptr_t zap_value); V8_WARN_UNUSED_RESULT bool CommitExecutableMemory(VirtualMemory* vm, Address start, size_t commit_size, size_t reserved_size); // Page allocator instance for allocating non-executable pages. // Guaranteed to be a valid pointer. v8::PageAllocator* data_page_allocator() { return data_page_allocator_; } // Page allocator instance for allocating executable pages. // Guaranteed to be a valid pointer. v8::PageAllocator* code_page_allocator() { return code_page_allocator_; } // Returns page allocator suitable for allocating pages with requested // executability. v8::PageAllocator* page_allocator(Executability executable) { return executable == EXECUTABLE ? code_page_allocator_ : data_page_allocator_; } // A region of memory that may contain executable code including reserved // OS page with read-write access in the beginning. const base::AddressRegion& code_range() const { // |code_range_| >= |optional RW pages| + |code_page_allocator_instance_| DCHECK_IMPLIES(!code_range_.is_empty(), code_page_allocator_instance_); DCHECK_IMPLIES(!code_range_.is_empty(), code_range_.contains(code_page_allocator_instance_->begin(), code_page_allocator_instance_->size())); return code_range_; } Unmapper* unmapper() { return &unmapper_; } // Performs all necessary bookkeeping to free the memory, but does not free // it. void UnregisterMemory(MemoryChunk* chunk); void UnregisterMemory(BasicMemoryChunk* chunk, Executability executable = NOT_EXECUTABLE); void UnregisterSharedMemory(BasicMemoryChunk* chunk); void RegisterReadOnlyMemory(ReadOnlyPage* page); private: void InitializeCodePageAllocator(v8::PageAllocator* page_allocator, size_t requested); // PreFreeMemory logically frees the object, i.e., it unregisters the // memory, logs a delete event and adds the chunk to remembered unmapped // pages. void PreFreeMemory(MemoryChunk* chunk); // PerformFreeMemory can be called concurrently when PreFree was executed // before. void PerformFreeMemory(MemoryChunk* chunk); // See AllocatePage for public interface. Note that currently we only // support pools for NOT_EXECUTABLE pages of size MemoryChunk::kPageSize. template <typename SpaceType> MemoryChunk* AllocatePagePooled(SpaceType* owner); // Initializes pages in a chunk. Returns the first page address. // This function and GetChunkId() are provided for the mark-compact // collector to rebuild page headers in the from space, which is // used as a marking stack and its page headers are destroyed. Page* InitializePagesInChunk(int chunk_id, int pages_in_chunk, PagedSpace* owner); void UpdateAllocatedSpaceLimits(Address low, Address high) { // The use of atomic primitives does not guarantee correctness (wrt. // desired semantics) by default. The loop here ensures that we update the // values only if they did not change in between. Address ptr = lowest_ever_allocated_.load(std::memory_order_relaxed); while ((low < ptr) && !lowest_ever_allocated_.compare_exchange_weak( ptr, low, std::memory_order_acq_rel)) { } ptr = highest_ever_allocated_.load(std::memory_order_relaxed); while ((high > ptr) && !highest_ever_allocated_.compare_exchange_weak( ptr, high, std::memory_order_acq_rel)) { } } void RegisterExecutableMemoryChunk(MemoryChunk* chunk) { base::MutexGuard guard(&executable_memory_mutex_); DCHECK(chunk->IsFlagSet(MemoryChunk::IS_EXECUTABLE)); DCHECK_EQ(executable_memory_.find(chunk), executable_memory_.end()); executable_memory_.insert(chunk); } void UnregisterExecutableMemoryChunk(MemoryChunk* chunk) { base::MutexGuard guard(&executable_memory_mutex_); DCHECK_NE(executable_memory_.find(chunk), executable_memory_.end()); executable_memory_.erase(chunk); chunk->heap()->UnregisterUnprotectedMemoryChunk(chunk); } Isolate* isolate_; // This object controls virtual space reserved for code on the V8 heap. This // is only valid for 64-bit architectures where kRequiresCodeRange. VirtualMemory code_reservation_; // Page allocator used for allocating data pages. Depending on the // configuration it may be a page allocator instance provided by // v8::Platform or a BoundedPageAllocator (when pointer compression is // enabled). v8::PageAllocator* data_page_allocator_; // Page allocator used for allocating code pages. Depending on the // configuration it may be a page allocator instance provided by // v8::Platform or a BoundedPageAllocator (when pointer compression is // enabled or on those 64-bit architectures where pc-relative 32-bit // displacement can be used for call and jump instructions). v8::PageAllocator* code_page_allocator_; // A part of the |code_reservation_| that may contain executable code // including reserved page with read-write access in the beginning. // See details below. base::AddressRegion code_range_; // This unique pointer owns the instance of bounded code allocator // that controls executable pages allocation. It does not control the // optionally existing page in the beginning of the |code_range_|. // So, summarizing all above, the following conditions hold: // 1) |code_reservation_| >= |code_range_| // 2) |code_range_| >= |optional RW pages| + // |code_page_allocator_instance_|. 3) |code_reservation_| is // AllocatePageSize()-aligned 4) |code_page_allocator_instance_| is // MemoryChunk::kAlignment-aligned 5) |code_range_| is // CommitPageSize()-aligned std::unique_ptr<base::BoundedPageAllocator> code_page_allocator_instance_; // Maximum space size in bytes. size_t capacity_; // Allocated space size in bytes. std::atomic<size_t> size_; // Allocated executable space size in bytes. std::atomic<size_t> size_executable_; // We keep the lowest and highest addresses allocated as a quick way // of determining that pointers are outside the heap. The estimate is // conservative, i.e. not all addresses in 'allocated' space are allocated // to our heap. The range is [lowest, highest[, inclusive on the low end // and exclusive on the high end. std::atomic<Address> lowest_ever_allocated_; std::atomic<Address> highest_ever_allocated_; VirtualMemory last_chunk_; Unmapper unmapper_; // Data structure to remember allocated executable memory chunks. std::unordered_set<MemoryChunk*> executable_memory_; base::Mutex executable_memory_mutex_; friend class heap::TestCodePageAllocatorScope; friend class heap::TestMemoryAllocatorScope; DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryAllocator); }; extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Page* MemoryAllocator::AllocatePage<MemoryAllocator::kRegular, PagedSpace>( size_t size, PagedSpace* owner, Executability executable); extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Page* MemoryAllocator::AllocatePage<MemoryAllocator::kRegular, SemiSpace>( size_t size, SemiSpace* owner, Executability executable); extern template EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE) Page* MemoryAllocator::AllocatePage<MemoryAllocator::kPooled, SemiSpace>( size_t size, SemiSpace* owner, Executability executable); extern template EXPORT_TEMPLATE_DECLARE( V8_EXPORT_PRIVATE) void MemoryAllocator:: Free<MemoryAllocator::kFull>(MemoryChunk* chunk); extern template EXPORT_TEMPLATE_DECLARE( V8_EXPORT_PRIVATE) void MemoryAllocator:: Free<MemoryAllocator::kAlreadyPooled>(MemoryChunk* chunk); extern template EXPORT_TEMPLATE_DECLARE( V8_EXPORT_PRIVATE) void MemoryAllocator:: Free<MemoryAllocator::kPreFreeAndQueue>(MemoryChunk* chunk); extern template EXPORT_TEMPLATE_DECLARE( V8_EXPORT_PRIVATE) void MemoryAllocator:: Free<MemoryAllocator::kPooledAndQueue>(MemoryChunk* chunk); } // namespace internal } // namespace v8 #endif // V8_HEAP_MEMORY_ALLOCATOR_H_