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