Linux TCP协议栈处理函数tcp_sacktag_write_queue的分析问题【部分解决？】

jiufei19

大家好，我在阅读linux的tcp部分源码时遇到一个问题，望各位大侠帮助解答，具体问题描述如下：

tcp_sacktag_write_queue(struct sock *sk, struct sk_buff *ack_skb, u32 prior_snd_una)
{
     ...
     for (i=0; i<num_sacks; i++, sp++) {
          ...
          /* Event "B" in the comment above. */
          if (after(end_seq, tp->high_seq))
              flag |= FLAG_DATA_LOST;
          ...
    }
    ...
}
         
上面代码中if那句的判断原理我一直没有太明白其依据究竟是什么？为了说明我的疑惑，我用附件的一副图进行说明，请各位帮我指出哪里有问题


1、图中对于发送方画图时似乎表示收到SACK后才发送下一个分段，实际不一定，请勿误会

2、Sx假定是因为某种原因丢失的分段，从Sx后，接收方连续收到S1,S2,S3三个分段，于是根据TCP的规范，此时接收方将针对每个收到的Sx后的分段进行立刻确认，实际也就是进行SACKed，而对于发送方，当收到SACK3后，知道此时网络发生了拥塞，于是进入到recovery阶段（或者是通过FACK方式知道拥塞发生，其判断是if ((snd.fack - snd.una> (3* MSS) || dupacks ==3) ， 不过这里为方便讨论，假定仍然是通过连续收到3个重复ACK来代表拥塞，其实也就是假定在3个重复ACK到来前没有再出现丢失分段的现象，此时FACK方式和普通3个重复ACK方式是一样的）

3、假定发送方在收到SACK3之前最近一次发送的分段为S5，S6是在Sx重发之后才会发送的下一分段

4、tp->high_seq的含义是发生拥塞时的snd_nxt，于是似乎其值应为S6

因为if判断中end_seq为发送方收到的SACK中某个block，这里判断的原理是若其值在tp->high_seq之后，即存在一个已被接收的分段，其分段的右边界大于tp->high_seq后，就表示有数据丢失了，所以设置flag为FLAG_DATA_LOST，但是根据我这里的图示，S5因为是重发Sx之前最后一个发出的分段，其正确到达了接收方，那么其右边界就是（S5+MSS）+1，而下一个即将发送的分段也是S6=S5+MSS+1， 那么怎么可能满足这个after的判断呢？并且既然已经连续收到了3个重复ACK了，那么已经可以表示当前有分段丢失了呀，为啥还要做这个判断呢？

我的理解哪里出现错误了？

-----------
补充一点
-----------

源码中那句英文注释如下，下面是我的翻译
964  *  B. SACK arrives sacking data transmitted after never retransmitted
965  *     hole was sent out.

966  *     SACK到达发送方，这些SACK对在hole所对应的数据被发出后的那些发出的数据进行确认,
967  *     此时，这些hole数据并未进行过重发（即对hole之后发出的数据进行了确认）

[ 本帖最后由 jiufei19 于 2009-9-6 19:32 编辑 ]

jiufei19

自己顶下，经过我又一遍仔细阅读，发现我之前发的帖子存在一个错误理解（如果这个理解没有错误的话，所以如果有则请各位指出），我的错误是将tp->high_seq理解错误了，该值应该为自发送方察觉拥塞发生后“已经”发出的数据的最高序号，而不是已经发出数据的最高序号+1，下面我根据此处的修改做如下更正
---------------------------------
从附件的图示可以看出，实际上这句if判断的做法就要在即将重发Sx之前将当前状态标识为LOST，因为在收到SACK3之后，实际上此时S5已经发出了，所以当前high_seq=|S5|+MSS（|S5|表示S5的起始序号，下同），而当S5被接收方SACKed后，则end_seq=|S5|+MSS+1，显然我们有end_seq > high_seq，于是发送方TCP认为出现了分段丢失情况，此时立刻启动重发Sx，重发后，S6，S7等再持续发出。

另外发方在收到SACK4之后，end_seq==|S4|+MSS+1，而high_seq仍然为=|S5|+MSS，于是end_seq < =high_seq， 此时并不认为出现lost现象，直到刚才分析的收到SACK5后。

总结：

发送方在收到连续3个重复ACK后，此时逻辑上虽然表示有分段丢失了，但是实际上并没有真正在代码中设定分段丢失状态，此过程一直持续到在重发丢失分段之前（此时再次收到2个SACK），根据上述分析的条件设置状态为LOST


-------------------
如有错误，请拍砖

[ 本帖最后由 jiufei19 于 2009-9-6 23:31 编辑 ]

hritian

你看的哪个版本的内核，这sack重传的问题上 2.6.24以前的内核有bug。

tp->high_seq是重传前的最大序号，目的是为了鉴别是不是重传包丢掉了。

eexplorer

> 从附件的图示可以看出，实际上这句if判断的做法就要在即将重发Sx之前将当前状态标识为LOST，
> 因为在收到SACK3之后，实际上此时S5已经发出了，所以当前high_seq=|S5|+MSS（|S5|表示S5的起
> 始序号，下同），

high_seq是tcp进入recovery state的时候的snd_nxt，以你举的例子为例，当收到连续3个duplicated ack后，tcp进入recovery state,这时已经发送了S5，那么这时的snd_nxt就是s6,high_seq也就是s6了。

一旦进入了recovery state，tcp就会重传high_seq以前它认为lost的packet。当所有它认为lost的packet传完后，如果cwnd允许的话，它会接着传新的数据，也就是s6,s7...

而如果接受方受到了所有重传的数据以及新的数据的话，它会ack一个seq,告诉发送方受到了所有的数据。这样tcp就跳出recovery state,重新进入正常状态。

如果这时sender还收到SACK的包，而且sack的是high_seq以后的数据的话，那说明receiver还是没有收到sender重传的那些包。所以sender就认为data lost了。

[ 本帖最后由 eexplorer 于 2009-9-11 16:50 编辑 ]

jiufei19

感谢指正，我看的是2.6.23版本，显然是有错误的版本

jiufei19

感谢eexplorer的帮助，我正在理解你的说明。稍后我发表下意见

先说个题外话，eexplorer对tcp_sacktag_write_queue函数和相关的tcp_fragment函数进行过全面的阅读分析吗？我在阅读过程中感到非常吃力，能指点下吗？

jiufei19

>high_seq是tcp进入recovery state的时候的snd_nxt，以你举的例子为例，当收到连续3个duplicated ack后，tcp进入recovery state,这时已经发送了S5，那么这时的
>snd_nxt就是s6,high_seq也就是s6了。

请问eexplorer，high_seq到底是指已经发出的最大序号（即真正发出的）还是那个即将发出的？

>如果这时sender还收到SACK的包，而且sack的是high_seq以后的数据的话，那说明receiver还是没有收到sender重传的那些包。所以sender就认为data lost了

我没有太理解eexploer的这句说明，请问是否你认为sender感知发生data lost的时机是在进行了Sx重发并丢失了该重发Sx后？还是如我原来分析的那样？

[ 本帖最后由 jiufei19 于 2009-9-11 18:57 编辑 ]

eexplorer

> 请问eexplorer，high_seq到底是指已经发出的最大序号（即真正发出的）还是那个即将发出的？

即将要发出的，所谓的snd_nxt就是下一次要发送的包的seq num。  

> 我没有太理解eexploer的这句说明，请问是否你认为sender感知发生data lost的时机是在进行了Sx重发并丢失了该重发Sx
> 后？ 还是如我原来分析的那样？

sender进入data lost的情况有很多种，你所说的是一种case。

end_seq > tp->high_seq也是一种，一旦进入recovery状态，tcp必须收到接收方发回的ack_seq >= tp->high_seq才会退出recovery状态，进入正常状态。如果收到sack的包且sack的是high_seq后面的包的话，说明client还是没有收到前面resend的包。

eexplorer

原帖由 jiufei19 于 2009-9-11 18:39 发表
感谢eexplorer的帮助，我正在理解你的说明。稍后我发表下意见

先说个题外话，eexplorer对tcp_sacktag_write_queue函数和相关的tcp_fragment函数进行过全面的阅读分析吗？我在阅读过程中感到非常吃力，能指点 ...

Linux tcp congestion control是非常复杂的一套逻辑，我推荐你看一下一篇文档: google一下"congestion control in Linux tcp"，是Alexey Kuznetsov写的。
里面虽然讲得是2.4的tcp，但是2.6其实原理是一样的。看了这篇文档可以对Linux tcp congestion control的框架有个整体的把握，再看code的话，会好很多。

八卦一下，Alexey Kuznetsov可是一个大牛，当年Linux的network stack performance不行，Alexey就在2.4的时候把tcp/ip重写了一下，然后就没人再说Linux kernel network stack performance不行了。

你可以 #grep ANK net/ipv4，到处都是这位大牛的爪子。。。

jiufei19

那么请问eexplorer，是否这里tcp_sacktag_write_queue所要判断的丢失现象就是指：重传包丢掉了这种case，而不是我所给出的那种丢失的case？请看我下面的补充说明

根据源码中所标注那句英文注释如下（下面是我的翻译）
964  *  B. SACK arrives sacking data transmitted after never retransmitted
965  *     hole was sent out.

966  *     SACK到达发送方，这些SACK对在hole所对应的数据被发出后的那些发出的数据进行确认,
967  *     此时，这些hole数据并未进行过重发（即对hole之后发出的数据进行了确认）


显然原文是指没有重发时发生的SACK，所以似乎这段代码要判断的所谓丢失是指非重发的丢失，我的理解是否正确？另外感谢eexplorer的提示，我下载了那篇文章，为便于其他人研究，作为了附件

[ 本帖最后由 jiufei19 于 2009-9-11 22:01 编辑 ]