两年未写总结博客，今天先来练练手，总结最近遇到的一个crash case。

　注意：以下的分析都基于GCC4.4.6

一、解决crash

    我们有一个复杂的排序，涉及到很多个因子，使用自定义排序函数的std::sort做排序。Compare函数类似下文的伪代码：

bool compare(const FakeObj& left, const FakeObj& right) {    if (left.a != right.a) {        return left.a > right.a;    }    if (left.b != right.b) {        return left.b > right.b;    }     ....}

    后来，我们给排序函数加了更多的复杂逻辑：

bool compare(const FakeObj& left, const FakeObj& right) {    if (left.a != right.a) {        return left.a > right.a;    }    if (left.b != right.b) {        return left.b > right.b;    }    if (left.c != 0 && right.c != 0 && left.c != right.c) {        // 当C属性都存在的时候使用C属性做比较        return left.c > right.c;    }    if (left.d != right.d) {        return left.d > right.d;    }    ....}

    服务发布之后，进程就开始出现偶现的crash，使用gdb查看，调用堆栈如下：

/usr/lib/gcc/x86_64-redhat-linux/4.4.6/../../../../include/c++/4.4.6/bits/stl_algo.h:5260/usr/lib/gcc/x86_64-redhat-linux/4.4.6/../../../../include/c++/4.4.6/bits/stl_algo.h:2194/usr/lib/gcc/x86_64-redhat-linux/4.4.6/../../../../include/c++/4.4.6/bits/stl_algo.h:2161/usr/lib/gcc/x86_64-redhat-linux/4.4.6/../../../../include/c++/4.4.6/bits/stl_algo.h:2084

    crash发生位置：在标准库调用compare函数执行比较的时候出现了越界：

 

    这时候，开始怀疑compare函数没有按照标准库的规范实现，查看相关资源：

　　

　　

       仔细看官方的文档可以发现：

 

    我们的compare函数对c属性的判断，没有严格遵守可传递性：if comp(a,b)==true and comp(b,c)==true then comp(a,c)==true。假设存在A、B、C三个对象，

1、A、B对象有属性c，且A.c > B.c，按照我们的比较函数，这时候A>B；

2、C对象没有c属性，且C.d>A.d，这时候C>A;

3、C对象没有c属性，且B.d < C.d，这时候B>C

综上，A>B 且 B>C，但是C>A，这就违反了strict weak ordering的transitivity。

    到这里，我们的case就解决了，但实际上，基于以下几个原因，这个case花费了很长的时间：

1、  我们的compare函数的代码不是逐步添加的，而是一次性写完，导致没有立即怀疑c属性的比较有bug；

2、  对官方文档不够重视，只关注到了非对称性：comp(a,b) ==true then comp(b,a)==false，忽略了可传递性；

辗转了很久才注意到传递性要求。后续在解决问题时，应该更细致，不放过每一个细节。

二、crash更深层的原因

    业务上的crash问题已经解决，但crash的直接原因是什么还是未知的，需要继续探索。

    找到std::sort的源码：

    再结合其他人分析std::sort源码的总结：

    简单的总结：std::sort为了提高效率，综合了快排、堆排序、插入排序，可以分为两阶段：

1、  快排+堆排序（__introsort_loop），对于元素个数大于_S_threshold的序列，执行快排，当快排的递归深入到一定层次（__depth_limit）时，不再递归深入，对待排序元素执行堆排序；对于元素个数小于_S_threshold的序列则不处理，交给后面的插入排序。

2、  插入排序（__final_insertion_sort），当元素个数小于_S_threshold时，执行普通的插入排序（__insertion_sort）；当大于_S_threshold时，执行两批次的插入排序，首先是普通的插入排序排[0, _S_threshold)；然后是无保护的插入排序（__unguarded_insertion_sort），从_S_threshold位置开始排，直到end，注意这里可能还会处理到_S_threshold之前的元素（因为这个函数只用比较结果来判断是否停止，而不强制要求在某个位置点上停止）。

    我们的crash发生在__unguarded_insertion_sort阶段，也就是无保护的插入排序。看下这块的代码：

/// This is a helper function for the sort routine.template
     
      inline void __unguarded_insertion_sort(_RandomAccessIterator __first,               _RandomAccessIterator __last, _Compare __comp){    typedef typename iterator_traits<_RandomAccessIterator>::value_type _ValueType;    for (_RandomAccessIterator __i = __first; __i != __last; ++__i)        std::__unguarded_linear_insert(__i, _ValueType(*__i), __comp);    }/// This is a helper function for the sort routine.template
      
       void __unguarded_linear_insert(_RandomAccessIterator __last, _Tp __val,              _Compare __comp) {    _RandomAccessIterator __next = __last;    --__next;    while (__comp(__val, *__next)) {        *__last = *__next;        __last = __next;        --__next;    }    *__last = __val;}
      
     

    可以看到，__unguarded_linear_insert 函数比较的终止条件是compare函数返回false，否则就一直排序下去，这里之所以可以这么做，是因为之前的快排+堆排代码保证了[0,X)序列的元素肯定大于（假设是递减排序）[X, end)，其中0<X<=_S_threshol，一旦无法保证，则会导致--__next越界，最终导致crash。

    再回到我们的crash case，因为compare函数不满足传递性，虽然[0,X)区间的所有元素都大于X，且(X,end]区间的所有元素都小于X，但是并不能保证(X,end]的元素都小于[0,X)区间的元素，在__unguarded_linear_insert函数里，对(X,end]区间的元素执行插入排序时， 某元素大于[0,X)区间的所有元素，这时候就发生了越界crash。

    这里使用__unguarded_insertion_sort而不是仅使用__insertion_sort的好处是可以节省边界判断。相关讨论：