Import binutils-2.20
[dragonfly.git] / contrib / binutils-2.20 / gold / token.h
1 // token.h -- lock tokens for gold   -*- C++ -*-
2
3 // Copyright 2006, 2007, 2008 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   // Remove a blocker from the token.  Returns true if block count
148   // drops to zero.
149   bool
150   remove_blocker()
151   {
152     gold_assert(this->is_blocker_ && this->blockers_ > 0);
153     --this->blockers_;
154     this->writer_ = NULL;
155     return this->blockers_ == 0;
156   }
157
158   // Is the token currently blocked?
159   bool
160   is_blocked() const
161   {
162     gold_assert(this->is_blocker_);
163     return this->blockers_ > 0;
164   }
165
166   // Both blocker and write lock tokens use these methods.
167
168   // Add T to the list of tasks waiting for this token to be released.
169   void
170   add_waiting(Task* t)
171   { this->waiting_.push_back(t); }
172
173   // Add T to the front of the list of tasks waiting for this token to
174   // be released.
175   void
176   add_waiting_front(Task* t)
177   { this->waiting_.push_front(t); }
178
179   // Remove the first Task waiting for this token to be released, and
180   // return it.  Return NULL if no Tasks are waiting.
181   Task*
182   remove_first_waiting()
183   { return this->waiting_.pop_front(); }
184
185  private:
186   // It makes no sense to copy these.
187   Task_token(const Task_token&);
188   Task_token& operator=(const Task_token&);
189
190   // Whether this is a blocker token.
191   bool is_blocker_;
192   // The number of blockers.
193   int blockers_;
194   // The single writer.
195   const Task* writer_;
196   // The list of Tasks waiting for this token to be released.
197   Task_list waiting_;
198 };
199
200 // In order to support tokens more reliably, we provide objects which
201 // handle them using RAII.
202
203 // RAII class to get a write lock on a token.  This requires
204 // specifying the task which is doing the lock.
205
206 class Task_write_token
207 {
208  public:
209   Task_write_token(Task_token* token, const Task* task)
210     : token_(token), task_(task)
211   { this->token_->add_writer(this->task_); }
212
213   ~Task_write_token()
214   { this->token_->remove_writer(this->task_); }
215
216  private:
217   Task_write_token(const Task_write_token&);
218   Task_write_token& operator=(const Task_write_token&);
219
220   Task_token* token_;
221   const Task* task_;
222 };
223
224 // RAII class for a blocker.
225
226 class Task_block_token
227 {
228  public:
229   // The blocker count must be incremented when the task is created.
230   // This object is created when the task is run, so we don't do
231   // anything in the constructor.
232   Task_block_token(Task_token* token)
233     : token_(token)
234   { gold_assert(this->token_->is_blocked()); }
235
236   ~Task_block_token()
237   { this->token_->remove_blocker(); }
238
239  private:
240   Task_block_token(const Task_block_token&);
241   Task_block_token& operator=(const Task_block_token&);
242
243   Task_token* token_;
244 };
245
246 // An object which implements an RAII lock for any object which
247 // supports lock and unlock methods.
248
249 template<typename Obj>
250 class Task_lock_obj
251 {
252  public:
253   Task_lock_obj(const Task* task, Obj* obj)
254     : task_(task), obj_(obj)
255   { this->obj_->lock(task); }
256
257   ~Task_lock_obj()
258   { this->obj_->unlock(this->task_); }
259
260  private:
261   Task_lock_obj(const Task_lock_obj&);
262   Task_lock_obj& operator=(const Task_lock_obj&);
263
264   const Task* task_;
265   Obj* obj_;
266 };
267
268 // A class which holds the set of Task_tokens which must be locked for
269 // a Task.  No Task requires more than four Task_tokens, so we set
270 // that as a limit.
271
272 class Task_locker
273 {
274  public:
275   static const int max_task_count = 4;
276
277   Task_locker()
278     : count_(0)
279   { }
280
281   ~Task_locker()
282   { }
283
284   // Clear the locker.
285   void
286   clear()
287   { this->count_ = 0; }
288
289   // Add a token to the locker.
290   void
291   add(Task* t, Task_token* token)
292   {
293     gold_assert(this->count_ < max_task_count);
294     this->tokens_[this->count_] = token;
295     ++this->count_;
296     // A blocker will have been incremented when the task is created.
297     // A writer we need to lock now.
298     if (!token->is_blocker())
299       token->add_writer(t);
300   }
301
302   // Iterate over the tokens.
303
304   typedef Task_token** iterator;
305
306   iterator
307   begin()
308   { return &this->tokens_[0]; }
309
310   iterator
311   end()
312   { return &this->tokens_[this->count_]; }
313
314  private:
315   Task_locker(const Task_locker&);
316   Task_locker& operator=(const Task_locker&);
317
318   // The number of tokens.
319   int count_;
320   // The tokens.
321   Task_token* tokens_[max_task_count];
322 };
323
324 } // End namespace gold.
325
326 #endif // !defined(GOLD_TOKEN_H)