1 // workqueue.h -- the work queue for gold -*- C++ -*-
3 // Copyright 2006, 2007 Free Software Foundation, Inc.
4 // Written by Ian Lance Taylor <iant@google.com>.
6 // This file is part of gold.
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.
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.
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.
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.
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.
32 // Task locking using RAII.
34 // An abstract class for jobs to run.
36 #ifndef GOLD_WORKQUEUE_H
37 #define GOLD_WORKQUEUE_H
39 #include "gold-threads.h"
45 class General_options
;
49 // Some tasks require access to shared data structures, such as the
50 // symbol table. Some tasks must be executed in a particular order,
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.
69 // A read/write token uses these methods.
84 add_writer(const Task
*);
87 remove_writer(const Task
*);
90 has_write_lock(const Task
*);
92 // A blocker token uses these methods.
97 // Returns true if block count drops to zero.
105 // It makes no sense to copy these.
106 Task_token(const Task_token
&);
107 Task_token
& operator=(const Task_token
&);
114 // In order to support tokens more reliably, we provide objects which
115 // handle them using RAII.
117 class Task_read_token
120 Task_read_token(Task_token
& token
)
122 { this->token_
.add_reader(); }
125 { this->token_
.remove_reader(); }
128 Task_read_token(const Task_read_token
&);
129 Task_read_token
& operator=(const Task_read_token
&);
134 class Task_write_token
137 Task_write_token(Task_token
& token
, const Task
* task
)
138 : token_(token
), task_(task
)
139 { this->token_
.add_writer(this->task_
); }
142 { this->token_
.remove_writer(this->task_
); }
145 Task_write_token(const Task_write_token
&);
146 Task_write_token
& operator=(const Task_write_token
&);
152 class Task_block_token
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
);
162 Task_block_token(const Task_block_token
&);
163 Task_block_token
& operator=(const Task_block_token
&);
166 Workqueue
* workqueue_
;
169 // An object which implements an RAII lock for any object which
170 // supports lock and unlock methods.
172 template<typename Obj
>
176 Task_lock_obj(Obj
& obj
)
178 { this->obj_
.lock(); }
181 { this->obj_
.unlock(); }
184 Task_lock_obj(const Task_lock_obj
&);
185 Task_lock_obj
& operator=(const Task_lock_obj
&);
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.
200 virtual ~Task_locker()
204 // A version of Task_locker which may be used for a single read lock.
206 class Task_locker_read
: public Task_locker
209 Task_locker_read(Task_token
& token
)
214 Task_locker_read(const Task_locker_read
&);
215 Task_locker_read
& operator=(const Task_locker_read
&);
217 Task_read_token read_token_
;
220 // A version of Task_locker which may be used for a single write lock.
222 class Task_locker_write
: public Task_locker
225 Task_locker_write(Task_token
& token
, const Task
* task
)
226 : write_token_(token
, task
)
230 Task_locker_write(const Task_locker_write
&);
231 Task_locker_write
& operator=(const Task_locker_write
&);
233 Task_write_token write_token_
;
236 // A version of Task_locker which may be used for a single blocker
239 class Task_locker_block
: public Task_locker
242 Task_locker_block(Task_token
& token
, Workqueue
* workqueue
)
243 : block_token_(token
, workqueue
)
247 Task_locker_block(const Task_locker_block
&);
248 Task_locker_block
& operator=(const Task_locker_block
&);
250 Task_block_token block_token_
;
253 // A version of Task_locker which may be used to hold a lock on any
254 // object which supports lock() and unlock() methods.
256 template<typename Obj
>
257 class Task_locker_obj
: public Task_locker
260 Task_locker_obj(Obj
& obj
)
265 Task_locker_obj(const Task_locker_obj
&);
266 Task_locker_obj
& operator=(const Task_locker_obj
&);
268 Task_lock_obj
<Obj
> obj_lock_
;
271 // The superclass for tasks to be placed on the workqueue. Each
272 // specific task class will inherit from this one.
283 // Type returned by Is_runnable.
284 enum Is_runnable_type
288 // Task is waiting for a block to clear.
290 // Task is not waiting for a block, but is not runnable--i.e., is
291 // waiting for a lock.
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;
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.
305 locks(Workqueue
*) = 0;
311 // Return the name of the Task. This is only used for debugging
316 if (this->name_
.empty())
317 this->name_
= this->get_name();
322 // Get the name of the task. This must be implemented by the child
325 get_name() const = 0;
328 // This task may not be copied.
330 Task
& operator=(const Task
&);
332 // Task name, for debugging purposes.
336 // A simple task which waits for a blocker and then runs a function.
338 class Task_function_runner
341 virtual ~Task_function_runner()
348 class Task_function
: public Task
351 // Both points should be allocated using new, and will be deleted
352 // after the task runs.
353 Task_function(Task_function_runner
* runner
, Task_token
* blocker
,
355 : runner_(runner
), blocker_(blocker
), name_(name
)
360 delete this->runner_
;
361 delete this->blocker_
;
364 // The standard task methods.
366 // Wait until the task is unblocked.
368 is_runnable(Workqueue
*)
369 { return this->blocker_
->is_blocked() ? IS_BLOCKED
: IS_RUNNABLE
; }
371 // This type of task does not normally hold any locks.
378 run(Workqueue
* workqueue
)
379 { this->runner_
->run(workqueue
); }
381 // The debugging name.
384 { return this->name_
; }
387 Task_function(const Task_function
&);
388 Task_function
& operator=(const Task_function
&);
390 Task_function_runner
* runner_
;
391 Task_token
* blocker_
;
397 class Workqueue_runner
;
402 Workqueue(const General_options
&);
405 // Add a new task to the work queue.
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.
414 // Process all the tasks on the work queue.
418 // A complete set of blocking tasks has completed.
422 // Set the thread count.
424 set_thread_count(int);
427 // This class can not be copied.
428 Workqueue(const Workqueue
&);
429 Workqueue
& operator=(const Workqueue
&);
431 typedef std::list
<Task
*> Task_list
;
437 friend class Workqueue_runner
;
439 // Find a runnable task.
441 find_runnable(Task_list
*, bool*);
443 // Add a lock to the completed queue.
445 completed(Task
*, Task_locker
*);
447 // Clear the completed queue.
451 // Print the list of queued tasks.
455 // How to run a task. Only accessed from main thread.
456 Workqueue_runner
* runner_
;
458 // Lock for access to tasks_ members.
460 // List of tasks to execute soon.
461 Task_list first_tasks_
;
462 // List of tasks to execute after the ones in first_tasks_.
465 // Lock for access to completed_, running_, and queued_.
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.
471 // Number of tasks currently on queue (both first_tasks_ and
474 // Condition variable signalled when a new entry is added to completed_.
475 Condvar completed_condvar_
;
477 // Number of blocker tokens which were fully cleared. Only accessed
479 int cleared_blockers_
;
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_
;
486 } // End namespace gold.
488 #endif // !defined(GOLD_WORKQUEUE_H)