tcp_data_queue_ofo
在新内核的实现中ofo队列实际上是一颗红黑树。
在tcp_data_queue_ofo中根据序号,查找到合适位置,合并或者添加到rbtree中。
同时设置dsack和sack,准备ack给发送方。
//http://abcdxyzk.github.io/blog/2015/04/01/kernel-net-data-queue/ static void tcp_data_queue_ofo(struct sock *sk, struct sk_buff *skb) { struct tcp_sock *tp = tcp_sk(sk); struct rb_node **p, *q, *parent; struct sk_buff *skb1; u32 seq, end_seq; bool fragstolen; /*如果收到乱序包 ,可能在传输过程中出现了 拥塞 所以检查ecn 标志如果是路由器 拥塞会设置这个标志 说明路径上存在拥塞,需要 给发送方 接收方进行拥塞处理 如果没有拥塞 需要尽快通知 发送方*/ tcp_ecn_check_ce(tp, skb); if (unlikely(tcp_try_rmem_schedule(sk, skb, skb->truesize))) {//接收缓存不够 NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPOFODROP); tcp_drop(sk, skb);//接收缓存不够 丢弃 return; } /* Disable header prediction. */ tp->pred_flags = 0;//收到乱序包,关闭快速路径 inet_csk_schedule_ack(sk);//乱序包会快速ack NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPOFOQUEUE); seq = TCP_SKB_CB(skb)->seq; end_seq = TCP_SKB_CB(skb)->end_seq; SOCK_DEBUG(sk, "out of order segment: rcv_next %X seq %X - %X ", tp->rcv_nxt, seq, end_seq); p = &tp->out_of_order_queue.rb_node; if (RB_EMPTY_ROOT(&tp->out_of_order_queue)) {//ofo队列中为空,简单插入新的sack /* Initial out of order segment, build 1 SACK. */ if (tcp_is_sack(tp)) { tp->rx_opt.num_sacks = 1; tp->selective_acks[0].start_seq = seq; tp->selective_acks[0].end_seq = end_seq; } rb_link_node(&skb->rbnode, NULL, p); rb_insert_color(&skb->rbnode, &tp->out_of_order_queue); tp->ooo_last_skb = skb; goto end; } /* In the typical case, we are adding an skb to the end of the list. * Use of ooo_last_skb avoids the O(Log(N)) rbtree lookup. */ if (tcp_try_coalesce(sk, tp->ooo_last_skb, skb, &fragstolen)) {//对于普遍场景,先尝试合并skb到上一个乱序包 coalesce_done://合并完成 tcp_grow_window(sk, skb); //尝试增加窗口通告 kfree_skb_partial(skb, fragstolen);//skb已经被合并,可以释放 skb = NULL; goto add_sack; } /* Can avoid an rbtree lookup if we are adding skb after ooo_last_skb */ if (!before(seq, TCP_SKB_CB(tp->ooo_last_skb)->end_seq)) {//如果序号比ooo_last_skb大,则可以直接添加,避免查找 parent = &tp->ooo_last_skb->rbnode; p = &parent->rb_right;//添加到ooo_last_skb的右子树 goto insert; } /* Find place to insert this segment. Handle overlaps on the way. */ parent = NULL;//需要查找这个ofo包的添加位置 while (*p) { parent = *p; skb1 = rb_entry(parent, struct sk_buff, rbnode); if (before(seq, TCP_SKB_CB(skb1)->seq)) { p = &parent->rb_left;//比当前节点小,添加到左子树 continue; } if (before(seq, TCP_SKB_CB(skb1)->end_seq)) { if (!after(end_seq, TCP_SKB_CB(skb1)->end_seq)) {//序号所有部分都已经在当前节点 /* All the bits are present. Drop. */ NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPOFOMERGE); __kfree_skb(skb); skb = NULL; tcp_dsack_set(sk, seq, end_seq); goto add_sack; } if (after(seq, TCP_SKB_CB(skb1)->seq)) {//有部分重叠 /* Partial overlap. */ tcp_dsack_set(sk, seq, TCP_SKB_CB(skb1)->end_seq);//设置重叠部分dsack } else {//skb1->seq = seq <= skb1->end_seq < end_seq /* skb's seq == skb1's seq and skb covers skb1. * Replace skb1 with skb. *///skb中包含了全部的skb1 //使用skb替换skb1 rb_replace_node(&skb1->rbnode, &skb->rbnode, &tp->out_of_order_queue); //设置或合并现有dsack设置 //因为skb包含了全部skb1部分,则整个skb1都被重传了 tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq, TCP_SKB_CB(skb1)->end_seq); NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPOFOMERGE); //释放skb1 __kfree_skb(skb1); goto merge_right;//还要继续查看skb1的右子数有没有需要合并的部分 } } else if (tcp_try_coalesce(sk, skb1, skb, &fragstolen)) { // skb1->seq < skb1->end_seq <= seq goto coalesce_done;//尝试合并 } p = &parent->rb_right;//比当前加点大,查找右子树 } insert: /* Insert segment into RB tree. *///找到合适位置后插入ofo队列 rb_link_node(&skb->rbnode, parent, p); rb_insert_color(&skb->rbnode, &tp->out_of_order_queue); merge_right: /* Remove other segments covered by skb. */ while ((q = rb_next(&skb->rbnode)) != NULL) {//查看右子树中有没需要合并的节点 skb1 = rb_entry(q, struct sk_buff, rbnode); if (!after(end_seq, TCP_SKB_CB(skb1)->seq))//没有交集,不需要合并 break; if (before(end_seq, TCP_SKB_CB(skb1)->end_seq)) {//有交集 tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq, end_seq);//更新dsack break; } //完全包含当前节点,删除该节点,并更新dsack rb_erase(&skb1->rbnode, &tp->out_of_order_queue); tcp_dsack_extend(sk, TCP_SKB_CB(skb1)->seq, TCP_SKB_CB(skb1)->end_seq); NET_INC_STATS(sock_net(sk), LINUX_MIB_TCPOFOMERGE); tcp_drop(sk, skb1);//可以删除skb1 } /* If there is no skb after us, we are the last_skb ! */ if (!q)//没有下一个skb了,更新ooo_last_skb tp->ooo_last_skb = skb; add_sack: if (tcp_is_sack(tp)) tcp_sack_new_ofo_skb(sk, seq, end_seq); end: if (skb) {//没有被合并//跟in-order包一样,调整窗口 tcp_grow_window(sk, skb); skb_condense(skb); skb_set_owner_r(skb, sk); } }