ASan failures in __std_find_trivial_unsized_impl

[StephanTLavavej]

The latest STL-ASan-CI run has failed. Most (but not all) of the failures look like:

Build setup steps:
Build steps:
Command: "C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.40.33617\bin\HostX64\x64\cl.EXE" "D:\a\_work\1\s\tests\std\tests\P0896R4_ranges_alg_find\test.cpp" "-ID:\build\out\inc" "-ID:\a\_work\1\s\llvm-project\libcxx\test\support" "-ID:\a\_work\1\s\tests\std\include" "/nologo" "/Od" "/W4" "/w14061" "/w14242" "/w14265" "/w14582" "/w14583" "/w14587" "/w14588" "/w14749" "/w14841" "/w14842" "/w15038" "/w15214" "/w15215" "/w15216" "/w15217" "/w15262" "/sdl" "/WX" "/D_ENABLE_STL_INTERNAL_CHECK" "/bigobj" "/FIforce_include.hpp" "/w14365" "/w14668" "/w15267" "/D_ENFORCE_FACET_SPECIALIZATIONS=1" "/D_STL_CALL_ABORT_INSTEAD_OF_INVALID_PARAMETER" "/w14640" "/Zc:threadSafeInit-" "/EHsc" "/MDd" "/std:c++latest" "/permissive-" "/Zc:wchar_t-" "/Zc:preprocessor" "-fsanitize=address" "/Zi" "-FeD:\build\tests\std\tests\P0896R4_ranges_alg_find\Output\07\P0896R4_ranges_alg_find.exe" "-link" "-LIBPATH:D:\build\out\lib\amd64" "-LIBPATH:C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.40.33617\lib\x64" "/MANIFEST:EMBED" "/debug"
Exit Code: 0 (0x0)
Standard Output:
--
test.cpp
--

Intellisense response file steps:
Test setup steps:
Test steps:
Test step failed unexpectedly.
Command: "D:\build\tests\std\tests\P0896R4_ranges_alg_find\Output\07\P0896R4_ranges_alg_find.exe"
Exit Code: 1 (0x1)
Standard Error:
--
=================================================================
==8792==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x00fbd52ff6c0 at pc 0x7ff6e3f380ac bp 0x00fbd52fee60 sp 0x00fbd52fee70
READ of size 32 at 0x00fbd52ff6c0 thread T0
    #0 0x7ff6e3f380ab in `anonymous namespace'::__std_find_trivial_unsized_impl<`anonymous namespace'::_Find_traits_1,unsigned char> D:\a\_work\1\s\stl\src\vector_algorithms.cpp:1864
    #1 0x7ff6e3f434eb in __std_find_trivial_unsized_1 D:\a\_work\1\s\stl\src\vector_algorithms.cpp:2083
    #2 0x7ff6e3e9ed0b in std::__std_find_trivial_unsized<char, int>(char *const, int) D:\build\out\inc\xutility:178
    #3 0x7ff6e3e97468 in std::ranges::_Find_unchecked<char *, struct std::unreachable_sentinel_t, int, struct std::identity>(char *, struct std::unreachable_sentinel_t, int const &, struct std::identity) D:\build\out\inc\xutility:6002
    #4 0x7ff6e3e90347 in std::ranges::_Find_fn::operator()<char *, struct std::unreachable_sentinel_t, int, struct std::identity>(char *, struct std::unreachable_sentinel_t, int const &, struct std::identity) const D:\build\out\inc\xutility:6053
    #5 0x7ff6e3ee773f in instantiator::call<class test::range<struct std::input_iterator_tag, struct std::pair<int, int> const, 0, 0, 0, 0, 0, 0, 0>>(void) D:\a\_work\1\s\tests\std\tests\P0896R4_ranges_alg_find\test.cpp:63
    #6 0x7ff6e3e9edf8 in with_input_ranges<struct instantiator, struct std::pair<int, int> const>::call<>(void) D:\a\_work\1\s\tests\std\include\range_algorithm_support.hpp:1175
    #7 0x7ff6e3ef7ee8 in test_in<struct instantiator, struct std::pair<int, int> const>(void) D:\a\_work\1\s\tests\std\include\range_algorithm_support.hpp:1362
    #8 0x7ff6e3e81138 in main D:\a\_work\1\s\tests\std\tests\P0896R4_ranges_alg_find\test.cpp:71
    #9 0x7ff6e3f48f08 in invoke_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:78
    #10 0x7ff6e3f48e5d in __scrt_common_main_seh D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288
    #11 0x7ff6e3f48d1d in __scrt_common_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:330
    #12 0x7ff6e3f48f7d in mainCRTStartup D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_main.cpp:16
    #13 0x7ff902124caf  (C:\Windows\System32\KERNEL32.DLL+0x180014caf)
    #14 0x7ff90359e8aa  (C:\Windows\SYSTEM32\ntdll.dll+0x18007e8aa)

Address 0x00fbd52ff6c0 is located in stack of thread T0 at offset 736 in frame
    #0 0x7ff6e3ee5e6f in instantiator::call<class test::range<struct std::input_iterator_tag, struct std::pair<int, int> const, 0, 0, 0, 0, 0, 0, 0>>(void)

[AlexGuteniev]

Recreated.

The failure originates from the reading before the range, which is intentional. We apply valid mask and ignore anything masked out:

STL/stl/src/vector_algorithms.cpp

Lines 1859 to 1865 in 191d51b

	const __m256i _Comparand = _Traits::_Set_avx(_Val);
	const intptr_t _Pad_start = reinterpret_cast<intptr_t>(_First) & _Vector_pad_mask;
	const unsigned int _Mask = _Full_mask << _Pad_start;
	_Advance_bytes(_First, -_Pad_start);
	__m256i _Data = _mm256_load_si256(static_cast<const __m256i*>(_First));
	unsigned int _Bingo = static_cast<unsigned int>(_mm256_movemask_epi8(_Traits::_Cmp_avx(_Data, _Comparand)));

This error potentially can be avoided by:

• Doing the aligning start in scalar way
• For some sizes can use masked loads if AVX2 is available
• For all sizes can use masked loads if AVX512 is available

However, this algorithm also relies on reading past the end. Here if an element is expected to be found near the end of the range, in particular the last element, the algorithm is likely to read past the end:

STL/stl/src/vector_algorithms.cpp

Lines 1878 to 1879 in 191d51b

	_Data = _mm256_load_si256(static_cast<const __m256i*>(_First));
	_Bingo = static_cast<unsigned int>(_mm256_movemask_epi8(_Traits::_Cmp_avx(_Data, _Comparand)));

The current coverage seem to miss this, but GH-4449 test can be easily altered to recreated this situation

STL/tests/std/tests/VSO_0000000_vector_algorithms/test.cpp

Lines 164 to 172 in 191d51b

	ArrayWrapper<T, 256> wrapper;
	auto& arr = wrapper.m_arr;
	constexpr int mid1 = 64;
	constexpr int mid2 = 192;
	ranges::fill(arr, arr + mid1, desired_val);
	ranges::fill(arr + mid1, arr + mid2, unwanted_val);
	ranges::fill(arr + mid2, end(arr), desired_val);

If excluding this optimization from ASAN is not an option, then we have to remove the vectorization completely, or yield to the runtime memchr / wmemchr. Need to benchmark if wmemchr is still bad for performance. I know memchr is good.

[StephanTLavavej]

@amyw-msft informed me that this appeared because DevCom-10405373 "Address sanitizer does not instrument most SSE2 intrinsics based memory accesses" was fixed in VS 2022 17.10 Preview 2.