1 // workqueue.cc -- the workqueue for gold
11 Task_token::Task_token()
12 : is_blocker_(false), readers_(0), writer_(NULL
)
16 Task_token::~Task_token()
18 assert(this->readers_
== 0 && this->writer_
== NULL
);
22 Task_token::is_readable() const
24 assert(!this->is_blocker_
);
25 return this->writer_
== NULL
;
29 Task_token::add_reader()
31 assert(!this->is_blocker_
);
32 assert(this->is_readable());
37 Task_token::remove_reader()
39 assert(!this->is_blocker_
);
40 assert(this->readers_
> 0);
45 Task_token::is_writable() const
47 assert(!this->is_blocker_
);
48 return this->writer_
== NULL
&& this->readers_
== 0;
52 Task_token::add_writer(const Task
* t
)
54 assert(!this->is_blocker_
);
55 assert(this->is_writable());
60 Task_token::remove_writer(const Task
* t
)
62 assert(!this->is_blocker_
);
63 assert(this->writer_
== t
);
68 Task_token::has_write_lock(const Task
* t
)
70 assert(!this->is_blocker_
);
71 return this->writer_
== t
;
74 // For blockers, we just use the readers_ field.
77 Task_token::add_blocker()
79 if (this->readers_
== 0 && this->writer_
== NULL
)
80 this->is_blocker_
= true;
82 assert(this->is_blocker_
);
87 Task_token::remove_blocker()
89 assert(this->is_blocker_
&& this->readers_
> 0);
91 return this->readers_
== 0;
95 Task_token::is_blocked() const
97 assert(this->is_blocker_
|| (this->readers_
== 0 && this->writer_
== NULL
));
98 return this->readers_
> 0;
101 // The Task_block_token class.
103 Task_block_token::Task_block_token(Task_token
& token
, Workqueue
* workqueue
)
104 : token_(token
), workqueue_(workqueue
)
106 // We must increment the block count when the task is created and
107 // put on the queue. This object is created when the task is run,
108 // so we don't increment the block count here.
109 assert(this->token_
.is_blocked());
112 Task_block_token::~Task_block_token()
114 if (this->token_
.remove_blocker())
116 // Tell the workqueue that a blocker was cleared. This is
117 // always called in the main thread, so no locking is required.
118 this->workqueue_
->cleared_blocker();
122 // The Workqueue_runner abstract class.
124 class Workqueue_runner
127 Workqueue_runner(Workqueue
* workqueue
)
128 : workqueue_(workqueue
)
130 virtual ~Workqueue_runner()
133 // Run a task. This is always called in the main thread.
134 virtual void run(Task
*, Task_locker
*) = 0;
137 // This is called by an implementation when a task is completed.
138 void completed(Task
* t
, Task_locker
* tl
)
139 { this->workqueue_
->completed(t
, tl
); }
141 Workqueue
* get_workqueue() const
142 { return this->workqueue_
; }
145 Workqueue
* workqueue_
;
148 // The simple single-threaded implementation of Workqueue_runner.
150 class Workqueue_runner_single
: public Workqueue_runner
153 Workqueue_runner_single(Workqueue
* workqueue
)
154 : Workqueue_runner(workqueue
)
156 ~Workqueue_runner_single()
159 void run(Task
*, Task_locker
*);
163 Workqueue_runner_single::run(Task
* t
, Task_locker
* tl
)
165 t
->run(this->get_workqueue());
166 this->completed(t
, tl
);
169 // Workqueue methods.
171 Workqueue::Workqueue(const General_options
&)
177 completed_condvar_(this->completed_lock_
),
180 // At some point we will select the specific implementation of
181 // Workqueue_runner to use based on the command line options.
182 this->runner_
= new Workqueue_runner_single(this);
185 Workqueue::~Workqueue()
187 assert(this->tasks_
.empty());
188 assert(this->completed_
.empty());
189 assert(this->running_
== 0);
193 Workqueue::queue(Task
* t
)
195 Hold_lock
hl(this->tasks_lock_
);
196 this->tasks_
.push_back(t
);
199 // Clear the list of completed tasks. Return whether we cleared
200 // anything. The completed_lock_ must be held when this is called.
203 Workqueue::clear_completed()
205 if (this->completed_
.empty())
209 delete this->completed_
.front();
210 this->completed_
.pop_front();
212 while (!this->completed_
.empty());
216 // Find a runnable task in TASKS, which is non-empty. Return NULL if
217 // none could be found. The tasks_lock_ must be held when this is
218 // called. Sets ALL_BLOCKED if all non-runnable tasks are waiting on
222 Workqueue::find_runnable(Task_list
& tasks
, bool* all_blocked
)
224 Task
* tlast
= tasks
.back();
228 Task
* t
= tasks
.front();
231 Task::Is_runnable_type is_runnable
= t
->is_runnable(this);
232 if (is_runnable
== Task::IS_RUNNABLE
)
235 if (is_runnable
!= Task::IS_BLOCKED
)
236 *all_blocked
= false;
242 // We couldn't find any runnable task. If there are any
243 // completed tasks, free their locks and try again.
246 Hold_lock
hl2(this->completed_lock_
);
248 if (!this->clear_completed())
250 // There had better be some tasks running, or we will
251 // never find a runnable task.
252 assert(this->running_
> 0);
254 // We couldn't find any runnable tasks, and we
255 // couldn't release any locks.
260 // We're going around again, so recompute ALL_BLOCKED.
266 // Process all the tasks on the workqueue. This is the main loop in
267 // the linker. Note that as we process tasks, new tasks will be
280 Hold_lock
hl(this->tasks_lock_
);
282 if (this->tasks_
.empty())
290 t
= this->find_runnable(this->tasks_
, &all_blocked
);
295 // If T != NULL, it is a task we can run.
296 // If T == NULL && empty, then there are no tasks waiting to
297 // be run at this level.
298 // If T == NULL && !empty, then there tasks waiting to be
299 // run at this level, but they are waiting for something to
307 Hold_lock
hl(this->completed_lock_
);
309 // There must be something for us to wait for, or we won't
310 // be able to make progress.
311 assert(this->running_
> 0 || !this->completed_
.empty());
315 this->cleared_blockers_
= 0;
316 this->clear_completed();
317 while (this->cleared_blockers_
== 0)
319 assert(this->running_
> 0);
320 this->completed_condvar_
.wait();
321 this->clear_completed();
326 if (this->running_
> 0)
328 // Wait for a task to finish.
329 this->completed_condvar_
.wait();
331 this->clear_completed();
338 Hold_lock
hl(this->completed_lock_
);
340 // If there are no running tasks, then we are done.
341 if (this->running_
== 0)
343 this->clear_completed();
347 // Wait for a task to finish. Then we have to loop around
348 // again in case it added any new tasks before finishing.
349 this->completed_condvar_
.wait();
350 this->clear_completed();
356 // Run a task. This is always called in the main thread.
359 Workqueue::run(Task
* t
)
362 this->runner_
->run(t
, t
->locks(this));
365 // This is called when a task is completed to put the locks on the
366 // list to be released. We use a list because we only want the locks
367 // to be released in the main thread.
370 Workqueue::completed(Task
* t
, Task_locker
* tl
)
373 Hold_lock
hl(this->completed_lock_
);
374 assert(this->running_
> 0);
376 this->completed_
.push_back(tl
);
377 this->completed_condvar_
.signal();
382 // This is called when the last task for a blocker has completed.
383 // This is always called in the main thread.
386 Workqueue::cleared_blocker()
388 ++this->cleared_blockers_
;
391 } // End namespace gold.