gold/token.h

   1 // token.h -- lock tokens for gold   -*- C++ -*-
   2
   3 // Copyright 2006, 2007, 2008, 2010 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   // Add some number of blockers to the token.
 148   void
 149   add_blockers(int c)
 150   {
 151     gold_assert(this->is_blocker_);
 152     this->blockers_ += c;
 153     this->writer_ = NULL;
 154   }
 155
 156   // Remove a blocker from the token.  Returns true if block count
 157   // drops to zero.
 158   bool
 159   remove_blocker()
 160   {
 161     gold_assert(this->is_blocker_ && this->blockers_ > 0);
 162     --this->blockers_;
 163     this->writer_ = NULL;
 164     return this->blockers_ == 0;
 165   }
 166
 167   // Is the token currently blocked?
 168   bool
 169   is_blocked() const
 170   {
 171     gold_assert(this->is_blocker_);
 172     return this->blockers_ > 0;
 173   }
 174
 175   // Both blocker and write lock tokens use these methods.
 176
 177   // Add T to the list of tasks waiting for this token to be released.
 178   void
 179   add_waiting(Task* t)
 180   { this->waiting_.push_back(t); }
 181
 182   // Add T to the front of the list of tasks waiting for this token to
 183   // be released.
 184   void
 185   add_waiting_front(Task* t)
 186   { this->waiting_.push_front(t); }
 187
 188   // Remove the first Task waiting for this token to be released, and
 189   // return it.  Return NULL if no Tasks are waiting.
 190   Task*
 191   remove_first_waiting()
 192   { return this->waiting_.pop_front(); }
 193
 194  private:
 195   // It makes no sense to copy these.
 196   Task_token(const Task_token&);
 197   Task_token& operator=(const Task_token&);
 198
 199   // Whether this is a blocker token.
 200   bool is_blocker_;
 201   // The number of blockers.
 202   int blockers_;
 203   // The single writer.
 204   const Task* writer_;
 205   // The list of Tasks waiting for this token to be released.
 206   Task_list waiting_;
 207 };
 208
 209 // In order to support tokens more reliably, we provide objects which
 210 // handle them using RAII.
 211
 212 // RAII class to get a write lock on a token.  This requires
 213 // specifying the task which is doing the lock.
 214
 215 class Task_write_token
 216 {
 217  public:
 218   Task_write_token(Task_token* token, const Task* task)
 219     : token_(token), task_(task)
 220   { this->token_->add_writer(this->task_); }
 221
 222   ~Task_write_token()
 223   { this->token_->remove_writer(this->task_); }
 224
 225  private:
 226   Task_write_token(const Task_write_token&);
 227   Task_write_token& operator=(const Task_write_token&);
 228
 229   Task_token* token_;
 230   const Task* task_;
 231 };
 232
 233 // RAII class for a blocker.
 234
 235 class Task_block_token
 236 {
 237  public:
 238   // The blocker count must be incremented when the task is created.
 239   // This object is created when the task is run, so we don't do
 240   // anything in the constructor.
 241   Task_block_token(Task_token* token)
 242     : token_(token)
 243   { gold_assert(this->token_->is_blocked()); }
 244
 245   ~Task_block_token()
 246   { this->token_->remove_blocker(); }
 247
 248  private:
 249   Task_block_token(const Task_block_token&);
 250   Task_block_token& operator=(const Task_block_token&);
 251
 252   Task_token* token_;
 253 };
 254
 255 // An object which implements an RAII lock for any object which
 256 // supports lock and unlock methods.
 257
 258 template<typename Obj>
 259 class Task_lock_obj
 260 {
 261  public:
 262   Task_lock_obj(const Task* task, Obj* obj)
 263     : task_(task), obj_(obj)
 264   { this->obj_->lock(task); }
 265
 266   ~Task_lock_obj()
 267   { this->obj_->unlock(this->task_); }
 268
 269  private:
 270   Task_lock_obj(const Task_lock_obj&);
 271   Task_lock_obj& operator=(const Task_lock_obj&);
 272
 273   const Task* task_;
 274   Obj* obj_;
 275 };
 276
 277 // A class which holds the set of Task_tokens which must be locked for
 278 // a Task.  No Task requires more than four Task_tokens, so we set
 279 // that as a limit.
 280
 281 class Task_locker
 282 {
 283  public:
 284   static const int max_task_count = 4;
 285
 286   Task_locker()
 287     : count_(0)
 288   { }
 289
 290   ~Task_locker()
 291   { }
 292
 293   // Clear the locker.
 294   void
 295   clear()
 296   { this->count_ = 0; }
 297
 298   // Add a token to the locker.
 299   void
 300   add(Task* t, Task_token* token)
 301   {
 302     gold_assert(this->count_ < max_task_count);
 303     this->tokens_[this->count_] = token;
 304     ++this->count_;
 305     // A blocker will have been incremented when the task is created.
 306     // A writer we need to lock now.
 307     if (!token->is_blocker())
 308       token->add_writer(t);
 309   }
 310
 311   // Iterate over the tokens.
 312
 313   typedef Task_token** iterator;
 314
 315   iterator
 316   begin()
 317   { return &this->tokens_[0]; }
 318
 319   iterator
 320   end()
 321   { return &this->tokens_[this->count_]; }
 322
 323  private:
 324   Task_locker(const Task_locker&);
 325   Task_locker& operator=(const Task_locker&);
 326
 327   // The number of tokens.
 328   int count_;
 329   // The tokens.
 330   Task_token* tokens_[max_task_count];
 331 };
 332
 333 } // End namespace gold.
 334
 335 #endif // !defined(GOLD_TOKEN_H)