Commit | Line | Data |
---|---|---|
bae7f79e ILT |
1 | // workqueue.h -- the work queue for gold -*- C++ -*- |
2 | ||
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. | |
6 | ||
7 | // Task_token | |
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. | |
11 | // Task_locker | |
12 | // Task locking using RAII. | |
13 | // Task | |
14 | // An abstract class for jobs to run. | |
15 | ||
16 | #ifndef GOLD_WORKQUEUE_H | |
17 | #define GOLD_WORKQUEUE_H | |
18 | ||
19 | #include "gold-threads.h" | |
20 | #include "options.h" | |
21 | #include "fileread.h" | |
22 | ||
23 | namespace gold | |
24 | { | |
25 | ||
26 | class Task; | |
27 | class Workqueue; | |
28 | ||
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. | |
41 | ||
42 | class Task_token | |
43 | { | |
44 | public: | |
45 | Task_token(); | |
46 | ||
47 | ~Task_token(); | |
48 | ||
49 | // A read/write token uses these methods. | |
50 | ||
51 | bool | |
52 | is_readable() const; | |
53 | ||
54 | void | |
55 | add_reader(); | |
56 | ||
57 | void | |
58 | remove_reader(); | |
59 | ||
60 | bool | |
61 | is_writable() const; | |
62 | ||
63 | void | |
64 | add_writer(const Task*); | |
65 | ||
66 | void | |
67 | remove_writer(const Task*); | |
68 | ||
69 | bool | |
70 | has_write_lock(const Task*); | |
71 | ||
72 | // A blocker token uses these methods. | |
73 | ||
74 | void | |
75 | add_blocker(); | |
76 | ||
77 | // Returns true if block count drops to zero. | |
78 | bool | |
79 | remove_blocker(); | |
80 | ||
81 | bool | |
82 | is_blocked() const; | |
83 | ||
84 | private: | |
85 | // It makes no sense to copy these. | |
86 | Task_token(const Task_token&); | |
87 | Task_token& operator=(const Task_token&); | |
88 | ||
89 | bool is_blocker_; | |
90 | int readers_; | |
91 | const Task* writer_; | |
92 | }; | |
93 | ||
94 | // In order to support tokens more reliably, we provide objects which | |
95 | // handle them using RAII. | |
96 | ||
97 | class Task_read_token | |
98 | { | |
99 | public: | |
100 | Task_read_token(Task_token& token) | |
101 | : token_(token) | |
102 | { this->token_.add_reader(); } | |
103 | ||
104 | ~Task_read_token() | |
105 | { this->token_.remove_reader(); } | |
106 | ||
107 | private: | |
108 | Task_read_token(const Task_read_token&); | |
109 | Task_read_token& operator=(const Task_read_token&); | |
110 | ||
111 | Task_token& token_; | |
112 | }; | |
113 | ||
114 | class Task_write_token | |
115 | { | |
116 | public: | |
117 | Task_write_token(Task_token& token, const Task* task) | |
118 | : token_(token), task_(task) | |
119 | { this->token_.add_writer(this->task_); } | |
120 | ||
121 | ~Task_write_token() | |
122 | { this->token_.remove_writer(this->task_); } | |
123 | ||
124 | private: | |
125 | Task_write_token(const Task_write_token&); | |
126 | Task_write_token& operator=(const Task_write_token&); | |
127 | ||
128 | Task_token& token_; | |
129 | const Task* task_; | |
130 | }; | |
131 | ||
132 | class Task_block_token | |
133 | { | |
134 | public: | |
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); | |
139 | ~Task_block_token(); | |
140 | ||
141 | private: | |
142 | Task_block_token(const Task_block_token&); | |
143 | Task_block_token& operator=(const Task_block_token&); | |
144 | ||
145 | Task_token& token_; | |
146 | Workqueue* workqueue_; | |
147 | }; | |
148 | ||
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. | |
152 | ||
153 | class Task_locker | |
154 | { | |
155 | public: | |
156 | Task_locker() | |
157 | { } | |
158 | ||
159 | virtual ~Task_locker() | |
160 | { } | |
161 | }; | |
162 | ||
163 | // A version of Task_locker which may be used for a single read lock. | |
164 | ||
165 | class Task_locker_read : public Task_locker | |
166 | { | |
167 | public: | |
168 | Task_locker_read(Task_token& token) | |
169 | : read_token_(token) | |
170 | { } | |
171 | ||
172 | private: | |
173 | Task_locker_read(const Task_locker_read&); | |
174 | Task_locker_read& operator=(const Task_locker_read&); | |
175 | ||
176 | Task_read_token read_token_; | |
177 | }; | |
178 | ||
179 | // A version of Task_locker which may be used for a single write lock. | |
180 | ||
181 | class Task_locker_write : public Task_locker | |
182 | { | |
183 | public: | |
184 | Task_locker_write(Task_token& token, const Task* task) | |
185 | : write_token_(token, task) | |
186 | { } | |
187 | ||
188 | private: | |
189 | Task_locker_write(const Task_locker_write&); | |
190 | Task_locker_write& operator=(const Task_locker_write&); | |
191 | ||
192 | Task_write_token write_token_; | |
193 | }; | |
194 | ||
195 | // A version of Task_locker which may be used for a single blocker | |
196 | // lock. | |
197 | ||
198 | class Task_locker_block : public Task_locker | |
199 | { | |
200 | public: | |
201 | Task_locker_block(Task_token& token, Workqueue* workqueue) | |
202 | : block_token_(token, workqueue) | |
203 | { } | |
204 | ||
205 | private: | |
206 | Task_locker_block(const Task_locker_block&); | |
207 | Task_locker_block& operator=(const Task_locker_block&); | |
208 | ||
209 | Task_block_token block_token_; | |
210 | }; | |
211 | ||
212 | // A version of Task_locker which may be used to hold a lock on a | |
213 | // File_read. | |
214 | ||
215 | class Task_locker_file : public Task_locker | |
216 | { | |
217 | public: | |
218 | Task_locker_file(File_read& file) | |
219 | : file_lock_(file) | |
220 | { } | |
221 | ||
222 | private: | |
223 | Task_locker_file(const Task_locker_file&); | |
224 | Task_locker_file& operator=(const Task_locker_file&); | |
225 | ||
226 | File_read_lock file_lock_; | |
227 | }; | |
228 | ||
229 | // The superclass for tasks to be placed on the workqueue. Each | |
230 | // specific task class will inherit from this one. | |
231 | ||
232 | class Task | |
233 | { | |
234 | public: | |
235 | Task() | |
236 | { } | |
237 | virtual ~Task() | |
238 | { } | |
239 | ||
240 | // Type returned by Is_runnable. | |
241 | enum Is_runnable_type | |
242 | { | |
243 | // Task is runnable. | |
244 | IS_RUNNABLE, | |
245 | // Task is waiting for a block to clear. | |
246 | IS_BLOCKED, | |
247 | // Task is not waiting for a block, but is not runnable--i.e., is | |
248 | // waiting for a lock. | |
249 | IS_LOCKED | |
250 | }; | |
251 | ||
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; | |
256 | ||
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. | |
261 | virtual Task_locker* | |
262 | locks(Workqueue*) = 0; | |
263 | ||
264 | // Run the task. | |
265 | virtual void | |
266 | run(Workqueue*) = 0; | |
267 | }; | |
268 | ||
269 | // The workqueue | |
270 | ||
271 | class Workqueue_runner; | |
272 | ||
273 | class Workqueue | |
274 | { | |
275 | public: | |
276 | Workqueue(const General_options&); | |
277 | ~Workqueue(); | |
278 | ||
279 | // Add a new task to the work queue. | |
280 | void | |
281 | queue(Task*); | |
282 | ||
283 | // Process all the tasks on the work queue. | |
284 | void | |
285 | process(); | |
286 | ||
287 | // A complete set of blocking tasks has completed. | |
288 | void | |
289 | cleared_blocker(); | |
290 | ||
291 | private: | |
292 | // This class can not be copied. | |
293 | Workqueue(const Workqueue&); | |
294 | Workqueue& operator=(const Workqueue&); | |
295 | ||
296 | typedef std::list<Task*> Task_list; | |
297 | ||
298 | // Run a task. | |
299 | void run(Task*); | |
300 | ||
301 | friend class Workqueue_runner; | |
302 | ||
303 | // Find a runnable task. | |
304 | Task* find_runnable(Task_list&, bool*); | |
305 | ||
306 | // Add a lock to the completed queue. | |
307 | void completed(Task*, Task_locker*); | |
308 | ||
309 | // Clear the completed queue. | |
310 | bool clear_completed(); | |
311 | ||
312 | // How to run a task. Only accessed from main thread. | |
313 | Workqueue_runner* runner_; | |
314 | ||
315 | // Lock for access to tasks_ members. | |
316 | Lock tasks_lock_; | |
317 | // List of tasks to execute at each link level. | |
318 | Task_list tasks_; | |
319 | ||
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. | |
325 | int running_; | |
326 | // Condition variable signalled when a new entry is added to completed_. | |
327 | Condvar completed_condvar_; | |
328 | ||
329 | // Number of blocker tokens which were fully cleared. Only accessed | |
330 | // from main thread. | |
331 | int cleared_blockers_; | |
332 | }; | |
333 | ||
334 | } // End namespace gold. | |
335 | ||
336 | #endif // !defined(GOLD_WORKQUEUE_H) |