11aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes/* 21aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * Copyright (C) 2012 The Android Open Source Project 31aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * 41aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * Licensed under the Apache License, Version 2.0 (the "License"); 51aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * you may not use this file except in compliance with the License. 61aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * You may obtain a copy of the License at 71aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * 81aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * http://www.apache.org/licenses/LICENSE-2.0 91aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * 101aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * Unless required by applicable law or agreed to in writing, software 111aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * distributed under the License is distributed on an "AS IS" BASIS, 121aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * See the License for the specific language governing permissions and 141aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes * limitations under the License. 151aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes */ 161aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes 171aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include "thread_pool.h" 181aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes 191aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include "base/casts.h" 201aa246dec5abe212f699de1413a0c4a191ca364aElliott Hughes#include "base/stl_util.h" 2141b175aba41c9365a1c53b8a1afbd17129c87c14Vladimir Marko#include "base/time_utils.h" 220e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier#include "runtime.h" 23a3d2718d1fac53210b2a311b1728409d6c8e7b9dBrian Carlstrom#include "thread-inl.h" 240e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 250e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiernamespace art { 260e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 27720ef7680573c1afd12f99f02eee3045daee5168Mathieu Chartierstatic constexpr bool kMeasureWaitTime = false; 2894c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier 290e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPoolWorker::ThreadPoolWorker(ThreadPool* thread_pool, const std::string& name, 300e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier size_t stack_size) 310e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier : thread_pool_(thread_pool), 32bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier name_(name) { 33bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier std::string error_msg; 34bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier stack_.reset(MemMap::MapAnonymous(name.c_str(), nullptr, stack_size, PROT_READ | PROT_WRITE, 355c42c29b89286e5efa4a4613132b09051ce5945bVladimir Marko false, false, &error_msg)); 36bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier CHECK(stack_.get() != nullptr) << error_msg; 370e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier const char* reason = "new thread pool worker thread"; 38bcc2926b9721f94c17ed98fae5264cc98f0e066fBrian Carlstrom pthread_attr_t attr; 390e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_attr_init, (&attr), reason); 40bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier CHECK_PTHREAD_CALL(pthread_attr_setstack, (&attr, stack_->Begin(), stack_->Size()), reason); 410e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_create, (&pthread_, &attr, &Callback, this), reason); 420e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attr), reason); 430e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 440e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 450e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPoolWorker::~ThreadPoolWorker() { 466a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers CHECK_PTHREAD_CALL(pthread_join, (pthread_, nullptr), "thread pool worker shutdown"); 470e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 480e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 490e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid ThreadPoolWorker::Run() { 500e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier Thread* self = Thread::Current(); 516a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers Task* task = nullptr; 5235883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier thread_pool_->creation_barier_.Wait(self); 536a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers while ((task = thread_pool_->GetTask(self)) != nullptr) { 540e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task->Run(self); 5502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier task->Finalize(); 560e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 570e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 580e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 590e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid* ThreadPoolWorker::Callback(void* arg) { 600e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier ThreadPoolWorker* worker = reinterpret_cast<ThreadPoolWorker*>(arg); 610e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier Runtime* runtime = Runtime::Current(); 626a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers CHECK(runtime->AttachCurrentThread(worker->name_.c_str(), true, nullptr, false)); 630e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // Do work until its time to shut down. 640e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier worker->Run(); 650e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier runtime->DetachCurrentThread(); 666a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers return nullptr; 670e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 680e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 692ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromvoid ThreadPool::AddTask(Thread* self, Task* task) { 700e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 710e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier tasks_.push_back(task); 720e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // If we have any waiters, signal one. 7394c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier if (started_ && waiting_count_ != 0) { 740e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_.Signal(self); 750e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 760e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 770e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 78bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu ChartierThreadPool::ThreadPool(const char* name, size_t num_threads) 79bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier : name_(name), 80bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier task_queue_lock_("task queue lock"), 810e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_("task queue condition", task_queue_lock_), 820e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier completion_condition_("task completion condition", task_queue_lock_), 830e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier started_(false), 840e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier shutting_down_(false), 8535883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier waiting_count_(0), 86d914eb2a839f7b40156ff0299a60e5cb80080b73Ian Rogers start_time_(0), 87d914eb2a839f7b40156ff0299a60e5cb80080b73Ian Rogers total_wait_time_(0), 8835883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier // Add one since the caller of constructor waits on the barrier too. 892775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier creation_barier_(num_threads + 1), 902775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier max_active_workers_(num_threads) { 9135883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier Thread* self = Thread::Current(); 920e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier while (GetThreadCount() < num_threads) { 93277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe const std::string worker_name = StringPrintf("%s worker thread %zu", name_.c_str(), 94277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe GetThreadCount()); 95277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe threads_.push_back(new ThreadPoolWorker(this, worker_name, ThreadPoolWorker::kDefaultStackSize)); 960e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 9735883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier // Wait for all of the threads to attach. 9835883cc623fdf475a4ead1dafcba9e9becc1ed11Mathieu Chartier creation_barier_.Wait(self); 990e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1000e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1012775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartiervoid ThreadPool::SetMaxActiveWorkers(size_t threads) { 1022775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier MutexLock mu(Thread::Current(), task_queue_lock_); 1032775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier CHECK_LE(threads, GetThreadCount()); 1042775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier max_active_workers_ = threads; 1052775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier} 1062775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier 1070e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu ChartierThreadPool::~ThreadPool() { 108e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier { 109e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier Thread* self = Thread::Current(); 110e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier MutexLock mu(self, task_queue_lock_); 111e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier // Tell any remaining workers to shut down. 112e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier shutting_down_ = true; 113e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier // Broadcast to everyone waiting. 114e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier task_queue_condition_.Broadcast(self); 11502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier completion_condition_.Broadcast(self); 116e46cd75f182a3d738c5e2ef3cc90b2f0b1de56eeMathieu Chartier } 1170e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // Wait for the threads to finish. 1180e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier STLDeleteElements(&threads_); 1190e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1200e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1210e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid ThreadPool::StartWorkers(Thread* self) { 1220e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 1230e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier started_ = true; 1240e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_.Broadcast(self); 12502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier start_time_ = NanoTime(); 12602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier total_wait_time_ = 0; 1270e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1280e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1290e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartiervoid ThreadPool::StopWorkers(Thread* self) { 1300e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 1310e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier started_ = false; 1320e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1330e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 13402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierTask* ThreadPool::GetTask(Thread* self) { 1350e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 13602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (!IsShuttingDown()) { 1372775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier const size_t thread_count = GetThreadCount(); 1382775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier // Ensure that we don't use more threads than the maximum active workers. 1392775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier const size_t active_threads = thread_count - waiting_count_; 1402775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier // <= since self is considered an active worker. 1412775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier if (active_threads <= max_active_workers_) { 1426a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers Task* task = TryGetTaskLocked(); 1436a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers if (task != nullptr) { 1442775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier return task; 1452775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier } 1460e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 1470e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1482775ee4f82dff260663ca16adddc0b15327aaa42Mathieu Chartier ++waiting_count_; 1490e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier if (waiting_count_ == GetThreadCount() && tasks_.empty()) { 1500e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // We may be done, lets broadcast to the completion condition. 1510e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier completion_condition_.Broadcast(self); 1520e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 15394c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier const uint64_t wait_start = kMeasureWaitTime ? NanoTime() : 0; 1540e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier task_queue_condition_.Wait(self); 15594c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier if (kMeasureWaitTime) { 15694c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier const uint64_t wait_end = NanoTime(); 15794c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier total_wait_time_ += wait_end - std::max(wait_start, start_time_); 15894c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier } 15994c32c5f01c7d44781317bf23933ed0a5bc4b796Mathieu Chartier --waiting_count_; 1600e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 1610e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1622cebb24bfc3247d3e9be138a3350106737455918Mathieu Chartier // We are shutting down, return null to tell the worker thread to stop looping. 1636a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers return nullptr; 1640e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1650e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 16602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierTask* ThreadPool::TryGetTask(Thread* self) { 1670e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier MutexLock mu(self, task_queue_lock_); 1686a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers return TryGetTaskLocked(); 16902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 17002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 1716a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan RogersTask* ThreadPool::TryGetTaskLocked() { 17202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (started_ && !tasks_.empty()) { 17302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Task* task = tasks_.front(); 17402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier tasks_.pop_front(); 17502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return task; 17602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 1776a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers return nullptr; 17802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 17902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 1801d54e73444e017d3a65234e0f193846f3e27472bIan Rogersvoid ThreadPool::Wait(Thread* self, bool do_work, bool may_hold_locks) { 1811d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (do_work) { 1826a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers Task* task = nullptr; 1836a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers while ((task = TryGetTask(self)) != nullptr) { 1841d54e73444e017d3a65234e0f193846f3e27472bIan Rogers task->Run(self); 1851d54e73444e017d3a65234e0f193846f3e27472bIan Rogers task->Finalize(); 1861d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 18702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 1880e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier // Wait until each thread is waiting and the task list is empty. 18902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, task_queue_lock_); 19002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (!shutting_down_ && (waiting_count_ != GetThreadCount() || !tasks_.empty())) { 1911d54e73444e017d3a65234e0f193846f3e27472bIan Rogers if (!may_hold_locks) { 1921d54e73444e017d3a65234e0f193846f3e27472bIan Rogers completion_condition_.Wait(self); 1931d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } else { 1941d54e73444e017d3a65234e0f193846f3e27472bIan Rogers completion_condition_.WaitHoldingLocks(self); 1951d54e73444e017d3a65234e0f193846f3e27472bIan Rogers } 1960e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier } 1970e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} 1980e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier 1992ce745c06271d5223d57dbf08117b20d5b60694aBrian Carlstromsize_t ThreadPool::GetTaskCount(Thread* self) { 20002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, task_queue_lock_); 20102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return tasks_.size(); 20202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 20302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 20402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu ChartierWorkStealingWorker::WorkStealingWorker(ThreadPool* thread_pool, const std::string& name, 20502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier size_t stack_size) 2066a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers : ThreadPoolWorker(thread_pool, name, stack_size), task_(nullptr) {} 20702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 20802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartiervoid WorkStealingWorker::Run() { 20902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier Thread* self = Thread::Current(); 2106a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers Task* task = nullptr; 21102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingThreadPool* thread_pool = down_cast<WorkStealingThreadPool*>(thread_pool_); 2126a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers while ((task = thread_pool_->GetTask(self)) != nullptr) { 21302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingTask* stealing_task = down_cast<WorkStealingTask*>(task); 21402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 21502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 2166a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers CHECK(task_ == nullptr); 21702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 21802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Register that we are running the task 21902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++stealing_task->ref_count_; 22002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier task_ = stealing_task; 22102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 22202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier stealing_task->Run(self); 22302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Mark ourselves as not running a task so that nobody tries to steal from us. 22402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // There is a race condition that someone starts stealing from us at this point. This is okay 22502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // due to the reference counting. 2266a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers task_ = nullptr; 22702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 22802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier bool finalize; 22902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 23002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Steal work from tasks until there is none left to steal. Note: There is a race, but 23102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // all that happens when the race occurs is that we steal some work instead of processing a 23202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // task from the queue. 23302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (thread_pool->GetTaskCount(self) == 0) { 2346a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers WorkStealingTask* steal_from_task = nullptr; 23502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 23602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 23702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 23802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Try finding a task to steal from. 2396a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers steal_from_task = thread_pool->FindTaskToStealFrom(); 2406a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers if (steal_from_task != nullptr) { 24102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier CHECK_NE(stealing_task, steal_from_task) 24202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier << "Attempting to steal from completed self task"; 24302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_from_task->ref_count_++; 24402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } else { 24502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier break; 24602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 24702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 24802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 2496a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers if (steal_from_task != nullptr) { 25002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Task which completed earlier is going to steal some work. 25102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier stealing_task->StealFrom(self, steal_from_task); 25202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 25302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 25402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // We are done stealing from the task, lets decrement its reference count. 25502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 25602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier finalize = !--steal_from_task->ref_count_; 25702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 25802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 25902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (finalize) { 26002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_from_task->Finalize(); 26102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 26202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 26302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 26402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 26502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier { 26602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier MutexLock mu(self, thread_pool->work_steal_lock_); 26702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // If nobody is still referencing task_ we can finalize it. 26802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier finalize = !--stealing_task->ref_count_; 26902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 27002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 27102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (finalize) { 27202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier stealing_task->Finalize(); 27302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 27402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 27502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 27602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 2770cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian CarlstromWorkStealingWorker::~WorkStealingWorker() {} 27802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 279bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu ChartierWorkStealingThreadPool::WorkStealingThreadPool(const char* name, size_t num_threads) 280bcd5e9daecad39f0dab3246808b4835caec29ea6Mathieu Chartier : ThreadPool(name, 0), 28102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier work_steal_lock_("work stealing lock"), 28202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_index_(0) { 28302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier while (GetThreadCount() < num_threads) { 284277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe const std::string worker_name = StringPrintf("Work stealing worker %zu", GetThreadCount()); 285277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe threads_.push_back(new WorkStealingWorker(this, worker_name, 286277ccbd200ea43590dfc06a93ae184a765327ad0Andreas Gampe ThreadPoolWorker::kDefaultStackSize)); 28702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 28802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 28902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 2906a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan RogersWorkStealingTask* WorkStealingThreadPool::FindTaskToStealFrom() { 29102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier const size_t thread_count = GetThreadCount(); 29202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier for (size_t i = 0; i < thread_count; ++i) { 29302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // TODO: Use CAS instead of lock. 29402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier ++steal_index_; 29502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (steal_index_ >= thread_count) { 29602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier steal_index_-= thread_count; 29702b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 29802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 29902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingWorker* worker = down_cast<WorkStealingWorker*>(threads_[steal_index_]); 30002b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier WorkStealingTask* task = worker->task_; 30102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier if (task) { 30202b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Not null, we can probably steal from this worker. 30302b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier return task; 30402b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 30502b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier } 30602b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier // Couldn't find something to steal. 3076a3c1fcb4ba42ad4d5d142c17a3712a6ddd3866fIan Rogers return nullptr; 30802b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier} 30902b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 3100cd7ec2dcd8d7ba30bf3ca420b40dac52849876cBrian CarlstromWorkStealingThreadPool::~WorkStealingThreadPool() {} 31102b6a78038f12c109f95eb31713cfc747f5512f1Mathieu Chartier 3120e4627e593bc39f8e3d89c31f8977d55054c07ccMathieu Chartier} // namespace art 313