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 | |
37 | namespace JSC { |
38 | |
39 | MarkingConstraintSet::MarkingConstraintSet(Heap& heap) |
40 | : m_heap(heap) |
41 | { |
42 | } |
43 | |
44 | MarkingConstraintSet::~MarkingConstraintSet() |
45 | { |
46 | } |
47 | |
48 | void 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 | |
68 | void 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 | |
73 | void 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 | |
83 | bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor) |
84 | { |
85 | bool result = executeConvergenceImpl(visitor); |
86 | if (Options::logGC()) |
87 | dataLog(" " ); |
88 | return result; |
89 | } |
90 | |
91 | bool 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 | |
100 | bool 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 | |
173 | void 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 | |