gas/testsuite/
[binutils.git] / gold / workqueue.cc
blob647daf2ed6ee9a468a2530fe5906aacabd6ccfb7
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.
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 // Remove and return the first Task waiting for this lock to be
54 // released.
56 inline Task*
57 Task_list::pop_front()
59 Task* ret = this->head_;
60 if (ret != NULL)
62 if (ret == this->tail_)
64 gold_assert(ret->list_next() == NULL);
65 this->head_ = NULL;
66 this->tail_ = NULL;
68 else
70 this->head_ = ret->list_next();
71 gold_assert(this->head_ != NULL);
72 ret->clear_list_next();
75 return ret;
78 // The simple single-threaded implementation of Workqueue_threader.
80 class Workqueue_threader_single : public Workqueue_threader
82 public:
83 Workqueue_threader_single(Workqueue* workqueue)
84 : Workqueue_threader(workqueue)
85 { }
86 ~Workqueue_threader_single()
87 { }
89 void
90 set_thread_count(int thread_count)
91 { gold_assert(thread_count > 0); }
93 bool
94 should_cancel_thread()
95 { return false; }
98 // Workqueue methods.
100 Workqueue::Workqueue(const General_options& options)
101 : lock_(),
102 first_tasks_(),
103 tasks_(),
104 running_(0),
105 waiting_(0),
106 condvar_(this->lock_),
107 threader_(NULL)
109 bool threads = options.threads();
110 #ifndef ENABLE_THREADS
111 threads = false;
112 #endif
113 if (!threads)
114 this->threader_ = new Workqueue_threader_single(this);
115 else
117 #ifdef ENABLE_THREADS
118 this->threader_ = new Workqueue_threader_threadpool(this);
119 #else
120 gold_unreachable();
121 #endif
125 Workqueue::~Workqueue()
129 // Add a task to the end of a specific queue, or put it on the list
130 // waiting for a Token.
132 void
133 Workqueue::add_to_queue(Task_list* queue, Task* t)
135 Hold_lock hl(this->lock_);
137 Task_token* token = t->is_runnable();
138 if (token != NULL)
140 token->add_waiting(t);
141 ++this->waiting_;
143 else
145 queue->push_back(t);
146 // Tell any waiting thread that there is work to do.
147 this->condvar_.signal();
151 // Add a task to the queue.
153 void
154 Workqueue::queue(Task* t)
156 this->add_to_queue(&this->tasks_, t);
159 // Add a task to the front of the queue.
161 void
162 Workqueue::queue_front(Task* t)
164 t->set_should_run_soon();
165 this->add_to_queue(&this->first_tasks_, t);
168 // Return whether to cancel the current thread.
170 inline bool
171 Workqueue::should_cancel_thread()
173 return this->threader_->should_cancel_thread();
176 // Find a runnable task in TASKS. Return NULL if none could be found.
177 // If we find a Task waiting for a Token, add it to the list for that
178 // Token. The workqueue lock must be held when this is called.
180 Task*
181 Workqueue::find_runnable_in_list(Task_list* tasks)
183 Task* t;
184 while ((t = tasks->pop_front()) != NULL)
186 Task_token* token = t->is_runnable();
188 if (token == NULL)
189 return t;
191 token->add_waiting(t);
192 ++this->waiting_;
195 // We couldn't find any runnable task.
196 return NULL;
199 // Find a runnable task. Return NULL if none could be found. The
200 // workqueue lock must be held when this is called.
202 Task*
203 Workqueue::find_runnable()
205 Task* t = this->find_runnable_in_list(&this->first_tasks_);
206 if (t == NULL)
207 t = this->find_runnable_in_list(&this->tasks_);
208 return t;
211 // Find a runnable a task, and wait until we find one. Return NULL if
212 // we should exit. The workqueue lock must be held when this is
213 // called.
215 Task*
216 Workqueue::find_runnable_or_wait(int thread_number)
218 Task* t = this->find_runnable();
220 while (t == NULL)
222 if (this->running_ == 0
223 && this->first_tasks_.empty()
224 && this->tasks_.empty())
226 // Kick all the threads to make them exit.
227 this->condvar_.broadcast();
229 gold_assert(this->waiting_ == 0);
230 return NULL;
233 if (this->should_cancel_thread())
234 return NULL;
236 gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
238 this->condvar_.wait();
240 gold_debug(DEBUG_TASK, "%3d awake", thread_number);
242 t = this->find_runnable();
245 return t;
248 // Find and run tasks. If we can't find a runnable task, wait for one
249 // to become available. If we run a task, and it frees up another
250 // runnable task, then run that one too. This returns true if we
251 // should look for another task, false if we are cancelling this
252 // thread.
254 bool
255 Workqueue::find_and_run_task(int thread_number)
257 Task* t;
258 Task_locker tl;
261 Hold_lock hl(this->lock_);
263 // Find a runnable task.
264 t = this->find_runnable_or_wait(thread_number);
266 if (t == NULL)
267 return false;
269 // Get the locks for the task. This must be called while we are
270 // still holding the Workqueue lock.
271 t->locks(&tl);
273 ++this->running_;
276 while (t != NULL)
278 gold_debug(DEBUG_TASK, "%3d running task %s", thread_number,
279 t->name().c_str());
281 t->run(this);
283 gold_debug(DEBUG_TASK, "%3d completed task %s", thread_number,
284 t->name().c_str());
286 Task* next;
288 Hold_lock hl(this->lock_);
290 --this->running_;
292 // Release the locks for the task. This must be done with the
293 // workqueue lock held. Get the next Task to run if any.
294 next = this->release_locks(t, &tl);
296 if (next == NULL)
297 next = this->find_runnable();
299 // If we have another Task to run, get the Locks. This must
300 // be called while we are still holding the Workqueue lock.
301 if (next != NULL)
303 tl.clear();
304 next->locks(&tl);
306 ++this->running_;
310 // We are done with this task.
311 delete t;
313 t = next;
316 return true;
319 // Handle the return value of release_locks, and get tasks ready to
320 // run.
322 // 1) If T is not runnable, queue it on the appropriate token.
324 // 2) Otherwise, T is runnable. If *PRET is not NULL, then we have
325 // already decided which Task to run next. Add T to the list of
326 // runnable tasks, and signal another thread.
328 // 3) Otherwise, *PRET is NULL. If IS_BLOCKER is false, then T was
329 // waiting on a write lock. We can grab that lock now, so we run T
330 // now.
332 // 4) Otherwise, IS_BLOCKER is true. If we should run T soon, then
333 // run it now.
335 // 5) Otherwise, check whether there are other tasks to run. If there
336 // are, then we generally get a better ordering if we run those tasks
337 // now, before T. A typical example is tasks waiting on the Dirsearch
338 // blocker. We don't want to run those tasks right away just because
339 // the Dirsearch was unblocked.
341 // 6) Otherwise, there are no other tasks to run, so we might as well
342 // run this one now.
344 // This function must be called with the Workqueue lock held.
346 // Return true if we set *PRET to T, false otherwise.
348 bool
349 Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)
351 Task_token* token = t->is_runnable();
353 if (token != NULL)
355 token->add_waiting(t);
356 ++this->waiting_;
357 return false;
360 bool should_queue = false;
361 bool should_return = false;
363 if (*pret != NULL)
364 should_queue = true;
365 else if (!is_blocker)
366 should_return = true;
367 else if (t->should_run_soon())
368 should_return = true;
369 else if (!this->first_tasks_.empty() || !this->tasks_.empty())
370 should_queue = true;
371 else
372 should_return = true;
374 if (should_return)
376 gold_assert(*pret == NULL);
377 *pret = t;
378 return true;
380 else if (should_queue)
382 if (t->should_run_soon())
383 this->first_tasks_.push_back(t);
384 else
385 this->tasks_.push_back(t);
386 this->condvar_.signal();
387 return false;
390 gold_unreachable();
393 // Release the locks associated with a Task. Return the first
394 // runnable Task that we find. If we find more runnable tasks, add
395 // them to the run queue and signal any other threads. This must be
396 // called with the Workqueue lock held.
398 Task*
399 Workqueue::release_locks(Task* t, Task_locker* tl)
401 Task* ret = NULL;
402 for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)
404 Task_token* token = *p;
405 if (token->is_blocker())
407 if (token->remove_blocker())
409 // The token has been unblocked. Every waiting Task may
410 // now be runnable.
411 Task* t;
412 while ((t = token->remove_first_waiting()) != NULL)
414 --this->waiting_;
415 this->return_or_queue(t, true, &ret);
419 else
421 token->remove_writer(t);
423 // One more waiting Task may now be runnable. If we are
424 // going to run it next, we can stop. Otherwise we need to
425 // move all the Tasks to the runnable queue, to avoid a
426 // potential deadlock if the locking status changes before
427 // we run the next thread.
428 Task* t;
429 while ((t = token->remove_first_waiting()) != NULL)
431 --this->waiting_;
432 if (this->return_or_queue(t, false, &ret))
433 break;
437 return ret;
440 // Process all the tasks on the workqueue. Keep going until the
441 // workqueue is empty, or until we have been told to exit. This
442 // function is called by all threads.
444 void
445 Workqueue::process(int thread_number)
447 while (this->find_and_run_task(thread_number))
451 // Set the number of threads to use for the workqueue, if we are using
452 // threads.
454 void
455 Workqueue::set_thread_count(int threads)
457 Hold_lock hl(this->lock_);
459 this->threader_->set_thread_count(threads);
460 // Wake up all the threads, since something has changed.
461 this->condvar_.broadcast();
464 } // End namespace gold.