tiny.tldr.formats.elf.symbol_table

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

1const std = @import("std");2const root = @import("../../root.zig");3const format = @import("format.zig");4const layout = @import("layout/root.zig");5const parser = @import("parser.zig");6const sections = @import("sections.zig");78const Allocator = std.mem.Allocator;9const model = root.model;10const parallel = root.parallel;11const ObjectFile = parser.ObjectFile;12const Symbol = format.Symbol;13const SymbolRef = layout.SymbolRef;14const GlobalSymbol = layout.GlobalSymbol;15const symbolSectionDiscarded = sections.symbolSectionDiscarded;1617pub const parallel_global_symbol_threshold = 32768;18const global_symbols_per_worker = 8192;1920pub fn collectGlobalSymbols(21    allocator: Allocator,22    objects: []const ObjectFile,23    globals: *std.StringHashMapUnmanaged(GlobalSymbol),24    global_symbol_refs: ?*std.ArrayListUnmanaged(SymbolRef),25    max_link_jobs: usize,26) model.Error!void {27    if (global_symbol_refs) |refs| {28        const total_symbols = objectSymbolTotal(objects);29        const requested_workers = if (max_link_jobs != 0)30            max_link_jobs31        else32            total_symbols / global_symbols_per_worker;33        const workers = if (total_symbols >= parallel_global_symbol_threshold)34            parallel.chooseWorkers(total_symbols, requested_workers)35        else36            1;37        if (workers <= 1) {38            try collectGlobalSymbolRefsSerial(allocator, objects, refs);39        } else {40            try collectGlobalSymbolRefsParallel(allocator, objects, refs, workers);41        }42        const capacity = std.math.cast(u32, refs.items.len) orelse return error.InvalidObject;43        try globals.ensureTotalCapacity(allocator, capacity);44        const active_refs = try allocator.alloc(bool, refs.items.len);45        defer allocator.free(active_refs);46        @memset(active_refs, false);47        for (refs.items, 0..) |ref, ref_index| {48            const ref_index_u32 = std.math.cast(u32, ref_index) orelse return error.InvalidObject;49            try addGlobalSymbolDefinitionTracked(allocator, objects, globals, ref.object_index, ref.symbol_index, ref_index_u32, active_refs);50        }51        compactGlobalSymbolRefs(refs, active_refs);52        return;53    }5455    var definition_count: usize = 0;56    for (objects) |object| {57        for (object.symbols) |symbol| {58            if (!globalSymbolCanBeAdded(object, symbol)) continue;59            definition_count += 1;60        }61    }62    const capacity = std.math.cast(u32, definition_count) orelse return error.InvalidObject;63    try globals.ensureTotalCapacity(allocator, capacity);6465    for (objects, 0..) |object, object_index| {66        for (object.symbols, 0..) |symbol, symbol_index| {67            if (!globalSymbolCanBeAdded(object, symbol)) continue;68            try addGlobalSymbolDefinition(allocator, objects, globals, object_index, symbol_index);69        }70    }71}7273fn collectGlobalSymbolRefsSerial(74    allocator: Allocator,75    objects: []const ObjectFile,76    refs: *std.ArrayListUnmanaged(SymbolRef),77) model.Error!void {78    refs.clearRetainingCapacity();79    try refs.ensureTotalCapacity(allocator, objects.len);80    for (objects, 0..) |object, object_index| {81        for (object.symbols, 0..) |symbol, symbol_index| {82            if (!globalSymbolCanBeAdded(object, symbol)) continue;83            try refs.append(allocator, .{84                .object_index = object_index,85                .symbol_index = symbol_index,86            });87        }88    }89}9091const GlobalSymbolRefCountContext = struct {92    objects: []const ObjectFile,93    offsets: []usize,94};9596const GlobalSymbolRefFillContext = struct {97    objects: []const ObjectFile,98    offsets: []const usize,99    refs: []SymbolRef,100};101102fn collectGlobalSymbolRefsParallel(103    allocator: Allocator,104    objects: []const ObjectFile,105    refs: *std.ArrayListUnmanaged(SymbolRef),106    workers: usize,107) model.Error!void {108    refs.clearRetainingCapacity();109    const offsets = try allocator.alloc(usize, objects.len + 1);110    defer allocator.free(offsets);111112    var count_context = GlobalSymbolRefCountContext{113        .objects = objects,114        .offsets = offsets,115    };116    parallel.forItems(objects.len, workers, &count_context, countGlobalSymbolRefsForObject);117118    var total: usize = 0;119    for (offsets[0..objects.len]) |*slot| {120        const count = slot.*;121        slot.* = total;122        total += count;123    }124    offsets[objects.len] = total;125126    _ = std.math.cast(u32, total) orelse return error.InvalidObject;127    try refs.resize(allocator, total);128129    var fill_context = GlobalSymbolRefFillContext{130        .objects = objects,131        .offsets = offsets,132        .refs = refs.items,133    };134    parallel.forItems(objects.len, workers, &fill_context, fillGlobalSymbolRefsForObject);135}136137fn countGlobalSymbolRefsForObject(context: *GlobalSymbolRefCountContext, worker: usize, object_index: usize) void {138    _ = worker;139    const object = context.objects[object_index];140    var count: usize = 0;141    for (object.symbols) |symbol| {142        if (!globalSymbolCanBeAdded(object, symbol)) continue;143        count += 1;144    }145    context.offsets[object_index] = count;146}147148fn fillGlobalSymbolRefsForObject(context: *GlobalSymbolRefFillContext, worker: usize, object_index: usize) void {149    _ = worker;150    const object = context.objects[object_index];151    var write_index = context.offsets[object_index];152    for (object.symbols, 0..) |symbol, symbol_index| {153        if (!globalSymbolCanBeAdded(object, symbol)) continue;154        context.refs[write_index] = .{155            .object_index = object_index,156            .symbol_index = symbol_index,157        };158        write_index += 1;159    }160    std.debug.assert(write_index == context.offsets[object_index + 1]);161}162163fn objectSymbolTotal(objects: []const ObjectFile) usize {164    var total: usize = 0;165    for (objects) |object| total += object.symbols.len;166    return total;167}168169pub fn globalSymbolCanBeAdded(object: ObjectFile, symbol: Symbol) bool {170    if (!symbol.isGlobalDefinition()) return false;171    if (symbolSectionDiscarded(object, symbol)) return false;172    return true;173}174175pub fn addGlobalSymbol(176    allocator: Allocator,177    objects: []const ObjectFile,178    globals: *std.StringHashMapUnmanaged(GlobalSymbol),179    object_index: usize,180    symbol_index: usize,181) model.Error!bool {182    const elf_symbol = objects[object_index].symbols[symbol_index];183    if (!globalSymbolCanBeAdded(objects[object_index], elf_symbol)) return false;184    try addGlobalSymbolDefinition(allocator, objects, globals, object_index, symbol_index);185    return true;186}187188pub fn addGlobalSymbolDefinition(189    allocator: Allocator,190    objects: []const ObjectFile,191    globals: *std.StringHashMapUnmanaged(GlobalSymbol),192    object_index: usize,193    symbol_index: usize,194) model.Error!void {195    try addGlobalSymbolDefinitionTracked(allocator, objects, globals, object_index, symbol_index, 0, null);196}197198fn addGlobalSymbolDefinitionTracked(199    allocator: Allocator,200    objects: []const ObjectFile,201    globals: *std.StringHashMapUnmanaged(GlobalSymbol),202    object_index: usize,203    symbol_index: usize,204    ref_index: u32,205    active_refs: ?[]bool,206) model.Error!void {207    const ref = SymbolRef{ .object_index = object_index, .symbol_index = symbol_index };208    const elf_symbol = objects[ref.object_index].symbols[ref.symbol_index];209    const gop = try globals.getOrPut(allocator, elf_symbol.name);210    const candidate = globalSymbolFromRef(objects, ref, ref_index);211    if (!gop.found_existing) {212        gop.value_ptr.* = candidate;213        if (active_refs) |active| active[ref_index] = true;214        return;215    }216    switch (try mergeGlobalSymbols(objects, gop.value_ptr.*, candidate)) {217        .keep => {},218        .replace => |replacement| {219            if (active_refs) |active| {220                active[gop.value_ptr.ref_index] = false;221                active[replacement.ref_index] = true;222            }223            gop.value_ptr.* = replacement;224        },225    }226}227228fn compactGlobalSymbolRefs(refs: *std.ArrayListUnmanaged(SymbolRef), active_refs: []const bool) void {229    var write_index: usize = 0;230    for (refs.items, active_refs) |ref, active| {231        if (!active) continue;232        refs.items[write_index] = ref;233        write_index += 1;234    }235    refs.shrinkRetainingCapacity(write_index);236}237238const GlobalSymbolMerge = union(enum) {239    keep,240    replace: GlobalSymbol,241};242243fn mergeGlobalSymbols(244    objects: []const ObjectFile,245    existing: GlobalSymbol,246    candidate: GlobalSymbol,247) model.Error!GlobalSymbolMerge {248    if (existing.ref.eql(candidate.ref)) return .keep;249250    const existing_symbol = objects[existing.ref.object_index].symbols[existing.ref.symbol_index];251    const candidate_symbol = objects[candidate.ref.object_index].symbols[candidate.ref.symbol_index];252    const existing_rank = globalSymbolRank(existing);253    const candidate_rank = globalSymbolRank(candidate);254255    if (existing_rank != candidate_rank) {256        if (candidate_rank > existing_rank) return .{ .replace = candidate };257        return .keep;258    }259    if (existing.common and candidate.common) {260        if (prefersCommonSymbol(candidate_symbol, existing_symbol, candidate.ref, existing.ref)) return .{ .replace = candidate };261        return .keep;262    }263    if (existing_rank == strong_definition_rank) {264        if (existing_symbol.isGnuUnique() and candidate_symbol.isGnuUnique()) {265            if (symbolRefBefore(candidate.ref, existing.ref)) return .{ .replace = candidate };266            return .keep;267        }268        return error.DuplicateSymbol;269    }270    if (symbolRefBefore(candidate.ref, existing.ref)) return .{ .replace = candidate };271    return .keep;272}273274const weak_definition_rank: u8 = 0;275const common_definition_rank: u8 = 1;276const strong_definition_rank: u8 = 2;277278fn globalSymbolRank(global: GlobalSymbol) u8 {279    if (!global.weak and !global.common) return strong_definition_rank;280    if (!global.weak and global.common) return common_definition_rank;281    return weak_definition_rank;282}283284fn globalSymbolFromRef(objects: []const ObjectFile, ref: SymbolRef, ref_index: u32) GlobalSymbol {285    const symbol = objects[ref.object_index].symbols[ref.symbol_index];286    return .{287        .ref = ref,288        .ref_index = ref_index,289        .weak = symbol.binding() == std.elf.STB_WEAK,290        .common = symbol.isCommon(),291    };292}293294fn prefersCommonSymbol(candidate: Symbol, existing: Symbol, candidate_ref: SymbolRef, existing_ref: SymbolRef) bool {295    if (candidate.size != existing.size) return candidate.size > existing.size;296    if (candidate.value != existing.value) return candidate.value > existing.value;297    return symbolRefBefore(candidate_ref, existing_ref);298}299300fn symbolRefBefore(left: SymbolRef, right: SymbolRef) bool {301    if (left.object_index != right.object_index) return left.object_index < right.object_index;302    return left.symbol_index < right.symbol_index;303}304305test "ELF global symbol merge keeps earliest weak definition" {306    var first_symbols = [_]Symbol{testSymbol("shared", std.elf.STB_WEAK, 1, 0, 1)};307    var second_symbols = [_]Symbol{testSymbol("shared", std.elf.STB_WEAK, 1, 0, 1)};308    var objects = [_]ObjectFile{309        testObject(first_symbols[0..]),310        testObject(second_symbols[0..]),311    };312    const first_ref = SymbolRef{ .object_index = 0, .symbol_index = 0 };313    const second_ref = SymbolRef{ .object_index = 1, .symbol_index = 0 };314315    try expectReplacedRef(try mergeGlobalSymbols(316        objects[0..],317        globalSymbolFromRef(objects[0..], second_ref, 1),318        globalSymbolFromRef(objects[0..], first_ref, 0),319    ), first_ref);320    try expectKept(try mergeGlobalSymbols(321        objects[0..],322        globalSymbolFromRef(objects[0..], first_ref, 0),323        globalSymbolFromRef(objects[0..], second_ref, 1),324    ));325}326327test "ELF global symbol merge ranks common symbols by size value then reference" {328    var small_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_GLOBAL, std.elf.SHN_COMMON, 8, 8)};329    var large_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_GLOBAL, std.elf.SHN_COMMON, 4, 16)};330    var tie_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_GLOBAL, std.elf.SHN_COMMON, 8, 8)};331    var objects = [_]ObjectFile{332        testObject(small_symbols[0..]),333        testObject(large_symbols[0..]),334        testObject(tie_symbols[0..]),335    };336    const small_ref = SymbolRef{ .object_index = 0, .symbol_index = 0 };337    const large_ref = SymbolRef{ .object_index = 1, .symbol_index = 0 };338    const tie_ref = SymbolRef{ .object_index = 2, .symbol_index = 0 };339340    try expectReplacedRef(try mergeGlobalSymbols(341        objects[0..],342        globalSymbolFromRef(objects[0..], small_ref, 0),343        globalSymbolFromRef(objects[0..], large_ref, 1),344    ), large_ref);345    try expectKept(try mergeGlobalSymbols(346        objects[0..],347        globalSymbolFromRef(objects[0..], small_ref, 0),348        globalSymbolFromRef(objects[0..], tie_ref, 2),349    ));350    try expectReplacedRef(try mergeGlobalSymbols(351        objects[0..],352        globalSymbolFromRef(objects[0..], tie_ref, 2),353        globalSymbolFromRef(objects[0..], small_ref, 0),354    ), small_ref);355}356357test "ELF global symbol merge ranks strong common above weak definitions" {358    var weak_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_WEAK, 1, 0, 1)};359    var common_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_GLOBAL, std.elf.SHN_COMMON, 16, 32)};360    var objects = [_]ObjectFile{361        testObject(weak_symbols[0..]),362        testObject(common_symbols[0..]),363    };364    const weak_ref = SymbolRef{ .object_index = 0, .symbol_index = 0 };365    const common_ref = SymbolRef{ .object_index = 1, .symbol_index = 0 };366367    try expectReplacedRef(try mergeGlobalSymbols(368        objects[0..],369        globalSymbolFromRef(objects[0..], weak_ref, 0),370        globalSymbolFromRef(objects[0..], common_ref, 1),371    ), common_ref);372    try expectKept(try mergeGlobalSymbols(373        objects[0..],374        globalSymbolFromRef(objects[0..], common_ref, 1),375        globalSymbolFromRef(objects[0..], weak_ref, 0),376    ));377}378379test "ELF global symbol merge rejects ordinary strong duplicates" {380    var first_symbols = [_]Symbol{testSymbol("call", std.elf.STB_GLOBAL, 1, 0, 1)};381    var second_symbols = [_]Symbol{testSymbol("call", std.elf.STB_GLOBAL, 1, 0, 1)};382    var objects = [_]ObjectFile{383        testObject(first_symbols[0..]),384        testObject(second_symbols[0..]),385    };386    const first_ref = SymbolRef{ .object_index = 0, .symbol_index = 0 };387    const second_ref = SymbolRef{ .object_index = 1, .symbol_index = 0 };388389    try std.testing.expectError(error.DuplicateSymbol, mergeGlobalSymbols(390        objects[0..],391        globalSymbolFromRef(objects[0..], first_ref, 0),392        globalSymbolFromRef(objects[0..], second_ref, 1),393    ));394}395396test "ELF global symbol merge coalesces GNU unique definitions by earliest reference" {397    var first_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_GNU_UNIQUE, 1, 0, 1)};398    var second_symbols = [_]Symbol{testSymbol("slot", std.elf.STB_GNU_UNIQUE, 1, 0, 1)};399    var objects = [_]ObjectFile{400        testObject(first_symbols[0..]),401        testObject(second_symbols[0..]),402    };403    const first_ref = SymbolRef{ .object_index = 0, .symbol_index = 0 };404    const second_ref = SymbolRef{ .object_index = 1, .symbol_index = 0 };405406    try expectReplacedRef(try mergeGlobalSymbols(407        objects[0..],408        globalSymbolFromRef(objects[0..], second_ref, 1),409        globalSymbolFromRef(objects[0..], first_ref, 0),410    ), first_ref);411    try expectKept(try mergeGlobalSymbols(412        objects[0..],413        globalSymbolFromRef(objects[0..], first_ref, 0),414        globalSymbolFromRef(objects[0..], second_ref, 1),415    ));416}417418fn expectKept(merge: GlobalSymbolMerge) !void {419    switch (merge) {420        .keep => {},421        .replace => return error.ExpectedKeep,422    }423}424425fn expectReplacedRef(merge: GlobalSymbolMerge, ref: SymbolRef) !void {426    switch (merge) {427        .keep => return error.ExpectedReplace,428        .replace => |replacement| try std.testing.expect(replacement.ref.eql(ref)),429    }430}431432fn testSymbol(name: []const u8, binding: u8, section_index: u16, value: u64, size: u64) Symbol {433    return .{434        .name_offset = 0,435        .info = format.elfSymbolInfo(binding, std.elf.STT_OBJECT),436        .other = 0,437        .section_index = section_index,438        .value = value,439        .size = size,440        .name = name,441    };442}443444fn testObject(symbols: []Symbol) ObjectFile {445    return .{446        .name = "symbols.o",447        .bytes = &.{},448        .sections = &.{},449        .section_names = &.{},450        .section_name_ends = &.{},451        .symbols = symbols,452        .relocations = &.{},453        .relocations_owned = false,454        .has_common_symbols = false,455        .has_named_strong_undefined_symbols = false,456        .has_ifunc_definitions = false,457        .has_group_sections = false,458        .relocation_ranges = &.{},459    };460}