Re: [PATCH net v2 1/2] tcp: restore RACK list membership when undoing loss

[Neal Cardwell]

From: Neal Cardwell <ncardwell@xxxxxxxxxx>

Hi Neil,

Thanks for your TCP patch and packetdrill test! I agree this is worth
improving.

I share Eric's concerns about the performance costs of this current TCP
patch. And Yuchung and I were chatting about this out of band a few days ago;
we were both concerned about the performance costs of that approach.

Yuchung and I were thinking that perhaps a better trade-off would be to
leverage the fact that most of the time when there is an undo there are no lost
packets in the scoreboard that were retransmitted, in which case all skbs that
are marked as lost have a transmission order that is the same as their sequence
order. That means that in most cases in the existing skb_rbtree_walk iterating
through the tcp_rtx_queue we can do a kind of fast "merge sort" of the (already
time-sorted) lost skbs in tcp_rtx_queue into the (already time-sorted) skbs in
tp->tsorted_sent_queue.  This should allow us to keep the cost of
tcp_undo_cwnd_reduction() as O(packets_out) (without any extra list_sort()
cost), while still integrating all the lost packets back into
tp->tsorted_sent_queue in the vast majority of cases.

And in the rare case when somehow there is an undo while there are lost packets
that were EVER_RETRANS, it would be OK to fall back to an RTO for this rare
case. That is no worse than the behavior we have been living with for a long
time.

And with this approach we would not need to add any per-socket or per-skb
state.

Along those lines, what do you think about something like the following (which
compiles and passes your nice packetdrill test):

diff --git a/net/ipv4/tcp_input.c b/net/ipv4/tcp_input.c
index 92bc60716..cd7c3e408 100644
--- a/net/ipv4/tcp_input.c
+++ b/net/ipv4/tcp_input.c
@@ -2840,15 +2840,62 @@ static void DBGUNDO(struct sock *sk, const char *msg)
 #endif
 }
 
+/* Is skb @a after skb @b in tp->tsorted_sent_queue (send) order? */
+static bool tcp_tsorted_after(const struct list_head *a,
+			      const struct list_head *b)
+{
+	const struct sk_buff *skb_a = list_entry(a, struct sk_buff,
+						 tcp_tsorted_anchor);
+	const struct sk_buff *skb_b = list_entry(b, struct sk_buff,
+						 tcp_tsorted_anchor);
+
+	return tcp_skb_sent_after(tcp_skb_timestamp_us(skb_a),
+				  tcp_skb_timestamp_us(skb_b),
+				  TCP_SKB_CB(skb_a)->end_seq,
+				  TCP_SKB_CB(skb_b)->end_seq);
+}
+
+/* Link skb back into tp->tsorted_sent_queue in send order, at or after
+ * pos, and advance pos to it. Leave skb alone if it was sent before
+ * pos. As pos only moves forward, each call is amortized O(1).
+ */
+static void tcp_tsorted_relink_skb(struct tcp_sock *tp, struct sk_buff *skb,
+				    struct list_head **pos_ptr)
+{
+	struct list_head *head = &tp->tsorted_sent_queue;
+	struct list_head *node = &skb->tcp_tsorted_anchor;
+	struct list_head *pos = *pos_ptr;
+
+	if (pos != head && !tcp_tsorted_after(node, pos))
+		return;
+	while (pos->next != head && !tcp_tsorted_after(pos->next, node))
+		pos = pos->next;
+	if (pos != node)		/* not already linked in place */
+		list_move(node, pos);
+	*pos_ptr = node;
+}
+
 static void tcp_undo_cwnd_reduction(struct sock *sk, bool unmark_loss)
 {
 	struct tcp_sock *tp = tcp_sk(sk);
 
 	if (unmark_loss) {
+		struct list_head *pos = &tp->tsorted_sent_queue;
 		struct sk_buff *skb;
 
 		skb_rbtree_walk(skb, &sk->tcp_rtx_queue) {
-			TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST;
+			u8 sacked = TCP_SKB_CB(skb)->sacked;
+
+			TCP_SKB_CB(skb)->sacked = sacked & ~TCPCB_LOST;
+			/* RACK unlinked the skbs it marked lost. Skbs never
+			 * retransmitted keep their original send times, which
+			 * increase with sequence, so in one forward pass we
+			 * relink them all. For the rare case of undo after
+			 * lost retransmissions, we will fall back to RTO.
+			 */
+			if ((sacked & (TCPCB_LOST | TCPCB_EVER_RETRANS)) ==
+			    TCPCB_LOST)
+				tcp_tsorted_relink_skb(tp, skb, &pos);
 		}
 		tp->lost_out = 0;
 		tcp_clear_all_retrans_hints(tp);