lib/tldr/src/formats/elf/object/layout.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const elf = @import("../root.zig");
3 const model = @import("model.zig");
4
5 const Allocator = std.mem.Allocator;
6 const format = elf.format;
7 const ehdr_size = format.ehdr_size;
8 const shdr_size = format.shdr_size;
9 const sym_size = format.sym_size;
10 const rela_size = format.rela_size;
11 const Description = model.Description;
12 const Error = model.Error;
13 const Section = model.Section;
14 const Symbol = model.Symbol;
15
16 /// The section names the writer supplies itself, leaving them out of every
17 /// description: the `.rela` prefix put before a section's name to name its
18 /// relocation section, and `.symtab`, `.strtab` and `.shstrtab`. The layout
19 /// sizes the section name table from these names, and the writer copies them
20 /// into it, so both agree on its bytes.
21 pub const rela_name_prefix = ".rela";
22 pub const symtab_name = ".symtab";
23 pub const strtab_name = ".strtab";
24 pub const shstrtab_name = ".shstrtab";
25
26 /// The number of section headers every object has besides one per described
27 /// section and one per relocation section: the empty header at index 0 plus the
28 /// headers of `.symtab`, `.strtab` and `.shstrtab`. The layout adds this
29 /// constant when counting section headers, and tests use it to predict the
30 /// header count.
31 pub const fixed_section_count = 4;
32
33 /// The number of 64-bit slots `plan` sets aside for each described section: the
34 /// section's file offset, its relocation count, and the file offset of its
35 /// relocation section. The `plan` function multiplies the section count by it
36 /// to size its scratch allocation.
37 const words_per_section = 3;
38
39 /// Records where each part of one described object goes in the file: each
40 /// section's bytes, each relocation section, `.symtab`, `.strtab`, `.shstrtab`
41 /// and the section header table, along with the total file size. The `plan`
42 /// function computes the layout once from the description and checks every
43 /// addition and multiplication, so `write` has no arithmetic left that can
44 /// fail. One allocation, `scratch`, holds four slices in this order: each
45 /// section's file offset, each section's relocation count, each relocation
46 /// section's file offset, and the order in which the writer emits relocations.
47 /// The `build` function plans a layout and passes it to `write`, and a caller
48 /// that writes into its own buffer does the same and calls `deinit` to free
49 /// `scratch` with the allocator that was given to `plan`.
50 pub const Layout = struct {
51 size: usize,
52 shoff: u64,
53 shnum: u16,
54 symtab_index: u16,
55 strtab_index: u16,
56 shstrtab_index: u16,
57 first_global: u32,
58 symtab_offset: u64,
59 symtab_size: u64,
60 strtab_offset: u64,
61 strtab_size: u64,
62 shstrtab_offset: u64,
63 shstrtab_size: u64,
64 scratch: []u64,
65 section_offsets: []u64,
66 rela_counts: []u64,
67 rela_starts: []u64,
68 order: []u64,
69
70 /// Checks `description` and computes the file offset of every record, so
71 /// callers run it before `write`, directly or through `build`, to learn the
72 /// file size to allocate. The call returns `error.TooManySymbols` for 2^32 -
73 /// 1 symbols or more, `error.InvalidAlignment` for an alignment that is
74 /// neither 0 nor a power of two, and `error.InvalidSize` for a NOBITS
75 /// section that carries bytes or for any other section whose nonzero `size`
76 /// differs from the length of its bytes. The function returns
77 /// `error.SymbolOrder` for a local symbol after a global one,
78 /// `error.InvalidSectionIndex` for a relocation whose target is 0 or past
79 /// the last section, `error.TooManySections` for more headers than an index
80 /// below `SHN_LORESERVE` can name, and `error.SizeOverflow` for an offset
81 /// or a string table size too large to represent. The function makes one
82 /// allocation whose size follows from the section and relocation counts
83 /// alone, so it is fixed up front and no later step enlarges it. The caller
84 /// frees the result with `Layout.deinit`.
85 pub fn plan(allocator: Allocator, description: Description) Error!Layout {
86 if (description.symbols.len >= std.math.maxInt(u32)) return error.TooManySymbols;
87 for (description.sections) |section| try validateSection(section);
88 const first_global = try firstGlobalIndex(description.symbols);
89
90 const section_count = description.sections.len;
91 const words = words_per_section * section_count + description.relocations.len;
92 const scratch = try allocator.alloc(u64, words);
93 errdefer allocator.free(scratch);
94 const section_offsets = scratch[0..section_count];
95 const rela_counts = scratch[section_count..][0..section_count];
96 const rela_starts = scratch[2 * section_count ..][0..section_count];
97 const order = scratch[words_per_section * section_count ..];
98 const carved = section_offsets.len + rela_counts.len + rela_starts.len;
99 std.debug.assert(carved + order.len == scratch.len);
100
101 const relocated_sections =
102 try countRelocations(description, rela_counts, rela_starts, order);
103
104 const shnum_count = section_count + relocated_sections + fixed_section_count;
105 if (shnum_count >= std.elf.SHN_LORESERVE) return error.TooManySections;
106 const symtab_index: u16 = @intCast(1 + section_count + relocated_sections);
107
108 var offset = try placePayloads(description, section_offsets, rela_counts, rela_starts);
109 offset = try alignForward(offset, 8);
110 const symtab_offset = offset;
111 const symtab_size = try mul(description.symbols.len + 1, sym_size);
112 offset = try add(offset, symtab_size);
113
114 const strtab_offset = offset;
115 const strtab_size = try symbolNameTableSize(description.symbols);
116 offset = try add(offset, strtab_size);
117
118 const shstrtab_offset = offset;
119 const shstrtab_size = try sectionNameTableSize(description.sections, rela_counts);
120 offset = try add(offset, shstrtab_size);
121
122 const shoff = try alignForward(offset, 8);
123 const total = try add(shoff, try mul(shnum_count, shdr_size));
124
125 return .{
126 .size = std.math.cast(usize, total) orelse return error.SizeOverflow,
127 .shoff = shoff,
128 .shnum = @intCast(shnum_count),
129 .symtab_index = symtab_index,
130 .strtab_index = symtab_index + 1,
131 .shstrtab_index = symtab_index + 2,
132 .first_global = first_global,
133 .symtab_offset = symtab_offset,
134 .symtab_size = symtab_size,
135 .strtab_offset = strtab_offset,
136 .strtab_size = strtab_size,
137 .shstrtab_offset = shstrtab_offset,
138 .shstrtab_size = shstrtab_size,
139 .scratch = scratch,
140 .section_offsets = section_offsets,
141 .rela_counts = rela_counts,
142 .rela_starts = rela_starts,
143 .order = order,
144 };
145 }
146
147 pub fn deinit(self: *Layout, allocator: Allocator) void {
148 allocator.free(self.scratch);
149 self.* = undefined;
150 }
151 };
152
153 /// Places each described section's bytes at the next offset its alignment
154 /// allows, starting after the 64-byte file header, then places each relocation
155 /// section at an 8-byte boundary, and returns the first offset past all of
156 /// them. The `plan` function calls it to place the section bytes and the
157 /// relocation sections before it places the tables that follow them. The
158 /// described sections go first so that each keeps the alignment its description
159 /// asked for. The function writes each relocation section's file offset into
160 /// `rela_starts`, or 0 for a section with no relocations, replacing the sort
161 /// positions `countRelocations` left there.
162 fn placePayloads(
163 description: Description,
164 section_offsets: []u64,
165 rela_counts: []const u64,
166 rela_starts: []u64,
167 ) Error!u64 {
168 var offset: u64 = ehdr_size;
169 for (description.sections, 0..) |section, index| {
170 offset = try alignForward(offset, section.alignment);
171 section_offsets[index] = offset;
172 offset = try add(offset, section.fileSize());
173 }
174 for (rela_counts, 0..) |count, index| {
175 if (count == 0) {
176 rela_starts[index] = 0;
177 continue;
178 }
179 offset = try alignForward(offset, 8);
180 rela_starts[index] = offset;
181 offset = try add(offset, try mul(count, rela_size));
182 }
183 return offset;
184 }
185
186 /// Counts the relocations aimed at each described section and returns how many
187 /// sections receive any. The `plan` function calls it once so that the writer
188 /// can emit every relocation section in a single walk. The function fills
189 /// `order` with relocation indices sorted by target section, keeping the input
190 /// order among relocations with the same target. `rela_starts` holds each
191 /// target's running position during this counting sort, and `placePayloads`
192 /// later overwrites it with file offsets. The function returns
193 /// `error.InvalidSectionIndex` for a target of 0 or one past the last described
194 /// section.
195 fn countRelocations(
196 description: Description,
197 rela_counts: []u64,
198 rela_starts: []u64,
199 order: []u64,
200 ) Error!usize {
201 @memset(rela_counts, 0);
202 for (description.relocations) |relocation| {
203 if (relocation.section == 0) return error.InvalidSectionIndex;
204 const target = @as(usize, relocation.section);
205 if (target > description.sections.len) return error.InvalidSectionIndex;
206 rela_counts[relocation.section - 1] += 1;
207 }
208
209 var running: u64 = 0;
210 var relocated_sections: usize = 0;
211 for (rela_counts, 0..) |count, index| {
212 rela_starts[index] = running;
213 running += count;
214 if (count != 0) relocated_sections += 1;
215 }
216 std.debug.assert(running == description.relocations.len);
217 for (description.relocations, 0..) |relocation, index| {
218 const target = relocation.section - 1;
219 order[@intCast(rela_starts[target])] = index;
220 rela_starts[target] += 1;
221 }
222 return relocated_sections;
223 }
224
225 fn validateSection(section: Section) Error!void {
226 const aligned = section.alignment == 0 or std.math.isPowerOfTwo(section.alignment);
227 if (!aligned) return error.InvalidAlignment;
228 if (section.isNoBits()) {
229 if (section.bytes.len != 0) return error.InvalidSize;
230 return;
231 }
232 if (section.size != 0 and section.size != section.bytes.len) return error.InvalidSize;
233 }
234
235 /// Computes the value of the symbol table header's `sh_info` field: the table
236 /// index one past the last local symbol. The `plan` function stores this result
237 /// so the writer can put it in the symbol table's header. Counting starts at
238 /// one because the writer places an empty entry at index 0. The function
239 /// returns `error.SymbolOrder` when a local symbol follows a global one.
240 fn firstGlobalIndex(symbols: []const Symbol) Error!u32 {
241 var locals: usize = 0;
242 var seen_global = false;
243 for (symbols) |symbol| {
244 if (!symbol.isLocal()) {
245 seen_global = true;
246 continue;
247 }
248 if (seen_global) return error.SymbolOrder;
249 locals += 1;
250 }
251 return @intCast(1 + locals);
252 }
253
254 fn symbolNameTableSize(symbols: []const Symbol) Error!u64 {
255 var size: u64 = 1;
256 for (symbols) |symbol| {
257 if (symbol.name.len == 0) continue;
258 size = try add(size, try add(symbol.name.len, 1));
259 }
260 if (size > std.math.maxInt(u32)) return error.SizeOverflow;
261 return size;
262 }
263
264 fn sectionNameTableSize(sections: []const Section, rela_counts: []const u64) Error!u64 {
265 var size: u64 = 1;
266 for (sections) |section| size = try add(size, try add(section.name.len, 1));
267 for (sections, 0..) |section, index| {
268 if (rela_counts[index] == 0) continue;
269 size = try add(size, try add(rela_name_prefix.len + section.name.len, 1));
270 }
271 size = try add(size, symtab_name.len + 1);
272 size = try add(size, strtab_name.len + 1);
273 size = try add(size, shstrtab_name.len + 1);
274 if (size > std.math.maxInt(u32)) return error.SizeOverflow;
275 return size;
276 }
277
278 fn add(left: u64, right: u64) Error!u64 {
279 return std.math.add(u64, left, right) catch error.SizeOverflow;
280 }
281
282 fn mul(left: u64, right: u64) Error!u64 {
283 return std.math.mul(u64, left, right) catch error.SizeOverflow;
284 }
285
286 /// Rounds `value` up to a multiple of `alignment`, and an alignment of 0 or 1
287 /// leaves it unchanged. `plan` and `placePayloads` use it for every aligned
288 /// offset. The function returns `error.SizeOverflow` when rounding up would
289 /// pass the largest 64-bit value.
290 fn alignForward(value: u64, alignment: u64) Error!u64 {
291 if (alignment <= 1) return value;
292 const mask = alignment - 1;
293 return (try add(value, mask)) & ~mask;
294 }
295
296 test "ELF object layout places every generated table after the described sections" {
297 const allocator = std.testing.allocator;
298 const description = Description{
299 .sections = &.{
300 Section.progbits(".text", "\x90\x90\x90\x90", std.elf.SHF_EXECINSTR, 16),
301 Section.progbits(".data", "\x00\x00\x00\x00\x00\x00\x00\x00", std.elf.SHF_WRITE, 8),
302 Section.nobits(".bss", 64, std.elf.SHF_WRITE, 8),
303 },
304 .symbols = &.{
305 Symbol.section(1),
306 Symbol.function("main", 1, 0, 4),
307 },
308 .relocations = &.{
309 model.Relocation.x86_64(2, 0, 2, .@"64", 0),
310 },
311 };
312
313 var layout = try Layout.plan(allocator, description);
314 defer layout.deinit(allocator);
315
316 try std.testing.expectEqual(@as(u16, 3 + 1 + fixed_section_count), layout.shnum);
317 try std.testing.expectEqual(@as(u16, 5), layout.symtab_index);
318 try std.testing.expectEqual(@as(u16, 6), layout.strtab_index);
319 try std.testing.expectEqual(@as(u16, 7), layout.shstrtab_index);
320 try std.testing.expectEqual(@as(u32, 2), layout.first_global);
321
322 try std.testing.expectEqual(@as(u64, 64), layout.section_offsets[0]);
323 try std.testing.expectEqual(@as(u64, 72), layout.section_offsets[1]);
324 try std.testing.expectEqual(@as(u64, 80), layout.section_offsets[2]);
325
326 try std.testing.expectEqual(@as(u64, 0), layout.rela_counts[0]);
327 try std.testing.expectEqual(@as(u64, 1), layout.rela_counts[1]);
328 try std.testing.expectEqual(@as(u64, 80), layout.rela_starts[1]);
329
330 try std.testing.expectEqual(@as(u64, 104), layout.symtab_offset);
331 try std.testing.expectEqual(@as(u64, 3 * sym_size), layout.symtab_size);
332 try std.testing.expectEqual(@as(u64, 176), layout.strtab_offset);
333 try std.testing.expectEqual(@as(u64, 6), layout.strtab_size);
334 try std.testing.expectEqual(@as(u64, 182), layout.shstrtab_offset);
335 try std.testing.expectEqual(@as(u64, 1 + 6 + 6 + 5 + 11 + 8 + 8 + 10), layout.shstrtab_size);
336 try std.testing.expectEqual(@as(u64, 240), layout.shoff);
337 try std.testing.expectEqual(@as(usize, 240 + 8 * shdr_size), layout.size);
338 }
339
340 test "ELF object layout orders relocations by target then by input" {
341 const allocator = std.testing.allocator;
342 const description = Description{
343 .sections = &.{
344 Section.progbits(".text", "\x90\x90\x90\x90\x90\x90\x90\x90", std.elf.SHF_EXECINSTR, 1),
345 Section.progbits(".data", "\x00\x00\x00\x00\x00\x00\x00\x00", std.elf.SHF_WRITE, 1),
346 },
347 .symbols = &.{Symbol.undefinedFunction("target")},
348 .relocations = &.{
349 model.Relocation.x86_64(2, 0, 1, .@"64", 0),
350 model.Relocation.x86_64(1, 1, 1, .PLT32, -4),
351 model.Relocation.x86_64(2, 8, 1, .@"64", 8),
352 model.Relocation.x86_64(1, 2, 1, .PC32, -4),
353 },
354 };
355
356 var layout = try Layout.plan(allocator, description);
357 defer layout.deinit(allocator);
358
359 try std.testing.expectEqualSlices(u64, &.{ 2, 2 }, layout.rela_counts);
360 try std.testing.expectEqualSlices(u64, &.{ 1, 3, 0, 2 }, layout.order);
361 try std.testing.expect(layout.rela_starts[0] < layout.rela_starts[1]);
362 }
363
364 test "ELF object layout refuses an alignment that is not a power of two" {
365 const description = Description{ .sections = &.{Section.progbits(".text", "\x90", 0, 3)} };
366 const planned = Layout.plan(std.testing.allocator, description);
367 try std.testing.expectError(error.InvalidAlignment, planned);
368 }
369
370 test "ELF object layout refuses a size that contradicts the section bytes" {
371 const stated = Description{
372 .sections = &.{.{ .name = ".text", .bytes = "\x90\x90", .size = 9 }},
373 };
374 try std.testing.expectError(error.InvalidSize, Layout.plan(std.testing.allocator, stated));
375
376 const occupied = Description{
377 .sections = &.{.{
378 .name = ".bss",
379 .section_type = std.elf.SHT_NOBITS,
380 .bytes = "\x00",
381 .size = 8,
382 }},
383 };
384 try std.testing.expectError(error.InvalidSize, Layout.plan(std.testing.allocator, occupied));
385 }
386
387 test "ELF object layout refuses a relocation against no described section" {
388 const sections = [_]Section{Section.progbits(".text", "\x90", 0, 1)};
389 const absent = Description{
390 .sections = §ions,
391 .relocations = &.{model.Relocation.x86_64(0, 0, 1, .@"64", 0)},
392 };
393 const missing = Layout.plan(std.testing.allocator, absent);
394 try std.testing.expectError(error.InvalidSectionIndex, missing);
395
396 const past_end = Description{
397 .sections = §ions,
398 .relocations = &.{model.Relocation.x86_64(2, 0, 1, .@"64", 0)},
399 };
400 const beyond = Layout.plan(std.testing.allocator, past_end);
401 try std.testing.expectError(error.InvalidSectionIndex, beyond);
402 }
403
404 test "ELF object layout refuses a local symbol after a global one" {
405 const description = Description{
406 .sections = &.{Section.progbits(".text", "\x90", 0, 1)},
407 .symbols = &.{ Symbol.function("main", 1, 0, 1), Symbol.section(1) },
408 };
409 try std.testing.expectError(error.SymbolOrder, Layout.plan(std.testing.allocator, description));
410 }
411
412 test "ELF object layout refuses more sections than a section index can name" {
413 const allocator = std.testing.allocator;
414 const sections = try allocator.alloc(Section, std.elf.SHN_LORESERVE);
415 defer allocator.free(sections);
416 for (sections) |*section| section.* = Section.progbits(".t", "\x90", 0, 1);
417
418 const planned = Layout.plan(allocator, .{ .sections = sections });
419 try std.testing.expectError(error.TooManySections, planned);
420 }
421
422 /// Returns a slice that claims 2^32 - 1 symbols over storage that holds one, so
423 /// the symbol limit test can pass `plan` a symbol count too large to store. The
424 /// `plan` function checks the count before it reads any entry, so the test
425 /// reads none of the missing elements and they need no memory.
426 fn overlongSymbols(storage: *const [1]Symbol) []const Symbol {
427 return @as([*]const Symbol, storage)[0..std.math.maxInt(u32)];
428 }
429
430 test "ELF object layout refuses more symbols than a table index can name" {
431 const storage = [_]Symbol{.{}};
432 const description = Description{ .sections = &.{}, .symbols = overlongSymbols(&storage) };
433
434 const planned = Layout.plan(std.testing.allocator, description);
435 try std.testing.expectError(error.TooManySymbols, planned);
436 }
437
438 test "ELF object layout refuses an alignment that leaves the address space" {
439 const huge = @as(u64, 1) << 63;
440 const description = Description{
441 .sections = &.{
442 .{ .name = ".a", .bytes = "\x90", .alignment = huge },
443 .{ .name = ".b", .bytes = "\x90", .alignment = huge },
444 },
445 };
446 const planned = Layout.plan(std.testing.allocator, description);
447 try std.testing.expectError(error.SizeOverflow, planned);
448 }
449
450 test "ELF object layout reports an allocator that cannot hold its scratch" {
451 const description = Description{ .sections = &.{Section.progbits(".text", "\x90", 0, 1)} };
452 const planned = Layout.plan(std.testing.failing_allocator, description);
453 try std.testing.expectError(error.OutOfMemory, planned);
454 }