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
37namespace v8 {
38namespace internal {
39
40class Page;
41class PagedSpace;
42class StoreBuffer;
43
44typedef void (*ObjectSlotCallback)(HeapObject** from, HeapObject* to);
45
46typedef 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.
53class 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
226class 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
251class 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