lib/reticulum/src/node/effect.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const carrier = @import("../carrier/root.zig");
4 const packet = @import("../packet/root.zig");
5 const event = @import("event.zig");
6 const timer = @import("timer.zig");
7 const transport = @import("transport/root.zig");
8
9 pub const PersistKind = enum(u8) {
10 known_identity,
11 known_ratchet,
12 ratchet_ring,
13 };
14
15 pub const Code = enum(u8) {
16 unregistered_interface,
17 frame_too_large,
18 ifac_unexpected_flag,
19 ifac_missing_flag,
20 ifac_invalid_code,
21 ifac_truncated,
22 malformed_packet,
23 duplicate_packet,
24 packet_filtered,
25 no_path,
26 path_request_malformed,
27 path_request_duplicate,
28 path_request_batched,
29 invalid_announce,
30 own_announce,
31 announce_key_changed,
32 announce_table_full,
33 discovery_table_full,
34 announce_relay_too_large,
35 unknown_destination,
36 destination_type_mismatch,
37 decryption_failed,
38 proof_rejected,
39 proof_relay_wrong_interface,
40 links_unsupported,
41 links_full,
42 link_request_invalid,
43 link_request_duplicate,
44 unknown_link,
45 link_state_mismatch,
46 link_wrong_interface,
47 link_close_invalid,
48 link_entries_full,
49 link_relay_early,
50 link_relay_no_direction,
51 unsupported_context,
52 storage_failed,
53 };
54
55 /// Records why a link closed: a deadline passed, the initiator closed it, or the responder closed
56 /// it. Reticulum@1.5.0 RNS/Link.py:116-118 names the same three teardown reasons `TIMEOUT`,
57 /// `INITIATOR_CLOSED`, and `DESTINATION_CLOSED`.
58 pub const LinkCloseReason = enum(u8) {
59 timeout = 1,
60 initiator_closed = 2,
61 destination_closed = 3,
62 };
63
64 /// Reports a link request the node sent. Every later effect of that link and its timer carry the
65 /// same link id, a value Reticulum@1.5.0 RNS/Link.py:316,320 computes ahead of the request leaving.
66 pub const LinkRequested = struct {
67 link_id: [16]u8,
68 destination: [16]u8,
69 };
70
71 /// Reports a link that became active, naming the carrier it runs on, so a caller waits for this
72 /// before it sends anything over the link. An initiator counts its round trip time in whole seconds
73 /// from the request to the proof, and Reticulum@1.5.0 RNS/Link.py:419 counts the same span in
74 /// fractional seconds. A responder's round trip time is the larger of its own whole-second
75 /// measurement and the time the initiator sent, as Reticulum@1.5.0 RNS/Link.py:518-522 computes it.
76 pub const LinkEstablished = struct {
77 link_id: [16]u8,
78 destination: [16]u8,
79 role: transport.links.Role,
80 rtt: f64,
81 interface: carrier.Index,
82 };
83
84 /// Reports a link that closed and why, so a caller drops its own state for the link when this
85 /// arrives. The node took the link out of its pool before it appended this effect, so the pool
86 /// holds no copy of the link's keys. Reticulum@1.5.0 RNS/Link.py:690-694 drops the link keys in its
87 /// own close.
88 pub const LinkClosed = struct {
89 link_id: [16]u8,
90 destination: [16]u8,
91 reason: LinkCloseReason,
92 };
93
94 /// Hands the application one packet of link data after decryption, so a caller reads the
95 /// application's plaintext here along with whether it has to prove it. `proof_requested` is set
96 /// under the `.app` proof strategy alone, and the application answers it with a link proof event
97 /// carrying that same packet hash. Under `.all` the node has sent that proof on its own account, as
98 /// Reticulum@1.5.0 RNS/Link.py:948-968 sends it.
99 pub const LinkDelivery = struct {
100 link_id: [16]u8,
101 packet_hash: [32]u8,
102 plaintext: []const u8,
103 proof_requested: bool,
104 };
105
106 /// Reports that another node asked for a path to one of this node's own destinations, naming the
107 /// carrier the question came in on, so a caller answers by announcing the named destination on that
108 /// same carrier as a path response.
109 pub const PathRequest = struct {
110 destination: [16]u8,
111 interface: carrier.Index,
112 };
113
114 /// Reports an announce whose signature checked out and whose path the node took, so a caller learns
115 /// from this that a destination exists and that the node can now reach it. The effect carries the
116 /// destination, the identity hash and public key behind it, the application data the announce
117 /// carried, how many hops away it came from, whether it carried a rotating key, and whether it
118 /// answered a path request.
119 pub const AnnounceReceived = struct {
120 destination_hash: [16]u8,
121 identity_hash: [16]u8,
122 public_key: [64]u8,
123 app_data: []const u8,
124 hops: u8,
125 rotating_key_present: bool,
126 path_response: bool,
127 };
128
129 pub const Effect = union(enum) {
130 carrier_send: struct {
131 interface: carrier.Index,
132 frame: []const u8,
133 },
134 application_delivery: struct {
135 destination: [16]u8,
136 packet_hash: [32]u8,
137 plaintext: []const u8,
138 ratchet_id: ?[10]u8,
139 proof_requested: bool,
140 interface: carrier.Index,
141 },
142 announce_received: AnnounceReceived,
143 path_request: PathRequest,
144 receipt_update: struct {
145 packet_hash: packet.Hash,
146 status: packet.receipt.Status,
147 rtt: ?timer.Seconds,
148 },
149 persist: struct {
150 kind: PersistKind,
151 key: [16]u8,
152 bytes: []const u8,
153 token: event.PersistToken,
154 },
155 schedule_timer: struct {
156 id: timer.TimerId,
157 at: timer.Seconds,
158 },
159 diagnostic: struct {
160 code: Code,
161 packet_hash: ?[32]u8,
162 },
163 link_requested: LinkRequested,
164 link_established: LinkEstablished,
165 link_delivery: LinkDelivery,
166 link_closed: LinkClosed,
167 };
168
169 /// Gives the most effects one event can produce, so a caller sizes its effect storage from this
170 /// bound. An announce reaches that number: it reports the announce, arms one timer, and sends one
171 /// answer over every one of 256 carriers. A link open with no known path reaches it too: it reports
172 /// the request, arms one timer, and sends that request over every one of 256 carriers.
173 pub const effects_per_event_max: u16 = 258;
174 /// Gives the most byte slices one event's effects retain, so a caller sizes the effect list's frame
175 /// storage from this bound. One delivery that also proves reaches that number, retaining the
176 /// plaintext and 256 carrier frames.
177 pub const effect_frames_per_event_max: u16 = 257;
178
179 const EffectsLimits = struct {
180 effects_max: usize,
181 frames_max: usize,
182 };
183
184 const EffectsCapacity = struct {
185 effects_max: usize,
186 frames_max: usize,
187 effect_bytes: usize,
188 frame_bytes: usize,
189 storage_bytes: usize,
190
191 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
192
193 pub fn derive(limits: EffectsLimits) DeriveError!EffectsCapacity {
194 if (limits.effects_max == 0) return error.InvalidLimit;
195 if (limits.frames_max == 0) return error.InvalidLimit;
196 const effects_max = limits.effects_max;
197 const frames_max = limits.frames_max;
198 const effect_bytes = alloc_phase.capacity.mul(
199 usize,
200 effects_max,
201 @sizeOf(Effect),
202 ) catch return error.CapacityOverflow;
203 const frame_bytes = alloc_phase.capacity.mul(
204 usize,
205 frames_max,
206 @sizeOf(carrier.Frame),
207 ) catch return error.CapacityOverflow;
208 const storage_bytes = alloc_phase.capacity.add(
209 usize,
210 effect_bytes,
211 frame_bytes,
212 ) catch return error.CapacityOverflow;
213 return .{
214 .effects_max = effects_max,
215 .frames_max = frames_max,
216 .effect_bytes = effect_bytes,
217 .frame_bytes = frame_bytes,
218 .storage_bytes = storage_bytes,
219 };
220 }
221 };
222
223 pub const Effects = struct {
224 phase: alloc_phase.capacity.Phase,
225 capacity: Capacity,
226 storage: Storage,
227 entries: []Effect,
228 frames: []carrier.Frame,
229 len: usize = 0,
230 frames_used: usize = 0,
231
232 pub const storage_alignment: usize = 8;
233 pub const Storage = []align(storage_alignment) u8;
234 pub const Limits: type = EffectsLimits;
235 pub const Capacity: type = EffectsCapacity;
236 pub const Exhaustion = error{Full};
237 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
238 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
239 .transition_steps_max = 2,
240 .cleanup_steps_per_call_max = 0,
241 .cleanup_calls_at_capacity_max = 0,
242 };
243 pub const claim: alloc_phase.capacity.Declaration = .{
244 .source = .{
245 .id = "reticulum.effects",
246 .kind = .phase_static,
247 .limit_source = .caller,
248 .storage = .{
249 .covered = &.{
250 .{
251 .id = "caller_effect_entries",
252 .lifetime = .transferred,
253 .detail = "caller storage for bounded effect values",
254 },
255 .{
256 .id = "caller_effect_frames",
257 .lifetime = .transferred,
258 .detail = "caller storage for bounded inline effect frame copies",
259 },
260 },
261 .excluded = &.{
262 "event input slices",
263 "carrier devices, application callbacks, and persistence state",
264 },
265 },
266 .capacity = .{
267 .inputs = &.{
268 alloc_phase.capacity.bindInput(EffectsLimits, "effects_max", "effects_max"),
269 alloc_phase.capacity.bindInput(EffectsLimits, "frames_max", "frames_max"),
270 },
271 .type_selectors = &.{
272 alloc_phase.capacity.bindType(Effect, "effect"),
273 alloc_phase.capacity.bindType(carrier.Frame, "frame"),
274 },
275 .nodes = &.{
276 .{ .input = 0 },
277 .{ .scale = .{
278 .node = 0,
279 .coefficient = .{ .size_of_concrete_type = 0 },
280 } },
281 .{ .input = 1 },
282 .{ .scale = .{
283 .node = 2,
284 .coefficient = .{ .size_of_concrete_type = 1 },
285 } },
286 .{ .add = .{ .left = 1, .right = 3 } },
287 },
288 .assertions = &.{.{
289 .scope = .closure_total,
290 .measure = .retained,
291 .relation = .exact,
292 .expression = 4,
293 }},
294 },
295 .overload = .{
296 .kind = .reject_before_mutation,
297 .detail = "full effect or frame admission preserves every retained effect",
298 },
299 .risks = .{
300 .transitive = .{
301 .status = .excluded,
302 .detail = "effect copying calls no allocating owner",
303 },
304 .foreign = .{
305 .status = .excluded,
306 .detail = "the effect sink crosses no foreign boundary",
307 },
308 },
309 .work = .{ .equation = "push copies at most one frame and one effect" },
310 .obligations = &.{
311 .{ .key = "reticulum_effects_capacity", .role = .capacity_model },
312 .{ .key = "reticulum_effects_overload", .role = .overload },
313 .{ .key = "reticulum_effects_work", .role = .work_bound },
314 },
315 },
316 .bindings = .{
317 .owner = @This(),
318 .seal = .{
319 .family = alloc_phase.capacity.selector(@This().activate),
320 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
321 },
322 .teardown = .{
323 .family = alloc_phase.capacity.selector(@This().deinit),
324 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
325 },
326 },
327 };
328
329 pub fn init(storage: Storage, limits: Limits) InitError!Effects {
330 const capacity = try Capacity.derive(limits);
331 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
332 const entries = std.mem.bytesAsSlice(Effect, storage[0..capacity.effect_bytes]);
333 const frame_storage: []align(@alignOf(carrier.Frame)) u8 = @alignCast(
334 storage[capacity.effect_bytes..],
335 );
336 const frames = std.mem.bytesAsSlice(carrier.Frame, frame_storage);
337 for (frames) |*frame| frame.* = .{};
338 return .{
339 .phase = .initialization,
340 .capacity = capacity,
341 .storage = storage,
342 .entries = entries,
343 .frames = frames,
344 };
345 }
346
347 pub fn activate(self: *Effects) void {
348 std.debug.assert(self.phase == .initialization);
349 std.debug.assert(self.len == 0);
350 std.debug.assert(self.frames_used == 0);
351 self.phase = .steady;
352 }
353
354 pub fn push(self: *Effects, value: Effect) Exhaustion!void {
355 std.debug.assert(self.phase == .steady);
356 if (self.len == self.capacity.effects_max) return error.Full;
357 const retained: Effect = switch (value) {
358 .carrier_send => |send| .{ .carrier_send = .{
359 .interface = send.interface,
360 .frame = try self.retain(send.frame),
361 } },
362 .application_delivery => |delivery| .{ .application_delivery = .{
363 .destination = delivery.destination,
364 .packet_hash = delivery.packet_hash,
365 .plaintext = try self.retain(delivery.plaintext),
366 .ratchet_id = delivery.ratchet_id,
367 .proof_requested = delivery.proof_requested,
368 .interface = delivery.interface,
369 } },
370 .announce_received => |announce| .{ .announce_received = .{
371 .destination_hash = announce.destination_hash,
372 .identity_hash = announce.identity_hash,
373 .public_key = announce.public_key,
374 .app_data = try self.retain(announce.app_data),
375 .hops = announce.hops,
376 .rotating_key_present = announce.rotating_key_present,
377 .path_response = announce.path_response,
378 } },
379 .link_delivery => |delivery| .{ .link_delivery = .{
380 .link_id = delivery.link_id,
381 .packet_hash = delivery.packet_hash,
382 .plaintext = try self.retain(delivery.plaintext),
383 .proof_requested = delivery.proof_requested,
384 } },
385 .persist => |persist| .{ .persist = .{
386 .kind = persist.kind,
387 .key = persist.key,
388 .bytes = try self.retain(persist.bytes),
389 .token = persist.token,
390 } },
391 .receipt_update,
392 .schedule_timer,
393 .diagnostic,
394 .path_request,
395 .link_requested,
396 .link_established,
397 .link_closed,
398 => value,
399 };
400 self.entries[self.len] = retained;
401 self.len += 1;
402 }
403
404 pub fn items(self: *const Effects) []const Effect {
405 std.debug.assert(self.phase == .steady);
406 return self.entries[0..self.len];
407 }
408
409 pub fn reset(self: *Effects) void {
410 std.debug.assert(self.phase == .steady);
411 self.len = 0;
412 self.frames_used = 0;
413 }
414
415 pub fn deinit(self: *Effects) Storage {
416 std.debug.assert(self.phase == .steady);
417 self.phase = .teardown;
418 const storage = self.storage;
419 self.* = undefined;
420 return storage;
421 }
422
423 fn retain(self: *Effects, bytes: []const u8) Exhaustion![]const u8 {
424 if (self.frames_used == self.capacity.frames_max) return error.Full;
425 const frame = carrier.Frame.init(bytes) catch return error.Full;
426 self.frames[self.frames_used] = frame;
427 const retained = self.frames[self.frames_used].slice();
428 self.frames_used += 1;
429 return retained;
430 }
431 };
432
433 comptime {
434 alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Effects);
435 }
436
437 fn diagnostic() Effect {
438 return .{ .diagnostic = .{ .code = .duplicate_packet, .packet_hash = null } };
439 }
440
441 test "effects admit maximum and reject maximum plus one" {
442 comptime {
443 @stardustClaim(alloc_phase.capacity.witness(
444 Effects,
445 "reticulum_effects_capacity",
446 ), null, null, null, null, null, null);
447 @stardustClaim(alloc_phase.capacity.witness(
448 Effects,
449 "reticulum_effects_overload",
450 ), null, null, null, null, null, null);
451 @stardustClaim(alloc_phase.capacity.witness(
452 Effects,
453 "reticulum_effects_work",
454 ), null, null, null, null, null, null);
455 }
456 const capacity = comptime EffectsCapacity.derive(.{
457 .effects_max = 3,
458 .frames_max = 3,
459 }) catch unreachable;
460 var bytes: [capacity.storage_bytes]u8 align(Effects.storage_alignment) = undefined;
461 var effects = try Effects.init(&bytes, .{ .effects_max = 3, .frames_max = 3 });
462 effects.activate();
463 defer _ = effects.deinit();
464 for (0..3) |_| try effects.push(diagnostic());
465 try std.testing.expectError(error.Full, effects.push(diagnostic()));
466 try std.testing.expectEqual(@as(usize, 3), effects.items().len);
467 }
468
469 test "effect frames admit maximum and reject maximum plus one" {
470 const capacity = comptime EffectsCapacity.derive(.{
471 .effects_max = 3,
472 .frames_max = 2,
473 }) catch unreachable;
474 var bytes: [capacity.storage_bytes]u8 align(Effects.storage_alignment) = undefined;
475 var effects = try Effects.init(&bytes, .{ .effects_max = 3, .frames_max = 2 });
476 effects.activate();
477 defer _ = effects.deinit();
478 const value = Effect{ .carrier_send = .{ .interface = 0, .frame = "frame" } };
479 try effects.push(value);
480 try effects.push(value);
481 try std.testing.expectError(error.Full, effects.push(value));
482 try std.testing.expectEqualSlices(u8, "frame", effects.items()[0].carrier_send.frame);
483 }
484
485 test "effects retain every slice in their frame pool" {
486 const capacity = comptime EffectsCapacity.derive(.{
487 .effects_max = 3,
488 .frames_max = 3,
489 }) catch unreachable;
490 var bytes: [capacity.storage_bytes]u8 align(Effects.storage_alignment) = undefined;
491 var effects = try Effects.init(&bytes, .{ .effects_max = 3, .frames_max = 3 });
492 effects.activate();
493 defer _ = effects.deinit();
494 var carrier_bytes = [_]u8{ 'o', 'n', 'e' };
495 var plaintext = [_]u8{ 't', 'w', 'o' };
496 var persisted = [_]u8{ 't', 'r', 'i' };
497 try effects.push(.{ .carrier_send = .{ .interface = 0, .frame = &carrier_bytes } });
498 try effects.push(.{ .application_delivery = .{
499 .destination = @splat(1),
500 .packet_hash = @splat(2),
501 .plaintext = &plaintext,
502 .ratchet_id = null,
503 .proof_requested = false,
504 .interface = 0,
505 } });
506 try effects.push(.{ .persist = .{
507 .kind = .known_identity,
508 .key = @splat(3),
509 .bytes = &persisted,
510 .token = 4,
511 } });
512 carrier_bytes[0] = 'x';
513 plaintext[0] = 'x';
514 persisted[0] = 'x';
515 try std.testing.expectEqualSlices(u8, "one", effects.items()[0].carrier_send.frame);
516 try std.testing.expectEqualSlices(
517 u8,
518 "two",
519 effects.items()[1].application_delivery.plaintext,
520 );
521 try std.testing.expectEqualSlices(u8, "tri", effects.items()[2].persist.bytes);
522 }
523
524 test "announce effects retain application data in their frame pool" {
525 const capacity = comptime EffectsCapacity.derive(.{
526 .effects_max = 1,
527 .frames_max = 1,
528 }) catch unreachable;
529 var bytes: [capacity.storage_bytes]u8 align(Effects.storage_alignment) = undefined;
530 var effects = try Effects.init(&bytes, .{ .effects_max = 1, .frames_max = 1 });
531 effects.activate();
532 defer _ = effects.deinit();
533 var app_data = [_]u8{ 'a', 'p', 'p' };
534 try effects.push(.{ .announce_received = .{
535 .destination_hash = @splat(1),
536 .identity_hash = @splat(2),
537 .public_key = @splat(3),
538 .app_data = &app_data,
539 .hops = 1,
540 .rotating_key_present = true,
541 .path_response = false,
542 } });
543 app_data[0] = 'x';
544 try std.testing.expectEqualSlices(u8, "app", effects.items()[0].announce_received.app_data);
545 }
546
547 test "effect frame bytes admit maximum and reject maximum plus one" {
548 const capacity = comptime EffectsCapacity.derive(.{
549 .effects_max = 2,
550 .frames_max = 2,
551 }) catch unreachable;
552 var storage: [capacity.storage_bytes]u8 align(Effects.storage_alignment) = undefined;
553 var effects = try Effects.init(&storage, .{ .effects_max = 2, .frames_max = 2 });
554 effects.activate();
555 defer _ = effects.deinit();
556 var frame: [carrier.frame_bytes_max + 1]u8 = @splat(0xa5);
557 try effects.push(.{ .carrier_send = .{
558 .interface = 0,
559 .frame = frame[0..][0..carrier.frame_bytes_max],
560 } });
561 try std.testing.expectError(error.Full, effects.push(.{
562 .carrier_send = .{ .interface = 0, .frame = &frame },
563 }));
564 }