| // Copyright 2016 The Chromium Authors | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #ifndef BASE_TASK_THREAD_POOL_SEQUENCE_H_ | |
| #define BASE_TASK_THREAD_POOL_SEQUENCE_H_ | |
| #include <stddef.h> | |
| #include "base/base_export.h" | |
| #include "base/containers/intrusive_heap.h" | |
| #include "base/containers/queue.h" | |
| #include "base/sequence_token.h" | |
| #include "base/task/task_traits.h" | |
| #include "base/task/thread_pool/pooled_parallel_task_runner.h" | |
| #include "base/task/thread_pool/task.h" | |
| #include "base/task/thread_pool/task_source.h" | |
| #include "base/task/thread_pool/task_source_sort_key.h" | |
| #include "base/threading/sequence_local_storage_map.h" | |
| namespace base { | |
| namespace internal { | |
| // A Sequence is intended to hold delayed tasks and immediate tasks. | |
| // Delayed tasks are held in a prority_queue until they are ripe and | |
| // immediate tasks in a simple fifo queue. | |
| // Sequence::PushTask is responsible for putting a task into the right | |
| // queue depending on its nature. | |
| // When Sequence::TakeTask is called, we select the next appropriate task | |
| // from both queues and return it. | |
| // Each queue holds slots each containing up to a single Task that must be | |
| // executed in posting/runtime order. | |
| // | |
| // In comments below, an "empty Sequence" is a Sequence with no slot. | |
| // | |
| // Note: there is a known refcounted-ownership cycle in the Scheduler | |
| // architecture: Sequence -> Task -> TaskRunner -> Sequence -> ... | |
| // This is okay so long as the other owners of Sequence (PriorityQueue and | |
| // WorkerThread in alternation and | |
| // ThreadGroupImpl::WorkerThreadDelegateImpl::GetWork() | |
| // temporarily) keep running it (and taking Tasks from it as a result). A | |
| // dangling reference cycle would only occur should they release their reference | |
| // to it while it's not empty. In other words, it is only correct for them to | |
| // release it after PopTask() returns false to indicate it was made empty by | |
| // that call (in which case the next PushImmediateTask() will return true to | |
| // indicate to the caller that the Sequence should be re-enqueued for | |
| // execution). This class is thread-safe. | |
| class BASE_EXPORT Sequence : public TaskSource { | |
| public: | |
| // A Transaction can perform multiple operations atomically on a | |
| // Sequence. While a Transaction is alive, it is guaranteed that nothing | |
| // else will access the Sequence; the Sequence's lock is held for the | |
| // lifetime of the Transaction. | |
| class BASE_EXPORT Transaction : public TaskSource::Transaction { | |
| public: | |
| Transaction(Transaction&& other); | |
| Transaction(const Transaction&) = delete; | |
| Transaction& operator=(const Transaction&) = delete; | |
| ~Transaction(); | |
| // Returns true if the sequence would need to be queued in the | |
| // immediate/delayed queue after receiving a new immediate/delayed Task. | |
| // Thread-safe but the returned value may immediately be obsolete when | |
| // pushing a delayed task since a sequence can become ready at any time; | |
| // therefore it must be externally synchronized to prevent races against | |
| // OnBecomeReady(). | |
| [[nodiscard]] bool ShouldBeQueued() const; | |
| // Returns true if the task to be posted will change the sequence | |
| // delayed_queue top. | |
| bool TopDelayedTaskWillChange(Task& delayed_task) const; | |
| // Adds immediate |task| to the end of this sequence. This must only | |
| // be called after invoking ShouldBeQueued(). | |
| void PushImmediateTask(Task task); | |
| // Adds a delayed |task| in this sequence to be prioritized based on it's | |
| // delayed run time. This must only be called after invoking | |
| // TopDelayedTaskWillChange()/ShouldBeQueued(). | |
| void PushDelayedTask(Task task); | |
| Sequence* sequence() const { return static_cast<Sequence*>(task_source()); } | |
| private: | |
| friend class Sequence; | |
| explicit Transaction(Sequence* sequence); | |
| }; | |
| // This indicates where a sequence is stored, used by Sequence to keep track | |
| // of its status. | |
| enum class SequenceLocation { | |
| // Sequence is not present in any queue. | |
| kNone, | |
| // Sequence is present in queue of immediate sequences. | |
| kImmediateQueue, | |
| // Sequence is present in queue of delayed sequences. | |
| kDelayedQueue, | |
| // Sequence is being run by a worker. | |
| kInWorker, | |
| }; | |
| // |traits| is metadata that applies to all Tasks in the Sequence. | |
| // |task_runner| is a reference to the TaskRunner feeding this TaskSource. | |
| // |task_runner| can be nullptr only for tasks with no TaskRunner, in which | |
| // case |execution_mode| must be kParallel. Otherwise, |execution_mode| is the | |
| // execution mode of |task_runner|. | |
| Sequence(const TaskTraits& traits, | |
| TaskRunner* task_runner, | |
| TaskSourceExecutionMode execution_mode); | |
| Sequence(const Sequence&) = delete; | |
| Sequence& operator=(const Sequence&) = delete; | |
| // Begins a Transaction. This method cannot be called on a thread which has an | |
| // active Sequence::Transaction. | |
| [[nodiscard]] Transaction BeginTransaction(); | |
| // TaskSource: | |
| ExecutionEnvironment GetExecutionEnvironment() override; | |
| size_t GetRemainingConcurrency() const override; | |
| TaskSourceSortKey GetSortKey() const override; | |
| TimeTicks GetDelayedSortKey() const override; | |
| // Returns a token that uniquely identifies this Sequence. | |
| const SequenceToken& token() const { return token_; } | |
| SequenceLocalStorageMap* sequence_local_storage() { | |
| return &sequence_local_storage_; | |
| } | |
| SequenceLocation GetCurrentLocationForTesting(); | |
| void OnBecomeReady() override; | |
| private: | |
| ~Sequence() override; | |
| struct DelayedTaskGreater { | |
| bool operator()(const Task& lhs, const Task& rhs) const; | |
| }; | |
| // TaskSource: | |
| RunStatus WillRunTask() override; | |
| Task TakeTask(TaskSource::Transaction* transaction) override; | |
| Task Clear(TaskSource::Transaction* transaction) override; | |
| bool DidProcessTask(TaskSource::Transaction* transaction) override; | |
| bool WillReEnqueue(TimeTicks now, | |
| TaskSource::Transaction* transaction) override; | |
| // Selects the earliest task to run, either from immediate or | |
| // delayed queue and return it. | |
| // Expects this sequence to have at least one task that can run | |
| // immediately. | |
| Task TakeEarliestTask(); | |
| // Get and return next task from immediate queue | |
| Task TakeNextImmediateTask(); | |
| // Determine next ready time and set ready time to it | |
| TimeTicks GetNextReadyTime(); | |
| // Returns true if there are immediate tasks | |
| bool HasImmediateTasks() const; | |
| // Returns true if there are tasks ripe for execution in the delayed queue | |
| bool HasRipeDelayedTasks(TimeTicks now) const; | |
| // Returns true if tasks ready to be executed | |
| bool HasReadyTasks(TimeTicks now) const; | |
| bool IsEmpty() const; | |
| TimeTicks GetReadyTime() const; | |
| // Releases reference to TaskRunner. | |
| void ReleaseTaskRunner(); | |
| const SequenceToken token_ = SequenceToken::Create(); | |
| // Queues of tasks to execute. | |
| base::queue<Task> queue_; | |
| base::IntrusiveHeap<Task, DelayedTaskGreater> delayed_queue_; | |
| std::atomic<TimeTicks> ready_time_{TimeTicks()}; | |
| // Holds data stored through the SequenceLocalStorageSlot API. | |
| SequenceLocalStorageMap sequence_local_storage_; | |
| // This member will hold the current location of the sequence at any time. | |
| // At instantiation, the sequence is not put in any queue yet so the | |
| // sequence location is set to |kNone|. | |
| std::atomic<SequenceLocation> current_location_{SequenceLocation::kNone}; | |
| }; | |
| } // namespace internal | |
| } // namespace base | |
| #endif // BASE_TASK_THREAD_POOL_SEQUENCE_H_ |