gold/workqueue.cc

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