lib/choir/src/backends/machine.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const Allocator = std.mem.Allocator;
4
5 pub const CallRelocation = struct {
6 offset: usize,
7 target: []const u8,
8 };
9
10 pub const data_symbol_attr_names = struct {
11 pub const name = "choir.backend.data_symbol.name";
12 pub const bytes = "choir.backend.data_symbol.bytes";
13 pub const alignment = "choir.backend.data_symbol.alignment";
14 };
15
16 /// Largest alignment a data symbol may request.
17 /// A JIT data mapping starts on a page boundary, so an offset aligned within the mapping is also
18 /// aligned in memory for any alignment up to one page.
19 pub const max_data_alignment = 4096;
20
21 pub const DataSymbolError = error{ InvalidDataSymbol, ConflictingDataSymbol };
22
23 pub const DataSymbolBinding = enum {
24 local,
25 global,
26 };
27
28 /// The section a data symbol lands in.
29 pub const DataSection = enum {
30 /// Mapped read-only.
31 rodata,
32 /// Mapped writable, with the bytes the file carries.
33 data,
34 /// Mapped writable and zero, with no bytes in the file at all.
35 bss,
36
37 /// Reports whether the object file carries this section's bytes.
38 pub fn carriesBytes(self: DataSection) bool {
39 return self != .bss;
40 }
41 };
42
43 /// Storage that code addresses by name.
44 ///
45 /// A `.bss` symbol is the same kind as any other and differs only in where its bytes come from:
46 /// the loader supplies them, so the file carries none and `reserved_size` states the extent that
47 /// `bytes.len` cannot. Keeping one kind is what lets one `DataSymbolSet` hold every global a
48 /// module declares, whichever section it lands in.
49 pub const DataSymbol = struct {
50 name: []const u8,
51 /// Bytes the file carries verbatim. Empty exactly when the section is `.bss`.
52 bytes: []const u8 = &.{},
53 /// How many bytes the symbol occupies, when that is not the byte count.
54 ///
55 /// Absent means the size IS `bytes.len`, which is the only reading available for a section
56 /// the file carries bytes for. It is required for `.bss`, where there are no bytes to count,
57 /// and a zero here is a refusal rather than an empty symbol.
58 reserved_size: ?usize = null,
59 alignment: usize = 1,
60 binding: DataSymbolBinding = .local,
61 section: DataSection = .rodata,
62
63 /// The number of bytes the symbol occupies once loaded.
64 pub fn size(self: DataSymbol) usize {
65 return self.reserved_size orelse self.bytes.len;
66 }
67
68 /// Reports whether the symbol has a nonempty name, a power-of-two alignment no larger than
69 /// `max_data_alignment`, and content its section can hold: bytes for `.rodata` and `.data`,
70 /// a stated nonzero size and no bytes for `.bss`.
71 pub fn isValid(self: DataSymbol) bool {
72 if (self.name.len == 0) return false;
73 if (self.alignment == 0 or self.alignment > max_data_alignment) return false;
74 if (!std.math.isPowerOfTwo(self.alignment)) return false;
75 if (self.section.carriesBytes()) {
76 if (self.bytes.len == 0) return false;
77 if (self.reserved_size) |reserved| return reserved == self.bytes.len;
78 return true;
79 }
80 if (self.bytes.len != 0) return false;
81 const reserved = self.reserved_size orelse return false;
82 return reserved != 0;
83 }
84
85 pub fn eql(self: DataSymbol, other: DataSymbol) bool {
86 return std.mem.eql(u8, self.name, other.name) and
87 std.mem.eql(u8, self.bytes, other.bytes) and
88 self.size() == other.size() and
89 self.alignment == other.alignment and
90 self.binding == other.binding and
91 self.section == other.section;
92 }
93 };
94
95 /// Data symbols in first-insertion order, one per name.
96 /// The set borrows each symbol's name and bytes, so both must outlive the set.
97 pub const DataSymbolSet = struct {
98 symbols: std.StringArrayHashMapUnmanaged(DataSymbol) = .empty,
99
100 pub fn deinit(self: *DataSymbolSet, allocator: Allocator) void {
101 self.symbols.deinit(allocator);
102 self.* = undefined;
103 }
104
105 /// Adds `symbol` unless an equal symbol already holds its name.
106 /// Fails when `symbol` is invalid, or when its name already holds different bytes,
107 /// alignment, or binding.
108 pub fn put(
109 self: *DataSymbolSet,
110 allocator: Allocator,
111 symbol: DataSymbol,
112 ) (Allocator.Error || DataSymbolError)!void {
113 if (!symbol.isValid()) return error.InvalidDataSymbol;
114 const entry = try self.symbols.getOrPut(allocator, symbol.name);
115 if (!entry.found_existing) {
116 entry.value_ptr.* = symbol;
117 return;
118 }
119 if (!entry.value_ptr.eql(symbol)) return error.ConflictingDataSymbol;
120 }
121
122 pub fn items(self: *const DataSymbolSet) []const DataSymbol {
123 return self.symbols.values();
124 }
125
126 pub fn indexOf(self: *const DataSymbolSet, name: []const u8) ?usize {
127 return self.symbols.getIndex(name);
128 }
129
130 pub fn clearRetainingCapacity(self: *DataSymbolSet) void {
131 self.symbols.clearRetainingCapacity();
132 }
133 };
134
135 /// Places data symbols in order, each at the first offset after the previous symbol that its
136 /// alignment allows.
137 pub const DataLayout = struct {
138 offsets: []usize,
139 size: usize,
140 alignment: usize,
141
142 pub const Error = Allocator.Error || error{ InvalidDataSymbol, DataTooLarge };
143
144 pub fn init(allocator: Allocator, symbols: []const DataSymbol) Error!DataLayout {
145 const offsets = try allocator.alloc(usize, symbols.len);
146 errdefer allocator.free(offsets);
147 var size: usize = 0;
148 var alignment: usize = 1;
149 for (symbols, offsets) |symbol, *offset| {
150 if (!symbol.isValid()) return error.InvalidDataSymbol;
151 const mask = symbol.alignment - 1;
152 const padded = std.math.add(usize, size, mask) catch return error.DataTooLarge;
153 offset.* = padded & ~mask;
154 std.debug.assert(offset.* >= size);
155 std.debug.assert(std.mem.isAligned(offset.*, symbol.alignment));
156 size = std.math.add(usize, offset.*, symbol.size()) catch return error.DataTooLarge;
157 alignment = @max(alignment, symbol.alignment);
158 }
159 return .{ .offsets = offsets, .size = size, .alignment = alignment };
160 }
161
162 pub fn deinit(self: *DataLayout, allocator: Allocator) void {
163 allocator.free(self.offsets);
164 self.* = undefined;
165 }
166
167 /// Copies each symbol to its offset in `out` and zeroes the padding between symbols.
168 ///
169 /// A symbol whose section carries no bytes contributes none, and the memset above has
170 /// already left its run at the zero the loader would have supplied.
171 pub fn write(self: *const DataLayout, symbols: []const DataSymbol, out: []u8) void {
172 std.debug.assert(symbols.len == self.offsets.len);
173 std.debug.assert(out.len >= self.size);
174 @memset(out[0..self.size], 0);
175 for (symbols, self.offsets) |symbol, offset| {
176 std.debug.assert(offset + symbol.size() <= self.size);
177 @memcpy(out[offset..][0..symbol.bytes.len], symbol.bytes);
178 }
179 }
180 };
181
182 pub const DataRelocation = struct {
183 offset: usize,
184 target: []const u8,
185 addend: i64 = 0,
186 width_bits: u16 = 64,
187 };
188
189 pub const MachineCode = struct {
190 code: []u8,
191 relocations: []CallRelocation,
192 data_symbols: []DataSymbol = &.{},
193 data_relocations: []DataRelocation = &.{},
194
195 pub fn deinit(self: *MachineCode, allocator: Allocator) void {
196 allocator.free(self.code);
197 allocator.free(self.relocations);
198 allocator.free(self.data_symbols);
199 allocator.free(self.data_relocations);
200 }
201 };
202
203 test "data layouts pack symbols at their alignments" {
204 const allocator = std.testing.allocator;
205 const symbols = [_]DataSymbol{
206 .{ .name = "string", .bytes = "abc", .alignment = 8 },
207 .{ .name = "pair", .bytes = "xy", .alignment = 4 },
208 .{ .name = "page", .bytes = "z", .alignment = max_data_alignment },
209 };
210 var layout = try DataLayout.init(allocator, &symbols);
211 defer layout.deinit(allocator);
212 try std.testing.expectEqualSlices(usize, &.{ 0, 4, max_data_alignment }, layout.offsets);
213 try std.testing.expectEqual(@as(usize, max_data_alignment + 1), layout.size);
214 try std.testing.expectEqual(@as(usize, max_data_alignment), layout.alignment);
215
216 var out: [max_data_alignment + 1]u8 = @splat(0xaa);
217 layout.write(&symbols, &out);
218 try std.testing.expectEqualSlices(u8, "abc\x00xy", out[0..6]);
219 try std.testing.expect(std.mem.allEqual(u8, out[6..max_data_alignment], 0));
220 try std.testing.expectEqual(@as(u8, 'z'), out[max_data_alignment]);
221
222 var empty = try DataLayout.init(allocator, &.{});
223 defer empty.deinit(allocator);
224 try std.testing.expectEqual(@as(usize, 0), empty.size);
225 for ([_]usize{ 0, 3, 2 * max_data_alignment }) |alignment| {
226 const invalid = [_]DataSymbol{.{ .name = "bad", .bytes = "abc", .alignment = alignment }};
227 try std.testing.expectError(error.InvalidDataSymbol, DataLayout.init(allocator, &invalid));
228 }
229 }
230
231 test "data symbol sets keep one symbol per name" {
232 const allocator = std.testing.allocator;
233 var set: DataSymbolSet = .{};
234 defer set.deinit(allocator);
235 try set.put(allocator, .{ .name = "table", .bytes = "\x01\x02" });
236 try set.put(allocator, .{ .name = "other", .bytes = "\x03", .alignment = 8 });
237 try set.put(allocator, .{ .name = "table", .bytes = "\x01\x02" });
238 try std.testing.expectEqual(@as(usize, 2), set.items().len);
239 try std.testing.expectEqual(@as(?usize, 1), set.indexOf("other"));
240
241 const conflicts = [_]DataSymbol{
242 .{ .name = "table", .bytes = "\x01\x03" },
243 .{ .name = "table", .bytes = "\x01\x02", .alignment = 2 },
244 .{ .name = "table", .bytes = "\x01\x02", .binding = .global },
245 };
246 for (conflicts) |conflict| {
247 try std.testing.expectError(error.ConflictingDataSymbol, set.put(allocator, conflict));
248 }
249 const nameless = DataSymbol{ .name = "", .bytes = "\x01" };
250 try std.testing.expectError(error.InvalidDataSymbol, set.put(allocator, nameless));
251 try std.testing.expectEqual(@as(usize, 2), set.items().len);
252 try std.testing.expectEqualSlices(u8, "\x01\x02", set.items()[0].bytes);
253 }