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 operand0 on 64-bit platforms (exposed as _JIT_OPERAND0):
33 OPERAND0 = enum.auto()
34 # The current uop's operand0 on 32-bit platforms (exposed as _JIT_OPERAND0_HI/LO):
35 OPERAND0_HI = enum.auto()
36 OPERAND0_LO = enum.auto()
37 # The current uop's operand1 on 64-bit platforms (exposed as _JIT_OPERAND1):
38 OPERAND1 = enum.auto()
39 # The current uop's operand1 on 32-bit platforms (exposed as _JIT_OPERAND1_HI/LO):
40 OPERAND1_HI = enum.auto()
41 OPERAND1_LO = enum.auto()
42 # The current uop's target (exposed as _JIT_TARGET):
43 TARGET = enum.auto()
44 # The base address of the machine code for the jump target (exposed as _JIT_JUMP_TARGET):
45 JUMP_TARGET = enum.auto()
46 # The base address of the machine code for the error jump target (exposed as _JIT_ERROR_TARGET):
47 ERROR_TARGET = enum.auto()
48 # A hardcoded value of zero (used for symbol lookups):
49 ZERO = enum.auto()
50
51
52 # Map relocation types to our JIT's patch functions. "r" suffixes indicate that
53 # the patch function is relative. "x" suffixes indicate that they are "relaxing"
54 # (see comments in jit.c for more info):
55 _PATCH_FUNCS = {
56 # aarch64-apple-darwin:
57 "ARM64_RELOC_BRANCH26": "patch_aarch64_26r",
58 "ARM64_RELOC_GOT_LOAD_PAGE21": "patch_aarch64_21r",
59 "ARM64_RELOC_GOT_LOAD_PAGEOFF12": "patch_aarch64_12",
60 "ARM64_RELOC_PAGE21": "patch_aarch64_21r",
61 "ARM64_RELOC_PAGEOFF12": "patch_aarch64_12",
62 "ARM64_RELOC_UNSIGNED": "patch_64",
63 # x86_64-pc-windows-msvc:
64 "IMAGE_REL_AMD64_REL32": "patch_x86_64_32rx",
65 # aarch64-pc-windows-msvc:
66 "IMAGE_REL_ARM64_BRANCH26": "patch_aarch64_26r",
67 "IMAGE_REL_ARM64_PAGEBASE_REL21": "patch_aarch64_21r",
68 "IMAGE_REL_ARM64_PAGEOFFSET_12A": "patch_aarch64_12",
69 "IMAGE_REL_ARM64_PAGEOFFSET_12L": "patch_aarch64_12",
70 # i686-pc-windows-msvc:
71 "IMAGE_REL_I386_DIR32": "patch_32",
72 "IMAGE_REL_I386_REL32": "patch_x86_64_32rx",
73 # aarch64-unknown-linux-gnu:
74 "R_AARCH64_ABS64": "patch_64",
75 "R_AARCH64_ADD_ABS_LO12_NC": "patch_aarch64_12",
76 "R_AARCH64_ADR_GOT_PAGE": "patch_aarch64_21r",
77 "R_AARCH64_ADR_PREL_PG_HI21": "patch_aarch64_21r",
78 "R_AARCH64_CALL26": "patch_aarch64_26r",
79 "R_AARCH64_JUMP26": "patch_aarch64_26r",
80 "R_AARCH64_LD64_GOT_LO12_NC": "patch_aarch64_12",
81 "R_AARCH64_MOVW_UABS_G0_NC": "patch_aarch64_16a",
82 "R_AARCH64_MOVW_UABS_G1_NC": "patch_aarch64_16b",
83 "R_AARCH64_MOVW_UABS_G2_NC": "patch_aarch64_16c",
84 "R_AARCH64_MOVW_UABS_G3": "patch_aarch64_16d",
85 # x86_64-unknown-linux-gnu:
86 "R_X86_64_64": "patch_64",
87 "R_X86_64_GOTPCRELX": "patch_x86_64_32rx",
88 "R_X86_64_PLT32": "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.OPERAND0: "instruction->operand0",
107 HoleValue.OPERAND0_HI: "(instruction->operand0 >> 32)",
108 HoleValue.OPERAND0_LO: "(instruction->operand0 & UINT32_MAX)",
109 HoleValue.OPERAND1: "instruction->operand1",
110 HoleValue.OPERAND1_HI: "(instruction->operand1 >> 32)",
111 HoleValue.OPERAND1_LO: "(instruction->operand1 & UINT32_MAX)",
112 HoleValue.TARGET: "instruction->target",
113 HoleValue.JUMP_TARGET: "state->instruction_starts[instruction->jump_target]",
114 HoleValue.ERROR_TARGET: "state->instruction_starts[instruction->error_target]",
115 HoleValue.ZERO: "",
116 }
117
118
119 @dataclasses.dataclass
120 class Hole:
121 """
122 A "hole" in the stencil to be patched with a computed runtime value.
123
124 Analogous to relocation records in an object file.
125 """
126
127 offset: int
128 kind: _schema.HoleKind
129 # Patch with this base value:
130 value: HoleValue
131 # ...plus the address of this symbol:
132 symbol: str | None
133 # ...plus this addend:
134 addend: int
135 need_state: bool = False
136 func: str = dataclasses.field(init=False)
137 # Convenience method:
138 replace = dataclasses.replace
139
140 def __post_init__(self) -> None:
141 self.func = _PATCH_FUNCS[self.kind]
142
143 def as_c(self, where: str) -> str:
144 """Dump this hole as a call to a patch_* function."""
145 location = f"{where} + {self.offset:#x}"
146 value = _HOLE_EXPRS[self.value]
147 if self.symbol:
148 if value:
149 value += " + "
150 value += f"(uintptr_t)&{self.symbol}"
151 if _signed(self.addend) or not value:
152 if value:
153 value += " + "
154 value += f"{_signed(self.addend):#x}"
155 if self.need_state:
156 return f"{self.func}({location}, {value}, state);"
157 return f"{self.func}({location}, {value});"
158
159
160 @dataclasses.dataclass
161 class Stencil:
162 """
163 A contiguous block of machine code or data to be copied-and-patched.
164
165 Analogous to a section or segment in an object file.
166 """
167
168 body: bytearray = dataclasses.field(default_factory=bytearray, init=False)
169 holes: list[Hole] = dataclasses.field(default_factory=list, init=False)
170 disassembly: list[str] = dataclasses.field(default_factory=list, init=False)
171
172 def pad(self, alignment: int) -> None:
173 """Pad the stencil to the given alignment."""
174 offset = len(self.body)
175 padding = -offset % alignment
176 if padding:
177 self.disassembly.append(f"{offset:x}: {' '.join(['00'] * padding)}")
178 self.body.extend([0] * padding)
179
180 def add_nops(self, nop: bytes, alignment: int) -> None:
181 """Add NOPs until there is alignment. Fail if it is not possible."""
182 offset = len(self.body)
183 nop_size = len(nop)
184
185 # Calculate the gap to the next multiple of alignment.
186 gap = -offset % alignment
187 if gap:
188 if gap % nop_size == 0:
189 count = gap // nop_size
190 self.body.extend(nop * count)
191 else:
192 raise ValueError(
193 f"Cannot add nops of size '{nop_size}' to a body with "
194 f"offset '{offset}' to align with '{alignment}'"
195 )
196
197 def remove_jump(self) -> None:
198 """Remove a zero-length continuation jump, if it exists."""
199 hole = max(self.holes, key=lambda hole: hole.offset)
200 match hole:
201 case Hole(
202 offset=offset,
203 kind="IMAGE_REL_AMD64_REL32",
204 value=HoleValue.GOT,
205 symbol="_JIT_CONTINUE",
206 addend=-4,
207 ) as hole:
208 # jmp qword ptr [rip]
209 jump = b"\x48\xff\x25\x00\x00\x00\x00"
210 offset -= 3
211 case Hole(
212 offset=offset,
213 kind="IMAGE_REL_I386_REL32" | "R_X86_64_PLT32" | "X86_64_RELOC_BRANCH",
214 value=HoleValue.CONTINUE,
215 symbol=None,
216 addend=addend,
217 ) as hole if (
218 _signed(addend) == -4
219 ):
220 # jmp 5
221 jump = b"\xe9\x00\x00\x00\x00"
222 offset -= 1
223 case Hole(
224 offset=offset,
225 kind="R_AARCH64_JUMP26",
226 value=HoleValue.CONTINUE,
227 symbol=None,
228 addend=0,
229 ) as hole:
230 # b #4
231 jump = b"\x00\x00\x00\x14"
232 case _:
233 return
234 if self.body[offset:] == jump:
235 self.body = self.body[:offset]
236 self.holes.remove(hole)
237
238
239 @dataclasses.dataclass
240 class StencilGroup:
241 """
242 Code and data corresponding to a given micro-opcode.
243
244 Analogous to an entire object file.
245 """
246
247 code: Stencil = dataclasses.field(default_factory=Stencil, init=False)
248 data: Stencil = dataclasses.field(default_factory=Stencil, init=False)
249 symbols: dict[int | str, tuple[HoleValue, int]] = dataclasses.field(
250 default_factory=dict, init=False
251 )
252 _got: dict[str, int] = dataclasses.field(default_factory=dict, init=False)
253 _trampolines: set[int] = dataclasses.field(default_factory=set, init=False)
254
255 def process_relocations(
256 self, known_symbols: dict[str, int], *, alignment: int = 1, nop: bytes = b""
257 ) -> None:
258 """Fix up all GOT and internal relocations for this stencil group."""
259 for hole in self.code.holes.copy():
260 if (
261 hole.kind
262 in {"R_AARCH64_CALL26", "R_AARCH64_JUMP26", "ARM64_RELOC_BRANCH26"}
263 and hole.value is HoleValue.ZERO
264 and hole.symbol not in self.symbols
265 ):
266 hole.func = "patch_aarch64_trampoline"
267 hole.need_state = True
268 assert hole.symbol is not None
269 if hole.symbol in known_symbols:
270 ordinal = known_symbols[hole.symbol]
271 else:
272 ordinal = len(known_symbols)
273 known_symbols[hole.symbol] = ordinal
274 self._trampolines.add(ordinal)
275 hole.addend = ordinal
276 hole.symbol = None
277 self.code.remove_jump()
278 self.code.add_nops(nop=nop, alignment=alignment)
279 self.data.pad(8)
280 for stencil in [self.code, self.data]:
281 for hole in stencil.holes:
282 if hole.value is HoleValue.GOT:
283 assert hole.symbol is not None
284 hole.value = HoleValue.DATA
285 hole.addend += self._global_offset_table_lookup(hole.symbol)
286 hole.symbol = None
287 elif hole.symbol in self.symbols:
288 hole.value, addend = self.symbols[hole.symbol]
289 hole.addend += addend
290 hole.symbol = None
291 elif (
292 hole.kind in {"IMAGE_REL_AMD64_REL32"}
293 and hole.value is HoleValue.ZERO
294 ):
295 raise ValueError(
296 f"Add PyAPI_FUNC(...) or PyAPI_DATA(...) to declaration of {hole.symbol}!"
297 )
298 self._emit_global_offset_table()
299 self.code.holes.sort(key=lambda hole: hole.offset)
300 self.data.holes.sort(key=lambda hole: hole.offset)
301
302 def _global_offset_table_lookup(self, symbol: str) -> int:
303 return len(self.data.body) + self._got.setdefault(symbol, 8 * len(self._got))
304
305 def _emit_global_offset_table(self) -> None:
306 got = len(self.data.body)
307 for s, offset in self._got.items():
308 if s in self.symbols:
309 value, addend = self.symbols[s]
310 symbol = None
311 else:
312 value, symbol = symbol_to_value(s)
313 addend = 0
314 self.data.holes.append(
315 Hole(got + offset, "R_X86_64_64", value, symbol, addend)
316 )
317 value_part = value.name if value is not HoleValue.ZERO else ""
318 if value_part and not symbol and not addend:
319 addend_part = ""
320 else:
321 signed = "+" if symbol is not None else ""
322 addend_part = f"&{symbol}" if symbol else ""
323 addend_part += f"{_signed(addend):{signed}#x}"
324 if value_part:
325 value_part += "+"
326 self.data.disassembly.append(
327 f"{len(self.data.body):x}: {value_part}{addend_part}"
328 )
329 self.data.body.extend([0] * 8)
330
331 def _get_trampoline_mask(self) -> str:
332 bitmask: int = 0
333 trampoline_mask: list[str] = []
334 for ordinal in self._trampolines:
335 bitmask |= 1 << ordinal
336 while bitmask:
337 word = bitmask & ((1 << 32) - 1)
338 trampoline_mask.append(f"{word:#04x}")
339 bitmask >>= 32
340 return "{" + (", ".join(trampoline_mask) or "0") + "}"
341
342 def as_c(self, opname: str) -> str:
343 """Dump this hole as a StencilGroup initializer."""
344 return f"{{emit_{opname}, {len(self.code.body)}, {len(self.data.body)}, {self._get_trampoline_mask()}}}"
345
346
347 def symbol_to_value(symbol: str) -> tuple[HoleValue, str | None]:
348 """
349 Convert a symbol name to a HoleValue and a symbol name.
350
351 Some symbols (starting with "_JIT_") are special and are converted to their
352 own HoleValues.
353 """
354 if symbol.startswith("_JIT_"):
355 try:
356 return HoleValue[symbol.removeprefix("_JIT_")], None
357 except KeyError:
358 pass
359 return HoleValue.ZERO, symbol
360
361
362 def _signed(value: int) -> int:
363 value %= 1 << 64
364 if value & (1 << 63):
365 value -= 1 << 64
366 return value