gold/workqueue.h

   1 // workqueue.h -- the work queue for gold   -*- C++ -*-
   2
   3 // Copyright 2006, 2007 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 // Task_token
  28 //   A simple locking implementation to ensure proper task ordering.
  29 // Task_read_token, Task_write_token
  30 //   Lock a Task_token for read or write.
  31 // Task_locker
  32 //   Task locking using RAII.
  33 // Task
  34 //   An abstract class for jobs to run.
  35
  36 #ifndef GOLD_WORKQUEUE_H
  37 #define GOLD_WORKQUEUE_H
  38
  39 #include "gold-threads.h"
  40 #include "fileread.h"
  41
  42 namespace gold
  43 {
  44
  45 class General_options;
  46 class Task;
  47 class Workqueue;
  48
  49 // Some tasks require access to shared data structures, such as the
  50 // symbol table.  Some tasks must be executed in a particular error,
  51 // such as reading input file symbol tables--if we see foo.o -llib, we
  52 // have to read the symbols for foo.o before we read the ones for
  53 // -llib.  To implement this safely and efficiently, we use tokens.
  54 // Task_tokens support shared read/exclusive write access to some
  55 // resource.  Alternatively, they support blockers: blockers implement
  56 // the requirement that some set of tasks must complete before another
  57 // set of tasks can start.  In such a case we increment the block
  58 // count when we create the task, and decrement it when the task
  59 // completes.  Task_tokens are only manipulated by the main thread, so
  60 // they do not themselves require any locking.
  61
  62 class Task_token
  63 {
  64  public:
  65   Task_token();
  66
  67   ~Task_token();
  68
  69   // A read/write token uses these methods.
  70
  71   bool
  72   is_readable() const;
  73
  74   void
  75   add_reader();
  76
  77   void
  78   remove_reader();
  79
  80   bool
  81   is_writable() const;
  82
  83   void
  84   add_writer(const Task*);
  85
  86   void
  87   remove_writer(const Task*);
  88
  89   bool
  90   has_write_lock(const Task*);
  91
  92   // A blocker token uses these methods.
  93
  94   void
  95   add_blocker();
  96
  97   // Returns true if block count drops to zero.
  98   bool
  99   remove_blocker();
 100
 101   bool
 102   is_blocked() const;
 103
 104  private:
 105   // It makes no sense to copy these.
 106   Task_token(const Task_token&);
 107   Task_token& operator=(const Task_token&);
 108
 109   bool is_blocker_;
 110   int readers_;
 111   const Task* writer_;
 112 };
 113
 114 // In order to support tokens more reliably, we provide objects which
 115 // handle them using RAII.
 116
 117 class Task_read_token
 118 {
 119  public:
 120   Task_read_token(Task_token& token)
 121     : token_(token)
 122   { this->token_.add_reader(); }
 123
 124   ~Task_read_token()
 125   { this->token_.remove_reader(); }
 126
 127  private:
 128   Task_read_token(const Task_read_token&);
 129   Task_read_token& operator=(const Task_read_token&);
 130
 131   Task_token& token_;
 132 };
 133
 134 class Task_write_token
 135 {
 136  public:
 137   Task_write_token(Task_token& token, const Task* task)
 138     : token_(token), task_(task)
 139   { this->token_.add_writer(this->task_); }
 140
 141   ~Task_write_token()
 142   { this->token_.remove_writer(this->task_); }
 143
 144  private:
 145   Task_write_token(const Task_write_token&);
 146   Task_write_token& operator=(const Task_write_token&);
 147
 148   Task_token& token_;
 149   const Task* task_;
 150 };
 151
 152 class Task_block_token
 153 {
 154  public:
 155   // The blocker count must be incremented when the task is created.
 156   // This object is created when the task is run.  When we unblock the
 157   // last task, we notify the workqueue.
 158   Task_block_token(Task_token& token, Workqueue* workqueue);
 159   ~Task_block_token();
 160
 161  private:
 162   Task_block_token(const Task_block_token&);
 163   Task_block_token& operator=(const Task_block_token&);
 164
 165   Task_token& token_;
 166   Workqueue* workqueue_;
 167 };
 168
 169 // An object which implements an RAII lock for any object which
 170 // supports lock and unlock methods.
 171
 172 template<typename Obj>
 173 class Task_lock_obj
 174 {
 175  public:
 176   Task_lock_obj(Obj& obj)
 177     : obj_(obj)
 178   { this->obj_.lock(); }
 179
 180   ~Task_lock_obj()
 181   { this->obj_.unlock(); }
 182
 183  private:
 184   Task_lock_obj(const Task_lock_obj&);
 185   Task_lock_obj& operator=(const Task_lock_obj&);
 186
 187   Obj& obj_;
 188 };
 189
 190 // An abstract class used to lock Task_tokens using RAII.  A typical
 191 // implementation would simply have a set of members of type
 192 // Task_read_token, Task_write_token, and Task_block_token.
 193
 194 class Task_locker
 195 {
 196  public:
 197   Task_locker()
 198   { }
 199
 200   virtual ~Task_locker()
 201   { }
 202 };
 203
 204 // A version of Task_locker which may be used for a single read lock.
 205
 206 class Task_locker_read : public Task_locker
 207 {
 208  public:
 209   Task_locker_read(Task_token& token)
 210     : read_token_(token)
 211   { }
 212
 213  private:
 214   Task_locker_read(const Task_locker_read&);
 215   Task_locker_read& operator=(const Task_locker_read&);
 216
 217   Task_read_token read_token_;
 218 };
 219
 220 // A version of Task_locker which may be used for a single write lock.
 221
 222 class Task_locker_write : public Task_locker
 223 {
 224  public:
 225   Task_locker_write(Task_token& token, const Task* task)
 226     : write_token_(token, task)
 227   { }
 228
 229  private:
 230   Task_locker_write(const Task_locker_write&);
 231   Task_locker_write& operator=(const Task_locker_write&);
 232
 233   Task_write_token write_token_;
 234 };
 235
 236 // A version of Task_locker which may be used for a single blocker
 237 // lock.
 238
 239 class Task_locker_block : public Task_locker
 240 {
 241  public:
 242   Task_locker_block(Task_token& token, Workqueue* workqueue)
 243     : block_token_(token, workqueue)
 244   { }
 245
 246  private:
 247   Task_locker_block(const Task_locker_block&);
 248   Task_locker_block& operator=(const Task_locker_block&);
 249
 250   Task_block_token block_token_;
 251 };
 252
 253 // A version of Task_locker which may be used to hold a lock on any
 254 // object which supports lock() and unlock() methods.
 255
 256 template<typename Obj>
 257 class Task_locker_obj : public Task_locker
 258 {
 259  public:
 260   Task_locker_obj(Obj& obj)
 261     : obj_lock_(obj)
 262   { }
 263
 264  private:
 265   Task_locker_obj(const Task_locker_obj&);
 266   Task_locker_obj& operator=(const Task_locker_obj&);
 267
 268   Task_lock_obj<Obj> obj_lock_;
 269 };
 270
 271 // The superclass for tasks to be placed on the workqueue.  Each
 272 // specific task class will inherit from this one.
 273
 274 class Task
 275 {
 276  public:
 277   Task()
 278   { }
 279   virtual ~Task()
 280   { }
 281
 282   // Type returned by Is_runnable.
 283   enum Is_runnable_type
 284   {
 285     // Task is runnable.
 286     IS_RUNNABLE,
 287     // Task is waiting for a block to clear.
 288     IS_BLOCKED,
 289     // Task is not waiting for a block, but is not runnable--i.e., is
 290     // waiting for a lock.
 291     IS_LOCKED
 292   };
 293
 294   // Return whether the task can be run now.  This method is only
 295   // called from the main thread.
 296   virtual Is_runnable_type
 297   is_runnable(Workqueue*) = 0;
 298
 299   // Return a pointer to a Task_locker which locks all the resources
 300   // required by the task.  We delete the pointer when the task is
 301   // complete.  This method can return NULL if no locks are required.
 302   // This method is only called from the main thread.
 303   virtual Task_locker*
 304   locks(Workqueue*) = 0;
 305
 306   // Run the task.
 307   virtual void
 308   run(Workqueue*) = 0;
 309
 310  private:
 311   Task(const Task&);
 312   Task& operator=(const Task&);
 313 };
 314
 315 // A simple task which waits for a blocker and then runs a function.
 316
 317 class Task_function_runner
 318 {
 319  public:
 320   virtual ~Task_function_runner()
 321   { }
 322
 323   virtual void
 324   run(Workqueue*) = 0;
 325 };
 326
 327 class Task_function : public Task
 328 {
 329  public:
 330   // Both points should be allocated using new, and will be deleted
 331   // after the task runs.
 332   Task_function(Task_function_runner* runner, Task_token* blocker)
 333     : runner_(runner), blocker_(blocker)
 334   { }
 335
 336   ~Task_function()
 337   {
 338     delete this->runner_;
 339     delete this->blocker_;
 340   }
 341
 342   // The standard task methods.
 343
 344   // Wait until the task is unblocked.
 345   Is_runnable_type
 346   is_runnable(Workqueue*)
 347   { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; }
 348
 349   // This type of task does not normally hold any locks.
 350   virtual Task_locker*
 351   locks(Workqueue*)
 352   { return NULL; }
 353
 354   // Run the action.
 355   void
 356   run(Workqueue* workqueue)
 357   { this->runner_->run(workqueue); }
 358
 359  private:
 360   Task_function(const Task_function&);
 361   Task_function& operator=(const Task_function&);
 362
 363   Task_function_runner* runner_;
 364   Task_token* blocker_;
 365 };
 366
 367 // The workqueue
 368
 369 class Workqueue_runner;
 370
 371 class Workqueue
 372 {
 373  public:
 374   Workqueue(const General_options&);
 375   ~Workqueue();
 376
 377   // Add a new task to the work queue.
 378   void
 379   queue(Task*);
 380
 381   // Add a new task to the front of the work queue.  It will be the
 382   // next task to run if it is ready.
 383   void
 384   queue_front(Task*);
 385
 386   // Process all the tasks on the work queue.
 387   void
 388   process();
 389
 390   // A complete set of blocking tasks has completed.
 391   void
 392   cleared_blocker();
 393
 394  private:
 395   // This class can not be copied.
 396   Workqueue(const Workqueue&);
 397   Workqueue& operator=(const Workqueue&);
 398
 399   typedef std::list<Task*> Task_list;
 400
 401   // Run a task.
 402   void run(Task*);
 403
 404   friend class Workqueue_runner;
 405
 406   // Find a runnable task.
 407   Task* find_runnable(Task_list&, bool*);
 408
 409   // Add a lock to the completed queue.
 410   void completed(Task*, Task_locker*);
 411
 412   // Clear the completed queue.
 413   bool clear_completed();
 414
 415   // How to run a task.  Only accessed from main thread.
 416   Workqueue_runner* runner_;
 417
 418   // Lock for access to tasks_ members.
 419   Lock tasks_lock_;
 420   // List of tasks to execute at each link level.
 421   Task_list tasks_;
 422
 423   // Lock for access to completed_ and running_ members.
 424   Lock completed_lock_;
 425   // List of Task_locker objects for main thread to free.
 426   std::list<Task_locker*> completed_;
 427   // Number of tasks currently running.
 428   int running_;
 429   // Condition variable signalled when a new entry is added to completed_.
 430   Condvar completed_condvar_;
 431
 432   // Number of blocker tokens which were fully cleared.  Only accessed
 433   // from main thread.
 434   int cleared_blockers_;
 435 };
 436
 437 } // End namespace gold.
 438
 439 #endif // !defined(GOLD_WORKQUEUE_H)