gold/token.h

   1 // token.h -- lock tokens for gold   -*- C++ -*-
   2
   3 // Copyright 2006, 2007, 2008 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 head of the list.
  52   void
  53   push_front(Task* t);
  54
  55   // Add T to the end of the list.
  56   void
  57   push_back(Task* t);
  58
  59   // Remove the first Task on the list and return it.  Return NULL if
  60   // the list is empty.
  61   Task*
  62   pop_front();
  63
  64  private:
  65   // The start of the list.  NULL if the list is empty.
  66   Task* head_;
  67   // The end of the list.  NULL if the list is empty.
  68   Task* tail_;
  69 };
  70
  71 // We support two basic types of locks, which are both implemented
  72 // using the single class Task_token.
  73
  74 // A write lock may be held by a single Task at a time.  This is used
  75 // to control access to a single shared resource such as an Object.
  76
  77 // A blocker is used to indicate that a Task A must be run after some
  78 // set of Tasks B.  For each of the Tasks B, we increment the blocker
  79 // when the Task is created, and decrement it when the Task is
  80 // completed.  When the count goes to 0, the task A is ready to run.
  81
  82 // There are no shared read locks.  We always read and write objects
  83 // in predictable patterns.  The purpose of the locks is to permit
  84 // some flexibility for the threading system, for cases where the
  85 // execution order does not matter.
  86
  87 // These tokens are only manipulated when the workqueue lock is held
  88 // or when they are first created.  They do not require any locking
  89 // themselves.
  90
  91 class Task_token
  92 {
  93  public:
  94   Task_token(bool is_blocker)
  95     : is_blocker_(is_blocker), blockers_(0), writer_(NULL), waiting_()
  96   { }
  97
  98   ~Task_token()
  99   {
 100     gold_assert(this->blockers_ == 0);
 101     gold_assert(this->writer_ == NULL);
 102   }
 103
 104   // Return whether this is a blocker.
 105   bool
 106   is_blocker() const
 107   { return this->is_blocker_; }
 108
 109   // A write lock token uses these methods.
 110
 111   // Is the token writable?
 112   bool
 113   is_writable() const
 114   {
 115     gold_assert(!this->is_blocker_);
 116     return this->writer_ == NULL;
 117   }
 118
 119   // Add the task as the token's writer (there may only be one
 120   // writer).
 121   void
 122   add_writer(const Task* t)
 123   {
 124     gold_assert(!this->is_blocker_ && this->writer_ == NULL);
 125     this->writer_ = t;
 126   }
 127
 128   // Remove the task as the token's writer.
 129   void
 130   remove_writer(const Task* t)
 131   {
 132     gold_assert(!this->is_blocker_ && this->writer_ == t);
 133     this->writer_ = NULL;
 134   }
 135
 136   // A blocker token uses these methods.
 137
 138   // Add a blocker to the token.
 139   void
 140   add_blocker()
 141   {
 142     gold_assert(this->is_blocker_);
 143     ++this->blockers_;
 144     this->writer_ = NULL;
 145   }
 146
 147   // Remove a blocker from the token.  Returns true if block count
 148   // drops to zero.
 149   bool
 150   remove_blocker()
 151   {
 152     gold_assert(this->is_blocker_ && this->blockers_ > 0);
 153     --this->blockers_;
 154     this->writer_ = NULL;
 155     return this->blockers_ == 0;
 156   }
 157
 158   // Is the token currently blocked?
 159   bool
 160   is_blocked() const
 161   {
 162     gold_assert(this->is_blocker_);
 163     return this->blockers_ > 0;
 164   }
 165
 166   // Both blocker and write lock tokens use these methods.
 167
 168   // Add T to the list of tasks waiting for this token to be released.
 169   void
 170   add_waiting(Task* t)
 171   { this->waiting_.push_back(t); }
 172
 173   // Add T to the front of the list of tasks waiting for this token to
 174   // be released.
 175   void
 176   add_waiting_front(Task* t)
 177   { this->waiting_.push_front(t); }
 178
 179   // Remove the first Task waiting for this token to be released, and
 180   // return it.  Return NULL if no Tasks are waiting.
 181   Task*
 182   remove_first_waiting()
 183   { return this->waiting_.pop_front(); }
 184
 185  private:
 186   // It makes no sense to copy these.
 187   Task_token(const Task_token&);
 188   Task_token& operator=(const Task_token&);
 189
 190   // Whether this is a blocker token.
 191   bool is_blocker_;
 192   // The number of blockers.
 193   int blockers_;
 194   // The single writer.
 195   const Task* writer_;
 196   // The list of Tasks waiting for this token to be released.
 197   Task_list waiting_;
 198 };
 199
 200 // In order to support tokens more reliably, we provide objects which
 201 // handle them using RAII.
 202
 203 // RAII class to get a write lock on a token.  This requires
 204 // specifying the task which is doing the lock.
 205
 206 class Task_write_token
 207 {
 208  public:
 209   Task_write_token(Task_token* token, const Task* task)
 210     : token_(token), task_(task)
 211   { this->token_->add_writer(this->task_); }
 212
 213   ~Task_write_token()
 214   { this->token_->remove_writer(this->task_); }
 215
 216  private:
 217   Task_write_token(const Task_write_token&);
 218   Task_write_token& operator=(const Task_write_token&);
 219
 220   Task_token* token_;
 221   const Task* task_;
 222 };
 223
 224 // RAII class for a blocker.
 225
 226 class Task_block_token
 227 {
 228  public:
 229   // The blocker count must be incremented when the task is created.
 230   // This object is created when the task is run, so we don't do
 231   // anything in the constructor.
 232   Task_block_token(Task_token* token)
 233     : token_(token)
 234   { gold_assert(this->token_->is_blocked()); }
 235
 236   ~Task_block_token()
 237   { this->token_->remove_blocker(); }
 238
 239  private:
 240   Task_block_token(const Task_block_token&);
 241   Task_block_token& operator=(const Task_block_token&);
 242
 243   Task_token* token_;
 244 };
 245
 246 // An object which implements an RAII lock for any object which
 247 // supports lock and unlock methods.
 248
 249 template<typename Obj>
 250 class Task_lock_obj
 251 {
 252  public:
 253   Task_lock_obj(const Task* task, Obj* obj)
 254     : task_(task), obj_(obj)
 255   { this->obj_->lock(task); }
 256
 257   ~Task_lock_obj()
 258   { this->obj_->unlock(this->task_); }
 259
 260  private:
 261   Task_lock_obj(const Task_lock_obj&);
 262   Task_lock_obj& operator=(const Task_lock_obj&);
 263
 264   const Task* task_;
 265   Obj* obj_;
 266 };
 267
 268 // A class which holds the set of Task_tokens which must be locked for
 269 // a Task.  No Task requires more than four Task_tokens, so we set
 270 // that as a limit.
 271
 272 class Task_locker
 273 {
 274  public:
 275   static const int max_task_count = 4;
 276
 277   Task_locker()
 278     : count_(0)
 279   { }
 280
 281   ~Task_locker()
 282   { }
 283
 284   // Clear the locker.
 285   void
 286   clear()
 287   { this->count_ = 0; }
 288
 289   // Add a token to the locker.
 290   void
 291   add(Task* t, Task_token* token)
 292   {
 293     gold_assert(this->count_ < max_task_count);
 294     this->tokens_[this->count_] = token;
 295     ++this->count_;
 296     // A blocker will have been incremented when the task is created.
 297     // A writer we need to lock now.
 298     if (!token->is_blocker())
 299       token->add_writer(t);
 300   }
 301
 302   // Iterate over the tokens.
 303
 304   typedef Task_token** iterator;
 305
 306   iterator
 307   begin()
 308   { return &this->tokens_[0]; }
 309
 310   iterator
 311   end()
 312   { return &this->tokens_[this->count_]; }
 313
 314  private:
 315   Task_locker(const Task_locker&);
 316   Task_locker& operator=(const Task_locker&);
 317
 318   // The number of tokens.
 319   int count_;
 320   // The tokens.
 321   Task_token* tokens_[max_task_count];
 322 };
 323
 324 } // End namespace gold.
 325
 326 #endif // !defined(GOLD_TOKEN_H)