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