Home | History | Annotate | Download | only in gold
      1 // workqueue.cc -- the workqueue for gold
      2 
      3 // Copyright (C) 2006-2014 Free Software Foundation, Inc.
      4 // Written by Ian Lance Taylor <iant (at) 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.
    522