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