gold/token.h

   1 // token.h -- lock tokens for gold   -*- C++ -*-
   2
   3 // Copyright 2006, 2007 Free Software Foundation, Inc.
   4 // Written by Ian Lance Taylor <iant@google.com>.
   5
   6 // This file is part of gold.
   7
   8 // This program is free software; you can redistribute it and/or modify
   9 // it under the terms of the GNU General Public License as published by
  10 // the Free Software Foundation; either version 3 of the License, or
  11 // (at your option) any later version.
  12
  13 // This program is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // You should have received a copy of the GNU General Public License
  19 // along with this program; if not, write to the Free Software
  20 // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
  21 // MA 02110-1301, USA.
  22
  23 #ifndef GOLD_TOKEN_H
  24 #define GOLD_TOKEN_H
  25
  26 namespace gold
  27 {
  28
  29 class Condvar;
  30 class Task;
  31
  32 // A list of Tasks, managed through the next_locked_ field in the
  33 // class Task.  We define this class here because we need it in
  34 // Task_token.
  35
  36 class Task_list
  37 {
  38  public:
  39   Task_list()
  40     : head_(NULL), tail_(NULL)
  41   { }
  42
  43   ~Task_list()
  44   { gold_assert(this->head_ == NULL && this->tail_ == NULL); }
  45
  46   // Return whether the list is empty.
  47   bool
  48   empty() const
  49   { return this->head_ == NULL; }
  50
  51   // Add T to the end of the list.
  52   void
  53   push_back(Task* t);
  54
  55   // Remove the first Task on the list and return it.  Return NULL if
  56   // the list is empty.
  57   Task*
  58   pop_front();
  59
  60  private:
  61   // The start of the list.  NULL if the list is empty.
  62   Task* head_;
  63   // The end of the list.  NULL if the list is empty.
  64   Task* tail_;
  65 };
  66
  67 // We support two basic types of locks, which are both implemented
  68 // using the single class Task_token.
  69
  70 // A write lock may be held by a single Task at a time.  This is used
  71 // to control access to a single shared resource such as an Object.
  72
  73 // A blocker is used to indicate that a Task A must be run after some
  74 // set of Tasks B.  For each of the Tasks B, we increment the blocker
  75 // when the Task is created, and decrement it when the Task is
  76 // completed.  When the count goes to 0, the task A is ready to run.
  77
  78 // There are no shared read locks.  We always read and write objects
  79 // in predictable patterns.  The purpose of the locks is to permit
  80 // some flexibility for the threading system, for cases where the
  81 // execution order does not matter.
  82
  83 // These tokens are only manipulated when the workqueue lock is held
  84 // or when they are first created.  They do not require any locking
  85 // themselves.
  86
  87 class Task_token
  88 {
  89  public:
  90   Task_token(bool is_blocker)
  91     : is_blocker_(is_blocker), blockers_(0), writer_(NULL), waiting_()
  92   { }
  93
  94   ~Task_token()
  95   {
  96     gold_assert(this->blockers_ == 0);
  97     gold_assert(this->writer_ == NULL);
  98   }
  99
 100   // Return whether this is a blocker.
 101   bool
 102   is_blocker() const
 103   { return this->is_blocker_; }
 104
 105   // A write lock token uses these methods.
 106
 107   // Is the token writable?
 108   bool
 109   is_writable() const
 110   {
 111     gold_assert(!this->is_blocker_);
 112     return this->writer_ == NULL;
 113   }
 114
 115   // Add the task as the token's writer (there may only be one
 116   // writer).
 117   void
 118   add_writer(const Task* t)
 119   {
 120     gold_assert(!this->is_blocker_ && this->writer_ == NULL);
 121     this->writer_ = t;
 122   }
 123
 124   // Remove the task as the token's writer.
 125   void
 126   remove_writer(const Task* t)
 127   {
 128     gold_assert(!this->is_blocker_ && this->writer_ == t);
 129     this->writer_ = NULL;
 130   }
 131
 132   // A blocker token uses these methods.
 133
 134   // Add a blocker to the token.
 135   void
 136   add_blocker()
 137   {
 138     gold_assert(this->is_blocker_);
 139     ++this->blockers_;
 140     this->writer_ = NULL;
 141   }
 142
 143   // Remove a blocker from the token.  Returns true if block count
 144   // drops to zero.
 145   bool
 146   remove_blocker()
 147   {
 148     gold_assert(this->is_blocker_ && this->blockers_ > 0);
 149     --this->blockers_;
 150     this->writer_ = NULL;
 151     return this->blockers_ == 0;
 152   }
 153
 154   // Is the token currently blocked?
 155   bool
 156   is_blocked() const
 157   {
 158     gold_assert(this->is_blocker_);
 159     return this->blockers_ > 0;
 160   }
 161
 162   // Both blocker and write lock tokens use these methods.
 163
 164   // Add T to the list of tasks waiting for this token to be released.
 165   void
 166   add_waiting(Task* t)
 167   { this->waiting_.push_back(t); }
 168
 169   // Remove the first Task waiting for this token to be released, and
 170   // return it.  Return NULL if no Tasks are waiting.
 171   Task*
 172   remove_first_waiting()
 173   { return this->waiting_.pop_front(); }
 174
 175  private:
 176   // It makes no sense to copy these.
 177   Task_token(const Task_token&);
 178   Task_token& operator=(const Task_token&);
 179
 180   // Whether this is a blocker token.
 181   bool is_blocker_;
 182   // The number of blockers.
 183   int blockers_;
 184   // The single writer.
 185   const Task* writer_;
 186   // The list of Tasks waiting for this token to be released.
 187   Task_list waiting_;
 188 };
 189
 190 // In order to support tokens more reliably, we provide objects which
 191 // handle them using RAII.
 192
 193 // RAII class to get a write lock on a token.  This requires
 194 // specifying the task which is doing the lock.
 195
 196 class Task_write_token
 197 {
 198  public:
 199   Task_write_token(Task_token* token, const Task* task)
 200     : token_(token), task_(task)
 201   { this->token_->add_writer(this->task_); }
 202
 203   ~Task_write_token()
 204   { this->token_->remove_writer(this->task_); }
 205
 206  private:
 207   Task_write_token(const Task_write_token&);
 208   Task_write_token& operator=(const Task_write_token&);
 209
 210   Task_token* token_;
 211   const Task* task_;
 212 };
 213
 214 // RAII class for a blocker.
 215
 216 class Task_block_token
 217 {
 218  public:
 219   // The blocker count must be incremented when the task is created.
 220   // This object is created when the task is run, so we don't do
 221   // anything in the constructor.
 222   Task_block_token(Task_token* token)
 223     : token_(token)
 224   { gold_assert(this->token_->is_blocked()); }
 225
 226   ~Task_block_token()
 227   { this->token_->remove_blocker(); }
 228
 229  private:
 230   Task_block_token(const Task_block_token&);
 231   Task_block_token& operator=(const Task_block_token&);
 232
 233   Task_token* token_;
 234 };
 235
 236 // An object which implements an RAII lock for any object which
 237 // supports lock and unlock methods.
 238
 239 template<typename Obj>
 240 class Task_lock_obj
 241 {
 242  public:
 243   Task_lock_obj(const Task* task, Obj* obj)
 244     : task_(task), obj_(obj)
 245   { this->obj_->lock(task); }
 246
 247   ~Task_lock_obj()
 248   { this->obj_->unlock(this->task_); }
 249
 250  private:
 251   Task_lock_obj(const Task_lock_obj&);
 252   Task_lock_obj& operator=(const Task_lock_obj&);
 253
 254   const Task* task_;
 255   Obj* obj_;
 256 };
 257
 258 // A class which holds the set of Task_tokens which must be locked for
 259 // a Task.  No Task requires more than four Task_tokens, so we set
 260 // that as a limit.
 261
 262 class Task_locker
 263 {
 264  public:
 265   static const int max_task_count = 4;
 266
 267   Task_locker()
 268     : count_(0)
 269   { }
 270
 271   ~Task_locker()
 272   { }
 273
 274   // Clear the locker.
 275   void
 276   clear()
 277   { this->count_ = 0; }
 278
 279   // Add a token to the locker.
 280   void
 281   add(Task* t, Task_token* token)
 282   {
 283     gold_assert(this->count_ < max_task_count);
 284     this->tokens_[this->count_] = token;
 285     ++this->count_;
 286     // A blocker will have been incremented when the task is created.
 287     // A writer we need to lock now.
 288     if (!token->is_blocker())
 289       token->add_writer(t);
 290   }
 291
 292   // Iterate over the tokens.
 293
 294   typedef Task_token** iterator;
 295
 296   iterator
 297   begin()
 298   { return &this->tokens_[0]; }
 299
 300   iterator
 301   end()
 302   { return &this->tokens_[this->count_]; }
 303
 304  private:
 305   Task_locker(const Task_locker&);
 306   Task_locker& operator=(const Task_locker&);
 307
 308   // The number of tokens.
 309   int count_;
 310   // The tokens.
 311   Task_token* tokens_[max_task_count];
 312 };
 313
 314 } // End namespace gold.
 315
 316 #endif // !defined(GOLD_TOKEN_H)