Initial CVS checkin of gold

1 files changed, 391 insertions, 0 deletions

diff --git a/gold/workqueue.cc b/gold/workqueue.cc
new file mode 100644
index 0000000..860484e
--- /dev/null
+++ b/gold/workqueue.cc
@@ -0,0 +1,391 @@
+// workqueue.cc -- the workqueue for gold
+
+#include "gold.h"
+#include "workqueue.h"
+
+namespace gold
+{
+
+// Task_token methods.
+
+Task_token::Task_token()
+  : is_blocker_(false), readers_(0), writer_(NULL)
+{
+}
+
+Task_token::~Task_token()
+{
+  assert(this->readers_ == 0 && this->writer_ == NULL);
+}
+
+bool
+Task_token::is_readable() const
+{
+  assert(!this->is_blocker_);
+  return this->writer_ == NULL;
+}
+
+void
+Task_token::add_reader()
+{
+  assert(!this->is_blocker_);
+  assert(this->is_readable());
+  ++this->readers_;
+}
+
+void
+Task_token::remove_reader()
+{
+  assert(!this->is_blocker_);
+  assert(this->readers_ > 0);
+  --this->readers_;
+}
+
+bool
+Task_token::is_writable() const
+{
+  assert(!this->is_blocker_);
+  return this->writer_ == NULL && this->readers_ == 0;
+}
+
+void
+Task_token::add_writer(const Task* t)
+{
+  assert(!this->is_blocker_);
+  assert(this->is_writable());
+  this->writer_ = t;
+}
+
+void
+Task_token::remove_writer(const Task* t)
+{
+  assert(!this->is_blocker_);
+  assert(this->writer_ == t);
+  this->writer_ = NULL;
+}
+
+bool
+Task_token::has_write_lock(const Task* t)
+{
+  assert(!this->is_blocker_);
+  return this->writer_ == t;
+}
+
+// For blockers, we just use the readers_ field.
+
+void
+Task_token::add_blocker()
+{
+  if (this->readers_ == 0 && this->writer_ == NULL)
+    this->is_blocker_ = true;
+  else
+    assert(this->is_blocker_);
+  ++this->readers_;
+}
+
+bool
+Task_token::remove_blocker()
+{
+  assert(this->is_blocker_ && this->readers_ > 0);
+  --this->readers_;
+  return this->readers_ == 0;
+}
+
+bool
+Task_token::is_blocked() const
+{
+  assert(this->is_blocker_ || (this->readers_ == 0 && this->writer_ == NULL));
+  return this->readers_ > 0;
+}
+
+// The Task_block_token class.
+
+Task_block_token::Task_block_token(Task_token& token, Workqueue* workqueue)
+  : token_(token), workqueue_(workqueue)
+{
+  // 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_block_token::~Task_block_token()
+{
+  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();
+    }
+}
+
+// The Workqueue_runner abstract class.
+
+class Workqueue_runner
+{
+ public:
+  Workqueue_runner(Workqueue* workqueue)
+    : workqueue_(workqueue)
+  { }
+  virtual ~Workqueue_runner()
+  { }
+
+  // Run a task.  This is always called in the main thread.
+  virtual void run(Task*, Task_locker*) = 0;
+
+ protected:
+  // This is called by an implementation when a task is completed.
+  void completed(Task* t, Task_locker* tl)
+  { this->workqueue_->completed(t, tl); }
+
+  Workqueue* get_workqueue() const
+  { return this->workqueue_; }
+
+ private:
+  Workqueue* workqueue_;
+};
+
+// The simple single-threaded implementation of Workqueue_runner.
+
+class Workqueue_runner_single : public Workqueue_runner
+{
+ public:
+  Workqueue_runner_single(Workqueue* workqueue)
+    : Workqueue_runner(workqueue)
+  { }
+  ~Workqueue_runner_single()
+  { }
+
+  void run(Task*, Task_locker*);
+};
+
+void
+Workqueue_runner_single::run(Task* t, Task_locker* tl)
+{
+  t->run(this->get_workqueue());
+  this->completed(t, tl);
+}
+
+// Workqueue methods.
+
+Workqueue::Workqueue(const General_options&)
+  : tasks_lock_(),
+    tasks_(),
+    completed_lock_(),
+    completed_(),
+    running_(0),
+    completed_condvar_(this->completed_lock_),
+    cleared_blockers_(0)
+{
+  // 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);
+}
+
+Workqueue::~Workqueue()
+{
+  assert(this->tasks_.empty());
+  assert(this->completed_.empty());
+  assert(this->running_ == 0);
+}
+
+void
+Workqueue::queue(Task* t)
+{
+  Hold_lock hl(this->tasks_lock_);
+  this->tasks_.push_back(t);
+}
+
+// Clear the list of completed tasks.  Return whether we cleared
+// anything.  The completed_lock_ must be held when this is called.
+
+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;
+}
+
+// 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.
+
+Task*
+Workqueue::find_runnable(Task_list& tasks, bool* all_blocked)
+{
+  Task* tlast = tasks.back();
+  *all_blocked = true;
+  while (true)
+    {
+      Task* t = tasks.front();
+      tasks.pop_front();
+
+      Task::Is_runnable_type is_runnable = t->is_runnable(this);
+      if (is_runnable == Task::IS_RUNNABLE)
+	return t;
+
+      if (is_runnable != Task::IS_BLOCKED)
+	*all_blocked = false;
+
+      tasks.push_back(t);
+
+      if (t == tlast)
+	{
+	  // We couldn't find any runnable task.  If there are any
+	  // completed tasks, free their locks and try again.
+
+	  {
+	    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;
+	      }
+	  }
+
+	  // We're going around again, so recompute ALL_BLOCKED.
+	  *all_blocked = 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.
+
+void
+Workqueue::process()
+{
+  while (true)
+    {
+      Task* t;
+      bool empty;
+      bool all_blocked;
+
+      {
+	Hold_lock hl(this->tasks_lock_);
+
+	if (this->tasks_.empty())
+	  {
+	    t = NULL;
+	    empty = true;
+	    all_blocked = false;
+	  }
+	else
+	  {
+	    t = this->find_runnable(this->tasks_, &all_blocked);
+	    empty = false;
+	  }
+      }
+
+      // 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.
+
+      if (t != NULL)
+	this->run(t);
+      else if (!empty)
+	{
+	  {
+	    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();
+	      }
+	  }
+	}
+      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();
+	  }
+	}
+    }
+}
+
+// Run a task.  This is always called in the main thread.
+
+void
+Workqueue::run(Task* t)
+{
+  ++this->running_;
+  this->runner_->run(t, t->locks(this));
+}
+
+// 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.
+
+void
+Workqueue::completed(Task* t, Task_locker* tl)
+{
+  {
+    Hold_lock hl(this->completed_lock_);
+    assert(this->running_ > 0);
+    --this->running_;
+    this->completed_.push_back(tl);
+    this->completed_condvar_.signal();
+  }
+  delete t;
+}
+
+// This is called when the last task for a blocker has completed.
+// This is always called in the main thread.
+
+void
+Workqueue::cleared_blocker()
+{
+  ++this->cleared_blockers_;
+}
+
+} // End namespace gold.