lib/reticulum/src/node/limits.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const carrier = @import("../carrier/root.zig");
4 const destination = @import("../destination/root.zig");
5 const identity = @import("../identity/root.zig");
6 const packet = @import("../packet/root.zig");
7 const wire = @import("../wire/root.zig");
8 const access = @import("access.zig");
9 const effect = @import("effect.zig");
10 const timer = @import("timer.zig");
11 const transport = @import("transport/root.zig");
12
13 /// The number of delivery receipts Reticulum@1.5.0 RNS/Transport.py:156 keeps at once, for a caller
14 /// that wants the reference's own bound.
15 pub const reference_receipts_max: usize = 1_024;
16 /// The number of packet hashes Reticulum@1.5.0 RNS/Transport.py:242 remembers to catch repeats, for
17 /// a caller that wants the reference's own bound.
18 pub const reference_duplicate_hashes_max: usize = 1_000_000;
19 /// The number of path request tags the node keeps, twice the 16000 that Reticulum@1.5.0
20 /// RNS/Transport.py:188-190,821-824 rotates into a second set, for a caller that wants the
21 /// reference's own bound.
22 pub const reference_path_request_tags_max: usize = 32_000;
23
24 pub const RatchetBinding = struct {
25 ring: ?*identity.Ring = null,
26 enforce: bool = false,
27 };
28
29 pub const Limits = struct {
30 interfaces_max: usize,
31 destinations_max: usize,
32 known_identities_max: usize,
33 known_ratchets_max: usize,
34 receipts_max: usize,
35 duplicate_hashes_max: usize,
36 timers_max: usize,
37 effects_max: usize,
38 effect_frames_max: usize,
39 paths_max: usize,
40 announces_max: usize,
41 reverse_entries_max: usize,
42 path_request_tags_max: usize,
43 inflight_requests_max: usize,
44 discoveries_max: usize,
45 links_max: usize,
46 link_entries_max: usize,
47
48 /// One set of limits that pairs the reference receipt, hash, and tag maxima above with a single
49 /// entry in every other table. The tests derive a capacity from it to show that those maxima
50 /// fit and that raising one past the range of its entry type is refused.
51 pub const reference = Limits{
52 .interfaces_max = 1,
53 .destinations_max = 1,
54 .known_identities_max = 1,
55 .known_ratchets_max = 1,
56 .receipts_max = reference_receipts_max,
57 .duplicate_hashes_max = reference_duplicate_hashes_max,
58 .timers_max = 1,
59 .effects_max = effect.effects_per_event_max,
60 .effect_frames_max = effect.effect_frames_per_event_max,
61 .paths_max = 1,
62 .announces_max = 1,
63 .reverse_entries_max = 1,
64 .path_request_tags_max = reference_path_request_tags_max,
65 .inflight_requests_max = 1,
66 .discoveries_max = 1,
67 .links_max = 1,
68 .link_entries_max = 1,
69 };
70 };
71
72 pub const Capacity = struct {
73 interface_storage_bytes: usize,
74 identity_storage_bytes: usize,
75 ratchet_binding_storage_bytes: usize,
76 scratch_storage_bytes: usize,
77 destinations: destination.registry.Table.Capacity,
78 known_identities: identity.known.Identities.Capacity,
79 known_ratchets: identity.known.Ratchets.Capacity,
80 receipts: packet.receipt.Table.Capacity,
81 duplicate_hashes: packet.hashlist.Table.Capacity,
82 timers: timer.Table.Capacity,
83 transport: transport.State.Capacity,
84 effects: effect.Effects.Capacity,
85 identities_offset: usize,
86 ratchet_bindings_offset: usize,
87 destinations_offset: usize,
88 known_identities_offset: usize,
89 known_ratchets_offset: usize,
90 receipts_offset: usize,
91 duplicate_hashes_offset: usize,
92 timers_offset: usize,
93 transport_offset: usize,
94 effects_offset: usize,
95 scratch_offset: usize,
96 storage_bytes: usize,
97
98 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
99
100 pub fn derive(limits: Limits) DeriveError!Capacity {
101 if (limits.interfaces_max == 0) return error.InvalidLimit;
102 if (limits.interfaces_max > @as(usize, std.math.maxInt(carrier.Index)) + 1) {
103 return error.InvalidLimit;
104 }
105 const subs = try deriveSubcapacities(limits);
106 const interface_storage_bytes = try alloc_phase.capacity.mul(
107 usize,
108 limits.interfaces_max,
109 @sizeOf(access.Registration),
110 );
111 var cursor = try alignForward(interface_storage_bytes, 8);
112 const identities_offset = try advance(&cursor, try alloc_phase.capacity.mul(
113 usize,
114 limits.destinations_max,
115 @sizeOf(identity.Private),
116 ));
117 const ratchet_bindings_offset = try advance(&cursor, try alloc_phase.capacity.mul(
118 usize,
119 limits.destinations_max,
120 @sizeOf(RatchetBinding),
121 ));
122 const destinations_offset = try advance(&cursor, subs.destinations.storage_bytes);
123 const known_identities_offset = try advance(&cursor, subs.known_identities.storage_bytes);
124 const known_ratchets_offset = try advance(&cursor, subs.known_ratchets.storage_bytes);
125 const receipts_offset = try advance(&cursor, subs.receipts.storage_bytes);
126 const duplicate_hashes_offset = try advance(&cursor, subs.duplicate_hashes.storage_bytes);
127 const timers_offset = try advance(&cursor, subs.timers.storage_bytes);
128 const transport_offset = try advance(&cursor, subs.transport.storage_bytes);
129 const effects_offset = try advance(&cursor, subs.effects.storage_bytes);
130 const scratch_offset = try advance(&cursor, wire.mtu);
131 return .{
132 .interface_storage_bytes = interface_storage_bytes,
133 .identity_storage_bytes = ratchet_bindings_offset - identities_offset,
134 .ratchet_binding_storage_bytes = destinations_offset - ratchet_bindings_offset,
135 .scratch_storage_bytes = wire.mtu,
136 .destinations = subs.destinations,
137 .known_identities = subs.known_identities,
138 .known_ratchets = subs.known_ratchets,
139 .receipts = subs.receipts,
140 .duplicate_hashes = subs.duplicate_hashes,
141 .timers = subs.timers,
142 .transport = subs.transport,
143 .effects = subs.effects,
144 .identities_offset = identities_offset,
145 .ratchet_bindings_offset = ratchet_bindings_offset,
146 .destinations_offset = destinations_offset,
147 .known_identities_offset = known_identities_offset,
148 .known_ratchets_offset = known_ratchets_offset,
149 .receipts_offset = receipts_offset,
150 .duplicate_hashes_offset = duplicate_hashes_offset,
151 .timers_offset = timers_offset,
152 .transport_offset = transport_offset,
153 .effects_offset = effects_offset,
154 .scratch_offset = scratch_offset,
155 .storage_bytes = cursor,
156 };
157 }
158 };
159
160 const Subcapacities = struct {
161 destinations: destination.registry.Table.Capacity,
162 known_identities: identity.known.Identities.Capacity,
163 known_ratchets: identity.known.Ratchets.Capacity,
164 receipts: packet.receipt.Table.Capacity,
165 duplicate_hashes: packet.hashlist.Table.Capacity,
166 timers: timer.Table.Capacity,
167 transport: transport.State.Capacity,
168 effects: effect.Effects.Capacity,
169 };
170
171 fn deriveSubcapacities(limits: Limits) Capacity.DeriveError!Subcapacities {
172 return .{
173 .destinations = try destination.registry.Table.Capacity.derive(.{
174 .destinations_max = limits.destinations_max,
175 }),
176 .known_identities = try identity.known.Identities.Capacity.derive(.{
177 .identities_max = limits.known_identities_max,
178 }),
179 .known_ratchets = try identity.known.Ratchets.Capacity.derive(.{
180 .ratchets_max = limits.known_ratchets_max,
181 }),
182 .receipts = try packet.receipt.Table.Capacity.derive(.{
183 .receipts_max = limits.receipts_max,
184 }),
185 .duplicate_hashes = try packet.hashlist.Table.Capacity.derive(.{
186 .hashes_max = limits.duplicate_hashes_max,
187 }),
188 .timers = try timer.Table.Capacity.derive(.{
189 .timers_max = limits.timers_max,
190 }),
191 .transport = try transport.State.Capacity.derive(.{
192 .paths_max = limits.paths_max,
193 .announces_max = limits.announces_max,
194 .reverse_entries_max = limits.reverse_entries_max,
195 .path_request_tags_max = limits.path_request_tags_max,
196 .inflight_requests_max = limits.inflight_requests_max,
197 .discoveries_max = limits.discoveries_max,
198 .links_max = limits.links_max,
199 .link_entries_max = limits.link_entries_max,
200 }),
201 .effects = try effect.Effects.Capacity.derive(.{
202 .effects_max = limits.effects_max,
203 .frames_max = limits.effect_frames_max,
204 }),
205 };
206 }
207
208 fn advance(cursor: *usize, bytes: usize) Capacity.DeriveError!usize {
209 const offset = cursor.*;
210 cursor.* = alloc_phase.capacity.add(usize, cursor.*, bytes) catch
211 return error.CapacityOverflow;
212 return offset;
213 }
214
215 fn alignForward(value: usize, alignment: usize) Capacity.DeriveError!usize {
216 std.debug.assert(alignment > 0);
217 std.debug.assert(std.math.isPowerOfTwo(alignment));
218 const remainder = value % alignment;
219 if (remainder == 0) return value;
220 return alloc_phase.capacity.add(usize, value, alignment - remainder) catch
221 error.CapacityOverflow;
222 }
223
224 test "node capacity accepts reference bounds and rejects summation overflow" {
225 const reference = try Capacity.derive(Limits.reference);
226 try std.testing.expectEqual(reference_receipts_max, reference.receipts.receipts_max);
227 try std.testing.expectEqual(
228 reference_duplicate_hashes_max,
229 reference.duplicate_hashes.hashes_max,
230 );
231 var overflowing = Limits.reference;
232 overflowing.receipts_max = std.math.maxInt(usize) / @sizeOf(packet.receipt.Receipt);
233 overflowing.duplicate_hashes_max = std.math.maxInt(usize) / @sizeOf(packet.Hash);
234 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(overflowing));
235 var too_many_interfaces = Limits.reference;
236 too_many_interfaces.interfaces_max = @as(usize, std.math.maxInt(carrier.Index)) + 2;
237 try std.testing.expectError(error.InvalidLimit, Capacity.derive(too_many_interfaces));
238 }
239
240 test "node capacity rejects zero and overflowing transport table limits" {
241 const reference = try Capacity.derive(Limits.reference);
242 try std.testing.expectEqual(@as(usize, 1), reference.transport.paths.paths_max);
243 try std.testing.expectEqual(@as(usize, 1), reference.transport.announces.announces_max);
244 try std.testing.expectEqual(
245 @as(usize, 1),
246 reference.transport.reverse_entries.reverse_entries_max,
247 );
248 try std.testing.expectEqual(
249 reference_path_request_tags_max,
250 reference.transport.tags.hashes_max,
251 );
252 try std.testing.expectEqual(
253 @as(usize, 1),
254 reference.transport.inflight_requests.inflight_requests_max,
255 );
256 try std.testing.expectEqual(@as(usize, 1), reference.transport.discoveries.discoveries_max);
257 try std.testing.expectEqual(@as(usize, 1), reference.transport.links.links_max);
258 try std.testing.expectEqual(
259 @as(usize, 1),
260 reference.transport.link_entries.link_entries_max,
261 );
262 const entry_bytes = .{
263 .paths_max = @sizeOf(transport.path.Entry),
264 .announces_max = @sizeOf(transport.announces.Entry),
265 .reverse_entries_max = @sizeOf(transport.reverse.Entry),
266 .path_request_tags_max = @sizeOf(packet.Hash),
267 .inflight_requests_max = @sizeOf(transport.inflight.Entry),
268 .discoveries_max = @sizeOf(transport.discoveries.Entry),
269 .links_max = @sizeOf(transport.links.Entry),
270 .link_entries_max = @sizeOf(transport.link.entries.Entry),
271 };
272 const fields = .{
273 "paths_max",
274 "announces_max",
275 "reverse_entries_max",
276 "path_request_tags_max",
277 "inflight_requests_max",
278 "discoveries_max",
279 "links_max",
280 "link_entries_max",
281 };
282 inline for (fields) |field| {
283 var zero = Limits.reference;
284 @field(zero, field) = 0;
285 try std.testing.expectError(error.InvalidLimit, Capacity.derive(zero));
286 var overflowing = Limits.reference;
287 @field(overflowing, field) = std.math.maxInt(usize) / @field(entry_bytes, field) + 1;
288 try std.testing.expectError(error.CapacityOverflow, Capacity.derive(overflowing));
289 }
290 }