Merge branch 'vendor/GCC50'
[dragonfly.git] / contrib / binutils-2.24 / gold / token.h
CommitLineData
f40e693d
JM
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
26namespace gold
27{
28
29class Condvar;
30class 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
36class 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
91class 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
215class 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
235class 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
258template<typename Obj>
259class 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
281class 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)