Debian Codegraph @

Tools/jit/_stencils.py

raw
1 """Core data structures for compiled code templates."""
2
3 import dataclasses
4 import enum
5 import sys
6 import typing
7
8 import _schema
9
10
11 @enum.unique
12 class HoleValue(enum.Enum):
13 """
14 Different "base" values that can be patched into holes (usually combined with the
15 address of a symbol and/or an addend).
16 """
17
18 # The base address of the machine code for the current uop (exposed as _JIT_ENTRY):
19 CODE = enum.auto()
20 # The base address of the machine code for the next uop (exposed as _JIT_CONTINUE):
21 CONTINUE = enum.auto()
22 # The base address of the read-only data for this uop:
23 DATA = enum.auto()
24 # The address of the current executor (exposed as _JIT_EXECUTOR):
25 EXECUTOR = enum.auto()
26 # The base address of the "global" offset table located in the read-only data.
27 # Shouldn't be present in the final stencils, since these are all replaced with
28 # equivalent DATA values:
29 GOT = enum.auto()
30 # The current uop's oparg (exposed as _JIT_OPARG):
31 OPARG = enum.auto()
32 # The current uop's operand on 64-bit platforms (exposed as _JIT_OPERAND):
33 OPERAND = enum.auto()
34 # The current uop's operand on 32-bit platforms (exposed as _JIT_OPERAND_HI/LO):
35 OPERAND_HI = enum.auto()
36 OPERAND_LO = enum.auto()
37 # The current uop's target (exposed as _JIT_TARGET):
38 TARGET = enum.auto()
39 # The base address of the machine code for the jump target (exposed as _JIT_JUMP_TARGET):
40 JUMP_TARGET = enum.auto()
41 # The base address of the machine code for the error jump target (exposed as _JIT_ERROR_TARGET):
42 ERROR_TARGET = enum.auto()
43 # The index of the exit to be jumped through (exposed as _JIT_EXIT_INDEX):
44 EXIT_INDEX = enum.auto()
45 # The base address of the machine code for the first uop (exposed as _JIT_TOP):
46 TOP = enum.auto()
47 # A hardcoded value of zero (used for symbol lookups):
48 ZERO = enum.auto()
49
50
51 # Map relocation types to our JIT's patch functions. "r" suffixes indicate that
52 # the patch function is relative. "x" suffixes indicate that they are "relaxing"
53 # (see comments in jit.c for more info):
54 _PATCH_FUNCS = {
55 # aarch64-apple-darwin:
56 "ARM64_RELOC_BRANCH26": "patch_aarch64_26r",
57 "ARM64_RELOC_GOT_LOAD_PAGE21": "patch_aarch64_21r",
58 "ARM64_RELOC_GOT_LOAD_PAGEOFF12": "patch_aarch64_12",
59 "ARM64_RELOC_PAGE21": "patch_aarch64_21r",
60 "ARM64_RELOC_PAGEOFF12": "patch_aarch64_12",
61 "ARM64_RELOC_UNSIGNED": "patch_64",
62 # x86_64-pc-windows-msvc:
63 "IMAGE_REL_AMD64_REL32": "patch_x86_64_32rx",
64 # aarch64-pc-windows-msvc:
65 "IMAGE_REL_ARM64_BRANCH26": "patch_aarch64_26r",
66 "IMAGE_REL_ARM64_PAGEBASE_REL21": "patch_aarch64_21r",
67 "IMAGE_REL_ARM64_PAGEOFFSET_12A": "patch_aarch64_12",
68 "IMAGE_REL_ARM64_PAGEOFFSET_12L": "patch_aarch64_12",
69 # i686-pc-windows-msvc:
70 "IMAGE_REL_I386_DIR32": "patch_32",
71 "IMAGE_REL_I386_REL32": "patch_x86_64_32rx",
72 # aarch64-unknown-linux-gnu:
73 "R_AARCH64_ABS64": "patch_64",
74 "R_AARCH64_ADD_ABS_LO12_NC": "patch_aarch64_12",
75 "R_AARCH64_ADR_GOT_PAGE": "patch_aarch64_21r",
76 "R_AARCH64_ADR_PREL_PG_HI21": "patch_aarch64_21r",
77 "R_AARCH64_CALL26": "patch_aarch64_26r",
78 "R_AARCH64_JUMP26": "patch_aarch64_26r",
79 "R_AARCH64_LD64_GOT_LO12_NC": "patch_aarch64_12",
80 "R_AARCH64_MOVW_UABS_G0_NC": "patch_aarch64_16a",
81 "R_AARCH64_MOVW_UABS_G1_NC": "patch_aarch64_16b",
82 "R_AARCH64_MOVW_UABS_G2_NC": "patch_aarch64_16c",
83 "R_AARCH64_MOVW_UABS_G3": "patch_aarch64_16d",
84 # x86_64-unknown-linux-gnu:
85 "R_X86_64_64": "patch_64",
86 "R_X86_64_GOTPCREL": "patch_32r",
87 "R_X86_64_GOTPCRELX": "patch_x86_64_32rx",
88 "R_X86_64_PC32": "patch_32r",
89 "R_X86_64_REX_GOTPCRELX": "patch_x86_64_32rx",
90 # x86_64-apple-darwin:
91 "X86_64_RELOC_BRANCH": "patch_32r",
92 "X86_64_RELOC_GOT": "patch_x86_64_32rx",
93 "X86_64_RELOC_GOT_LOAD": "patch_x86_64_32rx",
94 "X86_64_RELOC_SIGNED": "patch_32r",
95 "X86_64_RELOC_UNSIGNED": "patch_64",
96 }
97 # Translate HoleValues to C expressions:
98 _HOLE_EXPRS = {
99 HoleValue.CODE: "(uintptr_t)code",
100 HoleValue.CONTINUE: "(uintptr_t)code + sizeof(code_body)",
101 HoleValue.DATA: "(uintptr_t)data",
102 HoleValue.EXECUTOR: "(uintptr_t)executor",
103 # These should all have been turned into DATA values by process_relocations:
104 # HoleValue.GOT: "",
105 HoleValue.OPARG: "instruction->oparg",
106 HoleValue.OPERAND: "instruction->operand",
107 HoleValue.OPERAND_HI: "(instruction->operand >> 32)",
108 HoleValue.OPERAND_LO: "(instruction->operand & UINT32_MAX)",
109 HoleValue.TARGET: "instruction->target",
110 HoleValue.JUMP_TARGET: "instruction_starts[instruction->jump_target]",
111 HoleValue.ERROR_TARGET: "instruction_starts[instruction->error_target]",
112 HoleValue.EXIT_INDEX: "instruction->exit_index",
113 HoleValue.TOP: "instruction_starts[1]",
114 HoleValue.ZERO: "",
115 }
116
117
118 @dataclasses.dataclass
119 class Hole:
120 """
121 A "hole" in the stencil to be patched with a computed runtime value.
122
123 Analogous to relocation records in an object file.
124 """
125
126 offset: int
127 kind: _schema.HoleKind
128 # Patch with this base value:
129 value: HoleValue
130 # ...plus the address of this symbol:
131 symbol: str | None
132 # ...plus this addend:
133 addend: int
134 func: str = dataclasses.field(init=False)
135 # Convenience method:
136 replace = dataclasses.replace
137
138 def __post_init__(self) -> None:
139 self.func = _PATCH_FUNCS[self.kind]
140
141 def as_c(self, where: str) -> str:
142 """Dump this hole as a call to a patch_* function."""
143 location = f"{where} + {self.offset:#x}"
144 value = _HOLE_EXPRS[self.value]
145 if self.symbol:
146 if value:
147 value += " + "
148 value += f"(uintptr_t)&{self.symbol}"
149 if _signed(self.addend):
150 if value:
151 value += " + "
152 value += f"{_signed(self.addend):#x}"
153 return f"{self.func}({location}, {value});"
154
155
156 @dataclasses.dataclass
157 class Stencil:
158 """
159 A contiguous block of machine code or data to be copied-and-patched.
160
161 Analogous to a section or segment in an object file.
162 """
163
164 body: bytearray = dataclasses.field(default_factory=bytearray, init=False)
165 holes: list[Hole] = dataclasses.field(default_factory=list, init=False)
166 disassembly: list[str] = dataclasses.field(default_factory=list, init=False)
167
168 def pad(self, alignment: int) -> None:
169 """Pad the stencil to the given alignment."""
170 offset = len(self.body)
171 padding = -offset % alignment
172 self.disassembly.append(f"{offset:x}: {' '.join(['00'] * padding)}")
173 self.body.extend([0] * padding)
174
175 def emit_aarch64_trampoline(self, hole: Hole) -> None:
176 """Even with the large code model, AArch64 Linux insists on 28-bit jumps."""
177 base = len(self.body)
178 where = slice(hole.offset, hole.offset + 4)
179 instruction = int.from_bytes(self.body[where], sys.byteorder)
180 instruction &= 0xFC000000
181 instruction |= ((base - hole.offset) >> 2) & 0x03FFFFFF
182 self.body[where] = instruction.to_bytes(4, sys.byteorder)
183 self.disassembly += [
184 f"{base + 4 * 0:x}: d2800008 mov x8, #0x0",
185 f"{base + 4 * 0:016x}: R_AARCH64_MOVW_UABS_G0_NC {hole.symbol}",
186 f"{base + 4 * 1:x}: f2a00008 movk x8, #0x0, lsl #16",
187 f"{base + 4 * 1:016x}: R_AARCH64_MOVW_UABS_G1_NC {hole.symbol}",
188 f"{base + 4 * 2:x}: f2c00008 movk x8, #0x0, lsl #32",
189 f"{base + 4 * 2:016x}: R_AARCH64_MOVW_UABS_G2_NC {hole.symbol}",
190 f"{base + 4 * 3:x}: f2e00008 movk x8, #0x0, lsl #48",
191 f"{base + 4 * 3:016x}: R_AARCH64_MOVW_UABS_G3 {hole.symbol}",
192 f"{base + 4 * 4:x}: d61f0100 br x8",
193 ]
194 for code in [
195 0xD2800008.to_bytes(4, sys.byteorder),
196 0xF2A00008.to_bytes(4, sys.byteorder),
197 0xF2C00008.to_bytes(4, sys.byteorder),
198 0xF2E00008.to_bytes(4, sys.byteorder),
199 0xD61F0100.to_bytes(4, sys.byteorder),
200 ]:
201 self.body.extend(code)
202 for i, kind in enumerate(
203 [
204 "R_AARCH64_MOVW_UABS_G0_NC",
205 "R_AARCH64_MOVW_UABS_G1_NC",
206 "R_AARCH64_MOVW_UABS_G2_NC",
207 "R_AARCH64_MOVW_UABS_G3",
208 ]
209 ):
210 self.holes.append(hole.replace(offset=base + 4 * i, kind=kind))
211
212 def remove_jump(self, *, alignment: int = 1) -> None:
213 """Remove a zero-length continuation jump, if it exists."""
214 hole = max(self.holes, key=lambda hole: hole.offset)
215 match hole:
216 case Hole(
217 offset=offset,
218 kind="IMAGE_REL_AMD64_REL32",
219 value=HoleValue.GOT,
220 symbol="_JIT_CONTINUE",
221 addend=-4,
222 ) as hole:
223 # jmp qword ptr [rip]
224 jump = b"\x48\xff\x25\x00\x00\x00\x00"
225 offset -= 3
226 case Hole(
227 offset=offset,
228 kind="IMAGE_REL_I386_REL32" | "X86_64_RELOC_BRANCH",
229 value=HoleValue.CONTINUE,
230 symbol=None,
231 addend=-4,
232 ) as hole:
233 # jmp 5
234 jump = b"\xe9\x00\x00\x00\x00"
235 offset -= 1
236 case Hole(
237 offset=offset,
238 kind="R_AARCH64_JUMP26",
239 value=HoleValue.CONTINUE,
240 symbol=None,
241 addend=0,
242 ) as hole:
243 # b #4
244 jump = b"\x00\x00\x00\x14"
245 case Hole(
246 offset=offset,
247 kind="R_X86_64_GOTPCRELX",
248 value=HoleValue.GOT,
249 symbol="_JIT_CONTINUE",
250 addend=addend,
251 ) as hole:
252 assert _signed(addend) == -4
253 # jmp qword ptr [rip]
254 jump = b"\xff\x25\x00\x00\x00\x00"
255 offset -= 2
256 case _:
257 return
258 if self.body[offset:] == jump and offset % alignment == 0:
259 self.body = self.body[:offset]
260 self.holes.remove(hole)
261
262
263 @dataclasses.dataclass
264 class StencilGroup:
265 """
266 Code and data corresponding to a given micro-opcode.
267
268 Analogous to an entire object file.
269 """
270
271 code: Stencil = dataclasses.field(default_factory=Stencil, init=False)
272 data: Stencil = dataclasses.field(default_factory=Stencil, init=False)
273 symbols: dict[int | str, tuple[HoleValue, int]] = dataclasses.field(
274 default_factory=dict, init=False
275 )
276 _got: dict[str, int] = dataclasses.field(default_factory=dict, init=False)
277
278 def process_relocations(self, *, alignment: int = 1) -> None:
279 """Fix up all GOT and internal relocations for this stencil group."""
280 for hole in self.code.holes.copy():
281 if (
282 hole.kind
283 in {"R_AARCH64_CALL26", "R_AARCH64_JUMP26", "ARM64_RELOC_BRANCH26"}
284 and hole.value is HoleValue.ZERO
285 ):
286 self.code.pad(alignment)
287 self.code.emit_aarch64_trampoline(hole)
288 self.code.holes.remove(hole)
289 self.code.remove_jump(alignment=alignment)
290 self.code.pad(alignment)
291 self.data.pad(8)
292 for stencil in [self.code, self.data]:
293 for hole in stencil.holes:
294 if hole.value is HoleValue.GOT:
295 assert hole.symbol is not None
296 hole.value = HoleValue.DATA
297 hole.addend += self._global_offset_table_lookup(hole.symbol)
298 hole.symbol = None
299 elif hole.symbol in self.symbols:
300 hole.value, addend = self.symbols[hole.symbol]
301 hole.addend += addend
302 hole.symbol = None
303 elif (
304 hole.kind in {"IMAGE_REL_AMD64_REL32"}
305 and hole.value is HoleValue.ZERO
306 ):
307 raise ValueError(
308 f"Add PyAPI_FUNC(...) or PyAPI_DATA(...) to declaration of {hole.symbol}!"
309 )
310 self._emit_global_offset_table()
311 self.code.holes.sort(key=lambda hole: hole.offset)
312 self.data.holes.sort(key=lambda hole: hole.offset)
313
314 def _global_offset_table_lookup(self, symbol: str) -> int:
315 return len(self.data.body) + self._got.setdefault(symbol, 8 * len(self._got))
316
317 def _emit_global_offset_table(self) -> None:
318 got = len(self.data.body)
319 for s, offset in self._got.items():
320 if s in self.symbols:
321 value, addend = self.symbols[s]
322 symbol = None
323 else:
324 value, symbol = symbol_to_value(s)
325 addend = 0
326 self.data.holes.append(
327 Hole(got + offset, "R_X86_64_64", value, symbol, addend)
328 )
329 value_part = value.name if value is not HoleValue.ZERO else ""
330 if value_part and not symbol and not addend:
331 addend_part = ""
332 else:
333 signed = "+" if symbol is not None else ""
334 addend_part = f"&{symbol}" if symbol else ""
335 addend_part += f"{_signed(addend):{signed}#x}"
336 if value_part:
337 value_part += "+"
338 self.data.disassembly.append(
339 f"{len(self.data.body):x}: {value_part}{addend_part}"
340 )
341 self.data.body.extend([0] * 8)
342
343 def as_c(self, opname: str) -> str:
344 """Dump this hole as a StencilGroup initializer."""
345 return f"{{emit_{opname}, {len(self.code.body)}, {len(self.data.body)}}}"
346
347
348 def symbol_to_value(symbol: str) -> tuple[HoleValue, str | None]:
349 """
350 Convert a symbol name to a HoleValue and a symbol name.
351
352 Some symbols (starting with "_JIT_") are special and are converted to their
353 own HoleValues.
354 """
355 if symbol.startswith("_JIT_"):
356 try:
357 return HoleValue[symbol.removeprefix("_JIT_")], None
358 except KeyError:
359 pass
360 return HoleValue.ZERO, symbol
361
362
363 def _signed(value: int) -> int:
364 value %= 1 << 64
365 if value & (1 << 63):
366 value -= 1 << 64
367 return value