CSE2410 Fall 2014 Bounce

// Copyright 2011 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 "allocation.h"

#include "hashmap.h"

#include "list.h"

#include "log.h"

#include "platform/mutex.h"

#include "v8utils.h"

namespace v8 {

namespace internal {

class Isolate;

// -----------------------------------------------------------------------------

// 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 and an 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. Pages in large object space

// may be larger than the page size.

//

// A store-buffer based write barrier is used to keep track of intergenerational

// references.  See store-buffer.h.

//

// During scavenges and mark-sweep collections we sometimes (after a store

// buffer overflow) iterate intergenerational pointers without decoding heap

// object maps so if the page belongs to old pointer space or large object

// space it is essential to guarantee that the page does not contain any

// garbage pointers to new space: every pointer aligned word which satisfies

// the Heap::InNewSpace() predicate must be a pointer to a live heap object in

// new space. Thus objects in old pointer and large object spaces should have a

// special layout (e.g. no bare integer fields). This requirement does not

// apply to map space which is iterated in a special fashion. However we still

// require pointer fields of dead maps to be cleaned.

//

// To enable lazy cleaning of old space pages we can mark chunks of the page

// as being garbage.  Garbage sections are marked with a special map.  These

// sections are skipped when scanning the page, even if we are otherwise

// scanning without regard for object boundaries.  Garbage sections are chained

// together to form a free list after a GC.  Garbage sections created outside

// of GCs by object trunctation etc. may not be in the free list chain.  Very

// small free spaces are ignored, they need only be cleaned of bogus pointers

// into new space.

//

// Each page may have up to one special garbage section.  The start of this

// section is denoted by the top field in the space.  The end of the section

// is denoted by the limit field in the space.  This special garbage section

// is not marked with a free space map in the data.  The point of this section

// is to enable linear allocation without having to constantly update the byte

// array every time the top field is updated and a new object is created.  The

// special garbage section is not in the chain of garbage sections.

//

// Since the top and limit fields are in the space, not the page, only one page

// has a special garbage section, and if the top and limit are equal then there

// is no special garbage section.

// 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::kMaxNonCodeHeapObjectSize))

#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;

class Space;

class FreeList;

class MemoryChunk;

class MarkBit {

 public:

  typedef uint32_t CellType;

  inline MarkBit(CellType* cell, CellType mask, bool data_only)

      : cell_(cell), mask_(mask), data_only_(data_only) { }

  inline CellType* cell() { return cell_; }

  inline CellType mask() { return mask_; }

#ifdef DEBUG

  bool operator==(const MarkBit& other) {

    return cell_ == other.cell_ && mask_ == other.mask_;

  }

#endif

  inline void Set() { *cell_ |= mask_; }

  inline bool Get() { return (*cell_ & mask_) != 0; }

  inline void Clear() { *cell_ &= ~mask_; }

  inline bool data_only() { return data_only_; }

  inline MarkBit Next() {

    CellType new_mask = mask_ << 1;

    if (new_mask == 0) {

      return MarkBit(cell_ + 1, 1, data_only_);

    } else {

      return MarkBit(cell_, new_mask, data_only_);

    }

  }

 private:

  CellType* cell_;

  CellType mask_;

  // This boolean indicates that the object is in a data-only space with no

  // pointers.  This enables some optimizations when marking.

  // It is expected that this field is inlined and turned into control flow

  // at the place where the MarkBit object is created.

  bool data_only_;

};

// Bitmap is a sequence of cells each containing fixed number of bits.

class Bitmap {

 public:

  static const uint32_t kBitsPerCell = 32;

  static const uint32_t kBitsPerCellLog2 = 5;

  static const uint32_t kBitIndexMask = kBitsPerCell - 1;

  static const uint32_t kBytesPerCell = kBitsPerCell / kBitsPerByte;

  static const uint32_t kBytesPerCellLog2 = kBitsPerCellLog2 - kBitsPerByteLog2;

  static const size_t kLength =

    (1 << kPageSizeBits) >> (kPointerSizeLog2);

  static const size_t kSize =

    (1 << kPageSizeBits) >> (kPointerSizeLog2 + kBitsPerByteLog2);

  static int CellsForLength(int length) {

    return (length + kBitsPerCell - 1) >> kBitsPerCellLog2;

  }

  int CellsCount() {

    return CellsForLength(kLength);

  }

  static int SizeFor(int cells_count) {

    return sizeof(MarkBit::CellType) * cells_count;

  }

  INLINE(static uint32_t IndexToCell(uint32_t index)) {

    return index >> kBitsPerCellLog2;

  }

  INLINE(static uint32_t CellToIndex(uint32_t index)) {

    return index << kBitsPerCellLog2;

  }

  INLINE(static uint32_t CellAlignIndex(uint32_t index)) {

    return (index + kBitIndexMask) & ~kBitIndexMask;

  }

  INLINE(MarkBit::CellType* cells()) {

    return reinterpret_cast<MarkBit::CellType*>(this);

  }

  INLINE(Address address()) {

    return reinterpret_cast<Address>(this);

  }

  INLINE(static Bitmap* FromAddress(Address addr)) {

    return reinterpret_cast<Bitmap*>(addr);

  }

  inline MarkBit MarkBitFromIndex(uint32_t index, bool data_only = false) {

    MarkBit::CellType mask = 1 << (index & kBitIndexMask);

    MarkBit::CellType* cell = this->cells() + (index >> kBitsPerCellLog2);

    return MarkBit(cell, mask, data_only);

  }

  static inline void Clear(MemoryChunk* chunk);

  static void PrintWord(uint32_t word, uint32_t himask = 0) {

    for (uint32_t mask = 1; mask != 0; mask <<= 1) {

      if ((mask & himask) != 0) PrintF("[");

      PrintF((mask & word) ? "1" : "0");

      if ((mask & himask) != 0) PrintF("]");

    }

  }

  class CellPrinter {

   public:

    CellPrinter() : seq_start(0), seq_type(0), seq_length(0) { }

    void Print(uint32_t pos, uint32_t cell) {

      if (cell == seq_type) {

        seq_length++;

        return;

      }

      Flush();

      if (IsSeq(cell)) {

        seq_start = pos;

        seq_length = 0;

        seq_type = cell;

        return;

      }

      PrintF("%d: ", pos);

      PrintWord(cell);

      PrintF("\n");

    }

    void Flush() {

      if (seq_length > 0) {

        PrintF("%d: %dx%d\n",

               seq_start,

               seq_type == 0 ? 0 : 1,

               seq_length * kBitsPerCell);

        seq_length = 0;

      }

    }

    static bool IsSeq(uint32_t cell) { return cell == 0 || cell == 0xFFFFFFFF; }

   private:

    uint32_t seq_start;

    uint32_t seq_type;

    uint32_t seq_length;

  };

  void Print() {

    CellPrinter printer;

    for (int i = 0; i < CellsCount(); i++) {

      printer.Print(i, cells()[i]);

    }

    printer.Flush();

    PrintF("\n");

  }

  bool IsClean() {

    for (int i = 0; i < CellsCount(); i++) {

      if (cells()[i] != 0) {

        return false;

      }

    }

    return true;

  }

};

class SkipList;

class SlotsBuffer;

// MemoryChunk represents a memory region owned by a specific space.

// It is divided into the header and the body. Chunk start is always

// 1MB aligned. Start of the body is aligned so it can accommodate

// any heap object.

class MemoryChunk {

 public:

  // Only works if the pointer is in the first kPageSize of the MemoryChunk.

  static MemoryChunk* FromAddress(Address a) {

    return reinterpret_cast<MemoryChunk*>(OffsetFrom(a) & ~kAlignmentMask);

  }

  // Only works for addresses in pointer spaces, not data or code spaces.

  static inline MemoryChunk* FromAnyPointerAddress(Heap* heap, Address addr);

  Address address() { return reinterpret_cast<Address>(this); }

  bool is_valid() { return address() != NULL; }

  MemoryChunk* next_chunk() const { return next_chunk_; }

  MemoryChunk* prev_chunk() const { return prev_chunk_; }

  void set_next_chunk(MemoryChunk* next) { next_chunk_ = next; }

  void set_prev_chunk(MemoryChunk* prev) { prev_chunk_ = prev; }

  Space* owner() const {

    if ((reinterpret_cast<intptr_t>(owner_) & kFailureTagMask) ==

        kFailureTag) {

      return reinterpret_cast<Space*>(reinterpret_cast<intptr_t>(owner_) -

                                      kFailureTag);

    } else {

      return NULL;

    }

  }

  void set_owner(Space* space) {

    ASSERT((reinterpret_cast<intptr_t>(space) & kFailureTagMask) == 0);

    owner_ = reinterpret_cast<Address>(space) + kFailureTag;

    ASSERT((reinterpret_cast<intptr_t>(owner_) & kFailureTagMask) ==

           kFailureTag);

  }

  VirtualMemory* reserved_memory() {

    return &reservation_;

  }

  void InitializeReservedMemory() {

    reservation_.Reset();

  }

  void set_reserved_memory(VirtualMemory* reservation) {

    ASSERT_NOT_NULL(reservation);

    reservation_.TakeControl(reservation);

  }

  bool scan_on_scavenge() { return IsFlagSet(SCAN_ON_SCAVENGE); }

  void initialize_scan_on_scavenge(bool scan) {

    if (scan) {

      SetFlag(SCAN_ON_SCAVENGE);

    } else {

      ClearFlag(SCAN_ON_SCAVENGE);

    }

  }

  inline void set_scan_on_scavenge(bool scan);

  int store_buffer_counter() { return store_buffer_counter_; }

  void set_store_buffer_counter(int counter) {

    store_buffer_counter_ = counter;

  }

  bool Contains(Address addr) {

    return addr >= area_start() && addr < area_end();

  }

  // Checks whether addr can be a limit of addresses in this page.

  // It's a limit if it's in the page, or if it's just after the

  // last byte of the page.

  bool ContainsLimit(Address addr) {

    return addr >= area_start() && addr <= area_end();

  }

  // Every n write barrier invocations we go to runtime even though

  // we could have handled it in generated code.  This lets us check

  // whether we have hit the limit and should do some more marking.

  static const int kWriteBarrierCounterGranularity = 500;

  enum MemoryChunkFlags {

    IS_EXECUTABLE,

    ABOUT_TO_BE_FREED,

    POINTERS_TO_HERE_ARE_INTERESTING,

    POINTERS_FROM_HERE_ARE_INTERESTING,

    SCAN_ON_SCAVENGE,

    IN_FROM_SPACE,  // Mutually exclusive with IN_TO_SPACE.

    IN_TO_SPACE,    // All pages in new space has one of these two set.

    NEW_SPACE_BELOW_AGE_MARK,

    CONTAINS_ONLY_DATA,

    EVACUATION_CANDIDATE,

    RESCAN_ON_EVACUATION,

    // Pages swept precisely can be iterated, hitting only the live objects.

    // Whereas those swept conservatively cannot be iterated over. Both flags

    // indicate that marking bits have been cleared by the sweeper, otherwise

    // marking bits are still intact.

    WAS_SWEPT_PRECISELY,

    WAS_SWEPT_CONSERVATIVELY,

    // Large objects can have a progress bar in their page header. These object

    // are scanned in increments and will be kept black while being scanned.

    // Even if the mutator writes to them they will be kept black and a white

    // to grey transition is performed in the value.

    HAS_PROGRESS_BAR,

    // Last flag, keep at bottom.

    NUM_MEMORY_CHUNK_FLAGS

  };

  static const int kPointersToHereAreInterestingMask =

      1 << POINTERS_TO_HERE_ARE_INTERESTING;

  static const int kPointersFromHereAreInterestingMask =

      1 << POINTERS_FROM_HERE_ARE_INTERESTING;

  static const int kEvacuationCandidateMask =

      1 << EVACUATION_CANDIDATE;

  static const int kSkipEvacuationSlotsRecordingMask =

      (1 << EVACUATION_CANDIDATE) |

      (1 << RESCAN_ON_EVACUATION) |

      (1 << IN_FROM_SPACE) |

      (1 << IN_TO_SPACE);

  void SetFlag(int flag) {

    flags_ |= static_cast<uintptr_t>(1) << flag;

  }

  void ClearFlag(int flag) {

    flags_ &= ~(static_cast<uintptr_t>(1) << flag);

  }

  void SetFlagTo(int flag, bool value) {

    if (value) {

      SetFlag(flag);

    } else {

      ClearFlag(flag);

    }

  }

  bool IsFlagSet(int flag) {

    return (flags_ & (static_cast<uintptr_t>(1) << flag)) != 0;

  }

  // Set or clear multiple flags at a time. The flags in the mask

  // are set to the value in "flags", the rest retain the current value

  // in flags_.

  void SetFlags(intptr_t flags, intptr_t mask) {

    flags_ = (flags_ & ~mask) | (flags & mask);

  }

  // Return all current flags.

  intptr_t GetFlags() { return flags_; }

  intptr_t parallel_sweeping() const {

    return parallel_sweeping_;

  }

  void set_parallel_sweeping(intptr_t state) {

    parallel_sweeping_ = state;

  }

  bool TryParallelSweeping() {

    return NoBarrier_CompareAndSwap(&parallel_sweeping_, 1, 0) == 1;

  }

  // Manage live byte count (count of bytes known to be live,

  // because they are marked black).

  void ResetLiveBytes() {

    if (FLAG_gc_verbose) {

      PrintF("ResetLiveBytes:%p:%x->0\n",

             static_cast<void*>(this), live_byte_count_);

    }

    live_byte_count_ = 0;

  }

  void IncrementLiveBytes(int by) {

    if (FLAG_gc_verbose) {

      printf("UpdateLiveBytes:%p:%x%c=%x->%x\n",

             static_cast<void*>(this), live_byte_count_,

             ((by < 0) ? '-' : '+'), ((by < 0) ? -by : by),

             live_byte_count_ + by);

    }

    live_byte_count_ += by;

    ASSERT_LE(static_cast<unsigned>(live_byte_count_), size_);

  }

  int LiveBytes() {

    ASSERT(static_cast<unsigned>(live_byte_count_) <= size_);

    return live_byte_count_;

  }

  int write_barrier_counter() {

    return static_cast<int>(write_barrier_counter_);

  }

  void set_write_barrier_counter(int counter) {

    write_barrier_counter_ = counter;

  }

  int progress_bar() {

    ASSERT(IsFlagSet(HAS_PROGRESS_BAR));

    return progress_bar_;

  }

  void set_progress_bar(int progress_bar) {

    ASSERT(IsFlagSet(HAS_PROGRESS_BAR));

    progress_bar_ = progress_bar;

  }

  void ResetProgressBar() {

    if (IsFlagSet(MemoryChunk::HAS_PROGRESS_BAR)) {

      set_progress_bar(0);

      ClearFlag(MemoryChunk::HAS_PROGRESS_BAR);

    }

  }

  bool IsLeftOfProgressBar(Object** slot) {

    Address slot_address = reinterpret_cast<Address>(slot);

    ASSERT(slot_address > this->address());

    return (slot_address - (this->address() + kObjectStartOffset)) <

           progress_bar();

  }

  static void IncrementLiveBytesFromGC(Address address, int by) {

    MemoryChunk::FromAddress(address)->IncrementLiveBytes(by);

  }

  static void IncrementLiveBytesFromMutator(Address address, int by);

  static const intptr_t kAlignment =

      (static_cast<uintptr_t>(1) << kPageSizeBits);

  static const intptr_t kAlignmentMask = kAlignment - 1;

  static const intptr_t kSizeOffset = kPointerSize + kPointerSize;

  static const intptr_t kLiveBytesOffset =

     kSizeOffset + kPointerSize + kPointerSize + kPointerSize +

     kPointerSize + kPointerSize +

     kPointerSize + kPointerSize + kPointerSize + kIntSize;

  static const size_t kSlotsBufferOffset = kLiveBytesOffset + kIntSize;

  static const size_t kWriteBarrierCounterOffset =

      kSlotsBufferOffset + kPointerSize + kPointerSize;

  static const size_t kHeaderSize = kWriteBarrierCounterOffset + kPointerSize +

                                    kIntSize + kIntSize + kPointerSize +

                                    5 * kPointerSize;

  static const int kBodyOffset =

      CODE_POINTER_ALIGN(kHeaderSize + Bitmap::kSize);

  // The start offset of the object area in a page. Aligned to both maps and

  // code alignment to be suitable for both.  Also aligned to 32 words because

  // the marking bitmap is arranged in 32 bit chunks.

  static const int kObjectStartAlignment = 32 * kPointerSize;

  static const int kObjectStartOffset = kBodyOffset - 1 +

      (kObjectStartAlignment - (kBodyOffset - 1) % kObjectStartAlignment);

  size_t size() const { return size_; }

  void set_size(size_t size) {

    size_ = size;

  }

  void SetArea(Address area_start, Address area_end) {

    area_start_ = area_start;

    area_end_ = area_end;

  }

  Executability executable() {

    return IsFlagSet(IS_EXECUTABLE) ? EXECUTABLE : NOT_EXECUTABLE;

  }

  bool ContainsOnlyData() {

    return IsFlagSet(CONTAINS_ONLY_DATA);

  }

  bool InNewSpace() {

    return (flags_ & ((1 << IN_FROM_SPACE) | (1 << IN_TO_SPACE))) != 0;

  }

  bool InToSpace() {

    return IsFlagSet(IN_TO_SPACE);

  }

  bool InFromSpace() {

    return IsFlagSet(IN_FROM_SPACE);

  }

  // ---------------------------------------------------------------------

  // Markbits support

  inline Bitmap* markbits() {

    return Bitmap::FromAddress(address() + kHeaderSize);

  }

  void PrintMarkbits() { markbits()->Print(); }

  inline uint32_t AddressToMarkbitIndex(Address addr) {

    return static_cast<uint32_t>(addr - this->address()) >> kPointerSizeLog2;

  }

  inline static uint32_t FastAddressToMarkbitIndex(Address addr) {

    const intptr_t offset =

        reinterpret_cast<intptr_t>(addr) & kAlignmentMask;

    return static_cast<uint32_t>(offset) >> kPointerSizeLog2;

  }

  inline Address MarkbitIndexToAddress(uint32_t index) {

    return this->address() + (index << kPointerSizeLog2);

  }

  void InsertAfter(MemoryChunk* other);

  void Unlink();

  inline Heap* heap() { return heap_; }

  static const int kFlagsOffset = kPointerSize * 3;

  bool IsEvacuationCandidate() { return IsFlagSet(EVACUATION_CANDIDATE); }

  bool ShouldSkipEvacuationSlotRecording() {

    return (flags_ & kSkipEvacuationSlotsRecordingMask) != 0;

  }

  inline SkipList* skip_list() {

    return skip_list_;

  }

  inline void set_skip_list(SkipList* skip_list) {

    skip_list_ = skip_list;

  }

  inline SlotsBuffer* slots_buffer() {

    return slots_buffer_;

  }

  inline SlotsBuffer** slots_buffer_address() {

    return &slots_buffer_;

  }

  void MarkEvacuationCandidate() {

    ASSERT(slots_buffer_ == NULL);

    SetFlag(EVACUATION_CANDIDATE);

  }

  void ClearEvacuationCandidate() {

    ASSERT(slots_buffer_ == NULL);

    ClearFlag(EVACUATION_CANDIDATE);

  }

  Address area_start() { return area_start_; }

  Address area_end() { return area_end_; }

  int area_size() {

    return static_cast<int>(area_end() - area_start());

  }

  bool CommitArea(size_t requested);

  // Approximate amount of physical memory committed for this chunk.

  size_t CommittedPhysicalMemory() {

    return high_water_mark_;

  }

  static inline void UpdateHighWaterMark(Address mark);

 protected:

  MemoryChunk* next_chunk_;

  MemoryChunk* prev_chunk_;

  size_t size_;

  intptr_t flags_;

  // Start and end of allocatable memory on this chunk.

  Address area_start_;

  Address area_end_;

  // If the chunk needs to remember its memory reservation, it is stored here.

  VirtualMemory reservation_;

  // The identity of the owning space.  This is tagged as a failure pointer, but

  // no failure can be in an object, so this can be distinguished from any entry

  // in a fixed array.

  Address owner_;

  Heap* heap_;

  // Used by the store buffer to keep track of which pages to mark scan-on-

  // scavenge.

  int store_buffer_counter_;

  // Count of bytes marked black on page.

  int live_byte_count_;

  SlotsBuffer* slots_buffer_;

  SkipList* skip_list_;

  intptr_t write_barrier_counter_;

  // Used by the incremental marker to keep track of the scanning progress in

  // large objects that have a progress bar and are scanned in increments.

  int progress_bar_;

  // Assuming the initial allocation on a page is sequential,

  // count highest number of bytes ever allocated on the page.

  int high_water_mark_;

  intptr_t parallel_sweeping_;

  // PagedSpace free-list statistics.

  intptr_t available_in_small_free_list_;

  intptr_t available_in_medium_free_list_;

  intptr_t available_in_large_free_list_;

  intptr_t available_in_huge_free_list_;

  intptr_t non_available_small_blocks_;

  static MemoryChunk* Initialize(Heap* heap,

                                 Address base,

                                 size_t size,

                                 Address area_start,

                                 Address area_end,

                                 Executability executable,

                                 Space* owner);

  friend class MemoryAllocator;

};

STATIC_CHECK(sizeof(MemoryChunk) <= MemoryChunk::kHeaderSize);

// -----------------------------------------------------------------------------

// A page is a memory chunk of a size 1MB. Large object pages may be larger.

//

// 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 MemoryChunk {

 public:

  // Returns the page containing a given address. The address ranges

  // from [page_addr .. page_addr + kPageSize[

  // This only works if the object is in fact in a page.  See also MemoryChunk::

  // FromAddress() and FromAnyAddress().

  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);

    return p;

  }

  // Returns the next page in the chain of pages owned by a space.

  inline Page* next_page();

  inline Page* prev_page();

  inline void set_next_page(Page* page);

  inline void set_prev_page(Page* page);

  // Checks whether an address is page aligned.

  static bool IsAlignedToPageSize(Address a) {

    return 0 == (OffsetFrom(a) & kPageAlignmentMask);

  }

  // Returns the offset of a given address to this page.

  INLINE(int Offset(Address a)) {

    int offset = static_cast<int>(a - address());

    return offset;

  }

  // Returns the address for a given offset to the this page.

  Address OffsetToAddress(int offset) {

    ASSERT_PAGE_OFFSET(offset);

    return address() + offset;

  }

  // ---------------------------------------------------------------------

  // Page size in bytes.  This must be a multiple of the OS page size.

  static const int kPageSize = 1 << kPageSizeBits;

  // Object area size in bytes.

  static const int kNonCodeObjectAreaSize = kPageSize - kObjectStartOffset;

  // Maximum object size that fits in a page. Objects larger than that size

  // are allocated in large object space and are never moved in memory. This

  // also applies to new space allocation, since objects are never migrated

  // from new space to large object space.  Takes double alignment into account.

  static const int kMaxNonCodeHeapObjectSize =

      kNonCodeObjectAreaSize - kPointerSize;

  // Page size mask.

  static const intptr_t kPageAlignmentMask = (1 << kPageSizeBits) - 1;

  inline void ClearGCFields();

  static inline Page* Initialize(Heap* heap,

                                 MemoryChunk* chunk,

                                 Executability executable,

                                 PagedSpace* owner);

  void InitializeAsAnchor(PagedSpace* owner);

  bool WasSweptPrecisely() { return IsFlagSet(WAS_SWEPT_PRECISELY); }

  bool WasSweptConservatively() { return IsFlagSet(WAS_SWEPT_CONSERVATIVELY); }

  bool WasSwept() { return WasSweptPrecisely() || WasSweptConservatively(); }

  void MarkSweptPrecisely() { SetFlag(WAS_SWEPT_PRECISELY); }

  void MarkSweptConservatively() { SetFlag(WAS_SWEPT_CONSERVATIVELY); }

  void ClearSweptPrecisely() { ClearFlag(WAS_SWEPT_PRECISELY); }

  void ClearSweptConservatively() { ClearFlag(WAS_SWEPT_CONSERVATIVELY); }

  void ResetFreeListStatistics();

#define FRAGMENTATION_STATS_ACCESSORS(type, name) \

  type name() { return name##_; }                 \

  void set_##name(type name) { name##_ = name; }  \

  void add_##name(type name) { name##_ += name; }

  FRAGMENTATION_STATS_ACCESSORS(intptr_t, non_available_small_blocks)

  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_small_free_list)

  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_medium_free_list)

  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_large_free_list)

  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_huge_free_list)

#undef FRAGMENTATION_STATS_ACCESSORS

#ifdef DEBUG

  void Print();

#endif  // DEBUG

  friend class MemoryAllocator;

};

STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize);

class LargePage : public MemoryChunk {

 public:

  HeapObject* GetObject() {

    return HeapObject::FromAddress(area_start());

  }

  inline LargePage* next_page() const {

    return static_cast<LargePage*>(next_chunk());

  }

  inline void set_next_page(LargePage* page) {

    set_next_chunk(page);

  }

 private:

  static inline LargePage* Initialize(Heap* heap, MemoryChunk* chunk);

  friend class MemoryAllocator;

};

STATIC_CHECK(sizeof(LargePage) <= MemoryChunk::kHeaderSize);

// ----------------------------------------------------------------------------

// Space is the abstract superclass for all allocation spaces.

class Space : public Malloced {

 public:

  Space(Heap* heap, AllocationSpace id, Executability executable)

      : heap_(heap), id_(id), executable_(executable) {}

  virtual ~Space() {}

  Heap* heap() const { return heap_; }

  // Does the space need executable memory?

  Executability executable() { return executable_; }

  // Identity used in error reporting.

  AllocationSpace identity() { return id_; }

  // Returns allocated size.

  virtual intptr_t Size() = 0;

  // Returns size of objects. Can differ from the allocated size

  // (e.g. see LargeObjectSpace).

  virtual intptr_t SizeOfObjects() { return Size(); }

  virtual int RoundSizeDownToObjectAlignment(int size) {

    if (id_ == CODE_SPACE) {

      return RoundDown(size, kCodeAlignment);

    } else {

      return RoundDown(size, kPointerSize);

    }

  }

#ifdef DEBUG

  virtual void Print() = 0;

#endif

 private:

  Heap* heap_;

  AllocationSpace id_;

  Executability executable_;

};

// ----------------------------------------------------------------------------

// All heap objects containing executable code (code objects) must be allocated

// from a 2 GB range of memory, so that they can call each other using 32-bit

// displacements.  This happens automatically on 32-bit platforms, where 32-bit

// displacements cover the entire 4GB virtual address space.  On 64-bit

// platforms, we support this using the CodeRange object, which reserves and

// manages a range of virtual memory.

class CodeRange {

 public:

  explicit CodeRange(Isolate* isolate);

  ~CodeRange() { TearDown(); }

  // Reserves a range of virtual memory, but does not commit any of it.

  // Can only be called once, at heap initialization time.

  // Returns false on failure.

  bool SetUp(const size_t requested_size);

  // Frees the range of virtual memory, and frees the data structures used to

  // manage it.

  void TearDown();

  bool exists() { return this != NULL && code_range_ != NULL; }

  Address start() {

    if (this == NULL || code_range_ == NULL) return NULL;

    return static_cast<Address>(code_range_->address());

  }

  bool contains(Address address) {

    if (this == NULL || code_range_ == NULL) return false;

    Address start = static_cast<Address>(code_range_->address());

    return start <= address && address < start + code_range_->size();

  }

  // Allocates a chunk of memory from the large-object portion of

  // the code range.  On platforms with no separate code range, should

  // not be called.

  MUST_USE_RESULT Address AllocateRawMemory(const size_t requested_size,

                                            const size_t commit_size,

                                            size_t* allocated);

  bool CommitRawMemory(Address start, size_t length);

  bool UncommitRawMemory(Address start, size_t length);

  void FreeRawMemory(Address buf, size_t length);

 private:

  Isolate* isolate_;

  // The reserved range of virtual memory that all code objects are put in.

  VirtualMemory* code_range_;

  // Plain old data class, just a struct plus a constructor.

  class FreeBlock {

   public:

    FreeBlock(Address start_arg, size_t size_arg)

        : start(start_arg), size(size_arg) {

      ASSERT(IsAddressAligned(start, MemoryChunk::kAlignment));

      ASSERT(size >= static_cast<size_t>(Page::kPageSize));

    }

    FreeBlock(void* start_arg, size_t size_arg)

        : start(static_cast<Address>(start_arg)), size(size_arg) {

      ASSERT(IsAddressAligned(start, MemoryChunk::kAlignment));

      ASSERT(size >= static_cast<size_t>(Page::kPageSize));

    }

    Address start;

    size_t size;

  };

  // Freed blocks of memory are added to the free list.  When the allocation

  // list is exhausted, the free list is sorted and merged to make the new

  // allocation list.

  List<FreeBlock> free_list_;

  // Memory is allocated from the free blocks on the allocation list.

  // The block at current_allocation_block_index_ is the current block.

  List<FreeBlock> allocation_list_;

  int current_allocation_block_index_;

  // Finds a block on the allocation list that contains at least the

  // requested amount of memory.  If none is found, sorts and merges

  // the existing free memory blocks, and searches again.

  // If none can be found, terminates V8 with FatalProcessOutOfMemory.

  void GetNextAllocationBlock(size_t requested);

  // Compares the start addresses of two free blocks.

  static int CompareFreeBlockAddress(const FreeBlock* left,

                                     const FreeBlock* right);

  DISALLOW_COPY_AND_ASSIGN(CodeRange);

};

class SkipList {

 public:

  SkipList() {

    Clear();

  }

  void Clear() {

    for (int idx = 0; idx < kSize; idx++) {

      starts_[idx] = reinterpret_cast<Address>(-1);

    }

  }

  Address StartFor(Address addr) {

    return starts_[RegionNumber(addr)];

  }

  void AddObject(Address addr, int size) {

    int start_region = RegionNumber(addr);

    int end_region = RegionNumber(addr + size - kPointerSize);

    for (int idx = start_region; idx <= end_region; idx++) {

      if (starts_[idx] > addr) starts_[idx] = addr;

    }

  }

  static inline int RegionNumber(Address addr) {

    return (OffsetFrom(addr) & Page::kPageAlignmentMask) >> kRegionSizeLog2;

  }

  static void Update(Address addr, int size) {

    Page* page = Page::FromAddress(addr);

    SkipList* list = page->skip_list();

    if (list == NULL) {

      list = new SkipList();

      page->set_skip_list(list);

    }

    list->AddObject(addr, size);

  }

 private:

  static const int kRegionSizeLog2 = 13;

  static const int kRegionSize = 1 << kRegionSizeLog2;

  static const int kSize = Page::kPageSize / kRegionSize;

  STATIC_ASSERT(Page::kPageSize % kRegionSize == 0);

  Address starts_[kSize];

};

// ----------------------------------------------------------------------------

// A space acquires chunks of memory from the operating system. The memory

// allocator allocated and deallocates pages for the paged heap spaces and large

// pages for large object space.

//

// Each space has to manage it's own pages.

//

class MemoryAllocator {

 public:

  explicit MemoryAllocator(Isolate* isolate);

  // Initializes its internal bookkeeping structures.

  // Max capacity of the total space and executable memory limit.

  bool SetUp(intptr_t max_capacity, intptr_t capacity_executable);

  void TearDown();

  Page* AllocatePage(

      intptr_t size, PagedSpace* owner, Executability executable);

  LargePage* AllocateLargePage(

      intptr_t object_size, Space* owner, Executability executable);

  void Free(MemoryChunk* chunk);

  // Returns the maximum available bytes of heaps.

  intptr_t Available() { return capacity_ < size_ ? 0 : capacity_ - size_; }

  // Returns allocated spaces in bytes.

  intptr_t Size() { return size_; }

  // Returns the maximum available executable bytes of heaps.

  intptr_t AvailableExecutable() {

    if (capacity_executable_ < size_executable_) return 0;

    return capacity_executable_ - size_executable_;

  }

  // Returns allocated executable spaces in bytes.

  intptr_t SizeExecutable() { return size_executable_; }

  // Returns maximum available bytes that the old space can have.

  intptr_t MaxAvailable() {

    return (Available() / Page::kPageSize) * Page::kMaxNonCodeHeapObjectSize;

  }

  // Returns an indication of whether a pointer is in a space that has

  // been allocated by this MemoryAllocator.

  V8_INLINE bool IsOutsideAllocatedSpace(const void* address) const {

    return address < lowest_ever_allocated_ ||

        address >= highest_ever_allocated_;

  }

#ifdef DEBUG

  // Reports statistic info of the space.

  void ReportStatistics();

#endif

  // 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.

  MemoryChunk* AllocateChunk(intptr_t reserve_area_size,

                             intptr_t commit_area_size,

                             Executability executable,

                             Space* space);

  Address ReserveAlignedMemory(size_t requested,

                               size_t alignment,

                               VirtualMemory* controller);

  Address AllocateAlignedMemory(size_t reserve_size,

                                size_t commit_size,

                                size_t alignment,

                                Executability executable,

                                VirtualMemory* controller);

  bool CommitMemory(Address addr, size_t size, Executability executable);

  void FreeMemory(VirtualMemory* reservation, Executability executable);

  void FreeMemory(Address addr, size_t size, Executability executable);

  // 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.

  bool CommitBlock(Address start, size_t size, Executability executable);

  // Uncommit a contiguous block of memory [start..(start+size)[.

  // start is not NULL, the size is greater than zero, and the

  // block is contained in the initial chunk.  Returns true if it succeeded

  // and false otherwise.

  bool UncommitBlock(Address start, size_t size);

  // Zaps a contiguous block of memory [start..(start+size)[ thus

  // filling it up with a recognizable non-NULL bit pattern.

  void ZapBlock(Address start, size_t size);

  void PerformAllocationCallback(ObjectSpace space,

                                 AllocationAction action,

                                 size_t size);

  void AddMemoryAllocationCallback(MemoryAllocationCallback callback,

                                          ObjectSpace space,

                                          AllocationAction action);

  void RemoveMemoryAllocationCallback(

      MemoryAllocationCallback callback);

  bool MemoryAllocationCallbackRegistered(

      MemoryAllocationCallback callback);

  static int CodePageGuardStartOffset();

  static int CodePageGuardSize();

  static int CodePageAreaStartOffset();

  static int CodePageAreaEndOffset();

  static int CodePageAreaSize() {

    return CodePageAreaEndOffset() - CodePageAreaStartOffset();

  }

  MUST_USE_RESULT bool CommitExecutableMemory(VirtualMemory* vm,

                                              Address start,

                                              size_t commit_size,

                                              size_t reserved_size);

 private:

  Isolate* isolate_;

  // Maximum space size in bytes.

  size_t capacity_;

  // Maximum subset of capacity_ that can be executable

  size_t capacity_executable_;

  // Allocated space size in bytes.

  size_t size_;

  // Allocated executable space size in bytes.

  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 addrsses in 'allocated' space are allocated

  // to our heap. The range is [lowest, highest[, inclusive on the low end

  // and exclusive on the high end.

  void* lowest_ever_allocated_;

  void* highest_ever_allocated_;

  struct MemoryAllocationCallbackRegistration {

    MemoryAllocationCallbackRegistration(MemoryAllocationCallback callback,

                                         ObjectSpace space,

                                         AllocationAction action)

        : callback(callback), space(space), action(action) {

    }

    MemoryAllocationCallback callback;

    ObjectSpace space;

    AllocationAction action;

  };

  // A List of callback that are triggered when memory is allocated or free'd

  List<MemoryAllocationCallbackRegistration>

      memory_allocation_callbacks_;

  // 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(void* low, void* high) {

    lowest_ever_allocated_ = Min(lowest_ever_allocated_, low);

    highest_ever_allocated_ = Max(highest_ever_allocated_, high);

  }

  DISALLOW_IMPLICIT_CONSTRUCTORS(MemoryAllocator);

};

// -----------------------------------------------------------------------------

// Interface for heap object iterator to be implemented by all object space

// object iterators.

//

// NOTE: The space specific object iterators also implements the own next()

//       method which is used to avoid using virtual functions

//       iterating a specific space.

class ObjectIterator : public Malloced {

 public:

  virtual ~ObjectIterator() { }

  virtual HeapObject* next_object() = 0;

};

// -----------------------------------------------------------------------------

// Heap object iterator in new/old/map spaces.

//

// A HeapObjectIterator iterates objects from the bottom of the given space

// to its top or from the bottom of the given page to its top.

//

// If objects are allocated in the page during iteration the iterator may

// or may not iterate over those objects.  The caller must create a new

// iterator in order to be sure to visit these new objects.

class HeapObjectIterator: public ObjectIterator {

 public:

  // Creates a new object iterator in a given space.

  // 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(Page* page, HeapObjectCallback size_func);

  // Advance to the next object, skipping free spaces and other fillers and

  // skipping the special garbage section of which there is one per space.

  // Returns NULL when the iteration has ended.

  inline HeapObject* Next() {

    do {

      HeapObject* next_obj = FromCurrentPage();

      if (next_obj != NULL) return next_obj;

    } while (AdvanceToNextPage());

    return NULL;

  }

  virtual HeapObject* next_object() {

    return Next();

  }

 private:

  enum PageMode { kOnePageOnly, kAllPagesInSpace };

  Address cur_addr_;  // Current iteration point.

  Address cur_end_;   // End iteration point.

  HeapObjectCallback size_func_;  // Size function or NULL.

  PagedSpace* space_;

  PageMode page_mode_;

  // Fast (inlined) path of next().

  inline HeapObject* FromCurrentPage();

  // Slow path of next(), goes into the next page.  Returns false if the

  // iteration has ended.

  bool AdvanceToNextPage();

  // Initializes fields.

  inline void Initialize(PagedSpace* owner,

                         Address start,

                         Address end,

                         PageMode mode,

                         HeapObjectCallback size_func);

};

// -----------------------------------------------------------------------------

// A PageIterator iterates the pages in a paged space.

class PageIterator BASE_EMBEDDED {

 public:

  explicit inline PageIterator(PagedSpace* space);

  inline bool has_next();

  inline Page* next();

 private:

  PagedSpace* space_;

  Page* prev_page_;  // Previous page returned.

  // Next page that will be returned.  Cached here so that we can use this

  // iterator for operations that deallocate pages.

  Page* next_page_;

};

// -----------------------------------------------------------------------------

// A space has a circular list of pages. The next page can be accessed via

// Page::next_page() call.

// An abstraction of allocation and relocation pointers in a page-structured

// space.

class AllocationInfo {

 public:

  AllocationInfo() : top_(NULL), limit_(NULL) {

  }

  INLINE(void set_top(Address top)) {

    SLOW_ASSERT(top == NULL ||

        (reinterpret_cast<intptr_t>(top) & HeapObjectTagMask()) == 0);

    top_ = top;

  }

  INLINE(Address top()) const {

    SLOW_ASSERT(top_ == NULL ||

        (reinterpret_cast<intptr_t>(top_) & HeapObjectTagMask()) == 0);

    return top_;

  }

  Address* top_address() {

    return &top_;

  }

  INLINE(void set_limit(Address limit)) {

    SLOW_ASSERT(limit == NULL ||

        (reinterpret_cast<intptr_t>(limit) & HeapObjectTagMask()) == 0);

    limit_ = limit;

  }

  INLINE(Address limit()) const {

    SLOW_ASSERT(limit_ == NULL ||

        (reinterpret_cast<intptr_t>(limit_) & HeapObjectTagMask()) == 0);

    return limit_;

  }

  Address* limit_address() {

    return &limit_;

  }

#ifdef DEBUG

  bool VerifyPagedAllocation() {

    return (Page::FromAllocationTop(top_) == Page::FromAllocationTop(limit_))

        && (top_ <= limit_);

  }

#endif

 private:

  // Current allocation top.

  Address top_;

  // Current allocation limit.

  Address limit_;

};

// An abstraction of the accounting statistics of a page-structured space.

// The 'capacity' of a space is the number of object-area bytes (i.e., 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 (e.g. 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(); }