1 // workqueue.cc -- the workqueue for gold
2 
3 // Copyright (C) 2006-2020 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.
522