lib/tldr/src/formats/elf/merge/string.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../../root.zig");
3 const elf = @import("../root.zig");
4 const record = @import("record.zig");
5 const start = @import("start.zig");
6 const target = @import("target.zig");
7
8 const Allocator = std.mem.Allocator;
9 const model = root.model;
10 const parallel = root.parallel;
11 const ObjectFile = elf.parser.ObjectFile;
12 const OutputSection = elf.layout.OutputSection;
13 const MergePieceLayout = elf.layout.MergePieceLayout;
14 const MergeSectionLayout = elf.layout.MergeSectionLayout;
15 const SectionHeader = elf.format.SectionHeader;
16 const output_section_count = elf.output_section.output_section_count;
17 const sectionBytes = elf.format.sectionBytes;
18 const outputIndexForAlloc = elf.output_section.indexForAllocated;
19 const Record = record.Record;
20
21 const parallel_scan_threshold = 2 * 1024 * 1024;
22 const scan_bytes_per_worker = 256 * 1024;
23
24 pub const String = struct {
25 records: std.ArrayListUnmanaged(Record) = .empty,
26 pending: std.ArrayListUnmanaged(Pending) = .empty,
27
28 const Pending = struct {
29 bytes: []const u8,
30 external_starts: []const u64,
31 layout_slot: *MergeSectionLayout,
32 alignment: u64,
33 section_type: u32,
34 output_index: u8,
35 base: usize = 0,
36 count: usize = 0,
37 pieces: []MergePieceLayout = &.{},
38 };
39
40 const ScanContext = struct {
41 pending: []Pending,
42 records: []Record,
43 };
44
45 pub fn deinit(self: *String, allocator: Allocator) void {
46 self.records.deinit(allocator);
47 self.pending.deinit(allocator);
48 }
49
50 pub fn register(
51 self: *String,
52 allocator: Allocator,
53 object: ObjectFile,
54 section: SectionHeader,
55 section_index: usize,
56 external_starts: []const u64,
57 output_sections: *[output_section_count]OutputSection,
58 layout_slot: *MergeSectionLayout,
59 ) model.Error!void {
60 if (object.relocationsForSection(section_index).len != 0) return error.UnsupportedRelocation;
61
62 const bytes = try sectionBytes(object.bytes, section);
63 if (bytes.len == 0) return;
64 if (bytes[bytes.len - 1] != 0) return error.InvalidObject;
65
66 const output_index = outputIndexForAlloc(section);
67 var output = &output_sections[output_index];
68 const alignment = @max(section.alignment, 1);
69 output.alignment = @max(output.alignment, alignment);
70
71 const starts = if (external_starts.len != 0)
72 try allocator.dupe(u64, external_starts)
73 else
74 external_starts;
75 try self.pending.append(allocator, .{
76 .bytes = bytes,
77 .external_starts = starts,
78 .layout_slot = layout_slot,
79 .alignment = alignment,
80 .section_type = section.section_type,
81 .output_index = @intCast(output_index),
82 });
83 }
84
85 pub fn finish(
86 self: *String,
87 allocator: Allocator,
88 output_sections: *[output_section_count]OutputSection,
89 options: model.LinkOptions,
90 ) model.Error!void {
91 try self.materialize(allocator, options);
92 try target.assign(allocator, output_sections, self.records.items, options);
93 }
94
95 fn materialize(self: *String, allocator: Allocator, options: model.LinkOptions) model.Error!void {
96 if (self.pending.items.len == 0) return;
97 const pending = self.pending.items;
98
99 var total_bytes: usize = 0;
100 for (pending) |entry| total_bytes += entry.bytes.len;
101 const requested_workers = if (options.max_link_jobs != 0)
102 options.max_link_jobs
103 else
104 total_bytes / scan_bytes_per_worker;
105 const workers = if (total_bytes >= parallel_scan_threshold)
106 parallel.chooseWorkers(pending.len, requested_workers)
107 else
108 1;
109
110 var count_context = ScanContext{ .pending = pending, .records = &.{} };
111 if (workers <= 1) {
112 for (pending, 0..) |_, index| countPending(&count_context, 0, index);
113 } else {
114 parallel.forItems(pending.len, workers, &count_context, countPending);
115 }
116
117 var total: usize = 0;
118 for (pending) |*entry| {
119 entry.base = total;
120 total += entry.count;
121 entry.pieces = try allocator.alloc(MergePieceLayout, entry.count);
122 entry.layout_slot.* = .{ .pieces = entry.pieces };
123 }
124 if (std.math.cast(u32, total) == null) return error.InvalidObject;
125 try self.records.resize(allocator, total);
126
127 var fill_context = ScanContext{ .pending = pending, .records = self.records.items };
128 if (workers <= 1) {
129 for (pending, 0..) |_, index| fillPending(&fill_context, 0, index);
130 } else {
131 parallel.forItems(pending.len, workers, &fill_context, fillPending);
132 }
133 }
134
135 fn countPending(context: *ScanContext, worker: usize, index: usize) void {
136 _ = worker;
137 context.pending[index].count = start.count(context.pending[index].bytes);
138 }
139
140 fn fillPending(context: *ScanContext, worker: usize, index: usize) void {
141 _ = worker;
142 const entry = context.pending[index];
143 const records = context.records[entry.base..][0..entry.count];
144 const bytes = entry.bytes;
145 var input_offset: usize = 0;
146 var piece_index: usize = 0;
147 var external_start_index: usize = 0;
148 for (bytes, 0..) |byte, byte_index| {
149 if (byte != 0) continue;
150 const end = byte_index + 1;
151 const string_bytes = bytes[input_offset..end];
152 entry.pieces[piece_index] = .{
153 .input_offset = @intCast(input_offset),
154 .size = @intCast(string_bytes.len),
155 };
156 records[piece_index] = .{
157 .ordinal = @intCast(entry.base + piece_index),
158 .section_type = entry.section_type,
159 .output_index = entry.output_index,
160 .alignment = entry.alignment,
161 .reverse_prefix = record.reversePrefix(string_bytes),
162 .bytes = string_bytes,
163 .piece = &entry.pieces[piece_index],
164 .external_start = start.has(entry.external_starts, &external_start_index, input_offset),
165 };
166 piece_index += 1;
167 input_offset = end;
168 }
169 }
170 };