Commit | Line | Data |
---|---|---|
17a1d0a9 ILT |
1 | // token.h -- lock tokens for gold -*- C++ -*- |
2 | ||
3 | // Copyright 2006, 2007 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 end of the list. | |
52 | void | |
53 | push_back(Task* t); | |
54 | ||
55 | // Remove the first Task on the list and return it. Return NULL if | |
56 | // the list is empty. | |
57 | Task* | |
58 | pop_front(); | |
59 | ||
60 | private: | |
61 | // The start of the list. NULL if the list is empty. | |
62 | Task* head_; | |
63 | // The end of the list. NULL if the list is empty. | |
64 | Task* tail_; | |
65 | }; | |
66 | ||
67 | // We support two basic types of locks, which are both implemented | |
68 | // using the single class Task_token. | |
69 | ||
70 | // A write lock may be held by a single Task at a time. This is used | |
71 | // to control access to a single shared resource such as an Object. | |
72 | ||
73 | // A blocker is used to indicate that a Task A must be run after some | |
74 | // set of Tasks B. For each of the Tasks B, we increment the blocker | |
75 | // when the Task is created, and decrement it when the Task is | |
76 | // completed. When the count goes to 0, the task A is ready to run. | |
77 | ||
78 | // There are no shared read locks. We always read and write objects | |
79 | // in predictable patterns. The purpose of the locks is to permit | |
80 | // some flexibility for the threading system, for cases where the | |
81 | // execution order does not matter. | |
82 | ||
83 | // These tokens are only manipulated when the workqueue lock is held | |
84 | // or when they are first created. They do not require any locking | |
85 | // themselves. | |
86 | ||
87 | class Task_token | |
88 | { | |
89 | public: | |
90 | Task_token(bool is_blocker) | |
91 | : is_blocker_(is_blocker), blockers_(0), writer_(NULL), waiting_() | |
92 | { } | |
93 | ||
94 | ~Task_token() | |
95 | { | |
96 | gold_assert(this->blockers_ == 0); | |
97 | gold_assert(this->writer_ == NULL); | |
98 | } | |
99 | ||
100 | // Return whether this is a blocker. | |
101 | bool | |
102 | is_blocker() const | |
103 | { return this->is_blocker_; } | |
104 | ||
105 | // A write lock token uses these methods. | |
106 | ||
107 | // Is the token writable? | |
108 | bool | |
109 | is_writable() const | |
110 | { | |
111 | gold_assert(!this->is_blocker_); | |
112 | return this->writer_ == NULL; | |
113 | } | |
114 | ||
115 | // Add the task as the token's writer (there may only be one | |
116 | // writer). | |
117 | void | |
118 | add_writer(const Task* t) | |
119 | { | |
120 | gold_assert(!this->is_blocker_ && this->writer_ == NULL); | |
121 | this->writer_ = t; | |
122 | } | |
123 | ||
124 | // Remove the task as the token's writer. | |
125 | void | |
126 | remove_writer(const Task* t) | |
127 | { | |
128 | gold_assert(!this->is_blocker_ && this->writer_ == t); | |
129 | this->writer_ = NULL; | |
130 | } | |
131 | ||
132 | // A blocker token uses these methods. | |
133 | ||
134 | // Add a blocker to the token. | |
135 | void | |
136 | add_blocker() | |
137 | { | |
138 | gold_assert(this->is_blocker_); | |
139 | ++this->blockers_; | |
140 | this->writer_ = NULL; | |
141 | } | |
142 | ||
143 | // Remove a blocker from the token. Returns true if block count | |
144 | // drops to zero. | |
145 | bool | |
146 | remove_blocker() | |
147 | { | |
148 | gold_assert(this->is_blocker_ && this->blockers_ > 0); | |
149 | --this->blockers_; | |
150 | this->writer_ = NULL; | |
151 | return this->blockers_ == 0; | |
152 | } | |
153 | ||
154 | // Is the token currently blocked? | |
155 | bool | |
156 | is_blocked() const | |
157 | { | |
158 | gold_assert(this->is_blocker_); | |
159 | return this->blockers_ > 0; | |
160 | } | |
161 | ||
162 | // Both blocker and write lock tokens use these methods. | |
163 | ||
164 | // Add T to the list of tasks waiting for this token to be released. | |
165 | void | |
166 | add_waiting(Task* t) | |
167 | { this->waiting_.push_back(t); } | |
168 | ||
169 | // Remove the first Task waiting for this token to be released, and | |
170 | // return it. Return NULL if no Tasks are waiting. | |
171 | Task* | |
172 | remove_first_waiting() | |
173 | { return this->waiting_.pop_front(); } | |
174 | ||
175 | private: | |
176 | // It makes no sense to copy these. | |
177 | Task_token(const Task_token&); | |
178 | Task_token& operator=(const Task_token&); | |
179 | ||
180 | // Whether this is a blocker token. | |
181 | bool is_blocker_; | |
182 | // The number of blockers. | |
183 | int blockers_; | |
184 | // The single writer. | |
185 | const Task* writer_; | |
186 | // The list of Tasks waiting for this token to be released. | |
187 | Task_list waiting_; | |
188 | }; | |
189 | ||
190 | // In order to support tokens more reliably, we provide objects which | |
191 | // handle them using RAII. | |
192 | ||
193 | // RAII class to get a write lock on a token. This requires | |
194 | // specifying the task which is doing the lock. | |
195 | ||
196 | class Task_write_token | |
197 | { | |
198 | public: | |
199 | Task_write_token(Task_token* token, const Task* task) | |
200 | : token_(token), task_(task) | |
201 | { this->token_->add_writer(this->task_); } | |
202 | ||
203 | ~Task_write_token() | |
204 | { this->token_->remove_writer(this->task_); } | |
205 | ||
206 | private: | |
207 | Task_write_token(const Task_write_token&); | |
208 | Task_write_token& operator=(const Task_write_token&); | |
209 | ||
210 | Task_token* token_; | |
211 | const Task* task_; | |
212 | }; | |
213 | ||
214 | // RAII class for a blocker. | |
215 | ||
216 | class Task_block_token | |
217 | { | |
218 | public: | |
219 | // The blocker count must be incremented when the task is created. | |
220 | // This object is created when the task is run, so we don't do | |
221 | // anything in the constructor. | |
222 | Task_block_token(Task_token* token) | |
223 | : token_(token) | |
224 | { gold_assert(this->token_->is_blocked()); } | |
225 | ||
226 | ~Task_block_token() | |
227 | { this->token_->remove_blocker(); } | |
228 | ||
229 | private: | |
230 | Task_block_token(const Task_block_token&); | |
231 | Task_block_token& operator=(const Task_block_token&); | |
232 | ||
233 | Task_token* token_; | |
234 | }; | |
235 | ||
236 | // An object which implements an RAII lock for any object which | |
237 | // supports lock and unlock methods. | |
238 | ||
239 | template<typename Obj> | |
240 | class Task_lock_obj | |
241 | { | |
242 | public: | |
243 | Task_lock_obj(const Task* task, Obj* obj) | |
244 | : task_(task), obj_(obj) | |
245 | { this->obj_->lock(task); } | |
246 | ||
247 | ~Task_lock_obj() | |
248 | { this->obj_->unlock(this->task_); } | |
249 | ||
250 | private: | |
251 | Task_lock_obj(const Task_lock_obj&); | |
252 | Task_lock_obj& operator=(const Task_lock_obj&); | |
253 | ||
254 | const Task* task_; | |
255 | Obj* obj_; | |
256 | }; | |
257 | ||
258 | // A class which holds the set of Task_tokens which must be locked for | |
259 | // a Task. No Task requires more than four Task_tokens, so we set | |
260 | // that as a limit. | |
261 | ||
262 | class Task_locker | |
263 | { | |
264 | public: | |
265 | static const int max_task_count = 4; | |
266 | ||
267 | Task_locker() | |
268 | : count_(0) | |
269 | { } | |
270 | ||
271 | ~Task_locker() | |
272 | { } | |
273 | ||
274 | // Clear the locker. | |
275 | void | |
276 | clear() | |
277 | { this->count_ = 0; } | |
278 | ||
279 | // Add a token to the locker. | |
280 | void | |
281 | add(Task* t, Task_token* token) | |
282 | { | |
283 | gold_assert(this->count_ < max_task_count); | |
284 | this->tokens_[this->count_] = token; | |
285 | ++this->count_; | |
286 | // A blocker will have been incremented when the task is created. | |
287 | // A writer we need to lock now. | |
288 | if (!token->is_blocker()) | |
289 | token->add_writer(t); | |
290 | } | |
291 | ||
292 | // Iterate over the tokens. | |
293 | ||
294 | typedef Task_token** iterator; | |
295 | ||
296 | iterator | |
297 | begin() | |
298 | { return &this->tokens_[0]; } | |
299 | ||
300 | iterator | |
301 | end() | |
302 | { return &this->tokens_[this->count_]; } | |
303 | ||
304 | private: | |
305 | Task_locker(const Task_locker&); | |
306 | Task_locker& operator=(const Task_locker&); | |
307 | ||
308 | // The number of tokens. | |
309 | int count_; | |
310 | // The tokens. | |
311 | Task_token* tokens_[max_task_count]; | |
312 | }; | |
313 | ||
314 | } // End namespace gold. | |
315 | ||
316 | #endif // !defined(GOLD_TOKEN_H) |