lib/tldr/src/formats/elf/payload.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const pretty = @import("pretty");
3 const root = @import("../../root.zig");
4 const format = @import("format.zig");
5 const layout = @import("layout/root.zig");
6 const parser = @import("parser.zig");
7
8 const model = root.model;
9 const parallel = root.parallel;
10 const ObjectFile = parser.ObjectFile;
11 const SectionHeader = format.SectionHeader;
12 const sectionBytes = format.sectionBytes;
13 const copyInto = format.copyInto;
14 const writeU32 = format.writeU32;
15 const OutputSection = layout.OutputSection;
16 const SectionContribution = layout.SectionContribution;
17 const ObjectLayout = layout.ObjectLayout;
18 const EhFrameSectionLayout = layout.EhFrameSectionLayout;
19 const contributionAt = layout.contributionAt;
20
21 const CopyFailure = struct {
22 found: bool = false,
23 object_index: usize = 0,
24 section_index: usize = 0,
25 err: model.Error = error.InvalidObject,
26
27 fn isFound(failure: CopyFailure) bool {
28 return failure.found;
29 }
30
31 fn before(left: CopyFailure, right: CopyFailure) bool {
32 if (left.object_index != right.object_index) return left.object_index < right.object_index;
33 return left.section_index < right.section_index;
34 }
35 };
36
37 const CopyFailures = parallel.FailureSlots(CopyFailure);
38
39 const ParallelObjectCopyContext = struct {
40 image: []u8,
41 objects: []const ObjectFile,
42 layouts: []const ObjectLayout,
43 output_sections: []const OutputSection,
44 failures: *CopyFailures,
45 };
46
47 const SectionCopyTask = struct {
48 object_index: usize,
49 section_index: usize,
50 };
51
52 const ParallelSectionCopyContext = struct {
53 image: []u8,
54 objects: []const ObjectFile,
55 layouts: []const ObjectLayout,
56 output_sections: []const OutputSection,
57 tasks: []const SectionCopyTask,
58 failures: *CopyFailures,
59 };
60
61 const CopyRun = struct {
62 source_start: usize = 0,
63 dest_start: usize = 0,
64 len: usize = 0,
65
66 fn append(self: *CopyRun, image: []u8, object_bytes: []const u8, source_start: usize, dest_start: usize, len: usize) void {
67 if (len == 0) return;
68 if (self.len != 0 and source_start == self.source_start + self.len and dest_start == self.dest_start + self.len) {
69 self.len += len;
70 return;
71 }
72 self.flush(image, object_bytes);
73 self.* = .{
74 .source_start = source_start,
75 .dest_start = dest_start,
76 .len = len,
77 };
78 }
79
80 fn flush(self: *CopyRun, image: []u8, object_bytes: []const u8) void {
81 if (self.len == 0) return;
82 copyBytes(image, self.dest_start, object_bytes[self.source_start..][0..self.len]);
83 self.len = 0;
84 }
85 };
86
87 const copy_run_section_threshold = 128;
88 const parallel_section_copy_threshold = 8 * 1024 * 1024;
89 const parallel_copy_threshold = 8 * 1024 * 1024;
90 pub const parallel_object_copy_threshold = 16 * 1024 * 1024;
91 const parallel_copy_bytes_per_worker = 8 * 1024 * 1024;
92 const parallel_section_copy_bytes_per_worker = 4 * 1024 * 1024;
93
94 const ParallelCopy = struct {
95 dest: []u8,
96 source: []const u8,
97 };
98
99 fn copyChunk(copy: *ParallelCopy, worker: usize, start: usize, end: usize) void {
100 _ = worker;
101 @memcpy(copy.dest[start..end], copy.source[start..end]);
102 }
103
104 fn copyBytes(image: []u8, start: usize, bytes: []const u8) void {
105 if (bytes.len == 0) return;
106 const dest = image[start..][0..bytes.len];
107 if (bytes.len >= parallel_copy_threshold) {
108 var copy = ParallelCopy{
109 .dest = dest,
110 .source = bytes,
111 };
112 parallel.forChunks(bytes.len, bytes.len / parallel_copy_bytes_per_worker, ©, copyChunk);
113 return;
114 }
115 @memcpy(dest, bytes);
116 }
117
118 test "parallel payload copy matches direct copy" {
119 const allocator = std.testing.allocator;
120 const source = try allocator.alloc(u8, parallel_copy_threshold + 4096);
121 defer allocator.free(source);
122 for (source, 0..) |*byte, index| byte.* = @truncate(index *% 251);
123
124 const padding = 32;
125 const parallel_image = try allocator.alloc(u8, source.len + padding * 2);
126 defer allocator.free(parallel_image);
127 const serial_image = try allocator.alloc(u8, source.len + padding * 2);
128 defer allocator.free(serial_image);
129 @memset(parallel_image, 0xaa);
130 @memset(serial_image, 0xaa);
131
132 copyBytes(parallel_image, padding, source);
133 @memcpy(serial_image[padding..][0..source.len], source);
134
135 try std.testing.expectEqualSlices(u8, serial_image, parallel_image);
136 }
137
138 pub fn verifyMergePieceBytes(
139 image: []const u8,
140 objects: []const ObjectFile,
141 layouts: []const ObjectLayout,
142 output_sections: []const OutputSection,
143 ) void {
144 var clobbered: usize = 0;
145 for (objects, 0..) |object, object_index| {
146 const object_layout = layouts[object_index];
147 for (object.sections, 0..) |section_header, section_index| {
148 const merge_section = layout.mergeSection(object_layout, section_index) orelse continue;
149 const bytes = sectionBytes(object.bytes, section_header) catch continue;
150 for (merge_section.pieces) |piece| {
151 const output = output_sections[piece.contribution.outputIndex()];
152 const start: usize = @intCast(output.file_offset + piece.contribution.offset + piece.output_intra_offset);
153 const piece_offset: usize = @intCast(piece.input_offset);
154 const piece_size: usize = @intCast(piece.size);
155 if (start > image.len or piece_size > image.len - start) {
156 pretty.diagnostic.writeStderrText(
157 "PIECE OOB {s} sec={d} off={d}\n",
158 .{ object.name, section_index, piece.input_offset },
159 );
160 continue;
161 }
162 if (!std.mem.eql(u8, image[start..][0..piece_size], bytes[piece_offset..][0..piece_size])) {
163 clobbered += 1;
164 if (clobbered <= 8) {
165 pretty.diagnostic.writeStderrText(
166 "PIECE CLOBBERED {s} sec={d} in_off={d} size={d} at=0x{x}\n",
167 .{ object.name, section_index, piece.input_offset, piece.size, start },
168 );
169 }
170 }
171 }
172 }
173 }
174 if (clobbered != 0) {
175 pretty.diagnostic.writeStderrText("PIECE CLOBBERED total={d}\n", .{clobbered});
176 }
177 }
178
179 pub fn wantsBatchedObjectCopy(objects: []const ObjectFile) bool {
180 return objects.len == 1 and objects[0].sections.len >= copy_run_section_threshold;
181 }
182
183 pub fn copyAllocSections(
184 scratch: std.mem.Allocator,
185 image: []u8,
186 objects: []const ObjectFile,
187 layouts: []const ObjectLayout,
188 output_sections: []const OutputSection,
189 options: model.LinkOptions,
190 ) model.Error!void {
191 if (wantsBatchedObjectCopy(objects)) {
192 return copyObjectAllocSectionsBatched(image, objects[0], layouts[0], output_sections);
193 }
194
195 const load_bytes = outputFileLoadBytes(output_sections);
196 if (load_bytes < parallel_object_copy_threshold) {
197 if (load_bytes >= parallel_section_copy_threshold) {
198 const requested_workers = if (options.max_link_jobs != 0)
199 options.max_link_jobs
200 else
201 load_bytes / parallel_section_copy_bytes_per_worker;
202 return copyAllocSectionsParallelBySection(scratch, image, objects, layouts, output_sections, requested_workers);
203 }
204 return copyAllocSectionsSerial(image, objects, layouts, output_sections);
205 }
206
207 const requested_workers = if (options.max_link_jobs != 0)
208 options.max_link_jobs
209 else
210 load_bytes / parallel_copy_bytes_per_worker;
211 const workers = parallel.chooseWorkers(objects.len, requested_workers);
212
213 if (workers > 1) return copyAllocSectionsParallel(scratch, image, objects, layouts, output_sections, workers);
214
215 try copyAllocSectionsSerial(image, objects, layouts, output_sections);
216 }
217
218 fn copyAllocSectionsParallelBySection(
219 scratch: std.mem.Allocator,
220 image: []u8,
221 objects: []const ObjectFile,
222 layouts: []const ObjectLayout,
223 output_sections: []const OutputSection,
224 requested_workers: usize,
225 ) model.Error!void {
226 if (requested_workers <= 1) return copyAllocSectionsSerial(image, objects, layouts, output_sections);
227
228 var tasks = std.ArrayListUnmanaged(SectionCopyTask).empty;
229 defer tasks.deinit(scratch);
230 for (objects, 0..) |object, object_index| {
231 try tasks.ensureUnusedCapacity(scratch, object.sections.len);
232 for (object.sections, 0..) |_, section_index| {
233 tasks.appendAssumeCapacity(.{
234 .object_index = object_index,
235 .section_index = section_index,
236 });
237 }
238 }
239 if (tasks.items.len == 0) return;
240 const workers = parallel.chooseWorkers(tasks.items.len, requested_workers);
241 if (workers <= 1) return copyAllocSectionsSerial(image, objects, layouts, output_sections);
242
243 var failures = try CopyFailures.init(scratch, workers, .{});
244 defer failures.deinit(scratch);
245
246 var context = ParallelSectionCopyContext{
247 .image = image,
248 .objects = objects,
249 .layouts = layouts,
250 .output_sections = output_sections,
251 .tasks = tasks.items,
252 .failures = &failures,
253 };
254 parallel.forItems(tasks.items.len, workers, &context, copySectionTask);
255 if (failures.earliest(CopyFailure.isFound, CopyFailure.before)) |failure| return failure.err;
256 }
257
258 fn copyAllocSectionsSerial(
259 image: []u8,
260 objects: []const ObjectFile,
261 layouts: []const ObjectLayout,
262 output_sections: []const OutputSection,
263 ) model.Error!void {
264 for (objects, 0..) |object, object_index| {
265 try copyObjectSections(image, object, layouts[object_index], output_sections);
266 }
267 }
268
269 fn copyAllocSectionsParallel(
270 scratch: std.mem.Allocator,
271 image: []u8,
272 objects: []const ObjectFile,
273 layouts: []const ObjectLayout,
274 output_sections: []const OutputSection,
275 workers: usize,
276 ) model.Error!void {
277 var failures = try CopyFailures.init(scratch, workers, .{});
278 defer failures.deinit(scratch);
279
280 var context = ParallelObjectCopyContext{
281 .image = image,
282 .objects = objects,
283 .layouts = layouts,
284 .output_sections = output_sections,
285 .failures = &failures,
286 };
287 parallel.forItems(objects.len, workers, &context, copyObjectTask);
288 if (failures.earliest(CopyFailure.isFound, CopyFailure.before)) |failure| return failure.err;
289 }
290
291 fn copyObjectTask(context: *ParallelObjectCopyContext, worker: usize, object_index: usize) void {
292 copyObjectSections(context.image, context.objects[object_index], context.layouts[object_index], context.output_sections) catch |err| {
293 const current = context.failures.items[worker];
294 const failure = CopyFailure{
295 .found = true,
296 .object_index = object_index,
297 .err = err,
298 };
299 if (!current.found or CopyFailure.before(failure, current)) {
300 context.failures.record(worker, failure);
301 }
302 };
303 }
304
305 fn copySectionTask(context: *ParallelSectionCopyContext, worker: usize, task_index: usize) void {
306 const task = context.tasks[task_index];
307 copySection(
308 context.image,
309 context.objects[task.object_index],
310 context.layouts[task.object_index],
311 context.output_sections,
312 task.section_index,
313 ) catch |err| {
314 const current = context.failures.items[worker];
315 const failure = CopyFailure{
316 .found = true,
317 .object_index = task.object_index,
318 .section_index = task.section_index,
319 .err = err,
320 };
321 if (!current.found or CopyFailure.before(failure, current)) {
322 context.failures.record(worker, failure);
323 }
324 };
325 }
326
327 pub fn copyObjectSections(
328 image: []u8,
329 object: ObjectFile,
330 object_layout: ObjectLayout,
331 output_sections: []const OutputSection,
332 ) model.Error!void {
333 if (object.sections.len >= copy_run_section_threshold) {
334 return copyObjectAllocSectionsBatched(image, object, object_layout, output_sections);
335 }
336
337 for (object.sections, 0..) |_, section_index| {
338 try copySection(image, object, object_layout, output_sections, section_index);
339 }
340 }
341
342 fn copySection(
343 image: []u8,
344 object: ObjectFile,
345 object_layout: ObjectLayout,
346 output_sections: []const OutputSection,
347 section_index: usize,
348 ) model.Error!void {
349 const section_header = object.sections[section_index];
350 if (layout.ehFrameSection(object_layout, section_index)) |eh_frame_section| {
351 const contribution = contributionAt(object_layout.sections, section_index) orelse return;
352 if (section_header.section_type == std.elf.SHT_NOBITS) return;
353 const output = output_sections[contribution.outputIndex()];
354 try copyEhFrameSection(image, object, section_header, output, contribution.*, eh_frame_section);
355 return;
356 }
357
358 if (layout.mergeSection(object_layout, section_index)) |merge_section| {
359 const bytes = try sectionBytes(object.bytes, section_header);
360 for (merge_section.pieces) |piece| {
361 const output = output_sections[piece.contribution.outputIndex()];
362 const start: usize = @intCast(output.file_offset + piece.contribution.offset + piece.output_intra_offset);
363 const piece_offset: usize = @intCast(piece.input_offset);
364 const piece_size: usize = @intCast(piece.size);
365 if (@import("builtin").mode == .debug) {
366 if (piece.contribution.offset == 0 and piece.size != 0 and piece.contribution.size == 0) {
367 pretty.diagnostic.writeStderrText(
368 "CLOBBER unassigned piece: {s} sec={d} in_off={d} size={d}\n",
369 .{ object.name, section_index, piece.input_offset, piece.size },
370 );
371 }
372 }
373 copyInto(image, start, bytes[piece_offset..][0..piece_size]);
374 }
375 return;
376 }
377
378 const contribution = contributionAt(object_layout.sections, section_index) orelse return;
379 if (section_header.section_type == std.elf.SHT_NOBITS) return;
380
381 const output = output_sections[contribution.outputIndex()];
382 const start: usize = @intCast(output.file_offset + contribution.offset);
383 copyBytes(image, start, try sectionBytes(object.bytes, section_header));
384 }
385
386 fn copyObjectAllocSectionsBatched(
387 image: []u8,
388 object: ObjectFile,
389 object_layout: ObjectLayout,
390 output_sections: []const OutputSection,
391 ) model.Error!void {
392 var run = CopyRun{};
393 for (object.sections, 0..) |section_header, section_index| {
394 if (layout.ehFrameSection(object_layout, section_index)) |eh_frame_section| {
395 run.flush(image, object.bytes);
396 const contribution = contributionAt(object_layout.sections, section_index) orelse continue;
397 if (section_header.section_type == std.elf.SHT_NOBITS) continue;
398 const output = output_sections[contribution.outputIndex()];
399 try copyEhFrameSection(image, object, section_header, output, contribution.*, eh_frame_section);
400 continue;
401 }
402
403 if (layout.mergeSection(object_layout, section_index)) |merge_section| {
404 run.flush(image, object.bytes);
405 const bytes = try sectionBytes(object.bytes, section_header);
406 for (merge_section.pieces) |piece| {
407 const output = output_sections[piece.contribution.outputIndex()];
408 const start: usize = @intCast(output.file_offset + piece.contribution.offset + piece.output_intra_offset);
409 const piece_offset: usize = @intCast(piece.input_offset);
410 const piece_size: usize = @intCast(piece.size);
411 copyInto(image, start, bytes[piece_offset..][0..piece_size]);
412 }
413 continue;
414 }
415
416 const contribution = contributionAt(object_layout.sections, section_index) orelse continue;
417 if (section_header.section_type == std.elf.SHT_NOBITS) continue;
418
419 const output = output_sections[contribution.outputIndex()];
420 const start: usize = @intCast(output.file_offset + contribution.offset);
421 const bytes = try sectionBytes(object.bytes, section_header);
422 run.append(image, object.bytes, @intCast(section_header.offset), start, bytes.len);
423 }
424 run.flush(image, object.bytes);
425 }
426
427 fn copyEhFrameSection(
428 image: []u8,
429 object: ObjectFile,
430 section_header: SectionHeader,
431 output: OutputSection,
432 contribution: SectionContribution,
433 eh_frame_section: EhFrameSectionLayout,
434 ) model.Error!void {
435 const bytes = try sectionBytes(object.bytes, section_header);
436 for (eh_frame_section.pieces) |piece| {
437 const input_offset: usize = @intCast(piece.input_offset);
438 const size: usize = @intCast(piece.size);
439 const output_offset: usize = @intCast(output.file_offset + contribution.offset + piece.output_offset);
440 copyInto(image, output_offset, bytes[input_offset..][0..size]);
441 if (piece.patch_cie_pointer) writeU32(image, output_offset + 4, piece.cie_pointer);
442 }
443 }
444
445 fn outputFileLoadBytes(output_sections: []const OutputSection) usize {
446 var total: usize = 0;
447 for (output_sections) |section| {
448 const size = std.math.cast(usize, section.fileLoadSize()) orelse return std.math.maxInt(usize);
449 total = std.math.add(usize, total, size) catch return std.math.maxInt(usize);
450 }
451 return total;
452 }