Commit | Line | Data |
---|---|---|
bae7f79e ILT |
1 | // workqueue.cc -- the workqueue for gold |
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 | 23 | #include "gold.h" |
c33feb2b | 24 | |
fe9a4c12 ILT |
25 | #ifdef ENABLE_THREADS |
26 | #include <pthread.h> | |
27 | #endif | |
28 | ||
bae7f79e ILT |
29 | #include "workqueue.h" |
30 | ||
31 | namespace gold | |
32 | { | |
33 | ||
34 | // Task_token methods. | |
35 | ||
36 | Task_token::Task_token() | |
37 | : is_blocker_(false), readers_(0), writer_(NULL) | |
38 | { | |
39 | } | |
40 | ||
41 | Task_token::~Task_token() | |
42 | { | |
a3ad94ed | 43 | gold_assert(this->readers_ == 0 && this->writer_ == NULL); |
bae7f79e ILT |
44 | } |
45 | ||
46 | bool | |
47 | Task_token::is_readable() const | |
48 | { | |
a3ad94ed | 49 | gold_assert(!this->is_blocker_); |
bae7f79e ILT |
50 | return this->writer_ == NULL; |
51 | } | |
52 | ||
53 | void | |
54 | Task_token::add_reader() | |
55 | { | |
a3ad94ed ILT |
56 | gold_assert(!this->is_blocker_); |
57 | gold_assert(this->is_readable()); | |
bae7f79e ILT |
58 | ++this->readers_; |
59 | } | |
60 | ||
61 | void | |
62 | Task_token::remove_reader() | |
63 | { | |
a3ad94ed ILT |
64 | gold_assert(!this->is_blocker_); |
65 | gold_assert(this->readers_ > 0); | |
bae7f79e ILT |
66 | --this->readers_; |
67 | } | |
68 | ||
69 | bool | |
70 | Task_token::is_writable() const | |
71 | { | |
a3ad94ed | 72 | gold_assert(!this->is_blocker_); |
bae7f79e ILT |
73 | return this->writer_ == NULL && this->readers_ == 0; |
74 | } | |
75 | ||
76 | void | |
77 | Task_token::add_writer(const Task* t) | |
78 | { | |
a3ad94ed ILT |
79 | gold_assert(!this->is_blocker_); |
80 | gold_assert(this->is_writable()); | |
bae7f79e ILT |
81 | this->writer_ = t; |
82 | } | |
83 | ||
84 | void | |
85 | Task_token::remove_writer(const Task* t) | |
86 | { | |
a3ad94ed ILT |
87 | gold_assert(!this->is_blocker_); |
88 | gold_assert(this->writer_ == t); | |
bae7f79e ILT |
89 | this->writer_ = NULL; |
90 | } | |
91 | ||
92 | bool | |
93 | Task_token::has_write_lock(const Task* t) | |
94 | { | |
a3ad94ed | 95 | gold_assert(!this->is_blocker_); |
bae7f79e ILT |
96 | return this->writer_ == t; |
97 | } | |
98 | ||
99 | // For blockers, we just use the readers_ field. | |
100 | ||
101 | void | |
102 | Task_token::add_blocker() | |
103 | { | |
104 | if (this->readers_ == 0 && this->writer_ == NULL) | |
105 | this->is_blocker_ = true; | |
106 | else | |
a3ad94ed | 107 | gold_assert(this->is_blocker_); |
bae7f79e ILT |
108 | ++this->readers_; |
109 | } | |
110 | ||
111 | bool | |
112 | Task_token::remove_blocker() | |
113 | { | |
a3ad94ed | 114 | gold_assert(this->is_blocker_ && this->readers_ > 0); |
bae7f79e ILT |
115 | --this->readers_; |
116 | return this->readers_ == 0; | |
117 | } | |
118 | ||
119 | bool | |
120 | Task_token::is_blocked() const | |
121 | { | |
a3ad94ed ILT |
122 | gold_assert(this->is_blocker_ |
123 | || (this->readers_ == 0 && this->writer_ == NULL)); | |
bae7f79e ILT |
124 | return this->readers_ > 0; |
125 | } | |
126 | ||
127 | // The Task_block_token class. | |
128 | ||
129 | Task_block_token::Task_block_token(Task_token& token, Workqueue* workqueue) | |
130 | : token_(token), workqueue_(workqueue) | |
131 | { | |
132 | // We must increment the block count when the task is created and | |
133 | // put on the queue. This object is created when the task is run, | |
134 | // so we don't increment the block count here. | |
a3ad94ed | 135 | gold_assert(this->token_.is_blocked()); |
bae7f79e ILT |
136 | } |
137 | ||
138 | Task_block_token::~Task_block_token() | |
139 | { | |
140 | if (this->token_.remove_blocker()) | |
141 | { | |
142 | // Tell the workqueue that a blocker was cleared. This is | |
143 | // always called in the main thread, so no locking is required. | |
144 | this->workqueue_->cleared_blocker(); | |
145 | } | |
146 | } | |
147 | ||
148 | // The Workqueue_runner abstract class. | |
149 | ||
150 | class Workqueue_runner | |
151 | { | |
152 | public: | |
153 | Workqueue_runner(Workqueue* workqueue) | |
154 | : workqueue_(workqueue) | |
155 | { } | |
156 | virtual ~Workqueue_runner() | |
157 | { } | |
158 | ||
159 | // Run a task. This is always called in the main thread. | |
fe9a4c12 ILT |
160 | virtual void |
161 | run(Task*, Task_locker*) = 0; | |
162 | ||
163 | // Set the number of threads to use. This is ignored when not using | |
164 | // threads. | |
165 | virtual void | |
166 | set_thread_count(int) = 0; | |
bae7f79e ILT |
167 | |
168 | protected: | |
169 | // This is called by an implementation when a task is completed. | |
170 | void completed(Task* t, Task_locker* tl) | |
171 | { this->workqueue_->completed(t, tl); } | |
172 | ||
173 | Workqueue* get_workqueue() const | |
174 | { return this->workqueue_; } | |
175 | ||
176 | private: | |
177 | Workqueue* workqueue_; | |
178 | }; | |
179 | ||
180 | // The simple single-threaded implementation of Workqueue_runner. | |
181 | ||
182 | class Workqueue_runner_single : public Workqueue_runner | |
183 | { | |
184 | public: | |
185 | Workqueue_runner_single(Workqueue* workqueue) | |
186 | : Workqueue_runner(workqueue) | |
187 | { } | |
188 | ~Workqueue_runner_single() | |
189 | { } | |
190 | ||
fe9a4c12 ILT |
191 | void |
192 | run(Task*, Task_locker*); | |
193 | ||
194 | void | |
195 | set_thread_count(int); | |
bae7f79e ILT |
196 | }; |
197 | ||
198 | void | |
199 | Workqueue_runner_single::run(Task* t, Task_locker* tl) | |
200 | { | |
201 | t->run(this->get_workqueue()); | |
202 | this->completed(t, tl); | |
203 | } | |
204 | ||
fe9a4c12 ILT |
205 | void |
206 | Workqueue_runner_single::set_thread_count(int thread_count) | |
207 | { | |
208 | gold_assert(thread_count > 0); | |
209 | } | |
210 | ||
bae7f79e ILT |
211 | // Workqueue methods. |
212 | ||
fe9a4c12 | 213 | Workqueue::Workqueue(const General_options& options) |
bae7f79e ILT |
214 | : tasks_lock_(), |
215 | tasks_(), | |
216 | completed_lock_(), | |
217 | completed_(), | |
218 | running_(0), | |
219 | completed_condvar_(this->completed_lock_), | |
220 | cleared_blockers_(0) | |
221 | { | |
fe9a4c12 ILT |
222 | bool threads = options.threads(); |
223 | #ifndef ENABLE_THREADS | |
224 | threads = false; | |
225 | #endif | |
226 | if (!threads) | |
227 | this->runner_ = new Workqueue_runner_single(this); | |
228 | else | |
229 | gold_unreachable(); | |
bae7f79e ILT |
230 | } |
231 | ||
232 | Workqueue::~Workqueue() | |
233 | { | |
a3ad94ed ILT |
234 | gold_assert(this->tasks_.empty()); |
235 | gold_assert(this->completed_.empty()); | |
236 | gold_assert(this->running_ == 0); | |
bae7f79e ILT |
237 | } |
238 | ||
92e059d8 ILT |
239 | // Add a task to the queue. |
240 | ||
bae7f79e ILT |
241 | void |
242 | Workqueue::queue(Task* t) | |
243 | { | |
244 | Hold_lock hl(this->tasks_lock_); | |
245 | this->tasks_.push_back(t); | |
246 | } | |
247 | ||
92e059d8 ILT |
248 | // Add a task to the front of the queue. |
249 | ||
250 | void | |
251 | Workqueue::queue_front(Task* t) | |
252 | { | |
253 | Hold_lock hl(this->tasks_lock_); | |
254 | this->tasks_.push_front(t); | |
255 | } | |
256 | ||
bae7f79e ILT |
257 | // Clear the list of completed tasks. Return whether we cleared |
258 | // anything. The completed_lock_ must be held when this is called. | |
259 | ||
260 | bool | |
261 | Workqueue::clear_completed() | |
262 | { | |
263 | if (this->completed_.empty()) | |
264 | return false; | |
265 | do | |
266 | { | |
267 | delete this->completed_.front(); | |
268 | this->completed_.pop_front(); | |
269 | } | |
270 | while (!this->completed_.empty()); | |
271 | return true; | |
272 | } | |
273 | ||
274 | // Find a runnable task in TASKS, which is non-empty. Return NULL if | |
275 | // none could be found. The tasks_lock_ must be held when this is | |
276 | // called. Sets ALL_BLOCKED if all non-runnable tasks are waiting on | |
277 | // a blocker. | |
278 | ||
279 | Task* | |
280 | Workqueue::find_runnable(Task_list& tasks, bool* all_blocked) | |
281 | { | |
282 | Task* tlast = tasks.back(); | |
283 | *all_blocked = true; | |
284 | while (true) | |
285 | { | |
286 | Task* t = tasks.front(); | |
287 | tasks.pop_front(); | |
288 | ||
289 | Task::Is_runnable_type is_runnable = t->is_runnable(this); | |
290 | if (is_runnable == Task::IS_RUNNABLE) | |
291 | return t; | |
292 | ||
293 | if (is_runnable != Task::IS_BLOCKED) | |
294 | *all_blocked = false; | |
295 | ||
296 | tasks.push_back(t); | |
297 | ||
298 | if (t == tlast) | |
299 | { | |
300 | // We couldn't find any runnable task. If there are any | |
301 | // completed tasks, free their locks and try again. | |
302 | ||
303 | { | |
304 | Hold_lock hl2(this->completed_lock_); | |
305 | ||
306 | if (!this->clear_completed()) | |
307 | { | |
308 | // There had better be some tasks running, or we will | |
309 | // never find a runnable task. | |
a3ad94ed | 310 | gold_assert(this->running_ > 0); |
bae7f79e ILT |
311 | |
312 | // We couldn't find any runnable tasks, and we | |
313 | // couldn't release any locks. | |
314 | return NULL; | |
315 | } | |
316 | } | |
317 | ||
318 | // We're going around again, so recompute ALL_BLOCKED. | |
319 | *all_blocked = true; | |
320 | } | |
321 | } | |
322 | } | |
323 | ||
324 | // Process all the tasks on the workqueue. This is the main loop in | |
325 | // the linker. Note that as we process tasks, new tasks will be | |
326 | // added. | |
327 | ||
328 | void | |
329 | Workqueue::process() | |
330 | { | |
331 | while (true) | |
332 | { | |
333 | Task* t; | |
334 | bool empty; | |
335 | bool all_blocked; | |
336 | ||
337 | { | |
338 | Hold_lock hl(this->tasks_lock_); | |
339 | ||
340 | if (this->tasks_.empty()) | |
341 | { | |
342 | t = NULL; | |
343 | empty = true; | |
344 | all_blocked = false; | |
345 | } | |
346 | else | |
347 | { | |
348 | t = this->find_runnable(this->tasks_, &all_blocked); | |
349 | empty = false; | |
350 | } | |
351 | } | |
352 | ||
353 | // If T != NULL, it is a task we can run. | |
354 | // If T == NULL && empty, then there are no tasks waiting to | |
355 | // be run at this level. | |
356 | // If T == NULL && !empty, then there tasks waiting to be | |
357 | // run at this level, but they are waiting for something to | |
358 | // unlock. | |
359 | ||
360 | if (t != NULL) | |
361 | this->run(t); | |
362 | else if (!empty) | |
363 | { | |
364 | { | |
365 | Hold_lock hl(this->completed_lock_); | |
366 | ||
367 | // There must be something for us to wait for, or we won't | |
368 | // be able to make progress. | |
a3ad94ed | 369 | gold_assert(this->running_ > 0 || !this->completed_.empty()); |
bae7f79e ILT |
370 | |
371 | if (all_blocked) | |
372 | { | |
373 | this->cleared_blockers_ = 0; | |
374 | this->clear_completed(); | |
375 | while (this->cleared_blockers_ == 0) | |
376 | { | |
a3ad94ed | 377 | gold_assert(this->running_ > 0); |
bae7f79e ILT |
378 | this->completed_condvar_.wait(); |
379 | this->clear_completed(); | |
380 | } | |
381 | } | |
382 | else | |
383 | { | |
384 | if (this->running_ > 0) | |
385 | { | |
386 | // Wait for a task to finish. | |
387 | this->completed_condvar_.wait(); | |
388 | } | |
389 | this->clear_completed(); | |
390 | } | |
391 | } | |
392 | } | |
393 | else | |
394 | { | |
395 | { | |
396 | Hold_lock hl(this->completed_lock_); | |
397 | ||
398 | // If there are no running tasks, then we are done. | |
399 | if (this->running_ == 0) | |
400 | { | |
401 | this->clear_completed(); | |
402 | return; | |
403 | } | |
404 | ||
405 | // Wait for a task to finish. Then we have to loop around | |
406 | // again in case it added any new tasks before finishing. | |
407 | this->completed_condvar_.wait(); | |
408 | this->clear_completed(); | |
409 | } | |
410 | } | |
411 | } | |
412 | } | |
413 | ||
414 | // Run a task. This is always called in the main thread. | |
415 | ||
416 | void | |
417 | Workqueue::run(Task* t) | |
418 | { | |
419 | ++this->running_; | |
420 | this->runner_->run(t, t->locks(this)); | |
421 | } | |
422 | ||
423 | // This is called when a task is completed to put the locks on the | |
424 | // list to be released. We use a list because we only want the locks | |
425 | // to be released in the main thread. | |
426 | ||
427 | void | |
428 | Workqueue::completed(Task* t, Task_locker* tl) | |
429 | { | |
430 | { | |
431 | Hold_lock hl(this->completed_lock_); | |
a3ad94ed | 432 | gold_assert(this->running_ > 0); |
bae7f79e ILT |
433 | --this->running_; |
434 | this->completed_.push_back(tl); | |
435 | this->completed_condvar_.signal(); | |
436 | } | |
437 | delete t; | |
438 | } | |
439 | ||
440 | // This is called when the last task for a blocker has completed. | |
441 | // This is always called in the main thread. | |
442 | ||
443 | void | |
444 | Workqueue::cleared_blocker() | |
445 | { | |
446 | ++this->cleared_blockers_; | |
447 | } | |
448 | ||
fe9a4c12 ILT |
449 | // Set the number of threads to use for the workqueue, if we are using |
450 | // threads. | |
451 | ||
452 | void | |
453 | Workqueue::set_thread_count(int threads) | |
454 | { | |
455 | this->runner_->set_thread_count(threads); | |
456 | } | |
457 | ||
bae7f79e | 458 | } // End namespace gold. |