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 #include "src/heap/marking-worklist.h"
6
7 #include <algorithm>
8 #include <cstddef>
9 #include <map>
10
11 #include "src/heap/cppgc-js/cpp-heap.h"
12 #include "src/heap/cppgc-js/cpp-marking-state.h"
13 #include "src/heap/marking-worklist-inl.h"
14 #include "src/objects/heap-object-inl.h"
15 #include "src/objects/heap-object.h"
16 #include "src/objects/instance-type-inl.h"
17 #include "src/objects/instance-type.h"
18 #include "src/objects/map.h"
19 #include "src/objects/objects-definitions.h"
20
21 namespace v8 {
22 namespace internal {
23
~MarkingWorklists()24 MarkingWorklists::~MarkingWorklists() {
25 DCHECK(shared_.IsEmpty());
26 DCHECK(on_hold_.IsEmpty());
27 DCHECK(other_.IsEmpty());
28 DCHECK(worklists_.empty());
29 DCHECK(context_worklists_.empty());
30 }
31
Clear()32 void MarkingWorklists::Clear() {
33 shared_.Clear();
34 on_hold_.Clear();
35 wrapper_.Clear();
36 other_.Clear();
37 for (auto cw : context_worklists_) {
38 if (cw.context == kSharedContext || cw.context == kOtherContext) {
39 // These contexts were cleared above.
40 continue;
41 }
42 cw.worklist->Clear();
43 }
44 ReleaseContextWorklists();
45 }
46
Print()47 void MarkingWorklists::Print() {
48 PrintWorklist("shared", &shared_);
49 PrintWorklist("on_hold", &on_hold_);
50 }
51
CreateContextWorklists(const std::vector<Address> & contexts)52 void MarkingWorklists::CreateContextWorklists(
53 const std::vector<Address>& contexts) {
54 DCHECK(worklists_.empty());
55 DCHECK(context_worklists_.empty());
56 if (contexts.empty()) return;
57 worklists_.reserve(contexts.size());
58 context_worklists_.reserve(contexts.size() + 2);
59 context_worklists_.push_back({kSharedContext, &shared_});
60 context_worklists_.push_back({kOtherContext, &other_});
61 for (Address context : contexts) {
62 MarkingWorklist* worklist = new MarkingWorklist();
63 worklists_.push_back(std::unique_ptr<MarkingWorklist>(worklist));
64 context_worklists_.push_back({context, worklist});
65 }
66 }
67
ReleaseContextWorklists()68 void MarkingWorklists::ReleaseContextWorklists() {
69 context_worklists_.clear();
70 worklists_.clear();
71 }
72
PrintWorklist(const char * worklist_name,MarkingWorklist * worklist)73 void MarkingWorklists::PrintWorklist(const char* worklist_name,
74 MarkingWorklist* worklist) {
75 #ifdef DEBUG
76 std::map<InstanceType, int> count;
77 int total_count = 0;
78 worklist->Iterate([&count, &total_count](HeapObject obj) {
79 ++total_count;
80 count[obj.map().instance_type()]++;
81 });
82 std::vector<std::pair<int, InstanceType>> rank;
83 rank.reserve(count.size());
84 for (const auto& i : count) {
85 rank.emplace_back(i.second, i.first);
86 }
87 std::map<InstanceType, std::string> instance_type_name;
88 #define INSTANCE_TYPE_NAME(name) instance_type_name[name] = #name;
89 INSTANCE_TYPE_LIST(INSTANCE_TYPE_NAME)
90 #undef INSTANCE_TYPE_NAME
91 std::sort(rank.begin(), rank.end(),
92 std::greater<std::pair<int, InstanceType>>());
93 PrintF("Worklist %s: %d\n", worklist_name, total_count);
94 for (auto i : rank) {
95 PrintF(" [%s]: %d\n", instance_type_name[i.second].c_str(), i.first);
96 }
97 #endif
98 }
99
100 constexpr Address MarkingWorklists::Local::kSharedContext;
101 constexpr Address MarkingWorklists::Local::kOtherContext;
102 constexpr std::nullptr_t MarkingWorklists::Local::kNoCppMarkingState;
103
Local(MarkingWorklists * global,std::unique_ptr<CppMarkingState> cpp_marking_state)104 MarkingWorklists::Local::Local(
105 MarkingWorklists* global,
106 std::unique_ptr<CppMarkingState> cpp_marking_state)
107 : on_hold_(global->on_hold()),
108 wrapper_(global->wrapper()),
109 is_per_context_mode_(false),
110 cpp_marking_state_(std::move(cpp_marking_state)) {
111 if (global->context_worklists().empty()) {
112 MarkingWorklist::Local shared(global->shared());
113 active_ = std::move(shared);
114 active_context_ = kSharedContext;
115 active_owner_ = nullptr;
116 } else {
117 is_per_context_mode_ = true;
118 worklist_by_context_.reserve(global->context_worklists().size());
119 for (auto& cw : global->context_worklists()) {
120 worklist_by_context_[cw.context] =
121 std::make_unique<MarkingWorklist::Local>(cw.worklist);
122 }
123 active_owner_ = worklist_by_context_[kSharedContext].get();
124 active_ = std::move(*active_owner_);
125 active_context_ = kSharedContext;
126 }
127 }
128
~Local()129 MarkingWorklists::Local::~Local() {
130 DCHECK(active_.IsLocalEmpty());
131 if (is_per_context_mode_) {
132 for (auto& cw : worklist_by_context_) {
133 if (cw.first != active_context_) {
134 DCHECK(cw.second->IsLocalEmpty());
135 }
136 }
137 }
138 }
139
Publish()140 void MarkingWorklists::Local::Publish() {
141 active_.Publish();
142 on_hold_.Publish();
143 wrapper_.Publish();
144 if (is_per_context_mode_) {
145 for (auto& cw : worklist_by_context_) {
146 if (cw.first != active_context_) {
147 cw.second->Publish();
148 }
149 }
150 }
151 PublishWrapper();
152 }
153
IsEmpty()154 bool MarkingWorklists::Local::IsEmpty() {
155 // This function checks the on_hold_ worklist, so it works only for the main
156 // thread.
157 if (!active_.IsLocalEmpty() || !on_hold_.IsLocalEmpty() ||
158 !active_.IsGlobalEmpty() || !on_hold_.IsGlobalEmpty()) {
159 return false;
160 }
161 if (!is_per_context_mode_) {
162 return true;
163 }
164 for (auto& cw : worklist_by_context_) {
165 if (cw.first != active_context_ &&
166 !(cw.second->IsLocalEmpty() && cw.second->IsGlobalEmpty())) {
167 SwitchToContext(cw.first, cw.second.get());
168 return false;
169 }
170 }
171 return true;
172 }
173
IsWrapperEmpty() const174 bool MarkingWorklists::Local::IsWrapperEmpty() const {
175 if (cpp_marking_state_) {
176 DCHECK(wrapper_.IsLocalAndGlobalEmpty());
177 return cpp_marking_state_->IsLocalEmpty();
178 }
179 return wrapper_.IsLocalAndGlobalEmpty();
180 }
181
ShareWork()182 void MarkingWorklists::Local::ShareWork() {
183 if (!active_.IsLocalEmpty() && active_.IsGlobalEmpty()) {
184 active_.Publish();
185 }
186 if (is_per_context_mode_ && active_context_ != kSharedContext) {
187 MarkingWorklist::Local* shared = worklist_by_context_[kSharedContext].get();
188 if (!shared->IsLocalEmpty() && shared->IsGlobalEmpty()) {
189 shared->Publish();
190 }
191 }
192 }
193
MergeOnHold()194 void MarkingWorklists::Local::MergeOnHold() {
195 MarkingWorklist::Local* shared =
196 active_context_ == kSharedContext
197 ? &active_
198 : worklist_by_context_[kSharedContext].get();
199 shared->Merge(&on_hold_);
200 }
201
PopContext(HeapObject * object)202 bool MarkingWorklists::Local::PopContext(HeapObject* object) {
203 DCHECK(is_per_context_mode_);
204 // As an optimization we first check only the local segments to avoid locks.
205 for (auto& cw : worklist_by_context_) {
206 if (cw.first != active_context_ && !cw.second->IsLocalEmpty()) {
207 SwitchToContext(cw.first, cw.second.get());
208 return active_.Pop(object);
209 }
210 }
211 // All local segments are empty. Check global segments.
212 for (auto& cw : worklist_by_context_) {
213 if (cw.first != active_context_ && cw.second->Pop(object)) {
214 SwitchToContext(cw.first, cw.second.get());
215 return true;
216 }
217 }
218 // All worklists are empty. Switch to the default shared worklist.
219 SwitchToContext(kSharedContext);
220 return false;
221 }
222
SwitchToContextSlow(Address context)223 Address MarkingWorklists::Local::SwitchToContextSlow(Address context) {
224 const auto& it = worklist_by_context_.find(context);
225 if (V8_UNLIKELY(it == worklist_by_context_.end())) {
226 // This context was created during marking or is not being measured,
227 // so we don't have a specific worklist for it.
228 SwitchToContext(kOtherContext, worklist_by_context_[kOtherContext].get());
229 } else {
230 SwitchToContext(it->first, it->second.get());
231 }
232 return active_context_;
233 }
234
235 } // namespace internal
236 } // namespace v8
237