lib/tldr/src/formats/elf/address/cache.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const root = @import("../../../root.zig");
3 const elf = @import("../root.zig");
4 const boundary = @import("boundary.zig");
5
6 const Allocator = std.mem.Allocator;
7 const model = root.model;
8 const Boundary = boundary.Boundary;
9 const BoundaryMap = std.HashMapUnmanaged(
10 Boundary,
11 u64,
12 Boundary.Context,
13 80,
14 );
15 const Range = struct {
16 start: u64,
17 stop: u64,
18 };
19 const ObjectFile = elf.parser.ObjectFile;
20 const ObjectLayout = elf.layout.ObjectLayout;
21 const OutputSection = elf.layout.OutputSection;
22 const contributionAt = elf.layout.contributionAt;
23 const foldedSection = elf.section_state.foldedSection;
24 const firstLoadSection = elf.program.firstLoadSection;
25 const mergeSectionLayout = elf.layout.mergeSection;
26 const sectionDiscarded = elf.section_state.sectionDiscarded;
27 const sectionIsAllocated = elf.format.sectionIsAllocated;
28 const sectionNameOrEmpty = elf.parser.sectionNameOrEmpty;
29
30 pub const Cache = struct {
31 pub const missing = std.math.maxInt(u64);
32
33 entries: []u64,
34 object_offsets: []usize,
35 synthetic_boundaries: BoundaryMap,
36
37 pub fn init(
38 allocator: Allocator,
39 objects: []const ObjectFile,
40 layouts: []const ObjectLayout,
41 output_sections: []const OutputSection,
42 ) model.Error!Cache {
43 const object_offsets = try allocator.alloc(usize, objects.len + 1);
44 errdefer allocator.free(object_offsets);
45
46 var total_symbol_count: usize = 0;
47 for (objects, 0..) |object, object_index| {
48 object_offsets[object_index] = total_symbol_count;
49 if (object.symbols.len > std.math.maxInt(usize) - total_symbol_count) {
50 return error.InvalidObject;
51 }
52 total_symbol_count += object.symbols.len;
53 }
54 object_offsets[objects.len] = total_symbol_count;
55
56 const entries = try allocator.alloc(u64, total_symbol_count);
57 errdefer allocator.free(entries);
58 @memset(entries, missing);
59
60 var synthetic_boundaries: BoundaryMap = .{};
61 errdefer synthetic_boundaries.deinit(allocator);
62 try collectSyntheticBoundaryAddresses(allocator, objects, layouts, output_sections, &synthetic_boundaries);
63
64 return .{
65 .entries = entries,
66 .object_offsets = object_offsets,
67 .synthetic_boundaries = synthetic_boundaries,
68 };
69 }
70
71 pub fn deinit(self: *Cache, allocator: Allocator) void {
72 allocator.free(self.entries);
73 allocator.free(self.object_offsets);
74 self.synthetic_boundaries.deinit(allocator);
75 self.* = undefined;
76 }
77
78 pub fn slot(self: *Cache, object_index: usize, symbol_index: usize) *u64 {
79 return &self.entries[self.object_offsets[object_index] + symbol_index];
80 }
81
82 pub fn syntheticBoundaryAddress(self: *const Cache, search_boundary: Boundary) ?u64 {
83 return self.synthetic_boundaries.get(search_boundary);
84 }
85 };
86
87 pub const Access = enum {
88 serial,
89 concurrent,
90 };
91
92 pub fn load(access: Access, slot: *const u64) u64 {
93 return switch (access) {
94 .serial => slot.*,
95 .concurrent => @atomicLoad(u64, slot, .monotonic),
96 };
97 }
98
99 pub fn store(access: Access, slot: *u64, address: u64) model.Error!u64 {
100 if (address == Cache.missing) return error.InvalidRange;
101 switch (access) {
102 .serial => slot.* = address,
103 .concurrent => @atomicStore(u64, slot, address, .monotonic),
104 }
105 return address;
106 }
107
108 fn collectSyntheticBoundaryAddresses(
109 allocator: Allocator,
110 objects: []const ObjectFile,
111 layouts: []const ObjectLayout,
112 output_sections: []const OutputSection,
113 addresses: *BoundaryMap,
114 ) model.Error!void {
115 for (objects) |object| {
116 for (object.symbols) |symbol| {
117 if (!symbol.isUndefined()) continue;
118 if (symbol.name.len == 0) continue;
119 const symbol_boundary = boundary.forSymbol(symbol.name) orelse continue;
120 if (addresses.contains(symbol_boundary)) continue;
121 const resolved = (try syntheticBoundaryAddress(objects, layouts, output_sections, symbol_boundary)) orelse continue;
122 if (resolved == Cache.missing) return error.InvalidRange;
123 try addresses.put(allocator, symbol_boundary, resolved);
124 }
125 }
126 }
127
128 fn syntheticBoundaryAddress(
129 objects: []const ObjectFile,
130 layouts: []const ObjectLayout,
131 output_sections: []const OutputSection,
132 search_boundary: Boundary,
133 ) model.Error!?u64 {
134 if (search_boundary.output_section) {
135 for (output_sections) |output| {
136 if (output.logicalSize() == 0) continue;
137 if (!std.mem.eql(u8, output.kind.name(), search_boundary.section_name)) continue;
138 return if (search_boundary.stop) output.address + output.logicalSize() else output.address;
139 }
140 if (search_boundary.optional) return syntheticBoundaryFallbackAddress(output_sections) orelse null;
141 return null;
142 }
143 var range: ?Range = null;
144 for (objects, 0..) |object, object_index| {
145 if (object_index >= layouts.len) return error.MissingSection;
146 const object_layout = layouts[object_index];
147 for (object.sections, 0..) |section, section_index| {
148 if (!sectionIsAllocated(section)) continue;
149 if (section.size == 0) continue;
150 if (sectionDiscarded(object, section_index)) continue;
151 if (foldedSection(object, section_index) != null) continue;
152 if (!boundary.sectionNameMatches(search_boundary, sectionNameOrEmpty(object, section_index))) continue;
153 const section_range = (try syntheticBoundaryRangeForSection(object_layout, output_sections, section_index)) orelse continue;
154 range = mergeSyntheticBoundaryRange(range, section_range);
155 }
156 }
157 const final_range = range orelse {
158 if (search_boundary.optional) {
159 const fallback = syntheticBoundaryFallbackAddress(output_sections) orelse return null;
160 return fallback;
161 }
162 return null;
163 };
164 return if (search_boundary.stop) final_range.stop else final_range.start;
165 }
166
167 fn syntheticBoundaryFallbackAddress(output_sections: []const OutputSection) ?u64 {
168 const first_load = firstLoadSection(output_sections) orelse return null;
169 return first_load.address - first_load.file_offset;
170 }
171
172 fn syntheticBoundaryRangeForSection(
173 object_layout: ObjectLayout,
174 output_sections: []const OutputSection,
175 section_index: usize,
176 ) model.Error!?Range {
177 if (mergeSectionLayout(object_layout, section_index)) |merge_section| {
178 return try syntheticBoundaryRangeForMergeSection(merge_section, output_sections);
179 }
180 const contribution = contributionAt(object_layout.sections, section_index) orelse return null;
181 const output = output_sections[contribution.outputIndex()];
182 const start = output.address + contribution.offset;
183 const stop = std.math.add(u64, start, contribution.size) catch return error.InvalidRange;
184 return .{ .start = start, .stop = stop };
185 }
186
187 fn syntheticBoundaryRangeForMergeSection(
188 merge_section: elf.layout.MergeSectionLayout,
189 output_sections: []const OutputSection,
190 ) model.Error!?Range {
191 var range: ?Range = null;
192 for (merge_section.pieces) |piece| {
193 if (!piece.contribution.isPresent()) continue;
194 const output = output_sections[piece.contribution.outputIndex()];
195 const start = output.address + piece.contribution.offset + piece.output_intra_offset;
196 const stop = std.math.add(u64, start, piece.size) catch return error.InvalidRange;
197 range = mergeSyntheticBoundaryRange(range, .{ .start = start, .stop = stop });
198 }
199 return range;
200 }
201
202 fn mergeSyntheticBoundaryRange(
203 current: ?Range,
204 update: Range,
205 ) Range {
206 const existing = current orelse return update;
207 return .{
208 .start = @min(existing.start, update.start),
209 .stop = @max(existing.stop, update.stop),
210 };
211 }