1 // Copyright 2016 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef BASE_TASK_SCHEDULER_TASK_TRACKER_H_ 6 #define BASE_TASK_SCHEDULER_TASK_TRACKER_H_ 7 8 #include <functional> 9 #include <memory> 10 #include <queue> 11 12 #include "base/atomicops.h" 13 #include "base/base_export.h" 14 #include "base/callback_forward.h" 15 #include "base/debug/task_annotator.h" 16 #include "base/logging.h" 17 #include "base/macros.h" 18 #include "base/metrics/histogram_base.h" 19 #include "base/strings/string_piece.h" 20 #include "base/synchronization/waitable_event.h" 21 #include "base/task_scheduler/can_schedule_sequence_observer.h" 22 #include "base/task_scheduler/scheduler_lock.h" 23 #include "base/task_scheduler/sequence.h" 24 #include "base/task_scheduler/task.h" 25 #include "base/task_scheduler/task_traits.h" 26 #include "base/task_scheduler/tracked_ref.h" 27 28 namespace base { 29 30 class ConditionVariable; 31 class HistogramBase; 32 33 namespace internal { 34 35 // TaskTracker enforces policies that determines whether: 36 // - A task can be added to a sequence (WillPostTask). 37 // - A sequence can be scheduled (WillScheduleSequence). 38 // - The next task in a scheduled sequence can run (RunAndPopNextTask). 39 // TaskTracker also sets up the environment to run a task (RunAndPopNextTask) 40 // and records metrics and trace events. This class is thread-safe. 41 // 42 // Life of a sequence: 43 // (possible states: IDLE, PREEMPTED, SCHEDULED, RUNNING) 44 // 45 // Create a sequence 46 // | 47 // ------------------------> Sequence is IDLE 48 // | | 49 // | Add a task to the sequence 50 // | (allowed by TaskTracker::WillPostTask) 51 // | | 52 // | TaskTracker:WillScheduleSequence 53 // | _____________________|_____________________ 54 // | | | 55 // | Returns true Returns false 56 // | | | 57 // | | Sequence is PREEMPTED <---- 58 // | | | | 59 // | | Eventually, | 60 // | | CanScheduleSequenceObserver | 61 // | | is notified that the | 62 // | | sequence can be scheduled. | 63 // | |__________________________________________| | 64 // | | | 65 // | (*) Sequence is SCHEDULED | 66 // | | | 67 // | A thread is ready to run the next | 68 // | task in the sequence | 69 // | | | 70 // | TaskTracker::RunAndPopNextTask | 71 // | A task from the sequence is run | 72 // | Sequence is RUNNING | 73 // | | | 74 // | ______________________|____ | 75 // | | | | 76 // | Sequence is empty Sequence has more tasks | 77 // |_________| _____________|_______________ | 78 // | | | 79 // Sequence can be Sequence cannot be | 80 // scheduled scheduled at this | 81 // | moment | 82 // Go back to (*) |_________________| 83 // 84 // 85 // Note: A background task is a task posted with TaskPriority::BACKGROUND. A 86 // foreground task is a task posted with TaskPriority::USER_VISIBLE or 87 // TaskPriority::USER_BLOCKING. 88 // 89 // TODO(fdoray): We want to allow disabling TaskPriority::BACKGROUND tasks in a 90 // scope (e.g. during startup or page load), but we don't need a dynamic maximum 91 // number of background tasks. The code could probably be simplified if it 92 // didn't support that. https://crbug.com/831835 93 class BASE_EXPORT TaskTracker { 94 public: 95 // |histogram_label| is used as a suffix for histograms, it must not be empty. 96 // The first constructor sets the maximum number of TaskPriority::BACKGROUND 97 // sequences that can be scheduled concurrently to 0 if the 98 // --disable-background-tasks flag is specified, max() otherwise. The second 99 // constructor sets it to |max_num_scheduled_background_sequences|. 100 TaskTracker(StringPiece histogram_label); 101 TaskTracker(StringPiece histogram_label, 102 int max_num_scheduled_background_sequences); 103 104 virtual ~TaskTracker(); 105 106 // Synchronously shuts down the scheduler. Once this is called, only tasks 107 // posted with the BLOCK_SHUTDOWN behavior will be run. Returns when: 108 // - All SKIP_ON_SHUTDOWN tasks that were already running have completed their 109 // execution. 110 // - All posted BLOCK_SHUTDOWN tasks have completed their execution. 111 // CONTINUE_ON_SHUTDOWN tasks still may be running after Shutdown returns. 112 // This can only be called once. 113 void Shutdown(); 114 115 // Waits until there are no incomplete undelayed tasks. May be called in tests 116 // to validate that a condition is met after all undelayed tasks have run. 117 // 118 // Does not wait for delayed tasks. Waits for undelayed tasks posted from 119 // other threads during the call. Returns immediately when shutdown completes. 120 void FlushForTesting(); 121 122 // Returns and calls |flush_callback| when there are no incomplete undelayed 123 // tasks. |flush_callback| may be called back on any thread and should not 124 // perform a lot of work. May be used when additional work on the current 125 // thread needs to be performed during a flush. Only one 126 // FlushAsyncForTesting() may be pending at any given time. 127 void FlushAsyncForTesting(OnceClosure flush_callback); 128 129 // Informs this TaskTracker that |task| is about to be posted. Returns true if 130 // this operation is allowed (|task| should be posted if-and-only-if it is). 131 // This method may also modify metadata on |task| if desired. 132 bool WillPostTask(Task* task); 133 134 // Informs this TaskTracker that |sequence| is about to be scheduled. If this 135 // returns |sequence|, it is expected that RunAndPopNextTask() will soon be 136 // called with |sequence| as argument. Otherwise, RunAndPopNextTask() must not 137 // be called with |sequence| as argument until |observer| is notified that 138 // |sequence| can be scheduled (the caller doesn't need to keep a pointer to 139 // |sequence|; it will be included in the notification to |observer|). 140 // WillPostTask() must have allowed the task in front of |sequence| to be 141 // posted before this is called. |observer| is only required if the priority 142 // of |sequence| is TaskPriority::BACKGROUND 143 scoped_refptr<Sequence> WillScheduleSequence( 144 scoped_refptr<Sequence> sequence, 145 CanScheduleSequenceObserver* observer); 146 147 // Runs the next task in |sequence| unless the current shutdown state prevents 148 // that. Then, pops the task from |sequence| (even if it didn't run). Returns 149 // |sequence| if it can be rescheduled immediately. If |sequence| is non-empty 150 // after popping a task from it but it can't be rescheduled immediately, it 151 // will be handed back to |observer| when it can be rescheduled. 152 // WillPostTask() must have allowed the task in front of |sequence| to be 153 // posted before this is called. Also, WillScheduleSequence(), 154 // RunAndPopNextTask() or CanScheduleSequenceObserver::OnCanScheduleSequence() 155 // must have allowed |sequence| to be (re)scheduled. 156 scoped_refptr<Sequence> RunAndPopNextTask( 157 scoped_refptr<Sequence> sequence, 158 CanScheduleSequenceObserver* observer); 159 160 // Returns true once shutdown has started (Shutdown() has been called but 161 // might not have returned). Note: sequential consistency with the thread 162 // calling Shutdown() (or SetHasShutdownStartedForTesting()) isn't guaranteed 163 // by this call. 164 bool HasShutdownStarted() const; 165 166 // Returns true if shutdown has completed (Shutdown() has returned). 167 bool IsShutdownComplete() const; 168 169 enum class LatencyHistogramType { 170 // Records the latency of each individual task posted through TaskTracker. 171 TASK_LATENCY, 172 // Records the latency of heartbeat tasks which are independent of current 173 // workload. These avoid a bias towards TASK_LATENCY reporting that high- 174 // priority tasks are "slower" than regular tasks because high-priority 175 // tasks tend to be correlated with heavy workloads. 176 HEARTBEAT_LATENCY, 177 }; 178 179 // Causes HasShutdownStarted() to return true. Unlike when Shutdown() returns, 180 // IsShutdownComplete() won't return true after this returns. Shutdown() 181 // cannot be called after this. 182 void SetHasShutdownStartedForTesting(); 183 184 // Records |Now() - posted_time| to the appropriate |latency_histogram_type| 185 // based on |task_traits|. 186 void RecordLatencyHistogram(LatencyHistogramType latency_histogram_type, 187 TaskTraits task_traits, 188 TimeTicks posted_time) const; 189 GetTrackedRef()190 TrackedRef<TaskTracker> GetTrackedRef() { 191 return tracked_ref_factory_.GetTrackedRef(); 192 } 193 194 protected: 195 // Runs and deletes |task| if |can_run_task| is true. Otherwise, just deletes 196 // |task|. |task| is always deleted in the environment where it runs or would 197 // have run. |sequence| is the sequence from which |task| was extracted. An 198 // override is expected to call its parent's implementation but is free to 199 // perform extra work before and after doing so. 200 virtual void RunOrSkipTask(Task task, Sequence* sequence, bool can_run_task); 201 202 #if DCHECK_IS_ON() 203 // Returns true if this context should be exempt from blocking shutdown 204 // DCHECKs. 205 // TODO(robliao): Remove when http://crbug.com/698140 is fixed. 206 virtual bool IsPostingBlockShutdownTaskAfterShutdownAllowed(); 207 #endif 208 209 // Returns true if there are undelayed tasks that haven't completed their 210 // execution (still queued or in progress). If it returns false: the side- 211 // effects of all completed tasks are guaranteed to be visible to the caller. 212 bool HasIncompleteUndelayedTasksForTesting() const; 213 214 private: 215 class State; 216 struct PreemptedBackgroundSequence; 217 218 void PerformShutdown(); 219 220 // Updates the maximum number of background sequences that can be scheduled 221 // concurrently to |max_num_scheduled_background_sequences|. Then, schedules 222 // as many preempted background sequences as allowed by the new value. 223 void SetMaxNumScheduledBackgroundSequences( 224 int max_num_scheduled_background_sequences); 225 226 // Pops the next sequence in |preempted_background_sequences_| and increments 227 // |num_scheduled_background_sequences_|. Must only be called in the scope of 228 // |background_lock_|, with |preempted_background_sequences_| non-empty. The 229 // caller must forward the returned sequence to the associated 230 // CanScheduleSequenceObserver as soon as |background_lock_| is released. 231 PreemptedBackgroundSequence 232 GetPreemptedBackgroundSequenceToScheduleLockRequired(); 233 234 // Schedules |sequence_to_schedule.sequence| using 235 // |sequence_to_schedule.observer|. Does not verify that the sequence is 236 // allowed to be scheduled. 237 void SchedulePreemptedBackgroundSequence( 238 PreemptedBackgroundSequence sequence_to_schedule); 239 240 // Called before WillPostTask() informs the tracing system that a task has 241 // been posted. Updates |num_tasks_blocking_shutdown_| if necessary and 242 // returns true if the current shutdown state allows the task to be posted. 243 bool BeforePostTask(TaskShutdownBehavior shutdown_behavior); 244 245 // Called before a task with |shutdown_behavior| is run by RunTask(). Updates 246 // |num_tasks_blocking_shutdown_| if necessary and returns true if the current 247 // shutdown state allows the task to be run. 248 bool BeforeRunTask(TaskShutdownBehavior shutdown_behavior); 249 250 // Called after a task with |shutdown_behavior| has been run by RunTask(). 251 // Updates |num_tasks_blocking_shutdown_| and signals |shutdown_cv_| if 252 // necessary. 253 void AfterRunTask(TaskShutdownBehavior shutdown_behavior); 254 255 // Called when the number of tasks blocking shutdown becomes zero after 256 // shutdown has started. 257 void OnBlockingShutdownTasksComplete(); 258 259 // Decrements the number of incomplete undelayed tasks and signals |flush_cv_| 260 // if it reaches zero. 261 void DecrementNumIncompleteUndelayedTasks(); 262 263 // To be called after running a background task from |just_ran_sequence|. 264 // Performs the following actions: 265 // - If |just_ran_sequence| is non-null: 266 // - returns it if it should be rescheduled by the caller of 267 // RunAndPopNextTask(), i.e. its next task is set to run earlier than the 268 // earliest currently preempted sequence. 269 // - Otherwise |just_ran_sequence| is preempted and the next preempted 270 // sequence is scheduled (|observer| will be notified when 271 // |just_ran_sequence| should be scheduled again). 272 // - If |just_ran_sequence| is null (RunAndPopNextTask() just popped the last 273 // task from it): 274 // - the next preempeted sequence (if any) is scheduled. 275 // - In all cases: adjusts the number of scheduled background sequences 276 // accordingly. 277 scoped_refptr<Sequence> ManageBackgroundSequencesAfterRunningTask( 278 scoped_refptr<Sequence> just_ran_sequence, 279 CanScheduleSequenceObserver* observer); 280 281 // Calls |flush_callback_for_testing_| if one is available in a lock-safe 282 // manner. 283 void CallFlushCallbackForTesting(); 284 285 debug::TaskAnnotator task_annotator_; 286 287 // Number of tasks blocking shutdown and boolean indicating whether shutdown 288 // has started. 289 const std::unique_ptr<State> state_; 290 291 // Number of undelayed tasks that haven't completed their execution. Is 292 // decremented with a memory barrier after a task runs. Is accessed with an 293 // acquire memory barrier in FlushForTesting(). The memory barriers ensure 294 // that the memory written by flushed tasks is visible when FlushForTesting() 295 // returns. 296 subtle::Atomic32 num_incomplete_undelayed_tasks_ = 0; 297 298 // Lock associated with |flush_cv_|. Partially synchronizes access to 299 // |num_incomplete_undelayed_tasks_|. Full synchronization isn't needed 300 // because it's atomic, but synchronization is needed to coordinate waking and 301 // sleeping at the right time. Fully synchronizes access to 302 // |flush_callback_for_testing_|. 303 mutable SchedulerLock flush_lock_; 304 305 // Signaled when |num_incomplete_undelayed_tasks_| is or reaches zero or when 306 // shutdown completes. 307 const std::unique_ptr<ConditionVariable> flush_cv_; 308 309 // Invoked if non-null when |num_incomplete_undelayed_tasks_| is zero or when 310 // shutdown completes. 311 OnceClosure flush_callback_for_testing_; 312 313 // Synchronizes access to shutdown related members below. 314 mutable SchedulerLock shutdown_lock_; 315 316 // Event instantiated when shutdown starts and signaled when shutdown 317 // completes. 318 std::unique_ptr<WaitableEvent> shutdown_event_; 319 320 // Synchronizes accesses to |preempted_background_sequences_|, 321 // |max_num_scheduled_background_sequences_| and 322 // |num_scheduled_background_sequences_|. 323 SchedulerLock background_lock_; 324 325 // A priority queue of sequences that are waiting to be scheduled. Use 326 // std::greater so that the sequence which contains the task that has been 327 // posted the earliest is on top of the priority queue. 328 std::priority_queue<PreemptedBackgroundSequence, 329 std::vector<PreemptedBackgroundSequence>, 330 std::greater<PreemptedBackgroundSequence>> 331 preempted_background_sequences_; 332 333 // Maximum number of background sequences that can that be scheduled 334 // concurrently. 335 int max_num_scheduled_background_sequences_; 336 337 // Number of currently scheduled background sequences. 338 int num_scheduled_background_sequences_ = 0; 339 340 // TaskScheduler.TaskLatencyMicroseconds.* and 341 // TaskScheduler.HeartbeatLatencyMicroseconds.* histograms. The first index is 342 // a TaskPriority. The second index is 0 for non-blocking tasks, 1 for 343 // blocking tasks. Intentionally leaked. 344 // TODO(scheduler-dev): Consider using STATIC_HISTOGRAM_POINTER_GROUP for 345 // these. 346 static constexpr int kNumTaskPriorities = 347 static_cast<int>(TaskPriority::HIGHEST) + 1; 348 HistogramBase* const task_latency_histograms_[kNumTaskPriorities][2]; 349 HistogramBase* const heartbeat_latency_histograms_[kNumTaskPriorities][2]; 350 351 // Number of BLOCK_SHUTDOWN tasks posted during shutdown. 352 HistogramBase::Sample num_block_shutdown_tasks_posted_during_shutdown_ = 0; 353 354 // Ensures all state (e.g. dangling cleaned up workers) is coalesced before 355 // destroying the TaskTracker (e.g. in test environments). 356 // Ref. https://crbug.com/827615. 357 TrackedRefFactory<TaskTracker> tracked_ref_factory_; 358 359 DISALLOW_COPY_AND_ASSIGN(TaskTracker); 360 }; 361 362 } // namespace internal 363 } // namespace base 364 365 #endif // BASE_TASK_SCHEDULER_TASK_TRACKER_H_ 366