Implement idle task scheduling.

Source/platform/scheduler/Scheduler.cpp

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "config.h"
 #include "platform/scheduler/Scheduler.h"
 
 #include "platform/PlatformThreadData.h"
 #include "platform/Task.h"
 #include "platform/ThreadTimers.h"
 #include "platform/TraceEvent.h"
 #include "public/platform/Platform.h"
 #include "wtf/MainThread.h"
 
 namespace blink {
 
 namespace {
 
 // The time we should stay in CompositorPriority mode for, after a touch event.
 double kLowSchedulerPolicyAfterTouchTimeSeconds = 0.1;
 
-// Can be created from any thread.
-// Note if the scheduler gets shutdown, this may be run after.
-class MainThreadIdleTaskAdapter : public WebThread::Task {
-public:
-    MainThreadIdleTaskAdapter(const Scheduler::IdleTask& idleTask, double allottedTimeMs, const TraceLocation& location)
-        : m_idleTask(idleTask)
-        , m_allottedTimeMs(allottedTimeMs)
-        , m_location(location)
-    {
-    }
-
-    // WebThread::Task implementation.
-    virtual void run() OVERRIDE
-    {
-        TRACE_EVENT2("blink", "MainThreadIdleTaskAdapter::run",
-            "src_file", m_location.fileName(),
-            "src_func", m_location.functionName());
-        m_idleTask(m_allottedTimeMs);
-    }
-
-private:
-    Scheduler::IdleTask m_idleTask;
-    double m_allottedTimeMs;
-    TraceLocation m_location;
-};
-
 } // namespace
 
 // Typically only created from compositor or render threads.
 // Note if the scheduler gets shutdown, this may be run after.
 class Scheduler::MainThreadPendingHighPriorityTaskRunner : public WebThread::Task {
 public:
     MainThreadPendingHighPriorityTaskRunner()
     {
         ASSERT(Scheduler::shared());
     }
@@ skipping 21 matching lines @@
         const Scheduler::Task& task, const TraceLocation& location, const char* traceName)
         : m_task(task, location, traceName)
     {
         ASSERT(Scheduler::shared());
     }
 
     // WebThread::Task implementation.
     virtual void run() OVERRIDE
     {
         Scheduler* scheduler = Scheduler::shared();
-        // FIXME: This check should't be necessary, tasks should not outlive blink.
+        // FIXME: This check shouldn't be necessary, tasks should not outlive blink.
         ASSERT(scheduler);
         if (scheduler)
-            Scheduler::shared()->runPendingHighPriorityTasksIfInCompositorPriority();
+            scheduler->runPendingHighPriorityTasksIfInCompositorPriority();
+
         m_task.run();
     }
 
-    TracedTask m_task;
+private:
+    TracedStandardTask m_task;
 };
 
+
+// Can be created from any thread.
+// Note if the scheduler gets shutdown, this may be run after.
+class Scheduler::MainThreadPendingIdleTaskRunner : public WebThread::Task {
+public:
+    MainThreadPendingIdleTaskRunner()
+    {
+        ASSERT(Scheduler::shared());
+    }
+
+    // WebThread::Task implementation.
+    virtual void run() OVERRIDE
+    {
+        Scheduler* scheduler = Scheduler::shared();
+        // FIXME: This check shouldn't be necessary, tasks should not outlive blink.
+        ASSERT(scheduler);
+        if (scheduler) {
+            scheduler->runPendingHighPriorityTasksIfInCompositorPriority();
+            scheduler->runPendingIdleTaskIfCanRunIdleTask();
+            // If possible, run the next idle task by reposting on the main thread.
+            scheduler->maybePostMainThreadPendingIdleTask();
+        }
+    }
+
+};
+
+
 Scheduler* Scheduler::s_sharedScheduler = nullptr;
 
 void Scheduler::initializeOnMainThread()
 {
     s_sharedScheduler = new Scheduler();
 }
 
 void Scheduler::shutdown()
 {
     delete s_sharedScheduler;
     s_sharedScheduler = nullptr;
 }
 
 Scheduler* Scheduler::shared()
 {
     return s_sharedScheduler;
 }
 
 Scheduler::Scheduler()
     : m_sharedTimerFunction(nullptr)
     , m_mainThread(blink::Platform::current()->currentThread())
     , m_compositorPriorityPolicyEndTimeSeconds(0)
+    , m_currentFrameDeadlineSeconds(0)
     , m_highPriorityTaskCount(0)
     , m_highPriorityTaskRunnerPosted(false)
     , m_schedulerPolicy(Normal)
 {
 }
 
 Scheduler::~Scheduler()
 {
     while (hasPendingHighPriorityWork()) {
         swapQueuesAndRunPendingTasks();
     }
 }
 
-void Scheduler::willBeginFrame(const WebBeginFrameArgs& args)
+void Scheduler::willBeginFrame(double frameDeadlineSeconds)
 {
-    // TODO: Use frame deadline and interval to schedule idle tasks.
+    m_currentFrameCommitted = false;
+    m_currentFrameDeadlineSeconds = frameDeadlineSeconds;
+    // TODO: Schedule a deferred task here to run idle work if didCommitFrameToCompositor never get's called
 }
 
 void Scheduler::didCommitFrameToCompositor()
 {
-    // TODO: Trigger the frame deadline immediately.
-}
-
-void Scheduler::scheduleIdleTask(const TraceLocation& location, const IdleTask& idleTask)
-{
-    // TODO: send a real allottedTime here.
-    m_mainThread->postTask(new MainThreadIdleTaskAdapter(idleTask, 0, location));
+    m_currentFrameCommitted = true;
+    maybePostMainThreadPendingIdleTask();
 }
 
 void Scheduler::postHighPriorityTaskInternal(const TraceLocation& location, const Task& task, const char* traceName)
 {
     Locker<Mutex> lock(m_pendingTasksMutex);
 
-    m_pendingHighPriorityTasks.append(TracedTask(task, location, traceName));
+    m_pendingHighPriorityTasks.append(TracedStandardTask(task, location, traceName));
     atomicIncrement(&m_highPriorityTaskCount);
     maybePostMainThreadPendingHighPriorityTaskRunner();
     TRACE_COUNTER1(TRACE_DISABLED_BY_DEFAULT("blink.scheduler"), "PendingHighPriorityTasks", m_highPriorityTaskCount);
 }
 
+void Scheduler::postIdleTaskInternal(const TraceLocation& location, const IdleTask& idleTask, const char* traceName)
+{
+    Locker<Mutex> lock(m_pendingTasksMutex);
+    m_pendingIdleTasks.append(TracedIdleTask(idleTask, location, traceName));
+}
+
 void Scheduler::postTask(const TraceLocation& location, const Task& task)
 {
     m_mainThread->postTask(new MainThreadPendingTaskRunner(task, location, "Scheduler::MainThreadTask"));
 }
 
 void Scheduler::postInputTask(const TraceLocation& location, const Task& task)
 {
     postHighPriorityTaskInternal(location, task, "Scheduler::InputTask");
 }
 
 void Scheduler::didReceiveInputEvent()
 {
     enterSchedulerPolicy(CompositorPriority);
 }
 
 void Scheduler::postCompositorTask(const TraceLocation& location, const Task& task)
 {
     postHighPriorityTaskInternal(location, task, "Scheduler::CompositorTask");
 }
 
 void Scheduler::postIpcTask(const TraceLocation& location, const Task& task)
 {
     // FIXME: we want IPCs to be high priority, but we can't currently do that because some of them can take a very long
     // time to process. These need refactoring but we need to add some infrastructure to identify them.
     m_mainThread->postTask(new MainThreadPendingTaskRunner(task, location, "Scheduler::IpcTask"));
 }
 
+void Scheduler::postIdleTask(const TraceLocation& location, const IdleTask& idleTask)
+{
+    postIdleTaskInternal(location, idleTask, "Scheduler::IdleTask");
+}
+
 void Scheduler::maybePostMainThreadPendingHighPriorityTaskRunner()
 {
     ASSERT(m_pendingTasksMutex.locked());
     if (m_highPriorityTaskRunnerPosted)
         return;
     m_mainThread->postTask(new MainThreadPendingHighPriorityTaskRunner());
     m_highPriorityTaskRunnerPosted = true;
 }
 
-void Scheduler::postIdleTask(const TraceLocation& location, const IdleTask& idleTask)
+bool Scheduler::maybePostMainThreadPendingIdleTask()
 {
-    scheduleIdleTask(location, idleTask);
+    TRACE_EVENT0("blink", "Scheduler::maybePostMainThreadPendingIdleTask");
+    if (canRunIdleTask()) {

[alexclarke, 2014/10/03 09:59:19]

Which threads will this function get called from?  If it's only the Blink
scheduler thread then this is fine (please add an assert if so), otherwise I'm
not sure this is safe and I suspect it needs to be guarded by the mutex.

Likewise willBeginFrame and didCommitFrameToCompositor should be too. I hope
that doesn't open the possibility of deadlocking.

[Sami, 2014/10/03 10:39:21]

Looks like m_pendingIdleTasks is the only bit of cross-thread data here, right?

[rmcilroy, 2014/10/03 21:41:21]

Right, mpendingIdleTasks is the only bit of cross-thread data here.  I've added
the check that this is only called on one thread.

+        Locker<Mutex> lock(m_pendingTasksMutex);
+        if (!m_pendingIdleTasks.isEmpty()) {
+            m_mainThread->postTask(new MainThreadPendingIdleTaskRunner());
+            return true;
+        }
+    }
+    return false;
 }
 
 void Scheduler::tickSharedTimer()
 {
     TRACE_EVENT0("blink", "Scheduler::tickSharedTimer");
 
     // Run any high priority tasks that are queued up, otherwise the blink timers will yield immediately.
     bool workDone = runPendingHighPriorityTasksIfInCompositorPriority();
     m_sharedTimerFunction();
 
     // The blink timers may have just yielded, so run any high priority tasks that where queued up
     // while the blink timers were executing.
     if (!workDone)
         runPendingHighPriorityTasksIfInCompositorPriority();
 }
 
 bool Scheduler::runPendingHighPriorityTasksIfInCompositorPriority()
 {
     ASSERT(isMainThread());
     if (schedulerPolicy() != CompositorPriority)
         return false;
 
     return swapQueuesAndRunPendingTasks();
 }
 
+bool Scheduler::runPendingIdleTaskIfCanRunIdleTask()

[alexclarke, 2014/10/03 09:59:19]

nit: how about maybeRunPendingIdleTask?

[rmcilroy, 2014/10/03 21:41:21]

Done.

+{
+    ASSERT(isMainThread());
+    m_pendingTasksMutex.lock();

[Sami, 2014/10/03 10:39:21]

Is there a way we could rewrite this to use a Locker? For example by having a
takeFirstTask(m_pendingIdleTasks) helper that handles locking?

[rmcilroy, 2014/10/03 21:41:21]

I originally tried to write this to use a locker, however it wasn't really
possible if I keep the isEmpty check since I would need to be able to return a
NULL task (which I can't do unless I allocate on the heap), or pass a task to be
filled in, which seems a bad design.

Saying that, we shouldn't really need to check whether the queue is empty since
this method will only be run if there was a task on the queue already, so I have
rewritten it without this check, wdyt?

+    if (canRunIdleTask() && !m_pendingIdleTasks.isEmpty()) {

[alexclarke, 2014/10/03 09:59:18]

While personally I like it your way, I'm under the impression it's more
consistent with blink style to invert the if like so:

if (!canRunIdleTask() || m_pendingIdleTasks.isEmpty()) {
   m_pendingTasksMutex.unlock();
   return false;
}

[rmcilroy, 2014/10/03 21:41:21]

Done.

+        TracedIdleTask task = m_pendingIdleTasks.takeFirst();
+        m_pendingTasksMutex.unlock();
+        task.run();
+        return true;
+    }
+    m_pendingTasksMutex.unlock();
+    return false;
+}
+
 bool Scheduler::swapQueuesAndRunPendingTasks()
 {
     ASSERT(isMainThread());
 
     // These locks guard against another thread posting input or compositor tasks while we swap the buffers.
     // One the buffers have been swapped we can safely access the returned deque without having to lock.
     m_pendingTasksMutex.lock();
-    Deque<TracedTask>& highPriorityTasks = m_pendingHighPriorityTasks.swapBuffers();
+    Deque<TracedStandardTask>& highPriorityTasks = m_pendingHighPriorityTasks.swapBuffers();
     maybeEnterNormalSchedulerPolicy();
     m_pendingTasksMutex.unlock();
     return executeHighPriorityTasks(highPriorityTasks);
 }
 
 void Scheduler::swapQueuesRunPendingTasksAndAllowHighPriorityTaskRunnerPosting()
 {
     ASSERT(isMainThread());
 
     // These locks guard against another thread posting input or compositor tasks while we swap the buffers.
     // One the buffers have been swapped we can safely access the returned deque without having to lock.
     m_pendingTasksMutex.lock();
-    Deque<TracedTask>& highPriorityTasks = m_pendingHighPriorityTasks.swapBuffers();
+    Deque<TracedStandardTask>& highPriorityTasks = m_pendingHighPriorityTasks.swapBuffers();
     m_highPriorityTaskRunnerPosted = false;
     maybeEnterNormalSchedulerPolicy();
     m_pendingTasksMutex.unlock();
     executeHighPriorityTasks(highPriorityTasks);
 }
 
 void Scheduler::maybeEnterNormalSchedulerPolicy()
 {
     ASSERT(isMainThread());
     ASSERT(m_pendingTasksMutex.locked());
 
     // Go back to the normal scheduler policy if enough time has elapsed.
     if (schedulerPolicy() == CompositorPriority && Platform::current()->monotonicallyIncreasingTime() > m_compositorPriorityPolicyEndTimeSeconds)
         enterSchedulerPolicyLocked(Normal);
 }
 
-bool Scheduler::executeHighPriorityTasks(Deque<TracedTask>& highPriorityTasks)
+bool Scheduler::executeHighPriorityTasks(Deque<TracedStandardTask>& highPriorityTasks)
 {
     TRACE_EVENT0("blink", "Scheduler::executeHighPriorityTasks");
     int highPriorityTasksExecuted = 0;
     while (!highPriorityTasks.isEmpty()) {
         highPriorityTasks.takeFirst().run();
         highPriorityTasksExecuted++;
     }
 
     int highPriorityTaskCount = atomicSubtract(&m_highPriorityTaskCount, highPriorityTasksExecuted);
     ASSERT_UNUSED(highPriorityTaskCount, highPriorityTaskCount >= 0);
@@ skipping 34 matching lines @@
 bool Scheduler::hasPendingHighPriorityWork() const
 {
     // This method is expected to be run on the main thread, but the high priority tasks will be posted by
     // other threads. We could use locks here, but this function is (sometimes) called a lot by
     // ThreadTimers::sharedTimerFiredInternal so we decided to use atomics + barrier loads here which
     // should be cheaper.
     // NOTE it's possible the barrier read is overkill here, since delayed yielding isn't a big deal.
     return acquireLoad(&m_highPriorityTaskCount) != 0;
 }
 
+double Scheduler::currentFrameDeadlineSeconds() const
+{
+    // TODO: Make idle time more fine-grain chunks when in Compositor priority.
+    return m_currentFrameDeadlineSeconds;

[Sami, 2014/10/03 10:39:21]

ASSERT(isMainThread());

[rmcilroy, 2014/10/03 21:41:21]

Done.

+}
+
+bool Scheduler::canRunIdleTask() const
+{
+    return m_currentFrameCommitted && (m_currentFrameDeadlineSeconds > Platform::current()->monotonicallyIncreasingTime());

[Sami, 2014/10/03 10:39:21]

ASSERT(isMainThread());

[rmcilroy, 2014/10/03 21:41:21]

Done.

+}
+
 Scheduler::SchedulerPolicy Scheduler::schedulerPolicy() const
 {
     ASSERT(isMainThread());
     // It's important not to miss the transition from normal to low latency mode, otherwise we're likely to
     // delay the processing of input tasks. Since that transition is triggered by a different thread, we
     // need either a lock or a memory barrier, and the memory barrier is probably cheaper.
     return static_cast<SchedulerPolicy>(acquireLoad(&m_schedulerPolicy));
 }
 
 void Scheduler::enterSchedulerPolicy(SchedulerPolicy schedulerPolicy)
 {
     Locker<Mutex> lock(m_pendingTasksMutex);
     enterSchedulerPolicyLocked(schedulerPolicy);
 }
 
 void Scheduler::enterSchedulerPolicyLocked(SchedulerPolicy schedulerPolicy)
 {
     ASSERT(m_pendingTasksMutex.locked());
     if (schedulerPolicy == CompositorPriority)
         m_compositorPriorityPolicyEndTimeSeconds = Platform::current()->monotonicallyIncreasingTime() + kLowSchedulerPolicyAfterTouchTimeSeconds;
 
     releaseStore(&m_schedulerPolicy, schedulerPolicy);
     TRACE_COUNTER1(TRACE_DISABLED_BY_DEFAULT("blink.scheduler"), "SchedulerPolicy", schedulerPolicy);
 }
 
 } // namespace blink