lib/tldr/src/formats/elf/relocation/application.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../../root.zig");
3 const elf = @import("../root.zig");
4 const checked = @import("value.zig");
5 const kind = @import("kind.zig");
6 const relax = @import("relax.zig");
7 const relocation_target = @import("target.zig");
8
9 const Allocator = std.mem.Allocator;
10 const model = root.model;
11 const trace = root.trace;
12 const parallel = root.parallel;
13 const diagnostic = elf.diagnostic;
14 const elf_object = elf.object;
15 const format = elf.format;
16 const layout = elf.layout;
17 const program = elf.program;
18 const parser = elf.parser;
19 const output_section = elf.output_section;
20 const section_state = elf.section_state;
21 const got_table = elf.got_table;
22 const parallel_relocation_threshold = format.parallel_relocation_threshold;
23 const relocations_per_worker = format.relocations_per_worker;
24 const OutputSectionKind = output_section.OutputSectionKind;
25 const OutputSection = layout.OutputSection;
26 const ObjectLayout = layout.ObjectLayout;
27 const contributionAt = layout.contributionAt;
28 const ehFrameSectionLayout = layout.ehFrameSection;
29 const GlobalSymbol = layout.GlobalSymbol;
30 const GotLayout = layout.GotLayout;
31 const ObjectFile = parser.ObjectFile;
32 const sectionNameOrEmpty = parser.sectionNameOrEmpty;
33 const Rela = format.Rela;
34 const writeU16 = format.writeU16;
35 const writeU32 = format.writeU32;
36 const writeU64 = format.writeU64;
37 const sectionDiscarded = section_state.sectionDiscarded;
38 const foldedSection = section_state.foldedSection;
39 const canonicalGotSymbolRef = got_table.canonicalSymbolRef;
40 const tlsMemorySize = program.tlsMemorySize;
41 const SymbolAddressCache = elf.addressing.Cache;
42 const SymbolCacheAccess = elf.addressing.Access;
43 const relocationTargetAddress = elf.addressing.relocationTarget;
44 const symbolIsUnresolvedWeak = elf.addressing.symbolIsUnresolvedWeak;
45
46 const absolute64_run_relocation_limit = 4096;
47 const absolute64_run_relocations_per_worker = relocations_per_worker * 8;
48 const debug_absolute_run_min_relocations = 4;
49
50 const 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 };
62
63 const JobRange = struct {
64 start: usize = 0,
65 end: usize = 0,
66 };
67
68 const JobList = struct {
69 jobs: std.ArrayListUnmanaged(RelocationJob) = .empty,
70 object_ranges: []JobRange = &.{},
71 total_relocations: usize = 0,
72 deferred_jobs: usize = 0,
73
74 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 };
79
80 fn 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.relocations
113 else
114 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;
118
119 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 }
126
127 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 }
147
148 const RelocationTask = struct {
149 job_index: usize,
150 start: usize,
151 end: usize,
152 global_offset: usize,
153 };
154
155 const 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 };
163
164 const RelocationFailures = parallel.FailureSlots(RelocationFailure);
165
166 const 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 };
179
180 const RelocationPlace = struct {
181 address: u64,
182 offset: u64,
183 };
184
185 fn 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 or
193 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 }
199
200 fn 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;
221
222 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 }
368
369 fn 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 }
372
373 fn 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 }
386
387 fn 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 }
431
432 fn 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 }
440
441 fn 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 }
454
455 fn 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;
476
477 const symbol_index: usize = @intCast(first.symbolIndex());
478 if (try debugAbsoluteRunTargetDependsOnAddend(objects, layouts, object_index, symbol_index)) return null;
479
480 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;
487
488 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);
491
492 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;
496
497 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 }
511
512 fn 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 }
550
551 fn relocationFailureFound(failure: RelocationFailure) bool {
552 return failure.found;
553 }
554
555 fn relocationFailureBefore(lhs: RelocationFailure, rhs: RelocationFailure) bool {
556 return lhs.global_index < rhs.global_index;
557 }
558
559 fn 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 }
577
578 fn 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];
588
589 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 }
611
612 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 }
674
675 fn 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 }
680
681 fn 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 }
731
732 pub 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;
746
747 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 }
753
754 fn 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_jobs
762 else if (all_absolute64)
763 @max(1, list.total_relocations / absolute64_run_relocations_per_worker)
764 else
765 list.total_relocations / relocations_per_worker;
766 return if (list.total_relocations >= parallel_relocation_threshold)
767 parallel.chooseWorkers(list.total_relocations, requested_workers)
768 else
769 1;
770 }
771
772 fn 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;
805
806 var failures = try RelocationFailures.init(scratch, workers, .{});
807 defer failures.deinit(scratch);
808
809 var worker_arenas = try parallel.WorkerArenaPool.init(scratch, workers);
810 defer worker_arenas.deinit();
811
812 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 }
818
819 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);
833
834 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 }
839
840 const CopyFailure = struct {
841 found: bool = false,
842 object_index: usize = 0,
843 err: model.Error = error.InvalidObject,
844 };
845
846 const CopyFailures = parallel.FailureSlots(CopyFailure);
847
848 const MaterializeContext = struct {
849 relocation: ParallelRelocationContext,
850 copy_failures: *CopyFailures,
851 };
852
853 const MaterializeObjectContext = struct {
854 shared: MaterializeContext,
855 object_ranges: []const JobRange,
856 };
857
858 fn 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 }
887
888 fn copyFailureFound(failure: CopyFailure) bool {
889 return failure.found;
890 }
891
892 fn copyFailureBefore(left: CopyFailure, right: CopyFailure) bool {
893 return left.object_index < right.object_index;
894 }
895
896 pub 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 }
911
912 var list = try buildJobs(scratch, objects, layouts, output_sections, options, true);
913 defer list.deinit(scratch);
914
915 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 }
920
921 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);
925
926 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 }
934
935 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 = ©_failures,
951 },
952 .object_ranges = list.object_ranges,
953 };
954 parallel.forItems(objects.len, workers, &context, materializeObjectTask);
955
956 if (copy_failures.earliest(copyFailureFound, copyFailureBefore)) |failure| {
957 return failure.err;
958 }
959
960 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 }
963
964 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 }
969
970 fn 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_jobs
980 else
981 @max(relocation_request, copy_request);
982 const busy = list.total_relocations >= parallel_relocation_threshold or
983 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 else
987 1;
988 }
989
990 const parallel_materialize_threshold = 8 * 1024 * 1024;
991 const parallel_materialize_bytes_per_worker = 4 * 1024 * 1024;
992
993 test "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;
997
998 const text = [_]u8{0xc3};
999 const payload = [_]u8{ 1, 2, 3, 4, 5, 6, 7, 8 };
1000
1001 const data = try allocator.alloc(u8, record_count * record_size);
1002 defer allocator.free(data);
1003 @memset(data, 0);
1004
1005 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);
1009
1010 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 };
1016
1017 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 };
1031
1032 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 };
1045
1046 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 );
1053
1054 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 }
1089
1090 const object = try elf_object.build(allocator, .{
1091 .sections = §ions,
1092 .symbols = &symbols,
1093 .relocations = relocations.items,
1094 });
1095 defer allocator.free(object);
1096
1097 const inputs = [_]model.Input{.{ .name = "reloc.o", .bytes = object }};
1098
1099 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);
1103
1104 try std.testing.expectEqualSlices(u8, serial.bytes, concurrent.bytes);
1105 }
1106
1107 fn firstEffectiveRelocation(relocations: []const Rela) ?Rela {
1108 for (relocations) |relocation| {
1109 if (!kind.isNone(relocation)) return relocation;
1110 }
1111 return null;
1112 }