diff options
Diffstat (limited to 'deps/v8/src/spaces.h')
| -rw-r--r-- | deps/v8/src/spaces.h | 1703 |
1 files changed, 1703 insertions, 0 deletions
diff --git a/deps/v8/src/spaces.h b/deps/v8/src/spaces.h new file mode 100644 index 000000000..3138cc360 --- /dev/null +++ b/deps/v8/src/spaces.h @@ -0,0 +1,1703 @@ +// Copyright 2006-2008 the V8 project authors. All rights reserved. +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following +// disclaimer in the documentation and/or other materials provided +// with the distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived +// from this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +#ifndef V8_SPACES_H_ +#define V8_SPACES_H_ + +#include "list-inl.h" +#include "log.h" + +namespace v8 { namespace internal { + +// ----------------------------------------------------------------------------- +// Heap structures: +// +// A JS heap consists of a young generation, an old generation, and a large +// object space. The young generation is divided into two semispaces. A +// scavenger implements Cheney's copying algorithm. The old generation is +// separated into a map space and an old object space. The map space contains +// all (and only) map objects, the rest of old objects go into the old space. +// The old generation is collected by a mark-sweep-compact collector. +// +// The semispaces of the young generation are contiguous. The old and map +// spaces consists of a list of pages. A page has a page header, a remembered +// set area, and an object area. A page size is deliberately chosen as 8K +// bytes. The first word of a page is an opaque page header that has the +// address of the next page and its ownership information. The second word may +// have the allocation top address of this page. The next 248 bytes are +// remembered sets. Heap objects are aligned to the pointer size (4 bytes). A +// remembered set bit corresponds to a pointer in the object area. +// +// There is a separate large object space for objects larger than +// Page::kMaxHeapObjectSize, so that they do not have to move during +// collection. The large object space is paged and uses the same remembered +// set implementation. Pages in large object space may be larger than 8K. +// +// NOTE: The mark-compact collector rebuilds the remembered set after a +// collection. It reuses first a few words of the remembered set for +// bookkeeping relocation information. + + +// Some assertion macros used in the debugging mode. + +#define ASSERT_PAGE_ALIGNED(address) \ + ASSERT((OffsetFrom(address) & Page::kPageAlignmentMask) == 0) + +#define ASSERT_OBJECT_ALIGNED(address) \ + ASSERT((OffsetFrom(address) & kObjectAlignmentMask) == 0) + +#define ASSERT_OBJECT_SIZE(size) \ + ASSERT((0 < size) && (size <= Page::kMaxHeapObjectSize)) + +#define ASSERT_PAGE_OFFSET(offset) \ + ASSERT((Page::kObjectStartOffset <= offset) \ + && (offset <= Page::kPageSize)) + +#define ASSERT_MAP_PAGE_INDEX(index) \ + ASSERT((0 <= index) && (index <= MapSpace::kMaxMapPageIndex)) + + +class PagedSpace; +class MemoryAllocator; +class AllocationInfo; + +// ----------------------------------------------------------------------------- +// A page normally has 8K bytes. Large object pages may be larger. A page +// address is always aligned to the 8K page size. A page is divided into +// three areas: the first two words are used for bookkeeping, the next 248 +// bytes are used as remembered set, and the rest of the page is the object +// area. +// +// Pointers are aligned to the pointer size (4 bytes), only 1 bit is needed +// for a pointer in the remembered set. Given an address, its remembered set +// bit position (offset from the start of the page) is calculated by dividing +// its page offset by 32. Therefore, the object area in a page starts at the +// 256th byte (8K/32). Bytes 0 to 255 do not need the remembered set, so that +// the first two words (64 bits) in a page can be used for other purposes. +// +// The mark-compact collector transforms a map pointer into a page index and a +// page offset. The map space can have up to 1024 pages, and 8M bytes (1024 * +// 8K) in total. Because a map pointer is aligned to the pointer size (4 +// bytes), 11 bits are enough to encode the page offset. 21 bits (10 for the +// page index + 11 for the offset in the page) are required to encode a map +// pointer. +// +// The only way to get a page pointer is by calling factory methods: +// Page* p = Page::FromAddress(addr); or +// Page* p = Page::FromAllocationTop(top); +class Page { + public: + // Returns the page containing a given address. The address ranges + // from [page_addr .. page_addr + kPageSize[ + // + // Note that this function only works for addresses in normal paged + // spaces and addresses in the first 8K of large object pages (ie, + // the start of large objects but not necessarily derived pointers + // within them). + INLINE(static Page* FromAddress(Address a)) { + return reinterpret_cast<Page*>(OffsetFrom(a) & ~kPageAlignmentMask); + } + + // Returns the page containing an allocation top. Because an allocation + // top address can be the upper bound of the page, we need to subtract + // it with kPointerSize first. The address ranges from + // [page_addr + kObjectStartOffset .. page_addr + kPageSize]. + INLINE(static Page* FromAllocationTop(Address top)) { + Page* p = FromAddress(top - kPointerSize); + ASSERT_PAGE_OFFSET(p->Offset(top)); + return p; + } + + // Returns the start address of this page. + Address address() { return reinterpret_cast<Address>(this); } + + // Checks whether this is a valid page address. + bool is_valid() { return address() != NULL; } + + // Returns the next page of this page. + inline Page* next_page(); + + // Return the end of allocation in this page. Undefined for unused pages. + inline Address AllocationTop(); + + // Returns the start address of the object area in this page. + Address ObjectAreaStart() { return address() + kObjectStartOffset; } + + // Returns the end address (exclusive) of the object area in this page. + Address ObjectAreaEnd() { return address() + Page::kPageSize; } + + // Returns the start address of the remembered set area. + Address RSetStart() { return address() + kRSetStartOffset; } + + // Returns the end address of the remembered set area (exclusive). + Address RSetEnd() { return address() + kRSetEndOffset; } + + // Checks whether an address is page aligned. + static bool IsAlignedToPageSize(Address a) { + return 0 == (OffsetFrom(a) & kPageAlignmentMask); + } + + // True if this page is a large object page. + bool IsLargeObjectPage() { return (is_normal_page & 0x1) == 0; } + + // Returns the offset of a given address to this page. + INLINE(int Offset(Address a)) { + int offset = a - address(); + ASSERT_PAGE_OFFSET(offset); + return offset; + } + + // Returns the address for a given offset to the this page. + Address OffsetToAddress(int offset) { + ASSERT_PAGE_OFFSET(offset); + return address() + offset; + } + + // --------------------------------------------------------------------- + // Remembered set support + + // Clears remembered set in this page. + inline void ClearRSet(); + + // Return the address of the remembered set word corresponding to an + // object address/offset pair, and the bit encoded as a single-bit + // mask in the output parameter 'bitmask'. + INLINE(static Address ComputeRSetBitPosition(Address address, int offset, + uint32_t* bitmask)); + + // Sets the corresponding remembered set bit for a given address. + INLINE(static void SetRSet(Address address, int offset)); + + // Clears the corresponding remembered set bit for a given address. + static inline void UnsetRSet(Address address, int offset); + + // Checks whether the remembered set bit for a given address is set. + static inline bool IsRSetSet(Address address, int offset); + +#ifdef DEBUG + // Use a state to mark whether remembered set space can be used for other + // purposes. + enum RSetState { IN_USE, NOT_IN_USE }; + static bool is_rset_in_use() { return rset_state_ == IN_USE; } + static void set_rset_state(RSetState state) { rset_state_ = state; } +#endif + + // 8K bytes per page. + static const int kPageSizeBits = 13; + + // Page size in bytes. This must be a multiple of the OS page size. + static const int kPageSize = 1 << kPageSizeBits; + + // Page size mask. + static const int kPageAlignmentMask = (1 << kPageSizeBits) - 1; + + // The end offset of the remembered set in a page + // (heaps are aligned to pointer size). + static const int kRSetEndOffset= kPageSize / kBitsPerPointer; + + // The start offset of the remembered set in a page. + static const int kRSetStartOffset = kRSetEndOffset / kBitsPerPointer; + + // The start offset of the object area in a page. + static const int kObjectStartOffset = kRSetEndOffset; + + // Object area size in bytes. + static const int kObjectAreaSize = kPageSize - kObjectStartOffset; + + // Maximum object size that fits in a page. + static const int kMaxHeapObjectSize = kObjectAreaSize; + + //--------------------------------------------------------------------------- + // Page header description. + // + // If a page is not in the large object space, the first word, + // opaque_header, encodes the next page address (aligned to kPageSize 8K) + // and the chunk number (0 ~ 8K-1). Only MemoryAllocator should use + // opaque_header. The value range of the opaque_header is [0..kPageSize[, + // or [next_page_start, next_page_end[. It cannot point to a valid address + // in the current page. If a page is in the large object space, the first + // word *may* (if the page start and large object chunk start are the + // same) contain the address of the next large object chunk. + int opaque_header; + + // If the page is not in the large object space, the low-order bit of the + // second word is set. If the page is in the large object space, the + // second word *may* (if the page start and large object chunk start are + // the same) contain the large object chunk size. In either case, the + // low-order bit for large object pages will be cleared. + int is_normal_page; + + // The following fields overlap with remembered set, they can only + // be used in the mark-compact collector when remembered set is not + // used. + + // The allocation pointer after relocating objects to this page. + Address mc_relocation_top; + + // The index of the page in its owner space. + int mc_page_index; + + // The forwarding address of the first live object in this page. + Address mc_first_forwarded; + +#ifdef DEBUG + private: + static RSetState rset_state_; // state of the remembered set +#endif +}; + + +// ---------------------------------------------------------------------------- +// Space is the abstract superclass for all allocation spaces. +class Space : public Malloced { + public: + Space(AllocationSpace id, Executability executable) + : id_(id), executable_(executable) {} + + virtual ~Space() {} + + // Does the space need executable memory? + Executability executable() { return executable_; } + + // Identity used in error reporting. + AllocationSpace identity() { return id_; } + + virtual int Size() = 0; + +#ifdef DEBUG + virtual void Verify() = 0; + virtual void Print() = 0; +#endif + + private: + AllocationSpace id_; + Executability executable_; +}; + + +// ---------------------------------------------------------------------------- +// A space acquires chunks of memory from the operating system. The memory +// allocator manages chunks for the paged heap spaces (old space and map +// space). A paged chunk consists of pages. Pages in a chunk have contiguous +// addresses and are linked as a list. +// +// The allocator keeps an initial chunk which is used for the new space. The +// leftover regions of the initial chunk are used for the initial chunks of +// old space and map space if they are big enough to hold at least one page. +// The allocator assumes that there is one old space and one map space, each +// expands the space by allocating kPagesPerChunk pages except the last +// expansion (before running out of space). The first chunk may contain fewer +// than kPagesPerChunk pages as well. +// +// The memory allocator also allocates chunks for the large object space, but +// they are managed by the space itself. The new space does not expand. + +class MemoryAllocator : public AllStatic { + public: + // Initializes its internal bookkeeping structures. + // Max capacity of the total space. + static bool Setup(int max_capacity); + + // Deletes valid chunks. + static void TearDown(); + + // Reserves an initial address range of virtual memory to be split between + // the two new space semispaces, the old space, and the map space. The + // memory is not yet committed or assigned to spaces and split into pages. + // The initial chunk is unmapped when the memory allocator is torn down. + // This function should only be called when there is not already a reserved + // initial chunk (initial_chunk_ should be NULL). It returns the start + // address of the initial chunk if successful, with the side effect of + // setting the initial chunk, or else NULL if unsuccessful and leaves the + // initial chunk NULL. + static void* ReserveInitialChunk(const size_t requested); + + // Commits pages from an as-yet-unmanaged block of virtual memory into a + // paged space. The block should be part of the initial chunk reserved via + // a call to ReserveInitialChunk. The number of pages is always returned in + // the output parameter num_pages. This function assumes that the start + // address is non-null and that it is big enough to hold at least one + // page-aligned page. The call always succeeds, and num_pages is always + // greater than zero. + static Page* CommitPages(Address start, size_t size, PagedSpace* owner, + int* num_pages); + + // Commit a contiguous block of memory from the initial chunk. Assumes that + // the address is not NULL, the size is greater than zero, and that the + // block is contained in the initial chunk. Returns true if it succeeded + // and false otherwise. + static bool CommitBlock(Address start, size_t size, Executability executable); + + // Attempts to allocate the requested (non-zero) number of pages from the + // OS. Fewer pages might be allocated than requested. If it fails to + // allocate memory for the OS or cannot allocate a single page, this + // function returns an invalid page pointer (NULL). The caller must check + // whether the returned page is valid (by calling Page::is_valid()). It is + // guaranteed that allocated pages have contiguous addresses. The actual + // number of allocated page is returned in the output parameter + // allocated_pages. + static Page* AllocatePages(int requested_pages, int* allocated_pages, + PagedSpace* owner); + + // Frees pages from a given page and after. If 'p' is the first page + // of a chunk, pages from 'p' are freed and this function returns an + // invalid page pointer. Otherwise, the function searches a page + // after 'p' that is the first page of a chunk. Pages after the + // found page are freed and the function returns 'p'. + static Page* FreePages(Page* p); + + // Allocates and frees raw memory of certain size. + // These are just thin wrappers around OS::Allocate and OS::Free, + // but keep track of allocated bytes as part of heap. + static void* AllocateRawMemory(const size_t requested, + size_t* allocated, + Executability executable); + static void FreeRawMemory(void* buf, size_t length); + + // Returns the maximum available bytes of heaps. + static int Available() { return capacity_ < size_ ? 0 : capacity_ - size_; } + + // Returns maximum available bytes that the old space can have. + static int MaxAvailable() { + return (Available() / Page::kPageSize) * Page::kObjectAreaSize; + } + + // Links two pages. + static inline void SetNextPage(Page* prev, Page* next); + + // Returns the next page of a given page. + static inline Page* GetNextPage(Page* p); + + // Checks whether a page belongs to a space. + static inline bool IsPageInSpace(Page* p, PagedSpace* space); + + // Returns the space that owns the given page. + static inline PagedSpace* PageOwner(Page* page); + + // Finds the first/last page in the same chunk as a given page. + static Page* FindFirstPageInSameChunk(Page* p); + static Page* FindLastPageInSameChunk(Page* p); + +#ifdef ENABLE_HEAP_PROTECTION + // Protect/unprotect a block of memory by marking it read-only/writable. + static inline void Protect(Address start, size_t size); + static inline void Unprotect(Address start, size_t size, + Executability executable); + + // Protect/unprotect a chunk given a page in the chunk. + static inline void ProtectChunkFromPage(Page* page); + static inline void UnprotectChunkFromPage(Page* page); +#endif + +#ifdef DEBUG + // Reports statistic info of the space. + static void ReportStatistics(); +#endif + + // Due to encoding limitation, we can only have 8K chunks. + static const int kMaxNofChunks = 1 << Page::kPageSizeBits; + // If a chunk has at least 32 pages, the maximum heap size is about + // 8 * 1024 * 32 * 8K = 2G bytes. + static const int kPagesPerChunk = 64; + static const int kChunkSize = kPagesPerChunk * Page::kPageSize; + + private: + // Maximum space size in bytes. + static int capacity_; + + // Allocated space size in bytes. + static int size_; + + // The initial chunk of virtual memory. + static VirtualMemory* initial_chunk_; + + // Allocated chunk info: chunk start address, chunk size, and owning space. + class ChunkInfo BASE_EMBEDDED { + public: + ChunkInfo() : address_(NULL), size_(0), owner_(NULL) {} + void init(Address a, size_t s, PagedSpace* o) { + address_ = a; + size_ = s; + owner_ = o; + } + Address address() { return address_; } + size_t size() { return size_; } + PagedSpace* owner() { return owner_; } + + private: + Address address_; + size_t size_; + PagedSpace* owner_; + }; + + // Chunks_, free_chunk_ids_ and top_ act as a stack of free chunk ids. + static List<ChunkInfo> chunks_; + static List<int> free_chunk_ids_; + static int max_nof_chunks_; + static int top_; + + // Push/pop a free chunk id onto/from the stack. + static void Push(int free_chunk_id); + static int Pop(); + static bool OutOfChunkIds() { return top_ == 0; } + + // Frees a chunk. + static void DeleteChunk(int chunk_id); + + // Basic check whether a chunk id is in the valid range. + static inline bool IsValidChunkId(int chunk_id); + + // Checks whether a chunk id identifies an allocated chunk. + static inline bool IsValidChunk(int chunk_id); + + // Returns the chunk id that a page belongs to. + static inline int GetChunkId(Page* p); + + // True if the address lies in the initial chunk. + static inline bool InInitialChunk(Address address); + + // 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. + static Page* InitializePagesInChunk(int chunk_id, int pages_in_chunk, + PagedSpace* owner); +}; + + +// ----------------------------------------------------------------------------- +// Interface for heap object iterator to be implemented by all object space +// object iterators. +// +// NOTE: The space specific object iterators also implements the own has_next() +// and next() methods which are used to avoid using virtual functions +// iterating a specific space. + +class ObjectIterator : public Malloced { + public: + virtual ~ObjectIterator() { } + + virtual bool has_next_object() = 0; + virtual HeapObject* next_object() = 0; +}; + + +// ----------------------------------------------------------------------------- +// Heap object iterator in new/old/map spaces. +// +// A HeapObjectIterator iterates objects from a given address to the +// top of a space. The given address must be below the current +// allocation pointer (space top). If the space top changes during +// iteration (because of allocating new objects), the iterator does +// not iterate new objects. The caller function must create a new +// iterator starting from the old top in order to visit these new +// objects. Heap::Scavenage() is such an example. + +class HeapObjectIterator: public ObjectIterator { + public: + // Creates a new object iterator in a given space. If a start + // address is not given, the iterator starts from the space bottom. + // If the size function is not given, the iterator calls the default + // Object::Size(). + explicit HeapObjectIterator(PagedSpace* space); + HeapObjectIterator(PagedSpace* space, HeapObjectCallback size_func); + HeapObjectIterator(PagedSpace* space, Address start); + HeapObjectIterator(PagedSpace* space, + Address start, + HeapObjectCallback size_func); + + inline bool has_next(); + inline HeapObject* next(); + + // implementation of ObjectIterator. + virtual bool has_next_object() { return has_next(); } + virtual HeapObject* next_object() { return next(); } + + private: + Address cur_addr_; // current iteration point + Address end_addr_; // end iteration point + Address cur_limit_; // current page limit + HeapObjectCallback size_func_; // size function + Page* end_page_; // caches the page of the end address + + // Slow path of has_next, checks whether there are more objects in + // the next page. + bool HasNextInNextPage(); + + // Initializes fields. + void Initialize(Address start, Address end, HeapObjectCallback size_func); + +#ifdef DEBUG + // Verifies whether fields have valid values. + void Verify(); +#endif +}; + + +// ----------------------------------------------------------------------------- +// A PageIterator iterates pages in a space. +// +// The PageIterator class provides three modes for iterating pages in a space: +// PAGES_IN_USE iterates pages that are in use by the allocator; +// PAGES_USED_BY_GC iterates pages that hold relocated objects during a +// mark-compact collection; +// ALL_PAGES iterates all pages in the space. + +class PageIterator BASE_EMBEDDED { + public: + enum Mode {PAGES_IN_USE, PAGES_USED_BY_MC, ALL_PAGES}; + + PageIterator(PagedSpace* space, Mode mode); + + inline bool has_next(); + inline Page* next(); + + private: + Page* cur_page_; // next page to return + Page* stop_page_; // page where to stop +}; + + +// ----------------------------------------------------------------------------- +// A space has a list of pages. The next page can be accessed via +// Page::next_page() call. The next page of the last page is an +// invalid page pointer. A space can expand and shrink dynamically. + +// An abstraction of allocation and relocation pointers in a page-structured +// space. +class AllocationInfo { + public: + Address top; // current allocation top + Address limit; // current allocation limit + +#ifdef DEBUG + bool VerifyPagedAllocation() { + return (Page::FromAllocationTop(top) == Page::FromAllocationTop(limit)) + && (top <= limit); + } +#endif +}; + + +// An abstraction of the accounting statistics of a page-structured space. +// The 'capacity' of a space is the number of object-area bytes (ie, not +// including page bookkeeping structures) currently in the space. The 'size' +// of a space is the number of allocated bytes, the 'waste' in the space is +// the number of bytes that are not allocated and not available to +// allocation without reorganizing the space via a GC (eg, small blocks due +// to internal fragmentation, top of page areas in map space), and the bytes +// 'available' is the number of unallocated bytes that are not waste. The +// capacity is the sum of size, waste, and available. +// +// The stats are only set by functions that ensure they stay balanced. These +// functions increase or decrease one of the non-capacity stats in +// conjunction with capacity, or else they always balance increases and +// decreases to the non-capacity stats. +class AllocationStats BASE_EMBEDDED { + public: + AllocationStats() { Clear(); } + + // Zero out all the allocation statistics (ie, no capacity). + void Clear() { + capacity_ = 0; + available_ = 0; + size_ = 0; + waste_ = 0; + } + + // Reset the allocation statistics (ie, available = capacity with no + // wasted or allocated bytes). + void Reset() { + available_ = capacity_; + size_ = 0; + waste_ = 0; + } + + // Accessors for the allocation statistics. + int Capacity() { return capacity_; } + int Available() { return available_; } + int Size() { return size_; } + int Waste() { return waste_; } + + // Grow the space by adding available bytes. + void ExpandSpace(int size_in_bytes) { + capacity_ += size_in_bytes; + available_ += size_in_bytes; + } + + // Shrink the space by removing available bytes. + void ShrinkSpace(int size_in_bytes) { + capacity_ -= size_in_bytes; + available_ -= size_in_bytes; + } + + // Allocate from available bytes (available -> size). + void AllocateBytes(int size_in_bytes) { + available_ -= size_in_bytes; + size_ += size_in_bytes; + } + + // Free allocated bytes, making them available (size -> available). + void DeallocateBytes(int size_in_bytes) { + size_ -= size_in_bytes; + available_ += size_in_bytes; + } + + // Waste free bytes (available -> waste). + void WasteBytes(int size_in_bytes) { + available_ -= size_in_bytes; + waste_ += size_in_bytes; + } + + // Consider the wasted bytes to be allocated, as they contain filler + // objects (waste -> size). + void FillWastedBytes(int size_in_bytes) { + waste_ -= size_in_bytes; + size_ += size_in_bytes; + } + + private: + int capacity_; + int available_; + int size_; + int waste_; +}; + + +class PagedSpace : public Space { + public: + // Creates a space with a maximum capacity, and an id. + PagedSpace(int max_capacity, AllocationSpace id, Executability executable); + + virtual ~PagedSpace() {} + + // Set up the space using the given address range of virtual memory (from + // the memory allocator's initial chunk) if possible. If the block of + // addresses is not big enough to contain a single page-aligned page, a + // fresh chunk will be allocated. + bool Setup(Address start, size_t size); + + // Returns true if the space has been successfully set up and not + // subsequently torn down. + bool HasBeenSetup(); + + // Cleans up the space, frees all pages in this space except those belonging + // to the initial chunk, uncommits addresses in the initial chunk. + void TearDown(); + + // Checks whether an object/address is in this space. + inline bool Contains(Address a); + bool Contains(HeapObject* o) { return Contains(o->address()); } + + // Given an address occupied by a live object, return that object if it is + // in this space, or Failure::Exception() if it is not. The implementation + // iterates over objects in the page containing the address, the cost is + // linear in the number of objects in the page. It may be slow. + Object* FindObject(Address addr); + + // Checks whether page is currently in use by this space. + bool IsUsed(Page* page); + + // Clears remembered sets of pages in this space. + void ClearRSet(); + + // Prepares for a mark-compact GC. + virtual void PrepareForMarkCompact(bool will_compact) = 0; + + virtual Address PageAllocationTop(Page* page) = 0; + + // Current capacity without growing (Size() + Available() + Waste()). + int Capacity() { return accounting_stats_.Capacity(); } + + // Available bytes without growing. + int Available() { return accounting_stats_.Available(); } + + // Allocated bytes in this space. + virtual int Size() { return accounting_stats_.Size(); } + + // Wasted bytes due to fragmentation and not recoverable until the + // next GC of this space. + int Waste() { return accounting_stats_.Waste(); } + + // Returns the address of the first object in this space. + Address bottom() { return first_page_->ObjectAreaStart(); } + + // Returns the allocation pointer in this space. + Address top() { return allocation_info_.top; } + + // Allocate the requested number of bytes in the space if possible, return a + // failure object if not. + inline Object* AllocateRaw(int size_in_bytes); + + // Allocate the requested number of bytes for relocation during mark-compact + // collection. + inline Object* MCAllocateRaw(int size_in_bytes); + + + // --------------------------------------------------------------------------- + // Mark-compact collection support functions + + // Set the relocation point to the beginning of the space. + void MCResetRelocationInfo(); + + // Writes relocation info to the top page. + void MCWriteRelocationInfoToPage() { + TopPageOf(mc_forwarding_info_)->mc_relocation_top = mc_forwarding_info_.top; + } + + // Computes the offset of a given address in this space to the beginning + // of the space. + int MCSpaceOffsetForAddress(Address addr); + + // Updates the allocation pointer to the relocation top after a mark-compact + // collection. + virtual void MCCommitRelocationInfo() = 0; + + // Releases half of unused pages. + void Shrink(); + + // Ensures that the capacity is at least 'capacity'. Returns false on failure. + bool EnsureCapacity(int capacity); + +#ifdef ENABLE_HEAP_PROTECTION + // Protect/unprotect the space by marking it read-only/writable. + void Protect(); + void Unprotect(); +#endif + +#ifdef DEBUG + // Print meta info and objects in this space. + virtual void Print(); + + // Report code object related statistics + void CollectCodeStatistics(); + static void ReportCodeStatistics(); + static void ResetCodeStatistics(); +#endif + + protected: + // Maximum capacity of this space. + int max_capacity_; + + // Accounting information for this space. + AllocationStats accounting_stats_; + + // The first page in this space. + Page* first_page_; + + // Normal allocation information. + AllocationInfo allocation_info_; + + // Relocation information during mark-compact collections. + AllocationInfo mc_forwarding_info_; + + // Sets allocation pointer to a page bottom. + static void SetAllocationInfo(AllocationInfo* alloc_info, Page* p); + + // Returns the top page specified by an allocation info structure. + static Page* TopPageOf(AllocationInfo alloc_info) { + return Page::FromAllocationTop(alloc_info.limit); + } + + // Expands the space by allocating a fixed number of pages. Returns false if + // it cannot allocate requested number of pages from OS. Newly allocated + // pages are append to the last_page; + bool Expand(Page* last_page); + + // Generic fast case allocation function that tries linear allocation in + // the top page of 'alloc_info'. Returns NULL on failure. + inline HeapObject* AllocateLinearly(AllocationInfo* alloc_info, + int size_in_bytes); + + // During normal allocation or deserialization, roll to the next page in + // the space (there is assumed to be one) and allocate there. This + // function is space-dependent. + virtual HeapObject* AllocateInNextPage(Page* current_page, + int size_in_bytes) = 0; + + // Slow path of AllocateRaw. This function is space-dependent. + virtual HeapObject* SlowAllocateRaw(int size_in_bytes) = 0; + + // Slow path of MCAllocateRaw. + HeapObject* SlowMCAllocateRaw(int size_in_bytes); + +#ifdef DEBUG + void DoPrintRSet(const char* space_name); +#endif + private: + // Returns the page of the allocation pointer. + Page* AllocationTopPage() { return TopPageOf(allocation_info_); } + + // Returns a pointer to the page of the relocation pointer. + Page* MCRelocationTopPage() { return TopPageOf(mc_forwarding_info_); } + +#ifdef DEBUG + // Returns the number of total pages in this space. + int CountTotalPages(); +#endif + + friend class PageIterator; +}; + + +#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING) +// HistogramInfo class for recording a single "bar" of a histogram. This +// class is used for collecting statistics to print to stdout (when compiled +// with DEBUG) or to the log file (when compiled with +// ENABLE_LOGGING_AND_PROFILING). +class HistogramInfo BASE_EMBEDDED { + public: + HistogramInfo() : number_(0), bytes_(0) {} + + const char* name() { return name_; } + void set_name(const char* name) { name_ = name; } + + int number() { return number_; } + void increment_number(int num) { number_ += num; } + + int bytes() { return bytes_; } + void increment_bytes(int size) { bytes_ += size; } + + // Clear the number of objects and size fields, but not the name. + void clear() { + number_ = 0; + bytes_ = 0; + } + + private: + const char* name_; + int number_; + int bytes_; +}; +#endif + + +// ----------------------------------------------------------------------------- +// SemiSpace in young generation +// +// A semispace is a contiguous chunk of memory. The mark-compact collector +// uses the memory in the from space as a marking stack when tracing live +// objects. + +class SemiSpace : public Space { + public: + // Constructor. + SemiSpace() :Space(NEW_SPACE, NOT_EXECUTABLE) { + start_ = NULL; + age_mark_ = NULL; + } + + // Sets up the semispace using the given chunk. + bool Setup(Address start, int initial_capacity, int maximum_capacity); + + // Tear down the space. Heap memory was not allocated by the space, so it + // is not deallocated here. + void TearDown(); + + // True if the space has been set up but not torn down. + bool HasBeenSetup() { return start_ != NULL; } + + // Double the size of the semispace by committing extra virtual memory. + // Assumes that the caller has checked that the semispace has not reached + // its maximum capacity (and thus there is space available in the reserved + // address range to grow). + bool Double(); + + // Returns the start address of the space. + Address low() { return start_; } + // Returns one past the end address of the space. + Address high() { return low() + capacity_; } + + // Age mark accessors. + Address age_mark() { return age_mark_; } + void set_age_mark(Address mark) { age_mark_ = mark; } + + // True if the address is in the address range of this semispace (not + // necessarily below the allocation pointer). + bool Contains(Address a) { + return (reinterpret_cast<uint32_t>(a) & address_mask_) + == reinterpret_cast<uint32_t>(start_); + } + + // True if the object is a heap object in the address range of this + // semispace (not necessarily below the allocation pointer). + bool Contains(Object* o) { + return (reinterpret_cast<uint32_t>(o) & object_mask_) == object_expected_; + } + + // The offset of an address from the beginning of the space. + int SpaceOffsetForAddress(Address addr) { return addr - low(); } + + // If we don't have this here then SemiSpace will be abstract. However + // it should never be called. + virtual int Size() { + UNREACHABLE(); + return 0; + } + +#ifdef DEBUG + virtual void Print(); + virtual void Verify(); +#endif + + private: + // The current and maximum capacity of the space. + int capacity_; + int maximum_capacity_; + + // The start address of the space. + Address start_; + // Used to govern object promotion during mark-compact collection. + Address age_mark_; + + // Masks and comparison values to test for containment in this semispace. + uint32_t address_mask_; + uint32_t object_mask_; + uint32_t object_expected_; + + public: + TRACK_MEMORY("SemiSpace") +}; + + +// A SemiSpaceIterator is an ObjectIterator that iterates over the active +// semispace of the heap's new space. It iterates over the objects in the +// semispace from a given start address (defaulting to the bottom of the +// semispace) to the top of the semispace. New objects allocated after the +// iterator is created are not iterated. +class SemiSpaceIterator : public ObjectIterator { + public: + // Create an iterator over the objects in the given space. If no start + // address is given, the iterator starts from the bottom of the space. If + // no size function is given, the iterator calls Object::Size(). + explicit SemiSpaceIterator(NewSpace* space); + SemiSpaceIterator(NewSpace* space, HeapObjectCallback size_func); + SemiSpaceIterator(NewSpace* space, Address start); + + bool has_next() {return current_ < limit_; } + + HeapObject* next() { + ASSERT(has_next()); + + HeapObject* object = HeapObject::FromAddress(current_); + int size = (size_func_ == NULL) ? object->Size() : size_func_(object); + ASSERT_OBJECT_SIZE(size); + + current_ += size; + return object; + } + + // Implementation of the ObjectIterator functions. + virtual bool has_next_object() { return has_next(); } + virtual HeapObject* next_object() { return next(); } + + private: + void Initialize(NewSpace* space, Address start, Address end, + HeapObjectCallback size_func); + + // The semispace. + SemiSpace* space_; + // The current iteration point. + Address current_; + // The end of iteration. + Address limit_; + // The callback function. + HeapObjectCallback size_func_; +}; + + +// ----------------------------------------------------------------------------- +// The young generation space. +// +// The new space consists of a contiguous pair of semispaces. It simply +// forwards most functions to the appropriate semispace. + +class NewSpace : public Space { + public: + // Constructor. + NewSpace() : Space(NEW_SPACE, NOT_EXECUTABLE) {} + + // Sets up the new space using the given chunk. + bool Setup(Address start, int size); + + // Tears down the space. Heap memory was not allocated by the space, so it + // is not deallocated here. + void TearDown(); + + // True if the space has been set up but not torn down. + bool HasBeenSetup() { + return to_space_.HasBeenSetup() && from_space_.HasBeenSetup(); + } + + // Flip the pair of spaces. + void Flip(); + + // Doubles the capacity of the semispaces. Assumes that they are not at + // their maximum capacity. Returns a flag indicating success or failure. + bool Double(); + + // True if the address or object lies in the address range of either + // semispace (not necessarily below the allocation pointer). + bool Contains(Address a) { + return (reinterpret_cast<uint32_t>(a) & address_mask_) + == reinterpret_cast<uint32_t>(start_); + } + bool Contains(Object* o) { + return (reinterpret_cast<uint32_t>(o) & object_mask_) == object_expected_; + } + + // Return the allocated bytes in the active semispace. + virtual int Size() { return top() - bottom(); } + // Return the current capacity of a semispace. + int Capacity() { return capacity_; } + // Return the available bytes without growing in the active semispace. + int Available() { return Capacity() - Size(); } + + // Return the maximum capacity of a semispace. + int MaximumCapacity() { return maximum_capacity_; } + + // Return the address of the allocation pointer in the active semispace. + Address top() { return allocation_info_.top; } + // Return the address of the first object in the active semispace. + Address bottom() { return to_space_.low(); } + + // Get the age mark of the inactive semispace. + Address age_mark() { return from_space_.age_mark(); } + // Set the age mark in the active semispace. + void set_age_mark(Address mark) { to_space_.set_age_mark(mark); } + + // The start address of the space and a bit mask. Anding an address in the + // new space with the mask will result in the start address. + Address start() { return start_; } + uint32_t mask() { return address_mask_; } + + // The allocation top and limit addresses. + Address* allocation_top_address() { return &allocation_info_.top; } + Address* allocation_limit_address() { return &allocation_info_.limit; } + + Object* AllocateRaw(int size_in_bytes) { + return AllocateRawInternal(size_in_bytes, &allocation_info_); + } + + // Allocate the requested number of bytes for relocation during mark-compact + // collection. + Object* MCAllocateRaw(int size_in_bytes) { + return AllocateRawInternal(size_in_bytes, &mc_forwarding_info_); + } + + // Reset the allocation pointer to the beginning of the active semispace. + void ResetAllocationInfo(); + // Reset the reloction pointer to the bottom of the inactive semispace in + // preparation for mark-compact collection. + void MCResetRelocationInfo(); + // Update the allocation pointer in the active semispace after a + // mark-compact collection. + void MCCommitRelocationInfo(); + + // Get the extent of the inactive semispace (for use as a marking stack). + Address FromSpaceLow() { return from_space_.low(); } + Address FromSpaceHigh() { return from_space_.high(); } + + // Get the extent of the active semispace (to sweep newly copied objects + // during a scavenge collection). + Address ToSpaceLow() { return to_space_.low(); } + Address ToSpaceHigh() { return to_space_.high(); } + + // Offsets from the beginning of the semispaces. + int ToSpaceOffsetForAddress(Address a) { + return to_space_.SpaceOffsetForAddress(a); + } + int FromSpaceOffsetForAddress(Address a) { + return from_space_.SpaceOffsetForAddress(a); + } + + // True if the object is a heap object in the address range of the + // respective semispace (not necessarily below the allocation pointer of the + // semispace). + bool ToSpaceContains(Object* o) { return to_space_.Contains(o); } + bool FromSpaceContains(Object* o) { return from_space_.Contains(o); } + + bool ToSpaceContains(Address a) { return to_space_.Contains(a); } + bool FromSpaceContains(Address a) { return from_space_.Contains(a); } + +#ifdef ENABLE_HEAP_PROTECTION + // Protect/unprotect the space by marking it read-only/writable. + virtual void Protect(); + virtual void Unprotect(); +#endif + +#ifdef DEBUG + // Verify the active semispace. + virtual void Verify(); + // Print the active semispace. + virtual void Print() { to_space_.Print(); } +#endif + +#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING) + // Iterates the active semispace to collect statistics. + void CollectStatistics(); + // Reports previously collected statistics of the active semispace. + void ReportStatistics(); + // Clears previously collected statistics. + void ClearHistograms(); + + // Record the allocation or promotion of a heap object. Note that we don't + // record every single allocation, but only those that happen in the + // to space during a scavenge GC. + void RecordAllocation(HeapObject* obj); + void RecordPromotion(HeapObject* obj); +#endif + + private: + // The current and maximum capacities of a semispace. + int capacity_; + int maximum_capacity_; + + // The semispaces. + SemiSpace to_space_; + SemiSpace from_space_; + + // Start address and bit mask for containment testing. + Address start_; + uint32_t address_mask_; + uint32_t object_mask_; + uint32_t object_expected_; + + // Allocation pointer and limit for normal allocation and allocation during + // mark-compact collection. + AllocationInfo allocation_info_; + AllocationInfo mc_forwarding_info_; + +#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING) + HistogramInfo* allocated_histogram_; + HistogramInfo* promoted_histogram_; +#endif + + // Implementation of AllocateRaw and MCAllocateRaw. + inline Object* AllocateRawInternal(int size_in_bytes, + AllocationInfo* alloc_info); + + friend class SemiSpaceIterator; + + public: + TRACK_MEMORY("NewSpace") +}; + + +// ----------------------------------------------------------------------------- +// Free lists for old object spaces +// +// Free-list nodes are free blocks in the heap. They look like heap objects +// (free-list node pointers have the heap object tag, and they have a map like +// a heap object). They have a size and a next pointer. The next pointer is +// the raw address of the next free list node (or NULL). +class FreeListNode: public HeapObject { + public: + // Obtain a free-list node from a raw address. This is not a cast because + // it does not check nor require that the first word at the address is a map + // pointer. + static FreeListNode* FromAddress(Address address) { + return reinterpret_cast<FreeListNode*>(HeapObject::FromAddress(address)); + } + + // Set the size in bytes, which can be read with HeapObject::Size(). This + // function also writes a map to the first word of the block so that it + // looks like a heap object to the garbage collector and heap iteration + // functions. + void set_size(int size_in_bytes); + + // Accessors for the next field. + inline Address next(); + inline void set_next(Address next); + + private: + static const int kNextOffset = Array::kHeaderSize; + + DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListNode); +}; + + +// The free list for the old space. +class OldSpaceFreeList BASE_EMBEDDED { + public: + explicit OldSpaceFreeList(AllocationSpace owner); + + // Clear the free list. + void Reset(); + + // Return the number of bytes available on the free list. + int available() { return available_; } + + // Place a node on the free list. The block of size 'size_in_bytes' + // starting at 'start' is placed on the free list. The return value is the + // number of bytes that have been lost due to internal fragmentation by + // freeing the block. Bookkeeping information will be written to the block, + // ie, its contents will be destroyed. The start address should be word + // aligned, and the size should be a non-zero multiple of the word size. + int Free(Address start, int size_in_bytes); + + // Allocate a block of size 'size_in_bytes' from the free list. The block + // is unitialized. A failure is returned if no block is available. The + // number of bytes lost to fragmentation is returned in the output parameter + // 'wasted_bytes'. The size should be a non-zero multiple of the word size. + Object* Allocate(int size_in_bytes, int* wasted_bytes); + + private: + // The size range of blocks, in bytes. (Smaller allocations are allowed, but + // will always result in waste.) + static const int kMinBlockSize = Array::kHeaderSize + kPointerSize; + static const int kMaxBlockSize = Page::kMaxHeapObjectSize; + + // The identity of the owning space, for building allocation Failure + // objects. + AllocationSpace owner_; + + // Total available bytes in all blocks on this free list. + int available_; + + // Blocks are put on exact free lists in an array, indexed by size in words. + // The available sizes are kept in an increasingly ordered list. Entries + // corresponding to sizes < kMinBlockSize always have an empty free list + // (but index kHead is used for the head of the size list). + struct SizeNode { + // Address of the head FreeListNode of the implied block size or NULL. + Address head_node_; + // Size (words) of the next larger available size if head_node_ != NULL. + int next_size_; + }; + static const int kFreeListsLength = kMaxBlockSize / kPointerSize + 1; + SizeNode free_[kFreeListsLength]; + + // Sentinel elements for the size list. Real elements are in ]kHead..kEnd[. + static const int kHead = kMinBlockSize / kPointerSize - 1; + static const int kEnd = kMaxInt; + + // We keep a "finger" in the size list to speed up a common pattern: + // repeated requests for the same or increasing sizes. + int finger_; + + // Starting from *prev, find and return the smallest size >= index (words), + // or kEnd. Update *prev to be the largest size < index, or kHead. + int FindSize(int index, int* prev) { + int cur = free_[*prev].next_size_; + while (cur < index) { + *prev = cur; + cur = free_[cur].next_size_; + } + return cur; + } + + // Remove an existing element from the size list. + void RemoveSize(int index) { + int prev = kHead; + int cur = FindSize(index, &prev); + ASSERT(cur == index); + free_[prev].next_size_ = free_[cur].next_size_; + finger_ = prev; + } + + // Insert a new element into the size list. + void InsertSize(int index) { + int prev = kHead; + int cur = FindSize(index, &prev); + ASSERT(cur != index); + free_[prev].next_size_ = index; + free_[index].next_size_ = cur; + } + + // The size list is not updated during a sequence of calls to Free, but is + // rebuilt before the next allocation. + void RebuildSizeList(); + bool needs_rebuild_; + +#ifdef DEBUG + // Does this free list contain a free block located at the address of 'node'? + bool Contains(FreeListNode* node); +#endif + + DISALLOW_COPY_AND_ASSIGN(OldSpaceFreeList); +}; + + +// The free list for the map space. +class MapSpaceFreeList BASE_EMBEDDED { + public: + explicit MapSpaceFreeList(AllocationSpace owner); + + // Clear the free list. + void Reset(); + + // Return the number of bytes available on the free list. + int available() { return available_; } + + // Place a node on the free list. The block starting at 'start' (assumed to + // have size Map::kSize) is placed on the free list. Bookkeeping + // information will be written to the block, ie, its contents will be + // destroyed. The start address should be word aligned. + void Free(Address start); + + // Allocate a map-sized block from the free list. The block is unitialized. + // A failure is returned if no block is available. + Object* Allocate(); + + private: + // Available bytes on the free list. + int available_; + + // The head of the free list. + Address head_; + + // The identity of the owning space, for building allocation Failure + // objects. + AllocationSpace owner_; + + DISALLOW_COPY_AND_ASSIGN(MapSpaceFreeList); +}; + + +// ----------------------------------------------------------------------------- +// Old object space (excluding map objects) + +class OldSpace : public PagedSpace { + public: + // Creates an old space object with a given maximum capacity. + // The constructor does not allocate pages from OS. + explicit OldSpace(int max_capacity, + AllocationSpace id, + Executability executable) + : PagedSpace(max_capacity, id, executable), free_list_(id) { + } + + // The bytes available on the free list (ie, not above the linear allocation + // pointer). + int AvailableFree() { return free_list_.available(); } + + // The top of allocation in a page in this space. Undefined if page is unused. + virtual Address PageAllocationTop(Page* page) { + return page == TopPageOf(allocation_info_) ? top() : page->ObjectAreaEnd(); + } + + // Give a block of memory to the space's free list. It might be added to + // the free list or accounted as waste. + void Free(Address start, int size_in_bytes) { + int wasted_bytes = free_list_.Free(start, size_in_bytes); + accounting_stats_.DeallocateBytes(size_in_bytes); + accounting_stats_.WasteBytes(wasted_bytes); + } + + // Prepare for full garbage collection. Resets the relocation pointer and + // clears the free list. + virtual void PrepareForMarkCompact(bool will_compact); + + // Adjust the top of relocation pointer to point to the end of the object + // given by 'address' and 'size_in_bytes'. Move it to the next page if + // necessary, ensure that it points to the address, then increment it by the + // size. + void MCAdjustRelocationEnd(Address address, int size_in_bytes); + + // Updates the allocation pointer to the relocation top after a mark-compact + // collection. + virtual void MCCommitRelocationInfo(); + +#ifdef DEBUG + // Verify integrity of this space. + virtual void Verify(); + + // Reports statistics for the space + void ReportStatistics(); + // Dump the remembered sets in the space to stdout. + void PrintRSet(); +#endif + + protected: + // Virtual function in the superclass. Slow path of AllocateRaw. + HeapObject* SlowAllocateRaw(int size_in_bytes); + + // Virtual function in the superclass. Allocate linearly at the start of + // the page after current_page (there is assumed to be one). + HeapObject* AllocateInNextPage(Page* current_page, int size_in_bytes); + + private: + // The space's free list. + OldSpaceFreeList free_list_; + + // During relocation, we keep a pointer to the most recently relocated + // object in order to know when to move to the next page. + Address mc_end_of_relocation_; + + public: + TRACK_MEMORY("OldSpace") +}; + + +// ----------------------------------------------------------------------------- +// Old space for all map objects + +class MapSpace : public PagedSpace { + public: + // Creates a map space object with a maximum capacity. + explicit MapSpace(int max_capacity, AllocationSpace id) + : PagedSpace(max_capacity, id, NOT_EXECUTABLE), free_list_(id) { } + + // The top of allocation in a page in this space. Undefined if page is unused. + virtual Address PageAllocationTop(Page* page) { + return page == TopPageOf(allocation_info_) ? top() + : page->ObjectAreaEnd() - kPageExtra; + } + + // Give a map-sized block of memory to the space's free list. + void Free(Address start) { + free_list_.Free(start); + accounting_stats_.DeallocateBytes(Map::kSize); + } + + // Given an index, returns the page address. + Address PageAddress(int page_index) { return page_addresses_[page_index]; } + + // Prepares for a mark-compact GC. + virtual void PrepareForMarkCompact(bool will_compact); + + // Updates the allocation pointer to the relocation top after a mark-compact + // collection. + virtual void MCCommitRelocationInfo(); + +#ifdef DEBUG + // Verify integrity of this space. + virtual void Verify(); + + // Reports statistic info of the space + void ReportStatistics(); + // Dump the remembered sets in the space to stdout. + void PrintRSet(); +#endif + + // Constants. + static const int kMapPageIndexBits = 10; + static const int kMaxMapPageIndex = (1 << kMapPageIndexBits) - 1; + + static const int kPageExtra = Page::kObjectAreaSize % Map::kSize; + + protected: + // Virtual function in the superclass. Slow path of AllocateRaw. + HeapObject* SlowAllocateRaw(int size_in_bytes); + + // Virtual function in the superclass. Allocate linearly at the start of + // the page after current_page (there is assumed to be one). + HeapObject* AllocateInNextPage(Page* current_page, int size_in_bytes); + + private: + // The space's free list. + MapSpaceFreeList free_list_; + + // An array of page start address in a map space. + Address page_addresses_[kMaxMapPageIndex + 1]; + + public: + TRACK_MEMORY("MapSpace") +}; + + +// ----------------------------------------------------------------------------- +// Large objects ( > Page::kMaxHeapObjectSize ) are allocated and managed by +// the large object space. A large object is allocated from OS heap with +// extra padding bytes (Page::kPageSize + Page::kObjectStartOffset). +// A large object always starts at Page::kObjectStartOffset to a page. +// Large objects do not move during garbage collections. + +// A LargeObjectChunk holds exactly one large object page with exactly one +// large object. +class LargeObjectChunk { + public: + // Allocates a new LargeObjectChunk that contains a large object page + // (Page::kPageSize aligned) that has at least size_in_bytes (for a large + // object and possibly extra remembered set words) bytes after the object + // area start of that page. The allocated chunk size is set in the output + // parameter chunk_size. + static LargeObjectChunk* New(int size_in_bytes, + size_t* chunk_size, + Executability executable); + + // Interpret a raw address as a large object chunk. + static LargeObjectChunk* FromAddress(Address address) { + return reinterpret_cast<LargeObjectChunk*>(address); + } + + // Returns the address of this chunk. + Address address() { return reinterpret_cast<Address>(this); } + + // Accessors for the fields of the chunk. + LargeObjectChunk* next() { return next_; } + void set_next(LargeObjectChunk* chunk) { next_ = chunk; } + + size_t size() { return size_; } + void set_size(size_t size_in_bytes) { size_ = size_in_bytes; } + + // Returns the object in this chunk. + inline HeapObject* GetObject(); + + // Given a requested size (including any extra remembered set words), + // returns the physical size of a chunk to be allocated. + static int ChunkSizeFor(int size_in_bytes); + + // Given a chunk size, returns the object size it can accommodate (not + // including any extra remembered set words). Used by + // LargeObjectSpace::Available. Note that this can overestimate the size + // of object that will fit in a chunk---if the object requires extra + // remembered set words (eg, for large fixed arrays), the actual object + // size for the chunk will be smaller than reported by this function. + static int ObjectSizeFor(int chunk_size) { + if (chunk_size <= (Page::kPageSize + Page::kObjectStartOffset)) return 0; + return chunk_size - Page::kPageSize - Page::kObjectStartOffset; + } + + private: + // A pointer to the next large object chunk in the space or NULL. + LargeObjectChunk* next_; + + // The size of this chunk. + size_t size_; + + public: + TRACK_MEMORY("LargeObjectChunk") +}; + + +class LargeObjectSpace : public Space { + public: + explicit LargeObjectSpace(AllocationSpace id); + virtual ~LargeObjectSpace() {} + + // Initializes internal data structures. + bool Setup(); + + // Releases internal resources, frees objects in this space. + void TearDown(); + + // Allocates a (non-FixedArray, non-Code) large object. + Object* AllocateRaw(int size_in_bytes); + // Allocates a large Code object. + Object* AllocateRawCode(int size_in_bytes); + // Allocates a large FixedArray. + Object* AllocateRawFixedArray(int size_in_bytes); + + // Available bytes for objects in this space, not including any extra + // remembered set words. + int Available() { + return LargeObjectChunk::ObjectSizeFor(MemoryAllocator::Available()); + } + + virtual int Size() { + return size_; + } + + int PageCount() { + return page_count_; + } + + // Finds an object for a given address, returns Failure::Exception() + // if it is not found. The function iterates through all objects in this + // space, may be slow. + Object* FindObject(Address a); + + // Clears remembered sets. + void ClearRSet(); + + // Iterates objects whose remembered set bits are set. + void IterateRSet(ObjectSlotCallback func); + + // Frees unmarked objects. + void FreeUnmarkedObjects(); + + // Checks whether a heap object is in this space; O(1). + bool Contains(HeapObject* obj); + + // Checks whether the space is empty. + bool IsEmpty() { return first_chunk_ == NULL; } + +#ifdef ENABLE_HEAP_PROTECTION + // Protect/unprotect the space by marking it read-only/writable. + void Protect(); + void Unprotect(); +#endif + +#ifdef DEBUG + virtual void Verify(); + virtual void Print(); + void ReportStatistics(); + void CollectCodeStatistics(); + // Dump the remembered sets in the space to stdout. + void PrintRSet(); +#endif + // Checks whether an address is in the object area in this space. It + // iterates all objects in the space. May be slow. + bool SlowContains(Address addr) { return !FindObject(addr)->IsFailure(); } + + private: + // The head of the linked list of large object chunks. + LargeObjectChunk* first_chunk_; + int size_; // allocated bytes + int page_count_; // number of chunks + + + // Shared implementation of AllocateRaw, AllocateRawCode and + // AllocateRawFixedArray. + Object* AllocateRawInternal(int requested_size, + int object_size, + Executability executable); + + // Returns the number of extra bytes (rounded up to the nearest full word) + // required for extra_object_bytes of extra pointers (in bytes). + static inline int ExtraRSetBytesFor(int extra_object_bytes); + + friend class LargeObjectIterator; + + public: + TRACK_MEMORY("LargeObjectSpace") +}; + + +class LargeObjectIterator: public ObjectIterator { + public: + explicit LargeObjectIterator(LargeObjectSpace* space); + LargeObjectIterator(LargeObjectSpace* space, HeapObjectCallback size_func); + + bool has_next() { return current_ != NULL; } + HeapObject* next(); + + // implementation of ObjectIterator. + virtual bool has_next_object() { return has_next(); } + virtual HeapObject* next_object() { return next(); } + + private: + LargeObjectChunk* current_; + HeapObjectCallback size_func_; +}; + + +} } // namespace v8::internal + +#endif // V8_SPACES_H_ |