TCP的实现中，SACK和DSACK是比较重要的一部分。
SACK和DSACK的处理部分由Ilpo Järvinen (ilpo.jarvinen@helsinki.fi) 维护。
tcp_ack()处理接收到的带有ACK标志的数据段时，如果此ACK处于慢速路径，且此ACK的记分牌不为空，则调用
tcp_sacktag_write_queue()来根据SACK选项标记发送队列中skb的记分牌状态。
笔者主要分析18和37这两个版本的实现。
相对而言，18版本的逻辑清晰，但效率较低；37版本的逻辑复杂，但效率较高。
本文主要内容：18版tcp_sacktag_write_queue()的实现，也即18版SACK和DSACK的实现。
Author：zhangskd @ csdn
18版数据结构
/* 这就是一个SACK块 */
struct tcp_sack_block {u32 start_seq; /* 起始序号 */u32 end_seq; /* 结束序号 */
};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块之外段的长度 */elsepkt_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 > 0BUG_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);
#endifreturn flag;
}
Q: 为什么说18版的实现效率不高呢？
A: 我们收到num_sacks个SACK块，如果符合快速路径，那么遍历一次发送队列就可以了；
但是如果不符合快速路径，那么对于每个SACK块，都要遍历一次发送队列，而且都是从头开始遍历，
这样就做了很多重复工作，复杂度为O(num_sacks * cwnd)。如果cwnd很大的话，CPU消耗会较高。
37版本在这一方面做了一些优化。
对于18版本中的一些细节，接下来会对照37版本的实现进行详细分析，比如：
SACK选项的地址在接收时是如何保存起来的，这是在tcp_rcv_established中处理的。
DSACK的原理和实现，这部分在37中独立出来。
检测重传包是否丢失的原理和实现，这部分在37中独立出来。
乱序是如何检测的，它的原理和实现。
Reference
RFC 2018
RFC 2883