Compare commits

...

1 Commits

Author SHA1 Message Date
coah
4ce997995d Add relocation-aware jump-table comparison and tests 2026-10-01 18:56:34 -05:00
2 changed files with 372 additions and 0 deletions

View File

@@ -0,0 +1,213 @@
"""Compare relocated switch destinations after checking instructions with ctxdiff.
Usage: python jump_table_diff.py <unit> <function> [--table <reference-symbol>]
Paths follow ctxdiff.py: build/43U/{src,obj}/<unit>.o. Requires pyelftools.
Exit 0: all selected tables match (or no tables); 1: mismatch; 2: invalid or
ambiguous input. This checks relative destinations, not behavioral equivalence.
Automatic selection covers local jumptable_* symbols whose R_PPC_ADDR32 entries
all target the selected function. External callback tables/vtables are not
covered. Source locations are inferred from corresponding function relocations,
never from an assumption that both data sections have the same layout.
"""
import argparse
from dataclasses import dataclass
from pathlib import Path
import sys
from elftools.common.exceptions import ELFError
from elftools.elf.elffile import ELFFile
@dataclass(frozen=True)
class Symbol:
name: str
section: object
value: int
size: int
kind: str = "STT_OBJECT"
@dataclass(frozen=True)
class Relocation:
offset: int
kind: int
symbol: int
addend: int
@dataclass
class ObjectInfo:
sections: dict
symbols: list
relocations: dict
def symbol(self, name):
found = [s for s in self.symbols if s.name == name
and isinstance(s.section, int) and s.size]
if len(found) != 1:
raise ValueError("expected one defined symbol: " + name)
symbol = found[0]
if (symbol.section not in self.sections or symbol.value < 0
or symbol.size <= 0
or symbol.value + symbol.size > self.sections[symbol.section][1]):
raise ValueError("symbol is outside its section: " + name)
return symbol
def location(self, relocation):
if not 0 <= relocation.symbol < len(self.symbols):
raise ValueError("relocation symbol index is out of range")
symbol = self.symbols[relocation.symbol]
if not isinstance(symbol.section, int):
return None
if symbol.section not in self.sections:
raise ValueError("relocation symbol has an invalid section")
return symbol.section, symbol.value + relocation.addend
def relocs(self, section):
return self.relocations.get(section, {})
def read_object(path):
with open(path, "rb") as stream:
elf = ELFFile(stream)
if (elf.elfclass != 32 or elf.little_endian
or elf["e_machine"] != "EM_PPC" or elf["e_type"] != "ET_REL"):
raise ValueError("expected a relocatable big-endian ELF32 PowerPC object")
symtab = elf.get_section_by_name(".symtab")
if symtab is None:
raise ValueError("object has no .symtab")
symbols = [Symbol(s.name, s["st_shndx"], s["st_value"], s["st_size"],
s["st_info"]["type"]) for s in symtab.iter_symbols()]
sections = {}
relocations = {}
for index, section in enumerate(elf.iter_sections()):
sections[index] = (section.name, section["sh_size"])
if section["sh_type"] == "SHT_REL":
raise ValueError("REL relocations are unsupported; expected RELA")
if section["sh_type"] != "SHT_RELA":
continue
if elf.get_section(section["sh_link"]).name != ".symtab":
raise ValueError("relocation uses a different symbol table")
entries = relocations.setdefault(section["sh_info"], {})
for r in section.iter_relocations():
if r["r_offset"] in entries:
raise ValueError("multiple relocations at the same offset")
entries[r["r_offset"]] = Relocation(
r["r_offset"], r["r_info_type"], r["r_info_sym"], r["r_addend"])
return ObjectInfo(sections, symbols, relocations)
def jump_target(obj, relocation, function):
if relocation is None or relocation.kind != 1: # R_PPC_ADDR32
return None
location = obj.location(relocation)
if location is None or location[0] != function.section:
return None
offset = location[1] - function.value
if offset < 0 or offset >= function.size or offset % 4:
return None
return offset
def reference_tables(obj, function, name=None):
candidates = [obj.symbol(name)] if name else [
s for s in obj.symbols if s.name.startswith("jumptable_") and s.size]
result = []
for table in candidates:
if not isinstance(table.section, int) or table.size % 4:
if name:
raise ValueError("invalid reference table extent")
continue
section_size = obj.sections[table.section][1]
if table.value < 0 or table.value + table.size > section_size:
raise ValueError("reference table is outside its section")
targets = [jump_target(obj, obj.relocs(table.section).get(offset), function)
for offset in range(table.value, table.value + table.size, 4)]
if targets and all(target is not None for target in targets):
result.append((table, targets))
elif name:
raise ValueError("reference table does not target the selected function")
return result
def source_table_location(source, reference, source_fn, reference_fn, table):
if source_fn.size != reference_fn.size:
raise ValueError("function sizes differ; check ctxdiff before table matching")
locations = set()
for relocation in reference.relocs(reference_fn.section).values():
if not reference_fn.value <= relocation.offset < reference_fn.value + reference_fn.size:
continue
if reference.location(relocation) != (table.section, table.value):
continue
offset = source_fn.value + relocation.offset - reference_fn.value
other = source.relocs(source_fn.section).get(offset)
if other is None or other.kind != relocation.kind:
raise ValueError("table-reference relocations differ; check ctxdiff")
location = source.location(other)
if location is None:
raise ValueError("source table reference is undefined")
if source.sections[location[0]][0] != reference.sections[table.section][0]:
raise ValueError("source table resolves to a different section")
locations.add(location)
if len(locations) != 1:
raise ValueError("cannot infer one source table from function relocations")
section, offset = next(iter(locations))
sizes = {s.size for s in source.symbols if s.section == section
and s.value == offset and s.size and s.kind != "STT_SECTION"}
if len(sizes) != 1:
raise ValueError("source table extent is missing or ambiguous")
size = next(iter(sizes))
if size % 4 or offset < 0 or offset + size > source.sections[section][1]:
raise ValueError("invalid source table extent")
return section, offset, size
def compare_table(source, reference, source_fn, reference_fn, table, expected):
section, offset, size = source_table_location(
source, reference, source_fn, reference_fn, table)
actual = [jump_target(source, source.relocs(section).get(i), source_fn)
for i in range(offset, offset + size, 4)]
differences = []
for i in range(max(len(actual), len(expected))):
src = actual[i] if i < len(actual) else None
ref = expected[i] if i < len(expected) else None
if i >= min(len(actual), len(expected)) or src != ref:
differences.append((i, src, ref))
return actual, differences
def main(argv=None):
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument("unit", help="e.g. src/scene/sdChannelSelect/iplSDChannelSelect")
parser.add_argument("function", help="exact function symbol used by ctxdiff")
parser.add_argument("--table", help="optional exact reference jump-table symbol")
args = parser.parse_args(argv)
try:
source = read_object(Path("build/43U/src") / (args.unit + ".o"))
reference = read_object(Path("build/43U/obj") / (args.unit + ".o"))
source_fn = source.symbol(args.function)
reference_fn = reference.symbol(args.function)
tables = reference_tables(reference, reference_fn, args.table)
mismatch = False
for table, expected in tables:
actual, differences = compare_table(
source, reference, source_fn, reference_fn, table, expected)
matched = sum(a == b for a, b in zip(actual, expected))
print("%s: %d/%d entries match (source=%d reference=%d)" %
(table.name, matched, len(expected), len(actual), len(expected)))
for index, src, ref in differences:
src_text = "unresolved/missing" if src is None else "+0x%X" % src
ref_text = "missing" if ref is None else "+0x%X" % ref
print(" [%d] source %s; reference %s" % (index, src_text, ref_text))
mismatch |= bool(differences)
print("Compared %d jump table(s); instruction correctness requires ctxdiff." % len(tables))
return 1 if mismatch else 0
except (OSError, ValueError, ELFError) as error:
print("ERROR: %s" % error, file=sys.stderr)
return 2
if __name__ == "__main__":
sys.exit(main())

View File

@@ -0,0 +1,159 @@
import contextlib
from dataclasses import replace
import io
import unittest
from unittest.mock import patch
import jump_table_diff as tool
def fixture(entries=(0x10, 0x20, 0x30), function_offset=0x100,
table_offset=0x40, source=False, section_ids=(1, 2)):
text, data = section_ids
symbols = [
tool.Symbol("dispatch", text, function_offset, 0x80, "STT_FUNC"),
tool.Symbol("@123" if source else "jumptable_test", data,
table_offset, len(entries) * 4),
]
references = {
text: {
function_offset + 2: tool.Relocation(function_offset + 2, 6, 1, 0),
function_offset + 6: tool.Relocation(function_offset + 6, 4, 1, 0),
},
data: {table_offset + i * 4: tool.Relocation(table_offset + i * 4, 1, 0, value)
for i, value in enumerate(entries)},
}
return tool.ObjectInfo({text: (".text", 0x1000), data: (".data", 0x1000)},
symbols, references)
def compare(source, reference=None):
reference = reference or fixture()
src_fn = source.symbol("dispatch")
ref_fn = reference.symbol("dispatch")
table, expected = tool.reference_tables(reference, ref_fn, "jumptable_test")[0]
return tool.compare_table(source, reference, src_fn, ref_fn, table, expected)
class JumpTableTests(unittest.TestCase):
def test_infers_shifted_source_table_and_function(self):
source = fixture(source=True, function_offset=0x200, table_offset=0x90,
section_ids=(3, 4))
self.assertEqual(compare(source), ([0x10, 0x20, 0x30], []))
def test_detects_swapped_destinations_despite_same_function_size(self):
actual, differences = compare(fixture((0x20, 0x10, 0x30), source=True))
self.assertEqual(actual, [0x20, 0x10, 0x30])
self.assertEqual(differences, [(0, 0x20, 0x10), (1, 0x10, 0x20)])
def test_section_relative_code_reference(self):
source = fixture(source=True, table_offset=0x90)
source.symbols.append(tool.Symbol("", 2, 0, 0, "STT_SECTION"))
for offset, relocation in list(source.relocations[1].items()):
source.relocations[1][offset] = replace(relocation, symbol=2, addend=0x90)
self.assertEqual(compare(source)[1], [])
def test_section_relative_table_entries(self):
source = fixture(source=True)
source.symbols.append(tool.Symbol("", 1, 0, 0, "STT_SECTION"))
for offset, relocation in list(source.relocations[2].items()):
source.relocations[2][offset] = replace(
relocation, symbol=2, addend=0x100 + relocation.addend)
self.assertEqual(compare(source)[1], [])
def test_missing_entry_is_mismatch(self):
source = fixture(source=True)
del source.relocations[2][0x44]
self.assertEqual(compare(source)[1], [(1, None, 0x20)])
def test_wrong_relocation_kind_is_mismatch(self):
source = fixture(source=True)
source.relocations[2][0x44] = replace(source.relocations[2][0x44], kind=10)
self.assertEqual(compare(source)[1], [(1, None, 0x20)])
def test_out_of_function_destination_is_mismatch(self):
source = fixture(source=True)
source.relocations[2][0x44] = replace(source.relocations[2][0x44], addend=0x80)
self.assertEqual(compare(source)[1], [(1, None, 0x20)])
def test_extra_source_entry_is_not_a_pass(self):
self.assertEqual(compare(fixture((0x10, 0x20, 0x30, 0x40), source=True))[1],
[(3, 0x40, None)])
def test_short_source_table_is_not_a_pass(self):
self.assertEqual(compare(fixture((0x10, 0x20), source=True))[1],
[(2, None, 0x30)])
def test_different_function_sizes_reject_inference(self):
source = fixture(source=True)
source.symbols[0] = replace(source.symbols[0], size=0x84)
with self.assertRaisesRegex(ValueError, "function sizes differ"):
compare(source)
def test_disagreeing_code_references_reject_inference(self):
source = fixture(source=True)
source.relocations[1][0x106] = replace(source.relocations[1][0x106], addend=4)
with self.assertRaisesRegex(ValueError, "infer one source table"):
compare(source)
def test_missing_code_reference_rejects_inference(self):
source = fixture(source=True)
del source.relocations[1][0x106]
with self.assertRaisesRegex(ValueError, "table-reference relocations differ"):
compare(source)
def test_ambiguous_source_extent_rejects_inference(self):
source = fixture(source=True)
source.symbols.append(tool.Symbol("alias", 2, 0x40, 16))
with self.assertRaisesRegex(ValueError, "extent is missing or ambiguous"):
compare(source)
def test_different_source_section_rejects_inference(self):
source = fixture(source=True)
source.sections[2] = (".rodata", 0x1000)
with self.assertRaisesRegex(ValueError, "different section"):
compare(source)
def test_undefined_source_reference_rejects_inference(self):
source = fixture(source=True)
source.symbols[1] = replace(source.symbols[1], section="SHN_UNDEF")
with self.assertRaisesRegex(ValueError, "reference is undefined"):
compare(source)
def test_invalid_relocation_symbol_rejected(self):
source = fixture(source=True)
source.relocations[2][0x44] = replace(source.relocations[2][0x44], symbol=999)
with self.assertRaisesRegex(ValueError, "symbol index is out of range"):
compare(source)
def test_duplicate_function_rejected(self):
source = fixture(source=True)
source.symbols.append(source.symbols[0])
with self.assertRaisesRegex(ValueError, "one defined symbol"):
compare(source)
def test_out_of_section_symbol_rejected(self):
source = fixture(source=True)
source.symbols[0] = replace(source.symbols[0], size=0x2000)
with self.assertRaisesRegex(ValueError, "outside its section"):
compare(source)
def test_unrelated_reference_table_is_not_selected(self):
reference = fixture((0x80, 0x84, 0x88))
self.assertEqual(tool.reference_tables(reference, reference.symbol("dispatch")), [])
with self.assertRaisesRegex(ValueError, "does not target"):
tool.reference_tables(reference, reference.symbol("dispatch"), "jumptable_test")
def test_cli_exit_codes(self):
for source, expected_status in [(fixture(source=True), 0),
(fixture((0x20, 0x10, 0x30), source=True), 1)]:
with patch.object(tool, "read_object", side_effect=[source, fixture()]):
with contextlib.redirect_stdout(io.StringIO()):
self.assertEqual(tool.main(["unused", "dispatch"]), expected_status)
with patch.object(tool, "read_object", side_effect=ValueError("bad object")):
with contextlib.redirect_stderr(io.StringIO()):
self.assertEqual(tool.main(["unused", "dispatch"]), 2)
if __name__ == "__main__":
unittest.main()