Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time

Neal Cardwell <ncardwell@google.com> Sun, 21 August 2016 19:45 UTC

Return-Path: <ncardwell@google.com>
X-Original-To: tcpm@ietfa.amsl.com
Delivered-To: tcpm@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7053C12D811 for <tcpm@ietfa.amsl.com>; Sun, 21 Aug 2016 12:45:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.249
X-Spam-Level:
X-Spam-Status: No, score=-3.249 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RP_MATCHES_RCVD=-0.548, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.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 M8erlPcln7MG for <tcpm@ietfa.amsl.com>; Sun, 21 Aug 2016 12:45:26 -0700 (PDT)
Received: from mail-oi0-x233.google.com (mail-oi0-x233.google.com [IPv6:2607:f8b0:4003:c06::233]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 10A7012D80E for <tcpm@ietf.org>; Sun, 21 Aug 2016 12:45:26 -0700 (PDT)
Received: by mail-oi0-x233.google.com with SMTP id c15so126133305oig.0 for <tcpm@ietf.org>; Sun, 21 Aug 2016 12:45:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=7mMdzEvAXatHRonBcTLg6/Z1j4kgE92mV74Ax1sefdI=; b=ZKNdn5+iTwpPHhOeUb8KtJbmPKVW0JJOGlVY7ZUg4Mm6whL7O5gamJxh9bxzRotI1J TyeuXvM9AL0BWi77QLk9G71kF1H6kcJAdmBAcqllksir46SshudAiouJKj/Bbce2pvnF BDmJr0mQm1mSrQwjGkdjAo3/MyXMykn5pniI3C+T0zjxCKJButvdAukRgSU6LKfrvRtm nL/D8nV+dEnTOoFXGBMTR+afvws3/lszjJbBivkkBJCOOLeOXYe7gPvEA/LWo9EIsfZs Aa2y5YvnEFTfjDiLWZ1A/kH2i9PPXcwfD3USlArzZtqsiuaKMQlpi7TZSy8G2ROwqz1a X9Pg==
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=7mMdzEvAXatHRonBcTLg6/Z1j4kgE92mV74Ax1sefdI=; b=Dq58CT3BCpOiqFz1P3gktjRHBrrnV34jBV8gKzZL5ESsmSvkVHSo7HPd4nP2LKjH8k EQ2YN5yrfgXYg9A9tmye5nCG4IcKuanqN4L99Z7SSdU8mv4GL9PMD4bh8jCW9r+VJvVL F54SpgThaHY80Vy/1aK+N5zUnmm/Z3tRX0KNwD2ODPj61/7BqbxS8ZQ3LAfuDCxpCI9h UBVsXvrEA1+ae38htG5sIeitZpH1PGWYUt9hMMznLrXjzpsQFoJZDk0XwNRirw1tgsZs fZe/ltkGeqIuM9TcYwFTY7KhjqJSYTFN4uNeL8QZmO7k7+QNi/48LFDTzojicXSFBq7B jcEQ==
X-Gm-Message-State: AEkoouutNjcCLuFQ8V6uUmGKt1yR82s5eMwLRhwY7nWkPiIaXDc4ORr3jHeIXb6cGoVriknVyd2dszklldOyl6NQ
X-Received: by 10.202.253.208 with SMTP id b199mr10824224oii.171.1471808725202; Sun, 21 Aug 2016 12:45:25 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.202.52.130 with HTTP; Sun, 21 Aug 2016 12:44:54 -0700 (PDT)
In-Reply-To: <CAO249yeeEo3B9H3SyGqA8aiWOWjoHYji=JXEh1GHOHSsf+RszA@mail.gmail.com>
References: <MWHPR11MB1374A50BC599B093EA09668984070@MWHPR11MB1374.namprd11.prod.outlook.com> <7070553C-65D1-46EE-95F4-DAE82E1F5A5E@weston.borman.com> <CY4PR11MB187848FCCEF4DB140F85913E841A0@CY4PR11MB1878.namprd11.prod.outlook.com> <2D524A8D-A5CA-45A6-B94D-FA1DA0CEE609@weston.borman.com> <CY4PR11MB1878E7E911194A1032E32428841E0@CY4PR11MB1878.namprd11.prod.outlook.com> <CAO249yeTNRFuFcWn5ga854g24GM_7DAjeKOSw3d7h=HQQYKX1Q@mail.gmail.com> <CADVnQymeyst9De4F8Zqc6wGfLEdzmGsypSC-ZKZ7bXT6PO=J4g@mail.gmail.com> <CAO249yeeEo3B9H3SyGqA8aiWOWjoHYji=JXEh1GHOHSsf+RszA@mail.gmail.com>
From: Neal Cardwell <ncardwell@google.com>
Date: Sun, 21 Aug 2016 15:44:54 -0400
Message-ID: <CADVnQym-wP=7pgSQ3ziWS-WmU9T-q2NVr1XSpB5ZkYOD8NYbAA@mail.gmail.com>
To: Yoshifumi Nishida <nishida@sfc.wide.ad.jp>
Content-Type: text/plain; charset=UTF-8
Archived-At: <https://mailarchive.ietf.org/arch/msg/tcpm/T4OuwPwW2SwnvDFTGORaq7wAd2U>
Cc: Kobby Carmona <kobby.Carmona@qlogic.com>, David Borman <dab@weston.borman.com>, "tcpm@ietf.org" <tcpm@ietf.org>
Subject: Re: [tcpm] Possible deadlock scenario with retransmission on both sides at the same time
X-BeenThere: tcpm@ietf.org
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: TCP Maintenance and Minor Extensions Working Group <tcpm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tcpm>, <mailto:tcpm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/tcpm/>
List-Post: <mailto:tcpm@ietf.org>
List-Help: <mailto:tcpm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tcpm>, <mailto:tcpm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Sun, 21 Aug 2016 19:45:27 -0000

I am pretty sure Linux does not have the issue Kobby pointed out in this thread.

At a high level Linux should be OK because it follows the principle
David Borman laid out in his August 16 email: "ACK-only packets should
be sent with the largest in-window sequence number that has ever been
sent."

Linux obeys that principle by using tp->snd_nxt to store the largest
sequence number that has ever been sent, and having
tcp_acceptable_seq() use tp->snd_nxt but clamp the outgoing sequence
number to make sure it is in-window. To be able to do this, in Linux,
the sender does not rewind tp->snd_nxt on retransmissions.

neal

On Sun, Aug 21, 2016 at 1:25 PM, Yoshifumi Nishida
<nishida@sfc.wide.ad.jp>; wrote:
> Hi Neal,
>
> Thanks for the info.
> So, it seems to me that the linux code has the issue Kobby pointed out.
> Or, am I missing something?
> --
> Yoshi
>
>
> On Mon, Aug 15, 2016 at 6:18 PM, Neal Cardwell <ncardwell@google.com>; wrote:
>>
>> On Mon, Aug 15, 2016 at 6:39 PM, Yoshifumi Nishida
>> <nishida@sfc.wide.ad.jp>; wrote:
>> > Hello,
>> > I personally think this is an interesting corner case for discussion.
>> > It looks a minor one, but I'm not not very sure if we can leave it for
>> > each
>> > implementation.
>> > I also guess a question would be if the BSD's fix is the best way for
>> > the
>> > issue.
>>
>> Yes, I agree this is an interesting case for discussion.
>>
>> FWIW, as a point of comparison for discussion, Linux's approach is a
>> little different: in Linux, the sender does not rewind SND.NXT on
>> retransmissions (RTO or Fast Recovery). Then the sender usually uses
>> SND.NXT for the seq field of outgoing pure ACKs. I say "usually"
>> because the Linux code has some code to deal with the case where the
>> receiver has withdrawn the receive window, so that SND.NXT is now
>> beyond the receive window. The code tcp_send_ack() uses to pick a seq
>> for outgoing pure ACKs looks like:
>>
>> /* SND.NXT, if window was not shrunk.
>>  * If window has been shrunk, what should we make? It is not clear at
>> all.
>>  * Using SND.UNA we will fail to open window, SND.NXT is out of
>> window. :-(
>>  * Anything in between SND.UNA...SND.UNA+SND.WND also can be already
>>  * invalid. OK, let's make this for now:
>>  */
>> static inline __u32 tcp_acceptable_seq(const struct sock *sk)
>> {
>>         const struct tcp_sock *tp = tcp_sk(sk);
>>
>>         if (!before(tcp_wnd_end(tp), tp->snd_nxt))
>>                 return tp->snd_nxt;
>>         else
>>                 return tcp_wnd_end(tp);
>> }
>>
>> neal
>
>