Add licensing text to every source file.
[deliverable/binutils-gdb.git] / gold / workqueue.cc
1 // workqueue.cc -- the workqueue for gold
2
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
23 #include "gold.h"
24
25 #include "workqueue.h"
26
27 namespace gold
28 {
29
30 // Task_token methods.
31
32 Task_token::Task_token()
33 : is_blocker_(false), readers_(0), writer_(NULL)
34 {
35 }
36
37 Task_token::~Task_token()
38 {
39 gold_assert(this->readers_ == 0 && this->writer_ == NULL);
40 }
41
42 bool
43 Task_token::is_readable() const
44 {
45 gold_assert(!this->is_blocker_);
46 return this->writer_ == NULL;
47 }
48
49 void
50 Task_token::add_reader()
51 {
52 gold_assert(!this->is_blocker_);
53 gold_assert(this->is_readable());
54 ++this->readers_;
55 }
56
57 void
58 Task_token::remove_reader()
59 {
60 gold_assert(!this->is_blocker_);
61 gold_assert(this->readers_ > 0);
62 --this->readers_;
63 }
64
65 bool
66 Task_token::is_writable() const
67 {
68 gold_assert(!this->is_blocker_);
69 return this->writer_ == NULL && this->readers_ == 0;
70 }
71
72 void
73 Task_token::add_writer(const Task* t)
74 {
75 gold_assert(!this->is_blocker_);
76 gold_assert(this->is_writable());
77 this->writer_ = t;
78 }
79
80 void
81 Task_token::remove_writer(const Task* t)
82 {
83 gold_assert(!this->is_blocker_);
84 gold_assert(this->writer_ == t);
85 this->writer_ = NULL;
86 }
87
88 bool
89 Task_token::has_write_lock(const Task* t)
90 {
91 gold_assert(!this->is_blocker_);
92 return this->writer_ == t;
93 }
94
95 // For blockers, we just use the readers_ field.
96
97 void
98 Task_token::add_blocker()
99 {
100 if (this->readers_ == 0 && this->writer_ == NULL)
101 this->is_blocker_ = true;
102 else
103 gold_assert(this->is_blocker_);
104 ++this->readers_;
105 }
106
107 bool
108 Task_token::remove_blocker()
109 {
110 gold_assert(this->is_blocker_ && this->readers_ > 0);
111 --this->readers_;
112 return this->readers_ == 0;
113 }
114
115 bool
116 Task_token::is_blocked() const
117 {
118 gold_assert(this->is_blocker_
119 || (this->readers_ == 0 && this->writer_ == NULL));
120 return this->readers_ > 0;
121 }
122
123 // The Task_block_token class.
124
125 Task_block_token::Task_block_token(Task_token& token, Workqueue* workqueue)
126 : token_(token), workqueue_(workqueue)
127 {
128 // We must increment the block count when the task is created and
129 // put on the queue. This object is created when the task is run,
130 // so we don't increment the block count here.
131 gold_assert(this->token_.is_blocked());
132 }
133
134 Task_block_token::~Task_block_token()
135 {
136 if (this->token_.remove_blocker())
137 {
138 // Tell the workqueue that a blocker was cleared. This is
139 // always called in the main thread, so no locking is required.
140 this->workqueue_->cleared_blocker();
141 }
142 }
143
144 // The Workqueue_runner abstract class.
145
146 class Workqueue_runner
147 {
148 public:
149 Workqueue_runner(Workqueue* workqueue)
150 : workqueue_(workqueue)
151 { }
152 virtual ~Workqueue_runner()
153 { }
154
155 // Run a task. This is always called in the main thread.
156 virtual void run(Task*, Task_locker*) = 0;
157
158 protected:
159 // This is called by an implementation when a task is completed.
160 void completed(Task* t, Task_locker* tl)
161 { this->workqueue_->completed(t, tl); }
162
163 Workqueue* get_workqueue() const
164 { return this->workqueue_; }
165
166 private:
167 Workqueue* workqueue_;
168 };
169
170 // The simple single-threaded implementation of Workqueue_runner.
171
172 class Workqueue_runner_single : public Workqueue_runner
173 {
174 public:
175 Workqueue_runner_single(Workqueue* workqueue)
176 : Workqueue_runner(workqueue)
177 { }
178 ~Workqueue_runner_single()
179 { }
180
181 void run(Task*, Task_locker*);
182 };
183
184 void
185 Workqueue_runner_single::run(Task* t, Task_locker* tl)
186 {
187 t->run(this->get_workqueue());
188 this->completed(t, tl);
189 }
190
191 // Workqueue methods.
192
193 Workqueue::Workqueue(const General_options&)
194 : tasks_lock_(),
195 tasks_(),
196 completed_lock_(),
197 completed_(),
198 running_(0),
199 completed_condvar_(this->completed_lock_),
200 cleared_blockers_(0)
201 {
202 // At some point we will select the specific implementation of
203 // Workqueue_runner to use based on the command line options.
204 this->runner_ = new Workqueue_runner_single(this);
205 }
206
207 Workqueue::~Workqueue()
208 {
209 gold_assert(this->tasks_.empty());
210 gold_assert(this->completed_.empty());
211 gold_assert(this->running_ == 0);
212 }
213
214 // Add a task to the queue.
215
216 void
217 Workqueue::queue(Task* t)
218 {
219 Hold_lock hl(this->tasks_lock_);
220 this->tasks_.push_back(t);
221 }
222
223 // Add a task to the front of the queue.
224
225 void
226 Workqueue::queue_front(Task* t)
227 {
228 Hold_lock hl(this->tasks_lock_);
229 this->tasks_.push_front(t);
230 }
231
232 // Clear the list of completed tasks. Return whether we cleared
233 // anything. The completed_lock_ must be held when this is called.
234
235 bool
236 Workqueue::clear_completed()
237 {
238 if (this->completed_.empty())
239 return false;
240 do
241 {
242 delete this->completed_.front();
243 this->completed_.pop_front();
244 }
245 while (!this->completed_.empty());
246 return true;
247 }
248
249 // Find a runnable task in TASKS, which is non-empty. Return NULL if
250 // none could be found. The tasks_lock_ must be held when this is
251 // called. Sets ALL_BLOCKED if all non-runnable tasks are waiting on
252 // a blocker.
253
254 Task*
255 Workqueue::find_runnable(Task_list& tasks, bool* all_blocked)
256 {
257 Task* tlast = tasks.back();
258 *all_blocked = true;
259 while (true)
260 {
261 Task* t = tasks.front();
262 tasks.pop_front();
263
264 Task::Is_runnable_type is_runnable = t->is_runnable(this);
265 if (is_runnable == Task::IS_RUNNABLE)
266 return t;
267
268 if (is_runnable != Task::IS_BLOCKED)
269 *all_blocked = false;
270
271 tasks.push_back(t);
272
273 if (t == tlast)
274 {
275 // We couldn't find any runnable task. If there are any
276 // completed tasks, free their locks and try again.
277
278 {
279 Hold_lock hl2(this->completed_lock_);
280
281 if (!this->clear_completed())
282 {
283 // There had better be some tasks running, or we will
284 // never find a runnable task.
285 gold_assert(this->running_ > 0);
286
287 // We couldn't find any runnable tasks, and we
288 // couldn't release any locks.
289 return NULL;
290 }
291 }
292
293 // We're going around again, so recompute ALL_BLOCKED.
294 *all_blocked = true;
295 }
296 }
297 }
298
299 // Process all the tasks on the workqueue. This is the main loop in
300 // the linker. Note that as we process tasks, new tasks will be
301 // added.
302
303 void
304 Workqueue::process()
305 {
306 while (true)
307 {
308 Task* t;
309 bool empty;
310 bool all_blocked;
311
312 {
313 Hold_lock hl(this->tasks_lock_);
314
315 if (this->tasks_.empty())
316 {
317 t = NULL;
318 empty = true;
319 all_blocked = false;
320 }
321 else
322 {
323 t = this->find_runnable(this->tasks_, &all_blocked);
324 empty = false;
325 }
326 }
327
328 // If T != NULL, it is a task we can run.
329 // If T == NULL && empty, then there are no tasks waiting to
330 // be run at this level.
331 // If T == NULL && !empty, then there tasks waiting to be
332 // run at this level, but they are waiting for something to
333 // unlock.
334
335 if (t != NULL)
336 this->run(t);
337 else if (!empty)
338 {
339 {
340 Hold_lock hl(this->completed_lock_);
341
342 // There must be something for us to wait for, or we won't
343 // be able to make progress.
344 gold_assert(this->running_ > 0 || !this->completed_.empty());
345
346 if (all_blocked)
347 {
348 this->cleared_blockers_ = 0;
349 this->clear_completed();
350 while (this->cleared_blockers_ == 0)
351 {
352 gold_assert(this->running_ > 0);
353 this->completed_condvar_.wait();
354 this->clear_completed();
355 }
356 }
357 else
358 {
359 if (this->running_ > 0)
360 {
361 // Wait for a task to finish.
362 this->completed_condvar_.wait();
363 }
364 this->clear_completed();
365 }
366 }
367 }
368 else
369 {
370 {
371 Hold_lock hl(this->completed_lock_);
372
373 // If there are no running tasks, then we are done.
374 if (this->running_ == 0)
375 {
376 this->clear_completed();
377 return;
378 }
379
380 // Wait for a task to finish. Then we have to loop around
381 // again in case it added any new tasks before finishing.
382 this->completed_condvar_.wait();
383 this->clear_completed();
384 }
385 }
386 }
387 }
388
389 // Run a task. This is always called in the main thread.
390
391 void
392 Workqueue::run(Task* t)
393 {
394 ++this->running_;
395 this->runner_->run(t, t->locks(this));
396 }
397
398 // This is called when a task is completed to put the locks on the
399 // list to be released. We use a list because we only want the locks
400 // to be released in the main thread.
401
402 void
403 Workqueue::completed(Task* t, Task_locker* tl)
404 {
405 {
406 Hold_lock hl(this->completed_lock_);
407 gold_assert(this->running_ > 0);
408 --this->running_;
409 this->completed_.push_back(tl);
410 this->completed_condvar_.signal();
411 }
412 delete t;
413 }
414
415 // This is called when the last task for a blocker has completed.
416 // This is always called in the main thread.
417
418 void
419 Workqueue::cleared_blocker()
420 {
421 ++this->cleared_blockers_;
422 }
423
424 } // End namespace gold.
This page took 0.042951 seconds and 5 git commands to generate.