lib/deadalloc/src/exterminator.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const report_mod = @import("report.zig");
3
4 pub const max_repair_entries: usize = 32;
5
6 pub const OverflowRepair = struct {
7 allocation_return_address: usize = 0,
8 padding_bytes: usize = 0,
9 };
10
11 pub const DangleRepair = struct {
12 allocation_return_address: usize = 0,
13 free_return_address: usize = 0,
14 quarantine_epochs: u64 = 0,
15 };
16
17 pub const RepairTable = struct {
18 overflow_count: usize = 0,
19 dangle_count: usize = 0,
20 overflow_entries: [max_repair_entries]OverflowRepair = @as([max_repair_entries]OverflowRepair, @splat(.{})),
21 dangle_entries: [max_repair_entries]DangleRepair = @as([max_repair_entries]DangleRepair, @splat(.{})),
22
23 pub fn fromReport(report: report_mod.Report, current: RepairTable) RepairTable {
24 var next = current;
25 for (report.issueSlice()) |issue| next.recordIssue(issue);
26 return next;
27 }
28
29 pub fn overflowPadding(self: RepairTable, allocation_return_address: usize) usize {
30 var index: usize = 0;
31 while (index < self.overflow_count) : (index += 1) {
32 const entry = self.overflow_entries[index];
33 if (entry.allocation_return_address == allocation_return_address) return entry.padding_bytes;
34 }
35 return 0;
36 }
37
38 pub fn lifeExtension(self: RepairTable, allocation_return_address: usize, free_return_address: usize) u64 {
39 var index: usize = 0;
40 while (index < self.dangle_count) : (index += 1) {
41 const entry = self.dangle_entries[index];
42 if (entry.allocation_return_address == allocation_return_address and entry.free_return_address == free_return_address) {
43 return entry.quarantine_epochs;
44 }
45 }
46 return 0;
47 }
48
49 fn recordIssue(self: *RepairTable, issue: report_mod.Issue) void {
50 switch (issue.kind) {
51 .buffer_overflow => self.recordOverflow(issue),
52 .use_after_free, .double_free => self.recordDangle(issue),
53 .invalid_free, .leak, .size_mismatch => {},
54 }
55 }
56
57 fn recordOverflow(self: *RepairTable, issue: report_mod.Issue) void {
58 if (issue.allocation_return_address == 0) return;
59 const needed = if (issue.offset >= issue.requested_len)
60 issue.offset - issue.requested_len + 1
61 else
62 1;
63 if (needed == 0) return;
64
65 var index: usize = 0;
66 while (index < self.overflow_count) : (index += 1) {
67 if (self.overflow_entries[index].allocation_return_address == issue.allocation_return_address) {
68 self.overflow_entries[index].padding_bytes = @max(self.overflow_entries[index].padding_bytes, needed);
69 return;
70 }
71 }
72 if (self.overflow_count == self.overflow_entries.len) return;
73 self.overflow_entries[self.overflow_count] = .{
74 .allocation_return_address = issue.allocation_return_address,
75 .padding_bytes = needed,
76 };
77 self.overflow_count += 1;
78 }
79
80 fn recordDangle(self: *RepairTable, issue: report_mod.Issue) void {
81 if (issue.allocation_return_address == 0) return;
82 const free_return_address = if (issue.free_return_address != 0) issue.free_return_address else issue.return_address;
83 if (free_return_address == 0) return;
84
85 var index: usize = 0;
86 while (index < self.dangle_count) : (index += 1) {
87 if (self.dangle_entries[index].allocation_return_address == issue.allocation_return_address and self.dangle_entries[index].free_return_address == free_return_address) {
88 self.dangle_entries[index].quarantine_epochs = growU64(self.dangle_entries[index].quarantine_epochs, 1, 4096);
89 return;
90 }
91 }
92 if (self.dangle_count == self.dangle_entries.len) return;
93 self.dangle_entries[self.dangle_count] = .{
94 .allocation_return_address = issue.allocation_return_address,
95 .free_return_address = free_return_address,
96 .quarantine_epochs = 1,
97 };
98 self.dangle_count += 1;
99 }
100 };
101
102 pub const RepairPolicy = struct {
103 red_zone_bytes: usize = 16,
104 quarantine_epochs: u64 = 16,
105 repairs: RepairTable = .{},
106
107 pub fn fromReport(report: report_mod.Report, current: RepairPolicy) RepairPolicy {
108 var next = current;
109 if (report.counters.buffer_overflow > 0) {
110 next.red_zone_bytes = growUsize(current.red_zone_bytes, 16, 1024);
111 }
112 if (report.counters.use_after_free > 0 or report.counters.double_free > 0) {
113 next.quarantine_epochs = growU64(current.quarantine_epochs, 1, 4096);
114 }
115 next.repairs = RepairTable.fromReport(report, current.repairs);
116 return next;
117 }
118 };
119
120 fn growUsize(current: usize, initial: usize, cap: usize) usize {
121 if (current == 0) return initial;
122 if (current >= cap) return current;
123 return @min(current * 2, cap);
124 }
125
126 fn growU64(current: u64, initial: u64, cap: u64) u64 {
127 if (current == 0) return initial;
128 if (current >= cap) return current;
129 return @min(current * 2, cap);
130 }
131
132 test "repair policy grows padding and quarantine from diagnostics" {
133 const report: report_mod.Report = .{
134 .counters = .{
135 .buffer_overflow = 1,
136 .use_after_free = 1,
137 },
138 };
139 const repaired = RepairPolicy.fromReport(report, .{ .red_zone_bytes = 8, .quarantine_epochs = 2 });
140 try std.testing.expectEqual(@as(usize, 16), repaired.red_zone_bytes);
141 try std.testing.expectEqual(@as(u64, 4), repaired.quarantine_epochs);
142 }
143
144 test "repair policy starts from zero without reducing hardened settings" {
145 const report: report_mod.Report = .{
146 .counters = .{
147 .buffer_overflow = 1,
148 .double_free = 1,
149 },
150 };
151
152 const started = RepairPolicy.fromReport(report, .{ .red_zone_bytes = 0, .quarantine_epochs = 0 });
153 try std.testing.expectEqual(@as(usize, 16), started.red_zone_bytes);
154 try std.testing.expectEqual(@as(u64, 1), started.quarantine_epochs);
155
156 const hardened = RepairPolicy.fromReport(report, .{ .red_zone_bytes = 2048, .quarantine_epochs = 8192 });
157 try std.testing.expectEqual(@as(usize, 2048), hardened.red_zone_bytes);
158 try std.testing.expectEqual(@as(u64, 8192), hardened.quarantine_epochs);
159 }
160
161 test "repair table records overflow padding by allocation site" {
162 const report: report_mod.Report = .{
163 .issues = .{
164 .count = 1,
165 .items = [_]report_mod.Issue{.{
166 .kind = .buffer_overflow,
167 .offset = 13,
168 .requested_len = 8,
169 .allocation_return_address = 0x1000,
170 }} ++ @as([(report_mod.max_issues - 1)]report_mod.Issue, @splat(.{})),
171 },
172 };
173
174 const table = RepairTable.fromReport(report, .{});
175 try std.testing.expectEqual(@as(usize, 6), table.overflowPadding(0x1000));
176 try std.testing.expectEqual(@as(usize, 0), table.overflowPadding(0x2000));
177 }
178
179 test "repair table records dangle extensions by allocation and free site" {
180 const report: report_mod.Report = .{
181 .issues = .{
182 .count = 1,
183 .items = [_]report_mod.Issue{.{
184 .kind = .use_after_free,
185 .allocation_return_address = 0x1000,
186 .free_return_address = 0x2000,
187 }} ++ @as([(report_mod.max_issues - 1)]report_mod.Issue, @splat(.{})),
188 },
189 };
190
191 const first = RepairTable.fromReport(report, .{});
192 const second = RepairTable.fromReport(report, first);
193 try std.testing.expectEqual(@as(u64, 1), first.lifeExtension(0x1000, 0x2000));
194 try std.testing.expectEqual(@as(u64, 2), second.lifeExtension(0x1000, 0x2000));
195 try std.testing.expectEqual(@as(u64, 0), second.lifeExtension(0x1000, 0x3000));
196 }