tiny.tldr.formats.elf.ehframe.scan

1pub const scan = @import("scan.zig");

1const std = @import("std");2const root = @import("../../../root.zig");3const elf = @import("../root.zig");4const section = @import("section.zig");56const Allocator = std.mem.Allocator;7const model = root.model;8const parallel = root.parallel;9const ObjectFile = elf.parser.ObjectFile;10const ObjectLayout = elf.layout.ObjectLayout;11const OutputSection = elf.layout.OutputSection;12const SectionContribution = elf.layout.SectionContribution;13const EhFramePieceLayout = elf.layout.EhFramePieceLayout;14const EhFrameCieLayout = elf.layout.EhFrameCieLayout;15const EhFrameSectionLayout = elf.layout.EhFrameSectionLayout;16const GlobalSymbol = elf.layout.GlobalSymbol;17const SectionHeader = elf.format.SectionHeader;18const Rela = elf.format.Rela;19const output_section_count = elf.output_section.output_section_count;20const sectionBytes = elf.format.sectionBytes;2122const parallel_scan_threshold = 2 * 1024 * 1024;23const scan_bytes_per_worker = 256 * 1024;2425pub const Scan = struct {26    pending: std.ArrayListUnmanaged(Pending) = .empty,2728    pub const Pending = struct {29        object_index: u32,30        section_index: u32,31        bytes: []const u8 = &.{},32        relocations: []const Rela = &.{},33        piece_count: usize = 0,34        relocation_count: usize = 0,35        cie_count: usize = 0,36        output_size: u64 = 0,37        pieces: []EhFramePieceLayout = &.{},38        adjusted: []Rela = &.{},39        cies: []EhFrameCieLayout = &.{},40        failure: model.Error!void = {},41    };4243    const PhaseContext = struct {44        pending: []Pending,45        objects: []const ObjectFile,46        globals: *const std.StringHashMapUnmanaged(GlobalSymbol),47    };4849    pub const Reference = struct {50        object_index: u32,51        section_index: u32,52    };5354    pub fn deinit(self: *Scan, allocator: Allocator) void {55        for (self.pending.items) |entry| {56            if (entry.cies.len != 0) allocator.free(entry.cies);57        }58        self.pending.deinit(allocator);59    }6061    pub fn prepare(62        self: *Scan,63        allocator: Allocator,64        objects: []const ObjectFile,65        layouts: []ObjectLayout,66        globals: *const std.StringHashMapUnmanaged(GlobalSymbol),67        options: model.LinkOptions,68        references: []const Reference,69    ) model.Error!void {70        var total_bytes: usize = 0;71        try self.pending.ensureTotalCapacity(allocator, references.len);72        for (references) |reference| {73            const object = objects[reference.object_index];74            const section_header = object.sections[reference.section_index];75            var entry = Pending{76                .object_index = reference.object_index,77                .section_index = reference.section_index,78                .relocations = object.relocationsForSection(reference.section_index),79            };80            if (sectionBytes(object.bytes, section_header)) |bytes| {81                entry.bytes = bytes;82                total_bytes += bytes.len;83            } else |err| {84                entry.failure = err;85            }86            self.pending.appendAssumeCapacity(entry);87        }88        if (self.pending.items.len == 0) return;8990        const pending = self.pending.items;91        const requested_workers = if (options.max_link_jobs != 0)92            options.max_link_jobs93        else94            total_bytes / scan_bytes_per_worker;95        const workers = if (total_bytes >= parallel_scan_threshold)96            parallel.chooseWorkers(pending.len, requested_workers)97        else98            1;99100        var context = PhaseContext{ .pending = pending, .objects = objects, .globals = globals };101        if (workers <= 1) {102            for (pending, 0..) |_, index| countPending(&context, 0, index);103        } else {104            parallel.forItems(pending.len, workers, &context, countPending);105        }106107        for (pending) |*entry| {108            entry.failure catch continue;109            entry.pieces = try allocator.alloc(EhFramePieceLayout, entry.piece_count);110            entry.adjusted = try allocator.alloc(Rela, entry.relocation_count);111            const slots = try ensureLayouts(allocator, objects[entry.object_index], &layouts[entry.object_index].eh_frame_sections);112            slots[entry.section_index] = .{113                .present = true,114                .pieces = entry.pieces,115                .relocations = entry.adjusted,116            };117            entry.cies = try allocator.alloc(EhFrameCieLayout, entry.cie_count);118        }119120        if (workers <= 1) {121            for (pending, 0..) |_, index| fillPending(&context, 0, index);122        } else {123            parallel.forItems(pending.len, workers, &context, fillPending);124        }125    }126127    fn countPending(context: *PhaseContext, worker: usize, index: usize) void {128        _ = worker;129        const entry = &context.pending[index];130        entry.failure catch return;131        var consumer = Count{};132        entry.output_size = section.walk(133            context.objects,134            entry.object_index,135            entry.bytes,136            entry.relocations,137            context.globals,138            &consumer,139        ) catch |err| {140            entry.failure = err;141            return;142        };143        entry.piece_count = consumer.pieces;144        entry.relocation_count = consumer.relocations;145        entry.cie_count = consumer.cies;146    }147148    fn fillPending(context: *PhaseContext, worker: usize, index: usize) void {149        _ = worker;150        const entry = &context.pending[index];151        entry.failure catch return;152        var consumer = Fill{ .entry = entry };153        const output_size = section.walk(154            context.objects,155            entry.object_index,156            entry.bytes,157            entry.relocations,158            context.globals,159            &consumer,160        ) catch |err| {161            entry.failure = err;162            return;163        };164        std.debug.assert(output_size == entry.output_size);165        std.debug.assert(consumer.piece_index == entry.piece_count);166        std.debug.assert(consumer.relocation_index == entry.relocation_count);167        std.debug.assert(consumer.cie_index == entry.cie_count);168    }169};170171const Count = struct {172    pieces: usize = 0,173    relocations: usize = 0,174    cies: usize = 0,175176    pub fn piece(self: *Count, piece_layout: EhFramePieceLayout) void {177        _ = piece_layout;178        self.pieces += 1;179    }180181    pub fn cie(self: *Count, input_offset: u64, output_offset: u64) void {182        _ = input_offset;183        _ = output_offset;184        self.cies += 1;185    }186187    pub fn relocation(self: *Count, adjusted: Rela) void {188        _ = adjusted;189        self.relocations += 1;190    }191192    pub fn resolve(self: *Count, cie_input_offset: u64, output_size: u64) model.Error!u32 {193        _ = self;194        _ = cie_input_offset;195        _ = output_size;196        return 0;197    }198};199200const Fill = struct {201    entry: *Scan.Pending,202    piece_index: usize = 0,203    relocation_index: usize = 0,204    cie_index: usize = 0,205206    pub fn piece(self: *Fill, piece_layout: EhFramePieceLayout) void {207        self.entry.pieces[self.piece_index] = piece_layout;208        self.piece_index += 1;209    }210211    pub fn cie(self: *Fill, input_offset: u64, output_offset: u64) void {212        self.entry.cies[self.cie_index] = .{213            .input_offset = input_offset,214            .output_offset = output_offset,215        };216        self.cie_index += 1;217    }218219    pub fn relocation(self: *Fill, adjusted: Rela) void {220        self.entry.adjusted[self.relocation_index] = adjusted;221        self.relocation_index += 1;222    }223224    pub fn resolve(self: *Fill, cie_input_offset: u64, output_size: u64) model.Error!u32 {225        const cie_output_offset = section.cieOutputOffset(self.entry.cies[0..self.cie_index], cie_input_offset) orelse return error.InvalidObject;226        if (output_size + 4 < cie_output_offset) return error.InvalidObject;227        return std.math.cast(u32, output_size + 4 - cie_output_offset) orelse return error.InvalidRange;228    }229};230231fn ensureLayouts(232    allocator: Allocator,233    object: ObjectFile,234    eh_frame_sections: *[]EhFrameSectionLayout,235) Allocator.Error![]EhFrameSectionLayout {236    if (eh_frame_sections.*.len != 0) return eh_frame_sections.*;237    const sections = try allocator.alloc(EhFrameSectionLayout, object.sections.len);238    @memset(sections, .{});239    eh_frame_sections.* = sections;240    return sections;241}242243fn testWalkBytes() [44]u8 {244    var bytes = @as([44]u8, @splat(0));245    std.mem.writeInt(u32, bytes[0..4], 16, .little);246    std.mem.writeInt(u32, bytes[4..8], 0, .little);247    std.mem.writeInt(u32, bytes[20..24], 16, .little);248    std.mem.writeInt(u32, bytes[24..28], 24, .little);249    std.mem.writeInt(u32, bytes[40..44], 0, .little);250    return bytes;251}252253test "count and fill walks agree on synthetic eh_frame records" {254    const bytes = testWalkBytes();255    const globals: std.StringHashMapUnmanaged(GlobalSymbol) = .empty;256257    var count = Count{};258    const counted_size = try section.walk(&.{}, 0, &bytes, &.{}, &globals, &count);259    try std.testing.expectEqual(@as(u64, 44), counted_size);260    try std.testing.expectEqual(@as(usize, 3), count.pieces);261    try std.testing.expectEqual(@as(usize, 1), count.cies);262    try std.testing.expectEqual(@as(usize, 0), count.relocations);263264    var pieces: [3]EhFramePieceLayout = undefined;265    var cies: [1]EhFrameCieLayout = undefined;266    var entry = Scan.Pending{267        .object_index = 0,268        .section_index = 0,269        .pieces = &pieces,270        .cies = &cies,271    };272    var fill = Fill{ .entry = &entry };273    const filled_size = try section.walk(&.{}, 0, &bytes, &.{}, &globals, &fill);274    try std.testing.expectEqual(counted_size, filled_size);275    try std.testing.expectEqual(count.pieces, fill.piece_index);276    try std.testing.expectEqual(count.cies, fill.cie_index);277278    try std.testing.expectEqual(@as(u64, 0), pieces[0].input_offset);279    try std.testing.expectEqual(@as(u64, 20), pieces[0].size);280    try std.testing.expect(!pieces[0].patch_cie_pointer);281    try std.testing.expectEqual(@as(u64, 20), pieces[1].input_offset);282    try std.testing.expectEqual(@as(u64, 20), pieces[1].output_offset);283    try std.testing.expect(pieces[1].patch_cie_pointer);284    try std.testing.expectEqual(@as(u32, 24), pieces[1].cie_pointer);285    try std.testing.expectEqual(@as(u64, 40), pieces[2].input_offset);286    try std.testing.expectEqual(@as(u64, 4), pieces[2].size);287    try std.testing.expectEqual(@as(u64, 0), cies[0].input_offset);288}289290test "fill walk rejects an unresolved cie reference" {291    var bytes = @as([24]u8, @splat(0));292    std.mem.writeInt(u32, bytes[0..4], 16, .little);293    std.mem.writeInt(u32, bytes[4..8], 3, .little);294    std.mem.writeInt(u32, bytes[20..24], 0, .little);295    const globals: std.StringHashMapUnmanaged(GlobalSymbol) = .empty;296297    var count = Count{};298    _ = try section.walk(&.{}, 0, &bytes, &.{}, &globals, &count);299300    var pieces: [2]EhFramePieceLayout = undefined;301    var entry = Scan.Pending{302        .object_index = 0,303        .section_index = 0,304        .pieces = &pieces,305    };306    var fill = Fill{ .entry = &entry };307    try std.testing.expectError(error.InvalidObject, section.walk(&.{}, 0, &bytes, &.{}, &globals, &fill));308}