1 // workqueue.h -- the work queue for gold -*- C++ -*-
3 // After processing the command line, everything the linker does is
4 // driven from a work queue. This permits us to parallelize the
5 // linker where possible.
8 // A simple locking implementation to ensure proper task ordering.
9 // Task_read_token, Task_write_token
10 // Lock a Task_token for read or write.
12 // Task locking using RAII.
14 // An abstract class for jobs to run.
16 #ifndef GOLD_WORKQUEUE_H
17 #define GOLD_WORKQUEUE_H
19 #include "gold-threads.h"
29 // Some tasks require access to shared data structures, such as the
30 // symbol table. Some tasks must be executed in a particular error,
31 // such as reading input file symbol tables--if we see foo.o -llib, we
32 // have to read the symbols for foo.o before we read the ones for
33 // -llib. To implement this safely and efficiently, we use tokens.
34 // Task_tokens support shared read/exclusive write access to some
35 // resource. Alternatively, they support blockers: blockers implement
36 // the requirement that some set of tasks must complete before another
37 // set of tasks can start. In such a case we increment the block
38 // count when we create the task, and decrement it when the task
39 // completes. Task_tokens are only manipulated by the main thread, so
40 // they do not themselves require any locking.
49 // A read/write token uses these methods.
64 add_writer(const Task
*);
67 remove_writer(const Task
*);
70 has_write_lock(const Task
*);
72 // A blocker token uses these methods.
77 // Returns true if block count drops to zero.
85 // It makes no sense to copy these.
86 Task_token(const Task_token
&);
87 Task_token
& operator=(const Task_token
&);
94 // In order to support tokens more reliably, we provide objects which
95 // handle them using RAII.
100 Task_read_token(Task_token
& token
)
102 { this->token_
.add_reader(); }
105 { this->token_
.remove_reader(); }
108 Task_read_token(const Task_read_token
&);
109 Task_read_token
& operator=(const Task_read_token
&);
114 class Task_write_token
117 Task_write_token(Task_token
& token
, const Task
* task
)
118 : token_(token
), task_(task
)
119 { this->token_
.add_writer(this->task_
); }
122 { this->token_
.remove_writer(this->task_
); }
125 Task_write_token(const Task_write_token
&);
126 Task_write_token
& operator=(const Task_write_token
&);
132 class Task_block_token
135 // The blocker count must be incremented when the task is created.
136 // This object is created when the task is run. When we unblock the
137 // last task, we notify the workqueue.
138 Task_block_token(Task_token
& token
, Workqueue
* workqueue
);
142 Task_block_token(const Task_block_token
&);
143 Task_block_token
& operator=(const Task_block_token
&);
146 Workqueue
* workqueue_
;
149 // An abstract class used to lock Task_tokens using RAII. A typical
150 // implementation would simply have a set of members of type
151 // Task_read_token, Task_write_token, and Task_block_token.
159 virtual ~Task_locker()
163 // A version of Task_locker which may be used for a single read lock.
165 class Task_locker_read
: public Task_locker
168 Task_locker_read(Task_token
& token
)
173 Task_locker_read(const Task_locker_read
&);
174 Task_locker_read
& operator=(const Task_locker_read
&);
176 Task_read_token read_token_
;
179 // A version of Task_locker which may be used for a single write lock.
181 class Task_locker_write
: public Task_locker
184 Task_locker_write(Task_token
& token
, const Task
* task
)
185 : write_token_(token
, task
)
189 Task_locker_write(const Task_locker_write
&);
190 Task_locker_write
& operator=(const Task_locker_write
&);
192 Task_write_token write_token_
;
195 // A version of Task_locker which may be used for a single blocker
198 class Task_locker_block
: public Task_locker
201 Task_locker_block(Task_token
& token
, Workqueue
* workqueue
)
202 : block_token_(token
, workqueue
)
206 Task_locker_block(const Task_locker_block
&);
207 Task_locker_block
& operator=(const Task_locker_block
&);
209 Task_block_token block_token_
;
212 // A version of Task_locker which may be used to hold a lock on a
215 class Task_locker_file
: public Task_locker
218 Task_locker_file(File_read
& file
)
223 Task_locker_file(const Task_locker_file
&);
224 Task_locker_file
& operator=(const Task_locker_file
&);
226 File_read_lock file_lock_
;
229 // The superclass for tasks to be placed on the workqueue. Each
230 // specific task class will inherit from this one.
240 // Type returned by Is_runnable.
241 enum Is_runnable_type
245 // Task is waiting for a block to clear.
247 // Task is not waiting for a block, but is not runnable--i.e., is
248 // waiting for a lock.
252 // Return whether the task can be run now. This method is only
253 // called from the main thread.
254 virtual Is_runnable_type
255 is_runnable(Workqueue
*) = 0;
257 // Return a pointer to a Task_locker which locks all the resources
258 // required by the task. We delete the pointer when the task is
259 // complete. This method can return NULL if no locks are required.
260 // This method is only called from the main thread.
262 locks(Workqueue
*) = 0;
271 class Workqueue_runner
;
276 Workqueue(const General_options
&);
279 // Add a new task to the work queue.
283 // Process all the tasks on the work queue.
287 // A complete set of blocking tasks has completed.
292 // This class can not be copied.
293 Workqueue(const Workqueue
&);
294 Workqueue
& operator=(const Workqueue
&);
296 typedef std::list
<Task
*> Task_list
;
301 friend class Workqueue_runner
;
303 // Find a runnable task.
304 Task
* find_runnable(Task_list
&, bool*);
306 // Add a lock to the completed queue.
307 void completed(Task
*, Task_locker
*);
309 // Clear the completed queue.
310 bool clear_completed();
312 // How to run a task. Only accessed from main thread.
313 Workqueue_runner
* runner_
;
315 // Lock for access to tasks_ members.
317 // List of tasks to execute at each link level.
320 // Lock for access to completed_ and running_ members.
321 Lock completed_lock_
;
322 // List of Task_locker objects for main thread to free.
323 std::list
<Task_locker
*> completed_
;
324 // Number of tasks currently running.
326 // Condition variable signalled when a new entry is added to completed_.
327 Condvar completed_condvar_
;
329 // Number of blocker tokens which were fully cleared. Only accessed
331 int cleared_blockers_
;
334 } // End namespace gold.
336 #endif // !defined(GOLD_WORKQUEUE_H)