说说tcp_sacktag_write_queue函数的改动

最近在把代码从18移植到 32的内核上，发现tcp_sacktag_write_queue函数改的面目全非，搞得我十分 头大，火大。
关于该函数的详细分析，请看http://simohayha.javaeye.com/blog/578744 ，我就不转载了。
比较大的变化有三个
1 tp->recv_sack_cache[]真正派上了用场，通过与上一次的sack块的比照，减少对发送缓存中的skb的查找次数。
对每个新sack块，比较是不是以前的sack块里面已经有了，如果已经有了，ok，可以直接退出来，如果没有顺序查找到，并将相应的发送包标记。如果新sack块的序号大于以前最大的那个sack块，那么直接跳到标记的最大的那个sack块。
如此，让我们假设一下重传包不丢，没有乱序的情况（这个是绝大多数的情况），对于sack包的处理，每次丢包是0（n），而在以前（我应该没记错）是o（kn），k=收到的sack包的数量。如果cwnd=1000，好吧，这个悲剧大了。
详细请看这一段的代码：
while (tcp_sack_cache_ok(tp, cache) &&
               !before(start_seq, cache->end_seq))
            cache++;

        /* Can skip some work by looking recv_sack_cache? */
        if (tcp_sack_cache_ok(tp, cache) && !dup_sack &&
            after(end_seq, cache->start_seq)) {

            /* Head todo? */
            if (before(start_seq, cache->start_seq)) {
                skb = tcp_sacktag_skip(skb, sk, &state,
                               start_seq);
                skb = tcp_sacktag_walk(skb, sk, next_dup,
                               &state,
                               start_seq,
                               cache->start_seq,
                               dup_sack);
            }

            /* Rest of the block already fully processed? */
            if (!after(end_seq, cache->end_seq))
                goto advance_sp;

            skb = tcp_maybe_skipping_dsack(skb, sk, next_dup,
                               &state,
                               cache->end_seq);

            /* ...tail remains todo... */
            if (tcp_highest_sack_seq(tp) == cache->end_seq) {
                /* ...but better entrypoint exists! */
                skb = tcp_highest_sack(sk);
                if (skb == NULL)
                    break;
                state.fack_count = tp->fackets_out;
                cache++;
                goto walk;
            }

            skb = tcp_sacktag_skip(skb, sk, &state, cache->end_seq);
            /* Check overlap against next cached too (past this one already) */
            cache++;
            continue;
        }

        if (!before(start_seq, tcp_highest_sack_seq(tp))) {
            skb = tcp_highest_sack(sk);
            if (skb == NULL)
                break;
            state.fack_count = tp->fackets_out;
        }

2 合并被确认的skb
新增加的函数tcp_shift_skb_data ，如此好处依然是提高效率，把相邻的包整合在一块，这样每次查找的数量就会更加减少（尤其是在重传丢包的时候），其查找次数和丢包的个数成正比，而不是与以前的（最坏情况下）和窗口成正比。

说到这，我可以来说一个我的亲身体会，如假包换，当时是拿TCP协议栈去和类FEC编码的算法去比，看谁的速度快。当时我们在300ms的rtt和10-20%的丢包率情况下，跑出了2MB的速度，但是，悲剧的发现，跑了10几个连接之后，一个CPU就耗完了。现在看来，如果我们是在32的内核上跑的话，性能应该会好很多。

3 重写了发现重传包丢失的函数
相比18内核（顺带说一下，有文献 已经证明18内核在发送重传包丢掉这个问题上是有bug的），这是一个很巧妙的算法，重传包以前，记住下一个要顺序发送的包（非重传包），如果这个包收到了，重传包还没有收到，那肯定就是丢掉了。

                                                                                                                   泓日天