HTTP/2: Race between PUSH_PROMISE and exclusive PRIORITY

Tom Bergan <tombergan@chromium.org> Thu, 15 September 2016 23:36 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 EC27512B0C2 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Thu, 15 Sep 2016 16:36:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.527
X-Spam-Level:
X-Spam-Status: No, score=-8.527 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, HTML_MESSAGE=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 (1024-bit key) header.d=chromium.org
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 11dTwvtjOSrC for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Thu, 15 Sep 2016 16:36:33 -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 1943312B0BC for <httpbisa-archive-bis2Juki@lists.ietf.org>; Thu, 15 Sep 2016 16:36:32 -0700 (PDT)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1bkg8Y-0003Vi-CX for ietf-http-wg-dist@listhub.w3.org; Thu, 15 Sep 2016 23:32:10 +0000
Resent-Date: Thu, 15 Sep 2016 23:32:10 +0000
Resent-Message-Id: <E1bkg8Y-0003Vi-CX@frink.w3.org>
Received: from lisa.w3.org ([128.30.52.41]) by frink.w3.org with esmtps (TLS1.2:DHE_RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <tombergan@chromium.org>) id 1bkg8R-0003UI-OV for ietf-http-wg@listhub.w3.org; Thu, 15 Sep 2016 23:32:03 +0000
Received: from mail-io0-f175.google.com ([209.85.223.175]) by lisa.w3.org with esmtps (TLS1.2:RSA_AES_128_CBC_SHA1:128) (Exim 4.80) (envelope-from <tombergan@chromium.org>) id 1bkg8P-0008Jk-W0 for ietf-http-wg@w3.org; Thu, 15 Sep 2016 23:32:03 +0000
Received: by mail-io0-f175.google.com with SMTP id q92so8325244ioi.1 for <ietf-http-wg@w3.org>; Thu, 15 Sep 2016 16:31:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=chromium.org; s=google; h=mime-version:from:date:message-id:subject:to; bh=caZsXF/BJKV52KGpmCjx04B0zkn4dYb+640CEbxnn2o=; b=dpHIKDkt5XnCpaqzIh9TuMEl///37hIRH+Q4N6qr0igXZhXBVn1blZgJo2vlqNlJSi wWo2IQhP/kMtjqYwd9RHJrd18zbXKiTzQiUEcVkNaHpakJwfnYtG86aYC1n7xGRqduj6 04/sqxcsBeYYC5W7YiOlwur4XbdD/cCTJtlEI=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=caZsXF/BJKV52KGpmCjx04B0zkn4dYb+640CEbxnn2o=; b=P50o/D2hwrTnpwHZ3wD2MnR/mTlNC0oJHcOPx49hwvWIa4bGX6FpZjyKYco6gQ7Gtj tbCrKaL1K/oUO5dcbo6KRf92hGmKBsj3xcBuAB1XqTovq1MLFkHMwbBtgTdymoG8dFbn EBa+RUF5Oo/P7xaf233fIBL82+KNC5+5FeFqwCLr53G4sSyUZNt1RZ9uhxf4NYKCcCzC mrMOyDZ5hDdKkEc9zsmmKASZLGyvDJrM5QSPbW5Xi56hh2mh7gFOHKfYEZlrTwV8gECt YrmkKSSpVQZ0frw75SysfWLUxBk14ju/Gtl2aRHg37D3jaf7NYHbL6/T0iEG5EmKtz87 Q7Pw==
X-Gm-Message-State: AE9vXwOkH+qryQJKMkhiPNJ++QdjX270S+Wf/sKPJ7F3gTRTBAXPkRGT+QaXopYITKbO3y7b
X-Received: by 10.107.26.210 with SMTP id a201mr20159868ioa.23.1473982294820; Thu, 15 Sep 2016 16:31:34 -0700 (PDT)
Received: from mail-io0-f176.google.com (mail-io0-f176.google.com. [209.85.223.176]) by smtp.gmail.com with ESMTPSA id e65sm2631484ioi.3.2016.09.15.16.31.33 for <ietf-http-wg@w3.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Thu, 15 Sep 2016 16:31:34 -0700 (PDT)
Received: by mail-io0-f176.google.com with SMTP id m79so8346710ioo.3 for <ietf-http-wg@w3.org>; Thu, 15 Sep 2016 16:31:33 -0700 (PDT)
X-Received: by 10.107.51.149 with SMTP id z143mr20021734ioz.190.1473982293393; Thu, 15 Sep 2016 16:31:33 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.107.48.136 with HTTP; Thu, 15 Sep 2016 16:31:32 -0700 (PDT)
From: Tom Bergan <tombergan@chromium.org>
Date: Thu, 15 Sep 2016 16:31:32 -0700
X-Gmail-Original-Message-ID: <CA+3+x5EG+PV-FEcy23xPU5iJgqh6u6aVRsTS-g=fQZnsMFTMHg@mail.gmail.com>
Message-ID: <CA+3+x5EG+PV-FEcy23xPU5iJgqh6u6aVRsTS-g=fQZnsMFTMHg@mail.gmail.com>
To: HTTP Working Group <ietf-http-wg@w3.org>
Content-Type: multipart/alternative; boundary=001a11441aa001184c053c943fe2
Received-SPF: pass client-ip=209.85.223.175; envelope-from=tombergan@chromium.org; helo=mail-io0-f175.google.com
X-W3C-Hub-Spam-Status: No, score=-5.2
X-W3C-Hub-Spam-Report: AWL=-1.010, BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=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: lisa.w3.org 1bkg8P-0008Jk-W0 b06d4e2f081718321276392fb87d6b50
X-Original-To: ietf-http-wg@w3.org
Subject: HTTP/2: Race between PUSH_PROMISE and exclusive PRIORITY
Archived-At: <http://www.w3.org/mid/CA+3+x5EG+PV-FEcy23xPU5iJgqh6u6aVRsTS-g=fQZnsMFTMHg@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/32407
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>

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