std::nth_element のクラッシュ問題_PHP チュートリアル-PHPチュートリアル-php.cn

std::nth_element のクラッシュ問題_PHP チュートリアル

WBOY

リリース： 2016-07-12 09:04:46

オリジナル

1091 人が閲覧しました

std::nth_element クラッシュ問題

(1) ソースコード:

<ol style="margin:0 1px 0 0px;padding-left:40px;" start="1" class="dp-css"><li>auto less_compare = [] (const MirroringGroup& mg1, const MirroringGroup& mg2) -> bool {<br /> </li><li>return (mg1.usage() < mg2.usage());<br /></li><li>};<br /></li><li>std::nth_element(mgs->begin(), mgs->begin() + (copy_count - 1), mgs->end(), less_compare); </li></ol>

ログイン後にコピー

(2) 問題:

クラッシュが頻繁に発生し、スタックは次のとおりです:

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

ログイン後にコピー

(3) 問題を見つけます:

std::nth_element で問題が発生し続けます。最初は STL の問題だとは思わなかったので、適切な解決策がありませんでした。後で、/usr/local/include/c++ の STL ソースコードを読んで理由を見つけました。 /4.8.2/bits/stl_algo.h:

<ol style="margin:0 1px 0 0px;padding-left:40px;" start="1" class="dp-css"><li>template<typename _RandomAccessIterator, typename _Compare><br /> </li><li>inline _RandomAccessIterator<br /></li><li>__unguarded_partition_pivot(_RandomAccessIterator __first,<br /></li><li>_RandomAccessIterator __last, _Compare __comp)<br /></li><li>{<br /></li><li>_RandomAccessIterator __mid = __first + (__last - __first) / 2;<br /></li><li>std::__move_median_to_first(__first, __first + 1, __mid, (__last - 2),<br /></li><li>__comp);<br /></li><li>return std::__unguarded_partition(__first + 1, __last, *__first, __comp);<br /></li><li>} </li></ol>

ログイン後にコピー

__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 が常に実行され、不正なメモリがアクセスされます。

<ol style="margin:0 1px 0 0px;padding-left:40px;" start="1" class="dp-css"><li>template<typename _RandomAccessIterator, typename _Tp, typename _Compare><br /> </li><li>_RandomAccessIterator<br /></li><li>__unguarded_partition(_RandomAccessIterator __first,<br /></li><li>_RandomAccessIterator __last,<br /></li><li>const _Tp& __pivot, _Compare __comp)<br /></li><li>{<br /></li><li>while (true)<br /></li><li>{<br /></li><li>while (__comp(*__first, __pivot))<br /></li><li>++__first;<br /></li><li>--__last;<br /></li><li>while (__comp(__pivot, *__last))<br /></li><li>--__last;<br /></li><li>if (!(__first < __last))<br /></li><li>return __first;<br /></li><li>std::iter_swap(__first, __last);<br /></li><li>++__first;<br /></li><li>}<br /></li><li>} </li></ol>

ログイン後にコピー

(4) 解決策:

Google で以下のリンクを見つけたところ、これは確かに STL のバグであり、C++ をアップグレードすることによってのみ解決できることがわかりました。

https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=732042