Put empty pages discovered during sweeping to the end of the list of pages...

src/spaces.h

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 149 matching lines @@
   Address RSetStart() { return address() + kRSetStartOffset; }
 
   // Returns the end address of the remembered set area (exclusive).
   Address RSetEnd() { return address() + kRSetEndOffset; }
 
   // Checks whether an address is page aligned.
   static bool IsAlignedToPageSize(Address a) {
     return 0 == (OffsetFrom(a) & kPageAlignmentMask);
   }
 
+  // True if this page was in use before current compaction started.
+  // Result is valid only for pages owned by paged spaces and
+  // only after PagedSpace::PrepareForMarkCompact was called.
+  inline bool WasInUseBeforeMC();
+
+  inline void SetWasInUseBeforeMC(bool was_in_use);
+
   // True if this page is a large object page.
-  bool IsLargeObjectPage() { return (is_normal_page & 0x1) == 0; }
+  inline bool IsLargeObjectPage();
+
+  inline void SetIsLargeObjectPage(bool is_large_object_page);
 
   // Returns the offset of a given address to this page.
   INLINE(int Offset(Address a)) {
     int offset = static_cast<int>(a - address());
     ASSERT_PAGE_OFFSET(offset);
     return offset;
   }
 
   // Returns the address for a given offset to the this page.
   Address OffsetToAddress(int offset) {
@@ skipping 55 matching lines @@
   // The start offset of the used part of the remembered set in a page.
   static const int kRSetStartOffset = kRSetOffset +
       kObjectStartOffset / kBitsPerPointer;
 
   // Object area size in bytes.
   static const int kObjectAreaSize = kPageSize - kObjectStartOffset;
 
   // Maximum object size that fits in a page.
   static const int kMaxHeapObjectSize = kObjectAreaSize;
 
+  enum PageFlag {
+    IS_NORMAL_PAGE = 1 << 0,
+    WAS_IN_USE_BEFORE_MC = 1 << 1
+  };
+
+  inline bool GetPageFlag(PageFlag flag);
+  inline void SetPageFlag(PageFlag flag, bool value);
+
   //---------------------------------------------------------------------------
   // Page header description.
   //
   // If a page is not in the large object space, the first word,
   // opaque_header, encodes the next page address (aligned to kPageSize 8K)
   // and the chunk number (0 ~ 8K-1).  Only MemoryAllocator should use
   // opaque_header. The value range of the opaque_header is [0..kPageSize[,
   // or [next_page_start, next_page_end[. It cannot point to a valid address
   // in the current page.  If a page is in the large object space, the first
   // word *may* (if the page start and large object chunk start are the
   // same) contain the address of the next large object chunk.
   intptr_t opaque_header;
 
   // If the page is not in the large object space, the low-order bit of the
   // second word is set. If the page is in the large object space, the
   // second word *may* (if the page start and large object chunk start are
   // the same) contain the large object chunk size.  In either case, the
   // low-order bit for large object pages will be cleared.
-  int is_normal_page;
+  // For normal pages this word is used to store various page flags.
+  int flags;
 
   // The following fields may overlap with remembered set, they can only
   // be used in the mark-compact collector when remembered set is not
   // used.
 
   // The index of the page in its owner space.
   int mc_page_index;
 
   // The allocation pointer after relocating objects to this page.
   Address mc_relocation_top;
@@ skipping 124 matching lines @@
 // The allocator keeps an initial chunk which is used for the new space.  The
 // leftover regions of the initial chunk are used for the initial chunks of
 // old space and map space if they are big enough to hold at least one page.
 // The allocator assumes that there is one old space and one map space, each
 // expands the space by allocating kPagesPerChunk pages except the last
 // expansion (before running out of space).  The first chunk may contain fewer
 // than kPagesPerChunk pages as well.
 //
 // The memory allocator also allocates chunks for the large object space, but
 // they are managed by the space itself.  The new space does not expand.
+//
+// The fact that pages for paged spaces are allocated and deallocated in chunks
+// induces a constraint on the order of pages in a linked lists. We say that
+// pages are linked in the chunk-order if and only if every two consecutive
+// pages from the same chunk are consecutive in the linked list.
+//
+
 
 class MemoryAllocator : public AllStatic {
  public:
   // Initializes its internal bookkeeping structures.
   // Max capacity of the total space.
   static bool Setup(int max_capacity);
 
   // Deletes valid chunks.
   static void TearDown();
 
@@ skipping 39 matching lines @@
   // allocate memory for the OS or cannot allocate a single page, this
   // function returns an invalid page pointer (NULL). The caller must check
   // whether the returned page is valid (by calling Page::is_valid()).  It is
   // guaranteed that allocated pages have contiguous addresses.  The actual
   // number of allocated pages is returned in the output parameter
   // allocated_pages.  If the PagedSpace owner is executable and there is
   // a code range, the pages are allocated from the code range.
   static Page* AllocatePages(int requested_pages, int* allocated_pages,
                              PagedSpace* owner);
 
-  // Frees pages from a given page and after. If 'p' is the first page
-  // of a chunk, pages from 'p' are freed and this function returns an
-  // invalid page pointer. Otherwise, the function searches a page
-  // after 'p' that is the first page of a chunk. Pages after the
-  // found page are freed and the function returns 'p'.
+  // Frees pages from a given page and after. Requires pages to be
+  // linked in chunk-order (see comment for class).
+  // If 'p' is the first page of a chunk, pages from 'p' are freed
+  // and this function returns an invalid page pointer.
+  // Otherwise, the function searches a page after 'p' that is
+  // the first page of a chunk. Pages after the found page
+  // are freed and the function returns 'p'.
   static Page* FreePages(Page* p);
 
+  // Frees all pages owned by given space.
+  static void FreeAllPages(PagedSpace* space);
+
   // Allocates and frees raw memory of certain size.
   // These are just thin wrappers around OS::Allocate and OS::Free,
   // but keep track of allocated bytes as part of heap.
   // If the flag is EXECUTABLE and a code range exists, the requested
   // memory is allocated from the code range.  If a code range exists
   // and the freed memory is in it, the code range manages the freed memory.
   static void* AllocateRawMemory(const size_t requested,
                                  size_t* allocated,
                                  Executability executable);
   static void FreeRawMemory(void* buf, size_t length);
@@ skipping 18 matching lines @@
   // Checks whether a page belongs to a space.
   static inline bool IsPageInSpace(Page* p, PagedSpace* space);
 
   // Returns the space that owns the given page.
   static inline PagedSpace* PageOwner(Page* page);
 
   // Finds the first/last page in the same chunk as a given page.
   static Page* FindFirstPageInSameChunk(Page* p);
   static Page* FindLastPageInSameChunk(Page* p);
 
+  // Relinks list of pages owned by space to make it chunk-ordered.
+  // Returns new first and last pages of space.
+  // Also returns last page in relinked list which has WasInUsedBeforeMC
+  // flag set.
+  static void RelinkPageListInChunkOrder(PagedSpace* space,
+                                         Page** first_page,
+                                         Page** last_page,
+                                         Page** last_page_in_use);
+
 #ifdef ENABLE_HEAP_PROTECTION
   // Protect/unprotect a block of memory by marking it read-only/writable.
   static inline void Protect(Address start, size_t size);
   static inline void Unprotect(Address start, size_t size,
                                Executability executable);
 
   // Protect/unprotect a chunk given a page in the chunk.
   static inline void ProtectChunkFromPage(Page* page);
   static inline void UnprotectChunkFromPage(Page* page);
 #endif
@@ skipping 68 matching lines @@
 
   // True if the address lies in the initial chunk.
   static inline bool InInitialChunk(Address address);
 
   // Initializes pages in a chunk. Returns the first page address.
   // This function and GetChunkId() are provided for the mark-compact
   // collector to rebuild page headers in the from space, which is
   // used as a marking stack and its page headers are destroyed.
   static Page* InitializePagesInChunk(int chunk_id, int pages_in_chunk,
                                       PagedSpace* owner);
+
+  static Page* RelinkPagesInChunk(int chunk_id,
+                                  Address chunk_start,
+                                  int chunk_size,
+                                  Page* prev,
+                                  Page** last_page_in_use);
 };
 
 
 // -----------------------------------------------------------------------------
 // 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.
@@ skipping 261 matching lines @@
   // 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 void PrepareForMarkCompact(bool will_compact);
 
   virtual Address PageAllocationTop(Page* page) = 0;
 
   // Current capacity without growing (Size() + Available() + Waste()).
   int Capacity() { return accounting_stats_.Capacity(); }
 
   // Total amount of memory committed for this space.  For paged
   // spaces this equals the capacity.
   int CommittedMemory() { return Capacity(); }
 
@@ skipping 19 matching lines @@
 
   // Allocate the requested number of bytes for relocation during mark-compact
   // collection.
   inline Object* MCAllocateRaw(int size_in_bytes);
 
   virtual bool ReserveSpace(int bytes);
 
   // Used by ReserveSpace.
   virtual void PutRestOfCurrentPageOnFreeList(Page* current_page) = 0;
 
+  // Free all pages in range from prev (exclusive) to last (inclusive).
+  // Freed pages are moved to the end of page list.
+  void FreePages(Page* prev, Page* last);
+
+  // Set space allocation info.
+  void SetTop(Address top, Address limit) {
+    allocation_info_.top = top;
+    allocation_info_.limit = limit;
+  }
+
   // ---------------------------------------------------------------------------
   // 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;
   }
@@ skipping 28 matching lines @@
   // Overridden by subclasses to verify space-specific object
   // properties (e.g., only maps or free-list nodes are in map space).
   virtual void VerifyObject(HeapObject* obj) {}
 
   // Report code object related statistics
   void CollectCodeStatistics();
   static void ReportCodeStatistics();
   static void ResetCodeStatistics();
 #endif
 
+  // Returns the page of the allocation pointer.
+  Page* AllocationTopPage() { return TopPageOf(allocation_info_); }
+
  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_;
 
   // The last page in this space.  Initially set in Setup, updated in
   // Expand and Shrink.
   Page* last_page_;
 
+  // True if pages owned by this space are linked in chunk-order.
+  // See comment for class MemoryAllocator for definition of chunk-order.
+  bool page_list_is_chunk_ordered_;
+
   // Normal allocation information.
   AllocationInfo allocation_info_;
 
   // Relocation information during mark-compact collections.
   AllocationInfo mc_forwarding_info_;
 
   // Bytes of each page that cannot be allocated.  Possibly non-zero
   // for pages in spaces with only fixed-size objects.  Always zero
   // for pages in spaces with variable sized objects (those pages are
   // padded with free-list nodes).
@@ skipping 41 matching lines @@
   // Slow path of MCAllocateRaw.
   HeapObject* SlowMCAllocateRaw(int size_in_bytes);
 
 #ifdef DEBUG
   // Returns the number of total pages in this space.
   int CountTotalPages();
 
   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_); }
 
   friend class PageIterator;
 };
 
 
 #if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING)
 class NumberAndSizeInfo BASE_EMBEDDED {
@@ skipping 606 matching lines @@
   // pointer).
   int AvailableFree() { return free_list_.available(); }
 
   // The top of allocation in a page in this space. Undefined if page is unused.
   virtual Address PageAllocationTop(Page* page) {
     return page == TopPageOf(allocation_info_) ? top() : page->ObjectAreaEnd();
   }
 
   // Give a block of memory to the space's free list.  It might be added to
   // the free list or accounted as waste.
-  void Free(Address start, int size_in_bytes) {
-    int wasted_bytes = free_list_.Free(start, size_in_bytes);
+  // If add_to_freelist is false then just accounting stats are updated and
+  // no attempt to add area to free list is made.
+  void Free(Address start, int size_in_bytes, bool add_to_freelist) {
     accounting_stats_.DeallocateBytes(size_in_bytes);
-    accounting_stats_.WasteBytes(wasted_bytes);
+
+    if (add_to_freelist) {
+      int wasted_bytes = free_list_.Free(start, size_in_bytes);
+      accounting_stats_.WasteBytes(wasted_bytes);
+    }
   }
 
   // Prepare for full garbage collection.  Resets the relocation pointer and
   // clears the free list.
   virtual void PrepareForMarkCompact(bool will_compact);
 
   // Updates the allocation pointer to the relocation top after a mark-compact
   // collection.
   virtual void MCCommitRelocationInfo();
 
@@ skipping 41 matching lines @@
 
   // The top of allocation in a page in this space. Undefined if page is unused.
   virtual Address PageAllocationTop(Page* page) {
     return page == TopPageOf(allocation_info_) ? top()
         : page->ObjectAreaEnd() - page_extra_;
   }
 
   int object_size_in_bytes() { return object_size_in_bytes_; }
 
   // Give a fixed sized block of memory to the space's free list.
-  void Free(Address start) {
-    free_list_.Free(start);
+  // If add_to_freelist is false then just accounting stats are updated and
+  // no attempt to add area to free list is made.
+  void Free(Address start, bool add_to_freelist) {
+    if (add_to_freelist) {
+      free_list_.Free(start);
+    }
     accounting_stats_.DeallocateBytes(object_size_in_bytes_);
   }
 
   // Prepares for a mark-compact GC.
   virtual void PrepareForMarkCompact(bool will_compact);
 
   // Updates the allocation pointer to the relocation top after a mark-compact
   // collection.
   virtual void MCCommitRelocationInfo();
 
@@ skipping 331 matching lines @@
 
  private:
   LargeObjectChunk* current_;
   HeapObjectCallback size_func_;
 };
 
 
 } }  // namespace v8::internal
 
 #endif  // V8_SPACES_H_