时间排序的SACK未确认报文链表

2023-12-19 09:48
文章标签 链表 时间 排序 确认 报文 sack

本文主要是介绍时间排序的SACK未确认报文链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

内核实现的时间排序的未确认报文链表（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);elseskb = 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))breakacked_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

这篇关于时间排序的SACK未确认报文链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/511749。

相关文章

Python的Darts库实现时间序列预测

Python的Darts库实现时间序列预测

《Python的Darts库实现时间序列预测》Darts一个集统计、机器学习与深度学习模型于一体的Python时间序列预测库,本文主要介绍了Python的Darts库实现时间序列预测,感兴趣的可以了解... 目录目录一、什么是 Darts？二、安装与基本配置安装 Darts导入基础模块三、时间序列数据结构与
阅读更多...
MyBatis Plus实现时间字段自动填充的完整方案

MyBatis Plus实现时间字段自动填充的完整方案

《MyBatisPlus实现时间字段自动填充的完整方案》在日常开发中,我们经常需要记录数据的创建时间和更新时间,传统的做法是在每次插入或更新操作时手动设置这些时间字段,这种方式不仅繁琐,还容易遗漏,... 目录前言解决目标技术栈实现步骤1. 实体类注解配置2. 创建元数据处理器3. 服务层代码优化填充机制详
阅读更多...
C++统计函数执行时间的最佳实践

C++统计函数执行时间的最佳实践

《C++统计函数执行时间的最佳实践》在软件开发过程中,性能分析是优化程序的重要环节,了解函数的执行时间分布对于识别性能瓶颈至关重要,本文将分享一个C++函数执行时间统计工具,希望对大家有所帮助... 目录前言工具特性核心设计1. 数据结构设计2. 单例模式管理器3. RAII自动计时使用方法基本用法高级用法
阅读更多...
C# LiteDB处理时间序列数据的高性能解决方案

C# LiteDB处理时间序列数据的高性能解决方案

《C#LiteDB处理时间序列数据的高性能解决方案》LiteDB作为.NET生态下的轻量级嵌入式NoSQL数据库,一直是时间序列处理的优选方案,本文将为大家大家简单介绍一下LiteDB处理时间序列数... 目录为什么选择LiteDB处理时间序列数据第一章：LiteDB时间序列数据模型设计1.1 核心设计原则
阅读更多...
MySQL按时间维度对亿级数据表进行平滑分表

MySQL按时间维度对亿级数据表进行平滑分表

《MySQL按时间维度对亿级数据表进行平滑分表》本文将以一个真实的4亿数据表分表案例为基础,详细介绍如何在不影响线上业务的情况下,完成按时间维度分表的完整过程,感兴趣的小伙伴可以了解一下... 目录引言一、为什么我们需要分表1.1 单表数据量过大的问题1.2 分表方案选型二、分表前的准备工作2.1 数据评估
阅读更多...
Java集合中的链表与结构详解

Java集合中的链表与结构详解

《Java集合中的链表与结构详解》链表是一种物理存储结构上非连续的存储结构,数据元素的逻辑顺序的通过链表中的引用链接次序实现,文章对比ArrayList与LinkedList的结构差异,详细讲解了链表... 目录一、链表概念与结构二、当向单链表的实现2.1 准备工作2.2 初始化链表2.3 打印数据、链表长
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
MySQL中DATE_FORMAT时间函数的使用小结

MySQL中DATE_FORMAT时间函数的使用小结

《MySQL中DATE_FORMAT时间函数的使用小结》本文主要介绍了MySQL中DATE_FORMAT时间函数的使用小结,用于格式化日期/时间字段,可提取年月、统计月份数据、精确到天,对大家的学习或... 目录前言DATE_FORMAT时间函数总结前言mysql可以使用DATE_FORMAT获取日期字段
阅读更多...
Python标准库datetime模块日期和时间数据类型解读

Python标准库datetime模块日期和时间数据类型解读

《Python标准库datetime模块日期和时间数据类型解读》文章介绍Python中datetime模块的date、time、datetime类,用于处理日期、时间及日期时间结合体,通过属性获取时间... 目录Datetime常用类日期date类型使用时间 time 类型使用日期和时间的结合体–日期时间(
阅读更多...
Java获取当前时间String类型和Date类型方式

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》：本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2