| 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(); |
| 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) |