1 // Copyright 2011 the V8 project authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef V8_STORE_BUFFER_H_ 6 #define V8_STORE_BUFFER_H_ 7 8 #include "src/allocation.h" 9 #include "src/base/logging.h" 10 #include "src/base/platform/platform.h" 11 #include "src/cancelable-task.h" 12 #include "src/globals.h" 13 #include "src/heap/remembered-set.h" 14 #include "src/heap/slot-set.h" 15 16 namespace v8 { 17 namespace internal { 18 19 // Intermediate buffer that accumulates old-to-new stores from the generated 20 // code. Moreover, it stores invalid old-to-new slots with two entries. 21 // The first is a tagged address of the start of the invalid range, the second 22 // one is the end address of the invalid range or null if there is just one slot 23 // that needs to be removed from the remembered set. On buffer overflow the 24 // slots are moved to the remembered set. 25 class StoreBuffer { 26 public: 27 static const int kStoreBufferSize = 1 << (14 + kPointerSizeLog2); 28 static const int kStoreBufferMask = kStoreBufferSize - 1; 29 static const int kStoreBuffers = 2; 30 static const intptr_t kDeletionTag = 1; 31 32 V8_EXPORT_PRIVATE static void StoreBufferOverflow(Isolate* isolate); 33 34 explicit StoreBuffer(Heap* heap); 35 void SetUp(); 36 void TearDown(); 37 38 // Used to add entries from generated code. top_address()39 inline Address* top_address() { return reinterpret_cast<Address*>(&top_); } 40 41 // Moves entries from a specific store buffer to the remembered set. This 42 // method takes a lock. 43 void MoveEntriesToRememberedSet(int index); 44 45 // This method ensures that all used store buffer entries are transfered to 46 // the remembered set. 47 void MoveAllEntriesToRememberedSet(); 48 IsDeletionAddress(Address address)49 inline bool IsDeletionAddress(Address address) const { 50 return reinterpret_cast<intptr_t>(address) & kDeletionTag; 51 } 52 MarkDeletionAddress(Address address)53 inline Address MarkDeletionAddress(Address address) { 54 return reinterpret_cast<Address>(reinterpret_cast<intptr_t>(address) | 55 kDeletionTag); 56 } 57 UnmarkDeletionAddress(Address address)58 inline Address UnmarkDeletionAddress(Address address) { 59 return reinterpret_cast<Address>(reinterpret_cast<intptr_t>(address) & 60 ~kDeletionTag); 61 } 62 63 // If we only want to delete a single slot, end should be set to null which 64 // will be written into the second field. When processing the store buffer 65 // the more efficient Remove method will be called in this case. 66 void DeleteEntry(Address start, Address end = nullptr); 67 InsertEntry(Address slot)68 void InsertEntry(Address slot) { 69 // Insertions coming from the GC are directly inserted into the remembered 70 // set. Insertions coming from the runtime are added to the store buffer to 71 // allow concurrent processing. 72 if (heap_->gc_state() == Heap::NOT_IN_GC) { 73 if (top_ + sizeof(Address) > limit_[current_]) { 74 StoreBufferOverflow(heap_->isolate()); 75 } 76 *top_ = slot; 77 top_++; 78 } else { 79 // In GC the store buffer has to be empty at any time. 80 DCHECK(Empty()); 81 RememberedSet<OLD_TO_NEW>::Insert(Page::FromAddress(slot), slot); 82 } 83 } 84 85 // Used by the concurrent processing thread to transfer entries from the 86 // store buffer to the remembered set. 87 void ConcurrentlyProcessStoreBuffer(); 88 Empty()89 bool Empty() { 90 for (int i = 0; i < kStoreBuffers; i++) { 91 if (lazy_top_[i]) { 92 return false; 93 } 94 } 95 return top_ == start_[current_]; 96 } 97 98 private: 99 // There are two store buffers. If one store buffer fills up, the main thread 100 // publishes the top pointer of the store buffer that needs processing in its 101 // global lazy_top_ field. After that it start the concurrent processing 102 // thread. The concurrent processing thread uses the pointer in lazy_top_. 103 // It will grab the given mutex and transfer its entries to the remembered 104 // set. If the concurrent thread does not make progress, the main thread will 105 // perform the work. 106 // Important: there is an ordering constrained. The store buffer with the 107 // older entries has to be processed first. 108 class Task : public CancelableTask { 109 public: Task(Isolate * isolate,StoreBuffer * store_buffer)110 Task(Isolate* isolate, StoreBuffer* store_buffer) 111 : CancelableTask(isolate), store_buffer_(store_buffer) {} ~Task()112 virtual ~Task() {} 113 114 private: RunInternal()115 void RunInternal() override { 116 store_buffer_->ConcurrentlyProcessStoreBuffer(); 117 } 118 StoreBuffer* store_buffer_; 119 DISALLOW_COPY_AND_ASSIGN(Task); 120 }; 121 122 void FlipStoreBuffers(); 123 124 Heap* heap_; 125 126 Address* top_; 127 128 // The start and the limit of the buffer that contains store slots 129 // added from the generated code. We have two chunks of store buffers. 130 // Whenever one fills up, we notify a concurrent processing thread and 131 // use the other empty one in the meantime. 132 Address* start_[kStoreBuffers]; 133 Address* limit_[kStoreBuffers]; 134 135 // At most one lazy_top_ pointer is set at any time. 136 Address* lazy_top_[kStoreBuffers]; 137 base::Mutex mutex_; 138 139 // We only want to have at most one concurrent processing tas running. 140 bool task_running_; 141 142 // Points to the current buffer in use. 143 int current_; 144 145 base::VirtualMemory* virtual_memory_; 146 }; 147 148 } // namespace internal 149 } // namespace v8 150 151 #endif // V8_STORE_BUFFER_H_ 152