1 /* 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 17 #include "thread_pool.h" 18 19 #include "base/casts.h" 20 #include "base/stl_util.h" 21 #include "base/time_utils.h" 22 #include "runtime.h" 23 #include "thread-inl.h" 24 25 namespace art { 26 27 static constexpr bool kMeasureWaitTime = false; 28 29 ThreadPoolWorker::ThreadPoolWorker(ThreadPool* thread_pool, const std::string& name, 30 size_t stack_size) 31 : thread_pool_(thread_pool), 32 name_(name) { 33 std::string error_msg; 34 stack_.reset(MemMap::MapAnonymous(name.c_str(), nullptr, stack_size, PROT_READ | PROT_WRITE, 35 false, false, &error_msg)); 36 CHECK(stack_.get() != nullptr) << error_msg; 37 const char* reason = "new thread pool worker thread"; 38 pthread_attr_t attr; 39 CHECK_PTHREAD_CALL(pthread_attr_init, (&attr), reason); 40 CHECK_PTHREAD_CALL(pthread_attr_setstack, (&attr, stack_->Begin(), stack_->Size()), reason); 41 CHECK_PTHREAD_CALL(pthread_create, (&pthread_, &attr, &Callback, this), reason); 42 CHECK_PTHREAD_CALL(pthread_attr_destroy, (&attr), reason); 43 } 44 45 ThreadPoolWorker::~ThreadPoolWorker() { 46 CHECK_PTHREAD_CALL(pthread_join, (pthread_, nullptr), "thread pool worker shutdown"); 47 } 48 49 void ThreadPoolWorker::Run() { 50 Thread* self = Thread::Current(); 51 Task* task = nullptr; 52 thread_pool_->creation_barier_.Wait(self); 53 while ((task = thread_pool_->GetTask(self)) != nullptr) { 54 task->Run(self); 55 task->Finalize(); 56 } 57 } 58 59 void* ThreadPoolWorker::Callback(void* arg) { 60 ThreadPoolWorker* worker = reinterpret_cast<ThreadPoolWorker*>(arg); 61 Runtime* runtime = Runtime::Current(); 62 CHECK(runtime->AttachCurrentThread(worker->name_.c_str(), true, nullptr, false)); 63 // Do work until its time to shut down. 64 worker->Run(); 65 runtime->DetachCurrentThread(); 66 return nullptr; 67 } 68 69 void ThreadPool::AddTask(Thread* self, Task* task) { 70 MutexLock mu(self, task_queue_lock_); 71 tasks_.push_back(task); 72 // If we have any waiters, signal one. 73 if (started_ && waiting_count_ != 0) { 74 task_queue_condition_.Signal(self); 75 } 76 } 77 78 ThreadPool::ThreadPool(const char* name, size_t num_threads) 79 : name_(name), 80 task_queue_lock_("task queue lock"), 81 task_queue_condition_("task queue condition", task_queue_lock_), 82 completion_condition_("task completion condition", task_queue_lock_), 83 started_(false), 84 shutting_down_(false), 85 waiting_count_(0), 86 start_time_(0), 87 total_wait_time_(0), 88 // Add one since the caller of constructor waits on the barrier too. 89 creation_barier_(num_threads + 1), 90 max_active_workers_(num_threads) { 91 Thread* self = Thread::Current(); 92 while (GetThreadCount() < num_threads) { 93 const std::string worker_name = StringPrintf("%s worker thread %zu", name_.c_str(), 94 GetThreadCount()); 95 threads_.push_back(new ThreadPoolWorker(this, worker_name, ThreadPoolWorker::kDefaultStackSize)); 96 } 97 // Wait for all of the threads to attach. 98 creation_barier_.Wait(self); 99 } 100 101 void ThreadPool::SetMaxActiveWorkers(size_t threads) { 102 MutexLock mu(Thread::Current(), task_queue_lock_); 103 CHECK_LE(threads, GetThreadCount()); 104 max_active_workers_ = threads; 105 } 106 107 ThreadPool::~ThreadPool() { 108 { 109 Thread* self = Thread::Current(); 110 MutexLock mu(self, task_queue_lock_); 111 // Tell any remaining workers to shut down. 112 shutting_down_ = true; 113 // Broadcast to everyone waiting. 114 task_queue_condition_.Broadcast(self); 115 completion_condition_.Broadcast(self); 116 } 117 // Wait for the threads to finish. 118 STLDeleteElements(&threads_); 119 } 120 121 void ThreadPool::StartWorkers(Thread* self) { 122 MutexLock mu(self, task_queue_lock_); 123 started_ = true; 124 task_queue_condition_.Broadcast(self); 125 start_time_ = NanoTime(); 126 total_wait_time_ = 0; 127 } 128 129 void ThreadPool::StopWorkers(Thread* self) { 130 MutexLock mu(self, task_queue_lock_); 131 started_ = false; 132 } 133 134 Task* ThreadPool::GetTask(Thread* self) { 135 MutexLock mu(self, task_queue_lock_); 136 while (!IsShuttingDown()) { 137 const size_t thread_count = GetThreadCount(); 138 // Ensure that we don't use more threads than the maximum active workers. 139 const size_t active_threads = thread_count - waiting_count_; 140 // <= since self is considered an active worker. 141 if (active_threads <= max_active_workers_) { 142 Task* task = TryGetTaskLocked(); 143 if (task != nullptr) { 144 return task; 145 } 146 } 147 148 ++waiting_count_; 149 if (waiting_count_ == GetThreadCount() && tasks_.empty()) { 150 // We may be done, lets broadcast to the completion condition. 151 completion_condition_.Broadcast(self); 152 } 153 const uint64_t wait_start = kMeasureWaitTime ? NanoTime() : 0; 154 task_queue_condition_.Wait(self); 155 if (kMeasureWaitTime) { 156 const uint64_t wait_end = NanoTime(); 157 total_wait_time_ += wait_end - std::max(wait_start, start_time_); 158 } 159 --waiting_count_; 160 } 161 162 // We are shutting down, return null to tell the worker thread to stop looping. 163 return nullptr; 164 } 165 166 Task* ThreadPool::TryGetTask(Thread* self) { 167 MutexLock mu(self, task_queue_lock_); 168 return TryGetTaskLocked(); 169 } 170 171 Task* ThreadPool::TryGetTaskLocked() { 172 if (started_ && !tasks_.empty()) { 173 Task* task = tasks_.front(); 174 tasks_.pop_front(); 175 return task; 176 } 177 return nullptr; 178 } 179 180 void ThreadPool::Wait(Thread* self, bool do_work, bool may_hold_locks) { 181 if (do_work) { 182 Task* task = nullptr; 183 while ((task = TryGetTask(self)) != nullptr) { 184 task->Run(self); 185 task->Finalize(); 186 } 187 } 188 // Wait until each thread is waiting and the task list is empty. 189 MutexLock mu(self, task_queue_lock_); 190 while (!shutting_down_ && (waiting_count_ != GetThreadCount() || !tasks_.empty())) { 191 if (!may_hold_locks) { 192 completion_condition_.Wait(self); 193 } else { 194 completion_condition_.WaitHoldingLocks(self); 195 } 196 } 197 } 198 199 size_t ThreadPool::GetTaskCount(Thread* self) { 200 MutexLock mu(self, task_queue_lock_); 201 return tasks_.size(); 202 } 203 204 WorkStealingWorker::WorkStealingWorker(ThreadPool* thread_pool, const std::string& name, 205 size_t stack_size) 206 : ThreadPoolWorker(thread_pool, name, stack_size), task_(nullptr) {} 207 208 void WorkStealingWorker::Run() { 209 Thread* self = Thread::Current(); 210 Task* task = nullptr; 211 WorkStealingThreadPool* thread_pool = down_cast<WorkStealingThreadPool*>(thread_pool_); 212 while ((task = thread_pool_->GetTask(self)) != nullptr) { 213 WorkStealingTask* stealing_task = down_cast<WorkStealingTask*>(task); 214 215 { 216 CHECK(task_ == nullptr); 217 MutexLock mu(self, thread_pool->work_steal_lock_); 218 // Register that we are running the task 219 ++stealing_task->ref_count_; 220 task_ = stealing_task; 221 } 222 stealing_task->Run(self); 223 // Mark ourselves as not running a task so that nobody tries to steal from us. 224 // There is a race condition that someone starts stealing from us at this point. This is okay 225 // due to the reference counting. 226 task_ = nullptr; 227 228 bool finalize; 229 230 // Steal work from tasks until there is none left to steal. Note: There is a race, but 231 // all that happens when the race occurs is that we steal some work instead of processing a 232 // task from the queue. 233 while (thread_pool->GetTaskCount(self) == 0) { 234 WorkStealingTask* steal_from_task = nullptr; 235 236 { 237 MutexLock mu(self, thread_pool->work_steal_lock_); 238 // Try finding a task to steal from. 239 steal_from_task = thread_pool->FindTaskToStealFrom(); 240 if (steal_from_task != nullptr) { 241 CHECK_NE(stealing_task, steal_from_task) 242 << "Attempting to steal from completed self task"; 243 steal_from_task->ref_count_++; 244 } else { 245 break; 246 } 247 } 248 249 if (steal_from_task != nullptr) { 250 // Task which completed earlier is going to steal some work. 251 stealing_task->StealFrom(self, steal_from_task); 252 253 { 254 // We are done stealing from the task, lets decrement its reference count. 255 MutexLock mu(self, thread_pool->work_steal_lock_); 256 finalize = !--steal_from_task->ref_count_; 257 } 258 259 if (finalize) { 260 steal_from_task->Finalize(); 261 } 262 } 263 } 264 265 { 266 MutexLock mu(self, thread_pool->work_steal_lock_); 267 // If nobody is still referencing task_ we can finalize it. 268 finalize = !--stealing_task->ref_count_; 269 } 270 271 if (finalize) { 272 stealing_task->Finalize(); 273 } 274 } 275 } 276 277 WorkStealingWorker::~WorkStealingWorker() {} 278 279 WorkStealingThreadPool::WorkStealingThreadPool(const char* name, size_t num_threads) 280 : ThreadPool(name, 0), 281 work_steal_lock_("work stealing lock"), 282 steal_index_(0) { 283 while (GetThreadCount() < num_threads) { 284 const std::string worker_name = StringPrintf("Work stealing worker %zu", GetThreadCount()); 285 threads_.push_back(new WorkStealingWorker(this, worker_name, 286 ThreadPoolWorker::kDefaultStackSize)); 287 } 288 } 289 290 WorkStealingTask* WorkStealingThreadPool::FindTaskToStealFrom() { 291 const size_t thread_count = GetThreadCount(); 292 for (size_t i = 0; i < thread_count; ++i) { 293 // TODO: Use CAS instead of lock. 294 ++steal_index_; 295 if (steal_index_ >= thread_count) { 296 steal_index_-= thread_count; 297 } 298 299 WorkStealingWorker* worker = down_cast<WorkStealingWorker*>(threads_[steal_index_]); 300 WorkStealingTask* task = worker->task_; 301 if (task) { 302 // Not null, we can probably steal from this worker. 303 return task; 304 } 305 } 306 // Couldn't find something to steal. 307 return nullptr; 308 } 309 310 WorkStealingThreadPool::~WorkStealingThreadPool() {} 311 312 } // namespace art 313