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

Martin Thomson <martin.thomson@gmail.com> Fri, 16 September 2016 00:08 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 6F73112B098 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Thu, 15 Sep 2016 17:08:22 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.528
X-Spam-Level:
X-Spam-Status: No, score=-8.528 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.001, RP_MATCHES_RCVD=-1.508, 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 1jJ3JjfsyErg for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Thu, 15 Sep 2016 17:08:21 -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 EEBB712B09B for <httpbisa-archive-bis2Juki@lists.ietf.org>; Thu, 15 Sep 2016 17:08:20 -0700 (PDT)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1bkgdf-0000Yi-B3 for ietf-http-wg-dist@listhub.w3.org; Fri, 16 Sep 2016 00:04:19 +0000
Resent-Date: Fri, 16 Sep 2016 00:04:19 +0000
Resent-Message-Id: <E1bkgdf-0000Yi-B3@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 <martin.thomson@gmail.com>) id 1bkgdY-0000XB-Cv for ietf-http-wg@listhub.w3.org; Fri, 16 Sep 2016 00:04:12 +0000
Received: from mail-qk0-f180.google.com ([209.85.220.180]) by maggie.w3.org with esmtps (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <martin.thomson@gmail.com>) id 1bkgdT-0003lz-Pl for ietf-http-wg@w3.org; Fri, 16 Sep 2016 00:04:11 +0000
Received: by mail-qk0-f180.google.com with SMTP id h8so68673618qka.1 for <ietf-http-wg@w3.org>; Thu, 15 Sep 2016 17:03:47 -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=5J6CgFU7TBrOsUF+5oStnrKlXksum0yNAiiClSy0VK4=; b=KNGXfs6kKh11vLYCIjEWT1DW5RLBLPcqETn2F9NI/ffolsFizfGccUswfkDEmaxumE xyt86Z5y7+c8F7enTh6PsAOBpD1c1dGnqqvGS+qxgjFtu1pKKCQVVAsBOKGFyl/QgJZi YGlSseSHYjgNezvlTM/y4OdGg5JNJuvStNMt49AAoDSt9hdGX9O4dri1mQxq3O7vqgZu ruSupUt+1xqem5/D+ZyHB63uSJQbKNidPg9c6+FVl0aMM2diadl2iemRczLaVCtZD2fc nuJ0W1sATzqFiYJrYXYCpmCHmIG0NeLckhA0KxGzRxdrGDsn8n/I8j/BoSaIdQCuU1xe hPeQ==
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=5J6CgFU7TBrOsUF+5oStnrKlXksum0yNAiiClSy0VK4=; b=kG88y7iOVSLN6Cnu94GPCFfUFFX4zcnuZ3ilQA5lv0g6CHC2e1gg+kaW29qhWBNq6C YxoB6ULd9/xLVnmbTJf/6anefJ9Z5b8R3RoESAYMBdosgY+sr7MXSc2jtxUARU9sUOV3 SLh/F+70aDrjgR5cYewvWuh9NAerts25cp5moYKK360Y2QJGf3hW6qKAZcdEV238OA1d 4+WKFYXfKvKbwc9WKGBiNlg20FkoqQxv1QMeEWtQ+x7j/Y7O3j+WNeiyTdu3rqP0wE+D 2LXiMdoNWNPDqEV2m83Dc+hMfEo6qIiyLJeK7XDg55c26l13E6IBpYi9CQQnPPYjkH2e yEXg==
X-Gm-Message-State: AE9vXwPhcBgqTmdxI+hXtFeg4RDrW5o3R2LWn4RridRfOgYLBV2qx0w1CDz/ofWVOGXtKW9Z+p6qtK65OasRjQ==
X-Received: by 10.55.68.66 with SMTP id r63mr12555269qka.81.1473984221751; Thu, 15 Sep 2016 17:03:41 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.140.22.146 with HTTP; Thu, 15 Sep 2016 17:03:41 -0700 (PDT)
In-Reply-To: <CA+3+x5EG+PV-FEcy23xPU5iJgqh6u6aVRsTS-g=fQZnsMFTMHg@mail.gmail.com>
References: <CA+3+x5EG+PV-FEcy23xPU5iJgqh6u6aVRsTS-g=fQZnsMFTMHg@mail.gmail.com>
From: Martin Thomson <martin.thomson@gmail.com>
Date: Thu, 15 Sep 2016 17:03:41 -0700
Message-ID: <CABkgnnUVa-7KfidT6caEXQ-_WEMN-UHoBgBUC=MUDxzcB4RL=g@mail.gmail.com>
To: Tom Bergan <tombergan@chromium.org>
Cc: HTTP Working Group <ietf-http-wg@w3.org>
Content-Type: text/plain; charset=UTF-8
Received-SPF: pass client-ip=209.85.220.180; envelope-from=martin.thomson@gmail.com; helo=mail-qk0-f180.google.com
X-W3C-Hub-Spam-Status: No, score=-7.6
X-W3C-Hub-Spam-Report: AWL=1.582, 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_DB=-1, W3C_IRA=-1, W3C_IRR=-3, W3C_WL=-1
X-W3C-Scan-Sig: maggie.w3.org 1bkgdT-0003lz-Pl 545106122d41bfef6c831901ed260c0c
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/CABkgnnUVa-7KfidT6caEXQ-_WEMN-UHoBgBUC=MUDxzcB4RL=g@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/32408
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>

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