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;
 
   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 133 matching lines @@
   intptr_t write_barrier_counter_;
   // Used by the incremental marker to keep track of the scanning progress in
   // large objects that have a progress bar and are scanned in increments.
   int progress_bar_;
   // Assuming the initial allocation on a page is sequential,
   // count highest number of bytes ever allocated on the page.
   int high_water_mark_;
 
   intptr_t parallel_sweeping_;
 
+  // PagedSpace free-list statistics.
+  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_;
+
   static MemoryChunk* Initialize(Heap* heap,
                                  Address base,
                                  size_t size,
                                  Address area_start,
                                  Address area_end,
                                  Executability executable,
                                  Space* owner);
 
   friend class MemoryAllocator;
 };
@@ skipping 76 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();
+
+#define FRAGMENTATION_STATS_ACCESSORS(type, name) \
+  type name() { return name##_; }                 \
+  void set_##name(type name) { name##_ = name; }  \
+  void add_##name(type name) { name##_ += name; }
+
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, non_available_small_blocks)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_small_free_list)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_medium_free_list)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_large_free_list)
+  FRAGMENTATION_STATS_ACCESSORS(intptr_t, available_in_huge_free_list)
+
+#undef FRAGMENTATION_STATS_ACCESSORS
+
 #ifdef DEBUG
   void Print();
 #endif  // DEBUG
 
   friend class MemoryAllocator;
 };
 
 
 STATIC_CHECK(sizeof(Page) <= MemoryChunk::kHeaderSize);
 
@@ skipping 615 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_