// workqueue.cc -- the workqueue for gold
-#include "gold.h"
+// Copyright (C) 2006-2020 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.
-#include <cassert>
+// 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
{
-// Task_token methods.
+// Class Task_list.
-Task_token::Task_token()
- : is_blocker_(false), readers_(0), writer_(NULL)
+// 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;
+ }
}
-Task_token::~Task_token()
+// Add T to the front of the list.
+
+inline void
+Task_list::push_front(Task* t)
{
- assert(this->readers_ == 0 && this->writer_ == NULL);
+ 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;
+ }
}
-bool
-Task_token::is_readable() const
+// Remove and return the first Task waiting for this lock to be
+// released.
+
+inline Task*
+Task_list::pop_front()
{
- assert(!this->is_blocker_);
- return this->writer_ == NULL;
+ 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;
}
-void
-Task_token::add_reader()
+// The simple single-threaded implementation of Workqueue_threader.
+
+class Workqueue_threader_single : public Workqueue_threader
{
- assert(!this->is_blocker_);
- assert(this->is_readable());
- ++this->readers_;
-}
+ public:
+ Workqueue_threader_single(Workqueue* workqueue)
+ : Workqueue_threader(workqueue)
+ { }
+ ~Workqueue_threader_single()
+ { }
-void
-Task_token::remove_reader()
+ 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)
{
- assert(!this->is_blocker_);
- assert(this->readers_ > 0);
- --this->readers_;
+ 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
+ }
}
-bool
-Task_token::is_writable() const
+Workqueue::~Workqueue()
{
- assert(!this->is_blocker_);
- return this->writer_ == NULL && this->readers_ == 0;
}
+// Add a task to the end of a specific queue, or put it on the list
+// waiting for a Token.
+
void
-Task_token::add_writer(const Task* t)
+Workqueue::add_to_queue(Task_list* queue, Task* t, bool front)
{
- assert(!this->is_blocker_);
- assert(this->is_writable());
- this->writer_ = t;
+ 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
-Task_token::remove_writer(const Task* t)
+Workqueue::queue(Task* t)
{
- assert(!this->is_blocker_);
- assert(this->writer_ == t);
- this->writer_ = NULL;
+ this->add_to_queue(&this->tasks_, t, false);
}
-bool
-Task_token::has_write_lock(const Task* t)
+// Queue a task which should run soon.
+
+void
+Workqueue::queue_soon(Task* t)
{
- assert(!this->is_blocker_);
- return this->writer_ == t;
+ t->set_should_run_soon();
+ this->add_to_queue(&this->first_tasks_, t, false);
}
-// For blockers, we just use the readers_ field.
+// Queue a task which should run next.
void
-Task_token::add_blocker()
+Workqueue::queue_next(Task* t)
{
- if (this->readers_ == 0 && this->writer_ == NULL)
- this->is_blocker_ = true;
- else
- assert(this->is_blocker_);
- ++this->readers_;
+ t->set_should_run_soon();
+ this->add_to_queue(&this->first_tasks_, t, true);
}
-bool
-Task_token::remove_blocker()
-{
- assert(this->is_blocker_ && this->readers_ > 0);
- --this->readers_;
- return this->readers_ == 0;
-}
+// Return whether to cancel the current thread.
-bool
-Task_token::is_blocked() const
+inline bool
+Workqueue::should_cancel_thread(int thread_number)
{
- assert(this->is_blocker_ || (this->readers_ == 0 && this->writer_ == NULL));
- return this->readers_ > 0;
+ return this->threader_->should_cancel_thread(thread_number);
}
-// The Task_block_token class.
+// 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_block_token::Task_block_token(Task_token& token, Workqueue* workqueue)
- : token_(token), workqueue_(workqueue)
+Task*
+Workqueue::find_runnable_in_list(Task_list* tasks)
{
- // We must increment the block count when the task is created and
- // put on the queue. This object is created when the task is run,
- // so we don't increment the block count here.
- assert(this->token_.is_blocked());
+ 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;
}
-Task_block_token::~Task_block_token()
+// 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()
{
- if (this->token_.remove_blocker())
- {
- // Tell the workqueue that a blocker was cleared. This is
- // always called in the main thread, so no locking is required.
- this->workqueue_->cleared_blocker();
- }
+ Task* t = this->find_runnable_in_list(&this->first_tasks_);
+ if (t == NULL)
+ t = this->find_runnable_in_list(&this->tasks_);
+ return t;
}
-// The Workqueue_runner abstract class.
+// 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.
-class Workqueue_runner
+Task*
+Workqueue::find_runnable_or_wait(int thread_number)
{
- public:
- Workqueue_runner(Workqueue* workqueue)
- : workqueue_(workqueue)
- { }
- virtual ~Workqueue_runner()
- { }
+ Task* t = this->find_runnable();
- // Run a task. This is always called in the main thread.
- virtual void run(Task*, Task_locker*) = 0;
+ 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();
- protected:
- // This is called by an implementation when a task is completed.
- void completed(Task* t, Task_locker* tl)
- { this->workqueue_->completed(t, tl); }
+ gold_assert(this->waiting_ == 0);
+ return NULL;
+ }
- Workqueue* get_workqueue() const
- { return this->workqueue_; }
+ if (this->should_cancel_thread(thread_number))
+ return NULL;
- private:
- Workqueue* workqueue_;
-};
+ gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
-// The simple single-threaded implementation of Workqueue_runner.
+ this->condvar_.wait();
-class Workqueue_runner_single : public Workqueue_runner
-{
- public:
- Workqueue_runner_single(Workqueue* workqueue)
- : Workqueue_runner(workqueue)
- { }
- ~Workqueue_runner_single()
- { }
+ gold_debug(DEBUG_TASK, "%3d awake", thread_number);
- void run(Task*, Task_locker*);
-};
+ t = this->find_runnable();
+ }
-void
-Workqueue_runner_single::run(Task* t, Task_locker* tl)
-{
- t->run(this->get_workqueue());
- this->completed(t, tl);
+ return t;
}
-// Workqueue methods.
+// 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.
-Workqueue::Workqueue(const General_options&)
- : tasks_lock_(),
- tasks_(),
- completed_lock_(),
- completed_(),
- running_(0),
- completed_condvar_(this->completed_lock_),
- cleared_blockers_(0)
+bool
+Workqueue::find_and_run_task(int thread_number)
{
- // At some point we will select the specific implementation of
- // Workqueue_runner to use based on the command line options.
- this->runner_ = new Workqueue_runner_single(this);
-}
+ Task* t;
+ Task_locker tl;
-Workqueue::~Workqueue()
-{
- assert(this->tasks_.empty());
- assert(this->completed_.empty());
- assert(this->running_ == 0);
-}
+ {
+ Hold_lock hl(this->lock_);
-void
-Workqueue::queue(Task* t)
-{
- Hold_lock hl(this->tasks_lock_);
- this->tasks_.push_back(t);
-}
+ // Find a runnable task.
+ t = this->find_runnable_or_wait(thread_number);
-// Clear the list of completed tasks. Return whether we cleared
-// anything. The completed_lock_ must be held when this is called.
+ if (t == NULL)
+ return false;
-bool
-Workqueue::clear_completed()
-{
- if (this->completed_.empty())
- return false;
- do
- {
- delete this->completed_.front();
- this->completed_.pop_front();
- }
- while (!this->completed_.empty());
- return true;
-}
+ // Get the locks for the task. This must be called while we are
+ // still holding the Workqueue lock.
+ t->locks(&tl);
-// Find a runnable task in TASKS, which is non-empty. Return NULL if
-// none could be found. The tasks_lock_ must be held when this is
-// called. Sets ALL_BLOCKED if all non-runnable tasks are waiting on
-// a blocker.
+ ++this->running_;
+ }
-Task*
-Workqueue::find_runnable(Task_list& tasks, bool* all_blocked)
-{
- Task* tlast = tasks.back();
- *all_blocked = true;
- while (true)
+ while (t != NULL)
{
- Task* t = tasks.front();
- tasks.pop_front();
+ gold_debug(DEBUG_TASK, "%3d running task %s", thread_number,
+ t->name().c_str());
- Task::Is_runnable_type is_runnable = t->is_runnable(this);
- if (is_runnable == Task::IS_RUNNABLE)
- return t;
+ Timer timer;
+ if (is_debugging_enabled(DEBUG_TASK))
+ timer.start();
- if (is_runnable != Task::IS_BLOCKED)
- *all_blocked = false;
+ t->run(this);
- tasks.push_back(t);
+ if (is_debugging_enabled(DEBUG_TASK))
+ {
+ Timer::TimeStats elapsed = timer.get_elapsed_time();
- if (t == tlast)
- {
- // We couldn't find any runnable task. If there are any
- // completed tasks, free their locks and try again.
+ 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)
{
- Hold_lock hl2(this->completed_lock_);
-
- if (!this->clear_completed())
- {
- // There had better be some tasks running, or we will
- // never find a runnable task.
- assert(this->running_ > 0);
-
- // We couldn't find any runnable tasks, and we
- // couldn't release any locks.
- return NULL;
- }
+ tl.clear();
+ next->locks(&tl);
+
+ ++this->running_;
}
+ }
- // We're going around again, so recompute ALL_BLOCKED.
- *all_blocked = true;
- }
+ // We are done with this task.
+ delete t;
+
+ t = next;
}
+
+ return true;
}
-// Process all the tasks on the workqueue. This is the main loop in
-// the linker. Note that as we process tasks, new tasks will be
-// added.
+// Handle the return value of release_locks, and get tasks ready to
+// run.
-void
-Workqueue::process()
+// 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)
{
- while (true)
+ Task_token* token = t->is_runnable();
+
+ if (token != NULL)
{
- Task* t;
- bool empty;
- bool all_blocked;
+ token->add_waiting(t);
+ ++this->waiting_;
+ return false;
+ }
- {
- Hold_lock hl(this->tasks_lock_);
+ 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 (this->tasks_.empty())
- {
- t = NULL;
- empty = true;
- all_blocked = false;
- }
- else
- {
- t = this->find_runnable(this->tasks_, &all_blocked);
- empty = false;
- }
- }
+ 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();
+}
- // If T != NULL, it is a task we can run.
- // If T == NULL && empty, then there are no tasks waiting to
- // be run at this level.
- // If T == NULL && !empty, then there tasks waiting to be
- // run at this level, but they are waiting for something to
- // unlock.
+// 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.
- if (t != NULL)
- this->run(t);
- else if (!empty)
+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())
{
- {
- Hold_lock hl(this->completed_lock_);
-
- // There must be something for us to wait for, or we won't
- // be able to make progress.
- assert(this->running_ > 0 || !this->completed_.empty());
-
- if (all_blocked)
- {
- this->cleared_blockers_ = 0;
- this->clear_completed();
- while (this->cleared_blockers_ == 0)
- {
- assert(this->running_ > 0);
- this->completed_condvar_.wait();
- this->clear_completed();
- }
- }
- else
- {
- if (this->running_ > 0)
- {
- // Wait for a task to finish.
- this->completed_condvar_.wait();
- }
- this->clear_completed();
- }
- }
+ 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
{
- {
- Hold_lock hl(this->completed_lock_);
-
- // If there are no running tasks, then we are done.
- if (this->running_ == 0)
- {
- this->clear_completed();
- return;
- }
-
- // Wait for a task to finish. Then we have to loop around
- // again in case it added any new tasks before finishing.
- this->completed_condvar_.wait();
- this->clear_completed();
- }
+ 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;
}
-// Run a task. This is always called in the main thread.
+// 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::run(Task* t)
+Workqueue::process(int thread_number)
{
- ++this->running_;
- this->runner_->run(t, t->locks(this));
+ while (this->find_and_run_task(thread_number))
+ ;
}
-// This is called when a task is completed to put the locks on the
-// list to be released. We use a list because we only want the locks
-// to be released in the main thread.
+// Set the number of threads to use for the workqueue, if we are using
+// threads.
void
-Workqueue::completed(Task* t, Task_locker* tl)
+Workqueue::set_thread_count(int threads)
{
- {
- Hold_lock hl(this->completed_lock_);
- assert(this->running_ > 0);
- --this->running_;
- this->completed_.push_back(tl);
- this->completed_condvar_.signal();
- }
- delete t;
+ Hold_lock hl(this->lock_);
+
+ this->threader_->set_thread_count(threads);
+ // Wake up all the threads, since something has changed.
+ this->condvar_.broadcast();
}
-// This is called when the last task for a blocker has completed.
-// This is always called in the main thread.
+// Add a new blocker to an existing Task_token.
void
-Workqueue::cleared_blocker()
+Workqueue::add_blocker(Task_token* token)
{
- ++this->cleared_blockers_;
+ Hold_lock hl(this->lock_);
+ token->add_blocker();
}
} // End namespace gold.
projects / deliverable / binutils-gdb.git / blobdiff