tiny.tldr.formats.elf.object.layout

1const std = @import("std");2const elf = @import("../root.zig");3const model = @import("model.zig");45const Allocator = std.mem.Allocator;6const format = elf.format;7const ehdr_size = format.ehdr_size;8const shdr_size = format.shdr_size;9const sym_size = format.sym_size;10const rela_size = format.rela_size;11const Description = model.Description;12const Error = model.Error;13const Section = model.Section;14const Symbol = model.Symbol;1516/// The section names the writer supplies itself, leaving them out of every17/// description: the `.rela` prefix put before a section's name to name its18/// relocation section, and `.symtab`, `.strtab` and `.shstrtab`. The layout19/// sizes the section name table from these names, and the writer copies them20/// into it, so both agree on its bytes.21pub const rela_name_prefix = ".rela";22pub const symtab_name = ".symtab";23pub const strtab_name = ".strtab";24pub const shstrtab_name = ".shstrtab";2526/// The number of section headers every object has besides one per described27/// section and one per relocation section: the empty header at index 0 plus the28/// headers of `.symtab`, `.strtab` and `.shstrtab`. The layout adds this29/// constant when counting section headers, and tests use it to predict the30/// header count.31pub const fixed_section_count = 4;3233/// The number of 64-bit slots `plan` sets aside for each described section: the34/// section's file offset, its relocation count, and the file offset of its35/// relocation section. The `plan` function multiplies the section count by it36/// to size its scratch allocation.37const words_per_section = 3;3839/// Records where each part of one described object goes in the file: each40/// section's bytes, each relocation section, `.symtab`, `.strtab`, `.shstrtab`41/// and the section header table, along with the total file size. The `plan`42/// function computes the layout once from the description and checks every43/// addition and multiplication, so `write` has no arithmetic left that can44/// fail. One allocation, `scratch`, holds four slices in this order: each45/// section's file offset, each section's relocation count, each relocation46/// section's file offset, and the order in which the writer emits relocations.47/// The `build` function plans a layout and passes it to `write`, and a caller48/// that writes into its own buffer does the same and calls `deinit` to free49/// `scratch` with the allocator that was given to `plan`.50pub const Layout = struct {51    size: usize,52    shoff: u64,53    shnum: u16,54    symtab_index: u16,55    strtab_index: u16,56    shstrtab_index: u16,57    first_global: u32,58    symtab_offset: u64,59    symtab_size: u64,60    strtab_offset: u64,61    strtab_size: u64,62    shstrtab_offset: u64,63    shstrtab_size: u64,64    scratch: []u64,65    section_offsets: []u64,66    rela_counts: []u64,67    rela_starts: []u64,68    order: []u64,6970    /// Checks `description` and computes the file offset of every record, so71    /// callers run it before `write`, directly or through `build`, to learn the72    /// file size to allocate. The call returns `error.TooManySymbols` for 2^32 -73    /// 1 symbols or more, `error.InvalidAlignment` for an alignment that is74    /// neither 0 nor a power of two, and `error.InvalidSize` for a NOBITS75    /// section that carries bytes or for any other section whose nonzero `size`76    /// differs from the length of its bytes. The function returns77    /// `error.SymbolOrder` for a local symbol after a global one,78    /// `error.InvalidSectionIndex` for a relocation whose target is 0 or past79    /// the last section, `error.TooManySections` for more headers than an index80    /// below `SHN_LORESERVE` can name, and `error.SizeOverflow` for an offset81    /// or a string table size too large to represent. The function makes one82    /// allocation whose size follows from the section and relocation counts83    /// alone, so it is fixed up front and no later step enlarges it. The caller84    /// frees the result with `Layout.deinit`.85    pub fn plan(allocator: Allocator, description: Description) Error!Layout {86        if (description.symbols.len >= std.math.maxInt(u32)) return error.TooManySymbols;87        for (description.sections) |section| try validateSection(section);88        const first_global = try firstGlobalIndex(description.symbols);8990        const section_count = description.sections.len;91        const words = words_per_section * section_count + description.relocations.len;92        const scratch = try allocator.alloc(u64, words);93        errdefer allocator.free(scratch);94        const section_offsets = scratch[0..section_count];95        const rela_counts = scratch[section_count..][0..section_count];96        const rela_starts = scratch[2 * section_count ..][0..section_count];97        const order = scratch[words_per_section * section_count ..];98        const carved = section_offsets.len + rela_counts.len + rela_starts.len;99        std.debug.assert(carved + order.len == scratch.len);100101        const relocated_sections =102            try countRelocations(description, rela_counts, rela_starts, order);103104        const shnum_count = section_count + relocated_sections + fixed_section_count;105        if (shnum_count >= std.elf.SHN_LORESERVE) return error.TooManySections;106        const symtab_index: u16 = @intCast(1 + section_count + relocated_sections);107108        var offset = try placePayloads(description, section_offsets, rela_counts, rela_starts);109        offset = try alignForward(offset, 8);110        const symtab_offset = offset;111        const symtab_size = try mul(description.symbols.len + 1, sym_size);112        offset = try add(offset, symtab_size);113114        const strtab_offset = offset;115        const strtab_size = try symbolNameTableSize(description.symbols);116        offset = try add(offset, strtab_size);117118        const shstrtab_offset = offset;119        const shstrtab_size = try sectionNameTableSize(description.sections, rela_counts);120        offset = try add(offset, shstrtab_size);121122        const shoff = try alignForward(offset, 8);123        const total = try add(shoff, try mul(shnum_count, shdr_size));124125        return .{126            .size = std.math.cast(usize, total) orelse return error.SizeOverflow,127            .shoff = shoff,128            .shnum = @intCast(shnum_count),129            .symtab_index = symtab_index,130            .strtab_index = symtab_index + 1,131            .shstrtab_index = symtab_index + 2,132            .first_global = first_global,133            .symtab_offset = symtab_offset,134            .symtab_size = symtab_size,135            .strtab_offset = strtab_offset,136            .strtab_size = strtab_size,137            .shstrtab_offset = shstrtab_offset,138            .shstrtab_size = shstrtab_size,139            .scratch = scratch,140            .section_offsets = section_offsets,141            .rela_counts = rela_counts,142            .rela_starts = rela_starts,143            .order = order,144        };145    }146147    pub fn deinit(self: *Layout, allocator: Allocator) void {148        allocator.free(self.scratch);149        self.* = undefined;150    }151};152153/// Places each described section's bytes at the next offset its alignment154/// allows, starting after the 64-byte file header, then places each relocation155/// section at an 8-byte boundary, and returns the first offset past all of156/// them. The `plan` function calls it to place the section bytes and the157/// relocation sections before it places the tables that follow them. The158/// described sections go first so that each keeps the alignment its description159/// asked for. The function writes each relocation section's file offset into160/// `rela_starts`, or 0 for a section with no relocations, replacing the sort161/// positions `countRelocations` left there.162fn placePayloads(163    description: Description,164    section_offsets: []u64,165    rela_counts: []const u64,166    rela_starts: []u64,167) Error!u64 {168    var offset: u64 = ehdr_size;169    for (description.sections, 0..) |section, index| {170        offset = try alignForward(offset, section.alignment);171        section_offsets[index] = offset;172        offset = try add(offset, section.fileSize());173    }174    for (rela_counts, 0..) |count, index| {175        if (count == 0) {176            rela_starts[index] = 0;177            continue;178        }179        offset = try alignForward(offset, 8);180        rela_starts[index] = offset;181        offset = try add(offset, try mul(count, rela_size));182    }183    return offset;184}185186/// Counts the relocations aimed at each described section and returns how many187/// sections receive any. The `plan` function calls it once so that the writer188/// can emit every relocation section in a single walk. The function fills189/// `order` with relocation indices sorted by target section, keeping the input190/// order among relocations with the same target. `rela_starts` holds each191/// target's running position during this counting sort, and `placePayloads`192/// later overwrites it with file offsets. The function returns193/// `error.InvalidSectionIndex` for a target of 0 or one past the last described194/// section.195fn countRelocations(196    description: Description,197    rela_counts: []u64,198    rela_starts: []u64,199    order: []u64,200) Error!usize {201    @memset(rela_counts, 0);202    for (description.relocations) |relocation| {203        if (relocation.section == 0) return error.InvalidSectionIndex;204        const target = @as(usize, relocation.section);205        if (target > description.sections.len) return error.InvalidSectionIndex;206        rela_counts[relocation.section - 1] += 1;207    }208209    var running: u64 = 0;210    var relocated_sections: usize = 0;211    for (rela_counts, 0..) |count, index| {212        rela_starts[index] = running;213        running += count;214        if (count != 0) relocated_sections += 1;215    }216    std.debug.assert(running == description.relocations.len);217    for (description.relocations, 0..) |relocation, index| {218        const target = relocation.section - 1;219        order[@intCast(rela_starts[target])] = index;220        rela_starts[target] += 1;221    }222    return relocated_sections;223}224225fn validateSection(section: Section) Error!void {226    const aligned = section.alignment == 0 or std.math.isPowerOfTwo(section.alignment);227    if (!aligned) return error.InvalidAlignment;228    if (section.isNoBits()) {229        if (section.bytes.len != 0) return error.InvalidSize;230        return;231    }232    if (section.size != 0 and section.size != section.bytes.len) return error.InvalidSize;233}234235/// Computes the value of the symbol table header's `sh_info` field: the table236/// index one past the last local symbol. The `plan` function stores this result237/// so the writer can put it in the symbol table's header. Counting starts at238/// one because the writer places an empty entry at index 0. The function239/// returns `error.SymbolOrder` when a local symbol follows a global one.240fn firstGlobalIndex(symbols: []const Symbol) Error!u32 {241    var locals: usize = 0;242    var seen_global = false;243    for (symbols) |symbol| {244        if (!symbol.isLocal()) {245            seen_global = true;246            continue;247        }248        if (seen_global) return error.SymbolOrder;249        locals += 1;250    }251    return @intCast(1 + locals);252}253254fn symbolNameTableSize(symbols: []const Symbol) Error!u64 {255    var size: u64 = 1;256    for (symbols) |symbol| {257        if (symbol.name.len == 0) continue;258        size = try add(size, try add(symbol.name.len, 1));259    }260    if (size > std.math.maxInt(u32)) return error.SizeOverflow;261    return size;262}263264fn sectionNameTableSize(sections: []const Section, rela_counts: []const u64) Error!u64 {265    var size: u64 = 1;266    for (sections) |section| size = try add(size, try add(section.name.len, 1));267    for (sections, 0..) |section, index| {268        if (rela_counts[index] == 0) continue;269        size = try add(size, try add(rela_name_prefix.len + section.name.len, 1));270    }271    size = try add(size, symtab_name.len + 1);272    size = try add(size, strtab_name.len + 1);273    size = try add(size, shstrtab_name.len + 1);274    if (size > std.math.maxInt(u32)) return error.SizeOverflow;275    return size;276}277278fn add(left: u64, right: u64) Error!u64 {279    return std.math.add(u64, left, right) catch error.SizeOverflow;280}281282fn mul(left: u64, right: u64) Error!u64 {283    return std.math.mul(u64, left, right) catch error.SizeOverflow;284}285286/// Rounds `value` up to a multiple of `alignment`, and an alignment of 0 or 1287/// leaves it unchanged. `plan` and `placePayloads` use it for every aligned288/// offset. The function returns `error.SizeOverflow` when rounding up would289/// pass the largest 64-bit value.290fn alignForward(value: u64, alignment: u64) Error!u64 {291    if (alignment <= 1) return value;292    const mask = alignment - 1;293    return (try add(value, mask)) & ~mask;294}295296test "ELF object layout places every generated table after the described sections" {297    const allocator = std.testing.allocator;298    const description = Description{299        .sections = &.{300            Section.progbits(".text", "\x90\x90\x90\x90", std.elf.SHF_EXECINSTR, 16),301            Section.progbits(".data", "\x00\x00\x00\x00\x00\x00\x00\x00", std.elf.SHF_WRITE, 8),302            Section.nobits(".bss", 64, std.elf.SHF_WRITE, 8),303        },304        .symbols = &.{305            Symbol.section(1),306            Symbol.function("main", 1, 0, 4),307        },308        .relocations = &.{309            model.Relocation.x86_64(2, 0, 2, .@"64", 0),310        },311    };312313    var layout = try Layout.plan(allocator, description);314    defer layout.deinit(allocator);315316    try std.testing.expectEqual(@as(u16, 3 + 1 + fixed_section_count), layout.shnum);317    try std.testing.expectEqual(@as(u16, 5), layout.symtab_index);318    try std.testing.expectEqual(@as(u16, 6), layout.strtab_index);319    try std.testing.expectEqual(@as(u16, 7), layout.shstrtab_index);320    try std.testing.expectEqual(@as(u32, 2), layout.first_global);321322    try std.testing.expectEqual(@as(u64, 64), layout.section_offsets[0]);323    try std.testing.expectEqual(@as(u64, 72), layout.section_offsets[1]);324    try std.testing.expectEqual(@as(u64, 80), layout.section_offsets[2]);325326    try std.testing.expectEqual(@as(u64, 0), layout.rela_counts[0]);327    try std.testing.expectEqual(@as(u64, 1), layout.rela_counts[1]);328    try std.testing.expectEqual(@as(u64, 80), layout.rela_starts[1]);329330    try std.testing.expectEqual(@as(u64, 104), layout.symtab_offset);331    try std.testing.expectEqual(@as(u64, 3 * sym_size), layout.symtab_size);332    try std.testing.expectEqual(@as(u64, 176), layout.strtab_offset);333    try std.testing.expectEqual(@as(u64, 6), layout.strtab_size);334    try std.testing.expectEqual(@as(u64, 182), layout.shstrtab_offset);335    try std.testing.expectEqual(@as(u64, 1 + 6 + 6 + 5 + 11 + 8 + 8 + 10), layout.shstrtab_size);336    try std.testing.expectEqual(@as(u64, 240), layout.shoff);337    try std.testing.expectEqual(@as(usize, 240 + 8 * shdr_size), layout.size);338}339340test "ELF object layout orders relocations by target then by input" {341    const allocator = std.testing.allocator;342    const description = Description{343        .sections = &.{344            Section.progbits(".text", "\x90\x90\x90\x90\x90\x90\x90\x90", std.elf.SHF_EXECINSTR, 1),345            Section.progbits(".data", "\x00\x00\x00\x00\x00\x00\x00\x00", std.elf.SHF_WRITE, 1),346        },347        .symbols = &.{Symbol.undefinedFunction("target")},348        .relocations = &.{349            model.Relocation.x86_64(2, 0, 1, .@"64", 0),350            model.Relocation.x86_64(1, 1, 1, .PLT32, -4),351            model.Relocation.x86_64(2, 8, 1, .@"64", 8),352            model.Relocation.x86_64(1, 2, 1, .PC32, -4),353        },354    };355356    var layout = try Layout.plan(allocator, description);357    defer layout.deinit(allocator);358359    try std.testing.expectEqualSlices(u64, &.{ 2, 2 }, layout.rela_counts);360    try std.testing.expectEqualSlices(u64, &.{ 1, 3, 0, 2 }, layout.order);361    try std.testing.expect(layout.rela_starts[0] < layout.rela_starts[1]);362}363364test "ELF object layout refuses an alignment that is not a power of two" {365    const description = Description{ .sections = &.{Section.progbits(".text", "\x90", 0, 3)} };366    const planned = Layout.plan(std.testing.allocator, description);367    try std.testing.expectError(error.InvalidAlignment, planned);368}369370test "ELF object layout refuses a size that contradicts the section bytes" {371    const stated = Description{372        .sections = &.{.{ .name = ".text", .bytes = "\x90\x90", .size = 9 }},373    };374    try std.testing.expectError(error.InvalidSize, Layout.plan(std.testing.allocator, stated));375376    const occupied = Description{377        .sections = &.{.{378            .name = ".bss",379            .section_type = std.elf.SHT_NOBITS,380            .bytes = "\x00",381            .size = 8,382        }},383    };384    try std.testing.expectError(error.InvalidSize, Layout.plan(std.testing.allocator, occupied));385}386387test "ELF object layout refuses a relocation against no described section" {388    const sections = [_]Section{Section.progbits(".text", "\x90", 0, 1)};389    const absent = Description{390        .sections = &sections,391        .relocations = &.{model.Relocation.x86_64(0, 0, 1, .@"64", 0)},392    };393    const missing = Layout.plan(std.testing.allocator, absent);394    try std.testing.expectError(error.InvalidSectionIndex, missing);395396    const past_end = Description{397        .sections = &sections,398        .relocations = &.{model.Relocation.x86_64(2, 0, 1, .@"64", 0)},399    };400    const beyond = Layout.plan(std.testing.allocator, past_end);401    try std.testing.expectError(error.InvalidSectionIndex, beyond);402}403404test "ELF object layout refuses a local symbol after a global one" {405    const description = Description{406        .sections = &.{Section.progbits(".text", "\x90", 0, 1)},407        .symbols = &.{ Symbol.function("main", 1, 0, 1), Symbol.section(1) },408    };409    try std.testing.expectError(error.SymbolOrder, Layout.plan(std.testing.allocator, description));410}411412test "ELF object layout refuses more sections than a section index can name" {413    const allocator = std.testing.allocator;414    const sections = try allocator.alloc(Section, std.elf.SHN_LORESERVE);415    defer allocator.free(sections);416    for (sections) |*section| section.* = Section.progbits(".t", "\x90", 0, 1);417418    const planned = Layout.plan(allocator, .{ .sections = sections });419    try std.testing.expectError(error.TooManySections, planned);420}421422/// Returns a slice that claims 2^32 - 1 symbols over storage that holds one, so423/// the symbol limit test can pass `plan` a symbol count too large to store. The424/// `plan` function checks the count before it reads any entry, so the test425/// reads none of the missing elements and they need no memory.426fn overlongSymbols(storage: *const [1]Symbol) []const Symbol {427    return @as([*]const Symbol, storage)[0..std.math.maxInt(u32)];428}429430test "ELF object layout refuses more symbols than a table index can name" {431    const storage = [_]Symbol{.{}};432    const description = Description{ .sections = &.{}, .symbols = overlongSymbols(&storage) };433434    const planned = Layout.plan(std.testing.allocator, description);435    try std.testing.expectError(error.TooManySymbols, planned);436}437438test "ELF object layout refuses an alignment that leaves the address space" {439    const huge = @as(u64, 1) << 63;440    const description = Description{441        .sections = &.{442            .{ .name = ".a", .bytes = "\x90", .alignment = huge },443            .{ .name = ".b", .bytes = "\x90", .alignment = huge },444        },445    };446    const planned = Layout.plan(std.testing.allocator, description);447    try std.testing.expectError(error.SizeOverflow, planned);448}449450test "ELF object layout reports an allocator that cannot hold its scratch" {451    const description = Description{ .sections = &.{Section.progbits(".text", "\x90", 0, 1)} };452    const planned = Layout.plan(std.testing.failing_allocator, description);453    try std.testing.expectError(error.OutOfMemory, planned);454}

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