一个std::sort 自定义比较排序函数 crash的分析过程

时间:2022-09-30 22:04:03

两年未写总结博客,今天先来练练手,总结最近遇到的一个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 != && right.c != && 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函数执行比较的时候出现了越界:

一个std::sort 自定义比较排序函数 crash的分析过程

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

  https://*.com/questions/41488093/why-do-i-get-runtime-error-when-comparison-function-in-stdsort-always-return-t

  https://en.cppreference.com/w/cpp/named_req/Compare

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

一个std::sort 自定义比较排序函数 crash的分析过程

我们的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的源码:

https://github.com/gcc-mirror/gcc/blob/gcc-4_4-branch/libstdc%2B%2B-v3/include/bits/stl_algo.h

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

https://www.cnblogs.com/AlvinZH/p/8682992.html

https://liam.page/2018/09/18/std-sort-in-STL/

简单的总结: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<typename _RandomAccessIterator, typename _Compare>
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<typename _RandomAccessIterator, typename _Tp, typename _Compare>
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的好处是可以节省边界判断。相关讨论:https://bytes.com/topic/c/answers/819473-questions-about-stl-sort