diff options
Diffstat (limited to 'binutils-2.25/gold/token.h')
| -rw-r--r-- | binutils-2.25/gold/token.h | 335 |
1 files changed, 335 insertions, 0 deletions
diff --git a/binutils-2.25/gold/token.h b/binutils-2.25/gold/token.h new file mode 100644 index 00000000..5cf64a0d --- /dev/null +++ b/binutils-2.25/gold/token.h @@ -0,0 +1,335 @@ +// token.h -- lock tokens for gold -*- C++ -*- + +// Copyright 2006, 2007, 2008, 2010 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) |