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.
29 #include "workqueue.h"
34 // Task_token methods.
36 Task_token::Task_token()
37 : is_blocker_(false), readers_(0), writer_(NULL
)
41 Task_token::~Task_token()
43 gold_assert(this->readers_
== 0 && this->writer_
== NULL
);
47 Task_token::is_readable() const
49 gold_assert(!this->is_blocker_
);
50 return this->writer_
== NULL
;
54 Task_token::add_reader()
56 gold_assert(!this->is_blocker_
);
57 gold_assert(this->is_readable());
62 Task_token::remove_reader()
64 gold_assert(!this->is_blocker_
);
65 gold_assert(this->readers_
> 0);
70 Task_token::is_writable() const
72 gold_assert(!this->is_blocker_
);
73 return this->writer_
== NULL
&& this->readers_
== 0;
77 Task_token::add_writer(const Task
* t
)
79 gold_assert(!this->is_blocker_
);
80 gold_assert(this->is_writable());
85 Task_token::remove_writer(const Task
* t
)
87 gold_assert(!this->is_blocker_
);
88 gold_assert(this->writer_
== t
);
93 Task_token::has_write_lock(const Task
* t
)
95 gold_assert(!this->is_blocker_
);
96 return this->writer_
== t
;
99 // For blockers, we just use the readers_ field.
102 Task_token::add_blocker()
104 if (this->readers_
== 0 && this->writer_
== NULL
)
105 this->is_blocker_
= true;
107 gold_assert(this->is_blocker_
);
112 Task_token::remove_blocker()
114 gold_assert(this->is_blocker_
&& this->readers_
> 0);
116 return this->readers_
== 0;
120 Task_token::is_blocked() const
122 gold_assert(this->is_blocker_
123 || (this->readers_
== 0 && this->writer_
== NULL
));
124 return this->readers_
> 0;
127 // The Task_block_token class.
129 Task_block_token::Task_block_token(Task_token
& token
, Workqueue
* workqueue
)
130 : token_(token
), workqueue_(workqueue
)
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.
135 gold_assert(this->token_
.is_blocked());
138 Task_block_token::~Task_block_token()
140 if (this->token_
.remove_blocker())
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();
148 // The Workqueue_runner abstract class.
150 class Workqueue_runner
153 Workqueue_runner(Workqueue
* workqueue
)
154 : workqueue_(workqueue
)
156 virtual ~Workqueue_runner()
159 // Run a task. This is always called in the main thread.
161 run(Task
*, Task_locker
*) = 0;
163 // Set the number of threads to use. This is ignored when not using
166 set_thread_count(int) = 0;
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
); }
173 Workqueue
* get_workqueue() const
174 { return this->workqueue_
; }
177 Workqueue
* workqueue_
;
180 // The simple single-threaded implementation of Workqueue_runner.
182 class Workqueue_runner_single
: public Workqueue_runner
185 Workqueue_runner_single(Workqueue
* workqueue
)
186 : Workqueue_runner(workqueue
)
188 ~Workqueue_runner_single()
192 run(Task
*, Task_locker
*);
195 set_thread_count(int);
199 Workqueue_runner_single::run(Task
* t
, Task_locker
* tl
)
201 t
->run(this->get_workqueue());
202 this->completed(t
, tl
);
206 Workqueue_runner_single::set_thread_count(int thread_count
)
208 gold_assert(thread_count
> 0);
211 // Workqueue methods.
213 Workqueue::Workqueue(const General_options
& options
)
219 completed_condvar_(this->completed_lock_
),
222 bool threads
= options
.threads();
223 #ifndef ENABLE_THREADS
227 this->runner_
= new Workqueue_runner_single(this);
232 Workqueue::~Workqueue()
234 gold_assert(this->tasks_
.empty());
235 gold_assert(this->completed_
.empty());
236 gold_assert(this->running_
== 0);
239 // Add a task to the queue.
242 Workqueue::queue(Task
* t
)
244 Hold_lock
hl(this->tasks_lock_
);
245 this->tasks_
.push_back(t
);
248 // Add a task to the front of the queue.
251 Workqueue::queue_front(Task
* t
)
253 Hold_lock
hl(this->tasks_lock_
);
254 this->tasks_
.push_front(t
);
257 // Clear the list of completed tasks. Return whether we cleared
258 // anything. The completed_lock_ must be held when this is called.
261 Workqueue::clear_completed()
263 if (this->completed_
.empty())
267 delete this->completed_
.front();
268 this->completed_
.pop_front();
270 while (!this->completed_
.empty());
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
280 Workqueue::find_runnable(Task_list
& tasks
, bool* all_blocked
)
282 Task
* tlast
= tasks
.back();
286 Task
* t
= tasks
.front();
289 Task::Is_runnable_type is_runnable
= t
->is_runnable(this);
290 if (is_runnable
== Task::IS_RUNNABLE
)
293 if (is_runnable
!= Task::IS_BLOCKED
)
294 *all_blocked
= false;
300 // We couldn't find any runnable task. If there are any
301 // completed tasks, free their locks and try again.
304 Hold_lock
hl2(this->completed_lock_
);
306 if (!this->clear_completed())
308 // There had better be some tasks running, or we will
309 // never find a runnable task.
310 gold_assert(this->running_
> 0);
312 // We couldn't find any runnable tasks, and we
313 // couldn't release any locks.
318 // We're going around again, so recompute ALL_BLOCKED.
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
338 Hold_lock
hl(this->tasks_lock_
);
340 if (this->tasks_
.empty())
348 t
= this->find_runnable(this->tasks_
, &all_blocked
);
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
365 Hold_lock
hl(this->completed_lock_
);
367 // There must be something for us to wait for, or we won't
368 // be able to make progress.
369 gold_assert(this->running_
> 0 || !this->completed_
.empty());
373 this->cleared_blockers_
= 0;
374 this->clear_completed();
375 while (this->cleared_blockers_
== 0)
377 gold_assert(this->running_
> 0);
378 this->completed_condvar_
.wait();
379 this->clear_completed();
384 if (this->running_
> 0)
386 // Wait for a task to finish.
387 this->completed_condvar_
.wait();
389 this->clear_completed();
396 Hold_lock
hl(this->completed_lock_
);
398 // If there are no running tasks, then we are done.
399 if (this->running_
== 0)
401 this->clear_completed();
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();
414 // Run a task. This is always called in the main thread.
417 Workqueue::run(Task
* t
)
420 this->runner_
->run(t
, t
->locks(this));
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.
428 Workqueue::completed(Task
* t
, Task_locker
* tl
)
431 Hold_lock
hl(this->completed_lock_
);
432 gold_assert(this->running_
> 0);
434 this->completed_
.push_back(tl
);
435 this->completed_condvar_
.signal();
440 // This is called when the last task for a blocker has completed.
441 // This is always called in the main thread.
444 Workqueue::cleared_blocker()
446 ++this->cleared_blockers_
;
449 // Set the number of threads to use for the workqueue, if we are using
453 Workqueue::set_thread_count(int threads
)
455 this->runner_
->set_thread_count(threads
);
458 } // End namespace gold.