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/heap/memory-chunk-layout.h"
13#include "src/objects/heap-object.h"
14#include "src/utils/allocation.h"
15#include "src/utils/utils.h"
16
17namespace v8 {
18namespace internal {
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.
24using InvalidatedSlots = std::set<HeapObject, Object::Comparer>;
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.
32class V8_EXPORT_PRIVATE InvalidatedSlotsFilter {
33 public:
34  static InvalidatedSlotsFilter OldToOld(MemoryChunk* chunk);
35  static InvalidatedSlotsFilter OldToNew(MemoryChunk* chunk);
36
37  inline bool IsValid(Address slot);
38
39 private:
40  explicit InvalidatedSlotsFilter(MemoryChunk* chunk,
41                                  InvalidatedSlots* invalidated_slots,
42                                  RememberedSetType remembered_set_type);
43
44  InvalidatedSlots::const_iterator iterator_;
45  InvalidatedSlots::const_iterator iterator_end_;
46  Address sentinel_;
47  Address invalidated_start_;
48  Address next_invalidated_start_;
49  int invalidated_size_;
50  InvalidatedSlots empty_;
51#ifdef DEBUG
52  Address last_slot_;
53  RememberedSetType remembered_set_type_;
54#endif
55
56 private:
57  inline void NextInvalidatedObject();
58};
59
60class V8_EXPORT_PRIVATE InvalidatedSlotsCleanup {
61 public:
62  static InvalidatedSlotsCleanup OldToNew(MemoryChunk* chunk);
63  static InvalidatedSlotsCleanup NoCleanup(MemoryChunk* chunk);
64
65  explicit InvalidatedSlotsCleanup(MemoryChunk* chunk,
66                                   InvalidatedSlots* invalidated_slots);
67
68  inline void Free(Address free_start, Address free_end);
69
70 private:
71  InvalidatedSlots::iterator iterator_;
72  InvalidatedSlots::iterator iterator_end_;
73  InvalidatedSlots* invalidated_slots_;
74  InvalidatedSlots empty_;
75
76  Address sentinel_;
77  Address invalidated_start_;
78
79  inline void NextInvalidatedObject();
80#ifdef DEBUG
81  Address last_free_;
82#endif
83};
84
85}  // namespace internal
86}  // namespace v8
87
88#endif  // V8_HEAP_INVALIDATED_SLOTS_H_
89