Revert product changes for `find_end` vectorization #5041

StephanTLavavej · 2024-10-25T20:19:53Z

After we merged #4943 (find_end vectorization), @CaseyCarter noticed that the STL-ASan-CI began failing with container-overflow errors.

This reverts the product code changes from #4943 but allows its benchmark and test changes to stand. It also keeps a control flow refactoring of __std_search_impl in stl/src/vector_algorithms.cpp, as I'm convinced it's a lossless transformation.

🙀 Test Failure Log

This can be found by downloading a test failure log as an XML artifact, then running my tools\scripts\print_failures.py to decode it. (Thanks again @CaseyCarter for noticing that the artifact captured the log, which was too big for the usual Azure Pipelines UI to display.)

Click to expand test failure log:

name: std.tests/VSO_0000000_vector_algorithms
output: Build setup steps:
Build steps:
Command: "C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.42.34430\bin\HostX64\x64\cl.EXE" "D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\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" "/EHsc" "/MD" "/std:c++14" "/w14640" "/Zc:threadSafeInit-" "-fsanitize=address" "/Zi" "-FeD:\build\tests\std\tests\VSO_0000000_vector_algorithms\Output\02\VSO_0000000_vector_algorithms.exe" "-link" "-LIBPATH:D:\build\out\lib\amd64" "-LIBPATH:C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.42.34430\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\VSO_0000000_vector_algorithms\Output\02\VSO_0000000_vector_algorithms.exe"
Exit Code: 1 (0x1)
Standard Output:
--
This is a randomized test.
DO NOT IGNORE/RERUN ANY FAILURES.
You must report them to the STL maintainers.
Seed vector: 2011068952,1800349505,1657366820,3107043617,1651127980,3260046398,15400191,1873058321,3237234911,3826518008,2914576800,3023067651,2863793863,3176310933,1035976458,1584814113,3645761852,2603711012,398302033,3220332235,3479953918,1627247034,2495544484,3808007759,2668160509,3030858208,1991303010,2331134663,3195459495,1052571626,2267005773,470620865,2856996601,4164755686,3078164348,3648764572,2646527408,3337787984,116391692,2229707523,2856658210,1931813679,292282476,2109247529,3829417261,2935829019,2982250063,622420786,4264727969,4058172462,4079835062,321192426,297423852,4245592591,1875091205,1857304947,1613956918,831694263,968329006,1169475324,1916357803,2982738080,2406543901,3139968786,202519371,246873437,1200258812,1707766541,857178778,3913697687,1530322986,1908672360,835051880,534500434,2428664387,3411225464,123034167,2559113815,3342239464,19158409,4147883316,1433634373,768858233,2449113694,325546895,2700415623,3938328643,3073210044,2285681681,903015171,2179344742,736290914,2905129771,2131266680,2575814788,4136725403,1417281482,3100175328,408599776,3509282416,3758827912,962080411,970932244,3088371761,3925131815,3492369811,758944521,2184515348,2655835272,2861927756,2813182753,509451779,3735905578,2364982079,402539953,1105920053,263634128,875795601,1429437621,1869601088,4142129620,1986893578,2116566250,2950645724,3190596778,1414589206,2642106073,532599899,1799822179,3668986244,3233127745,2791600445,2901570897,458602993,1854330026,424986833,111687351,1606274551,758460865,134981425,1188604210,3549331806,3282138848,773561944,1361887694,22402482,4114180469,464729789,3312719481,1504787436,3872857272,4191435540,1467497249,1319472103,3405620429,2259291454,120503514,2130234242,1863918787,368730050,3525779885,448738331,804249522,2913226562,2325961125,1827461579,1382068634,2912280469,1472785127,822245788,397465641,3233808011,1008885528,1013257583,1938623677,4046731228,516932277,880706749,1298926651,172472773,2462792547,1316302827,800137223,3427808702,950219626,1949787057,1786531086,4265085186,1071593515,1169558681,2852875651,2370238476,769898125,4066886242,2653211205,1428998300,1618935610,114687281,728862980,256932986,1348132859,1551744971,55423173,3562735612,4001567145,2237794644,3244335815,3902729622,1695462421,3742641501,2732329923,1087272810,1957614825,2566432756,4032405094,983038140,3912717552,2456021457,1696554340,3090374432,3736030988,2347373906,640059456,3860235184,742790861,4067577861,3602023206,1297314135,1416388059,1519067742,756191024,2385381113,748996437,1265098562,3569805643,2514002747,276138074,4094160565,3330487062,758482058,3593784580,1812809580,766921760,3381065353,740117692,1950419051,4010365163,3756530706,8765525,1613542144,2851910570,2449425820,1609964223,3573884803,1280740777,16387889,3666837180,361397975,3006417432,2554573412,3185378302,1238586497,3879295604,4084880397,2703845395,571910872,466229177,848239127,929961539,846127199,1890172138,2792640325,1358476327,2782571701,3026179870,807806587,3728639638,814364754,1380231081,1906622436,2108285195,1463027426,396226289,4080045934,491189244,527127807,3150184362,1019696525,2618985245,4009715955,985590636,1320516031,551558302,1779073836,2940974049,4175735776,828939631,2557145166,691689456,3148180338,544628276,282271145,414941916,4121253749,2536515091,1459981188,828724823,1191095279,2749771357,3369369760,1270935465,1820451023,3511452484,121616160,1606010456,3726136436,139266204,27082308,3863850034,2472964748,3522249275,3487409475,127501491,848269134,3553350081,1286525666,1281783698,1382666568,3893982171,2008905543,2648155505,2889575531,814423046,2165914790,108705247,184272403,3646804496,634981345,1882357081,3676732359,214693199,306588649,260299410,4232974665,1899148162,208127625,1904379070,3584762883,3716800050,65955686,43590010,4129309316,4124814887,1286267047,1827185369,2465767878,3643904392,2149954499,295431555,259439948,4046757173,2271350434,916327116,905287810,499631451,4236789356,2954710849,4085008392,2747657282,1275866175,3108735711,1206061667,198133870,927530334,3966029148,2653378031,72299589,3912197471,2102990358,2764342096,3229134931,3156320293,1341610995,3192927223,2337105174,2110060083,1489144010,459911385,550490213,692457889,2624799649,11334890,2406353028,1915807794,605618613,513705456,3864380873,4199956147,2218965101,469655204,864958714,3806644643,834077491,1742017098,2801253004,3860780662,687406354,344065831,2754819679,3174813101,656105269,3968154028,288933350,533773015,2425276143,436291995,3965676620,3312810081,2261859312,2503949923,1605787302,4233843984,1472384500,1473765606,1614887789,2861684869,56448885,1323164365,3764144926,3017510408,2884833810,3861436053,2308726463,500953552,69562809,2415295656,918099702,809684240,1263182173,113151192,906990781,1363217266,3470428302,2533453819,2612193736,3516742804,3710800193,1390981148,3680577752,2772525961,365907877,4249820706,411846345,3397228791,1645638854,884959290,3961736111,3041490195,3734608541,1475309574,36023412,3746665600,1490872667,2131541876,18941448,3640559111,1006035896,941539141,1920429648,687252276,1185217618,3469886766,2570745178,3081518363,1490826935,2617926642,2869511626,2073322834,2808967644,4079209883,2343264819,845969595,4044988658,3454771801,780180754,4263566314,926085622,713064173,3430671900,1778663272,3438181157,412982688,2193876743,1146348340,3222478913,2287237156,1119453240,1734767354,1504208915,3382158195,3421396733,1416047329,733965968,566182400,1222722879,1325861379,1230646915,1518020050,2083111034,1717616525,426871704,3335070254,1420497405,1291879419,4206696464,2465491358,3649624428,3280323781,184482236,4073079772,3807972274,1943983621,93486245,351632978,2161829867,4244967171,4009511684,163510711,206317229,3757585980,3017339704,740813614,3938928483,1141410889,3908464433,3703919474,3784465891,1432087571,1757544277,2904516984,929626878,1759094921,442618468,1470189625,4217400554,1945688789,471523255,3709742932,3677057809,2844062185,2710486911,3218476143,944822773,3584262299,325772606,129803551,1991650842,2369193260,2968008293,50135414,721455388,2191756448,2582620022,2413974665,1302297283,3688522746,4056322878,1669505827,1897232925,3976725825,165337602,4221524198,2316631291,3588144051,1389323383,1747379036,876044655,1031700110,337344199,4273931236,3107679220,4033981379,4271298648,2578611637,498398443,2572783817,172908045,641766931,502499022,2109447611,14925703,970442322,985368944,3224023473,1216830302,12038398,2425830969,376680416,3244397628,1304822910,1060196594,643517479,61412589,2091368317,3456531160,2363326553,1621816927,3356831066,1944015571,3744267984,215429163,4273416040,2414487240,2196848132,3568580393,180029871,3913888601,3697765551,1855512809,3160380217,2928789472,2667895349,3891968106,1038151028,
--
Standard Error:
--
=================================================================
==11852==ERROR: AddressSanitizer: container-overflow on address 0x12c416ba0f52 at pc 0x7ff71f1748fb bp 0x00d79f2fd340 sp 0x00d79f2fd348
READ of size 16 at 0x12c416ba0f52 thread T0
    #0 0x7ff71f1748fa in ``anonymous namespace'::__std_find_end_impl<`anonymous namespace'::_Find_traits_1,unsigned char>'::`33'::<lambda_3>::operator() D:\a\_work\1\s\stl\src\vector_algorithms.cpp:3788
    #1 0x7ff71f14ef9e in `anonymous namespace'::__std_find_end_impl<`anonymous namespace'::_Find_traits_1,unsigned char> D:\a\_work\1\s\stl\src\vector_algorithms.cpp:3819
    #2 0x7ff71f17b698 in __std_find_end_1 D:\a\_work\1\s\stl\src\vector_algorithms.cpp:3999
    #3 0x7ff71e9fca30 in std::_Find_end_vectorized<char const, char const>(char const *const, char const *const, char const *const, unsigned __int64) D:\build\out\inc\algorithm:202
    #4 0x7ff71ea94cd2 in std::find_end<class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, struct std::equal_to<void>>(class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, struct std::equal_to<void>) D:\build\out\inc\algorithm:3220
    #5 0x7ff71ea9483d in std::find_end<class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>>(class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>, class std::_Vector_const_iterator<class std::_Vector_val<struct std::_Simple_types<char>>>) D:\build\out\inc\algorithm:3307
    #6 0x7ff71f05bfef in test_case_search<char>(class std::vector<char, class std::allocator<char>> const &, class std::vector<char, class std::allocator<char>> const &) D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:328
    #7 0x7ff71f0994a6 in test_search<char>(class std::mersenne_twister_engine<unsigned __int64, 64, 312, 156, 31, -5403634167711393303, 29, 6148914691236517205, 17, 8202884508482404352, 37, -2270628950310912, 43, 6364136223846793005> &) D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:372
    #8 0x7ff71e9b1995 in test_vector_algorithms(class std::mersenne_twister_engine<unsigned __int64, 64, 312, 156, 31, -5403634167711393303, 29, 6148914691236517205, 17, 8202884508482404352, 37, -2270628950310912, 43, 6364136223846793005> &) D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:955
    #9 0x7ff71e9b5b67 in <lambda_24b1af959ca32f2eb49b34af9c40a73a>::operator() D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:1368
    #10 0x7ff71eae0dfb in run_randomized_tests_with_different_isa_levels<<lambda_24b1af959ca32f2eb49b34af9c40a73a> > D:\a\_work\1\s\tests\std\include\test_vector_algorithms_support.hpp:55
    #11 0x7ff71e9b5aee in main D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:1367
    #12 0x7ff71f17fb1b in invoke_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:78
    #13 0x7ff71f17fb1b in __scrt_common_main_seh D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288
    #14 0x7ffb0cd64caf  (C:\Windows\System32\KERNEL32.DLL+0x180014caf)
    #15 0x7ffb0da5ecda  (C:\Windows\SYSTEM32\ntdll.dll+0x18007ecda)
0x12c416ba0f52 is located 18 bytes inside of 200-byte region [0x12c416ba0f40,0x12c416ba1008)
allocated by thread T0 here:
    #0 0x7ff71f17ece5 in operator new(unsigned __int64) D:\a\_work\1\s\src\vctools\asan\llvm\compiler-rt\lib\asan\asan_win_new_scalar_thunk.cpp:40
    #1 0x7ff71f0f2de2 in std::_Default_allocate_traits::_Allocate(unsigned __int64) D:\build\out\inc\xmemory:136
    #2 0x7ff71e9c4075 in std::_Allocate<16, struct std::_Default_allocate_traits>(unsigned __int64) D:\build\out\inc\xmemory:256
    #3 0x7ff71f11fadf in std::allocator<char>::allocate(unsigned __int64) D:\build\out\inc\xmemory:986
    #4 0x7ff71e9c4176 in std::_Allocate_at_least_helper<class std::allocator<char>>(class std::allocator<char> &, unsigned __int64 &) D:\build\out\inc\xmemory:2221
    #5 0x7ff71ea0ef22 in std::vector<char, class std::allocator<char>>::_Reallocate<0>(unsigned __int64 &) D:\build\out\inc\vector:1636
    #6 0x7ff71f134824 in std::vector<char, class std::allocator<char>>::reserve(unsigned __int64) D:\build\out\inc\vector:1713
    #7 0x7ff71f099366 in test_search<char>(class std::mersenne_twister_engine<unsigned __int64, 64, 312, 156, 31, -5403634167711393303, 29, 6148914691236517205, 17, 8202884508482404352, 37, -2270628950310912, 43, 6364136223846793005> &) D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:362
    #8 0x7ff71e9b1995 in test_vector_algorithms(class std::mersenne_twister_engine<unsigned __int64, 64, 312, 156, 31, -5403634167711393303, 29, 6148914691236517205, 17, 8202884508482404352, 37, -2270628950310912, 43, 6364136223846793005> &) D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:955
    #9 0x7ff71e9b5b67 in <lambda_24b1af959ca32f2eb49b34af9c40a73a>::operator() D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:1368
    #10 0x7ff71eae0dfb in run_randomized_tests_with_different_isa_levels<<lambda_24b1af959ca32f2eb49b34af9c40a73a> > D:\a\_work\1\s\tests\std\include\test_vector_algorithms_support.hpp:55
    #11 0x7ff71e9b5aee in main D:\a\_work\1\s\tests\std\tests\VSO_0000000_vector_algorithms\test.cpp:1367
    #12 0x7ff71f17fb1b in invoke_main D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:78
    #13 0x7ff71f17fb1b in __scrt_common_main_seh D:\a\_work\1\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl:288
    #14 0x7ffb0cd64caf  (C:\Windows\System32\KERNEL32.DLL+0x180014caf)
    #15 0x7ffb0da5ecda  (C:\Windows\SYSTEM32\ntdll.dll+0x18007ecda)
HINT: if you don't care about these errors you may set ASAN_OPTIONS=detect_container_overflow=0.
If you suspect a false positive see also: https://github.com/google/sanitizers/wiki/AddressSanitizerContainerOverflow.
SUMMARY: AddressSanitizer: container-overflow D:\a\_work\1\s\stl\src\vector_algorithms.cpp:3788 in ``anonymous namespace'::__std_find_end_impl<`anonymous namespace'::_Find_traits_1,unsigned char>'::`33'::<lambda_3>::operator()
Shadow bytes around the buggy address:
  0x12c416ba0c80: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x12c416ba0d00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x12c416ba0d80: fd fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x12c416ba0e00: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x12c416ba0e80: fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa fa
=>0x12c416ba0f00: fa fa fa fa fa fa fa fa 00 00[07]fc fc fc fc fc
  0x12c416ba0f80: fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc fc
  0x12c416ba1000: fc fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x12c416ba1080: fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd fd
  0x12c416ba1100: fd fd fd fd fd fd fd fd fd fa fa fa fa fa fa fa
  0x12c416ba1180: fa fa fa fa fa fa fa fa fd fd fd fd fd fd fd fd
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==11852==ABORTING
--

✅ ASan Validation Incantations

Here's how to build the STL with ASan enabled (-DSTL_ASAN_BUILD=ON), then run the test with ASan enabled (-Dtags=ASAN):

title x64
"C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Auxiliary\Build\vcvarsall.bat" x64
set STL=D:\GitHub\STL
pushd %STL%
git clean -x -d -f
cmake --preset x64 -DSTL_ASAN_BUILD=ON && cmake --build --preset x64
pushd out\x64
python tests\utils\stl-lit\stl-lit.py -o testing_x64.log -Dtags=ASAN --order=random %STL%\tests\std\tests\VSO_0000000_vector_algorithms

This was GH 4943.

…t#5041)" This reverts commit ca1553d.

Revert product changes for find_end vectorization.

f22a04d

This was GH 4943.

StephanTLavavej added bug Something isn't working high priority Important! labels Oct 25, 2024

StephanTLavavej assigned CaseyCarter Oct 25, 2024

StephanTLavavej requested a review from a team as a code owner October 25, 2024 20:19

CaseyCarter approved these changes Oct 25, 2024

View reviewed changes

CaseyCarter removed their assignment Oct 25, 2024

StephanTLavavej mentioned this pull request Oct 24, 2024

Maintainer priorities #4700

Open

StephanTLavavej self-assigned this Oct 25, 2024

StephanTLavavej merged commit ca1553d into microsoft:main Oct 26, 2024
39 checks passed

StephanTLavavej deleted the step-out-of-the-path-of-collapse branch October 26, 2024 00:09

CaseyCarter mentioned this pull request Oct 14, 2024

Sporadic STL-ASan-CI failures mentioning __asan_wrap_memmove #4696

Open

AlexGuteniev added a commit to AlexGuteniev/STL that referenced this pull request Oct 26, 2024

Revert "Revert product changes for find_end vectorization (microsof…

a0e3cfc

…t#5041)" This reverts commit ca1553d.

AlexGuteniev mentioned this pull request Oct 26, 2024

Vectorize find_end, make sure ASan passes #5042

Merged

MahmoudGSaleh added the ASan Address Sanitizer label Oct 30, 2024

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Revert product changes for `find_end` vectorization #5041

Revert product changes for `find_end` vectorization #5041

Uh oh!

StephanTLavavej commented Oct 25, 2024

Uh oh!

Uh oh!

Uh oh!

Revert product changes for find_end vectorization #5041

Revert product changes for find_end vectorization #5041

Uh oh!

Conversation

StephanTLavavej commented Oct 25, 2024

🙀 Test Failure Log

✅ ASan Validation Incantations

Uh oh!

Uh oh!

Uh oh!

Revert product changes for `find_end` vectorization #5041

Revert product changes for `find_end` vectorization #5041