lib/tldr/src/formats/elf/ehframe/record.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../../root.zig");
3 const elf = @import("../root.zig");
4
5 const model = root.model;
6 const Rela = elf.format.Rela;
7 const readU32 = elf.format.readU32;
8
9 pub const Cursor = struct {
10 relocations: []const Rela,
11 index: usize = 0,
12 sorted: bool,
13
14 pub fn init(relocations: []const Rela) Cursor {
15 return .{
16 .relocations = relocations,
17 .sorted = sortedByOffset(relocations),
18 };
19 }
20
21 pub fn at(self: *Cursor, offset: u64) ?Rela {
22 if (!self.sorted) return scanAt(self.relocations, offset);
23 while (self.index < self.relocations.len and self.relocations[self.index].offset < offset) self.index += 1;
24 var run = self.index;
25 while (run < self.relocations.len and self.relocations[run].offset == offset) : (run += 1) {
26 if (!elf.relocation.isNone(self.relocations[run])) return self.relocations[run];
27 }
28 return null;
29 }
30
31 pub fn window(self: *Cursor, start_offset: u64, end_offset: u64) ?[]const Rela {
32 if (!self.sorted) return null;
33 while (self.index < self.relocations.len and self.relocations[self.index].offset < start_offset) self.index += 1;
34 const window_start = self.index;
35 while (self.index < self.relocations.len and self.relocations[self.index].offset < end_offset) self.index += 1;
36 return self.relocations[window_start..self.index];
37 }
38 };
39
40 pub fn hasHeaderEntry(
41 bytes: []const u8,
42 input_offset: u64,
43 size: u64,
44 output_offset: u64,
45 cursor: *Cursor,
46 ) model.Error!bool {
47 if (size < 4) return error.InvalidObject;
48 const start: usize = @intCast(input_offset);
49 if (bytes.len - start < 4) return error.InvalidObject;
50 const record_length = readU32(bytes, start);
51 if (record_length == 0) return false;
52 if (record_length == 0xffffffff) return error.UnsupportedFormat;
53 if (size < @as(u64, record_length) + 4) return error.InvalidObject;
54 if (record_length < 4) return error.InvalidObject;
55 const record_id = readU32(bytes, start + 4);
56 if (record_id == 0) return false;
57 return cursor.at(output_offset + 8) != null;
58 }
59
60 fn sortedByOffset(relocations: []const Rela) bool {
61 if (relocations.len < 2) return true;
62 for (relocations[0 .. relocations.len - 1], relocations[1..]) |previous, next| {
63 if (next.offset < previous.offset) return false;
64 }
65 return true;
66 }
67
68 fn scanAt(relocations: []const Rela, offset: u64) ?Rela {
69 for (relocations) |relocation| {
70 if (relocation.offset == offset and !elf.relocation.isNone(relocation)) return relocation;
71 }
72 return null;
73 }
74
75 test "eh frame relocation cursor answers monotone queries" {
76 const none_type: u32 = @backingInt(std.elf.R_X86_64.NONE);
77 const pc32_type: u32 = @backingInt(std.elf.R_X86_64.PC32);
78 const relocations = [_]Rela{
79 .{ .offset = 8, .info = (@as(u64, 1) << 32) | pc32_type, .addend = 0 },
80 .{ .offset = 16, .info = (@as(u64, 2) << 32) | none_type, .addend = 0 },
81 .{ .offset = 16, .info = (@as(u64, 3) << 32) | pc32_type, .addend = 4 },
82 .{ .offset = 40, .info = (@as(u64, 4) << 32) | pc32_type, .addend = 0 },
83 };
84
85 var cursor = Cursor.init(&relocations);
86 try std.testing.expect(cursor.sorted);
87 try std.testing.expectEqual(@as(i64, 0), cursor.at(8).?.addend);
88 try std.testing.expectEqual(@as(u32, 3), cursor.at(16).?.symbolIndex());
89 try std.testing.expectEqual(@as(u32, 3), cursor.at(16).?.symbolIndex());
90 try std.testing.expect(cursor.at(24) == null);
91 try std.testing.expectEqual(@as(u32, 4), cursor.at(40).?.symbolIndex());
92 }
93
94 test "eh frame relocation cursor extracts consuming windows" {
95 const pc32_type: u32 = @backingInt(std.elf.R_X86_64.PC32);
96 const relocations = [_]Rela{
97 .{ .offset = 8, .info = (@as(u64, 1) << 32) | pc32_type, .addend = 0 },
98 .{ .offset = 24, .info = (@as(u64, 2) << 32) | pc32_type, .addend = 0 },
99 .{ .offset = 40, .info = (@as(u64, 3) << 32) | pc32_type, .addend = 0 },
100 };
101
102 var cursor = Cursor.init(&relocations);
103 const first = cursor.window(0, 32).?;
104 try std.testing.expectEqual(@as(usize, 2), first.len);
105 const second = cursor.window(32, 64).?;
106 try std.testing.expectEqual(@as(usize, 1), second.len);
107 try std.testing.expectEqual(@as(u32, 3), second[0].symbolIndex());
108 }
109
110 test "eh frame relocation cursor falls back on unsorted input" {
111 const pc32_type: u32 = @backingInt(std.elf.R_X86_64.PC32);
112 const relocations = [_]Rela{
113 .{ .offset = 40, .info = (@as(u64, 1) << 32) | pc32_type, .addend = 0 },
114 .{ .offset = 8, .info = (@as(u64, 2) << 32) | pc32_type, .addend = 0 },
115 };
116
117 var cursor = Cursor.init(&relocations);
118 try std.testing.expect(!cursor.sorted);
119 try std.testing.expect(cursor.window(0, 64) == null);
120 try std.testing.expectEqual(@as(u32, 2), cursor.at(8).?.symbolIndex());
121 try std.testing.expectEqual(@as(u32, 1), cursor.at(40).?.symbolIndex());
122 }