From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail.ozlabs.org (mail.ozlabs.org [IPv6:2404:9400:2221:ea00::3]) by passt.top (Postfix) with ESMTPS id 5628E5A02C2 for ; Mon, 13 May 2024 03:32:51 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gibson.dropbear.id.au; s=202312; t=1715563964; bh=dMZwYij5ddOXKWv5sGC9lJmkcy/RCN/vxsbq++ArDMc=; h=Date:From:To:Cc:Subject:References:In-Reply-To:From; b=fNBwL/mtd6Gjw0gL+4FX+S4j19TRVvoxU/SgHIcaw1ZIj82+j+5N7iGmA0efS9dsg S27/yR9Q1h4Um7i68E9lu2dmYanKDyg+H7aPIBK5mi1mH4htNWOMKITP0Ok9ZRp5ff N50s3w86jM2fw2OoORvYTg3MgolLZhFp3WhmP1F1ak9Rtg189q1FA4ejUp8KdTdOhH 8cZcyqOcQZq29+p9bxBsuCYlrJ1ut2SmBNtXJtDMDXG9k5Pr4QtcQ9A2DHjqzGd7Xs v510To6sGzBWZOxRY3REb6NrgXs/DCsrVqWcK7Ci4/evDlJV57UfNaoNYQMaueZGa3 DOu8fmRm4qVuw== Received: by gandalf.ozlabs.org (Postfix, from userid 1007) id 4Vd26h3d6bz4wqM; Mon, 13 May 2024 11:32:44 +1000 (AEST) Date: Mon, 13 May 2024 11:32:39 +1000 From: David Gibson To: Jon Maloy Subject: Re: [PATCH] tcp: move seq_to_tap update to when frame is queued Message-ID: References: <20240509030023.4153802-1-jmaloy@redhat.com> <20240510184030.44b57a2f@elisabeth> <51413033-7a19-bf44-39da-980e826de896@redhat.com> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="XCo3iyvuwBzVM5or" Content-Disposition: inline In-Reply-To: <51413033-7a19-bf44-39da-980e826de896@redhat.com> Message-ID-Hash: MP6ZWDRXTJIWOMKECTXSJWEUQH3YDJOD X-Message-ID-Hash: MP6ZWDRXTJIWOMKECTXSJWEUQH3YDJOD X-MailFrom: dgibson@gandalf.ozlabs.org X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header CC: Stefano Brivio , passt-dev@passt.top, lvivier@redhat.com, dgibson@redhat.com X-Mailman-Version: 3.3.8 Precedence: list List-Id: Development discussion and patches for passt Archived-At: Archived-At: List-Archive: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --XCo3iyvuwBzVM5or Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, May 10, 2024 at 03:40:41PM -0400, Jon Maloy wrote: > On 2024-05-10 12:40, Stefano Brivio wrote: > > On Wed, 8 May 2024 23:00:23 -0400 > > Jon Maloy wrote: [snip] > > > + */ > > > +static void tcp_revert_seq(struct tcp_buf_seq_update *seq_update, in= t s, int e) > > > +{ > > > + struct tcp_tap_conn *conn; > > > + uint32_t lowest_seq; > > > + int i, ii; > > > + > > > + for (i =3D s; i < e; i++) { > > > + conn =3D seq_update[i].conn; > > > + lowest_seq =3D seq_update[i].seq; > > > + > > > + for (ii =3D i + 1; ii < e; ii++) { > > > + if (seq_update[ii].conn !=3D conn) > > > + continue; > > > + if (SEQ_GT(lowest_seq, seq_update[ii].seq)) > > > + lowest_seq =3D seq_update[ii].seq; > > > + } > > If I recall correctly, David suggested a simpler approach that avoids > > this O(n^2) scan, based on the observation that 1. the first entry you > > find in the table also has the lowest sequence number (we don't send > > frames out-of-order), > Not so sure about that. We can be in the middle of retransmit. We could, but I think that's ok. If we hit this on retransmit frames, it means they actually haven't been retramsitted yet because of the failure, so we need to try again, just like any other frame we failed to retransmit. For example in a single epoll cycle: 1. We queue frames 2, 3 & 4 [queue is (2, 3, 4)] 2. We get a dup ack for frame 1, and start retransmit 3. We queue frames 1 & 2 for retransmit [queue is (2, 3, 4, 1, 2)], seq_to_tap is 3 4. We flush the queued frames, but there's a failure after the first two. (2, 3) where transmitted, (4, 1, 2) failed. 5. We step through the failed frames 5.1. We see frame 4 failed, but seq_to_tap =3D=3D 3 <=3D 4, so we ignor= e it 5.2. We see frame 1 failed, and seq_to_tap =3D=3D 3 > 1 so we rewind to 1. This is correct, because our retransmit failed and we need to do it again. 5.3. We see frame 2 failed, but seq_to_tap =3D=3D 1 <=3D 2 so ignore The steps are slightly different, but I'm pretty sure this also does the right thing if - In the retransmit we get further than we got with the initial transmits - We start a retransmit several times (in a single queue batch (not sure if that's possible). This could involve multiple rewinds during a single revert scan, but while that's arguably non-optimal it should be both rare and not really that expensive. =20 - The retransmit starts from a point after the earliest initial frame in the queue (how would the peer request a retransmit for something we never transmitted? but maybe possible if the first transmit in this queue batch is itself a retransmit from an earlier cycle. --=20 David Gibson | I'll have my music baroque, and my code david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_ | _way_ _around_! http://www.ozlabs.org/~dgibson --XCo3iyvuwBzVM5or Content-Type: application/pgp-signature; name="signature.asc" -----BEGIN PGP SIGNATURE----- iQIzBAEBCAAdFiEEO+dNsU4E3yXUXRK2zQJF27ox2GcFAmZBbbYACgkQzQJF27ox 2GcYdxAAiniMncTiQzsk7s3yZV19fgHHYA0kbD96ySO3tBZLHxeUId/mCaUvUQgn YitcZ3px05Xfxonigxi4v1u0k5tJdBr7UcVhDJ7ktejhBgmjdzFZq52t8nJemI38 834bFTA1iqLiyhcnm0kBizy3RwX7PJKz7l+H3yZpQ1nPkzjyz0nzxYxHxPuKHelY FGsKhpYqcBX7iRtFGruQJ0MWksu+kkUj/rgClKdRsGLDqFKX0mnWjIBnp5zU6SrB WaV1YYIySLjnBpKpUcaBQ2RHwhiUEHcGNMHsTcSLda5We7AZ/LBggwrlyzgB13Wn KZiQlweY2Vl7Rh34hNT88+yTWdis24LEnvPUgNJE86ZIYDCprvl90e8QAF/U7vbD tuDMZSQOywIyObuq34+tAR+Ein8t3V3rSlAaPUBtYHEmnm1PAdHM3UdZqXYzxr67 p2CrsEfaV9RyWgrO+SChiuHcTVcHrUVi9ixdOv/Y0iWgWErbD5lgj82NZ8pyoHbP 0MCgHlhXt5dLchTAmobr4jhKLqElFZFe9dnWwGvfiBhApWeMncyapi1BSNev2hRX fEqlD4PRkwk4iu5o3MKJ3W6mMMbtJR1OHZp+g01QMy5QugNLjmrjMT+Hbk5kp3mt 9m0rSfZvN8fDGQ64y6308xhbadIbSdjnai9O6iAluXGJ+IW05J4= =2GSM -----END PGP SIGNATURE----- --XCo3iyvuwBzVM5or--