Prepare FreeList for parallel and concurrent sweeping.

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 1357 matching lines @@
     return reinterpret_cast<FreeListNode*>(maybe);
   }
 
  private:
   static const int kNextOffset = POINTER_SIZE_ALIGN(FreeSpace::kHeaderSize);
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListNode);
 };
 
 
+struct FreeListCategorie {

[Michael Starzinger, 2012/11/27 13:51:53]

This should be a proper class with the helper functions as member methods. Also
naming it "FreeListCategory" is better I guess. Also some comments above the
class describing it's purpose would be nice.

[Hannes Payer (out of office), 2012/11/29 13:17:42]

Done. I refactored the whole free list implementation.

+  FreeListNode* top;
+  FreeListNode* end;
+};
+
+
 // 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'
 // 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 old space free list is organized in categories.
 // 1-31 words:  Such small free areas are discarded for efficiency reasons.
@@ skipping 10 matching lines @@
 //     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.
 class FreeList BASE_EMBEDDED {
  public:
   explicit FreeList(PagedSpace* owner);
 
   // Clear the free list.
   void Reset();
 
+  void Reset(struct FreeListCategorie *categorie);

[Michael Starzinger, 2012/11/27 13:51:53]

Move all of these helper functions into FreeListCategory.

[Hannes Payer (out of office), 2012/11/29 13:17:42]

Done.

+
+  // ConcurrentGetList is just safe to call when there is just one producer
+  // thread which only adds elements to the free list. ABA problem can be
+  // ignored in the given setup.
+  void ConcurrentGetList(struct FreeListCategorie *categorie,
+                         FreeListNode** top,
+                         FreeListNode** end);
+
+  void ConcurrentAddList(struct FreeListCategorie *categorie,
+                         FreeListNode* top,
+                         FreeListNode* end);
+
+  void GetList(struct FreeListCategorie *categorie,
+               FreeListNode** top,
+               FreeListNode** end);
+
+  void AddList(struct FreeListCategorie *categorie,
+               FreeListNode* top,
+               FreeListNode* end);
+
   // Return the number of bytes available on the free list.
   intptr_t available() { return 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);
 
   // 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
   // number of bytes lost to fragmentation is returned in the output parameter
   // 'wasted_bytes'.  The size should be a non-zero multiple of the word size.
   MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes);
 
 #ifdef DEBUG
   void Zap();
-  static intptr_t SumFreeList(FreeListNode* node);
-  static int FreeListLength(FreeListNode* cur);
+  static intptr_t SumFreeList(FreeListCategorie* categorie);
+  static int FreeListLength(FreeListCategorie* categorie);
   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);
 
  private:
   // The size range of blocks, in bytes.
   static const int kMinBlockSize = 3 * kPointerSize;
   static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize;
 
-  FreeListNode* PickNodeFromList(FreeListNode** list, int* node_size);
+  FreeListNode* PickNodeFromList(FreeListCategorie* categorie,
+                                 int* node_size);
 
   FreeListNode* FindNodeFor(int size_in_bytes, int* node_size);
 
   PagedSpace* owner_;
   Heap* heap_;
 
   // Total available bytes in all blocks on this free list.
   int available_;
 
   static const int kSmallListMin = 0x20 * kPointerSize;
   static const int kSmallListMax = 0xff * kPointerSize;
   static const int kMediumListMax = 0x7ff * kPointerSize;
   static const int kLargeListMax = 0x3fff * kPointerSize;
   static const int kSmallAllocationMax = kSmallListMin - kPointerSize;
   static const int kMediumAllocationMax = kSmallListMax;
   static const int kLargeAllocationMax = kMediumListMax;
-  FreeListNode* small_list_;
-  FreeListNode* medium_list_;
-  FreeListNode* large_list_;
-  FreeListNode* huge_list_;
+  struct FreeListCategorie small_list_;
+  struct FreeListCategorie medium_list_;
+  struct FreeListCategorie large_list_;
+  struct FreeListCategorie huge_list_;
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList);
 };
 
 
 class PagedSpace : public Space {
  public:
   // Creates a space with a maximum capacity, and an id.
   PagedSpace(Heap* heap,
              intptr_t max_capacity,
@@ skipping 1235 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_