gold/workqueue.cc

   1 // workqueue.cc -- the workqueue for gold
   2
   3 // Copyright 2006, 2007 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 "workqueue.h"
  27 #include "workqueue-internal.h"
  28
  29 namespace gold
  30 {
  31
  32 // Task_token methods.
  33
  34 Task_token::Task_token()
  35   : is_blocker_(false), readers_(0), writer_(NULL)
  36 {
  37 }
  38
  39 Task_token::~Task_token()
  40 {
  41   gold_assert(this->readers_ == 0 && this->writer_ == NULL);
  42 }
  43
  44 bool
  45 Task_token::is_readable() const
  46 {
  47   gold_assert(!this->is_blocker_);
  48   return this->writer_ == NULL;
  49 }
  50
  51 void
  52 Task_token::add_reader()
  53 {
  54   gold_assert(!this->is_blocker_);
  55   gold_assert(this->is_readable());
  56   ++this->readers_;
  57 }
  58
  59 void
  60 Task_token::remove_reader()
  61 {
  62   gold_assert(!this->is_blocker_);
  63   gold_assert(this->readers_ > 0);
  64   --this->readers_;
  65 }
  66
  67 bool
  68 Task_token::is_writable() const
  69 {
  70   gold_assert(!this->is_blocker_);
  71   return this->writer_ == NULL && this->readers_ == 0;
  72 }
  73
  74 void
  75 Task_token::add_writer(const Task* t)
  76 {
  77   gold_assert(!this->is_blocker_);
  78   gold_assert(this->is_writable());
  79   this->writer_ = t;
  80 }
  81
  82 void
  83 Task_token::remove_writer(const Task* t)
  84 {
  85   gold_assert(!this->is_blocker_);
  86   gold_assert(this->writer_ == t);
  87   this->writer_ = NULL;
  88 }
  89
  90 bool
  91 Task_token::has_write_lock(const Task* t)
  92 {
  93   gold_assert(!this->is_blocker_);
  94   return this->writer_ == t;
  95 }
  96
  97 // For blockers, we just use the readers_ field.
  98
  99 void
 100 Task_token::add_blocker()
 101 {
 102   if (this->readers_ == 0 && this->writer_ == NULL)
 103     this->is_blocker_ = true;
 104   else
 105     gold_assert(this->is_blocker_);
 106   ++this->readers_;
 107 }
 108
 109 bool
 110 Task_token::remove_blocker()
 111 {
 112   gold_assert(this->is_blocker_ && this->readers_ > 0);
 113   --this->readers_;
 114   return this->readers_ == 0;
 115 }
 116
 117 bool
 118 Task_token::is_blocked() const
 119 {
 120   gold_assert(this->is_blocker_
 121               || (this->readers_ == 0 && this->writer_ == NULL));
 122   return this->readers_ > 0;
 123 }
 124
 125 // The Task_block_token class.
 126
 127 Task_block_token::Task_block_token(Task_token& token, Workqueue* workqueue)
 128   : token_(token), workqueue_(workqueue)
 129 {
 130   // We must increment the block count when the task is created and
 131   // put on the queue.  This object is created when the task is run,
 132   // so we don't increment the block count here.
 133   gold_assert(this->token_.is_blocked());
 134 }
 135
 136 Task_block_token::~Task_block_token()
 137 {
 138   if (this->token_.remove_blocker())
 139     {
 140       // Tell the workqueue that a blocker was cleared.  This is
 141       // always called in the main thread, so no locking is required.
 142       this->workqueue_->cleared_blocker();
 143     }
 144 }
 145
 146 // The simple single-threaded implementation of Workqueue_runner.
 147
 148 class Workqueue_runner_single : public Workqueue_runner
 149 {
 150  public:
 151   Workqueue_runner_single(Workqueue* workqueue)
 152     : Workqueue_runner(workqueue)
 153   { }
 154   ~Workqueue_runner_single()
 155   { }
 156
 157   void
 158   run(Task*, Task_locker*);
 159
 160   void
 161   set_thread_count(int);
 162 };
 163
 164 void
 165 Workqueue_runner_single::run(Task* t, Task_locker* tl)
 166 {
 167   t->run(this->get_workqueue());
 168   this->completed(t, tl);
 169 }
 170
 171 void
 172 Workqueue_runner_single::set_thread_count(int thread_count)
 173 {
 174   gold_assert(thread_count > 0);
 175 }
 176
 177 // Workqueue methods.
 178
 179 Workqueue::Workqueue(const General_options& options)
 180   : tasks_lock_(),
 181     first_tasks_(),
 182     tasks_(),
 183     completed_lock_(),
 184     completed_(),
 185     running_(0),
 186     queued_(0),
 187     completed_condvar_(this->completed_lock_),
 188     cleared_blockers_(0),
 189     desired_thread_count_(1)
 190 {
 191   bool threads = options.threads();
 192 #ifndef ENABLE_THREADS
 193   threads = false;
 194 #endif
 195   if (!threads)
 196     this->runner_ = new Workqueue_runner_single(this);
 197   else
 198     {
 199 #ifdef ENABLE_THREADS
 200       this->runner_ = new Workqueue_runner_threadpool(this);
 201 #else
 202       gold_unreachable();
 203 #endif
 204     }
 205 }
 206
 207 Workqueue::~Workqueue()
 208 {
 209   gold_assert(this->first_tasks_.empty());
 210   gold_assert(this->tasks_.empty());
 211   gold_assert(this->completed_.empty());
 212   gold_assert(this->running_ == 0);
 213 }
 214
 215 // Add a task to the queue.
 216
 217 void
 218 Workqueue::queue(Task* t)
 219 {
 220   {
 221     Hold_lock hl(this->tasks_lock_);
 222     this->tasks_.push_back(t);
 223   }
 224   {
 225     Hold_lock hl(this->completed_lock_);
 226     ++this->queued_;
 227   }
 228 }
 229
 230 // Add a task to the front of the queue.
 231
 232 void
 233 Workqueue::queue_front(Task* t)
 234 {
 235   {
 236     Hold_lock hl(this->tasks_lock_);
 237     this->first_tasks_.push_front(t);
 238   }
 239   {
 240     Hold_lock hl(this->completed_lock_);
 241     ++this->queued_;
 242   }
 243 }
 244
 245 // Clear the list of completed tasks.  Return whether we cleared
 246 // anything.  The completed_lock_ must be held when this is called.
 247
 248 bool
 249 Workqueue::clear_completed()
 250 {
 251   if (this->completed_.empty())
 252     return false;
 253   do
 254     {
 255       delete this->completed_.front();
 256       this->completed_.pop_front();
 257     }
 258   while (!this->completed_.empty());
 259   return true;
 260 }
 261
 262 // Find a runnable task in TASKS, which is non-empty.  Return NULL if
 263 // none could be found.  The tasks_lock_ must be held when this is
 264 // called.  Sets ALL_BLOCKED if all non-runnable tasks are waiting on
 265 // a blocker.
 266
 267 Task*
 268 Workqueue::find_runnable(Task_list* tasks, bool* all_blocked)
 269 {
 270   Task* tlast = tasks->back();
 271   *all_blocked = true;
 272   Task* t;
 273   do
 274     {
 275       t = tasks->front();
 276       tasks->pop_front();
 277
 278       Task::Is_runnable_type is_runnable = t->is_runnable(this);
 279       if (is_runnable == Task::IS_RUNNABLE)
 280         {
 281           {
 282             Hold_lock hl(this->completed_lock_);
 283             --this->queued_;
 284           }
 285
 286           return t;
 287         }
 288
 289       if (is_runnable != Task::IS_BLOCKED)
 290         *all_blocked = false;
 291
 292       tasks->push_back(t);
 293     }
 294   while (t != tlast);
 295
 296   // We couldn't find any runnable task.
 297   return NULL;
 298 }
 299
 300 // Process all the tasks on the workqueue.  This is the main loop in
 301 // the linker.  Note that as we process tasks, new tasks will be
 302 // added.
 303
 304 void
 305 Workqueue::process()
 306 {
 307   while (true)
 308     {
 309       Task* t;
 310       bool empty;
 311       bool all_blocked;
 312
 313       // Don't start more tasks than desired.
 314       {
 315         Hold_lock hl(this->completed_lock_);
 316
 317         this->clear_completed();
 318         while (this->running_ >= this->desired_thread_count_)
 319           {
 320             this->completed_condvar_.wait();
 321             this->clear_completed();
 322           }
 323       }
 324
 325       {
 326         Hold_lock hl(this->tasks_lock_);
 327
 328         bool first_empty;
 329         bool all_blocked_first;
 330         if (this->first_tasks_.empty())
 331           {
 332             t = NULL;
 333             empty = true;
 334             first_empty = true;
 335             all_blocked_first = false;
 336           }
 337         else
 338           {
 339             t = this->find_runnable(&this->first_tasks_, &all_blocked_first);
 340             empty = false;
 341             first_empty = false;
 342           }
 343
 344         if (t == NULL)
 345           {
 346             if (this->tasks_.empty())
 347               all_blocked = false;
 348             else
 349               {
 350                 t = this->find_runnable(&this->tasks_, &all_blocked);
 351                 if (!first_empty && !all_blocked_first)
 352                   all_blocked = false;
 353                 empty = false;
 354               }
 355           }
 356       }
 357
 358       // If T != NULL, it is a task we can run.
 359       // If T == NULL && empty, then there are no tasks waiting to
 360       // be run.
 361       // If T == NULL && !empty, then there tasks waiting to be
 362       // run, but they are waiting for something to unlock.
 363
 364       if (t != NULL)
 365         this->run(t);
 366       else if (!empty)
 367         {
 368           {
 369             Hold_lock hl(this->completed_lock_);
 370
 371             // There must be something for us to wait for, or we won't
 372             // be able to make progress.
 373             gold_assert(this->running_ > 0 || !this->completed_.empty());
 374
 375             if (all_blocked)
 376               {
 377                 this->cleared_blockers_ = 0;
 378                 int queued = this->queued_;
 379                 this->clear_completed();
 380                 while (this->cleared_blockers_ == 0
 381                        && queued == this->queued_)
 382                   {
 383                     if (this->running_ <= 0)
 384                       {
 385                         this->show_queued_tasks();
 386                         gold_unreachable();
 387                       }
 388                     this->completed_condvar_.wait();
 389                     this->clear_completed();
 390                   }
 391               }
 392             else
 393               {
 394                 if (this->running_ > 0)
 395                   {
 396                     // Wait for a task to finish.
 397                     this->completed_condvar_.wait();
 398                   }
 399                 this->clear_completed();
 400               }
 401           }
 402         }
 403       else
 404         {
 405           {
 406             Hold_lock hl(this->completed_lock_);
 407
 408             // If there are no running tasks, then we are done.
 409             if (this->running_ == 0)
 410               {
 411                 this->clear_completed();
 412                 return;
 413               }
 414
 415             // Wait for a task to finish.  Then we have to loop around
 416             // again in case it added any new tasks before finishing.
 417             this->completed_condvar_.wait();
 418             this->clear_completed();
 419           }
 420         }
 421     }
 422 }
 423
 424 // Run a task.  This is always called in the main thread.
 425
 426 void
 427 Workqueue::run(Task* t)
 428 {
 429   gold_debug(DEBUG_TASK, "starting  task %s", t->name().c_str());
 430
 431   {
 432     Hold_lock hl(this->completed_lock_);
 433     ++this->running_;
 434   }
 435   this->runner_->run(t, t->locks(this));
 436 }
 437
 438 // This is called when a task is completed to put the locks on the
 439 // list to be released.  We use a list because we only want the locks
 440 // to be released in the main thread.
 441
 442 void
 443 Workqueue::completed(Task* t, Task_locker* tl)
 444 {
 445   gold_debug(DEBUG_TASK, "completed task %s", t->name().c_str());
 446
 447   {
 448     Hold_lock hl(this->completed_lock_);
 449     gold_assert(this->running_ > 0);
 450     --this->running_;
 451     this->completed_.push_back(tl);
 452     this->completed_condvar_.signal();
 453   }
 454
 455   delete t;
 456 }
 457
 458 // This is called when the last task for a blocker has completed.
 459 // This is always called in the main thread.
 460
 461 void
 462 Workqueue::cleared_blocker()
 463 {
 464   ++this->cleared_blockers_;
 465 }
 466
 467 // Set the number of threads to use for the workqueue, if we are using
 468 // threads.
 469
 470 void
 471 Workqueue::set_thread_count(int threads)
 472 {
 473   gold_assert(threads > 0);
 474   this->desired_thread_count_ = threads;
 475   this->runner_->set_thread_count(threads);
 476 }
 477
 478 // Dump the list of queued tasks and their current state, for
 479 // debugging purposes.
 480
 481 void
 482 Workqueue::show_queued_tasks()
 483 {
 484   fprintf(stderr, _("gold task queue:\n"));
 485   Hold_lock hl(this->tasks_lock_);
 486   for (Task_list::const_iterator p = this->tasks_.begin();
 487        p != this->tasks_.end();
 488        ++p)
 489     {
 490       fprintf(stderr, "  %s ", (*p)->name().c_str());
 491       switch ((*p)->is_runnable(this))
 492         {
 493         case Task::IS_RUNNABLE:
 494           fprintf(stderr, "runnable");
 495           break;
 496         case Task::IS_BLOCKED:
 497           fprintf(stderr, "blocked");
 498           break;
 499         case Task::IS_LOCKED:
 500           fprintf(stderr, "locked");
 501           break;
 502         default:
 503           gold_unreachable();
 504         }
 505       putc('\n', stderr);
 506     }
 507 }
 508
 509 } // End namespace gold.