daily update
[binutils.git] / gold / workqueue.h
blobed7a5b00d7ddf030abe295497a2ef91d2b2170a6
1 // workqueue.h -- the work queue for gold -*- C++ -*-
3 // After processing the command line, everything the linker does is
4 // driven from a work queue. This permits us to parallelize the
5 // linker where possible.
7 // Task_token
8 // A simple locking implementation to ensure proper task ordering.
9 // Task_read_token, Task_write_token
10 // Lock a Task_token for read or write.
11 // Task_locker
12 // Task locking using RAII.
13 // Task
14 // An abstract class for jobs to run.
16 #ifndef GOLD_WORKQUEUE_H
17 #define GOLD_WORKQUEUE_H
19 #include "gold-threads.h"
20 #include "fileread.h"
22 namespace gold
25 class General_options;
26 class Task;
27 class Workqueue;
29 // Some tasks require access to shared data structures, such as the
30 // symbol table. Some tasks must be executed in a particular error,
31 // such as reading input file symbol tables--if we see foo.o -llib, we
32 // have to read the symbols for foo.o before we read the ones for
33 // -llib. To implement this safely and efficiently, we use tokens.
34 // Task_tokens support shared read/exclusive write access to some
35 // resource. Alternatively, they support blockers: blockers implement
36 // the requirement that some set of tasks must complete before another
37 // set of tasks can start. In such a case we increment the block
38 // count when we create the task, and decrement it when the task
39 // completes. Task_tokens are only manipulated by the main thread, so
40 // they do not themselves require any locking.
42 class Task_token
44 public:
45 Task_token();
47 ~Task_token();
49 // A read/write token uses these methods.
51 bool
52 is_readable() const;
54 void
55 add_reader();
57 void
58 remove_reader();
60 bool
61 is_writable() const;
63 void
64 add_writer(const Task*);
66 void
67 remove_writer(const Task*);
69 bool
70 has_write_lock(const Task*);
72 // A blocker token uses these methods.
74 void
75 add_blocker();
77 // Returns true if block count drops to zero.
78 bool
79 remove_blocker();
81 bool
82 is_blocked() const;
84 private:
85 // It makes no sense to copy these.
86 Task_token(const Task_token&);
87 Task_token& operator=(const Task_token&);
89 bool is_blocker_;
90 int readers_;
91 const Task* writer_;
94 // In order to support tokens more reliably, we provide objects which
95 // handle them using RAII.
97 class Task_read_token
99 public:
100 Task_read_token(Task_token& token)
101 : token_(token)
102 { this->token_.add_reader(); }
104 ~Task_read_token()
105 { this->token_.remove_reader(); }
107 private:
108 Task_read_token(const Task_read_token&);
109 Task_read_token& operator=(const Task_read_token&);
111 Task_token& token_;
114 class Task_write_token
116 public:
117 Task_write_token(Task_token& token, const Task* task)
118 : token_(token), task_(task)
119 { this->token_.add_writer(this->task_); }
121 ~Task_write_token()
122 { this->token_.remove_writer(this->task_); }
124 private:
125 Task_write_token(const Task_write_token&);
126 Task_write_token& operator=(const Task_write_token&);
128 Task_token& token_;
129 const Task* task_;
132 class Task_block_token
134 public:
135 // The blocker count must be incremented when the task is created.
136 // This object is created when the task is run. When we unblock the
137 // last task, we notify the workqueue.
138 Task_block_token(Task_token& token, Workqueue* workqueue);
139 ~Task_block_token();
141 private:
142 Task_block_token(const Task_block_token&);
143 Task_block_token& operator=(const Task_block_token&);
145 Task_token& token_;
146 Workqueue* workqueue_;
149 // An object which implements an RAII lock for any object which
150 // supports lock and unlock methods.
152 template<typename Obj>
153 class Task_lock_obj
155 public:
156 Task_lock_obj(Obj& obj)
157 : obj_(obj)
158 { this->obj_.lock(); }
160 ~Task_lock_obj()
161 { this->obj_.unlock(); }
163 private:
164 Task_lock_obj(const Task_lock_obj&);
165 Task_lock_obj& operator=(const Task_lock_obj&);
167 Obj& obj_;
170 // An abstract class used to lock Task_tokens using RAII. A typical
171 // implementation would simply have a set of members of type
172 // Task_read_token, Task_write_token, and Task_block_token.
174 class Task_locker
176 public:
177 Task_locker()
180 virtual ~Task_locker()
184 // A version of Task_locker which may be used for a single read lock.
186 class Task_locker_read : public Task_locker
188 public:
189 Task_locker_read(Task_token& token)
190 : read_token_(token)
193 private:
194 Task_locker_read(const Task_locker_read&);
195 Task_locker_read& operator=(const Task_locker_read&);
197 Task_read_token read_token_;
200 // A version of Task_locker which may be used for a single write lock.
202 class Task_locker_write : public Task_locker
204 public:
205 Task_locker_write(Task_token& token, const Task* task)
206 : write_token_(token, task)
209 private:
210 Task_locker_write(const Task_locker_write&);
211 Task_locker_write& operator=(const Task_locker_write&);
213 Task_write_token write_token_;
216 // A version of Task_locker which may be used for a single blocker
217 // lock.
219 class Task_locker_block : public Task_locker
221 public:
222 Task_locker_block(Task_token& token, Workqueue* workqueue)
223 : block_token_(token, workqueue)
226 private:
227 Task_locker_block(const Task_locker_block&);
228 Task_locker_block& operator=(const Task_locker_block&);
230 Task_block_token block_token_;
233 // A version of Task_locker which may be used to hold a lock on any
234 // object which supports lock() and unlock() methods.
236 template<typename Obj>
237 class Task_locker_obj : public Task_locker
239 public:
240 Task_locker_obj(Obj& obj)
241 : obj_lock_(obj)
244 private:
245 Task_locker_obj(const Task_locker_obj&);
246 Task_locker_obj& operator=(const Task_locker_obj&);
248 Task_lock_obj<Obj> obj_lock_;
251 // The superclass for tasks to be placed on the workqueue. Each
252 // specific task class will inherit from this one.
254 class Task
256 public:
257 Task()
259 virtual ~Task()
262 // Type returned by Is_runnable.
263 enum Is_runnable_type
265 // Task is runnable.
266 IS_RUNNABLE,
267 // Task is waiting for a block to clear.
268 IS_BLOCKED,
269 // Task is not waiting for a block, but is not runnable--i.e., is
270 // waiting for a lock.
271 IS_LOCKED
274 // Return whether the task can be run now. This method is only
275 // called from the main thread.
276 virtual Is_runnable_type
277 is_runnable(Workqueue*) = 0;
279 // Return a pointer to a Task_locker which locks all the resources
280 // required by the task. We delete the pointer when the task is
281 // complete. This method can return NULL if no locks are required.
282 // This method is only called from the main thread.
283 virtual Task_locker*
284 locks(Workqueue*) = 0;
286 // Run the task.
287 virtual void
288 run(Workqueue*) = 0;
290 private:
291 Task(const Task&);
292 Task& operator=(const Task&);
295 // A simple task which waits for a blocker and then runs a function.
297 class Task_function_runner
299 public:
300 virtual ~Task_function_runner()
303 virtual void
304 run(Workqueue*) = 0;
307 class Task_function : public Task
309 public:
310 // Both points should be allocated using new, and will be deleted
311 // after the task runs.
312 Task_function(Task_function_runner* runner, Task_token* blocker)
313 : runner_(runner), blocker_(blocker)
316 ~Task_function()
318 delete this->runner_;
319 delete this->blocker_;
322 // The standard task methods.
324 // Wait until the task is unblocked.
325 Is_runnable_type
326 is_runnable(Workqueue*)
327 { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; }
329 // This type of task does not normally hold any locks.
330 virtual Task_locker*
331 locks(Workqueue*)
332 { return NULL; }
334 // Run the action.
335 void
336 run(Workqueue* workqueue)
337 { this->runner_->run(workqueue); }
339 private:
340 Task_function(const Task_function&);
341 Task_function& operator=(const Task_function&);
343 Task_function_runner* runner_;
344 Task_token* blocker_;
347 // The workqueue
349 class Workqueue_runner;
351 class Workqueue
353 public:
354 Workqueue(const General_options&);
355 ~Workqueue();
357 // Add a new task to the work queue.
358 void
359 queue(Task*);
361 // Add a new task to the front of the work queue. It will be the
362 // next task to run if it is ready.
363 void
364 queue_front(Task*);
366 // Process all the tasks on the work queue.
367 void
368 process();
370 // A complete set of blocking tasks has completed.
371 void
372 cleared_blocker();
374 private:
375 // This class can not be copied.
376 Workqueue(const Workqueue&);
377 Workqueue& operator=(const Workqueue&);
379 typedef std::list<Task*> Task_list;
381 // Run a task.
382 void run(Task*);
384 friend class Workqueue_runner;
386 // Find a runnable task.
387 Task* find_runnable(Task_list&, bool*);
389 // Add a lock to the completed queue.
390 void completed(Task*, Task_locker*);
392 // Clear the completed queue.
393 bool clear_completed();
395 // How to run a task. Only accessed from main thread.
396 Workqueue_runner* runner_;
398 // Lock for access to tasks_ members.
399 Lock tasks_lock_;
400 // List of tasks to execute at each link level.
401 Task_list tasks_;
403 // Lock for access to completed_ and running_ members.
404 Lock completed_lock_;
405 // List of Task_locker objects for main thread to free.
406 std::list<Task_locker*> completed_;
407 // Number of tasks currently running.
408 int running_;
409 // Condition variable signalled when a new entry is added to completed_.
410 Condvar completed_condvar_;
412 // Number of blocker tokens which were fully cleared. Only accessed
413 // from main thread.
414 int cleared_blockers_;
417 } // End namespace gold.
419 #endif // !defined(GOLD_WORKQUEUE_H)