go icon indicating copy to clipboard operation
go copied to clipboard
Published 3 weeks ago • verified publisher icon golang

cmd/link: on wasm, number of functions limited to 2^16

Open HarikrishnanBalagopal opened this issue 2 years ago • 37 comments

Overview

It seems to me that the size of a WASM function is limited to 2^16 = 65536 bytes?

https://github.com/golang/go/blob/649671b08fbd49bcf65578b18d188d55779e6eca/src/cmd/link/internal/wasm/asm.go#L90

This leads to a bunch of errors whenever using more than a few libraries in our WASM app The code for our app is available in this branch https://github.com/konveyor/move2kube/blob/wasm/go.mod The code is able to build using the official Go compiler WASIP1 support https://github.com/konveyor/move2kube/blob/dec9d8da6e5f8882aacb46a8e5f784b96b42a3c6/Makefile#L45C2-L45C100

Issue

When we try to add the https://pkg.go.dev/go.starlark.net/starlark library then we get a bunch of compile errors

type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).ModTime is too big: 0x100c40000
type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).ModTime is too big: 0x100c40000
type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).Mode is too big: 0x100c60000
type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).Mode is too big: 0x100c60000
type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).Name is too big: 0x100c70000
type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).Name is too big: 0x100c70000
type:*github.com/mholt/archiver/v3.FileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*FileInfo).Size is too big: 0x100c90000
/usr/local/go/pkg/tool/linux_amd64/link: too many errors
make: *** [Makefile:45: build] Error 1

Fix

Please remove this arbitrary limit on function size or at least provide a way to work around it. This is a severe limit on any real world app that will use many different libraries to implement various features.

The WASM page size is 65536 bytes https://developer.mozilla.org/en-US/docs/WebAssembly/JavaScript_interface/Memory/Memory which is 2^16 and can be addressed with 16 bits. That might explain where this particular limit came from but it doesn't explain why a single function has to fit all inside of one WASM page. Especially since WASM functions live is a completely separate address space than the WASM linear memory.

Also see these comments:

  • https://github.com/WebAssembly/design/issues/1138#issuecomment-337766850
  • https://github.com/WebAssembly/design/issues/1138#issuecomment-341808035
  • https://github.com/WebAssembly/design/issues/1138#issuecomment-338921461

Related

https://stackoverflow.com/questions/67294859/why-golang-limit-the-symbol-number-to-65535-while-compile-wasm-target https://github.com/golang/go/issues/7769 https://github.com/golang/go/issues/7980 https://github.com/WebAssembly/design/issues/1138

HarikrishnanBalagopal avatar Dec 24 '23 13:12 HarikrishnanBalagopal

/cc @golang/wasm

mauri870 avatar Dec 25 '23 15:12 mauri870

Looking at the limits for other implementations I see no issue bumping the function size in Go, unless that has to do with some internal implementation detail on our side that I'm not aware of. For instance, Webkit and V8 use 7654321, we might as well just ride the same train.

mauri870 avatar Dec 25 '23 15:12 mauri870

After some investigation this appears to be a bug with 1.22. I'm able to compile this without any errors with go 1.21.

It happens for both js and wasip1 here. Since there are unrelated failures I was only able to bisect to a certain range https://github.com/golang/go/compare/4346ba34df...8be8bfeaa2 (113 commits).

This error prevents the compilation of large wasm programs with Go 1.22 without a workaround.

/cc @golang/release

mauri870 avatar Dec 25 '23 19:12 mauri870

After some investigation this appears to be a bug with 1.22. I'm able to compile this without any errors with go 1.21.

It happens for both js and wasip1 here. Since there are unrelated failures I was only able to bisect to a certain range 4346ba3...8be8bfe (113 commits).

This error prevents the compilation of large wasm programs with Go 1.22 without a workaround.

/cc @golang/release

@mauri870 I don't think the bug is only in v1.22 because we have not tried v1.22 yet. The errors we saw are all with Go v1.21

The line I linked in the first post is still there in the master branch https://github.com/golang/go/blob/2184a394777ccc9ce9625932b2ad773e6e626be0/src/cmd/link/internal/wasm/asm.go#L157 The git blame shows that line has been there from the beginning when WASM got added https://github.com/golang/go/commit/f41dc711d80cf750a6df994a49608ffd3786bb19#diff-b189a5a4d6f377939c502fb248c71ab0f1febe60a54f283eaca1dad73c196604R85

Working

Building the wasm branch https://github.com/konveyor/move2kube/tree/wasm works correctly:

$ go version
go version go1.21.0 darwin/arm64
$ make build
mkdir -p "./bin"
CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm go build -ldflags ' -X github.com/konveyor/move2kube-wasm/types/info.buildmetadata=unreleased -X github.com/konveyor/move2kube-wasm/types/info.gitCommit=dec9d8da6e5f8882aacb46a8e5f784b96b42a3c6 -X github.com/konveyor/move2kube-wasm/types/info.gitTreeState=clean' -o "./bin/move2kube.wasm" .
gzip -f "./bin/move2kube.wasm"
# We have to put require github.com/sirupsen/logrus v1.9.4-0.20230606125235-dd1b4c2e81af
# in order for logrus to work. See https://github.com/HarikrishnanBalagopal/test-wasi-fs-browser/tree/main
# CGO_ENABLED=0 tinygo build -o "./bin/move2kube.wasm" -target=wasi .
$ echo $?
0

Non-working

After adding the go.starlark.net v0.0.0-20200306205701-8dd3e2ee1dd5 library, building this branch https://github.com/HarikrishnanBalagopal/move2kube/tree/feat/starlark with Golang v1.21.0 gives errors:

$ go version
go version go1.21.0 darwin/arm64
$ make build
mkdir -p "./bin"
CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm go build -ldflags ' -X github.com/konveyor/move2kube-wasm/types/info.buildmetadata=unreleased -X github.com/konveyor/move2kube-wasm/types/info.gitCommit=6d72f91783749e697f9fa38c17f8b4d892c9d102 -X github.com/konveyor/move2kube-wasm/types/info.gitTreeState=clean' -o "./bin/move2kube.wasm" .
# github.com/konveyor/move2kube-wasm
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).IsDir is too big: 0x100240000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).IsDir is too big: 0x100240000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).ModTime is too big: 0x100250000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).ModTime is too big: 0x100250000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Mode is too big: 0x100260000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Mode is too big: 0x100260000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Name is too big: 0x100270000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Name is too big: 0x100270000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Size is too big: 0x100280000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Size is too big: 0x100280000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Sys is too big: 0x100290000
type:*github.com/mholt/archiver/v3.rarFileInfo: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*rarFileInfo).Sys is too big: 0x100290000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Match is too big: 0x100010000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Match is too big: 0x100010000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Read is too big: 0x100030000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Read is too big: 0x100030000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Write is too big: 0x100050000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Write is too big: 0x100050000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).CheckPath is too big: 0x100070000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).CheckPath is too big: 0x100070000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Close is too big: 0x100090000
/opt/homebrew/Cellar/go/1.21.0/libexec/pkg/tool/darwin_arm64/link: too many errors
make: *** [build] Error 1

Difference

The difference is that we added the starlark-go library and a file that uses it https://github.com/HarikrishnanBalagopal/move2kube/blob/feat/starlark/transformer/external/starlarktransformer.go

$ git checkout feat/starlark 
Switched to branch 'feat/starlark'
Your branch is up to date with 'origin/feat/starlark'.
$ git status
On branch feat/starlark
Your branch is up to date with 'origin/feat/starlark'.

nothing to commit, working tree clean
$ git diff wasm --name-status 
M       go.mod
M       go.sum
A       transformer/external/starlarktransformer.go
$ git diff wasm go.mod
diff --git a/go.mod b/go.mod
index 8fdc019..e8de3ed 100644
--- a/go.mod
+++ b/go.mod
@@ -28,6 +28,7 @@ require (
        github.com/spf13/cobra v1.7.0
        github.com/spf13/viper v1.16.0
        github.com/whilp/git-urls v1.0.0
+       go.starlark.net v0.0.0-20200306205701-8dd3e2ee1dd5
        golang.org/x/crypto v0.12.0
        golang.org/x/mod v0.10.0
        golang.org/x/text v0.12.0
$ git diff wasm go.sum
diff --git a/go.sum b/go.sum
index 6fe3536..0caf20c 100644
--- a/go.sum
+++ b/go.sum
@@ -1702,6 +1702,7 @@ go.opentelemetry.io/otel/trace v0.20.0/go.mod h1:6GjCW8zgDjwGHGa6GkyeB8+/5vjT16g
 go.opentelemetry.io/otel/trace v1.0.0-RC1/go.mod h1:86UHmyHWFEtWjfWPSbu0+d0Pf9Q6e1U+3ViBOc+NXAg=
 go.opentelemetry.io/proto/otlp v0.7.0/go.mod h1:PqfVotwruBrMGOCsRd/89rSnXhoiJIqeYNgFYFoEGnI=
 go.opentelemetry.io/proto/otlp v0.9.0/go.mod h1:1vKfU9rv61e9EVGthD1zNvUbiwPcimSsOPU9brfSHJg=
+go.starlark.net v0.0.0-20200306205701-8dd3e2ee1dd5 h1:+FNtrFTmVw0YZGpBGX56XDee331t6JAXeK2bcyhLOOc=
 go.starlark.net v0.0.0-20200306205701-8dd3e2ee1dd5/go.mod h1:nmDLcffg48OtT/PSW0Hg7FvpRQsQh5OSqIylirxKC7o=
 go.uber.org/atomic v1.3.2/go.mod h1:gD2HeocX3+yG+ygLZcrzQJaqmWj9AIm7n08wl/qW/PE=
 go.uber.org/atomic v1.4.0/go.mod h1:gD2HeocX3+yG+ygLZcrzQJaqmWj9AIm7n08wl/qW/PE=

HarikrishnanBalagopal avatar Dec 26 '23 10:12 HarikrishnanBalagopal

Thanks, but I still can't reproduce on 1.21 for some reason

$ CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm go1.21.5 build
$ CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm gotip build
# github.com/konveyor/move2kube-wasm
type:*github.com/mholt/archiver/v3.TarGz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarGz).Match is too big: 0x100010000
type:*github.com/mholt/archiver/v3.TarGz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarGz).Match is too big: 0x100010000
type:*github.com/mholt/archiver/v3.TarGz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarGz).Read is too big: 0x100030000 
# ...

mauri870 avatar Dec 26 '23 10:12 mauri870

type:*github.com/mholt/archiver/v3.TarGz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarGz).Match is too big: 0x100010000

I might be confused but the output you have shown includes the compile error. Are you trying to reproduce something else?

HarikrishnanBalagopal avatar Dec 26 '23 11:12 HarikrishnanBalagopal

Sorry, I think I was not clear enough. With 1.21.5 it built just fine, the error you see is for gotip(1.22).

mauri870 avatar Dec 26 '23 11:12 mauri870

Sorry, I think I was not clear enough. With 1.21.5 it built just fine, the error you see is for gotip(1.22).

hmm, that's weird the line I linked hasn't changed very much https://github.com/golang/go/blob/2184a394777ccc9ce9625932b2ad773e6e626be0/src/cmd/link/internal/wasm/asm.go#L157 since it was added. The error due to function size limit should be in all the versions.

Update

@mauri870 I just updated to v1.21.5 and I am still getting the error. I am using the go formula provided by brew https://formulae.brew.sh/formula/go The WASM app commit hash is 95c7fb33c04bb31d3d5e25a8553930693de86194

$ go version
go version go1.21.5 darwin/arm64
$ git log
commit 95c7fb33c04bb31d3d5e25a8553930693de86194 (HEAD -> feat/starlark, origin/feat/starlark)
Author: Harikrishnan Balagopal <[email protected]>
Date:   Tue Dec 26 15:04:57 2023 +0530

    feat: add the starlark transformer
    
    chore: update dependencies
    fix: issue with string not implementing a starlark interface
    
    Signed-off-by: Harikrishnan Balagopal <[email protected]>
$ git status
On branch feat/starlark
Your branch is up to date with 'origin/feat/starlark'.

nothing to commit, working tree clean
$ make build
mkdir -p "./bin"
CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm go build -ldflags ' -X github.com/konveyor/move2kube-wasm/types/info.buildmetadata=unreleased -X github.com/konveyor/move2kube-wasm/types/info.gitCommit=95c7fb33c04bb31d3d5e25a8553930693de86194 -X github.com/konveyor/move2kube-wasm/types/info.gitTreeState=clean' -o "./bin/move2kube.wasm" .
# github.com/konveyor/move2kube-wasm
type:*github.com/mholt/archiver/v3.TarGz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarGz).Write is too big: 0x100010000
type:*github.com/mholt/archiver/v3.TarGz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarGz).Write is too big: 0x100010000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).CheckPath is too big: 0x100030000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).CheckPath is too big: 0x100030000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Close is too big: 0x100050000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Close is too big: 0x100050000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Match is too big: 0x100070000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Match is too big: 0x100070000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Read is too big: 0x100090000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Read is too big: 0x100090000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Write is too big: 0x1000b0000
type:*github.com/mholt/archiver/v3.TarLz4: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarLz4).Write is too big: 0x1000b0000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).CheckPath is too big: 0x1000d0000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).CheckPath is too big: 0x1000d0000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Close is too big: 0x1000f0000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Close is too big: 0x1000f0000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Match is too big: 0x100110000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Match is too big: 0x100110000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Read is too big: 0x100130000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Read is too big: 0x100130000
type:*github.com/mholt/archiver/v3.TarSz: non-pc-relative relocation address for github.com/mholt/archiver/v3.(*TarSz).Write is too big: 0x100150000
/opt/homebrew/Cellar/go/1.21.5/libexec/pkg/tool/darwin_arm64/link: too many errors
make: *** [build] Error 1

HarikrishnanBalagopal avatar Dec 26 '23 11:12 HarikrishnanBalagopal

I managed to reproduce it consistently in go 1.21 now, thanks. I would not trust on my initial bisecting results because the repro was not very consistent.

I was able to reproduce the issue with:

git clone https://github.com/HarikrishnanBalagopal/move2kube.git -b feat/starlark
cd move2kube
GOOS=js GOARCH=wasm go1.21.5 build

Since 1.20 does not have the wasip1 port, I tried with GOOS=js and it compiled just fine, so it appears to not be affected.

It is unclear to me where the issue is, but since programs compile just fine in Go 1.20 and we have the same function size in 1.20, 1.21 and tip something changed between 1.20 and 1.21 that caused the error to appear.

@gopherbot please backport to Go 1.21, this is a linker issue when compiling large wasm programs without a workaround.

mauri870 avatar Dec 26 '23 12:12 mauri870

Backport issue(s) opened: #64867 (for 1.20), #64868 (for 1.21).

Remember to create the cherry-pick CL(s) as soon as the patch is submitted to master, according to https://go.dev/wiki/MinorReleases.

gopherbot avatar Dec 26 '23 12:12 gopherbot

I tried bisecting again and it points to CL 484856. I tried the parent commit and it works fine, but fails on the CL commit.

I have honestly no idea why this change would cause relocations to overflow in large wasm programs.

cc @randall77 @dr2chase (sorry about the double cc, I posted in the backport issue before by mistake)

mauri870 avatar Dec 26 '23 13:12 mauri870

It seems to me that the size of a WASM function is limited to 2^16 = 65536 bytes? ldr.SetSymValue(s, int64(funcValueOffset+va/ld.MINFUNC)<<16) // va starts at zero

This line does not limit a WASM function's size to 65536 bytes. In our WASM backend, the "PC" is an index of a basic block, not a byte count or instruction count. To overflow that limit, the function needs to have more than 65536 basic blocks, which is possible but quite rare.

cherrymui avatar Dec 26 '23 16:12 cherrymui

It seems to me that the size of a WASM function is limited to 2^16 = 65536 bytes? ldr.SetSymValue(s, int64(funcValueOffset+va/ld.MINFUNC)<<16) // va starts at zero

This line does not limit a WASM function's size to 65536 bytes. In our WASM backend, the "PC" is an index of a basic block, not a byte count or instruction count. To overflow that limit, the function needs to have more than 65536 basic blocks, which is possible but quite rare.

	// The following rules describe how wasm handles function indices and addresses:
	//   PC_F = funcValueOffset + WebAssembly function index (not including the imports)
	//   s.Value = PC = PC_F<<16 + PC_B
	//
	// The funcValueOffset is necessary to avoid conflicts with expectations
	// that the Go runtime has about function addresses.
	// The field "s.Value" corresponds to the concept of PC at runtime.
	// However, there is no PC register, only PC_F and PC_B. PC_F denotes the function,
	// PC_B the resume point inside of that function. The entry of the function has PC_B = 0.

hmm, the comment above that line makes it seem like it's a regular PC (but calculated from 2 values PC_F and PC_B).

  • What is the size of a basic block?
  • Why is it triggering the compile error in the above case then? Is it going over the 65536 basic blocks limit?

HarikrishnanBalagopal avatar Dec 26 '23 17:12 HarikrishnanBalagopal

It is not a regular PC. PC_B only increments per "resume point", which is essentially per basic block. How many instructions in a basic block and how many bytes are used to encode those instructions do not matter.

I'll look into what the cause of the error is. I'm not sure yet, but it is probably not the basic block number limit.

cherrymui avatar Dec 26 '23 17:12 cherrymui

It is not the basic block number limit, but the total number of (reachable) functions. As you saw in the comment above, PC = PC_F<<16 + PC_B, where PC_F is function index. With the current encoding scheme, when there are more than 65536 functions, PC is larger than 32-bit. The method table uses a 32-bit offset for the PC of the method. So it overflows. (The bisection probably just points to a CL that just increases the total number of functions slightly and pushes it over the limit.)

We might be able to change the encoding scheme. E.g. we could change the method table to encode only the PC_F part, as we never call to the middle of a method. But there are places where we call to the middle of a function: e.g. preemption and resumption. That will make things more complicated.

cc @neelance

cherrymui avatar Dec 26 '23 17:12 cherrymui

Change https://go.dev/cl/552835 mentions this issue: cmd/link, runtime: put only function index in method table

gopherbot avatar Dec 26 '23 21:12 gopherbot

CL https://go.dev/cl/552835 changes the method table encoding to allow more than 65536 functions. Now https://github.com/HarikrishnanBalagopal/move2kube/tree/feat/starlark builds. Could you test if the resulting binary is correct? Thanks.

I don't really like the CL, as it adds more special case for Wasm. But maybe it is fine...

cherrymui avatar Dec 26 '23 21:12 cherrymui

It is not the basic block number limit, but the total number of (reachable) functions. As you saw in the comment above, PC = PC_F<<16 + PC_B, where PC_F is function index. With the current encoding scheme, when there are more than 65536 functions, PC is larger than 32-bit. The method table uses a 32-bit offset for the PC of the method. So it overflows. (The bisection probably just points to a CL that just increases the total number of functions slightly and pushes it over the limit.)

We might be able to change the encoding scheme. E.g. we could change the method table to encode only the PC_F part, as we never call to the middle of a method. But there are places where we call to the middle of a function: e.g. preemption and resumption. That will make things more complicated.

cc @neelance

Is it necessary to keep the size to 32bit? The line shows an explicit cast to int64 https://github.com/golang/go/blob/649671b08fbd49bcf65578b18d188d55779e6eca/src/cmd/link/internal/wasm/asm.go#L90 Both the input va and the return value are also uint64 https://github.com/golang/go/blob/649671b08fbd49bcf65578b18d188d55779e6eca/src/cmd/link/internal/wasm/asm.go#L91-L92

Since the WASM functions live in a separate address space to the WASM linear memory, it should not be affected by the same constraints when it comes to address bit size.

HarikrishnanBalagopal avatar Dec 27 '23 05:12 HarikrishnanBalagopal

CL https://go.dev/cl/552835 changes the method table encoding to allow more than 65536 functions. Now https://github.com/HarikrishnanBalagopal/move2kube/tree/feat/starlark builds. Could you test if the resulting binary is correct? Thanks.

I don't really like the CL, as it adds more special case for Wasm. But maybe it is fine...

Do I need to fetch the git fetch https://go.googlesource.com/go refs/changes/35/552835/2 && git checkout -b change-552835 FETCH_HEAD changes and build to get the Go compiler with the changes? If you have the pre-built wasm binary I can test that directly.

Update 1

I was able to build the Go compiler with the changes.

$ ./make.bash 
Building Go cmd/dist using /opt/homebrew/Cellar/go/1.21.5/libexec. (go1.21.5 darwin/arm64)
Building Go toolchain1 using /opt/homebrew/Cellar/go/1.21.5/libexec.
Building Go bootstrap cmd/go (go_bootstrap) using Go toolchain1.
Building Go toolchain2 using go_bootstrap and Go toolchain1.
Building Go toolchain3 using go_bootstrap and Go toolchain2.
Building packages and commands for darwin/arm64.
---
Installed Go for darwin/arm64 in /Users/haribala/Documents/code/remote/go.googlesource.com/go
Installed commands in /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin
*** You need to add /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin to your PATH.

I was able to build the WASM app with the new compiler

$ CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin/go build -ldflags ' -X github.com/konveyor/move2kube-wasm/types/info.buildmetadata=unreleased -X github.com/konveyor/move2kube-wasm/types/info.gitCommit=95c7fb33c04bb31d3d5e25a8553930693de86194 -X github.com/konveyor/move2kube-wasm/types/info.gitTreeState=clean' -o "./bin/move2kube.wasm" .
$ echo $?
0

This is the compressed WASM binary move2kube.wasm.gz

Update 2

@cherrymui Running the new WASM binary gives a very large stack trace and a fatal error at the end. For comparison, here's a working version https://move2kube.konveyor.io/experimental

This is the partial stack trace that we were able to capture https://gist.github.com/HarikrishnanBalagopal/80ca5e1d359ffdafd1692700b3370168

fatal error: invalid runtime symbol table
runtime: panic before malloc heap initialized

runtime stack:
runtime.throw({0x4aae37, 0x1c})
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/panic.go:1023 +0x3 fp=0x27e4628 sp=0x27e4600 pc=0x13710003
runtime.moduledataverify1(0x2699700)
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/symtab.go:553 +0x8d fp=0x27e4720 sp=0x27e4628 pc=0x148c008d
runtime.moduledataverify(...)
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/symtab.go:518
runtime.schedinit()
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/proc.go:783 +0xb fp=0x27e4770 sp=0x27e4720 pc=0x13a8000b
runtime.rt0_go()
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/asm_wasm.s:22 +0x3 fp=0x27e4778 sp=0x27e4770 pc=0x160b0003

Steps:

  • gzip -f bin/move2kube.wasm to compress the WASM binary.
  • cd m2k-web-ui && pnpm install to install dependencies.
  • cd .. go back to the parent directory.
  • make dev to start the webpack dev server. (This also copies the compressed WASM binary into the dist folder). Alternatively you can also use make build-web && make serve-web to build in production mode.
  • Go to http://127.0.0.1:8080/ and give an input zip file to analyze. We used the language-platforms sample from here https://github.com/konveyor/move2kube-demos/tree/main/samples/language-platforms. Here's the zip file for convenience: language-platforms.zip
image

Update 3

@cherrymui So with the new compiler changes, even the wasm branch (without the starlark-go library https://github.com/konveyor/move2kube/tree/wasm) is also failing with fatal error move2kube.wasm.gz

https://gist.github.com/HarikrishnanBalagopal/d59b6f5a724dc49e207de967f2394e84

fatal error: invalid runtime symbol table
runtime: panic before malloc heap initialized

runtime stack:
runtime.throw({0x4a2792, 0x1c})
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/panic.go:1023 +0x3 fp=0x27a0c48 sp=0x27a0c20 pc=0x13700003
runtime.moduledataverify1(0x2656660)
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/symtab.go:553 +0x8d fp=0x27a0d40 sp=0x27a0c48 pc=0x148b008d
runtime.moduledataverify(...)
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/symtab.go:518
runtime.schedinit()
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/proc.go:783 +0xb fp=0x27a0d90 sp=0x27a0d40 pc=0x13a7000b
runtime.rt0_go()
        /Users/haribala/Documents/code/remote/go.googlesource.com/go/src/runtime/asm_wasm.s:22 +0x3 fp=0x27a0d98 sp=0x27a0d90 pc=0x160a0003

Update 4

Managed to capture the beginning of the stack trace: https://gist.github.com/HarikrishnanBalagopal/539cb78919807beeceba33049b2b2e4d

function symbol table not sorted by PC offset: 0xffff0000 github.com/mholt/archiver/v3.(*TarGz).Close > 0x0 github.com/mholt/archiver/v3.TarGz.Match , plugin: 
	 0x10000000 
	 0x10010000 internal/abi.(*RegArgs).Dump
	 0x10020000 internal/abi.(*RegArgs).IntRegArgAddr
	 0x10030000 internal/abi.(*IntArgRegBitmap).Set

HarikrishnanBalagopal avatar Dec 27 '23 05:12 HarikrishnanBalagopal

@cherrymui The panic seems to be coming from https://github.com/golang/go/blob/26ba75fe5927a078695288da0efefba37b4a4d6e/src/runtime/symtab.go#L546 and https://github.com/golang/go/blob/26ba75fe5927a078695288da0efefba37b4a4d6e/src/runtime/symtab.go#L553

HarikrishnanBalagopal avatar Dec 27 '23 09:12 HarikrishnanBalagopal

Thanks for trying the code and posting the error message. It seems the function table will need a similar update. I'll look into that.

Is it necessary to keep the size to 32bit?

Yes. It is not va that needs to be in 32-bit, but the relative addresses are stored in the binary as 32-bit in various places. If that value overflows 32-bit, the stored relative address is truncated and incorrect. (Please refrain from commenting on the code. The failure mode and error message are helpful, but the comments on the code are not. Thanks.)

cherrymui avatar Dec 27 '23 15:12 cherrymui

Thanks for trying the code and posting the error message. It seems the function table will need a similar update. I'll look into that.

Is it necessary to keep the size to 32bit?

Yes. It is not va that needs to be in 32-bit, but the relative addresses are stored in the binary as 32-bit in various places. If that value overflows 32-bit, the stored relative address is truncated and incorrect. (Please refrain from commenting on the code. The failure mode and error message are helpful, but the comments on the code are not. Thanks.)

Thanks, please let me know when you make the changes to the function table and I will test them out as well.

HarikrishnanBalagopal avatar Dec 29 '23 07:12 HarikrishnanBalagopal

Any update on this?

HarikrishnanBalagopal avatar Jan 03 '24 11:01 HarikrishnanBalagopal

I was OOO last week and I'm just back. I'll work on the function table change. Thanks.

cherrymui avatar Jan 09 '24 16:01 cherrymui

I was OOO last week and I'm just back. I'll work on the function table change. Thanks.

Np, hope you had a good vacation. Please let me know if there's any update on this.

HarikrishnanBalagopal avatar Jan 22 '24 04:01 HarikrishnanBalagopal

Hi! Any update on this? now that v1.22 has been released.

HarikrishnanBalagopal avatar Feb 13 '24 17:02 HarikrishnanBalagopal

Not yet. Still working on it. I hope to get a new version of the fix by this week.

cherrymui avatar Feb 13 '24 18:02 cherrymui

@HarikrishnanBalagopal could you try the new version of CL https://go.dev/cl/552835 ? Thanks.

cherrymui avatar Feb 14 '24 18:02 cherrymui

@HarikrishnanBalagopal could you try the new version of CL https://go.dev/cl/552835 ? Thanks.

Sorry, I went on vacation myself 😅 I will try it tomorrow and update here.

Update 1

@cherrymui I have tried the change and it failed to build the wasm webapp.

  1. Building the patch set 5 Go commit 06039ae75fa4505de13184f520fe1c6bd0bb7bc9 https://go.googlesource.com/go/+/06039ae75fa4505de13184f520fe1c6bd0bb7bc9
$ go version
go version go1.22.0 darwin/arm64
$ git remote -v
origin	https://go.googlesource.com/go (fetch)
origin	https://go.googlesource.com/go (push)
$ git log
commit 06039ae75fa4505de13184f520fe1c6bd0bb7bc9 (HEAD -> change-552835, tag: change-patchset-5)
Author: Cherry Mui <[email protected]>
Date:   Tue Dec 26 15:35:56 2023 -0500

    cmd/link, runtime: put only function index in method table and func table
.................
$ cd src/ && ./make.bash 
Building Go cmd/dist using /opt/homebrew/Cellar/go/1.22.0/libexec. (go1.22.0 darwin/arm64)
Building Go toolchain1 using /opt/homebrew/Cellar/go/1.22.0/libexec.
Building Go bootstrap cmd/go (go_bootstrap) using Go toolchain1.
Building Go toolchain2 using go_bootstrap and Go toolchain1.
Building Go toolchain3 using go_bootstrap and Go toolchain2.
Building packages and commands for darwin/arm64.
---
Installed Go for darwin/arm64 in /Users/haribala/Documents/code/remote/go.googlesource.com/go
Installed commands in /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin
*** You need to add /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin to your PATH.
  1. Building the wasm webapp using the same commit 95c7fb33c04bb31d3d5e25a8553930693de86194 https://github.com/HarikrishnanBalagopal/move2kube/tree/95c7fb33c04bb31d3d5e25a8553930693de86194
$ /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin/go version
go version devel go1.23-06039ae75f Thu Feb 15 13:53:32 2024 -0500 darwin/arm64
$ git log
commit 95c7fb33c04bb31d3d5e25a8553930693de86194 (HEAD -> feat/starlark, origin/feat/starlark)
Author: Harikrishnan Balagopal <[email protected]>
Date:   Tue Dec 26 15:04:57 2023 +0530

    feat: add the starlark transformer
.................
$ CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin/go build -ldflags ' -X github.com/konveyor/move2kube-wasm/types/info.buildmetadata=unreleased -X github.com/konveyor/move2kube-wasm/types/info.gitCommit=95c7fb33c04bb31d3d5e25a8553930693de86194 -X github.com/konveyor/move2kube-wasm/types/info.gitTreeState=clean' -o "./bin/move2kube.wasm" .
# github.com/konveyor/move2kube-wasm
github.com/mholt/archiver/v3.(*Rar).Close.wrapinfo: non-pc-relative relocation R_ADDROFF address for github.com/mholt/archiver/v3.(*Rar).Close is too big: 0x1007b0000
github.com/mholt/archiver/v3.(*Tar).Close.wrapinfo: non-pc-relative relocation R_ADDROFF address for github.com/mholt/archiver/v3.(*Tar).Close is too big: 0x100a80000
github.com/mholt/archiver/v3.(*Zip).Close.wrapinfo: non-pc-relative relocation R_ADDROFF address for github.com/mholt/archiver/v3.(*Zip).Close is too big: 0x101420000
$ echo $?
1

The wasm webapp build fails now.

With the previous change we were able to build the wasm webapp at least https://github.com/golang/go/issues/64856#issuecomment-1869962501 and it was failing at runtime.

One difference is that I used go version go1.21.5 darwin/arm64 when building the Go compiler before. Now I am using go version go1.22.0 darwin/arm64 to build the Go compiler.

Update 2

The new changed Go compiler 06039ae75fa4505de13184f520fe1c6bd0bb7bc9 is able to build the parent commit which doesn't have the Starlark library and all the new functions that it brings in https://github.com/HarikrishnanBalagopal/move2kube/tree/dec9d8da6e5f8882aacb46a8e5f784b96b42a3c6

$ CGO_ENABLED=0 GOOS=wasip1 GOARCH=wasm /Users/haribala/Documents/code/remote/go.googlesource.com/go/bin/go build -ldflags ' -X github.com/konveyor/move2kube-wasm/types/info.buildmetadata=unreleased -X github.com/konveyor/move2kube-wasm/types/info.gitCommit=dec9d8da6e5f8882aacb46a8e5f784b96b42a3c6 -X github.com/konveyor/move2kube-wasm/types/info.gitTreeState=clean' -o "./bin/move2kube.wasm" .
$ echo $?
0

Update 3

@cherrymui I think there's a regression with v1.22.0 of Golang https://github.com/golang/go/issues/65786

HarikrishnanBalagopal avatar Feb 18 '24 16:02 HarikrishnanBalagopal

@cherrymui Please let me know if you need any more details.

HarikrishnanBalagopal avatar Feb 27 '24 10:02 HarikrishnanBalagopal