Repository: tetratelabs/wazero (go)

Issue:
compiler(arm64) overflow in call relocations
**Describe the bug**

A wasm module that was being compiled and instantiated with wazero 1.6.0 successfully now segfaults with version 1.7.0.

**To Reproduce**
I am building my own experimental tool that embeds wazero for supporting wasm. Here is a link to the wasm file I was testing with:
https://github.com/davidmdm/flights/releases/download/v0.0.0-yokecd-test/pg.wasm

This module is an executable that should output some JSON to stdout.

This is the code I use to intantiate it:

```go
package wasi

import (
	"bytes"
	"context"
	"crypto/rand"
	"fmt"
	"io"

	"github.com/tetratelabs/wazero"
	"github.com/tetratelabs/wazero/imports/wasi_snapshot_preview1"

	"github.com/davidmdm/x/xerr"
)

func Execute(ctx context.Context, wasm []byte, release string, stdin io.Reader, args ...string) (output []byte, err error) {
	cfg := wazero.
		NewRuntimeConfig().
		WithCloseOnContextDone(true)

	// Create a new WebAssembly Runtime.
	wasi := wazero.NewRuntimeWithConfig(ctx, cfg)
	defer func() {
		err = xerr.MultiErrFrom("", err, wasi.Close(ctx))
	}()

	wasi_snapshot_preview1.MustInstantiate(ctx, wasi)

	// Because we are running a binary directly rather than embedding in an application,
	// we default to wiring up commonly used OS functionality.
	mod, err := wasi.CompileModule(ctx, wasm)
	if err != nil {
		return nil, fmt.Errorf("failed to compile module: %w", err)
	}

	var (
		stdout bytes.Buffer
		stderr bytes.Buffer
	)

	moduleCfg := wazero.
		NewModuleConfig().
		WithStdout(&stdout).
		WithStderr(&stderr).
		WithRandSource(rand.Reader).
		WithSysNanosleep().
		WithSysNanotime().
		WithSysWalltime().
		WithArgs(append([]string{release}, args...)...)

	if stdin != nil {
		moduleCfg = moduleCfg.WithStdin(stdin)
	}

	if _, err := wasi.InstantiateModule(ctx, mod, moduleCfg); err != nil {
		details := stderr.String()
		if details == "" {
			details = "(no output captured on stderr)"
		}
		return nil, fmt.Errorf("failed to instantiate module: %w: stderr: %s", err, details)
	}

	return stdout.Bytes(), nil
}
```


**Expected behavior**

I expect the wasm file to be executed without segfaults, and to produce the same output as wazero 1.6.0

**Screenshots**
<img width="1014" alt="image" src="https://github.com/tetratelabs/wazero/assets/12768642/aec4eb60-ab67-43b8-add2-115df4ca8811">

**Environment (please complete the relevant information):**
- go version go1.22.1 darwin/arm64
- wazero Version: 1.7.0
- Host architecture: arm64

**Additional context**
Add any other context about the problem here.


Pull request description:
compiler(arm64): fixes overflow in huge executable relocations
Obviates https://github.com/tetratelabs/wazero/pull/2169 and fixes #2158 

Patch:
diff --git a/internal/engine/wazevo/backend/compiler.go b/internal/engine/wazevo/backend/compiler.go
index ddb85893..59bbfe02 100644
--- a/internal/engine/wazevo/backend/compiler.go
+++ b/internal/engine/wazevo/backend/compiler.go
@@ -52,7 +52,7 @@ type Compiler interface {
 
 	// Finalize performs the finalization of the compilation, including machine code emission.
 	// This must be called after RegAlloc.
-	Finalize(ctx context.Context)
+	Finalize(ctx context.Context) error
 
 	// Buf returns the buffer of the encoded machine code. This is only used for testing purpose.
 	Buf() []byte
@@ -175,7 +175,9 @@ func (c *compiler) Compile(ctx context.Context) ([]byte, []RelocationInfo, error
 	if wazevoapi.DeterministicCompilationVerifierEnabled {
 		wazevoapi.VerifyOrSetDeterministicCompilationContextValue(ctx, "After Register Allocation", c.Format())
 	}
-	c.Finalize(ctx)
+	if err := c.Finalize(ctx); err != nil {
+		return nil, nil, err
+	}
 	if wazevoapi.PrintFinalizedMachineCode && wazevoapi.PrintEnabledIndex(ctx) {
 		fmt.Printf("[[[after finalize for %s]]]%s\n", wazevoapi.GetCurrentFunctionName(ctx), c.Format())
 	}
@@ -191,9 +193,9 @@ func (c *compiler) RegAlloc() {
 }
 
 // Finalize implements Compiler.Finalize.
-func (c *compiler) Finalize(ctx context.Context) {
+func (c *compiler) Finalize(ctx context.Context) error {
 	c.mach.PostRegAlloc()
-	c.mach.Encode(ctx)
+	return c.mach.Encode(ctx)
 }
 
 // setCurrentGroupID sets the current instruction group ID.
diff --git a/internal/engine/wazevo/backend/isa/amd64/machine.go b/internal/engine/wazevo/backend/isa/amd64/machine.go
index 0bccf967..7012dff0 100644
--- a/internal/engine/wazevo/backend/isa/amd64/machine.go
+++ b/internal/engine/wazevo/backend/isa/amd64/machine.go
@@ -1963,7 +1963,7 @@ func (m *machine) encodeWithoutSSA(root *instruction) {
 }
 
 // Encode implements backend.Machine Encode.
-func (m *machine) Encode(ctx context.Context) {
+func (m *machine) Encode(ctx context.Context) (err error) {
 	ectx := m.ectx
 	bufPtr := m.c.BufPtr()
 
@@ -2055,10 +2055,11 @@ func (m *machine) Encode(ctx context.Context) {
 			panic("BUG")
 		}
 	}
+	return
 }
 
 // ResolveRelocations implements backend.Machine.
-func (m *machine) ResolveRelocations(refToBinaryOffset map[ssa.FuncRef]int, binary []byte, relocations []backend.RelocationInfo) {
+func (m *machine) ResolveRelocations(refToBinaryOffset map[ssa.FuncRef]int, binary []byte, relocations []backend.RelocationInfo, _ []int) {
 	for _, r := range relocations {
 		offset := r.Offset
 		calleeFnOffset := refToBinaryOffset[r.FuncRef]
@@ -2072,6 +2073,9 @@ func (m *machine) ResolveRelocations(refToBinaryOffset map[ssa.FuncRef]int, bina
 	}
 }
 
+// CallTrampolineIslandInfo implements backend.Machine CallTrampolineIslandInfo.
+func (m *machine) CallTrampolineIslandInfo(_ int) (_, _ int, _ error) { return }
+
 func (m *machine) lowerIcmpToFlag(xd, yd *backend.SSAValueDefinition, _64 bool) {
 	x := m.getOperand_Reg(xd)
 	y := m.getOperand_Mem_Imm32_Reg(yd)
diff --git a/internal/engine/wazevo/backend/isa/arm64/instr_encoding.go b/internal/engine/wazevo/backend/isa/arm64/instr_encoding.go
index 513ad6fb..227a9647 100644
--- a/internal/engine/wazevo/backend/isa/arm64/instr_encoding.go
+++ b/internal/engine/wazevo/backend/isa/arm64/instr_encoding.go
@@ -10,9 +10,13 @@ import (
 )
 
 // Encode implements backend.Machine Encode.
-func (m *machine) Encode(ctx context.Context) {
+func (m *machine) Encode(ctx context.Context) error {
 	m.resolveRelativeAddresses(ctx)
 	m.encode(m.executableContext.RootInstr)
+	if l := len(m.compiler.Buf()); l > maxFunctionExecutableSize {
+		return fmt.Errorf("function size exceeds the limit: %d > %d", l, maxFunctionExecutableSize)
+	}
+	return nil
 }
 
 func (m *machine) encode(root *instruction) {
diff --git a/internal/engine/wazevo/backend/isa/arm64/machine.go b/internal/engine/wazevo/backend/isa/arm64/machine.go
index e845ee93..dbdb18dd 100644
--- a/internal/engine/wazevo/backend/isa/arm64/machine.go
+++ b/internal/engine/wazevo/backend/isa/arm64/machine.go
@@ -388,11 +388,11 @@ func (m *machine) resolveRelativeAddresses(ctx context.Context) {
 }
 
 const (
-	maxSignedInt26 int64 = 1<<25 - 1
-	minSignedInt26 int64 = -(1 << 25)
+	maxSignedInt26 = 1<<25 - 1
+	minSignedInt26 = -(1 << 25)
 
-	maxSignedInt19 int64 = 1<<19 - 1
-	minSignedInt19 int64 = -(1 << 19)
+	maxSignedInt19 = 1<<19 - 1
+	minSignedInt19 = -(1 << 19)
 )
 
 func (m *machine) insertConditionalJumpTrampoline(cbr *instruction, currentBlk *labelPosition, nextLabel label) {
diff --git a/internal/engine/wazevo/backend/isa/arm64/machine_relocation.go b/internal/engine/wazevo/backend/isa/arm64/machine_relocation.go
index 8b619770..959c744a 100644
--- a/internal/engine/wazevo/backend/isa/arm64/machine_relocation.go
+++ b/internal/engine/wazevo/backend/isa/arm64/machine_relocation.go
@@ -1,34 +1,118 @@
 package arm64
 
 import (
+	"encoding/binary"
 	"fmt"
+	"math"
+	"sort"
 
 	"github.com/tetratelabs/wazero/internal/engine/wazevo/backend"
 	"github.com/tetratelabs/wazero/internal/engine/wazevo/ssa"
 )
 
+const (
+	// trampolineCallSize is the size of the trampoline instruction sequence for each function in an island.
+	trampolineCallSize = 4*4 + 4 // Four instructions + 32-bit immediate.
+
+	// Unconditional branch offset is encoded as divided by 4 in imm26.
+	// https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/BL--Branch-with-Link-?lang=en
+
+	maxUnconditionalBranchOffset = maxSignedInt26 * 4
+	minUnconditionalBranchOffset = minSignedInt26 * 4
+
+	// trampolineIslandInterval is the range of the trampoline island.
+	// Half of the range is used for the trampoline island, and the other half is used for the function.
+	trampolineIslandInterval = maxUnconditionalBranchOffset / 2
+
+	// maxNumFunctions explicitly specifies the maximum number of functions that can be allowed in a single executable.
+	maxNumFunctions = trampolineIslandInterval >> 6
+
+	// maxFunctionExecutableSize is the maximum size of a function that can exist in a trampoline island.
+	// Conservatively set to 1/4 of the trampoline island interval.
+	maxFunctionExecutableSize = trampolineIslandInterval >> 2
+)
+
+// CallTrampolineIslandInfo implements backend.Machine CallTrampolineIslandInfo.
+func (m *machine) CallTrampolineIslandInfo(numFunctions int) (interval, size int, err error) {
+	if numFunctions > maxNumFunctions {
+		return 0, 0, fmt.Errorf("too many functions: %d > %d", numFunctions, maxNumFunctions)
+	}
+	return trampolineIslandInterval, trampolineCallSize * numFunctions, nil
+}
+
 // ResolveRelocations implements backend.Machine ResolveRelocations.
-//
-// TODO: unit test!
-func (m *machine) ResolveRelocations(refToBinaryOffset map[ssa.FuncRef]int, binary []byte, relocations []backend.RelocationInfo) {
+func (m *machine) ResolveRelocations(
+	refToBinaryOffset map[ssa.FuncRef]int,
+	executable []byte,
+	relocations []backend.RelocationInfo,
+	callTrampolineIslandOffsets []int,
+) {
+	for _, islandOffset := range callTrampolineIslandOffsets {
+		encodeCallTrampolineIsland(refToBinaryOffset, islandOffset, executable)
+	}
+
 	for _, r := range relocations {
 		instrOffset := r.Offset
 		calleeFnOffset := refToBinaryOffset[r.FuncRef]
-		brInstr := binary[instrOffset : instrOffset+4]
 		diff := int64(calleeFnOffset) - (instrOffset)
 		// Check if the diff is within the range of the branch instruction.
-		if diff < -(1<<25)*4 || diff > ((1<<25)-1)*4 {
-			panic(fmt.Sprintf("TODO: too large binary where branch target is out of the supported range +/-128MB: %#x", diff))
+		if diff < minUnconditionalBranchOffset || diff > maxUnconditionalBranchOffset {
+			// Find the near trampoline island from callTrampolineIslandOffsets.
+			islandOffset := searchTrampolineIsland(callTrampolineIslandOffsets, int(instrOffset))
+			islandTargetOffset := islandOffset + trampolineCallSize*int(r.FuncRef)
+			diff = int64(islandTargetOffset) - (instrOffset)
+			if diff < minUnconditionalBranchOffset || diff > maxUnconditionalBranchOffset {
+				panic("BUG in trampoline placement")
+			}
 		}
-		// https://developer.arm.com/documentation/ddi0596/2020-12/Base-Instructions/BL--Branch-with-Link-
-		imm26 := diff / 4
-		brInstr[0] = byte(imm26)
-		brInstr[1] = byte(imm26 >> 8)
-		brInstr[2] = byte(imm26 >> 16)
-		if diff < 0 {
-			brInstr[3] = (byte(imm26 >> 24 & 0b000000_01)) | 0b100101_10 // Set sign bit.
-		} else {
-			brInstr[3] = (byte(imm26 >> 24 & 0b000000_01)) | 0b100101_00 // No sign bit.
+		binary.LittleEndian.PutUint32(executable[instrOffset:instrOffset+4], encodeUnconditionalBranch(true, diff))
+	}
+}
+
+// encodeCallTrampolineIsland encodes a trampoline island for the given functions.
+// Each island consists of a trampoline instruction sequence for each function.
+// Each trampoline instruction sequence consists of 4 instructions + 32-bit immediate.
+func encodeCallTrampolineIsland(refToBinaryOffset map[ssa.FuncRef]int, islandOffset int, executable []byte) {
+	for i := 0; i < len(refToBinaryOffset); i++ {
+		trampolineOffset := islandOffset + trampolineCallSize*i
+
+		fnOffset := refToBinaryOffset[ssa.FuncRef(i)]
+		diff := fnOffset - (trampolineOffset + 16)
+		if diff > math.MaxInt32 || diff < math.MinInt32 {
+			// This case even amd64 can't handle. 4GB is too big.
+			panic("too big binary")
 		}
+
+		// The tmpReg, tmpReg2 is safe to overwrite (in fact any caller-saved register is safe to use).
+		tmpReg, tmpReg2 := regNumberInEncoding[tmpRegVReg.RealReg()], regNumberInEncoding[x11]
+
+		// adr tmpReg, PC+16: load the address of #diff into tmpReg.
+		binary.LittleEndian.PutUint32(executable[trampolineOffset:], encodeAdr(tmpReg, 16))
+		// ldrsw tmpReg2, [tmpReg]: Load #diff into tmpReg2.
+		binary.LittleEndian.PutUint32(executable[trampolineOffset+4:],
+			encodeLoadOrStore(sLoad32, tmpReg2, addressMode{kind: addressModeKindRegUnsignedImm12, rn: tmpRegVReg}))
+		// add tmpReg, tmpReg2, tmpReg: add #diff to the address of #diff, getting the absolute address of the function.
+		binary.LittleEndian.PutUint32(executable[trampolineOffset+8:],
+			encodeAluRRR(aluOpAdd, tmpReg, tmpReg, tmpReg2, true, false))
+		// br tmpReg: branch to the function without overwriting the link register.
+		binary.LittleEndian.PutUint32(executable[trampolineOffset+12:], encodeUnconditionalBranchReg(tmpReg, false))
+		// #diff
+		binary.LittleEndian.PutUint32(executable[trampolineOffset+16:], uint32(diff))
+	}
+}
+
+// searchTrampolineIsland finds the nearest trampoline island from callTrampolineIslandOffsets.
+// Note that even if the offset is in the middle of two islands, it returns the latter one.
+// That is ok because the island is always placed in the middle of the range.
+//
+// precondition: callTrampolineIslandOffsets is sorted in ascending order.
+func searchTrampolineIsland(callTrampolineIslandOffsets []int, offset int) int {
+	l := len(callTrampolineIslandOffsets)
+	n := sort.Search(l, func(i int) bool {
+		return callTrampolineIslandOffsets[i] >= offset
+	})
+	if n == l {
+		n = l - 1
 	}
+	return callTrampolineIslandOffsets[n]
 }
diff --git a/internal/engine/wazevo/backend/machine.go b/internal/engine/wazevo/backend/machine.go
index f56e3480..cf45ea55 100644
--- a/internal/engine/wazevo/backend/machine.go
+++ b/internal/engine/wazevo/backend/machine.go
@@ -59,10 +59,19 @@ type (
 		PostRegAlloc()
 
 		// ResolveRelocations resolves the relocations after emitting machine code.
-		ResolveRelocations(refToBinaryOffset map[ssa.FuncRef]int, binary []byte, relocations []RelocationInfo)
+		//  * refToBinaryOffset: the map from the function reference to the executable offset.
+		//  * executable: the binary to resolve the relocations.
+		//  * relocations: the relocations to resolve.
+		//  * callTrampolineIslandOffsets: the offsets of the trampoline islands in the executable.
+		ResolveRelocations(
+			refToBinaryOffset map[ssa.FuncRef]int,
+			executable []byte,
+			relocations []RelocationInfo,
+			callTrampolineIslandOffsets []int,
+		)
 
 		// Encode encodes the machine instructions to the Compiler.
-		Encode(ctx context.Context)
+		Encode(ctx context.Context) error
 
 		// CompileGoFunctionTrampoline compiles the trampoline function  to call a Go function of the given exit code and signature.
 		CompileGoFunctionTrampoline(exitCode wazevoapi.ExitCode, sig *ssa.Signature, needModuleContextPtr bool) []byte
@@ -83,5 +92,9 @@ type (
 
 		// ArgsResultsRegs returns the registers used for arguments and return values.
 		ArgsResultsRegs() (argResultInts, argResultFloats []regalloc.RealReg)
+
+		// CallTrampolineIslandInfo returns the interval of the offset where the trampoline island is placed, and
+		// the size of the trampoline island. If islandSize is zero, the trampoline island is not used on this machine.
+		CallTrampolineIslandInfo(numFunctions int) (interval, islandSize int, err error)
 	}
 )
diff --git a/internal/engine/wazevo/engine.go b/internal/engine/wazevo/engine.go
index d0c984ad..60bb4a3c 100644
--- a/internal/engine/wazevo/engine.go
+++ b/internal/engine/wazevo/engine.go
@@ -220,6 +220,15 @@ func (e *engine) compileModule(ctx context.Context, module *wasm.Module, listene
 	totalSize := 0 // Total binary size of the executable.
 	cm.functionOffsets = make([]int, localFns)
 	bodies := make([][]byte, localFns)
+
+	// Trampoline relocation related variables.
+	trampolineInterval, callTrampolineIslandSize, err := machine.CallTrampolineIslandInfo(localFns)
+	if err != nil {
+		return nil, err
+	}
+	needCallTrampoline := callTrampolineIslandSize > 0
+	var callTrampolineIslandOffsets []int // Holds the offsets of trampoline islands.
+
 	for i := range module.CodeSection {
 		if wazevoapi.DeterministicCompilationVerifierEnabled {
 			i = wazevoapi.DeterministicCompilationVerifierGetRandomizedLocalFunctionIndex(ctx, i)
@@ -273,6 +282,14 @@ func (e *engine) compileModule(ctx context.Context, module *wasm.Module, listene
 		if wazevoapi.PrintMachineCodeHexPerFunction {
 			fmt.Printf("[[[machine code for %s]]]\n%s\n\n", wazevoapi.GetCurrentFunctionName(ctx), hex.EncodeToString(body))
 		}
+
+		if needCallTrampoline {
+			// If the total size exceeds the trampoline interval, we need to add a trampoline island.
+			if totalSize/trampolineInterval > len(callTrampolineIslandOffsets) {
+				callTrampolineIslandOffsets = append(callTrampolineIslandOffsets, totalSize)
+				totalSize += callTrampolineIslandSize
+			}
+		}
 	}
 
 	// Allocate executable memory and then copy the generated machine code.
@@ -299,7 +316,7 @@ func (e *engine) compileModule(ctx context.Context, module *wasm.Module, listene
 
 	// Resolve relocations for local function calls.
 	if len(e.rels) > 0 {
-		machine.ResolveRelocations(e.refToBinaryOffset, executable, e.rels)
+		machine.ResolveRelocations(e.refToBinaryOffset, executable, e.rels, callTrampolineIslandOffsets)
 	}
 
 	if runtime.GOARCH == "arm64" {
@@ -419,7 +436,9 @@ func (e *engine) compileHostModule(ctx context.Context, module *wasm.Module, lis
 
 		be.Init()
 		machine.CompileGoFunctionTrampoline(exitCode, &sig, true)
-		be.Finalize(ctx)
+		if err := be.Finalize(ctx); err != nil {
+			return nil, err
+		}
 		body := be.Buf()
 
 		if wazevoapi.PerfMapEnabled {


Test patch:
diff --git a/internal/engine/wazevo/backend/backend_test.go b/internal/engine/wazevo/backend/backend_test.go
index 8fc824ae..b4e10b51 100644
--- a/internal/engine/wazevo/backend/backend_test.go
+++ b/internal/engine/wazevo/backend/backend_test.go
@@ -2375,7 +2375,8 @@ L2 (SSA Block: blk2):
 				fmt.Println(be.Format())
 			}
 
-			be.Finalize(context.Background())
+			err = be.Finalize(context.Background())
+			require.NoError(t, err)
 			if verbose {
 				fmt.Println("============ finalization result ============")
 				fmt.Println(be.Format())
diff --git a/internal/engine/wazevo/backend/isa/amd64/abi_go_call_test.go b/internal/engine/wazevo/backend/isa/amd64/abi_go_call_test.go
index 67db16b2..78c0c721 100644
--- a/internal/engine/wazevo/backend/isa/amd64/abi_go_call_test.go
+++ b/internal/engine/wazevo/backend/isa/amd64/abi_go_call_test.go
@@ -370,10 +370,9 @@ L3:
 		t.Run(tc.name, func(t *testing.T) {
 			_, _, m := newSetupWithMockContext()
 			m.CompileGoFunctionTrampoline(tc.exitCode, tc.sig, tc.needModuleContextPtr)
-
 			require.Equal(t, tc.exp, m.Format())
-
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 		})
 	}
 }
@@ -521,7 +520,8 @@ L2:
 			_, _, m := newSetupWithMockContext()
 			m.ectx.RootInstr = m.allocateNop()
 			m.insertStackBoundsCheck(tc.requiredStackSize, m.ectx.RootInstr)
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 			require.Equal(t, tc.exp, m.Format())
 		})
 	}
diff --git a/internal/engine/wazevo/backend/isa/amd64/machine_pro_epi_logue_test.go b/internal/engine/wazevo/backend/isa/amd64/machine_pro_epi_logue_test.go
index 9fdcdace..1a86a445 100644
--- a/internal/engine/wazevo/backend/isa/amd64/machine_pro_epi_logue_test.go
+++ b/internal/engine/wazevo/backend/isa/amd64/machine_pro_epi_logue_test.go
@@ -77,7 +77,8 @@ func TestMachine_setupPrologue(t *testing.T) {
 
 			m.setupPrologue()
 			require.Equal(t, root, m.ectx.RootInstr)
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 			require.Equal(t, tc.exp, m.Format())
 		})
 	}
@@ -151,7 +152,8 @@ func TestMachine_postRegAlloc(t *testing.T) {
 			m.postRegAlloc()
 
 			require.Equal(t, root, m.ectx.RootInstr)
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 			require.Equal(t, tc.exp, m.Format())
 		})
 	}
diff --git a/internal/engine/wazevo/backend/isa/amd64/util_test.go b/internal/engine/wazevo/backend/isa/amd64/util_test.go
index e7a91dc5..29b2c6c1 100644
--- a/internal/engine/wazevo/backend/isa/amd64/util_test.go
+++ b/internal/engine/wazevo/backend/isa/amd64/util_test.go
@@ -67,11 +67,11 @@ func (m *mockCompiler) Buf() []byte { return m.buf }
 func (m *mockCompiler) TypeOf(v regalloc.VReg) (ret ssa.Type) {
 	return m.typeOf[v.ID()]
 }
-func (m *mockCompiler) Finalize(context.Context) {}
-func (m *mockCompiler) RegAlloc()                {}
-func (m *mockCompiler) Lower()                   {}
-func (m *mockCompiler) Format() string           { return "" }
-func (m *mockCompiler) Init()                    {}
+func (m *mockCompiler) Finalize(context.Context) (err error) { return }
+func (m *mockCompiler) RegAlloc()                            {}
+func (m *mockCompiler) Lower()                               {}
+func (m *mockCompiler) Format() string                       { return "" }
+func (m *mockCompiler) Init()                                {}
 
 func newMockCompilationContext() *mockCompiler { //nolint
 	return &mockCompiler{
diff --git a/internal/engine/wazevo/backend/isa/arm64/abi_entry_preamble_test.go b/internal/engine/wazevo/backend/isa/arm64/abi_entry_preamble_test.go
index 038d9115..beca3f02 100644
--- a/internal/engine/wazevo/backend/isa/arm64/abi_entry_preamble_test.go
+++ b/internal/engine/wazevo/backend/isa/arm64/abi_entry_preamble_test.go
@@ -535,7 +535,8 @@ func TestMachine_goEntryPreamblePassArg(t *testing.T) {
 			m.executableContext.RootInstr = cur
 			m.goEntryPreamblePassArg(cur, paramSlicePtr, &tc.arg, tc.argSlotBeginOffsetFromSP)
 			require.Equal(t, tc.exp, m.Format())
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 		})
 	}
 }
@@ -688,7 +689,8 @@ func TestMachine_goEntryPreamblePassResult(t *testing.T) {
 			m.executableContext.RootInstr = cur
 			m.goEntryPreamblePassResult(cur, paramSlicePtr, &tc.arg, tc.retStart)
 			require.Equal(t, tc.exp, m.Format())
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 		})
 	}
 }
diff --git a/internal/engine/wazevo/backend/isa/arm64/abi_go_call_test.go b/internal/engine/wazevo/backend/isa/arm64/abi_go_call_test.go
index 29fe5c83..5fef0cfb 100644
--- a/internal/engine/wazevo/backend/isa/arm64/abi_go_call_test.go
+++ b/internal/engine/wazevo/backend/isa/arm64/abi_go_call_test.go
@@ -451,7 +451,8 @@ func TestMachine_CompileGoFunctionTrampoline(t *testing.T) {
 
 			require.Equal(t, tc.exp, m.Format())
 
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 		})
 	}
 }
@@ -519,7 +520,8 @@ func Test_goFunctionCallLoadStackArg(t *testing.T) {
 				m.executableContext.RootInstr = nop
 
 				require.Equal(t, tc.exp, m.Format())
-				m.Encode(context.Background())
+				err := m.Encode(context.Background())
+				require.NoError(t, err)
 			})
 		})
 	}
@@ -585,7 +587,8 @@ func Test_goFunctionCallStoreStackResult(t *testing.T) {
 				m.executableContext.RootInstr = nop
 
 				require.Equal(t, tc.exp, m.Format())
-				m.Encode(context.Background())
+				err := m.Encode(context.Background())
+				require.NoError(t, err)
 			})
 		})
 	}
diff --git a/internal/engine/wazevo/backend/isa/arm64/machine_pro_epi_logue_test.go b/internal/engine/wazevo/backend/isa/arm64/machine_pro_epi_logue_test.go
index ad82e716..91926011 100644
--- a/internal/engine/wazevo/backend/isa/arm64/machine_pro_epi_logue_test.go
+++ b/internal/engine/wazevo/backend/isa/arm64/machine_pro_epi_logue_test.go
@@ -110,7 +110,8 @@ func TestMachine_setupPrologue(t *testing.T) {
 
 			m.setupPrologue()
 			require.Equal(t, root, m.executableContext.RootInstr)
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 			require.Equal(t, tc.exp, m.Format())
 		})
 	}
@@ -223,7 +224,8 @@ func TestMachine_postRegAlloc(t *testing.T) {
 			m.postRegAlloc()
 
 			require.Equal(t, root, m.executableContext.RootInstr)
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 			require.Equal(t, tc.exp, m.Format())
 		})
 	}
@@ -268,7 +270,8 @@ func TestMachine_insertStackBoundsCheck(t *testing.T) {
 			m.executableContext.RootInstr = m.allocateInstr()
 			m.executableContext.RootInstr.asNop0()
 			m.insertStackBoundsCheck(tc.requiredStackSize, m.executableContext.RootInstr)
-			m.Encode(context.Background())
+			err := m.Encode(context.Background())
+			require.NoError(t, err)
 			require.Equal(t, tc.exp, m.Format())
 		})
 	}
diff --git a/internal/engine/wazevo/backend/isa/arm64/machine_relocation_test.go b/internal/engine/wazevo/backend/isa/arm64/machine_relocation_test.go
new file mode 100644
index 00000000..c74b663d
--- /dev/null
+++ b/internal/engine/wazevo/backend/isa/arm64/machine_relocation_test.go
@@ -0,0 +1,42 @@
+package arm64
+
+import (
+	"encoding/binary"
+	"encoding/hex"
+	"testing"
+
+	"github.com/tetratelabs/wazero/internal/engine/wazevo/ssa"
+	"github.com/tetratelabs/wazero/internal/testing/require"
+)
+
+func Test_maxNumFunctions(t *testing.T) {
+	// Ensures that trampoline island is small enough to fit in the interval.
+	require.True(t, maxNumFunctions*trampolineCallSize < trampolineIslandInterval/2) //nolint:gomnd
+	// Ensures that each function is small enough to fit in the interval.
+	require.True(t, maxFunctionExecutableSize < trampolineIslandInterval/2) //nolint:gomnd
+}
+
+func Test_encodeCallTrampolineIsland(t *testing.T) {
+	executable := make([]byte, 16*1000)
+	islandOffset := 160
+	refToBinaryOffset := map[ssa.FuncRef]int{0: 0, 1: 16, 2: 1600, 3: 16000}
+	encodeCallTrampolineIsland(refToBinaryOffset, islandOffset, executable)
+	for i := 0; i < len(refToBinaryOffset); i++ {
+		offset := islandOffset + trampolineCallSize*i
+		instrs := executable[offset : offset+trampolineCallSize-4]
+		// Instructions are always the same except for the last immediate.
+		require.Equal(t, "9b0000106b0380b97b030b8b60031fd6", hex.EncodeToString(instrs))
+		imm := binary.LittleEndian.Uint32(executable[offset+trampolineCallSize-4:])
+		require.Equal(t, uint32(refToBinaryOffset[ssa.FuncRef(i)]-(offset+16)), imm)
+	}
+}
+
+func Test_searchTrampolineIsland(t *testing.T) {
+	offsets := []int{16, 32, 48}
+	require.Equal(t, 32, searchTrampolineIsland(offsets, 30))
+	require.Equal(t, 32, searchTrampolineIsland(offsets, 17))
+	require.Equal(t, 16, searchTrampolineIsland(offsets, 16))
+	require.Equal(t, 48, searchTrampolineIsland(offsets, 48))
+	require.Equal(t, 48, searchTrampolineIsland(offsets, 56))
+	require.Equal(t, 16, searchTrampolineIsland(offsets, 1))
+}
diff --git a/internal/engine/wazevo/backend/isa/arm64/util_test.go b/internal/engine/wazevo/backend/isa/arm64/util_test.go
index 2e9fc3e1..a19fb336 100644
--- a/internal/engine/wazevo/backend/isa/arm64/util_test.go
+++ b/internal/engine/wazevo/backend/isa/arm64/util_test.go
@@ -97,11 +97,11 @@ func (m *mockCompiler) Buf() []byte { return m.buf }
 func (m *mockCompiler) TypeOf(v regalloc.VReg) (ret ssa.Type) {
 	return m.typeOf[v.ID()]
 }
-func (m *mockCompiler) Finalize(context.Context) {}
-func (m *mockCompiler) RegAlloc()                {}
-func (m *mockCompiler) Lower()                   {}
-func (m *mockCompiler) Format() string           { return "" }
-func (m *mockCompiler) Init()                    {}
+func (m *mockCompiler) Finalize(context.Context) (err error) { return }
+func (m *mockCompiler) RegAlloc()                            {}
+func (m *mockCompiler) Lower()                               {}
+func (m *mockCompiler) Format() string                       { return "" }
+func (m *mockCompiler) Init()                                {}
 
 func newMockCompilationContext() *mockCompiler {
 	return &mockCompiler{
diff --git a/internal/engine/wazevo/backend/machine_test.go b/internal/engine/wazevo/backend/machine_test.go
index b2d8efe6..a6d789b2 100644
--- a/internal/engine/wazevo/backend/machine_test.go
+++ b/internal/engine/wazevo/backend/machine_test.go
@@ -25,6 +25,8 @@ type mockMachine struct {
 	linkAdjacentBlocks             func(prev, next ssa.BasicBlock)
 }
 
+func (m mockMachine) CallTrampolineIslandInfo(_ int) (_, _ int, _ error) { panic("implement me") }
+
 func (m mockMachine) ArgsResultsRegs() (argResultInts, argResultFloats []regalloc.RealReg) {
 	return m.argResultInts, m.argResultFloats
 }
@@ -51,10 +53,10 @@ func (m mockMachine) CompileGoFunctionTrampoline(wazevoapi.ExitCode, *ssa.Signat
 }
 
 // Encode implements Machine.Encode.
-func (m mockMachine) Encode(ctx context.Context) {}
+func (m mockMachine) Encode(context.Context) (err error) { return }
 
 // ResolveRelocations implements Machine.ResolveRelocations.
-func (m mockMachine) ResolveRelocations(map[ssa.FuncRef]int, []byte, []RelocationInfo) {}
+func (m mockMachine) ResolveRelocations(map[ssa.FuncRef]int, []byte, []RelocationInfo, []int) {}
 
 // PostRegAlloc implements Machine.SetupPrologue.
 func (m mockMachine) PostRegAlloc() {}
diff --git a/internal/integration_test/engine/adhoc_test.go b/internal/integration_test/engine/adhoc_test.go
index f0936480..624afda1 100644
--- a/internal/integration_test/engine/adhoc_test.go
+++ b/internal/integration_test/engine/adhoc_test.go
@@ -74,6 +74,7 @@ var tests = map[string]testCase{
 	"many params many results / call_many_consts_and_pick_last_vector / listener": {f: testManyParamsResultsCallManyConstsAndPickLastVectorListener},
 	"close table importing module": {f: testCloseTableImportingModule},
 	"close table exporting module": {f: testCloseTableExportingModule},
+	"huge binary":                  {f: testHugeBinary},
 }
 
 func TestEngineCompiler(t *testing.T) {
@@ -2361,3 +2362,66 @@ func instantiateClose(t *testing.T, r wazero.Runtime, ctx context.Context, bin [
 	require.NoError(t, compiled.Close(ctx))
 	runtime.GC()
 }
+
+// testHugeBinary is supposed to do e2e on huge relocation in arm64.
+func testHugeBinary(t *testing.T, r wazero.Runtime) {
+	if testing.Short() {
+		t.Skip("skipping testHugeBinary in short mode since it takes a long time")
+	}
+	var addFuncBody []byte
+	for i := 0; i < 1024; i++ {
+		addFuncBody = append(addFuncBody, wasm.OpcodeLocalGet, 0)
+		addFuncBody = append(addFuncBody, wasm.OpcodeI32Const)
+		addFuncBody = append(addFuncBody, leb128.EncodeInt32(int32(i))...)
+		addFuncBody = append(addFuncBody, wasm.OpcodeI32Add)
+		addFuncBody = append(addFuncBody, wasm.OpcodeLocalSet, 0)
+	}
+	addFuncBody = append(addFuncBody, wasm.OpcodeLocalGet, 0, wasm.OpcodeEnd)
+
+	const functionCount = 40000
+	// The first function calls the second last function.
+	var firstFunctionBody []byte
+	firstFunctionBody = append(firstFunctionBody, wasm.OpcodeLocalGet, 0)
+	firstFunctionBody = append(firstFunctionBody, wasm.OpcodeCall)
+	firstFunctionBody = append(firstFunctionBody, leb128.EncodeUint32(functionCount-2)...)
+	firstFunctionBody = append(firstFunctionBody, wasm.OpcodeEnd)
+	// The last function calls the second function.
+	lastFunctionBody := []byte{wasm.OpcodeLocalGet, 0, wasm.OpcodeCall, 1, wasm.OpcodeEnd}
+
+	// Create a Code section with 20000 functions.
+	codes := make([]wasm.Code, functionCount)
+	codes[0] = wasm.Code{Body: firstFunctionBody}
+	for i := 0; i < functionCount-2; i++ {
+		codes[i+1] = wasm.Code{Body: addFuncBody}
+	}
+	codes[functionCount-1] = wasm.Code{Body: lastFunctionBody}
+
+	funcType := wasm.FunctionType{Params: []wasm.ValueType{i32}, Results: []wasm.ValueType{i32}}
+	m := &wasm.Module{}
+	m.FunctionSection = make([]wasm.Index, functionCount)
+	m.CodeSection = codes
+	m.TypeSection = []wasm.FunctionType{funcType}
+	// Export the first and last function.
+	m.ExportSection = []wasm.Export{
+		{Name: "first", Type: wasm.ExternTypeFunc, Index: 0},
+		{Name: "last", Type: wasm.ExternTypeFunc, Index: functionCount - 1},
+	}
+
+	bin := binaryencoding.EncodeModule(m)
+
+	ctx := context.Background()
+	mod, err := r.Instantiate(ctx, bin)
+	require.NoError(t, err)
+
+	first := mod.ExportedFunction("first")
+	require.NotNil(t, first)
+	res, err := first.Call(ctx, 0)
+	require.NoError(t, err)
+	require.Equal(t, uint64(1023*1024/2), res[0])
+
+	last := mod.ExportedFunction("last")
+	require.NotNil(t, last)
+	res, err = last.Call(ctx, 0)
+	require.NoError(t, err)
+	require.Equal(t, uint64(1023*1024/2), res[0])
+}