1 // workqueue.cc -- the workqueue for gold
12 // Task_token methods.
14 Task_token::Task_token()
15 : is_blocker_(false), readers_(0), writer_(NULL
)
19 Task_token::~Task_token()
21 assert(this->readers_
== 0 && this->writer_
== NULL
);
25 Task_token::is_readable() const
27 assert(!this->is_blocker_
);
28 return this->writer_
== NULL
;
32 Task_token::add_reader()
34 assert(!this->is_blocker_
);
35 assert(this->is_readable());
40 Task_token::remove_reader()
42 assert(!this->is_blocker_
);
43 assert(this->readers_
> 0);
48 Task_token::is_writable() const
50 assert(!this->is_blocker_
);
51 return this->writer_
== NULL
&& this->readers_
== 0;
55 Task_token::add_writer(const Task
* t
)
57 assert(!this->is_blocker_
);
58 assert(this->is_writable());
63 Task_token::remove_writer(const Task
* t
)
65 assert(!this->is_blocker_
);
66 assert(this->writer_
== t
);
71 Task_token::has_write_lock(const Task
* t
)
73 assert(!this->is_blocker_
);
74 return this->writer_
== t
;
77 // For blockers, we just use the readers_ field.
80 Task_token::add_blocker()
82 if (this->readers_
== 0 && this->writer_
== NULL
)
83 this->is_blocker_
= true;
85 assert(this->is_blocker_
);
90 Task_token::remove_blocker()
92 assert(this->is_blocker_
&& this->readers_
> 0);
94 return this->readers_
== 0;
98 Task_token::is_blocked() const
100 assert(this->is_blocker_
|| (this->readers_
== 0 && this->writer_
== NULL
));
101 return this->readers_
> 0;
104 // The Task_block_token class.
106 Task_block_token::Task_block_token(Task_token
& token
, Workqueue
* workqueue
)
107 : token_(token
), workqueue_(workqueue
)
109 // We must increment the block count when the task is created and
110 // put on the queue. This object is created when the task is run,
111 // so we don't increment the block count here.
112 assert(this->token_
.is_blocked());
115 Task_block_token::~Task_block_token()
117 if (this->token_
.remove_blocker())
119 // Tell the workqueue that a blocker was cleared. This is
120 // always called in the main thread, so no locking is required.
121 this->workqueue_
->cleared_blocker();
125 // The Workqueue_runner abstract class.
127 class Workqueue_runner
130 Workqueue_runner(Workqueue
* workqueue
)
131 : workqueue_(workqueue
)
133 virtual ~Workqueue_runner()
136 // Run a task. This is always called in the main thread.
137 virtual void run(Task
*, Task_locker
*) = 0;
140 // This is called by an implementation when a task is completed.
141 void completed(Task
* t
, Task_locker
* tl
)
142 { this->workqueue_
->completed(t
, tl
); }
144 Workqueue
* get_workqueue() const
145 { return this->workqueue_
; }
148 Workqueue
* workqueue_
;
151 // The simple single-threaded implementation of Workqueue_runner.
153 class Workqueue_runner_single
: public Workqueue_runner
156 Workqueue_runner_single(Workqueue
* workqueue
)
157 : Workqueue_runner(workqueue
)
159 ~Workqueue_runner_single()
162 void run(Task
*, Task_locker
*);
166 Workqueue_runner_single::run(Task
* t
, Task_locker
* tl
)
168 t
->run(this->get_workqueue());
169 this->completed(t
, tl
);
172 // Workqueue methods.
174 Workqueue::Workqueue(const General_options
&)
180 completed_condvar_(this->completed_lock_
),
183 // At some point we will select the specific implementation of
184 // Workqueue_runner to use based on the command line options.
185 this->runner_
= new Workqueue_runner_single(this);
188 Workqueue::~Workqueue()
190 assert(this->tasks_
.empty());
191 assert(this->completed_
.empty());
192 assert(this->running_
== 0);
196 Workqueue::queue(Task
* t
)
198 Hold_lock
hl(this->tasks_lock_
);
199 this->tasks_
.push_back(t
);
202 // Clear the list of completed tasks. Return whether we cleared
203 // anything. The completed_lock_ must be held when this is called.
206 Workqueue::clear_completed()
208 if (this->completed_
.empty())
212 delete this->completed_
.front();
213 this->completed_
.pop_front();
215 while (!this->completed_
.empty());
219 // Find a runnable task in TASKS, which is non-empty. Return NULL if
220 // none could be found. The tasks_lock_ must be held when this is
221 // called. Sets ALL_BLOCKED if all non-runnable tasks are waiting on
225 Workqueue::find_runnable(Task_list
& tasks
, bool* all_blocked
)
227 Task
* tlast
= tasks
.back();
231 Task
* t
= tasks
.front();
234 Task::Is_runnable_type is_runnable
= t
->is_runnable(this);
235 if (is_runnable
== Task::IS_RUNNABLE
)
238 if (is_runnable
!= Task::IS_BLOCKED
)
239 *all_blocked
= false;
245 // We couldn't find any runnable task. If there are any
246 // completed tasks, free their locks and try again.
249 Hold_lock
hl2(this->completed_lock_
);
251 if (!this->clear_completed())
253 // There had better be some tasks running, or we will
254 // never find a runnable task.
255 assert(this->running_
> 0);
257 // We couldn't find any runnable tasks, and we
258 // couldn't release any locks.
263 // We're going around again, so recompute ALL_BLOCKED.
269 // Process all the tasks on the workqueue. This is the main loop in
270 // the linker. Note that as we process tasks, new tasks will be
283 Hold_lock
hl(this->tasks_lock_
);
285 if (this->tasks_
.empty())
293 t
= this->find_runnable(this->tasks_
, &all_blocked
);
298 // If T != NULL, it is a task we can run.
299 // If T == NULL && empty, then there are no tasks waiting to
300 // be run at this level.
301 // If T == NULL && !empty, then there tasks waiting to be
302 // run at this level, but they are waiting for something to
310 Hold_lock
hl(this->completed_lock_
);
312 // There must be something for us to wait for, or we won't
313 // be able to make progress.
314 assert(this->running_
> 0 || !this->completed_
.empty());
318 this->cleared_blockers_
= 0;
319 this->clear_completed();
320 while (this->cleared_blockers_
== 0)
322 assert(this->running_
> 0);
323 this->completed_condvar_
.wait();
324 this->clear_completed();
329 if (this->running_
> 0)
331 // Wait for a task to finish.
332 this->completed_condvar_
.wait();
334 this->clear_completed();
341 Hold_lock
hl(this->completed_lock_
);
343 // If there are no running tasks, then we are done.
344 if (this->running_
== 0)
346 this->clear_completed();
350 // Wait for a task to finish. Then we have to loop around
351 // again in case it added any new tasks before finishing.
352 this->completed_condvar_
.wait();
353 this->clear_completed();
359 // Run a task. This is always called in the main thread.
362 Workqueue::run(Task
* t
)
365 this->runner_
->run(t
, t
->locks(this));
368 // This is called when a task is completed to put the locks on the
369 // list to be released. We use a list because we only want the locks
370 // to be released in the main thread.
373 Workqueue::completed(Task
* t
, Task_locker
* tl
)
376 Hold_lock
hl(this->completed_lock_
);
377 assert(this->running_
> 0);
379 this->completed_
.push_back(tl
);
380 this->completed_condvar_
.signal();
385 // This is called when the last task for a blocker has completed.
386 // This is always called in the main thread.
389 Workqueue::cleared_blocker()
391 ++this->cleared_blockers_
;
394 } // End namespace gold.