1 // Copyright 2019 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_MARKING_WORKLIST_H_ 6 #define V8_HEAP_MARKING_WORKLIST_H_ 7 8 #include <unordered_map> 9 #include <vector> 10 11 #include "src/heap/base/worklist.h" 12 #include "src/heap/marking.h" 13 #include "src/objects/heap-object.h" 14 15 namespace v8 { 16 namespace internal { 17 18 // The index of the main thread task used by concurrent/parallel GC. 19 const int kMainThreadTask = 0; 20 21 using MarkingWorklist = ::heap::base::Worklist<HeapObject, 64>; 22 using EmbedderTracingWorklist = ::heap::base::Worklist<HeapObject, 16>; 23 24 // We piggyback on marking to compute object sizes per native context that is 25 // needed for the new memory measurement API. The algorithm works as follows: 26 // 1) At the start of marking we create a marking worklist for each context. 27 // The existing shared, on_hold, and embedder worklists continue to work 28 // as they did before, but they hold objects that are not attributed to any 29 // context yet. 30 // 2) Each marker has an active worklist where it pushes newly discovered 31 // objects. Initially the shared worklist is set as active for all markers. 32 // 3) When a marker pops an object from the active worklist: 33 // a) It checks if the object has a known context (e.g. JSObjects, Maps, 34 // Contexts know the context they belong to). If that's the case, then 35 // the marker changes its active worklist to the worklist corresponding 36 // to the context of the object. 37 // b) It account the size of object to the active context. 38 // c) It visits all pointers in the object and pushes new objects onto the 39 // active worklist. 40 // 4) When the active worklist becomes empty the marker selects any other 41 // non-empty worklist as the active worklist. 42 // 5) The write barrier pushes onto the shared worklist. 43 // 44 // The main invariant for context worklists: 45 // If object X is in the worklist of context C, then either 46 // a) X has a context and that context is C. 47 // b) X is retained by object Y that has context C. 48 // 49 // The algorithm allows us to attribute context-independent objects such as 50 // strings, numbers, FixedArrays to their retaining contexts. The algorithm is 51 // not precise for context-independent objects that are shared between multiple 52 // contexts. Such objects may be attributed to any retaining context. 53 54 // Named pair of native context address and its marking worklist. 55 // Since native contexts are allocated in the old generation, their addresses 56 // a stable across Scavenges and stay valid throughout the marking phase. 57 struct ContextWorklistPair { 58 Address context; 59 MarkingWorklist* worklist; 60 }; 61 62 // A helper class that owns all global marking worklists. 63 class V8_EXPORT_PRIVATE MarkingWorklists { 64 public: 65 class Local; 66 // Fake addresses of special contexts used for per-context accounting. 67 // - kSharedContext is for objects that are not attributed to any context. 68 // - kOtherContext is for objects that are attributed to contexts that are 69 // not being measured. 70 static const Address kSharedContext = 0; 71 static const Address kOtherContext = 8; 72 73 MarkingWorklists() = default; 74 ~MarkingWorklists(); 75 76 // Calls the specified callback on each element of the deques and replaces 77 // the element with the result of the callback. If the callback returns 78 // nullptr then the element is removed from the deque. 79 // The callback must accept HeapObject and return HeapObject. 80 template <typename Callback> 81 void Update(Callback callback); 82 shared()83 MarkingWorklist* shared() { return &shared_; } on_hold()84 MarkingWorklist* on_hold() { return &on_hold_; } embedder()85 EmbedderTracingWorklist* embedder() { return &embedder_; } 86 87 // A list of (context, worklist) pairs that was set up at the start of 88 // marking by CreateContextWorklists. context_worklists()89 const std::vector<ContextWorklistPair>& context_worklists() const { 90 return context_worklists_; 91 } 92 // This should be invoked at the start of marking with the list of contexts 93 // that require object size accounting. 94 void CreateContextWorklists(const std::vector<Address>& contexts); 95 // This should be invoked at the end of marking. All worklists must be 96 // empty at that point. 97 void ReleaseContextWorklists(); 98 99 void Clear(); 100 void Print(); 101 102 private: 103 // Prints the stats about the global pool of the worklist. 104 void PrintWorklist(const char* worklist_name, MarkingWorklist* worklist); 105 106 // Worklist used for most objects. 107 MarkingWorklist shared_; 108 109 // Concurrent marking uses this worklist to bail out of marking objects 110 // in new space's linear allocation area. Used to avoid black allocation 111 // for new space. This allow the compiler to remove write barriers 112 // for freshly allocatd objects. 113 MarkingWorklist on_hold_; 114 115 // Worklist for objects that potentially require embedder tracing, i.e., 116 // these objects need to be handed over to the embedder to find the full 117 // transitive closure. 118 EmbedderTracingWorklist embedder_; 119 120 // Per-context worklists. 121 std::vector<ContextWorklistPair> context_worklists_; 122 // This is used only for lifetime management of the per-context worklists. 123 std::vector<std::unique_ptr<MarkingWorklist>> worklists_; 124 125 // Worklist used for objects that are attributed to contexts that are 126 // not being measured. 127 MarkingWorklist other_; 128 }; 129 130 // A thread-local view of the marking worklists. It owns all local marking 131 // worklists and keeps track of the currently active local marking worklist 132 // for per-context marking. In order to avoid additional indirections for 133 // pushing and popping entries, the active_ worklist is not a pointer to 134 // Local but an actual instance of Local with the following invariants: 135 // - active_owner == worlist_by_context[active_context_].get() 136 // - *active_owner is empty (all fields are null) because its content has 137 // been moved to active_. 138 class V8_EXPORT_PRIVATE MarkingWorklists::Local { 139 public: 140 static const Address kSharedContext = MarkingWorklists::kSharedContext; 141 static const Address kOtherContext = MarkingWorklists::kOtherContext; 142 143 explicit Local(MarkingWorklists* global); 144 ~Local(); 145 146 inline void Push(HeapObject object); 147 inline bool Pop(HeapObject* object); 148 149 inline void PushOnHold(HeapObject object); 150 inline bool PopOnHold(HeapObject* object); 151 152 inline void PushEmbedder(HeapObject object); 153 inline bool PopEmbedder(HeapObject* object); 154 155 void Publish(); 156 bool IsEmpty(); 157 bool IsEmbedderEmpty() const; 158 // Publishes the local active marking worklist if its global worklist is 159 // empty. In the per-context marking mode it also publishes the shared 160 // worklist. 161 void ShareWork(); 162 // Merges the on-hold worklist to the shared worklist. 163 void MergeOnHold(); 164 165 // Returns the context of the active worklist. Context()166 Address Context() const { return active_context_; } 167 inline Address SwitchToContext(Address context); 168 inline Address SwitchToShared(); IsPerContextMode()169 bool IsPerContextMode() const { return is_per_context_mode_; } 170 171 private: 172 bool PopContext(HeapObject* object); 173 Address SwitchToContextSlow(Address context); 174 inline void SwitchToContext(Address context, 175 MarkingWorklist::Local* worklist); 176 MarkingWorklist::Local on_hold_; 177 EmbedderTracingWorklist::Local embedder_; 178 MarkingWorklist::Local active_; 179 Address active_context_; 180 MarkingWorklist::Local* active_owner_; 181 bool is_per_context_mode_; 182 std::unordered_map<Address, std::unique_ptr<MarkingWorklist::Local>> 183 worklist_by_context_; 184 }; 185 186 } // namespace internal 187 } // namespace v8 188 189 #endif // V8_HEAP_MARKING_WORKLIST_H_ 190