// workqueue.h -- the work queue for gold -*- C++ -*-
-// Copyright 2006, 2007 Free Software Foundation, Inc.
+// Copyright (C) 2006-2020 Free Software Foundation, Inc.
// Written by Ian Lance Taylor <iant@google.com>.
// This file is part of gold.
// 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 <string>
+
#include "gold-threads.h"
-#include "fileread.h"
+#include "token.h"
namespace gold
{
class General_options;
-class Task;
class Workqueue;
-// Some tasks require access to shared data structures, such as the
-// symbol table. Some tasks must be executed in a particular order,
-// 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.
-
-class Task_read_token
-{
- public:
- Task_read_token(Task_token& token)
- : token_(token)
- { this->token_.add_reader(); }
+ clear_list_next()
+ { this->list_next_ = NULL; }
- ~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_;
-};
-
-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();
-
- private:
- Task_block_token(const Task_block_token&);
- Task_block_token& operator=(const Task_block_token&);
-
- Task_token& token_;
- Workqueue* workqueue_;
-};
-
-// An object which implements an RAII lock for any object which
-// supports lock and unlock methods.
-
-template<typename Obj>
-class Task_lock_obj
-{
- public:
- Task_lock_obj(Obj& obj)
- : obj_(obj)
- { this->obj_.lock(); }
-
- ~Task_lock_obj()
- { this->obj_.unlock(); }
-
- private:
- Task_lock_obj(const Task_lock_obj&);
- Task_lock_obj& operator=(const Task_lock_obj&);
-
- Obj& obj_;
-};
-
-// 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.
-
-class Task_locker
-{
- public:
- Task_locker()
- { }
-
- 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_;
-};
-
-// A version of Task_locker which may be used for a single write lock.
-
-class Task_locker_write : public Task_locker
-{
- 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&);
-
- Task_write_token write_token_;
-};
-
-// A version of Task_locker which may be used for a single blocker
-// lock.
-
-class Task_locker_block : public Task_locker
-{
- public:
- Task_locker_block(Task_token& token, Workqueue* workqueue)
- : block_token_(token, workqueue)
- { }
-
- 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 any
-// object which supports lock() and unlock() methods.
-
-template<typename Obj>
-class Task_locker_obj : public Task_locker
-{
- public:
- Task_locker_obj(Obj& obj)
- : obj_lock_(obj)
- { }
-
- private:
- Task_locker_obj(const Task_locker_obj&);
- Task_locker_obj& operator=(const Task_locker_obj&);
-
- Task_lock_obj<Obj> obj_lock_;
-};
-
-// The superclass for tasks to be placed on the workqueue. Each
-// specific task class will inherit from this one.
-
-class Task
-{
- public:
- Task()
- { }
- virtual ~Task()
- { }
-
- // Type returned by Is_runnable.
- enum Is_runnable_type
+ // Return the name of the Task. This is only used for debugging
+ // purposes.
+ const std::string&
+ name()
{
- // 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;
+ if (this->name_.empty())
+ this->name_ = this->get_name();
+ return this->name_;
+ }
- // Run the task.
- virtual void
- run(Workqueue*) = 0;
+ protected:
+ // Get the name of the task. This must be implemented by the child
+ // class.
+ virtual std::string
+ get_name() const = 0;
private:
+ // 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_;
};
-// A simple task which waits for a blocker and then runs a function.
+// An interface for Task_function. This is a convenience class to run
+// a single function.
class Task_function_runner
{
{ }
virtual void
- run(Workqueue*) = 0;
+ run(Workqueue*, const Task*) = 0;
};
+// A simple task which waits for a blocker and then runs a function.
+
class Task_function : public Task
{
public:
- // Both points should be allocated using new, and will be deleted
- // after the task runs.
- Task_function(Task_function_runner* runner, Task_token* blocker)
- : runner_(runner), blocker_(blocker)
- { }
+ // 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()
{
// The standard task methods.
// Wait until the task is unblocked.
- Is_runnable_type
- is_runnable(Workqueue*)
- { return this->blocker_->is_blocked() ? IS_BLOCKED : IS_RUNNABLE; }
+ Task_token*
+ is_runnable()
+ { return this->blocker_->is_blocked() ? this->blocker_ : NULL; }
// This type of task does not normally hold any locks.
- virtual Task_locker*
- locks(Workqueue*)
- { return NULL; }
+ virtual void
+ locks(Task_locker*)
+ { }
// Run the action.
void
run(Workqueue* workqueue)
- { this->runner_->run(workqueue); }
+ { this->runner_->run(workqueue, this); }
+
+ // The debugging name.
+ std::string
+ get_name() const
+ { return this->name_; }
private:
Task_function(const Task_function&);
Task_function_runner* runner_;
Task_token* blocker_;
+ const char* name_;
};
-// The workqueue
+// The workqueue itself.
-class Workqueue_runner;
+class Workqueue_threader;
class Workqueue
{
void
queue(Task*);
- // Add a new task to the front of the work queue. It will be the
- // next task to run if it is ready.
+ // 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
- queue_front(Task*);
+ queue_soon(Task*);
- // Process all the tasks on the work queue.
+ // Add a new task to the work queue which should run next if it is
+ // ready.
void
- process();
+ queue_next(Task*);
- // A complete set of blocking tasks has completed.
+ // 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
- cleared_blocker();
+ process(int);
- // Set the thread count.
+ // 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*> 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<Task_locker*> 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.
projects / deliverable / binutils-gdb.git / blobdiff