search

aardappel / lobster

The Lobster Programming Language
http://strlen.com/lobster
2.24k stars 121 forks source link

Crash due to possible heap use after free #233

Closed MortimerSnerd closed 1 year ago

MortimerSnerd commented 1 year ago

I pulled the latest on master, 56ed7897ef3e71513118a0f865ab5b0b8cef4d32

Short summary

I started getting a crash with the lobster release build after changing a data file that I read from a lobster program. The debug version of lobster shows an assertion in type/borrow checking before the program can even run, and the ASAN build runs and shows a use after free.

Details

So I get this in lobster-release.exe.exp.log:

===== Crash Log =====
Date: 2023-04-05, Time: 20:14:59
CMD: lobster-release.exe src\main.lobster 
ExpCode: 0xC0000005, ExpFlags: 0, ExpAddress: 0xEE22CDB3
SymInit: Symbol-SearchPath: '.;C:\src\lobster_bsp;C:\src\lobster\bin;C:\Windows;C:\Windows\system32;SRV*C:\websymbols*http://msdl.microsoft.com/download/symbols;', symOptions: 530, UserName: 'pkelley'
OS-Version: 6.2.9200 () 0x300-0x1
C:\src\lobster\dev\src\lobster\slaballoc.h (197): SlabAlloc::alloc_small
C:\src\lobster\dev\src\vm.cpp (260): lobster::VM::NewVec
C:\src\lobster\dev\src\vm.cpp (840): CVM_NEWVEC
ERROR: SymGetSymFromAddr64, GetLastError: 126 (Address: 000001FCB20FB718)
ERROR: SymGetLineFromAddr64, GetLastError: 126 (Address: 000001FCB20FB718)
ERROR: SymGetModuleInfo64, GetLastError: 1114 (Address: 000001FCB20FB718)
000001FCB20FB718 ((module-name not available)): (filename not available): (function-name not available)
ERROR: SymGetSymFromAddr64, GetLastError: 126 (Address: 000001FCB03CB680)
ERROR: SymGetLineFromAddr64, GetLastError: 126 (Address: 000001FCB03CB680)
ERROR: SymGetModuleInfo64, GetLastError: 1114 (Address: 000001FCB03CB680)
000001FCB03CB680 ((module-name not available)): (filename not available): (function-name not available)
ERROR: SymGetSymFromAddr64, GetLastError: 126 (Address: 000000AA0AB4DDD0)
ERROR: SymGetLineFromAddr64, GetLastError: 126 (Address: 000000AA0AB4DDD0)
ERROR: SymGetModuleInfo64, GetLastError: 1114 (Address: 000000AA0AB4DDD0)
000000AA0AB4DDD0 ((module-name not available)): (filename not available): (function-name not available)
ERROR: SymGetSymFromAddr64, GetLastError: 126 (Address: 000000AA0AB4F828)
ERROR: SymGetLineFromAddr64, GetLastError: 126 (Address: 000000AA0AB4F828)
ERROR: SymGetModuleInfo64, GetLastError: 1114 (Address: 000000AA0AB4F828)
000000AA0AB4F828 ((module-name not available)): (filename not available): (function-name not available)
ERROR: SymGetSymFromAddr64, GetLastError: 126 (Address: 000001FCB03AF708)
ERROR: SymGetLineFromAddr64, GetLastError: 126 (Address: 000001FCB03AF708)
ERROR: SymGetModuleInfo64, GetLastError: 1114 (Address: 000001FCB03AF708)
000001FCB03AF708 ((module-name not available)): (filename not available): (function-name not available)
ERROR: SymGetSymFromAddr64, GetLastError: 126 (Address: 000001FCB037E7E0)
ERROR: SymGetLineFromAddr64, GetLastError: 126 (Address: 000001FCB037E7E0)
ERROR: SymGetModuleInfo64, GetLastError: 1114 (Address: 000001FCB037E7E0)
000001FCB037E7E0 ((module-name not available)): (filename not available): (function-name not available)
C:\src\lobster\dev\src\vm.cpp (840): CVM_BCALLRET3

I switched to the debug version of lobster to see if I got an assertion, and I get this: 

Assertion failed: IsRefNilVar(b.sid->type->t), file C:\src\lobster\dev\src\lobster\typecheck.h, line 2074

And I get this in lobster-debug.exe.exp.log:

===== Crash Log =====
Date: 2023-04-05, Time: 16:30:28
CMD: lobster-debug.exe src\main.lobster 
ExpCode: 0x80000003, ExpFlags: 0, ExpAddress: 0x5A810385
SymInit: Symbol-SearchPath: '.;C:\src\lobster_bsp;C:\src\lobster\bin;C:\Windows;C:\Windows\system32;SRV*C:\websymbols*http://msdl.microsoft.com/download/symbols;', symOptions: 530, UserName: 'pkelley'
OS-Version: 6.2.9200 () 0x300-0x1
minkernel\crts\ucrt\src\appcrt\internal\report_runtime_error.cpp (28): issue_debug_notification
minkernel\crts\ucrt\src\appcrt\internal\report_runtime_error.cpp (154): __acrt_report_runtime_error
minkernel\crts\ucrt\src\appcrt\startup\abort.cpp (61): abort
minkernel\crts\ucrt\src\appcrt\startup\assert.cpp (187): common_assert_to_stderr<wchar_t>
minkernel\crts\ucrt\src\appcrt\startup\assert.cpp (420): common_assert<wchar_t>
minkernel\crts\ucrt\src\appcrt\startup\assert.cpp (444): _wassert
C:\src\lobster\dev\src\lobster\typecheck.h (2015): lobster::TypeChecker::Borrowers
C:\src\lobster\dev\src\lobster\typecheck.h (2028): lobster::TypeChecker::DecBorrowers
C:\src\lobster\dev\src\lobster\typecheck.h (677): lobster::TypeChecker::TypeCheckComp
C:\src\lobster\dev\src\lobster\typecheck.h (2671): lobster::Equal::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (3230): lobster::Return::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (910): lobster::TypeChecker::TypeCheckFunctionDef
C:\src\lobster\dev\src\lobster\typecheck.h (1029): lobster::TypeChecker::TypeCheckMatchingCall
C:\src\lobster\dev\src\lobster\typecheck.h (1285): lobster::TypeChecker::TypeCheckCallStatic
C:\src\lobster\dev\src\lobster\typecheck.h (1683): lobster::TypeChecker::TypeCheckDynCall
C:\src\lobster\dev\src\lobster\typecheck.h (3194): lobster::DynCall::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (1856): lobster::TypeChecker::TypeCheckCondition
C:\src\lobster\dev\src\lobster\typecheck.h (2279): lobster::IfThen::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2379): lobster::For::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (910): lobster::TypeChecker::TypeCheckFunctionDef
C:\src\lobster\dev\src\lobster\typecheck.h (1029): lobster::TypeChecker::TypeCheckMatchingCall
C:\src\lobster\dev\src\lobster\typecheck.h (1285): lobster::TypeChecker::TypeCheckCallStatic
C:\src\lobster\dev\src\lobster\typecheck.h (1516): lobster::TypeChecker::TypeCheckCall
C:\src\lobster\dev\src\lobster\typecheck.h (3174): lobster::Call::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2916): lobster::GenericCall::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (551): lobster::TypeChecker::OperatorOverload
C:\src\lobster\dev\src\lobster\typecheck.h (646): lobster::TypeChecker::TypeCheckComp
C:\src\lobster\dev\src\lobster\typecheck.h (2687): lobster::LessThan::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (1856): lobster::TypeChecker::TypeCheckCondition
C:\src\lobster\dev\src\lobster\typecheck.h (2279): lobster::IfThen::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2379): lobster::For::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (1695): lobster::TypeChecker::TypeCheckBranch
C:\src\lobster\dev\src\lobster\typecheck.h (2281): lobster::IfThen::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (1695): lobster::TypeChecker::TypeCheckBranch
C:\src\lobster\dev\src\lobster\typecheck.h (2311): lobster::IfElse::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (1695): lobster::TypeChecker::TypeCheckBranch
C:\src\lobster\dev\src\lobster\typecheck.h (2281): lobster::IfThen::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2379): lobster::For::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (910): lobster::TypeChecker::TypeCheckFunctionDef
C:\src\lobster\dev\src\lobster\typecheck.h (1029): lobster::TypeChecker::TypeCheckMatchingCall
C:\src\lobster\dev\src\lobster\typecheck.h (1285): lobster::TypeChecker::TypeCheckCallStatic
C:\src\lobster\dev\src\lobster\typecheck.h (1516): lobster::TypeChecker::TypeCheckCall
C:\src\lobster\dev\src\lobster\typecheck.h (3174): lobster::Call::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2916): lobster::GenericCall::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (1695): lobster::TypeChecker::TypeCheckBranch
C:\src\lobster\dev\src\lobster\typecheck.h (2281): lobster::IfThen::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (1695): lobster::TypeChecker::TypeCheckBranch
C:\src\lobster\dev\src\lobster\typecheck.h (2281): lobster::IfThen::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (1695): lobster::TypeChecker::TypeCheckBranch
C:\src\lobster\dev\src\lobster\typecheck.h (2349): lobster::While::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (3230): lobster::Return::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (910): lobster::TypeChecker::TypeCheckFunctionDef
C:\src\lobster\dev\src\lobster\typecheck.h (1029): lobster::TypeChecker::TypeCheckMatchingCall
C:\src\lobster\dev\src\lobster\typecheck.h (1285): lobster::TypeChecker::TypeCheckCallStatic
C:\src\lobster\dev\src\lobster\typecheck.h (1516): lobster::TypeChecker::TypeCheckCall
C:\src\lobster\dev\src\lobster\typecheck.h (3174): lobster::Call::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2916): lobster::GenericCall::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (3230): lobster::Return::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (2237): lobster::Block::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (910): lobster::TypeChecker::TypeCheckFunctionDef
C:\src\lobster\dev\src\lobster\typecheck.h (1029): lobster::TypeChecker::TypeCheckMatchingCall
C:\src\lobster\dev\src\lobster\typecheck.h (1285): lobster::TypeChecker::TypeCheckCallStatic
C:\src\lobster\dev\src\lobster\typecheck.h (1516): lobster::TypeChecker::TypeCheckCall
C:\src\lobster\dev\src\lobster\typecheck.h (3174): lobster::Call::TypeCheck
C:\src\lobster\dev\src\lobster\typecheck.h (2091): lobster::TypeChecker::TT
C:\src\lobster\dev\src\lobster\typecheck.h (101): lobster::TypeChecker::TypeChecker
C:\src\lobster\dev\src\compiler.cpp (347): lobster::Compile
C:\src\lobster\dev\src\main.cpp (197): SDL_main
C:\src\lobster\dev\external\SDL\src\main\windows\SDL_windows_main.c (175): main_getcmdline
C:\src\lobster\dev\external\SDL\src\main\windows\SDL_windows_main.c (188): main
d:\a01\_work\20\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl (79): invoke_main
d:\a01\_work\20\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl (288): __scrt_common_main_seh
d:\a01\_work\20\s\src\vctools\crt\vcstartup\src\startup\exe_common.inl (331): __scrt_common_main
d:\a01\_work\20\s\src\vctools\crt\vcstartup\src\startup\exe_main.cpp (17): mainCRTStartup
ERROR: SymGetLineFromAddr64, GetLastError: 487 (Address: 00007FFD347B7034)
00007FFD347B7034 (KERNEL32): (filename not available): BaseThreadInitThunk
ERROR: SymGetLineFromAddr64, GetLastError: 487 (Address: 00007FFD353C2651)
00007FFD353C2651 (ntdll): (filename not available): RtlUserThreadStart

I poked around in the debugger for a few minutes to see what line of my lobster code it was referencing when it asserted, and it's an innocuous looking find on a [xyz_f]:

                  if (find(seen_norms) nn: nn == p_norm) < 0:

I built the asan-release target and run with it, and it detects a use after free (with the byte legend at the end elided):

C:\src\lobster_bsp>lobster-asan.exe src\main.lobster
=================================================================
==20780==ERROR: AddressSanitizer: heap-use-after-free on address 0x12ac27a7b3d4 at pc 0x7ff6b3dc05aa bp 0x00e43394c500 sp 0x00e43394c508
READ of size 4 at 0x12ac27a7b3d4 thread T0
    #0 0x7ff6b3dc05a9 in lobster::RefObj::Dec(struct lobster::VM &) C:\src\lobster\dev\src\lobster\vmdata.h:213
    #1 0x7ff6b3da764a in CVM_POPREF C:\src\lobster\dev\src\vm.cpp:840
    #2 0x13202c4fc464  (<unknown module>)

0x12ac27a7b3d4 is located 20 bytes inside of 56-byte region [0x12ac27a7b3c0,0x12ac27a7b3f8)
freed by thread T0 here:
    #0 0x7ff6b3c50a51 in _aligned_free D:\a01\_work\20\s\src\vctools\crt\asan\llvm\compiler-rt\lib\asan\asan_malloc_win.cpp:198
    #1 0x7ff6b3dd0ddc in lobster::RefObj::DECDELETE(struct lobster::VM &) C:\src\lobster\dev\src\vmdata.cpp:226
    #2 0x7ff6b3dc05ff in lobster::RefObj::Dec(struct lobster::VM &) C:\src\lobster\dev\src\lobster\vmdata.h:221
    #3 0x7ff6b3da42f4 in CVM_DecOwned C:\src\lobster\dev\src\vm.cpp:822
    #4 0x13202c4fb6fd  (<unknown module>)

previously allocated by thread T0 here:
    #0 0x7ff6b3c511e1 in malloc D:\a01\_work\20\s\src\vctools\crt\asan\llvm\compiler-rt\lib\asan\asan_malloc_win.cpp:118
    #1 0x7ff6b3dc8ea7 in SlabAlloc::alloc_large(__int64) C:\src\lobster\dev\src\lobster\slaballoc.h:158
    #2 0x7ff6b3da7460 in CVM_NEWVEC C:\src\lobster\dev\src\vm.cpp:840
    #3 0x13202c4fb287  (<unknown module>)

SUMMARY: AddressSanitizer: heap-use-after-free C:\src\lobster\dev\src\lobster\vmdata.h:213 in lobster::RefObj::Dec(struct lobster::VM &)
Shadow bytes around the buggy address:
  0x04f5ac84f620: fa fa fa fa fd fd fd fd fd fd fd fa fa fa fa fa
  0x04f5ac84f630: fd fd fd fd fd fd fd fa fa fa fa fa 00 00 00 00
  0x04f5ac84f640: 00 00 00 fa fa fa fa fa 00 00 00 00 00 00 00 fa
  0x04f5ac84f650: fa fa fa fa 00 00 00 00 00 00 00 fa fa fa fa fa
  0x04f5ac84f660: fd fd fd fd fd fd fd fa fa fa fa fa 00 00 00 00
=>0x04f5ac84f670: 00 00 00 fa fa fa fa fa fd fd[fd]fd fd fd fd fa
  0x04f5ac84f680: fa fa fa fa fd fd fd fd fd fd fd fa fa fa fa fa
  0x04f5ac84f690: fd fd fd fd fd fd fd fa fa fa fa fa fd fd fd fd
  0x04f5ac84f6a0: fd fd fd fa fa fa fa fa fd fd fd fd fd fd fd fd
  0x04f5ac84f6b0: fa fa fa fa fd fd fd fd fd fd fd fd fa fa fa fa
  0x04f5ac84f6c0: fd fd fd fd fd fd fd fd fa fa fa fa fd fd fd fd

Other notes about the crash:

This seems complicated enough I doubt it's enough for you to go on. If you need it, I can put together a zip of the files, and PM a gdrive link or something similar.

aardappel commented 1 year ago

So Assertion failed: IsRefNilVar(b.sid->type->t), file C:\src\lobster\dev\src\lobster\typecheck.h, line 2074 is the first thing to check, since all the use after free stuff you found is way later, at runtime, and could be the consequence of that assert.

Easiest if you can somehow give me access to something that reproduces that assert?

From looking at your data it looks like your xyz_f structs would have a lifetime associated with it, lets see if I can repro with similar code..

aardappel commented 1 year ago

This simple program does not repro, so I need either a more complex test, or your full program:

import vec
import std

let seen_norms = [ xyz_1 ]
let p_norm = xyz_1

if (find(seen_norms) nn: nn == p_norm) < 0:
    print "foo"
MortimerSnerd commented 1 year ago

I'll message you in discord with the google drive link in a sec. The main thing I cut out of the picture in the zip file is the large-ish main.lobster. If you run src\smallmain.lobster, it has just a call to the problem function in core\physics.lobster which is enough for me to get the assertion.

aardappel commented 1 year ago

Found the type-checker problem. For posterity, what happens is that [] which gets passed into find is a list of unknown element type (a "type variable"), that then gets passed to nn which is now a type variable, which then gets registered as possibly a borrowed value in ==, but then gets bound to be a struct and not something that can be borrowed.

Now to see what is the cleanest solution..

aardappel commented 1 year ago

Looks like removing the assert is the only way for now, since we allow borrows on type variables.

Your small main then game/physics.lobster(347): error: unknown field/function reference is_floor_normal

Your regular main runs the actual game, and does not crash. This is in VS Debug mode which normally does pretty thorough memory checks, but I guess not as strong as ASAN.

aardappel commented 1 year ago

Ok managed to get repro, fixed in: https://github.com/aardappel/lobster/commit/764661230bf8524b48c62248fc2ed41803c675ea

The problem was the code generator got confused between the number of return values declared, vs the ones actually requested by the caller.