lib/tldr/src/formats/elf/archive/select.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const allocators = @import("alloc");
3 const root = @import("../../../root.zig");
4 const elf = @import("../root.zig");
5 const definition = @import("definition.zig");
6 const member_selection = @import("member.zig");
7 const object_selection = @import("object.zig");
8 const prefetch = @import("prefetch.zig");
9
10 const Allocator = std.mem.Allocator;
11 const archive_format = root.archive;
12 const model = root.model;
13 const parallel = root.parallel;
14 const trace = root.trace;
15 const ObjectFile = elf.parser.ObjectFile;
16 const ObjectParseOptions = elf.parser.ObjectParseOptions;
17 const ObjectSelectionSummary = elf.parser.ObjectSelectionSummary;
18 const parseObjectSelectionSummary = elf.parser.parseObjectSelectionSummary;
19 const parseObjectWithSelectionSummary = elf.parser.parseObjectWithSelectionSummary;
20 const parseObjectWithOptions = elf.parser.parseObjectWithOptions;
21
22 const selected_objects_per_worker = 4;
23
24 const Candidate = struct {
25 archive_name: []const u8,
26 archive_input_index: usize,
27 member: archive_format.Member,
28 object: ?ObjectFile = null,
29 summary: ?ObjectSelectionSummary = null,
30 summary_failure: ?model.Error = null,
31 extracted: bool = false,
32
33 fn deinitIfUnextracted(self: *Candidate, allocator: Allocator) void {
34 if (!self.extracted) {
35 if (self.object) |*object| object.deinit(allocator);
36 }
37 }
38
39 fn load(
40 self: *Candidate,
41 allocator: Allocator,
42 options: model.LinkOptions,
43 ) model.Error!*ObjectFile {
44 if (self.object) |*object| return object;
45 if (self.summary) |summary| {
46 self.object = parseObjectWithSelectionSummary(allocator, summary, .{
47 .strip_debug = options.strip_debug,
48 }) catch |err| switch (err) {
49 error.InvalidElfHeader => return archiveMemberHeaderFailure(self.*, err, options),
50 else => return err,
51 };
52 self.summary = null;
53 } else {
54 self.object = parseObjectWithOptions(allocator, .{
55 .name = self.member.name,
56 .bytes = self.member.bytes,
57 }, .{
58 .strip_debug = options.strip_debug,
59 }) catch |err| switch (err) {
60 error.InvalidElfHeader => return archiveMemberHeaderFailure(self.*, err, options),
61 else => return err,
62 };
63 }
64 if (self.object) |*object| object.input_index = self.archive_input_index;
65 if (self.object) |*object| return object;
66 unreachable;
67 }
68
69 fn loadSelectionSummary(
70 self: *Candidate,
71 selection: Allocator,
72 options: model.LinkOptions,
73 ) model.Error!*ObjectSelectionSummary {
74 if (self.summary) |*summary| return summary;
75 if (self.summary_failure) |failure| return mapSummaryFailure(self.*, failure, options);
76 self.summary = parseObjectSelectionSummary(selection, .{
77 .name = self.member.name,
78 .bytes = self.member.bytes,
79 }) catch |err| return mapSummaryFailure(self.*, err, options);
80 if (self.summary) |*summary| return summary;
81 unreachable;
82 }
83 };
84
85 fn mapSummaryFailure(
86 candidate: Candidate,
87 parse_err: model.Error,
88 options: model.LinkOptions,
89 ) model.Error {
90 return switch (parse_err) {
91 error.InvalidElfHeader => archiveMemberHeaderFailure(candidate, parse_err, options),
92 else => parse_err,
93 };
94 }
95
96 const ArchiveIdentity = struct {
97 address: usize,
98 len: usize,
99 };
100
101 fn archiveMemberHeaderFailure(
102 candidate: Candidate,
103 parse_err: model.Error,
104 options: model.LinkOptions,
105 ) model.Error {
106 const input_format = root.detectObjectFormat(candidate.member.bytes) catch |err| switch (err) {
107 error.UnsupportedFormat => return parse_err,
108 else => return err,
109 };
110 if (input_format == .elf) return parse_err;
111 if (options.diagnostics) |diagnostics| {
112 diagnostics.recordUnsupportedArchiveMemberFormat(
113 candidate.archive_name,
114 candidate.member.name,
115 input_format,
116 .elf,
117 );
118 }
119 return error.UnsupportedFormat;
120 }
121
122 pub const ExtractionState = struct {
123 candidates: std.ArrayListUnmanaged(Candidate) = .empty,
124 first_archive: ?ArchiveIdentity = null,
125 seen_archives: std.AutoHashMapUnmanaged(ArchiveIdentity, void) = .empty,
126 definitions: definition.Index = .{},
127 unresolved_names: usize = 0,
128 active_candidate_counts: std.ArrayListUnmanaged(usize) = .empty,
129 pending: definition.Queue = definition.Queue.initContext({}),
130 observed_objects: usize = 0,
131
132 pub fn deinit(self: *ExtractionState, allocator: Allocator) void {
133 for (self.candidates.items) |*candidate| candidate.deinitIfUnextracted(allocator);
134 self.candidates.deinit(allocator);
135 self.seen_archives.deinit(allocator);
136 definition.deinit(allocator, &self.definitions);
137 self.active_candidate_counts.deinit(allocator);
138 self.pending.deinit(allocator);
139 self.* = undefined;
140 }
141
142 pub fn observeArchive(
143 self: *ExtractionState,
144 allocator: Allocator,
145 input: model.Input,
146 ) Allocator.Error!bool {
147 const identity: ArchiveIdentity = .{
148 .address = @intFromPtr(input.bytes.ptr),
149 .len = input.bytes.len,
150 };
151 if (self.first_archive) |first_archive| {
152 if (sameArchiveIdentity(first_archive, identity)) return false;
153 } else {
154 self.first_archive = identity;
155 return true;
156 }
157 if (self.seen_archives.count() == 0) {
158 try self.seen_archives.ensureTotalCapacity(allocator, 4);
159 self.seen_archives.putAssumeCapacityNoClobber(self.first_archive.?, {});
160 }
161 const gop = try self.seen_archives.getOrPut(allocator, identity);
162 return !gop.found_existing;
163 }
164
165 pub fn hasCandidates(self: ExtractionState) bool {
166 return self.candidates.items.len != 0;
167 }
168
169 pub fn appendCandidate(
170 self: *ExtractionState,
171 allocator: Allocator,
172 candidate: Candidate,
173 ) Allocator.Error!usize {
174 const index = self.candidates.items.len;
175 try self.active_candidate_counts.append(allocator, 0);
176 errdefer _ = self.active_candidate_counts.pop();
177 try self.candidates.append(allocator, candidate);
178 return index;
179 }
180
181 pub fn addDefinition(
182 self: *ExtractionState,
183 allocator: Allocator,
184 symbol_name: []const u8,
185 candidate_index: usize,
186 ) model.Error!void {
187 try definition.add(
188 allocator,
189 &self.definitions,
190 symbol_name,
191 candidate_index,
192 self.active_candidate_counts.items,
193 &self.pending,
194 );
195 }
196
197 pub fn observeNewObjects(
198 self: *ExtractionState,
199 allocator: Allocator,
200 objects: []const ObjectFile,
201 ) model.Error!void {
202 if (self.observed_objects >= objects.len) return;
203 const recording_phase = trace.product(.archive_symbol_recording);
204 defer recording_phase.end();
205 while (self.observed_objects < objects.len) {
206 try object_selection.record(
207 allocator,
208 objects,
209 self.observed_objects,
210 &self.definitions,
211 &self.unresolved_names,
212 self.active_candidate_counts.items,
213 &self.pending,
214 );
215 self.observed_objects += 1;
216 }
217 }
218 };
219
220 fn sameArchiveIdentity(a: ArchiveIdentity, b: ArchiveIdentity) bool {
221 return a.address == b.address and a.len == b.len;
222 }
223
224 test "archive extraction state skips repeated archive byte identities" {
225 const allocator = std.testing.allocator;
226 const first = [_]u8{ 1, 2, 3 };
227 const second = [_]u8{ 1, 2, 4 };
228
229 var state: ExtractionState = .{};
230 defer state.deinit(allocator);
231
232 try std.testing.expect(try state.observeArchive(allocator, .{ .name = "lib.a", .bytes = &first }));
233 try std.testing.expect(!try state.observeArchive(allocator, .{ .name = "lib.a", .bytes = &first }));
234 try std.testing.expect(try state.observeArchive(allocator, .{ .name = "lib.a", .bytes = &second }));
235 try std.testing.expect(!try state.observeArchive(allocator, .{ .name = "lib.a", .bytes = &second }));
236 }
237
238 pub fn addCandidates(
239 allocator: Allocator,
240 selection: Allocator,
241 input: model.Input,
242 input_index: usize,
243 state: *ExtractionState,
244 options: model.LinkOptions,
245 prefetcher: *prefetch.Prefetcher,
246 ) model.Error!void {
247 if (!try state.observeArchive(allocator, input)) return;
248 const prefetched = take_prefetch: {
249 const table_phase = trace.product(.archive_table_parse);
250 defer table_phase.end();
251 break :take_prefetch try prefetcher.take(input_index);
252 };
253 const first_new_candidate = state.candidates.items.len;
254 try member_selection.addCandidates(allocator, selection, input, input_index, state, ObjectParseOptions{
255 .strip_debug = options.strip_debug,
256 }, prefetched);
257 prefetch.prepareSummaries(selection, state.candidates.items[first_new_candidate..], options);
258 }
259
260 pub fn extractCandidates(
261 allocator: Allocator,
262 selection: Allocator,
263 objects: *std.ArrayListUnmanaged(ObjectFile),
264 state: *ExtractionState,
265 options: model.LinkOptions,
266 ) model.Error!void {
267 if (state.pending.peek() == null) return;
268 if (options.max_link_jobs == 1) {
269 return extractCandidatesSerial(allocator, objects, state, options);
270 }
271
272 return extractCandidatesBatched(allocator, selection, objects, state, options);
273 }
274
275 fn extractCandidatesSerial(
276 allocator: Allocator,
277 objects: *std.ArrayListUnmanaged(ObjectFile),
278 state: *ExtractionState,
279 options: model.LinkOptions,
280 ) model.Error!void {
281 if (state.pending.peek() == null) return;
282
283 try objects.ensureUnusedCapacity(allocator, @min(state.candidates.items.len, state.unresolved_names));
284
285 while (state.pending.pop()) |index| {
286 if (index >= state.candidates.items.len) continue;
287 var candidate = &state.candidates.items[index];
288 if (candidate.extracted) continue;
289 if (state.active_candidate_counts.items[index] == 0) continue;
290 const object = load_member: {
291 const parse_phase = trace.product(.selected_member_parse);
292 defer parse_phase.end();
293 break :load_member try candidate.load(allocator, options);
294 };
295
296 const object_index = objects.items.len;
297 try objects.append(allocator, object.*);
298 candidate.object = null;
299 candidate.extracted = true;
300 {
301 const recording_phase = trace.product(.archive_symbol_recording);
302 defer recording_phase.end();
303 try object_selection.record(
304 allocator,
305 objects.items,
306 object_index,
307 &state.definitions,
308 &state.unresolved_names,
309 state.active_candidate_counts.items,
310 &state.pending,
311 );
312 }
313 state.observed_objects = object_index + 1;
314 }
315 }
316
317 fn extractCandidatesBatched(
318 allocator: Allocator,
319 selection: Allocator,
320 objects: *std.ArrayListUnmanaged(ObjectFile),
321 state: *ExtractionState,
322 options: model.LinkOptions,
323 ) model.Error!void {
324 var selected = std.ArrayListUnmanaged(usize).empty;
325 defer selected.deinit(allocator);
326
327 try selected.ensureUnusedCapacity(allocator, @min(state.candidates.items.len, state.unresolved_names));
328
329 while (state.pending.pop()) |index| {
330 if (index >= state.candidates.items.len) continue;
331 var candidate = &state.candidates.items[index];
332 if (candidate.extracted) continue;
333 if (state.active_candidate_counts.items[index] == 0) continue;
334 const summary = load_summary: {
335 const summary_phase = trace.product(.archive_summary_parse);
336 defer summary_phase.end();
337 break :load_summary try candidate.loadSelectionSummary(selection, options);
338 };
339
340 try selected.append(allocator, index);
341 candidate.extracted = true;
342 {
343 const recording_phase = trace.product(.archive_symbol_recording);
344 defer recording_phase.end();
345 try object_selection.recordSymbols(
346 allocator,
347 summary.symbols,
348 &state.definitions,
349 &state.unresolved_names,
350 state.active_candidate_counts.items,
351 &state.pending,
352 );
353 }
354 }
355
356 if (selected.items.len == 0) return;
357 {
358 const parse_phase = trace.product(.selected_member_parse);
359 defer parse_phase.end();
360 try parseSelectedObjects(allocator, objects, state, selected.items, options);
361 }
362 state.observed_objects = objects.items.len;
363 }
364
365 const SelectedParseFailure = struct {
366 selected_index: usize = std.math.maxInt(usize),
367 err: ?model.Error = null,
368
369 fn found(self: SelectedParseFailure) bool {
370 return self.err != null;
371 }
372
373 fn before(self: SelectedParseFailure, other: SelectedParseFailure) bool {
374 return self.selected_index < other.selected_index;
375 }
376 };
377
378 const SelectedParseFailures = parallel.FailureSlots(SelectedParseFailure);
379
380 const SelectedParseContext = struct {
381 allocator: Allocator,
382 candidates: []Candidate,
383 selected: []const usize,
384 objects: []ObjectFile,
385 parse_options: ObjectParseOptions,
386 failures: *SelectedParseFailures,
387 };
388
389 fn parseSelectedObjects(
390 allocator: Allocator,
391 objects: *std.ArrayListUnmanaged(ObjectFile),
392 state: *ExtractionState,
393 selected: []const usize,
394 options: model.LinkOptions,
395 ) model.Error!void {
396 const object_start = objects.items.len;
397 try objects.resize(allocator, object_start + selected.len);
398
399 const requested_workers = if (options.max_link_jobs != 0)
400 options.max_link_jobs
401 else
402 @max(@as(usize, 1), selected.len / selected_objects_per_worker);
403 const workers = parallel.chooseWorkers(selected.len, requested_workers);
404 const parse_options = ObjectParseOptions{ .strip_debug = options.strip_debug };
405
406 if (workers <= 1) {
407 for (selected, 0..) |candidate_index, selected_index| {
408 objects.items[object_start + selected_index] = try parseSelectedObject(
409 allocator,
410 &state.candidates.items[candidate_index],
411 parse_options,
412 );
413 }
414 return;
415 }
416
417 var locked_allocator = allocators.LockedAllocator.init(allocator);
418 var failures = try SelectedParseFailures.init(allocator, workers, .{});
419 defer failures.deinit(allocator);
420
421 var context = SelectedParseContext{
422 .allocator = locked_allocator.allocator(),
423 .candidates = state.candidates.items,
424 .selected = selected,
425 .objects = objects.items[object_start..][0..selected.len],
426 .parse_options = parse_options,
427 .failures = &failures,
428 };
429 parallel.forItems(selected.len, workers, &context, parseSelectedObjectTask);
430 if (failures.earliest(SelectedParseFailure.found, SelectedParseFailure.before)) |failure| {
431 return failure.err.?;
432 }
433 }
434
435 fn parseSelectedObject(
436 allocator: Allocator,
437 candidate: *Candidate,
438 parse_options: ObjectParseOptions,
439 ) model.Error!ObjectFile {
440 const summary = candidate.summary orelse return error.InvalidObject;
441 var object = try parseObjectWithSelectionSummary(allocator, summary, parse_options);
442 candidate.summary = null;
443 object.input_index = candidate.archive_input_index;
444 return object;
445 }
446
447 fn parseSelectedObjectTask(context: *SelectedParseContext, worker: usize, selected_index: usize) void {
448 const candidate_index = context.selected[selected_index];
449 context.objects[selected_index] = parseSelectedObject(
450 context.allocator,
451 &context.candidates[candidate_index],
452 context.parse_options,
453 ) catch |err| {
454 context.failures.record(worker, .{
455 .selected_index = selected_index,
456 .err = err,
457 });
458 return;
459 };
460 }