X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=gold%2Fworkqueue.h;h=2047620d4b8e37d621d0de127f9a42ae8fb2b7e3;hb=f65fe5704af56aca58fd5547d0841a9512e540af;hp=5949cf5f4396d9502337192e8f9d36bd684b1cb1;hpb=bae7f79e03d6405f5ceec0e3e24671e6b30f29ed;p=deliverable%2Fbinutils-gdb.git diff --git a/gold/workqueue.h b/gold/workqueue.h index 5949cf5f43..2047620d4b 100644 --- a/gold/workqueue.h +++ b/gold/workqueue.h @@ -1,274 +1,199 @@ // workqueue.h -- the work queue for gold -*- C++ -*- +// Copyright (C) 2006-2019 Free Software Foundation, Inc. +// Written by Ian Lance Taylor . + +// This file is part of gold. + +// This program is free software; you can redistribute it and/or modify +// it under the terms of the GNU General Public License as published by +// the Free Software Foundation; either version 3 of the License, or +// (at your option) any later version. + +// This program is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License +// along with this program; if not, write to the Free Software +// Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, +// MA 02110-1301, USA. + // After processing the command line, everything the linker does is // driven from a work queue. This permits us to parallelize the // linker where possible. -// Task_token -// A simple locking implementation to ensure proper task ordering. -// Task_read_token, Task_write_token -// Lock a Task_token for read or write. -// Task_locker -// Task locking using RAII. -// Task -// An abstract class for jobs to run. - #ifndef GOLD_WORKQUEUE_H #define GOLD_WORKQUEUE_H +#include + #include "gold-threads.h" -#include "options.h" -#include "fileread.h" +#include "token.h" namespace gold { -class Task; +class General_options; class Workqueue; -// Some tasks require access to shared data structures, such as the -// symbol table. Some tasks must be executed in a particular error, -// such as reading input file symbol tables--if we see foo.o -llib, we -// have to read the symbols for foo.o before we read the ones for -// -llib. To implement this safely and efficiently, we use tokens. -// Task_tokens support shared read/exclusive write access to some -// resource. Alternatively, they support blockers: blockers implement -// the requirement that some set of tasks must complete before another -// set of tasks can start. In such a case we increment the block -// count when we create the task, and decrement it when the task -// completes. Task_tokens are only manipulated by the main thread, so -// they do not themselves require any locking. - -class Task_token +// The superclass for tasks to be placed on the workqueue. Each +// specific task class will inherit from this one. + +class Task { public: - Task_token(); + Task() + : list_next_(NULL), name_(), should_run_soon_(false) + { } + virtual ~Task() + { } - ~Task_token(); + // Check whether the Task can be run now. This method is only + // called with the workqueue lock held. If the Task can run, this + // returns NULL. Otherwise it returns a pointer to a token which + // must be released before the Task can run. + virtual Task_token* + is_runnable() = 0; + + // Lock all the resources required by the Task, and store the locks + // in a Task_locker. This method does not need to do anything if no + // locks are required. This method is only called with the + // workqueue lock held. + virtual void + locks(Task_locker*) = 0; - // A read/write token uses these methods. + // Run the task. + virtual void + run(Workqueue*) = 0; + // Return whether this task should run soon. bool - is_readable() const; + should_run_soon() const + { return this->should_run_soon_; } + // Note that this task should run soon. void - add_reader(); - - void - remove_reader(); - - bool - is_writable() const; + set_should_run_soon() + { this->should_run_soon_ = true; } - void - add_writer(const Task*); + // Get the next Task on the list of Tasks. Called by Task_list. + Task* + list_next() const + { return this->list_next_; } + // Set the next Task on the list of Tasks. Called by Task_list. void - remove_writer(const Task*); - - bool - has_write_lock(const Task*); - - // A blocker token uses these methods. + set_list_next(Task* t) + { + gold_assert(this->list_next_ == NULL); + this->list_next_ = t; + } + // Clear the next Task on the list of Tasks. Called by Task_list. void - add_blocker(); - - // Returns true if block count drops to zero. - bool - remove_blocker(); - - bool - is_blocked() const; - - private: - // It makes no sense to copy these. - Task_token(const Task_token&); - Task_token& operator=(const Task_token&); - - bool is_blocker_; - int readers_; - const Task* writer_; -}; - -// In order to support tokens more reliably, we provide objects which -// handle them using RAII. + clear_list_next() + { this->list_next_ = NULL; } -class Task_read_token -{ - public: - Task_read_token(Task_token& token) - : token_(token) - { this->token_.add_reader(); } - - ~Task_read_token() - { this->token_.remove_reader(); } - - private: - Task_read_token(const Task_read_token&); - Task_read_token& operator=(const Task_read_token&); - - Task_token& token_; -}; - -class Task_write_token -{ - public: - Task_write_token(Task_token& token, const Task* task) - : token_(token), task_(task) - { this->token_.add_writer(this->task_); } - - ~Task_write_token() - { this->token_.remove_writer(this->task_); } - - private: - Task_write_token(const Task_write_token&); - Task_write_token& operator=(const Task_write_token&); - - Task_token& token_; - const Task* task_; -}; + // Return the name of the Task. This is only used for debugging + // purposes. + const std::string& + name() + { + if (this->name_.empty()) + this->name_ = this->get_name(); + return this->name_; + } -class Task_block_token -{ - public: - // The blocker count must be incremented when the task is created. - // This object is created when the task is run. When we unblock the - // last task, we notify the workqueue. - Task_block_token(Task_token& token, Workqueue* workqueue); - ~Task_block_token(); + protected: + // Get the name of the task. This must be implemented by the child + // class. + virtual std::string + get_name() const = 0; private: - Task_block_token(const Task_block_token&); - Task_block_token& operator=(const Task_block_token&); - - Task_token& token_; - Workqueue* workqueue_; + // Tasks may not be copied. + Task(const Task&); + Task& operator=(const Task&); + + // If this Task is on a list, this is a pointer to the next Task on + // the list. We use this simple list structure rather than building + // a container, in order to avoid memory allocation while holding + // the Workqueue lock. + Task* list_next_; + // Task name, for debugging purposes. + std::string name_; + // Whether this Task should be executed soon. This is used for + // Tasks which can be run after some data is read. + bool should_run_soon_; }; -// An abstract class used to lock Task_tokens using RAII. A typical -// implementation would simply have a set of members of type -// Task_read_token, Task_write_token, and Task_block_token. +// An interface for Task_function. This is a convenience class to run +// a single function. -class Task_locker +class Task_function_runner { public: - Task_locker() + virtual ~Task_function_runner() { } - virtual ~Task_locker() - { } -}; - -// A version of Task_locker which may be used for a single read lock. - -class Task_locker_read : public Task_locker -{ - public: - Task_locker_read(Task_token& token) - : read_token_(token) - { } - - private: - Task_locker_read(const Task_locker_read&); - Task_locker_read& operator=(const Task_locker_read&); - - Task_read_token read_token_; + virtual void + run(Workqueue*, const Task*) = 0; }; -// A version of Task_locker which may be used for a single write lock. +// A simple task which waits for a blocker and then runs a function. -class Task_locker_write : public Task_locker +class Task_function : public Task { public: - Task_locker_write(Task_token& token, const Task* task) - : write_token_(token, task) - { } - - private: - Task_locker_write(const Task_locker_write&); - Task_locker_write& operator=(const Task_locker_write&); + // RUNNER and BLOCKER should be allocated using new, and will be + // deleted after the task runs. + Task_function(Task_function_runner* runner, Task_token* blocker, + const char* name) + : runner_(runner), blocker_(blocker), name_(name) + { gold_assert(blocker != NULL); } + + ~Task_function() + { + delete this->runner_; + delete this->blocker_; + } - Task_write_token write_token_; -}; + // The standard task methods. -// A version of Task_locker which may be used for a single blocker -// lock. + // Wait until the task is unblocked. + Task_token* + is_runnable() + { return this->blocker_->is_blocked() ? this->blocker_ : NULL; } -class Task_locker_block : public Task_locker -{ - public: - Task_locker_block(Task_token& token, Workqueue* workqueue) - : block_token_(token, workqueue) + // This type of task does not normally hold any locks. + virtual void + locks(Task_locker*) { } - private: - Task_locker_block(const Task_locker_block&); - Task_locker_block& operator=(const Task_locker_block&); - - Task_block_token block_token_; -}; - -// A version of Task_locker which may be used to hold a lock on a -// File_read. + // Run the action. + void + run(Workqueue* workqueue) + { this->runner_->run(workqueue, this); } -class Task_locker_file : public Task_locker -{ - public: - Task_locker_file(File_read& file) - : file_lock_(file) - { } + // The debugging name. + std::string + get_name() const + { return this->name_; } private: - Task_locker_file(const Task_locker_file&); - Task_locker_file& operator=(const Task_locker_file&); + Task_function(const Task_function&); + Task_function& operator=(const Task_function&); - File_read_lock file_lock_; + Task_function_runner* runner_; + Task_token* blocker_; + const char* name_; }; -// The superclass for tasks to be placed on the workqueue. Each -// specific task class will inherit from this one. +// The workqueue itself. -class Task -{ - public: - Task() - { } - virtual ~Task() - { } - - // Type returned by Is_runnable. - enum Is_runnable_type - { - // Task is runnable. - IS_RUNNABLE, - // Task is waiting for a block to clear. - IS_BLOCKED, - // Task is not waiting for a block, but is not runnable--i.e., is - // waiting for a lock. - IS_LOCKED - }; - - // Return whether the task can be run now. This method is only - // called from the main thread. - virtual Is_runnable_type - is_runnable(Workqueue*) = 0; - - // Return a pointer to a Task_locker which locks all the resources - // required by the task. We delete the pointer when the task is - // complete. This method can return NULL if no locks are required. - // This method is only called from the main thread. - virtual Task_locker* - locks(Workqueue*) = 0; - - // Run the task. - virtual void - run(Workqueue*) = 0; -}; - -// The workqueue - -class Workqueue_runner; +class Workqueue_threader; class Workqueue { @@ -280,55 +205,89 @@ class Workqueue void queue(Task*); - // Process all the tasks on the work queue. + // Add a new task to the work queue which should run soon. If the + // task is ready, it will be run before any tasks added using + // queue(). void - process(); + queue_soon(Task*); - // A complete set of blocking tasks has completed. + // Add a new task to the work queue which should run next if it is + // ready. void - cleared_blocker(); + queue_next(Task*); + + // Process all the tasks on the work queue. This function runs + // until all tasks have completed. The argument is the thread + // number, used only for debugging. + void + process(int); + + // Set the desired thread count--the number of threads we want to + // have running. + void + set_thread_count(int); + + // Add a new blocker to an existing Task_token. This must be done + // with the workqueue lock held. This should not be done routinely, + // only in special circumstances. + void + add_blocker(Task_token*); private: // This class can not be copied. Workqueue(const Workqueue&); Workqueue& operator=(const Workqueue&); - typedef std::list Task_list; - - // Run a task. - void run(Task*); + // Add a task to a queue. + void + add_to_queue(Task_list* queue, Task* t, bool front); - friend class Workqueue_runner; + // Find a runnable task, or wait for one. + Task* + find_runnable_or_wait(int thread_number); // Find a runnable task. - Task* find_runnable(Task_list&, bool*); + Task* + find_runnable(); - // Add a lock to the completed queue. - void completed(Task*, Task_locker*); + // Find a runnable task in a list. + Task* + find_runnable_in_list(Task_list*); - // Clear the completed queue. - bool clear_completed(); + // Find an run a task. + bool + find_and_run_task(int); - // How to run a task. Only accessed from main thread. - Workqueue_runner* runner_; + // Release the locks for a Task. Return the next Task to run. + Task* + release_locks(Task*, Task_locker*); - // Lock for access to tasks_ members. - Lock tasks_lock_; - // List of tasks to execute at each link level. - Task_list tasks_; + // Store T into *PRET, or queue it as appropriate. + bool + return_or_queue(Task* t, bool is_blocker, Task** pret); - // Lock for access to completed_ and running_ members. - Lock completed_lock_; - // List of Task_locker objects for main thread to free. - std::list completed_; + // Return whether to cancel this thread. + bool + should_cancel_thread(int thread_number); + + // Master Workqueue lock. This controls access to the following + // member variables. + Lock lock_; + // List of tasks to execute soon. + Task_list first_tasks_; + // List of tasks to execute after the ones in first_tasks_. + Task_list tasks_; // Number of tasks currently running. int running_; - // Condition variable signalled when a new entry is added to completed_. - Condvar completed_condvar_; - - // Number of blocker tokens which were fully cleared. Only accessed - // from main thread. - int cleared_blockers_; + // Number of tasks waiting for a lock to release. + int waiting_; + // Condition variable associated with lock_. This is signalled when + // there may be a new Task to execute. + Condvar condvar_; + + // The threading implementation. This is set at construction time + // and not changed thereafter. + Workqueue_threader* threader_; }; } // End namespace gold.