• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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