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 "fileread.h"
  21
  22 namespace gold
  23 {
  24
  25 class General_options;
  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 object which implements an RAII lock for any object which
 150 // supports lock and unlock methods.
 151
 152 template<typename Obj>
 153 class Task_lock_obj
 154 {
 155  public:
 156   Task_lock_obj(Obj& obj)
 157     : obj_(obj)
 158   { this->obj_.lock(); }
 159
 160   ~Task_lock_obj()
 161   { this->obj_.unlock(); }
 162
 163  private:
 164   Task_lock_obj(const Task_lock_obj&);
 165   Task_lock_obj& operator=(const Task_lock_obj&);
 166
 167   Obj& obj_;
 168 };
 169
 170 // An abstract class used to lock Task_tokens using RAII.  A typical
 171 // implementation would simply have a set of members of type
 172 // Task_read_token, Task_write_token, and Task_block_token.
 173
 174 class Task_locker
 175 {
 176  public:
 177   Task_locker()
 178   { }
 179
 180   virtual ~Task_locker()
 181   { }
 182 };
 183
 184 // A version of Task_locker which may be used for a single read lock.
 185
 186 class Task_locker_read : public Task_locker
 187 {
 188  public:
 189   Task_locker_read(Task_token& token)
 190     : read_token_(token)
 191   { }
 192
 193  private:
 194   Task_locker_read(const Task_locker_read&);
 195   Task_locker_read& operator=(const Task_locker_read&);
 196
 197   Task_read_token read_token_;
 198 };
 199
 200 // A version of Task_locker which may be used for a single write lock.
 201
 202 class Task_locker_write : public Task_locker
 203 {
 204  public:
 205   Task_locker_write(Task_token& token, const Task* task)
 206     : write_token_(token, task)
 207   { }
 208
 209  private:
 210   Task_locker_write(const Task_locker_write&);
 211   Task_locker_write& operator=(const Task_locker_write&);
 212
 213   Task_write_token write_token_;
 214 };
 215
 216 // A version of Task_locker which may be used for a single blocker
 217 // lock.
 218
 219 class Task_locker_block : public Task_locker
 220 {
 221  public:
 222   Task_locker_block(Task_token& token, Workqueue* workqueue)
 223     : block_token_(token, workqueue)
 224   { }
 225
 226  private:
 227   Task_locker_block(const Task_locker_block&);
 228   Task_locker_block& operator=(const Task_locker_block&);
 229
 230   Task_block_token block_token_;
 231 };
 232
 233 // A version of Task_locker which may be used to hold a lock on any
 234 // object which supports lock() and unlock() methods.
 235
 236 template<typename Obj>
 237 class Task_locker_obj : public Task_locker
 238 {
 239  public:
 240   Task_locker_obj(Obj& obj)
 241     : obj_lock_(obj)
 242   { }
 243
 244  private:
 245   Task_locker_obj(const Task_locker_obj&);
 246   Task_locker_obj& operator=(const Task_locker_obj&);
 247
 248   Task_lock_obj<Obj> obj_lock_;
 249 };
 250
 251 // The superclass for tasks to be placed on the workqueue.  Each
 252 // specific task class will inherit from this one.
 253
 254 class Task
 255 {
 256  public:
 257   Task()
 258   { }
 259   virtual ~Task()
 260   { }
 261
 262   // Type returned by Is_runnable.
 263   enum Is_runnable_type
 264   {
 265     // Task is runnable.
 266     IS_RUNNABLE,
 267     // Task is waiting for a block to clear.
 268     IS_BLOCKED,
 269     // Task is not waiting for a block, but is not runnable--i.e., is
 270     // waiting for a lock.
 271     IS_LOCKED
 272   };
 273
 274   // Return whether the task can be run now.  This method is only
 275   // called from the main thread.
 276   virtual Is_runnable_type
 277   is_runnable(Workqueue*) = 0;
 278
 279   // Return a pointer to a Task_locker which locks all the resources
 280   // required by the task.  We delete the pointer when the task is
 281   // complete.  This method can return NULL if no locks are required.
 282   // This method is only called from the main thread.
 283   virtual Task_locker*
 284   locks(Workqueue*) = 0;
 285
 286   // Run the task.
 287   virtual void
 288   run(Workqueue*) = 0;
 289
 290  private:
 291   Task(const Task&);
 292   Task& operator=(const Task&);
 293 };
 294
 295 // A simple task which waits for a blocker and then runs a function.
 296
 297 class Task_function_runner
 298 {
 299  public:
 300   virtual ~Task_function_runner()
 301   { }
 302
 303   virtual void
 304   run(Workqueue*) = 0;
 305 };
 306
 307 class Task_function : public Task
 308 {
 309  public:
 310   // Both points should be allocated using new, and will be deleted
 311   // after the task runs.
 312   Task_function(Task_function_runner* runner, Task_token* blocker)
 313     : runner_(runner), blocker_(blocker)
 314   { }
 315
 316   ~Task_function()
 317   {
 318     delete this->runner_;
 319     delete this->blocker_;
 320   }
 321
 322   // The standard task methods.
 323
 324   // Wait until the task is unblocked.
 325   Is_runnable_type
 326   is_runnable(Workqueue*)
 327   { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; }
 328
 329   // This type of task does not normally hold any locks.
 330   virtual Task_locker*
 331   locks(Workqueue*)
 332   { return NULL; }
 333
 334   // Run the action.
 335   void
 336   run(Workqueue* workqueue)
 337   { this->runner_->run(workqueue); }
 338
 339  private:
 340   Task_function(const Task_function&);
 341   Task_function& operator=(const Task_function&);
 342
 343   Task_function_runner* runner_;
 344   Task_token* blocker_;
 345 };
 346
 347 // The workqueue
 348
 349 class Workqueue_runner;
 350
 351 class Workqueue
 352 {
 353  public:
 354   Workqueue(const General_options&);
 355   ~Workqueue();
 356
 357   // Add a new task to the work queue.
 358   void
 359   queue(Task*);
 360
 361   // Add a new task to the front of the work queue.  It will be the
 362   // next task to run if it is ready.
 363   void
 364   queue_front(Task*);
 365
 366   // Process all the tasks on the work queue.
 367   void
 368   process();
 369
 370   // A complete set of blocking tasks has completed.
 371   void
 372   cleared_blocker();
 373
 374  private:
 375   // This class can not be copied.
 376   Workqueue(const Workqueue&);
 377   Workqueue& operator=(const Workqueue&);
 378
 379   typedef std::list<Task*> Task_list;
 380
 381   // Run a task.
 382   void run(Task*);
 383
 384   friend class Workqueue_runner;
 385
 386   // Find a runnable task.
 387   Task* find_runnable(Task_list&, bool*);
 388
 389   // Add a lock to the completed queue.
 390   void completed(Task*, Task_locker*);
 391
 392   // Clear the completed queue.
 393   bool clear_completed();
 394
 395   // How to run a task.  Only accessed from main thread.
 396   Workqueue_runner* runner_;
 397
 398   // Lock for access to tasks_ members.
 399   Lock tasks_lock_;
 400   // List of tasks to execute at each link level.
 401   Task_list tasks_;
 402
 403   // Lock for access to completed_ and running_ members.
 404   Lock completed_lock_;
 405   // List of Task_locker objects for main thread to free.
 406   std::list<Task_locker*> completed_;
 407   // Number of tasks currently running.
 408   int running_;
 409   // Condition variable signalled when a new entry is added to completed_.
 410   Condvar completed_condvar_;
 411
 412   // Number of blocker tokens which were fully cleared.  Only accessed
 413   // from main thread.
 414   int cleared_blockers_;
 415 };
 416
 417 } // End namespace gold.
 418
 419 #endif // !defined(GOLD_WORKQUEUE_H)