Home | History | Annotate | Download | only in src
      1 // Copyright 2011 the V8 project authors. All rights reserved.
      2 // Redistribution and use in source and binary forms, with or without
      3 // modification, are permitted provided that the following conditions are
      4 // met:
      5 //
      6 //     * Redistributions of source code must retain the above copyright
      7 //       notice, this list of conditions and the following disclaimer.
      8 //     * Redistributions in binary form must reproduce the above
      9 //       copyright notice, this list of conditions and the following
     10 //       disclaimer in the documentation and/or other materials provided
     11 //       with the distribution.
     12 //     * Neither the name of Google Inc. nor the names of its
     13 //       contributors may be used to endorse or promote products derived
     14 //       from this software without specific prior written permission.
     15 //
     16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
     17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
     18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
     19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
     20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
     22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
     26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 
     28 #ifndef V8_STORE_BUFFER_H_
     29 #define V8_STORE_BUFFER_H_
     30 
     31 #include "allocation.h"
     32 #include "checks.h"
     33 #include "globals.h"
     34 #include "platform.h"
     35 #include "v8globals.h"
     36 
     37 namespace v8 {
     38 namespace internal {
     39 
     40 class Page;
     41 class PagedSpace;
     42 class StoreBuffer;
     43 
     44 typedef void (*ObjectSlotCallback)(HeapObject** from, HeapObject* to);
     45 
     46 typedef void (StoreBuffer::*RegionCallback)(Address start,
     47                                             Address end,
     48                                             ObjectSlotCallback slot_callback,
     49                                             bool clear_maps);
     50 
     51 // Used to implement the write barrier by collecting addresses of pointers
     52 // between spaces.
     53 class StoreBuffer {
     54  public:
     55   explicit StoreBuffer(Heap* heap);
     56 
     57   static void StoreBufferOverflow(Isolate* isolate);
     58 
     59   inline Address TopAddress();
     60 
     61   void SetUp();
     62   void TearDown();
     63 
     64   // This is used by the mutator to enter addresses into the store buffer.
     65   inline void Mark(Address addr);
     66 
     67   // This is used by the heap traversal to enter the addresses into the store
     68   // buffer that should still be in the store buffer after GC.  It enters
     69   // addresses directly into the old buffer because the GC starts by wiping the
     70   // old buffer and thereafter only visits each cell once so there is no need
     71   // to attempt to remove any dupes.  During the first part of a GC we
     72   // are using the store buffer to access the old spaces and at the same time
     73   // we are rebuilding the store buffer using this function.  There is, however
     74   // no issue of overwriting the buffer we are iterating over, because this
     75   // stage of the scavenge can only reduce the number of addresses in the store
     76   // buffer (some objects are promoted so pointers to them do not need to be in
     77   // the store buffer).  The later parts of the GC scan the pages that are
     78   // exempt from the store buffer and process the promotion queue.  These steps
     79   // can overflow this buffer.  We check for this and on overflow we call the
     80   // callback set up with the StoreBufferRebuildScope object.
     81   inline void EnterDirectlyIntoStoreBuffer(Address addr);
     82 
     83   // Iterates over all pointers that go from old space to new space.  It will
     84   // delete the store buffer as it starts so the callback should reenter
     85   // surviving old-to-new pointers into the store buffer to rebuild it.
     86   void IteratePointersToNewSpace(ObjectSlotCallback callback);
     87 
     88   // Same as IteratePointersToNewSpace but additonally clears maps in objects
     89   // referenced from the store buffer that do not contain a forwarding pointer.
     90   void IteratePointersToNewSpaceAndClearMaps(ObjectSlotCallback callback);
     91 
     92   static const int kStoreBufferOverflowBit = 1 << (14 + kPointerSizeLog2);
     93   static const int kStoreBufferSize = kStoreBufferOverflowBit;
     94   static const int kStoreBufferLength = kStoreBufferSize / sizeof(Address);
     95   static const int kOldStoreBufferLength = kStoreBufferLength * 16;
     96   static const int kHashSetLengthLog2 = 12;
     97   static const int kHashSetLength = 1 << kHashSetLengthLog2;
     98 
     99   void Compact();
    100 
    101   void GCPrologue();
    102   void GCEpilogue();
    103 
    104   Object*** Limit() { return reinterpret_cast<Object***>(old_limit_); }
    105   Object*** Start() { return reinterpret_cast<Object***>(old_start_); }
    106   Object*** Top() { return reinterpret_cast<Object***>(old_top_); }
    107   void SetTop(Object*** top) {
    108     ASSERT(top >= Start());
    109     ASSERT(top <= Limit());
    110     old_top_ = reinterpret_cast<Address*>(top);
    111   }
    112 
    113   bool old_buffer_is_sorted() { return old_buffer_is_sorted_; }
    114   bool old_buffer_is_filtered() { return old_buffer_is_filtered_; }
    115 
    116   // Goes through the store buffer removing pointers to things that have
    117   // been promoted.  Rebuilds the store buffer completely if it overflowed.
    118   void SortUniq();
    119 
    120   void EnsureSpace(intptr_t space_needed);
    121   void Verify();
    122 
    123   bool PrepareForIteration();
    124 
    125 #ifdef DEBUG
    126   void Clean();
    127   // Slow, for asserts only.
    128   bool CellIsInStoreBuffer(Address cell);
    129 #endif
    130 
    131   void Filter(int flag);
    132 
    133  private:
    134   Heap* heap_;
    135 
    136   // The store buffer is divided up into a new buffer that is constantly being
    137   // filled by mutator activity and an old buffer that is filled with the data
    138   // from the new buffer after compression.
    139   Address* start_;
    140   Address* limit_;
    141 
    142   Address* old_start_;
    143   Address* old_limit_;
    144   Address* old_top_;
    145   Address* old_reserved_limit_;
    146   VirtualMemory* old_virtual_memory_;
    147 
    148   bool old_buffer_is_sorted_;
    149   bool old_buffer_is_filtered_;
    150   bool during_gc_;
    151   // The garbage collector iterates over many pointers to new space that are not
    152   // handled by the store buffer.  This flag indicates whether the pointers
    153   // found by the callbacks should be added to the store buffer or not.
    154   bool store_buffer_rebuilding_enabled_;
    155   StoreBufferCallback callback_;
    156   bool may_move_store_buffer_entries_;
    157 
    158   VirtualMemory* virtual_memory_;
    159 
    160   // Two hash sets used for filtering.
    161   // If address is in the hash set then it is guaranteed to be in the
    162   // old part of the store buffer.
    163   uintptr_t* hash_set_1_;
    164   uintptr_t* hash_set_2_;
    165   bool hash_sets_are_empty_;
    166 
    167   void ClearFilteringHashSets();
    168 
    169   bool SpaceAvailable(intptr_t space_needed);
    170   void Uniq();
    171   void ExemptPopularPages(int prime_sample_step, int threshold);
    172 
    173   // Set the map field of the object to NULL if contains a map.
    174   inline void ClearDeadObject(HeapObject *object);
    175 
    176   void IteratePointersToNewSpace(ObjectSlotCallback callback, bool clear_maps);
    177 
    178   void FindPointersToNewSpaceInRegion(Address start,
    179                                       Address end,
    180                                       ObjectSlotCallback slot_callback,
    181                                       bool clear_maps);
    182 
    183   // For each region of pointers on a page in use from an old space call
    184   // visit_pointer_region callback.
    185   // If either visit_pointer_region or callback can cause an allocation
    186   // in old space and changes in allocation watermark then
    187   // can_preallocate_during_iteration should be set to true.
    188   void IteratePointersOnPage(
    189       PagedSpace* space,
    190       Page* page,
    191       RegionCallback region_callback,
    192       ObjectSlotCallback slot_callback);
    193 
    194   void FindPointersToNewSpaceInMaps(
    195     Address start,
    196     Address end,
    197     ObjectSlotCallback slot_callback,
    198     bool clear_maps);
    199 
    200   void FindPointersToNewSpaceInMapsRegion(
    201     Address start,
    202     Address end,
    203     ObjectSlotCallback slot_callback,
    204     bool clear_maps);
    205 
    206   void FindPointersToNewSpaceOnPage(
    207     PagedSpace* space,
    208     Page* page,
    209     RegionCallback region_callback,
    210     ObjectSlotCallback slot_callback,
    211     bool clear_maps);
    212 
    213   void IteratePointersInStoreBuffer(ObjectSlotCallback slot_callback,
    214                                     bool clear_maps);
    215 
    216 #ifdef VERIFY_HEAP
    217   void VerifyPointers(PagedSpace* space, RegionCallback region_callback);
    218   void VerifyPointers(LargeObjectSpace* space);
    219 #endif
    220 
    221   friend class StoreBufferRebuildScope;
    222   friend class DontMoveStoreBufferEntriesScope;
    223 };
    224 
    225 
    226 class StoreBufferRebuildScope {
    227  public:
    228   explicit StoreBufferRebuildScope(Heap* heap,
    229                                    StoreBuffer* store_buffer,
    230                                    StoreBufferCallback callback)
    231       : store_buffer_(store_buffer),
    232         stored_state_(store_buffer->store_buffer_rebuilding_enabled_),
    233         stored_callback_(store_buffer->callback_) {
    234     store_buffer_->store_buffer_rebuilding_enabled_ = true;
    235     store_buffer_->callback_ = callback;
    236     (*callback)(heap, NULL, kStoreBufferStartScanningPagesEvent);
    237   }
    238 
    239   ~StoreBufferRebuildScope() {
    240     store_buffer_->callback_ = stored_callback_;
    241     store_buffer_->store_buffer_rebuilding_enabled_ = stored_state_;
    242   }
    243 
    244  private:
    245   StoreBuffer* store_buffer_;
    246   bool stored_state_;
    247   StoreBufferCallback stored_callback_;
    248 };
    249 
    250 
    251 class DontMoveStoreBufferEntriesScope {
    252  public:
    253   explicit DontMoveStoreBufferEntriesScope(StoreBuffer* store_buffer)
    254       : store_buffer_(store_buffer),
    255         stored_state_(store_buffer->may_move_store_buffer_entries_) {
    256     store_buffer_->may_move_store_buffer_entries_ = false;
    257   }
    258 
    259   ~DontMoveStoreBufferEntriesScope() {
    260     store_buffer_->may_move_store_buffer_entries_ = stored_state_;
    261   }
    262 
    263  private:
    264   StoreBuffer* store_buffer_;
    265   bool stored_state_;
    266 };
    267 
    268 } }  // namespace v8::internal
    269 
    270 #endif  // V8_STORE_BUFFER_H_
    271