tiny.tldr.formats.elf.relocation.application

1const std = @import("std");2const root = @import("../../../root.zig");3const elf = @import("../root.zig");4const checked = @import("value.zig");5const kind = @import("kind.zig");6const relax = @import("relax.zig");7const relocation_target = @import("target.zig");89const Allocator = std.mem.Allocator;10const model = root.model;11const trace = root.trace;12const parallel = root.parallel;13const diagnostic = elf.diagnostic;14const elf_object = elf.object;15const format = elf.format;16const layout = elf.layout;17const program = elf.program;18const parser = elf.parser;19const output_section = elf.output_section;20const section_state = elf.section_state;21const got_table = elf.got_table;22const parallel_relocation_threshold = format.parallel_relocation_threshold;23const relocations_per_worker = format.relocations_per_worker;24const OutputSectionKind = output_section.OutputSectionKind;25const OutputSection = layout.OutputSection;26const ObjectLayout = layout.ObjectLayout;27const contributionAt = layout.contributionAt;28const ehFrameSectionLayout = layout.ehFrameSection;29const GlobalSymbol = layout.GlobalSymbol;30const GotLayout = layout.GotLayout;31const ObjectFile = parser.ObjectFile;32const sectionNameOrEmpty = parser.sectionNameOrEmpty;33const Rela = format.Rela;34const writeU16 = format.writeU16;35const writeU32 = format.writeU32;36const writeU64 = format.writeU64;37const sectionDiscarded = section_state.sectionDiscarded;38const foldedSection = section_state.foldedSection;39const canonicalGotSymbolRef = got_table.canonicalSymbolRef;40const tlsMemorySize = program.tlsMemorySize;41const SymbolAddressCache = elf.addressing.Cache;42const SymbolCacheAccess = elf.addressing.Access;43const relocationTargetAddress = elf.addressing.relocationTarget;44const symbolIsUnresolvedWeak = elf.addressing.symbolIsUnresolvedWeak;4546const absolute64_run_relocation_limit = 4096;47const absolute64_run_relocations_per_worker = relocations_per_worker * 8;48const debug_absolute_run_min_relocations = 4;4950const RelocationJob = struct {51    object_index: usize,52    contribution_size: u64,53    base_address: u64,54    base_file_offset: u64,55    relocations: []const Rela,56    absolute64_run: bool,57    ignore_missing_targets: bool,58    global_offset: usize,59    section_index: usize,60    deferred: bool = false,61};6263const JobRange = struct {64    start: usize = 0,65    end: usize = 0,66};6768const JobList = struct {69    jobs: std.ArrayListUnmanaged(RelocationJob) = .empty,70    object_ranges: []JobRange = &.{},71    total_relocations: usize = 0,72    deferred_jobs: usize = 0,7374    fn deinit(self: *JobList, scratch: Allocator) void {75        if (self.object_ranges.len != 0) scratch.free(self.object_ranges);76        self.jobs.deinit(scratch);77    }78};7980fn buildJobs(81    scratch: Allocator,82    objects: []const ObjectFile,83    layouts: []const ObjectLayout,84    output_sections: []const OutputSection,85    options: model.LinkOptions,86    with_object_ranges: bool,87) model.Error!JobList {88    var list = JobList{};89    errdefer list.deinit(scratch);90    if (with_object_ranges) {91        list.object_ranges = try scratch.alloc(JobRange, objects.len);92        @memset(list.object_ranges, .{});93    }94    for (objects, 0..) |object, object_index| {95        const object_job_start = list.jobs.items.len;96        const object_relocation_start = list.total_relocations;97        if (with_object_ranges) list.object_ranges[object_index].start = object_job_start;98        defer if (with_object_ranges) {99            list.object_ranges[object_index].end = list.jobs.items.len;100            if (list.total_relocations - object_relocation_start > relocations_per_worker) {101                for (list.jobs.items[object_job_start..]) |*job| {102                    if (!job.deferred) {103                        job.deferred = true;104                        list.deferred_jobs += 1;105                    }106                }107            }108        };109        if (object.relocations.len == 0) continue;110        for (object.sections, 0..) |_, section_index| {111            const relocations = if (ehFrameSectionLayout(layouts[object_index], section_index)) |eh_frame_section|112                eh_frame_section.relocations113            else114                object.relocationsForSection(section_index);115            if (relocations.len == 0) continue;116            if (sectionDiscarded(object, section_index)) continue;117            if (foldedSection(object, section_index) != null) continue;118119            const target_contribution = contributionAt(layouts[object_index].sections, section_index) orelse continue;120            const target_output = output_sections[target_contribution.outputIndex()];121            if (target_output.kind.isNoBits()) {122                const first_effective = firstEffectiveRelocation(relocations) orelse continue;123                diagnostic.recordUnsupportedRelocation(options, object, section_index, first_effective);124                return error.UnsupportedRelocation;125            }126127            const absolute64_run = relocations.len <= absolute64_run_relocation_limit and relocationsAreAbsolute64Run(relocations);128            const deferred = relocations.len > relocations_per_worker;129            if (deferred) list.deferred_jobs += 1;130            try list.jobs.append(scratch, .{131                .object_index = object_index,132                .contribution_size = target_contribution.size,133                .base_address = target_output.address + target_contribution.offset,134                .base_file_offset = target_output.file_offset + target_contribution.offset,135                .relocations = relocations,136                .absolute64_run = absolute64_run,137                .ignore_missing_targets = !target_output.kind.isAllocated(),138                .global_offset = list.total_relocations,139                .section_index = section_index,140                .deferred = deferred,141            });142            list.total_relocations += relocations.len;143        }144    }145    return list;146}147148const RelocationTask = struct {149    job_index: usize,150    start: usize,151    end: usize,152    global_offset: usize,153};154155const RelocationFailure = struct {156    found: bool = false,157    global_index: usize = 0,158    err: model.Error = error.UnsupportedRelocation,159    object_index: usize = 0,160    section_index: usize = 0,161    relocation: Rela = undefined,162};163164const RelocationFailures = parallel.FailureSlots(RelocationFailure);165166const ParallelRelocationContext = struct {167    objects: []const ObjectFile,168    layouts: []const ObjectLayout,169    output_sections: []const OutputSection,170    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),171    symbol_addresses: *SymbolAddressCache,172    got_layout: GotLayout,173    image: []u8,174    jobs: []const RelocationJob,175    tasks: []const RelocationTask,176    failures: *RelocationFailures,177    target_caches: []*relocation_target.Cache,178};179180const RelocationPlace = struct {181    address: u64,182    offset: u64,183};184185fn checkedRelocationPlace(186    contribution_size: u64,187    base_address: u64,188    base_file_offset: u64,189    relocation: Rela,190    write_size: u64,191) model.Error!RelocationPlace {192    if (relocation.offset > contribution_size or193        write_size > contribution_size - relocation.offset) return error.InvalidRange;194    return .{195        .address = base_address + relocation.offset,196        .offset = base_file_offset + relocation.offset,197    };198}199200fn applyOneRelocation(201    comptime cache_access: SymbolCacheAccess,202    objects: []const ObjectFile,203    layouts: []const ObjectLayout,204    output_sections: []const OutputSection,205    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),206    symbol_addresses: *SymbolAddressCache,207    got_layout: GotLayout,208    image: []u8,209    object_index: usize,210    contribution_size: u64,211    base_address: u64,212    base_file_offset: u64,213    relocation: Rela,214    ignore_missing_target: bool,215    target_cache: *relocation_target.Cache,216) model.Error!void {217    const object = objects[object_index];218    const relocation_type = relocation.relocationType();219    const symbol_index: usize = @intCast(relocation.symbolIndex());220    if (symbol_index >= object.symbols.len) return error.UndefinedSymbol;221222    switch (relocation_type) {223        @backingInt(std.elf.R_X86_64.@"64"),224        @backingInt(std.elf.R_X86_64.@"32"),225        @backingInt(std.elf.R_X86_64.@"32S"),226        @backingInt(std.elf.R_X86_64.@"16"),227        @backingInt(std.elf.R_X86_64.@"8"),228        => {229            const write_size: u64 = switch (relocation_type) {230                @backingInt(std.elf.R_X86_64.@"64") => 8,231                @backingInt(std.elf.R_X86_64.@"32"),232                @backingInt(std.elf.R_X86_64.@"32S"),233                => 4,234                @backingInt(std.elf.R_X86_64.@"16") => 2,235                @backingInt(std.elf.R_X86_64.@"8") => 1,236                else => unreachable,237            };238            const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, write_size);239            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, false, ignore_missing_target, target_cache)) orelse return;240            const value = target.address + target.addend;241            switch (relocation_type) {242                @backingInt(std.elf.R_X86_64.@"64") => writeU64(image, @intCast(place.offset), try checked.checkedX8664U64(value)),243                @backingInt(std.elf.R_X86_64.@"32") => writeU32(image, @intCast(place.offset), try checked.checkedU32(value)),244                @backingInt(std.elf.R_X86_64.@"32S") => writeU32(image, @intCast(place.offset), @bitCast(try checked.checkedI32(value))),245                @backingInt(std.elf.R_X86_64.@"16") => writeU16(image, @intCast(place.offset), try checked.checkedX8664U16(value)),246                @backingInt(std.elf.R_X86_64.@"8") => image[@intCast(place.offset)] = try checked.checkedX8664U8(value),247                else => unreachable,248            }249        },250        @backingInt(std.elf.R_X86_64.PC16),251        @backingInt(std.elf.R_X86_64.PC8),252        @backingInt(std.elf.R_X86_64.PC32),253        @backingInt(std.elf.R_X86_64.PLT32),254        @backingInt(std.elf.R_X86_64.PC64),255        => {256            const write_size: u64 = switch (relocation_type) {257                @backingInt(std.elf.R_X86_64.PC64) => 8,258                @backingInt(std.elf.R_X86_64.PC16) => 2,259                @backingInt(std.elf.R_X86_64.PC8) => 1,260                else => 4,261            };262            const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, write_size);263            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, false, ignore_missing_target, target_cache)) orelse return;264            const value = target.address + target.addend - @as(i128, @intCast(place.address));265            switch (relocation_type) {266                @backingInt(std.elf.R_X86_64.PC64) => writeU64(image, @intCast(place.offset), @bitCast(try checked.checkedI64(value))),267                @backingInt(std.elf.R_X86_64.PC32),268                @backingInt(std.elf.R_X86_64.PLT32),269                => writeU32(image, @intCast(place.offset), @bitCast(try checked.checkedI32(value))),270                @backingInt(std.elf.R_X86_64.PC16) => writeU16(image, @intCast(place.offset), @bitCast(try checked.checkedI16(value))),271                @backingInt(std.elf.R_X86_64.PC8) => image[@intCast(place.offset)] = @bitCast(try checked.checkedI8(value)),272                else => unreachable,273            }274        },275        @backingInt(std.elf.R_X86_64.GOTPCREL),276        @backingInt(std.elf.R_X86_64.GOTPCRELX),277        @backingInt(std.elf.R_X86_64.REX_GOTPCRELX),278        => {279            const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, 4);280            if (relocation_type == @backingInt(std.elf.R_X86_64.GOTPCREL) and symbolIsUnresolvedWeak(object, symbol_index, globals)) {281                if (relax.gotpcrelWeakUndefinedNullCheck(image, @intCast(place.offset))) return;282            }283            if (relocation_type == @backingInt(std.elf.R_X86_64.GOTPCREL)) {284                if (relax.gotpcrelxInstruction(image, @intCast(place.offset), relocation_type)) |relaxation| {285                    const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, false, ignore_missing_target, target_cache)) orelse return;286                    const value = switch (relaxation) {287                        .pc_relative => target.address + target.addend - @as(i128, @intCast(place.address)),288                        .absolute_signed_32 => target.address + target.addend + 4,289                    };290                    writeU32(image, @intCast(place.offset), @bitCast(try checked.checkedI32(value)));291                    return;292                }293                const ref = try canonicalGotSymbolRef(objects, globals, object_index, symbol_index);294                const got_offset = got_layout.entryOffset(ref) orelse return error.MissingSection;295                const got = output_sections[@backingInt(OutputSectionKind.got)];296                const value = @as(i128, @intCast(got.address + got_offset)) + relocation.addend - @as(i128, @intCast(place.address));297                writeU32(image, @intCast(place.offset), @bitCast(try checked.checkedI32(value)));298                return;299            }300            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, false, ignore_missing_target, target_cache)) orelse return;301            const relaxation = relax.gotpcrelxInstruction(image, @intCast(place.offset), relocation_type) orelse return error.UnsupportedRelocation;302            const value = switch (relaxation) {303                .pc_relative => target.address + target.addend - @as(i128, @intCast(place.address)),304                .absolute_signed_32 => target.address + target.addend + 4,305            };306            writeU32(image, @intCast(place.offset), @bitCast(try checked.checkedI32(value)));307        },308        @backingInt(std.elf.R_X86_64.SIZE32),309        @backingInt(std.elf.R_X86_64.SIZE64),310        => {311            const write_size: u64 = if (relocation_type == @backingInt(std.elf.R_X86_64.SIZE64)) 8 else 4;312            const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, write_size);313            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, true, false, ignore_missing_target, target_cache)) orelse return;314            const value = @as(i128, @intCast(target.size)) + target.addend;315            switch (relocation_type) {316                @backingInt(std.elf.R_X86_64.SIZE32) => writeU32(image, @intCast(place.offset), try checked.checkedU32(value)),317                @backingInt(std.elf.R_X86_64.SIZE64) => writeU64(image, @intCast(place.offset), try checked.checkedU64(value)),318                else => unreachable,319            }320        },321        @backingInt(std.elf.R_X86_64.TPOFF32),322        @backingInt(std.elf.R_X86_64.TPOFF64),323        @backingInt(std.elf.R_X86_64.DTPOFF32),324        @backingInt(std.elf.R_X86_64.DTPOFF64),325        => {326            const write_size: u64 = switch (relocation_type) {327                @backingInt(std.elf.R_X86_64.TPOFF64),328                @backingInt(std.elf.R_X86_64.DTPOFF64),329                => 8,330                else => 4,331            };332            const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, write_size);333            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, true, ignore_missing_target, target_cache)) orelse return;334            const tls_size: i128 = @intCast(tlsMemorySize(output_sections));335            const value = target.address + target.addend - tls_size;336            switch (relocation_type) {337                @backingInt(std.elf.R_X86_64.TPOFF32),338                @backingInt(std.elf.R_X86_64.DTPOFF32),339                => writeU32(image, @intCast(place.offset), @bitCast(try checked.checkedI32(value))),340                @backingInt(std.elf.R_X86_64.TPOFF64),341                @backingInt(std.elf.R_X86_64.DTPOFF64),342                => writeU64(image, @intCast(place.offset), @bitCast(try checked.checkedI64(value))),343                else => unreachable,344            }345        },346        @backingInt(std.elf.R_X86_64.GOTTPOFF) => {347            const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, 4);348            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, true, ignore_missing_target, target_cache)) orelse return;349            const tls_size: i128 = @intCast(tlsMemorySize(output_sections));350            try relax.gottpoffToLocalExec(image, @intCast(place.offset), target.address - tls_size);351        },352        @backingInt(std.elf.R_X86_64.TLSGD) => {353            _ = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, 4);354            const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, relocation, false, true, ignore_missing_target, target_cache)) orelse return;355            const tls_size: i128 = @intCast(tlsMemorySize(output_sections));356            try relax.tlsGdToLocalExec(image, contribution_size, base_file_offset, relocation, target.address + target.addend - tls_size + 4);357        },358        @backingInt(std.elf.R_X86_64.TLSLD) => {359            _ = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, 4);360            try relax.tlsLdToLocalExec(image, contribution_size, base_file_offset, relocation);361        },362        else => {363            std.debug.assert(!kind.applicationSupported(relocation_type));364            return error.UnsupportedRelocation;365        },366    }367}368369fn recordRelocationDiagnostic(options: model.LinkOptions, object: ObjectFile, section_index: usize, err: model.Error, relocation: Rela) void {370    if (err == error.UnsupportedRelocation) diagnostic.recordUnsupportedRelocation(options, object, section_index, relocation);371}372373fn relocationsAreAbsolute64Run(relocations: []const Rela) bool {374    if (relocations.len < 2) return false;375    const first = relocations[0];376    if (first.relocationType() != @backingInt(std.elf.R_X86_64.@"64")) return false;377    const symbol_index = first.symbolIndex();378    const addend = first.addend;379    for (relocations[1..]) |relocation| {380        if (relocation.relocationType() != @backingInt(std.elf.R_X86_64.@"64")) return false;381        if (relocation.symbolIndex() != symbol_index) return false;382        if (relocation.addend != addend) return false;383    }384    return true;385}386387fn applyAbsolute64RelocationRun(388    comptime cache_access: SymbolCacheAccess,389    objects: []const ObjectFile,390    layouts: []const ObjectLayout,391    output_sections: []const OutputSection,392    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),393    symbol_addresses: *SymbolAddressCache,394    image: []u8,395    object_index: usize,396    contribution_size: u64,397    base_file_offset: u64,398    relocations: []const Rela,399    ignore_missing_targets: bool,400    target_cache: *relocation_target.Cache,401) model.Error!void {402    const first = relocations[0];403    const symbol_index: usize = @intCast(first.symbolIndex());404    if (symbol_index >= objects[object_index].symbols.len) return error.UndefinedSymbol;405    const target = target_cache.get(object_index, symbol_index, first.addend, false, false) orelse blk: {406        const resolved = relocationTargetAddress(407            cache_access,408            objects,409            layouts,410            output_sections,411            globals,412            symbol_addresses,413            object_index,414            symbol_index,415            first,416            false,417        ) catch |err| switch (err) {418            error.MissingSection => if (ignore_missing_targets) return else return err,419            else => return err,420        };421        target_cache.put(object_index, symbol_index, first.addend, false, false, resolved);422        break :blk resolved;423    };424    const resolved_value = try checked.checkedX8664U64(target.address + target.addend);425    for (relocations) |relocation| {426        if (relocation.offset > contribution_size or 8 > contribution_size - relocation.offset) return error.InvalidRange;427        const place_offset = base_file_offset + relocation.offset;428        writeU64(image, @intCast(place_offset), resolved_value);429    }430}431432fn relocationTypeIsDebugAbsoluteRunCandidate(relocation_type: u32) bool {433    return switch (relocation_type) {434        @backingInt(std.elf.R_X86_64.@"64"),435        @backingInt(std.elf.R_X86_64.@"32"),436        => true,437        else => false,438    };439}440441fn debugAbsoluteRunTargetDependsOnAddend(442    objects: []const ObjectFile,443    layouts: []const ObjectLayout,444    object_index: usize,445    symbol_index: usize,446) model.Error!bool {447    const object = objects[object_index];448    if (symbol_index >= object.symbols.len) return error.UndefinedSymbol;449    const symbol_record = object.symbols[symbol_index];450    if (!symbol_record.isSection()) return false;451    if (symbol_record.section_index >= object.sections.len) return false;452    return layout.mergeSection(layouts[object_index], symbol_record.section_index) != null;453}454455fn applyDebugAbsoluteRelocationRun(456    comptime cache_access: SymbolCacheAccess,457    objects: []const ObjectFile,458    layouts: []const ObjectLayout,459    output_sections: []const OutputSection,460    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),461    symbol_addresses: *SymbolAddressCache,462    image: []u8,463    object_index: usize,464    contribution_size: u64,465    base_address: u64,466    base_file_offset: u64,467    relocations: []const Rela,468    start: usize,469    end: usize,470    failed_local: *usize,471    target_cache: *relocation_target.Cache,472) model.Error!?usize {473    const first = relocations[start];474    const relocation_type = first.relocationType();475    if (!relocationTypeIsDebugAbsoluteRunCandidate(relocation_type)) return null;476477    const symbol_index: usize = @intCast(first.symbolIndex());478    if (try debugAbsoluteRunTargetDependsOnAddend(objects, layouts, object_index, symbol_index)) return null;479480    var run_end = start + 1;481    while (run_end < end) : (run_end += 1) {482        const relocation = relocations[run_end];483        if (relocation.relocationType() != relocation_type) break;484        if (relocation.symbolIndex() != first.symbolIndex()) break;485    }486    if (run_end - start < debug_absolute_run_min_relocations) return null;487488    const write_size: u64 = if (relocation_type == @backingInt(std.elf.R_X86_64.@"64")) 8 else 4;489    failed_local.* = start;490    _ = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, first, write_size);491492    var base_relocation = first;493    base_relocation.addend = 0;494    const target = (try relocation_target.cachedOrSkip(cache_access, objects, layouts, output_sections, globals, symbol_addresses, object_index, symbol_index, base_relocation, false, false, true, target_cache)) orelse return run_end;495    const base_value = target.address + target.addend;496497    var index = start;498    while (index < run_end) : (index += 1) {499        failed_local.* = index;500        const relocation = relocations[index];501        const place = try checkedRelocationPlace(contribution_size, base_address, base_file_offset, relocation, write_size);502        const value = base_value + relocation.addend;503        switch (relocation_type) {504            @backingInt(std.elf.R_X86_64.@"64") => writeU64(image, @intCast(place.offset), try checked.checkedX8664U64(value)),505            @backingInt(std.elf.R_X86_64.@"32") => writeU32(image, @intCast(place.offset), try checked.checkedU32(value)),506            else => unreachable,507        }508    }509    return run_end;510}511512fn applySerialRelocationJob(513    objects: []const ObjectFile,514    layouts: []const ObjectLayout,515    output_sections: []const OutputSection,516    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),517    symbol_addresses: *SymbolAddressCache,518    got_layout: GotLayout,519    image: []u8,520    options: model.LinkOptions,521    job: RelocationJob,522    target_cache: *relocation_target.Cache,523) model.Error!void {524    const object = objects[job.object_index];525    for (job.relocations, 0..) |relocation, relocation_index| {526        if (kind.isNone(relocation)) continue;527        if (kind.isRelaxedTlsRuntimeResolver(object, job.relocations, relocation_index)) continue;528        applyOneRelocation(529            .serial,530            objects,531            layouts,532            output_sections,533            globals,534            symbol_addresses,535            got_layout,536            image,537            job.object_index,538            job.contribution_size,539            job.base_address,540            job.base_file_offset,541            relocation,542            job.ignore_missing_targets,543            target_cache,544        ) catch |err| {545            recordRelocationDiagnostic(options, objects[job.object_index], job.section_index, err, relocation);546            return err;547        };548    }549}550551fn relocationFailureFound(failure: RelocationFailure) bool {552    return failure.found;553}554555fn relocationFailureBefore(lhs: RelocationFailure, rhs: RelocationFailure) bool {556    return lhs.global_index < rhs.global_index;557}558559fn recordParallelRelocationFailure(560    context: *ParallelRelocationContext,561    worker: usize,562    global_index: usize,563    err: model.Error,564    job: RelocationJob,565    relocation: Rela,566) void {567    if (context.failures.items[worker].found) return;568    context.failures.record(worker, .{569        .found = true,570        .global_index = global_index,571        .err = err,572        .object_index = job.object_index,573        .section_index = job.section_index,574        .relocation = relocation,575    });576}577578fn applyJobRange(579    context: *ParallelRelocationContext,580    worker: usize,581    job_index: usize,582    start: usize,583    end: usize,584    global_offset: usize,585) void {586    const job = context.jobs[job_index];587    const target_cache = context.target_caches[worker];588589    if (job.absolute64_run) {590        const relocation = job.relocations[start];591        applyAbsolute64RelocationRun(592            .concurrent,593            context.objects,594            context.layouts,595            context.output_sections,596            context.globals,597            context.symbol_addresses,598            context.image,599            job.object_index,600            job.contribution_size,601            job.base_file_offset,602            job.relocations[start..end],603            job.ignore_missing_targets,604            target_cache,605        ) catch |err| {606            recordParallelRelocationFailure(context, worker, global_offset, err, job, relocation);607            return;608        };609        return;610    }611612    var local = start;613    while (local < end) {614        const relocation = job.relocations[local];615        if (kind.isNone(relocation)) {616            local += 1;617            continue;618        }619        if (kind.isRelaxedTlsRuntimeResolver(context.objects[job.object_index], job.relocations, local)) {620            local += 1;621            continue;622        }623        if (job.ignore_missing_targets and end - local >= debug_absolute_run_min_relocations) {624            var failed_local = local;625            const next = applyDebugAbsoluteRelocationRun(626                .concurrent,627                context.objects,628                context.layouts,629                context.output_sections,630                context.globals,631                context.symbol_addresses,632                context.image,633                job.object_index,634                job.contribution_size,635                job.base_address,636                job.base_file_offset,637                job.relocations,638                local,639                end,640                &failed_local,641                target_cache,642            ) catch |err| {643                recordParallelRelocationFailure(context, worker, global_offset + failed_local - start, err, job, job.relocations[failed_local]);644                return;645            };646            if (next) |next_local| {647                local = next_local;648                continue;649            }650        }651        applyOneRelocation(652            .concurrent,653            context.objects,654            context.layouts,655            context.output_sections,656            context.globals,657            context.symbol_addresses,658            context.got_layout,659            context.image,660            job.object_index,661            job.contribution_size,662            job.base_address,663            job.base_file_offset,664            relocation,665            job.ignore_missing_targets,666            target_cache,667        ) catch |err| {668            recordParallelRelocationFailure(context, worker, global_offset + local - start, err, job, relocation);669            return;670        };671        local += 1;672    }673}674675fn applyRelocationTask(context: *ParallelRelocationContext, worker: usize, task_index: usize) void {676    if (context.failures.items[worker].found) return;677    const task = context.tasks[task_index];678    applyJobRange(context, worker, task.job_index, task.start, task.end, task.global_offset);679}680681fn applySerialJobs(682    objects: []const ObjectFile,683    layouts: []const ObjectLayout,684    output_sections: []const OutputSection,685    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),686    symbol_addresses: *SymbolAddressCache,687    got_layout: GotLayout,688    image: []u8,689    options: model.LinkOptions,690    jobs: []const RelocationJob,691) model.Error!void {692    var target_cache = relocation_target.Cache{};693    for (jobs) |job| {694        if (job.relocations.len == 0) continue;695        if (job.absolute64_run) {696            const relocation = job.relocations[0];697            applyAbsolute64RelocationRun(698                .serial,699                objects,700                layouts,701                output_sections,702                globals,703                symbol_addresses,704                image,705                job.object_index,706                job.contribution_size,707                job.base_file_offset,708                job.relocations,709                job.ignore_missing_targets,710                &target_cache,711            ) catch |err| {712                recordRelocationDiagnostic(options, objects[job.object_index], job.section_index, err, relocation);713                return err;714            };715            continue;716        }717        try applySerialRelocationJob(718            objects,719            layouts,720            output_sections,721            globals,722            symbol_addresses,723            got_layout,724            image,725            options,726            job,727            &target_cache,728        );729    }730}731732pub fn apply(733    scratch: Allocator,734    objects: []const ObjectFile,735    layouts: []const ObjectLayout,736    output_sections: []const OutputSection,737    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),738    symbol_addresses: *SymbolAddressCache,739    got_layout: GotLayout,740    image: []u8,741    options: model.LinkOptions,742) model.Error!void {743    var list = try buildJobs(scratch, objects, layouts, output_sections, options, false);744    defer list.deinit(scratch);745    if (list.total_relocations == 0) return;746747    const workers = relocationWorkers(list, options);748    if (workers <= 1) {749        return applySerialJobs(objects, layouts, output_sections, globals, symbol_addresses, got_layout, image, options, list.jobs.items);750    }751    return applyJobsParallel(scratch, objects, layouts, output_sections, globals, symbol_addresses, got_layout, image, options, list.jobs.items, workers, false);752}753754fn relocationWorkers(list: JobList, options: model.LinkOptions) usize {755    var absolute64_relocations: usize = 0;756    for (list.jobs.items) |job| {757        if (job.absolute64_run) absolute64_relocations += job.relocations.len;758    }759    const all_absolute64 = absolute64_relocations == list.total_relocations;760    const requested_workers = if (options.max_link_jobs != 0)761        options.max_link_jobs762    else if (all_absolute64)763        @max(1, list.total_relocations / absolute64_run_relocations_per_worker)764    else765        list.total_relocations / relocations_per_worker;766    return if (list.total_relocations >= parallel_relocation_threshold)767        parallel.chooseWorkers(list.total_relocations, requested_workers)768    else769        1;770}771772fn applyJobsParallel(773    scratch: Allocator,774    objects: []const ObjectFile,775    layouts: []const ObjectLayout,776    output_sections: []const OutputSection,777    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),778    symbol_addresses: *SymbolAddressCache,779    got_layout: GotLayout,780    image: []u8,781    options: model.LinkOptions,782    jobs: []const RelocationJob,783    workers: usize,784    deferred_only: bool,785) model.Error!void {786    var tasks = std.ArrayListUnmanaged(RelocationTask).empty;787    defer tasks.deinit(scratch);788    for (jobs, 0..) |job, job_index| {789        if (deferred_only and !job.deferred) continue;790        if (job.relocations.len == 0) continue;791        const grain: usize = if (job.absolute64_run) absolute64_run_relocations_per_worker else relocations_per_worker;792        var start: usize = 0;793        while (start < job.relocations.len) {794            const end = @min(start + grain, job.relocations.len);795            try tasks.append(scratch, .{796                .job_index = job_index,797                .start = start,798                .end = end,799                .global_offset = job.global_offset + start,800            });801            start = end;802        }803    }804    if (tasks.items.len == 0) return;805806    var failures = try RelocationFailures.init(scratch, workers, .{});807    defer failures.deinit(scratch);808809    var worker_arenas = try parallel.WorkerArenaPool.init(scratch, workers);810    defer worker_arenas.deinit();811812    const target_caches = try scratch.alloc(*relocation_target.Cache, workers);813    defer scratch.free(target_caches);814    for (target_caches, 0..) |*target_cache, worker| {815        target_cache.* = try worker_arenas.allocator(worker).create(relocation_target.Cache);816        target_cache.*.* = .{};817    }818819    var context = ParallelRelocationContext{820        .objects = objects,821        .layouts = layouts,822        .output_sections = output_sections,823        .globals = globals,824        .symbol_addresses = symbol_addresses,825        .got_layout = got_layout,826        .image = image,827        .jobs = jobs,828        .tasks = tasks.items,829        .failures = &failures,830        .target_caches = target_caches,831    };832    parallel.forItems(tasks.items.len, workers, &context, applyRelocationTask);833834    if (failures.earliest(relocationFailureFound, relocationFailureBefore)) |failure| {835        recordRelocationDiagnostic(options, objects[failure.object_index], failure.section_index, failure.err, failure.relocation);836        return failure.err;837    }838}839840const CopyFailure = struct {841    found: bool = false,842    object_index: usize = 0,843    err: model.Error = error.InvalidObject,844};845846const CopyFailures = parallel.FailureSlots(CopyFailure);847848const MaterializeContext = struct {849    relocation: ParallelRelocationContext,850    copy_failures: *CopyFailures,851};852853const MaterializeObjectContext = struct {854    shared: MaterializeContext,855    object_ranges: []const JobRange,856};857858fn materializeObjectTask(context: *MaterializeObjectContext, worker: usize, object_index: usize) void {859    const relocation = &context.shared.relocation;860    elf.payload.copyObjectSections(861        relocation.image,862        relocation.objects[object_index],863        relocation.layouts[object_index],864        relocation.output_sections,865    ) catch |err| {866        const current = context.shared.copy_failures.items[worker];867        const failure = CopyFailure{868            .found = true,869            .object_index = object_index,870            .err = err,871        };872        if (!current.found or copyFailureBefore(failure, current)) {873            context.shared.copy_failures.record(worker, failure);874        }875        return;876    };877    if (relocation.failures.items[worker].found) return;878    const range = context.object_ranges[object_index];879    var job_index = range.start;880    while (job_index < range.end) : (job_index += 1) {881        const job = relocation.jobs[job_index];882        if (job.deferred) continue;883        applyJobRange(relocation, worker, job_index, 0, job.relocations.len, job.global_offset);884        if (relocation.failures.items[worker].found) return;885    }886}887888fn copyFailureFound(failure: CopyFailure) bool {889    return failure.found;890}891892fn copyFailureBefore(left: CopyFailure, right: CopyFailure) bool {893    return left.object_index < right.object_index;894}895896pub fn materialize(897    scratch: Allocator,898    objects: []const ObjectFile,899    layouts: []const ObjectLayout,900    output_sections: []const OutputSection,901    globals: *const std.StringHashMapUnmanaged(GlobalSymbol),902    symbol_addresses: *SymbolAddressCache,903    got_layout: GotLayout,904    image: []u8,905    options: model.LinkOptions,906) model.Error!void {907    if (elf.payload.wantsBatchedObjectCopy(objects)) {908        try elf.payload.copyAllocSections(scratch, image, objects, layouts, output_sections, options);909        return apply(scratch, objects, layouts, output_sections, globals, symbol_addresses, got_layout, image, options);910    }911912    var list = try buildJobs(scratch, objects, layouts, output_sections, options, true);913    defer list.deinit(scratch);914915    const workers = materializeWorkers(list, output_sections, options);916    if (workers <= 1) {917        try elf.payload.copyAllocSections(scratch, image, objects, layouts, output_sections, options);918        return applySerialJobs(objects, layouts, output_sections, globals, symbol_addresses, got_layout, image, options, list.jobs.items);919    }920921    var copy_failures = try CopyFailures.init(scratch, workers, .{});922    defer copy_failures.deinit(scratch);923    var relocation_failures = try RelocationFailures.init(scratch, workers, .{});924    defer relocation_failures.deinit(scratch);925926    var worker_arenas = try parallel.WorkerArenaPool.init(scratch, workers);927    defer worker_arenas.deinit();928    const target_caches = try scratch.alloc(*relocation_target.Cache, workers);929    defer scratch.free(target_caches);930    for (target_caches, 0..) |*target_cache, worker| {931        target_cache.* = try worker_arenas.allocator(worker).create(relocation_target.Cache);932        target_cache.*.* = .{};933    }934935    var context = MaterializeObjectContext{936        .shared = .{937            .relocation = .{938                .objects = objects,939                .layouts = layouts,940                .output_sections = output_sections,941                .globals = globals,942                .symbol_addresses = symbol_addresses,943                .got_layout = got_layout,944                .image = image,945                .jobs = list.jobs.items,946                .tasks = &.{},947                .failures = &relocation_failures,948                .target_caches = target_caches,949            },950            .copy_failures = &copy_failures,951        },952        .object_ranges = list.object_ranges,953    };954    parallel.forItems(objects.len, workers, &context, materializeObjectTask);955956    if (copy_failures.earliest(copyFailureFound, copyFailureBefore)) |failure| {957        return failure.err;958    }959960    if (list.deferred_jobs != 0) {961        try applyJobsParallel(scratch, objects, layouts, output_sections, globals, symbol_addresses, got_layout, image, options, list.jobs.items, workers, true);962    }963964    if (relocation_failures.earliest(relocationFailureFound, relocationFailureBefore)) |failure| {965        recordRelocationDiagnostic(options, objects[failure.object_index], failure.section_index, failure.err, failure.relocation);966        return failure.err;967    }968}969970fn materializeWorkers(list: JobList, output_sections: []const OutputSection, options: model.LinkOptions) usize {971    var load_bytes: usize = 0;972    for (output_sections) |section| {973        if (section.kind.isNoBits()) continue;974        load_bytes +|= @intCast(section.fileLoadSize());975    }976    const relocation_request = list.total_relocations / relocations_per_worker;977    const copy_request = load_bytes / parallel_materialize_bytes_per_worker;978    const requested_workers = if (options.max_link_jobs != 0)979        options.max_link_jobs980    else981        @max(relocation_request, copy_request);982    const busy = list.total_relocations >= parallel_relocation_threshold or983        load_bytes >= parallel_materialize_threshold;984    return if (busy and list.object_ranges.len > 1)985        parallel.chooseWorkers(list.object_ranges.len, requested_workers)986    else987        1;988}989990const parallel_materialize_threshold = 8 * 1024 * 1024;991const parallel_materialize_bytes_per_worker = 4 * 1024 * 1024;992993test "parallel relocation application matches serial output" {994    const allocator = std.testing.allocator;995    const record_count = parallel_relocation_threshold / 4 + 10_000;996    const record_size = 32;997998    const text = [_]u8{0xc3};999    const payload = [_]u8{ 1, 2, 3, 4, 5, 6, 7, 8 };10001001    const data = try allocator.alloc(u8, record_count * record_size);1002    defer allocator.free(data);1003    @memset(data, 0);10041005    const repeated_count = parallel_relocation_threshold + 1024;1006    const repeated_data = try allocator.alloc(u8, repeated_count * 8);1007    defer allocator.free(repeated_data);1008    @memset(repeated_data, 0);10091010    const debug_record_count = 1024;1011    const debug_record_size = 12;1012    const debug_data = try allocator.alloc(u8, debug_record_count * debug_record_size);1013    defer allocator.free(debug_data);1014    @memset(debug_data, 0);1015    const debug_abbrev = [_]u8{ 1, 2, 3, 4 };10161017    const text_index: u16 = 1;1018    const payload_index: u16 = 2;1019    const data_index: u16 = 3;1020    const repeated_index: u16 = 4;1021    const debug_index: u16 = 5;1022    const debug_abbrev_index: u16 = 6;1023    const sections = [_]elf_object.Section{1024        elf_object.Section.progbits(".text", &text, std.elf.SHF_EXECINSTR, 16),1025        elf_object.Section.progbits(".rodata.payload", &payload, 0, 1),1026        elf_object.Section.progbits(".data.relocs", data, std.elf.SHF_WRITE, 8),1027        elf_object.Section.progbits(".data.repeated", repeated_data, std.elf.SHF_WRITE, 8),1028        elf_object.Section.nonAlloc(".debug_info", debug_data, std.elf.SHT_PROGBITS, 1),1029        elf_object.Section.nonAlloc(".debug_abbrev", &debug_abbrev, std.elf.SHT_PROGBITS, 1),1030    };10311032    const debug_abbrev_symbol: u32 = debug_abbrev_index;1033    const start_symbol: u32 = sections.len + 1;1034    const payload_symbol: u32 = sections.len + 2;1035    const symbols = [_]elf_object.Symbol{1036        elf_object.Symbol.section(text_index),1037        elf_object.Symbol.section(payload_index),1038        elf_object.Symbol.section(data_index),1039        elf_object.Symbol.section(repeated_index),1040        elf_object.Symbol.section(debug_index),1041        elf_object.Symbol.section(debug_abbrev_index),1042        elf_object.Symbol.function("_start", text_index, 0, text.len),1043        elf_object.Symbol.object("payload", payload_index, 0, payload.len),1044    };10451046    const Relocation = elf_object.Relocation;1047    var relocations: std.ArrayListUnmanaged(Relocation) = .empty;1048    defer relocations.deinit(allocator);1049    try relocations.ensureTotalCapacityPrecise(1050        allocator,1051        4 * record_count + repeated_count + 2 * debug_record_count,1052    );10531054    var index: usize = 0;1055    while (index < record_count) : (index += 1) {1056        const base = index * record_size;1057        const size_addend: i64 = @intCast(index % 7);1058        const absolute_addend: i64 = @intCast(index % 5);1059        relocations.appendSliceAssumeCapacity(&.{1060            Relocation.x86_64(data_index, base + 0, payload_symbol, .SIZE64, size_addend),1061            Relocation.x86_64(data_index, base + 8, start_symbol, .PC64, 0),1062            Relocation.x86_64(data_index, base + 16, payload_symbol, .SIZE32, -1),1063            Relocation.x86_64(data_index, base + 24, start_symbol, .@"64", absolute_addend),1064        });1065    }1066    index = 0;1067    while (index < repeated_count) : (index += 1) {1068        const offset = index * 8;1069        relocations.appendAssumeCapacity(1070            Relocation.x86_64(repeated_index, offset, start_symbol, .@"64", 0),1071        );1072    }1073    index = 0;1074    while (index < debug_record_count) : (index += 1) {1075        const offset = index * debug_record_size;1076        const addend: i64 = @intCast(index % 17);1077        relocations.appendAssumeCapacity(1078            Relocation.x86_64(debug_index, offset, start_symbol, .@"64", addend),1079        );1080    }1081    index = 0;1082    while (index < debug_record_count) : (index += 1) {1083        const offset = index * debug_record_size + 8;1084        const addend: i64 = @intCast(index % 23);1085        relocations.appendAssumeCapacity(1086            Relocation.x86_64(debug_index, offset, debug_abbrev_symbol, .@"32", addend),1087        );1088    }10891090    const object = try elf_object.build(allocator, .{1091        .sections = &sections,1092        .symbols = &symbols,1093        .relocations = relocations.items,1094    });1095    defer allocator.free(object);10961097    const inputs = [_]model.Input{.{ .name = "reloc.o", .bytes = object }};10981099    var serial = try elf.linkExecutable(allocator, &inputs, .{ .incremental_mode = .off, .max_link_jobs = 1 });1100    defer serial.deinit(allocator);1101    var concurrent = try elf.linkExecutable(allocator, &inputs, .{ .incremental_mode = .off, .max_link_jobs = 0 });1102    defer concurrent.deinit(allocator);11031104    try std.testing.expectEqualSlices(u8, serial.bytes, concurrent.bytes);1105}11061107fn firstEffectiveRelocation(relocations: []const Rela) ?Rela {1108    for (relocations) |relocation| {1109        if (!kind.isNone(relocation)) return relocation;1110    }1111    return null;1112}

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