89c606a2a3c7adb5bbf0158ad89a5a3fc4290011
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkingConstraintSolver.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 "MarkingConstraintSolver.h"
28
29 #include "JSCInlines.h"
30
31 namespace JSC { 
32
33 MarkingConstraintSolver::MarkingConstraintSolver(MarkingConstraintSet& set)
34     : m_heap(set.m_heap)
35     , m_mainVisitor(m_heap.collectorSlotVisitor())
36     , m_set(set)
37 {
38     m_heap.forEachSlotVisitor(
39         [&] (SlotVisitor& visitor) {
40             m_visitCounters.append(VisitCounter(visitor));
41         });
42 }
43
44 MarkingConstraintSolver::~MarkingConstraintSolver()
45 {
46 }
47
48 bool MarkingConstraintSolver::didVisitSomething() const
49 {
50     for (const VisitCounter& visitCounter : m_visitCounters) {
51         if (visitCounter.visitCount())
52             return true;
53     }
54     // If the number of SlotVisitors increases after creating m_visitCounters,
55     // we conservatively say there could be something visited by added SlotVisitors.
56     if (m_heap.numberOfSlotVisitors() > m_visitCounters.size())
57         return true;
58     return false;
59 }
60
61 void MarkingConstraintSolver::execute(SchedulerPreference preference, ScopedLambda<std::optional<unsigned>()> pickNext)
62 {
63     m_pickNextIsStillActive = true;
64     RELEASE_ASSERT(!m_numThreadsThatMayProduceWork);
65     
66     if (Options::useParallelMarkingConstraintSolver()) {
67         if (Options::logGC())
68             dataLog(preference == ParallelWorkFirst ? "P" : "N", "<");
69         
70         m_heap.runFunctionInParallel(
71             [&] (SlotVisitor& visitor) { runExecutionThread(visitor, preference, pickNext); });
72         
73         if (Options::logGC())
74             dataLog(">");
75     } else
76         runExecutionThread(m_mainVisitor, preference, pickNext);
77     
78     RELEASE_ASSERT(!m_pickNextIsStillActive);
79     RELEASE_ASSERT(!m_numThreadsThatMayProduceWork);
80         
81     for (unsigned indexToRun : m_didExecuteInParallel)
82         m_set.m_set[indexToRun]->finishParallelWork(m_mainVisitor);
83     m_didExecuteInParallel.clear();
84     
85     if (!m_toExecuteSequentially.isEmpty()) {
86         for (unsigned indexToRun : m_toExecuteSequentially)
87             execute(*m_set.m_set[indexToRun]);
88         m_toExecuteSequentially.clear();
89     }
90         
91     RELEASE_ASSERT(m_toExecuteInParallel.isEmpty());
92     RELEASE_ASSERT(!m_toExecuteInParallelSet.bitCount());
93 }
94
95 void MarkingConstraintSolver::drain(BitVector& unexecuted)
96 {
97     auto iter = unexecuted.begin();
98     auto end = unexecuted.end();
99     if (iter == end)
100         return;
101     auto pickNext = scopedLambda<std::optional<unsigned>()>(
102         [&] () -> std::optional<unsigned> {
103             if (iter == end)
104                 return std::nullopt;
105             return *iter++;
106         });
107     execute(NextConstraintFirst, pickNext);
108     unexecuted.clearAll();
109 }
110
111 void MarkingConstraintSolver::converge(const Vector<MarkingConstraint*>& order)
112 {
113     if (didVisitSomething())
114         return;
115     
116     if (order.isEmpty())
117         return;
118         
119     size_t index = 0;
120
121     // We want to execute the first constraint sequentially if we think it will quickly give us a
122     // result. If we ran it in parallel to other constraints, then we might end up having to wait for
123     // those other constraints to finish, which would be a waste of time since during convergence it's
124     // empirically most optimal to return to draining as soon as a constraint generates work. Most
125     // constraints don't generate any work most of the time, and when they do generate work, they tend
126     // to generate enough of it to feed a decent draining cycle. Therefore, pause times are lowest if
127     // we get the heck out of here as soon as a constraint generates work. I think that part of what
128     // makes this optimal is that we also never abort running a constraint early, so when we do run
129     // one, it has an opportunity to generate as much work as it possibly can.
130     if (order[index]->quickWorkEstimate(m_mainVisitor) > 0.) {
131         execute(*order[index++]);
132         
133         if (m_toExecuteInParallel.isEmpty()
134             && (order.isEmpty() || didVisitSomething()))
135             return;
136     }
137     
138     auto pickNext = scopedLambda<std::optional<unsigned>()>(
139         [&] () -> std::optional<unsigned> {
140             if (didVisitSomething())
141                 return std::nullopt;
142             
143             if (index >= order.size())
144                 return std::nullopt;
145             
146             MarkingConstraint& constraint = *order[index++];
147             return constraint.index();
148         });
149     
150     execute(ParallelWorkFirst, pickNext);
151 }
152
153 void MarkingConstraintSolver::execute(MarkingConstraint& constraint)
154 {
155     if (m_executed.get(constraint.index()))
156         return;
157     
158     constraint.prepareToExecute(NoLockingNecessary, m_mainVisitor);
159     ConstraintParallelism parallelism = constraint.execute(m_mainVisitor);
160     didExecute(parallelism, constraint.index());
161 }
162
163 void MarkingConstraintSolver::runExecutionThread(SlotVisitor& visitor, SchedulerPreference preference, ScopedLambda<std::optional<unsigned>()> pickNext)
164 {
165     for (;;) {
166         bool doParallelWorkMode;
167         unsigned indexToRun;
168         {
169             auto locker = holdLock(m_lock);
170                         
171             for (;;) {
172                 auto tryParallelWork = [&] () -> bool {
173                     if (m_toExecuteInParallel.isEmpty())
174                         return false;
175                     
176                     indexToRun = m_toExecuteInParallel.first();
177                     doParallelWorkMode = true;
178                     return true;
179                 };
180                             
181                 auto tryNextConstraint = [&] () -> bool {
182                     if (!m_pickNextIsStillActive)
183                         return false;
184                     
185                     for (;;) {
186                         std::optional<unsigned> pickResult = pickNext();
187                         if (!pickResult) {
188                             m_pickNextIsStillActive = false;
189                             return false;
190                         }
191                         
192                         if (m_executed.get(*pickResult))
193                             continue;
194                                     
195                         MarkingConstraint& constraint = *m_set.m_set[*pickResult];
196                         if (constraint.concurrency() == ConstraintConcurrency::Sequential) {
197                             m_toExecuteSequentially.append(*pickResult);
198                             continue;
199                         }
200                         if (constraint.parallelism() == ConstraintParallelism::Parallel)
201                             m_numThreadsThatMayProduceWork++;
202                         indexToRun = *pickResult;
203                         doParallelWorkMode = false;
204                         constraint.prepareToExecute(locker, visitor);
205                         return true;
206                     }
207                 };
208                 
209                 if (preference == ParallelWorkFirst) {
210                     if (tryParallelWork() || tryNextConstraint())
211                         break;
212                 } else {
213                     if (tryNextConstraint() || tryParallelWork())
214                         break;
215                 }
216                 
217                 // This means that we have nothing left to run. The only way for us to have more work is
218                 // if someone is running a constraint that may produce parallel work.
219                 
220                 if (!m_numThreadsThatMayProduceWork)
221                     return;
222                 
223                 // FIXME: Any waiting could be replaced with just running the SlotVisitor.
224                 // I wonder if that would be profitable.
225                 m_condition.wait(m_lock);
226             }
227         }
228                     
229         ConstraintParallelism parallelism = ConstraintParallelism::Sequential;
230                     
231         MarkingConstraint& constraint = *m_set.m_set[indexToRun];
232                     
233         if (doParallelWorkMode)
234             constraint.doParallelWork(visitor);
235         else
236             parallelism = constraint.execute(visitor);
237                     
238         {
239             auto locker = holdLock(m_lock);
240                         
241             if (doParallelWorkMode) {
242                 if (m_toExecuteInParallelSet.get(indexToRun)) {
243                     m_didExecuteInParallel.append(indexToRun);
244                                 
245                     m_toExecuteInParallel.takeFirst(
246                         [&] (unsigned value) { return value == indexToRun; });
247                     m_toExecuteInParallelSet.clear(indexToRun);
248                 }
249             } else {
250                 if (constraint.parallelism() == ConstraintParallelism::Parallel)
251                     m_numThreadsThatMayProduceWork--;
252                 m_executed.set(indexToRun);
253                 if (parallelism == ConstraintParallelism::Parallel) {
254                     m_toExecuteInParallel.append(indexToRun);
255                     m_toExecuteInParallelSet.set(indexToRun);
256                 }
257             }
258                         
259             m_condition.notifyAll();
260         }
261     }
262 }
263
264 void MarkingConstraintSolver::didExecute(ConstraintParallelism parallelism, unsigned index)
265 {
266     m_executed.set(index);
267     if (parallelism == ConstraintParallelism::Parallel) {
268         m_toExecuteInParallel.append(index);
269         m_toExecuteInParallelSet.set(index);
270     }
271 }
272
273 } // namespace JSC
274