Rewrite workqueue. This version eliminates the master thread, and

reduces the amount of locking required to find a new thread to run.

1 files changed, 316 insertions, 0 deletions

diff --git a/gold/token.h b/gold/token.h
new file mode 100644
index 0000000..49a7d51
--- /dev/null
+++ b/gold/token.h
@@ -0,0 +1,316 @@
+// token.h -- lock tokens for gold   -*- C++ -*-
+
+// Copyright 2006, 2007 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.
+
+#ifndef GOLD_TOKEN_H
+#define GOLD_TOKEN_H
+
+namespace gold
+{
+
+class Condvar;
+class Task;
+
+// A list of Tasks, managed through the next_locked_ field in the
+// class Task.  We define this class here because we need it in
+// Task_token.
+
+class Task_list
+{
+ public:
+  Task_list()
+    : head_(NULL), tail_(NULL)
+  { }
+
+  ~Task_list()
+  { gold_assert(this->head_ == NULL && this->tail_ == NULL); }
+
+  // Return whether the list is empty.
+  bool
+  empty() const
+  { return this->head_ == NULL; }
+
+  // Add T to the end of the list.
+  void
+  push_back(Task* t);
+
+  // Remove the first Task on the list and return it.  Return NULL if
+  // the list is empty.
+  Task*
+  pop_front();
+
+ private:
+  // The start of the list.  NULL if the list is empty.
+  Task* head_;
+  // The end of the list.  NULL if the list is empty.
+  Task* tail_;
+};
+
+// We support two basic types of locks, which are both implemented
+// using the single class Task_token.
+
+// A write lock may be held by a single Task at a time.  This is used
+// to control access to a single shared resource such as an Object.
+
+// A blocker is used to indicate that a Task A must be run after some
+// set of Tasks B.  For each of the Tasks B, we increment the blocker
+// when the Task is created, and decrement it when the Task is
+// completed.  When the count goes to 0, the task A is ready to run.
+
+// There are no shared read locks.  We always read and write objects
+// in predictable patterns.  The purpose of the locks is to permit
+// some flexibility for the threading system, for cases where the
+// execution order does not matter.
+
+// These tokens are only manipulated when the workqueue lock is held
+// or when they are first created.  They do not require any locking
+// themselves.
+
+class Task_token
+{
+ public:
+  Task_token(bool is_blocker)
+    : is_blocker_(is_blocker), blockers_(0), writer_(NULL), waiting_()
+  { }
+
+  ~Task_token()
+  {
+    gold_assert(this->blockers_ == 0);
+    gold_assert(this->writer_ == NULL);
+  }
+
+  // Return whether this is a blocker.
+  bool
+  is_blocker() const
+  { return this->is_blocker_; }
+
+  // A write lock token uses these methods.
+
+  // Is the token writable?
+  bool
+  is_writable() const
+  {
+    gold_assert(!this->is_blocker_);
+    return this->writer_ == NULL;
+  }
+
+  // Add the task as the token's writer (there may only be one
+  // writer).
+  void
+  add_writer(const Task* t)
+  {
+    gold_assert(!this->is_blocker_ && this->writer_ == NULL);
+    this->writer_ = t;
+  }
+
+  // Remove the task as the token's writer.
+  void
+  remove_writer(const Task* t)
+  {
+    gold_assert(!this->is_blocker_ && this->writer_ == t);
+    this->writer_ = NULL;
+  }
+
+  // A blocker token uses these methods.
+
+  // Add a blocker to the token.
+  void
+  add_blocker()
+  {
+    gold_assert(this->is_blocker_);
+    ++this->blockers_;
+    this->writer_ = NULL;
+  }
+
+  // Remove a blocker from the token.  Returns true if block count
+  // drops to zero.
+  bool
+  remove_blocker()
+  {
+    gold_assert(this->is_blocker_ && this->blockers_ > 0);
+    --this->blockers_;
+    this->writer_ = NULL;
+    return this->blockers_ == 0;
+  }
+
+  // Is the token currently blocked?
+  bool
+  is_blocked() const
+  {
+    gold_assert(this->is_blocker_);
+    return this->blockers_ > 0;
+  }
+
+  // Both blocker and write lock tokens use these methods.
+
+  // Add T to the list of tasks waiting for this token to be released.
+  void
+  add_waiting(Task* t)
+  { this->waiting_.push_back(t); }
+
+  // Remove the first Task waiting for this token to be released, and
+  // return it.  Return NULL if no Tasks are waiting.
+  Task*
+  remove_first_waiting()
+  { return this->waiting_.pop_front(); }
+
+ private:
+  // It makes no sense to copy these.
+  Task_token(const Task_token&);
+  Task_token& operator=(const Task_token&);
+
+  // Whether this is a blocker token.
+  bool is_blocker_;
+  // The number of blockers.
+  int blockers_;
+  // The single writer.
+  const Task* writer_;
+  // The list of Tasks waiting for this token to be released.
+  Task_list waiting_;
+};
+
+// In order to support tokens more reliably, we provide objects which
+// handle them using RAII.
+
+// RAII class to get a write lock on a token.  This requires
+// specifying the task which is doing the lock.
+
+class Task_write_token
+{
+ public:
+  Task_write_token(Task_token* token, const Task* task)
+    : token_(token), task_(task)
+  { this->token_->add_writer(this->task_); }
+
+  ~Task_write_token()
+  { this->token_->remove_writer(this->task_); }
+
+ private:
+  Task_write_token(const Task_write_token&);
+  Task_write_token& operator=(const Task_write_token&);
+
+  Task_token* token_;
+  const Task* task_;
+};
+
+// RAII class for a blocker.
+
+class Task_block_token
+{
+ public:
+  // The blocker count must be incremented when the task is created.
+  // This object is created when the task is run, so we don't do
+  // anything in the constructor.
+  Task_block_token(Task_token* token)
+    : token_(token)
+  { gold_assert(this->token_->is_blocked()); }
+
+  ~Task_block_token()
+  { this->token_->remove_blocker(); }
+
+ private:
+  Task_block_token(const Task_block_token&);
+  Task_block_token& operator=(const Task_block_token&);
+
+  Task_token* token_;
+};
+
+// An object which implements an RAII lock for any object which
+// supports lock and unlock methods.
+
+template<typename Obj>
+class Task_lock_obj
+{
+ public:
+  Task_lock_obj(const Task* task, Obj* obj)
+    : task_(task), obj_(obj)
+  { this->obj_->lock(task); }
+
+  ~Task_lock_obj()
+  { this->obj_->unlock(this->task_); }
+
+ private:
+  Task_lock_obj(const Task_lock_obj&);
+  Task_lock_obj& operator=(const Task_lock_obj&);
+
+  const Task* task_;
+  Obj* obj_;
+};
+
+// A class which holds the set of Task_tokens which must be locked for
+// a Task.  No Task requires more than four Task_tokens, so we set
+// that as a limit.
+
+class Task_locker
+{
+ public:
+  static const int max_task_count = 4;
+
+  Task_locker()
+    : count_(0)
+  { }
+
+  ~Task_locker()
+  { }
+
+  // Clear the locker.
+  void
+  clear()
+  { this->count_ = 0; }
+
+  // Add a token to the locker.
+  void
+  add(Task* t, Task_token* token)
+  {
+    gold_assert(this->count_ < max_task_count);
+    this->tokens_[this->count_] = token;
+    ++this->count_;
+    // A blocker will have been incremented when the task is created.
+    // A writer we need to lock now.
+    if (!token->is_blocker())
+      token->add_writer(t);
+  }
+
+  // Iterate over the tokens.
+
+  typedef Task_token** iterator;
+
+  iterator
+  begin()
+  { return &this->tokens_[0]; }
+
+  iterator
+  end()
+  { return &this->tokens_[this->count_]; }
+
+ private:
+  Task_locker(const Task_locker&);
+  Task_locker& operator=(const Task_locker&);
+
+  // The number of tokens.
+  int count_;
+  // The tokens.
+  Task_token* tokens_[max_task_count];
+};
+
+} // End namespace gold.
+
+#endif // !defined(GOLD_TOKEN_H)