Debian Codegraph @

internal/engine/wazevo/backend/isa/arm64/machine_relocation.go

raw
1 package arm64
2
3 import (
4 "encoding/binary"
5 "fmt"
6 "math"
7 "sort"
8
9 "github.com/tetratelabs/wazero/internal/engine/wazevo/backend"
10 )
11
12 const (
13 // trampolineCallSize is the size of the trampoline instruction sequence for each function in an island.
14 trampolineCallSize = 4*4 + 4 // Four instructions + 32-bit immediate.
15
16 // Unconditional branch offset is encoded as divided by 4 in imm26.
17 // https://developer.arm.com/documentation/ddi0596/2021-12/Base-Instructions/BL--Branch-with-Link-?lang=en
18
19 maxUnconditionalBranchOffset = maxSignedInt26 * 4
20 minUnconditionalBranchOffset = minSignedInt26 * 4
21
22 // trampolineIslandInterval is the range of the trampoline island.
23 // Half of the range is used for the trampoline island, and the other half is used for the function.
24 trampolineIslandInterval = (maxUnconditionalBranchOffset - 1) / 2
25
26 // maxNumFunctions explicitly specifies the maximum number of functions that can be allowed in a single executable.
27 maxNumFunctions = trampolineIslandInterval >> 6
28
29 // maxFunctionExecutableSize is the maximum size of a function that can exist in a trampoline island.
30 // Conservatively set to 1/4 of the trampoline island interval.
31 maxFunctionExecutableSize = trampolineIslandInterval >> 2
32 )
33
34 // CallTrampolineIslandInfo implements backend.Machine CallTrampolineIslandInfo.
35 func (m *machine) CallTrampolineIslandInfo(numFunctions int) (interval, size int, err error) {
36 if numFunctions > maxNumFunctions {
37 return 0, 0, fmt.Errorf("too many functions: %d > %d", numFunctions, maxNumFunctions)
38 }
39 return trampolineIslandInterval, trampolineCallSize * numFunctions, nil
40 }
41
42 // ResolveRelocations implements backend.Machine ResolveRelocations.
43 func (m *machine) ResolveRelocations(
44 refToBinaryOffset []int,
45 importedFns int,
46 executable []byte,
47 relocations []backend.RelocationInfo,
48 callTrampolineIslandOffsets []int,
49 ) {
50 for _, islandOffset := range callTrampolineIslandOffsets {
51 encodeCallTrampolineIsland(refToBinaryOffset, importedFns, islandOffset, executable)
52 }
53
54 for _, r := range relocations {
55 instrOffset := r.Offset
56 calleeFnOffset := refToBinaryOffset[r.FuncRef]
57 diff := int64(calleeFnOffset) - (instrOffset)
58 // Check if the diff is within the range of the branch instruction.
59 if diff < minUnconditionalBranchOffset || diff > maxUnconditionalBranchOffset {
60 // Find the near trampoline island from callTrampolineIslandOffsets.
61 islandOffset := searchTrampolineIsland(callTrampolineIslandOffsets, int(instrOffset))
62 // Imported functions don't need trampolines, so we ignore them when we compute the offset
63 // (see also encodeCallTrampolineIsland)
64 funcOffset := int(r.FuncRef) - importedFns
65 islandTargetOffset := islandOffset + trampolineCallSize*funcOffset
66 diff = int64(islandTargetOffset) - (instrOffset)
67 if diff < minUnconditionalBranchOffset || diff > maxUnconditionalBranchOffset {
68 panic("BUG in trampoline placement")
69 }
70 }
71 // The unconditional branch instruction is usually encoded as a branch-and-link (BL),
72 // because it is a function call. However, if the instruction is a tail call,
73 // we encode it as a plain unconditional branch (B), so we won't overwrite the link register.
74 binary.LittleEndian.PutUint32(executable[instrOffset:instrOffset+4], encodeUnconditionalBranch(!r.IsTailCall, diff))
75 }
76 }
77
78 // encodeCallTrampolineIsland encodes a trampoline island for the given functions.
79 // Each island consists of a trampoline instruction sequence for each function.
80 // Each trampoline instruction sequence consists of 4 instructions + 32-bit immediate.
81 func encodeCallTrampolineIsland(refToBinaryOffset []int, importedFns int, islandOffset int, executable []byte) {
82 // We skip the imported functions: they don't need trampolines
83 // and are not accounted for.
84 binaryOffsets := refToBinaryOffset[importedFns:]
85
86 for i := 0; i < len(binaryOffsets); i++ {
87 trampolineOffset := islandOffset + trampolineCallSize*i
88
89 fnOffset := binaryOffsets[i]
90 diff := fnOffset - (trampolineOffset + 16)
91 if diff > math.MaxInt32 || diff < math.MinInt32 {
92 // This case even amd64 can't handle. 4GB is too big.
93 panic("too big binary")
94 }
95
96 // The tmpReg, tmpReg2 is safe to overwrite (in fact any caller-saved register is safe to use).
97 tmpReg, tmpReg2 := regNumberInEncoding[tmpRegVReg.RealReg()], regNumberInEncoding[x11]
98
99 // adr tmpReg, PC+16: load the address of #diff into tmpReg.
100 binary.LittleEndian.PutUint32(executable[trampolineOffset:], encodeAdr(tmpReg, 16))
101 // ldrsw tmpReg2, [tmpReg]: Load #diff into tmpReg2.
102 binary.LittleEndian.PutUint32(executable[trampolineOffset+4:],
103 encodeLoadOrStore(sLoad32, tmpReg2, addressMode{kind: addressModeKindRegUnsignedImm12, rn: tmpRegVReg}))
104 // add tmpReg, tmpReg2, tmpReg: add #diff to the address of #diff, getting the absolute address of the function.
105 binary.LittleEndian.PutUint32(executable[trampolineOffset+8:],
106 encodeAluRRR(aluOpAdd, tmpReg, tmpReg, tmpReg2, true, false))
107 // br tmpReg: branch to the function without overwriting the link register.
108 binary.LittleEndian.PutUint32(executable[trampolineOffset+12:], encodeUnconditionalBranchReg(tmpReg, false))
109 // #diff
110 binary.LittleEndian.PutUint32(executable[trampolineOffset+16:], uint32(diff))
111 }
112 }
113
114 // searchTrampolineIsland finds the nearest trampoline island from callTrampolineIslandOffsets.
115 // Note that even if the offset is in the middle of two islands, it returns the latter one.
116 // That is ok because the island is always placed in the middle of the range.
117 //
118 // precondition: callTrampolineIslandOffsets is sorted in ascending order.
119 func searchTrampolineIsland(callTrampolineIslandOffsets []int, offset int) int {
120 l := len(callTrampolineIslandOffsets)
121 n := sort.Search(l, func(i int) bool {
122 return callTrampolineIslandOffsets[i] >= offset
123 })
124 if n == l {
125 n = l - 1
126 }
127 return callTrampolineIslandOffsets[n]
128 }