Home | History | Annotate | Download | only in heap 
      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   enum StoreBufferMode { IN_GC, NOT_IN_GC };
     28 
     29   static const int kStoreBufferSize = 1 << (11 + kPointerSizeLog2);
     30   static const int kStoreBufferMask = kStoreBufferSize - 1;
     31   static const int kStoreBuffers = 2;
     32   static const intptr_t kDeletionTag = 1;
     33 
     34   V8_EXPORT_PRIVATE static void StoreBufferOverflow(Isolate* isolate);
     35 
     36   explicit StoreBuffer(Heap* heap);
     37   void SetUp();
     38   void TearDown();
     39 
     40   // Used to add entries from generated code.
     41   inline Address* top_address() { return reinterpret_cast<Address*>(&top_); }
     42 
     43   // Moves entries from a specific store buffer to the remembered set. This
     44   // method takes a lock.
     45   void MoveEntriesToRememberedSet(int index);
     46 
     47   // This method ensures that all used store buffer entries are transfered to
     48   // the remembered set.
     49   void MoveAllEntriesToRememberedSet();
     50 
     51   inline bool IsDeletionAddress(Address address) const {
     52     return reinterpret_cast<intptr_t>(address) & kDeletionTag;
     53   }
     54 
     55   inline Address MarkDeletionAddress(Address address) {
     56     return reinterpret_cast<Address>(reinterpret_cast<intptr_t>(address) |
     57                                      kDeletionTag);
     58   }
     59 
     60   inline Address UnmarkDeletionAddress(Address address) {
     61     return reinterpret_cast<Address>(reinterpret_cast<intptr_t>(address) &
     62                                      ~kDeletionTag);
     63   }
     64 
     65   // If we only want to delete a single slot, end should be set to null which
     66   // will be written into the second field. When processing the store buffer
     67   // the more efficient Remove method will be called in this case.
     68   void DeleteEntry(Address start, Address end = nullptr) {
     69     // Deletions coming from the GC are directly deleted from the remembered
     70     // set. Deletions coming from the runtime are added to the store buffer
     71     // to allow concurrent processing.
     72     deletion_callback(this, start, end);
     73   }
     74 
     75   static void DeleteDuringGarbageCollection(StoreBuffer* store_buffer,
     76                                             Address start, Address end) {
     77     // In GC the store buffer has to be empty at any time.
     78     DCHECK(store_buffer->Empty());
     79     DCHECK(store_buffer->mode() != StoreBuffer::NOT_IN_GC);
     80     Page* page = Page::FromAddress(start);
     81     if (end) {
     82       RememberedSet<OLD_TO_NEW>::RemoveRange(page, start, end,
     83                                              SlotSet::PREFREE_EMPTY_BUCKETS);
     84     } else {
     85       RememberedSet<OLD_TO_NEW>::Remove(page, start);
     86     }
     87   }
     88 
     89   static void DeleteDuringRuntime(StoreBuffer* store_buffer, Address start,
     90                                   Address end) {
     91     DCHECK(store_buffer->mode() == StoreBuffer::NOT_IN_GC);
     92     store_buffer->InsertDeletionIntoStoreBuffer(start, end);
     93   }
     94 
     95   void InsertDeletionIntoStoreBuffer(Address start, Address end) {
     96     if (top_ + sizeof(Address) * 2 > limit_[current_]) {
     97       StoreBufferOverflow(heap_->isolate());
     98     }
     99     *top_ = MarkDeletionAddress(start);
    100     top_++;
    101     *top_ = end;
    102     top_++;
    103   }
    104 
    105   static void InsertDuringGarbageCollection(StoreBuffer* store_buffer,
    106                                             Address slot) {
    107     DCHECK(store_buffer->mode() != StoreBuffer::NOT_IN_GC);
    108     RememberedSet<OLD_TO_NEW>::Insert(Page::FromAddress(slot), slot);
    109   }
    110 
    111   static void InsertDuringRuntime(StoreBuffer* store_buffer, Address slot) {
    112     DCHECK(store_buffer->mode() == StoreBuffer::NOT_IN_GC);
    113     store_buffer->InsertIntoStoreBuffer(slot);
    114   }
    115 
    116   void InsertIntoStoreBuffer(Address slot) {
    117     if (top_ + sizeof(Address) > limit_[current_]) {
    118       StoreBufferOverflow(heap_->isolate());
    119     }
    120     *top_ = slot;
    121     top_++;
    122   }
    123 
    124   void InsertEntry(Address slot) {
    125     // Insertions coming from the GC are directly inserted into the remembered
    126     // set. Insertions coming from the runtime are added to the store buffer to
    127     // allow concurrent processing.
    128     insertion_callback(this, slot);
    129   }
    130 
    131   void SetMode(StoreBufferMode mode) {
    132     mode_ = mode;
    133     if (mode == NOT_IN_GC) {
    134       insertion_callback = &InsertDuringRuntime;
    135       deletion_callback = &DeleteDuringRuntime;
    136     } else {
    137       insertion_callback = &InsertDuringGarbageCollection;
    138       deletion_callback = &DeleteDuringGarbageCollection;
    139     }
    140   }
    141 
    142   // Used by the concurrent processing thread to transfer entries from the
    143   // store buffer to the remembered set.
    144   void ConcurrentlyProcessStoreBuffer();
    145 
    146   bool Empty() {
    147     for (int i = 0; i < kStoreBuffers; i++) {
    148       if (lazy_top_[i]) {
    149         return false;
    150       }
    151     }
    152     return top_ == start_[current_];
    153   }
    154 
    155   Heap* heap() { return heap_; }
    156 
    157  private:
    158   // There are two store buffers. If one store buffer fills up, the main thread
    159   // publishes the top pointer of the store buffer that needs processing in its
    160   // global lazy_top_ field. After that it start the concurrent processing
    161   // thread. The concurrent processing thread uses the pointer in lazy_top_.
    162   // It will grab the given mutex and transfer its entries to the remembered
    163   // set. If the concurrent thread does not make progress, the main thread will
    164   // perform the work.
    165   // Important: there is an ordering constrained. The store buffer with the
    166   // older entries has to be processed first.
    167   class Task : public CancelableTask {
    168    public:
    169     Task(Isolate* isolate, StoreBuffer* store_buffer)
    170         : CancelableTask(isolate), store_buffer_(store_buffer) {}
    171     virtual ~Task() {}
    172 
    173    private:
    174     void RunInternal() override {
    175       store_buffer_->ConcurrentlyProcessStoreBuffer();
    176     }
    177     StoreBuffer* store_buffer_;
    178     DISALLOW_COPY_AND_ASSIGN(Task);
    179   };
    180 
    181   StoreBufferMode mode() const { return mode_; }
    182 
    183   void FlipStoreBuffers();
    184 
    185   Heap* heap_;
    186 
    187   Address* top_;
    188 
    189   // The start and the limit of the buffer that contains store slots
    190   // added from the generated code. We have two chunks of store buffers.
    191   // Whenever one fills up, we notify a concurrent processing thread and
    192   // use the other empty one in the meantime.
    193   Address* start_[kStoreBuffers];
    194   Address* limit_[kStoreBuffers];
    195 
    196   // At most one lazy_top_ pointer is set at any time.
    197   Address* lazy_top_[kStoreBuffers];
    198   base::Mutex mutex_;
    199 
    200   // We only want to have at most one concurrent processing tas running.
    201   bool task_running_;
    202 
    203   // Points to the current buffer in use.
    204   int current_;
    205 
    206   // During GC, entries are directly added to the remembered set without
    207   // going through the store buffer. This is signaled by a special
    208   // IN_GC mode.
    209   StoreBufferMode mode_;
    210 
    211   base::VirtualMemory* virtual_memory_;
    212 
    213   // Callbacks are more efficient than reading out the gc state for every
    214   // store buffer operation.
    215   void (*insertion_callback)(StoreBuffer*, Address);
    216   void (*deletion_callback)(StoreBuffer*, Address, Address);
    217 };
    218 
    219 }  // namespace internal
    220 }  // namespace v8
    221 
    222 #endif  // V8_STORE_BUFFER_H_
    223