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