1 // Copyright 2021 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/task/sequence_manager/wake_up_queue.h"
6
7 #include "base/task/sequence_manager/associated_thread_id.h"
8 #include "base/task/sequence_manager/sequence_manager_impl.h"
9 #include "base/task/sequence_manager/task_queue_impl.h"
10 #include "base/threading/thread_checker.h"
11 #include "third_party/abseil-cpp/absl/types/optional.h"
12
13 namespace base {
14 namespace sequence_manager {
15 namespace internal {
16
WakeUpQueue(scoped_refptr<const internal::AssociatedThreadId> associated_thread)17 WakeUpQueue::WakeUpQueue(
18 scoped_refptr<const internal::AssociatedThreadId> associated_thread)
19 : associated_thread_(std::move(associated_thread)) {}
20
~WakeUpQueue()21 WakeUpQueue::~WakeUpQueue() {
22 DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker);
23 }
24
RemoveAllCanceledDelayedTasksFromFront(LazyNow * lazy_now)25 void WakeUpQueue::RemoveAllCanceledDelayedTasksFromFront(LazyNow* lazy_now) {
26 // Repeatedly trim the front of the top queue until it stabilizes. This is
27 // needed because a different queue can become the top one once you remove the
28 // canceled tasks.
29 while (!wake_up_queue_.empty()) {
30 auto* top_queue = wake_up_queue_.top().queue.get();
31
32 // If no tasks are removed from the top queue, then it means the top queue
33 // cannot change anymore.
34 if (!top_queue->RemoveAllCanceledDelayedTasksFromFront(lazy_now))
35 break;
36 }
37 }
38
39 // TODO(kraynov): https://crbug.com/857101 Consider making an interface
40 // for SequenceManagerImpl which will expose SetNextDelayedDoWork and
41 // MaybeScheduleImmediateWork methods to make the functions below pure-virtual.
42
SetNextWakeUpForQueue(internal::TaskQueueImpl * queue,LazyNow * lazy_now,absl::optional<WakeUp> wake_up)43 void WakeUpQueue::SetNextWakeUpForQueue(internal::TaskQueueImpl* queue,
44 LazyNow* lazy_now,
45 absl::optional<WakeUp> wake_up) {
46 DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker);
47 DCHECK_EQ(queue->wake_up_queue(), this);
48 DCHECK(queue->IsQueueEnabled() || !wake_up);
49
50 absl::optional<WakeUp> previous_wake_up = GetNextDelayedWakeUp();
51 absl::optional<WakeUpResolution> previous_queue_resolution;
52 if (queue->heap_handle().IsValid()) {
53 previous_queue_resolution =
54 wake_up_queue_.at(queue->heap_handle()).wake_up.resolution;
55 }
56
57 if (wake_up) {
58 // Insert a new wake-up into the heap.
59 if (queue->heap_handle().IsValid()) {
60 // O(log n)
61 wake_up_queue_.Replace(queue->heap_handle(), {wake_up.value(), queue});
62 } else {
63 // O(log n)
64 wake_up_queue_.insert({wake_up.value(), queue});
65 }
66 } else {
67 // Remove a wake-up from heap if present.
68 if (queue->heap_handle().IsValid())
69 wake_up_queue_.erase(queue->heap_handle());
70 }
71
72 absl::optional<WakeUp> new_wake_up = GetNextDelayedWakeUp();
73
74 if (previous_queue_resolution &&
75 *previous_queue_resolution == WakeUpResolution::kHigh) {
76 pending_high_res_wake_up_count_--;
77 }
78 if (wake_up && wake_up->resolution == WakeUpResolution::kHigh)
79 pending_high_res_wake_up_count_++;
80 DCHECK_GE(pending_high_res_wake_up_count_, 0);
81
82 if (new_wake_up != previous_wake_up)
83 OnNextWakeUpChanged(lazy_now, GetNextDelayedWakeUp());
84 }
85
MoveReadyDelayedTasksToWorkQueues(LazyNow * lazy_now,EnqueueOrder enqueue_order)86 void WakeUpQueue::MoveReadyDelayedTasksToWorkQueues(
87 LazyNow* lazy_now,
88 EnqueueOrder enqueue_order) {
89 DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker);
90 bool update_needed = false;
91 while (!wake_up_queue_.empty() &&
92 wake_up_queue_.top().wake_up.earliest_time() <= lazy_now->Now()) {
93 internal::TaskQueueImpl* queue = wake_up_queue_.top().queue;
94 // OnWakeUp() is expected to update the next wake-up for this queue with
95 // SetNextWakeUpForQueue(), thus allowing us to make progress.
96 queue->OnWakeUp(lazy_now, enqueue_order);
97 update_needed = true;
98 }
99
100 if (!update_needed || wake_up_queue_.empty())
101 return;
102 // If any queue was notified, possibly update following queues. This ensures
103 // the wake up is up to date, which is necessary because calling OnWakeUp() on
104 // a throttled queue may affect state that is shared between other related
105 // throttled queues. The wake up for an affected queue might be pushed back
106 // and needs to be updated. This is done lazily only once the related queue
107 // becomes the next one to wake up, since that wake up can't be moved up.
108 // `wake_up_queue_` is non-empty here, per the condition above.
109 internal::TaskQueueImpl* queue = wake_up_queue_.top().queue;
110 queue->UpdateWakeUp(lazy_now);
111 while (!wake_up_queue_.empty()) {
112 internal::TaskQueueImpl* old_queue =
113 std::exchange(queue, wake_up_queue_.top().queue);
114 if (old_queue == queue)
115 break;
116 queue->UpdateWakeUp(lazy_now);
117 }
118 }
119
GetNextDelayedWakeUp() const120 absl::optional<WakeUp> WakeUpQueue::GetNextDelayedWakeUp() const {
121 DCHECK_CALLED_ON_VALID_THREAD(associated_thread_->thread_checker);
122 if (wake_up_queue_.empty())
123 return absl::nullopt;
124 WakeUp wake_up = wake_up_queue_.top().wake_up;
125 // `wake_up.resolution` is not meaningful since it may be different from
126 // has_pending_high_resolution_tasks(). Return WakeUpResolution::kLow here to
127 // simplify comparison between wake ups.
128 // TODO(1153139): Drive resolution by DelayPolicy and return
129 // has_pending_high_resolution_tasks() here.
130 wake_up.resolution = WakeUpResolution::kLow;
131 return wake_up;
132 }
133
AsValue(TimeTicks now) const134 Value::Dict WakeUpQueue::AsValue(TimeTicks now) const {
135 Value::Dict state;
136 state.Set("name", GetName());
137 // TODO(crbug.com/1334256): Make base::Value able to store an int64_t and
138 // remove this cast.
139 state.Set("registered_delay_count", checked_cast<int>(wake_up_queue_.size()));
140 if (!wake_up_queue_.empty()) {
141 TimeDelta delay = wake_up_queue_.top().wake_up.time - now;
142 state.Set("next_delay_ms", delay.InMillisecondsF());
143 }
144 return state;
145 }
146
DefaultWakeUpQueue(scoped_refptr<internal::AssociatedThreadId> associated_thread,internal::SequenceManagerImpl * sequence_manager)147 DefaultWakeUpQueue::DefaultWakeUpQueue(
148 scoped_refptr<internal::AssociatedThreadId> associated_thread,
149 internal::SequenceManagerImpl* sequence_manager)
150 : WakeUpQueue(std::move(associated_thread)),
151 sequence_manager_(sequence_manager) {}
152
153 DefaultWakeUpQueue::~DefaultWakeUpQueue() = default;
154
OnNextWakeUpChanged(LazyNow * lazy_now,absl::optional<WakeUp> wake_up)155 void DefaultWakeUpQueue::OnNextWakeUpChanged(LazyNow* lazy_now,
156 absl::optional<WakeUp> wake_up) {
157 sequence_manager_->SetNextWakeUp(lazy_now, wake_up);
158 }
159
UnregisterQueue(internal::TaskQueueImpl * queue)160 void DefaultWakeUpQueue::UnregisterQueue(internal::TaskQueueImpl* queue) {
161 DCHECK_EQ(queue->wake_up_queue(), this);
162 LazyNow lazy_now(sequence_manager_->main_thread_clock());
163 SetNextWakeUpForQueue(queue, &lazy_now, absl::nullopt);
164 }
165
GetName() const166 const char* DefaultWakeUpQueue::GetName() const {
167 return "DefaultWakeUpQueue";
168 }
169
NonWakingWakeUpQueue(scoped_refptr<internal::AssociatedThreadId> associated_thread)170 NonWakingWakeUpQueue::NonWakingWakeUpQueue(
171 scoped_refptr<internal::AssociatedThreadId> associated_thread)
172 : WakeUpQueue(std::move(associated_thread)) {}
173
174 NonWakingWakeUpQueue::~NonWakingWakeUpQueue() = default;
175
OnNextWakeUpChanged(LazyNow * lazy_now,absl::optional<WakeUp> wake_up)176 void NonWakingWakeUpQueue::OnNextWakeUpChanged(LazyNow* lazy_now,
177 absl::optional<WakeUp> wake_up) {
178 }
179
GetName() const180 const char* NonWakingWakeUpQueue::GetName() const {
181 return "NonWakingWakeUpQueue";
182 }
183
UnregisterQueue(internal::TaskQueueImpl * queue)184 void NonWakingWakeUpQueue::UnregisterQueue(internal::TaskQueueImpl* queue) {
185 DCHECK_EQ(queue->wake_up_queue(), this);
186 SetNextWakeUpForQueue(queue, nullptr, absl::nullopt);
187 }
188
189 } // namespace internal
190 } // namespace sequence_manager
191 } // namespace base
192