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