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   { }
 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  private:
 231   // This class can not be copied.
 232   Workqueue(const Workqueue&);
 233   Workqueue& operator=(const Workqueue&);
 234
 235   // Add a task to a queue.
 236   void
 237   add_to_queue(Task_list* queue, Task* t, bool front);
 238
 239   // Find a runnable task, or wait for one.
 240   Task*
 241   find_runnable_or_wait(int thread_number);
 242
 243   // Find a runnable task.
 244   Task*
 245   find_runnable();
 246
 247   // Find a runnable task in a list.
 248   Task*
 249   find_runnable_in_list(Task_list*);
 250
 251   // Find an run a task.
 252   bool
 253   find_and_run_task(int);
 254
 255   // Release the locks for a Task.  Return the next Task to run.
 256   Task*
 257   release_locks(Task*, Task_locker*);
 258
 259   // Store T into *PRET, or queue it as appropriate.
 260   bool
 261   return_or_queue(Task* t, bool is_blocker, Task** pret);
 262
 263   // Return whether to cancel this thread.
 264   bool
 265   should_cancel_thread();
 266
 267   // Master Workqueue lock.  This controls access to the following
 268   // member variables.
 269   Lock lock_;
 270   // List of tasks to execute soon.
 271   Task_list first_tasks_;
 272   // List of tasks to execute after the ones in first_tasks_.
 273   Task_list tasks_;
 274   // Number of tasks currently running.
 275   int running_;
 276   // Number of tasks waiting for a lock to release.
 277   int waiting_;
 278   // Condition variable associated with lock_.  This is signalled when
 279   // there may be a new Task to execute.
 280   Condvar condvar_;
 281
 282   // The threading implementation.  This is set at construction time
 283   // and not changed thereafter.
 284   Workqueue_threader* threader_;
 285 };
 286
 287 } // End namespace gold.
 288
 289 #endif // !defined(GOLD_WORKQUEUE_H)