1160814Ssimon// workqueue.cc -- the workqueue for gold 2160814Ssimon 3160814Ssimon// Copyright 2006, 2007, 2008 Free Software Foundation, Inc. 4160814Ssimon// Written by Ian Lance Taylor <iant@google.com>. 5160814Ssimon 6160814Ssimon// This file is part of gold. 7160814Ssimon 8160814Ssimon// This program is free software; you can redistribute it and/or modify 9160814Ssimon// it under the terms of the GNU General Public License as published by 10160814Ssimon// the Free Software Foundation; either version 3 of the License, or 11160814Ssimon// (at your option) any later version. 12160814Ssimon 13160814Ssimon// This program is distributed in the hope that it will be useful, 14160814Ssimon// but WITHOUT ANY WARRANTY; without even the implied warranty of 15160814Ssimon// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16160814Ssimon// GNU General Public License for more details. 17160814Ssimon 18160814Ssimon// You should have received a copy of the GNU General Public License 19160814Ssimon// along with this program; if not, write to the Free Software 20160814Ssimon// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, 21160814Ssimon// MA 02110-1301, USA. 22160814Ssimon 23160814Ssimon#include "gold.h" 24160814Ssimon 25160814Ssimon#include "debug.h" 26160814Ssimon#include "options.h" 27160814Ssimon#include "timer.h" 28160814Ssimon#include "workqueue.h" 29160814Ssimon#include "workqueue-internal.h" 30160814Ssimon 31160814Ssimonnamespace gold 32160814Ssimon{ 33160814Ssimon 34160814Ssimon// Class Task_list. 35160814Ssimon 36160814Ssimon// Add T to the end of the list. 37160814Ssimon 38160814Ssimoninline void 39160814SsimonTask_list::push_back(Task* t) 40160814Ssimon{ 41160814Ssimon gold_assert(t->list_next() == NULL); 42160814Ssimon if (this->head_ == NULL) 43160814Ssimon { 44160814Ssimon this->head_ = t; 45160814Ssimon this->tail_ = t; 46160814Ssimon } 47160814Ssimon else 48160814Ssimon { 49160814Ssimon this->tail_->set_list_next(t); 50160814Ssimon this->tail_ = t; 51160814Ssimon } 52160814Ssimon} 53160814Ssimon 54160814Ssimon// Add T to the front of the list. 55160814Ssimon 56160814Ssimoninline void 57160814SsimonTask_list::push_front(Task* t) 58160814Ssimon{ 59160814Ssimon gold_assert(t->list_next() == NULL); 60160814Ssimon if (this->head_ == NULL) 61160814Ssimon { 62160814Ssimon this->head_ = t; 63160814Ssimon this->tail_ = t; 64160814Ssimon } 65160814Ssimon else 66160814Ssimon { 67160814Ssimon t->set_list_next(this->head_); 68160814Ssimon this->head_ = t; 69160814Ssimon } 70160814Ssimon} 71160814Ssimon 72160814Ssimon// Remove and return the first Task waiting for this lock to be 73160814Ssimon// released. 74160814Ssimon 75160814Ssimoninline Task* 76160814SsimonTask_list::pop_front() 77160814Ssimon{ 78160814Ssimon Task* ret = this->head_; 79160814Ssimon if (ret != NULL) 80160814Ssimon { 81160814Ssimon if (ret == this->tail_) 82160814Ssimon { 83160814Ssimon gold_assert(ret->list_next() == NULL); 84160814Ssimon this->head_ = NULL; 85160814Ssimon this->tail_ = NULL; 86160814Ssimon } 87160814Ssimon else 88160814Ssimon { 89160814Ssimon this->head_ = ret->list_next(); 90160814Ssimon gold_assert(this->head_ != NULL); 91160814Ssimon ret->clear_list_next(); 92160814Ssimon } 93160814Ssimon } 94160814Ssimon return ret; 95160814Ssimon} 96160814Ssimon 97160814Ssimon// The simple single-threaded implementation of Workqueue_threader. 98160814Ssimon 99160814Ssimonclass Workqueue_threader_single : public Workqueue_threader 100160814Ssimon{ 101160814Ssimon public: 102160814Ssimon Workqueue_threader_single(Workqueue* workqueue) 103160814Ssimon : Workqueue_threader(workqueue) 104160814Ssimon { } 105160814Ssimon ~Workqueue_threader_single() 106160814Ssimon { } 107160814Ssimon 108160814Ssimon void 109160814Ssimon set_thread_count(int thread_count) 110160814Ssimon { gold_assert(thread_count > 0); } 111160814Ssimon 112160814Ssimon bool 113160814Ssimon should_cancel_thread() 114160814Ssimon { return false; } 115160814Ssimon}; 116160814Ssimon 117160814Ssimon// Workqueue methods. 118160814Ssimon 119160814SsimonWorkqueue::Workqueue(const General_options& options) 120160814Ssimon : lock_(), 121160814Ssimon first_tasks_(), 122160814Ssimon tasks_(), 123160814Ssimon running_(0), 124160814Ssimon waiting_(0), 125160814Ssimon condvar_(this->lock_), 126160814Ssimon threader_(NULL) 127160814Ssimon{ 128160814Ssimon bool threads = options.threads(); 129160814Ssimon#ifndef ENABLE_THREADS 130160814Ssimon threads = false; 131160814Ssimon#endif 132160814Ssimon if (!threads) 133160814Ssimon this->threader_ = new Workqueue_threader_single(this); 134160814Ssimon else 135160814Ssimon { 136160814Ssimon#ifdef ENABLE_THREADS 137160814Ssimon this->threader_ = new Workqueue_threader_threadpool(this); 138160814Ssimon#else 139160814Ssimon gold_unreachable(); 140160814Ssimon#endif 141160814Ssimon } 142160814Ssimon} 143160814Ssimon 144160814SsimonWorkqueue::~Workqueue() 145160814Ssimon{ 146160814Ssimon} 147160814Ssimon 148160814Ssimon// Add a task to the end of a specific queue, or put it on the list 149160814Ssimon// waiting for a Token. 150160814Ssimon 151160814Ssimonvoid 152160814SsimonWorkqueue::add_to_queue(Task_list* queue, Task* t, bool front) 153160814Ssimon{ 154160814Ssimon Hold_lock hl(this->lock_); 155160814Ssimon 156160814Ssimon Task_token* token = t->is_runnable(); 157160814Ssimon if (token != NULL) 158160814Ssimon { 159160814Ssimon if (front) 160160814Ssimon token->add_waiting_front(t); 161160814Ssimon else 162160814Ssimon token->add_waiting(t); 163160814Ssimon ++this->waiting_; 164160814Ssimon } 165160814Ssimon else 166160814Ssimon { 167160814Ssimon if (front) 168160814Ssimon queue->push_front(t); 169160814Ssimon else 170160814Ssimon queue->push_back(t); 171160814Ssimon // Tell any waiting thread that there is work to do. 172160814Ssimon this->condvar_.signal(); 173160814Ssimon } 174160814Ssimon} 175160814Ssimon 176160814Ssimon// Add a task to the queue. 177160814Ssimon 178160814Ssimonvoid 179160814SsimonWorkqueue::queue(Task* t) 180160814Ssimon{ 181160814Ssimon this->add_to_queue(&this->tasks_, t, false); 182160814Ssimon} 183160814Ssimon 184160814Ssimon// Queue a task which should run soon. 185160814Ssimon 186160814Ssimonvoid 187160814SsimonWorkqueue::queue_soon(Task* t) 188160814Ssimon{ 189160814Ssimon t->set_should_run_soon(); 190160814Ssimon this->add_to_queue(&this->first_tasks_, t, false); 191160814Ssimon} 192160814Ssimon 193160814Ssimon// Queue a task which should run next. 194160814Ssimon 195160814Ssimonvoid 196160814SsimonWorkqueue::queue_next(Task* t) 197160814Ssimon{ 198160814Ssimon t->set_should_run_soon(); 199160814Ssimon this->add_to_queue(&this->first_tasks_, t, true); 200160814Ssimon} 201160814Ssimon 202160814Ssimon// Return whether to cancel the current thread. 203160814Ssimon 204160814Ssimoninline bool 205160814SsimonWorkqueue::should_cancel_thread() 206160814Ssimon{ 207160814Ssimon return this->threader_->should_cancel_thread(); 208160814Ssimon} 209160814Ssimon 210160814Ssimon// Find a runnable task in TASKS. Return NULL if none could be found. 211160814Ssimon// If we find a Task waiting for a Token, add it to the list for that 212160814Ssimon// Token. The workqueue lock must be held when this is called. 213160814Ssimon 214160814SsimonTask* 215160814SsimonWorkqueue::find_runnable_in_list(Task_list* tasks) 216160814Ssimon{ 217160814Ssimon Task* t; 218160814Ssimon while ((t = tasks->pop_front()) != NULL) 219160814Ssimon { 220160814Ssimon Task_token* token = t->is_runnable(); 221160814Ssimon 222160814Ssimon if (token == NULL) 223160814Ssimon return t; 224160814Ssimon 225160814Ssimon token->add_waiting(t); 226160814Ssimon ++this->waiting_; 227160814Ssimon } 228160814Ssimon 229160814Ssimon // We couldn't find any runnable task. 230160814Ssimon return NULL; 231160814Ssimon} 232160814Ssimon 233160814Ssimon// Find a runnable task. Return NULL if none could be found. The 234160814Ssimon// workqueue lock must be held when this is called. 235160814Ssimon 236160814SsimonTask* 237160814SsimonWorkqueue::find_runnable() 238160814Ssimon{ 239160814Ssimon Task* t = this->find_runnable_in_list(&this->first_tasks_); 240160814Ssimon if (t == NULL) 241160814Ssimon t = this->find_runnable_in_list(&this->tasks_); 242160814Ssimon return t; 243160814Ssimon} 244160814Ssimon 245160814Ssimon// Find a runnable a task, and wait until we find one. Return NULL if 246160814Ssimon// we should exit. The workqueue lock must be held when this is 247160814Ssimon// called. 248160814Ssimon 249160814SsimonTask* 250160814SsimonWorkqueue::find_runnable_or_wait(int thread_number) 251160814Ssimon{ 252160814Ssimon Task* t = this->find_runnable(); 253160814Ssimon 254160814Ssimon while (t == NULL) 255160814Ssimon { 256160814Ssimon if (this->running_ == 0 257160814Ssimon && this->first_tasks_.empty() 258160814Ssimon && this->tasks_.empty()) 259160814Ssimon { 260160814Ssimon // Kick all the threads to make them exit. 261160814Ssimon this->condvar_.broadcast(); 262160814Ssimon 263160814Ssimon gold_assert(this->waiting_ == 0); 264160814Ssimon return NULL; 265160814Ssimon } 266160814Ssimon 267160814Ssimon if (this->should_cancel_thread()) 268160814Ssimon return NULL; 269160814Ssimon 270160814Ssimon gold_debug(DEBUG_TASK, "%3d sleeping", thread_number); 271160814Ssimon 272160814Ssimon this->condvar_.wait(); 273160814Ssimon 274160814Ssimon gold_debug(DEBUG_TASK, "%3d awake", thread_number); 275160814Ssimon 276160814Ssimon t = this->find_runnable(); 277160814Ssimon } 278160814Ssimon 279160814Ssimon return t; 280160814Ssimon} 281160814Ssimon 282160814Ssimon// Find and run tasks. If we can't find a runnable task, wait for one 283160814Ssimon// to become available. If we run a task, and it frees up another 284160814Ssimon// runnable task, then run that one too. This returns true if we 285160814Ssimon// should look for another task, false if we are cancelling this 286160814Ssimon// thread. 287160814Ssimon 288160814Ssimonbool 289160814SsimonWorkqueue::find_and_run_task(int thread_number) 290160814Ssimon{ 291160814Ssimon Task* t; 292160814Ssimon Task_locker tl; 293160814Ssimon 294160814Ssimon { 295160814Ssimon Hold_lock hl(this->lock_); 296160814Ssimon 297160814Ssimon // Find a runnable task. 298160814Ssimon t = this->find_runnable_or_wait(thread_number); 299160814Ssimon 300160814Ssimon if (t == NULL) 301160814Ssimon return false; 302160814Ssimon 303160814Ssimon // Get the locks for the task. This must be called while we are 304160814Ssimon // still holding the Workqueue lock. 305160814Ssimon t->locks(&tl); 306160814Ssimon 307160814Ssimon ++this->running_; 308160814Ssimon } 309160814Ssimon 310160814Ssimon while (t != NULL) 311160814Ssimon { 312160814Ssimon gold_debug(DEBUG_TASK, "%3d running task %s", thread_number, 313160814Ssimon t->name().c_str()); 314160814Ssimon 315160814Ssimon Timer timer; 316160814Ssimon if (is_debugging_enabled(DEBUG_TASK)) 317160814Ssimon timer.start(); 318160814Ssimon 319160814Ssimon t->run(this); 320160814Ssimon 321160814Ssimon if (is_debugging_enabled(DEBUG_TASK)) 322160814Ssimon { 323160814Ssimon Timer::TimeStats elapsed = timer.get_elapsed_time(); 324160814Ssimon 325160814Ssimon gold_debug(DEBUG_TASK, 326160814Ssimon "%3d completed task %s " 327160814Ssimon "(user: %ld.%06ld sys: %ld.%06ld wall: %ld.%06ld)", 328160814Ssimon thread_number, t->name().c_str(), 329160814Ssimon elapsed.user / 1000, (elapsed.user % 1000) * 1000, 330160814Ssimon elapsed.sys / 1000, (elapsed.sys % 1000) * 1000, 331160814Ssimon elapsed.wall / 1000, (elapsed.wall % 1000) * 1000); 332160814Ssimon } 333160814Ssimon 334160814Ssimon Task* next; 335160814Ssimon { 336160814Ssimon Hold_lock hl(this->lock_); 337160814Ssimon 338160814Ssimon --this->running_; 339160814Ssimon 340160814Ssimon // Release the locks for the task. This must be done with the 341160814Ssimon // workqueue lock held. Get the next Task to run if any. 342160814Ssimon next = this->release_locks(t, &tl); 343160814Ssimon 344160814Ssimon if (next == NULL) 345160814Ssimon next = this->find_runnable(); 346160814Ssimon 347160814Ssimon // If we have another Task to run, get the Locks. This must 348160814Ssimon // be called while we are still holding the Workqueue lock. 349160814Ssimon if (next != NULL) 350160814Ssimon { 351160814Ssimon tl.clear(); 352160814Ssimon next->locks(&tl); 353160814Ssimon 354160814Ssimon ++this->running_; 355160814Ssimon } 356160814Ssimon } 357160814Ssimon 358160814Ssimon // We are done with this task. 359160814Ssimon delete t; 360160814Ssimon 361160814Ssimon t = next; 362160814Ssimon } 363160814Ssimon 364160814Ssimon return true; 365160814Ssimon} 366160814Ssimon 367160814Ssimon// Handle the return value of release_locks, and get tasks ready to 368160814Ssimon// run. 369160814Ssimon 370160814Ssimon// 1) If T is not runnable, queue it on the appropriate token. 371160814Ssimon 372160814Ssimon// 2) Otherwise, T is runnable. If *PRET is not NULL, then we have 373160814Ssimon// already decided which Task to run next. Add T to the list of 374160814Ssimon// runnable tasks, and signal another thread. 375160814Ssimon 376160814Ssimon// 3) Otherwise, *PRET is NULL. If IS_BLOCKER is false, then T was 377160814Ssimon// waiting on a write lock. We can grab that lock now, so we run T 378160814Ssimon// now. 379160814Ssimon 380160814Ssimon// 4) Otherwise, IS_BLOCKER is true. If we should run T soon, then 381160814Ssimon// run it now. 382160814Ssimon 383160814Ssimon// 5) Otherwise, check whether there are other tasks to run. If there 384160814Ssimon// are, then we generally get a better ordering if we run those tasks 385160814Ssimon// now, before T. A typical example is tasks waiting on the Dirsearch 386160814Ssimon// blocker. We don't want to run those tasks right away just because 387160814Ssimon// the Dirsearch was unblocked. 388160814Ssimon 389160814Ssimon// 6) Otherwise, there are no other tasks to run, so we might as well 390160814Ssimon// run this one now. 391160814Ssimon 392160814Ssimon// This function must be called with the Workqueue lock held. 393160814Ssimon 394160814Ssimon// Return true if we set *PRET to T, false otherwise. 395160814Ssimon 396160814Ssimonbool 397160814SsimonWorkqueue::return_or_queue(Task* t, bool is_blocker, Task** pret) 398160814Ssimon{ 399160814Ssimon Task_token* token = t->is_runnable(); 400160814Ssimon 401160814Ssimon if (token != NULL) 402160814Ssimon { 403160814Ssimon token->add_waiting(t); 404160814Ssimon ++this->waiting_; 405160814Ssimon return false; 406160814Ssimon } 407160814Ssimon 408160814Ssimon bool should_queue = false; 409160814Ssimon bool should_return = false; 410160814Ssimon 411160814Ssimon if (*pret != NULL) 412160814Ssimon should_queue = true; 413160814Ssimon else if (!is_blocker) 414160814Ssimon should_return = true; 415160814Ssimon else if (t->should_run_soon()) 416160814Ssimon should_return = true; 417160814Ssimon else if (!this->first_tasks_.empty() || !this->tasks_.empty()) 418160814Ssimon should_queue = true; 419160814Ssimon else 420160814Ssimon should_return = true; 421160814Ssimon 422160814Ssimon if (should_return) 423160814Ssimon { 424160814Ssimon gold_assert(*pret == NULL); 425160814Ssimon *pret = t; 426160814Ssimon return true; 427160814Ssimon } 428160814Ssimon else if (should_queue) 429160814Ssimon { 430160814Ssimon if (t->should_run_soon()) 431160814Ssimon this->first_tasks_.push_back(t); 432160814Ssimon else 433160814Ssimon this->tasks_.push_back(t); 434160814Ssimon this->condvar_.signal(); 435160814Ssimon return false; 436160814Ssimon } 437160814Ssimon 438160814Ssimon gold_unreachable(); 439160814Ssimon} 440160814Ssimon 441160814Ssimon// Release the locks associated with a Task. Return the first 442160814Ssimon// runnable Task that we find. If we find more runnable tasks, add 443160814Ssimon// them to the run queue and signal any other threads. This must be 444160814Ssimon// called with the Workqueue lock held. 445160814Ssimon 446160814SsimonTask* 447160814SsimonWorkqueue::release_locks(Task* t, Task_locker* tl) 448160814Ssimon{ 449160814Ssimon Task* ret = NULL; 450160814Ssimon for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p) 451160814Ssimon { 452160814Ssimon Task_token* token = *p; 453160814Ssimon if (token->is_blocker()) 454160814Ssimon { 455160814Ssimon if (token->remove_blocker()) 456160814Ssimon { 457160814Ssimon // The token has been unblocked. Every waiting Task may 458160814Ssimon // now be runnable. 459160814Ssimon Task* t; 460160814Ssimon while ((t = token->remove_first_waiting()) != NULL) 461160814Ssimon { 462160814Ssimon --this->waiting_; 463160814Ssimon this->return_or_queue(t, true, &ret); 464160814Ssimon } 465160814Ssimon } 466160814Ssimon } 467160814Ssimon else 468160814Ssimon { 469160814Ssimon token->remove_writer(t); 470160814Ssimon 471160814Ssimon // One more waiting Task may now be runnable. If we are 472160814Ssimon // going to run it next, we can stop. Otherwise we need to 473160814Ssimon // move all the Tasks to the runnable queue, to avoid a 474160814Ssimon // potential deadlock if the locking status changes before 475160814Ssimon // we run the next thread. 476160814Ssimon Task* t; 477160814Ssimon while ((t = token->remove_first_waiting()) != NULL) 478160814Ssimon { 479160814Ssimon --this->waiting_; 480160814Ssimon if (this->return_or_queue(t, false, &ret)) 481160814Ssimon break; 482160814Ssimon } 483160814Ssimon } 484160814Ssimon } 485160814Ssimon return ret; 486160814Ssimon} 487160814Ssimon 488160814Ssimon// Process all the tasks on the workqueue. Keep going until the 489160814Ssimon// workqueue is empty, or until we have been told to exit. This 490160814Ssimon// function is called by all threads. 491160814Ssimon 492160814Ssimonvoid 493160814SsimonWorkqueue::process(int thread_number) 494160814Ssimon{ 495160814Ssimon while (this->find_and_run_task(thread_number)) 496160814Ssimon ; 497160814Ssimon} 498160814Ssimon 499160814Ssimon// Set the number of threads to use for the workqueue, if we are using 500160814Ssimon// threads. 501160814Ssimon 502160814Ssimonvoid 503160814SsimonWorkqueue::set_thread_count(int threads) 504160814Ssimon{ 505160814Ssimon Hold_lock hl(this->lock_); 506160814Ssimon 507160814Ssimon this->threader_->set_thread_count(threads); 508160814Ssimon // Wake up all the threads, since something has changed. 509160814Ssimon this->condvar_.broadcast(); 510160814Ssimon} 511160814Ssimon 512160814Ssimon// Add a new blocker to an existing Task_token. 513160814Ssimon 514160814Ssimonvoid 515160814SsimonWorkqueue::add_blocker(Task_token* token) 516160814Ssimon{ 517160814Ssimon Hold_lock hl(this->lock_); 518160814Ssimon token->add_blocker(); 519160814Ssimon} 520160814Ssimon 521160814Ssimon} // End namespace gold. 522160814Ssimon