Commit | Line | Data |
---|---|---|
bae7f79e ILT |
1 | // workqueue.h -- the work queue for gold -*- C++ -*- |
2 | ||
6cb15b7f ILT |
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 | ||
bae7f79e ILT |
23 | // After processing the command line, everything the linker does is |
24 | // driven from a work queue. This permits us to parallelize the | |
25 | // linker where possible. | |
26 | ||
27 | // Task_token | |
28 | // A simple locking implementation to ensure proper task ordering. | |
29 | // Task_read_token, Task_write_token | |
30 | // Lock a Task_token for read or write. | |
31 | // Task_locker | |
32 | // Task locking using RAII. | |
33 | // Task | |
34 | // An abstract class for jobs to run. | |
35 | ||
36 | #ifndef GOLD_WORKQUEUE_H | |
37 | #define GOLD_WORKQUEUE_H | |
38 | ||
39 | #include "gold-threads.h" | |
bae7f79e ILT |
40 | #include "fileread.h" |
41 | ||
42 | namespace gold | |
43 | { | |
44 | ||
ead1e424 | 45 | class General_options; |
bae7f79e ILT |
46 | class Task; |
47 | class Workqueue; | |
48 | ||
49 | // Some tasks require access to shared data structures, such as the | |
50 | // symbol table. Some tasks must be executed in a particular error, | |
51 | // such as reading input file symbol tables--if we see foo.o -llib, we | |
52 | // have to read the symbols for foo.o before we read the ones for | |
53 | // -llib. To implement this safely and efficiently, we use tokens. | |
54 | // Task_tokens support shared read/exclusive write access to some | |
55 | // resource. Alternatively, they support blockers: blockers implement | |
56 | // the requirement that some set of tasks must complete before another | |
57 | // set of tasks can start. In such a case we increment the block | |
58 | // count when we create the task, and decrement it when the task | |
59 | // completes. Task_tokens are only manipulated by the main thread, so | |
60 | // they do not themselves require any locking. | |
61 | ||
62 | class Task_token | |
63 | { | |
64 | public: | |
65 | Task_token(); | |
66 | ||
67 | ~Task_token(); | |
68 | ||
69 | // A read/write token uses these methods. | |
70 | ||
71 | bool | |
72 | is_readable() const; | |
73 | ||
74 | void | |
75 | add_reader(); | |
76 | ||
77 | void | |
78 | remove_reader(); | |
79 | ||
80 | bool | |
81 | is_writable() const; | |
82 | ||
83 | void | |
84 | add_writer(const Task*); | |
85 | ||
86 | void | |
87 | remove_writer(const Task*); | |
88 | ||
89 | bool | |
90 | has_write_lock(const Task*); | |
91 | ||
92 | // A blocker token uses these methods. | |
93 | ||
94 | void | |
95 | add_blocker(); | |
96 | ||
97 | // Returns true if block count drops to zero. | |
98 | bool | |
99 | remove_blocker(); | |
100 | ||
101 | bool | |
102 | is_blocked() const; | |
103 | ||
104 | private: | |
105 | // It makes no sense to copy these. | |
106 | Task_token(const Task_token&); | |
107 | Task_token& operator=(const Task_token&); | |
108 | ||
109 | bool is_blocker_; | |
110 | int readers_; | |
111 | const Task* writer_; | |
112 | }; | |
113 | ||
114 | // In order to support tokens more reliably, we provide objects which | |
115 | // handle them using RAII. | |
116 | ||
117 | class Task_read_token | |
118 | { | |
119 | public: | |
120 | Task_read_token(Task_token& token) | |
121 | : token_(token) | |
122 | { this->token_.add_reader(); } | |
123 | ||
124 | ~Task_read_token() | |
125 | { this->token_.remove_reader(); } | |
126 | ||
127 | private: | |
128 | Task_read_token(const Task_read_token&); | |
129 | Task_read_token& operator=(const Task_read_token&); | |
130 | ||
131 | Task_token& token_; | |
132 | }; | |
133 | ||
134 | class Task_write_token | |
135 | { | |
136 | public: | |
137 | Task_write_token(Task_token& token, const Task* task) | |
138 | : token_(token), task_(task) | |
139 | { this->token_.add_writer(this->task_); } | |
140 | ||
141 | ~Task_write_token() | |
142 | { this->token_.remove_writer(this->task_); } | |
143 | ||
144 | private: | |
145 | Task_write_token(const Task_write_token&); | |
146 | Task_write_token& operator=(const Task_write_token&); | |
147 | ||
148 | Task_token& token_; | |
149 | const Task* task_; | |
150 | }; | |
151 | ||
152 | class Task_block_token | |
153 | { | |
154 | public: | |
155 | // The blocker count must be incremented when the task is created. | |
156 | // This object is created when the task is run. When we unblock the | |
157 | // last task, we notify the workqueue. | |
158 | Task_block_token(Task_token& token, Workqueue* workqueue); | |
159 | ~Task_block_token(); | |
160 | ||
161 | private: | |
162 | Task_block_token(const Task_block_token&); | |
163 | Task_block_token& operator=(const Task_block_token&); | |
164 | ||
165 | Task_token& token_; | |
166 | Workqueue* workqueue_; | |
167 | }; | |
168 | ||
a2fb1b05 ILT |
169 | // An object which implements an RAII lock for any object which |
170 | // supports lock and unlock methods. | |
171 | ||
172 | template<typename Obj> | |
173 | class Task_lock_obj | |
174 | { | |
175 | public: | |
176 | Task_lock_obj(Obj& obj) | |
177 | : obj_(obj) | |
178 | { this->obj_.lock(); } | |
179 | ||
180 | ~Task_lock_obj() | |
181 | { this->obj_.unlock(); } | |
182 | ||
183 | private: | |
184 | Task_lock_obj(const Task_lock_obj&); | |
185 | Task_lock_obj& operator=(const Task_lock_obj&); | |
186 | ||
187 | Obj& obj_; | |
188 | }; | |
189 | ||
bae7f79e ILT |
190 | // An abstract class used to lock Task_tokens using RAII. A typical |
191 | // implementation would simply have a set of members of type | |
192 | // Task_read_token, Task_write_token, and Task_block_token. | |
193 | ||
194 | class Task_locker | |
195 | { | |
196 | public: | |
197 | Task_locker() | |
198 | { } | |
199 | ||
200 | virtual ~Task_locker() | |
201 | { } | |
202 | }; | |
203 | ||
204 | // A version of Task_locker which may be used for a single read lock. | |
205 | ||
206 | class Task_locker_read : public Task_locker | |
207 | { | |
208 | public: | |
209 | Task_locker_read(Task_token& token) | |
210 | : read_token_(token) | |
211 | { } | |
212 | ||
213 | private: | |
214 | Task_locker_read(const Task_locker_read&); | |
215 | Task_locker_read& operator=(const Task_locker_read&); | |
216 | ||
217 | Task_read_token read_token_; | |
218 | }; | |
219 | ||
220 | // A version of Task_locker which may be used for a single write lock. | |
221 | ||
222 | class Task_locker_write : public Task_locker | |
223 | { | |
224 | public: | |
225 | Task_locker_write(Task_token& token, const Task* task) | |
226 | : write_token_(token, task) | |
227 | { } | |
228 | ||
229 | private: | |
230 | Task_locker_write(const Task_locker_write&); | |
231 | Task_locker_write& operator=(const Task_locker_write&); | |
232 | ||
233 | Task_write_token write_token_; | |
234 | }; | |
235 | ||
236 | // A version of Task_locker which may be used for a single blocker | |
237 | // lock. | |
238 | ||
239 | class Task_locker_block : public Task_locker | |
240 | { | |
241 | public: | |
242 | Task_locker_block(Task_token& token, Workqueue* workqueue) | |
243 | : block_token_(token, workqueue) | |
244 | { } | |
245 | ||
246 | private: | |
247 | Task_locker_block(const Task_locker_block&); | |
248 | Task_locker_block& operator=(const Task_locker_block&); | |
249 | ||
250 | Task_block_token block_token_; | |
251 | }; | |
252 | ||
a2fb1b05 ILT |
253 | // A version of Task_locker which may be used to hold a lock on any |
254 | // object which supports lock() and unlock() methods. | |
bae7f79e | 255 | |
a2fb1b05 ILT |
256 | template<typename Obj> |
257 | class Task_locker_obj : public Task_locker | |
bae7f79e ILT |
258 | { |
259 | public: | |
a2fb1b05 ILT |
260 | Task_locker_obj(Obj& obj) |
261 | : obj_lock_(obj) | |
bae7f79e ILT |
262 | { } |
263 | ||
264 | private: | |
a2fb1b05 ILT |
265 | Task_locker_obj(const Task_locker_obj&); |
266 | Task_locker_obj& operator=(const Task_locker_obj&); | |
bae7f79e | 267 | |
a2fb1b05 | 268 | Task_lock_obj<Obj> obj_lock_; |
bae7f79e ILT |
269 | }; |
270 | ||
271 | // The superclass for tasks to be placed on the workqueue. Each | |
272 | // specific task class will inherit from this one. | |
273 | ||
274 | class Task | |
275 | { | |
276 | public: | |
277 | Task() | |
278 | { } | |
279 | virtual ~Task() | |
280 | { } | |
281 | ||
282 | // Type returned by Is_runnable. | |
283 | enum Is_runnable_type | |
284 | { | |
285 | // Task is runnable. | |
286 | IS_RUNNABLE, | |
287 | // Task is waiting for a block to clear. | |
288 | IS_BLOCKED, | |
289 | // Task is not waiting for a block, but is not runnable--i.e., is | |
290 | // waiting for a lock. | |
291 | IS_LOCKED | |
292 | }; | |
293 | ||
294 | // Return whether the task can be run now. This method is only | |
295 | // called from the main thread. | |
296 | virtual Is_runnable_type | |
297 | is_runnable(Workqueue*) = 0; | |
298 | ||
299 | // Return a pointer to a Task_locker which locks all the resources | |
300 | // required by the task. We delete the pointer when the task is | |
301 | // complete. This method can return NULL if no locks are required. | |
302 | // This method is only called from the main thread. | |
303 | virtual Task_locker* | |
304 | locks(Workqueue*) = 0; | |
305 | ||
306 | // Run the task. | |
307 | virtual void | |
308 | run(Workqueue*) = 0; | |
ead1e424 ILT |
309 | |
310 | private: | |
311 | Task(const Task&); | |
312 | Task& operator=(const Task&); | |
bae7f79e ILT |
313 | }; |
314 | ||
92e059d8 ILT |
315 | // A simple task which waits for a blocker and then runs a function. |
316 | ||
317 | class Task_function_runner | |
318 | { | |
319 | public: | |
320 | virtual ~Task_function_runner() | |
321 | { } | |
322 | ||
323 | virtual void | |
324 | run(Workqueue*) = 0; | |
325 | }; | |
326 | ||
327 | class Task_function : public Task | |
328 | { | |
329 | public: | |
330 | // Both points should be allocated using new, and will be deleted | |
331 | // after the task runs. | |
332 | Task_function(Task_function_runner* runner, Task_token* blocker) | |
333 | : runner_(runner), blocker_(blocker) | |
334 | { } | |
335 | ||
336 | ~Task_function() | |
337 | { | |
338 | delete this->runner_; | |
339 | delete this->blocker_; | |
340 | } | |
341 | ||
342 | // The standard task methods. | |
343 | ||
344 | // Wait until the task is unblocked. | |
345 | Is_runnable_type | |
346 | is_runnable(Workqueue*) | |
347 | { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; } | |
348 | ||
349 | // This type of task does not normally hold any locks. | |
350 | virtual Task_locker* | |
351 | locks(Workqueue*) | |
352 | { return NULL; } | |
353 | ||
354 | // Run the action. | |
355 | void | |
356 | run(Workqueue* workqueue) | |
357 | { this->runner_->run(workqueue); } | |
358 | ||
359 | private: | |
360 | Task_function(const Task_function&); | |
361 | Task_function& operator=(const Task_function&); | |
362 | ||
363 | Task_function_runner* runner_; | |
364 | Task_token* blocker_; | |
365 | }; | |
366 | ||
bae7f79e ILT |
367 | // The workqueue |
368 | ||
369 | class Workqueue_runner; | |
370 | ||
371 | class Workqueue | |
372 | { | |
373 | public: | |
374 | Workqueue(const General_options&); | |
375 | ~Workqueue(); | |
376 | ||
377 | // Add a new task to the work queue. | |
378 | void | |
379 | queue(Task*); | |
380 | ||
92e059d8 ILT |
381 | // Add a new task to the front of the work queue. It will be the |
382 | // next task to run if it is ready. | |
383 | void | |
384 | queue_front(Task*); | |
385 | ||
bae7f79e ILT |
386 | // Process all the tasks on the work queue. |
387 | void | |
388 | process(); | |
389 | ||
390 | // A complete set of blocking tasks has completed. | |
391 | void | |
392 | cleared_blocker(); | |
393 | ||
394 | private: | |
395 | // This class can not be copied. | |
396 | Workqueue(const Workqueue&); | |
397 | Workqueue& operator=(const Workqueue&); | |
398 | ||
399 | typedef std::list<Task*> Task_list; | |
400 | ||
401 | // Run a task. | |
402 | void run(Task*); | |
403 | ||
404 | friend class Workqueue_runner; | |
405 | ||
406 | // Find a runnable task. | |
407 | Task* find_runnable(Task_list&, bool*); | |
408 | ||
409 | // Add a lock to the completed queue. | |
410 | void completed(Task*, Task_locker*); | |
411 | ||
412 | // Clear the completed queue. | |
413 | bool clear_completed(); | |
414 | ||
415 | // How to run a task. Only accessed from main thread. | |
416 | Workqueue_runner* runner_; | |
417 | ||
418 | // Lock for access to tasks_ members. | |
419 | Lock tasks_lock_; | |
420 | // List of tasks to execute at each link level. | |
421 | Task_list tasks_; | |
422 | ||
423 | // Lock for access to completed_ and running_ members. | |
424 | Lock completed_lock_; | |
425 | // List of Task_locker objects for main thread to free. | |
426 | std::list<Task_locker*> completed_; | |
427 | // Number of tasks currently running. | |
428 | int running_; | |
429 | // Condition variable signalled when a new entry is added to completed_. | |
430 | Condvar completed_condvar_; | |
431 | ||
432 | // Number of blocker tokens which were fully cleared. Only accessed | |
433 | // from main thread. | |
434 | int cleared_blockers_; | |
435 | }; | |
436 | ||
437 | } // End namespace gold. | |
438 | ||
439 | #endif // !defined(GOLD_WORKQUEUE_H) |