lib/tldr/src/formats/elf/symbol.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../root.zig");
3 const format = @import("format.zig");
4 const layout = @import("layout/root.zig");
5 const parser = @import("parser.zig");
6 const sections = @import("sections.zig");
7
8 const Allocator = std.mem.Allocator;
9 const model = root.model;
10 const parallel = root.parallel;
11 const ObjectFile = parser.ObjectFile;
12 const Symbol = format.Symbol;
13 const SymbolRef = layout.SymbolRef;
14 const GlobalSymbol = layout.GlobalSymbol;
15 const symbolSectionDiscarded = sections.symbolSectionDiscarded;
16
17 pub const parallel_global_symbol_threshold = 32768;
18 const global_symbols_per_worker = 8192;
19
20 pub 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_jobs
31 else
32 total_symbols / global_symbols_per_worker;
33 const workers = if (total_symbols >= parallel_global_symbol_threshold)
34 parallel.chooseWorkers(total_symbols, requested_workers)
35 else
36 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 }
54
55 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);
64
65 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 }
72
73 fn 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 }
90
91 const GlobalSymbolRefCountContext = struct {
92 objects: []const ObjectFile,
93 offsets: []usize,
94 };
95
96 const GlobalSymbolRefFillContext = struct {
97 objects: []const ObjectFile,
98 offsets: []const usize,
99 refs: []SymbolRef,
100 };
101
102 fn 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);
111
112 var count_context = GlobalSymbolRefCountContext{
113 .objects = objects,
114 .offsets = offsets,
115 };
116 parallel.forItems(objects.len, workers, &count_context, countGlobalSymbolRefsForObject);
117
118 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;
125
126 _ = std.math.cast(u32, total) orelse return error.InvalidObject;
127 try refs.resize(allocator, total);
128
129 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 }
136
137 fn 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 }
147
148 fn 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 }
162
163 fn objectSymbolTotal(objects: []const ObjectFile) usize {
164 var total: usize = 0;
165 for (objects) |object| total += object.symbols.len;
166 return total;
167 }
168
169 pub fn globalSymbolCanBeAdded(object: ObjectFile, symbol: Symbol) bool {
170 if (!symbol.isGlobalDefinition()) return false;
171 if (symbolSectionDiscarded(object, symbol)) return false;
172 return true;
173 }
174
175 pub 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 }
187
188 pub 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 }
197
198 fn 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 }
227
228 fn 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 }
237
238 const GlobalSymbolMerge = union(enum) {
239 keep,
240 replace: GlobalSymbol,
241 };
242
243 fn mergeGlobalSymbols(
244 objects: []const ObjectFile,
245 existing: GlobalSymbol,
246 candidate: GlobalSymbol,
247 ) model.Error!GlobalSymbolMerge {
248 if (existing.ref.eql(candidate.ref)) return .keep;
249
250 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);
254
255 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 }
273
274 const weak_definition_rank: u8 = 0;
275 const common_definition_rank: u8 = 1;
276 const strong_definition_rank: u8 = 2;
277
278 fn 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 }
283
284 fn 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 }
293
294 fn 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 }
299
300 fn 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 }
304
305 test "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 };
314
315 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 }
326
327 test "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 };
339
340 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 }
356
357 test "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 };
366
367 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 }
378
379 test "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 };
388
389 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 }
395
396 test "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 };
405
406 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 }
417
418 fn expectKept(merge: GlobalSymbolMerge) !void {
419 switch (merge) {
420 .keep => {},
421 .replace => return error.ExpectedKeep,
422 }
423 }
424
425 fn 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 }
431
432 fn 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 }
443
444 fn 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 }