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