X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gold%2Fworkqueue.cc;h=b12f4a1221ac4a0101ac336e392c5f058db468bc;hb=2026dcfcc0c0e60efa968b889f010a10a93cfe09;hp=860484ebdc6282174f156790efbb990da726d754;hpb=bae7f79e03d6405f5ceec0e3e24671e6b30f29ed;p=binutils-gdb.git

diff --git a/gold/workqueue.cc b/gold/workqueue.cc
index 860484ebdc6..b12f4a1221a 100644
--- a/gold/workqueue.cc
+++ b/gold/workqueue.cc
@@ -1,391 +1,521 @@
 // workqueue.cc -- the workqueue for gold
 
+// Copyright (C) 2006-2022 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
 {
 
-// 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.