public inbox for passt-dev@passt.top
 help / color / mirror / code / Atom feed
From: David Gibson <david@gibson.dropbear.id.au>
To: Jon Maloy <jmaloy@redhat.com>
Cc: Stefano Brivio <sbrivio@redhat.com>,
	passt-dev@passt.top, lvivier@redhat.com, dgibson@redhat.com
Subject: Re: [PATCH] tcp: move seq_to_tap update to when frame is queued
Date: Mon, 13 May 2024 11:32:39 +1000	[thread overview]
Message-ID: <ZkFtt7NmdDzPDwxM@zatzit> (raw)
In-Reply-To: <51413033-7a19-bf44-39da-980e826de896@redhat.com>

[-- Attachment #1: Type: text/plain, Size: 2934 bytes --]

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 <jmaloy@redhat.com> wrote:
[snip]
> > > + */
> > > +static void tcp_revert_seq(struct tcp_buf_seq_update *seq_update, int s, int e)
> > > +{
> > > +	struct tcp_tap_conn *conn;
> > > +	uint32_t lowest_seq;
> > > +	int i, ii;
> > > +
> > > +	for (i = s; i < e; i++) {
> > > +		conn = seq_update[i].conn;
> > > +		lowest_seq = seq_update[i].seq;
> > > +
> > > +		for (ii = i + 1; ii < e; ii++) {
> > > +			if (seq_update[ii].conn != conn)
> > > +				continue;
> > > +			if (SEQ_GT(lowest_seq, seq_update[ii].seq))
> > > +				lowest_seq = 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 == 3 <= 4, so we ignore it
   5.2.  We see frame 1 failed, and seq_to_tap == 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 == 1 <= 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.    

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

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

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

  reply	other threads:[~2024-05-13  1:32 UTC|newest]

Thread overview: 5+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2024-05-09  3:00 [PATCH] tcp: move seq_to_tap update to when frame is queued Jon Maloy
2024-05-10 16:40 ` Stefano Brivio
2024-05-10 19:40   ` Jon Maloy
2024-05-13  1:32     ` David Gibson [this message]
2024-05-13  1:03   ` David Gibson

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=ZkFtt7NmdDzPDwxM@zatzit \
    --to=david@gibson.dropbear.id.au \
    --cc=dgibson@redhat.com \
    --cc=jmaloy@redhat.com \
    --cc=lvivier@redhat.com \
    --cc=passt-dev@passt.top \
    --cc=sbrivio@redhat.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

	https://passt.top/passt

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for IMAP folder(s).