Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / binutils-2.22 / gold / workqueue.cc
1 // workqueue.cc -- the workqueue for gold
2
3 // Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
4 // Written by Ian Lance Taylor <iant@google.com>.
5
6 // This file is part of gold.
7
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.
12
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.
17
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.
22
23 #include "gold.h"
24
25 #include "debug.h"
26 #include "options.h"
27 #include "timer.h"
28 #include "workqueue.h"
29 #include "workqueue-internal.h"
30
31 namespace gold
32 {
33
34 // Class Task_list.
35
36 // Add T to the end of the list.
37
38 inline void
39 Task_list::push_back(Task* t)
40 {
41   gold_assert(t->list_next() == NULL);
42   if (this->head_ == NULL)
43     {
44       this->head_ = t;
45       this->tail_ = t;
46     }
47   else
48     {
49       this->tail_->set_list_next(t);
50       this->tail_ = t;
51     }
52 }
53
54 // Add T to the front of the list.
55
56 inline void
57 Task_list::push_front(Task* t)
58 {
59   gold_assert(t->list_next() == NULL);
60   if (this->head_ == NULL)
61     {
62       this->head_ = t;
63       this->tail_ = t;
64     }
65   else
66     {
67       t->set_list_next(this->head_);
68       this->head_ = t;
69     }
70 }
71
72 // Remove and return the first Task waiting for this lock to be
73 // released.
74
75 inline Task*
76 Task_list::pop_front()
77 {
78   Task* ret = this->head_;
79   if (ret != NULL)
80     {
81       if (ret == this->tail_)
82         {
83           gold_assert(ret->list_next() == NULL);
84           this->head_ = NULL;
85           this->tail_ = NULL;
86         }
87       else
88         {
89           this->head_ = ret->list_next();
90           gold_assert(this->head_ != NULL);
91           ret->clear_list_next();
92         }
93     }
94   return ret;
95 }
96
97 // The simple single-threaded implementation of Workqueue_threader.
98
99 class Workqueue_threader_single : public Workqueue_threader
100 {
101  public:
102   Workqueue_threader_single(Workqueue* workqueue)
103     : Workqueue_threader(workqueue)
104   { }
105   ~Workqueue_threader_single()
106   { }
107
108   void
109   set_thread_count(int thread_count)
110   { gold_assert(thread_count > 0); }
111
112   bool
113   should_cancel_thread(int)
114   { return false; }
115 };
116
117 // Workqueue methods.
118
119 Workqueue::Workqueue(const General_options& options)
120   : lock_(),
121     first_tasks_(),
122     tasks_(),
123     running_(0),
124     waiting_(0),
125     condvar_(this->lock_),
126     threader_(NULL)
127 {
128   bool threads = options.threads();
129 #ifndef ENABLE_THREADS
130   threads = false;
131 #endif
132   if (!threads)
133     this->threader_ = new Workqueue_threader_single(this);
134   else
135     {
136 #ifdef ENABLE_THREADS
137       this->threader_ = new Workqueue_threader_threadpool(this);
138 #else
139       gold_unreachable();
140 #endif
141     }
142 }
143
144 Workqueue::~Workqueue()
145 {
146 }
147
148 // Add a task to the end of a specific queue, or put it on the list
149 // waiting for a Token.
150
151 void
152 Workqueue::add_to_queue(Task_list* queue, Task* t, bool front)
153 {
154   Hold_lock hl(this->lock_);
155
156   Task_token* token = t->is_runnable();
157   if (token != NULL)
158     {
159       if (front)
160         token->add_waiting_front(t);
161       else
162         token->add_waiting(t);
163       ++this->waiting_;
164     }
165   else
166     {
167       if (front)
168         queue->push_front(t);
169       else
170         queue->push_back(t);
171       // Tell any waiting thread that there is work to do.
172       this->condvar_.signal();
173     }
174 }
175
176 // Add a task to the queue.
177
178 void
179 Workqueue::queue(Task* t)
180 {
181   this->add_to_queue(&this->tasks_, t, false);
182 }
183
184 // Queue a task which should run soon.
185
186 void
187 Workqueue::queue_soon(Task* t)
188 {
189   t->set_should_run_soon();
190   this->add_to_queue(&this->first_tasks_, t, false);
191 }
192
193 // Queue a task which should run next.
194
195 void
196 Workqueue::queue_next(Task* t)
197 {
198   t->set_should_run_soon();
199   this->add_to_queue(&this->first_tasks_, t, true);
200 }
201
202 // Return whether to cancel the current thread.
203
204 inline bool
205 Workqueue::should_cancel_thread(int thread_number)
206 {
207   return this->threader_->should_cancel_thread(thread_number);
208 }
209
210 // Find a runnable task in TASKS.  Return NULL if none could be found.
211 // If we find a Task waiting for a Token, add it to the list for that
212 // Token.  The workqueue lock must be held when this is called.
213
214 Task*
215 Workqueue::find_runnable_in_list(Task_list* tasks)
216 {
217   Task* t;
218   while ((t = tasks->pop_front()) != NULL)
219     {
220       Task_token* token = t->is_runnable();
221
222       if (token == NULL)
223         return t;
224
225       token->add_waiting(t);
226       ++this->waiting_;
227     }
228
229   // We couldn't find any runnable task.
230   return NULL;
231 }
232
233 // Find a runnable task.  Return NULL if none could be found.  The
234 // workqueue lock must be held when this is called.
235
236 Task*
237 Workqueue::find_runnable()
238 {
239   Task* t = this->find_runnable_in_list(&this->first_tasks_);
240   if (t == NULL)
241     t = this->find_runnable_in_list(&this->tasks_);
242   return t;
243 }
244
245 // Find a runnable a task, and wait until we find one.  Return NULL if
246 // we should exit.  The workqueue lock must be held when this is
247 // called.
248
249 Task*
250 Workqueue::find_runnable_or_wait(int thread_number)
251 {
252   Task* t = this->find_runnable();
253
254   while (t == NULL)
255     {
256       if (this->running_ == 0
257           && this->first_tasks_.empty()
258           && this->tasks_.empty())
259         {
260           // Kick all the threads to make them exit.
261           this->condvar_.broadcast();
262
263           gold_assert(this->waiting_ == 0);
264           return NULL;
265         }
266
267       if (this->should_cancel_thread(thread_number))
268         return NULL;
269
270       gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
271
272       this->condvar_.wait();
273
274       gold_debug(DEBUG_TASK, "%3d awake", thread_number);
275
276       t = this->find_runnable();
277     }
278
279   return t;
280 }
281
282 // Find and run tasks.  If we can't find a runnable task, wait for one
283 // to become available.  If we run a task, and it frees up another
284 // runnable task, then run that one too.  This returns true if we
285 // should look for another task, false if we are cancelling this
286 // thread.
287
288 bool
289 Workqueue::find_and_run_task(int thread_number)
290 {
291   Task* t;
292   Task_locker tl;
293
294   {
295     Hold_lock hl(this->lock_);
296
297     // Find a runnable task.
298     t = this->find_runnable_or_wait(thread_number);
299
300     if (t == NULL)
301       return false;
302
303     // Get the locks for the task.  This must be called while we are
304     // still holding the Workqueue lock.
305     t->locks(&tl);
306
307     ++this->running_;
308   }
309
310   while (t != NULL)
311     {
312       gold_debug(DEBUG_TASK, "%3d running   task %s", thread_number,
313                  t->name().c_str());
314
315       Timer timer;
316       if (is_debugging_enabled(DEBUG_TASK))
317         timer.start();
318
319       t->run(this);
320
321       if (is_debugging_enabled(DEBUG_TASK))
322         {
323           Timer::TimeStats elapsed = timer.get_elapsed_time();
324
325           gold_debug(DEBUG_TASK,
326                      "%3d completed task %s "
327                      "(user: %ld.%06ld sys: %ld.%06ld wall: %ld.%06ld)",
328                      thread_number,  t->name().c_str(),
329                      elapsed.user / 1000, (elapsed.user % 1000) * 1000,
330                      elapsed.sys / 1000, (elapsed.sys % 1000) * 1000,
331                      elapsed.wall / 1000, (elapsed.wall % 1000) * 1000);
332         }
333
334       Task* next;
335       {
336         Hold_lock hl(this->lock_);
337
338         --this->running_;
339
340         // Release the locks for the task.  This must be done with the
341         // workqueue lock held.  Get the next Task to run if any.
342         next = this->release_locks(t, &tl);
343
344         if (next == NULL)
345           next = this->find_runnable();
346
347         // If we have another Task to run, get the Locks.  This must
348         // be called while we are still holding the Workqueue lock.
349         if (next != NULL)
350           {
351             tl.clear();
352             next->locks(&tl);
353
354             ++this->running_;
355           }
356       }
357
358       // We are done with this task.
359       delete t;
360
361       t = next;
362     }
363
364   return true;
365 }
366
367 // Handle the return value of release_locks, and get tasks ready to
368 // run.
369
370 // 1) If T is not runnable, queue it on the appropriate token.
371
372 // 2) Otherwise, T is runnable.  If *PRET is not NULL, then we have
373 // already decided which Task to run next.  Add T to the list of
374 // runnable tasks, and signal another thread.
375
376 // 3) Otherwise, *PRET is NULL.  If IS_BLOCKER is false, then T was
377 // waiting on a write lock.  We can grab that lock now, so we run T
378 // now.
379
380 // 4) Otherwise, IS_BLOCKER is true.  If we should run T soon, then
381 // run it now.
382
383 // 5) Otherwise, check whether there are other tasks to run.  If there
384 // are, then we generally get a better ordering if we run those tasks
385 // now, before T.  A typical example is tasks waiting on the Dirsearch
386 // blocker.  We don't want to run those tasks right away just because
387 // the Dirsearch was unblocked.
388
389 // 6) Otherwise, there are no other tasks to run, so we might as well
390 // run this one now.
391
392 // This function must be called with the Workqueue lock held.
393
394 // Return true if we set *PRET to T, false otherwise.
395
396 bool
397 Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)
398 {
399   Task_token* token = t->is_runnable();
400
401   if (token != NULL)
402     {
403       token->add_waiting(t);
404       ++this->waiting_;
405       return false;
406     }
407
408   bool should_queue = false;
409   bool should_return = false;
410
411   if (*pret != NULL)
412     should_queue = true;
413   else if (!is_blocker)
414     should_return = true;
415   else if (t->should_run_soon())
416     should_return = true;
417   else if (!this->first_tasks_.empty() || !this->tasks_.empty())
418     should_queue = true;
419   else
420     should_return = true;
421
422   if (should_return)
423     {
424       gold_assert(*pret == NULL);
425       *pret = t;
426       return true;
427     }
428   else if (should_queue)
429     {
430       if (t->should_run_soon())
431         this->first_tasks_.push_back(t);
432       else
433         this->tasks_.push_back(t);
434       this->condvar_.signal();
435       return false;
436     }
437
438   gold_unreachable();
439 }
440
441 // Release the locks associated with a Task.  Return the first
442 // runnable Task that we find.  If we find more runnable tasks, add
443 // them to the run queue and signal any other threads.  This must be
444 // called with the Workqueue lock held.
445
446 Task*
447 Workqueue::release_locks(Task* t, Task_locker* tl)
448 {
449   Task* ret = NULL;
450   for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)
451     {
452       Task_token* token = *p;
453       if (token->is_blocker())
454         {
455           if (token->remove_blocker())
456             {
457               // The token has been unblocked.  Every waiting Task may
458               // now be runnable.
459               Task* t;
460               while ((t = token->remove_first_waiting()) != NULL)
461                 {
462                   --this->waiting_;
463                   this->return_or_queue(t, true, &ret);
464                 }
465             }
466         }
467       else
468         {
469           token->remove_writer(t);
470
471           // One more waiting Task may now be runnable.  If we are
472           // going to run it next, we can stop.  Otherwise we need to
473           // move all the Tasks to the runnable queue, to avoid a
474           // potential deadlock if the locking status changes before
475           // we run the next thread.
476           Task* t;
477           while ((t = token->remove_first_waiting()) != NULL)
478             {
479               --this->waiting_;
480               if (this->return_or_queue(t, false, &ret))
481                 break;
482             }
483         }
484     }
485   return ret;
486 }
487
488 // Process all the tasks on the workqueue.  Keep going until the
489 // workqueue is empty, or until we have been told to exit.  This
490 // function is called by all threads.
491
492 void
493 Workqueue::process(int thread_number)
494 {
495   while (this->find_and_run_task(thread_number))
496     ;
497 }
498
499 // Set the number of threads to use for the workqueue, if we are using
500 // threads.
501
502 void
503 Workqueue::set_thread_count(int threads)
504 {
505   Hold_lock hl(this->lock_);
506
507   this->threader_->set_thread_count(threads);
508   // Wake up all the threads, since something has changed.
509   this->condvar_.broadcast();
510 }
511
512 // Add a new blocker to an existing Task_token.
513
514 void
515 Workqueue::add_blocker(Task_token* token)
516 {
517   Hold_lock hl(this->lock_);
518   token->add_blocker();
519 }
520
521 } // End namespace gold.