gold/workqueue.cc

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