和18版本相比，37版本的SACK和DSACK的实现做了很多改进，最明显的就是需要遍历的次数少了，
减少了CPU的消耗。37版的性能提升了，代码有大幅度的改动，逻辑也更加复杂了。
本文主要内容：37版tcp_sacktag_write_queue()的实现，也即37版SACK和DSACK的实现。
Author：zhangskd @ csdn
数据结构
/* This defines a selective acknowledgement block. */
struct tcp_sack_block_wire {
__be32 start_seq;
__be32 end_seq;
}; /* 这就是一个SACK块 */
struct tcp_sack_block {
u32 start_seq; /* 起始序号 */
u32 end_seq; /* 结束序号 */
}; /* 用于处理SACK块时保存一些信息 */
struct tcp_sacktag_state {
int reord; /* 乱序的位置 */
int fack_count; /* 累加fackets_out */
int flag; /* 返回标志 */
};
struct tcp_sock {
...
/* Options received (usually on last packet, some only on SYN packets). */
struct tcp_options_received rx_opt;
...
/* SACKs data, these 2 need to be together (see tcp_build_and_update_options)
* 收到乱序包时填入信息，用于回复
*/
struct tcp_sack_block duplicate_sack[1]; /* D-SACK block */
struct tcp_sack_block selective_acks[4]; /* The SACKS themselves */
struct tcp_sack_block recv_sack_cache[4]; /* 保存收到的SACK块，用于提高效率*/
struct sk_buff *highest_sack; /* highest skb with SACK received
* (validity guaranteed only if sacked_out > 0) */
...
};
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块数 */
...
};
37版本实现
37版本做了一些改进，主要是为了提升效率，减少重复工作。
static int tcp_sacktag_write_queue (struct sock *sk, const 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首部的偏移 */
const unsigned char *ptr = (skb_transport_header(ack_skb) + TCP_SKB_CB(ack_skb)->sacked); struct tcp_sack_block_wire *sp_wire = (struct tcp_sack_block_wire *) (ptr + 2); /* 指向第一个sack块 */
struct tcp_sack_block sp[TCP_NUM_SACKS];
struct tcp_sack_block *cache;
struct tcp_sacktag_state state;
struct sk_buff *skb;
int num_sacks = min(TCP_NUM_SACKS, (ptr[1] - TCPOLEN_SACK_BASE) >> 3); /* sack的块数 */
int used_sacks;
int found_dup_sack = 0;
int i, j;
int first_sack_index; state.flag = 0;
state.reord = tp->packets_out; /* 乱序的起始位置一开始设为最大 */ /* 如果之前没有SACKed的数据 */
if (! tp->sacked_out) {
if (WARN_ON(tp->fackets_out))
tp->fackets_out = 0; /* FACK是根据最新的SACK来计算的，也要为0 */
tcp_highest_sack_reset(sk); /* tp->highest_sack置为发送队列的第一个数据包，因为没有SACK块 */
} /* 检查第一个SACK块是否为DSACK */
found_dup_sack = tcp_check_dsack(sk, ack_skb, sp_wire, num_sacks, prior_snd_una);
if (found_dup_sack)
state.flag |= FLAG_DSACKING_ACK; /* SACK blocks contained D-SACK info */ /* 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(TCP_SKB_CB(ack_skb)->ack_seq, prior_snd_una - tp->max_window))
return 0; if (! tp->packets_out) /* 如果我们并没有发送数据到网络中，错误 */
goto out; used_sacks = 0;
first_sack_index = 0; /* 进行SACK块的合法性检查，并确定要使用哪些SACK块 */
for (i = 0; i < num_sacks; i++) {
int dup_sack = ! i && found_dup_sack; /* 是否为DSACK块，DSACK块只能是第一个块 */ sp[used_sacks].start_seq = get_unaligned_be32(&sp_wire[i].start_seq);
sp[used_sacks].end_seq = get_unaligned_be32(&sp_wire[i].end_seq); /* 检查这个SACK块是否为合法的 */
if (! tcp_is_sackblock_valid(tp, dup_sack, sp[used_sacks].start_seq,
sp[used_sacks].end_seq)) { /* 不合法的话进行处理 */
int mib_idx; if (dup_sack) { /* 如果是DSACK块 */
if (! tp->undo_marker) /* 之前没有进入Recovery或Loss状态 */
mib_idx = LINUX_MIB_TCPDSACKINGOREDNOUNDO; /* TCPSACKIgnoredNoUndo */
else
mib_idx = LINUX_MIB_TCPDSACKINGNOREDOLD; /* TCPSACKIgnoredOld */ } else { /* 不是DSACK块 */
/* Don't count olds caused by ACK reordering，不处理ACK乱序 */
if ((TCP_SKB_CB(ack_skb)->ack_seq != tp->snd_una) &&
! after(sp[used_sacks].end_seq, tp->snd_una))
continue;
mib_idx = LINUX_MIB_TCPSACKDISCARD;
} NET_INC_STATS_BH(sock_net(sk), mib_idx); if (i == 0)
first_sack_index = -1; /* 表示第一个块无效 */ continue;
} /* Ignore very old stuff early，忽略已确认过的块 */
if (! after(sp[used_sacks].end_seq, prior_snd_una))
continue; used_sacks++; /* 实际要使用的SACK块数，忽略不合法和已确认过的 */
} /* order SACK blocks to allow in order walk of the retrans queue.
* 对实际使用的SACK块，按起始序列号，从小到大进行冒泡排序。
*/
for (i = used_sacks - 1; i > 0; i--) {
for (j = 0; j < i; j++) {
if (after(sp[j].start_seq, sp[j+1].start_seq)) {
swap(sp[j], sp[j+1]); /* 交换SACK块 */ /* Track where the first SACK block goes to，跟踪第一个SACK块 */
if (j == first_sack_index)
first_sack_index = j + 1;
}
}
} skb = tcp_write_queue_head(sk); /* 发送队列的第一个包 */
state.fack_count = 0;
i = 0; /* 接下来使cache指向之前的SACK块，即recv_sack_cache */
if (! tp->sacked_out) { /* 如果之前没有SACK块 */
/* It's already past, so skip checking against it.
* cache指向recv_sack_cache数组的末尾
*/
cache = tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache); } else {
cache = tp->recv_sack_cache;
/* Skip empty blocks in at head of the cache. 跳过空的块 */
while(tcp_sack_cache_ok(tp, cache) && ! cache->start_seq && ! cache->end_seq)
cache++;
} /* 遍历实际用到的SACK块 */
while (i < used_sacks) {
u32 start_seq = sp[i].start_seq;
u32 end_seq = sp[i].end_seq;
int dup_sack = (found_dup_sack && (i == first_sack_index)); /* 这个SACK块是否为DSACK块 */
struct tcp_sack_block *next_dup = NULL; /* 如果下一个SACK块是DSACK块，则next_dup指向DSACK块 */
if (found_dup_sack && ((i + 1) == first_sack_index))
next_dup = &sp[i + 1]; /* 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))
state.flag |= FLAG_DATA_LOST; /* Skip too early cached blocks.
* 如果cache块的end_seq < SACK块的start_seq，那说明cache块在当前块之前，不用管它了。
*/
while (tcp_sack_cache_ok(tp, cache) && ! before(start_seq, cache->end_seq))
cache++; /* Can skip some work by looking recv_sack_cache?
* 查看当前SACK块和cache块有无交集，避免重复工作。
*/
if (tcp_sack_cache_ok(tp, cache) && ! dup_sack &&
after(end_seq, cache->start_seq)) { /* Head todo? 处理start_seq到cache->start_seq之间的段 */
if (before(start_seq, cache->start_seq)) {
/* 找到start_seq对应的数据段 */
skb = tcp_sacktag_skip(skb, sk, &state, start_seq);
/* 遍历start_seq到cache->start_seq之间的段，为其间的skb更新记分牌 */
skb = tcp_sacktag_walk(skb, sk, next_dup, &state, start_seq, cache->start_seq, dup_sack);
} /* Rest of the block already fully processed?
* 如果此块剩下的部分都包含在cache块中，那么就不用再处理了。
*/
if (! after(end_seq, cache->end_seq))
goto advance_sp; /* 如果cache->start_seq < next_dup->start_seq < cache->end_seq，那么处理next_dup。
* 注意，如果start_seq < next_dup->start_seq < cache->start_seq，那么next_dup落在
* (start_seq, cache->start_seq) 内的部分已经被上面的处理过了：）现在处理的next_dup的剩余部分。
*/
skb = tcp_maybe_skipping_dsack(skb, sk, next_dup, &state, cache->end_seq); /* 处理(cache->end_seq, end_seq) ...tail remains todo... */
if (tcp_highest_sack_seq(tp) == cache->end_seq) {
skb = tcp_highest_sack(sk);
/* 如果已经到了snd_nxt了，那么直接退出SACK块的遍历 */
if (skb == NULL)
break;
state.fack_count = tp->fackets_out;
cache++; /* 此cache已经用完了 */
goto walk; /* 继续SACK块还没处理完的部分 */
} /* 找到end_seq > cache->end_seq的skb */
skb = tcp_sacktag_skip(skb, sk, &state, cache->end_seq); /* Check overlap against next cached too (past this one already) */
cache++; continue;
} /* 这个块没有和cache块重叠，是新的 */
if (! before(start_seq, tcp_highest_sack_seq(tp))) {
skb = tcp_highest_sack(sk);
if (skb == NULL)
break;
state.fack_count = tp->fackets_out;
} skb = tcp_sacktag_skip(skb, sk, &state, start_seq); /* skb跳到start_seq处，下面会walk遍历此块 */ walk:
/* 从skb开始遍历，标志块间的包 */
skb = tcp_sacktag_walk(skb, sk, next_dup, &state, start_seq, end_seq, dup_sack); advance_sp:
/* SACK enhanced FRTO (RFC4138, Appendix B): Clearing correct due to
* in-order walk.
*/
if (after(end_seq, tp->frto_highmark))
state.flag &= ~FLAG_ONLY_ORIG_SACKED; /* 清除这个标志 */ i++; /* 接下来处理下一个SACK块 */
} /* Clear the head of the cache sack blocks so we can skip it next time.
* 两个循环用于清除旧的SACK块，保存新的SACK块
*/
for (i = 0; i < ARRAY_SIZE(tp->recv_sack_cache) - used_sacks; i++) {
tp->recv_sack_cache[i].start_seq = 0;
tp->recv_sack_cache[i].end_seq = 0;
} for (j = 0; j < used_sacks; j++)
tp->recv_sack_cache[i++] = sp[j]; /* 检查重传包是否丢失，这部分独立出来 */
tcp_mark_lost_retrans(sk); tcp_verify_left_out(tp); if ((state.reord < tp->fackets_out) && ((icsk->icsk_ca_state != TCP_CA_Loss) || tp->undo_marker) &&
(! tp->frto_highmark || after(tp->snd_una, tp->frto_highmark)))
tcp_update_reordering(sk, tp->fackets_out - state.reord, 0); /* 更新乱序长度 */ out:
#if FASTRETRANS_DEBUG > 0
WARN_ON((int) tp->sacked_out < 0);
WARN_ON((int) tp->lost_out < 0);
WARN_ON((int) tp->retrans_out < 0);
WARN_ON((int) tcp_packets_in_flight(tp) < 0);
#endif return state.flag;
}
/*
* swap - swap value of @a and @b
*/
#define swap(a, b) \
do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0) static int tcp_sack_cache_ok(struct tcp_sock *tp, struct tcp_sack_block *cache)
{
return cache < tp->recv_sack_cache + ARRAY_SIZE(tp->recv_sack_cache);
} /* 被SACK过的包的最大初始序列号
* Start sequence of the highest skb with SACKed bit, valid only if sacked > 0
* or when the caller has ensured validity by itself.
*/
static inline u32 tcp_highest_sack_seq(struct tcp_sock *tp)
{
if (! tp->sacked_out) /* 没有包被SACK过，则设置成snd_una */
return tp->snd_una; if (tp->highest_sack == NULL) /* 已经是发送队列的最后一个包了 */
return tp->snd_nxt; return TCP_SKB_CB(tp->highest_sack)->seq;
} static inline void tcp_advance_highest_sack(struct sock *sk, struct sk_buff *skb)
{
tcp_sk(sk)->highest_sack = tcp_skb_is_last(sk, skb) ? NULL : tcp_write_queue_next(sk, skb);
}
使用cache
37版本利用上次缓存的tp->recv_sack_cache块来避免重复工作，提高处理效率。
主要思想就是，处理sack块时，和cache块作比较，如果它们有交集，说明交集部分已经处理过了，
不用再重复处理。
（1）忽略cache块
如果cache块完全在sack块的前面，即cache->end_seq < start_seq，那么忽略此cache块。
（2）没有交集
如果sack块完全在cache块前面，即end_seq < cache->start_seq，那么跳到walk处理，不考虑cache块。
（3）有交集
case 1：
只需处理(start_seq, cache->start_seq)这部分，交集不必处理。处理完后直接跳到advance_sp。
case 2：
只需处理(cache->end_seq, end_seq)这部分，交集不必处理。先skip到cache->end_seq，cache++，再continue。
case 3：
sack块完全包含在cache块中，那么什么都不用做，直接跳到advance_sp，处理下一个sack块。
case 4：
cache块完全包含在sack块中，这时候需要处理两部分：(start_seq, cache->start_seq)，(cache->end_seq, end_seq)。