1 // workqueue.h -- the work queue for gold -*- C++ -*-
2
3 // Copyright (C) 2006-2023 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)