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 436 matching lines @@
   // Set or clear multiple flags at a time. The flags in the mask
   // are set to the value in "flags", the rest retain the current value
   // in flags_.
   void SetFlags(intptr_t flags, intptr_t mask) {
     flags_ = (flags_ & ~mask) | (flags & mask);
   }
 
   // Return all current flags.
   intptr_t GetFlags() { return flags_; }
 
+  intptr_t parallel_sweeping() const {
+    return parallel_sweeping_;
+  }
+
+  void set_parallel_sweeping(intptr_t state) {
+    parallel_sweeping_ = state;
+  }
+
+  bool TryParallelSweeping() {
+    return NoBarrier_CompareAndSwap(&parallel_sweeping_, 1, 0) == 1;
+  }
+
   // Manage live byte count (count of bytes known to be live,
   // because they are marked black).
   void ResetLiveBytes() {
     if (FLAG_gc_verbose) {
       PrintF("ResetLiveBytes:%p:%x->0\n",
              static_cast<void*>(this), live_byte_count_);
     }
     live_byte_count_ = 0;
   }
   void IncrementLiveBytes(int by) {
@@ skipping 59 matching lines @@
   static const intptr_t kLiveBytesOffset =
      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;
+  static const size_t kHeaderSize = kWriteBarrierCounterOffset + kPointerSize +
+                                    kIntSize + kIntSize + 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 131 matching lines @@
   SlotsBuffer* slots_buffer_;
   SkipList* skip_list_;
   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_;
+
   static MemoryChunk* Initialize(Heap* heap,
                                  Address base,
                                  size_t size,
                                  Address area_start,
                                  Address area_end,
                                  Executability executable,
                                  Space* owner);
 
   friend class MemoryAllocator;
 };
@@ skipping 689 matching lines @@
   static const int kNextOffset = POINTER_SIZE_ALIGN(FreeSpace::kHeaderSize);
 
   DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListNode);
 };
 
 
 // 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.
 class FreeListCategory {
  public:
-  FreeListCategory() : top_(NULL), end_(NULL), available_(0) {}
+  FreeListCategory() :
+      top_(NULL),
+      end_(NULL),
+      mutex_(OS::CreateMutex()),
+      available_(0) {}
+
+  ~FreeListCategory() {
+    delete mutex_;
+  }
+
+  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_; }
   void set_end(FreeListNode* end) { end_ = end; }
 
   int* GetAvailableAddress() { return &available_; }
   int available() const { return available_; }
   void set_available(int available) { available_ = available; }
 
+  Mutex* mutex() { return mutex_; }
+
 #ifdef DEBUG
   intptr_t SumFreeList();
   int FreeListLength();
 #endif
 
  private:
   FreeListNode* top_;
   FreeListNode* end_;
+  Mutex* mutex_;
 
   // Total available bytes in all blocks of this free list category.
   int available_;
 };
 
 
 // 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
@@ skipping 13 matching lines @@
 //     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.
 class FreeList BASE_EMBEDDED {
  public:
   explicit FreeList(PagedSpace* owner);
 
+  intptr_t Concatenate(FreeList* free_list);
+
   // Clear the free list.
   void Reset();
 
   // 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'
@@ skipping 27 matching lines @@
     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;
   static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize;
 
   FreeListNode* FindNodeFor(int size_in_bytes, int* node_size);
 
   PagedSpace* owner_;
   Heap* heap_;
 
@@ skipping 194 matching lines @@
     unswept_free_bytes_ += (p->area_size() - p->LiveBytes());
   }
 
   void DecreaseUnsweptFreeBytes(Page* p) {
     ASSERT(ShouldBeSweptLazily(p));
     unswept_free_bytes_ -= (p->area_size() - p->LiveBytes());
   }
 
   bool AdvanceSweeper(intptr_t bytes_to_sweep);
 
+  // When parallel sweeper threads are active this function waits
+  // for them to complete, otherwise AdvanceSweeper with size_in_bytes
+  // is called.
+  bool EnsureSweeperProgress(intptr_t size_in_bytes);
+
   bool IsSweepingComplete() {
     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_;
   }
 
  protected:
+  FreeList* free_list() { return &free_list_; }
+
+  void AddToAccountingStats(intptr_t bytes) {
+    accounting_stats_.DeallocateBytes(bytes);
+  }
+
   int area_size_;
 
   // Maximum capacity of this space.
   intptr_t max_capacity_;
 
   intptr_t SizeOfFirstPage();
 
   // Accounting information for this space.
   AllocationStats accounting_stats_;
 
@@ skipping 29 matching lines @@
   bool Expand();
 
   // Generic fast case allocation function that tries linear allocation at the
   // address denoted by top in allocation_info_.
   inline HeapObject* AllocateLinearly(int size_in_bytes);
 
   // Slow path of AllocateRaw.  This function is space-dependent.
   MUST_USE_RESULT virtual HeapObject* SlowAllocateRaw(int size_in_bytes);
 
   friend class PageIterator;
+  friend class SweeperThread;
 };
 
 
 class NumberAndSizeInfo BASE_EMBEDDED {
  public:
   NumberAndSizeInfo() : number_(0), bytes_(0) {}
 
   int number() const { return number_; }
   void increment_number(int num) { number_ += num; }
 
@@ skipping 964 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_