summaryrefslogtreecommitdiff
path: root/gold/workqueue.h
blob: 3b7a764d73796b10890e7db16781fd35726c8a72 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
// workqueue.h -- the work queue for gold   -*- C++ -*-

// Copyright 2006, 2007, 2008 Free Software Foundation, Inc.
// Written by Ian Lance Taylor <iant@google.com>.

// This file is part of gold.

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston,
// MA 02110-1301, USA.

// After processing the command line, everything the linker does is
// driven from a work queue.  This permits us to parallelize the
// linker where possible.

#ifndef GOLD_WORKQUEUE_H
#define GOLD_WORKQUEUE_H

#include <string>

#include "gold-threads.h"
#include "token.h"

namespace gold
{

class General_options;
class Workqueue;

// The superclass for tasks to be placed on the workqueue.  Each
// specific task class will inherit from this one.

class Task
{
 public:
  Task()
    : list_next_(NULL), name_(), should_run_soon_(false)
  { }
  virtual ~Task()
  { }

  // Check whether the Task can be run now.  This method is only
  // called with the workqueue lock held.  If the Task can run, this
  // returns NULL.  Otherwise it returns a pointer to a token which
  // must be released before the Task can run.
  virtual Task_token*
  is_runnable() = 0;

  // Lock all the resources required by the Task, and store the locks
  // in a Task_locker.  This method does not need to do anything if no
  // locks are required.  This method is only called with the
  // workqueue lock held.
  virtual void
  locks(Task_locker*) = 0;

  // Run the task.
  virtual void
  run(Workqueue*) = 0;

  // Return whether this task should run soon.
  bool
  should_run_soon() const
  { return this->should_run_soon_; }

  // Note that this task should run soon.
  void
  set_should_run_soon()
  { this->should_run_soon_ = true; }

  // Get the next Task on the list of Tasks.  Called by Task_list.
  Task*
  list_next() const
  { return this->list_next_; }

  // Set the next Task on the list of Tasks.  Called by Task_list.
  void
  set_list_next(Task* t)
  {
    gold_assert(this->list_next_ == NULL);
    this->list_next_ = t;
  }

  // Clear the next Task on the list of Tasks.  Called by Task_list.
  void
  clear_list_next()
  { this->list_next_ = NULL; }

  // Return the name of the Task.  This is only used for debugging
  // purposes.
  const std::string&
  name()
  {
    if (this->name_.empty())
      this->name_ = this->get_name();
    return this->name_;
  }

 protected:
  // Get the name of the task.  This must be implemented by the child
  // class.
  virtual std::string
  get_name() const = 0;

 private:
  // Tasks may not be copied.
  Task(const Task&);
  Task& operator=(const Task&);

  // If this Task is on a list, this is a pointer to the next Task on
  // the list.  We use this simple list structure rather than building
  // a container, in order to avoid memory allocation while holding
  // the Workqueue lock.
  Task* list_next_;
  // Task name, for debugging purposes.
  std::string name_;
  // Whether this Task should be executed soon.  This is used for
  // Tasks which can be run after some data is read.
  bool should_run_soon_;
};

// An interface for Task_function.  This is a convenience class to run
// a single function.

class Task_function_runner
{
 public:
  virtual ~Task_function_runner()
  { }

  virtual void
  run(Workqueue*, const Task*) = 0;
};

// A simple task which waits for a blocker and then runs a function.

class Task_function : public Task
{
 public:
  // RUNNER and BLOCKER should be allocated using new, and will be
  // deleted after the task runs.
  Task_function(Task_function_runner* runner, Task_token* blocker,
		const char* name)
    : runner_(runner), blocker_(blocker), name_(name)
  { }

  ~Task_function()
  {
    delete this->runner_;
    delete this->blocker_;
  }

  // The standard task methods.

  // Wait until the task is unblocked.
  Task_token*
  is_runnable()
  { return this->blocker_->is_blocked() ? this->blocker_ : NULL; }

  // This type of task does not normally hold any locks.
  virtual void
  locks(Task_locker*)
  { }

  // Run the action.
  void
  run(Workqueue* workqueue)
  { this->runner_->run(workqueue, this); }

  // The debugging name.
  std::string
  get_name() const
  { return this->name_; }

 private:
  Task_function(const Task_function&);
  Task_function& operator=(const Task_function&);

  Task_function_runner* runner_;
  Task_token* blocker_;
  const char* name_;
};

// The workqueue itself.

class Workqueue_threader;

class Workqueue
{
 public:
  Workqueue(const General_options&);
  ~Workqueue();

  // Add a new task to the work queue.
  void
  queue(Task*);

  // Add a new task to the work queue which should run soon.  If the
  // task is ready, it will be run before any tasks added using
  // queue().
  void
  queue_soon(Task*);

  // Add a new task to the work queue which should run next if it is
  // ready.
  void
  queue_next(Task*);

  // Process all the tasks on the work queue.  This function runs
  // until all tasks have completed.  The argument is the thread
  // number, used only for debugging.
  void
  process(int);

  // Set the desired thread count--the number of threads we want to
  // have running.
  void
  set_thread_count(int);

 private:
  // This class can not be copied.
  Workqueue(const Workqueue&);
  Workqueue& operator=(const Workqueue&);

  // Add a task to a queue.
  void
  add_to_queue(Task_list* queue, Task* t, bool front);

  // Find a runnable task, or wait for one.
  Task*
  find_runnable_or_wait(int thread_number);

  // Find a runnable task.
  Task*
  find_runnable();

  // Find a runnable task in a list.
  Task*
  find_runnable_in_list(Task_list*);

  // Find an run a task.
  bool
  find_and_run_task(int);

  // Release the locks for a Task.  Return the next Task to run.
  Task*
  release_locks(Task*, Task_locker*);

  // Store T into *PRET, or queue it as appropriate.
  bool
  return_or_queue(Task* t, bool is_blocker, Task** pret);

  // Return whether to cancel this thread.
  bool
  should_cancel_thread();

  // Master Workqueue lock.  This controls access to the following
  // member variables.
  Lock lock_;
  // List of tasks to execute soon.
  Task_list first_tasks_;
  // List of tasks to execute after the ones in first_tasks_.
  Task_list tasks_;
  // Number of tasks currently running.
  int running_;
  // Number of tasks waiting for a lock to release.
  int waiting_;
  // Condition variable associated with lock_.  This is signalled when
  // there may be a new Task to execute.
  Condvar condvar_;

  // The threading implementation.  This is set at construction time
  // and not changed thereafter.
  Workqueue_threader* threader_;
};

} // End namespace gold.

#endif // !defined(GOLD_WORKQUEUE_H)