| 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 |