1 // workqueue.cc -- the workqueue for gold
11 Task_token::Task_token()
12 : is_blocker_(false), readers_(0), writer_(NULL)
16 Task_token::~Task_token()
18 assert(this->readers_ == 0 && this->writer_ == NULL);
22 Task_token::is_readable() const
24 assert(!this->is_blocker_);
25 return this->writer_ == NULL;
29 Task_token::add_reader()
31 assert(!this->is_blocker_);
32 assert(this->is_readable());
37 Task_token::remove_reader()
39 assert(!this->is_blocker_);
40 assert(this->readers_ > 0);
45 Task_token::is_writable() const
47 assert(!this->is_blocker_);
48 return this->writer_ == NULL && this->readers_ == 0;
52 Task_token::add_writer(const Task* t)
54 assert(!this->is_blocker_);
55 assert(this->is_writable());
60 Task_token::remove_writer(const Task* t)
62 assert(!this->is_blocker_);
63 assert(this->writer_ == t);
68 Task_token::has_write_lock(const Task* t)
70 assert(!this->is_blocker_);
71 return this->writer_ == t;
74 // For blockers, we just use the readers_ field.
77 Task_token::add_blocker()
79 if (this->readers_ == 0 && this->writer_ == NULL)
80 this->is_blocker_ = true;
82 assert(this->is_blocker_);
87 Task_token::remove_blocker()
89 assert(this->is_blocker_ && this->readers_ > 0);
91 return this->readers_ == 0;
95 Task_token::is_blocked() const
97 assert(this->is_blocker_ || (this->readers_ == 0 && this->writer_ == NULL));
98 return this->readers_ > 0;
101 // The Task_block_token class.
103 Task_block_token::Task_block_token(Task_token& token, Workqueue* workqueue)
104 : token_(token), workqueue_(workqueue)
106 // We must increment the block count when the task is created and
107 // put on the queue. This object is created when the task is run,
108 // so we don't increment the block count here.
109 assert(this->token_.is_blocked());
112 Task_block_token::~Task_block_token()
114 if (this->token_.remove_blocker())
116 // Tell the workqueue that a blocker was cleared. This is
117 // always called in the main thread, so no locking is required.
118 this->workqueue_->cleared_blocker();
122 // The Workqueue_runner abstract class.
124 class Workqueue_runner
127 Workqueue_runner(Workqueue* workqueue)
128 : workqueue_(workqueue)
130 virtual ~Workqueue_runner()
133 // Run a task. This is always called in the main thread.
134 virtual void run(Task*, Task_locker*) = 0;
137 // This is called by an implementation when a task is completed.
138 void completed(Task* t, Task_locker* tl)
139 { this->workqueue_->completed(t, tl); }
141 Workqueue* get_workqueue() const
142 { return this->workqueue_; }
145 Workqueue* workqueue_;
148 // The simple single-threaded implementation of Workqueue_runner.
150 class Workqueue_runner_single : public Workqueue_runner
153 Workqueue_runner_single(Workqueue* workqueue)
154 : Workqueue_runner(workqueue)
156 ~Workqueue_runner_single()
159 void run(Task*, Task_locker*);
163 Workqueue_runner_single::run(Task* t, Task_locker* tl)
165 t->run(this->get_workqueue());
166 this->completed(t, tl);
169 // Workqueue methods.
171 Workqueue::Workqueue(const General_options&)
177 completed_condvar_(this->completed_lock_),
180 // At some point we will select the specific implementation of
181 // Workqueue_runner to use based on the command line options.
182 this->runner_ = new Workqueue_runner_single(this);
185 Workqueue::~Workqueue()
187 assert(this->tasks_.empty());
188 assert(this->completed_.empty());
189 assert(this->running_ == 0);
193 Workqueue::queue(Task* t)
195 Hold_lock hl(this->tasks_lock_);
196 this->tasks_.push_back(t);
199 // Clear the list of completed tasks. Return whether we cleared
200 // anything. The completed_lock_ must be held when this is called.
203 Workqueue::clear_completed()
205 if (this->completed_.empty())
209 delete this->completed_.front();
210 this->completed_.pop_front();
212 while (!this->completed_.empty());
216 // Find a runnable task in TASKS, which is non-empty. Return NULL if
217 // none could be found. The tasks_lock_ must be held when this is
218 // called. Sets ALL_BLOCKED if all non-runnable tasks are waiting on
222 Workqueue::find_runnable(Task_list& tasks, bool* all_blocked)
224 Task* tlast = tasks.back();
228 Task* t = tasks.front();
231 Task::Is_runnable_type is_runnable = t->is_runnable(this);
232 if (is_runnable == Task::IS_RUNNABLE)
235 if (is_runnable != Task::IS_BLOCKED)
236 *all_blocked = false;
242 // We couldn't find any runnable task. If there are any
243 // completed tasks, free their locks and try again.
246 Hold_lock hl2(this->completed_lock_);
248 if (!this->clear_completed())
250 // There had better be some tasks running, or we will
251 // never find a runnable task.
252 assert(this->running_ > 0);
254 // We couldn't find any runnable tasks, and we
255 // couldn't release any locks.
260 // We're going around again, so recompute ALL_BLOCKED.
266 // Process all the tasks on the workqueue. This is the main loop in
267 // the linker. Note that as we process tasks, new tasks will be
280 Hold_lock hl(this->tasks_lock_);
282 if (this->tasks_.empty())
290 t = this->find_runnable(this->tasks_, &all_blocked);
295 // If T != NULL, it is a task we can run.
296 // If T == NULL && empty, then there are no tasks waiting to
297 // be run at this level.
298 // If T == NULL && !empty, then there tasks waiting to be
299 // run at this level, but they are waiting for something to
307 Hold_lock hl(this->completed_lock_);
309 // There must be something for us to wait for, or we won't
310 // be able to make progress.
311 assert(this->running_ > 0 || !this->completed_.empty());
315 this->cleared_blockers_ = 0;
316 this->clear_completed();
317 while (this->cleared_blockers_ == 0)
319 assert(this->running_ > 0);
320 this->completed_condvar_.wait();
321 this->clear_completed();
326 if (this->running_ > 0)
328 // Wait for a task to finish.
329 this->completed_condvar_.wait();
331 this->clear_completed();
338 Hold_lock hl(this->completed_lock_);
340 // If there are no running tasks, then we are done.
341 if (this->running_ == 0)
343 this->clear_completed();
347 // Wait for a task to finish. Then we have to loop around
348 // again in case it added any new tasks before finishing.
349 this->completed_condvar_.wait();
350 this->clear_completed();
356 // Run a task. This is always called in the main thread.
359 Workqueue::run(Task* t)
362 this->runner_->run(t, t->locks(this));
365 // This is called when a task is completed to put the locks on the
366 // list to be released. We use a list because we only want the locks
367 // to be released in the main thread.
370 Workqueue::completed(Task* t, Task_locker* tl)
373 Hold_lock hl(this->completed_lock_);
374 assert(this->running_ > 0);
376 this->completed_.push_back(tl);
377 this->completed_condvar_.signal();
382 // This is called when the last task for a blocker has completed.
383 // This is always called in the main thread.
386 Workqueue::cleared_blocker()
388 ++this->cleared_blockers_;
391 } // End namespace gold.