| 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) |