1pub fn gcAtoms(elf_file: *Elf) !void {
2 const comp = elf_file.base.comp;
3 const gpa = comp.gpa;
4 var roots = std.array_list.Managed(*Atom).init(gpa);
5 defer roots.deinit();
6 try collectRoots(&roots, elf_file);
7 mark(roots, elf_file);
8 prune(elf_file);
9}
10
11fn collectRoots(roots: *std.array_list.Managed(*Atom), elf_file: *Elf) !void {
12 if (elf_file.linkerDefinedPtr()) |obj| {
13 if (obj.entrySymbol(elf_file)) |sym| {
14 try markSymbol(sym, roots, elf_file);
15 }
16 }
17
18 if (elf_file.zigObjectPtr()) |zo| {
19 for (0..zo.global_symbols.items.len) |i| {
20 const ref = zo.resolveSymbol(@intCast(i | ZigObject.global_symbol_bit), elf_file);
21 const sym = elf_file.symbol(ref) orelse continue;
22 if (sym.file(elf_file).?.index() != zo.index) continue;
23 if (sym.flags.@"export") {
24 try markSymbol(sym, roots, elf_file);
25 }
26 }
27 }
28
29 for (elf_file.objects.items) |index| {
30 const object = elf_file.file(index).?.object;
31 for (0..object.globals().len) |i| {
32 const ref = object.resolveSymbol(@intCast(i), elf_file);
33 const sym = elf_file.symbol(ref) orelse continue;
34 if (sym.file(elf_file).?.index() != object.index) continue;
35 if (sym.flags.@"export") {
36 try markSymbol(sym, roots, elf_file);
37 }
38 }
39 }
40
41 const atomRoots = struct {
42 fn atomRoots(file: File, rs: anytype, ef: *Elf) !void {
43 for (file.atoms()) |atom_index| {
44 const atom = file.atom(atom_index) orelse continue;
45 if (!atom.alive) continue;
46
47 const shdr = atom.inputShdr(ef);
48 const name = atom.name(ef);
49 const is_gc_root = blk: {
50 if (shdr.sh_flags & elf.SHF_GNU_RETAIN != 0) break :blk true;
51 if (shdr.sh_type == elf.SHT_NOTE) break :blk true;
52 if (shdr.sh_type == elf.SHT_PREINIT_ARRAY) break :blk true;
53 if (shdr.sh_type == elf.SHT_INIT_ARRAY) break :blk true;
54 if (shdr.sh_type == elf.SHT_FINI_ARRAY) break :blk true;
55 if (mem.startsWith(u8, name, ".ctors")) break :blk true;
56 if (mem.startsWith(u8, name, ".dtors")) break :blk true;
57 if (mem.startsWith(u8, name, ".init")) break :blk true;
58 if (mem.startsWith(u8, name, ".fini")) break :blk true;
59 if (Elf.isCIdentifier(name)) break :blk true;
60 break :blk false;
61 };
62 if (is_gc_root and markAtom(atom)) try rs.append(atom);
63 if (shdr.sh_flags & elf.SHF_ALLOC == 0) atom.visited = true;
64 }
65
66 // Mark every atom referenced by CIE as alive.
67 for (file.cies()) |cie| {
68 for (cie.relocs(ef)) |rel| {
69 const ref = file.resolveSymbol(rel.r_sym(), ef);
70 const sym = ef.symbol(ref) orelse continue;
71 try markSymbol(sym, rs, ef);
72 }
73 }
74 }
75 }.atomRoots;
76
77 if (elf_file.zigObjectPtr()) |zo| {
78 try atomRoots(zo.asFile(), roots, elf_file);
79 }
80 for (elf_file.objects.items) |index| {
81 try atomRoots(elf_file.file(index).?, roots, elf_file);
82 }
83}
84
85fn markSymbol(sym: *Symbol, roots: *std.array_list.Managed(*Atom), elf_file: *Elf) !void {
86 if (sym.mergeSubsection(elf_file)) |msub| {
87 msub.alive = true;
88 return;
89 }
90 const atom = sym.atom(elf_file) orelse return;
91 if (markAtom(atom)) try roots.append(atom);
92}
93
94fn markAtom(atom: *Atom) bool {
95 const already_visited = atom.visited;
96 atom.visited = true;
97 return atom.alive and !already_visited;
98}
99
100fn markLive(atom: *Atom, elf_file: *Elf) void {
101 if (@import("build_options").enable_logging) track_live_level.incr();
102
103 assert(atom.visited);
104 const file = atom.file(elf_file).?;
105
106 switch (file) {
107 .object => |object| {
108 for (atom.fdes(object)) |fde| {
109 for (fde.relocs(object)[1..]) |rel| {
110 const ref = file.resolveSymbol(rel.r_sym(), elf_file);
111 const target_sym = elf_file.symbol(ref) orelse continue;
112 const target_atom = target_sym.atom(elf_file) orelse continue;
113 target_atom.alive = true;
114 gc_track_live_log.debug("{f}marking live atom({d})", .{ track_live_level, target_atom.atom_index });
115 if (markAtom(target_atom)) markLive(target_atom, elf_file);
116 }
117 }
118 },
119 else => {},
120 }
121
122 for (atom.relocs(elf_file)) |rel| {
123 const ref = file.resolveSymbol(rel.r_sym(), elf_file);
124 const target_sym = elf_file.symbol(ref) orelse continue;
125 if (target_sym.mergeSubsection(elf_file)) |msub| {
126 msub.alive = true;
127 continue;
128 }
129 const target_atom = target_sym.atom(elf_file) orelse continue;
130 target_atom.alive = true;
131 gc_track_live_log.debug("{f}marking live atom({d})", .{ track_live_level, target_atom.atom_index });
132 if (markAtom(target_atom)) markLive(target_atom, elf_file);
133 }
134}
135
136fn mark(roots: std.array_list.Managed(*Atom), elf_file: *Elf) void {
137 for (roots.items) |root| {
138 gc_track_live_log.debug("root atom({d})", .{root.atom_index});
139 markLive(root, elf_file);
140 }
141}
142
143fn pruneInFile(file: File) void {
144 for (file.atoms()) |atom_index| {
145 const atom = file.atom(atom_index) orelse continue;
146 if (atom.alive and !atom.visited) {
147 atom.alive = false;
148 switch (file) {
149 .object => |object| atom.markFdesDead(object),
150 else => {},
151 }
152 }
153 }
154}
155
156fn prune(elf_file: *Elf) void {
157 if (elf_file.zigObjectPtr()) |zo| {
158 pruneInFile(zo.asFile());
159 }
160 for (elf_file.objects.items) |index| {
161 pruneInFile(elf_file.file(index).?);
162 }
163}
164
165const Level = struct {
166 value: usize = 0,
167
168 fn incr(self: *@This()) void {
169 self.value += 1;
170 }
171
172 pub fn format(self: *const @This(), w: *std.Io.Writer) std.Io.Writer.Error!void {
173 try w.splatByteAll(' ', self.value);
174 }
175};
176
177var track_live_level: Level = .{};
178
179const std = @import("std");
180const assert = std.debug.assert;
181const elf = std.elf;
182const gc_track_live_log = std.log.scoped(.gc_track_live);
183const mem = std.mem;
184
185const Allocator = mem.Allocator;
186const Atom = @import("Atom.zig");
187const Elf = @import("../Elf.zig");
188const File = @import("file.zig").File;
189const Symbol = @import("Symbol.zig");
190const ZigObject = @import("ZigObject.zig");