spaces.h.svn-base

Google浏览器V8内核代码

// 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:
  // Creates a space in the young generation. The constructor does not
  // allocate memory from the OS.  A SemiSpace is given a contiguous chunk of
  // memory of size 'capacity' when set up, and does not grow or shrink
  // otherwise.  In the mark-compact collector, the memory region of the from
  // space is used as the marking stack. It requires contiguous memory
  // addresses.
  SemiSpace(int initial_capacity,
            int maximum_capacity,
            AllocationSpace id);
  virtual ~SemiSpace() {}

  // Sets up the semispace using the given chunk.
  bool Setup(Address start, int size);

  // 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 maxmimum 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 begining 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:
  // Create a new space with a given allocation capacity (ie, the capacity of
  // *one* of the semispaces).  The constructor does not allocate heap memory
  // from the OS.  When the space is set up, it is given a contiguous chunk of
  // memory of size 2 * semispace_capacity.  To support fast containment
  // testing in the new space, the size of this chunk must be a power of two
  // and it must be aligned to its size.
  NewSpace(int initial_semispace_capacity,
           int maximum_semispace_capacity,
           AllocationSpace id);
  virtual ~NewSpace() {}

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