lib/reticulum/src/node/transport/links.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const carrier = @import("../../carrier/root.zig");
4 const ProofStrategy = @import("../../destination/root.zig").registry.ProofStrategy;
5
6 pub const Seconds = u64;
7
8 /// Distinguishes which of a link's two ends this node is, so a caller tells
9 /// which end of a session this node holds, because the two ends answer for
10 /// different things. Reticulum@1.5.0 RNS/Link.py:274-280 carries the same
11 /// distinction on its own object.
12 pub const Role = enum(u1) {
13 initiator,
14 responder,
15 };
16
17 /// Tracks how far along a link in the pool is, so a caller knows whether a
18 /// session may carry traffic yet and how close it is to closing. The end that
19 /// opened a link waits at `pending` until a proof checks out. Silence lasting
20 /// twice the keepalive period moves a link to `stale`, and five seconds more of
21 /// it closes the link. One packet arriving over the link's own carrier brings
22 /// the link back to `active`, as Reticulum@1.5.0
23 /// RNS/Link.py:110-113,753-766,938-946 arranges.
24 pub const Status = enum(u2) {
25 pending,
26 handshake,
27 active,
28 stale,
29 };
30
31 /// Records one link this node holds an end of, so a caller sees the keys and
32 /// the instants that decide a session's deadlines. On an initiator, the
33 /// ephemeral Ed25519 private key stays and the X25519 one is wiped at the
34 /// moment the link activates. On a responder, both private key fields read as
35 /// zero throughout. The instants of the last inbound packet, the last outbound
36 /// packet, the last keepalive sent, and the last validated data proof only move
37 /// forward, and they fix the keepalive and stale deadlines. The closing second
38 /// carries a value only while a link sits at `stale`, and reads zero at every
39 /// other moment, as Reticulum@1.5.0 RNS/Link.py:245-249,744-766 arranges.
40 pub const Entry = struct {
41 id: [16]u8,
42 destination: [16]u8,
43 encryption_private: [32]u8,
44 signing_private: [32]u8,
45 peer_signing_public: [32]u8,
46 derived_key: [64]u8,
47 request_time: Seconds,
48 establishment_timeout: Seconds,
49 activated_at: Seconds,
50 last_inbound: Seconds,
51 last_outbound: Seconds,
52 last_keepalive: Seconds,
53 last_proof: Seconds,
54 close_at: Seconds,
55 rtt: f64,
56 expected_hops: u8,
57 attached: carrier.Index,
58 role: Role,
59 status: Status,
60 rebalanced: bool,
61 proof_strategy: ProofStrategy,
62
63 /// Writes zero over every byte of the record, key material included, so a
64 /// closed session leaves no key material behind in the pool.
65 pub fn zero(self: *Entry) void {
66 std.crypto.secureZero(u8, std.mem.asBytes(self));
67 }
68 };
69
70 const TableLimits = struct {
71 links_max: usize,
72 };
73
74 const TableCapacity = struct {
75 links_max: usize,
76 storage_bytes: usize,
77
78 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
79
80 pub fn derive(limits: TableLimits) DeriveError!TableCapacity {
81 if (limits.links_max == 0) return error.InvalidLimit;
82 const storage_bytes = alloc_phase.capacity.mul(
83 usize,
84 limits.links_max,
85 @sizeOf(Entry),
86 ) catch return error.CapacityOverflow;
87 return .{ .links_max = limits.links_max, .storage_bytes = storage_bytes };
88 }
89 };
90
91 /// Provides room for `links_max` links this node holds an end of, carved from
92 /// bytes the caller supplies. Links sit in the order they were written, and one
93 /// link id appears at most once.
94 pub const Table = struct {
95 phase: alloc_phase.capacity.Phase,
96 capacity: Capacity,
97 storage: Storage,
98 entries: []Entry,
99 len: usize = 0,
100
101 pub const storage_alignment: usize = 8;
102 pub const Storage = []align(storage_alignment) u8;
103 pub const Limits: type = TableLimits;
104 pub const Capacity: type = TableCapacity;
105 pub const Exhaustion = error{Full};
106 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
107 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
108 .transition_steps_max = 65_536,
109 .cleanup_steps_per_call_max = 0,
110 .cleanup_calls_at_capacity_max = 0,
111 };
112 pub const claim: alloc_phase.capacity.Declaration = .{
113 .source = .{
114 .id = "reticulum.links",
115 .kind = .phase_static,
116 .limit_source = .caller,
117 .storage = .{
118 .covered = &.{.{
119 .id = "caller_link_table",
120 .lifetime = .transferred,
121 .detail = "caller storage for open link endpoints and their keys",
122 }},
123 .excluded = &.{
124 "link frames in effect storage",
125 "local destination identities",
126 },
127 },
128 .capacity = .{
129 .inputs = &.{alloc_phase.capacity.bindInput(
130 Limits,
131 "links_max",
132 "links_max",
133 )},
134 .type_selectors = &.{alloc_phase.capacity.bindType(Entry, "link")},
135 .nodes = &.{
136 .{ .input = 0 },
137 .{ .scale = .{
138 .node = 0,
139 .coefficient = .{ .size_of_concrete_type = 0 },
140 } },
141 },
142 .assertions = &.{.{
143 .scope = .closure_total,
144 .measure = .retained,
145 .relation = .exact,
146 .expression = 1,
147 }},
148 },
149 .overload = .{
150 .kind = .reject_before_mutation,
151 .detail = "a full link table rejects a new link and keeps every open link",
152 },
153 .risks = .{
154 .transitive = .{
155 .status = .excluded,
156 .detail = "link operations call no allocating owner",
157 },
158 .foreign = .{
159 .status = .excluded,
160 .detail = "link storage crosses no foreign boundary",
161 },
162 },
163 .work = .{ .equation = "link operations scan at most links_max entries" },
164 .obligations = &.{
165 .{ .key = "reticulum_links_capacity", .role = .capacity_model },
166 .{ .key = "reticulum_links_overload", .role = .overload },
167 .{ .key = "reticulum_links_work", .role = .work_bound },
168 },
169 },
170 .bindings = .{
171 .owner = @This(),
172 .seal = .{
173 .family = alloc_phase.capacity.selector(@This().activate),
174 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
175 },
176 .teardown = .{
177 .family = alloc_phase.capacity.selector(@This().deinit),
178 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
179 },
180 },
181 };
182
183 pub fn init(storage: Storage, limits: Limits) InitError!Table {
184 const capacity = try Capacity.derive(limits);
185 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
186 const entries = std.mem.bytesAsSlice(Entry, storage);
187 std.debug.assert(entries.len == capacity.links_max);
188 for (entries) |*entry| entry.zero();
189 return .{
190 .phase = .initialization,
191 .capacity = capacity,
192 .storage = storage,
193 .entries = entries,
194 };
195 }
196
197 pub fn activate(self: *Table) void {
198 std.debug.assert(self.phase == .initialization);
199 std.debug.assert(self.len == 0);
200 self.phase = .steady;
201 }
202
203 /// Looks one link id up in the pool, answering null when the id is absent,
204 /// so a caller finds the session an arriving packet belongs to. The lookup
205 /// asserts along the way that the id matched at most one link.
206 pub fn find(self: *Table, id: [16]u8) ?*Entry {
207 std.debug.assert(self.phase == .steady);
208 std.debug.assert(self.len <= self.capacity.links_max);
209 var found: ?*Entry = null;
210 for (self.entries[0..self.len]) |*entry| {
211 if (!std.mem.eql(u8, &entry.id, &id)) continue;
212 std.debug.assert(found == null);
213 found = entry;
214 }
215 return found;
216 }
217
218 /// Returns whether the pool holds `links_max` links, so a caller asks
219 /// before it opens or accepts a session, because a full pool refuses one.
220 pub fn full(self: *const Table) bool {
221 std.debug.assert(self.phase == .steady);
222 std.debug.assert(self.len <= self.capacity.links_max);
223 return self.len == self.capacity.links_max;
224 }
225
226 /// Writes a link at the end of the pool and hands back a pointer to it, so
227 /// a caller records a session it has opened or accepted. The write asserts
228 /// that the link id is new to the pool. A pool already holding `links_max`
229 /// links returns `error.Full` and leaves every link as it was.
230 pub fn insert(self: *Table, entry: Entry) Exhaustion!*Entry {
231 std.debug.assert(self.phase == .steady);
232 std.debug.assert(self.find(entry.id) == null);
233 if (self.full()) return error.Full;
234 self.entries[self.len] = entry;
235 self.len += 1;
236 std.debug.assert(self.len <= self.capacity.links_max);
237 return &self.entries[self.len - 1];
238 }
239
240 /// Takes one link id out of the pool and answers whether the id was
241 /// present, so a caller drops a session that closed. Links written after it
242 /// move down one place, and the freed place is written over with zeros.
243 pub fn remove(self: *Table, id: [16]u8) bool {
244 std.debug.assert(self.phase == .steady);
245 for (self.entries[0..self.len], 0..) |entry, index| {
246 if (!std.mem.eql(u8, &entry.id, &id)) continue;
247 std.mem.copyForwards(
248 Entry,
249 self.entries[index .. self.len - 1],
250 self.entries[index + 1 .. self.len],
251 );
252 self.len -= 1;
253 self.entries[self.len].zero();
254 std.debug.assert(self.len < self.capacity.links_max);
255 std.debug.assert(self.find(id) == null);
256 return true;
257 }
258 return false;
259 }
260
261 pub fn count(self: *const Table) usize {
262 std.debug.assert(self.phase == .steady);
263 std.debug.assert(self.len <= self.capacity.links_max);
264 return self.len;
265 }
266
267 pub fn deinit(self: *Table) Storage {
268 std.debug.assert(self.phase == .steady);
269 std.debug.assert(self.len <= self.capacity.links_max);
270 for (self.entries[0..self.len]) |*entry| entry.zero();
271 self.phase = .teardown;
272 const storage = self.storage;
273 self.* = undefined;
274 return storage;
275 }
276 };
277
278 comptime {
279 alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Table);
280 }
281
282 fn entryFor(byte: u8) Entry {
283 return .{
284 .id = @splat(byte),
285 .destination = @splat(0xd0),
286 .encryption_private = @splat(0xa1),
287 .signing_private = @splat(0xa2),
288 .peer_signing_public = @splat(0xa4),
289 .derived_key = @splat(0xa5),
290 .request_time = 100,
291 .establishment_timeout = 366,
292 .activated_at = 0,
293 .last_inbound = 100,
294 .last_outbound = 100,
295 .last_keepalive = 0,
296 .last_proof = 0,
297 .close_at = 0,
298 .rtt = 0,
299 .expected_hops = 1,
300 .attached = 0,
301 .role = .responder,
302 .status = .handshake,
303 .rebalanced = false,
304 .proof_strategy = .none,
305 };
306 }
307
308 test "links admit maximum and reject maximum plus one" {
309 comptime {
310 @stardustClaim(alloc_phase.capacity.witness(
311 Table,
312 "reticulum_links_capacity",
313 ), null, null, null, null, null, null);
314 @stardustClaim(alloc_phase.capacity.witness(
315 Table,
316 "reticulum_links_overload",
317 ), null, null, null, null, null, null);
318 @stardustClaim(alloc_phase.capacity.witness(
319 Table,
320 "reticulum_links_work",
321 ), null, null, null, null, null, null);
322 }
323 const capacity = comptime TableCapacity.derive(.{ .links_max = 3 }) catch unreachable;
324 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
325 var table = try Table.init(&bytes, .{ .links_max = 3 });
326 table.activate();
327 defer _ = table.deinit();
328 for (1..4) |value| _ = try table.insert(entryFor(@intCast(value)));
329 try std.testing.expect(table.full());
330 try std.testing.expectError(error.Full, table.insert(entryFor(4)));
331 try std.testing.expectEqual(@as(usize, 3), table.count());
332 for (1..4) |value| try std.testing.expect(table.find(@splat(@intCast(value))) != null);
333 try std.testing.expect(table.find(@splat(4)) == null);
334 }
335
336 test "link removal keeps order and zeroes the vacated slot" {
337 const capacity = comptime TableCapacity.derive(.{ .links_max = 3 }) catch unreachable;
338 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
339 var table = try Table.init(&bytes, .{ .links_max = 3 });
340 table.activate();
341 defer _ = table.deinit();
342 for (1..4) |value| _ = try table.insert(entryFor(@intCast(value)));
343 try std.testing.expect(table.remove(@splat(1)));
344 try std.testing.expect(!table.remove(@splat(1)));
345 try std.testing.expectEqual(@as(usize, 2), table.count());
346 try std.testing.expectEqual(@as(u8, 2), table.entries[0].id[0]);
347 try std.testing.expectEqual(@as(u8, 3), table.entries[1].id[0]);
348 try std.testing.expect(std.mem.allEqual(u8, std.mem.asBytes(&table.entries[2]), 0));
349 _ = try table.insert(entryFor(4));
350 try std.testing.expect(table.full());
351 }
352
353 test "link capacity rejects zero and overflowing limits" {
354 try std.testing.expectError(error.InvalidLimit, TableCapacity.derive(.{ .links_max = 0 }));
355 const overflowing = std.math.maxInt(usize) / @sizeOf(Entry) + 1;
356 try std.testing.expectError(
357 error.CapacityOverflow,
358 TableCapacity.derive(.{ .links_max = overflowing }),
359 );
360 }