TCP的核心系列 — SACK和DSACK的实现

struct tcp_sock {
	...
	/* Options received (usually on last packet, some only on SYN packets). */
	struct tcp_options_received rx_opt;
	...
	struct tcp_sack_block recv_sack_cache[4]; /* 保存收到的SACK块，用于提高效率*/
	...
	/* 快速路径中使用，上次第一个SACK块的结束处，现在直接从这里开始处理 */
	struct sk_buff *fastpath_skb_hint;
	int fastpath_cnt_hint;  /* 快速路径中使用，上次记录的fack_count，现在继续累加 */
	...

};

struct tcp_options_received {
	...
	u16 saw_tstamp : 1,    /* Saw TIMESTAMP on last packet */
		tstamp_ok : 1,     /* TIMESTAMP seen on SYN packet */
		dsack : 1,         /* D-SACK is scheduled, 下一个发送段是否存在D-SACK */
		sack_ok : 4,       /* SACK seen on SYN packet, 接收方是否支持SACK */
		...
	u8 num_sacks;          /* Number of SACK blocks, 下一个发送段中SACK块数 */
	...
};

18版本实现

18版本的逻辑较清晰，我们先来看看。

static int tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_una)
{
	const struct inet_connection_sock *icsk = inet_csk(sk);
	struct tcp_sock *tp = tcp_sk(sk);

	/* SACK选项的起始地址，sacked为SACK选项在TCP首部的偏移 */
	unsigned char *ptr = ack_skb->h.raw + TCP_SKB_CB(ack_skb)->sacked;

	struct tcp_sack_block *sp = (struct tcp_sack_block *) (ptr + 2); /* 指向第一个sack块 */
	int num_sacks = (ptr[1] - TCPOLEN_SACK_BASE) >> 3;               /* sack的块数 */

	int reord = tp->packets_out;     /* 乱序的起始包位置，一开始设为最大 */
	int prior_fackets;               /* 上次的fackets_out */
	u32 lost_retrans = 0;            /* 重传包可能丢失时SACK块结束序号，表示需要遍历到的最高序号 */
	int flag = 0;                    /* 有两种用途：先表示是否为快速路径，后用于返回标志 */
	int dup_sack = 0;                /* 有没有DSACK */
	int i;

	/* 如果之前没有SACKed的数据 */
	if (! tp->sacked_out)
		tp->fackets_out = 0;         /* FACK是根据最新的SACK来计算的，所以也要为0 */
	prior_fackets = tp->fackets_out; /* 处理前先保存上次的fackets_out */

	/* SACK fastpath:
	 * if the only SACK change is the increase of the end_seq of the first block then only
	 * apply that SACK block and use retrans queue hinting otherwise slowpath.
	 * 什么是快速路径：就是只有第一个SACK块的结束序号发生变化，其它的都不变。
	 */
	flag = 1; /* 为1的话为快速路径，0为慢速路径 */

	for (i = 0; i < num_sacks; i++) {
		__u32 start_seq = ntohl(sp[i].start_seq);  /* 块的起始序号 */
		__u32 end_seq = ntohl(sp[i].end_seq);      /* 块的结束序号 */

		/* 判断是否进入快速路径。
		 * 对第一个块：只要求起始序号相同
		 * 对于非第一个块：要求起始序号和结束序号都相同
		 * 也就是说，快速路径指的是只有第一个块的结束序号增加的情况
		 */
		if (i == 0) {
			if (tp->recv_sack_cache[i].start_seq != start_seq)
				flag = 0;

		} else {
			if ((tp->recv_sack_cache[i].start_seq != start_seq) ||
				(tp->recv_sack_cache[i].end_seq != end_seq))
				flag = 0;
		}

		/* 更新，保存这次收到的SACK块 */
		tp->recv_sack_cache[i].start_seq = start_seq;
		tp->recv_sack_cache[i].end_seq = end_seq;

		/* Check for D-SACK.
		 * 检测是否有DSACK ，DSACK块如果有，只能在第一个块
		 */
		if (i == 0) {
			u32 ack = TCP_SKB_CB(ack_skb)->ack_seq;

			/* 如果第一个SACK块的起始序号小于它的确认序号，说明此SACK块包含了确认过的数据 */
			if (before(start_seq, ack)) {
				dup_sack = 1;
				tp->rx_opt.sack_ok |= 4;
				NET_INC_STATS_BH(LINUX_MIB_TCPDSACKRECV);

			/* 如果第一个SACK块包含在第二个SACK块中，也说明第一个SACK块是重复的，即DSACK */
			} else if (num_sacks > 1 &&
				!after(end_seq, ntohl(sp[1].end_seq)) &&
				!before(start_seq, ntohl(sp[1].start_seq))) {
					dup_sack = 1;
					tp->rx_opt.sack_ok |= 4;
					NET_INC_STATS_BH(LINUX_MIB_TCPDSACKOFORECV);
			}
		}

		/* D-SACK for already forgotten data...
		 * Do dumb counting.
		 * undo_retrans记录重传数据包的个数，如果undo_retrans降到0，
		 * 就说明之前的重传都是不必要的，进行拥塞调整撤销。
		 * 条件：DSACK、undo_marker < end_seq <= prior_snd_una
		 */
		if (dup_sack && !after(end_seq, prior_snd_una) &&
			after(end_seq, tp->undo_marker))
			tp->undo_retrans--;

		/* Eliminate too old ACKs, but take into account more or less fresh ones,
		 * they can contain valid SACK info.
		 * tp->max_window为接收方通告过的最大接收窗口。
		 * 如果SACK信息是很早以前的，直接丢弃。
		 */
		if (before(ack, prior_snd_una - tp->max_window))
			return 0;
	}

	if (flag)
		num_sacks = 1; /* 快速路径时只有第一个块有变化，处理第一个块即可 */
	else {
		int j;
		/* 上次第一个SACK块的结束处，也是这次快速路径的开始点，慢速路径中重置了 */
		tp->fastpath_skb_hint = NULL;

		/* order SACK blocks to allow in order walk of the retrans queue.
		 * 对SACK块按起始序号，从小到大冒泡排序，以便与接下来的顺序遍历。
		 */
		for (i = num_sacks - 1; i > 0; i--) {
			for (j = 0; j < i; j++) {
				if (after(ntohl(sp[j].start_seq), ntohl(sp[j+1].start_seq))) {
					sp[j].start_seq = htonl(tp->recv_sack_cache[j+1].start_seq);
					sp[j].end_seq = htonl(tp->recv_sack_cache[j+1].end_seq);
					sp[j+1].start_seq = htonl(tp->recv_sack_cache[j].start_seq);
					sp[j+1].end_seq = htonl(tp->recv_sack_cache[j].end_seq);
				}
			}
		}
	}

	/* clear flag as used for different purpose in following code */
	flag = 0; /* 用于返回一些标志 */

	/* 逐个处理SACK块，可能只有一个，也可能多个 */
	for (i = 0; i < num_sacks; i++, sp++) {
		struct sk_buff *skb;
		__u32 start_seq = ntohl(sp->start_seq);  /* SACK块起始序号 */
		__u32 end_seq = ntohl(sp->end_seq);      /* SACK块结束序号 */
		int fack_count;                          /* 用于更新fackets_out */

		/* Use SACK fastpath hint if valid.
		 * 如果处于快速路径，那么可以不用从头遍历发送队列。
		  */
		if (tp->fastpath_skb_hint) {
			skb = tp->fastpath_skb_hint;         /* 从这个段开始处理 */
			fack_count = tp->fastpath_cnt_hint;  /* 已有的fackets_out */

		} else {                                 /* 否则慢速路径，从头开始处理 */
			skb = sk->sk_write_queue.next;       /* 发送队列头 */
			fack_count = 0;
		}

		/* Event B in the comment above.
		 * high_seq是进入Recovery或Loss时的snd_nxt，如果high_seq被SACK了，那么很可能有数据包
		  * 丢失了，不然就可以ACK掉high_seq返回Open态了。
		  */
		if (after(end_seq, tp->high_seq))
			flag |= FLAG_DATA_LOST;

		/* 从skb开始遍历发送队列 */
		sk_stream_for_retrans_queue_from(skb, sk) {
			int in_sack, pcount;
			u8 sacked;

			/* 记录最后一个正在处理的段，下次进入快速路径时，可以直接从这里
			 * 开始处理，而不用从头遍历发送队列。
			 */
			tp->fastpath_skb_hint = skb;
			tp->fastpath_cnt_hint = fack_count;

			/* The retransmission queue is always in order, so we can short-circuit
			 * the walk early.
			 * 当前skb段的序号超过SACK块的右端时，说明这个SACK块已经处理好了。
			 */
			if (! before(TCP_SKB_CB(skb)->seq, end_seq))
				break;

			/* 这个段是否完全包含在SACK块中 */
			in_sack = ! after(start_seq, TCP_SKB_CB(skb)->seq) &&
							   ! before(end_seq, TCP_SKB_CB(skb)->end_seq);
			pcount = tcp_skb_pcount(skb); /* 这个段分为多少个包 */

			/* 如果当前的段是TSO段，且它的一部份包含在SACK块中。
			 * 那么那些已经被SACK的部分就不用再重传了，所以需要重新分割TSO段。
			 */
			if (pcount > 1 && ! in_sack &&
				after(TCP_SKB_CB(skb)->end_seq, start_seq)) {
				unsigned int pkt_len;

				/* 表示TSO段的后半部在SACK块之外 */
				in_sack = ! after(start_seq, TCP_SKB_CB(skb)->seq);

				if (! in_sack)                                    /* 如果TSO段的前半部在SACK块之外 */
					pkt_len = (start_seq - TCP_SKB_CB(skb)->seq); /* SACK块之外段的长度 */
				else
					pkt_len = (end_seq - TCP_SKB_CB(skb)->seq);   /* SACK块之内段的长度 */

				/* 把TSO段分为两部分 */
				if (tcp_fragment(sk, skb, pkt_len, skb_shinfo(skb)->gso_size))
					break;

				pcount += tcp_skb_pcount(skb); /* skb缩减了，需要重新计算 */
			}

			fack_count += pcount;              /* 累加fackets_out */

			sacked = TCP_SKB_CB(skb)->sacked;  /* 这就是记分板scoreboard */

			/* Account D-SACK for retransmitted packet.
			 * 如果此skb属于DSACK块，且skb被重传过。
			 * 这里in_sack指的是：全部包含在SACK块中，还有前半部包含也算，因为分割了：）
			 */
			if ((dup_sack && in_sack) && (sacked & TCPCB_RETRANS) &&
				after(TCP_SKB_CB(skb)->end_seq, tp->undo_marker))
				tp->undo_retrans--; /* 如果减为0，那么说明之前重传都是不必要的，进行拥塞控制调整撤销 */

			/* The frame is ACKed. 当这个skb被确认了*/
			if (! after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)) {
				/* 乱序情况1：R|S标志，收到DSACK */
				if (sacked & TCPCB_RETRANS) {
					if ((dup_sack && in_sack) && (sacked & TCPCB_SACKED_ACKED))
						reord = min(fack_count, reord); /* 更新乱序的起始位置 */

				} else {
					/* 乱序情况2：一个包落在highest_sack之前，它既没被SACK过，也不是重传的，
					 * 现在才到达了，那么它就是乱序了。就是前面的洞自动填满了：）
					 */
					if (fack_count < prior_fackets && ! (sacked & TCPCB_SACKED_ACKED))
						reord = min(fack_count, reord);
				}

				/* Nothing to do; acked frame is about to be dropped.
				 * 这个skb已经被正常确认了，不用再处理了，它即将被丢弃。
				 */
				continue;
			}

			/* 如果这个包是重传包，并且它的snd_nxt小于此块的结束序号，
			 * 那么这个重传包可能是丢失了，我们记录这个块的结束序号，
			 * 作为接下来遍历的最高序号。
			 */
			if ((sacked & TCPCB_SACKED_RETRANS) &&
				after(end_seq, TCP_SKB_CB(skb)->ack_seq) &&
				(! lost_retrans || after(end_seq, lost_retrans)))
				lost_retrans = end_seq;

			/* 如果这个包不包含在SACK块中，即在SACK块之外，则不用继续处理 */
			if (! in_sack)
				continue;

			/* 如果skb还没有被标志为SACK，那么进行处理 */
			if (! (sacked & TCPCB_SACKED_ACKED)) {
				/* 有R标志，表示被重传过 */
				if (sacked & TCPCB_SACKED_RETRANS) {
					/* If the segment is not tagged as lost, we do not clear RETRANS, believing
					 * that retransmission is still in flight.
					 * 如果之前的标志是：R | L，那么好，现在收到包了，可以清除R和L。
					 * 如果之前的标志是：R，那么认为现在收到的是orig，重传包还在路上，所以不用干活：）
					 */
					if (sacked & TCPCB_LOST) {
						TCP_SKB_CB(skb)->sacked &= ~(TCPCB_LOST | TCPCB_SACKED_RETRANS); /* 取消L和R标志 */
						tp->lost_out -= tcp_skb_pcount(skb);    /* 更新LOST包个数 */
						tp->retrans_out -= tcp_skb_pcount(skb); /* 更新RETRANS包个数 */
						/* clear lost hint */
						tp->retransmit_skb_hint = NULL;
					}

				} else {
					/* New sack for not retransmitted frame, which was in hole. It is reordering.
					 * 如果一个包落在highest_sack之前，它即没被SACK过，也不是重传的，那么
					 * 它肯定是乱序了，到现在才被SACK。
					 */
					if (! (sacked & TCPCB_RETRANS) && fack_count < prior_fackets)
						reord = min(fack_count, reord); /* 记录乱序的起始 */

					/* 如果有L标志 */
					if (sacked & TCPCB_LOST) {
						TCP_SKB_CB(skb)->sacked &= ~TCPCB_LOST; /* 清除L标志 */
						tp->lost_out -= tcp_skb_pcount(skb);    /* 更新lost_out */
						/* clear lost hint */
						tp->retransmit_skb_hint = NULL;
					}
				}

				TCP_SKB_CB(skb)->sacked |= TCPCB_SACKED_ACKED;  /* 打上S标志 */
				flag |= FLAG_DATA_SACKED;                       /* New SACK */
				tp->sacked_out += tcp_skb_pcount(skb);          /* 更新sacked_out */

				if (fack_count > tp->fackets_out)
					tp->fackets_out = fack_count;               /* 更新fackets_out */

			} else { /* 已经有S标志 */
				/* 如果之前是R|S标志，且这个包被DSACK了，说明是乱序 */
				if (dup_sack && (sacked & TCPCB_RETRANS))
					reord = min(fack_count, reord);
			}

			/* D-SACK. We can detect redundant retransmission in S|R and plain R frames
			 * and clear it.
			 * undo_retrans is decreased above, L|R frames are accounted above as well.
			 * 如果skb被D-SACK，并且它的重传标志还未被清除，那么现在清除。
			 */
			if (dup_sack && (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS)) {
				TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;
				tp->retrans_out -= tcp_skb_pcount(skb);
				tp->retransmit_skb_hint = NULL;
			}
		}
	}

	/* Check for lost retransmit. This superb idea is borrowed from "ratehalving." Event C.
	 * 如果lost_retrans不为0，且处于Recovery状态，说明有重传包丢失，进行处理。
	 */
	if (lost_retrans && icsk->icsk_ca_state == TCP_CA_Recovery) {
		struct sk_buff *skb;

		/* 从头开始遍历发送队列 */
		sk_stream_for_retrans_queue(skb, sk) {
			/* lost_retrans记录的是SACK块结束序号，并且只在小于lost_retrans内有发现重传包丢失 */
			if (after(TCP_SKB_CB(skb)->seq, lost_retrans))
				break;

			/* 不关心成功确认过的包 */
			if (! after(TCP_SKB_CB(skb)->end_seq, tp->snd_una)
				continue;

			/* 现在判断这个重传包是否丢失。
			 * 这个包要是重传包，并且它的snd_nxt小于lost_retrans
			 */
			if ((TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_RETRANS) &&
				after(lost_retrans, TCP_SKB_CB(skb)->ack_seq) &&  (IsFack(tp) ||
				!before(lost_retrans, TCP_SKB_CB(skb)->ack_seq + tp->reordering * tp->mss_cache))) {
				TCP_SKB_CB(skb)->sacked &= ~TCPCB_SACKED_RETRANS;   /* 清除R标志 */
				tp->retrans_out -= tcp_skb_pcount(skb);             /* 更新retrans_out */
				/* clear lost hint */
				tp->retransmit_skb_hint = NULL;

				/* 给这个包重新打上L标志 */
				if (! (TCP_SKB_CB(skb)->sacked & (TCPCB_LOST | TCPCB_SACKED_ACKED))) {
					tp->lost_out += tcp_skb_pcount(skb);            /* 更新lost_out */
					TCP_SKB_CB(skb)->sacked |= TCPCB_LOST;          /* 打上L标志 */
					/* 这个弄错了吧？应该是FLAG_DATA_LOST才对 */
					flag |= FLAG_DATA_SACKED;
					NET_INC_STATS_BH(LINUX_MIB_TCPLOSTRETRANSMIT);
				}
			}
		}
	}

	tp->left_out = tp->sacked_out + tp->lost_out;
	/* 更新乱序队列长度。
	 * 乱序队列的长度 = fackets_out - reord + 1，reord记录从第几个包开始乱序
	 */
	if ((reord < tp->fackets_out) && icsk->icsk_ca_state != TCP_CA_Loss)
		tcp_update_reordering(sk, ((tp->fackets_out + 1) - reord), 0);

#if FASTRETRANS_DEBUG > 0
	BUG_TRAP((int) tp->sacked_out >= 0);
	BUG_TRAP((int) tp->lost_out >= 0);
	BUG_TRAP((int) tp->retrans_out >= 0);
	BUG_TRAP((int) tcp_packets_in_flight(tp) >= 0);
#endif

	return flag;
}