Simple non-incremental compaction by evacuation.

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 99 matching lines @@
       && (offset <= Page::kPageSize))
 
 #define ASSERT_MAP_PAGE_INDEX(index)                                           \
   ASSERT((0 <= index) && (index <= MapSpace::kMaxMapPageIndex))
 
 
 class PagedSpace;
 class MemoryAllocator;
 class AllocationInfo;
 class Space;
-class OldSpaceFreeList;
+class FreeList;
 
 
 // TODO(gc): Check that this all gets inlined and register allocated on
 // all platforms.
 class MarkBit {
  public:
   typedef uint32_t CellType;
 
   inline MarkBit(CellType* cell, CellType mask, bool data_only)
       : cell_(cell), mask_(mask), data_only_(data_only) { }
@@ skipping 252 matching lines @@
   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.
     NEW_SPACE_BELOW_AGE_MARK,
+    EVACUATION_CANDIDATE,
     NUM_MEMORY_CHUNK_FLAGS
   };
 
   void SetFlag(int flag) {
     flags_ |= (1 << flag);
   }
 
   void ClearFlag(int flag) {
     flags_ &= ~(1 << flag);
   }
@@ skipping 194 matching lines @@
 
   inline void ClearGCFields();
 
   static inline Page* Initialize(Heap* heap,
                                  MemoryChunk* chunk,
                                  Executability executable,
                                  PagedSpace* owner);
 
   void InitializeAsAnchor(PagedSpace* owner);
 
+  bool IsEvacuationCandidate() { return IsFlagSet(EVACUATION_CANDIDATE); }
+
+  bool IsEvacuationCandidateOrNewSpace() {
+    intptr_t mask = (1 << EVACUATION_CANDIDATE) |
+        (1 << IN_FROM_SPACE) |
+        (1 << IN_TO_SPACE);
+    return (flags_ & mask) != 0;
+  }
+
+  void MarkEvacuationCandidate() { SetFlag(EVACUATION_CANDIDATE); }
+
+  void ClearEvacuationCandidate() { ClearFlag(EVACUATION_CANDIDATE); }
+
   friend class MemoryAllocator;
 };
 
 
 STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize);
 
 
 class LargePage : public MemoryChunk {
  public:
   HeapObject* GetObject() {
@@ skipping 548 matching lines @@
 //     limit when the object we need to allocate is 1-31 words in size.  These
 //     spaces are called small.
 // 256-2047 words: There is a list of spaces this large.  It is used for top and
 //     limit when the object we need to allocate is 32-255 words in size.  These
 //     spaces are called medium.
 // 1048-16383 words: There is a list of spaces this large.  It is used for top
 //     and limit when the object we need to allocate is 256-2047 words in size.
 //     These spaces are call large.
 // At least 16384 words.  This list is for objects of 2048 words or larger.
 //     Empty pages are added to this list.  These spaces are called huge.
-class OldSpaceFreeList BASE_EMBEDDED {
+class FreeList BASE_EMBEDDED {
  public:
-  explicit OldSpaceFreeList(PagedSpace* owner);
+  explicit FreeList(PagedSpace* owner);
 
   // Clear the free list.
   void Reset();
 
   // Return the number of bytes available on the free list.
   intptr_t 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
@@ skipping 11 matching lines @@
   void MarkNodes();
 
 #ifdef DEBUG
   void Zap();
   static intptr_t SumFreeList(FreeListNode* node);
   static int FreeListLength(FreeListNode* cur);
   intptr_t SumFreeLists();
   bool IsVeryLong();
 #endif
 
+  void CountFreeListItems(Page* p, intptr_t* sizes);
+
  private:
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kMaxHeapObjectSize;
 
   PagedSpace* owner_;
   Heap* heap_;
 
   // Total available bytes in all blocks on this free list.
   int available_;
 
   static const int kSmallListMin = 0x20 * kPointerSize;
   static const int kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kSmallAllocationMax = kSmallListMin - kPointerSize;
   static const int kMediumAllocationMax = kSmallListMax;
   static const int kLargeAllocationMax = kMediumListMax;
   FreeListNode* small_list_;
   FreeListNode* medium_list_;
   FreeListNode* large_list_;
   FreeListNode* huge_list_;
 
-  DISALLOW_IMPLICIT_CONSTRUCTORS(OldSpaceFreeList);
+  DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
 
 class PagedSpace : public Space {
  public:
   // Creates a space with a maximum capacity, and an id.
   PagedSpace(Heap* heap,
              intptr_t max_capacity,
              AllocationSpace id,
              Executability executable);
@@ skipping 18 matching lines @@
   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.
   MUST_USE_RESULT MaybeObject* FindObject(Address addr);
 
   // Prepares for a mark-compact GC.
-  virtual void PrepareForMarkCompact(bool will_compact);
+  virtual void PrepareForMarkCompact();
 
   // Current capacity without growing (Size() + Available()).
   intptr_t Capacity() { return accounting_stats_.Capacity(); }
 
   // Total amount of memory committed for this space.  For paged
   // spaces this equals the capacity.
   intptr_t CommittedMemory() { return Capacity(); }
 
   // Sets the capacity, the available space and the wasted space to zero.
   // The stats are rebuilt during sweeping by adding each page to the
@@ skipping 113 matching lines @@
 
   bool AdvanceSweeper(intptr_t bytes_to_sweep);
 
   bool IsSweepingComplete() {
     return !first_unswept_page_->is_valid();
   }
 
   Page* FirstPage() { return anchor_.next_page(); }
   Page* LastPage() { return anchor_.prev_page(); }
 
+
+  bool IsFragmented(Page* p) {
+    intptr_t sizes[4];
+    free_list_.CountFreeListItems(p, sizes);
+
+    intptr_t ratio =
+        (sizes[0] * 5 + sizes[1]) * 100 / Page::kObjectAreaSize;
+
+    if (FLAG_trace_fragmentation) {
+      PrintF("%p: %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %d (%.2f%%) %s\n",
+             (void*) p,
+             sizes[0],
+             static_cast<double>(sizes[0] * 100) / Page::kObjectAreaSize,
+             sizes[1],
+             static_cast<double>(sizes[1] * 100) / Page::kObjectAreaSize,
+             sizes[2],
+             static_cast<double>(sizes[2] * 100) / Page::kObjectAreaSize,
+             sizes[3],
+             static_cast<double>(sizes[3] * 100) / Page::kObjectAreaSize,
+             (ratio > 15) ? "[fragmented]" : "");
+    }
+
+    return ratio > 15;
+  }
+
  protected:
   // Maximum capacity of this space.
   intptr_t max_capacity_;
 
   // Accounting information for this space.
   AllocationStats accounting_stats_;
 
   // The dummy page that anchors the double linked list of pages.
   Page anchor_;
 
   // The space's free list.
-  OldSpaceFreeList free_list_;
+  FreeList free_list_;
 
   // Normal allocation information.
   AllocationInfo allocation_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).
   int page_extra_;
 
@@ skipping 720 matching lines @@
     page_extra_ = 0;
   }
 
   // The limit of allocation for a page in this space.
   virtual Address PageAllocationLimit(Page* page) {
     return page->ObjectAreaEnd();
   }
 
   // Prepare for full garbage collection.  Resets the relocation pointer and
   // clears the free list.
-  virtual void PrepareForMarkCompact(bool will_compact);
+  virtual void PrepareForMarkCompact();
 
  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).page_low() <= (info).top             \
@@ skipping 18 matching lines @@
   }
 
   // The limit of allocation for a page in this space.
   virtual Address PageAllocationLimit(Page* page) {
     return page->ObjectAreaEnd() - page_extra_;
   }
 
   int object_size_in_bytes() { return object_size_in_bytes_; }
 
   // Prepares for a mark-compact GC.
-  virtual void PrepareForMarkCompact(bool will_compact);
+  virtual void PrepareForMarkCompact();
 
   void MarkFreeListNodes() { free_list_.MarkNodes(); }
 
  protected:
   void ResetFreeList() {
     free_list_.Reset();
   }
 
  private:
   // The size of objects in this space.
@@ skipping 11 matching lines @@
  public:
   // Creates a map space object with a maximum capacity.
   MapSpace(Heap* heap,
            intptr_t max_capacity,
            int max_map_space_pages,
            AllocationSpace id)
       : FixedSpace(heap, max_capacity, id, Map::kSize, "map"),
         max_map_space_pages_(max_map_space_pages) {
   }
 
-  // Prepares for a mark-compact GC.
-  virtual void PrepareForMarkCompact(bool will_compact);
-
   // Given an index, returns the page address.
   // TODO(gc): this limit is artifical just to keep code compilable
   static const int kMaxMapPageIndex = 1 << 16;
 
   // Are map pointers encodable into map word?
   bool MapPointersEncodable() {
     return false;
   }
 
   // Should be called after forced sweep to find out if map space needs
@@ skipping 252 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_