Implement idle task scheduling.

Source/platform/scheduler/Scheduler.cpp

Index: Source/platform/scheduler/Scheduler.cpp
diff --git a/Source/platform/scheduler/Scheduler.cpp b/Source/platform/scheduler/Scheduler.cpp
index c88c4203a6a7e3c9ad6a36fb3f400e6ea1a7bcc0..3ab073242f21fa3df6ea8073c2074a9ac0cb0adb 100644
--- a/Source/platform/scheduler/Scheduler.cpp
+++ b/Source/platform/scheduler/Scheduler.cpp
@@ -10,7 +10,9 @@
 #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 {
 
@@ -19,32 +21,6 @@ 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.
@@ -86,16 +62,19 @@ public:
     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()
@@ -118,6 +97,7 @@ 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)
@@ -133,30 +113,36 @@ Scheduler::~Scheduler()
 
 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()
 {
-    // TODO: Trigger the frame deadline immediately.
-}
+    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;
 
-void Scheduler::scheduleIdleTask(const TraceLocation& location, const IdleTask& idleTask)
-{
-    // TODO: send a real allottedTime here.
-    m_mainThread->postTask(new MainThreadIdleTaskAdapter(idleTask, 0, location));
+    // TODO: Trigger the frame deadline immediately.
 }
 
 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"));
@@ -184,6 +170,11 @@ void Scheduler::postIpcTask(const TraceLocation& location, const Task& task)
     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());
@@ -193,10 +184,6 @@ void Scheduler::maybePostMainThreadPendingHighPriorityTaskRunner()
     m_highPriorityTaskRunnerPosted = true;
 }
 
-void Scheduler::postIdleTask(const TraceLocation& location, const IdleTask& idleTask)
-{
-    scheduleIdleTask(location, idleTask);
-}
 
 void Scheduler::tickSharedTimer()
 {
@@ -228,7 +215,7 @@ bool Scheduler::swapQueuesAndRunPendingTasks()
     // 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);
@@ -241,7 +228,7 @@ void Scheduler::swapQueuesRunPendingTasksAndAllowHighPriorityTaskRunnerPosting()
     // 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();
@@ -258,12 +245,12 @@ void Scheduler::maybeEnterNormalSchedulerPolicy()
         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++;
     }
 
@@ -273,6 +260,47 @@ bool Scheduler::executeHighPriorityTasks(Deque<TracedTask>& highPriorityTasks)
     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();
@@ -313,6 +341,12 @@ bool Scheduler::hasPendingHighPriorityWork() const
     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());