Two-page newspace.

src/spaces.h

 // 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
@@ skipping 353 matching lines @@
   Address body() { return address() + kObjectStartOffset; }
 
   Address body_limit() { return address() + size(); }
 
   int body_size() { return size() - kObjectStartOffset; }
 
   bool Contains(Address addr) {
     return addr >= body() && addr < address() + size();
   }
 
+  // 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 >= body() && addr <= address() + size();
+  }
+
   enum MemoryChunkFlags {
     IS_EXECUTABLE,
     WAS_SWEPT_CONSERVATIVELY,
     CONTAINS_ONLY_DATA,
     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.
     NUM_MEMORY_CHUNK_FLAGS
@@ skipping 938 matching lines @@
     accounting_stats_.ExpandSpace(size);
   }
 
   // Releases half of unused pages.
   void Shrink();
 
   // Ensures that the capacity is at least 'capacity'. Returns false on failure.
   bool EnsureCapacity(int capacity);
 
   // The dummy page that anchors the linked list of pages.
-  Page *anchor() { return &anchor_; }
+  Page* anchor() { return &anchor_; }
 
 #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();
@@ skipping 159 matching lines @@
   }
 
   inline void set_prev_page(NewSpacePage* page) {
     set_prev_chunk(page);
   }
 
   SemiSpace* semi_space() {
     return reinterpret_cast<SemiSpace*>(owner());
   }
 
+  bool is_anchor() { return !this->InNewSpace(); }
+
+  // Finds the NewSpacePage containg the given address.
+  static inline NewSpacePage* FromAddress(Address address_in_page) {
+    Address page_start =
+        reinterpret_cast<Address>(reinterpret_cast<uintptr_t>(address_in_page) &
+                                  ~Page::kPageAlignmentMask);
+    NewSpacePage* page = reinterpret_cast<NewSpacePage*>(page_start);
+    ASSERT(page->InNewSpace());
+    return page;
+  }
+
+  // Find the page for a limit address. A limit address is either an address
+  // inside a page, or the address right after the last byte of a page.
+  static inline NewSpacePage* FromLimit(Address address_limit) {
+    return NewSpacePage::FromAddress(address_limit - 1);
+  }
+
  private:
-  NewSpacePage(SemiSpace* owner) {
+  // Create a NewSpacePage object that is only used as anchor
+  // for the doubly-linked list of real pages.
+  explicit NewSpacePage(SemiSpace* owner) {
     InitializeAsAnchor(owner);
   }
 
-  // Finds the NewSpacePage containg the given address.
-  static NewSpacePage* FromAddress(Address address_in_page) {
-    Address page_start =
-        reinterpret_cast<Address>(reinterpret_cast<uintptr_t>(address_in_page) &
-                                  ~Page::kPageAlignmentMask);
-    return reinterpret_cast<NewSpacePage*>(page_start);
-  }
-
   static NewSpacePage* Initialize(Heap* heap,
                                   Address start,
                                   SemiSpace* semi_space);
 
   // Intialize a fake NewSpacePage used as sentinel at the ends
   // of a doubly-linked list of real NewSpacePages.
-  // Only uses the prev/next links.
+  // Only uses the prev/next links, and sets flags to not be in new-space.
   void InitializeAsAnchor(SemiSpace* owner);
 
   friend class SemiSpace;
   friend class SemiSpaceIterator;
 };
 
 
 // -----------------------------------------------------------------------------
 // SemiSpace in young generation
 //
@@ skipping 31 matching lines @@
   // Grow the semispace to the new capacity.  The new capacity
   // requested must be larger than the current capacity.
   bool GrowTo(int new_capacity);
 
   // Shrinks the semispace to the new capacity.  The new capacity
   // requested must be more than the amount of used memory in the
   // semispace and less than the current capacity.
   bool ShrinkTo(int new_capacity);
 
   // Returns the start address of the first page of the space.
-  Address low() {
+  Address space_low() {
     ASSERT(anchor_.next_page() != &anchor_);
     return anchor_.next_page()->body();
   }
 
   // Returns the start address of the current page of the space.
   Address page_low() {
     ASSERT(anchor_.next_page() != &anchor_);
     return current_page_->body();
   }
 
   // Returns one past the end address of the space.
-  Address high() {
-    // TODO(gc): Change when there is more than one page.
+  Address space_high() {
+    return anchor_.prev_page()->body_limit();
+  }
+
+  // Returns one past the end address of the current page of the space.
+  Address page_high() {
     return current_page_->body_limit();
   }
 
+  bool AdvancePage() {
+    NewSpacePage* next_page = current_page_->next_page();
+    if (next_page == &anchor_) return false;
+    current_page_ = next_page;
+    return true;
+  }
+
   // Resets the space to using the first page.
   void Reset();
 
   // Age mark accessors.
   Address age_mark() { return age_mark_; }
   void set_age_mark(Address mark) { age_mark_ = mark; }
 
-  // The offset of an address from the beginning of the space.
-  int SpaceOffsetForAddress(Address addr) {
-    return static_cast<int>(addr - low());
-  }
-
   // If we don't have these here then SemiSpace will be abstract.  However
   // they should never be called.
   virtual intptr_t Size() {
     UNREACHABLE();
     return 0;
   }
 
   virtual bool ReserveSpace(int bytes) {
     UNREACHABLE();
     return false;
   }
 
   bool is_committed() { return committed_; }
   bool Commit();
   bool Uncommit();
 
-  NewSpacePage* first_page() { return NewSpacePage::FromAddress(start_); }
+  NewSpacePage* first_page() { return anchor_.next_page(); }
   NewSpacePage* current_page() { return current_page_; }
 
 #ifdef ENABLE_HEAP_PROTECTION
   // Protect/unprotect the space by marking it read-only/writable.
   virtual void Protect() {}
   virtual void Unprotect() {}
 #endif
 
 #ifdef DEBUG
   virtual void Print();
   virtual void Verify();
+  static void ValidateRange(Address from, Address to);
 #endif
 
   // Returns the current capacity of the semi space.
   int Capacity() { return capacity_; }
 
   // Returns the maximum capacity of the semi space.
   int MaximumCapacity() { return maximum_capacity_; }
 
   // Returns the initial capacity of the semi space.
   int InitialCapacity() { return initial_capacity_; }
 
   SemiSpaceId id() { return id_; }
 
   static void Swap(SemiSpace* from, SemiSpace* to);
 
  private:
   // Flips the semispace between being from-space and to-space.
   // Copies the flags into the masked positions on all pages in the space.
   void FlipPages(intptr_t flags, intptr_t flag_mask);
 
+  NewSpacePage* anchor() { return &anchor_; }
+
   // The current and maximum capacity of the space.
   int capacity_;
   int maximum_capacity_;
   int initial_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.
   uintptr_t address_mask_;
   uintptr_t object_mask_;
   uintptr_t object_expected_;
 
   bool committed_;
   SemiSpaceId id_;
 
   NewSpacePage anchor_;
   NewSpacePage* current_page_;
 
+  friend class SemiSpaceIterator;
+  friend class NewSpacePageIterator;
  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().
+
+  // Iterate over all of allocated to-space.
   explicit SemiSpaceIterator(NewSpace* space);
+  // Iterate over all of allocated to-space, with a custome size function.
   SemiSpaceIterator(NewSpace* space, HeapObjectCallback size_func);
+  // Iterate over part of allocated to-space, from start to the end
+  // of allocation.
   SemiSpaceIterator(NewSpace* space, Address start);
+  // Iterate from one address to another in the same semi-space.
+  SemiSpaceIterator(Address from, Address to);
 
   HeapObject* Next() {
+    if (current_ == limit_) return NULL;
     if (current_ == current_page_limit_) {
-      // TODO(gc): Add something here when we have more than one page.
+      NewSpacePage* page = NewSpacePage::FromAddress(current_ - 1);
+      page = page->next_page();
+      ASSERT(!page->is_anchor());
+      current_ = page->body();
+      if (current_ == limit_) return NULL;
     }
-    if (current_ == limit_) return NULL;
 
     HeapObject* object = HeapObject::FromAddress(current_);
     int size = (size_func_ == NULL) ? object->Size() : size_func_(object);
 
     current_ += size;
     return object;
   }
 
   // Implementation of the ObjectIterator functions.
   virtual HeapObject* next_object() { return Next(); }
 
  private:
-  void Initialize(NewSpace* space,
-                  Address start,
+  void Initialize(Address start,
                   Address end,
                   HeapObjectCallback size_func);
 
-  // The semispace.
-  SemiSpace* space_;
   // The current iteration point.
   Address current_;
   // The end of the current page.
   Address current_page_limit_;
   // The end of iteration.
   Address limit_;
   // The callback function.
   HeapObjectCallback size_func_;
 };
 
 
 // -----------------------------------------------------------------------------
+// A PageIterator iterates the pages in a semi-space.
+class NewSpacePageIterator BASE_EMBEDDED {
+ public:
+  // Make an iterator that runs over all pages in the given semispace,
+  // even those not used in allocation.
+  explicit inline NewSpacePageIterator(SemiSpace* space);
+  // Make iterator that iterates from the page containing start
+  // to the page that contains limit in the same semispace.
+  inline NewSpacePageIterator(Address start, Address limit);
+
+  inline bool has_next();
+  inline NewSpacePage* next();
+
+ private:
+  NewSpacePage* 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.
+  NewSpacePage* next_page_;
+  // Last page returned.
+  NewSpacePage* last_page_;
+};
+
+
+// -----------------------------------------------------------------------------
 // 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.
   explicit NewSpace(Heap* heap)
     : Space(heap, NEW_SPACE, NOT_EXECUTABLE),
@@ skipping 65 matching lines @@
     ASSERT(to_space_.Capacity() == from_space_.Capacity());
     return to_space_.Capacity();
   }
 
   // Return the total amount of memory committed for new space.
   intptr_t CommittedMemory() {
     if (from_space_.is_committed()) return 2 * Capacity();
     return Capacity();
   }
 
-  // Return the available bytes without growing in the active semispace.
-  intptr_t Available() { return Capacity() - Size(); }
+  // Return the available bytes without growing or switching page in the
+  // active semispace.
+  intptr_t Available() {
+    return allocation_info_.limit - allocation_info_.top;
+  }
 
   // Return the maximum capacity of a semispace.
   int MaximumCapacity() {
     ASSERT(to_space_.MaximumCapacity() == from_space_.MaximumCapacity());
     return to_space_.MaximumCapacity();
   }
 
   // Returns the initial capacity of a semispace.
   int InitialCapacity() {
     ASSERT(to_space_.InitialCapacity() == from_space_.InitialCapacity());
     return to_space_.InitialCapacity();
   }
 
   // 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(); }
+  Address bottom() { return to_space_.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_; }
   uintptr_t mask() { return address_mask_; }
@@ skipping 16 matching lines @@
   MUST_USE_RESULT MaybeObject* AllocateRaw(int size_in_bytes) {
     return AllocateRawInternal(size_in_bytes);
   }
 
   // Reset the allocation pointer to the beginning of the active semispace.
   void ResetAllocationInfo();
 
   void LowerInlineAllocationLimit(intptr_t step) {
     inline_alloction_limit_step_ = step;
     if (step == 0) {
-      allocation_info_.limit = to_space_.high();
+      allocation_info_.limit = to_space_.page_high();
     } else {
       allocation_info_.limit = Min(
           allocation_info_.top + inline_alloction_limit_step_,
           allocation_info_.limit);
     }
     top_on_previous_step_ = allocation_info_.top;
   }
 
-  // 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 inactive semispace (for use as a marking stack,
+  // or to zap it).
+  Address FromSpacePageLow() { return from_space_.page_low(); }
+  Address FromSpaceLow() { return from_space_.space_low(); }
+  Address FromSpaceHigh() { return from_space_.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);
-  }
+  // Get the extent of the active semispace's pages' memory.
+  Address ToSpaceLow() { return to_space_.space_low(); }
+  Address ToSpaceHigh() { return to_space_.space_high(); }
 
   inline bool ToSpaceContains(Address address) {
     MemoryChunk* page = MemoryChunk::FromAddress(address);
     return page->is_valid() && page->InToSpace();
   }
 
   inline bool FromSpaceContains(Address address) {
     MemoryChunk* page = MemoryChunk::FromAddress(address);
     return page->is_valid() && page->InFromSpace();
   }
 
   // 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) {
     if (o->IsSmi()) return false;
     Address address = reinterpret_cast<Address>(o);
     return ToSpaceContains(address);
   }
 
   bool FromSpaceContains(Object* o) {
     if (o->IsSmi()) return false;
     Address address = reinterpret_cast<Address>(o);
     return FromSpaceContains(address);
   }
 
+  // Try to switch the active semispace to a new, empty, page.
+  // Returns false if this isn't possible or reasonable (i.e., there
+  // are no pages, or the current page is already empty), or true
+  // if successful.
+  bool AddFreshPage();
+
   virtual bool ReserveSpace(int bytes);
 
   // Resizes a sequential string which must be the most recent thing that was
   // allocated in new space.
   template <typename StringType>
   inline void ShrinkStringAtAllocationBoundary(String* string, int len);
 
 #ifdef ENABLE_HEAP_PROTECTION
   // Protect/unprotect the space by marking it read-only/writable.
   virtual void Protect();
@@ skipping 39 matching lines @@
 
   NewSpacePage* ActivePage() {
     return to_space_.current_page();
   }
 
   NewSpacePage* InactivePage() {
     return from_space_.current_page();
   }
 
  private:
+  // Update allocation info to match the current to-space page.
+  void UpdateAllocationInfo();
+
   Address chunk_base_;
   uintptr_t chunk_size_;
 
   // The semispaces.
   SemiSpace to_space_;
   SemiSpace from_space_;
 
   // Start address and bit mask for containment testing.
   Address start_;
   uintptr_t address_mask_;
@@ skipping 52 matching lines @@
   virtual void PrepareForMarkCompact(bool will_compact);
 
  public:
   TRACK_MEMORY("OldSpace")
 };
 
 
 // For contiguous spaces, top should be in the space (or at the end) and limit
 // should be the end of the space.
 #define ASSERT_SEMISPACE_ALLOCATION_INFO(info, space) \
-  ASSERT((space).low() <= (info).top                  \
-         && (info).top <= (space).high()              \
-         && (info).limit <= (space).high())
+  ASSERT((space).page_low() <= (info).top             \
+         && (info).top <= (space).page_high()         \
+         && (info).limit <= (space).page_high())
 
 
 // -----------------------------------------------------------------------------
 // Old space for objects of a fixed size
 
 class FixedSpace : public PagedSpace {
  public:
   FixedSpace(Heap* heap,
              intptr_t max_capacity,
              AllocationSpace id,
@@ skipping 300 matching lines @@
   }
   // Must be small, since an iteration is used for lookup.
   static const int kMaxComments = 64;
 };
 #endif
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SPACES_H_