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 void
 196 Workqueue::queue(Task* t)
 197 {
 198   Hold_lock hl(this->tasks_lock_);
 199   this->tasks_.push_back(t);
 200 }
 201
 202 // Clear the list of completed tasks.  Return whether we cleared
 203 // anything.  The completed_lock_ must be held when this is called.
 204
 205 bool
 206 Workqueue::clear_completed()
 207 {
 208   if (this->completed_.empty())
 209     return false;
 210   do
 211     {
 212       delete this->completed_.front();
 213       this->completed_.pop_front();
 214     }
 215   while (!this->completed_.empty());
 216   return true;
 217 }
 218
 219 // Find a runnable task in TASKS, which is non-empty.  Return NULL if
 220 // none could be found.  The tasks_lock_ must be held when this is
 221 // called.  Sets ALL_BLOCKED if all non-runnable tasks are waiting on
 222 // a blocker.
 223
 224 Task*
 225 Workqueue::find_runnable(Task_list& tasks, bool* all_blocked)
 226 {
 227   Task* tlast = tasks.back();
 228   *all_blocked = true;
 229   while (true)
 230     {
 231       Task* t = tasks.front();
 232       tasks.pop_front();
 233
 234       Task::Is_runnable_type is_runnable = t->is_runnable(this);
 235       if (is_runnable == Task::IS_RUNNABLE)
 236         return t;
 237
 238       if (is_runnable != Task::IS_BLOCKED)
 239         *all_blocked = false;
 240
 241       tasks.push_back(t);
 242
 243       if (t == tlast)
 244         {
 245           // We couldn't find any runnable task.  If there are any
 246           // completed tasks, free their locks and try again.
 247
 248           {
 249             Hold_lock hl2(this->completed_lock_);
 250
 251             if (!this->clear_completed())
 252               {
 253                 // There had better be some tasks running, or we will
 254                 // never find a runnable task.
 255                 assert(this->running_ > 0);
 256
 257                 // We couldn't find any runnable tasks, and we
 258                 // couldn't release any locks.
 259                 return NULL;
 260               }
 261           }
 262
 263           // We're going around again, so recompute ALL_BLOCKED.
 264           *all_blocked = true;
 265         }
 266     }
 267 }
 268
 269 // Process all the tasks on the workqueue.  This is the main loop in
 270 // the linker.  Note that as we process tasks, new tasks will be
 271 // added.
 272
 273 void
 274 Workqueue::process()
 275 {
 276   while (true)
 277     {
 278       Task* t;
 279       bool empty;
 280       bool all_blocked;
 281
 282       {
 283         Hold_lock hl(this->tasks_lock_);
 284
 285         if (this->tasks_.empty())
 286           {
 287             t = NULL;
 288             empty = true;
 289             all_blocked = false;
 290           }
 291         else
 292           {
 293             t = this->find_runnable(this->tasks_, &all_blocked);
 294             empty = false;
 295           }
 296       }
 297
 298       // If T != NULL, it is a task we can run.
 299       // If T == NULL && empty, then there are no tasks waiting to
 300       // be run at this level.
 301       // If T == NULL && !empty, then there tasks waiting to be
 302       // run at this level, but they are waiting for something to
 303       // unlock.
 304
 305       if (t != NULL)
 306         this->run(t);
 307       else if (!empty)
 308         {
 309           {
 310             Hold_lock hl(this->completed_lock_);
 311
 312             // There must be something for us to wait for, or we won't
 313             // be able to make progress.
 314             assert(this->running_ > 0 || !this->completed_.empty());
 315
 316             if (all_blocked)
 317               {
 318                 this->cleared_blockers_ = 0;
 319                 this->clear_completed();
 320                 while (this->cleared_blockers_ == 0)
 321                   {
 322                     assert(this->running_ > 0);
 323                     this->completed_condvar_.wait();
 324                     this->clear_completed();
 325                   }
 326               }
 327             else
 328               {
 329                 if (this->running_ > 0)
 330                   {
 331                     // Wait for a task to finish.
 332                     this->completed_condvar_.wait();
 333                   }
 334                 this->clear_completed();
 335               }
 336           }
 337         }
 338       else
 339         {
 340           {
 341             Hold_lock hl(this->completed_lock_);
 342
 343             // If there are no running tasks, then we are done.
 344             if (this->running_ == 0)
 345               {
 346                 this->clear_completed();
 347                 return;
 348               }
 349
 350             // Wait for a task to finish.  Then we have to loop around
 351             // again in case it added any new tasks before finishing.
 352             this->completed_condvar_.wait();
 353             this->clear_completed();
 354           }
 355         }
 356     }
 357 }
 358
 359 // Run a task.  This is always called in the main thread.
 360
 361 void
 362 Workqueue::run(Task* t)
 363 {
 364   ++this->running_;
 365   this->runner_->run(t, t->locks(this));
 366 }
 367
 368 // This is called when a task is completed to put the locks on the
 369 // list to be released.  We use a list because we only want the locks
 370 // to be released in the main thread.
 371
 372 void
 373 Workqueue::completed(Task* t, Task_locker* tl)
 374 {
 375   {
 376     Hold_lock hl(this->completed_lock_);
 377     assert(this->running_ > 0);
 378     --this->running_;
 379     this->completed_.push_back(tl);
 380     this->completed_condvar_.signal();
 381   }
 382   delete t;
 383 }
 384
 385 // This is called when the last task for a blocker has completed.
 386 // This is always called in the main thread.
 387
 388 void
 389 Workqueue::cleared_blocker()
 390 {
 391   ++this->cleared_blockers_;
 392 }
 393
 394 } // End namespace gold.