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 <map> 9 #include <stack> 10 11 #include "src/allocation.h" 12 #include "src/base/atomic-utils.h" 13 #include "src/utils.h" 14 15 namespace v8 { 16 namespace internal { 17 18 class HeapObject; 19 20 // This data structure stores objects that went through object layout change 21 // that potentially invalidates slots recorded concurrently. The second part 22 // of each element is the size of the corresponding object before the layout 23 // change. 24 using InvalidatedSlots = std::map<HeapObject*, int>; 25 26 // This class provides IsValid predicate that takes into account the set 27 // of invalidated objects in the given memory chunk. 28 // The sequence of queried slot must be non-decreasing. This allows fast 29 // implementation with complexity O(m*log(m) + n), where 30 // m is the number of invalidated objects in the memory chunk. 31 // n is the number of IsValid queries. 32 class InvalidatedSlotsFilter { 33 public: 34 explicit InvalidatedSlotsFilter(MemoryChunk* chunk); 35 inline bool IsValid(Address slot); 36 37 private: 38 InvalidatedSlots::const_iterator iterator_; 39 InvalidatedSlots::const_iterator iterator_end_; 40 Address sentinel_; 41 Address invalidated_start_; 42 Address invalidated_end_; 43 HeapObject* invalidated_object_; 44 int invalidated_object_size_; 45 bool slots_in_free_space_are_valid_; 46 InvalidatedSlots empty_; 47 #ifdef DEBUG 48 Address last_slot_; 49 #endif 50 }; 51 52 } // namespace internal 53 } // namespace v8 54 55 #endif // V8_HEAP_INVALIDATED_SLOTS_H_ 56