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#pragma once
27
28#include "VisitCounter.h"
29#include <wtf/BitVector.h>
30#include <wtf/Condition.h>
31#include <wtf/Deque.h>
32#include <wtf/FastMalloc.h>
33#include <wtf/Lock.h>
34#include <wtf/Noncopyable.h>
35#include <wtf/ScopedLambda.h>
36#include <wtf/Vector.h>
37
38namespace JSC {
39
40class Heap;
41class MarkingConstraint;
42class MarkingConstraintSet;
43
44class MarkingConstraintSolver {
45 WTF_MAKE_NONCOPYABLE(MarkingConstraintSolver);
46 WTF_MAKE_FAST_ALLOCATED;
47
48public:
49 MarkingConstraintSolver(MarkingConstraintSet&);
50 ~MarkingConstraintSolver();
51
52 bool didVisitSomething() const;
53
54 enum SchedulerPreference {
55 ParallelWorkFirst,
56 NextConstraintFirst
57 };
58
59 void execute(SchedulerPreference, ScopedLambda<Optional<unsigned>()> pickNext);
60
61 void drain(BitVector& unexecuted);
62
63 void converge(const Vector<MarkingConstraint*>& order);
64
65 void execute(MarkingConstraint&);
66
67 // Parallel constraints can add parallel tasks.
68 void addParallelTask(RefPtr<SharedTask<void(SlotVisitor&)>>, MarkingConstraint&);
69
70private:
71 void runExecutionThread(SlotVisitor&, SchedulerPreference, ScopedLambda<Optional<unsigned>()> pickNext);
72
73 struct TaskWithConstraint {
74 TaskWithConstraint() { }
75
76 TaskWithConstraint(RefPtr<SharedTask<void(SlotVisitor&)>> task, MarkingConstraint* constraint)
77 : task(WTFMove(task))
78 , constraint(constraint)
79 {
80 }
81
82 bool operator==(const TaskWithConstraint& other) const
83 {
84 return task == other.task
85 && constraint == other.constraint;
86 }
87
88 RefPtr<SharedTask<void(SlotVisitor&)>> task;
89 MarkingConstraint* constraint { nullptr };
90 };
91
92 Heap& m_heap;
93 SlotVisitor& m_mainVisitor;
94 MarkingConstraintSet& m_set;
95 BitVector m_executed;
96 Deque<TaskWithConstraint, 32> m_toExecuteInParallel;
97 Vector<unsigned, 32> m_toExecuteSequentially;
98 Lock m_lock;
99 Condition m_condition;
100 bool m_pickNextIsStillActive { true };
101 unsigned m_numThreadsThatMayProduceWork { 0 };
102 Vector<VisitCounter, 16> m_visitCounters;
103};
104
105} // namespace JSC
106
107