Merge branch 'vendor/GCC44'
[dragonfly.git] / contrib / binutils-2.22 / gold / workqueue.h
1 // workqueue.h -- the work queue for gold   -*- C++ -*-
2
3 // Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
4 // Written by Ian Lance Taylor <iant@google.com>.
5
6 // This file is part of gold.
7
8 // This program is free software; you can redistribute it and/or modify
9 // it under the terms of the GNU General Public License as published by
10 // the Free Software Foundation; either version 3 of the License, or
11 // (at your option) any later version.
12
13 // This program is distributed in the hope that it will be useful,
14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 // GNU General Public License for more details.
17
18 // You should have received a copy of the GNU General Public License
19 // along with this program; if not, write to the Free Software
20 // Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
21 // MA 02110-1301, USA.
22
23 // After processing the command line, everything the linker does is
24 // driven from a work queue.  This permits us to parallelize the
25 // linker where possible.
26
27 #ifndef GOLD_WORKQUEUE_H
28 #define GOLD_WORKQUEUE_H
29
30 #include <string>
31
32 #include "gold-threads.h"
33 #include "token.h"
34
35 namespace gold
36 {
37
38 class General_options;
39 class Workqueue;
40
41 // The superclass for tasks to be placed on the workqueue.  Each
42 // specific task class will inherit from this one.
43
44 class Task
45 {
46  public:
47   Task()
48     : list_next_(NULL), name_(), should_run_soon_(false)
49   { }
50   virtual ~Task()
51   { }
52
53   // Check whether the Task can be run now.  This method is only
54   // called with the workqueue lock held.  If the Task can run, this
55   // returns NULL.  Otherwise it returns a pointer to a token which
56   // must be released before the Task can run.
57   virtual Task_token*
58   is_runnable() = 0;
59
60   // Lock all the resources required by the Task, and store the locks
61   // in a Task_locker.  This method does not need to do anything if no
62   // locks are required.  This method is only called with the
63   // workqueue lock held.
64   virtual void
65   locks(Task_locker*) = 0;
66
67   // Run the task.
68   virtual void
69   run(Workqueue*) = 0;
70
71   // Return whether this task should run soon.
72   bool
73   should_run_soon() const
74   { return this->should_run_soon_; }
75
76   // Note that this task should run soon.
77   void
78   set_should_run_soon()
79   { this->should_run_soon_ = true; }
80
81   // Get the next Task on the list of Tasks.  Called by Task_list.
82   Task*
83   list_next() const
84   { return this->list_next_; }
85
86   // Set the next Task on the list of Tasks.  Called by Task_list.
87   void
88   set_list_next(Task* t)
89   {
90     gold_assert(this->list_next_ == NULL);
91     this->list_next_ = t;
92   }
93
94   // Clear the next Task on the list of Tasks.  Called by Task_list.
95   void
96   clear_list_next()
97   { this->list_next_ = NULL; }
98
99   // Return the name of the Task.  This is only used for debugging
100   // purposes.
101   const std::string&
102   name()
103   {
104     if (this->name_.empty())
105       this->name_ = this->get_name();
106     return this->name_;
107   }
108
109  protected:
110   // Get the name of the task.  This must be implemented by the child
111   // class.
112   virtual std::string
113   get_name() const = 0;
114
115  private:
116   // Tasks may not be copied.
117   Task(const Task&);
118   Task& operator=(const Task&);
119
120   // If this Task is on a list, this is a pointer to the next Task on
121   // the list.  We use this simple list structure rather than building
122   // a container, in order to avoid memory allocation while holding
123   // the Workqueue lock.
124   Task* list_next_;
125   // Task name, for debugging purposes.
126   std::string name_;
127   // Whether this Task should be executed soon.  This is used for
128   // Tasks which can be run after some data is read.
129   bool should_run_soon_;
130 };
131
132 // An interface for Task_function.  This is a convenience class to run
133 // a single function.
134
135 class Task_function_runner
136 {
137  public:
138   virtual ~Task_function_runner()
139   { }
140
141   virtual void
142   run(Workqueue*, const Task*) = 0;
143 };
144
145 // A simple task which waits for a blocker and then runs a function.
146
147 class Task_function : public Task
148 {
149  public:
150   // RUNNER and BLOCKER should be allocated using new, and will be
151   // deleted after the task runs.
152   Task_function(Task_function_runner* runner, Task_token* blocker,
153                 const char* name)
154     : runner_(runner), blocker_(blocker), name_(name)
155   { gold_assert(blocker != NULL); }
156
157   ~Task_function()
158   {
159     delete this->runner_;
160     delete this->blocker_;
161   }
162
163   // The standard task methods.
164
165   // Wait until the task is unblocked.
166   Task_token*
167   is_runnable()
168   { return this->blocker_->is_blocked() ? this->blocker_ : NULL; }
169
170   // This type of task does not normally hold any locks.
171   virtual void
172   locks(Task_locker*)
173   { }
174
175   // Run the action.
176   void
177   run(Workqueue* workqueue)
178   { this->runner_->run(workqueue, this); }
179
180   // The debugging name.
181   std::string
182   get_name() const
183   { return this->name_; }
184
185  private:
186   Task_function(const Task_function&);
187   Task_function& operator=(const Task_function&);
188
189   Task_function_runner* runner_;
190   Task_token* blocker_;
191   const char* name_;
192 };
193
194 // The workqueue itself.
195
196 class Workqueue_threader;
197
198 class Workqueue
199 {
200  public:
201   Workqueue(const General_options&);
202   ~Workqueue();
203
204   // Add a new task to the work queue.
205   void
206   queue(Task*);
207
208   // Add a new task to the work queue which should run soon.  If the
209   // task is ready, it will be run before any tasks added using
210   // queue().
211   void
212   queue_soon(Task*);
213
214   // Add a new task to the work queue which should run next if it is
215   // ready.
216   void
217   queue_next(Task*);
218
219   // Process all the tasks on the work queue.  This function runs
220   // until all tasks have completed.  The argument is the thread
221   // number, used only for debugging.
222   void
223   process(int);
224
225   // Set the desired thread count--the number of threads we want to
226   // have running.
227   void
228   set_thread_count(int);
229
230   // Add a new blocker to an existing Task_token. This must be done
231   // with the workqueue lock held.  This should not be done routinely,
232   // only in special circumstances.
233   void
234   add_blocker(Task_token*);
235
236  private:
237   // This class can not be copied.
238   Workqueue(const Workqueue&);
239   Workqueue& operator=(const Workqueue&);
240
241   // Add a task to a queue.
242   void
243   add_to_queue(Task_list* queue, Task* t, bool front);
244
245   // Find a runnable task, or wait for one.
246   Task*
247   find_runnable_or_wait(int thread_number);
248
249   // Find a runnable task.
250   Task*
251   find_runnable();
252
253   // Find a runnable task in a list.
254   Task*
255   find_runnable_in_list(Task_list*);
256
257   // Find an run a task.
258   bool
259   find_and_run_task(int);
260
261   // Release the locks for a Task.  Return the next Task to run.
262   Task*
263   release_locks(Task*, Task_locker*);
264
265   // Store T into *PRET, or queue it as appropriate.
266   bool
267   return_or_queue(Task* t, bool is_blocker, Task** pret);
268
269   // Return whether to cancel this thread.
270   bool
271   should_cancel_thread(int thread_number);
272
273   // Master Workqueue lock.  This controls access to the following
274   // member variables.
275   Lock lock_;
276   // List of tasks to execute soon.
277   Task_list first_tasks_;
278   // List of tasks to execute after the ones in first_tasks_.
279   Task_list tasks_;
280   // Number of tasks currently running.
281   int running_;
282   // Number of tasks waiting for a lock to release.
283   int waiting_;
284   // Condition variable associated with lock_.  This is signalled when
285   // there may be a new Task to execute.
286   Condvar condvar_;
287
288   // The threading implementation.  This is set at construction time
289   // and not changed thereafter.
290   Workqueue_threader* threader_;
291 };
292
293 } // End namespace gold.
294
295 #endif // !defined(GOLD_WORKQUEUE_H)