1entries: std.ArrayList(Entry) = .empty,
2buffer: std.ArrayList(u8) = .empty,
3
4pub const Entry = struct {
5 offset: u64,
6 segment_id: u8,
7
8 pub fn lessThan(ctx: void, entry: Entry, other: Entry) bool {
9 _ = ctx;
10 if (entry.segment_id == other.segment_id) {
11 return entry.offset < other.offset;
12 }
13 return entry.segment_id < other.segment_id;
14 }
15};
16
17pub fn deinit(rebase: *Rebase, gpa: Allocator) void {
18 rebase.entries.deinit(gpa);
19 rebase.buffer.deinit(gpa);
20}
21
22pub fn updateSize(rebase: *Rebase, macho_file: *MachO) !void {
23 const tracy = trace(@src());
24 defer tracy.end();
25
26 const gpa = macho_file.base.comp.gpa;
27
28 var objects = try std.array_list.Managed(File.Index).initCapacity(gpa, macho_file.objects.items.len + 2);
29 defer objects.deinit();
30 objects.appendSliceAssumeCapacity(macho_file.objects.items);
31 if (macho_file.getZigObject()) |obj| objects.appendAssumeCapacity(obj.index);
32 if (macho_file.getInternalObject()) |obj| objects.appendAssumeCapacity(obj.index);
33
34 for (objects.items) |index| {
35 const file = macho_file.getFile(index).?;
36 for (file.getAtoms()) |atom_index| {
37 const atom = file.getAtom(atom_index) orelse continue;
38 if (!atom.isAlive()) continue;
39 if (atom.getInputSection(macho_file).isZerofill()) continue;
40 const atom_addr = atom.getAddress(macho_file);
41 const seg_id = macho_file.sections.items(.segment_id)[atom.out_n_sect];
42 const seg = macho_file.segments.items[seg_id];
43 for (atom.getRelocs(macho_file)) |rel| {
44 if (rel.type != .unsigned or rel.meta.length != 3) continue;
45 if (rel.tag == .@"extern") {
46 const sym = rel.getTargetSymbol(atom.*, macho_file);
47 if (sym.isTlvInit(macho_file)) continue;
48 if (sym.flags.import) continue;
49 }
50 const rel_offset = rel.offset - atom.off;
51 try rebase.entries.append(gpa, .{
52 .offset = atom_addr + rel_offset - seg.vmaddr,
53 .segment_id = seg_id,
54 });
55 }
56 }
57 }
58
59 if (macho_file.got_sect_index) |sid| {
60 const seg_id = macho_file.sections.items(.segment_id)[sid];
61 const seg = macho_file.segments.items[seg_id];
62 for (macho_file.got.symbols.items, 0..) |ref, idx| {
63 const sym = ref.getSymbol(macho_file).?;
64 const addr = macho_file.got.getAddress(@intCast(idx), macho_file);
65 if (!sym.flags.import) {
66 try rebase.entries.append(gpa, .{
67 .offset = addr - seg.vmaddr,
68 .segment_id = seg_id,
69 });
70 }
71 }
72 }
73
74 if (macho_file.la_symbol_ptr_sect_index) |sid| {
75 const sect = macho_file.sections.items(.header)[sid];
76 const seg_id = macho_file.sections.items(.segment_id)[sid];
77 const seg = macho_file.segments.items[seg_id];
78 for (macho_file.stubs.symbols.items, 0..) |ref, idx| {
79 const sym = ref.getSymbol(macho_file).?;
80 const addr = sect.addr + idx * @sizeOf(u64);
81 const rebase_entry = Rebase.Entry{
82 .offset = addr - seg.vmaddr,
83 .segment_id = seg_id,
84 };
85 if ((sym.flags.import and !sym.flags.weak) or !sym.flags.import) {
86 try rebase.entries.append(gpa, rebase_entry);
87 }
88 }
89 }
90
91 if (macho_file.tlv_ptr_sect_index) |sid| {
92 const seg_id = macho_file.sections.items(.segment_id)[sid];
93 const seg = macho_file.segments.items[seg_id];
94 for (macho_file.tlv_ptr.symbols.items, 0..) |ref, idx| {
95 const sym = ref.getSymbol(macho_file).?;
96 const addr = macho_file.tlv_ptr.getAddress(@intCast(idx), macho_file);
97 if (!sym.flags.import) {
98 try rebase.entries.append(gpa, .{
99 .offset = addr - seg.vmaddr,
100 .segment_id = seg_id,
101 });
102 }
103 }
104 }
105
106 try rebase.finalize(gpa);
107 macho_file.dyld_info_cmd.rebase_size = mem.alignForward(u32, @intCast(rebase.buffer.items.len), @alignOf(u64));
108}
109
110fn finalize(rebase: *Rebase, gpa: Allocator) !void {
111 if (rebase.entries.items.len == 0) return;
112
113 log.debug("rebase opcodes", .{});
114
115 std.mem.sort(Entry, rebase.entries.items, {}, Entry.lessThan);
116
117 var allocating: std.Io.Writer.Allocating = .fromArrayList(gpa, &rebase.buffer);
118 defer rebase.buffer = allocating.toArrayList();
119 const writer = &allocating.writer;
120
121 try setTypePointer(writer);
122
123 var start: usize = 0;
124 var seg_id: ?u8 = null;
125 for (rebase.entries.items, 0..) |entry, i| {
126 if (seg_id != null and seg_id.? == entry.segment_id) continue;
127 try finalizeSegment(rebase.entries.items[start..i], writer);
128 seg_id = entry.segment_id;
129 start = i;
130 }
131
132 try finalizeSegment(rebase.entries.items[start..], writer);
133 try done(writer);
134}
135
136fn finalizeSegment(entries: []const Entry, writer: anytype) !void {
137 if (entries.len == 0) return;
138
139 const segment_id = entries[0].segment_id;
140 var offset = entries[0].offset;
141 try setSegmentOffset(segment_id, offset, writer);
142
143 var count: usize = 0;
144 var skip: u64 = 0;
145 var state: enum {
146 start,
147 times,
148 times_skip,
149 } = .times;
150
151 var i: usize = 0;
152 while (i < entries.len) : (i += 1) {
153 log.debug("{x}, {d}, {x}, {s}", .{ offset, count, skip, @tagName(state) });
154 const current_offset = entries[i].offset;
155 log.debug(" => {x}", .{current_offset});
156 switch (state) {
157 .start => {
158 if (offset < current_offset) {
159 const delta = current_offset - offset;
160 try addAddr(delta, writer);
161 offset += delta;
162 }
163 state = .times;
164 offset += @sizeOf(u64);
165 count = 1;
166 },
167 .times => {
168 const delta = current_offset - offset;
169 if (delta == 0) {
170 count += 1;
171 offset += @sizeOf(u64);
172 continue;
173 }
174 if (count == 1) {
175 state = .times_skip;
176 skip = delta;
177 offset += skip;
178 i -= 1;
179 } else {
180 try rebaseTimes(count, writer);
181 state = .start;
182 i -= 1;
183 }
184 },
185 .times_skip => {
186 if (current_offset < offset) {
187 count -= 1;
188 if (count == 1) {
189 try rebaseAddAddr(skip, writer);
190 } else {
191 try rebaseTimesSkip(count, skip, writer);
192 }
193 state = .start;
194 offset = offset - (@sizeOf(u64) + skip);
195 i -= 2;
196 continue;
197 }
198
199 const delta = current_offset - offset;
200 if (delta == 0) {
201 count += 1;
202 offset += @sizeOf(u64) + skip;
203 } else {
204 try rebaseTimesSkip(count, skip, writer);
205 state = .start;
206 i -= 1;
207 }
208 },
209 }
210 }
211
212 switch (state) {
213 .start => unreachable,
214 .times => {
215 try rebaseTimes(count, writer);
216 },
217 .times_skip => {
218 try rebaseTimesSkip(count, skip, writer);
219 },
220 }
221}
222
223fn setTypePointer(writer: anytype) !void {
224 log.debug(">>> set type: {d}", .{macho.REBASE_TYPE_POINTER});
225 try writer.writeByte(macho.REBASE_OPCODE_SET_TYPE_IMM | @as(u4, @truncate(macho.REBASE_TYPE_POINTER)));
226}
227
228fn setSegmentOffset(segment_id: u8, offset: u64, writer: anytype) !void {
229 log.debug(">>> set segment: {d} and offset: {x}", .{ segment_id, offset });
230 try writer.writeByte(macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | @as(u4, @truncate(segment_id)));
231 try writer.writeUleb128(offset);
232}
233
234fn rebaseAddAddr(addr: u64, writer: anytype) !void {
235 log.debug(">>> rebase with add: {x}", .{addr});
236 try writer.writeByte(macho.REBASE_OPCODE_DO_REBASE_ADD_ADDR_ULEB);
237 try writer.writeUleb128(addr);
238}
239
240fn rebaseTimes(count: usize, writer: anytype) !void {
241 log.debug(">>> rebase with count: {d}", .{count});
242 if (count <= 0xf) {
243 try writer.writeByte(macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | @as(u4, @truncate(count)));
244 } else {
245 try writer.writeByte(macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES);
246 try writer.writeUleb128(count);
247 }
248}
249
250fn rebaseTimesSkip(count: usize, skip: u64, writer: anytype) !void {
251 log.debug(">>> rebase with count: {d} and skip: {x}", .{ count, skip });
252 try writer.writeByte(macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB);
253 try writer.writeUleb128(count);
254 try writer.writeUleb128(skip);
255}
256
257fn addAddr(addr: u64, writer: anytype) !void {
258 log.debug(">>> add: {x}", .{addr});
259 if (std.mem.isAlignedGeneric(u64, addr, @sizeOf(u64))) {
260 const imm = @divExact(addr, @sizeOf(u64));
261 if (imm <= 0xf) {
262 try writer.writeByte(macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | @as(u4, @truncate(imm)));
263 return;
264 }
265 }
266 try writer.writeByte(macho.REBASE_OPCODE_ADD_ADDR_ULEB);
267 try writer.writeUleb128(addr);
268}
269
270fn done(writer: anytype) !void {
271 log.debug(">>> done", .{});
272 try writer.writeByte(macho.REBASE_OPCODE_DONE);
273}
274
275pub fn write(rebase: Rebase, writer: anytype) !void {
276 try writer.writeAll(rebase.buffer.items);
277}
278
279test "rebase - no entries" {
280 const gpa = testing.allocator;
281
282 var rebase = Rebase{};
283 defer rebase.deinit(gpa);
284
285 try rebase.finalize(gpa);
286 try testing.expectEqual(0, rebase.buffer.items.len);
287}
288
289test "rebase - single entry" {
290 const gpa = testing.allocator;
291
292 var rebase = Rebase{};
293 defer rebase.deinit(gpa);
294 try rebase.entries.append(gpa, .{
295 .segment_id = 1,
296 .offset = 0x10,
297 });
298 try rebase.finalize(gpa);
299 try testing.expectEqualSlices(u8, &[_]u8{
300 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
301 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
302 0x10,
303 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 1,
304 macho.REBASE_OPCODE_DONE,
305 }, rebase.buffer.items);
306}
307
308test "rebase - emitTimes - IMM" {
309 const gpa = testing.allocator;
310
311 var rebase = Rebase{};
312 defer rebase.deinit(gpa);
313
314 var i: u64 = 0;
315 while (i < 10) : (i += 1) {
316 try rebase.entries.append(gpa, .{
317 .segment_id = 1,
318 .offset = i * @sizeOf(u64),
319 });
320 }
321
322 try rebase.finalize(gpa);
323
324 try testing.expectEqualSlices(u8, &[_]u8{
325 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
326 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
327 0x0,
328 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 10,
329 macho.REBASE_OPCODE_DONE,
330 }, rebase.buffer.items);
331}
332
333test "rebase - emitTimes - ULEB" {
334 const gpa = testing.allocator;
335
336 var rebase = Rebase{};
337 defer rebase.deinit(gpa);
338
339 var i: u64 = 0;
340 while (i < 100) : (i += 1) {
341 try rebase.entries.append(gpa, .{
342 .segment_id = 1,
343 .offset = i * @sizeOf(u64),
344 });
345 }
346
347 try rebase.finalize(gpa);
348
349 try testing.expectEqualSlices(u8, &[_]u8{
350 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
351 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
352 0x0,
353 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES,
354 0x64,
355 macho.REBASE_OPCODE_DONE,
356 }, rebase.buffer.items);
357}
358
359test "rebase - emitTimes followed by addAddr followed by emitTimes" {
360 const gpa = testing.allocator;
361
362 var rebase = Rebase{};
363 defer rebase.deinit(gpa);
364
365 var offset: u64 = 0;
366 var i: u64 = 0;
367 while (i < 15) : (i += 1) {
368 try rebase.entries.append(gpa, .{
369 .segment_id = 1,
370 .offset = offset,
371 });
372 offset += @sizeOf(u64);
373 }
374
375 offset += @sizeOf(u64);
376
377 try rebase.entries.append(gpa, .{
378 .segment_id = 1,
379 .offset = offset,
380 });
381
382 try rebase.finalize(gpa);
383
384 try testing.expectEqualSlices(u8, &[_]u8{
385 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
386 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
387 0x0,
388 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 15,
389 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 1,
390 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 1,
391 macho.REBASE_OPCODE_DONE,
392 }, rebase.buffer.items);
393}
394
395test "rebase - emitTimesSkip" {
396 const gpa = testing.allocator;
397
398 var rebase = Rebase{};
399 defer rebase.deinit(gpa);
400
401 var offset: u64 = 0;
402 var i: u64 = 0;
403 while (i < 15) : (i += 1) {
404 try rebase.entries.append(gpa, .{
405 .segment_id = 1,
406 .offset = offset,
407 });
408 offset += 2 * @sizeOf(u64);
409 }
410
411 try rebase.finalize(gpa);
412
413 try testing.expectEqualSlices(u8, &[_]u8{
414 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
415 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
416 0x0,
417 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
418 0xf,
419 0x8,
420 macho.REBASE_OPCODE_DONE,
421 }, rebase.buffer.items);
422}
423
424test "rebase - complex" {
425 const gpa = testing.allocator;
426
427 var rebase = Rebase{};
428 defer rebase.deinit(gpa);
429
430 try rebase.entries.append(gpa, .{
431 .segment_id = 1,
432 .offset = 0,
433 });
434 try rebase.entries.append(gpa, .{
435 .segment_id = 1,
436 .offset = 0x10,
437 });
438 try rebase.entries.append(gpa, .{
439 .segment_id = 1,
440 .offset = 0x40,
441 });
442 try rebase.entries.append(gpa, .{
443 .segment_id = 1,
444 .offset = 0x48,
445 });
446 try rebase.entries.append(gpa, .{
447 .segment_id = 1,
448 .offset = 0x50,
449 });
450 try rebase.entries.append(gpa, .{
451 .segment_id = 1,
452 .offset = 0x58,
453 });
454 try rebase.entries.append(gpa, .{
455 .segment_id = 1,
456 .offset = 0x70,
457 });
458 try rebase.finalize(gpa);
459
460 try testing.expectEqualSlices(u8, &[_]u8{
461 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
462 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
463 0x0,
464 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
465 0x2,
466 0x8,
467 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 4,
468 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 4,
469 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 2,
470 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 1,
471 macho.REBASE_OPCODE_DONE,
472 }, rebase.buffer.items);
473}
474
475test "rebase - complex 2" {
476 const gpa = testing.allocator;
477
478 var rebase = Rebase{};
479 defer rebase.deinit(gpa);
480
481 try rebase.entries.append(gpa, .{
482 .segment_id = 1,
483 .offset = 0,
484 });
485 try rebase.entries.append(gpa, .{
486 .segment_id = 1,
487 .offset = 0x10,
488 });
489 try rebase.entries.append(gpa, .{
490 .segment_id = 1,
491 .offset = 0x28,
492 });
493 try rebase.entries.append(gpa, .{
494 .segment_id = 1,
495 .offset = 0x48,
496 });
497 try rebase.entries.append(gpa, .{
498 .segment_id = 1,
499 .offset = 0x78,
500 });
501 try rebase.entries.append(gpa, .{
502 .segment_id = 1,
503 .offset = 0xb8,
504 });
505 try rebase.entries.append(gpa, .{
506 .segment_id = 2,
507 .offset = 0x0,
508 });
509 try rebase.entries.append(gpa, .{
510 .segment_id = 2,
511 .offset = 0x8,
512 });
513 try rebase.entries.append(gpa, .{
514 .segment_id = 2,
515 .offset = 0x10,
516 });
517 try rebase.entries.append(gpa, .{
518 .segment_id = 2,
519 .offset = 0x18,
520 });
521 try rebase.entries.append(gpa, .{
522 .segment_id = 3,
523 .offset = 0x0,
524 });
525 try rebase.entries.append(gpa, .{
526 .segment_id = 3,
527 .offset = 0x20,
528 });
529 try rebase.entries.append(gpa, .{
530 .segment_id = 3,
531 .offset = 0x40,
532 });
533 try rebase.entries.append(gpa, .{
534 .segment_id = 3,
535 .offset = 0x60,
536 });
537 try rebase.entries.append(gpa, .{
538 .segment_id = 3,
539 .offset = 0x68,
540 });
541 try rebase.finalize(gpa);
542
543 try testing.expectEqualSlices(u8, &[_]u8{
544 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
545 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
546 0x0,
547 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
548 0x2,
549 0x8,
550 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 1,
551 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
552 0x2,
553 0x18,
554 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 2,
555 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
556 0x2,
557 0x38,
558 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 2,
559 0x0,
560 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 4,
561 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 3,
562 0x0,
563 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
564 0x3,
565 0x18,
566 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 2,
567 macho.REBASE_OPCODE_DONE,
568 }, rebase.buffer.items);
569}
570
571test "rebase - composite" {
572 const gpa = testing.allocator;
573
574 var rebase = Rebase{};
575 defer rebase.deinit(gpa);
576
577 try rebase.entries.append(gpa, .{
578 .segment_id = 1,
579 .offset = 0x8,
580 });
581 try rebase.entries.append(gpa, .{
582 .segment_id = 1,
583 .offset = 0x38,
584 });
585 try rebase.entries.append(gpa, .{
586 .segment_id = 1,
587 .offset = 0xa0,
588 });
589 try rebase.entries.append(gpa, .{
590 .segment_id = 1,
591 .offset = 0xa8,
592 });
593 try rebase.entries.append(gpa, .{
594 .segment_id = 1,
595 .offset = 0xb0,
596 });
597 try rebase.entries.append(gpa, .{
598 .segment_id = 1,
599 .offset = 0xc0,
600 });
601 try rebase.entries.append(gpa, .{
602 .segment_id = 1,
603 .offset = 0xc8,
604 });
605 try rebase.entries.append(gpa, .{
606 .segment_id = 1,
607 .offset = 0xd0,
608 });
609 try rebase.entries.append(gpa, .{
610 .segment_id = 1,
611 .offset = 0xd8,
612 });
613 try rebase.entries.append(gpa, .{
614 .segment_id = 1,
615 .offset = 0xe0,
616 });
617 try rebase.entries.append(gpa, .{
618 .segment_id = 1,
619 .offset = 0xe8,
620 });
621 try rebase.entries.append(gpa, .{
622 .segment_id = 1,
623 .offset = 0xf0,
624 });
625 try rebase.entries.append(gpa, .{
626 .segment_id = 1,
627 .offset = 0xf8,
628 });
629 try rebase.entries.append(gpa, .{
630 .segment_id = 1,
631 .offset = 0x108,
632 });
633 try rebase.finalize(gpa);
634
635 try testing.expectEqualSlices(u8, &[_]u8{
636 macho.REBASE_OPCODE_SET_TYPE_IMM | macho.REBASE_TYPE_POINTER,
637 macho.REBASE_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB | 1,
638 0x8,
639 macho.REBASE_OPCODE_DO_REBASE_ULEB_TIMES_SKIPPING_ULEB,
640 0x2,
641 0x28,
642 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 7,
643 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 3,
644 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 1,
645 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 8,
646 macho.REBASE_OPCODE_ADD_ADDR_IMM_SCALED | 1,
647 macho.REBASE_OPCODE_DO_REBASE_IMM_TIMES | 1,
648 macho.REBASE_OPCODE_DONE,
649 }, rebase.buffer.items);
650}
651
652const std = @import("std");
653const assert = std.debug.assert;
654const log = std.log.scoped(.link_dyld_info);
655const macho = std.macho;
656const mem = std.mem;
657const testing = std.testing;
658const Allocator = mem.Allocator;
659const Writer = std.Io.Writer;
660
661const trace = @import("../../../tracy.zig").trace;
662const File = @import("../file.zig").File;
663const MachO = @import("../../MachO.zig");
664const Rebase = @This();