Home | History | Annotate | Download | only in gold
      1 // token.h -- lock tokens for gold   -*- C++ -*-
      2 
      3 // Copyright (C) 2006-2014 Free Software Foundation, Inc.
      4 // Written by Ian Lance Taylor <iant (at) 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)
    336