<vector>: _Copy_vbool() mishandles vector<bool>s of size 32 and 64, revealed by constexpr Clang #5345
Description
Found by an upcoming libcxx test update.
Reduced repro
D:\GitHub\STL\out\x64>type meow.cpp
#include <algorithm>
#include <cstddef>
#include <vector>
using namespace std;
template <size_t N>
constexpr bool test() {
const vector<bool> src(N, true);
vector<bool> dst(N, false);
copy(src.begin(), src.end(), dst.begin());
return src == dst;
}
int main() {
static_assert(test<32>());
static_assert(test<64>());
}Size 32 error
D:\GitHub\STL\out\x64>clang-cl /EHsc /nologo /W4 /std:c++20 /MT /Od meow.cpp
meow.cpp(15,19): error: static assertion expression is not an integral constant expression
15 | static_assert(test<32>());
| ^~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\vector(3819,59): note: shift count 32 >= width of type '_Vbase' (aka 'unsigned int')
(32 bits)
3819 | const auto _LastSourceMask = static_cast<_Vbase>(-1) >> (_VBITS - _Last._Myoff);
| ^
D:\GitHub\STL\out\x64\out\inc\xutility(4833,16): note: in call to
'_Copy_vbool<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[1]#0}[0], 0}},
{{{}, &{*new unsigned int[1]#0}[1], 0}}, {{{{}, &{*new unsigned int[1]#1}[0], 0}}})'
4833 | return _STD _Copy_vbool(_First, _Last, _Dest);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
1928 | #define _STD ::std::
| ^
D:\GitHub\STL\out\x64\out\inc\xutility(4865,31): note: in call to
'_Copy_unchecked<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[1]#0}[0], 0}},
{{{}, &{*new unsigned int[1]#0}[1], 0}}, {{{{}, &{*new unsigned int[1]#1}[0], 0}}})'
4865 | _STD _Seek_wrapped(_Dest, _STD _Copy_unchecked(_UFirst, _ULast, _STD move(_UDest)));
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
1928 | #define _STD ::std::
| ^
meow.cpp(10,5): note: in call to 'copy<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[1]#0}[0], 0}},
{{{}, &{*new unsigned int[1]#0}[1], 0}}, {{{{}, &{*new unsigned int[1]#1}[0], 0}}})'
10 | copy(src.begin(), src.end(), dst.begin());
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meow.cpp(15,19): note: in call to 'test<32ULL>()'
15 | static_assert(test<32>());
| ^~~~~~~~~~
This correctly points to _LastSourceMask which is performing a forbidden full shift:
Lines 3817 to 3820 in 1f6e5b1
It looks like we can patch this with the same pattern used for _FirstDestMask, but I haven't exhaustively verified this.
Size 64 error
meow.cpp(16,19): error: static assertion expression is not an integral constant expression
16 | static_assert(test<64>());
| ^~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\vector(3967,25): note: read of dereferenced one-past-the-end pointer is not allowed in a
constant expression
3967 | *_VbDest = (*_VbDest & _LastDestMask) | _CarryVal;
| ^
D:\GitHub\STL\out\x64\out\inc\xutility(4833,16): note: in call to
'_Copy_vbool<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[2]#0}[0], 0}},
{{{}, &{*new unsigned int[2]#0}[2], 0}}, {{{{}, &{*new unsigned int[2]#1}[0], 0}}})'
4833 | return _STD _Copy_vbool(_First, _Last, _Dest);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
1928 | #define _STD ::std::
| ^
D:\GitHub\STL\out\x64\out\inc\xutility(4865,31): note: in call to
'_Copy_unchecked<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[2]#0}[0], 0}},
{{{}, &{*new unsigned int[2]#0}[2], 0}}, {{{{}, &{*new unsigned int[2]#1}[0], 0}}})'
4865 | _STD _Seek_wrapped(_Dest, _STD _Copy_unchecked(_UFirst, _ULast, _STD move(_UDest)));
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
1928 | #define _STD ::std::
| ^
meow.cpp(10,5): note: in call to 'copy<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[2]#0}[0], 0}},
{{{}, &{*new unsigned int[2]#0}[2], 0}}, {{{{}, &{*new unsigned int[2]#1}[0], 0}}})'
10 | copy(src.begin(), src.end(), dst.begin());
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meow.cpp(16,19): note: in call to 'test<64ULL>()'
16 | static_assert(test<64>());
| ^~~~~~~~~~
2 errors generated.
This one's sneaky because above there's a runtime-only optimization that absorbs this case:
Lines 3861 to 3865 in 1f6e5b1
Commenting it out allows runtime execution to follow the same path as constexpr evaluation, and ASan can notice the same badness that constexpr does here.
After the runtime-only optimization, things start looking bad. It starts by talking about having "Unaligned _VbFirst and _VbLast":
Lines 3897 to 3898 in 1f6e5b1
But in this case we're not unaligned - _Dest._Myoff is equal to _First._Myoff. So we're not _IsRightShift, but we're also not performing a left shift either. So the else block appears to perform a forbidden full shift:
Lines 3934 to 3940 in 1f6e5b1
When I debugged into this, I saw that _SourceShift was 0, so _CarryShift was 32. I'm not sure why constexpr evaluation didn't stop right here.
In any event, things get worse from here. Eventually we get a "read of dereferenced one-past-the-end pointer".
I think this one needs more significant surgery than just handling the forbidden full shift. It looks like we need an entire third case handling "no shift".