Re: HTTP/2: Race between PUSH_PROMISE and exclusive PRIORITY

Your fix would work.

An even simpler (but maybe more controversial) fix is to eliminate the
notion of exclusive dependencies entirely. Say the tree is A -> {X1...XN}
and the client requests B, where the client wants to promote B above all
Xn. With exclusive dependencies, we can do this in a single HEADERS frame.
Without exclusive dependencies, we can still accomplish this by sending A
-> B in the HEADERS, followed by a PRIORITY frame for each B -> Xn. The
second version is a problem only if: (a) N is large, or (b) we are worried
about a race where the server receives the HEADERS frame and starts sending
a response before receiving the following PRIORITY frames.

(a) is an empirical question. Do any H2 clients use exclusive dependencies
on trees with large fanout? I can only speak for Chrome, which does not do
this. Chrome's priority trees are mostly linear.

(b) is a possible race, but I'm not sure how much we should care. The
server's priority tree is "wrong" between receiving HEADERS and the Nth
PRIORITY. In practice, I expect this will be a very short time period
unless there happens to be a congestion window boundary in the middle, and
since PRIORITY frames are small, I expect that to be rare, but this is only
a hunch.

On Thu, Sep 15, 2016 at 5:03 PM, Martin Thomson <martin.thomson@gmail.com>
wrote:

> Hey Tom,
>
> This is a good bug.  I think that we built the exclusive thing without
> considering that possibility.  The problem is that there is no knowing
> what streams the sender of priority frame knew about when they send
> the PRIORITY frame.
>
> The same problem exists for PRIORITY sent by the server, but that's
> far less of a problem because we don't see anyone using that (or if
> they do, we don't agree on what that means).
>
> A simple "fix" here is to prohibit PRIORITY+exclusive from affecting
> streams that haven't been "mentioned" by the endpoint sending
> PRIORITY.  That is, each endpoint maintains a watermark (for both odd
> and even stream numbers) that increases every time they receive a
> frame from their peer and any stream number below that is assumed to
> be known to the other side.  That means tracking mentions though,
> which is a little cumbersome.
>
> --Martin
>
> On 15 September 2016 at 16:31, Tom Bergan <tombergan@chromium.org> wrote:
> > I believe the following example has a race:
> >
> > 1. Server receives request A.
> > 2. Server sends PUSH_PROMISE frames for B, C, D.
> > 3. Client sends PRIORITY to make B the exclusive parent of C
> > 4. Server receives that PRIORITY frame.
> >
> > After step 2, the server's local priority tree is A -> {B,C,D}, due to
> the
> > default priority rules in RFC 7540 Section 5.3.5. At step 4, the server
> > cannot know if the client has received the PUSH_PROMISE for D yet. This
> > makes it ambiguous whether the client intended the tree to be A -> B ->
> > {C,D} or A -> {B->C, D}. I believe this race can happen any time a
> > PUSH_PROMISE and exclusive PRIORITY can pass each other on the wire. I
> think
> > the race is impossible for non-exclusive PRIORITYs.
> >
> > This is the simplest example of the race, but it's admittedly strange
> that
> > the client would send that specific PRIORITY frame. Here's slightly more
> > complex, but less strange example:
> >
> > 1. Client requests A then B, where B's HEADERS frame makes A the
> exclusive
> > parent of B
> > 2. Server receives request A
> > 3. Server sends PUSH_PROMISE frames for C, D.
> > 4. Server receives request B
> > 5. Client receives PUSH_PROMISE frames for C, D
> >
> > At each step, the priority trees are updated like this:
> >
> > 1. Client's tree is A -> B
> > 2. Server's tree is A
> > 3. Server's tree is A -> {C,D}
> > 4. Server's tree is A -> B -> {C,D}
> > 5. Client's tree is A -> {B,C,D}
> >
> > If steps 3 and 4 are swapped, the client and server will finish with the
> > same priority tree. As-is, they finish with different priority trees.
> >
> > Does that sound right? If so, is this worth mentioning in some kind of
> > errata or other note? Apologies if this was brought up previously -- I
> > searched through the mailing list archives and did not see a mention.
> >
> > -Tom
>