tiny.tldr.formats.elf.layout.collect

1const std = @import("std");2const allocators = @import("alloc");3const root = @import("../../../root.zig");4const elf = @import("../root.zig");56const Allocator = std.mem.Allocator;7const model = root.model;8const parallel = root.parallel;9const trace = root.trace;10const ObjectFile = elf.parser.ObjectFile;11const OutputSection = elf.layout.OutputSection;12const SectionContribution = elf.layout.SectionContribution;13const ObjectLayout = elf.layout.ObjectLayout;14const SymbolRef = elf.layout.SymbolRef;15const GlobalSymbol = elf.layout.GlobalSymbol;16const OutputSectionKind = elf.output_section.OutputSectionKind;17const SectionHeader = elf.format.SectionHeader;18const Symbol = elf.format.Symbol;19const output_section_count = elf.output_section.output_section_count;20const debugOutputIndexForName = elf.output_section.debugOutputIndexForName;21const outputIndexForAlloc = elf.output_section.indexForAllocatedNamed;22const outputIndexForFixedMerge = elf.output_section.indexForAllocated;23const isAllocPayloadSection = elf.output_section.isAllocatedPayloadType;24const sectionIsAllocated = elf.format.sectionIsAllocated;25const sectionNameOrEmpty = elf.parser.sectionNameOrEmpty;26const validateAlignment = elf.format.validateAlignment;27const alignForwardU64 = elf.format.alignForwardU64;28const contributionReserveSize = elf.layout.contributionReserveSize;2930const parallel_section_threshold = 4096;3132const Class = enum(u8) {33    none,34    empty_alloc,35    payload,36    ehframe,37    fixed_merge,38    string_merge,39};4041const Classification = struct {42    classes: []Class,43    outputs: []u8,44    merge_flags: []bool,45    object_bases: []usize,46};4748const WalkFailure = struct {49    object_index: usize = std.math.maxInt(usize),50    section_index: usize = 0,51    err: ?model.Error = null,5253    fn found(self: WalkFailure) bool {54        return self.err != null;55    }5657    fn before(self: WalkFailure, other: WalkFailure) bool {58        if (self.object_index != other.object_index) return self.object_index < other.object_index;59        return self.section_index < other.section_index;60    }61};6263const WalkFailures = parallel.FailureSlots(WalkFailure);6465pub fn sections(66    allocator: Allocator,67    objects: []const ObjectFile,68    output_sections: *[output_section_count]OutputSection,69    layouts: []ObjectLayout,70    section_contributions: []SectionContribution,71    layout_count: *usize,72    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),73    options: model.LinkOptions,74) model.Error!void {75    var string_merge: elf.merge.String = .{};76    defer string_merge.deinit(allocator);77    var eh_frame_scan: elf.ehframe.Scan = .{};78    defer eh_frame_scan.deinit(allocator);7980    initObjectLayouts(objects, layouts, section_contributions);81    layout_count.* += objects.len;8283    const classification = Classification{84        .classes = try allocator.alloc(Class, section_contributions.len),85        .outputs = try allocator.alloc(u8, section_contributions.len),86        .merge_flags = try allocator.alloc(bool, objects.len),87        .object_bases = try allocator.alloc(usize, objects.len),88    };89    defer {90        allocator.free(classification.object_bases);91        allocator.free(classification.merge_flags);92        allocator.free(classification.outputs);93        allocator.free(classification.classes);94    }95    var object_base: usize = 0;96    for (objects, 0..) |object, object_index| {97        classification.object_bases[object_index] = object_base;98        object_base += object.sections.len;99    }100101    const classify_failure = run_classify: {102        const classify_phase = trace.product(.contribution_classification);103        defer classify_phase.end();104        break :run_classify try classify(allocator, objects, layouts, classification, options);105    };106    {107        const scan_phase = trace.product(.contribution_ehframe_scan);108        defer scan_phase.end();109        var eh_references: std.ArrayListUnmanaged(elf.ehframe.Scan.Reference) = .empty;110        defer eh_references.deinit(allocator);111        for (objects, 0..) |object, object_index| {112            const base = classification.object_bases[object_index];113            for (0..object.sections.len) |section_index| {114                if (classification.classes[base + section_index] != .ehframe) continue;115                try eh_references.append(allocator, .{116                    .object_index = @intCast(object_index),117                    .section_index = @intCast(section_index),118                });119            }120        }121        try eh_frame_scan.prepare(allocator, objects, layouts, globals, options, eh_references.items);122    }123    const register_failure = run_register: {124        const register_phase = trace.product(.contribution_merge_registration);125        defer register_phase.end();126        try reserveCommonSymbols(allocator, objects, layouts, globals);127        try reserveMergeLayouts(allocator, objects, layouts, classification);128        break :run_register try registerStringMerges(129            allocator,130            objects,131            layouts,132            classification,133            output_sections,134            &string_merge,135        );136    };137    const assign_failure = run_assign: {138        const assign_phase = trace.product(.contribution_chain_assignment);139        defer assign_phase.end();140        break :run_assign try assignChains(141            allocator,142            objects,143            layouts,144            classification,145            eh_frame_scan.pending.items,146            output_sections,147            globals,148            options,149        );150    };151152    if (earliestWalkFailure(classify_failure, earliestWalkFailure(register_failure, assign_failure))) |failure| {153        return failure.err.?;154    }155    const finish_phase = trace.product(.contribution_string_merge);156    defer finish_phase.end();157    try string_merge.finish(allocator, output_sections, options);158}159160fn earliestWalkFailure(left: ?WalkFailure, right: ?WalkFailure) ?WalkFailure {161    const first = left orelse return right;162    const second = right orelse return left;163    return if (WalkFailure.before(first, second)) first else second;164}165166const ClassifyContext = struct {167    objects: []const ObjectFile,168    layouts: []ObjectLayout,169    classification: Classification,170    options: model.LinkOptions,171    failures: *WalkFailures,172};173174fn classify(175    allocator: Allocator,176    objects: []const ObjectFile,177    layouts: []ObjectLayout,178    classification: Classification,179    options: model.LinkOptions,180) model.Error!?WalkFailure {181    const requested_workers = if (options.max_link_jobs != 0) options.max_link_jobs else 0;182    const workers = if (classification.classes.len >= parallel_section_threshold)183        parallel.chooseWorkers(objects.len, requested_workers)184    else185        1;186187    var failures = try WalkFailures.init(allocator, workers, .{});188    defer failures.deinit(allocator);189190    var context = ClassifyContext{191        .objects = objects,192        .layouts = layouts,193        .classification = classification,194        .options = options,195        .failures = &failures,196    };197    if (workers <= 1) {198        for (objects, 0..) |_, object_index| classifyObject(&context, 0, object_index);199    } else {200        parallel.forItems(objects.len, workers, &context, classifyObject);201    }202    return failures.earliest(WalkFailure.found, WalkFailure.before);203}204205fn classifyObject(context: *ClassifyContext, worker: usize, object_index: usize) void {206    const object = context.objects[object_index];207    const object_base = context.classification.object_bases[object_index];208    const classes = context.classification.classes[object_base..][0..object.sections.len];209    const outputs = context.classification.outputs[object_base..][0..object.sections.len];210    const contributions = context.layouts[object_index].sections;211    var has_merge = false;212213    for (object.sections, 0..) |section, section_index| {214        const class = classifySection(object, section, section_index, context.options) catch |err| {215            recordWalkFailure(context.failures, worker, object_index, section_index, err);216            classes[section_index] = .none;217            outputs[section_index] = 0;218            contributions[section_index] = .{};219            continue;220        };221        classes[section_index] = class.class;222        outputs[section_index] = class.output;223        switch (class.class) {224            .none, .fixed_merge, .string_merge => contributions[section_index] = .{},225            .empty_alloc, .payload, .ehframe => {},226        }227        if (class.class == .fixed_merge or class.class == .string_merge) has_merge = true;228    }229    context.classification.merge_flags[object_index] = has_merge;230}231232fn recordWalkFailure(233    failures: *WalkFailures,234    worker: usize,235    object_index: usize,236    section_index: usize,237    err: model.Error,238) void {239    const failure = WalkFailure{240        .object_index = object_index,241        .section_index = section_index,242        .err = err,243    };244    const current = failures.items[worker];245    if (!current.found() or WalkFailure.before(failure, current)) {246        failures.record(worker, failure);247    }248}249250const SectionClass = struct {251    class: Class,252    output: u8 = 0,253};254255fn classifySection(256    object: ObjectFile,257    section: SectionHeader,258    section_index: usize,259    options: model.LinkOptions,260) model.Error!SectionClass {261    const discarded_sections = object.discarded_sections;262    if (discarded_sections.len != 0 and discarded_sections[section_index]) return .{ .class = .none };263    const folded_sections = object.folded_sections;264    if (folded_sections.len != 0 and folded_sections[section_index] != null) return .{ .class = .none };265    if (section.size == 0) {266        if (!sectionIsAllocated(section)) return .{ .class = .none };267        if (!isAllocPayloadSection(section.section_type)) return error.UnsupportedFormat;268        try validateAlignment(section.alignment);269        const output_index = outputIndexForAlloc(section, sectionNameOrEmpty(object, section_index));270        return .{ .class = .empty_alloc, .output = @intCast(output_index) };271    }272    if ((section.flags & std.elf.SHF_ALLOC) == 0) {273        if (section.section_type != std.elf.SHT_PROGBITS) return .{ .class = .none };274        const name = sectionNameOrEmpty(object, section_index);275        const output_index = debugOutputIndexForName(name) orelse return .{ .class = .none };276        if (options.strip_debug) return .{ .class = .none };277        try validateAlignment(section.alignment);278        return .{ .class = .payload, .output = @intCast(output_index) };279    }280    if (elf.ehframe.isSection(object, section_index, section) and object.relocationsForSection(section_index).len != 0) {281        try validateAlignment(section.alignment);282        return .{ .class = .ehframe, .output = @backingInt(OutputSectionKind.eh_frame) };283    }284    if (elf.merge.fixed(section)) {285        if (object.relocationsForSection(section_index).len != 0) {286            return classifyAllocPayload(object, section, section_index);287        }288        return .{ .class = .fixed_merge, .output = @intCast(outputIndexForFixedMerge(section)) };289    }290    if (elf.merge.string(section)) {291        if (object.relocationsForSection(section_index).len != 0) {292            return classifyAllocPayload(object, section, section_index);293        }294        return .{ .class = .string_merge };295    }296    return classifyAllocPayload(object, section, section_index);297}298299fn classifyAllocPayload(300    object: ObjectFile,301    section: SectionHeader,302    section_index: usize,303) model.Error!SectionClass {304    if (!isAllocPayloadSection(section.section_type)) return error.UnsupportedFormat;305    try validateAlignment(section.alignment);306    const output_index = outputIndexForAlloc(section, sectionNameOrEmpty(object, section_index));307    return .{ .class = .payload, .output = @intCast(output_index) };308}309310fn reserveCommonSymbols(311    allocator: Allocator,312    objects: []const ObjectFile,313    layouts: []ObjectLayout,314    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),315) model.Error!void {316    for (objects, 0..) |object, object_index| {317        if (!object.has_common_symbols) continue;318        for (object.symbols, 0..) |symbol, symbol_index| {319            if (!commonSymbolEligible(object_index, symbol, symbol_index, globals)) continue;320            _ = try ensureCommonSymbolLayouts(allocator, object, &layouts[object_index].common_symbols);321            break;322        }323    }324}325326fn commonSymbolEligible(327    object_index: usize,328    symbol: Symbol,329    symbol_index: usize,330    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),331) bool {332    if (!symbol.isCommon()) return false;333    if (symbol.name.len == 0) return true;334    const global = globals.get(symbol.name) orelse return false;335    const current_ref = SymbolRef{ .object_index = object_index, .symbol_index = symbol_index };336    return global.ref.eql(current_ref);337}338339fn reserveMergeLayouts(340    allocator: Allocator,341    objects: []const ObjectFile,342    layouts: []ObjectLayout,343    classification: Classification,344) model.Error!void {345    for (objects, 0..) |object, object_index| {346        if (!classification.merge_flags[object_index]) continue;347        _ = try elf.merge.ensure(allocator, object, &layouts[object_index].merge_sections);348    }349}350351fn registerStringMerges(352    allocator: Allocator,353    objects: []const ObjectFile,354    layouts: []ObjectLayout,355    classification: Classification,356    output_sections: *[output_section_count]OutputSection,357    string_merge: *elf.merge.String,358) model.Error!?WalkFailure {359    for (objects, 0..) |object, object_index| {360        if (!classification.merge_flags[object_index]) continue;361        const object_base = classification.object_bases[object_index];362        const merge_sections = layouts[object_index].merge_sections;363        var merge_starts: elf.merge.StartIndex = .{};364        defer merge_starts.deinit(allocator);365        var use_merge_start_index: ?bool = null;366        for (object.sections, 0..) |section, section_index| {367            if (classification.classes[object_base + section_index] != .string_merge) continue;368            registerStringMerge(369                allocator,370                object,371                section,372                section_index,373                &merge_starts,374                &use_merge_start_index,375                output_sections,376                string_merge,377                merge_sections,378            ) catch |err| {379                return WalkFailure{380                    .object_index = object_index,381                    .section_index = section_index,382                    .err = err,383                };384            };385        }386    }387    return null;388}389390fn registerStringMerge(391    allocator: Allocator,392    object: ObjectFile,393    section: SectionHeader,394    section_index: usize,395    merge_starts: *elf.merge.StartIndex,396    use_merge_start_index: *?bool,397    output_sections: *[output_section_count]OutputSection,398    string_merge: *elf.merge.String,399    merge_sections: []elf.layout.MergeSectionLayout,400) model.Error!void {401    if (use_merge_start_index.* == null) use_merge_start_index.* = elf.merge.shouldIndexStarts(object);402    const external_starts = if (use_merge_start_index.*.?)403        try merge_starts.forSection(allocator, object, section_index)404    else405        try elf.merge.collectStarts(allocator, object, section_index);406    defer if (!use_merge_start_index.*.? and external_starts.len != 0) allocator.free(external_starts);407    try string_merge.register(408        allocator,409        object,410        section,411        section_index,412        external_starts,413        output_sections,414        &merge_sections[section_index],415    );416}417418const ChainContext = struct {419    allocator: Allocator,420    objects: []const ObjectFile,421    layouts: []ObjectLayout,422    classification: Classification,423    eh_pending: []const elf.ehframe.Scan.Pending,424    output_sections: *[output_section_count]OutputSection,425    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),426    options: model.LinkOptions,427    failures: *WalkFailures,428};429430fn assignChains(431    allocator: Allocator,432    objects: []const ObjectFile,433    layouts: []ObjectLayout,434    classification: Classification,435    eh_pending: []const elf.ehframe.Scan.Pending,436    output_sections: *[output_section_count]OutputSection,437    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),438    options: model.LinkOptions,439) model.Error!?WalkFailure {440    const requested_workers = if (options.max_link_jobs != 0) options.max_link_jobs else 0;441    const workers = if (classification.classes.len >= parallel_section_threshold)442        parallel.chooseWorkers(output_section_count, requested_workers)443    else444        1;445446    var failures = try WalkFailures.init(allocator, workers, .{});447    defer failures.deinit(allocator);448449    var locked_allocator = allocators.LockedAllocator.init(allocator);450    var context = ChainContext{451        .allocator = locked_allocator.allocator(),452        .objects = objects,453        .layouts = layouts,454        .classification = classification,455        .eh_pending = eh_pending,456        .output_sections = output_sections,457        .globals = globals,458        .options = options,459        .failures = &failures,460    };461    if (workers <= 1) {462        context.allocator = allocator;463        var chain_index: usize = 0;464        while (chain_index < output_section_count) : (chain_index += 1) assignChain(&context, 0, chain_index);465    } else {466        parallel.forItems(output_section_count, workers, &context, assignChain);467    }468    return failures.earliest(WalkFailure.found, WalkFailure.before);469}470471fn assignChain(context: *ChainContext, worker: usize, chain_index: usize) void {472    const is_eh_chain = chain_index == @backingInt(OutputSectionKind.eh_frame);473    const is_bss_chain = chain_index == @backingInt(OutputSectionKind.bss);474    var eh_cursor: usize = 0;475    var fixed_merge: elf.merge.Fixed = .{};476    defer fixed_merge.deinit(context.allocator);477478    for (context.objects, 0..) |object, object_index| {479        const object_base = context.classification.object_bases[object_index];480        const contributions = context.layouts[object_index].sections;481        for (object.sections, 0..) |section, section_index| {482            const flat = object_base + section_index;483            switch (context.classification.classes[flat]) {484                .ehframe => {485                    if (!is_eh_chain) continue;486                    const entry = context.eh_pending[eh_cursor];487                    std.debug.assert(entry.object_index == object_index);488                    std.debug.assert(entry.section_index == section_index);489                    eh_cursor += 1;490                    assignEhFrameSection(context, entry, section, section_index, contributions) catch |err| {491                        recordWalkFailure(context.failures, worker, object_index, section_index, err);492                        return;493                    };494                },495                .payload => {496                    if (context.classification.outputs[flat] != chain_index) continue;497                    payloadSection(context.output_sections, contributions, section, section_index, chain_index, context.options) catch |err| {498                        recordWalkFailure(context.failures, worker, object_index, section_index, err);499                        return;500                    };501                },502                .empty_alloc => {503                    if (context.classification.outputs[flat] != chain_index) continue;504                    emptyAllocSection(context.output_sections, contributions, section, section_index, chain_index) catch |err| {505                        recordWalkFailure(context.failures, worker, object_index, section_index, err);506                        return;507                    };508                },509                .fixed_merge => {510                    if (context.classification.outputs[flat] != chain_index) continue;511                    fixed_merge.collect(512                        context.allocator,513                        object,514                        section,515                        section_index,516                        context.output_sections,517                        context.layouts[object_index].merge_sections,518                        context.options,519                    ) catch |err| {520                        recordWalkFailure(context.failures, worker, object_index, section_index, err);521                        return;522                    };523                },524                .none, .string_merge => {},525            }526        }527        if (is_bss_chain and object.has_common_symbols and context.layouts[object_index].common_symbols.len != 0) {528            commonSymbols(529                object,530                object_index,531                context.output_sections,532                context.layouts[object_index].common_symbols,533                context.globals,534                context.options,535            ) catch |err| {536                recordWalkFailure(context.failures, worker, object_index, object.sections.len, err);537                return;538            };539        }540    }541}542543fn assignEhFrameSection(544    context: *ChainContext,545    entry: elf.ehframe.Scan.Pending,546    section: SectionHeader,547    section_index: usize,548    contributions: []SectionContribution,549) model.Error!void {550    try entry.failure;551    try elf.ehframe.section.assign(552        context.output_sections,553        contributions,554        section,555        section_index,556        entry.output_size,557        context.options,558    );559}560561fn initObjectLayouts(562    objects: []const ObjectFile,563    layouts: []ObjectLayout,564    section_contributions: []SectionContribution,565) void {566    var section_contribution_cursor: usize = 0;567    for (objects, 0..) |object, object_index| {568        const next_cursor = section_contribution_cursor + object.sections.len;569        layouts[object_index] = .{570            .sections = section_contributions[section_contribution_cursor..next_cursor],571            .common_symbols = &.{},572            .merge_sections = &.{},573            .eh_frame_sections = &.{},574        };575        section_contribution_cursor = next_cursor;576    }577    std.debug.assert(section_contribution_cursor == section_contributions.len);578}579580pub fn countObjectSections(objects: []const ObjectFile) model.Error!usize {581    var total: usize = 0;582    for (objects) |object| {583        if (object.sections.len > std.math.maxInt(usize) - total) return error.InvalidObject;584        total += object.sections.len;585    }586    return total;587}588589fn emptyAllocSection(590    output_sections: *[output_section_count]OutputSection,591    contributions: []SectionContribution,592    section: SectionHeader,593    section_index: usize,594    output_index: usize,595) model.Error!void {596    var output = &output_sections[output_index];597    try validateAlignment(section.alignment);598    const alignment = @max(section.alignment, 1);599    output.alignment = @max(output.alignment, alignment);600    const offset = if (section.section_type == std.elf.SHT_NOBITS)601        alignForwardU64(output.memory_size, alignment)602    else603        alignForwardU64(output.file_size, alignment);604    contributions[section_index] = SectionContribution.init(output_index, offset, 0, 0, alignment);605}606607fn payloadSize(608    output_sections: *[output_section_count]OutputSection,609    contributions: []SectionContribution,610    section: SectionHeader,611    section_index: usize,612    output_index: usize,613    size: u64,614    options: model.LinkOptions,615) model.Error!void {616    var output = &output_sections[output_index];617    try validateAlignment(section.alignment);618    output.alignment = @max(output.alignment, @max(section.alignment, 1));619    const alignment = @max(section.alignment, 1);620    const aligned_offset = if (section.section_type == std.elf.SHT_NOBITS)621        alignForwardU64(output.memory_size, alignment)622    else623        alignForwardU64(output.file_size, alignment);624    const reserved_size = contributionReserveSize(size, alignment, options);625    contributions[section_index] = SectionContribution.init(626        output_index,627        aligned_offset,628        size,629        reserved_size,630        alignment,631    );632633    if (section.section_type == std.elf.SHT_NOBITS) {634        output.memory_size = aligned_offset + reserved_size;635    } else {636        output.file_size = aligned_offset + reserved_size;637        output.memory_size = output.file_size;638    }639}640641fn payloadSection(642    output_sections: *[output_section_count]OutputSection,643    contributions: []SectionContribution,644    section: SectionHeader,645    section_index: usize,646    output_index: usize,647    options: model.LinkOptions,648) model.Error!void {649    try payloadSize(output_sections, contributions, section, section_index, output_index, section.size, options);650}651652fn commonSymbols(653    object: ObjectFile,654    object_index: usize,655    output_sections: *[output_section_count]OutputSection,656    contributions: []SectionContribution,657    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),658    options: model.LinkOptions,659) model.Error!void {660    for (object.symbols, 0..) |symbol, symbol_index| {661        if (!commonSymbolEligible(object_index, symbol, symbol_index, globals)) continue;662663        const alignment = @max(symbol.value, 1);664        try validateAlignment(alignment);665        const output_index = @backingInt(OutputSectionKind.bss);666        var output = &output_sections[output_index];667        output.alignment = @max(output.alignment, alignment);668        const aligned_offset = alignForwardU64(output.memory_size, alignment);669        const reserved_size = contributionReserveSize(symbol.size, alignment, options);670        contributions[symbol_index] = SectionContribution.init(671            output_index,672            aligned_offset,673            symbol.size,674            reserved_size,675            alignment,676        );677        output.memory_size = aligned_offset + reserved_size;678    }679}680681fn ensureCommonSymbolLayouts(682    allocator: Allocator,683    object: ObjectFile,684    common_symbols: *[]SectionContribution,685) Allocator.Error![]SectionContribution {686    if (common_symbols.*.len != 0) return common_symbols.*;687    const symbols = try allocator.alloc(SectionContribution, object.symbols.len);688    @memset(symbols, .{});689    common_symbols.* = symbols;690    return symbols;691}

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