[heap] Cleanup: Enforce coding style in FreeList and FreeListCategory

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 1566 matching lines @@
   intptr_t capacity_;
 
   // |max_capacity_|: The maximum capacity ever observed.
   intptr_t max_capacity_;
 
   // |size_|: The number of allocated bytes.
   intptr_t size_;
 };
 
 
-// -----------------------------------------------------------------------------
-// Free lists for old object spaces
-
-// The free list category holds a pointer to the top element and a pointer to
-// the end element of the linked list of free memory blocks.
+// A free list category maintains a linked list of free memory blocks.
 class FreeListCategory {
  public:
   explicit FreeListCategory(FreeList* owner, FreeListCategoryType type)
       : type_(type),
         top_(nullptr),
         end_(nullptr),
         available_(0),
         owner_(owner) {}
 
+  // Concatenates {category} into {this}.
+  //
+  // Note: Concurrency safe.

[Hannes Payer (out of office), 2015/10/15 12:23:42]

thread-safe.

[Michael Lippautz, 2015/10/15 12:31:34]

Done.

   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:
+  static const int kVeryLongFreeList = 500;

[Hannes Payer (out of office), 2015/10/15 12:23:42]

Let's add a comment that describes that constant.

[Michael Lippautz, 2015/10/15 12:31:34]

Done.

+
   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_;
 };
 
-
-// The free list for the old space.  The free list is organized in such a way
-// as 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'
+// 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
+// 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 old space free list is organized in categories.
-// 1-31 words:  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.
-// 32-255 words: There is a list of spaces this large.  It is used for top and
-//     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.
+// The free list is organized in categories as follows:
+// 1-31 words: Such small free areas are discarded for efficiency reasons. They

[Hannes Payer (out of office), 2015/10/15 12:23:42]

We could call this category "too small". WDYT?

[Michael Lippautz, 2015/10/15 12:31:34]

Done.

+//   can be reclaimed by the compactor. However the distance between top and
+//   limit may be this small.
+// 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:
-  explicit FreeList(PagedSpace* owner);
-
-  // The method concatenates {other} into {this} and returns the added bytes,
-  // including waste.
-  //
-  // Can be used concurrently.
-  intptr_t Concatenate(FreeList* other);
-
-  // Clear the free list.
-  void Reset();
-
-  void ResetStats() { wasted_bytes_ = 0; }
-
-  // Return the number of bytes available on the free list.
-  intptr_t available() {
-    return small_list_.available() + medium_list_.available() +
-           large_list_.available() + huge_list_.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
-  // freeing the block.  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);
-
   // 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) {
       return 0;
     } else if (maximum_freed <= kSmallListMax) {
       return kSmallAllocationMax;
     } else if (maximum_freed <= kMediumListMax) {
       return kMediumAllocationMax;
     } else if (maximum_freed <= kLargeListMax) {
       return kLargeAllocationMax;
     }
     return maximum_freed;
   }
 
-  // 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.
+  explicit FreeList(PagedSpace* owner);
+
+  // The method concatenates {other} into {this} and returns the added bytes,
+  // including waste.
+  //
+  // Note: Concurrency safe.

[Hannes Payer (out of office), 2015/10/15 12:23:42]

thread-safe.

[Michael Lippautz, 2015/10/15 12:31:34]

Done.

+  intptr_t Concatenate(FreeList* other);
+
+  // Place a node on the free list. The block of size {size_in_bytes} starting

[Hannes Payer (out of office), 2015/10/15 12:23:42]

Adds

[Michael Lippautz, 2015/10/15 12:31:34]

Done.

+  // 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 freeing the

[Hannes Payer (out of office), 2015/10/15 12:23:42]

...bytes that were not added to the free list, because they freed memory block
is too small.

[Michael Lippautz, 2015/10/15 12:31:34]

Done.

+  // block. 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);
+
+  // 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; }
+
+  // Return the number of bytes available on the free list.
+  intptr_t Available() {
+    return small_list_.available() + medium_list_.available() +
+           large_list_.available() + huge_list_.available();
+  }
+
   bool IsEmpty() {
     return small_list_.IsEmpty() && medium_list_.IsEmpty() &&
            large_list_.IsEmpty() && huge_list_.IsEmpty();
   }
 
-#ifdef DEBUG
-  void Zap();
-  intptr_t SumFreeLists();
-  bool IsVeryLong();
-#endif
-
   // Used after booting the VM.
   void RepairLists(Heap* heap);
 
   intptr_t EvictFreeListItems(Page* p);
   bool ContainsPageFreeListItems(Page* p);
 
   PagedSpace* owner() { return owner_; }
   intptr_t wasted_bytes() { return wasted_bytes_; }
   base::Mutex* mutex() { return &mutex_; }
 
+#ifdef DEBUG
+  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 kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kSmallAllocationMax = kSmallListMin;
@@ skipping 13 matching lines @@
         return &large_list_;
       case kHuge:
         return &huge_list_;
       default:
         UNREACHABLE();
     }
     UNREACHABLE();
     return nullptr;
   }
 
-
   PagedSpace* owner_;
-  Heap* heap_;
   base::Mutex mutex_;
   intptr_t wasted_bytes_;
   FreeListCategory small_list_;
   FreeListCategory medium_list_;
   FreeListCategory large_list_;
   FreeListCategory huge_list_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
@@ skipping 99 matching lines @@
 
   // 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(); }
+  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.
   intptr_t Size() override { return accounting_stats_.Size(); }
 
   // As size, but the bytes in lazily swept pages are estimated and the bytes
   // in the current linear allocation area are not included.
   intptr_t SizeOfObjects() override;
@@ skipping 1093 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_