1// workqueue.cc -- the workqueue for gold 2 3// Copyright (C) 2006-2020 Free Software Foundation, Inc. 4// Written by Ian Lance Taylor <iant@google.com>. 5 6// This file is part of gold. 7 8// This program is free software; you can redistribute it and/or modify 9// it under the terms of the GNU General Public License as published by 10// the Free Software Foundation; either version 3 of the License, or 11// (at your option) any later version. 12 13// This program is distributed in the hope that it will be useful, 14// but WITHOUT ANY WARRANTY; without even the implied warranty of 15// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16// GNU General Public License for more details. 17 18// You should have received a copy of the GNU General Public License 19// along with this program; if not, write to the Free Software 20// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 21// MA 02110-1301, USA. 22 23#include "gold.h" 24 25#include "debug.h" 26#include "options.h" 27#include "timer.h" 28#include "workqueue.h" 29#include "workqueue-internal.h" 30 31namespace gold 32{ 33 34// Class Task_list. 35 36// Add T to the end of the list. 37 38inline void 39Task_list::push_back(Task* t) 40{ 41 gold_assert(t->list_next() == NULL); 42 if (this->head_ == NULL) 43 { 44 this->head_ = t; 45 this->tail_ = t; 46 } 47 else 48 { 49 this->tail_->set_list_next(t); 50 this->tail_ = t; 51 } 52} 53 54// Add T to the front of the list. 55 56inline void 57Task_list::push_front(Task* t) 58{ 59 gold_assert(t->list_next() == NULL); 60 if (this->head_ == NULL) 61 { 62 this->head_ = t; 63 this->tail_ = t; 64 } 65 else 66 { 67 t->set_list_next(this->head_); 68 this->head_ = t; 69 } 70} 71 72// Remove and return the first Task waiting for this lock to be 73// released. 74 75inline Task* 76Task_list::pop_front() 77{ 78 Task* ret = this->head_; 79 if (ret != NULL) 80 { 81 if (ret == this->tail_) 82 { 83 gold_assert(ret->list_next() == NULL); 84 this->head_ = NULL; 85 this->tail_ = NULL; 86 } 87 else 88 { 89 this->head_ = ret->list_next(); 90 gold_assert(this->head_ != NULL); 91 ret->clear_list_next(); 92 } 93 } 94 return ret; 95} 96 97// The simple single-threaded implementation of Workqueue_threader. 98 99class Workqueue_threader_single : public Workqueue_threader 100{ 101 public: 102 Workqueue_threader_single(Workqueue* workqueue) 103 : Workqueue_threader(workqueue) 104 { } 105 ~Workqueue_threader_single() 106 { } 107 108 void 109 set_thread_count(int thread_count) 110 { gold_assert(thread_count > 0); } 111 112 bool 113 should_cancel_thread(int) 114 { return false; } 115}; 116 117// Workqueue methods. 118 119Workqueue::Workqueue(const General_options& options) 120 : lock_(), 121 first_tasks_(), 122 tasks_(), 123 running_(0), 124 waiting_(0), 125 condvar_(this->lock_), 126 threader_(NULL) 127{ 128 bool threads = options.threads(); 129#ifndef ENABLE_THREADS 130 threads = false; 131#endif 132 if (!threads) 133 this->threader_ = new Workqueue_threader_single(this); 134 else 135 { 136#ifdef ENABLE_THREADS 137 this->threader_ = new Workqueue_threader_threadpool(this); 138#else 139 gold_unreachable(); 140#endif 141 } 142} 143 144Workqueue::~Workqueue() 145{ 146} 147 148// Add a task to the end of a specific queue, or put it on the list 149// waiting for a Token. 150 151void 152Workqueue::add_to_queue(Task_list* queue, Task* t, bool front) 153{ 154 Hold_lock hl(this->lock_); 155 156 Task_token* token = t->is_runnable(); 157 if (token != NULL) 158 { 159 if (front) 160 token->add_waiting_front(t); 161 else 162 token->add_waiting(t); 163 ++this->waiting_; 164 } 165 else 166 { 167 if (front) 168 queue->push_front(t); 169 else 170 queue->push_back(t); 171 // Tell any waiting thread that there is work to do. 172 this->condvar_.signal(); 173 } 174} 175 176// Add a task to the queue. 177 178void 179Workqueue::queue(Task* t) 180{ 181 this->add_to_queue(&this->tasks_, t, false); 182} 183 184// Queue a task which should run soon. 185 186void 187Workqueue::queue_soon(Task* t) 188{ 189 t->set_should_run_soon(); 190 this->add_to_queue(&this->first_tasks_, t, false); 191} 192 193// Queue a task which should run next. 194 195void 196Workqueue::queue_next(Task* t) 197{ 198 t->set_should_run_soon(); 199 this->add_to_queue(&this->first_tasks_, t, true); 200} 201 202// Return whether to cancel the current thread. 203 204inline bool 205Workqueue::should_cancel_thread(int thread_number) 206{ 207 return this->threader_->should_cancel_thread(thread_number); 208} 209 210// Find a runnable task in TASKS. Return NULL if none could be found. 211// If we find a Task waiting for a Token, add it to the list for that 212// Token. The workqueue lock must be held when this is called. 213 214Task* 215Workqueue::find_runnable_in_list(Task_list* tasks) 216{ 217 Task* t; 218 while ((t = tasks->pop_front()) != NULL) 219 { 220 Task_token* token = t->is_runnable(); 221 222 if (token == NULL) 223 return t; 224 225 token->add_waiting(t); 226 ++this->waiting_; 227 } 228 229 // We couldn't find any runnable task. 230 return NULL; 231} 232 233// Find a runnable task. Return NULL if none could be found. The 234// workqueue lock must be held when this is called. 235 236Task* 237Workqueue::find_runnable() 238{ 239 Task* t = this->find_runnable_in_list(&this->first_tasks_); 240 if (t == NULL) 241 t = this->find_runnable_in_list(&this->tasks_); 242 return t; 243} 244 245// Find a runnable a task, and wait until we find one. Return NULL if 246// we should exit. The workqueue lock must be held when this is 247// called. 248 249Task* 250Workqueue::find_runnable_or_wait(int thread_number) 251{ 252 Task* t = this->find_runnable(); 253 254 while (t == NULL) 255 { 256 if (this->running_ == 0 257 && this->first_tasks_.empty() 258 && this->tasks_.empty()) 259 { 260 // Kick all the threads to make them exit. 261 this->condvar_.broadcast(); 262 263 gold_assert(this->waiting_ == 0); 264 return NULL; 265 } 266 267 if (this->should_cancel_thread(thread_number)) 268 return NULL; 269 270 gold_debug(DEBUG_TASK, "%3d sleeping", thread_number); 271 272 this->condvar_.wait(); 273 274 gold_debug(DEBUG_TASK, "%3d awake", thread_number); 275 276 t = this->find_runnable(); 277 } 278 279 return t; 280} 281 282// Find and run tasks. If we can't find a runnable task, wait for one 283// to become available. If we run a task, and it frees up another 284// runnable task, then run that one too. This returns true if we 285// should look for another task, false if we are cancelling this 286// thread. 287 288bool 289Workqueue::find_and_run_task(int thread_number) 290{ 291 Task* t; 292 Task_locker tl; 293 294 { 295 Hold_lock hl(this->lock_); 296 297 // Find a runnable task. 298 t = this->find_runnable_or_wait(thread_number); 299 300 if (t == NULL) 301 return false; 302 303 // Get the locks for the task. This must be called while we are 304 // still holding the Workqueue lock. 305 t->locks(&tl); 306 307 ++this->running_; 308 } 309 310 while (t != NULL) 311 { 312 gold_debug(DEBUG_TASK, "%3d running task %s", thread_number, 313 t->name().c_str()); 314 315 Timer timer; 316 if (is_debugging_enabled(DEBUG_TASK)) 317 timer.start(); 318 319 t->run(this); 320 321 if (is_debugging_enabled(DEBUG_TASK)) 322 { 323 Timer::TimeStats elapsed = timer.get_elapsed_time(); 324 325 gold_debug(DEBUG_TASK, 326 "%3d completed task %s " 327 "(user: %ld.%06ld sys: %ld.%06ld wall: %ld.%06ld)", 328 thread_number, t->name().c_str(), 329 elapsed.user / 1000, (elapsed.user % 1000) * 1000, 330 elapsed.sys / 1000, (elapsed.sys % 1000) * 1000, 331 elapsed.wall / 1000, (elapsed.wall % 1000) * 1000); 332 } 333 334 Task* next; 335 { 336 Hold_lock hl(this->lock_); 337 338 --this->running_; 339 340 // Release the locks for the task. This must be done with the 341 // workqueue lock held. Get the next Task to run if any. 342 next = this->release_locks(t, &tl); 343 344 if (next == NULL) 345 next = this->find_runnable(); 346 347 // If we have another Task to run, get the Locks. This must 348 // be called while we are still holding the Workqueue lock. 349 if (next != NULL) 350 { 351 tl.clear(); 352 next->locks(&tl); 353 354 ++this->running_; 355 } 356 } 357 358 // We are done with this task. 359 delete t; 360 361 t = next; 362 } 363 364 return true; 365} 366 367// Handle the return value of release_locks, and get tasks ready to 368// run. 369 370// 1) If T is not runnable, queue it on the appropriate token. 371 372// 2) Otherwise, T is runnable. If *PRET is not NULL, then we have 373// already decided which Task to run next. Add T to the list of 374// runnable tasks, and signal another thread. 375 376// 3) Otherwise, *PRET is NULL. If IS_BLOCKER is false, then T was 377// waiting on a write lock. We can grab that lock now, so we run T 378// now. 379 380// 4) Otherwise, IS_BLOCKER is true. If we should run T soon, then 381// run it now. 382 383// 5) Otherwise, check whether there are other tasks to run. If there 384// are, then we generally get a better ordering if we run those tasks 385// now, before T. A typical example is tasks waiting on the Dirsearch 386// blocker. We don't want to run those tasks right away just because 387// the Dirsearch was unblocked. 388 389// 6) Otherwise, there are no other tasks to run, so we might as well 390// run this one now. 391 392// This function must be called with the Workqueue lock held. 393 394// Return true if we set *PRET to T, false otherwise. 395 396bool 397Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret) 398{ 399 Task_token* token = t->is_runnable(); 400 401 if (token != NULL) 402 { 403 token->add_waiting(t); 404 ++this->waiting_; 405 return false; 406 } 407 408 bool should_queue = false; 409 bool should_return = false; 410 411 if (*pret != NULL) 412 should_queue = true; 413 else if (!is_blocker) 414 should_return = true; 415 else if (t->should_run_soon()) 416 should_return = true; 417 else if (!this->first_tasks_.empty() || !this->tasks_.empty()) 418 should_queue = true; 419 else 420 should_return = true; 421 422 if (should_return) 423 { 424 gold_assert(*pret == NULL); 425 *pret = t; 426 return true; 427 } 428 else if (should_queue) 429 { 430 if (t->should_run_soon()) 431 this->first_tasks_.push_back(t); 432 else 433 this->tasks_.push_back(t); 434 this->condvar_.signal(); 435 return false; 436 } 437 438 gold_unreachable(); 439} 440 441// Release the locks associated with a Task. Return the first 442// runnable Task that we find. If we find more runnable tasks, add 443// them to the run queue and signal any other threads. This must be 444// called with the Workqueue lock held. 445 446Task* 447Workqueue::release_locks(Task* t, Task_locker* tl) 448{ 449 Task* ret = NULL; 450 for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p) 451 { 452 Task_token* token = *p; 453 if (token->is_blocker()) 454 { 455 if (token->remove_blocker()) 456 { 457 // The token has been unblocked. Every waiting Task may 458 // now be runnable. 459 Task* t; 460 while ((t = token->remove_first_waiting()) != NULL) 461 { 462 --this->waiting_; 463 this->return_or_queue(t, true, &ret); 464 } 465 } 466 } 467 else 468 { 469 token->remove_writer(t); 470 471 // One more waiting Task may now be runnable. If we are 472 // going to run it next, we can stop. Otherwise we need to 473 // move all the Tasks to the runnable queue, to avoid a 474 // potential deadlock if the locking status changes before 475 // we run the next thread. 476 Task* t; 477 while ((t = token->remove_first_waiting()) != NULL) 478 { 479 --this->waiting_; 480 if (this->return_or_queue(t, false, &ret)) 481 break; 482 } 483 } 484 } 485 return ret; 486} 487 488// Process all the tasks on the workqueue. Keep going until the 489// workqueue is empty, or until we have been told to exit. This 490// function is called by all threads. 491 492void 493Workqueue::process(int thread_number) 494{ 495 while (this->find_and_run_task(thread_number)) 496 ; 497} 498 499// Set the number of threads to use for the workqueue, if we are using 500// threads. 501 502void 503Workqueue::set_thread_count(int threads) 504{ 505 Hold_lock hl(this->lock_); 506 507 this->threader_->set_thread_count(threads); 508 // Wake up all the threads, since something has changed. 509 this->condvar_.broadcast(); 510} 511 512// Add a new blocker to an existing Task_token. 513 514void 515Workqueue::add_blocker(Task_token* token) 516{ 517 Hold_lock hl(this->lock_); 518 token->add_blocker(); 519} 520 521} // End namespace gold. 522