daily update
[binutils.git] / gold / workqueue.cc
blob42182eabfb38b52b27bb545085564dd8d366b078
1 // workqueue.cc -- the workqueue for gold
3 // Copyright 2006, 2007, 2008 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.
23 #include "gold.h"
25 #include "debug.h"
26 #include "options.h"
27 #include "workqueue.h"
28 #include "workqueue-internal.h"
30 namespace gold
33 // Class Task_list.
35 // Add T to the end of the list.
37 inline void
38 Task_list::push_back(Task* t)
40 gold_assert(t->list_next() == NULL);
41 if (this->head_ == NULL)
43 this->head_ = t;
44 this->tail_ = t;
46 else
48 this->tail_->set_list_next(t);
49 this->tail_ = t;
53 // Add T to the front of the list.
55 inline void
56 Task_list::push_front(Task* t)
58 gold_assert(t->list_next() == NULL);
59 if (this->head_ == NULL)
61 this->head_ = t;
62 this->tail_ = t;
64 else
66 t->set_list_next(this->head_);
67 this->head_ = t;
71 // Remove and return the first Task waiting for this lock to be
72 // released.
74 inline Task*
75 Task_list::pop_front()
77 Task* ret = this->head_;
78 if (ret != NULL)
80 if (ret == this->tail_)
82 gold_assert(ret->list_next() == NULL);
83 this->head_ = NULL;
84 this->tail_ = NULL;
86 else
88 this->head_ = ret->list_next();
89 gold_assert(this->head_ != NULL);
90 ret->clear_list_next();
93 return ret;
96 // The simple single-threaded implementation of Workqueue_threader.
98 class Workqueue_threader_single : public Workqueue_threader
100 public:
101 Workqueue_threader_single(Workqueue* workqueue)
102 : Workqueue_threader(workqueue)
104 ~Workqueue_threader_single()
107 void
108 set_thread_count(int thread_count)
109 { gold_assert(thread_count > 0); }
111 bool
112 should_cancel_thread()
113 { return false; }
116 // Workqueue methods.
118 Workqueue::Workqueue(const General_options& options)
119 : lock_(),
120 first_tasks_(),
121 tasks_(),
122 running_(0),
123 waiting_(0),
124 condvar_(this->lock_),
125 threader_(NULL)
127 bool threads = options.threads();
128 #ifndef ENABLE_THREADS
129 threads = false;
130 #endif
131 if (!threads)
132 this->threader_ = new Workqueue_threader_single(this);
133 else
135 #ifdef ENABLE_THREADS
136 this->threader_ = new Workqueue_threader_threadpool(this);
137 #else
138 gold_unreachable();
139 #endif
143 Workqueue::~Workqueue()
147 // Add a task to the end of a specific queue, or put it on the list
148 // waiting for a Token.
150 void
151 Workqueue::add_to_queue(Task_list* queue, Task* t, bool front)
153 Hold_lock hl(this->lock_);
155 Task_token* token = t->is_runnable();
156 if (token != NULL)
158 if (front)
159 token->add_waiting_front(t);
160 else
161 token->add_waiting(t);
162 ++this->waiting_;
164 else
166 if (front)
167 queue->push_front(t);
168 else
169 queue->push_back(t);
170 // Tell any waiting thread that there is work to do.
171 this->condvar_.signal();
175 // Add a task to the queue.
177 void
178 Workqueue::queue(Task* t)
180 this->add_to_queue(&this->tasks_, t, false);
183 // Queue a task which should run soon.
185 void
186 Workqueue::queue_soon(Task* t)
188 t->set_should_run_soon();
189 this->add_to_queue(&this->first_tasks_, t, false);
192 // Queue a task which should run next.
194 void
195 Workqueue::queue_next(Task* t)
197 t->set_should_run_soon();
198 this->add_to_queue(&this->first_tasks_, t, true);
201 // Return whether to cancel the current thread.
203 inline bool
204 Workqueue::should_cancel_thread()
206 return this->threader_->should_cancel_thread();
209 // Find a runnable task in TASKS. Return NULL if none could be found.
210 // If we find a Task waiting for a Token, add it to the list for that
211 // Token. The workqueue lock must be held when this is called.
213 Task*
214 Workqueue::find_runnable_in_list(Task_list* tasks)
216 Task* t;
217 while ((t = tasks->pop_front()) != NULL)
219 Task_token* token = t->is_runnable();
221 if (token == NULL)
222 return t;
224 token->add_waiting(t);
225 ++this->waiting_;
228 // We couldn't find any runnable task.
229 return NULL;
232 // Find a runnable task. Return NULL if none could be found. The
233 // workqueue lock must be held when this is called.
235 Task*
236 Workqueue::find_runnable()
238 Task* t = this->find_runnable_in_list(&this->first_tasks_);
239 if (t == NULL)
240 t = this->find_runnable_in_list(&this->tasks_);
241 return t;
244 // Find a runnable a task, and wait until we find one. Return NULL if
245 // we should exit. The workqueue lock must be held when this is
246 // called.
248 Task*
249 Workqueue::find_runnable_or_wait(int thread_number)
251 Task* t = this->find_runnable();
253 while (t == NULL)
255 if (this->running_ == 0
256 && this->first_tasks_.empty()
257 && this->tasks_.empty())
259 // Kick all the threads to make them exit.
260 this->condvar_.broadcast();
262 gold_assert(this->waiting_ == 0);
263 return NULL;
266 if (this->should_cancel_thread())
267 return NULL;
269 gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
271 this->condvar_.wait();
273 gold_debug(DEBUG_TASK, "%3d awake", thread_number);
275 t = this->find_runnable();
278 return t;
281 // Find and run tasks. If we can't find a runnable task, wait for one
282 // to become available. If we run a task, and it frees up another
283 // runnable task, then run that one too. This returns true if we
284 // should look for another task, false if we are cancelling this
285 // thread.
287 bool
288 Workqueue::find_and_run_task(int thread_number)
290 Task* t;
291 Task_locker tl;
294 Hold_lock hl(this->lock_);
296 // Find a runnable task.
297 t = this->find_runnable_or_wait(thread_number);
299 if (t == NULL)
300 return false;
302 // Get the locks for the task. This must be called while we are
303 // still holding the Workqueue lock.
304 t->locks(&tl);
306 ++this->running_;
309 while (t != NULL)
311 gold_debug(DEBUG_TASK, "%3d running task %s", thread_number,
312 t->name().c_str());
314 t->run(this);
316 gold_debug(DEBUG_TASK, "%3d completed task %s", thread_number,
317 t->name().c_str());
319 Task* next;
321 Hold_lock hl(this->lock_);
323 --this->running_;
325 // Release the locks for the task. This must be done with the
326 // workqueue lock held. Get the next Task to run if any.
327 next = this->release_locks(t, &tl);
329 if (next == NULL)
330 next = this->find_runnable();
332 // If we have another Task to run, get the Locks. This must
333 // be called while we are still holding the Workqueue lock.
334 if (next != NULL)
336 tl.clear();
337 next->locks(&tl);
339 ++this->running_;
343 // We are done with this task.
344 delete t;
346 t = next;
349 return true;
352 // Handle the return value of release_locks, and get tasks ready to
353 // run.
355 // 1) If T is not runnable, queue it on the appropriate token.
357 // 2) Otherwise, T is runnable. If *PRET is not NULL, then we have
358 // already decided which Task to run next. Add T to the list of
359 // runnable tasks, and signal another thread.
361 // 3) Otherwise, *PRET is NULL. If IS_BLOCKER is false, then T was
362 // waiting on a write lock. We can grab that lock now, so we run T
363 // now.
365 // 4) Otherwise, IS_BLOCKER is true. If we should run T soon, then
366 // run it now.
368 // 5) Otherwise, check whether there are other tasks to run. If there
369 // are, then we generally get a better ordering if we run those tasks
370 // now, before T. A typical example is tasks waiting on the Dirsearch
371 // blocker. We don't want to run those tasks right away just because
372 // the Dirsearch was unblocked.
374 // 6) Otherwise, there are no other tasks to run, so we might as well
375 // run this one now.
377 // This function must be called with the Workqueue lock held.
379 // Return true if we set *PRET to T, false otherwise.
381 bool
382 Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)
384 Task_token* token = t->is_runnable();
386 if (token != NULL)
388 token->add_waiting(t);
389 ++this->waiting_;
390 return false;
393 bool should_queue = false;
394 bool should_return = false;
396 if (*pret != NULL)
397 should_queue = true;
398 else if (!is_blocker)
399 should_return = true;
400 else if (t->should_run_soon())
401 should_return = true;
402 else if (!this->first_tasks_.empty() || !this->tasks_.empty())
403 should_queue = true;
404 else
405 should_return = true;
407 if (should_return)
409 gold_assert(*pret == NULL);
410 *pret = t;
411 return true;
413 else if (should_queue)
415 if (t->should_run_soon())
416 this->first_tasks_.push_back(t);
417 else
418 this->tasks_.push_back(t);
419 this->condvar_.signal();
420 return false;
423 gold_unreachable();
426 // Release the locks associated with a Task. Return the first
427 // runnable Task that we find. If we find more runnable tasks, add
428 // them to the run queue and signal any other threads. This must be
429 // called with the Workqueue lock held.
431 Task*
432 Workqueue::release_locks(Task* t, Task_locker* tl)
434 Task* ret = NULL;
435 for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)
437 Task_token* token = *p;
438 if (token->is_blocker())
440 if (token->remove_blocker())
442 // The token has been unblocked. Every waiting Task may
443 // now be runnable.
444 Task* t;
445 while ((t = token->remove_first_waiting()) != NULL)
447 --this->waiting_;
448 this->return_or_queue(t, true, &ret);
452 else
454 token->remove_writer(t);
456 // One more waiting Task may now be runnable. If we are
457 // going to run it next, we can stop. Otherwise we need to
458 // move all the Tasks to the runnable queue, to avoid a
459 // potential deadlock if the locking status changes before
460 // we run the next thread.
461 Task* t;
462 while ((t = token->remove_first_waiting()) != NULL)
464 --this->waiting_;
465 if (this->return_or_queue(t, false, &ret))
466 break;
470 return ret;
473 // Process all the tasks on the workqueue. Keep going until the
474 // workqueue is empty, or until we have been told to exit. This
475 // function is called by all threads.
477 void
478 Workqueue::process(int thread_number)
480 while (this->find_and_run_task(thread_number))
484 // Set the number of threads to use for the workqueue, if we are using
485 // threads.
487 void
488 Workqueue::set_thread_count(int threads)
490 Hold_lock hl(this->lock_);
492 this->threader_->set_thread_count(threads);
493 // Wake up all the threads, since something has changed.
494 this->condvar_.broadcast();
497 } // End namespace gold.