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 "public/web/WebBeginFrameArgs.h"

[rmcilroy, 2014/09/24 08:49:18]

Sami: I get a checkdeps error when I include this file, but need to do so to
access the fields in WebBeginFrameArgs.  Can we change the DEPS file to allow
this include or do we need to move things around a bit?

[Sami, 2014/09/24 14:00:40]

Right, we can't use the web/ headers from platform. I think we can just pass the
necessary parameters to willBeginFrame() as separate doubles instead of using
the struct.

[rmcilroy, 2014/09/29 17:42:57]

Done.

 #include "wtf/MainThread.h"
+#include "wtf/PassOwnPtr.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();
+
         m_task.run();
     }
 
-    TracedTask m_task;
+private:
+    TracedStandardTask m_task;
 };
 
+
 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)
 {
-    // TODO: Use frame deadline and interval to schedule idle tasks.
+    m_currentFrameDeadlineSeconds = args.lastFrameTimeMonotonic + args.interval;

[rmcilroy, 2014/09/24 08:49:18]

This is the deadline used by the compositor implementation rather than the
explicit deadline field in args. Should we use the deadline field instead?

[Sami, 2014/09/24 14:00:40]

I think there are two different deadlines here: 1) the time we should start
running idle tasks (i.e., args.deadline) and 2) the time we should stop running
idle tasks in anticipation of new input. I think we should have both as explicit
variables with good names to avoid confusing them.

Looks like your patch uses the second type of deadline so it should base that on
the interval like you are doing.

[rmcilroy, 2014/09/29 17:42:57]

Acknowledged.

 }
 
 void Scheduler::didCommitFrameToCompositor()
 {
+    if (getSecondsUntilFrameDeadline() > 0) {

[Sami, 2014/09/24 14:00:40]

I don't think we want to run any tasks directly in this callback since the code
that calls this also does other things. Let's post another task instead.

[rmcilroy, 2014/09/29 17:42:57]

Sounds like a plan - done.

+        swapQueuesAndRunPendingIdleTasks();
+    }
+    // Reset frame deadline.
+    m_currentFrameDeadlineSeconds = 0;
+
     // 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));
-}
-
 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(adoptPtr(new 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(adoptPtr(new 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)
-{
-    scheduleIdleTask(location, idleTask);
-}
 
 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
@@ skipping 11 matching lines @@
     return swapQueuesAndRunPendingTasks();
 }
 
 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<OwnPtr<TracedTask> >& 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<OwnPtr<TracedTask> >& 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<OwnPtr<TracedTask> >& highPriorityTasks)
 {
     TRACE_EVENT0("blink", "Scheduler::executeHighPriorityTasks");
     int highPriorityTasksExecuted = 0;
     while (!highPriorityTasks.isEmpty()) {
-        highPriorityTasks.takeFirst().run();
+        highPriorityTasks.takeFirst()->run();
         highPriorityTasksExecuted++;
     }
 
     int highPriorityTaskCount = atomicSubtract(&m_highPriorityTaskCount, highPriorityTasksExecuted);
     ASSERT_UNUSED(highPriorityTaskCount, highPriorityTaskCount >= 0);
     TRACE_COUNTER1(TRACE_DISABLED_BY_DEFAULT("blink.scheduler"), "PendingHighPriorityTasks", m_highPriorityTaskCount);
     return highPriorityTasksExecuted > 0;
 }
 
+bool Scheduler::swapQueuesAndRunPendingIdleTasks()
+{
+    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<OwnPtr<TracedTask> >& idleTasks = m_pendingIdleTasks.swapBuffers();
+    m_pendingTasksMutex.unlock();
+    return executeIdleTasks(idleTasks);
+}

[picksi1, 2014/09/25 08:53:31]

I wonder if the added complexity of swapping buffers and then re-posting the
unprocessed tasks will turn out to be worth the hassle? I'm assuming that there
might be a lot of idle tasks but only a few will get processed every frame, so
there will be lots of shuffling going on. As part of my refactor-proposal I
ended up creating a task queue that could return a task at a time, something
like this would make the code much simpler... even if in some instances it would
be slower.

[rmcilroy, 2014/09/29 17:42:57]

I've re-worked this completely such that we only ever take a single task off the
pending idle queue at a time now. At worst that task will be reposted if it
can't be executed, but there is no swapping buffers or reposting of many items.
Actually I don't think the pending idle queue will be very large, probably only
a few items in it most of the time I would think (but maybe I'm wrong).

+
+bool Scheduler::executeIdleTasks(Deque<OwnPtr<TracedTask> >& idleTasks)
+{
+    TRACE_EVENT0("blink", "Scheduler::executeIdleTasks");
+    int idleTasksExecuted = 0;
+    while (!idleTasks.isEmpty() && getSecondsUntilFrameDeadline() > 0) {
+        idleTasks.takeFirst()->run();
+        idleTasksExecuted++;
+
+        // Give high priority a chance to preempt idle tasks.
+        runPendingHighPriorityTasksIfInCompositorPriority();
+    }
+
+    if (!idleTasks.isEmpty()) {
+        repostAllIdleTasks(idleTasks);
+    }
+    ASSERT(idleTasks.isEmpty());
+
+    return idleTasksExecuted > 0;
+}
+
+void Scheduler::repostAllIdleTasks(Deque<OwnPtr<TracedTask> >& idleTasks)
+{
+    Locker<Mutex> lock(m_pendingTasksMutex);
+    while (!idleTasks.isEmpty()) {
+        // TODO: Post at the front to avoid starvation?
+        m_pendingIdleTasks.append(idleTasks.takeFirst());
+    }
+}
+
 void Scheduler::sharedTimerAdapter()
 {
     shared()->tickSharedTimer();
 }
 
 void Scheduler::setSharedTimerFiredFunction(void (*function)())
 {
     m_sharedTimerFunction = function;
     blink::Platform::current()->setSharedTimerFiredFunction(function ? &Scheduler::sharedTimerAdapter : nullptr);
 }
@@ skipping 20 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::getSecondsUntilFrameDeadline() const
+{
+    double delta = m_currentFrameDeadlineSeconds - Platform::current()->monotonicallyIncreasingTime();
+    return (delta > 0) ? delta : 0;
+}
+

[picksi1, 2014/09/25 08:53:31]

Do we actually need the result in seconds? Is it worth making another function
deadlineHasPassed() that could be used more explicitly if we don't care about
the actual value?

Also, not sure if clamping the result to be non-negative is necessary... a -ve
result still could be useful (to some future developer) and it's one less line
of code.

[rmcilroy, 2014/09/29 17:42:57]

Reworked this so that we have canRunIdleTask() and currentFrameDeadline()
instead.  No clamping now since we never expose the remaining amount of allotted
time.

 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