lib/tldr/src/formats/elf/relocation/decode.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const root = @import("../../../root.zig");
  3 const elf = @import("../root.zig");
  4 const relocation_counts_mod = @import("count.zig");
  5 const relocation_model = @import("model.zig");
  6 
  7 const Allocator = std.mem.Allocator;
  8 const model = root.model;
  9 const parallel = root.parallel;
 10 const format = elf.format;
 11 const rela_size = format.rela_size;
 12 const native_endian = format.native_endian;
 13 const parallel_relocation_threshold = format.parallel_relocation_threshold;
 14 const relocations_per_worker = format.relocations_per_worker;
 15 const SectionHeader = format.SectionHeader;
 16 const Rela = format.Rela;
 17 const sectionBytes = format.sectionBytes;
 18 const readU64 = format.readU64;
 19 const writeU64 = format.writeU64;
 20 const RelocationRange = relocation_model.RelocationRange;
 21 const ObjectParseOptions = relocation_model.ObjectParseOptions;
 22 const RelocationCounts = relocation_model.RelocationCounts;
 23 const ParsedRelocations = relocation_model.ParsedRelocations;
 24 const countRelocationsBySection = relocation_counts_mod.countRelocationsBySection;
 25 const relocationSectionSkipped = relocation_counts_mod.relocationSectionSkipped;
 26 const relocationSectionAllNone = relocation_counts_mod.relocationSectionAllNone;
 27 
 28 test "ELF parser skips debug relocation sections when stripping debug output" {
 29     const allocator = std.testing.allocator;
 30 
 31     var rela_bytes = @as([rela_size]u8, @splat(0));
 32     writeU64(&rela_bytes, 0, 1);
 33     writeU64(&rela_bytes, 8, @backingInt(std.elf.R_X86_64.@"64"));
 34     const section_names = "\x00.debug_info\x00";
 35 
 36     const sections = [_]SectionHeader{
 37         .{
 38             .name_offset = 0,
 39             .section_type = 0,
 40             .flags = 0,
 41             .address = 0,
 42             .offset = 0,
 43             .size = 0,
 44             .link = 0,
 45             .info = 0,
 46             .alignment = 0,
 47             .entry_size = 0,
 48         },
 49         .{
 50             .name_offset = 1,
 51             .section_type = std.elf.SHT_PROGBITS,
 52             .flags = 0,
 53             .address = 0,
 54             .offset = 0,
 55             .size = 8,
 56             .link = 0,
 57             .info = 0,
 58             .alignment = 0,
 59             .entry_size = 0,
 60         },
 61         .{
 62             .name_offset = 0,
 63             .section_type = std.elf.SHT_RELA,
 64             .flags = 0,
 65             .address = 0,
 66             .offset = 0,
 67             .size = rela_size,
 68             .link = 0,
 69             .info = 1,
 70             .alignment = 0,
 71             .entry_size = rela_size,
 72         },
 73     };
 74 
 75     var retained_counts = try countRelocationsBySection(allocator, &rela_bytes, &sections, section_names, 0, .{});
 76     defer retained_counts.deinit(allocator);
 77     try std.testing.expectEqual(@as(usize, 1), retained_counts.counts[1]);
 78 
 79     var stripped_counts = try countRelocationsBySection(allocator, &rela_bytes, &sections, section_names, 0, .{ .strip_debug = true });
 80     defer stripped_counts.deinit(allocator);
 81     try std.testing.expectEqual(@as(usize, 0), stripped_counts.counts[1]);
 82 
 83     var parsed = try parseRelocationsBySection(allocator, &rela_bytes, &sections, section_names, stripped_counts, .{ .strip_debug = true });
 84     defer parsed.deinit(allocator);
 85     try std.testing.expectEqual(@as(usize, 0), parsed.relocations.len);
 86     try std.testing.expectEqual(@as(usize, 0), parsed.ranges[1].count);
 87 }
 88 
 89 test "ELF parser combines duplicate relocation targets" {
 90     const allocator = std.testing.allocator;
 91 
 92     var rela_bytes = @as([(rela_size * 2)]u8, @splat(0));
 93     writeU64(&rela_bytes, 0, 1);
 94     writeU64(&rela_bytes, 8, @backingInt(std.elf.R_X86_64.@"64"));
 95     writeU64(&rela_bytes, rela_size, 2);
 96     writeU64(&rela_bytes, rela_size + 8, @backingInt(std.elf.R_X86_64.@"64"));
 97 
 98     const sections = [_]SectionHeader{
 99         .{
100             .name_offset = 0,
101             .section_type = 0,
102             .flags = 0,
103             .address = 0,
104             .offset = 0,
105             .size = 0,
106             .link = 0,
107             .info = 0,
108             .alignment = 0,
109             .entry_size = 0,
110         },
111         .{
112             .name_offset = 0,
113             .section_type = std.elf.SHT_PROGBITS,
114             .flags = std.elf.SHF_ALLOC,
115             .address = 0,
116             .offset = 0,
117             .size = 8,
118             .link = 0,
119             .info = 0,
120             .alignment = 0,
121             .entry_size = 0,
122         },
123         .{
124             .name_offset = 0,
125             .section_type = std.elf.SHT_RELA,
126             .flags = 0,
127             .address = 0,
128             .offset = 0,
129             .size = rela_size,
130             .link = 0,
131             .info = 1,
132             .alignment = 0,
133             .entry_size = rela_size,
134         },
135         .{
136             .name_offset = 0,
137             .section_type = std.elf.SHT_RELA,
138             .flags = 0,
139             .address = 0,
140             .offset = rela_size,
141             .size = rela_size,
142             .link = 0,
143             .info = 1,
144             .alignment = 0,
145             .entry_size = rela_size,
146         },
147     };
148 
149     var counts = try countRelocationsBySection(allocator, &rela_bytes, &sections, "", 0, .{});
150     defer counts.deinit(allocator);
151     try std.testing.expect(counts.duplicate_targets);
152 
153     var parsed = try parseRelocationsBySection(allocator, &rela_bytes, &sections, "", counts, .{});
154     defer parsed.deinit(allocator);
155     try std.testing.expect(parsed.owned);
156     try std.testing.expectEqual(@as(usize, 2), parsed.ranges[1].count);
157     try std.testing.expectEqual(@as(u64, 1), parsed.relocations[0].offset);
158     try std.testing.expectEqual(@as(u64, 2), parsed.relocations[1].offset);
159 }
160 
161 const RelocationDecodeJob = struct {
162     rela_bytes: []const u8,
163     rela_count: usize,
164     output_base: usize,
165     flat_start: usize,
166 };
167 
168 const ParallelDecodeContext = struct {
169     jobs: []const RelocationDecodeJob,
170     relocations: []Rela,
171 };
172 
173 fn decodeRelocationRange(job: RelocationDecodeJob, relocations: []Rela, lo: usize, hi: usize) void {
174     if (native_endian == .little) {
175         const out = relocations[job.output_base + lo ..][0 .. hi - lo];
176         const bytes_start = lo * rela_size;
177         const bytes_end = hi * rela_size;
178         @memcpy(std.mem.sliceAsBytes(out), job.rela_bytes[bytes_start..bytes_end]);
179         return;
180     }
181 
182     var index = lo;
183     while (index < hi) : (index += 1) {
184         const raw = job.rela_bytes[index * rela_size ..][0..rela_size];
185         relocations[job.output_base + index] = .{
186             .offset = readU64(raw, 0),
187             .info = readU64(raw, 8),
188             .addend = @bitCast(readU64(raw, 16)),
189         };
190     }
191 }
192 
193 fn decodeRelocationChunk(context: *ParallelDecodeContext, worker: usize, start: usize, end: usize) void {
194     _ = worker;
195     for (context.jobs) |job| {
196         const job_end = job.flat_start + job.rela_count;
197         if (job_end <= start) continue;
198         if (job.flat_start >= end) break;
199         const lo = if (start > job.flat_start) start - job.flat_start else 0;
200         const hi = if (end < job_end) end - job.flat_start else job.rela_count;
201         decodeRelocationRange(job, context.relocations, lo, hi);
202     }
203 }
204 
205 pub fn parseRelocationsBySection(
206     allocator: Allocator,
207     bytes: []const u8,
208     sections: []const SectionHeader,
209     section_names: []const u8,
210     relocation_counts: RelocationCounts,
211     parse_options: ObjectParseOptions,
212 ) model.Error!ParsedRelocations {
213     if (relocation_counts.counts.len == 0) {
214         return .{
215             .relocations = &.{},
216             .owned = false,
217             .ranges = &.{},
218         };
219     }
220 
221     const relocation_ranges = try allocator.alloc(RelocationRange, sections.len);
222     errdefer allocator.free(relocation_ranges);
223     var relocation_count: usize = 0;
224     for (relocation_ranges, 0..) |*range, section_index| {
225         const count = relocation_counts.counts[section_index];
226         range.* = .{
227             .start = relocation_count,
228             .count = count,
229         };
230         if (count > std.math.maxInt(usize) - relocation_count) return error.InvalidObject;
231         relocation_count += count;
232     }
233     if (relocation_count == 0) {
234         return .{
235             .relocations = &.{},
236             .owned = false,
237             .ranges = relocation_ranges,
238         };
239     }
240 
241     if (try borrowSingleRelocationSection(bytes, sections, section_names, relocation_count, parse_options)) |relocations| {
242         return .{
243             .relocations = relocations,
244             .owned = false,
245             .ranges = relocation_ranges,
246         };
247     }
248 
249     const relocations = try allocator.alloc(Rela, relocation_count);
250     errdefer allocator.free(relocations);
251 
252     var jobs = std.ArrayListUnmanaged(RelocationDecodeJob).empty;
253     defer jobs.deinit(allocator);
254     var write_offsets: []usize = &.{};
255     defer if (write_offsets.len != 0) allocator.free(write_offsets);
256     if (relocation_counts.duplicate_targets) {
257         write_offsets = try allocator.alloc(usize, sections.len);
258         for (write_offsets, 0..) |*offset, section_index| {
259             offset.* = relocation_ranges[section_index].start;
260         }
261     }
262 
263     var flat_total: usize = 0;
264     for (sections) |section| {
265         if (section.section_type != std.elf.SHT_RELA) continue;
266         if (try relocationSectionSkipped(section, sections, section_names, parse_options)) continue;
267         const rela_bytes = try sectionBytes(bytes, section);
268         if (relocationSectionAllNone(rela_bytes)) continue;
269         const rela_count = rela_bytes.len / rela_size;
270         const output_base = if (relocation_counts.duplicate_targets) blk: {
271             const base = write_offsets[section.info];
272             write_offsets[section.info] += rela_count;
273             break :blk base;
274         } else relocation_ranges[section.info].start;
275         try jobs.append(allocator, .{
276             .rela_bytes = rela_bytes,
277             .rela_count = rela_count,
278             .output_base = output_base,
279             .flat_start = flat_total,
280         });
281         flat_total += rela_count;
282     }
283 
284     const requested_workers = flat_total / relocations_per_worker;
285     const workers = if (flat_total >= parallel_relocation_threshold)
286         parallel.chooseWorkers(flat_total, requested_workers)
287     else
288         1;
289 
290     if (workers <= 1) {
291         for (jobs.items) |job| decodeRelocationRange(job, relocations, 0, job.rela_count);
292     } else {
293         var context = ParallelDecodeContext{ .jobs = jobs.items, .relocations = relocations };
294         parallel.forChunks(flat_total, requested_workers, &context, decodeRelocationChunk);
295     }
296 
297     return .{
298         .relocations = relocations,
299         .owned = true,
300         .ranges = relocation_ranges,
301     };
302 }
303 
304 fn borrowSingleRelocationSection(
305     bytes: []const u8,
306     sections: []const SectionHeader,
307     section_names: []const u8,
308     relocation_count: usize,
309     parse_options: ObjectParseOptions,
310 ) model.Error!?[]const Rela {
311     if (native_endian != .little) return null;
312 
313     var found: ?SectionHeader = null;
314     for (sections) |section| {
315         if (section.section_type != std.elf.SHT_RELA) continue;
316         if (try relocationSectionSkipped(section, sections, section_names, parse_options)) continue;
317         if (section.size == 0) continue;
318         const rela_bytes = try sectionBytes(bytes, section);
319         if (relocationSectionAllNone(rela_bytes)) continue;
320         if (found != null) return null;
321         found = section;
322     }
323     const section = found orelse return null;
324     if (section.size / rela_size != relocation_count) return null;
325 
326     const rela_bytes = try sectionBytes(bytes, section);
327     if (!std.mem.isAligned(@intFromPtr(rela_bytes.ptr), @alignOf(Rela))) return null;
328     return @alignCast(std.mem.bytesAsSlice(Rela, rela_bytes));
329 }