SACK 分析

首先我们要看 sack 和dsack的 rfc 链接如下 sack https://tools.ietf.org/html/rfc2018 dsack https://tools.ietf.org/html/rfc2883 要理解 kernel 中是怎么实现 sack和dsack。需要知道以下几个关键点

1. kernel 发送数据包是以 skb为基础单元。发送完成以后会议skb的seq number作为key ，将这些发送完成的skb 插入到红黑树中，数据结构是（sk->tcp_rtx_queue）

2. 当发送端接收到ack后，会遍历 sk->tcp_rtx_queue 中的skb。如果这个skb整个都在ack的seq范围内，则会删除释放这个skb。 否则 只释放skb前部分内存，调整skb的seq。

3. 当接收到sack 时，内核会做会根据sack的分段，查找红黑树，sack最多可以包含4个分段，每个分段分别包含start_seq 和 end_seq。

   • 内核会首先使用start_seq在红黑树中找到包含 这个seq的skb即（skb start_seq < start_seq < skb end_seq）

   • 找到这个skb后，内核会将这个skb，列分为两个skb，将两个skb都插入红黑树中，第一部分不标记TCPCB_SACKED_CACKED.第二部分标记为TCPCB_SACKED_CACKED,标记在TCP_SKB_CB的sacked结构中。

   • 内核继续沿着红黑树查找下一个skb.如果这个skb的 end_seq 小于 sack的end_seq， 则会将这个skb 与上一个skb 合并。

   • 直到找到一个skb 他的 end_seq 大于 sack的end_seq。这时候，内核会将这个skb 以sack中的end_seq为分析界限，分成两部分。 第一部分的数据合并到上一个skb。后面的数据继续保持独立。

4. 当重传时，会从这个红黑树中找skb。如果skb的sacked 已经标记为 TCPCB_SACKED_ACKED|TCPCB_SACKED_RETRANS 则不会重传，否则重传。

5. 虽然红黑树中是以skb为单元记录。但是列分时是以mss 为最小单元的，即一个skb 的长度是mss的倍数，列分时，只能列分出去mss的倍数的长度。skb中包含多少个mss的长度记录在TCP_SKB_CB数据结构中的tcp_gso_segs成员中，注意这个成员是16位的。

在理解以上几点的基础上我们看代码。 首先看数据包发送的代码，在tcp_event_new_data_sent 函数中将发送出去的skb 插入红黑树。在tso_fragment函数中会计算tcp_gso_segs的值。

tcp_sendmsg 
    --> tcp_sendmsg_locked 
        -->tcp_push
            -->__tcp_push_pending_frames 
                -->tcp_write_xmit 
                    -->tso_fragment
                    -->tcp_event_new_data_sent

在看快重传逻辑。在tcp_xmit_retransmit_queue函数中对过滤掉已经有 TCPCB_SACKED_ACKED标记的skb。

tcp_ack
    -->tcp_fastretrans_alert
        -->tcp_simple_retransmit
            -->tcp_xmit_retransmit_queue
                -->tcp_retransmit_skb

最后，我们看 sack 包的处理逻辑。 tcp_clean_rtx_queue 以后的函数调用是收到ack以后清理 红黑树上的skb的逻辑， tcp_clean_rtx_queue以前的逻辑是处理sack的。结合上面几点，我们可以清晰的看到 内核是怎么处理sack。

tcp_v4_rcv
    -->tcp_v4_fill_cb
    -->tcp_v4_do_rcv
        tcp_rcv_established
            -->tcp_validate_incoming
                -->tcp_fast_parse_options
                    -->tcp_parse_options
            -->tcp_ack
                -->tcp_sacktag_write_queue
                    -->tcp_sacktag_skip
                    -->tcp_sacktag_walk
                        -->tcp_shift_skb_data
                            -->tcp_shift_skb_data
                                -->skb_shift
                                -->tcp_shifted_skb
                                    -->tcp_sacktag_one
                        -->tcp_match_skb_to_sack
                            -->tcp_fragment
                        -->tcp_sacktag_one
                -->tcp_clean_rtx_queue
                    -->tcp_tso_acked
                        -->tcp_trim_head
                    -->tcp_rtx_queue_unlink_and_free