Repository navigation
The size calculated to be negative and cause Access Violation when doing vxsort vectorized_partition #86548
Description
Description
The following is the context and call stack when Access Violation occurs in the TTT.
0:054> r
rax=0000025178de776c rbx=fffffffffffffff8 rcx=0000025178de8b80
rdx=0000009ca317ff60 rsi=0000025178de7968 rdi=0000025178de776c
rip=00007ff851e5e576 rsp=0000009ca317e308 rbp=0000009ca317e380
r8=ffffffffffffebe4 r9=ffffffffffffffec r10=00007ff851d00000
r11=0000025178de78a0 r12=0000009ca317ec24 r13=00007ff852114800
r14=0000025178de78d8 r15=0000000080104fa0
iopl=0 nv up ei ng nz na po nc
cs=0033 ss=002b ds=002b es=002b fs=0053 gs=002b efl=00000286
coreclr!memcpy+0x336:
00007ff8`51e5e576 c5fe6f9ac0000000 vmovdqu ymm3,ymmword ptr [rdx+0C0h] ds:0000009c`a3180020=??
0:054> kc
# Call Site
00 coreclr!memcpy
01 coreclr!vxsort::vxsort<int,1,8,0>::vectorized_partition<6>
02 coreclr!vxsort::vxsort<int,1,8,0>::sort
03 coreclr!vxsort::vxsort<int,1,8,0>::sort
04 coreclr!vxsort::vxsort<int,1,8,0>::sort
05 coreclr!vxsort::vxsort<int,1,8,0>::sort
06 coreclr!vxsort::vxsort<int,1,8,0>::sort
07 coreclr!vxsort::vxsort<int,1,8,0>::sort
08 coreclr!vxsort::vxsort<int,1,8,0>::sort
09 coreclr!vxsort::vxsort<int,1,8,0>::sort
0a coreclr!vxsort::vxsort<int,1,8,0>::sort
0b coreclr!vxsort::vxsort<int,1,8,0>::sort
0c coreclr!vxsort::vxsort<int,1,8,0>::sort
0d coreclr!vxsort::vxsort<int,1,8,0>::sort
0e coreclr!vxsort::vxsort<__int64,1,8,3>::sort
0f coreclr!vxsort::vxsort<__int64,1,8,3>::sort
10 coreclr!do_vxsort_avx2
11 coreclr!SVR::do_vxsort
12 coreclr!SVR::gc_heap::sort_mark_list
13 coreclr!SVR::gc_heap::mark_phase
14 coreclr!SVR::gc_heap::gc1
15 coreclr!SVR::gc_heap::garbage_collect
...
The crash occurs when doing memcpy in the below source code:
// 3. Copy-back the 4 registers + remainder we partitioned in the beginning
auto leftTmpSize = tmpLeft - tmpStartLeft;
memcpy(writeLeft, tmpStartLeft, leftTmpSize * sizeof(T));
Switch to frame 1 and check the value for tmpLeft and tmpStartLeft, could see tmpStartLeft is after tmpLeft which is not expected, so that leftTmpSize is calculated to be negative -20 (0xffffffff`ffffffec)
0:054> .frame 1
01 0000009c`a317e310 00007ff8`51e0511d coreclr!vxsort::vxsort<int,1,8,0>::vectorized_partition<6>+0x261 [D:\a\_work\1\s\src\coreclr\gc\vxsort\vxsort.h @ 511]
0:054> dv tmpLeft
tmpLeft = 0x0000009c`a317eb38
0:054> dv tmpStartLeft
tmpStartLeft = 0x0000009c`a317eb4c
0:054> ?0x0000009c`a317eb38-0x0000009c`a317eb4c
Evaluate expression: -20 = ffffffff`ffffffec
trace back how tmpLeft and tmpStartLet were changed before crash
0:054> p-
Time Travel Position: 3AFCBA:4B1
rax=0000009ca317eb38 rbx=0000000000000006 rcx=0000000000000004
rdx=0000009ca317eb38 rsi=0000009ca317e388 rdi=0000000000000006
rip=00007ff851e05a13 rsp=0000009ca317e2f0 rbp=0000009ca317e380
r8=0000000000000000 r9=0000009ca317eb30 r10=ffffffffffffffff
r11=0000009ca317e380 r12=0000025178de771c r13=fffffffffffffff9
r14=0000000000000008 r15=ffffffffffffffe8
iopl=0 nv up ei ng nz na po cy
cs=0033 ss=002b ds=002b es=002b fs=0053 gs=002b efl=00000287
coreclr!vxsort::vxsort<int,1,8,0>::align_vectorized+0x153:
00007ff8`51e05a13 488906 mov qword ptr [rsi],rax ds:0000009c`a317e388=0000009ca317eb30
the tmpLeft and tmpStartLeft were set in the function vxsort::vxsort<int,1,8,0>::align_vectorized as the below:
const auto leftAlign = hint.left_align;
const auto rightAlign = hint.right_align;
const auto rai = ~((rightAlign - 1) >> 31);
const auto lai = leftAlign >> 31;
...
const auto rtPopCountRightPart = max(_mm_popcnt_u32(rtMask), rightAlign);
const auto ltPopCountRightPart = _mm_popcnt_u32(ltMask);
const auto rtPopCountLeftPart = N - rtPopCountRightPart;
const auto ltPopCountLeftPart = N - ltPopCountRightPart;
...
tmpLeft += ltPopCountLeftPart & lai;
tmpStartLeft += -leftAlign & lai;
...
tmpLeft += rtPopCountLeftPart & rai;
we could see from the TTT in the crash case, leftAlign is -7 and rightAlign is 6 so that rai and lai are both calculated to be all 1's (0xffffffff), rtMask is 0xff and ltMask is 0x3f so that rtPopCountRightPart is 8 and ltPopCountRightPart is 6, then rtPopCountLeftPart is 0 (8 - 8) and ltPopCountLeftPart is 2(8-6) as N is 8. which means in this scenarios, based on the above algorithm, tmpLeft only advanced 2x4 8 bytes but tmpStartLeft would advance 7x4 (--7x4) 28 bytes which is after tmpLeft 20 bytes.
Reproduction Steps
No local repro and it always reproduced with the customer complex application on both windows and linux environment..
Expected behavior
tmpLeft should be after or the same as tmpStartLeft in all scenarios.
Actual behavior
tmpLeft is before tmpStartLeft on some scenarios.
Regression?
don't know
Known Workarounds
N/A
Configuration
.net core 6.0
0:054> lmv mcoreclr
...
Timestamp: Wed Nov 30 13:32:33 2022 (6387CBF1)
CheckSum: 004E4C93
ImageSize: 004FE000
File version: 6.0.1322.58009
Product version: 6.0.1322.58009
File flags: 0 (Mask 3F)
File OS: 4 Unknown Win32
...
CompanyName: Microsoft Corporation
ProductName: Microsoft® .NET
InternalName: CoreCLR.dll
OriginalFilename: CoreCLR.dll
ProductVersion: 6,0,1322,58009 @Commit: 1af80ba
FileVersion: 6,0,1322,58009 @Commit: 1af80ba
FileDescription: Microsoft .NET Runtime
LegalCopyright: © Microsoft Corporation. All rights reserved.
Comments: Flavor=Retail
Other information
No response
Activity
PeterSolMS commentedon May 23, 2023
We have seen this issue only under time travel debugging - I assume this is what TTT above refers to? If so, this was a debugger issue with certain AVX2 instructions used by the sorting code that has been fixed by the debugger team, so I would suggest updating the version of the debugger used.
oldzhu commentedon May 25, 2023
Thanks the reply! I will test and revert back.
Fix negative tmp-buffer size in vxsort align_vectorized (AV in GC vec…
Fix negative tmp-buffer size in vxsort align_vectorized (#134881)