spaces.h.svn-base

Google浏览器V8内核代码

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

  // 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 {
  friend class PageIterator;
 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 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 appened 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
};


#if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)