On-the-fly bookkeeping of PagedSpace memory kept in free-lists.

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 529 matching lines @@
      kSizeOffset + kPointerSize + kPointerSize + kPointerSize +
      kPointerSize + kPointerSize +
      kPointerSize + kPointerSize + kPointerSize + kIntSize;
 
   static const size_t kSlotsBufferOffset = kLiveBytesOffset + kIntSize;
 
   static const size_t kWriteBarrierCounterOffset =
       kSlotsBufferOffset + kPointerSize + kPointerSize;
 
   static const size_t kHeaderSize = kWriteBarrierCounterOffset + kPointerSize +
-                                    kIntSize + kIntSize + kPointerSize;
+                                    kIntSize + kIntSize + kPointerSize +
+                                    5 * kPointerSize;

[Michael Starzinger, 2013/04/09 16:56:04]

As discussed offline: Can we check whether that still fits into the current page
header alignment, or if it bumps the size of the page header? If it does bump
the size we have wiggle-room with the unused "non_available_small_blocks" field
and there should be some room to squeeze the other fields together.

[Hannes Payer (out of office), 2013/04/10 07:53:49]

It still fits.

 
   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
   // code alignment to be suitable for both.  Also aligned to 32 words because
   // the marking bitmap is arranged in 32 bit chunks.
   static const int kObjectStartAlignment = 32 * kPointerSize;
   static const int kObjectStartOffset = kBodyOffset - 1 +
       (kObjectStartAlignment - (kBodyOffset - 1) % kObjectStartAlignment);
@@ skipping 156 matching lines @@
 
 
 // -----------------------------------------------------------------------------
 // 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:
+  Page();

[Michael Starzinger, 2013/04/09 16:56:04]

There should be no constructor for Pages, they should only be constructed
through the FromAddress() accessors.

[Hannes Payer (out of office), 2013/04/10 07:53:49]

Done.

   // Returns the page containing a given address. The address ranges
   // from [page_addr .. page_addr + kPageSize[
   // This only works if the object is in fact in a page.  See also MemoryChunk::
   // FromAddress() and FromAnyAddress().
   INLINE(static Page* FromAddress(Address a)) {
     return reinterpret_cast<Page*>(OffsetFrom(a) & ~kPageAlignmentMask);
   }
 
   // Returns the page containing an allocation top. Because an allocation
   // top address can be the upper bound of the page, we need to subtract
@@ skipping 53 matching lines @@
   bool WasSweptPrecisely() { return IsFlagSet(WAS_SWEPT_PRECISELY); }
   bool WasSweptConservatively() { return IsFlagSet(WAS_SWEPT_CONSERVATIVELY); }
   bool WasSwept() { return WasSweptPrecisely() || WasSweptConservatively(); }
 
   void MarkSweptPrecisely() { SetFlag(WAS_SWEPT_PRECISELY); }
   void MarkSweptConservatively() { SetFlag(WAS_SWEPT_CONSERVATIVELY); }
 
   void ClearSweptPrecisely() { ClearFlag(WAS_SWEPT_PRECISELY); }
   void ClearSweptConservatively() { ClearFlag(WAS_SWEPT_CONSERVATIVELY); }
 
+  void ResetFreeListStatistics();
+
+  intptr_t available_in_small_free_list() const {
+    return available_in_small_free_list_;
+  }
+
+  void set_available_in_small_free_list(intptr_t available_in_small_free_list) {

[Michael Starzinger, 2013/04/09 16:56:04]

Just an idea. We could use macros to generate this long tail of accessors. I
would prefer the macro approach here, but I'll leave the final decision up to
you.

[Hannes Payer (out of office), 2013/04/10 07:53:49]

Done.

+    available_in_small_free_list_ = available_in_small_free_list;
+  }
+
+  void AddAvailableInSmallFreeList(intptr_t add) {
+    available_in_small_free_list_ += add;
+  }
+
+  intptr_t available_in_medium_free_list() const {
+    return available_in_medium_free_list_;
+  }
+
+  void set_available_in_medium_free_list(
+      intptr_t available_in_medium_free_list) {
+    available_in_medium_free_list_ = available_in_medium_free_list;
+  }
+
+  void AddAvailableInMediumFreeList(intptr_t add) {
+    available_in_medium_free_list_ += add;
+  }
+
+  intptr_t available_in_large_free_list() const {
+    return available_in_large_free_list_;
+  }
+
+  void set_available_in_large_free_list(intptr_t available_in_large_free_list) {
+    available_in_large_free_list_ = available_in_large_free_list;
+  }
+
+  void AddAvailableInLargeFreeList(intptr_t add) {
+    available_in_large_free_list_ += add;
+  }
+
+  intptr_t available_in_huge_free_list() const {
+    return available_in_huge_free_list_;
+  }
+
+  void set_available_in_huge_free_list(intptr_t available_in_huge_free_list) {
+    available_in_huge_free_list_ = available_in_huge_free_list;
+  }
+
+  void AddAvailableInHugeFreeList(intptr_t add) {
+    available_in_huge_free_list_ += add;
+  }
+
+  intptr_t non_available_small_blocks() const {
+    return non_available_small_blocks_;
+  }
+
+  void set_non_available_small_blocks(intptr_t non_available_small_blocks) {
+    non_available_small_blocks_ = non_available_small_blocks;
+  }
+
+  void AddNonAvailableSmallBlocks(intptr_t add) {
+    non_available_small_blocks_ += add;
+  }
+
 #ifdef DEBUG
   void Print();
 #endif  // DEBUG
 
+ private:
+  intptr_t available_in_small_free_list_;
+  intptr_t available_in_medium_free_list_;
+  intptr_t available_in_large_free_list_;
+  intptr_t available_in_huge_free_list_;
+  intptr_t non_available_small_blocks_;
+
   friend class MemoryAllocator;
 };
 
 
 STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize);
 
 
 class LargePage : public MemoryChunk {
  public:
   HeapObject* GetObject() {
@@ skipping 611 matching lines @@
   }
 
   intptr_t Concatenate(FreeListCategory* category);
 
   void Reset();
 
   void Free(FreeListNode* node, int size_in_bytes);
 
   FreeListNode* PickNodeFromList(int *node_size);
 
-  intptr_t CountFreeListItemsInList(Page* p);
-
   intptr_t EvictFreeListItemsInList(Page* p);
 
   void RepairFreeList(Heap* heap);
 
   FreeListNode** GetTopAddress() { return &top_; }
   FreeListNode* top() const { return top_; }
   void set_top(FreeListNode* top) { top_ = top; }
 
   FreeListNode** GetEndAddress() { return &end_; }
   FreeListNode* end() const { return end_; }
@@ skipping 74 matching lines @@
 
 #ifdef DEBUG
   void Zap();
   intptr_t SumFreeLists();
   bool IsVeryLong();
 #endif
 
   // Used after booting the VM.
   void RepairLists(Heap* heap);
 
-  struct SizeStats {
-    intptr_t Total() {
-      return small_size_ + medium_size_ + large_size_ + huge_size_;
-    }
-
-    intptr_t small_size_;
-    intptr_t medium_size_;
-    intptr_t large_size_;
-    intptr_t huge_size_;
-  };
-
-  void CountFreeListItems(Page* p, SizeStats* sizes);
-
   intptr_t EvictFreeListItems(Page* p);
 
   FreeListCategory* small_list() { return &small_list_; }
   FreeListCategory* medium_list() { return &medium_list_; }
   FreeListCategory* large_list() { return &large_list_; }
   FreeListCategory* huge_list() { return &huge_list_; }
 
  private:
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
@@ skipping 64 matching lines @@
   // 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(); }
 
   // Approximate amount of physical memory committed for this space.
   size_t CommittedPhysicalMemory();
 
+  struct SizeStats {
+    intptr_t Total() {
+      return small_size_ + medium_size_ + large_size_ + huge_size_;
+    }
+
+    intptr_t small_size_;
+    intptr_t medium_size_;
+    intptr_t large_size_;
+    intptr_t huge_size_;
+  };
+
+  void ObtainFreeListStatistics(Page* p, SizeStats* sizes);
+  void ResetFreeListStatistics();
+
   // Sets the capacity, the available space and the wasted space to zero.
   // 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_.ClearSizeWaste();
+    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
@@ skipping 133 matching lines @@
   // AdvanceSweeper with size_in_bytes is called.
   bool EnsureSweeperProgress(intptr_t size_in_bytes);
 
   bool IsLazySweepingComplete() {
     return !first_unswept_page_->is_valid();
   }
 
   Page* FirstPage() { return anchor_.next_page(); }
   Page* LastPage() { return anchor_.prev_page(); }
 
-  void CountFreeListItems(Page* p, FreeList::SizeStats* sizes) {
-    free_list_.CountFreeListItems(p, sizes);
-  }
-
   void EvictEvacuationCandidatesFromFreeLists();
 
   bool CanExpand();
 
   // Returns the number of total pages in this space.
   int CountTotalPages();
 
   // Return size of allocatable area on a page in this space.
   inline int AreaSize() {
     return area_size_;
@@ skipping 1024 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_