lib/reticulum/src/node/transport/state.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const packet = @import("../../packet/root.zig");
4 const announces = @import("announces.zig");
5 const discoveries = @import("discoveries.zig");
6 const inflight = @import("inflight.zig");
7 const link_entries = @import("link/entries.zig");
8 const links = @import("links.zig");
9 const path = @import("path.zig");
10 const reverse = @import("reverse.zig");
11
12 const StateLimits = struct {
13 paths_max: usize,
14 announces_max: usize,
15 reverse_entries_max: usize,
16 path_request_tags_max: usize,
17 inflight_requests_max: usize,
18 discoveries_max: usize,
19 links_max: usize,
20 link_entries_max: usize,
21 };
22
23 const StateCapacity = struct {
24 paths: path.Table.Capacity,
25 announces: announces.Table.Capacity,
26 reverse_entries: reverse.Table.Capacity,
27 tags: packet.hashlist.Table.Capacity,
28 inflight_requests: inflight.Table.Capacity,
29 discoveries: discoveries.Table.Capacity,
30 links: links.Table.Capacity,
31 link_entries: link_entries.Table.Capacity,
32 announces_offset: usize,
33 reverse_entries_offset: usize,
34 tags_offset: usize,
35 inflight_requests_offset: usize,
36 discoveries_offset: usize,
37 links_offset: usize,
38 link_entries_offset: usize,
39 storage_bytes: usize,
40
41 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
42
43 pub fn derive(limits: StateLimits) DeriveError!StateCapacity {
44 const paths = try path.Table.Capacity.derive(.{ .paths_max = limits.paths_max });
45 const pending = try announces.Table.Capacity.derive(.{
46 .announces_max = limits.announces_max,
47 });
48 const relayed = try reverse.Table.Capacity.derive(.{
49 .reverse_entries_max = limits.reverse_entries_max,
50 });
51 const tag_hashes = try packet.hashlist.Table.Capacity.derive(.{
52 .hashes_max = limits.path_request_tags_max,
53 });
54 const gates = try inflight.Table.Capacity.derive(.{
55 .inflight_requests_max = limits.inflight_requests_max,
56 });
57 const waiting = try discoveries.Table.Capacity.derive(.{
58 .discoveries_max = limits.discoveries_max,
59 });
60 const endpoints = try links.Table.Capacity.derive(.{ .links_max = limits.links_max });
61 const relays = try link_entries.Table.Capacity.derive(.{
62 .link_entries_max = limits.link_entries_max,
63 });
64 var cursor: usize = paths.storage_bytes;
65 const announces_offset = try advance(&cursor, pending.storage_bytes);
66 const reverse_entries_offset = try advance(&cursor, relayed.storage_bytes);
67 const tags_offset = try advance(&cursor, tag_hashes.storage_bytes);
68 const inflight_requests_offset = try advance(&cursor, gates.storage_bytes);
69 const discoveries_offset = try advance(&cursor, waiting.storage_bytes);
70 const links_offset = try advance(&cursor, endpoints.storage_bytes);
71 const link_entries_offset = try advance(&cursor, relays.storage_bytes);
72 return .{
73 .paths = paths,
74 .announces = pending,
75 .reverse_entries = relayed,
76 .tags = tag_hashes,
77 .inflight_requests = gates,
78 .discoveries = waiting,
79 .links = endpoints,
80 .link_entries = relays,
81 .announces_offset = announces_offset,
82 .reverse_entries_offset = reverse_entries_offset,
83 .tags_offset = tags_offset,
84 .inflight_requests_offset = inflight_requests_offset,
85 .discoveries_offset = discoveries_offset,
86 .links_offset = links_offset,
87 .link_entries_offset = link_entries_offset,
88 .storage_bytes = cursor,
89 };
90 }
91 };
92
93 fn advance(cursor: *usize, bytes: usize) StateCapacity.DeriveError!usize {
94 const offset = cursor.*;
95 cursor.* = alloc_phase.capacity.add(usize, offset, bytes) catch
96 return error.CapacityOverflow;
97 return offset;
98 }
99
100 /// The eight tables a node needs to carry traffic for others, together with the
101 /// hash that names it and the flag that turns the carrying on. A caller holds
102 /// one of these per node, and every transport step reaches its store through
103 /// it. The eight tables are carved from one block of caller storage whose
104 /// length has to equal the derived byte count exactly.
105 pub const State = struct {
106 phase: alloc_phase.capacity.Phase,
107 capacity: Capacity,
108 storage: Storage,
109 paths: path.Table,
110 announces: announces.Table,
111 reverse_entries: reverse.Table,
112 tags: packet.hashlist.Table,
113 inflight_requests: inflight.Table,
114 discoveries: discoveries.Table,
115 links: links.Table,
116 link_entries: link_entries.Table,
117 identity_hash: ?[16]u8 = null,
118 enabled: bool = false,
119
120 pub const storage_alignment: usize = 8;
121 pub const Storage = []align(storage_alignment) u8;
122 pub const Limits: type = StateLimits;
123 pub const Capacity: type = StateCapacity;
124 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
125 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
126 .transition_steps_max = 8,
127 .cleanup_steps_per_call_max = 0,
128 .cleanup_calls_at_capacity_max = 0,
129 };
130 pub const claim: alloc_phase.capacity.Declaration = .{
131 .source = .{
132 .id = "reticulum.transport",
133 .kind = .phase_static,
134 .limit_source = .caller,
135 .storage = .{
136 .covered = &.{.{
137 .id = "caller_transport_tables",
138 .lifetime = .transferred,
139 .detail = "caller storage for routing, relay, path request, and link tables",
140 }},
141 .excluded = &.{"relayed, rebroadcast, request, and link frames in effect storage"},
142 },
143 .capacity = .{
144 .inputs = &.{
145 alloc_phase.capacity.bindInput(Limits, "paths", "paths_max"),
146 alloc_phase.capacity.bindInput(Limits, "announces", "announces_max"),
147 alloc_phase.capacity.bindInput(
148 Limits,
149 "reverse_entries",
150 "reverse_entries_max",
151 ),
152 alloc_phase.capacity.bindInput(
153 Limits,
154 "path_request_tags",
155 "path_request_tags_max",
156 ),
157 alloc_phase.capacity.bindInput(
158 Limits,
159 "inflight_requests",
160 "inflight_requests_max",
161 ),
162 alloc_phase.capacity.bindInput(Limits, "discoveries", "discoveries_max"),
163 alloc_phase.capacity.bindInput(Limits, "links", "links_max"),
164 alloc_phase.capacity.bindInput(
165 Limits,
166 "link_entries",
167 "link_entries_max",
168 ),
169 },
170 .type_selectors = &.{
171 alloc_phase.capacity.bindType(path.Entry, "path"),
172 alloc_phase.capacity.bindType(announces.Entry, "announce"),
173 alloc_phase.capacity.bindType(reverse.Entry, "reverse_entry"),
174 alloc_phase.capacity.bindType(packet.Hash, "path_request_tag"),
175 alloc_phase.capacity.bindType(inflight.Entry, "inflight_request"),
176 alloc_phase.capacity.bindType(discoveries.Entry, "discovery"),
177 alloc_phase.capacity.bindType(links.Entry, "link"),
178 alloc_phase.capacity.bindType(link_entries.Entry, "link_entry"),
179 },
180 .nodes = &.{
181 .{ .input = 0 },
182 .{ .scale = .{
183 .node = 0,
184 .coefficient = .{ .size_of_concrete_type = 0 },
185 } },
186 .{ .input = 1 },
187 .{ .scale = .{
188 .node = 2,
189 .coefficient = .{ .size_of_concrete_type = 1 },
190 } },
191 .{ .add = .{ .left = 1, .right = 3 } },
192 .{ .input = 2 },
193 .{ .scale = .{
194 .node = 5,
195 .coefficient = .{ .size_of_concrete_type = 2 },
196 } },
197 .{ .add = .{ .left = 4, .right = 6 } },
198 .{ .input = 3 },
199 .{ .scale = .{
200 .node = 8,
201 .coefficient = .{ .size_of_concrete_type = 3 },
202 } },
203 .{ .add = .{ .left = 7, .right = 9 } },
204 .{ .input = 4 },
205 .{ .scale = .{
206 .node = 11,
207 .coefficient = .{ .size_of_concrete_type = 4 },
208 } },
209 .{ .add = .{ .left = 10, .right = 12 } },
210 .{ .input = 5 },
211 .{ .scale = .{
212 .node = 14,
213 .coefficient = .{ .size_of_concrete_type = 5 },
214 } },
215 .{ .add = .{ .left = 13, .right = 15 } },
216 .{ .input = 6 },
217 .{ .scale = .{
218 .node = 17,
219 .coefficient = .{ .size_of_concrete_type = 6 },
220 } },
221 .{ .add = .{ .left = 16, .right = 18 } },
222 .{ .input = 7 },
223 .{ .scale = .{
224 .node = 20,
225 .coefficient = .{ .size_of_concrete_type = 7 },
226 } },
227 .{ .add = .{ .left = 19, .right = 21 } },
228 },
229 .assertions = &.{.{
230 .scope = .closure_total,
231 .measure = .retained,
232 .relation = .exact,
233 .expression = 22,
234 }},
235 },
236 .overload = .{
237 .kind = .reject_before_seal,
238 .detail = "invalid limits and short caller storage reject before activation",
239 },
240 .risks = .{
241 .transitive = .{
242 .status = .witnessed,
243 .detail = "all retained table storage is carved from the transport region",
244 },
245 .foreign = .{
246 .status = .excluded,
247 .detail = "the transport owner crosses no foreign boundary",
248 },
249 },
250 .work = .{ .equation = "activation and teardown each visit eight subowners" },
251 .dependencies = &.{
252 "reticulum.paths",
253 "reticulum.announces",
254 "reticulum.reverse_entries",
255 "reticulum.hashlist",
256 "reticulum.inflight_requests",
257 "reticulum.discoveries",
258 "reticulum.links",
259 "reticulum.link_entries",
260 },
261 .obligations = &.{
262 .{ .key = "reticulum_transport_capacity", .role = .capacity_model },
263 .{ .key = "reticulum_transport_overload", .role = .overload },
264 .{ .key = "reticulum_transport_transitive", .role = .transitive_risk },
265 .{ .key = "reticulum_transport_work", .role = .work_bound },
266 },
267 },
268 .bindings = .{
269 .owner = @This(),
270 .seal = .{
271 .family = alloc_phase.capacity.selector(@This().activate),
272 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
273 },
274 .teardown = .{
275 .family = alloc_phase.capacity.selector(@This().deinit),
276 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
277 },
278 },
279 };
280
281 pub fn init(storage: Storage, limits: Limits) InitError!State {
282 const capacity = try Capacity.derive(limits);
283 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
284 return .{
285 .phase = .initialization,
286 .capacity = capacity,
287 .storage = storage,
288 .paths = try path.Table.init(
289 region(storage, 0, capacity.paths.storage_bytes),
290 .{ .paths_max = limits.paths_max },
291 ),
292 .announces = try announces.Table.init(
293 region(storage, capacity.announces_offset, capacity.announces.storage_bytes),
294 .{ .announces_max = limits.announces_max },
295 ),
296 .reverse_entries = try reverse.Table.init(
297 region(
298 storage,
299 capacity.reverse_entries_offset,
300 capacity.reverse_entries.storage_bytes,
301 ),
302 .{ .reverse_entries_max = limits.reverse_entries_max },
303 ),
304 .tags = try packet.hashlist.Table.init(
305 region(storage, capacity.tags_offset, capacity.tags.storage_bytes),
306 .{ .hashes_max = limits.path_request_tags_max },
307 ),
308 .inflight_requests = try inflight.Table.init(
309 region(
310 storage,
311 capacity.inflight_requests_offset,
312 capacity.inflight_requests.storage_bytes,
313 ),
314 .{ .inflight_requests_max = limits.inflight_requests_max },
315 ),
316 .discoveries = try discoveries.Table.init(
317 region(storage, capacity.discoveries_offset, capacity.discoveries.storage_bytes),
318 .{ .discoveries_max = limits.discoveries_max },
319 ),
320 .links = try links.Table.init(
321 region(storage, capacity.links_offset, capacity.links.storage_bytes),
322 .{ .links_max = limits.links_max },
323 ),
324 .link_entries = try link_entries.Table.init(
325 region(
326 storage,
327 capacity.link_entries_offset,
328 capacity.link_entries.storage_bytes,
329 ),
330 .{ .link_entries_max = limits.link_entries_max },
331 ),
332 };
333 }
334
335 pub fn activate(self: *State) void {
336 std.debug.assert(self.phase == .initialization);
337 self.paths.activate();
338 self.announces.activate();
339 self.reverse_entries.activate();
340 self.tags.activate();
341 self.inflight_requests.activate();
342 self.discoveries.activate();
343 self.links.activate();
344 self.link_entries.activate();
345 self.phase = .steady;
346 }
347
348 /// Names this node as a next hop, following Reticulum@1.5.0
349 /// RNS/Transport.py:1577-1580,1907. A caller turns the node into one that
350 /// carries traffic for others, and gives it the hash that names it to its
351 /// neighbors. Every step that carries traffic for others refuses until the
352 /// flag is set.
353 pub fn configure(self: *State, identity_hash: [16]u8, enabled: bool) void {
354 std.debug.assert(self.phase == .steady);
355 self.identity_hash = identity_hash;
356 self.enabled = enabled;
357 }
358
359 pub fn deinit(self: *State) Storage {
360 std.debug.assert(self.phase == .steady);
361 _ = self.link_entries.deinit();
362 _ = self.links.deinit();
363 _ = self.discoveries.deinit();
364 _ = self.inflight_requests.deinit();
365 _ = self.tags.deinit();
366 _ = self.reverse_entries.deinit();
367 _ = self.announces.deinit();
368 _ = self.paths.deinit();
369 self.phase = .teardown;
370 const storage = self.storage;
371 self.* = undefined;
372 return storage;
373 }
374 };
375
376 fn region(storage: State.Storage, offset: usize, length: usize) []align(8) u8 {
377 std.debug.assert(offset % State.storage_alignment == 0);
378 std.debug.assert(offset <= storage.len);
379 std.debug.assert(length <= storage.len - offset);
380 const pointer: [*]align(State.storage_alignment) u8 = @ptrCast(
381 @alignCast(storage[offset..].ptr),
382 );
383 return pointer[0..length];
384 }
385
386 comptime {
387 std.debug.assert(@sizeOf(path.Entry) % State.storage_alignment == 0);
388 std.debug.assert(@sizeOf(announces.Entry) % State.storage_alignment == 0);
389 std.debug.assert(@sizeOf(reverse.Entry) % State.storage_alignment == 0);
390 std.debug.assert(@sizeOf(packet.Hash) % State.storage_alignment == 0);
391 std.debug.assert(@sizeOf(inflight.Entry) % State.storage_alignment == 0);
392 std.debug.assert(@sizeOf(discoveries.Entry) % State.storage_alignment == 0);
393 std.debug.assert(@sizeOf(links.Entry) % State.storage_alignment == 0);
394 }
395
396 comptime {
397 alloc_phase.capacity.requireProvisionedExactOwnerShape(State);
398 }
399
400 const small_limits = StateLimits{
401 .paths_max = 3,
402 .announces_max = 2,
403 .reverse_entries_max = 4,
404 .path_request_tags_max = 5,
405 .inflight_requests_max = 6,
406 .discoveries_max = 7,
407 .links_max = 8,
408 .link_entries_max = 9,
409 };
410
411 test "transport state carves and activates its eight tables" {
412 comptime {
413 @stardustClaim(alloc_phase.capacity.witness(
414 State,
415 "reticulum_transport_capacity",
416 ), null, null, null, null, null, null);
417 @stardustClaim(alloc_phase.capacity.witness(
418 State,
419 "reticulum_transport_overload",
420 ), null, null, null, null, null, null);
421 @stardustClaim(alloc_phase.capacity.witness(
422 State,
423 "reticulum_transport_transitive",
424 ), null, null, null, null, null, null);
425 @stardustClaim(alloc_phase.capacity.witness(
426 State,
427 "reticulum_transport_work",
428 ), null, null, null, null, null, null);
429 }
430 const capacity = comptime StateCapacity.derive(small_limits) catch unreachable;
431 const routing_bytes = 3 * @sizeOf(path.Entry) + 2 * @sizeOf(announces.Entry) +
432 4 * @sizeOf(reverse.Entry);
433 const request_bytes = 5 * @sizeOf(packet.Hash) + 6 * @sizeOf(inflight.Entry) +
434 7 * @sizeOf(discoveries.Entry);
435 const link_bytes = 8 * @sizeOf(links.Entry) + 9 * @sizeOf(link_entries.Entry);
436 const expected_bytes = routing_bytes + request_bytes + link_bytes;
437 try std.testing.expectEqual(expected_bytes, capacity.storage_bytes);
438 var bytes: [capacity.storage_bytes]u8 align(State.storage_alignment) = undefined;
439 var state = try State.init(&bytes, small_limits);
440 state.activate();
441 defer _ = state.deinit();
442 try std.testing.expectEqual(@as(usize, 3), state.paths.capacity.paths_max);
443 try std.testing.expectEqual(@as(usize, 2), state.announces.capacity.announces_max);
444 try std.testing.expectEqual(
445 @as(usize, 4),
446 state.reverse_entries.capacity.reverse_entries_max,
447 );
448 try std.testing.expectEqual(@as(usize, 5), state.tags.capacity.hashes_max);
449 try std.testing.expectEqual(
450 @as(usize, 6),
451 state.inflight_requests.capacity.inflight_requests_max,
452 );
453 try std.testing.expectEqual(@as(usize, 7), state.discoveries.capacity.discoveries_max);
454 try std.testing.expectEqual(@as(usize, 8), state.links.capacity.links_max);
455 try std.testing.expectEqual(
456 @as(usize, 9),
457 state.link_entries.capacity.link_entries_max,
458 );
459 try std.testing.expect(state.identity_hash == null);
460 try std.testing.expect(!state.enabled);
461 state.configure(@splat(0xb0), true);
462 try std.testing.expectEqualSlices(u8, &@as([16]u8, @splat(0xb0)), &state.identity_hash.?);
463 try std.testing.expect(state.enabled);
464 }
465
466 test "transport state rejects zero limits, summation overflow, and short storage" {
467 const limits = StateLimits{
468 .paths_max = 1,
469 .announces_max = 1,
470 .reverse_entries_max = 1,
471 .path_request_tags_max = 1,
472 .inflight_requests_max = 1,
473 .discoveries_max = 1,
474 .links_max = 1,
475 .link_entries_max = 1,
476 };
477 const fields = .{
478 "paths_max",
479 "announces_max",
480 "reverse_entries_max",
481 "path_request_tags_max",
482 "inflight_requests_max",
483 "discoveries_max",
484 "links_max",
485 "link_entries_max",
486 };
487 inline for (fields) |field| {
488 var zero = limits;
489 @field(zero, field) = 0;
490 try std.testing.expectError(error.InvalidLimit, StateCapacity.derive(zero));
491 }
492 var overflowing = limits;
493 overflowing.paths_max = std.math.maxInt(usize) / @sizeOf(path.Entry);
494 overflowing.discoveries_max = std.math.maxInt(usize) / @sizeOf(discoveries.Entry);
495 try std.testing.expectError(error.CapacityOverflow, StateCapacity.derive(overflowing));
496 var overflowing_links = limits;
497 overflowing_links.links_max = std.math.maxInt(usize) / @sizeOf(links.Entry) + 1;
498 try std.testing.expectError(error.CapacityOverflow, StateCapacity.derive(overflowing_links));
499 const capacity = comptime StateCapacity.derive(limits) catch unreachable;
500 var bytes: [capacity.storage_bytes + State.storage_alignment]u8 align(State.storage_alignment) =
501 undefined;
502 try std.testing.expectError(error.StorageLengthMismatch, State.init(&bytes, limits));
503 }