1 // workqueue.cc -- the workqueue for gold
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.
26 #include "workqueue.h"
27 #include "workqueue-internal.h"
32 // Task_token methods.
34 Task_token::Task_token()
35 : is_blocker_(false), readers_(0), writer_(NULL
)
39 Task_token::~Task_token()
41 gold_assert(this->readers_
== 0 && this->writer_
== NULL
);
45 Task_token::is_readable() const
47 gold_assert(!this->is_blocker_
);
48 return this->writer_
== NULL
;
52 Task_token::add_reader()
54 gold_assert(!this->is_blocker_
);
55 gold_assert(this->is_readable());
60 Task_token::remove_reader()
62 gold_assert(!this->is_blocker_
);
63 gold_assert(this->readers_
> 0);
68 Task_token::is_writable() const
70 gold_assert(!this->is_blocker_
);
71 return this->writer_
== NULL
&& this->readers_
== 0;
75 Task_token::add_writer(const Task
* t
)
77 gold_assert(!this->is_blocker_
);
78 gold_assert(this->is_writable());
83 Task_token::remove_writer(const Task
* t
)
85 gold_assert(!this->is_blocker_
);
86 gold_assert(this->writer_
== t
);
91 Task_token::has_write_lock(const Task
* t
)
93 gold_assert(!this->is_blocker_
);
94 return this->writer_
== t
;
97 // For blockers, we just use the readers_ field.
100 Task_token::add_blocker()
102 if (this->readers_
== 0 && this->writer_
== NULL
)
103 this->is_blocker_
= true;
105 gold_assert(this->is_blocker_
);
110 Task_token::remove_blocker()
112 gold_assert(this->is_blocker_
&& this->readers_
> 0);
114 return this->readers_
== 0;
118 Task_token::is_blocked() const
120 gold_assert(this->is_blocker_
121 || (this->readers_
== 0 && this->writer_
== NULL
));
122 return this->readers_
> 0;
125 // The Task_block_token class.
127 Task_block_token::Task_block_token(Task_token
& token
, Workqueue
* workqueue
)
128 : token_(token
), workqueue_(workqueue
)
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.
133 gold_assert(this->token_
.is_blocked());
136 Task_block_token::~Task_block_token()
138 if (this->token_
.remove_blocker())
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();
146 // The simple single-threaded implementation of Workqueue_runner.
148 class Workqueue_runner_single
: public Workqueue_runner
151 Workqueue_runner_single(Workqueue
* workqueue
)
152 : Workqueue_runner(workqueue
)
154 ~Workqueue_runner_single()
158 run(Task
*, Task_locker
*);
161 set_thread_count(int);
165 Workqueue_runner_single::run(Task
* t
, Task_locker
* tl
)
167 t
->run(this->get_workqueue());
168 this->completed(t
, tl
);
172 Workqueue_runner_single::set_thread_count(int thread_count
)
174 gold_assert(thread_count
> 0);
177 // Workqueue methods.
179 Workqueue::Workqueue(const General_options
& options
)
187 completed_condvar_(this->completed_lock_
),
188 cleared_blockers_(0),
189 desired_thread_count_(1)
191 bool threads
= options
.threads();
192 #ifndef ENABLE_THREADS
196 this->runner_
= new Workqueue_runner_single(this);
199 #ifdef ENABLE_THREADS
200 this->runner_
= new Workqueue_runner_threadpool(this);
207 Workqueue::~Workqueue()
209 gold_assert(this->first_tasks_
.empty());
210 gold_assert(this->tasks_
.empty());
211 gold_assert(this->completed_
.empty());
212 gold_assert(this->running_
== 0);
215 // Add a task to the queue.
218 Workqueue::queue(Task
* t
)
221 Hold_lock
hl(this->tasks_lock_
);
222 this->tasks_
.push_back(t
);
225 Hold_lock
hl(this->completed_lock_
);
230 // Add a task to the front of the queue.
233 Workqueue::queue_front(Task
* t
)
236 Hold_lock
hl(this->tasks_lock_
);
237 this->first_tasks_
.push_front(t
);
240 Hold_lock
hl(this->completed_lock_
);
245 // Clear the list of completed tasks. Return whether we cleared
246 // anything. The completed_lock_ must be held when this is called.
249 Workqueue::clear_completed()
251 if (this->completed_
.empty())
255 delete this->completed_
.front();
256 this->completed_
.pop_front();
258 while (!this->completed_
.empty());
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
268 Workqueue::find_runnable(Task_list
* tasks
, bool* all_blocked
)
270 Task
* tlast
= tasks
->back();
278 Task::Is_runnable_type is_runnable
= t
->is_runnable(this);
279 if (is_runnable
== Task::IS_RUNNABLE
)
282 Hold_lock
hl(this->completed_lock_
);
289 if (is_runnable
!= Task::IS_BLOCKED
)
290 *all_blocked
= false;
296 // We couldn't find any runnable task.
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
313 // Don't start more tasks than desired.
315 Hold_lock
hl(this->completed_lock_
);
317 this->clear_completed();
318 while (this->running_
>= this->desired_thread_count_
)
320 this->completed_condvar_
.wait();
321 this->clear_completed();
326 Hold_lock
hl(this->tasks_lock_
);
329 bool all_blocked_first
;
330 if (this->first_tasks_
.empty())
335 all_blocked_first
= false;
339 t
= this->find_runnable(&this->first_tasks_
, &all_blocked_first
);
346 if (this->tasks_
.empty())
350 t
= this->find_runnable(&this->tasks_
, &all_blocked
);
351 if (!first_empty
&& !all_blocked_first
)
358 // If T != NULL, it is a task we can run.
359 // If T == NULL && empty, then there are no tasks waiting to
361 // If T == NULL && !empty, then there tasks waiting to be
362 // run, but they are waiting for something to unlock.
369 Hold_lock
hl(this->completed_lock_
);
371 // There must be something for us to wait for, or we won't
372 // be able to make progress.
373 gold_assert(this->running_
> 0 || !this->completed_
.empty());
377 this->cleared_blockers_
= 0;
378 int queued
= this->queued_
;
379 this->clear_completed();
380 while (this->cleared_blockers_
== 0
381 && queued
== this->queued_
)
383 if (this->running_
<= 0)
385 this->show_queued_tasks();
388 this->completed_condvar_
.wait();
389 this->clear_completed();
394 if (this->running_
> 0)
396 // Wait for a task to finish.
397 this->completed_condvar_
.wait();
399 this->clear_completed();
406 Hold_lock
hl(this->completed_lock_
);
408 // If there are no running tasks, then we are done.
409 if (this->running_
== 0)
411 this->clear_completed();
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();
424 // Run a task. This is always called in the main thread.
427 Workqueue::run(Task
* t
)
429 gold_debug(DEBUG_TASK
, "starting task %s", t
->name().c_str());
432 Hold_lock
hl(this->completed_lock_
);
435 this->runner_
->run(t
, t
->locks(this));
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.
443 Workqueue::completed(Task
* t
, Task_locker
* tl
)
445 gold_debug(DEBUG_TASK
, "completed task %s", t
->name().c_str());
448 Hold_lock
hl(this->completed_lock_
);
449 gold_assert(this->running_
> 0);
451 this->completed_
.push_back(tl
);
452 this->completed_condvar_
.signal();
458 // This is called when the last task for a blocker has completed.
459 // This is always called in the main thread.
462 Workqueue::cleared_blocker()
464 ++this->cleared_blockers_
;
467 // Set the number of threads to use for the workqueue, if we are using
471 Workqueue::set_thread_count(int threads
)
473 gold_assert(threads
> 0);
474 this->desired_thread_count_
= threads
;
475 this->runner_
->set_thread_count(threads
);
478 // Dump the list of queued tasks and their current state, for
479 // debugging purposes.
482 Workqueue::show_queued_tasks()
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();
490 fprintf(stderr
, " %s ", (*p
)->name().c_str());
491 switch ((*p
)->is_runnable(this))
493 case Task::IS_RUNNABLE
:
494 fprintf(stderr
, "runnable");
496 case Task::IS_BLOCKED
:
497 fprintf(stderr
, "blocked");
499 case Task::IS_LOCKED
:
500 fprintf(stderr
, "locked");
509 } // End namespace gold.