gold/workqueue.cc

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