Add support for reading Go assembly files

[aykevl]

This is a pretty big change that adds support for Go assembly files. Go assembly files are different from standard assembly and can't be read by tools like Clang. They also use a different calling convention. On top of that, the tools that can read them (the gc toolchain) only output custom (unstable) object files. In a previous attempt I tried to parse these files but with this attempt I simply read the output of go tool asm -S, which is a more-or-less stable text format (that, importantly, includes the raw machine code and all relocations).

As a result:

• This implements syscall.seek on 386 and arm. The following works with this commit: GOARCH=arm tinygo test os. See #2578.
• This changes the math package, probably speeding up some algorithms (although I didn't benchmark them).
• The crypto/aes package now works (issue #2779).
• Undefined references to crypto/internal/boring/sig.StandardCrypto in Go 1.19 are fixed (see #3057, #3080).

So far, this is only for Linux (on all supported architectures: 386, amd64, arm, arm64). Adding support for macOS and Windows should be feasible by implementing the appropriate file formats (MachO and COFF). It should be relatively easy to also add support for js/wasm. I'm not so sure about other systems where the GOARCH doesn't match the actual architecture, like WASI and most/all baremetal systems. It might be possible to get them to work by lifting ARM machine code to LLVM IR, but that will be quite some work in itself and certainly something for the longer term.

---

This replaces #2688. It is still a draft because it depends on #3102 (math intrinsics) and #2904 (drop Go 1.16/1.17 support). It needs to be rebased on top of the dev branch once those PRs are in.

[deadprogram]

Looks like macOS and Linux not passing CI on this @aykevl

[deadprogram]

Looks like needs merge conflict resolved @aykevl

[aykevl]

Rebased to fix the merge conflict.

[aykevl]

Can someone take a look at this? I have a number of other changes waiting for this PR to be merged.

[dgryski]

I tried reviewing this, but there's too much compiler stuff I don't yet understand. Can we put this behind a flag temporarily so that it can be merged and allow us to do more tests before making it the default?

Also, is there anything inherently preventing this from working on Darwin, or just "haven't gotten around to it yet"?

[aykevl]

I tried reviewing this, but there's too much compiler stuff I don't yet understand.

If you need help with anything, feel free to ask.

Can we put this behind a flag temporarily so that it can be merged and allow us to do more tests before making it the default?

I guess, but we'd have to review it some time anyway. Not sure what the advantage is. Avoiding breakage?

Also, is there anything inherently preventing this from working on Darwin, or just "haven't gotten around to it yet"?

I just need to write a port to MachO, shouldn't be too difficult. I already made one for Windows. (Those are things I will make PRs for once this PR is in).

[dgryski]

Yes. We can review it and test it more thoroughly without holding up other PRs and without creating large merge conflicts.

Glad to hear Darwin support is possible.

[kenbell]

I think this change also means we can get rid of this 'hack' in the test cases: https://github.com/tinygo-org/tinygo/blob/dev/main_test.go#L173-L180

[aykevl]

@dgryski I still don't understand why this feature should be disabled in the beginning? If it's disabled, that won't help with testing. What is it exactly that you're proposing and what's the advantage of it?

I think this change also means we can get rid of this 'hack' in the test cases: https://github.com/tinygo-org/tinygo/blob/dev/main_test.go#L173-L180

Thanks, yes it does! Happy to see it go away. I've updated this PR.

[dgryski]

@aykevl My goal with the merge but with flag to enable was to allow this to unblock other patches (as you said above) and give people the opportunity to test it more easily until we made it the default.

I'll try to understand this patch tonight and you can merge it (since it seems to be working.)

[dgryski]

My suggestion is to run the test corpus, removing all the purego and noasm tags. If that passes, we can merge this and debug any issues as they come up.

[deadprogram]

Just catching up on this PR. Did we ever perform the test suggested by @dgryski and if so do we consider it ready to merge?

[deadprogram]

@dgryski and @aykevl have we performed the recommended tests and/or are we ready to merge this?

[dgryski]

@dkegel-fastly You have a linux box. You want to take a look at running these tests?

[dkegel-fastly]

will do

[dankegel]

Hrm. "make test" fails on my linux box with

tinygo:ld.lld: error: undefined symbol: log
>>> referenced by log.go:80 (/usr/lib/go-1.18/src/math/log.go:80)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
>>> referenced by log.go:80 (/usr/lib/go-1.18/src/math/log.go:80)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
>>> referenced by log.go:80 (/usr/lib/go-1.18/src/math/log.go:80)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
>>> referenced 4 more times

tinygo:ld.lld: error: undefined symbol: ceil
>>> referenced by floor.go:41 (/usr/lib/go-1.18/src/math/floor.go:41)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)

tinygo:ld.lld: error: undefined symbol: exp
>>> referenced by sinh.go:0 (/usr/lib/go-1.18/src/math/sinh.go:0)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
>>> referenced by exp.go:14 (/usr/lib/go-1.18/src/math/exp.go:14)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
>>> referenced by exp.go:14 (/usr/lib/go-1.18/src/math/exp.go:14)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
>>> referenced 7 more times

tinygo:ld.lld: error: undefined symbol: exp2
>>> referenced by exp.go:140 (/usr/lib/go-1.18/src/math/exp.go:140)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)

tinygo:ld.lld: error: undefined symbol: floor
>>> referenced by floor.go:13 (/usr/lib/go-1.18/src/math/floor.go:13)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)

tinygo:ld.lld: error: undefined symbol: trunc
>>> referenced by floor.go:58 (/usr/lib/go-1.18/src/math/floor.go:58)
>>>               /home/dank/.cache/tinygo/thinlto/llvmcache-CC40CEA9C88595CE4A2271BD52FFCD6A1FF971D3:(runtime.run$1$gowrapper)
failed to run tool: ld.lld
--- FAIL: TestBuild (0.00s)
    --- FAIL: TestBuild/Host (0.00s)
        --- FAIL: TestBuild/Host/math.go (1.25s)
            main.go:1192: error: failed to link /tmp/tinygo1886996487/main: exit status 1
FAIL
FAIL	github.com/tinygo-org/tinygo	14.778s

It's like it needs -lm or something.

[aykevl]

@dankegel most likely you need to run tinygo clean: you seem to be using and old cached build of musl. See #3099 for details.

[dankegel]

Thanks. I'm afraid I'm hitting panics on the real test, though.

e.g.

=== CONT  TestCorpus/github.com/dgryski/go-postings
    main_test.go:523: go: creating new go.mod: module github.com/tinygo/tinygo-corpus-test
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc0413fe4a0 stack=[0xc0413fe000, 0xc0613fe000]
fatal error: stack overflow

runtime stack:
runtime.throw({0x57c250d?, 0x77bcda0?})
	/usr/lib/go-1.18/src/runtime/panic.go:992 +0x71
runtime.newstack()
	/usr/lib/go-1.18/src/runtime/stack.go:1101 +0x5cc
runtime.morestack()
	/usr/lib/go-1.18/src/runtime/asm_amd64.s:547 +0x8b
...

What's the easiest way to tell the corpus test to use a bigger stack?

[dgryski]

Pretty sure that test shouldn't be hitting a stack overflow. The assembly version of the code is a few instructions and a table lookup.

Edit: oh, saw the stack overflow was in the compiler not the test.

[aykevl]

What's the easiest way to tell the corpus test to use a bigger stack?

It's using a 1GB stack, more stack is not going to help you here.

(Now running the corpus test to reproduce the issue)

[aykevl]

I rebased this PR and I can't reproduce the stack overflow. I think it has been fixed in the dev branch. (That said, I'm running on a slightly unusual setup with a linux/arm64 host and testing on linux/amd64 via qemu-x86_64).

[dkegel-fastly]

I'll retest tonight.

[aykevl]

With some testing (now with the build tags removed), I don't think this is quite ready yet:

• github.com/dgryski/go-bloomindex crashed QEMU with a SIGILL. I suspect this is actually a QEMU bug (apparently the ptest instruction isn't commonly used and isn't implemented in QEMU)
• github.com/dgryski/go-chaskey results in a SIGSEGV, apparently because it jumps somewhere it really shouldn't.
• github.com/dgryski/go-cuckoof also resulted in a SIGSEGV, this time it appears to happen somewhere in the Go assembly wrapper code

So while the first seems to be a QEMU bug, the other two are most likely real bugs that I need to fix. I did not yet test other packages than these three.

[dkegel-fastly]

test corpus FTW!

[aykevl]

github.com/dgryski/go-bloomindex crashed QEMU with a SIGILL. I suspect this is actually a QEMU bug (apparently the ptest instruction isn't commonly used and isn't implemented in QEMU)

Not anymore with a recent QEMU (apparently they implemented ptest) but it now triggers a segmentation fault... so there is still a bug in TinyGo.

[dgryski]

I'm always so pleased when testing reveals bugs :D

[aykevl]

Took me a while to figure out, but I think I found the bug: LLVM doesn't save/restore the rbp register through the call even though the assembly marks it as clobbered.

[aykevl]

I know a solution to this, but it's going to need a bit of a rewrite. It's a cleanup I've wanted to do after this PR landed but it appears I now need to clean up my code for it to work :smiling_face_with_tear:

[aykevl]

The rewrite works. Those 3 tests that failed before now pass with my new implementation (I didn't test any others yet). The resulting assembly is a lot cleaner so it's probably also a lot faster (if that matters).

Now I need to clean it up, implement all the loose ends, and make sure it also works on all other architectures. And of course test the rest of the corpus.

[dankegel]

Currently fails with

    main_test.go:523: FAIL	github.com/dgryski/go-bloomindex	0.174s
    main_test.go:523: FAIL	github.com/dgryski/go-metro	0.179s
    main_test.go:523: FAIL	github.com/dgryski/go-marvin32	0.176s
    main_test.go:523: FAIL	github.com/dgryski/go-farm	0.177s
    main_test.go:523: FAIL	github.com/dgryski/go-cuckoof	0.176s

and then a stack overflow (which probably hides a bunch of failures).

I narrowed the go-farm failure down slightly; the hash tests pass, but 'tinygo test -run TestFingerprint32' fails.

Also, go-postings on its own still fails here :-(