Home | History | Annotate | Download | only in gold
      1 // workqueue.h -- the work queue for gold   -*- C++ -*-
      2 
      3 // Copyright (C) 2006-2014 Free Software Foundation, Inc.
      4 // Written by Ian Lance Taylor <iant (at) 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(int thread_number);
    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)
    296