[heap] Move to two-level free-list

src/heap/spaces.h

 // Copyright 2011 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_HEAP_SPACES_H_
 #define V8_HEAP_SPACES_H_
 
 #include "src/allocation.h"
 #include "src/atomic-utils.h"
 #include "src/base/atomicops.h"
 #include "src/base/bits.h"
 #include "src/base/platform/mutex.h"
 #include "src/flags.h"
 #include "src/hashmap.h"
 #include "src/list.h"
 #include "src/objects.h"
 #include "src/utils.h"
 
 namespace v8 {
 namespace internal {
 
 class AllocationInfo;
 class AllocationObserver;
 class CompactionSpace;
 class CompactionSpaceCollection;
 class FreeList;
 class Isolate;
 class MemoryAllocator;
 class MemoryChunk;
+class Page;
 class PagedSpace;
 class SemiSpace;
 class SkipList;
 class SlotsBuffer;
 class SlotSet;
 class TypedSlotSet;
 class Space;
 
 // -----------------------------------------------------------------------------
 // Heap structures:
@@ skipping 238 matching lines @@
     // Clear all cells till the cell containing the last index.
     for (uint32_t i = start_cell_index; i < end_cell_index; i++) {
       cells()[i] = 0;
     }
     // Clear all bits in the last cell till the last bit before index.
     uint32_t clear_mask = ~((1u << IndexInCell(index)) - 1);
     cells()[end_cell_index] &= clear_mask;
   }
 };
 
+enum FreeListCategoryType {
+  kTiniest,
+  kTiny,
+  kSmall,
+  kMedium,
+  kLarge,
+  kHuge,
+
+  kFirstCategory = kTiniest,
+  kLastCategory = kHuge,
+  kNumberOfCategories = kLastCategory + 1,
+  kInvalidCategory
+};
+
+enum FreeMode { kLinkCategory, kDoNotLinkCategory };
+
+// A free list category maintains a linked list of free memory blocks.
+class FreeListCategory {
+ public:
+  static const int kSize = kIntSize +      // FreeListCategoryType type_
+                           kIntSize +      // int available_
+                           kPointerSize +  // FreeSpace* top_
+                           kPointerSize +  // FreeListCategory* prev_
+                           kPointerSize;   // FreeListCategory* next_
+
+  FreeListCategory()
+      : type_(kInvalidCategory),
+        available_(0),
+        top_(nullptr),
+        prev_(nullptr),
+        next_(nullptr) {}
+
+  void Initialize(FreeListCategoryType type) {
+    type_ = type;
+    available_ = 0;
+    top_ = nullptr;
+    prev_ = nullptr;
+    next_ = nullptr;
+  }
+
+  void Invalidate();
+
+  void Reset();
+
+  void ResetStats() { Reset(); }
+
+  void RepairFreeList(Heap* heap);
+
+  // Relinks the category into the currently owning free list. Requires that the
+  // category is currently unlinked.
+  void Relink();
+
+  bool Free(FreeSpace* node, int size_in_bytes, FreeMode mode);

[Hannes Payer (out of office), 2016/03/11 09:56:24]

Why not templatize on mode?

[Michael Lippautz, 2016/03/11 10:19:12]

Templatizing FreeListCategory::Free would then require to templatize
FreeList:Free, which is non-inlined and cannot easily put in spaces.h because of
missing definitions (PagedSpace).

+
+  // Picks a node from the list and stores its size in |node_size|. Returns
+  // nullptr if the category is empty.
+  FreeSpace* PickNodeFromList(int* node_size);
+
+  // Performs a single try to pick a node of at least |minimum_size| from the
+  // category. Stores the actual size in |node_size|. Returns nullptr if no
+  // node is found.
+  FreeSpace* TryPickNodeFromList(int minimum_size, int* node_size);
+
+  // Picks a node of at least |minimum_size| from the category. Stores the
+  // actual size in |node_size|. Returns nullptr if no node is found.
+  FreeSpace* SearchForNodeInList(int minimum_size, int* node_size);
+
+  inline FreeList* owner();
+  inline bool is_linked();
+  bool is_empty() { return top() == nullptr; }
+  int available() const { return available_; }
+
+#ifdef DEBUG
+  intptr_t SumFreeList();
+  int FreeListLength();
+#endif
+
+ private:
+  // For debug builds we accurately compute free lists lengths up until
+  // {kVeryLongFreeList} by manually walking the list.
+  static const int kVeryLongFreeList = 500;
+
+  inline Page* page();
+
+  FreeSpace* top() { return top_; }
+  void set_top(FreeSpace* top) { top_ = top; }
+  FreeListCategory* prev() { return prev_; }
+  void set_prev(FreeListCategory* prev) { prev_ = prev; }
+  FreeListCategory* next() { return next_; }
+  void set_next(FreeListCategory* next) { next_ = next; }
+
+  // |type_|: The type of this free list category.
+  FreeListCategoryType type_;
+
+  // |available_|: Total available bytes in all blocks of this free list
+  //   category.

[Hannes Payer (out of office), 2016/03/11 09:56:24]

remvove space

[Michael Lippautz, 2016/03/11 10:19:12]

Done.

+  int available_;
+
+  // |top_|: Points to the top FreeSpace* in the free list category.
+  FreeSpace* top_;
+
+  FreeListCategory* prev_;
+  FreeListCategory* next_;
+
+  friend class FreeList;
+  friend class PagedSpace;
+};
 
 // MemoryChunk represents a memory region owned by a specific space.
 // It is divided into the header and the body. Chunk start is always
 // 1MB aligned. Start of the body is aligned so it can accommodate
 // any heap object.
 class MemoryChunk {
  public:
   enum MemoryChunkFlags {
     IS_EXECUTABLE,
     POINTERS_TO_HERE_ARE_INTERESTING,
@@ skipping 102 matching lines @@
 
   static const size_t kMinHeaderSize =
       kWriteBarrierCounterOffset +
       kIntptrSize         // intptr_t write_barrier_counter_
       + kPointerSize      // AtomicValue high_water_mark_
       + kPointerSize      // base::Mutex* mutex_
       + kPointerSize      // base::AtomicWord parallel_sweeping_
       + kPointerSize      // AtomicValue parallel_compaction_
       + 2 * kPointerSize  // AtomicNumber free-list statistics
       + kPointerSize      // AtomicValue next_chunk_
-      + kPointerSize;     // AtomicValue prev_chunk_
+      + kPointerSize      // AtomicValue prev_chunk_
+      // FreeListCategory categories_[kNumberOfCategories]
+      + FreeListCategory::kSize * kNumberOfCategories;
 
   // We add some more space to the computed header size to amount for missing
   // alignment requirements in our computation.
   // Try to get kHeaderSize properly aligned on 32-bit and 64-bit machines.
   static const size_t kHeaderSize = kMinHeaderSize;
 
   static const int kBodyOffset =
       CODE_POINTER_ALIGN(kHeaderSize + Bitmap::kSize);
 
   // The start offset of the object area in a page. Aligned to both maps and
@@ skipping 161 matching lines @@
 
   bool IsEvacuationCandidate() {
     DCHECK(!(IsFlagSet(NEVER_EVACUATE) && IsFlagSet(EVACUATION_CANDIDATE)));
     return IsFlagSet(EVACUATION_CANDIDATE);
   }
 
   bool CanAllocate() {
     return !IsEvacuationCandidate() && !IsFlagSet(NEVER_ALLOCATE_ON_PAGE);
   }
 
-  void MarkEvacuationCandidate() {
-    DCHECK(!IsFlagSet(NEVER_EVACUATE));
-    DCHECK_NULL(old_to_old_slots_);
-    DCHECK_NULL(typed_old_to_old_slots_);
-    SetFlag(EVACUATION_CANDIDATE);
-  }
-
-  void ClearEvacuationCandidate() {
-    DCHECK_NULL(old_to_old_slots_);
-    DCHECK_NULL(typed_old_to_old_slots_);
-    ClearFlag(EVACUATION_CANDIDATE);
-  }
-
   bool ShouldSkipEvacuationSlotRecording() {
     return (flags_ & kSkipEvacuationSlotsRecordingMask) != 0;
   }
 
   Executability executable() {
     return IsFlagSet(IS_EXECUTABLE) ? EXECUTABLE : NOT_EXECUTABLE;
   }
 
   bool InNewSpace() {
     return (flags_ & ((1 << IN_FROM_SPACE) | (1 << IN_TO_SPACE))) != 0;
@@ skipping 90 matching lines @@
 
   // PagedSpace free-list statistics.
   AtomicNumber<intptr_t> available_in_free_list_;
   AtomicNumber<intptr_t> wasted_memory_;
 
   // next_chunk_ holds a pointer of type MemoryChunk
   AtomicValue<MemoryChunk*> next_chunk_;
   // prev_chunk_ holds a pointer of type MemoryChunk
   AtomicValue<MemoryChunk*> prev_chunk_;
 
+  FreeListCategory categories_[kNumberOfCategories];
+
  private:
   void InitializeReservedMemory() { reservation_.Reset(); }
 
   friend class MemoryAllocator;
   friend class MemoryChunkValidator;
 };
 
-enum FreeListCategoryType {
-  kTiniest,
-  kTiny,
-  kSmall,
-  kMedium,
-  kLarge,
-  kHuge,
-
-  kFirstCategory = kTiniest,
-  kLastCategory = kHuge,
-  kNumberOfCategories = kLastCategory + 1
-};
-
 // -----------------------------------------------------------------------------
 // A page is a memory chunk of a size 1MB. Large object pages may be larger.
 //
 // The only way to get a page pointer is by calling factory methods:
 //   Page* p = Page::FromAddress(addr); or
 //   Page* p = Page::FromAllocationTop(top);
 class Page : public MemoryChunk {
  public:
   // Returns the page containing a given address. The address ranges
   // from [page_addr .. page_addr + kPageSize[
@@ skipping 83 matching lines @@
     return concurrent_sweeping_state().Value() == kSweepingDone;
   }
 
   void ResetFreeListStatistics();
 
   int LiveBytesFromFreeList() {
     return static_cast<int>(area_size() - wasted_memory() -
                             available_in_free_list());
   }
 
+  template <typename Callback>
+  inline void ForAllFreeListCategories(Callback callback) {
+    for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
+      callback(&categories_[i]);
+    }
+  }
+
+  FreeListCategory* free_list_category(FreeListCategoryType type) {
+    return &categories_[type];
+  }
+
 #define FRAGMENTATION_STATS_ACCESSORS(type, name)        \
   type name() { return name##_.Value(); }                \
   void set_##name(type name) { name##_.SetValue(name); } \
   void add_##name(type name) { name##_.Increment(name); }
 
   FRAGMENTATION_STATS_ACCESSORS(intptr_t, wasted_memory)
   FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_free_list)
 
 #undef FRAGMENTATION_STATS_ACCESSORS
 
 #ifdef DEBUG
   void Print();
 #endif  // DEBUG
 
+  inline void MarkNeverAllocateForTesting();
+  inline void MarkEvacuationCandidate();
+  inline void ClearEvacuationCandidate();
+
+ private:
+  inline void InitializeFreeListCategories();
+
   friend class MemoryAllocator;
 };
 
 
 class LargePage : public MemoryChunk {
  public:
   HeapObject* GetObject() { return HeapObject::FromAddress(area_start()); }
 
   inline LargePage* next_page() {
     return static_cast<LargePage*>(next_chunk());
@@ skipping 619 matching lines @@
 
   // Zero out all the allocation statistics (i.e., no capacity).
   void Clear() {
     capacity_ = 0;
     max_capacity_ = 0;
     size_ = 0;
   }
 
   void ClearSize() { size_ = capacity_; }
 
-  // Reset the allocation statistics (i.e., available = capacity with no wasted
-  // or allocated bytes).
-  void Reset() {
-    size_ = 0;
-  }
-
   // Accessors for the allocation statistics.
   intptr_t Capacity() { return capacity_; }
   intptr_t MaxCapacity() { return max_capacity_; }
   intptr_t Size() {
     CHECK_GE(size_, 0);
     return size_;
   }
 
   // Grow the space by adding available bytes.  They are initially marked as
   // being in use (part of the size), but will normally be immediately freed,
   // putting them on the free list and removing them from size_.
   void ExpandSpace(int size_in_bytes) {
     capacity_ += size_in_bytes;
     size_ += size_in_bytes;
     if (capacity_ > max_capacity_) {
       max_capacity_ = capacity_;
     }
     CHECK(size_ >= 0);
   }
 
   // Shrink the space by removing available bytes.  Since shrinking is done
   // during sweeping, bytes have been marked as being in use (part of the size)
   // and are hereby freed.
   void ShrinkSpace(int size_in_bytes) {
     capacity_ -= size_in_bytes;
     size_ -= size_in_bytes;
-    CHECK(size_ >= 0);
+    CHECK_GE(size_, 0);
   }
 
   // Allocate from available bytes (available -> size).
   void AllocateBytes(intptr_t size_in_bytes) {
     size_ += size_in_bytes;
-    CHECK(size_ >= 0);
+    CHECK_GE(size_, 0);
   }
 
   // Free allocated bytes, making them available (size -> available).
   void DeallocateBytes(intptr_t size_in_bytes) {
     size_ -= size_in_bytes;
     CHECK_GE(size_, 0);
   }
 
   // Merge {other} into {this}.
   void Merge(const AllocationStats& other) {
@@ skipping 18 matching lines @@
   // bookkeeping structures) currently in the space.
   intptr_t capacity_;
 
   // |max_capacity_|: The maximum capacity ever observed.
   intptr_t max_capacity_;
 
   // |size_|: The number of allocated bytes.
   intptr_t size_;
 };
 
-
-// A free list category maintains a linked list of free memory blocks.
-class FreeListCategory {
- public:
-  FreeListCategory() : top_(nullptr), end_(nullptr), available_(0) {}
-
-  void Initialize(FreeList* owner, FreeListCategoryType type) {
-    owner_ = owner;
-    type_ = type;
-  }
-
-  // Concatenates {category} into {this}.
-  //
-  // Note: Thread-safe.
-  intptr_t Concatenate(FreeListCategory* category);
-
-  void Reset();
-
-  void Free(FreeSpace* node, int size_in_bytes);
-
-  // Pick a node from the list.
-  FreeSpace* PickNodeFromList(int* node_size);
-
-  // Pick a node from the list and compare it against {size_in_bytes}. If the
-  // node's size is greater or equal return the node and null otherwise.
-  FreeSpace* PickNodeFromList(int size_in_bytes, int* node_size);
-
-  // Search for a node of size {size_in_bytes}.
-  FreeSpace* SearchForNodeInList(int size_in_bytes, int* node_size);
-
-  intptr_t EvictFreeListItemsInList(Page* p);
-  bool ContainsPageFreeListItemsInList(Page* p);
-
-  void RepairFreeList(Heap* heap);
-
-  bool IsEmpty() { return top() == nullptr; }
-
-  FreeList* owner() { return owner_; }
-  int available() const { return available_; }
-
-#ifdef DEBUG
-  intptr_t SumFreeList();
-  int FreeListLength();
-  bool IsVeryLong();
-#endif
-
- private:
-  // For debug builds we accurately compute free lists lengths up until
-  // {kVeryLongFreeList} by manually walking the list.
-  static const int kVeryLongFreeList = 500;
-
-  FreeSpace* top() { return top_.Value(); }
-  void set_top(FreeSpace* top) { top_.SetValue(top); }
-
-  FreeSpace* end() const { return end_; }
-  void set_end(FreeSpace* end) { end_ = end; }
-
-  // |type_|: The type of this free list category.
-  FreeListCategoryType type_;
-
-  // |top_|: Points to the top FreeSpace* in the free list category.
-  AtomicValue<FreeSpace*> top_;
-
-  // |end_|: Points to the end FreeSpace* in the free list category.
-  FreeSpace* end_;
-
-  // |available_|: Total available bytes in all blocks of this free list
-  //   category.
-  int available_;
-
-  // |owner_|: The owning free list of this category.
-  FreeList* owner_;
-};
-
 // A free list maintaining free blocks of memory. The free list is organized in
 // a way to encourage objects allocated around the same time to be near each
 // other. The normal way to allocate is intended to be by bumping a 'top'
 // pointer until it hits a 'limit' pointer.  When the limit is hit we need to
 // find a new space to allocate from. This is done with the free list, which is
 // divided up into rough categories to cut down on waste. Having finer
 // categories would scatter allocation more.
 
 // The free list is organized in categories as follows:
 // kMinBlockSize-10 words (tiniest): The tiniest blocks are only used for
@@ skipping 24 matching lines @@
     } else if (maximum_freed <= kMediumListMax) {
       return kMediumAllocationMax;
     } else if (maximum_freed <= kLargeListMax) {
       return kLargeAllocationMax;
     }
     return maximum_freed;
   }
 
   explicit FreeList(PagedSpace* owner);
 
-  // The method concatenates {other} into {this} and returns the added bytes,
-  // including waste.
-  //
-  // Note: Thread-safe.
-  intptr_t Concatenate(FreeList* other);
-
   // Adds 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 were not added to the free list, because they freed memory block
   // was too small. Bookkeeping information will be written to the block, i.e.,
   // 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);
+  int Free(Address start, int size_in_bytes, FreeMode mode);
 
   // 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 size
   // should be a non-zero multiple of the word size.
   MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes);
 
   // Clear the free list.
   void Reset();
 
-  void ResetStats() { wasted_bytes_ = 0; }
+  void ResetStats() {
+    wasted_bytes_.SetValue(0);
+    ForAllFreeListCategories(
+        [](FreeListCategory* category) { category->ResetStats(); });
+  }
 
   // Return the number of bytes available on the free list.
   intptr_t Available() {
     intptr_t available = 0;
-    for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
-      available += category_[i].available();
-    }
+    ForAllFreeListCategories([&available](FreeListCategory* category) {
+      available += category->available();
+    });
     return available;
   }
 
-  // The method tries to find a {FreeSpace} node of at least {size_in_bytes}
-  // size in the free list category exactly matching the size. If no suitable
-  // node could be found, the method falls back to retrieving a {FreeSpace}
-  // from the large or huge free list category.
-  //
-  // Can be used concurrently.
-  MUST_USE_RESULT FreeSpace* TryRemoveMemory(intptr_t hint_size_in_bytes);
-
   bool IsEmpty() {
-    for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
-      if (!category_[i].IsEmpty()) return false;
-    }
-    return true;
+    bool empty = true;
+    ForAllFreeListCategories([&empty](FreeListCategory* category) {
+      if (!category->is_empty()) empty = false;
+    });
+    return empty;
   }
 
   // Used after booting the VM.
   void RepairLists(Heap* heap);
 
-  intptr_t EvictFreeListItems(Page* p);
-  bool ContainsPageFreeListItems(Page* p);
+  intptr_t EvictFreeListItems(Page* page);
+  bool ContainsPageFreeListItems(Page* page);
 
   PagedSpace* owner() { return owner_; }
-  intptr_t wasted_bytes() { return wasted_bytes_; }
-  base::Mutex* mutex() { return &mutex_; }
+  intptr_t wasted_bytes() { return wasted_bytes_.Value(); }
+
+  template <typename Callback>
+  void ForAllFreeListCategories(FreeListCategoryType type, Callback callback) {
+    FreeListCategory* current = categories_[type];
+    while (current != nullptr) {
+      FreeListCategory* next = current->next();
+      callback(current);
+      current = next;
+    }
+  }
+
+  template <typename Callback>
+  void ForAllFreeListCategories(Callback callback) {
+    for (int i = kFirstCategory; i < kNumberOfCategories; i++) {
+      ForAllFreeListCategories(static_cast<FreeListCategoryType>(i), callback);
+    }
+  }
+
+  bool AddCategory(FreeListCategory* category);
+  void RemoveCategory(FreeListCategory* category);
+  void PrintCategories(FreeListCategoryType type);
 
 #ifdef DEBUG
-  void Zap();
   intptr_t SumFreeLists();
   bool IsVeryLong();
 #endif
 
  private:
+  class FreeListCategoryIterator {
+   public:
+    FreeListCategoryIterator(FreeList* free_list, FreeListCategoryType type)
+        : current_(free_list->categories_[type]) {}
+
+    bool HasNext() { return current_ != nullptr; }
+
+    FreeListCategory* Next() {
+      DCHECK(HasNext());
+      FreeListCategory* tmp = current_;
+      current_ = current_->next();
+      return tmp;
+    }
+
+   private:
+    FreeListCategory* current_;
+  };
+
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kAllocatableMemory;
 
   static const int kTiniestListMax = 0xa * kPointerSize;
   static const int kTinyListMax = 0x1f * kPointerSize;
   static const int kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kTinyAllocationMax = kTiniestListMax;
   static const int kSmallAllocationMax = kTinyListMax;
   static const int kMediumAllocationMax = kSmallListMax;
   static const int kLargeAllocationMax = kMediumListMax;
 
   FreeSpace* FindNodeFor(int size_in_bytes, int* node_size);
-  FreeSpace* FindNodeIn(FreeListCategoryType category, int* node_size);
 
-  FreeListCategory* GetFreeListCategory(FreeListCategoryType category) {
-    return &category_[category];
-  }
+  // Walks all available categories for a given |type| and tries to retrieve
+  // a node. Returns nullptr if the category is empty.
+  FreeSpace* FindNodeIn(FreeListCategoryType type, int* node_size);
+
+  // Tries to retrieve a node from the first category in a given |type|.
+  // Returns nullptr if the category is empty.
+  FreeSpace* TryFindNodeIn(FreeListCategoryType type, int* node_size,
+                           int minimum_size);
+
+  // Searches a given |type| for a node of at least |minimum_size|.
+  FreeSpace* SearchForNodeInList(FreeListCategoryType type, int* node_size,
+                                 int minimum_size);
 
   FreeListCategoryType SelectFreeListCategoryType(size_t size_in_bytes) {
     if (size_in_bytes <= kTiniestListMax) {
       return kTiniest;
     } else if (size_in_bytes <= kTinyListMax) {
       return kTiny;
     } else if (size_in_bytes <= kSmallListMax) {
       return kSmall;
     } else if (size_in_bytes <= kMediumListMax) {
       return kMedium;
     } else if (size_in_bytes <= kLargeListMax) {
       return kLarge;
     }
     return kHuge;
   }
 
   // The tiny categories are not used for fast allocation.
   FreeListCategoryType SelectFastAllocationFreeListCategoryType(
       size_t size_in_bytes) {
     if (size_in_bytes <= kSmallAllocationMax) {
       return kSmall;
     } else if (size_in_bytes <= kMediumAllocationMax) {
       return kMedium;
     } else if (size_in_bytes <= kLargeAllocationMax) {
       return kLarge;
     }
     return kHuge;
   }
 
+  FreeListCategory* top(FreeListCategoryType type) { return categories_[type]; }
+
   PagedSpace* owner_;
-  base::Mutex mutex_;
-  intptr_t wasted_bytes_;
-  FreeListCategory category_[kNumberOfCategories];
+  AtomicNumber<intptr_t> wasted_bytes_;
+  FreeListCategory* categories_[kNumberOfCategories];
+
+  friend class FreeListCategory;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
 
 class AllocationResult {
  public:
   // Implicit constructor from Object*.
   AllocationResult(Object* object)  // NOLINT
       : object_(object) {
@@ skipping 81 matching lines @@
 
  private:
   LocalAllocationBuffer(Heap* heap, AllocationInfo allocation_info);
 
   void Close();
 
   Heap* heap_;
   AllocationInfo allocation_info_;
 };
 
-
 class PagedSpace : public Space {
  public:
   static const intptr_t kCompactionMemoryWanted = 500 * KB;
 
   // Creates a space with an id.
   PagedSpace(Heap* heap, AllocationSpace id, Executability executable);
 
   ~PagedSpace() override { TearDown(); }
 
   // Set up the space using the given address range of virtual memory (from
@@ skipping 36 matching lines @@
   // The stats are rebuilt during sweeping by adding each page to the
   // capacity and the size when it is encountered.  As free spaces are
   // discovered during the sweeping they are subtracted from the size and added
   // to the available and wasted totals.
   void ClearStats() {
     accounting_stats_.ClearSize();
     free_list_.ResetStats();
     ResetFreeListStatistics();
   }
 
-  // Increases the number of available bytes of that space.
-  void AddToAccountingStats(intptr_t bytes) {
-    accounting_stats_.DeallocateBytes(bytes);
-  }
-
   // Available bytes without growing.  These are the bytes on the free list.
   // The bytes in the linear allocation area are not included in this total
   // because updating the stats would slow down allocation.  New pages are
   // immediately added to the free list so they show up here.
   intptr_t Available() override { return free_list_.Available(); }
 
   // Allocated bytes in this space.  Garbage bytes that were not found due to
   // concurrent sweeping are counted as being allocated!  The bytes in the
   // current linear allocation area (between top and limit) are also counted
   // here.
@@ skipping 35 matching lines @@
   // Allocate the requested number of bytes in the space and consider allocation
   // alignment if needed.
   MUST_USE_RESULT inline AllocationResult AllocateRaw(
       int size_in_bytes, AllocationAlignment alignment);
 
   // Give a block of memory to the space's free list.  It might be added to
   // the free list or accounted as waste.
   // If add_to_freelist is false then just accounting stats are updated and
   // no attempt to add area to free list is made.
   int Free(Address start, int size_in_bytes) {
-    int wasted = free_list_.Free(start, size_in_bytes);
+    int wasted = free_list_.Free(start, size_in_bytes, kLinkCategory);
     accounting_stats_.DeallocateBytes(size_in_bytes);
     return size_in_bytes - wasted;
   }
 
+  int UnaccountedFree(Address start, int size_in_bytes) {
+    int wasted = free_list_.Free(start, size_in_bytes, kDoNotLinkCategory);
+    return size_in_bytes - wasted;
+  }
+
   void ResetFreeList() { free_list_.Reset(); }
 
   // Set space allocation info.
   void SetTopAndLimit(Address top, Address limit) {
     DCHECK(top == limit ||
            Page::FromAddress(top) == Page::FromAddress(limit - 1));
     MemoryChunk::UpdateHighWaterMark(allocation_info_.top());
     allocation_info_.Reset(top, limit);
   }
 
   // Empty space allocation info, returning unused area to free list.
   void EmptyAllocationInfo() {
     // Mark the old linear allocation area with a free space map so it can be
     // skipped when scanning the heap.
     int old_linear_size = static_cast<int>(limit() - top());
     Free(top(), old_linear_size);
     SetTopAndLimit(NULL, NULL);
   }
 
   void Allocate(int bytes) { accounting_stats_.AllocateBytes(bytes); }
 
   void IncreaseCapacity(int size);
 
   // Releases an unused page and shrinks the space.
-  void ReleasePage(Page* page, bool evict_free_list_items);
+  void ReleasePage(Page* page);
 
   // The dummy page that anchors the linked list of pages.
   Page* anchor() { return &anchor_; }
 
 #ifdef VERIFY_HEAP
   // Verify integrity of this space.
   virtual void Verify(ObjectVisitor* visitor);
 
   // Overridden by subclasses to verify space-specific object
   // properties (e.g., only maps or free-list nodes are in map space).
@@ skipping 35 matching lines @@
   virtual bool is_local() { return false; }
 
   // Merges {other} into the current space. Note that this modifies {other},
   // e.g., removes its bump pointer area and resets statistics.
   void MergeCompactionSpace(CompactionSpace* other);
 
   // Refills the free list from the corresponding free list filled by the
   // sweeper.
   virtual void RefillFreeList();
 
+  FreeList* free_list() { return &free_list_; }
+
+  base::Mutex* mutex() { return &space_mutex_; }
+
+  inline void UnlinkFreeListCategories(Page* page);
+  inline intptr_t RelinkFreeListCategories(Page* page);
+
  protected:
-  void AddMemory(Address start, intptr_t size);
-
-  void MoveOverFreeMemory(PagedSpace* other);
-
   // PagedSpaces that should be included in snapshots have different, i.e.,
   // smaller, initial pages.
   virtual bool snapshotable() { return true; }
 
-  FreeList* free_list() { return &free_list_; }
-
   bool HasPages() { return anchor_.next_page() != &anchor_; }
 
   // 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();
 
   // Expands the space by allocating a fixed number of pages. Returns false if
   // it cannot allocate requested number of pages from OS, or if the hard heap
   // size limit has been hit.
   bool Expand();
@@ skipping 676 matching lines @@
 // -----------------------------------------------------------------------------
 // Compaction space that is used temporarily during compaction.
 
 class CompactionSpace : public PagedSpace {
  public:
   CompactionSpace(Heap* heap, AllocationSpace id, Executability executable)
       : PagedSpace(heap, id, executable) {}
 
   bool is_local() override { return true; }
 
-  void RefillFreeList() override;
-
  protected:
   // The space is temporary and not included in any snapshots.
   bool snapshotable() override { return false; }
 
   MUST_USE_RESULT HeapObject* SweepAndRetryAllocation(
       int size_in_bytes) override;
 };
 
 
 // A collection of |CompactionSpace|s used by a single compaction task.
@@ skipping 213 matching lines @@
     count = 0;
   }
   // Must be small, since an iteration is used for lookup.
   static const int kMaxComments = 64;
 };
 #endif
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_HEAP_SPACES_H_