// workqueue.cc -- the workqueue for gold // Copyright (C) 2006-2022 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.