| // workqueue.cc -- the workqueue for gold |
| |
| // Copyright (C) 2006-2021 Free Software Foundation, Inc. |
| // Written by Ian Lance Taylor <iant@google.com>. |
| |
| // 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. |
| |
| #include "gold.h" |
| |
| #include "debug.h" |
| #include "options.h" |
| #include "timer.h" |
| #include "workqueue.h" |
| #include "workqueue-internal.h" |
| |
| namespace gold |
| { |
| |
| // Class Task_list. |
| |
| // Add T to the end of the list. |
| |
| inline void |
| Task_list::push_back(Task* t) |
| { |
| gold_assert(t->list_next() == NULL); |
| if (this->head_ == NULL) |
| { |
| this->head_ = t; |
| this->tail_ = t; |
| } |
| else |
| { |
| this->tail_->set_list_next(t); |
| this->tail_ = t; |
| } |
| } |
| |
| // Add T to the front of the list. |
| |
| inline void |
| Task_list::push_front(Task* t) |
| { |
| gold_assert(t->list_next() == NULL); |
| if (this->head_ == NULL) |
| { |
| this->head_ = t; |
| this->tail_ = t; |
| } |
| else |
| { |
| t->set_list_next(this->head_); |
| this->head_ = t; |
| } |
| } |
| |
| // Remove and return the first Task waiting for this lock to be |
| // released. |
| |
| inline Task* |
| Task_list::pop_front() |
| { |
| Task* ret = this->head_; |
| if (ret != NULL) |
| { |
| if (ret == this->tail_) |
| { |
| gold_assert(ret->list_next() == NULL); |
| this->head_ = NULL; |
| this->tail_ = NULL; |
| } |
| else |
| { |
| this->head_ = ret->list_next(); |
| gold_assert(this->head_ != NULL); |
| ret->clear_list_next(); |
| } |
| } |
| return ret; |
| } |
| |
| // The simple single-threaded implementation of Workqueue_threader. |
| |
| class Workqueue_threader_single : public Workqueue_threader |
| { |
| public: |
| Workqueue_threader_single(Workqueue* workqueue) |
| : Workqueue_threader(workqueue) |
| { } |
| ~Workqueue_threader_single() |
| { } |
| |
| void |
| set_thread_count(int thread_count) |
| { gold_assert(thread_count > 0); } |
| |
| bool |
| should_cancel_thread(int) |
| { return false; } |
| }; |
| |
| // Workqueue methods. |
| |
| Workqueue::Workqueue(const General_options& options) |
| : lock_(), |
| first_tasks_(), |
| tasks_(), |
| running_(0), |
| waiting_(0), |
| condvar_(this->lock_), |
| threader_(NULL) |
| { |
| bool threads = options.threads(); |
| #ifndef ENABLE_THREADS |
| threads = false; |
| #endif |
| if (!threads) |
| this->threader_ = new Workqueue_threader_single(this); |
| else |
| { |
| #ifdef ENABLE_THREADS |
| this->threader_ = new Workqueue_threader_threadpool(this); |
| #else |
| gold_unreachable(); |
| #endif |
| } |
| } |
| |
| Workqueue::~Workqueue() |
| { |
| } |
| |
| // Add a task to the end of a specific queue, or put it on the list |
| // waiting for a Token. |
| |
| void |
| Workqueue::add_to_queue(Task_list* queue, Task* t, bool front) |
| { |
| Hold_lock hl(this->lock_); |
| |
| Task_token* token = t->is_runnable(); |
| if (token != NULL) |
| { |
| if (front) |
| token->add_waiting_front(t); |
| else |
| token->add_waiting(t); |
| ++this->waiting_; |
| } |
| else |
| { |
| if (front) |
| queue->push_front(t); |
| else |
| queue->push_back(t); |
| // Tell any waiting thread that there is work to do. |
| this->condvar_.signal(); |
| } |
| } |
| |
| // Add a task to the queue. |
| |
| void |
| Workqueue::queue(Task* t) |
| { |
| this->add_to_queue(&this->tasks_, t, false); |
| } |
| |
| // Queue a task which should run soon. |
| |
| void |
| Workqueue::queue_soon(Task* t) |
| { |
| t->set_should_run_soon(); |
| this->add_to_queue(&this->first_tasks_, t, false); |
| } |
| |
| // Queue a task which should run next. |
| |
| void |
| Workqueue::queue_next(Task* t) |
| { |
| t->set_should_run_soon(); |
| this->add_to_queue(&this->first_tasks_, t, true); |
| } |
| |
| // Return whether to cancel the current thread. |
| |
| inline bool |
| Workqueue::should_cancel_thread(int thread_number) |
| { |
| return this->threader_->should_cancel_thread(thread_number); |
| } |
| |
| // Find a runnable task in TASKS. Return NULL if none could be found. |
| // If we find a Task waiting for a Token, add it to the list for that |
| // Token. The workqueue lock must be held when this is called. |
| |
| Task* |
| Workqueue::find_runnable_in_list(Task_list* tasks) |
| { |
| Task* t; |
| while ((t = tasks->pop_front()) != NULL) |
| { |
| Task_token* token = t->is_runnable(); |
| |
| if (token == NULL) |
| return t; |
| |
| token->add_waiting(t); |
| ++this->waiting_; |
| } |
| |
| // We couldn't find any runnable task. |
| return NULL; |
| } |
| |
| // Find a runnable task. Return NULL if none could be found. The |
| // workqueue lock must be held when this is called. |
| |
| Task* |
| Workqueue::find_runnable() |
| { |
| Task* t = this->find_runnable_in_list(&this->first_tasks_); |
| if (t == NULL) |
| t = this->find_runnable_in_list(&this->tasks_); |
| return t; |
| } |
| |
| // Find a runnable a task, and wait until we find one. Return NULL if |
| // we should exit. The workqueue lock must be held when this is |
| // called. |
| |
| Task* |
| Workqueue::find_runnable_or_wait(int thread_number) |
| { |
| Task* t = this->find_runnable(); |
| |
| while (t == NULL) |
| { |
| if (this->running_ == 0 |
| && this->first_tasks_.empty() |
| && this->tasks_.empty()) |
| { |
| // Kick all the threads to make them exit. |
| this->condvar_.broadcast(); |
| |
| gold_assert(this->waiting_ == 0); |
| return NULL; |
| } |
| |
| if (this->should_cancel_thread(thread_number)) |
| return NULL; |
| |
| gold_debug(DEBUG_TASK, "%3d sleeping", thread_number); |
| |
| this->condvar_.wait(); |
| |
| gold_debug(DEBUG_TASK, "%3d awake", thread_number); |
| |
| t = this->find_runnable(); |
| } |
| |
| return t; |
| } |
| |
| // Find and run tasks. If we can't find a runnable task, wait for one |
| // to become available. If we run a task, and it frees up another |
| // runnable task, then run that one too. This returns true if we |
| // should look for another task, false if we are cancelling this |
| // thread. |
| |
| bool |
| Workqueue::find_and_run_task(int thread_number) |
| { |
| Task* t; |
| Task_locker tl; |
| |
| { |
| Hold_lock hl(this->lock_); |
| |
| // Find a runnable task. |
| t = this->find_runnable_or_wait(thread_number); |
| |
| if (t == NULL) |
| return false; |
| |
| // Get the locks for the task. This must be called while we are |
| // still holding the Workqueue lock. |
| t->locks(&tl); |
| |
| ++this->running_; |
| } |
| |
| while (t != NULL) |
| { |
| gold_debug(DEBUG_TASK, "%3d running task %s", thread_number, |
| t->name().c_str()); |
| |
| Timer timer; |
| if (is_debugging_enabled(DEBUG_TASK)) |
| timer.start(); |
| |
| t->run(this); |
| |
| if (is_debugging_enabled(DEBUG_TASK)) |
| { |
| Timer::TimeStats elapsed = timer.get_elapsed_time(); |
| |
| gold_debug(DEBUG_TASK, |
| "%3d completed task %s " |
| "(user: %ld.%06ld sys: %ld.%06ld wall: %ld.%06ld)", |
| thread_number, t->name().c_str(), |
| elapsed.user / 1000, (elapsed.user % 1000) * 1000, |
| elapsed.sys / 1000, (elapsed.sys % 1000) * 1000, |
| elapsed.wall / 1000, (elapsed.wall % 1000) * 1000); |
| } |
| |
| Task* next; |
| { |
| Hold_lock hl(this->lock_); |
| |
| --this->running_; |
| |
| // Release the locks for the task. This must be done with the |
| // workqueue lock held. Get the next Task to run if any. |
| next = this->release_locks(t, &tl); |
| |
| if (next == NULL) |
| next = this->find_runnable(); |
| |
| // If we have another Task to run, get the Locks. This must |
| // be called while we are still holding the Workqueue lock. |
| if (next != NULL) |
| { |
| tl.clear(); |
| next->locks(&tl); |
| |
| ++this->running_; |
| } |
| } |
| |
| // We are done with this task. |
| delete t; |
| |
| t = next; |
| } |
| |
| return true; |
| } |
| |
| // Handle the return value of release_locks, and get tasks ready to |
| // run. |
| |
| // 1) If T is not runnable, queue it on the appropriate token. |
| |
| // 2) Otherwise, T is runnable. If *PRET is not NULL, then we have |
| // already decided which Task to run next. Add T to the list of |
| // runnable tasks, and signal another thread. |
| |
| // 3) Otherwise, *PRET is NULL. If IS_BLOCKER is false, then T was |
| // waiting on a write lock. We can grab that lock now, so we run T |
| // now. |
| |
| // 4) Otherwise, IS_BLOCKER is true. If we should run T soon, then |
| // run it now. |
| |
| // 5) Otherwise, check whether there are other tasks to run. If there |
| // are, then we generally get a better ordering if we run those tasks |
| // now, before T. A typical example is tasks waiting on the Dirsearch |
| // blocker. We don't want to run those tasks right away just because |
| // the Dirsearch was unblocked. |
| |
| // 6) Otherwise, there are no other tasks to run, so we might as well |
| // run this one now. |
| |
| // This function must be called with the Workqueue lock held. |
| |
| // Return true if we set *PRET to T, false otherwise. |
| |
| bool |
| Workqueue::return_or_queue(Task* t, bool is_blocker, Task** pret) |
| { |
| Task_token* token = t->is_runnable(); |
| |
| if (token != NULL) |
| { |
| token->add_waiting(t); |
| ++this->waiting_; |
| return false; |
| } |
| |
| bool should_queue = false; |
| bool should_return = false; |
| |
| if (*pret != NULL) |
| should_queue = true; |
| else if (!is_blocker) |
| should_return = true; |
| else if (t->should_run_soon()) |
| should_return = true; |
| else if (!this->first_tasks_.empty() || !this->tasks_.empty()) |
| should_queue = true; |
| else |
| should_return = true; |
| |
| if (should_return) |
| { |
| gold_assert(*pret == NULL); |
| *pret = t; |
| return true; |
| } |
| else if (should_queue) |
| { |
| if (t->should_run_soon()) |
| this->first_tasks_.push_back(t); |
| else |
| this->tasks_.push_back(t); |
| this->condvar_.signal(); |
| return false; |
| } |
| |
| gold_unreachable(); |
| } |
| |
| // Release the locks associated with a Task. Return the first |
| // runnable Task that we find. If we find more runnable tasks, add |
| // them to the run queue and signal any other threads. This must be |
| // called with the Workqueue lock held. |
| |
| Task* |
| Workqueue::release_locks(Task* t, Task_locker* tl) |
| { |
| Task* ret = NULL; |
| for (Task_locker::iterator p = tl->begin(); p != tl->end(); ++p) |
| { |
| Task_token* token = *p; |
| if (token->is_blocker()) |
| { |
| if (token->remove_blocker()) |
| { |
| // The token has been unblocked. Every waiting Task may |
| // now be runnable. |
| Task* t; |
| while ((t = token->remove_first_waiting()) != NULL) |
| { |
| --this->waiting_; |
| this->return_or_queue(t, true, &ret); |
| } |
| } |
| } |
| else |
| { |
| token->remove_writer(t); |
| |
| // One more waiting Task may now be runnable. If we are |
| // going to run it next, we can stop. Otherwise we need to |
| // move all the Tasks to the runnable queue, to avoid a |
| // potential deadlock if the locking status changes before |
| // we run the next thread. |
| Task* t; |
| while ((t = token->remove_first_waiting()) != NULL) |
| { |
| --this->waiting_; |
| if (this->return_or_queue(t, false, &ret)) |
| break; |
| } |
| } |
| } |
| return ret; |
| } |
| |
| // Process all the tasks on the workqueue. Keep going until the |
| // workqueue is empty, or until we have been told to exit. This |
| // function is called by all threads. |
| |
| void |
| Workqueue::process(int thread_number) |
| { |
| while (this->find_and_run_task(thread_number)) |
| ; |
| } |
| |
| // Set the number of threads to use for the workqueue, if we are using |
| // threads. |
| |
| void |
| Workqueue::set_thread_count(int threads) |
| { |
| Hold_lock hl(this->lock_); |
| |
| this->threader_->set_thread_count(threads); |
| // Wake up all the threads, since something has changed. |
| this->condvar_.broadcast(); |
| } |
| |
| // Add a new blocker to an existing Task_token. |
| |
| void |
| Workqueue::add_blocker(Task_token* token) |
| { |
| Hold_lock hl(this->lock_); |
| token->add_blocker(); |
| } |
| |
| } // End namespace gold. |