1/*
2 * Copyright (C) 2017 Apple Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 * 1. Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * 2. Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 *
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "MarkingConstraintSet.h"
28
29#include "JSCInlines.h"
30#include "MarkingConstraintSolver.h"
31#include "Options.h"
32#include "SimpleMarkingConstraint.h"
33#include "SuperSampler.h"
34#include <wtf/Function.h>
35#include <wtf/TimeWithDynamicClockType.h>
36
37namespace JSC {
38
39MarkingConstraintSet::MarkingConstraintSet(Heap& heap)
40 : m_heap(heap)
41{
42}
43
44MarkingConstraintSet::~MarkingConstraintSet()
45{
46}
47
48void MarkingConstraintSet::didStartMarking()
49{
50 m_unexecutedRoots.clearAll();
51 m_unexecutedOutgrowths.clearAll();
52 for (auto& constraint : m_set) {
53 constraint->resetStats();
54 switch (constraint->volatility()) {
55 case ConstraintVolatility::GreyedByExecution:
56 m_unexecutedRoots.set(constraint->index());
57 break;
58 case ConstraintVolatility::GreyedByMarking:
59 m_unexecutedOutgrowths.set(constraint->index());
60 break;
61 case ConstraintVolatility::SeldomGreyed:
62 break;
63 }
64 }
65 m_iteration = 1;
66}
67
68void MarkingConstraintSet::add(CString abbreviatedName, CString name, ::Function<void(SlotVisitor&)> function, ConstraintVolatility volatility, ConstraintConcurrency concurrency, ConstraintParallelism parallelism)
69{
70 add(std::make_unique<SimpleMarkingConstraint>(WTFMove(abbreviatedName), WTFMove(name), WTFMove(function), volatility, concurrency, parallelism));
71}
72
73void MarkingConstraintSet::add(
74 std::unique_ptr<MarkingConstraint> constraint)
75{
76 constraint->m_index = m_set.size();
77 m_ordered.append(constraint.get());
78 if (constraint->volatility() == ConstraintVolatility::GreyedByMarking)
79 m_outgrowths.append(constraint.get());
80 m_set.append(WTFMove(constraint));
81}
82
83bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor)
84{
85 bool result = executeConvergenceImpl(visitor);
86 if (Options::logGC())
87 dataLog(" ");
88 return result;
89}
90
91bool MarkingConstraintSet::isWavefrontAdvancing(SlotVisitor& visitor)
92{
93 for (MarkingConstraint* outgrowth : m_outgrowths) {
94 if (outgrowth->workEstimate(visitor))
95 return true;
96 }
97 return false;
98}
99
100bool MarkingConstraintSet::executeConvergenceImpl(SlotVisitor& visitor)
101{
102 SuperSamplerScope superSamplerScope(false);
103 MarkingConstraintSolver solver(*this);
104
105 unsigned iteration = m_iteration++;
106
107 if (Options::logGC())
108 dataLog("i#", iteration, ":");
109
110 if (iteration == 1) {
111 // First iteration is before any visitor draining, so it's unlikely to trigger any constraints
112 // other than roots.
113 solver.drain(m_unexecutedRoots);
114 return false;
115 }
116
117 if (iteration == 2) {
118 solver.drain(m_unexecutedOutgrowths);
119 return false;
120 }
121
122 // We want to keep preferring the outgrowth constraints - the ones that need to be fixpointed
123 // even in a stop-the-world GC - until they stop producing. They have a tendency to go totally
124 // silent at some point during GC, at which point it makes sense not to run them again until
125 // the end. Outgrowths producing new information corresponds almost exactly to the wavefront
126 // advancing: it usually means that we are marking objects that should be marked based on
127 // other objects that we would have marked anyway. Once the wavefront is no longer advancing,
128 // we want to run mostly the root constraints (based on their predictions of how much work
129 // they will have) because at this point we are just trying to outpace the retreating
130 // wavefront.
131 //
132 // Note that this function (executeConvergenceImpl) only returns true if it runs all
133 // constraints. So, all we are controlling are the heuristics that say which constraints to
134 // run first. Choosing the constraints that are the most likely to produce means running fewer
135 // constraints before returning.
136 bool isWavefrontAdvancing = this->isWavefrontAdvancing(visitor);
137
138 std::sort(
139 m_ordered.begin(), m_ordered.end(),
140 [&] (MarkingConstraint* a, MarkingConstraint* b) -> bool {
141 // Remember: return true if a should come before b.
142
143 auto volatilityScore = [] (MarkingConstraint* constraint) -> unsigned {
144 return constraint->volatility() == ConstraintVolatility::GreyedByMarking ? 1 : 0;
145 };
146
147 unsigned aVolatilityScore = volatilityScore(a);
148 unsigned bVolatilityScore = volatilityScore(b);
149
150 if (aVolatilityScore != bVolatilityScore) {
151 if (isWavefrontAdvancing)
152 return aVolatilityScore > bVolatilityScore;
153 else
154 return aVolatilityScore < bVolatilityScore;
155 }
156
157 double aWorkEstimate = a->workEstimate(visitor);
158 double bWorkEstimate = b->workEstimate(visitor);
159
160 if (aWorkEstimate != bWorkEstimate)
161 return aWorkEstimate > bWorkEstimate;
162
163 // This causes us to use SeldomGreyed vs GreyedByExecution as a final tie-breaker.
164 return a->volatility() > b->volatility();
165 });
166
167 solver.converge(m_ordered);
168
169 // Return true if we've converged. That happens if we did not visit anything.
170 return !solver.didVisitSomething();
171}
172
173void MarkingConstraintSet::executeAll(SlotVisitor& visitor)
174{
175 for (auto& constraint : m_set)
176 constraint->execute(visitor);
177 if (Options::logGC())
178 dataLog(" ");
179}
180
181} // namespace JSC
182
183