lib/memtrace/src/census/capacity.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const model = @import("model.zig");
3
4 pub const storage_alignment: usize = @max(@alignOf(model.Slot), @alignOf(model.Entry));
5
6 pub const Limits = struct {
7 categories: usize,
8 label_bytes: usize,
9 joined_label_bytes: usize,
10 };
11
12 pub const DeriveError = error{
13 CapacityOverflow,
14 CategoryCapacityTooSmall,
15 LabelStorageTooSmall,
16 };
17
18 pub const Capacity = struct {
19 categories: usize,
20 table_slots: usize,
21 table_bytes: usize,
22 table_offset: usize,
23 summary_entries: usize,
24 summary_bytes: usize,
25 summary_offset: usize,
26 label_bytes: usize,
27 label_offset: usize,
28 joined_label_bytes: usize,
29 joined_label_offset: usize,
30 storage_bytes: usize,
31
32 pub fn derive(limits: Limits) DeriveError!Capacity {
33 if (limits.categories == 0) return error.CategoryCapacityTooSmall;
34 if (limits.label_bytes == 0) return error.LabelStorageTooSmall;
35
36 const doubled_categories = try multiplied(limits.categories, 2);
37 const table_slots = std.math.ceilPowerOfTwo(usize, doubled_categories) catch
38 return error.CapacityOverflow;
39 const table = try placed(model.Slot, 0, table_slots);
40 const summary = try placed(model.Entry, table.end, limits.categories);
41 const label_offset = summary.end;
42 const joined_label_offset = try added(label_offset, limits.label_bytes);
43 const storage_bytes = try added(joined_label_offset, limits.joined_label_bytes);
44
45 return .{
46 .categories = limits.categories,
47 .table_slots = table_slots,
48 .table_bytes = table.bytes,
49 .table_offset = table.start,
50 .summary_entries = limits.categories,
51 .summary_bytes = summary.bytes,
52 .summary_offset = summary.start,
53 .label_bytes = limits.label_bytes,
54 .label_offset = label_offset,
55 .joined_label_bytes = limits.joined_label_bytes,
56 .joined_label_offset = joined_label_offset,
57 .storage_bytes = storage_bytes,
58 };
59 }
60 };
61
62 const Region = struct {
63 start: usize,
64 bytes: usize,
65 end: usize,
66 };
67
68 fn added(left: usize, right: usize) DeriveError!usize {
69 return std.math.add(usize, left, right) catch error.CapacityOverflow;
70 }
71
72 fn multiplied(left: usize, right: usize) DeriveError!usize {
73 return std.math.mul(usize, left, right) catch error.CapacityOverflow;
74 }
75
76 fn aligned(offset: usize, alignment: usize) DeriveError!usize {
77 const mask = alignment - 1;
78 const padded = try added(offset, mask);
79 return padded & ~mask;
80 }
81
82 fn placed(comptime T: type, offset: usize, count: usize) DeriveError!Region {
83 const start = try aligned(offset, @alignOf(T));
84 const bytes = try multiplied(count, @sizeOf(T));
85 const end = try added(start, bytes);
86 return .{ .start = start, .bytes = bytes, .end = end };
87 }
88
89 fn modelCapacity(limits: Limits) DeriveError!Capacity {
90 if (limits.categories == 0) return error.CategoryCapacityTooSmall;
91 if (limits.label_bytes == 0) return error.LabelStorageTooSmall;
92
93 const doubled_categories = @as(u128, limits.categories) * 2;
94 var table_slots: u128 = 1;
95 while (table_slots < doubled_categories) table_slots *= 2;
96 const table_offset = alignedModel(0, @alignOf(model.Slot));
97 const table_bytes = table_slots * @sizeOf(model.Slot);
98 const summary_offset = alignedModel(table_offset + table_bytes, @alignOf(model.Entry));
99 const summary_bytes = @as(u128, limits.categories) * @sizeOf(model.Entry);
100 const label_offset = summary_offset + summary_bytes;
101 const joined_label_offset = label_offset + limits.label_bytes;
102 const storage_bytes = joined_label_offset + limits.joined_label_bytes;
103
104 const values = [_]u128{
105 table_slots,
106 table_offset,
107 table_bytes,
108 summary_offset,
109 summary_bytes,
110 label_offset,
111 joined_label_offset,
112 storage_bytes,
113 };
114 for (values) |value| {
115 if (value > std.math.maxInt(usize)) return error.CapacityOverflow;
116 }
117
118 return .{
119 .categories = limits.categories,
120 .table_slots = @intCast(table_slots),
121 .table_bytes = @intCast(table_bytes),
122 .table_offset = @intCast(table_offset),
123 .summary_entries = limits.categories,
124 .summary_bytes = @intCast(summary_bytes),
125 .summary_offset = @intCast(summary_offset),
126 .label_bytes = limits.label_bytes,
127 .label_offset = @intCast(label_offset),
128 .joined_label_bytes = limits.joined_label_bytes,
129 .joined_label_offset = @intCast(joined_label_offset),
130 .storage_bytes = @intCast(storage_bytes),
131 };
132 }
133
134 fn alignedModel(offset: u128, alignment: usize) u128 {
135 const mask = @as(u128, alignment - 1);
136 return (offset + mask) & ~mask;
137 }
138
139 test "Census capacity matches an independent aligned byte model" {
140 comptime {
141 @stardustClaim(
142 @import("alloc_phase").capacity.witness(@import("./root.zig").Storage, "memtrace_census_capacity"),
143 null,
144 null,
145 null,
146 null,
147 null,
148 null,
149 );
150 }
151
152 const limits = Limits{
153 .categories = 3,
154 .label_bytes = 64,
155 .joined_label_bytes = 31,
156 };
157 const capacity = try Capacity.derive(limits);
158 const independent = try modelCapacity(limits);
159
160 try std.testing.expectEqual(independent, capacity);
161 try std.testing.expectEqual(@as(usize, 8), capacity.table_slots);
162 try std.testing.expectEqual(capacity.storage_bytes, capacity.joined_label_offset + capacity.joined_label_bytes);
163 }
164
165 test "census capacity rejects unusable and overflowing limits" {
166 try std.testing.expectError(error.CategoryCapacityTooSmall, Capacity.derive(.{
167 .categories = 0,
168 .label_bytes = 1,
169 .joined_label_bytes = 0,
170 }));
171 try std.testing.expectError(error.LabelStorageTooSmall, Capacity.derive(.{
172 .categories = 1,
173 .label_bytes = 0,
174 .joined_label_bytes = 0,
175 }));
176 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(.{
177 .categories = std.math.maxInt(usize) / 2 + 1,
178 .label_bytes = 1,
179 .joined_label_bytes = 0,
180 }));
181 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(.{
182 .categories = 1,
183 .label_bytes = std.math.maxInt(usize),
184 .joined_label_bytes = 1,
185 }));
186 }