tiny.tldr.formats.elf.relocation.decode

1const std = @import("std");2const root = @import("../../../root.zig");3const elf = @import("../root.zig");4const relocation_counts_mod = @import("count.zig");5const relocation_model = @import("model.zig");67const Allocator = std.mem.Allocator;8const model = root.model;9const parallel = root.parallel;10const format = elf.format;11const rela_size = format.rela_size;12const native_endian = format.native_endian;13const parallel_relocation_threshold = format.parallel_relocation_threshold;14const relocations_per_worker = format.relocations_per_worker;15const SectionHeader = format.SectionHeader;16const Rela = format.Rela;17const sectionBytes = format.sectionBytes;18const readU64 = format.readU64;19const writeU64 = format.writeU64;20const RelocationRange = relocation_model.RelocationRange;21const ObjectParseOptions = relocation_model.ObjectParseOptions;22const RelocationCounts = relocation_model.RelocationCounts;23const ParsedRelocations = relocation_model.ParsedRelocations;24const countRelocationsBySection = relocation_counts_mod.countRelocationsBySection;25const relocationSectionSkipped = relocation_counts_mod.relocationSectionSkipped;26const relocationSectionAllNone = relocation_counts_mod.relocationSectionAllNone;2728test "ELF parser skips debug relocation sections when stripping debug output" {29    const allocator = std.testing.allocator;3031    var rela_bytes = @as([rela_size]u8, @splat(0));32    writeU64(&rela_bytes, 0, 1);33    writeU64(&rela_bytes, 8, @backingInt(std.elf.R_X86_64.@"64"));34    const section_names = "\x00.debug_info\x00";3536    const sections = [_]SectionHeader{37        .{38            .name_offset = 0,39            .section_type = 0,40            .flags = 0,41            .address = 0,42            .offset = 0,43            .size = 0,44            .link = 0,45            .info = 0,46            .alignment = 0,47            .entry_size = 0,48        },49        .{50            .name_offset = 1,51            .section_type = std.elf.SHT_PROGBITS,52            .flags = 0,53            .address = 0,54            .offset = 0,55            .size = 8,56            .link = 0,57            .info = 0,58            .alignment = 0,59            .entry_size = 0,60        },61        .{62            .name_offset = 0,63            .section_type = std.elf.SHT_RELA,64            .flags = 0,65            .address = 0,66            .offset = 0,67            .size = rela_size,68            .link = 0,69            .info = 1,70            .alignment = 0,71            .entry_size = rela_size,72        },73    };7475    var retained_counts = try countRelocationsBySection(allocator, &rela_bytes, &sections, section_names, 0, .{});76    defer retained_counts.deinit(allocator);77    try std.testing.expectEqual(@as(usize, 1), retained_counts.counts[1]);7879    var stripped_counts = try countRelocationsBySection(allocator, &rela_bytes, &sections, section_names, 0, .{ .strip_debug = true });80    defer stripped_counts.deinit(allocator);81    try std.testing.expectEqual(@as(usize, 0), stripped_counts.counts[1]);8283    var parsed = try parseRelocationsBySection(allocator, &rela_bytes, &sections, section_names, stripped_counts, .{ .strip_debug = true });84    defer parsed.deinit(allocator);85    try std.testing.expectEqual(@as(usize, 0), parsed.relocations.len);86    try std.testing.expectEqual(@as(usize, 0), parsed.ranges[1].count);87}8889test "ELF parser combines duplicate relocation targets" {90    const allocator = std.testing.allocator;9192    var rela_bytes = @as([(rela_size * 2)]u8, @splat(0));93    writeU64(&rela_bytes, 0, 1);94    writeU64(&rela_bytes, 8, @backingInt(std.elf.R_X86_64.@"64"));95    writeU64(&rela_bytes, rela_size, 2);96    writeU64(&rela_bytes, rela_size + 8, @backingInt(std.elf.R_X86_64.@"64"));9798    const sections = [_]SectionHeader{99        .{100            .name_offset = 0,101            .section_type = 0,102            .flags = 0,103            .address = 0,104            .offset = 0,105            .size = 0,106            .link = 0,107            .info = 0,108            .alignment = 0,109            .entry_size = 0,110        },111        .{112            .name_offset = 0,113            .section_type = std.elf.SHT_PROGBITS,114            .flags = std.elf.SHF_ALLOC,115            .address = 0,116            .offset = 0,117            .size = 8,118            .link = 0,119            .info = 0,120            .alignment = 0,121            .entry_size = 0,122        },123        .{124            .name_offset = 0,125            .section_type = std.elf.SHT_RELA,126            .flags = 0,127            .address = 0,128            .offset = 0,129            .size = rela_size,130            .link = 0,131            .info = 1,132            .alignment = 0,133            .entry_size = rela_size,134        },135        .{136            .name_offset = 0,137            .section_type = std.elf.SHT_RELA,138            .flags = 0,139            .address = 0,140            .offset = rela_size,141            .size = rela_size,142            .link = 0,143            .info = 1,144            .alignment = 0,145            .entry_size = rela_size,146        },147    };148149    var counts = try countRelocationsBySection(allocator, &rela_bytes, &sections, "", 0, .{});150    defer counts.deinit(allocator);151    try std.testing.expect(counts.duplicate_targets);152153    var parsed = try parseRelocationsBySection(allocator, &rela_bytes, &sections, "", counts, .{});154    defer parsed.deinit(allocator);155    try std.testing.expect(parsed.owned);156    try std.testing.expectEqual(@as(usize, 2), parsed.ranges[1].count);157    try std.testing.expectEqual(@as(u64, 1), parsed.relocations[0].offset);158    try std.testing.expectEqual(@as(u64, 2), parsed.relocations[1].offset);159}160161const RelocationDecodeJob = struct {162    rela_bytes: []const u8,163    rela_count: usize,164    output_base: usize,165    flat_start: usize,166};167168const ParallelDecodeContext = struct {169    jobs: []const RelocationDecodeJob,170    relocations: []Rela,171};172173fn decodeRelocationRange(job: RelocationDecodeJob, relocations: []Rela, lo: usize, hi: usize) void {174    if (native_endian == .little) {175        const out = relocations[job.output_base + lo ..][0 .. hi - lo];176        const bytes_start = lo * rela_size;177        const bytes_end = hi * rela_size;178        @memcpy(std.mem.sliceAsBytes(out), job.rela_bytes[bytes_start..bytes_end]);179        return;180    }181182    var index = lo;183    while (index < hi) : (index += 1) {184        const raw = job.rela_bytes[index * rela_size ..][0..rela_size];185        relocations[job.output_base + index] = .{186            .offset = readU64(raw, 0),187            .info = readU64(raw, 8),188            .addend = @bitCast(readU64(raw, 16)),189        };190    }191}192193fn decodeRelocationChunk(context: *ParallelDecodeContext, worker: usize, start: usize, end: usize) void {194    _ = worker;195    for (context.jobs) |job| {196        const job_end = job.flat_start + job.rela_count;197        if (job_end <= start) continue;198        if (job.flat_start >= end) break;199        const lo = if (start > job.flat_start) start - job.flat_start else 0;200        const hi = if (end < job_end) end - job.flat_start else job.rela_count;201        decodeRelocationRange(job, context.relocations, lo, hi);202    }203}204205pub fn parseRelocationsBySection(206    allocator: Allocator,207    bytes: []const u8,208    sections: []const SectionHeader,209    section_names: []const u8,210    relocation_counts: RelocationCounts,211    parse_options: ObjectParseOptions,212) model.Error!ParsedRelocations {213    if (relocation_counts.counts.len == 0) {214        return .{215            .relocations = &.{},216            .owned = false,217            .ranges = &.{},218        };219    }220221    const relocation_ranges = try allocator.alloc(RelocationRange, sections.len);222    errdefer allocator.free(relocation_ranges);223    var relocation_count: usize = 0;224    for (relocation_ranges, 0..) |*range, section_index| {225        const count = relocation_counts.counts[section_index];226        range.* = .{227            .start = relocation_count,228            .count = count,229        };230        if (count > std.math.maxInt(usize) - relocation_count) return error.InvalidObject;231        relocation_count += count;232    }233    if (relocation_count == 0) {234        return .{235            .relocations = &.{},236            .owned = false,237            .ranges = relocation_ranges,238        };239    }240241    if (try borrowSingleRelocationSection(bytes, sections, section_names, relocation_count, parse_options)) |relocations| {242        return .{243            .relocations = relocations,244            .owned = false,245            .ranges = relocation_ranges,246        };247    }248249    const relocations = try allocator.alloc(Rela, relocation_count);250    errdefer allocator.free(relocations);251252    var jobs = std.ArrayListUnmanaged(RelocationDecodeJob).empty;253    defer jobs.deinit(allocator);254    var write_offsets: []usize = &.{};255    defer if (write_offsets.len != 0) allocator.free(write_offsets);256    if (relocation_counts.duplicate_targets) {257        write_offsets = try allocator.alloc(usize, sections.len);258        for (write_offsets, 0..) |*offset, section_index| {259            offset.* = relocation_ranges[section_index].start;260        }261    }262263    var flat_total: usize = 0;264    for (sections) |section| {265        if (section.section_type != std.elf.SHT_RELA) continue;266        if (try relocationSectionSkipped(section, sections, section_names, parse_options)) continue;267        const rela_bytes = try sectionBytes(bytes, section);268        if (relocationSectionAllNone(rela_bytes)) continue;269        const rela_count = rela_bytes.len / rela_size;270        const output_base = if (relocation_counts.duplicate_targets) blk: {271            const base = write_offsets[section.info];272            write_offsets[section.info] += rela_count;273            break :blk base;274        } else relocation_ranges[section.info].start;275        try jobs.append(allocator, .{276            .rela_bytes = rela_bytes,277            .rela_count = rela_count,278            .output_base = output_base,279            .flat_start = flat_total,280        });281        flat_total += rela_count;282    }283284    const requested_workers = flat_total / relocations_per_worker;285    const workers = if (flat_total >= parallel_relocation_threshold)286        parallel.chooseWorkers(flat_total, requested_workers)287    else288        1;289290    if (workers <= 1) {291        for (jobs.items) |job| decodeRelocationRange(job, relocations, 0, job.rela_count);292    } else {293        var context = ParallelDecodeContext{ .jobs = jobs.items, .relocations = relocations };294        parallel.forChunks(flat_total, requested_workers, &context, decodeRelocationChunk);295    }296297    return .{298        .relocations = relocations,299        .owned = true,300        .ranges = relocation_ranges,301    };302}303304fn borrowSingleRelocationSection(305    bytes: []const u8,306    sections: []const SectionHeader,307    section_names: []const u8,308    relocation_count: usize,309    parse_options: ObjectParseOptions,310) model.Error!?[]const Rela {311    if (native_endian != .little) return null;312313    var found: ?SectionHeader = null;314    for (sections) |section| {315        if (section.section_type != std.elf.SHT_RELA) continue;316        if (try relocationSectionSkipped(section, sections, section_names, parse_options)) continue;317        if (section.size == 0) continue;318        const rela_bytes = try sectionBytes(bytes, section);319        if (relocationSectionAllNone(rela_bytes)) continue;320        if (found != null) return null;321        found = section;322    }323    const section = found orelse return null;324    if (section.size / rela_size != relocation_count) return null;325326    const rela_bytes = try sectionBytes(bytes, section);327    if (!std.mem.isAligned(@intFromPtr(rela_bytes.ptr), @alignOf(Rela))) return null;328    return @alignCast(std.mem.bytesAsSlice(Rela, rela_bytes));329}

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