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