Refactor reflect package

[aykevl]

This is a big PR that changes the way runtime type information is stored in the binary. Instead of compressing it and storing it in a number of sidetables, it is stored similar to how the Go compiler toolchain stores it (but still more compactly).

TODO:

• clean up the code
• add tests
• do some tests to check whether the encoding/json package can be fully supported without too much binary size increase

[ricochet]

I am very excited about this. I noticed map support like MapOf is not part of this refactor. That's something I'm game to help implement to close #2640.

The project I'm looking to build with WASI/Wasm is fq. With many different support formats, this will likely exercise reflect more than most libraries.

I gave this PR a try on an M1. The error below doesn't appear to be M1 specific, but many of the others likely are.

--- FAIL: TestInterfaceLowering (0.00s)
panic: expected method set [recovered]
        panic: expected method set

goroutine 8 [running]:
testing.tRunner.func1.2({0x106ed6ee0, 0x106f2ea50})
        /opt/homebrew/Cellar/go/1.18.4/libexec/src/testing/testing.go:1389 +0x1c8
testing.tRunner.func1()
        /opt/homebrew/Cellar/go/1.18.4/libexec/src/testing/testing.go:1392 +0x380
panic({0x106ed6ee0, 0x106f2ea50})
        /opt/homebrew/Cellar/go/1.18.4/libexec/src/runtime/panic.go:838 +0x20c
github.com/tinygo-org/tinygo/transform.(*lowerInterfacesPass).run(0x1400022ba48)
        /Users/bhayes/repos/tinygo/transform/interface-lowering.go:170 +0x10d8
github.com/tinygo-org/tinygo/transform.LowerInterfaces({0x14e81d3d0?}, 0x1070d49c0)
        /Users/bhayes/repos/tinygo/transform/interface-lowering.go:131 +0x270
github.com/tinygo-org/tinygo/transform_test.TestInterfaceLowering.func1({0x14000212060?})
        /Users/bhayes/repos/tinygo/transform/interface-lowering_test.go:13 +0x40
github.com/tinygo-org/tinygo/transform_test.testTransform(0x14000123a00, {0x1059f6b94, 0x12}, 0x14000053748)
        /Users/bhayes/repos/tinygo/transform/transform_test.go:48 +0x1c0
github.com/tinygo-org/tinygo/transform_test.TestInterfaceLowering(0x14000123a00)
        /Users/bhayes/repos/tinygo/transform/interface-lowering_test.go:12 +0x50
testing.tRunner(0x14000123a00, 0x106f2e0a8)
        /opt/homebrew/Cellar/go/1.18.4/libexec/src/testing/testing.go:1439 +0x110
created by testing.(*T).Run
        /opt/homebrew/Cellar/go/1.18.4/libexec/src/testing/testing.go:1486 +0x328
FAIL    github.com/tinygo-org/tinygo/transform  0.804s

fuzzyEqualIR -> given the target triple, I'm guessing this is darwin-arm64 specific:

    interp_test.go:99: output does not match expected output:
        ; ModuleID = 'testdata/interface.ll'
        source_filename = "testdata/interface.ll"
        target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
        target triple = "x86_64--linux"
        
        @main.v1 = local_unnamed_addr global i1 false
        @main.v2 = local_unnamed_addr global i1 false
        
        define void @runtime.initAll() unnamed_addr {
        entry:
          ret void
        }

Likely related to the same issue as above:

=== CONT  TestOptimizeReflectImplements
transform_test.go:75: output does not match expected output:
    target datalayout = "e-m:e-p:32:32-p270:32:32-p271:32:32-p272:64:64-f64:32:64-f80:32-n8:16:32-S128"
    target triple = "i686--linux"
    
    %runtime.typecodeID = type { %runtime.typecodeID*, i32, %runtime.interfaceMethodInfo*, %runtime.typecodeID*, i32 }
    %runtime.interfaceMethodInfo = type { i8*, i32 }
    
    @"reflect/types.type:named:error" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:interface:{Error:func:{}{basic:string}}", i32 0, %runtime.interfaceMethodInfo* null, %runtime.typecodeID* null, i32 ptrtoint (i1 (i32)* @"error.$typeassert" to i32) }
    @"reflect/types.type:interface:{Error:func:{}{basic:string}}" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* bitcast ([1 x i8*]* @"reflect/types.interface:interface{Error() string}$interface" to %runtime.typecodeID*), i32 0, %runtime.interfaceMethodInfo* null, %runtime.typecodeID* null, i32 ptrtoint (i1 (i32)* @"error.$typeassert" to i32) }
    @"reflect/methods.Error() string" = linkonce_odr constant i8 0
    @"reflect/types.interface:interface{Error() string}$interface" = linkonce_odr constant [1 x i8*] [i8* @"reflect/methods.Error() string"]
    @"reflect/methods.Align() int" = linkonce_odr constant i8 0
    @"reflect/methods.Implements(reflect.Type) bool" = linkonce_odr constant i8 0
    @"reflect.Type$interface" = linkonce_odr constant [2 x i8*] [i8* @"reflect/methods.Align() int", i8* @"reflect/methods.Implements(reflect.Type) bool"]
    @"reflect/types.type:named:reflect.rawType" = linkonce_odr constant %runtime.typecodeID { %runtime.typecodeID* @"reflect/types.type:basic:uintptr", i32 0, %runtime.interfaceMethodInfo* getelementptr inbounds ([20 x %runtime.interfaceMethodInfo], [20 x %runtime.interfaceMethodInfo]* @"reflect.rawType$methodset", i32 0, i32 0), %runtime.typecodeID* null, i32 0 }
    @"reflect.rawType$methodset" = linkonce_odr constant [20 x %runtime.interfaceMethodInfo] zeroinitializer
    @"reflect/types.type:basic:uintptr" = linkonce_odr constant %runtime.typecodeID zeroinitializer
    
    define i1 @main.isError(i32 %typ.typecode, i8* %typ.value, i8* %context) {
    entry:
      %result = call i1 @"reflect.Type.Implements$invoke"(i8* %typ.value, i32 ptrtoint (%runtime.typecodeID* @"reflect/types.type:named:reflect.rawType" to i32), i8* bitcast (%runtime.typecodeID* @"reflect/types.type:named:error" to i8*), i32 %typ.typecode, i8* undef)
      ret i1 %result
    }
    
    define i1 @main.isUnknown(i32 %typ.typecode, i8* %typ.value, i32 %itf.typecode, i8* %itf.value, i8* %context) {
    entry:
      %result = call i1 @"reflect.Type.Implements$invoke"(i8* %typ.value, i32 %itf.typecode, i8* %itf.value, i32 %typ.typecode, i8* undef)
      ret i1 %result
    }
    
    declare i1 @"reflect.Type.Implements$invoke"(i8*, i32, i8*, i32, i8*) #0
    
    declare i1 @"error.$typeassert"(i32) #1
    
    attributes #0 = { "tinygo-invoke"="reflect/methods.Implements(reflect.Type) bool" "tinygo-methods"="reflect/methods.Align() int; reflect/methods.Implements(reflect.Type) bool" }
    attributes #1 = { "tinygo-methods"="reflect/methods.Error() string" }

This is almost definitely from me running on arm (note works on dev).

=== CONT  TestTest/WASM/Fail
panic: unexpected feature flags

goroutine 234 [running]:
github.com/tinygo-org/tinygo/compiler.(*compilerContext).isThumb(0x107260501?)
        /Users/bhayes/repos/tinygo/compiler/llvm.go:299 +0x8c
github.com/tinygo-org/tinygo/compiler.(*builder).createInvokeCheckpoint(0x14004fecc80)
        /Users/bhayes/repos/tinygo/compiler/defer.go:144 +0x70
github.com/tinygo-org/tinygo/compiler.(*builder).createInvoke(0x1401263e270?, {0x1400a4af408?}, {0x1400a4af570, 0x2, 0x2}, {0x0, 0x0})
        /Users/bhayes/repos/tinygo/compiler/calls.go:81 +0x48
github.com/tinygo-org/tinygo/compiler.(*builder).createFunctionCall(0x14004fecc80, 0x14000f1fd40)
        /Users/bhayes/repos/tinygo/compiler/compiler.go:1715 +0xae8
github.com/tinygo-org/tinygo/compiler.(*builder).createExpr(0x14004fecc80, {0x1072d5ee0?, 0x14000f1fd00?})
        /Users/bhayes/repos/tinygo/compiler/compiler.go:1811 +0x1760
github.com/tinygo-org/tinygo/compiler.(*builder).createInstruction(0x14004fecc80, {0x1072d5e98?, 0x14000f1fd00?})
        /Users/bhayes/repos/tinygo/compiler/compiler.go:1323 +0x780
github.com/tinygo-org/tinygo/compiler.(*builder).createFunction(0x14004fecc80)
        /Users/bhayes/repos/tinygo/compiler/compiler.go:1222 +0x7b8
github.com/tinygo-org/tinygo/compiler.(*compilerContext).createPackage(0x1401263e270, {0x14007f581a0?}, 0x140035c8380)
        /Users/bhayes/repos/tinygo/compiler/compiler.go:795 +0x518
github.com/tinygo-org/tinygo/compiler.CompilePackage({0x14012d4da40?, 0x140081f69c0?}, 0x14013189680, 0x140035c8380, {0x1400005dc18?}, 0x105c7d86d?, 0x0?)
        /Users/bhayes/repos/tinygo/compiler/compiler.go:294 +0x3c8
github.com/tinygo-org/tinygo/builder.Build.func3(0x14000db8780)
        /Users/bhayes/repos/tinygo/builder/build.go:354 +0x1a8
github.com/tinygo-org/tinygo/builder.runJob(0x14000db8780, 0x0?)
        /Users/bhayes/repos/tinygo/builder/jobs.go:222 +0x4c
created by github.com/tinygo-org/tinygo/builder.runJobs
        /Users/bhayes/repos/tinygo/builder/jobs.go:123 +0x44c
FAIL    github.com/tinygo-org/tinygo    1.929s
FAIL
make: *** [test] Error 1

# test workflow
git checkout dev
git pull --rebase origin dev
make test
# all tests passed
gh pr checkout 2640

make test
# about 4 test failures

# passing spot checks
make wasmtest
make tinygo-test-wasi-fast

make smoketest # failed
# /opt/homebrew/bin/tinygo build -size short -o test.hex -target=xiao-rp2040         examples/blinky1
# error: open /opt/homebrew/Cellar/tinygo/0.24.0/targets/xiao-rp2040.json: no such file or directory
# make: *** [smoketest] Error 1

[aykevl]

I am very excited about this. I noticed map support like MapOf is not part of this refactor. That's something I'm game to help implement to close #2640.

Correct. This is purely a refactor, it doesn't add new features.

[aykevl]

Current state: it works, but I'd like to do some more testing before marking this ready for review.

[dgryski]

This seems like the perfect time to spin up the test corpus..

[aykevl]

I had to patch the corpus a bit to get it to work (this is also an issue in the dev branch):

   - pkg: curve25519
   - pkg: ed25519
   - pkg: hkdf
-  - pkg: internal/subtle
+  #- pkg: internal/subtle
   - pkg: md4
   - pkg: nacl/auth
   - pkg: nacl/box

but with that, all tests in the corpus pass.

I also did a quick code size check, and it currently stands at a 3-4% increase in code size. Which still feels like too much to me, but we do need the features this PR unlocks. Maybe I can still improve it somehow.

[dgryski]

Arguably we shouldn't test internal/* packages. Probably safe to remove that from the corpus yaml.

[aykevl]

Update: I managed to shave off ~0.5% of code size (out of 3-4%) with some optimizations, but I'm hitting a weird memory corruption that I don't understand.

[dgryski]

Do you have an example of the memory corruption I could take a look at?

[aykevl]

Rebased on the commit right before the LLVM 15 changes. Doing this in steps (and testing in between) to make things easier. EDIT: oh, apparently most test won't run because there are merge conflicts...

[aykevl]

Rebased until right after the LLVM 15 change. It seems there are no more conflicts now.

[dgryski]

Does this include the change you said was causing memory corruption?

[dgryski]

Interesting, this now causes a corpus test failure:

~/go/src/github.com/dgryski/tinygo-test-corpus/_corpus/gonum/gonum/lapack/gonum $ tinygo test -tags="noasm appengine"
panic: runtime error: out of memory
FAIL	gonum.org/v1/gonum/lapack/gonum	54.462s

This package passes with the current dev branch.

[aykevl]

Rebased on the dev branch.

Interesting, this now causes a corpus test failure:

Can't reproduce this on Linux both before and after the rebase. I'm assuming it's MacOS-only.

[aykevl]

Can't reproduce this on MacOS either. Steps:

• build TinyGo with LLVM 15 (at 0f38e7c10fa8913f94b69cc0c7e409bce7cc37ca or 28ff421e26ace256a98fe165d58dd63bf7a41475)
• Checkout gonum at 98316cc24c8495e120ee47f080e2ea1f5d7f32af.
• Run the command tinygo test -tags="noasm appengine" in the lapack/gonum directory.

[aykevl]

Update: I managed to shave off ~0.5% of code size (out of 3-4%) with some optimizations, but I'm hitting a weird memory corruption that I don't understand.

I wanted to reduce binary size a bit but this is taking too long. I think it's better to do that in follow-up PRs instead. So I marked this PR as ready for review.

Do you have an example of the memory corruption I could take a look at?

Pretty sure I was referring to the local changes I made to reduce binary size. So not something in this PR.

[dgryski]

Huh. I'll recheck gonum now that you've finished the rebase.

I'll start working on this Monday.

[dgryski]

Yup. gonum tests pass for me now too.

[dgryski]

Hmm... back to this repo I'm now fairly consistently getting oom panics, but not always. There must be something wonky happening here.

Edit: Ok, so out of 5 runs it passed twice and failed 3 times. I wonder if this is ASLR-related?

[dgryski]

As expected, failure is ASLR addresses pinning allocations.

~/go/src/github.com/dgryski/tinygo-test-corpus/_corpus/gonum/gonum/lapack/gonum $ while :; do ./gonum.test ; done
PASS
panic: runtime error: out of memory
Abort trap: 6
panic: runtime error: out of memory
Abort trap: 6
PASS
PASS
PASS
panic: runtime error: out of memory
Abort trap: 6
PASS
^C
~/go/src/github.com/dgryski/tinygo-test-corpus/_corpus/gonum/gonum/lapack/gonum $ while :; do noaslr ./gonum.test ; done
PASS
PASS
PASS
PASS
PASS
PASS
PASS
PASS

[aykevl]

Huh, interesting. My best guess is that depending on where ASLR puts the heap, some non-pointer values look like pointers into the heap. Guess I need to start working on precise GC for the heap.

[aykevl]

So, I implemented a precise GC :) Well, at least as far as this is supported right now (many runtime.alloc calls don't provide a layout parameter so they are still scanned conservatively). See: https://github.com/tinygo-org/tinygo/pull/3346 This should in theory help with the out of memory issues you've been seeing.

[aykevl]

As expected, failure is ASLR addresses pinning allocations.

Unfortunately I can't reproduce this locally (linux/arm64, ASLR enabled). I ran the test about 20 times.

[dgryski]

This was happening on my Mac. I can only assume Darwin addresses are different from the Linux ones.

[dgryski]

So, do we want to merge this and then tag the next release, or play it safe and merge it after the tag so people on the (b)leading edge can test it out more?

[aykevl]

I prefer doing it early in the next release, so we can shake out any bugs that might turn up. It's a pretty big change after all.

[aykevl]

I did a force-push to update the PR a bit (see https://github.com/tinygo-org/tinygo/compare/5c32d7e49957f4136e947e30389eece2667e8ec8..4d69d0ba712abba5982d79ba4ff8a020ae2b05a7 for the diff):

• I fixed the issue with null bytes in struct tags. The limit is now 255 bytes in struct tags, I could bump it to 65535 if needed.
• I added some documentation and fixed some existing erroneous documentation, see src/reflect/type.go.

[aykevl]

Another force push to fix a vet warning. It's harmless, but it's an error in go test so had to be fixed.

[johnkeates]

Any chance this makes it into 0.27?

[dgryski]

As this is a large change, we specifically didn't want to land it into a release right at the end of the cycle. The plan has always been to merge it right at the start so that people running the development branch have more time to hit and hunt down any issues before releasing.

[johnkeates]

Makes sense, thanks for the reply 👍