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 | |
fe9a4c12 | 50 | // symbol table. Some tasks must be executed in a particular order, |
bae7f79e ILT |
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() | |
c7912668 | 278 | : name_() |
bae7f79e ILT |
279 | { } |
280 | virtual ~Task() | |
281 | { } | |
282 | ||
283 | // Type returned by Is_runnable. | |
284 | enum Is_runnable_type | |
285 | { | |
286 | // Task is runnable. | |
287 | IS_RUNNABLE, | |
288 | // Task is waiting for a block to clear. | |
289 | IS_BLOCKED, | |
290 | // Task is not waiting for a block, but is not runnable--i.e., is | |
291 | // waiting for a lock. | |
292 | IS_LOCKED | |
293 | }; | |
294 | ||
295 | // Return whether the task can be run now. This method is only | |
296 | // called from the main thread. | |
297 | virtual Is_runnable_type | |
298 | is_runnable(Workqueue*) = 0; | |
299 | ||
300 | // Return a pointer to a Task_locker which locks all the resources | |
301 | // required by the task. We delete the pointer when the task is | |
302 | // complete. This method can return NULL if no locks are required. | |
303 | // This method is only called from the main thread. | |
304 | virtual Task_locker* | |
305 | locks(Workqueue*) = 0; | |
306 | ||
307 | // Run the task. | |
308 | virtual void | |
309 | run(Workqueue*) = 0; | |
ead1e424 | 310 | |
c7912668 ILT |
311 | // Return the name of the Task. This is only used for debugging |
312 | // purposes. | |
313 | const std::string& | |
314 | name() | |
315 | { | |
316 | if (this->name_.empty()) | |
317 | this->name_ = this->get_name(); | |
318 | return this->name_; | |
319 | } | |
320 | ||
321 | protected: | |
322 | // Get the name of the task. This must be implemented by the child | |
323 | // class. | |
324 | virtual std::string | |
325 | get_name() const = 0; | |
326 | ||
ead1e424 | 327 | private: |
c7912668 | 328 | // This task may not be copied. |
ead1e424 ILT |
329 | Task(const Task&); |
330 | Task& operator=(const Task&); | |
c7912668 ILT |
331 | |
332 | // Task name, for debugging purposes. | |
333 | std::string name_; | |
bae7f79e ILT |
334 | }; |
335 | ||
92e059d8 ILT |
336 | // A simple task which waits for a blocker and then runs a function. |
337 | ||
338 | class Task_function_runner | |
339 | { | |
340 | public: | |
341 | virtual ~Task_function_runner() | |
342 | { } | |
343 | ||
344 | virtual void | |
345 | run(Workqueue*) = 0; | |
346 | }; | |
347 | ||
348 | class Task_function : public Task | |
349 | { | |
350 | public: | |
351 | // Both points should be allocated using new, and will be deleted | |
352 | // after the task runs. | |
c7912668 ILT |
353 | Task_function(Task_function_runner* runner, Task_token* blocker, |
354 | const char* name) | |
355 | : runner_(runner), blocker_(blocker), name_(name) | |
92e059d8 ILT |
356 | { } |
357 | ||
358 | ~Task_function() | |
359 | { | |
360 | delete this->runner_; | |
361 | delete this->blocker_; | |
362 | } | |
363 | ||
364 | // The standard task methods. | |
365 | ||
366 | // Wait until the task is unblocked. | |
367 | Is_runnable_type | |
368 | is_runnable(Workqueue*) | |
369 | { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; } | |
370 | ||
371 | // This type of task does not normally hold any locks. | |
372 | virtual Task_locker* | |
373 | locks(Workqueue*) | |
374 | { return NULL; } | |
375 | ||
376 | // Run the action. | |
377 | void | |
378 | run(Workqueue* workqueue) | |
379 | { this->runner_->run(workqueue); } | |
380 | ||
c7912668 ILT |
381 | // The debugging name. |
382 | std::string | |
383 | get_name() const | |
384 | { return this->name_; } | |
385 | ||
92e059d8 ILT |
386 | private: |
387 | Task_function(const Task_function&); | |
388 | Task_function& operator=(const Task_function&); | |
389 | ||
390 | Task_function_runner* runner_; | |
391 | Task_token* blocker_; | |
c7912668 | 392 | const char* name_; |
92e059d8 ILT |
393 | }; |
394 | ||
bae7f79e ILT |
395 | // The workqueue |
396 | ||
397 | class Workqueue_runner; | |
398 | ||
399 | class Workqueue | |
400 | { | |
401 | public: | |
402 | Workqueue(const General_options&); | |
403 | ~Workqueue(); | |
404 | ||
405 | // Add a new task to the work queue. | |
406 | void | |
407 | queue(Task*); | |
408 | ||
92e059d8 ILT |
409 | // Add a new task to the front of the work queue. It will be the |
410 | // next task to run if it is ready. | |
411 | void | |
412 | queue_front(Task*); | |
413 | ||
bae7f79e ILT |
414 | // Process all the tasks on the work queue. |
415 | void | |
416 | process(); | |
417 | ||
418 | // A complete set of blocking tasks has completed. | |
419 | void | |
420 | cleared_blocker(); | |
421 | ||
fe9a4c12 ILT |
422 | // Set the thread count. |
423 | void | |
424 | set_thread_count(int); | |
425 | ||
bae7f79e ILT |
426 | private: |
427 | // This class can not be copied. | |
428 | Workqueue(const Workqueue&); | |
429 | Workqueue& operator=(const Workqueue&); | |
430 | ||
431 | typedef std::list<Task*> Task_list; | |
432 | ||
433 | // Run a task. | |
c7912668 ILT |
434 | void |
435 | run(Task*); | |
bae7f79e ILT |
436 | |
437 | friend class Workqueue_runner; | |
438 | ||
439 | // Find a runnable task. | |
c7912668 ILT |
440 | Task* |
441 | find_runnable(Task_list*, bool*); | |
bae7f79e ILT |
442 | |
443 | // Add a lock to the completed queue. | |
c7912668 ILT |
444 | void |
445 | completed(Task*, Task_locker*); | |
bae7f79e ILT |
446 | |
447 | // Clear the completed queue. | |
c7912668 ILT |
448 | bool |
449 | clear_completed(); | |
450 | ||
451 | // Print the list of queued tasks. | |
452 | void | |
453 | show_queued_tasks(); | |
bae7f79e ILT |
454 | |
455 | // How to run a task. Only accessed from main thread. | |
456 | Workqueue_runner* runner_; | |
457 | ||
458 | // Lock for access to tasks_ members. | |
459 | Lock tasks_lock_; | |
c7912668 ILT |
460 | // List of tasks to execute soon. |
461 | Task_list first_tasks_; | |
462 | // List of tasks to execute after the ones in first_tasks_. | |
bae7f79e ILT |
463 | Task_list tasks_; |
464 | ||
c7912668 | 465 | // Lock for access to completed_, running_, and queued_. |
bae7f79e ILT |
466 | Lock completed_lock_; |
467 | // List of Task_locker objects for main thread to free. | |
468 | std::list<Task_locker*> completed_; | |
469 | // Number of tasks currently running. | |
470 | int running_; | |
c7912668 ILT |
471 | // Number of tasks currently on queue (both first_tasks_ and |
472 | // tasks_). | |
473 | int queued_; | |
bae7f79e ILT |
474 | // Condition variable signalled when a new entry is added to completed_. |
475 | Condvar completed_condvar_; | |
476 | ||
477 | // Number of blocker tokens which were fully cleared. Only accessed | |
478 | // from main thread. | |
479 | int cleared_blockers_; | |
c7912668 ILT |
480 | |
481 | // The desired thread count. Only set by the main thread or by a | |
482 | // singleton thread. Only accessed from the main thread. | |
483 | int desired_thread_count_; | |
bae7f79e ILT |
484 | }; |
485 | ||
486 | } // End namespace gold. | |
487 | ||
488 | #endif // !defined(GOLD_WORKQUEUE_H) |