时间排序的SACK未确认报文链表
https://blog.csdn.net/sinat_20184565/article/details/105884870
内核实现的时间排序的未确认报文链表（time-sorted sent but un-SACKed skbs），用于加速RACK算法的处理。
tsorted链表初始化
首先是位于套接口的初始化函数tcp_init_sock中，初始化此链表tsorted_sent_queue。
void tcp_init_sock(struct sock *sk)
{
struct inet_connection_sock *icsk = inet_csk(sk);
struct tcp_sock *tp = tcp_sk(sk);
INIT_LIST_HEAD(&tp->tsorted_sent_queue);
其次，是位于子套接口的创建函数tcp_create_openreq_child中，初始化子套接口的tsorted链表。
struct sock *tcp_create_openreq_child(const struct sock *sk,
struct request_sock *req, struct sk_buff *skb)
{
INIT_LIST_HEAD(&newtp->tsorted_sent_queue);
最后，在断开连接、复位连接、销毁套接口、或者因套接口异常需要关闭时，将在函数tcp_write_queue_purge中清理tsorted链表，并且进行重新初始化。在初始化之前，先使用函数tcp_skb_tsorted_anchor_cleanup进行了相应清理操作，对此稍后进行介绍。
void tcp_write_queue_purge(struct sock *sk)
{
struct sk_buff *skb;
tcp_chrono_stop(sk, TCP_CHRONO_BUSY);
while ((skb = __skb_dequeue(&sk->sk_write_queue)) != NULL) {
tcp_skb_tsorted_anchor_cleanup(skb);
sk_wmem_free_skb(sk, skb);
}
tcp_rtx_queue_purge(sk);
INIT_LIST_HEAD(&tcp_sk(sk)->tsorted_sent_queue);
sk_buff中的tsorted链表挂点
在sk_buff结构中，tsorted链表成员tcp_tsorted_anchor与_skb_refdst和destructor定义在一个联合体union中，其中tcp_tsorted_anchor和_skb_refdst共用内存空间，意味着两者不能同时使用。
struct sk_buff {
...
union {
struct {
unsigned long _skb_refdst;
void (*destructor)(struct sk_buff *skb);
};
struct list_head tcp_tsorted_anchor;
};
在操作tsorted链表时，需要使用以下两个宏tcp_skb_tsorted_save和tcp_skb_tsorted_restore，前者初始化sk_buff结构中的tsorted链表挂点，保存_skb_refdst中的原有数据。后者在tsorted链表操作完成之后，还原_skb_refdst的值。
#define tcp_skb_tsorted_save(skb) { \
unsigned long _save = skb->_skb_refdst; \
skb->_skb_refdst = 0UL;
#define tcp_skb_tsorted_restore(skb) \
skb->_skb_refdst = _save; \
}
tsorted链表添加
tsorted链表的添加操作发生在数据发送和数据重传之后，如下在数据发送函数__tcp_transmit_skb中，对于不包含任何数据的Pure ACK报文不需要进行clone克隆处理，其它情况下，首先对报文进行克隆。在克隆之前，调用以上函数tcp_skb_tsorted_save保存_skb_refdst值，并将原值清零。在克隆完成之后，还原结构体中_skb_refdst的值。
static int __tcp_transmit_skb(struct sock *sk, struct sk_buff *skb,
int clone_it, gfp_t gfp_mask, u32 rcv_nxt)
{
BUG_ON(!skb || !tcp_skb_pcount(skb));
tp = tcp_sk(sk);
if (clone_it) {
TCP_SKB_CB(skb)->tx.in_flight = TCP_SKB_CB(skb)->end_seq - tp->snd_una;
oskb = skb;
tcp_skb_tsorted_save(oskb) {
if (unlikely(skb_cloned(oskb)))
skb = pskb_copy(oskb, gfp_mask);
else
skb = skb_clone(oskb, gfp_mask);
} tcp_skb_tsorted_restore(oskb);
if (unlikely(!skb))
return -ENOBUFS;
}
克隆之后的报文将用于执行发送操作，在IP层的发送函数ip_queue_xmit中，可以由套接口中缓存的路由项重新设置skb中的_skb_refdst值，或者通过路由查找进行设置。如果报文发送成功，调用tcp_update_skb_after_send函数，其中将处理tsorted链表的添加操作，这里使用的是克隆之前的报文结构oskb。
...
err = icsk->icsk_af_ops->queue_xmit(sk, skb, &inet->cork.fl);
if (unlikely(err > 0)) {
tcp_enter_cwr(sk);
err = net_xmit_eval(err);
}
if (!err && oskb) {
tcp_update_skb_after_send(sk, oskb, prior_wstamp);
tcp_rate_skb_sent(sk, oskb);
}
在看一下在重传函数__tcp_retransmit_skb中，如果要重传的报文skb结构的数据指针非4字节对齐（最后两位不为零），或者skb数据段的头部空间超过或等于U16_MAX长度，将导致校验和计算的起始位置变量csum_start（16位）溢出，具体可参见内核函数skb_partial_csum_set中的类似判断。以上的两种情况出现的几率都不大，但是如果出现，如下将拷贝报文结构，消除以上两种问题，这样，在TCP传输函数tcp_transmit_skb中就不需再对报文进行克隆处理。
报文重传完成之后，调用tcp_update_skb_after_send处理tsorted链表（在tcp_transmit_skb中略过了这一步）。
int __tcp_retransmit_skb(struct sock *sk, struct sk_buff *skb, int segs)
{
/* make sure skb->data is aligned on arches that require it
* and check if ack-trimming & collapsing extended the headroom
* beyond what csum_start can cover.
*/
if (unlikely((NET_IP_ALIGN && ((unsigned long)skb->data & 3)) ||
skb_headroom(skb) >= 0xFFFF)) {
struct sk_buff *nskb;
tcp_skb_tsorted_save(skb) {
nskb = __pskb_copy(skb, MAX_TCP_HEADER, GFP_ATOMIC);
err = nskb ? tcp_transmit_skb(sk, nskb, 0, GFP_ATOMIC) : -ENOBUFS;
} tcp_skb_tsorted_restore(skb);
if (!err) {
tcp_update_skb_after_send(sk, skb, tp->tcp_wstamp_ns);
tcp_rate_skb_sent(sk, skb);
}
} else {
函数tcp_update_skb_after_send如下，将报文skb链接到tsorted链表的末尾。
static void tcp_update_skb_after_send(struct sock *sk, struct sk_buff *skb, u64 prior_wstamp)
{
struct tcp_sock *tp = tcp_sk(sk);
skb->skb_mstamp_ns = tp->tcp_wstamp_ns;
if (sk->sk_pacing_status != SK_PACING_NONE) {
u...
}
list_move_tail(&skb->tcp_tsorted_anchor, &tp->tsorted_sent_queue);
}
tsorted链表与重传队列
对于新发送的报文（非重传），函数tcp_write_xmit将报文发送之后，调用tcp_event_new_data_sent函数。
static bool tcp_write_xmit(struct sock *sk, unsigned int mss_now, int nonagle, int push_one, gfp_t gfp)
{
...
while ((skb = tcp_send_head(sk))) {
...
if (unlikely(tcp_transmit_skb(sk, skb, 1, gfp)))
break;
repair:
/* Advance the send_head. This one is sent out.
* This call will increment packets_out.
*/
tcp_event_new_data_sent(sk, skb);
函数tcp_event_new_data_sent将报文由发送队列中移除，并添加到重传队列中，
static void tcp_event_new_data_sent(struct sock *sk, struct sk_buff *skb)
{
struct inet_connection_sock *icsk = inet_csk(sk);
struct tcp_sock *tp = tcp_sk(sk);
unsigned int prior_packets = tp->packets_out;
tp->snd_nxt = TCP_SKB_CB(skb)->end_seq;
__skb_unlink(skb, &sk->sk_write_queue);
tcp_rbtree_insert(&sk->tcp_rtx_queue, skb);
在重传函数__tcp_retransmit_skb中，如果报文长度大于允许的重传长度，将报文进行分片，仅发送允许长度的报文。否则，如果skb长度小于允许的长度，并且小于当前的MSS值，尝试合并重传队列中的后续报文组成长度为MSS的报文。
int __tcp_retransmit_skb(struct sock *sk, struct sk_buff *skb, int segs)
{
...
len = cur_mss * segs;
if (skb->len > len) {
if (tcp_fragment(sk, TCP_FRAG_IN_RTX_QUEUE, skb, len,
cur_mss, GFP_ATOMIC))
return -ENOMEM; /* We'll try again later. */
} else {
if (skb_unclone(skb, GFP_ATOMIC))
return -ENOMEM;
diff = tcp_skb_pcount(skb);
tcp_set_skb_tso_segs(skb, cur_mss);
diff -= tcp_skb_pcount(skb);
if (diff)
tcp_adjust_pcount(sk, skb, diff);
if (skb->len < cur_mss)
tcp_retrans_try_collapse(sk, skb, cur_mss);
}
如下分片函数tcp_fragment，其将skb分为两个报文结构：skb和buff，其中skb的数据长度为参数中指定的len；而buff中为剩余的数据。在函数最后，将buff链接到重传队列，以及将其链接在原skb在tsorted链表中的后部。
int tcp_fragment(struct sock *sk, enum tcp_queue tcp_queue,
struct sk_buff *skb, u32 len, unsigned int mss_now, gfp_t gfp)
{
struct sk_buff *buff;
...
tcp_insert_write_queue_after(skb, buff, sk, tcp_queue);
if (tcp_queue == TCP_FRAG_IN_RTX_QUEUE)
list_add(&buff->tcp_tsorted_anchor, &skb->tcp_tsorted_anchor);
如下函数tcp_retrans_try_collapse遍历重传队列中skb之后的报文，如果有合适的报文，由函数tcp_collapse_retrans完成合并。
static void tcp_retrans_try_collapse(struct sock *sk, struct sk_buff *to, int space)
{
skb_rbtree_walk_from_safe(skb, tmp) {
...
if (!tcp_collapse_retrans(sk, to))
break;
}
}
如下tcp_collapse_retrans函数，如果下一个报文的长度小于当前skb的末尾可用空间，将其数据拷贝到skb数据空间内。否则，由函数skb_shift将数据移动到skb的共享区。函数的最后，调用tcp_rtx_queue_unlink_and_free将被合并的报文由重传队列和tsorted链表中移除。
static bool tcp_collapse_retrans(struct sock *sk, struct sk_buff *skb)
{
struct tcp_sock *tp = tcp_sk(sk);
struct sk_buff *next_skb = skb_rb_next(skb);
next_skb_size = next_skb->len;
BUG_ON(tcp_skb_pcount(skb) != 1 || tcp_skb_pcount(next_skb) != 1);
if (next_skb_size) {
if (next_skb_size <= skb_availroom(skb))
skb_copy_bits(next_skb, 0, skb_put(skb, next_skb_size),
next_skb_size);
else if (!skb_shift(skb, next_skb, next_skb_size))
return false;
}
...
tcp_rtx_queue_unlink_and_free(next_skb, sk);
tsorted与报文确认
在接收到ACK确认报文，将使用函数tcp_clean_rtx_queue清除重传队列中序号在ACK确认序号（SND.UNA）之前的数据，这些数据已经被对端接收。调用函数tcp_rtx_queue_unlink_and_free将确认的报文skb，由重传队列和tsorted链表中移除，并释放。注意，对于仅确认了部分数据的skb（fully_acked==0），暂不清除。
static int tcp_clean_rtx_queue(struct sock *sk, u32 prior_fack,
u32 prior_snd_una, struct tcp_sacktag_state *sack)
{
bool fully_acked = true;
for (skb = skb_rb_first(&sk->tcp_rtx_queue); skb; skb = next) {
struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
if (after(scb->end_seq, tp->snd_una)) {
if (tcp_skb_pcount(skb) == 1 || !after(tp->snd_una, scb->seq))
break
acked_pcount = tcp_tso_acked(sk, skb);
if (!acked_pcount) break;
fully_acked = false;
} else {
acked_pcount = tcp_skb_pcount(skb);
}
...
if (!fully_acked) break;
...
tcp_rtx_queue_unlink_and_free(skb, sk);
}
对于SACK确认的报文，其序号块可能仅确认了skb中的部分数据，函数tcp_shifted_skb尝试将此部分数据与前面已被SACK确认的skb进行合并。在合并到前一个skb（prev）之后，如果skb中不再包含数据，由重传队列和tsorted链表中移除，并释放。
static bool tcp_shifted_skb(struct sock *sk, struct sk_buff *prev,
struct sk_buff *skb, struct tcp_sacktag_state *state,
unsigned int pcount, int shifted, int mss, bool dup_sack)
{
struct tcp_sock *tp = tcp_sk(sk);
u32 start_seq = TCP_SKB_CB(skb)->seq; /* start of newly-SACKed */
u32 end_seq = start_seq + shifted; /* end of newly-SACKed */
...
TCP_SKB_CB(prev)->end_seq += shifted;
TCP_SKB_CB(skb)->seq += shifted;
if (skb->len > 0) {
BUG_ON(!tcp_skb_pcount(skb));
NET_INC_STATS(sock_net(sk), LINUX_MIB_SACKSHIFTED);
return false;
}
...
tcp_rtx_queue_unlink_and_free(skb, sk);
NET_INC_STATS(sock_net(sk), LINUX_MIB_SACKMERGED);
如下tcp_sacktag_walk函数，对于SACK确认的报文，将其由tsorted链表中移除。
static struct sk_buff *tcp_sacktag_walk(struct sk_buff *skb, struct sock *sk,
struct tcp_sack_block *next_dup, struct tcp_sacktag_state *state,
u32 start_seq, u32 end_seq, bool dup_sack_in)
{
skb_rbtree_walk_from(skb) {
int in_sack = 0;
bool dup_sack = dup_sack_in;
...
if (unlikely(in_sack < 0)) break;
if (in_sack) {
TCP_SKB_CB(skb)->sacked =
tcp_sacktag_one(sk, state,
TCP_SKB_CB(skb)->sacked,
TCP_SKB_CB(skb)->seq,
TCP_SKB_CB(skb)->end_seq,
dup_sack,
tcp_skb_pcount(skb),
tcp_skb_timestamp_us(skb));
tcp_rate_skb_delivered(sk, skb, state->rate);
if (TCP_SKB_CB(skb)->sacked & TCPCB_SACKED_ACKED)
list_del_init(&skb->tcp_tsorted_anchor);
销毁tsorted链表
当套接口初始化、关闭、出错、销毁或者接收到对端复位报文时，将使用函数tcp_write_queue_purge清空套接口的发送队列和重传队列。函数tcp_skb_tsorted_anchor_cleanup将清空链接在套接口tsorted链表上的skb结构指针tcp_tsorted_anchor。最后，重新初始化tsorted链表tsorted_sent_queue。
void tcp_write_queue_purge(struct sock *sk)
{
struct sk_buff *skb;
tcp_chrono_stop(sk, TCP_CHRONO_BUSY);
while ((skb = __skb_dequeue(&sk->sk_write_queue)) != NULL) {
tcp_skb_tsorted_anchor_cleanup(skb);
sk_wmem_free_skb(sk, skb);
}
tcp_rtx_queue_purge(sk);
INIT_LIST_HEAD(&tcp_sk(sk)->tsorted_sent_queue);
如下tcp_rtx_queue_purge函数清空重传队列，清空报文结构skb的tcp_tsorted_anchor链表连接点。由于这里是清空整个tsorted链表，没有必要调用删除链表元素的函数list_del。
static inline void tcp_skb_tsorted_anchor_cleanup(struct sk_buff *skb)
{
skb->destructor = NULL;
skb->_skb_refdst = 0UL;
}
static inline void tcp_rtx_queue_unlink(struct sk_buff *skb, struct sock *sk)
{
tcp_skb_tsorted_anchor_cleanup(skb);
rb_erase(&skb->rbnode, &sk->tcp_rtx_queue);
}
static void tcp_rtx_queue_purge(struct sock *sk)
{
struct rb_node *p = rb_first(&sk->tcp_rtx_queue);
while (p) {
struct sk_buff *skb = rb_to_skb(p);
p = rb_next(p);
/* Since we are deleting whole queue, no need to list_del(&skb->tcp_tsorted_anchor)
*/
tcp_rtx_queue_unlink(skb, sk);
sk_wmem_free_skb(sk, skb);
RACK之tsorted链表处理
函数tcp_rack_detect_loss负责依据RACK算法标记丢失报文，即如果发送时间靠后的报文已经被确认（ACK或者SACK），那么之前的未确认报文认为已经丢失。为抵御乱序的情况，RACK在确认报文和丢失报文之间设置了一定的时间差值。
如下遍历tsorted时间排序的报文链表，从最早发送的报文开始，如果其已经被标记为丢失，但是还没有重传，不进行处理。
static void tcp_rack_detect_loss(struct sock *sk, u32 *reo_timeout)
{
struct tcp_sock *tp = tcp_sk(sk);
*reo_timeout = 0;
reo_wnd = tcp_rack_reo_wnd(sk);
list_for_each_entry_safe(skb, n, &tp->tsorted_sent_queue,
tcp_tsorted_anchor) {
struct tcp_skb_cb *scb = TCP_SKB_CB(skb);
s32 remaining;
/* Skip ones marked lost but not yet retransmitted */
if ((scb->sacked & TCPCB_LOST) &&
!(scb->sacked & TCPCB_SACKED_RETRANS))
continue;
如果遇到报文，其发送时间戳不在RACK记录的时间戳（最近确认报文的发送时间戳）之前，或者时间戳相等，但是其其结束序号在RACK记录的序号的后边，表明此报文在RACK记录的报文之后发送，结束遍历。
if (!tcp_rack_sent_after(tp->rack.mstamp,
tcp_skb_timestamp_us(skb),
tp->rack.end_seq, scb->end_seq))
break;
如果一个报文经过了当前RTT（非SRTT）加上乱序窗口时长之后还没被ACK确认或者SACK确认，即认为此报文已经丢失，并将其由tsorted链表中移除。随后，在重传之后，还会将此报文添加到tsorted链表中，由于那时其发送时间戳已经变化，将位于tsorted链表尾部。
/* A packet is lost if it has not been s/acked beyond
* the recent RTT plus the reordering window.
*/
remaining = tcp_rack_skb_timeout(tp, skb, reo_wnd);
if (remaining <= 0) {
tcp_mark_skb_lost(sk, skb);
list_del_init(&skb->tcp_tsorted_anchor);
} else {
/* Record maximum wait time */
*reo_timeout = max_t(u32, *reo_timeout, remaining);
tsorted与ACK时间戳
在处理重传队列函数tcp_clean_rtx_queue中，函数tcp_ack_tstamp记录对端发送的ACK报文时间戳。
static int tcp_clean_rtx_queue(struct sock *sk, u32 prior_fack,
u32 prior_snd_una, struct tcp_sacktag_state *sack)
{
for (skb = skb_rb_first(&sk->tcp_rtx_queue); skb; skb = next) {
tcp_ack_tstamp(sk, skb, prior_snd_una);
由于在函数调用__skb_tstamp_tx中要操作路由缓存_skb_refdst，这里先行将tsorted链表指针tcp_tsorted_anchor保存，之后进行还原。
static void tcp_ack_tstamp(struct sock *sk, struct sk_buff *skb, u32 prior_snd_una)
{
/* Avoid cache line misses to get skb_shinfo() and shinfo->tx_flags */
if (likely(!TCP_SKB_CB(skb)->txstamp_ack))
return;
shinfo = skb_shinfo(skb);
if (!before(shinfo->tskey, prior_snd_una) &&
before(shinfo->tskey, tcp_sk(sk)->snd_una)) {
tcp_skb_tsorted_save(skb) {
__skb_tstamp_tx(skb, NULL, sk, SCM_TSTAMP_ACK);
} tcp_skb_tsorted_restore(skb);
内核版本 5.0