Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

<vector>: _Copy_vbool() mishandles vector<bool>s of size 32 and 64, revealed by constexpr Clang #5345

Open
StephanTLavavej opened this issue Mar 18, 2025 · 2 comments · May be fixed by #5347
Open

<vector>: _Copy_vbool() mishandles vector<bool>s of size 32 and 64, revealed by constexpr Clang #5345

StephanTLavavej opened this issue Mar 18, 2025 · 2 comments · May be fixed by #5347
Labels
bug Something isn't working

Comments

@StephanTLavavej
Copy link
Member

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:

STL/stl/inc/vector

Lines 3817 to 3820 in 1f6e5b1

const auto _FirstSourceMask = static_cast<_Vbase>(-1) << _First._Myoff;
const auto _FirstDestMask = _Dest._Myoff == 0 ? 0 : (static_cast<_Vbase>(-1) >> (_VBITS - _Dest._Myoff));
const auto _LastSourceMask = static_cast<_Vbase>(-1) >> (_VBITS - _Last._Myoff);
const auto _LastDestMask = static_cast<_Vbase>(-1) << _DestEnd._Myoff;

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:

STL/stl/inc/vector

Lines 3861 to 3865 in 1f6e5b1

#if _HAS_CXX20
if (!_STD is_constant_evaluated())
#endif
{
// If _First and _Dest have matching char alignment, use memmove

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":

STL/stl/inc/vector

Lines 3897 to 3898 in 1f6e5b1

// Unaligned _VbFirst and _VbLast require a two step copy with carry
if (_IsRightShift) {

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:

STL/stl/inc/vector

Lines 3934 to 3940 in 1f6e5b1

} else {
const auto _SourceShift = _Dest._Myoff - _First._Myoff;
const auto _CarryShift = _VBITS - _SourceShift;
const auto _FirstSourceVal = (*_VbFirst & _FirstSourceMask) << _SourceShift;
*_VbDest = (*_VbDest & _FirstDestMask) | _FirstSourceVal;
auto _CarryVal = *_VbFirst >> _CarryShift;

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".
@StephanTLavavej StephanTLavavej added the bug Something isn't working label Mar 18, 2025
@AlexGuteniev
Copy link
Contributor

Size 32 fix seems to be right.

Also found an ICE. Just try with 33:

#include <cassert>
#include <iostream>

#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<33>());
}
example.cpp
<source>(19): fatal error C1001: Internal compiler error.
(compiler file 'D:\a\_work\1\s\src\vctools\Compiler\CxxFE\sl\p1\c\constexpr\constexpr.cpp', line 9027)
 To work around this problem, try simplifying or changing the program near the locations listed above.
If possible please provide a repro here: https://developercommunity.visualstudio.com 
Please choose the Technical Support command on the Visual C++ 
 Help menu, or open the Technical Support help file for more information
Compiler returned: 2

https://godbolt.org/z/ndoG5T1cG

@AlexGuteniev AlexGuteniev linked a pull request Mar 19, 2025 that will close this issue
Open
@AlexGuteniev
Copy link
Contributor

DevCom-10875249 reported

@StephanTLavavej StephanTLavavej mentioned this issue Mar 20, 2025
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Handle aligned vector<bool> in constexpr copy() properly AlexGuteniev/STL
2 participants
@AlexGuteniev @StephanTLavavej