1 // Copyright 2017 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_HEAP_INVALIDATED_SLOTS_H_
6 #define V8_HEAP_INVALIDATED_SLOTS_H_
7 
8 #include <set>
9 #include <stack>
10 
11 #include "src/base/atomic-utils.h"
12 #include "src/objects/heap-object.h"
13 #include "src/utils/allocation.h"
14 #include "src/utils/utils.h"
15 
16 namespace v8 {
17 namespace internal {
18 
19 // This data structure stores objects that went through object layout change
20 // that potentially invalidates slots recorded concurrently. The second part
21 // of each element is the size of the corresponding object before the layout
22 // change.
23 using InvalidatedSlots = std::set<HeapObject, Object::Comparer>;
24 
25 // This class provides IsValid predicate that takes into account the set
26 // of invalidated objects in the given memory chunk.
27 // The sequence of queried slot must be non-decreasing. This allows fast
28 // implementation with complexity O(m*log(m) + n), where
29 // m is the number of invalidated objects in the memory chunk.
30 // n is the number of IsValid queries.
31 class V8_EXPORT_PRIVATE InvalidatedSlotsFilter {
32  public:
33   static InvalidatedSlotsFilter OldToOld(MemoryChunk* chunk);
34   static InvalidatedSlotsFilter OldToNew(MemoryChunk* chunk);
35 
36   explicit InvalidatedSlotsFilter(MemoryChunk* chunk,
37                                   InvalidatedSlots* invalidated_slots);
38   inline bool IsValid(Address slot);
39 
40  private:
41   InvalidatedSlots::const_iterator iterator_;
42   InvalidatedSlots::const_iterator iterator_end_;
43   Address sentinel_;
44   Address invalidated_start_;
45   Address next_invalidated_start_;
46   int invalidated_size_;
47   InvalidatedSlots empty_;
48 #ifdef DEBUG
49   Address last_slot_;
50 #endif
51 
52  private:
53   inline void NextInvalidatedObject();
54 };
55 
56 class V8_EXPORT_PRIVATE InvalidatedSlotsCleanup {
57  public:
58   static InvalidatedSlotsCleanup OldToNew(MemoryChunk* chunk);
59   static InvalidatedSlotsCleanup NoCleanup(MemoryChunk* chunk);
60 
61   explicit InvalidatedSlotsCleanup(MemoryChunk* chunk,
62                                    InvalidatedSlots* invalidated_slots);
63 
64   inline void Free(Address free_start, Address free_end);
65 
66  private:
67   InvalidatedSlots::iterator iterator_;
68   InvalidatedSlots::iterator iterator_end_;
69   InvalidatedSlots* invalidated_slots_;
70   InvalidatedSlots empty_;
71 
72   Address sentinel_;
73   Address invalidated_start_;
74 
75   inline void NextInvalidatedObject();
76 #ifdef DEBUG
77   Address last_free_;
78 #endif
79 };
80 
81 }  // namespace internal
82 }  // namespace v8
83 
84 #endif  // V8_HEAP_INVALIDATED_SLOTS_H_
85