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 "debug.h"
  26 #include "options.h"
  27 #include "workqueue.h"
  28 #include "workqueue-internal.h"
  29
  30 namespace gold
  31 {
  32
  33 // Class Task_list.
  34
  35 // Add T to the end of the list.
  36
  37 inline void
  38 Task_list::push_back(Task* t)
  39 {
  40   gold_assert(t->list_next() == NULL);
  41   if (this->head_ == NULL)
  42     {
  43       this->head_ = t;
  44       this->tail_ = t;
  45     }
  46   else
  47     {
  48       this->tail_->set_list_next(t);
  49       this->tail_ = t;
  50     }
  51 }
  52
  53 // Remove and return the first Task waiting for this lock to be
  54 // released.
  55
  56 inline Task*
  57 Task_list::pop_front()
  58 {
  59   Task* ret = this->head_;
  60   if (ret != NULL)
  61     {
  62       if (ret == this->tail_)
  63         {
  64           gold_assert(ret->list_next() == NULL);
  65           this->head_ = NULL;
  66           this->tail_ = NULL;
  67         }
  68       else
  69         {
  70           this->head_ = ret->list_next();
  71           gold_assert(this->head_ != NULL);
  72           ret->clear_list_next();
  73         }
  74     }
  75   return ret;
  76 }
  77
  78 // The simple single-threaded implementation of Workqueue_threader.
  79
  80 class Workqueue_threader_single : public Workqueue_threader
  81 {
  82  public:
  83   Workqueue_threader_single(Workqueue* workqueue)
  84     : Workqueue_threader(workqueue)
  85   { }
  86   ~Workqueue_threader_single()
  87   { }
  88
  89   void
  90   set_thread_count(int thread_count)
  91   { gold_assert(thread_count > 0); }
  92
  93   bool
  94   should_cancel_thread()
  95   { return false; }
  96 };
  97
  98 // Workqueue methods.
  99
 100 Workqueue::Workqueue(const General_options& options)
 101   : lock_(),
 102     first_tasks_(),
 103     tasks_(),
 104     running_(0),
 105     waiting_(0),
 106     condvar_(this->lock_),
 107     threader_(NULL)
 108 {
 109   bool threads = options.threads();
 110 #ifndef ENABLE_THREADS
 111   threads = false;
 112 #endif
 113   if (!threads)
 114     this->threader_ = new Workqueue_threader_single(this);
 115   else
 116     {
 117 #ifdef ENABLE_THREADS
 118       this->threader_ = new Workqueue_threader_threadpool(this);
 119 #else
 120       gold_unreachable();
 121 #endif
 122     }
 123 }
 124
 125 Workqueue::~Workqueue()
 126 {
 127 }
 128
 129 // Add a task to the end of a specific queue, or put it on the list
 130 // waiting for a Token.
 131
 132 void
 133 Workqueue::add_to_queue(Task_list* queue, Task* t)
 134 {
 135   Hold_lock hl(this->lock_);
 136
 137   Task_token* token = t->is_runnable();
 138   if (token != NULL)
 139     {
 140       token->add_waiting(t);
 141       ++this->waiting_;
 142     }
 143   else
 144     {
 145       queue->push_back(t);
 146       // Tell any waiting thread that there is work to do.
 147       this->condvar_.signal();
 148     }
 149 }
 150
 151 // Add a task to the queue.
 152
 153 void
 154 Workqueue::queue(Task* t)
 155 {
 156   this->add_to_queue(&this->tasks_, t);
 157 }
 158
 159 // Add a task to the front of the queue.
 160
 161 void
 162 Workqueue::queue_front(Task* t)
 163 {
 164   t->set_should_run_soon();
 165   this->add_to_queue(&this->first_tasks_, t);
 166 }
 167
 168 // Return whether to cancel the current thread.
 169
 170 inline bool
 171 Workqueue::should_cancel_thread()
 172 {
 173   return this->threader_->should_cancel_thread();
 174 }
 175
 176 // Find a runnable task in TASKS.  Return NULL if none could be found.
 177 // If we find a Task waiting for a Token, add it to the list for that
 178 // Token.  The workqueue lock must be held when this is called.
 179
 180 Task*
 181 Workqueue::find_runnable_in_list(Task_list* tasks)
 182 {
 183   Task* t;
 184   while ((t = tasks->pop_front()) != NULL)
 185     {
 186       Task_token* token = t->is_runnable();
 187
 188       if (token == NULL)
 189         return t;
 190
 191       token->add_waiting(t);
 192       ++this->waiting_;
 193     }
 194
 195   // We couldn't find any runnable task.
 196   return NULL;
 197 }
 198
 199 // Find a runnable task.  Return NULL if none could be found.  The
 200 // workqueue lock must be held when this is called.
 201
 202 Task*
 203 Workqueue::find_runnable()
 204 {
 205   Task* t = this->find_runnable_in_list(&this->first_tasks_);
 206   if (t == NULL)
 207     t = this->find_runnable_in_list(&this->tasks_);
 208   return t;
 209 }
 210
 211 // Find a runnable a task, and wait until we find one.  Return NULL if
 212 // we should exit.  The workqueue lock must be held when this is
 213 // called.
 214
 215 Task*
 216 Workqueue::find_runnable_or_wait(int thread_number)
 217 {
 218   Task* t = this->find_runnable();
 219
 220   while (t == NULL)
 221     {
 222       if (this->running_ == 0
 223           && this->first_tasks_.empty()
 224           && this->tasks_.empty())
 225         {
 226           // Kick all the threads to make them exit.
 227           this->condvar_.broadcast();
 228
 229           gold_assert(this->waiting_ == 0);
 230           return NULL;
 231         }
 232
 233       if (this->should_cancel_thread())
 234         return NULL;
 235
 236       gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
 237
 238       this->condvar_.wait();
 239
 240       gold_debug(DEBUG_TASK, "%3d awake", thread_number);
 241
 242       t = this->find_runnable();
 243     }
 244
 245   return t;
 246 }
 247
 248 // Find and run tasks.  If we can't find a runnable task, wait for one
 249 // to become available.  If we run a task, and it frees up another
 250 // runnable task, then run that one too.  This returns true if we
 251 // should look for another task, false if we are cancelling this
 252 // thread.
 253
 254 bool
 255 Workqueue::find_and_run_task(int thread_number)
 256 {
 257   Task* t;
 258   Task_locker tl;
 259
 260   {
 261     Hold_lock hl(this->lock_);
 262
 263     // Find a runnable task.
 264     t = this->find_runnable_or_wait(thread_number);
 265
 266     if (t == NULL)
 267       return false;
 268
 269     // Get the locks for the task.  This must be called while we are
 270     // still holding the Workqueue lock.
 271     t->locks(&tl);
 272
 273     ++this->running_;
 274   }
 275
 276   while (t != NULL)
 277     {
 278       gold_debug(DEBUG_TASK, "%3d running   task %s", thread_number,
 279                  t->name().c_str());
 280
 281       t->run(this);
 282
 283       gold_debug(DEBUG_TASK, "%3d completed task %s", thread_number,
 284                  t->name().c_str());
 285
 286       Task* next;
 287       {
 288         Hold_lock hl(this->lock_);
 289
 290         --this->running_;
 291
 292         // Release the locks for the task.  This must be done with the
 293         // workqueue lock held.  Get the next Task to run if any.
 294         next = this->release_locks(t, &tl);
 295
 296         if (next == NULL)
 297           next = this->find_runnable();
 298
 299         // If we have another Task to run, get the Locks.  This must
 300         // be called while we are still holding the Workqueue lock.
 301         if (next != NULL)
 302           {
 303             tl.clear();
 304             next->locks(&tl);
 305
 306             ++this->running_;
 307           }
 308       }
 309
 310       // We are done with this task.
 311       delete t;
 312
 313       t = next;
 314     }
 315
 316   return true;
 317 }
 318
 319 // Handle the return value of release_locks, and get tasks ready to
 320 // run.
 321
 322 // 1) If T is not runnable, queue it on the appropriate token.
 323
 324 // 2) Otherwise, T is runnable.  If *PRET is not NULL, then we have
 325 // already decided which Task to run next.  Add T to the list of
 326 // runnable tasks, and signal another thread.
 327
 328 // 3) Otherwise, *PRET is NULL.  If IS_BLOCKER is false, then T was
 329 // waiting on a write lock.  We can grab that lock now, so we run T
 330 // now.
 331
 332 // 4) Otherwise, IS_BLOCKER is true.  If we should run T soon, then
 333 // run it now.
 334
 335 // 5) Otherwise, check whether there are other tasks to run.  If there
 336 // are, then we generally get a better ordering if we run those tasks
 337 // now, before T.  A typical example is tasks waiting on the Dirsearch
 338 // blocker.  We don't want to run those tasks right away just because
 339 // the Dirsearch was unblocked.
 340
 341 // 6) Otherwise, there are no other tasks to run, so we might as well
 342 // run this one now.
 343
 344 // This function must be called with the Workqueue lock held.
 345
 346 // Return true if we set *PRET to T, false otherwise.
 347
 348 bool
 349 Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)
 350 {
 351   Task_token* token = t->is_runnable();
 352
 353   if (token != NULL)
 354     {
 355       token->add_waiting(t);
 356       ++this->waiting_;
 357       return false;
 358     }
 359
 360   bool should_queue = false;
 361   bool should_return = false;
 362
 363   if (*pret != NULL)
 364     should_queue = true;
 365   else if (!is_blocker)
 366     should_return = true;
 367   else if (t->should_run_soon())
 368     should_return = true;
 369   else if (!this->first_tasks_.empty() || !this->tasks_.empty())
 370     should_queue = true;
 371   else
 372     should_return = true;
 373
 374   if (should_return)
 375     {
 376       gold_assert(*pret == NULL);
 377       *pret = t;
 378       return true;
 379     }
 380   else if (should_queue)
 381     {
 382       if (t->should_run_soon())
 383         this->first_tasks_.push_back(t);
 384       else
 385         this->tasks_.push_back(t);
 386       this->condvar_.signal();
 387       return false;
 388     }
 389
 390   gold_unreachable();
 391 }
 392
 393 // Release the locks associated with a Task.  Return the first
 394 // runnable Task that we find.  If we find more runnable tasks, add
 395 // them to the run queue and signal any other threads.  This must be
 396 // called with the Workqueue lock held.
 397
 398 Task*
 399 Workqueue::release_locks(Task* t, Task_locker* tl)
 400 {
 401   Task* ret = NULL;
 402   for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)
 403     {
 404       Task_token* token = *p;
 405       if (token->is_blocker())
 406         {
 407           if (token->remove_blocker())
 408             {
 409               // The token has been unblocked.  Every waiting Task may
 410               // now be runnable.
 411               Task* t;
 412               while ((t = token->remove_first_waiting()) != NULL)
 413                 {
 414                   --this->waiting_;
 415                   this->return_or_queue(t, true, &ret);
 416                 }
 417             }
 418         }
 419       else
 420         {
 421           token->remove_writer(t);
 422
 423           // One more waiting Task may now be runnable.  If we are
 424           // going to run it next, we can stop.  Otherwise we need to
 425           // move all the Tasks to the runnable queue, to avoid a
 426           // potential deadlock if the locking status changes before
 427           // we run the next thread.
 428           Task* t;
 429           while ((t = token->remove_first_waiting()) != NULL)
 430             {
 431               --this->waiting_;
 432               if (this->return_or_queue(t, false, &ret))
 433                 break;
 434             }
 435         }
 436     }
 437   return ret;
 438 }
 439
 440 // Process all the tasks on the workqueue.  Keep going until the
 441 // workqueue is empty, or until we have been told to exit.  This
 442 // function is called by all threads.
 443
 444 void
 445 Workqueue::process(int thread_number)
 446 {
 447   while (this->find_and_run_task(thread_number))
 448     ;
 449 }
 450
 451 // Set the number of threads to use for the workqueue, if we are using
 452 // threads.
 453
 454 void
 455 Workqueue::set_thread_count(int threads)
 456 {
 457   Hold_lock hl(this->lock_);
 458
 459   this->threader_->set_thread_count(threads);
 460   // Wake up all the threads, since something has changed.
 461   this->condvar_.broadcast();
 462 }
 463
 464 } // End namespace gold.