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

Kazuho Oku <kazuhooku@gmail.com> Tue, 20 September 2016 01:39 UTC

Return-Path: <ietf-http-wg-request+bounce-httpbisa-archive-bis2juki=lists.ie@listhub.w3.org>
X-Original-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Delivered-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9661912B17B for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Mon, 19 Sep 2016 18:39:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.837
X-Spam-Level:
X-Spam-Status: No, score=-8.837 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_DNSWL_HI=-5, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RCVD_IN_SORBS_SPAM=0.5, RP_MATCHES_RCVD=-2.316, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id rke98fNO2bjc for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Mon, 19 Sep 2016 18:39:13 -0700 (PDT)
Received: from frink.w3.org (frink.w3.org [128.30.52.56]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E2A8B12B171 for <httpbisa-archive-bis2Juki@lists.ietf.org>; Mon, 19 Sep 2016 18:39:12 -0700 (PDT)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1bm9xg-0006bi-IZ for ietf-http-wg-dist@listhub.w3.org; Tue, 20 Sep 2016 01:35:04 +0000
Resent-Date: Tue, 20 Sep 2016 01:35:04 +0000
Resent-Message-Id: <E1bm9xg-0006bi-IZ@frink.w3.org>
Received: from maggie.w3.org ([128.30.52.39]) by frink.w3.org with esmtps (TLS1.2:DHE_RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <kazuhooku@gmail.com>) id 1bm9xY-0005Cl-0X for ietf-http-wg@listhub.w3.org; Tue, 20 Sep 2016 01:34:56 +0000
Received: from mail-wm0-f51.google.com ([74.125.82.51]) by maggie.w3.org with esmtps (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <kazuhooku@gmail.com>) id 1bm9xS-0005Sq-OC for ietf-http-wg@w3.org; Tue, 20 Sep 2016 01:34:55 +0000
Received: by mail-wm0-f51.google.com with SMTP id b130so8459874wmc.0 for <ietf-http-wg@w3.org>; Mon, 19 Sep 2016 18:34:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=e3jp359yMIYcs72DW1Xj35mrSh4NBg0BlT39DsZLXT0=; b=e19YCMm5lbncQlM8KUHae8HmwdhH+MHz5limKlgphSkjqYpk3YrZt1VX3dBc14ovuz 4cSL4DcDP1jlfWjIdj1k3/dcIF5ojjWDuytJBakUo3iZTYvpxFQQbBhej3nxUA9+9S+6 iIkuhlJL2sjpA2eCSkZafcQTnIcMgafS+xgejRV8ysJfhvQ+05L8NXSaDFhBO3oQqjfc +Av+W57Bpsru8B02dnCw+hSpgJqzeEd+q3OvlSnJTl0Pv1McWswy2r3diSjMsUxUYzWL vQZ303yEgvc/MMK3tqECchMvzNv9pT2fqwuryzsMXeSBchFKlcoAys3NnxOb2jbqtVGG 0xpA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=e3jp359yMIYcs72DW1Xj35mrSh4NBg0BlT39DsZLXT0=; b=OrTsln4R9TieiBWN7LujmP+mraO0KxWP1ZCxkN0+ipMc1+/IQ5Q0Wb9i6+5e5175ET ug/570CpLL2FZZBYxAFP5d+7FR1rOBO2AfFRm0/9hjOlhaXq2+Vle64zyOiIu1dVvQEh c4r4eL0YDXxDPOnFdrUUjCVk1AuMKryar4QkBz6HFGwClOQm8VX8wgzl9keH0Sn1YXXD Fg3+eZe8UgcnJTS6Y96Hs6a00AziJS4ulXk0cooRElcQ3I51oZomVt2GEgX5Rf6B3A82 lOhuh96T8XpIgz//QPU7GxaHWdwY+lsZBI9xbpvuG5CIeMo2Sl8TvrTilN5omzA1PhYB oY0A==
X-Gm-Message-State: AE9vXwMWdZcCG1hPmP5NAxS9seUXMqa1WwW3KxXpIrJrK/GIjC0QKxJ6jorqt+xqtLobrd65W090BBEigl3lOQ==
X-Received: by 10.28.203.196 with SMTP id b187mr734152wmg.120.1474335264204; Mon, 19 Sep 2016 18:34:24 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.194.122.67 with HTTP; Mon, 19 Sep 2016 18:34:23 -0700 (PDT)
In-Reply-To: <CABkgnnUVa-7KfidT6caEXQ-_WEMN-UHoBgBUC=MUDxzcB4RL=g@mail.gmail.com>
References: <CA+3+x5EG+PV-FEcy23xPU5iJgqh6u6aVRsTS-g=fQZnsMFTMHg@mail.gmail.com> <CABkgnnUVa-7KfidT6caEXQ-_WEMN-UHoBgBUC=MUDxzcB4RL=g@mail.gmail.com>
From: Kazuho Oku <kazuhooku@gmail.com>
Date: Tue, 20 Sep 2016 10:34:23 +0900
Message-ID: <CANatvzwrCOt8oFeMcwo-B7kYYRhAw=J8ANNtuCSGrngF-zoK4Q@mail.gmail.com>
To: Martin Thomson <martin.thomson@gmail.com>
Cc: Tom Bergan <tombergan@chromium.org>, HTTP Working Group <ietf-http-wg@w3.org>
Content-Type: text/plain; charset=UTF-8
Received-SPF: pass client-ip=74.125.82.51; envelope-from=kazuhooku@gmail.com; helo=mail-wm0-f51.google.com
X-W3C-Hub-Spam-Status: No, score=-5.2
X-W3C-Hub-Spam-Report: AWL=-0.966, BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_SORBS_SPAM=0.5, SPF_PASS=-0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: maggie.w3.org 1bm9xS-0005Sq-OC d8aceff9ecc49500002957e08f6cf3bd
X-Original-To: ietf-http-wg@w3.org
Subject: Re: HTTP/2: Race between PUSH_PROMISE and exclusive PRIORITY
Archived-At: <http://www.w3.org/mid/CANatvzwrCOt8oFeMcwo-B7kYYRhAw=J8ANNtuCSGrngF-zoK4Q@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/32412
X-Loop: ietf-http-wg@w3.org
Resent-Sender: ietf-http-wg-request@w3.org
Precedence: list
List-Id: <ietf-http-wg.w3.org>
List-Help: <http://www.w3.org/Mail/>
List-Post: <mailto:ietf-http-wg@w3.org>
List-Unsubscribe: <mailto:ietf-http-wg-request@w3.org?subject=unsubscribe>

Hi,

2016-09-16 9:03 GMT+09:00 Martin Thomson <martin.thomson@gmail.com>om>:
> 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.

I would like to point out that having that kind of method would also
be beneficial for server-side performance.

RFC 7540 section 5.3.4 suggests:

   an endpoint SHOULD retain stream
   prioritization state for a period after streams become closed.  The
   longer state is retained, the lower the chance that streams are
   assigned incorrect or default priority values.

This suggestion is vague and is hard to implement. Ideally, server
needs to maintain the prioritization states of closed streams at least
for one RTT so that it would not receive PRIORITY frames from client
that is relative to the state of a closed stream. However, it is hard
to find out the correct RTT.

Therefore, a cautious server implementation would try to retain the
prioritization states of most-recently-used streams up to
MAX_CONCURRENT_STREAMS. By doing so, one can get rid of the risk to
receive a PRIORITY stream relative to the state of a closed stream,
since a client would never try to open more streams at once than
MAX_CONCURRENT_STREAMS.

However, trying to retain the prioritization states of streams as much
as MAX_CONCURRENT_STREAMS may become a performance bottleneck as you
try to more precisely distribute the bandwidth between the streams.

That said, there would be other ways than using a watermark to solve the issue.

For example, we could introduce frames for indicating the server that
the client has seen a stream getting open, or closed, or the priority
being changed.

For the push case, a client would send such frame as it receives
PUSH_PROMISE. Server can use the ordering between the such frames and
PRIORITY frame to find out the client's view of the prioritization
tree at the moment the client has sent the PRIORITY frame.

For the case described in this mail, a client would send such frame at
it sees a stream being closed. Server can use the frame to discard the
prioritization state of the closed streams.

> --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
>



-- 
Kazuho Oku