Subversion Repositories open8_urisc

// workqueue.cc -- the workqueue for gold

// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.

// Written by Ian Lance Taylor <iant@google.com>.

// This file is part of gold.

// This program is free software; you can redistribute it and/or modify

// it under the terms of the GNU General Public License as published by

// the Free Software Foundation; either version 3 of the License, or

// (at your option) any later version.

// This program is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License

// along with this program; if not, write to the Free Software

// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,

// MA 02110-1301, USA.

#include "gold.h"

#include "debug.h"

#include "options.h"

#include "timer.h"

#include "workqueue.h"

#include "workqueue-internal.h"

namespace gold

{

// Class Task_list.

// Add T to the end of the list.

inline void

Task_list::push_back(Task* t)

{

  gold_assert(t->list_next() == NULL);

  if (this->head_ == NULL)

    {

      this->head_ = t;

      this->tail_ = t;

    }

  else

    {

      this->tail_->set_list_next(t);

      this->tail_ = t;

    }

}

// Add T to the front of the list.

inline void

Task_list::push_front(Task* t)

{

  gold_assert(t->list_next() == NULL);

  if (this->head_ == NULL)

    {

      this->head_ = t;

      this->tail_ = t;

    }

  else

    {

      t->set_list_next(this->head_);

      this->head_ = t;

    }

}

// Remove and return the first Task waiting for this lock to be

// released.

inline Task*

Task_list::pop_front()

{

  Task* ret = this->head_;

  if (ret != NULL)

    {

      if (ret == this->tail_)

        {

          gold_assert(ret->list_next() == NULL);

          this->head_ = NULL;

          this->tail_ = NULL;

        }

      else

        {

          this->head_ = ret->list_next();

          gold_assert(this->head_ != NULL);

          ret->clear_list_next();

        }

    }

  return ret;

}

// The simple single-threaded implementation of Workqueue_threader.

class Workqueue_threader_single : public Workqueue_threader

{

 public:

  Workqueue_threader_single(Workqueue* workqueue)

    : Workqueue_threader(workqueue)

  { }

  ~Workqueue_threader_single()

  { }

  void

  set_thread_count(int thread_count)

  { gold_assert(thread_count > 0); }

  bool

  should_cancel_thread(int)

  { return false; }

};

// Workqueue methods.

Workqueue::Workqueue(const General_options& options)

  : lock_(),

    first_tasks_(),

    tasks_(),

    running_(0),

    waiting_(0),

    condvar_(this->lock_),

    threader_(NULL)

{

  bool threads = options.threads();

#ifndef ENABLE_THREADS

  threads = false;

#endif

  if (!threads)

    this->threader_ = new Workqueue_threader_single(this);

  else

    {

#ifdef ENABLE_THREADS

      this->threader_ = new Workqueue_threader_threadpool(this);

#else

      gold_unreachable();

#endif

    }

}

Workqueue::~Workqueue()

{

}

// Add a task to the end of a specific queue, or put it on the list

// waiting for a Token.

void

Workqueue::add_to_queue(Task_list* queue, Task* t, bool front)

{

  Hold_lock hl(this->lock_);

  Task_token* token = t->is_runnable();

  if (token != NULL)

    {

      if (front)

        token->add_waiting_front(t);

      else

        token->add_waiting(t);

      ++this->waiting_;

    }

  else

    {

      if (front)

        queue->push_front(t);

      else

        queue->push_back(t);

      // Tell any waiting thread that there is work to do.

      this->condvar_.signal();

    }

}

// Add a task to the queue.

void

Workqueue::queue(Task* t)

{

  this->add_to_queue(&this->tasks_, t, false);

}

// Queue a task which should run soon.

void

Workqueue::queue_soon(Task* t)

{

  t->set_should_run_soon();

  this->add_to_queue(&this->first_tasks_, t, false);

}

// Queue a task which should run next.

void

Workqueue::queue_next(Task* t)

{

  t->set_should_run_soon();

  this->add_to_queue(&this->first_tasks_, t, true);

}

// Return whether to cancel the current thread.

inline bool

Workqueue::should_cancel_thread(int thread_number)

{

  return this->threader_->should_cancel_thread(thread_number);

}

// Find a runnable task in TASKS.  Return NULL if none could be found.

// If we find a Task waiting for a Token, add it to the list for that

// Token.  The workqueue lock must be held when this is called.

Task*

Workqueue::find_runnable_in_list(Task_list* tasks)

{

  Task* t;

  while ((t = tasks->pop_front()) != NULL)

    {

      Task_token* token = t->is_runnable();

      if (token == NULL)

        return t;

      token->add_waiting(t);

      ++this->waiting_;

    }

  // We couldn't find any runnable task.

  return NULL;

}

// Find a runnable task.  Return NULL if none could be found.  The

// workqueue lock must be held when this is called.

Task*

Workqueue::find_runnable()

{

  Task* t = this->find_runnable_in_list(&this->first_tasks_);

  if (t == NULL)

    t = this->find_runnable_in_list(&this->tasks_);

  return t;

}

// Find a runnable a task, and wait until we find one.  Return NULL if

// we should exit.  The workqueue lock must be held when this is

// called.

Task*

Workqueue::find_runnable_or_wait(int thread_number)

{

  Task* t = this->find_runnable();

  while (t == NULL)

    {

      if (this->running_ == 0

          && this->first_tasks_.empty()

          && this->tasks_.empty())

        {

          // Kick all the threads to make them exit.

          this->condvar_.broadcast();

          gold_assert(this->waiting_ == 0);

          return NULL;

        }

      if (this->should_cancel_thread(thread_number))

        return NULL;

      gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);

      this->condvar_.wait();

      gold_debug(DEBUG_TASK, "%3d awake", thread_number);

      t = this->find_runnable();

    }

  return t;

}

// Find and run tasks.  If we can't find a runnable task, wait for one

// to become available.  If we run a task, and it frees up another

// runnable task, then run that one too.  This returns true if we

// should look for another task, false if we are cancelling this

// thread.

bool

Workqueue::find_and_run_task(int thread_number)

{

  Task* t;

  Task_locker tl;

  {

    Hold_lock hl(this->lock_);

    // Find a runnable task.

    t = this->find_runnable_or_wait(thread_number);

    if (t == NULL)

      return false;

    // Get the locks for the task.  This must be called while we are

    // still holding the Workqueue lock.

    t->locks(&tl);

    ++this->running_;

  }

  while (t != NULL)

    {

      gold_debug(DEBUG_TASK, "%3d running   task %s", thread_number,

                 t->name().c_str());

      Timer timer;

      if (is_debugging_enabled(DEBUG_TASK))

        timer.start();

      t->run(this);

      if (is_debugging_enabled(DEBUG_TASK))

        {

          Timer::TimeStats elapsed = timer.get_elapsed_time();

          gold_debug(DEBUG_TASK,

                     "%3d completed task %s "

                     "(user: %ld.%06ld sys: %ld.%06ld wall: %ld.%06ld)",

                     thread_number,  t->name().c_str(),

                     elapsed.user / 1000, (elapsed.user % 1000) * 1000,

                     elapsed.sys / 1000, (elapsed.sys % 1000) * 1000,

                     elapsed.wall / 1000, (elapsed.wall % 1000) * 1000);

        }

      Task* next;

      {

        Hold_lock hl(this->lock_);

        --this->running_;

        // Release the locks for the task.  This must be done with the

        // workqueue lock held.  Get the next Task to run if any.

        next = this->release_locks(t, &tl);

        if (next == NULL)

          next = this->find_runnable();

        // If we have another Task to run, get the Locks.  This must

        // be called while we are still holding the Workqueue lock.

        if (next != NULL)

          {

            tl.clear();

            next->locks(&tl);

            ++this->running_;

          }

      }

      // We are done with this task.

      delete t;

      t = next;

    }

  return true;

}

// Handle the return value of release_locks, and get tasks ready to

// run.

// 1) If T is not runnable, queue it on the appropriate token.

// 2) Otherwise, T is runnable.  If *PRET is not NULL, then we have

// already decided which Task to run next.  Add T to the list of

// runnable tasks, and signal another thread.

// 3) Otherwise, *PRET is NULL.  If IS_BLOCKER is false, then T was

// waiting on a write lock.  We can grab that lock now, so we run T

// now.

// 4) Otherwise, IS_BLOCKER is true.  If we should run T soon, then

// run it now.

// 5) Otherwise, check whether there are other tasks to run.  If there

// are, then we generally get a better ordering if we run those tasks

// now, before T.  A typical example is tasks waiting on the Dirsearch

// blocker.  We don't want to run those tasks right away just because

// the Dirsearch was unblocked.

// 6) Otherwise, there are no other tasks to run, so we might as well

// run this one now.

// This function must be called with the Workqueue lock held.

// Return true if we set *PRET to T, false otherwise.

bool

Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)

{

  Task_token* token = t->is_runnable();

  if (token != NULL)

    {

      token->add_waiting(t);

      ++this->waiting_;

      return false;

    }

  bool should_queue = false;

  bool should_return = false;

  if (*pret != NULL)

    should_queue = true;

  else if (!is_blocker)

    should_return = true;

  else if (t->should_run_soon())

    should_return = true;

  else if (!this->first_tasks_.empty() || !this->tasks_.empty())

    should_queue = true;

  else

    should_return = true;

  if (should_return)

    {

      gold_assert(*pret == NULL);

      *pret = t;

      return true;

    }

  else if (should_queue)

    {

      if (t->should_run_soon())

        this->first_tasks_.push_back(t);

      else

        this->tasks_.push_back(t);

      this->condvar_.signal();

      return false;

    }

  gold_unreachable();

}

// Release the locks associated with a Task.  Return the first

// runnable Task that we find.  If we find more runnable tasks, add

// them to the run queue and signal any other threads.  This must be

// called with the Workqueue lock held.

Task*

Workqueue::release_locks(Task* t, Task_locker* tl)

{

  Task* ret = NULL;

  for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)

    {

      Task_token* token = *p;

      if (token->is_blocker())

        {

          if (token->remove_blocker())

            {

              // The token has been unblocked.  Every waiting Task may

              // now be runnable.

              Task* t;

              while ((t = token->remove_first_waiting()) != NULL)

                {

                  --this->waiting_;

                  this->return_or_queue(t, true, &ret);

                }

            }

        }

      else

        {

          token->remove_writer(t);

          // One more waiting Task may now be runnable.  If we are

          // going to run it next, we can stop.  Otherwise we need to

          // move all the Tasks to the runnable queue, to avoid a

          // potential deadlock if the locking status changes before

          // we run the next thread.

          Task* t;

          while ((t = token->remove_first_waiting()) != NULL)

            {

              --this->waiting_;

              if (this->return_or_queue(t, false, &ret))

                break;

            }

        }

    }

  return ret;

}

// Process all the tasks on the workqueue.  Keep going until the

// workqueue is empty, or until we have been told to exit.  This

// function is called by all threads.

void

Workqueue::process(int thread_number)

{

  while (this->find_and_run_task(thread_number))

    ;

}

// Set the number of threads to use for the workqueue, if we are using

// threads.

void

Workqueue::set_thread_count(int threads)

{

  Hold_lock hl(this->lock_);

  this->threader_->set_thread_count(threads);

  // Wake up all the threads, since something has changed.

  this->condvar_.broadcast();

}

// Add a new blocker to an existing Task_token.

void

Workqueue::add_blocker(Task_token* token)

{

  Hold_lock hl(this->lock_);

  token->add_blocker();

}

} // End namespace gold.