Commit | Line | Data |
---|---|---|
bae7f79e ILT |
1 | // workqueue.cc -- the workqueue for gold |
2 | ||
6cb15b7f ILT |
3 | // Copyright 2006, 2007 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 | ||
bae7f79e | 23 | #include "gold.h" |
c33feb2b | 24 | |
c7912668 | 25 | #include "debug.h" |
17a1d0a9 | 26 | #include "options.h" |
bae7f79e | 27 | #include "workqueue.h" |
c7912668 | 28 | #include "workqueue-internal.h" |
bae7f79e ILT |
29 | |
30 | namespace gold | |
31 | { | |
32 | ||
17a1d0a9 | 33 | // Class Task_list. |
bae7f79e | 34 | |
17a1d0a9 | 35 | // Add T to the end of the list. |
bae7f79e | 36 | |
17a1d0a9 ILT |
37 | inline void |
38 | Task_list::push_back(Task* t) | |
bae7f79e | 39 | { |
17a1d0a9 ILT |
40 | gold_assert(t->list_next() == NULL); |
41 | if (this->head_ == NULL) | |
42 | { | |
43 | this->head_ = t; | |
44 | this->tail_ = t; | |
45 | } | |
bae7f79e | 46 | else |
17a1d0a9 ILT |
47 | { |
48 | this->tail_->set_list_next(t); | |
49 | this->tail_ = t; | |
50 | } | |
bae7f79e ILT |
51 | } |
52 | ||
17a1d0a9 ILT |
53 | // Remove and return the first Task waiting for this lock to be |
54 | // released. | |
bae7f79e | 55 | |
17a1d0a9 ILT |
56 | inline Task* |
57 | Task_list::pop_front() | |
bae7f79e | 58 | { |
17a1d0a9 ILT |
59 | Task* ret = this->head_; |
60 | if (ret != NULL) | |
bae7f79e | 61 | { |
17a1d0a9 ILT |
62 | if (ret == this->tail_) |
63 | { | |
64 | gold_assert(ret->list_next() == NULL); | |
65 | this->head_ = NULL; | |
66 | this->tail_ = NULL; | |
67 | } | |
68 | else | |
69 | { | |
70 | this->head_ = ret->list_next(); | |
71 | gold_assert(this->head_ != NULL); | |
72 | ret->clear_list_next(); | |
73 | } | |
bae7f79e | 74 | } |
17a1d0a9 | 75 | return ret; |
bae7f79e ILT |
76 | } |
77 | ||
17a1d0a9 | 78 | // The simple single-threaded implementation of Workqueue_threader. |
bae7f79e | 79 | |
17a1d0a9 | 80 | class Workqueue_threader_single : public Workqueue_threader |
bae7f79e ILT |
81 | { |
82 | public: | |
17a1d0a9 ILT |
83 | Workqueue_threader_single(Workqueue* workqueue) |
84 | : Workqueue_threader(workqueue) | |
bae7f79e | 85 | { } |
17a1d0a9 | 86 | ~Workqueue_threader_single() |
bae7f79e ILT |
87 | { } |
88 | ||
fe9a4c12 | 89 | void |
17a1d0a9 ILT |
90 | set_thread_count(int thread_count) |
91 | { gold_assert(thread_count > 0); } | |
fe9a4c12 | 92 | |
17a1d0a9 ILT |
93 | bool |
94 | should_cancel_thread() | |
95 | { return false; } | |
bae7f79e ILT |
96 | }; |
97 | ||
bae7f79e ILT |
98 | // Workqueue methods. |
99 | ||
fe9a4c12 | 100 | Workqueue::Workqueue(const General_options& options) |
17a1d0a9 | 101 | : lock_(), |
c7912668 | 102 | first_tasks_(), |
bae7f79e | 103 | tasks_(), |
bae7f79e | 104 | running_(0), |
17a1d0a9 ILT |
105 | waiting_(0), |
106 | condvar_(this->lock_), | |
107 | threader_(NULL) | |
bae7f79e | 108 | { |
fe9a4c12 ILT |
109 | bool threads = options.threads(); |
110 | #ifndef ENABLE_THREADS | |
111 | threads = false; | |
112 | #endif | |
113 | if (!threads) | |
17a1d0a9 | 114 | this->threader_ = new Workqueue_threader_single(this); |
fe9a4c12 | 115 | else |
c7912668 ILT |
116 | { |
117 | #ifdef ENABLE_THREADS | |
17a1d0a9 | 118 | this->threader_ = new Workqueue_threader_threadpool(this); |
c7912668 ILT |
119 | #else |
120 | gold_unreachable(); | |
121 | #endif | |
122 | } | |
bae7f79e ILT |
123 | } |
124 | ||
125 | Workqueue::~Workqueue() | |
126 | { | |
17a1d0a9 ILT |
127 | } |
128 | ||
129 | // Add a task to the end of a specific queue, or put it on the list | |
130 | // waiting for a Token. | |
131 | ||
132 | void | |
133 | Workqueue::add_to_queue(Task_list* queue, Task* t) | |
134 | { | |
135 | Hold_lock hl(this->lock_); | |
136 | ||
137 | Task_token* token = t->is_runnable(); | |
138 | if (token != NULL) | |
139 | { | |
140 | token->add_waiting(t); | |
141 | ++this->waiting_; | |
142 | } | |
143 | else | |
144 | { | |
145 | queue->push_back(t); | |
146 | // Tell any waiting thread that there is work to do. | |
147 | this->condvar_.signal(); | |
148 | } | |
bae7f79e ILT |
149 | } |
150 | ||
92e059d8 ILT |
151 | // Add a task to the queue. |
152 | ||
bae7f79e ILT |
153 | void |
154 | Workqueue::queue(Task* t) | |
155 | { | |
17a1d0a9 | 156 | this->add_to_queue(&this->tasks_, t); |
bae7f79e ILT |
157 | } |
158 | ||
92e059d8 ILT |
159 | // Add a task to the front of the queue. |
160 | ||
161 | void | |
162 | Workqueue::queue_front(Task* t) | |
163 | { | |
17a1d0a9 ILT |
164 | t->set_should_run_soon(); |
165 | this->add_to_queue(&this->first_tasks_, t); | |
92e059d8 ILT |
166 | } |
167 | ||
17a1d0a9 | 168 | // Return whether to cancel the current thread. |
bae7f79e | 169 | |
17a1d0a9 ILT |
170 | inline bool |
171 | Workqueue::should_cancel_thread() | |
bae7f79e | 172 | { |
17a1d0a9 | 173 | return this->threader_->should_cancel_thread(); |
bae7f79e ILT |
174 | } |
175 | ||
17a1d0a9 ILT |
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. | |
bae7f79e ILT |
179 | |
180 | Task* | |
17a1d0a9 | 181 | Workqueue::find_runnable_in_list(Task_list* tasks) |
bae7f79e | 182 | { |
c7912668 | 183 | Task* t; |
17a1d0a9 | 184 | while ((t = tasks->pop_front()) != NULL) |
bae7f79e | 185 | { |
17a1d0a9 ILT |
186 | Task_token* token = t->is_runnable(); |
187 | ||
188 | if (token == NULL) | |
189 | return t; | |
190 | ||
191 | token->add_waiting(t); | |
192 | ++this->waiting_; | |
193 | } | |
194 | ||
195 | // We couldn't find any runnable task. | |
196 | return NULL; | |
197 | } | |
198 | ||
199 | // Find a runnable task. Return NULL if none could be found. The | |
200 | // workqueue lock must be held when this is called. | |
bae7f79e | 201 | |
17a1d0a9 ILT |
202 | Task* |
203 | Workqueue::find_runnable() | |
204 | { | |
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; | |
209 | } | |
210 | ||
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. | |
214 | ||
215 | Task* | |
216 | Workqueue::find_runnable_or_wait(int thread_number) | |
217 | { | |
218 | Task* t = this->find_runnable(); | |
219 | ||
220 | while (t == NULL) | |
221 | { | |
222 | if (this->running_ == 0 | |
223 | && this->first_tasks_.empty() | |
224 | && this->tasks_.empty()) | |
bae7f79e | 225 | { |
17a1d0a9 ILT |
226 | // Kick all the threads to make them exit. |
227 | this->condvar_.broadcast(); | |
bae7f79e | 228 | |
17a1d0a9 ILT |
229 | gold_assert(this->waiting_ == 0); |
230 | return NULL; | |
bae7f79e | 231 | } |
c7912668 | 232 | |
17a1d0a9 ILT |
233 | if (this->should_cancel_thread()) |
234 | return NULL; | |
235 | ||
236 | gold_debug(DEBUG_TASK, "%3d sleeping", thread_number); | |
c7912668 | 237 | |
17a1d0a9 ILT |
238 | this->condvar_.wait(); |
239 | ||
240 | gold_debug(DEBUG_TASK, "%3d awake", thread_number); | |
241 | ||
242 | t = this->find_runnable(); | |
bae7f79e | 243 | } |
c7912668 | 244 | |
17a1d0a9 | 245 | return t; |
bae7f79e ILT |
246 | } |
247 | ||
17a1d0a9 ILT |
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. | |
bae7f79e | 253 | |
17a1d0a9 ILT |
254 | bool |
255 | Workqueue::find_and_run_task(int thread_number) | |
bae7f79e | 256 | { |
17a1d0a9 ILT |
257 | Task* t; |
258 | Task_locker tl; | |
259 | ||
260 | { | |
261 | Hold_lock hl(this->lock_); | |
262 | ||
263 | // Find a runnable task. | |
264 | t = this->find_runnable_or_wait(thread_number); | |
265 | ||
266 | if (t == NULL) | |
267 | return false; | |
268 | ||
269 | // Get the locks for the task. This must be called while we are | |
270 | // still holding the Workqueue lock. | |
271 | t->locks(&tl); | |
272 | ||
273 | ++this->running_; | |
274 | } | |
275 | ||
276 | while (t != NULL) | |
bae7f79e | 277 | { |
17a1d0a9 ILT |
278 | gold_debug(DEBUG_TASK, "%3d running task %s", thread_number, |
279 | t->name().c_str()); | |
bae7f79e | 280 | |
17a1d0a9 | 281 | t->run(this); |
c7912668 | 282 | |
17a1d0a9 ILT |
283 | gold_debug(DEBUG_TASK, "%3d completed task %s", thread_number, |
284 | t->name().c_str()); | |
c7912668 | 285 | |
17a1d0a9 | 286 | Task* next; |
bae7f79e | 287 | { |
17a1d0a9 | 288 | Hold_lock hl(this->lock_); |
bae7f79e | 289 | |
17a1d0a9 | 290 | --this->running_; |
c7912668 | 291 | |
17a1d0a9 ILT |
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); | |
295 | ||
296 | if (next == NULL) | |
297 | next = this->find_runnable(); | |
298 | ||
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) | |
c7912668 | 302 | { |
17a1d0a9 ILT |
303 | tl.clear(); |
304 | next->locks(&tl); | |
305 | ||
306 | ++this->running_; | |
bae7f79e ILT |
307 | } |
308 | } | |
309 | ||
17a1d0a9 ILT |
310 | // We are done with this task. |
311 | delete t; | |
bae7f79e | 312 | |
17a1d0a9 | 313 | t = next; |
bae7f79e | 314 | } |
17a1d0a9 ILT |
315 | |
316 | return true; | |
bae7f79e ILT |
317 | } |
318 | ||
17a1d0a9 ILT |
319 | // Handle the return value of release_locks, and get tasks ready to |
320 | // run. | |
bae7f79e | 321 | |
17a1d0a9 | 322 | // 1) If T is not runnable, queue it on the appropriate token. |
c7912668 | 323 | |
17a1d0a9 ILT |
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. | |
bae7f79e | 327 | |
17a1d0a9 ILT |
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. | |
bae7f79e | 331 | |
17a1d0a9 ILT |
332 | // 4) Otherwise, IS_BLOCKER is true. If we should run T soon, then |
333 | // run it now. | |
334 | ||
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. | |
340 | ||
341 | // 6) Otherwise, there are no other tasks to run, so we might as well | |
342 | // run this one now. | |
343 | ||
344 | // This function must be called with the Workqueue lock held. | |
345 | ||
346 | // Return true if we set *PRET to T, false otherwise. | |
347 | ||
348 | bool | |
349 | Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret) | |
bae7f79e | 350 | { |
17a1d0a9 | 351 | Task_token* token = t->is_runnable(); |
c7912668 | 352 | |
17a1d0a9 ILT |
353 | if (token != NULL) |
354 | { | |
355 | token->add_waiting(t); | |
356 | ++this->waiting_; | |
357 | return false; | |
358 | } | |
359 | ||
360 | bool should_queue = false; | |
361 | bool should_return = false; | |
362 | ||
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; | |
c7912668 | 373 | |
17a1d0a9 ILT |
374 | if (should_return) |
375 | { | |
376 | gold_assert(*pret == NULL); | |
377 | *pret = t; | |
378 | return true; | |
379 | } | |
380 | else if (should_queue) | |
381 | { | |
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; | |
388 | } | |
389 | ||
390 | gold_unreachable(); | |
bae7f79e ILT |
391 | } |
392 | ||
17a1d0a9 ILT |
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. | |
bae7f79e | 397 | |
17a1d0a9 ILT |
398 | Task* |
399 | Workqueue::release_locks(Task* t, Task_locker* tl) | |
bae7f79e | 400 | { |
17a1d0a9 ILT |
401 | Task* ret = NULL; |
402 | for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p) | |
403 | { | |
404 | Task_token* token = *p; | |
405 | if (token->is_blocker()) | |
406 | { | |
407 | if (token->remove_blocker()) | |
408 | { | |
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) | |
413 | { | |
414 | --this->waiting_; | |
415 | this->return_or_queue(t, true, &ret); | |
416 | } | |
417 | } | |
418 | } | |
419 | else | |
420 | { | |
421 | token->remove_writer(t); | |
422 | ||
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) | |
430 | { | |
431 | --this->waiting_; | |
432 | if (this->return_or_queue(t, false, &ret)) | |
433 | break; | |
434 | } | |
435 | } | |
436 | } | |
437 | return ret; | |
bae7f79e ILT |
438 | } |
439 | ||
17a1d0a9 ILT |
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. | |
fe9a4c12 ILT |
443 | |
444 | void | |
17a1d0a9 | 445 | Workqueue::process(int thread_number) |
fe9a4c12 | 446 | { |
17a1d0a9 ILT |
447 | while (this->find_and_run_task(thread_number)) |
448 | ; | |
fe9a4c12 ILT |
449 | } |
450 | ||
17a1d0a9 ILT |
451 | // Set the number of threads to use for the workqueue, if we are using |
452 | // threads. | |
c7912668 ILT |
453 | |
454 | void | |
17a1d0a9 | 455 | Workqueue::set_thread_count(int threads) |
c7912668 | 456 | { |
17a1d0a9 ILT |
457 | Hold_lock hl(this->lock_); |
458 | ||
459 | this->threader_->set_thread_count(threads); | |
460 | // Wake up all the threads, since something has changed. | |
461 | this->condvar_.broadcast(); | |
c7912668 ILT |
462 | } |
463 | ||
bae7f79e | 464 | } // End namespace gold. |