Merge lp:~vanvugt/mir/ddouble into lp:mir

[Daniel van Vugt]

Introducing dynamic buffer queue scaling to minimize lag.
(LP: #1240909)

Actually the size of the queue doesn't really change with this branch.
What it does do is reliably detect when a client is staying ahead of
the compositor and throttle it so that no more than one future frame
is ever pre-rendered. Hence you get the same single-frame latency as
double buffering. But the moment the client fails to keep up, it will
get to use all three buffers again.

Background reading and imagery to help you understand the improvement:
https://docs.google.com/document/d/116i4TC0rls4wKFmbaRrHL_UT_Jg22XI8YqpXGLLTVCc/edit#

Fun facts:

* For manual testing you can see the switching in action if you set MIR_CLIENT_PERF_REPORT=log and then resize mir_demo_client_flicker to large enough that it takes too long to render (>16ms). It will get triple buffers then. If you shrink it, the client can render quickly again and reports double buffers.

* Strange and wonderful things happen with input resampling. Event-driven clients that use the default 59Hz resampling rate (e.g. mir_demo_client_eglsquare) will generally not be detected as "keeping up" and so will always be on triple buffers. But surprisingly this is a good thing -- the low input rate means the compositor is always consuming buffers faster than we're producing and you get lag around one frame as the consumer eats through the queue up to where the producer is (so the queue length is almost irrelevant). Other clients that reliably produce at full frame rate or higher however will get switched to double buffers (one frame lag).

* Additional manual testing has been done on a couple of phones (I backported this branch). Everything remains smooth. Unity8 is fast enough on some devices to qualify for double buffering. Unity8-dash is generally not fast enough on any device to qualify. You can see the stats on a live phone with:
    restart unity8 MIR_CLIENT_PERF_REPORT=log
    tail -f ~/.cache/upstart/unity8.log

* In raw numbers this branch at least reduces end-to-end lag on the phone from 5 frames to 4 (when unity8 qualifies for double buffering). And if your app (not unity8-dash) is fast enough to keep up too, it's then only 3 frames lag. So this branch reduces Unity8/USC total graphics latency by 20-40%, but more consistent results closer to 40% will depend on Unity8/dash performance improving in future. Also keep in mind on common mobile devices the touchscreen hardware itself may represent most of the latency. So even a 100% reduction in graphics latency could likely still feel slightly laggy to the user. And thus a 40% improvement is actually less than 40% of the total lag you perceive.

* A "slow" client that gets triple buffers is actually one that's achieving between 50% and 100% of the compositor frame rate. 100% or more is obviously fast and gets double buffers. Less obvious is that really slow clients doing less than 50% frame rate (e.g. a clock) actually keep the system idle enough that the third buffer doesn't get touched so you might see really slow clients only report 1 or 2 buffers in action even though we allow them 3.

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:2151
http://jenkins.qa.ubuntu.com/job/mir-ci/3731/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-vivid-i386-build/2331
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-vivid-amd64-build/2330
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-vivid-touch/2279
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1728
        deb: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1728/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2279
        deb: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2279/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-runner-mako/5172
    SUCCESS: http://s-jenkins.ubuntu-ci:8080/job/touch-flash-device/20217

Click here to trigger a rebuild:
http://s-jenkins.ubuntu-ci:8080/job/mir-ci/3731/rebuild

review: Approve (continuous-integration)

[Alberto Aguirre (albaguirre)]

I don't see a way of disabling the prediction.

review: Needs Fixing

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:2155
http://jenkins.qa.ubuntu.com/job/mir-ci/3768/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-vivid-i386-build/2385
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-vivid-amd64-build/2384
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-vivid-touch/2333
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1765
        deb: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1765/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2333
        deb: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2333/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-runner-mako/5215
    SUCCESS: http://s-jenkins.ubuntu-ci:8080/job/touch-flash-device/20305

Click here to trigger a rebuild:
http://s-jenkins.ubuntu-ci:8080/job/mir-ci/3768/rebuild

review: Approve (continuous-integration)

[Alan Griffiths (alan-griffiths)]

While descriptions of manual testing scenarios are interesting we all know that manual testing doesn't scale and we'll miss regressions.

Can we think of a way to automate any of this? Even if we need to define a new test category "test_needing_graphics_hardware"? (I know this problem existed before this MP but here's as good a place as any to discuss.)

It would be really nice to have something more than unit tests to prove the /system/ behavior is as intended, not just the buffer queue.

review: Needs Information

[Daniel van Vugt (vanvugt)]

The new tests cover the new functionality completely. And what you don't see in the diff is existing test `slow_client_framerate_matches_compositor' covering off any potential for performance regressions really well (it took quite some effort to make that test pass).

Of course more tests always help. But AFAIK we're at 100% functionality coverage here already so it shouldn't be a blocking issue. All pre-existing tests still pass too.

[Alan Griffiths (alan-griffiths)]

I agree that the new unit tests cover the new behavior of BufferQueue.

But I disagree that the proposed tests cover the new functionality of the system: there are no new tests of /the system as a whole/. The potential value of such tests is clear from the "Description of the Change" detailing how to /manually/ test the new functionality.

We should always be looking for ways to avoid relying on manual testing and this seems like an opportunity.

[Kevin DuBois (kdub)]

Seems like the idea can get a better latency/throughput balance, some questions...

Questions:
I can see some sort of policy (mc::BufferingPolicy?) being added to the constructor to try to keep the complexity of BufferQueue down, and make the policies interchangeable (also could providing a null/disabled policy to turn off dynamism)

190+ void set_scaling_delay(int nframes);
191+ int scaling_delay() const;
these are just here for for the benefit of the tests... is there a plan in the works so that something else in the system can change this?

249+ std::this_thread::sleep_for(throttled_compositor_rate);
Is this timing sensitive?

nits:
47+ else if (int(buffers.size()) < nbuffers)
c-cast

review: Needs Information

[Daniel van Vugt (vanvugt)]

set_scaling_delay was only just added to satisfy Alberto. I preferred not having that at all because in the absence of bugs (and none are known) it makes no sense to ever turn it off. That just allows people to shoot themselves in the proverbial foot, performance wise. Throughput is never compromised so it should always be turned on. Although it does help with a couple of tests that are invalid with queue scaling so would need to be deleted/disabled in the absence of set_scaling_delay.

The sleep_for was not my first preference. I toyed a lot with timerless tests but what I found was that they were nowhere near as effective at finding subtle bugs (when I intentionally introduced them) as the tests using real time. So I switched back to using real time because they're stronger tests more sensitive to subtle mistakes. Just as the existing `slow_client_framerate_matches_compositor' is so effective it continues to surprise me.

Yeah that cast is there for readability. If I said:
  int x = buffers.size();
  if (x < nbuffers)
then no one would complain. It's all the same and not something we should bother blocking on. The current form is more readable.

[Daniel van Vugt (vanvugt)]

Alan:
I only mentioned manual testing in the description because people should have some healthy suspicion of my claims and test for themselves. The suggestion to use manual testing is for healthy quality assurance and does not indicate any gap in the automated test coverage.

[Kevin DuBois (kdub)]

> Yeah that cast is there for readability. If I said:
> int x = buffers.size();
> if (x < nbuffers)
> then no one would complain. It's all the same and not something we should
> bother blocking on. The current form is more readable.

Just trying to stick to the style guide :)
http://unity.ubuntu.com/mir/cppguide/index.html?showone=Casting#Casting
We've been chatting about some of the style guide stuff in the EU/US standup (and probably at the sprint next week too), maybe just another point of the style guide to bring up

[Kevin DuBois (kdub)]

> The sleep_for was not my first preference. I toyed a lot with timerless tests
> but what I found was that they were nowhere near as effective at finding
> subtle bugs (when I intentionally introduced them) as the tests using real
> time. So I switched back to using real time because they're stronger tests
> more sensitive to subtle mistakes. Just as the existing
> `slow_client_framerate_matches_compositor' is so effective it continues to
> surprise me.

So, obviously the worst thing possible is to have a bug or regression, so a strong test is good. Another bad thing though is to have tests break under loaded CI, or to have the tests take a long time to run.

The test seems robust enough, but just leery of timing tests from past bugs.
The unit test time increases significantly with these tests. At least on my system, the old BufferQueueTests take 3-4s to run, but the new tests increase that time to about 12-13s. (log of run: http://pastebin.ubuntu.com/11100093/). Is there a way to decrease the test time while still having bugs guarded against? Its difficult to know where to draw the line as to how long a test can take to run, but this seems like an increase in test run time that should be avoided if at all possible.

[Kevin DuBois (kdub)]

> set_scaling_delay was only just added to satisfy Alberto. I preferred not
> having that at all because in the absence of bugs (and none are known) it
> makes no sense to ever turn it off. That just allows people to shoot
> themselves in the proverbial foot, performance wise. Throughput is never
> compromised so it should always be turned on. Although it does help with a
> couple of tests that are invalid with queue scaling so would need to be
> deleted/disabled in the absence of set_scaling_delay.

Side-stepping the argument of if it should be disabled or configurable a bit [1], the current code does have disable/configure abilities. So, it makes more sense to have this be a policy interface (or even an int parameter) passed in via the BufferQueue constructor than it does to have dangling functions that we don't intend to use in production code.

[1] I buy that its more of a nice-to-have (and easy-to-have) than something we're planning on making use of often.

[Daniel van Vugt (vanvugt)]

Indeed I think I can shorten the new tests more and maintain robustness... They're not "time sensitive" like other tests though. The only timing I introduce is the sleep in throttled_compositor_thread() to ensure that the client loop (which is not throttled at all) runs faster than the compositor. That holds true even under load on a slow system so no false positives are expected (but the probability is never quite zero).

As for a "policy" interface. It's possible but would be messy, requiring more code (more classes) and end up less readable than "q.scaling_delay()" is right now. So I'd rather not.

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:2159
http://jenkins.qa.ubuntu.com/job/mir-ci/3820/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-vivid-i386-build/2461
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-vivid-amd64-build/2460
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-vivid-touch/2409
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1817
        deb: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1817/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2409
        deb: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2409/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-runner-mako/5288
    SUCCESS: http://s-jenkins.ubuntu-ci:8080/job/touch-flash-device/20447

Click here to trigger a rebuild:
http://s-jenkins.ubuntu-ci:8080/job/mir-ci/3820/rebuild

review: Approve (continuous-integration)

[Alan Griffiths (alan-griffiths)]

I'll leave it to those with stronger opinions

review: Abstain

[Alberto Aguirre (albaguirre)]

"set_scaling_delay was only just added to satisfy Alberto. "

It shouldn't just be me. ANY predictive algorithm will get wrong predictions. And I would prefer something less cryptic than setting -1 on set_scaling_delay. Just a enable_dynamic_depth or something like that should suffice.

47 + else if (int(buffers.size()) < nbuffers)

C-cast... No c-casts per mir style guide.

> As for a "policy" interface. It's possible but would be messy, requiring more
> code (more classes) and end up less readable than "q.scaling_delay()" is right
> now. So I'd rather not.

As oppossed to the complex web of logic introduced in BufferQueue? The algorithm is not clear (which is one benefit of an interface with clear boundaries).

Also it's not obvious what the trade-offs are in this scheme.

Needs fixing, needs info.

review: Needs Fixing

[Kevin DuBois (kdub)]

@test shortening, thanks!

> As for a "policy" interface. It's possible but would be messy, requiring more
> code (more classes) and end up less readable than "q.scaling_delay()" is right
> now. So I'd rather not.

Sure, it requires some interfaces, but the expressiveness of the code improves by not having to figure out what a 'scaling delay' is. As the code stands now, we have to bake the policies and the swapping all into on BufferQueue object, which has always been pretty complex with just the swapping requirements. It also diffuses the BufferQueue logic a bit, because we have a dividing line that 'this is the size/scaling/queing policy' and 'this is the swapping queue'.

Like Alberto points out, this is something that can be optimized for in different ways, and I can see that using differing policies could be helpful. Having to define the interfaces and relationships between the BufferQueue and the policy-interface would stop the BufferQueue from mixing up the policy portion with the swapping portion, and hopefully lead to a a more flexible system.

So, I guess 'needs-fixing' on the c-cast, and 'appreciates-further-discussion' on the interface (its seeming like a good vs better situation)

[Daniel van Vugt (vanvugt)]

I glad people are suspicious. You should be since we've been trying to achieve this for over a year.

Although please be wary of "rearranging deck chairs on the titanic". Requests to change designs that contribute nothing functional and result in more complex code will be accommodated to some extent to avoid argument, but quickly become a waste of time. Try not to be Vogons...

[Daniel van Vugt (vanvugt)]

C cast:
Now removed. Not my preferred syntax but the hit to readability is minor.

What's the trade-off?
Although none has been observed this this current implementation (I never put it up for review until I believed all the corner cases had been solved), in theory there is a trade-off. That is for clients who are on the bleeding edge of keeping up most-of-but-not-quite-all the time. A client keeping up for 80% of frames and only missing every 5th for example would get scaled back to two buffers for 60% of the time, and would get three buffers for the 40% of the time. Depending on the specific client's behaviour, this could result in it keeping up only 60% of the time with this algorithm, instead of 80% of the time with always-triple-buffers.
  But this whole branch is an exercise in working around sub-optimal clients (most notably unity8-dash). I have worked for months on and off to ensure those edge cases we actually see in Ubuntu where our clients are too slow are correctly handled by this algorithm. But in the long run we should of course aim to make all our graphics code fast (so double buffering can be used). It's not hard; just requires some commitment.
  The current algorithm presented here has no visible stuttering on our phones, and provides a slightly visible reduction in lag.

Redesign with a policy object:
I'll make a proposal or two separately into this branch so you can see the changes more clearly...

[PS Jenkins bot (ps-jenkins)]

PASSED: Continuous integration, rev:2161
http://jenkins.qa.ubuntu.com/job/mir-ci/3833/
Executed test runs:
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-android-vivid-i386-build/2477
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-clang-vivid-amd64-build/2476
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-vivid-touch/2425
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1830
        deb: http://jenkins.qa.ubuntu.com/job/mir-vivid-amd64-ci/1830/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2425
        deb: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-builder-vivid-armhf/2425/artifact/work/output/*zip*/output.zip
    SUCCESS: http://jenkins.qa.ubuntu.com/job/mir-mediumtests-runner-mako/5301
    SUCCESS: http://s-jenkins.ubuntu-ci:8080/job/touch-flash-device/20486

Click here to trigger a rebuild:
http://s-jenkins.ubuntu-ci:8080/job/mir-ci/3833/rebuild

review: Approve (continuous-integration)

[Daniel van Vugt (vanvugt)]

Correction:
A client keeping up for 80% of frames and only missing every 5th for example would get scaled back to two buffers for 20% of the time (on the fourth frame), and would get three buffers for the other 80% of the time. Depending on the specific client's behaviour, this could result in it keeping up only 60% of the time with this algorithm, instead of 80% of the time with always-triple-buffers.

[Kevin DuBois (kdub)]

@the policy discussion,
Its more of a request to define the relationships between the objects and allow for object-oriented substitution of the algorithm. I suppose this can be done later, but (imo) would help us review better if we teased out what policy decisions are being made, and what is being optimized for in the tradeoffs. This seems like something to sort out next week, abstain for now.

review: Abstain

[Daniel van Vugt (vanvugt)]

I will do it, but might not be ready till next week.

[Alberto Aguirre (albaguirre)]

@Daniel, thanks for the info.

Abstain for now until we have the buffer semantics discussion.

review: Abstain

[Daniel van Vugt (vanvugt)]

Talking about redesigning the buffer allocation architecture today, I won't bother redesigning this proposal for now. Sounds like the effort might go to waste within some months.

[Daniel van Vugt (vanvugt)]

Ignore my most recent comments above.

Last week people were saying they'd be happy to land this as-is. Still true?

[Daniel van Vugt (vanvugt)]

This branch is important and we need to not drop the ball. Unity8 needs every reduction in latency we can get, released as soon as possible.

If anyone truly wants it redesigned, please tell me ASAP.

[Kevin DuBois (kdub)]

I guess still (if I can introduce a new branch of arithmetic to expand on the nuances):

+1 that using some sort of heuristic to dynamically trade off between "double buffering" and "triple buffering" is beneficial.

-1 that the heuristic is not easily extractable from BufferQueue.

+? that it improves some situtations, as described in the description, but its difficult to see that we're making a good universal tradeoff.

+? On how to prove that this new feature has transferred to 'the new buffer semantics'. If its something in trunk, we don't want to remove the feature with 'the new buffer semantics'; but it will look markedly different once we have server-initiated buffer transfers. Its difficult to see how to transfer the feature because we don't have an established way to test a variety of loads and pop a hard number out at the end to compare.

so I guess all that adds up to "0??", which (I suppose) translates to abstain.

[Daniel van Vugt (vanvugt)]

This branch is visibly beneficial. When used on the phone you can see shell elements are least are a bit more responsive.

And the heuristic is mostly not a heuristic. It's based on careful logic and reasoning which is why it took me over 6 months to bring this version to reality, now 12 months after we first started trying to get back to double buffering.

I don't care to think about new buffer semantics right now. Future work may replace it, but this branch works today and solves 40% of the lag. So let's take advantage of it.

[Alexandros Frantzis (afrantzis)]

As with most additions to BufferQueue, it's not easy to convince oneself that this is bug free. However, it seems to work well in practice, and if we are going to have it, let's introduce it early in the cycle.

My main concern is that this branch would be largely irrelevant after the planned move to client-owned buffers (although we could provide a helper library that implements similar logic on the client side). However, we are not there yet, and since changing our buffer semantics is a long-term effort, I am OK "living for today" in this case.

There are a few things to improve (in the future):

As mentioned in previous comments, I would very much like to see tests that simulate our manual tests, i.e., they check the effects that buffer queue changes have end-to-end.

This branch optimizes latency, but leaves memory consumption intact (i.e. we mantain 3 buffers internally even if we don't need them). It would be nice to see memory consumption addressed too.

review: Approve

[Cemil Azizoglu (cemil-azizoglu)]

There is some healthy skepticism but no strong objections. I'm willing to try this out.

review: Approve

=== modified file 'src/server/compositor/buffer_queue.cpp'
--- src/server/compositor/buffer_queue.cpp	2015-05-01 08:54:27 +0000
+++ src/server/compositor/buffer_queue.cpp	2015-05-14 06:01:15 +0000
@@ -137,6 +137,8 @@
     graphics::BufferProperties const& props,
     mc::FrameDroppingPolicyFactory const& policy_provider)
     : nbuffers{nbuffers},
+      frame_deadlines_threshold{3},
+      frame_deadlines_met{0},
       frame_dropping_enabled{false},
       current_compositor_buffer_valid{false},
       the_properties{props},
@@ -168,30 +170,63 @@
         std::make_shared<BufferQueue::LockableCallback>(this));
 }
 
+void mc::BufferQueue::set_scaling_delay(int nframes)
+{
+    std::unique_lock<decltype(guard)> lock(guard);
+    frame_deadlines_threshold = nframes;
+}
+
+int mc::BufferQueue::scaling_delay() const
+{
+    std::unique_lock<decltype(guard)> lock(guard);
+    return frame_deadlines_threshold;
+}
+
+bool mc::BufferQueue::client_ahead_of_compositor() const
+{
+    return nbuffers > 1 &&
+           !frame_dropping_enabled &&  // Never throttle frame droppers
+           frame_deadlines_threshold >= 0 &&  // Queue scaling enabled
+           !ready_to_composite_queue.empty() &&  // At least one frame is ready
+           frame_deadlines_met >= frame_deadlines_threshold;  // Is smooth
+}
+
+mg::Buffer* mc::BufferQueue::get_a_free_buffer()
+{
+    mg::Buffer* buf = nullptr;
+
+    if (!free_buffers.empty())
+    {
+        buf = free_buffers.back();
+        free_buffers.pop_back();
+    }
+    else if (static_cast<int>(buffers.size()) < nbuffers)
+    {
+        auto const& buffer = gralloc->alloc_buffer(the_properties);
+        buffers.push_back(buffer);
+        buf = buffer.get();
+    }
+
+    return buf;
+}
+
 void mc::BufferQueue::client_acquire(mc::BufferQueue::Callback complete)
 {
     std::unique_lock<decltype(guard)> lock(guard);
 
     pending_client_notifications.push_back(std::move(complete));
 
-    if (!free_buffers.empty())
-    {
-        auto const buffer = free_buffers.back();
-        free_buffers.pop_back();
-        give_buffer_to_client(buffer, lock);
-        return;
-    }
-
-    /* No empty buffers, attempt allocating more
-     * TODO: need a good heuristic to switch
-     * between double-buffering to n-buffering
+    /*
+     * Fast clients that can be safely throttled should be. This keeps the
+     * number of prefilled buffers limited to one (equivalent to double-
+     * buffering) for minimal latency.
      */
-    int const allocated_buffers = buffers.size();
-    if (allocated_buffers < nbuffers)
+    if (client_ahead_of_compositor())
+        return;
+
+    if (auto buf = get_a_free_buffer())
     {
-        auto const& buffer = gralloc->alloc_buffer(the_properties);
-        buffers.push_back(buffer);
-        give_buffer_to_client(buffer.get(), lock);
+        give_buffer_to_client(buf, lock);
         return;
     }
 
@@ -235,7 +270,14 @@
     std::unique_lock<decltype(guard)> lock(guard);
 
     bool use_current_buffer = false;
-    if (!is_a_current_buffer_user(user_id))
+    if (is_a_current_buffer_user(user_id))   // Primary/fastest display
+    {
+        if (ready_to_composite_queue.empty())
+            frame_deadlines_met = 0;
+        else if (frame_deadlines_met < frame_deadlines_threshold)
+            ++frame_deadlines_met;
+    }
+    else   // Second and subsequent displays sync to the primary one
     {
         use_current_buffer = true;
         current_buffer_users.push_back(user_id);
@@ -267,6 +309,15 @@
         current_buffer_users.push_back(user_id);
         current_compositor_buffer = pop(ready_to_composite_queue);
         current_compositor_buffer_valid = true;
+
+        /*
+         * If we just emptied the ready queue above and hold this compositor
+         * buffer for very long (e.g. bypass) then there's a chance the client
+         * would starve and miss a frame. Make sure that can't happen, by
+         * using more than double buffers...
+         */
+        if (!buffer_to_release && !client_ahead_of_compositor())
+            buffer_to_release = get_a_free_buffer();
     }
     else if (current_buffer_users.empty())
     {   // current_buffer_users and ready_to_composite_queue both empty
@@ -375,14 +426,40 @@
         ++count;
     }
 
+    /*
+     * Intentionally schedule one more frame than we need, and for good
+     * reason... We can only accurately detect frame_deadlines_met in
+     * compositor_acquire if compositor_acquire is still waking up at full
+     * frame rate even with a slow client. This is crucial to scaling the
+     * queue performance dynamically in "client_ahead_of_compositor".
+     *   But don't be concerned; very little is lost by over-scheduling. Under
+     * normal smooth rendering conditions all frames are used (not wasted).
+     * And under sluggish client rendering conditions the extra frame has a
+     * critical role in providing a sample point in which we detect if the
+     * client is keeping up. Only when the compositor changes from active to
+     * idle is the extra frame wasted. Sounds like a reasonable price to pay
+     * for dynamic performance monitoring.
+     */
+    if (count && frame_deadlines_threshold >= 0)
+        ++count;
+
     return count;
 }
 
+/*
+ * This function is a kludge used in tests only. It attempts to predict how
+ * many calls to client_acquire you can make before it blocks.
+ * Future tests should not use it.
+ */
 int mc::BufferQueue::buffers_free_for_client() const
 {
     std::lock_guard<decltype(guard)> lock(guard);
     int ret = 1;
-    if (nbuffers > 1)
+    if (nbuffers == 1)
+        ret = 1;
+    else if (client_ahead_of_compositor())  // client_acquire will block
+        ret = 0;
+    else
     {
         int nfree = free_buffers.size();
         int future_growth = nbuffers - buffers.size();
@@ -456,7 +533,7 @@
     mg::Buffer* buffer,
     std::unique_lock<std::mutex> lock)
 {
-    if (!pending_client_notifications.empty())
+    if (!pending_client_notifications.empty() && !client_ahead_of_compositor())
     {
         framedrop_policy->swap_unblocked();
         give_buffer_to_client(buffer, lock);
 
=== modified file 'src/server/compositor/buffer_queue.h'
--- src/server/compositor/buffer_queue.h	2015-04-30 11:36:36 +0000
+++ src/server/compositor/buffer_queue.h	2015-05-14 06:01:15 +0000
@@ -65,6 +65,15 @@
     void drop_old_buffers() override;
     void drop_client_requests() override;
 
+    /**
+     * Set the minimum number of smooth frames the client must keep up with
+     * the compositor for in order to qualify for queue scaling (dynamic
+     * double buffering for reduced latency). A negative value means never
+     * but it's recommended that you never change this.
+     */
+    void set_scaling_delay(int nframes);
+    int scaling_delay() const;
+
 private:
     class LockableCallback;
     enum SnapshotWait
@@ -94,7 +103,12 @@
 
     std::deque<Callback> pending_client_notifications;
 
+    bool client_ahead_of_compositor() const;
+    graphics::Buffer* get_a_free_buffer();
+
     int nbuffers;
+    int frame_deadlines_threshold;
+    int frame_deadlines_met;
     bool frame_dropping_enabled;
     bool current_compositor_buffer_valid;
     graphics::BufferProperties the_properties;
 
=== modified file 'tests/unit-tests/compositor/test_buffer_queue.cpp'
--- tests/unit-tests/compositor/test_buffer_queue.cpp	2015-04-30 11:36:36 +0000
+++ tests/unit-tests/compositor/test_buffer_queue.cpp	2015-05-14 06:01:15 +0000
@@ -151,7 +151,8 @@
     return handle->buffer();
 }
 
-void compositor_thread(mc::BufferQueue &bundle, std::atomic<bool> &done)
+void unthrottled_compositor_thread(mc::BufferQueue &bundle,
+                                   std::atomic<bool> &done)
 {
    while (!done)
    {
@@ -160,6 +161,36 @@
    }
 }
 
+std::chrono::milliseconds const throttled_compositor_rate(10);
+void throttled_compositor_thread(mc::BufferQueue &bundle,
+                                 std::atomic<bool> &done)
+{
+   while (!done)
+   {
+       bundle.compositor_release(bundle.compositor_acquire(nullptr));
+       std::this_thread::sleep_for(throttled_compositor_rate);
+   }
+}
+
+void overlapping_compositor_thread(mc::BufferQueue &bundle,
+                                   std::atomic<bool> &done)
+{
+   std::shared_ptr<mg::Buffer> b[2];
+   int i = 0;
+
+   b[0] = bundle.compositor_acquire(nullptr);
+   while (!done)
+   {
+       b[i^1] = bundle.compositor_acquire(nullptr);
+       bundle.compositor_release(b[i]);
+       std::this_thread::sleep_for(throttled_compositor_rate);
+       i ^= 1;
+   }
+
+   if (b[i])
+       bundle.compositor_release(b[i]);
+}
+
 void snapshot_thread(mc::BufferQueue &bundle,
                       std::atomic<bool> &done)
 {
@@ -420,10 +451,13 @@
     {
         mc::BufferQueue q(nbuffers, allocator, basic_properties, policy_factory);
 
+        // This test is technically not valid with dynamic queue scaling on
+        q.set_scaling_delay(-1);
+
         std::atomic<bool> done(false);
         auto unblock = [&done] { done = true; };
         mt::AutoUnblockThread compositor(unblock,
-            compositor_thread, std::ref(q), std::ref(done));
+            unthrottled_compositor_thread, std::ref(q), std::ref(done));
 
         std::unordered_set<uint32_t> ids_acquired;
         int const max_ownable_buffers = nbuffers - 1;
@@ -537,8 +571,7 @@
         {
             std::deque<mg::BufferID> client_release_sequence;
             std::vector<mg::Buffer *> buffers;
-            int const max_ownable_buffers = nbuffers - 1;
-            for (int i = 0; i < max_ownable_buffers; ++i)
+            for (int i = 0; i < q.buffers_free_for_client(); ++i)
             {
                 auto handle = client_acquire_async(q);
                 ASSERT_THAT(handle->has_acquired_buffer(), Eq(true));
@@ -804,7 +837,7 @@
 
         auto unblock = [&done]{ done = true;};
 
-        mt::AutoUnblockThread compositor(unblock, compositor_thread,
+        mt::AutoUnblockThread compositor(unblock, unthrottled_compositor_thread,
                                          std::ref(q),
                                          std::ref(done));
         mt::AutoUnblockThread snapshotter1(unblock, snapshot_thread,
@@ -1393,8 +1426,14 @@
         // Consume
         for (int m = 0; m < nmonitors; ++m)
         {
-            ASSERT_EQ(1, q.buffers_ready_for_compositor(&monitor[m]));
-            q.compositor_release(q.compositor_acquire(&monitor[m]));
+            ASSERT_NE(0, q.buffers_ready_for_compositor(&monitor[m]));
+
+            // Double consume to account for the +1 that
+            // buffers_ready_for_compositor adds to do dynamic performance
+            // detection.
+            q.compositor_release(q.compositor_acquire(&monitor[m]));
+            q.compositor_release(q.compositor_acquire(&monitor[m]));
+
             ASSERT_EQ(0, q.buffers_ready_for_compositor(&monitor[m]));
         }
     }
@@ -1466,7 +1505,7 @@
         std::atomic<bool> done(false);
 
         auto unblock = [&done]{ done = true; };
-        mt::AutoUnblockThread compositor_thread(unblock, [&]
+        mt::AutoUnblockThread unthrottled_compositor_thread(unblock, [&]
         {
             while (!done)
             {
@@ -1552,6 +1591,9 @@
     {
         mc::BufferQueue q(nbuffers, allocator, basic_properties, policy_factory);
 
+        // This test is technically not valid with dynamic queue scaling on
+        q.set_scaling_delay(-1);
+
         void const* main_compositor = reinterpret_cast<void const*>(0);
         void const* second_compositor = reinterpret_cast<void const*>(1);
 
@@ -1579,7 +1621,7 @@
         std::atomic<bool> done(false);
         auto unblock = [&done] { done = true; };
         mt::AutoUnblockThread compositor(unblock,
-           compositor_thread, std::ref(q), std::ref(done));
+           unthrottled_compositor_thread, std::ref(q), std::ref(done));
 
         std::unordered_set<mg::Buffer *> unique_buffers_acquired;
         int const max_ownable_buffers = nbuffers - 1;
@@ -1606,32 +1648,131 @@
     }
 }
 
-/* FIXME (enabling this optimization breaks timing tests) */
-TEST_F(BufferQueueTest, DISABLED_synchronous_clients_only_get_two_real_buffers)
+// Test that dynamic queue scaling/throttling actually works
+TEST_F(BufferQueueTest, queue_size_scales_with_client_performance)
+{
+    for (int nbuffers = 3; nbuffers <= max_nbuffers_to_test; ++nbuffers)
+    {
+        mc::BufferQueue q(nbuffers, allocator, basic_properties, policy_factory);
+        q.allow_framedropping(false);
+
+        std::atomic<bool> done(false);
+        auto unblock = [&done] { done = true; };
+
+        // To emulate a "fast" client we use a "slow" compositor
+        mt::AutoUnblockThread compositor(unblock,
+           throttled_compositor_thread, std::ref(q), std::ref(done));
+
+        std::unordered_set<mg::Buffer *> buffers_acquired;
+
+        int const delay = q.scaling_delay();
+        EXPECT_EQ(3, delay);  // expect a sane default
+
+        for (int frame = 0; frame < 10; frame++)
+        {
+            auto handle = client_acquire_async(q);
+            handle->wait_for(std::chrono::seconds(1));
+            ASSERT_THAT(handle->has_acquired_buffer(), Eq(true));
+
+            if (frame > delay)
+                buffers_acquired.insert(handle->buffer());
+            handle->release_buffer();
+        }
+        // Expect double-buffers for fast clients
+        EXPECT_THAT(buffers_acquired.size(), Eq(2));
+
+        // Now check what happens if the client becomes slow...
+        buffers_acquired.clear();
+        for (int frame = 0; frame < 10; frame++)
+        {
+            auto handle = client_acquire_async(q);
+            handle->wait_for(std::chrono::seconds(1));
+            ASSERT_THAT(handle->has_acquired_buffer(), Eq(true));
+
+            if (frame > delay)
+                buffers_acquired.insert(handle->buffer());
+
+            // Client is just too slow to keep up:
+            std::this_thread::sleep_for(throttled_compositor_rate * 1.5);
+
+            handle->release_buffer();
+        }
+        // Expect at least triple buffers for sluggish clients
+        EXPECT_THAT(buffers_acquired.size(), Ge(3));
+
+        // And what happens if the client becomes fast again?...
+        buffers_acquired.clear();
+        for (int frame = 0; frame < 10; frame++)
+        {
+            auto handle = client_acquire_async(q);
+            handle->wait_for(std::chrono::seconds(1));
+            ASSERT_THAT(handle->has_acquired_buffer(), Eq(true));
+
+            if (frame > delay)
+                buffers_acquired.insert(handle->buffer());
+            handle->release_buffer();
+        }
+        // Expect double-buffers for fast clients
+        EXPECT_THAT(buffers_acquired.size(), Eq(2));
+    }
+}
+
+TEST_F(BufferQueueTest, greedy_compositors_need_triple_buffers)
+{
+    /*
+     * "Greedy" compositors means those that can hold multiple buffers from
+     * the same client simultaneously or a single buffer for a long time.
+     * This usually means bypass/overlays, but can also mean multi-monitor.
+     */
+    for (int nbuffers = 3; nbuffers <= max_nbuffers_to_test; ++nbuffers)
+    {
+        mc::BufferQueue q(nbuffers, allocator, basic_properties, policy_factory);
+        q.allow_framedropping(false);
+
+        std::atomic<bool> done(false);
+        auto unblock = [&done] { done = true; };
+
+        mt::AutoUnblockThread compositor(unblock,
+           overlapping_compositor_thread, std::ref(q), std::ref(done));
+
+        std::unordered_set<mg::Buffer *> buffers_acquired;
+        int const delay = q.scaling_delay();
+
+        for (int frame = 0; frame < 10; frame++)
+        {
+            auto handle = client_acquire_async(q);
+            handle->wait_for(std::chrono::seconds(1));
+            ASSERT_THAT(handle->has_acquired_buffer(), Eq(true));
+
+            if (frame > delay)
+                buffers_acquired.insert(handle->buffer());
+            handle->release_buffer();
+        }
+        // Expect triple buffers for the whole time
+        EXPECT_THAT(buffers_acquired.size(), Ge(3));
+    }
+}
+
+TEST_F(BufferQueueTest, compositor_double_rate_of_slow_client)
 {
     for (int nbuffers = 2; nbuffers <= max_nbuffers_to_test; ++nbuffers)
     {
         mc::BufferQueue q(nbuffers, allocator, basic_properties, policy_factory);
         q.allow_framedropping(false);
 
-        std::atomic<bool> done(false);
-        auto unblock = [&done] { done = true; };
-        mt::AutoUnblockThread compositor(unblock,
-           compositor_thread, std::ref(q), std::ref(done));
-
-        std::unordered_set<mg::Buffer *> buffers_acquired;
-
-        for (int frame = 0; frame < 100; frame++)
+        for (int frame = 0; frame < 10; frame++)
         {
-            auto handle = client_acquire_async(q);
-            handle->wait_for(std::chrono::seconds(1));
-            ASSERT_THAT(handle->has_acquired_buffer(), Eq(true));
+            ASSERT_EQ(0, q.buffers_ready_for_compositor(this));
+            q.client_release(client_acquire_sync(q));
 
-            buffers_acquired.insert(handle->buffer());
-            handle->release_buffer();
+            // Detecting a slow client requires scheduling at least one extra
+            // frame...
+            int nready = q.buffers_ready_for_compositor(this);
+            ASSERT_EQ(2, nready);
+            for (int i = 0; i < nready; ++i)
+                q.compositor_release(q.compositor_acquire(this));
+            ASSERT_EQ(0, q.buffers_ready_for_compositor(this));
         }
-
-        EXPECT_THAT(buffers_acquired.size(), Eq(2));
     }
 }