1/*
2 * Copyright (C) 2015-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. ``AS IS'' AND ANY
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28#include <wtf/Box.h>
29#include <wtf/Condition.h>
30#include <wtf/Lock.h>
31#include <wtf/RefPtr.h>
32#include <wtf/SharedTask.h>
33#include <wtf/ThreadSafeRefCounted.h>
34#include <wtf/Threading.h>
35#include <wtf/Vector.h>
36#include <wtf/WeakRandom.h>
37#include <wtf/text/CString.h>
38
39namespace WTF {
40
41class AutomaticThread;
42class AutomaticThreadCondition;
43
44// A ParallelHelperPool is a shared pool of threads that can be asked to help with some finite-time
45// parallel activity. It's designed to work well when there are multiple concurrent tasks that may
46// all want parallel help. In that case, we don't want each task to start its own thread pool. It's
47// also designed to work well for tasks that do their own load balancing and do not wish to
48// participate in microtask-style load balancing.
49//
50// A pool can have many clients, and each client may have zero or one tasks. The pool will have up
51// to some number of threads, configurable with ParallelHelperPool::addThreads(); usually you bound
52// this by the number of CPUs. Whenever a thread is idle and it notices that some client has a
53// task, it will run the task. A task may be run on anywhere between zero and N threads, where N is
54// the number of threads in the pool. Tasks run to completion. It's expected that a task will have
55// its own custom ideas about how to participate in some parallel activity's load balancing, and it
56// will return when the parallel activity is done. For example, a parallel marking task will return
57// when the mark phase is done.
58//
59// Threads may have a choice between many tasks, since there may be many clients and each client
60// may have a task. For the marking example, that may happen if there are multiple VM instances and
61// each instance decides to start parallel marking at the same time. In that case, threads choose
62// a task at random. So long as any client has a task, all threads in the pool will continue
63// running the available tasks. Threads go idle when no client has tasks to run.
64
65class ParallelHelperPool;
66
67// A client is a placeholder for a parallel algorithm. A parallel algorithm will have a task that
68// can be run concurrently. Whenever a client has a task set (you have called setTask() or
69// setFunction()), threads in the pool may run that task. If a task returns on any thread, the
70// client will assume that the task is done and will clear the task. If the task is cleared (the
71// task runs to completion on any thread or you call finish()), any threads in the pool already
72// running the last set task(s) will continue to run them. You can wait for all of them to finish
73// by calling finish(). That method will clear the task and wait for any threads running the last
74// set task to finish. There are two known-good patterns for using a client:
75//
76// 1) Tasks intrinsically know when the algorithm reaches termination, and simply returns when
77// this happens. The main thread runs the task by doing:
78//
79// client->setFunction(
80// [=] () {
81// do things;
82// });
83// client->doSomeHelping();
84// client->finish();
85//
86// Calling doSomeHelping() ensures that the algorithm runs on at least one thread (this one).
87// Tasks will know when to complete, and will return when they are done. This will clear the
88// task to ensure that no new threads will run the task. Then, finish() clears the current task
89// and waits for any parallel tasks to finish after the main thread has finished. It's possible
90// for threads to still be running the last set task (i.e. the one set by setFunction()) even
91// after the task has been cleared. Waiting for idle ensures that no old tasks are running
92// anymore.
93//
94// You can do this more easily by using the runFunctionInParallel() helper:
95//
96// clients->runFunctionInParallel(
97// [=] () {
98// do things;
99// });
100//
101// 2) Tasks keep doing things until they are told to quit using some custom notification mechanism.
102// The main thread runs the task by doing:
103//
104// bool keepGoing = true;
105// client->setFunction(
106// [=] () {
107// while (keepGoing) {
108// do things;
109// }
110// });
111//
112// When work runs out, the main thread will inform tasks that there is no more work, and then
113// wait until no more tasks are running:
114//
115// keepGoing = false;
116// client->finish();
117//
118// This works best when the main thread doesn't actually want to run the task that it set in the
119// client. This happens for example in parallel marking. The main thread uses a somewhat
120// different marking algorithm than the helpers. The main thread may provide work that the
121// helpers steal. The main thread knows when termination is reached, and simply tells the
122// helpers to stop upon termination.
123//
124// The known-good styles of using ParallelHelperClient all involve a parallel algorithm that has
125// its own work distribution and load balancing.
126//
127// Note that it is not valid to use the same ParallelHelperClient instance from multiple threads.
128// Each thread should have its own ParallelHelperClient in that case. Failure to follow this advice
129// will lead to RELEASE_ASSERT's or worse.
130class ParallelHelperClient {
131 WTF_MAKE_NONCOPYABLE(ParallelHelperClient);
132 WTF_MAKE_FAST_ALLOCATED;
133public:
134 WTF_EXPORT_PRIVATE ParallelHelperClient(RefPtr<ParallelHelperPool>&&);
135 WTF_EXPORT_PRIVATE ~ParallelHelperClient();
136
137 WTF_EXPORT_PRIVATE void setTask(RefPtr<SharedTask<void ()>>&&);
138
139 template<typename Functor>
140 void setFunction(const Functor& functor)
141 {
142 setTask(createSharedTask<void ()>(functor));
143 }
144
145 WTF_EXPORT_PRIVATE void finish();
146
147 WTF_EXPORT_PRIVATE void doSomeHelping();
148
149 // Equivalent to:
150 // client->setTask(task);
151 // client->doSomeHelping();
152 // client->finish();
153 WTF_EXPORT_PRIVATE void runTaskInParallel(RefPtr<SharedTask<void ()>>&&);
154
155 // Equivalent to:
156 // client->setFunction(functor);
157 // client->doSomeHelping();
158 // client->finish();
159 template<typename Functor>
160 void runFunctionInParallel(const Functor& functor)
161 {
162 runTaskInParallel(createSharedTask<void ()>(functor));
163 }
164
165 ParallelHelperPool& pool() { return *m_pool; }
166 unsigned numberOfActiveThreads() const { return m_numActive; }
167
168private:
169 friend class ParallelHelperPool;
170
171 void finish(const AbstractLocker&);
172 RefPtr<SharedTask<void ()>> claimTask(const AbstractLocker&);
173 void runTask(const RefPtr<SharedTask<void ()>>&);
174
175 RefPtr<ParallelHelperPool> m_pool;
176 RefPtr<SharedTask<void ()>> m_task;
177 unsigned m_numActive { 0 };
178};
179
180class ParallelHelperPool : public ThreadSafeRefCounted<ParallelHelperPool> {
181public:
182 WTF_EXPORT_PRIVATE ParallelHelperPool(CString&& threadName);
183 WTF_EXPORT_PRIVATE ~ParallelHelperPool();
184
185 WTF_EXPORT_PRIVATE void ensureThreads(unsigned numThreads);
186
187 unsigned numberOfThreads() const { return m_numThreads; }
188
189 WTF_EXPORT_PRIVATE void doSomeHelping();
190
191private:
192 friend class ParallelHelperClient;
193 class Thread;
194 friend class Thread;
195
196 void didMakeWorkAvailable(const AbstractLocker&);
197
198 bool hasClientWithTask(const AbstractLocker&);
199 ParallelHelperClient* getClientWithTask(const AbstractLocker&);
200 ParallelHelperClient* waitForClientWithTask(const AbstractLocker&);
201
202 Box<Lock> m_lock; // AutomaticThread wants this in a box for safety.
203 Ref<AutomaticThreadCondition> m_workAvailableCondition;
204 Condition m_workCompleteCondition;
205
206 WeakRandom m_random;
207
208 Vector<ParallelHelperClient*> m_clients;
209 Vector<RefPtr<AutomaticThread>> m_threads;
210 CString m_threadName;
211 unsigned m_numThreads { 0 }; // This can be larger than m_threads.size() because we start threads only once there is work.
212 bool m_isDying { false };
213};
214
215} // namespace WTF
216
217using WTF::ParallelHelperClient;
218using WTF::ParallelHelperPool;
219