blob: 067ef2d5d80064f4fb3904d642a96447f15b5af7 [file] [log] [blame]
Elliott Hughes1aa246d2012-12-13 09:29:36 -08001/*
2 * Copyright (C) 2012 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070017#include "thread_pool.h"
18
Elliott Hughes1aa246d2012-12-13 09:29:36 -080019#include "base/casts.h"
20#include "base/stl_util.h"
21#include "runtime.h"
22#include "thread.h"
23
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070024namespace art {
25
26ThreadPoolWorker::ThreadPoolWorker(ThreadPool* thread_pool, const std::string& name,
27 size_t stack_size)
28 : thread_pool_(thread_pool),
29 name_(name),
30 stack_size_(stack_size) {
31 const char* reason = "new thread pool worker thread";
Brian Carlstrombcc29262012-11-02 11:36:03 -070032 pthread_attr_t attr;
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070033 CHECK_PTHREAD_CALL(pthread_attr_init, (&attr), reason);
34 CHECK_PTHREAD_CALL(pthread_attr_setstacksize, (&attr, stack_size), reason);
35 CHECK_PTHREAD_CALL(pthread_create, (&pthread_, &attr, &Callback, this), reason);
36 CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attr), reason);
37}
38
39ThreadPoolWorker::~ThreadPoolWorker() {
40 CHECK_PTHREAD_CALL(pthread_join, (pthread_, NULL), "thread pool worker shutdown");
41}
42
43void ThreadPoolWorker::Run() {
44 Thread* self = Thread::Current();
Mathieu Chartier02b6a782012-10-26 13:51:26 -070045 Task* task = NULL;
Mathieu Chartier35883cc2012-11-13 14:08:12 -080046 thread_pool_->creation_barier_.Wait(self);
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070047 while ((task = thread_pool_->GetTask(self)) != NULL) {
48 task->Run(self);
Mathieu Chartier02b6a782012-10-26 13:51:26 -070049 task->Finalize();
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070050 }
51}
52
53void* ThreadPoolWorker::Callback(void* arg) {
54 ThreadPoolWorker* worker = reinterpret_cast<ThreadPoolWorker*>(arg);
55 Runtime* runtime = Runtime::Current();
Mathieu Chartier664bebf2012-11-12 16:54:11 -080056 CHECK(runtime->AttachCurrentThread(worker->name_.c_str(), true, NULL, false));
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070057 // Do work until its time to shut down.
58 worker->Run();
59 runtime->DetachCurrentThread();
60 return NULL;
61}
62
Brian Carlstrom2ce745c2013-07-17 17:44:30 -070063void ThreadPool::AddTask(Thread* self, Task* task) {
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070064 MutexLock mu(self, task_queue_lock_);
65 tasks_.push_back(task);
66 // If we have any waiters, signal one.
67 if (waiting_count_ != 0) {
68 task_queue_condition_.Signal(self);
69 }
70}
71
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070072ThreadPool::ThreadPool(size_t num_threads)
73 : task_queue_lock_("task queue lock"),
74 task_queue_condition_("task queue condition", task_queue_lock_),
75 completion_condition_("task completion condition", task_queue_lock_),
76 started_(false),
77 shutting_down_(false),
Mathieu Chartier35883cc2012-11-13 14:08:12 -080078 waiting_count_(0),
Ian Rogersd914eb22013-04-18 16:11:15 -070079 start_time_(0),
80 total_wait_time_(0),
Mathieu Chartier35883cc2012-11-13 14:08:12 -080081 // Add one since the caller of constructor waits on the barrier too.
82 creation_barier_(num_threads + 1) {
83 Thread* self = Thread::Current();
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070084 while (GetThreadCount() < num_threads) {
Mathieu Chartier02b6a782012-10-26 13:51:26 -070085 const std::string name = StringPrintf("Thread pool worker %zu", GetThreadCount());
86 threads_.push_back(new ThreadPoolWorker(this, name, ThreadPoolWorker::kDefaultStackSize));
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070087 }
Mathieu Chartier35883cc2012-11-13 14:08:12 -080088 // Wait for all of the threads to attach.
89 creation_barier_.Wait(self);
Mathieu Chartier0e4627e2012-10-23 16:13:36 -070090}
91
92ThreadPool::~ThreadPool() {
Mathieu Chartiere46cd752012-10-31 16:56:18 -070093 {
94 Thread* self = Thread::Current();
95 MutexLock mu(self, task_queue_lock_);
96 // Tell any remaining workers to shut down.
97 shutting_down_ = true;
Mathieu Chartiere46cd752012-10-31 16:56:18 -070098 // Broadcast to everyone waiting.
99 task_queue_condition_.Broadcast(self);
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700100 completion_condition_.Broadcast(self);
Mathieu Chartiere46cd752012-10-31 16:56:18 -0700101 }
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700102 // Wait for the threads to finish.
103 STLDeleteElements(&threads_);
104}
105
106void ThreadPool::StartWorkers(Thread* self) {
107 MutexLock mu(self, task_queue_lock_);
108 started_ = true;
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700109 task_queue_condition_.Broadcast(self);
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700110 start_time_ = NanoTime();
111 total_wait_time_ = 0;
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700112}
113
114void ThreadPool::StopWorkers(Thread* self) {
115 MutexLock mu(self, task_queue_lock_);
116 started_ = false;
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700117}
118
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700119Task* ThreadPool::GetTask(Thread* self) {
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700120 MutexLock mu(self, task_queue_lock_);
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700121 while (!IsShuttingDown()) {
122 Task* task = TryGetTaskLocked(self);
123 if (task != NULL) {
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700124 return task;
125 }
126
127 waiting_count_++;
128 if (waiting_count_ == GetThreadCount() && tasks_.empty()) {
129 // We may be done, lets broadcast to the completion condition.
130 completion_condition_.Broadcast(self);
131 }
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700132 const uint64_t wait_start = NanoTime();
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700133 task_queue_condition_.Wait(self);
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700134 const uint64_t wait_end = NanoTime();
135 total_wait_time_ += wait_end - std::max(wait_start, start_time_);
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700136 waiting_count_--;
137 }
138
139 // We are shutting down, return NULL to tell the worker thread to stop looping.
140 return NULL;
141}
142
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700143Task* ThreadPool::TryGetTask(Thread* self) {
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700144 MutexLock mu(self, task_queue_lock_);
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700145 return TryGetTaskLocked(self);
146}
147
148Task* ThreadPool::TryGetTaskLocked(Thread* self) {
149 if (started_ && !tasks_.empty()) {
150 Task* task = tasks_.front();
151 tasks_.pop_front();
152 return task;
153 }
154 return NULL;
155}
156
Ian Rogers1d54e732013-05-02 21:10:01 -0700157void ThreadPool::Wait(Thread* self, bool do_work, bool may_hold_locks) {
158 if (do_work) {
159 Task* task = NULL;
160 while ((task = TryGetTask(self)) != NULL) {
161 task->Run(self);
162 task->Finalize();
163 }
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700164 }
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700165 // Wait until each thread is waiting and the task list is empty.
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700166 MutexLock mu(self, task_queue_lock_);
167 while (!shutting_down_ && (waiting_count_ != GetThreadCount() || !tasks_.empty())) {
Ian Rogers1d54e732013-05-02 21:10:01 -0700168 if (!may_hold_locks) {
169 completion_condition_.Wait(self);
170 } else {
171 completion_condition_.WaitHoldingLocks(self);
172 }
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700173 }
174}
175
Brian Carlstrom2ce745c2013-07-17 17:44:30 -0700176size_t ThreadPool::GetTaskCount(Thread* self) {
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700177 MutexLock mu(self, task_queue_lock_);
178 return tasks_.size();
179}
180
181WorkStealingWorker::WorkStealingWorker(ThreadPool* thread_pool, const std::string& name,
182 size_t stack_size)
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700183 : ThreadPoolWorker(thread_pool, name, stack_size), task_(NULL) {}
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700184
185void WorkStealingWorker::Run() {
186 Thread* self = Thread::Current();
187 Task* task = NULL;
188 WorkStealingThreadPool* thread_pool = down_cast<WorkStealingThreadPool*>(thread_pool_);
189 while ((task = thread_pool_->GetTask(self)) != NULL) {
190 WorkStealingTask* stealing_task = down_cast<WorkStealingTask*>(task);
191
192 {
193 CHECK(task_ == NULL);
194 MutexLock mu(self, thread_pool->work_steal_lock_);
195 // Register that we are running the task
196 ++stealing_task->ref_count_;
197 task_ = stealing_task;
198 }
199 stealing_task->Run(self);
200 // Mark ourselves as not running a task so that nobody tries to steal from us.
201 // There is a race condition that someone starts stealing from us at this point. This is okay
202 // due to the reference counting.
203 task_ = NULL;
204
205 bool finalize;
206
207 // Steal work from tasks until there is none left to steal. Note: There is a race, but
208 // all that happens when the race occurs is that we steal some work instead of processing a
209 // task from the queue.
210 while (thread_pool->GetTaskCount(self) == 0) {
211 WorkStealingTask* steal_from_task = NULL;
212
213 {
214 MutexLock mu(self, thread_pool->work_steal_lock_);
215 // Try finding a task to steal from.
216 steal_from_task = thread_pool->FindTaskToStealFrom(self);
217 if (steal_from_task != NULL) {
218 CHECK_NE(stealing_task, steal_from_task)
219 << "Attempting to steal from completed self task";
220 steal_from_task->ref_count_++;
221 } else {
222 break;
223 }
224 }
225
226 if (steal_from_task != NULL) {
227 // Task which completed earlier is going to steal some work.
228 stealing_task->StealFrom(self, steal_from_task);
229
230 {
231 // We are done stealing from the task, lets decrement its reference count.
232 MutexLock mu(self, thread_pool->work_steal_lock_);
233 finalize = !--steal_from_task->ref_count_;
234 }
235
236 if (finalize) {
237 steal_from_task->Finalize();
238 }
239 }
240 }
241
242 {
243 MutexLock mu(self, thread_pool->work_steal_lock_);
244 // If nobody is still referencing task_ we can finalize it.
245 finalize = !--stealing_task->ref_count_;
246 }
247
248 if (finalize) {
249 stealing_task->Finalize();
250 }
251 }
252}
253
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700254WorkStealingWorker::~WorkStealingWorker() {}
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700255
256WorkStealingThreadPool::WorkStealingThreadPool(size_t num_threads)
257 : ThreadPool(0),
258 work_steal_lock_("work stealing lock"),
259 steal_index_(0) {
260 while (GetThreadCount() < num_threads) {
261 const std::string name = StringPrintf("Work stealing worker %zu", GetThreadCount());
262 threads_.push_back(new WorkStealingWorker(this, name, ThreadPoolWorker::kDefaultStackSize));
263 }
264}
265
266WorkStealingTask* WorkStealingThreadPool::FindTaskToStealFrom(Thread* self) {
267 const size_t thread_count = GetThreadCount();
268 for (size_t i = 0; i < thread_count; ++i) {
269 // TODO: Use CAS instead of lock.
270 ++steal_index_;
271 if (steal_index_ >= thread_count) {
272 steal_index_-= thread_count;
273 }
274
275 WorkStealingWorker* worker = down_cast<WorkStealingWorker*>(threads_[steal_index_]);
276 WorkStealingTask* task = worker->task_;
277 if (task) {
278 // Not null, we can probably steal from this worker.
279 return task;
280 }
281 }
282 // Couldn't find something to steal.
283 return NULL;
284}
285
Brian Carlstrom0cd7ec22013-07-17 23:40:20 -0700286WorkStealingThreadPool::~WorkStealingThreadPool() {}
Mathieu Chartier02b6a782012-10-26 13:51:26 -0700287
Mathieu Chartier0e4627e2012-10-23 16:13:36 -0700288} // namespace art