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.