gold/workqueue.cc

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