[heap] Concurrent store buffer processing.

src/heap/store-buffer.cc

 // 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.
 
 #include "src/heap/store-buffer.h"
 
 #include <algorithm>
 
 #include "src/counters.h"
 #include "src/heap/incremental-marking.h"
 #include "src/isolate.h"
 #include "src/objects-inl.h"
 #include "src/v8.h"
 
 namespace v8 {
 namespace internal {
 
 StoreBuffer::StoreBuffer(Heap* heap)
-    : heap_(heap),
-      top_(nullptr),
-      start_(nullptr),
-      limit_(nullptr),
-      virtual_memory_(nullptr) {}
+    : heap_(heap), top_(nullptr), current_(0), virtual_memory_(nullptr) {
+  for (int i = 0; i < kStoreBuffers; i++) {
+    start_[i] = nullptr;
+    limit_[i] = nullptr;
+    lazy_top_[i].SetValue(nullptr);
+  }
+  task_running_.SetValue(false);
+}
 
 void StoreBuffer::SetUp() {
   // Allocate 3x the buffer size, so that we can start the new store buffer
   // aligned to 2x the size.  This lets us use a bit test to detect the end of
   // the area.
-  virtual_memory_ = new base::VirtualMemory(kStoreBufferSize * 2);
+  virtual_memory_ = new base::VirtualMemory(kStoreBufferSize * 3);
   uintptr_t start_as_int =
       reinterpret_cast<uintptr_t>(virtual_memory_->address());
-  start_ = reinterpret_cast<Address*>(RoundUp(start_as_int, kStoreBufferSize));
-  limit_ = start_ + (kStoreBufferSize / kPointerSize);
+  start_[0] =
+      reinterpret_cast<Address*>(RoundUp(start_as_int, kStoreBufferSize));
+  limit_[0] = start_[0] + (kStoreBufferSize / kPointerSize);
+  start_[1] = limit_[0];
+  limit_[1] = start_[1] + (kStoreBufferSize / kPointerSize);
 
-  DCHECK(reinterpret_cast<Address>(start_) >= virtual_memory_->address());
-  DCHECK(reinterpret_cast<Address>(limit_) >= virtual_memory_->address());
   Address* vm_limit = reinterpret_cast<Address*>(
       reinterpret_cast<char*>(virtual_memory_->address()) +
       virtual_memory_->size());
-  DCHECK(start_ <= vm_limit);
-  DCHECK(limit_ <= vm_limit);
+
   USE(vm_limit);
-  DCHECK((reinterpret_cast<uintptr_t>(limit_) & kStoreBufferMask) == 0);
+  for (int i = 0; i < kStoreBuffers; i++) {
+    DCHECK(reinterpret_cast<Address>(start_[i]) >= virtual_memory_->address());
+    DCHECK(reinterpret_cast<Address>(limit_[i]) >= virtual_memory_->address());
+    DCHECK(start_[i] <= vm_limit);
+    DCHECK(limit_[i] <= vm_limit);
+    DCHECK((reinterpret_cast<uintptr_t>(limit_[i]) & kStoreBufferMask) == 0);
+  }
 
-  if (!virtual_memory_->Commit(reinterpret_cast<Address>(start_),
-                               kStoreBufferSize,
+  if (!virtual_memory_->Commit(reinterpret_cast<Address>(start_[0]),
+                               kStoreBufferSize * kStoreBuffers,
                                false)) {  // Not executable.
     V8::FatalProcessOutOfMemory("StoreBuffer::SetUp");
   }
-  top_ = start_;
+  current_ = 0;
+  top_ = start_[current_];
 }
 
 
 void StoreBuffer::TearDown() {
   delete virtual_memory_;
-  top_ = start_ = limit_ = nullptr;
+  top_ = nullptr;
+  for (int i = 0; i < kStoreBuffers; i++) {
+    start_[i] = nullptr;
+    limit_[i] = nullptr;
+    lazy_top_[i].SetValue(nullptr);
+  }
 }
 
 
 void StoreBuffer::StoreBufferOverflow(Isolate* isolate) {
-  isolate->heap()->store_buffer()->MoveEntriesToRememberedSet();
+  isolate->heap()->store_buffer()->FlipStoreBuffers();
   isolate->counters()->store_buffer_overflows()->Increment();
 }
 
-void StoreBuffer::MoveEntriesToRememberedSet() {
-  if (top_ == start_) return;
-  DCHECK(top_ <= limit_);
-  for (Address* current = start_; current < top_; current++) {
+void StoreBuffer::FlipStoreBuffers() {
+  int other = (current_ + 1) % kStoreBuffers;
+  Address* other_top = lazy_top_[other].Value();
+  if (other_top) {
+    MoveEntriesToRememberedSet(other);
+  }
+
+  lazy_top_[current_].SetValue(top_);
+  current_ = other;
+  top_ = start_[current_];
+
+  if (!task_running_.Value()) {

[ulan, 2016/10/28 09:18:01]

It could be that the task is almost finishing, but task_running_ is true. In
that case we will not start a new task and the store buffer will have to be
processed by the main thread.

Is it expected?

Since we already use mutex, I wonder if it is worth moving the mutex one level
up to FlipStoreBuffers, ConcurrentlyProcessStoreBuffer, and
MoveAllEntriesToRememberedSet? I think the lock contention would be the same
because the main work is done in MoveEntriesToRememberedSet.

The task_running would be normal variable (not atomic) and we would be able to
use current_ from the task and drain the other buffer using top_[(current_ + 1)
% kStoreBuffers]. There would be no need for atomic lazy_top_. wdyt?

[Hannes Payer (out of office), 2016/10/28 09:58:32]

I optimized for the case that Flip would not need to take a lock when the other
buffer was already processed. However, that may be a micro optimization not
necessary. The solution you outlined is even coarser grained from a locking
perspective, which results in simpler code. Since it is not clear what the
optimization buys us I will go with the simpler solution.

+    task_running_.SetValue(true);
+    Task* task = new Task(heap_->isolate(), this);
+    V8::GetCurrentPlatform()->CallOnBackgroundThread(
+        task, v8::Platform::kShortRunningTask);
+  }
+}
+
+void StoreBuffer::MoveEntriesToRememberedSet(int index) {
+  base::LockGuard<base::Mutex> guard(&mutex_);
+  Address* limit = lazy_top_[index].Value();
+  if (!limit) return;
+  DCHECK_GE(index, 0);
+  DCHECK_LT(index, kStoreBuffers);
+  for (Address* current = start_[index]; current < limit; current++) {
     DCHECK(!heap_->code_space()->Contains(*current));
     Address addr = *current;
     Page* page = Page::FromAnyPointerAddress(heap_, addr);
-    RememberedSet<OLD_TO_NEW>::Insert(page, addr);
+    if (IsDeletionAddress(addr)) {
+      current++;
+      Address end = *current;
+      DCHECK(!IsDeletionAddress(end));
+      addr = UnmarkDeletionAddress(addr);
+      if (end) {
+        RememberedSet<OLD_TO_NEW>::RemoveRange(page, addr, end,
+                                               SlotSet::PREFREE_EMPTY_BUCKETS);
+      } else {
+        RememberedSet<OLD_TO_NEW>::Remove(page, addr);
+      }
+    } else {
+      DCHECK(!IsDeletionAddress(addr));
+      RememberedSet<OLD_TO_NEW>::Insert(page, addr);
+    }
   }
-  top_ = start_;
+  lazy_top_[index].SetValue(nullptr);
+}
+
+void StoreBuffer::MoveAllEntriesToRememberedSet() {
+  int other = (current_ + 1) % kStoreBuffers;
+  Address* other_top = lazy_top_[other].Value();
+  if (other_top) {
+    MoveEntriesToRememberedSet(other);
+  }
+  lazy_top_[current_].SetValue(top_);
+  MoveEntriesToRememberedSet(current_);
+  top_ = start_[current_];
+}
+
+void StoreBuffer::ConcurrentlyProcessStoreBuffer() {
+  for (int i = 0; i < kStoreBuffers; i++) {
+    Address* top = lazy_top_[i].Value();
+    if (top) {
+      MoveEntriesToRememberedSet(i);
+    }
+  }
+  task_running_.SetValue(false);
+}
+
+void StoreBuffer::DeleteEntry(Address start, Address end) {
+  if (top_ + sizeof(Address) * 2 > limit_[current_]) {
+    StoreBufferOverflow(heap_->isolate());
+  }
+  *top_ = MarkDeletionAddress(start);
+  top_++;
+  *top_ = end;
+  top_++;
 }
 
 }  // namespace internal
 }  // namespace v8