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