std::nth_element crash问题

php中文网

发布时间：2016-06-13 08:50:57

1414人浏览过

来源于php中文网

原创

std::nth_element crash问题

(1) 源码：

auto less_compare = [] (const MirroringGroup& mg1, const MirroringGroup& mg2) -> bool {
 
return (mg1.usage() < mg2.usage());
};
std::nth_element(mgs->begin(), mgs->begin() + (copy_count - 1), mgs->end(), less_compare);

(2) 问题：

经常发生crash，stack如下：

#0  0x00000000004b3807 in MirroringGroup::CopyFrom (this=0x15edf20, from=...) at miuifs/miuistorage-dev/idl/proto/InternalData.pb.cc:6487
 
#1  0x000000000052bc71 in MirroringGroup::operator= (this=0x15edf20, from=...) at miuifs/miuistorage-dev/idl/proto/InternalData.pb.h:1797
#2  0x000000000052f7cb in std::swap (__a=..., __b=...) at /usr/local/include/c++/4.8.2/bits/move.h:177
#3  0x000000000052e0b0 in std::iter_swap<__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > > > (__a=..., __b=...)
at /usr/local/include/c++/4.8.2/bits/stl_algobase.h:147
#4  0x0000000000604b11 in std::__unguarded_partition<__gnu_cxx::__normal_iterator >, MirroringGroup, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, const MirroringGroup &, miuifs::BlockManager::__lambda101) (__first=..., __last=..., __pivot=..., __comp=...) at /usr/local/include/c++/4.8.2/bits/stl_algo.h:2270
#5  0x0000000000603c1b in std::__unguarded_partition_pivot<__gnu_cxx::__normal_iterator >, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, miuifs::BlockManager::__lambda101) (
__first=..., __last=..., __comp=...) at /usr/local/include/c++/4.8.2/bits/stl_algo.h:2296
#6  0x0000000000603408 in std::__introselect<__gnu_cxx::__normal_iterator >, long int, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, long, miuifs::BlockManager::__lambda101) (__first=..., __nth=..., __last=..., __depth_limit=2, 
__comp=...) at /usr/local/include/c++/4.8.2/bits/stl_algo.h:2394
#7  0x0000000000602c95 in std::nth_element<__gnu_cxx::__normal_iterator >, miuifs::BlockManager::ChooseWritableMirroringGroups(std::vector*, int)::__lambda101>(__gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, __gnu_cxx::__normal_iterator > >, miuifs::BlockManager::__lambda101) (__first=..., __nth=..., __last=..., __comp=...)
at /usr/local/include/c++/4.8.2/bits/stl_algo.h:5417
#8  0x000000000060039c in miuifs::BlockManager::ChooseWritableMirroringGroups (this=0x118abe0 , mgs=0x7fffeb9f4140, 
copy_count=2) at miuifs/miuistorage-dev/BlockManager.cc:391
#9  0x00000000005ff9cf in miuifs::BlockManager::NewBlock (this=0x118abe0 ) at miuifs/miuistorage-dev/BlockManager.cc:331
#10 0x00000000005fed63 in miuifs::BlockManager::AcquireBlock (this=0x118abe0 , attribute=...)
at miuifs/miuistorage-dev/BlockManager.cc:243

(3) 查找问题：

问题一直出现在std::nth_element中，开始没有想到是STL的问题，一直没有很好的解决办法，后来通过阅读STL源码找到原因在/usr/local/include/c++/4.8.2/bits/stl_algo.h中：

template
 
inline _RandomAccessIterator
__unguarded_partition_pivot(_RandomAccessIterator __first,
_RandomAccessIterator __last, _Compare __comp)
{
_RandomAccessIterator __mid = __first + (__last - __first) / 2;
std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),
__comp);
return std::__unguarded_partition(__first + 1, __last, *__first, __comp);
}

__move_median_to_first函数的作用是将 __first +1 , __mid, (__last - 2) 中中间大小的值和 __first交换。但是却忽略了__mid,(__last - 2) 指向相同迭代器的情况，如果输入时情况如下：

经过__move_median_to_first之后的结果如下：

此时__first指向了最大的值。然后看std::__unguarded_partition的实现，在2263行__comp(*__first, __pivot))永远返回true，导致++__first一直执行而访问了非法内存。

template
 
_RandomAccessIterator
__unguarded_partition(_RandomAccessIterator __first,
_RandomAccessIterator __last,
const _Tp& __pivot, _Compare __comp)
{
while (true)
{
while (__comp(*__first, __pivot))
++__first;
--__last;
while (__comp(__pivot, *__last))
--__last;
if (!(__first < __last))
return __first;
std::iter_swap(__first, __last);
++__first;
}
}