lib/tldr/src/formats/elf/parser.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../root.zig");
3 const format = @import("format.zig");
4 const elf_object = @import("object/root.zig");
5 const relocation = @import("relocation/root.zig");
6 const section_state = @import("sections.zig");
7
8 const Allocator = std.mem.Allocator;
9 const model = root.model;
10 const trace = root.trace;
11
12 const ehdr_size = format.ehdr_size;
13 const shdr_size = format.shdr_size;
14 const sym_size = format.sym_size;
15 const native_endian = format.native_endian;
16 const SectionHeader = format.SectionHeader;
17 const Symbol = format.Symbol;
18 const Rela = format.Rela;
19 const symbolBindingIsExternalDefinition = format.symbolBindingIsExternalDefinition;
20 const sectionBytes = format.sectionBytes;
21 const requireRange = format.requireRange;
22 const stringFromTable = format.stringFromTable;
23 const decodeSectionHeaders = format.decodeSectionHeaders;
24 const readSymbol = format.readSymbol;
25 const readU16 = format.readU16;
26 const readU64 = format.readU64;
27 pub const RelocationRange = relocation.RelocationRange;
28 pub const ObjectParseOptions = relocation.ObjectParseOptions;
29 const RelocationCounts = relocation.RelocationCounts;
30 const scanSectionMetadata = relocation.scanSectionMetadata;
31 const countRelocationsBySection = relocation.countRelocationsBySection;
32 const parseRelocationsBySection = relocation.parseRelocationsBySection;
33
34 test "ELF parser borrows aligned single relocation section" {
35 if (native_endian != .little) return;
36 const allocator = std.testing.allocator;
37
38 const text = [_]u8{0xc3};
39 const data = @as([8]u8, @splat(0));
40 const text_index: u16 = 1;
41 const data_index: u16 = 2;
42 const sections = [_]elf_object.Section{
43 elf_object.Section.progbits(".text", &text, std.elf.SHF_EXECINSTR, 16),
44 elf_object.Section.progbits(".data", &data, std.elf.SHF_WRITE, 8),
45 };
46 const symbols = [_]elf_object.Symbol{
47 elf_object.Symbol.section(text_index),
48 elf_object.Symbol.section(data_index),
49 elf_object.Symbol.function("_start", text_index, 0, text.len),
50 };
51 const start_symbol: u32 = sections.len + 1;
52 const object_bytes = try elf_object.build(allocator, .{
53 .sections = §ions,
54 .symbols = &symbols,
55 .relocations = &.{
56 elf_object.Relocation.x86_64(data_index, 0, start_symbol, .@"64", 0),
57 },
58 });
59 defer allocator.free(object_bytes);
60 var object = try parseObject(allocator, .{ .name = "borrow.o", .bytes = object_bytes });
61 defer object.deinit(allocator);
62
63 try std.testing.expect(!object.relocations_owned);
64 try std.testing.expectEqual(@as(usize, 1), object.relocations.len);
65 const object_start = @intFromPtr(object_bytes.ptr);
66 const object_end = object_start + object_bytes.len;
67 const relocations_start = @intFromPtr(object.relocations.ptr);
68 try std.testing.expect(relocations_start >= object_start);
69 try std.testing.expect(relocations_start < object_end);
70 }
71
72 test "ELF parser borrows single effective relocation section" {
73 if (native_endian != .little) return;
74 const allocator = std.testing.allocator;
75
76 const text = [_]u8{0xc3};
77 const data = @as([8]u8, @splat(0));
78 const text_index: u16 = 1;
79 const data_index: u16 = 2;
80 const sections = [_]elf_object.Section{
81 elf_object.Section.progbits(".text", &text, std.elf.SHF_EXECINSTR, 16),
82 elf_object.Section.progbits(".data", &data, std.elf.SHF_WRITE, 8),
83 };
84 const symbols = [_]elf_object.Symbol{
85 elf_object.Symbol.section(text_index),
86 elf_object.Symbol.section(data_index),
87 elf_object.Symbol.function("_start", text_index, 0, text.len),
88 };
89 const start_symbol: u32 = sections.len + 1;
90 const object_bytes = try elf_object.build(allocator, .{
91 .sections = §ions,
92 .symbols = &symbols,
93 .relocations = &.{
94 elf_object.Relocation.x86_64(text_index, 0, 0, .NONE, 0),
95 elf_object.Relocation.x86_64(data_index, 0, start_symbol, .@"64", 0),
96 },
97 });
98 defer allocator.free(object_bytes);
99 var object = try parseObject(allocator, .{ .name = "effective-borrow.o", .bytes = object_bytes });
100 defer object.deinit(allocator);
101
102 try std.testing.expect(!object.relocations_owned);
103 try std.testing.expectEqual(@as(usize, 0), object.relocationsForSection(text_index).len);
104 try std.testing.expectEqual(@as(usize, 1), object.relocationsForSection(data_index).len);
105 }
106
107 test "ELF parser rejects string table without zero slot" {
108 const allocator = std.testing.allocator;
109
110 const text = [_]u8{0xc3};
111 const object_bytes = try elf_object.build(allocator, .{
112 .sections = &.{elf_object.Section.progbits(".text", &text, std.elf.SHF_EXECINSTR, 16)},
113 .symbols = &.{elf_object.Symbol.section(1)},
114 });
115 defer allocator.free(object_bytes);
116
117 const shoff = readU64(object_bytes, 40);
118 const shnum = readU16(object_bytes, 60);
119 const shstrndx = readU16(object_bytes, 62);
120 const sections = try allocator.alloc(SectionHeader, shnum);
121 defer allocator.free(sections);
122 decodeSectionHeaders(object_bytes, shoff, sections);
123
124 const shstrtab = try sectionBytes(object_bytes, sections[shstrndx]);
125 var strtab_offset: ?usize = null;
126 for (sections) |section| {
127 const name = try stringFromTable(shstrtab, section.name_offset);
128 if (std.mem.eql(u8, name, ".strtab")) {
129 strtab_offset = @intCast(section.offset);
130 break;
131 }
132 }
133 try std.testing.expect(strtab_offset != null);
134
135 object_bytes[strtab_offset.?] = 'x';
136 try std.testing.expectError(error.InvalidStringTable, parseObject(allocator, .{ .name = "bad-strtab.o", .bytes = object_bytes }));
137 }
138
139 pub const SectionRef = section_state.SectionRef;
140
141 pub const ObjectFile = struct {
142 name: []const u8,
143 input_index: usize = 0,
144 bytes: []const u8,
145 sections: []SectionHeader,
146 section_names: []const u8,
147 section_name_ends: []u32,
148 symbols: []Symbol,
149 relocations: []const Rela,
150 relocations_owned: bool,
151 has_common_symbols: bool,
152 has_named_strong_undefined_symbols: bool,
153 has_ifunc_definitions: bool,
154 has_group_sections: bool,
155 relocation_ranges: []RelocationRange,
156 discarded_sections: []bool = &.{},
157 folded_sections: []?SectionRef = &.{},
158
159 pub fn deinit(self: *ObjectFile, allocator: Allocator) void {
160 allocator.free(self.sections);
161 allocator.free(self.section_name_ends);
162 allocator.free(self.symbols);
163 if (self.relocations_owned and self.relocations.len != 0) allocator.free(@constCast(self.relocations));
164 if (self.relocation_ranges.len != 0) allocator.free(self.relocation_ranges);
165 if (self.discarded_sections.len != 0) allocator.free(self.discarded_sections);
166 if (self.folded_sections.len != 0) allocator.free(self.folded_sections);
167 }
168
169 pub fn relocationsForSection(self: ObjectFile, section_index: usize) []const Rela {
170 if (self.relocation_ranges.len == 0) return &.{};
171 const range = self.relocation_ranges[section_index];
172 return self.relocations[range.start..][0..range.count];
173 }
174 };
175
176 pub const ObjectSelectionSummary = struct {
177 name: []const u8,
178 bytes: []const u8,
179 sections: []SectionHeader,
180 section_names: []const u8,
181 symbols: []Symbol,
182 has_common_symbols: bool,
183 has_named_strong_undefined_symbols: bool,
184 has_ifunc_definitions: bool,
185 has_group_sections: bool,
186 symtab_index: ?usize,
187
188 pub fn deinit(self: *ObjectSelectionSummary, allocator: Allocator) void {
189 allocator.free(self.sections);
190 allocator.free(self.symbols);
191 self.* = undefined;
192 }
193 };
194
195 pub fn sectionName(object: ObjectFile, section_index: usize) model.Error![]const u8 {
196 if (section_index >= object.sections.len) return error.MissingSection;
197 const name_end = object.section_name_ends[section_index];
198 if (name_end == invalid_section_name_end) return error.InvalidStringTable;
199 return object.section_names[object.sections[section_index].name_offset..name_end];
200 }
201
202 const invalid_section_name_end = std.math.maxInt(u32);
203
204 fn resolveSectionNameEnds(
205 allocator: Allocator,
206 sections: []const SectionHeader,
207 section_names: []const u8,
208 ) Allocator.Error![]u32 {
209 const name_ends = try allocator.alloc(u32, sections.len);
210 errdefer allocator.free(name_ends);
211 for (sections, name_ends) |section, *name_end| {
212 if (section.name_offset >= section_names.len) {
213 name_end.* = invalid_section_name_end;
214 continue;
215 }
216 const terminator = std.mem.indexOfScalarPos(u8, section_names, section.name_offset, 0) orelse {
217 name_end.* = invalid_section_name_end;
218 continue;
219 };
220 name_end.* = @intCast(terminator);
221 }
222 return name_ends;
223 }
224
225 pub fn sectionNameOrEmpty(object: ObjectFile, section_index: usize) []const u8 {
226 return sectionName(object, section_index) catch "";
227 }
228
229 pub fn sectionNameFromTableOrEmpty(section_names: []const u8, section: SectionHeader) []const u8 {
230 return stringFromTable(section_names, section.name_offset) catch "";
231 }
232
233 pub fn parseObjectMetadata(allocator: Allocator, input: model.Input) model.Error!root.Object {
234 var object = try parseObject(allocator, input);
235 defer object.deinit(allocator);
236
237 const sections = try allocator.alloc(root.ObjectSection, object.sections.len);
238 errdefer allocator.free(sections);
239 for (sections, 0..) |*section, index| {
240 const source = object.sections[index];
241 section.* = .{
242 .name = sectionNameOrEmpty(object, index),
243 .address = source.address,
244 .size = source.size,
245 .offset = source.offset,
246 .alignment = source.alignment,
247 .flags = source.flags,
248 .section_type = source.section_type,
249 .relocation_count = @intCast(object.relocationsForSection(index).len),
250 };
251 }
252
253 const symbols = try allocator.alloc(root.ObjectSymbol, object.symbols.len);
254 errdefer allocator.free(symbols);
255 for (symbols, 0..) |*symbol, index| {
256 const source = object.symbols[index];
257 symbol.* = .{
258 .name = source.name,
259 .section_index = source.section_index,
260 .value = source.value,
261 .size = source.size,
262 .kind = source.kind(),
263 .binding = source.binding(),
264 .external = symbolBindingIsExternalDefinition(source.binding()),
265 .undefined = source.isUndefined(),
266 };
267 }
268
269 return .{
270 .target = .linux_x86_64_elf,
271 .sections = sections,
272 .symbols = symbols,
273 };
274 }
275
276 pub fn parseObject(allocator: Allocator, input: model.Input) model.Error!ObjectFile {
277 return parseObjectWithOptions(allocator, input, .{});
278 }
279
280 pub fn parseObjectSelectionSummary(allocator: Allocator, input: model.Input) model.Error!ObjectSelectionSummary {
281 const phase = trace.product(.input_discovery);
282 defer phase.end();
283 const bytes = input.bytes;
284 if (bytes.len < ehdr_size) return error.InvalidElfHeader;
285 if (!std.mem.eql(u8, bytes[0..4], std.elf.MAGIC)) return error.InvalidElfHeader;
286 if (bytes[std.elf.EI_CLASS] != std.elf.ELFCLASS64) return error.UnsupportedFormat;
287 if (bytes[std.elf.EI_DATA] != std.elf.ELFDATA2LSB) return error.UnsupportedFormat;
288 if (readU16(bytes, 16) != @backingInt(std.elf.ET.REL)) return error.UnsupportedOutputKind;
289 if (readU16(bytes, 18) != @backingInt(std.elf.EM.X86_64)) return error.UnsupportedArchitecture;
290
291 const shoff = readU64(bytes, 40);
292 const shentsize = readU16(bytes, 58);
293 const shnum = readU16(bytes, 60);
294 const shstrndx = readU16(bytes, 62);
295 if (shentsize != shdr_size or shnum == 0 or shstrndx >= shnum) return error.InvalidElfHeader;
296 try requireRange(bytes, shoff, @as(u64, shnum) * shdr_size);
297
298 const sections = try allocator.alloc(SectionHeader, shnum);
299 errdefer allocator.free(sections);
300 decodeSectionHeaders(bytes, shoff, sections);
301
302 const shstrtab = try sectionBytes(bytes, sections[shstrndx]);
303 const section_metadata = scanSectionMetadata(sections);
304
305 var has_common_symbols = false;
306 var has_named_strong_undefined_symbols = false;
307 var has_ifunc_definitions = false;
308 const symbols = if (section_metadata.symtab_index) |index| blk: {
309 const symtab = sections[index];
310 if (symtab.entry_size != sym_size or symtab.size % sym_size != 0) return error.InvalidObject;
311 if (symtab.link >= sections.len) return error.MissingStringTable;
312 const strtab = try sectionBytes(bytes, sections[symtab.link]);
313 const symtab_bytes = try sectionBytes(bytes, symtab);
314 const symbol_count = symtab_bytes.len / sym_size;
315 if (symbol_count != 0 and (strtab.len == 0 or strtab[0] != 0)) return error.InvalidStringTable;
316
317 const parsed_symbols = try allocator.alloc(Symbol, symbol_count);
318 errdefer allocator.free(parsed_symbols);
319 for (parsed_symbols, 0..) |*symbol, symbol_index| {
320 symbol.* = readSymbol(symtab_bytes[symbol_index * sym_size ..][0..sym_size]);
321 symbol.name = if (symbol.name_offset == 0) "" else try stringFromTable(strtab, symbol.name_offset);
322 if (symbol.isCommon()) has_common_symbols = true;
323 if (symbol.kind() == std.elf.STT_GNU_IFUNC and !symbol.isUndefined()) has_ifunc_definitions = true;
324 if (symbol.isUndefined() and symbol.name.len != 0 and !symbol.isWeakUndefined()) {
325 has_named_strong_undefined_symbols = true;
326 }
327 }
328 break :blk parsed_symbols;
329 } else try allocator.alloc(Symbol, 0);
330 errdefer allocator.free(symbols);
331
332 return .{
333 .name = input.name,
334 .bytes = bytes,
335 .sections = sections,
336 .section_names = shstrtab,
337 .symbols = symbols,
338 .has_common_symbols = has_common_symbols,
339 .has_named_strong_undefined_symbols = has_named_strong_undefined_symbols,
340 .has_ifunc_definitions = has_ifunc_definitions,
341 .has_group_sections = section_metadata.has_group_sections,
342 .symtab_index = section_metadata.symtab_index,
343 };
344 }
345
346 pub fn parseObjectWithSelectionSummary(
347 allocator: Allocator,
348 summary: ObjectSelectionSummary,
349 parse_options: ObjectParseOptions,
350 ) model.Error!ObjectFile {
351 const phase = trace.product(.input_discovery);
352 defer phase.end();
353 var relocation_counts: RelocationCounts = .{};
354 defer relocation_counts.deinit(allocator);
355 const section_metadata = scanSectionMetadata(summary.sections);
356 if (section_metadata.has_relocation_sections) {
357 relocation_counts = try countRelocationsBySection(
358 allocator,
359 summary.bytes,
360 summary.sections,
361 summary.section_names,
362 summary.symtab_index,
363 parse_options,
364 );
365 }
366
367 const relocation_data = try parseRelocationsBySection(
368 allocator,
369 summary.bytes,
370 summary.sections,
371 summary.section_names,
372 relocation_counts,
373 parse_options,
374 );
375 errdefer relocation_data.deinit(allocator);
376
377 const section_name_ends = try resolveSectionNameEnds(allocator, summary.sections, summary.section_names);
378 errdefer allocator.free(section_name_ends);
379
380 return .{
381 .name = summary.name,
382 .bytes = summary.bytes,
383 .sections = summary.sections,
384 .section_names = summary.section_names,
385 .section_name_ends = section_name_ends,
386 .symbols = summary.symbols,
387 .relocations = relocation_data.relocations,
388 .relocations_owned = relocation_data.owned,
389 .has_common_symbols = summary.has_common_symbols,
390 .has_named_strong_undefined_symbols = summary.has_named_strong_undefined_symbols,
391 .has_ifunc_definitions = summary.has_ifunc_definitions,
392 .has_group_sections = summary.has_group_sections,
393 .relocation_ranges = relocation_data.ranges,
394 };
395 }
396
397 pub fn parseObjectWithOptions(allocator: Allocator, input: model.Input, parse_options: ObjectParseOptions) model.Error!ObjectFile {
398 const phase = trace.product(.input_discovery);
399 defer phase.end();
400 const bytes = input.bytes;
401 if (bytes.len < ehdr_size) return error.InvalidElfHeader;
402 if (!std.mem.eql(u8, bytes[0..4], std.elf.MAGIC)) return error.InvalidElfHeader;
403 if (bytes[std.elf.EI_CLASS] != std.elf.ELFCLASS64) return error.UnsupportedFormat;
404 if (bytes[std.elf.EI_DATA] != std.elf.ELFDATA2LSB) return error.UnsupportedFormat;
405 if (readU16(bytes, 16) != @backingInt(std.elf.ET.REL)) return error.UnsupportedOutputKind;
406 if (readU16(bytes, 18) != @backingInt(std.elf.EM.X86_64)) return error.UnsupportedArchitecture;
407
408 const shoff = readU64(bytes, 40);
409 const shentsize = readU16(bytes, 58);
410 const shnum = readU16(bytes, 60);
411 const shstrndx = readU16(bytes, 62);
412 if (shentsize != shdr_size or shnum == 0 or shstrndx >= shnum) return error.InvalidElfHeader;
413 try requireRange(bytes, shoff, @as(u64, shnum) * shdr_size);
414
415 const sections = try allocator.alloc(SectionHeader, shnum);
416 errdefer allocator.free(sections);
417 decodeSectionHeaders(bytes, shoff, sections);
418
419 const shstrtab = try sectionBytes(bytes, sections[shstrndx]);
420
421 const section_metadata = scanSectionMetadata(sections);
422 const symtab_index = section_metadata.symtab_index;
423 var has_common_symbols = false;
424 var has_named_strong_undefined_symbols = false;
425 var has_ifunc_definitions = false;
426 const symbols = if (symtab_index) |index| blk: {
427 const symtab = sections[index];
428 if (symtab.entry_size != sym_size or symtab.size % sym_size != 0) return error.InvalidObject;
429 if (symtab.link >= sections.len) return error.MissingStringTable;
430 const strtab = try sectionBytes(bytes, sections[symtab.link]);
431 const symtab_bytes = try sectionBytes(bytes, symtab);
432 const symbol_count = symtab_bytes.len / sym_size;
433 if (symbol_count != 0 and (strtab.len == 0 or strtab[0] != 0)) return error.InvalidStringTable;
434
435 const parsed_symbols = try allocator.alloc(Symbol, symbol_count);
436 errdefer allocator.free(parsed_symbols);
437 for (parsed_symbols, 0..) |*symbol, symbol_index| {
438 symbol.* = readSymbol(symtab_bytes[symbol_index * sym_size ..][0..sym_size]);
439 symbol.name = if (symbol.name_offset == 0) "" else try stringFromTable(strtab, symbol.name_offset);
440 if (symbol.isCommon()) has_common_symbols = true;
441 if (symbol.kind() == std.elf.STT_GNU_IFUNC and !symbol.isUndefined()) has_ifunc_definitions = true;
442 if (symbol.isUndefined() and symbol.name.len != 0 and !symbol.isWeakUndefined()) {
443 has_named_strong_undefined_symbols = true;
444 }
445 }
446 break :blk parsed_symbols;
447 } else try allocator.alloc(Symbol, 0);
448 errdefer allocator.free(symbols);
449
450 var relocation_counts: RelocationCounts = .{};
451 defer relocation_counts.deinit(allocator);
452 if (section_metadata.has_relocation_sections) {
453 relocation_counts = try countRelocationsBySection(allocator, bytes, sections, shstrtab, symtab_index, parse_options);
454 }
455
456 const relocation_data = try parseRelocationsBySection(allocator, bytes, sections, shstrtab, relocation_counts, parse_options);
457 errdefer relocation_data.deinit(allocator);
458
459 const section_name_ends = try resolveSectionNameEnds(allocator, sections, shstrtab);
460 errdefer allocator.free(section_name_ends);
461
462 return .{
463 .name = input.name,
464 .bytes = bytes,
465 .sections = sections,
466 .section_names = shstrtab,
467 .section_name_ends = section_name_ends,
468 .symbols = symbols,
469 .relocations = relocation_data.relocations,
470 .relocations_owned = relocation_data.owned,
471 .has_common_symbols = has_common_symbols,
472 .has_named_strong_undefined_symbols = has_named_strong_undefined_symbols,
473 .has_ifunc_definitions = has_ifunc_definitions,
474 .has_group_sections = section_metadata.has_group_sections,
475 .relocation_ranges = relocation_data.ranges,
476 };
477 }