store-buffer.h 7.74 KB
Newer Older
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4

5 6
#ifndef V8_HEAP_STORE_BUFFER_H_
#define V8_HEAP_STORE_BUFFER_H_
7

8
#include "src/allocation.h"
9 10
#include "src/base/logging.h"
#include "src/base/platform/platform.h"
11
#include "src/cancelable-task.h"
12
#include "src/globals.h"
13
#include "src/heap/gc-tracer.h"
14
#include "src/heap/remembered-set.h"
ulan's avatar
ulan committed
15
#include "src/heap/slot-set.h"
16 17 18 19

namespace v8 {
namespace internal {

20
// Intermediate buffer that accumulates old-to-new stores from the generated
21 22 23 24 25
// code. Moreover, it stores invalid old-to-new slots with two entries.
// The first is a tagged address of the start of the invalid range, the second
// one is the end address of the invalid range or null if there is just one slot
// that needs to be removed from the remembered set. On buffer overflow the
// slots are moved to the remembered set.
26 27
class StoreBuffer {
 public:
28 29
  enum StoreBufferMode { IN_GC, NOT_IN_GC };

30
  static const int kStoreBufferSize = 1 << (11 + kPointerSizeLog2);
31
  static const int kStoreBufferMask = kStoreBufferSize - 1;
32 33
  static const int kStoreBuffers = 2;
  static const intptr_t kDeletionTag = 1;
34

35
  V8_EXPORT_PRIVATE static int StoreBufferOverflow(Isolate* isolate);
36 37

  explicit StoreBuffer(Heap* heap);
38
  void SetUp();
39 40
  void TearDown();

41 42
  // Used to add entries from generated code.
  inline Address* top_address() { return reinterpret_cast<Address*>(&top_); }
43

44 45 46 47
  // Moves entries from a specific store buffer to the remembered set. This
  // method takes a lock.
  void MoveEntriesToRememberedSet(int index);

48
  // This method ensures that all used store buffer entries are transferred to
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
  // the remembered set.
  void MoveAllEntriesToRememberedSet();

  inline bool IsDeletionAddress(Address address) const {
    return reinterpret_cast<intptr_t>(address) & kDeletionTag;
  }

  inline Address MarkDeletionAddress(Address address) {
    return reinterpret_cast<Address>(reinterpret_cast<intptr_t>(address) |
                                     kDeletionTag);
  }

  inline Address UnmarkDeletionAddress(Address address) {
    return reinterpret_cast<Address>(reinterpret_cast<intptr_t>(address) &
                                     ~kDeletionTag);
  }

  // If we only want to delete a single slot, end should be set to null which
  // will be written into the second field. When processing the store buffer
  // the more efficient Remove method will be called in this case.
69 70 71 72 73 74 75 76 77 78 79
  void DeleteEntry(Address start, Address end = nullptr) {
    // Deletions coming from the GC are directly deleted from the remembered
    // set. Deletions coming from the runtime are added to the store buffer
    // to allow concurrent processing.
    deletion_callback(this, start, end);
  }

  static void DeleteDuringGarbageCollection(StoreBuffer* store_buffer,
                                            Address start, Address end) {
    // In GC the store buffer has to be empty at any time.
    DCHECK(store_buffer->Empty());
80
    DCHECK(store_buffer->mode() != StoreBuffer::NOT_IN_GC);
81 82 83 84 85 86 87 88 89 90 91
    Page* page = Page::FromAddress(start);
    if (end) {
      RememberedSet<OLD_TO_NEW>::RemoveRange(page, start, end,
                                             SlotSet::PREFREE_EMPTY_BUCKETS);
    } else {
      RememberedSet<OLD_TO_NEW>::Remove(page, start);
    }
  }

  static void DeleteDuringRuntime(StoreBuffer* store_buffer, Address start,
                                  Address end) {
92
    DCHECK(store_buffer->mode() == StoreBuffer::NOT_IN_GC);
93 94 95 96 97 98 99 100 101 102 103 104 105 106 107
    store_buffer->InsertDeletionIntoStoreBuffer(start, end);
  }

  void InsertDeletionIntoStoreBuffer(Address start, Address end) {
    if (top_ + sizeof(Address) * 2 > limit_[current_]) {
      StoreBufferOverflow(heap_->isolate());
    }
    *top_ = MarkDeletionAddress(start);
    top_++;
    *top_ = end;
    top_++;
  }

  static void InsertDuringGarbageCollection(StoreBuffer* store_buffer,
                                            Address slot) {
108
    DCHECK(store_buffer->mode() != StoreBuffer::NOT_IN_GC);
109 110 111 112
    RememberedSet<OLD_TO_NEW>::Insert(Page::FromAddress(slot), slot);
  }

  static void InsertDuringRuntime(StoreBuffer* store_buffer, Address slot) {
113
    DCHECK(store_buffer->mode() == StoreBuffer::NOT_IN_GC);
114 115 116 117 118 119 120 121 122 123
    store_buffer->InsertIntoStoreBuffer(slot);
  }

  void InsertIntoStoreBuffer(Address slot) {
    if (top_ + sizeof(Address) > limit_[current_]) {
      StoreBufferOverflow(heap_->isolate());
    }
    *top_ = slot;
    top_++;
  }
124

125 126 127 128
  void InsertEntry(Address slot) {
    // Insertions coming from the GC are directly inserted into the remembered
    // set. Insertions coming from the runtime are added to the store buffer to
    // allow concurrent processing.
129 130 131
    insertion_callback(this, slot);
  }

132 133 134
  void SetMode(StoreBufferMode mode) {
    mode_ = mode;
    if (mode == NOT_IN_GC) {
135 136
      insertion_callback = &InsertDuringRuntime;
      deletion_callback = &DeleteDuringRuntime;
137
    } else {
138 139
      insertion_callback = &InsertDuringGarbageCollection;
      deletion_callback = &DeleteDuringGarbageCollection;
140 141 142
    }
  }

143 144 145 146 147 148 149 150 151 152 153 154
  // Used by the concurrent processing thread to transfer entries from the
  // store buffer to the remembered set.
  void ConcurrentlyProcessStoreBuffer();

  bool Empty() {
    for (int i = 0; i < kStoreBuffers; i++) {
      if (lazy_top_[i]) {
        return false;
      }
    }
    return top_ == start_[current_];
  }
155

156 157
  Heap* heap() { return heap_; }

158
 private:
159 160 161 162 163 164 165 166 167 168 169 170
  // There are two store buffers. If one store buffer fills up, the main thread
  // publishes the top pointer of the store buffer that needs processing in its
  // global lazy_top_ field. After that it start the concurrent processing
  // thread. The concurrent processing thread uses the pointer in lazy_top_.
  // It will grab the given mutex and transfer its entries to the remembered
  // set. If the concurrent thread does not make progress, the main thread will
  // perform the work.
  // Important: there is an ordering constrained. The store buffer with the
  // older entries has to be processed first.
  class Task : public CancelableTask {
   public:
    Task(Isolate* isolate, StoreBuffer* store_buffer)
171 172 173
        : CancelableTask(isolate),
          store_buffer_(store_buffer),
          tracer_(isolate->heap()->tracer()) {}
174 175 176 177
    virtual ~Task() {}

   private:
    void RunInternal() override {
178 179
      TRACE_BACKGROUND_GC(tracer_,
                          GCTracer::BackgroundScope::BACKGROUND_STORE_BUFFER);
180 181 182
      store_buffer_->ConcurrentlyProcessStoreBuffer();
    }
    StoreBuffer* store_buffer_;
183
    GCTracer* tracer_;
184 185 186
    DISALLOW_COPY_AND_ASSIGN(Task);
  };

187 188
  StoreBufferMode mode() const { return mode_; }

189 190
  void FlipStoreBuffers();

191 192
  Heap* heap_;

193 194
  Address* top_;

ulan's avatar
ulan committed
195
  // The start and the limit of the buffer that contains store slots
196 197 198 199 200 201 202 203 204 205 206 207 208 209 210
  // added from the generated code. We have two chunks of store buffers.
  // Whenever one fills up, we notify a concurrent processing thread and
  // use the other empty one in the meantime.
  Address* start_[kStoreBuffers];
  Address* limit_[kStoreBuffers];

  // At most one lazy_top_ pointer is set at any time.
  Address* lazy_top_[kStoreBuffers];
  base::Mutex mutex_;

  // We only want to have at most one concurrent processing tas running.
  bool task_running_;

  // Points to the current buffer in use.
  int current_;
211

212 213 214 215 216
  // During GC, entries are directly added to the remembered set without
  // going through the store buffer. This is signaled by a special
  // IN_GC mode.
  StoreBufferMode mode_;

217
  VirtualMemory virtual_memory_;
218 219 220

  // Callbacks are more efficient than reading out the gc state for every
  // store buffer operation.
221 222
  void (*insertion_callback)(StoreBuffer*, Address);
  void (*deletion_callback)(StoreBuffer*, Address, Address);
223 224
};

225 226
}  // namespace internal
}  // namespace v8
227

228
#endif  // V8_HEAP_STORE_BUFFER_H_