| // token.h -- lock tokens for gold -*- C++ -*- |
| |
| // Copyright (C) 2006-2024 Free Software Foundation, Inc. |
| // Written by Ian Lance Taylor <iant@google.com>. |
| |
| // This file is part of gold. |
| |
| // This program is free software; you can redistribute it and/or modify |
| // it under the terms of the GNU General Public License as published by |
| // the Free Software Foundation; either version 3 of the License, or |
| // (at your option) any later version. |
| |
| // This program is distributed in the hope that it will be useful, |
| // but WITHOUT ANY WARRANTY; without even the implied warranty of |
| // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| // GNU General Public License for more details. |
| |
| // You should have received a copy of the GNU General Public License |
| // along with this program; if not, write to the Free Software |
| // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, |
| // MA 02110-1301, USA. |
| |
| #ifndef GOLD_TOKEN_H |
| #define GOLD_TOKEN_H |
| |
| namespace gold |
| { |
| |
| class Condvar; |
| class Task; |
| |
| // A list of Tasks, managed through the next_locked_ field in the |
| // class Task. We define this class here because we need it in |
| // Task_token. |
| |
| class Task_list |
| { |
| public: |
| Task_list() |
| : head_(NULL), tail_(NULL) |
| { } |
| |
| ~Task_list() |
| { gold_assert(this->head_ == NULL && this->tail_ == NULL); } |
| |
| // Return whether the list is empty. |
| bool |
| empty() const |
| { return this->head_ == NULL; } |
| |
| // Add T to the head of the list. |
| void |
| push_front(Task* t); |
| |
| // Add T to the end of the list. |
| void |
| push_back(Task* t); |
| |
| // Remove the first Task on the list and return it. Return NULL if |
| // the list is empty. |
| Task* |
| pop_front(); |
| |
| private: |
| // The start of the list. NULL if the list is empty. |
| Task* head_; |
| // The end of the list. NULL if the list is empty. |
| Task* tail_; |
| }; |
| |
| // We support two basic types of locks, which are both implemented |
| // using the single class Task_token. |
| |
| // A write lock may be held by a single Task at a time. This is used |
| // to control access to a single shared resource such as an Object. |
| |
| // A blocker is used to indicate that a Task A must be run after some |
| // set of Tasks B. For each of the Tasks B, we increment the blocker |
| // when the Task is created, and decrement it when the Task is |
| // completed. When the count goes to 0, the task A is ready to run. |
| |
| // There are no shared read locks. We always read and write objects |
| // in predictable patterns. The purpose of the locks is to permit |
| // some flexibility for the threading system, for cases where the |
| // execution order does not matter. |
| |
| // These tokens are only manipulated when the workqueue lock is held |
| // or when they are first created. They do not require any locking |
| // themselves. |
| |
| class Task_token |
| { |
| public: |
| Task_token(bool is_blocker) |
| : is_blocker_(is_blocker), blockers_(0), writer_(NULL), waiting_() |
| { } |
| |
| ~Task_token() |
| { |
| gold_assert(this->blockers_ == 0); |
| gold_assert(this->writer_ == NULL); |
| } |
| |
| // Return whether this is a blocker. |
| bool |
| is_blocker() const |
| { return this->is_blocker_; } |
| |
| // A write lock token uses these methods. |
| |
| // Is the token writable? |
| bool |
| is_writable() const |
| { |
| gold_assert(!this->is_blocker_); |
| return this->writer_ == NULL; |
| } |
| |
| // Add the task as the token's writer (there may only be one |
| // writer). |
| void |
| add_writer(const Task* t) |
| { |
| gold_assert(!this->is_blocker_ && this->writer_ == NULL); |
| this->writer_ = t; |
| } |
| |
| // Remove the task as the token's writer. |
| void |
| remove_writer(const Task* t) |
| { |
| gold_assert(!this->is_blocker_ && this->writer_ == t); |
| this->writer_ = NULL; |
| } |
| |
| // A blocker token uses these methods. |
| |
| // Add a blocker to the token. |
| void |
| add_blocker() |
| { |
| gold_assert(this->is_blocker_); |
| ++this->blockers_; |
| this->writer_ = NULL; |
| } |
| |
| // Add some number of blockers to the token. |
| void |
| add_blockers(int c) |
| { |
| gold_assert(this->is_blocker_); |
| this->blockers_ += c; |
| this->writer_ = NULL; |
| } |
| |
| // Remove a blocker from the token. Returns true if block count |
| // drops to zero. |
| bool |
| remove_blocker() |
| { |
| gold_assert(this->is_blocker_ && this->blockers_ > 0); |
| --this->blockers_; |
| this->writer_ = NULL; |
| return this->blockers_ == 0; |
| } |
| |
| // Is the token currently blocked? |
| bool |
| is_blocked() const |
| { |
| gold_assert(this->is_blocker_); |
| return this->blockers_ > 0; |
| } |
| |
| // Both blocker and write lock tokens use these methods. |
| |
| // Add T to the list of tasks waiting for this token to be released. |
| void |
| add_waiting(Task* t) |
| { this->waiting_.push_back(t); } |
| |
| // Add T to the front of the list of tasks waiting for this token to |
| // be released. |
| void |
| add_waiting_front(Task* t) |
| { this->waiting_.push_front(t); } |
| |
| // Remove the first Task waiting for this token to be released, and |
| // return it. Return NULL if no Tasks are waiting. |
| Task* |
| remove_first_waiting() |
| { return this->waiting_.pop_front(); } |
| |
| private: |
| // It makes no sense to copy these. |
| Task_token(const Task_token&); |
| Task_token& operator=(const Task_token&); |
| |
| // Whether this is a blocker token. |
| bool is_blocker_; |
| // The number of blockers. |
| int blockers_; |
| // The single writer. |
| const Task* writer_; |
| // The list of Tasks waiting for this token to be released. |
| Task_list waiting_; |
| }; |
| |
| // In order to support tokens more reliably, we provide objects which |
| // handle them using RAII. |
| |
| // RAII class to get a write lock on a token. This requires |
| // specifying the task which is doing the lock. |
| |
| class Task_write_token |
| { |
| public: |
| Task_write_token(Task_token* token, const Task* task) |
| : token_(token), task_(task) |
| { this->token_->add_writer(this->task_); } |
| |
| ~Task_write_token() |
| { this->token_->remove_writer(this->task_); } |
| |
| private: |
| Task_write_token(const Task_write_token&); |
| Task_write_token& operator=(const Task_write_token&); |
| |
| Task_token* token_; |
| const Task* task_; |
| }; |
| |
| // RAII class for a blocker. |
| |
| class Task_block_token |
| { |
| public: |
| // The blocker count must be incremented when the task is created. |
| // This object is created when the task is run, so we don't do |
| // anything in the constructor. |
| Task_block_token(Task_token* token) |
| : token_(token) |
| { gold_assert(this->token_->is_blocked()); } |
| |
| ~Task_block_token() |
| { this->token_->remove_blocker(); } |
| |
| private: |
| Task_block_token(const Task_block_token&); |
| Task_block_token& operator=(const Task_block_token&); |
| |
| Task_token* token_; |
| }; |
| |
| // An object which implements an RAII lock for any object which |
| // supports lock and unlock methods. |
| |
| template<typename Obj> |
| class Task_lock_obj |
| { |
| public: |
| Task_lock_obj(const Task* task, Obj* obj) |
| : task_(task), obj_(obj) |
| { this->obj_->lock(task); } |
| |
| ~Task_lock_obj() |
| { this->obj_->unlock(this->task_); } |
| |
| private: |
| Task_lock_obj(const Task_lock_obj&); |
| Task_lock_obj& operator=(const Task_lock_obj&); |
| |
| const Task* task_; |
| Obj* obj_; |
| }; |
| |
| // A class which holds the set of Task_tokens which must be locked for |
| // a Task. No Task requires more than four Task_tokens, so we set |
| // that as a limit. |
| |
| class Task_locker |
| { |
| public: |
| static const int max_task_count = 4; |
| |
| Task_locker() |
| : count_(0) |
| { } |
| |
| ~Task_locker() |
| { } |
| |
| // Clear the locker. |
| void |
| clear() |
| { this->count_ = 0; } |
| |
| // Add a token to the locker. |
| void |
| add(Task* t, Task_token* token) |
| { |
| gold_assert(this->count_ < max_task_count); |
| this->tokens_[this->count_] = token; |
| ++this->count_; |
| // A blocker will have been incremented when the task is created. |
| // A writer we need to lock now. |
| if (!token->is_blocker()) |
| token->add_writer(t); |
| } |
| |
| // Iterate over the tokens. |
| |
| typedef Task_token** iterator; |
| |
| iterator |
| begin() |
| { return &this->tokens_[0]; } |
| |
| iterator |
| end() |
| { return &this->tokens_[this->count_]; } |
| |
| private: |
| Task_locker(const Task_locker&); |
| Task_locker& operator=(const Task_locker&); |
| |
| // The number of tokens. |
| int count_; |
| // The tokens. |
| Task_token* tokens_[max_task_count]; |
| }; |
| |
| } // End namespace gold. |
| |
| #endif // !defined(GOLD_TOKEN_H) |