Import binutils-2.20
[dragonfly.git] / contrib / binutils-2.20 / 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 "workqueue.h"
28 #include "workqueue-internal.h"
29
30 namespace gold
31 {
32
33 // Class Task_list.
34
35 // Add T to the end of the list.
36
37 inline void
38 Task_list::push_back(Task* t)
39 {
40   gold_assert(t->list_next() == NULL);
41   if (this->head_ == NULL)
42     {
43       this->head_ = t;
44       this->tail_ = t;
45     }
46   else
47     {
48       this->tail_->set_list_next(t);
49       this->tail_ = t;
50     }
51 }
52
53 // Add T to the front of the list.
54
55 inline void
56 Task_list::push_front(Task* t)
57 {
58   gold_assert(t->list_next() == NULL);
59   if (this->head_ == NULL)
60     {
61       this->head_ = t;
62       this->tail_ = t;
63     }
64   else
65     {
66       t->set_list_next(this->head_);
67       this->head_ = t;
68     }
69 }
70
71 // Remove and return the first Task waiting for this lock to be
72 // released.
73
74 inline Task*
75 Task_list::pop_front()
76 {
77   Task* ret = this->head_;
78   if (ret != NULL)
79     {
80       if (ret == this->tail_)
81         {
82           gold_assert(ret->list_next() == NULL);
83           this->head_ = NULL;
84           this->tail_ = NULL;
85         }
86       else
87         {
88           this->head_ = ret->list_next();
89           gold_assert(this->head_ != NULL);
90           ret->clear_list_next();
91         }
92     }
93   return ret;
94 }
95
96 // The simple single-threaded implementation of Workqueue_threader.
97
98 class Workqueue_threader_single : public Workqueue_threader
99 {
100  public:
101   Workqueue_threader_single(Workqueue* workqueue)
102     : Workqueue_threader(workqueue)
103   { }
104   ~Workqueue_threader_single()
105   { }
106
107   void
108   set_thread_count(int thread_count)
109   { gold_assert(thread_count > 0); }
110
111   bool
112   should_cancel_thread()
113   { return false; }
114 };
115
116 // Workqueue methods.
117
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)
126 {
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
134     {
135 #ifdef ENABLE_THREADS
136       this->threader_ = new Workqueue_threader_threadpool(this);
137 #else
138       gold_unreachable();
139 #endif
140     }
141 }
142
143 Workqueue::~Workqueue()
144 {
145 }
146
147 // Add a task to the end of a specific queue, or put it on the list
148 // waiting for a Token.
149
150 void
151 Workqueue::add_to_queue(Task_list* queue, Task* t, bool front)
152 {
153   Hold_lock hl(this->lock_);
154
155   Task_token* token = t->is_runnable();
156   if (token != NULL)
157     {
158       if (front)
159         token->add_waiting_front(t);
160       else
161         token->add_waiting(t);
162       ++this->waiting_;
163     }
164   else
165     {
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();
172     }
173 }
174
175 // Add a task to the queue.
176
177 void
178 Workqueue::queue(Task* t)
179 {
180   this->add_to_queue(&this->tasks_, t, false);
181 }
182
183 // Queue a task which should run soon.
184
185 void
186 Workqueue::queue_soon(Task* t)
187 {
188   t->set_should_run_soon();
189   this->add_to_queue(&this->first_tasks_, t, false);
190 }
191
192 // Queue a task which should run next.
193
194 void
195 Workqueue::queue_next(Task* t)
196 {
197   t->set_should_run_soon();
198   this->add_to_queue(&this->first_tasks_, t, true);
199 }
200
201 // Return whether to cancel the current thread.
202
203 inline bool
204 Workqueue::should_cancel_thread()
205 {
206   return this->threader_->should_cancel_thread();
207 }
208
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.
212
213 Task*
214 Workqueue::find_runnable_in_list(Task_list* tasks)
215 {
216   Task* t;
217   while ((t = tasks->pop_front()) != NULL)
218     {
219       Task_token* token = t->is_runnable();
220
221       if (token == NULL)
222         return t;
223
224       token->add_waiting(t);
225       ++this->waiting_;
226     }
227
228   // We couldn't find any runnable task.
229   return NULL;
230 }
231
232 // Find a runnable task.  Return NULL if none could be found.  The
233 // workqueue lock must be held when this is called.
234
235 Task*
236 Workqueue::find_runnable()
237 {
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;
242 }
243
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.
247
248 Task*
249 Workqueue::find_runnable_or_wait(int thread_number)
250 {
251   Task* t = this->find_runnable();
252
253   while (t == NULL)
254     {
255       if (this->running_ == 0
256           && this->first_tasks_.empty()
257           && this->tasks_.empty())
258         {
259           // Kick all the threads to make them exit.
260           this->condvar_.broadcast();
261
262           gold_assert(this->waiting_ == 0);
263           return NULL;
264         }
265
266       if (this->should_cancel_thread())
267         return NULL;
268
269       gold_debug(DEBUG_TASK, "%3d sleeping", thread_number);
270
271       this->condvar_.wait();
272
273       gold_debug(DEBUG_TASK, "%3d awake", thread_number);
274
275       t = this->find_runnable();
276     }
277
278   return t;
279 }
280
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.
286
287 bool
288 Workqueue::find_and_run_task(int thread_number)
289 {
290   Task* t;
291   Task_locker tl;
292
293   {
294     Hold_lock hl(this->lock_);
295
296     // Find a runnable task.
297     t = this->find_runnable_or_wait(thread_number);
298
299     if (t == NULL)
300       return false;
301
302     // Get the locks for the task.  This must be called while we are
303     // still holding the Workqueue lock.
304     t->locks(&tl);
305
306     ++this->running_;
307   }
308
309   while (t != NULL)
310     {
311       gold_debug(DEBUG_TASK, "%3d running   task %s", thread_number,
312                  t->name().c_str());
313
314       t->run(this);
315
316       gold_debug(DEBUG_TASK, "%3d completed task %s", thread_number,
317                  t->name().c_str());
318
319       Task* next;
320       {
321         Hold_lock hl(this->lock_);
322
323         --this->running_;
324
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);
328
329         if (next == NULL)
330           next = this->find_runnable();
331
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)
335           {
336             tl.clear();
337             next->locks(&tl);
338
339             ++this->running_;
340           }
341       }
342
343       // We are done with this task.
344       delete t;
345
346       t = next;
347     }
348
349   return true;
350 }
351
352 // Handle the return value of release_locks, and get tasks ready to
353 // run.
354
355 // 1) If T is not runnable, queue it on the appropriate token.
356
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.
360
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.
364
365 // 4) Otherwise, IS_BLOCKER is true.  If we should run T soon, then
366 // run it now.
367
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.
373
374 // 6) Otherwise, there are no other tasks to run, so we might as well
375 // run this one now.
376
377 // This function must be called with the Workqueue lock held.
378
379 // Return true if we set *PRET to T, false otherwise.
380
381 bool
382 Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret)
383 {
384   Task_token* token = t->is_runnable();
385
386   if (token != NULL)
387     {
388       token->add_waiting(t);
389       ++this->waiting_;
390       return false;
391     }
392
393   bool should_queue = false;
394   bool should_return = false;
395
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;
406
407   if (should_return)
408     {
409       gold_assert(*pret == NULL);
410       *pret = t;
411       return true;
412     }
413   else if (should_queue)
414     {
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;
421     }
422
423   gold_unreachable();
424 }
425
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.
430
431 Task*
432 Workqueue::release_locks(Task* t, Task_locker* tl)
433 {
434   Task* ret = NULL;
435   for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p)
436     {
437       Task_token* token = *p;
438       if (token->is_blocker())
439         {
440           if (token->remove_blocker())
441             {
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)
446                 {
447                   --this->waiting_;
448                   this->return_or_queue(t, true, &ret);
449                 }
450             }
451         }
452       else
453         {
454           token->remove_writer(t);
455
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)
463             {
464               --this->waiting_;
465               if (this->return_or_queue(t, false, &ret))
466                 break;
467             }
468         }
469     }
470   return ret;
471 }
472
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.
476
477 void
478 Workqueue::process(int thread_number)
479 {
480   while (this->find_and_run_task(thread_number))
481     ;
482 }
483
484 // Set the number of threads to use for the workqueue, if we are using
485 // threads.
486
487 void
488 Workqueue::set_thread_count(int threads)
489 {
490   Hold_lock hl(this->lock_);
491
492   this->threader_->set_thread_count(threads);
493   // Wake up all the threads, since something has changed.
494   this->condvar_.broadcast();
495 }
496
497 // Add a new blocker to an existing Task_token.
498
499 void
500 Workqueue::add_blocker(Task_token* token)
501 {
502   Hold_lock hl(this->lock_);
503   token->add_blocker();
504 }
505
506 } // End namespace gold.