[heap] Add two tiny free list categories.

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"
@@ skipping 706 matching lines @@
   AtomicValue<MemoryChunk*> prev_chunk_;
 
  private:
   void InitializeReservedMemory() { reservation_.Reset(); }
 
   friend class MemoryAllocator;
   friend class MemoryChunkValidator;
 };
 
 enum FreeListCategoryType {
+  kTiniest,
+  kTiny,
   kSmall,
   kMedium,
   kLarge,
   kHuge,
 
-  kFirstCategory = kSmall,
+  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);
@@ skipping 900 matching lines @@
 
 // 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:
-// 1-31 words (too small): Such small free areas are discarded for efficiency
-//   reasons. They can be reclaimed by the compactor. However the distance
-//   between top and limit may be this small.
+// kMinBlockSize-10 words (tiniest): The tiniest blocks are only used for
+//   allocation, when categories >= small do not have entries anymore.
+// 11-31 words (tiny): The tiny blocks are only used for allocation, when
+//   categories >= small do not have entries anymore.
 // 32-255 words (small): Used for allocating free space between 1-31 words in
 //   size.
 // 256-2047 words (medium): Used for allocating free space between 32-255 words
 //   in size.
 // 1048-16383 words (large): Used for allocating free space between 256-2047
 //   words in size.
 // At least 16384 words (huge): This list is for objects of 2048 words or
 //   larger. Empty pages are also added to this list.
 class FreeList {
  public:
   // This method returns how much memory can be allocated after freeing
   // maximum_freed memory.
   static inline int GuaranteedAllocatable(int maximum_freed) {
-    if (maximum_freed <= kSmallListMin) {
+    if (maximum_freed <= kTiniestListMax) {
+      // Since we are not iterating over all list entries, we cannot guarantee
+      // that we can find the maximum freed block in that free list.
       return 0;
+    } else if (maximum_freed <= kTinyListMax) {
+      return kTinyAllocationMax;
     } else if (maximum_freed <= kSmallListMax) {
       return kSmallAllocationMax;
     } else if (maximum_freed <= kMediumListMax) {
       return kMediumAllocationMax;
     } else if (maximum_freed <= kLargeListMax) {
       return kLargeAllocationMax;
     }
     return maximum_freed;
   }
 
@@ skipping 61 matching lines @@
   void Zap();
   intptr_t SumFreeLists();
   bool IsVeryLong();
 #endif
 
  private:
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kAllocatableMemory;
 
-  static const int kSmallListMin = 0x1f * kPointerSize;
+  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 kSmallAllocationMax = kSmallListMin;
+  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];
   }
 
   FreeListCategoryType SelectFreeListCategoryType(size_t size_in_bytes) {
-    if (size_in_bytes <= kSmallListMax) {
+    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;
@@ skipping 1256 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_