src/heap/store-buffer.h

   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/globals.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15
  16 class Page;
  17 class PagedSpace;
  18 class StoreBuffer;
  19
  20 typedef void (*ObjectSlotCallback)(HeapObject** from, HeapObject* to);
  21
  22 typedef void (StoreBuffer::*RegionCallback)(Address start, Address end,
  23                                             ObjectSlotCallback slot_callback);
  24
  25 // Used to implement the write barrier by collecting addresses of pointers
  26 // between spaces.
  27 class StoreBuffer {
  28  public:
  29   explicit StoreBuffer(Heap* heap);
  30
  31   static void StoreBufferOverflow(Isolate* isolate);
  32
  33   void SetUp();
  34   void TearDown();
  35
  36   // This is used to add addresses to the store buffer non-concurrently.
  37   inline void Mark(Address addr);
  38
  39   // This is used to add addresses to the store buffer when multiple threads
  40   // may operate on the store buffer.
  41   inline void MarkSynchronized(Address addr);
  42
  43   // This is used by the heap traversal to enter the addresses into the store
  44   // buffer that should still be in the store buffer after GC.  It enters
  45   // addresses directly into the old buffer because the GC starts by wiping the
  46   // old buffer and thereafter only visits each cell once so there is no need
  47   // to attempt to remove any dupes.  During the first part of a GC we
  48   // are using the store buffer to access the old spaces and at the same time
  49   // we are rebuilding the store buffer using this function.  There is, however
  50   // no issue of overwriting the buffer we are iterating over, because this
  51   // stage of the scavenge can only reduce the number of addresses in the store
  52   // buffer (some objects are promoted so pointers to them do not need to be in
  53   // the store buffer).  The later parts of the GC scan the pages that are
  54   // exempt from the store buffer and process the promotion queue.  These steps
  55   // can overflow this buffer.  We check for this and on overflow we call the
  56   // callback set up with the StoreBufferRebuildScope object.
  57   inline void EnterDirectlyIntoStoreBuffer(Address addr);
  58
  59   // Iterates over all pointers that go from old space to new space.  It will
  60   // delete the store buffer as it starts so the callback should reenter
  61   // surviving old-to-new pointers into the store buffer to rebuild it.
  62   void IteratePointersToNewSpace(ObjectSlotCallback callback);
  63
  64   static const int kStoreBufferOverflowBit = 1 << (14 + kPointerSizeLog2);
  65   static const int kStoreBufferSize = kStoreBufferOverflowBit;
  66   static const int kStoreBufferLength = kStoreBufferSize / sizeof(Address);
  67   static const int kOldStoreBufferLength = kStoreBufferLength * 16;
  68   static const int kHashSetLengthLog2 = 12;
  69   static const int kHashSetLength = 1 << kHashSetLengthLog2;
  70
  71   void Compact();
  72
  73   void GCPrologue();
  74   void GCEpilogue();
  75
  76   Object*** Limit() { return reinterpret_cast<Object***>(old_limit_); }
  77   Object*** Start() { return reinterpret_cast<Object***>(old_start_); }
  78   Object*** Top() { return reinterpret_cast<Object***>(old_top_); }
  79   void SetTop(Object*** top) {
  80     DCHECK(top >= Start());
  81     DCHECK(top <= Limit());
  82     old_top_ = reinterpret_cast<Address*>(top);
  83   }
  84
  85   bool old_buffer_is_sorted() { return old_buffer_is_sorted_; }
  86   bool old_buffer_is_filtered() { return old_buffer_is_filtered_; }
  87
  88   void EnsureSpace(intptr_t space_needed);
  89   void Verify();
  90
  91   bool PrepareForIteration();
  92
  93   void Filter(int flag);
  94
  95   // Eliminates all stale store buffer entries from the store buffer, i.e.,
  96   // slots that are not part of live objects anymore. This method must be
  97   // called after marking, when the whole transitive closure is known and
  98   // must be called before sweeping when mark bits are still intact.
  99   void ClearInvalidStoreBufferEntries();
 100   void VerifyValidStoreBufferEntries();
 101
 102  private:
 103   Heap* heap_;
 104
 105   // The store buffer is divided up into a new buffer that is constantly being
 106   // filled by mutator activity and an old buffer that is filled with the data
 107   // from the new buffer after compression.
 108   Address* start_;
 109   Address* limit_;
 110
 111   Address* old_start_;
 112   Address* old_limit_;
 113   Address* old_top_;
 114   Address* old_reserved_limit_;
 115   base::VirtualMemory* old_virtual_memory_;
 116
 117   bool old_buffer_is_sorted_;
 118   bool old_buffer_is_filtered_;
 119   bool during_gc_;
 120   // The garbage collector iterates over many pointers to new space that are not
 121   // handled by the store buffer.  This flag indicates whether the pointers
 122   // found by the callbacks should be added to the store buffer or not.
 123   bool store_buffer_rebuilding_enabled_;
 124   StoreBufferCallback callback_;
 125   bool may_move_store_buffer_entries_;
 126
 127   base::VirtualMemory* virtual_memory_;
 128
 129   // Two hash sets used for filtering.
 130   // If address is in the hash set then it is guaranteed to be in the
 131   // old part of the store buffer.
 132   uintptr_t* hash_set_1_;
 133   uintptr_t* hash_set_2_;
 134   bool hash_sets_are_empty_;
 135
 136   // Used for synchronization of concurrent store buffer access.
 137   base::Mutex mutex_;
 138
 139   void ClearFilteringHashSets();
 140
 141   bool SpaceAvailable(intptr_t space_needed);
 142   void ExemptPopularPages(int prime_sample_step, int threshold);
 143
 144   void ProcessOldToNewSlot(Address slot_address,
 145                            ObjectSlotCallback slot_callback);
 146
 147   void FindPointersToNewSpaceInRegion(Address start, Address end,
 148                                       ObjectSlotCallback slot_callback);
 149
 150   // For each region of pointers on a page in use from an old space call
 151   // visit_pointer_region callback.
 152   // If either visit_pointer_region or callback can cause an allocation
 153   // in old space and changes in allocation watermark then
 154   // can_preallocate_during_iteration should be set to true.
 155   void IteratePointersOnPage(PagedSpace* space, Page* page,
 156                              RegionCallback region_callback,
 157                              ObjectSlotCallback slot_callback);
 158
 159   void IteratePointersInStoreBuffer(ObjectSlotCallback slot_callback);
 160
 161 #ifdef VERIFY_HEAP
 162   void VerifyPointers(LargeObjectSpace* space);
 163 #endif
 164
 165   friend class StoreBufferRebuildScope;
 166   friend class DontMoveStoreBufferEntriesScope;
 167 };
 168
 169
 170 class StoreBufferRebuilder {
 171  public:
 172   explicit StoreBufferRebuilder(StoreBuffer* store_buffer)
 173       : store_buffer_(store_buffer) {}
 174
 175   void Callback(MemoryChunk* page, StoreBufferEvent event);
 176
 177  private:
 178   StoreBuffer* store_buffer_;
 179
 180   // We record in this variable how full the store buffer was when we started
 181   // iterating over the current page, finding pointers to new space.  If the
 182   // store buffer overflows again we can exempt the page from the store buffer
 183   // by rewinding to this point instead of having to search the store buffer.
 184   Object*** start_of_current_page_;
 185   // The current page we are scanning in the store buffer iterator.
 186   MemoryChunk* current_page_;
 187 };
 188
 189
 190 class StoreBufferRebuildScope {
 191  public:
 192   explicit StoreBufferRebuildScope(Heap* heap, StoreBuffer* store_buffer,
 193                                    StoreBufferCallback callback)
 194       : store_buffer_(store_buffer),
 195         stored_state_(store_buffer->store_buffer_rebuilding_enabled_),
 196         stored_callback_(store_buffer->callback_) {
 197     store_buffer_->store_buffer_rebuilding_enabled_ = true;
 198     store_buffer_->callback_ = callback;
 199     (*callback)(heap, NULL, kStoreBufferStartScanningPagesEvent);
 200   }
 201
 202   ~StoreBufferRebuildScope() {
 203     store_buffer_->callback_ = stored_callback_;
 204     store_buffer_->store_buffer_rebuilding_enabled_ = stored_state_;
 205   }
 206
 207  private:
 208   StoreBuffer* store_buffer_;
 209   bool stored_state_;
 210   StoreBufferCallback stored_callback_;
 211 };
 212
 213
 214 class DontMoveStoreBufferEntriesScope {
 215  public:
 216   explicit DontMoveStoreBufferEntriesScope(StoreBuffer* store_buffer)
 217       : store_buffer_(store_buffer),
 218         stored_state_(store_buffer->may_move_store_buffer_entries_) {
 219     store_buffer_->may_move_store_buffer_entries_ = false;
 220   }
 221
 222   ~DontMoveStoreBufferEntriesScope() {
 223     store_buffer_->may_move_store_buffer_entries_ = stored_state_;
 224   }
 225
 226  private:
 227   StoreBuffer* store_buffer_;
 228   bool stored_state_;
 229 };
 230 }
 231 }  // namespace v8::internal
 232
 233 #endif  // V8_STORE_BUFFER_H_