//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\n",

           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);

    }

}