gold/workqueue.h

   1 // workqueue.h -- the work queue for gold   -*- C++ -*-
   2
   3 // After processing the command line, everything the linker does is
   4 // driven from a work queue.  This permits us to parallelize the
   5 // linker where possible.
   6
   7 // Task_token
   8 //   A simple locking implementation to ensure proper task ordering.
   9 // Task_read_token, Task_write_token
  10 //   Lock a Task_token for read or write.
  11 // Task_locker
  12 //   Task locking using RAII.
  13 // Task
  14 //   An abstract class for jobs to run.
  15
  16 #ifndef GOLD_WORKQUEUE_H
  17 #define GOLD_WORKQUEUE_H
  18
  19 #include "gold-threads.h"
  20 #include "options.h"
  21 #include "fileread.h"
  22
  23 namespace gold
  24 {
  25
  26 class Task;
  27 class Workqueue;
  28
  29 // Some tasks require access to shared data structures, such as the
  30 // symbol table.  Some tasks must be executed in a particular error,
  31 // such as reading input file symbol tables--if we see foo.o -llib, we
  32 // have to read the symbols for foo.o before we read the ones for
  33 // -llib.  To implement this safely and efficiently, we use tokens.
  34 // Task_tokens support shared read/exclusive write access to some
  35 // resource.  Alternatively, they support blockers: blockers implement
  36 // the requirement that some set of tasks must complete before another
  37 // set of tasks can start.  In such a case we increment the block
  38 // count when we create the task, and decrement it when the task
  39 // completes.  Task_tokens are only manipulated by the main thread, so
  40 // they do not themselves require any locking.
  41
  42 class Task_token
  43 {
  44  public:
  45   Task_token();
  46
  47   ~Task_token();
  48
  49   // A read/write token uses these methods.
  50
  51   bool
  52   is_readable() const;
  53
  54   void
  55   add_reader();
  56
  57   void
  58   remove_reader();
  59
  60   bool
  61   is_writable() const;
  62
  63   void
  64   add_writer(const Task*);
  65
  66   void
  67   remove_writer(const Task*);
  68
  69   bool
  70   has_write_lock(const Task*);
  71
  72   // A blocker token uses these methods.
  73
  74   void
  75   add_blocker();
  76
  77   // Returns true if block count drops to zero.
  78   bool
  79   remove_blocker();
  80
  81   bool
  82   is_blocked() const;
  83
  84  private:
  85   // It makes no sense to copy these.
  86   Task_token(const Task_token&);
  87   Task_token& operator=(const Task_token&);
  88
  89   bool is_blocker_;
  90   int readers_;
  91   const Task* writer_;
  92 };
  93
  94 // In order to support tokens more reliably, we provide objects which
  95 // handle them using RAII.
  96
  97 class Task_read_token
  98 {
  99  public:
 100   Task_read_token(Task_token& token)
 101     : token_(token)
 102   { this->token_.add_reader(); }
 103
 104   ~Task_read_token()
 105   { this->token_.remove_reader(); }
 106
 107  private:
 108   Task_read_token(const Task_read_token&);
 109   Task_read_token& operator=(const Task_read_token&);
 110
 111   Task_token& token_;
 112 };
 113
 114 class Task_write_token
 115 {
 116  public:
 117   Task_write_token(Task_token& token, const Task* task)
 118     : token_(token), task_(task)
 119   { this->token_.add_writer(this->task_); }
 120
 121   ~Task_write_token()
 122   { this->token_.remove_writer(this->task_); }
 123
 124  private:
 125   Task_write_token(const Task_write_token&);
 126   Task_write_token& operator=(const Task_write_token&);
 127
 128   Task_token& token_;
 129   const Task* task_;
 130 };
 131
 132 class Task_block_token
 133 {
 134  public:
 135   // The blocker count must be incremented when the task is created.
 136   // This object is created when the task is run.  When we unblock the
 137   // last task, we notify the workqueue.
 138   Task_block_token(Task_token& token, Workqueue* workqueue);
 139   ~Task_block_token();
 140
 141  private:
 142   Task_block_token(const Task_block_token&);
 143   Task_block_token& operator=(const Task_block_token&);
 144
 145   Task_token& token_;
 146   Workqueue* workqueue_;
 147 };
 148
 149 // An abstract class used to lock Task_tokens using RAII.  A typical
 150 // implementation would simply have a set of members of type
 151 // Task_read_token, Task_write_token, and Task_block_token.
 152
 153 class Task_locker
 154 {
 155  public:
 156   Task_locker()
 157   { }
 158
 159   virtual ~Task_locker()
 160   { }
 161 };
 162
 163 // A version of Task_locker which may be used for a single read lock.
 164
 165 class Task_locker_read : public Task_locker
 166 {
 167  public:
 168   Task_locker_read(Task_token& token)
 169     : read_token_(token)
 170   { }
 171
 172  private:
 173   Task_locker_read(const Task_locker_read&);
 174   Task_locker_read& operator=(const Task_locker_read&);
 175
 176   Task_read_token read_token_;
 177 };
 178
 179 // A version of Task_locker which may be used for a single write lock.
 180
 181 class Task_locker_write : public Task_locker
 182 {
 183  public:
 184   Task_locker_write(Task_token& token, const Task* task)
 185     : write_token_(token, task)
 186   { }
 187
 188  private:
 189   Task_locker_write(const Task_locker_write&);
 190   Task_locker_write& operator=(const Task_locker_write&);
 191
 192   Task_write_token write_token_;
 193 };
 194
 195 // A version of Task_locker which may be used for a single blocker
 196 // lock.
 197
 198 class Task_locker_block : public Task_locker
 199 {
 200  public:
 201   Task_locker_block(Task_token& token, Workqueue* workqueue)
 202     : block_token_(token, workqueue)
 203   { }
 204
 205  private:
 206   Task_locker_block(const Task_locker_block&);
 207   Task_locker_block& operator=(const Task_locker_block&);
 208
 209   Task_block_token block_token_;
 210 };
 211
 212 // A version of Task_locker which may be used to hold a lock on a
 213 // File_read.
 214
 215 class Task_locker_file : public Task_locker
 216 {
 217  public:
 218   Task_locker_file(File_read& file)
 219     : file_lock_(file)
 220   { }
 221
 222  private:
 223   Task_locker_file(const Task_locker_file&);
 224   Task_locker_file& operator=(const Task_locker_file&);
 225
 226   File_read_lock file_lock_;
 227 };
 228
 229 // The superclass for tasks to be placed on the workqueue.  Each
 230 // specific task class will inherit from this one.
 231
 232 class Task
 233 {
 234  public:
 235   Task()
 236   { }
 237   virtual ~Task()
 238   { }
 239
 240   // Type returned by Is_runnable.
 241   enum Is_runnable_type
 242   {
 243     // Task is runnable.
 244     IS_RUNNABLE,
 245     // Task is waiting for a block to clear.
 246     IS_BLOCKED,
 247     // Task is not waiting for a block, but is not runnable--i.e., is
 248     // waiting for a lock.
 249     IS_LOCKED
 250   };
 251
 252   // Return whether the task can be run now.  This method is only
 253   // called from the main thread.
 254   virtual Is_runnable_type
 255   is_runnable(Workqueue*) = 0;
 256
 257   // Return a pointer to a Task_locker which locks all the resources
 258   // required by the task.  We delete the pointer when the task is
 259   // complete.  This method can return NULL if no locks are required.
 260   // This method is only called from the main thread.
 261   virtual Task_locker*
 262   locks(Workqueue*) = 0;
 263
 264   // Run the task.
 265   virtual void
 266   run(Workqueue*) = 0;
 267 };
 268
 269 // The workqueue
 270
 271 class Workqueue_runner;
 272
 273 class Workqueue
 274 {
 275  public:
 276   Workqueue(const General_options&);
 277   ~Workqueue();
 278
 279   // Add a new task to the work queue.
 280   void
 281   queue(Task*);
 282
 283   // Process all the tasks on the work queue.
 284   void
 285   process();
 286
 287   // A complete set of blocking tasks has completed.
 288   void
 289   cleared_blocker();
 290
 291  private:
 292   // This class can not be copied.
 293   Workqueue(const Workqueue&);
 294   Workqueue& operator=(const Workqueue&);
 295
 296   typedef std::list<Task*> Task_list;
 297
 298   // Run a task.
 299   void run(Task*);
 300
 301   friend class Workqueue_runner;
 302
 303   // Find a runnable task.
 304   Task* find_runnable(Task_list&, bool*);
 305
 306   // Add a lock to the completed queue.
 307   void completed(Task*, Task_locker*);
 308
 309   // Clear the completed queue.
 310   bool clear_completed();
 311
 312   // How to run a task.  Only accessed from main thread.
 313   Workqueue_runner* runner_;
 314
 315   // Lock for access to tasks_ members.
 316   Lock tasks_lock_;
 317   // List of tasks to execute at each link level.
 318   Task_list tasks_;
 319
 320   // Lock for access to completed_ and running_ members.
 321   Lock completed_lock_;
 322   // List of Task_locker objects for main thread to free.
 323   std::list<Task_locker*> completed_;
 324   // Number of tasks currently running.
 325   int running_;
 326   // Condition variable signalled when a new entry is added to completed_.
 327   Condvar completed_condvar_;
 328
 329   // Number of blocker tokens which were fully cleared.  Only accessed
 330   // from main thread.
 331   int cleared_blockers_;
 332 };
 333
 334 } // End namespace gold.
 335
 336 #endif // !defined(GOLD_WORKQUEUE_H)