tiny.tldr.formats.elf.merge

1pub const Fixed = struct {2    pieces: Map = .empty,34    pub fn deinit(self: *Fixed, allocator: Allocator) void {5        self.pieces.deinit(allocator);6    }78    pub fn collect(9        self: *Fixed,10        allocator: Allocator,11        object: ObjectFile,12        section: SectionHeader,13        section_index: usize,14        output_sections: *[output_section_count]OutputSection,15        merge_sections: []MergeSectionLayout,16        options: model.LinkOptions,17    ) model.Error!void {18        if (section.size % section.entry_size != 0) return error.InvalidObject;19        if (object.relocationsForSection(section_index).len != 0) return error.UnsupportedRelocation;2021        try validateAlignment(section.alignment);22        const entry_size: usize = @intCast(section.entry_size);23        const entry_count: usize = @intCast(section.size / section.entry_size);24        const layouts = try allocator.alloc(MergePieceLayout, entry_count);25        errdefer allocator.free(layouts);2627        const output_index = outputIndexForAlloc(section);28        const output_index_u8: u8 = @intCast(output_index);29        var output = &output_sections[output_index];30        const alignment = @max(section.alignment, 1);31        output.alignment = @max(output.alignment, alignment);3233        const bytes = try sectionBytes(object.bytes, section);34        for (layouts, 0..) |*piece_layout, index| {35            const start = index * entry_size;36            const piece_bytes = bytes[start..][0..entry_size];37            piece_layout.* = .{38                .input_offset = @intCast(start),39                .size = section.entry_size,40            };41            const key: Key = .{42                .section_type = section.section_type,43                .output_index = output_index_u8,44                .entry_size = section.entry_size,45                .alignment = alignment,46                .bytes = piece_bytes,47            };48            if (self.pieces.getContext(key, context)) |existing| {49                piece_layout.contribution = existing.contribution;50                piece_layout.output_intra_offset = existing.intra_offset;51                continue;52            }5354            const aligned_offset = alignForwardU64(output.file_size, alignment);55            const reserved_size = contributionReserveSize(section.entry_size, alignment, options);56            const contribution = SectionContribution.init(57                output_index,58                aligned_offset,59                section.entry_size,60                reserved_size,61                alignment,62            );63            try self.pieces.putContext(allocator, key, .{ .contribution = contribution }, context);64            piece_layout.contribution = contribution;65            output.file_size = aligned_offset + reserved_size;66            output.memory_size = output.file_size;67        }6869        merge_sections[section_index] = .{70            .pieces = layouts,71            .fixed_piece_size = section.entry_size,72        };73    }74};

1pub const Piece = struct {2    contribution: SectionContribution,3    intra_offset: u64,4};

1pub const Index = struct {2    built: bool = false,3    sections: []SectionStarts = &.{},45    pub fn deinit(self: *Index, allocator: Allocator) void {6        for (self.sections) |section| allocator.free(section.starts);7        allocator.free(self.sections);8        self.* = .{};9    }1011    pub fn forSection(12        self: *Index,13        allocator: Allocator,14        object: ObjectFile,15        section_index: usize,16    ) Allocator.Error![]const u64 {17        if (!self.built) try self.build(allocator, object);18        for (self.sections) |section| {19            if (section.section_index == section_index) return section.starts;20        }21        return &.{};22    }2324    fn build(self: *Index, allocator: Allocator, object: ObjectFile) Allocator.Error!void {25        var builders = std.ArrayListUnmanaged(SectionBuilder).empty;26        defer builders.deinit(allocator);27        errdefer deinitBuilders(allocator, builders.items);2829        for (object.symbols) |symbol| {30            if (symbol.section_index >= object.sections.len) continue;31            const section_index: usize = symbol.section_index;32            const section = object.sections[section_index];33            if (!mergeStringSectionWithoutRelocations(object, section, section_index)) continue;34            if (!symbol.isGlobalDefinition()) continue;35            const starts = try builderForSection(allocator, &builders, section_index);36            try starts.append(allocator, symbol.value);37        }3839        const sections = try allocator.alloc(SectionStarts, builders.items.len);40        var initialized_sections: usize = 0;41        errdefer {42            for (sections[0..initialized_sections]) |section| allocator.free(section.starts);43            allocator.free(sections);44        }45        for (builders.items, sections) |*builder, *section| {46            std.mem.sort(u64, builder.starts.items, {}, std.sort.asc(u64));47            section.* = .{48                .section_index = builder.section_index,49                .starts = try builder.starts.toOwnedSlice(allocator),50            };51            initialized_sections += 1;52        }53        self.sections = sections;54        self.built = true;55    }56};

1pub const String = struct {2    records: std.ArrayListUnmanaged(Record) = .empty,3    pending: std.ArrayListUnmanaged(Pending) = .empty,45    const Pending = struct {6        bytes: []const u8,7        external_starts: []const u64,8        layout_slot: *MergeSectionLayout,9        alignment: u64,10        section_type: u32,11        output_index: u8,12        base: usize = 0,13        count: usize = 0,14        pieces: []MergePieceLayout = &.{},15    };1617    const ScanContext = struct {18        pending: []Pending,19        records: []Record,20    };2122    pub fn deinit(self: *String, allocator: Allocator) void {23        self.records.deinit(allocator);24        self.pending.deinit(allocator);25    }2627    pub fn register(28        self: *String,29        allocator: Allocator,30        object: ObjectFile,31        section: SectionHeader,32        section_index: usize,33        external_starts: []const u64,34        output_sections: *[output_section_count]OutputSection,35        layout_slot: *MergeSectionLayout,36    ) model.Error!void {37        if (object.relocationsForSection(section_index).len != 0) return error.UnsupportedRelocation;3839        const bytes = try sectionBytes(object.bytes, section);40        if (bytes.len == 0) return;41        if (bytes[bytes.len - 1] != 0) return error.InvalidObject;4243        const output_index = outputIndexForAlloc(section);44        var output = &output_sections[output_index];45        const alignment = @max(section.alignment, 1);46        output.alignment = @max(output.alignment, alignment);4748        const starts = if (external_starts.len != 0)49            try allocator.dupe(u64, external_starts)50        else51            external_starts;52        try self.pending.append(allocator, .{53            .bytes = bytes,54            .external_starts = starts,55            .layout_slot = layout_slot,56            .alignment = alignment,57            .section_type = section.section_type,58            .output_index = @intCast(output_index),59        });60    }6162    pub fn finish(63        self: *String,64        allocator: Allocator,65        output_sections: *[output_section_count]OutputSection,66        options: model.LinkOptions,67    ) model.Error!void {68        try self.materialize(allocator, options);69        try target.assign(allocator, output_sections, self.records.items, options);70    }7172    fn materialize(self: *String, allocator: Allocator, options: model.LinkOptions) model.Error!void {73        if (self.pending.items.len == 0) return;74        const pending = self.pending.items;7576        var total_bytes: usize = 0;77        for (pending) |entry| total_bytes += entry.bytes.len;78        const requested_workers = if (options.max_link_jobs != 0)79            options.max_link_jobs80        else81            total_bytes / scan_bytes_per_worker;82        const workers = if (total_bytes >= parallel_scan_threshold)83            parallel.chooseWorkers(pending.len, requested_workers)84        else85            1;8687        var count_context = ScanContext{ .pending = pending, .records = &.{} };88        if (workers <= 1) {89            for (pending, 0..) |_, index| countPending(&count_context, 0, index);90        } else {91            parallel.forItems(pending.len, workers, &count_context, countPending);92        }9394        var total: usize = 0;95        for (pending) |*entry| {96            entry.base = total;97            total += entry.count;98            entry.pieces = try allocator.alloc(MergePieceLayout, entry.count);99            entry.layout_slot.* = .{ .pieces = entry.pieces };100        }101        if (std.math.cast(u32, total) == null) return error.InvalidObject;102        try self.records.resize(allocator, total);103104        var fill_context = ScanContext{ .pending = pending, .records = self.records.items };105        if (workers <= 1) {106            for (pending, 0..) |_, index| fillPending(&fill_context, 0, index);107        } else {108            parallel.forItems(pending.len, workers, &fill_context, fillPending);109        }110    }111112    fn countPending(context: *ScanContext, worker: usize, index: usize) void {113        _ = worker;114        context.pending[index].count = start.count(context.pending[index].bytes);115    }116117    fn fillPending(context: *ScanContext, worker: usize, index: usize) void {118        _ = worker;119        const entry = context.pending[index];120        const records = context.records[entry.base..][0..entry.count];121        const bytes = entry.bytes;122        var input_offset: usize = 0;123        var piece_index: usize = 0;124        var external_start_index: usize = 0;125        for (bytes, 0..) |byte, byte_index| {126            if (byte != 0) continue;127            const end = byte_index + 1;128            const string_bytes = bytes[input_offset..end];129            entry.pieces[piece_index] = .{130                .input_offset = @intCast(input_offset),131                .size = @intCast(string_bytes.len),132            };133            records[piece_index] = .{134                .ordinal = @intCast(entry.base + piece_index),135                .section_type = entry.section_type,136                .output_index = entry.output_index,137                .alignment = entry.alignment,138                .reverse_prefix = record.reversePrefix(string_bytes),139                .bytes = string_bytes,140                .piece = &entry.pieces[piece_index],141                .external_start = start.has(entry.external_starts, &external_start_index, input_offset),142            };143            piece_index += 1;144            input_offset = end;145        }146    }147};

1pub fn address(2    object_layout: ObjectLayout,3    object: ObjectFile,4    output_sections: []const OutputSection,5    section_index: usize,6    offset: u64,7) ?u64 {8    const entry = piece(object_layout, object, section_index, offset) orelse return null;9    const output = output_sections[entry.contribution.outputIndex()];10    return output.address + entry.contribution.offset + entry.intra_offset;11}

1pub fn contribution(2    object_layout: ObjectLayout,3    object: ObjectFile,4    section_index: usize,5    offset: u64,6) ?SectionContribution {7    const entry = piece(object_layout, object, section_index, offset) orelse return null;8    return entry.contribution;9}

1pub fn piece(2    object_layout: ObjectLayout,3    object: ObjectFile,4    section_index: usize,5    offset: u64,6) ?Piece {7    const merge_section = mergeSectionLayout(object_layout, section_index) orelse return null;8    const section = object.sections[section_index];9    if (offset >= section.size) return null;1011    if (merge_section.fixed_piece_size != 0) {12        const piece_index: usize = @intCast(offset / merge_section.fixed_piece_size);13        if (piece_index >= merge_section.pieces.len) return null;14        const fixed_piece = merge_section.pieces[piece_index];15        return .{16            .contribution = fixed_piece.contribution,17            .intra_offset = fixed_piece.output_intra_offset + offset % merge_section.fixed_piece_size,18        };19    }2021    const string_piece = stringPiece(merge_section.pieces, offset) orelse return null;22    return .{23        .contribution = string_piece.contribution,24        .intra_offset = string_piece.output_intra_offset + offset - string_piece.input_offset,25    };26}

1pub fn ensure(2    allocator: Allocator,3    object: ObjectFile,4    merge_sections: *[]MergeSectionLayout,5) Allocator.Error![]MergeSectionLayout {6    if (merge_sections.*.len != 0) return merge_sections.*;7    const sections = try allocator.alloc(MergeSectionLayout, object.sections.len);8    @memset(sections, .{});9    merge_sections.* = sections;10    return sections;11}

1pub fn fixed(section: SectionHeader) bool {2    if ((section.flags & std.elf.SHF_ALLOC) == 0) return false;3    if ((section.flags & std.elf.SHF_MERGE) == 0) return false;4    if ((section.flags & std.elf.SHF_STRINGS) != 0) return false;5    if (section.section_type != std.elf.SHT_PROGBITS) return false;6    if (section.entry_size == 0) return false;7    return true;8}

1pub fn string(section: SectionHeader) bool {2    if ((section.flags & std.elf.SHF_ALLOC) == 0) return false;3    if ((section.flags & std.elf.SHF_MERGE) == 0) return false;4    if ((section.flags & std.elf.SHF_STRINGS) == 0) return false;5    if (section.section_type != std.elf.SHT_PROGBITS) return false;6    if (section.entry_size > 1) return false;7    if (section.alignment > 1) return false;8    return true;9}

1pub fn collect(2    allocator: Allocator,3    object: ObjectFile,4    section_index: usize,5) Allocator.Error![]u64 {6    var starts = std.ArrayListUnmanaged(u64).empty;7    errdefer starts.deinit(allocator);8    for (object.symbols) |symbol| {9        if (symbol.section_index != section_index) continue;10        if (!symbol.isGlobalDefinition()) continue;11        try starts.append(allocator, symbol.value);12    }13    if (starts.items.len == 0) return &.{};14    std.mem.sort(u64, starts.items, {}, std.sort.asc(u64));15    return try starts.toOwnedSlice(allocator);16}

1pub fn shouldIndex(object: ObjectFile) bool {2    var section_count: usize = 0;3    for (object.sections, 0..) |section, section_index| {4        if (!mergeStringSectionWithoutRelocations(object, section, section_index)) continue;5        section_count += 1;6        if (section_count > 1) return true;7    }8    return false;9}

1const fixed_module = @import("fixed.zig");2const lookup = @import("lookup.zig");3const section = @import("section.zig");4const start = @import("start.zig");5const string_module = @import("string.zig");67pub const Piece = lookup.Piece;8pub const Fixed = fixed_module.Fixed;9pub const StartIndex = start.Index;10pub const String = string_module.String;11pub const address = lookup.address;12pub const collectStarts = start.collect;13pub const contribution = lookup.contribution;14pub const ensure = section.ensure;15pub const fixed = section.fixed;16pub const shouldIndexStarts = start.shouldIndex;17pub const piece = lookup.piece;18pub const string = section.string;

1pub const merge = @import("merge/root.zig");