c5a6c6697592f7940effa55619ef33a0d501d6ed
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkingConstraintSet.cpp
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 "Options.h"
30 #include <wtf/Function.h>
31 #include <wtf/TimeWithDynamicClockType.h>
32
33 namespace JSC {
34
35 class MarkingConstraintSet::ExecutionContext {
36 public:
37     ExecutionContext(MarkingConstraintSet& set, SlotVisitor& visitor, MonotonicTime timeout)
38         : m_set(set)
39         , m_visitor(visitor)
40         , m_timeout(timeout)
41     {
42     }
43     
44     bool didVisitSomething() const
45     {
46         return m_didVisitSomething;
47     }
48     
49     bool shouldTimeOut() const
50     {
51         return didVisitSomething() && hasElapsed(m_timeout);
52     }
53     
54     // Returns false if it times out.
55     bool drain(BitVector& unexecuted)
56     {
57         for (size_t index : unexecuted) {
58             execute(index);
59             unexecuted.clear(index);
60             if (shouldTimeOut())
61                 return false;
62         }
63         return true;
64     }
65     
66     bool didExecute(size_t index) const { return m_executed.get(index); }
67
68     void execute(size_t index)
69     {
70         m_set.m_set[index]->execute(m_visitor, m_didVisitSomething, m_timeout);
71         m_executed.set(index);
72     }
73     
74 private:
75     MarkingConstraintSet& m_set;
76     SlotVisitor& m_visitor;
77     MonotonicTime m_timeout;
78     BitVector m_executed;
79     bool m_didVisitSomething { false };
80 };
81
82 MarkingConstraintSet::MarkingConstraintSet()
83 {
84 }
85
86 MarkingConstraintSet::~MarkingConstraintSet()
87 {
88 }
89
90 void MarkingConstraintSet::didStartMarking()
91 {
92     m_unexecutedRoots.clearAll();
93     m_unexecutedOutgrowths.clearAll();
94     for (auto& constraint : m_set) {
95         constraint->resetStats();
96         switch (constraint->volatility()) {
97         case ConstraintVolatility::GreyedByExecution:
98             m_unexecutedRoots.set(constraint->index());
99             break;
100         case ConstraintVolatility::GreyedByMarking:
101             m_unexecutedOutgrowths.set(constraint->index());
102             break;
103         case ConstraintVolatility::SeldomGreyed:
104             break;
105         }
106     }
107     m_iteration = 1;
108 }
109
110 void MarkingConstraintSet::add(CString abbreviatedName, CString name, ::Function<void(SlotVisitor&, const VisitingTimeout&)> function, ConstraintVolatility volatility)
111 {
112     add(std::make_unique<MarkingConstraint>(WTFMove(abbreviatedName), WTFMove(name), WTFMove(function), volatility));
113 }
114
115 void MarkingConstraintSet::add(
116     CString abbreviatedName, CString name,
117     ::Function<void(SlotVisitor&, const VisitingTimeout&)> executeFunction,
118     ::Function<double(SlotVisitor&)> quickWorkEstimateFunction,
119     ConstraintVolatility volatility)
120 {
121     add(std::make_unique<MarkingConstraint>(WTFMove(abbreviatedName), WTFMove(name), WTFMove(executeFunction), WTFMove(quickWorkEstimateFunction), volatility));
122 }
123
124 void MarkingConstraintSet::add(
125     std::unique_ptr<MarkingConstraint> constraint)
126 {
127     constraint->m_index = m_set.size();
128     m_ordered.append(constraint.get());
129     if (constraint->volatility() == ConstraintVolatility::GreyedByMarking)
130         m_outgrowths.append(constraint.get());
131     m_set.append(WTFMove(constraint));
132 }
133
134 bool MarkingConstraintSet::executeConvergence(SlotVisitor& visitor, MonotonicTime timeout)
135 {
136     bool result = executeConvergenceImpl(visitor, timeout);
137     if (Options::logGC())
138         dataLog(" ");
139     return result;
140 }
141
142 bool MarkingConstraintSet::isWavefrontAdvancing(SlotVisitor& visitor)
143 {
144     for (MarkingConstraint* outgrowth : m_outgrowths) {
145         if (outgrowth->workEstimate(visitor))
146             return true;
147     }
148     return false;
149 }
150
151 bool MarkingConstraintSet::executeConvergenceImpl(SlotVisitor& visitor, MonotonicTime timeout)
152 {
153     ExecutionContext executionContext(*this, visitor, timeout);
154     
155     unsigned iteration = m_iteration++;
156     
157     if (Options::logGC())
158         dataLog("i#", iteration, ":");
159
160     // If there are any constraints that we have not executed at all during this cycle, then
161     // we should execute those now.
162     if (!executionContext.drain(m_unexecutedRoots))
163         return false;
164     
165     // First iteration is before any visitor draining, so it's unlikely to trigger any constraints other
166     // than roots.
167     if (iteration == 1)
168         return false;
169     
170     if (!executionContext.drain(m_unexecutedOutgrowths))
171         return false;
172     
173     // We want to keep preferring the outgrowth constraints - the ones that need to be fixpointed
174     // even in a stop-the-world GC - until they stop producing. They have a tendency to go totally
175     // silent at some point during GC, at which point it makes sense not to run them again until
176     // the end. Outgrowths producing new information corresponds almost exactly to the wavefront
177     // advancing: it usually means that we are marking objects that should be marked based on
178     // other objects that we would have marked anyway. Once the wavefront is no longer advancing,
179     // we want to run mostly the root constraints (based on their predictions of how much work
180     // they will have) because at this point we are just trying to outpace the retreating
181     // wavefront.
182     //
183     // Note that this function (executeConvergenceImpl) only returns true if it runs all
184     // constraints. So, all we are controlling are the heuristics that say which constraints to
185     // run first. Choosing the constraints that are the most likely to produce means running fewer
186     // constraints before returning.
187     bool isWavefrontAdvancing = this->isWavefrontAdvancing(visitor);
188     
189     std::sort(
190         m_ordered.begin(), m_ordered.end(),
191         [&] (MarkingConstraint* a, MarkingConstraint* b) -> bool {
192             // Remember: return true if a should come before b.
193             
194             auto volatilityScore = [] (MarkingConstraint* constraint) -> unsigned {
195                 return constraint->volatility() == ConstraintVolatility::GreyedByMarking ? 1 : 0;
196             };
197             
198             unsigned aVolatilityScore = volatilityScore(a);
199             unsigned bVolatilityScore = volatilityScore(b);
200             
201             if (aVolatilityScore != bVolatilityScore) {
202                 if (isWavefrontAdvancing)
203                     return aVolatilityScore > bVolatilityScore;
204                 else
205                     return aVolatilityScore < bVolatilityScore;
206             }
207             
208             double aWorkEstimate = a->workEstimate(visitor);
209             double bWorkEstimate = b->workEstimate(visitor);
210             
211             if (aWorkEstimate != bWorkEstimate)
212                 return aWorkEstimate > bWorkEstimate;
213             
214             // This causes us to use SeldomGreyed vs GreyedByExecution as a final tie-breaker.
215             return a->volatility() > b->volatility();
216         });
217     
218     for (MarkingConstraint* constraint : m_ordered) {
219         size_t i = constraint->index();
220         
221         if (executionContext.didExecute(i))
222             continue;
223         executionContext.execute(i);
224         
225         // Once we're in convergence, it makes the most sense to let some marking happen anytime
226         // we find work.
227         // FIXME: Maybe this should execute all constraints until timeout? Not clear if that's
228         // better or worse. Maybe even better is this:
229         // - If the visitor is empty, keep running.
230         // - If the visitor is has at least N things, return.
231         // - Else run until timeout.
232         // https://bugs.webkit.org/show_bug.cgi?id=166832
233         if (executionContext.didVisitSomething())
234             return false;
235     }
236     
237     return true;
238 }
239
240 void MarkingConstraintSet::executeAll(SlotVisitor& visitor)
241 {
242     bool didVisitSomething = false;
243     for (auto& constraint : m_set)
244         constraint->execute(visitor, didVisitSomething, MonotonicTime::infinity());
245     if (Options::logGC())
246         dataLog(" ");
247 }
248
249 } // namespace JSC
250