lib/tldr/src/formats/elf/ehframe/scan.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../../root.zig");
3 const elf = @import("../root.zig");
4 const section = @import("section.zig");
5
6 const Allocator = std.mem.Allocator;
7 const model = root.model;
8 const parallel = root.parallel;
9 const ObjectFile = elf.parser.ObjectFile;
10 const ObjectLayout = elf.layout.ObjectLayout;
11 const OutputSection = elf.layout.OutputSection;
12 const SectionContribution = elf.layout.SectionContribution;
13 const EhFramePieceLayout = elf.layout.EhFramePieceLayout;
14 const EhFrameCieLayout = elf.layout.EhFrameCieLayout;
15 const EhFrameSectionLayout = elf.layout.EhFrameSectionLayout;
16 const GlobalSymbol = elf.layout.GlobalSymbol;
17 const SectionHeader = elf.format.SectionHeader;
18 const Rela = elf.format.Rela;
19 const output_section_count = elf.output_section.output_section_count;
20 const sectionBytes = elf.format.sectionBytes;
21
22 const parallel_scan_threshold = 2 * 1024 * 1024;
23 const scan_bytes_per_worker = 256 * 1024;
24
25 pub const Scan = struct {
26 pending: std.ArrayListUnmanaged(Pending) = .empty,
27
28 pub const Pending = struct {
29 object_index: u32,
30 section_index: u32,
31 bytes: []const u8 = &.{},
32 relocations: []const Rela = &.{},
33 piece_count: usize = 0,
34 relocation_count: usize = 0,
35 cie_count: usize = 0,
36 output_size: u64 = 0,
37 pieces: []EhFramePieceLayout = &.{},
38 adjusted: []Rela = &.{},
39 cies: []EhFrameCieLayout = &.{},
40 failure: model.Error!void = {},
41 };
42
43 const PhaseContext = struct {
44 pending: []Pending,
45 objects: []const ObjectFile,
46 globals: *const std.StringHashMapUnmanaged(GlobalSymbol),
47 };
48
49 pub const Reference = struct {
50 object_index: u32,
51 section_index: u32,
52 };
53
54 pub fn deinit(self: *Scan, allocator: Allocator) void {
55 for (self.pending.items) |entry| {
56 if (entry.cies.len != 0) allocator.free(entry.cies);
57 }
58 self.pending.deinit(allocator);
59 }
60
61 pub fn prepare(
62 self: *Scan,
63 allocator: Allocator,
64 objects: []const ObjectFile,
65 layouts: []ObjectLayout,
66 globals: *const std.StringHashMapUnmanaged(GlobalSymbol),
67 options: model.LinkOptions,
68 references: []const Reference,
69 ) model.Error!void {
70 var total_bytes: usize = 0;
71 try self.pending.ensureTotalCapacity(allocator, references.len);
72 for (references) |reference| {
73 const object = objects[reference.object_index];
74 const section_header = object.sections[reference.section_index];
75 var entry = Pending{
76 .object_index = reference.object_index,
77 .section_index = reference.section_index,
78 .relocations = object.relocationsForSection(reference.section_index),
79 };
80 if (sectionBytes(object.bytes, section_header)) |bytes| {
81 entry.bytes = bytes;
82 total_bytes += bytes.len;
83 } else |err| {
84 entry.failure = err;
85 }
86 self.pending.appendAssumeCapacity(entry);
87 }
88 if (self.pending.items.len == 0) return;
89
90 const pending = self.pending.items;
91 const requested_workers = if (options.max_link_jobs != 0)
92 options.max_link_jobs
93 else
94 total_bytes / scan_bytes_per_worker;
95 const workers = if (total_bytes >= parallel_scan_threshold)
96 parallel.chooseWorkers(pending.len, requested_workers)
97 else
98 1;
99
100 var context = PhaseContext{ .pending = pending, .objects = objects, .globals = globals };
101 if (workers <= 1) {
102 for (pending, 0..) |_, index| countPending(&context, 0, index);
103 } else {
104 parallel.forItems(pending.len, workers, &context, countPending);
105 }
106
107 for (pending) |*entry| {
108 entry.failure catch continue;
109 entry.pieces = try allocator.alloc(EhFramePieceLayout, entry.piece_count);
110 entry.adjusted = try allocator.alloc(Rela, entry.relocation_count);
111 const slots = try ensureLayouts(allocator, objects[entry.object_index], &layouts[entry.object_index].eh_frame_sections);
112 slots[entry.section_index] = .{
113 .present = true,
114 .pieces = entry.pieces,
115 .relocations = entry.adjusted,
116 };
117 entry.cies = try allocator.alloc(EhFrameCieLayout, entry.cie_count);
118 }
119
120 if (workers <= 1) {
121 for (pending, 0..) |_, index| fillPending(&context, 0, index);
122 } else {
123 parallel.forItems(pending.len, workers, &context, fillPending);
124 }
125 }
126
127 fn countPending(context: *PhaseContext, worker: usize, index: usize) void {
128 _ = worker;
129 const entry = &context.pending[index];
130 entry.failure catch return;
131 var consumer = Count{};
132 entry.output_size = section.walk(
133 context.objects,
134 entry.object_index,
135 entry.bytes,
136 entry.relocations,
137 context.globals,
138 &consumer,
139 ) catch |err| {
140 entry.failure = err;
141 return;
142 };
143 entry.piece_count = consumer.pieces;
144 entry.relocation_count = consumer.relocations;
145 entry.cie_count = consumer.cies;
146 }
147
148 fn fillPending(context: *PhaseContext, worker: usize, index: usize) void {
149 _ = worker;
150 const entry = &context.pending[index];
151 entry.failure catch return;
152 var consumer = Fill{ .entry = entry };
153 const output_size = section.walk(
154 context.objects,
155 entry.object_index,
156 entry.bytes,
157 entry.relocations,
158 context.globals,
159 &consumer,
160 ) catch |err| {
161 entry.failure = err;
162 return;
163 };
164 std.debug.assert(output_size == entry.output_size);
165 std.debug.assert(consumer.piece_index == entry.piece_count);
166 std.debug.assert(consumer.relocation_index == entry.relocation_count);
167 std.debug.assert(consumer.cie_index == entry.cie_count);
168 }
169 };
170
171 const Count = struct {
172 pieces: usize = 0,
173 relocations: usize = 0,
174 cies: usize = 0,
175
176 pub fn piece(self: *Count, piece_layout: EhFramePieceLayout) void {
177 _ = piece_layout;
178 self.pieces += 1;
179 }
180
181 pub fn cie(self: *Count, input_offset: u64, output_offset: u64) void {
182 _ = input_offset;
183 _ = output_offset;
184 self.cies += 1;
185 }
186
187 pub fn relocation(self: *Count, adjusted: Rela) void {
188 _ = adjusted;
189 self.relocations += 1;
190 }
191
192 pub fn resolve(self: *Count, cie_input_offset: u64, output_size: u64) model.Error!u32 {
193 _ = self;
194 _ = cie_input_offset;
195 _ = output_size;
196 return 0;
197 }
198 };
199
200 const Fill = struct {
201 entry: *Scan.Pending,
202 piece_index: usize = 0,
203 relocation_index: usize = 0,
204 cie_index: usize = 0,
205
206 pub fn piece(self: *Fill, piece_layout: EhFramePieceLayout) void {
207 self.entry.pieces[self.piece_index] = piece_layout;
208 self.piece_index += 1;
209 }
210
211 pub fn cie(self: *Fill, input_offset: u64, output_offset: u64) void {
212 self.entry.cies[self.cie_index] = .{
213 .input_offset = input_offset,
214 .output_offset = output_offset,
215 };
216 self.cie_index += 1;
217 }
218
219 pub fn relocation(self: *Fill, adjusted: Rela) void {
220 self.entry.adjusted[self.relocation_index] = adjusted;
221 self.relocation_index += 1;
222 }
223
224 pub fn resolve(self: *Fill, cie_input_offset: u64, output_size: u64) model.Error!u32 {
225 const cie_output_offset = section.cieOutputOffset(self.entry.cies[0..self.cie_index], cie_input_offset) orelse return error.InvalidObject;
226 if (output_size + 4 < cie_output_offset) return error.InvalidObject;
227 return std.math.cast(u32, output_size + 4 - cie_output_offset) orelse return error.InvalidRange;
228 }
229 };
230
231 fn ensureLayouts(
232 allocator: Allocator,
233 object: ObjectFile,
234 eh_frame_sections: *[]EhFrameSectionLayout,
235 ) Allocator.Error![]EhFrameSectionLayout {
236 if (eh_frame_sections.*.len != 0) return eh_frame_sections.*;
237 const sections = try allocator.alloc(EhFrameSectionLayout, object.sections.len);
238 @memset(sections, .{});
239 eh_frame_sections.* = sections;
240 return sections;
241 }
242
243 fn testWalkBytes() [44]u8 {
244 var bytes = @as([44]u8, @splat(0));
245 std.mem.writeInt(u32, bytes[0..4], 16, .little);
246 std.mem.writeInt(u32, bytes[4..8], 0, .little);
247 std.mem.writeInt(u32, bytes[20..24], 16, .little);
248 std.mem.writeInt(u32, bytes[24..28], 24, .little);
249 std.mem.writeInt(u32, bytes[40..44], 0, .little);
250 return bytes;
251 }
252
253 test "count and fill walks agree on synthetic eh_frame records" {
254 const bytes = testWalkBytes();
255 const globals: std.StringHashMapUnmanaged(GlobalSymbol) = .empty;
256
257 var count = Count{};
258 const counted_size = try section.walk(&.{}, 0, &bytes, &.{}, &globals, &count);
259 try std.testing.expectEqual(@as(u64, 44), counted_size);
260 try std.testing.expectEqual(@as(usize, 3), count.pieces);
261 try std.testing.expectEqual(@as(usize, 1), count.cies);
262 try std.testing.expectEqual(@as(usize, 0), count.relocations);
263
264 var pieces: [3]EhFramePieceLayout = undefined;
265 var cies: [1]EhFrameCieLayout = undefined;
266 var entry = Scan.Pending{
267 .object_index = 0,
268 .section_index = 0,
269 .pieces = &pieces,
270 .cies = &cies,
271 };
272 var fill = Fill{ .entry = &entry };
273 const filled_size = try section.walk(&.{}, 0, &bytes, &.{}, &globals, &fill);
274 try std.testing.expectEqual(counted_size, filled_size);
275 try std.testing.expectEqual(count.pieces, fill.piece_index);
276 try std.testing.expectEqual(count.cies, fill.cie_index);
277
278 try std.testing.expectEqual(@as(u64, 0), pieces[0].input_offset);
279 try std.testing.expectEqual(@as(u64, 20), pieces[0].size);
280 try std.testing.expect(!pieces[0].patch_cie_pointer);
281 try std.testing.expectEqual(@as(u64, 20), pieces[1].input_offset);
282 try std.testing.expectEqual(@as(u64, 20), pieces[1].output_offset);
283 try std.testing.expect(pieces[1].patch_cie_pointer);
284 try std.testing.expectEqual(@as(u32, 24), pieces[1].cie_pointer);
285 try std.testing.expectEqual(@as(u64, 40), pieces[2].input_offset);
286 try std.testing.expectEqual(@as(u64, 4), pieces[2].size);
287 try std.testing.expectEqual(@as(u64, 0), cies[0].input_offset);
288 }
289
290 test "fill walk rejects an unresolved cie reference" {
291 var bytes = @as([24]u8, @splat(0));
292 std.mem.writeInt(u32, bytes[0..4], 16, .little);
293 std.mem.writeInt(u32, bytes[4..8], 3, .little);
294 std.mem.writeInt(u32, bytes[20..24], 0, .little);
295 const globals: std.StringHashMapUnmanaged(GlobalSymbol) = .empty;
296
297 var count = Count{};
298 _ = try section.walk(&.{}, 0, &bytes, &.{}, &globals, &count);
299
300 var pieces: [2]EhFramePieceLayout = undefined;
301 var entry = Scan.Pending{
302 .object_index = 0,
303 .section_index = 0,
304 .pieces = &pieces,
305 };
306 var fill = Fill{ .entry = &entry };
307 try std.testing.expectError(error.InvalidObject, section.walk(&.{}, 0, &bytes, &.{}, &globals, &fill));
308 }