Hash tables, dynamic section, i386 PLT, gold_assert.
[platform/upstream/binutils.git] / gold / workqueue.cc
1 // workqueue.cc -- the workqueue for gold
2
3 #include "gold.h"
4
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 {
19   gold_assert(this->readers_ == 0 && this->writer_ == NULL);
20 }
21
22 bool
23 Task_token::is_readable() const
24 {
25   gold_assert(!this->is_blocker_);
26   return this->writer_ == NULL;
27 }
28
29 void
30 Task_token::add_reader()
31 {
32   gold_assert(!this->is_blocker_);
33   gold_assert(this->is_readable());
34   ++this->readers_;
35 }
36
37 void
38 Task_token::remove_reader()
39 {
40   gold_assert(!this->is_blocker_);
41   gold_assert(this->readers_ > 0);
42   --this->readers_;
43 }
44
45 bool
46 Task_token::is_writable() const
47 {
48   gold_assert(!this->is_blocker_);
49   return this->writer_ == NULL && this->readers_ == 0;
50 }
51
52 void
53 Task_token::add_writer(const Task* t)
54 {
55   gold_assert(!this->is_blocker_);
56   gold_assert(this->is_writable());
57   this->writer_ = t;
58 }
59
60 void
61 Task_token::remove_writer(const Task* t)
62 {
63   gold_assert(!this->is_blocker_);
64   gold_assert(this->writer_ == t);
65   this->writer_ = NULL;
66 }
67
68 bool
69 Task_token::has_write_lock(const Task* t)
70 {
71   gold_assert(!this->is_blocker_);
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
83     gold_assert(this->is_blocker_);
84   ++this->readers_;
85 }
86
87 bool
88 Task_token::remove_blocker()
89 {
90   gold_assert(this->is_blocker_ && this->readers_ > 0);
91   --this->readers_;
92   return this->readers_ == 0;
93 }
94
95 bool
96 Task_token::is_blocked() const
97 {
98   gold_assert(this->is_blocker_
99               || (this->readers_ == 0 && this->writer_ == NULL));
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.
111   gold_assert(this->token_.is_blocked());
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 {
189   gold_assert(this->tasks_.empty());
190   gold_assert(this->completed_.empty());
191   gold_assert(this->running_ == 0);
192 }
193
194 // Add a task to the queue.
195
196 void
197 Workqueue::queue(Task* t)
198 {
199   Hold_lock hl(this->tasks_lock_);
200   this->tasks_.push_back(t);
201 }
202
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
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.
265                 gold_assert(this->running_ > 0);
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.
324             gold_assert(this->running_ > 0 || !this->completed_.empty());
325
326             if (all_blocked)
327               {
328                 this->cleared_blockers_ = 0;
329                 this->clear_completed();
330                 while (this->cleared_blockers_ == 0)
331                   {
332                     gold_assert(this->running_ > 0);
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_);
387     gold_assert(this->running_ > 0);
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.