lib/reticulum/src/node/transport/link/entries.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const carrier = @import("../../../carrier/root.zig");
4
5 pub const Seconds = u64;
6
7 /// Nine hundred seconds, the lifetime Reticulum@1.5.0 RNS/Transport.py:149
8 /// gives a validated relay. The figure is the stale time of Reticulum@1.5.0
9 /// RNS/Link.py:97-99 multiplied by 1.25, and this package computes the same
10 /// stale time as twice a keepalive period of at most 360 seconds.
11 pub const validated_timeout: Seconds = 900;
12
13 /// One link between two other nodes whose packets this node moves. A record
14 /// appears at the moment the node sends an arriving link request onward. The
15 /// record turns validated once the node has sent the answering proof back. The
16 /// record leaves the store at whichever second falls first: the one its proof
17 /// was due by, or the one 900 seconds past its last traffic.
18 pub const Entry = struct {
19 link_id: [16]u8,
20 destination: [16]u8,
21 next_hop: [16]u8,
22 timestamp: Seconds,
23 proof_deadline: Seconds,
24 next_hop_carrier: carrier.Index,
25 receiving_carrier: carrier.Index,
26 remaining_hops: u8,
27 taken_hops: u8,
28 validated: bool,
29
30 /// The earliest second at which this record leaves the store. A record
31 /// lives out the second its deadline names under Reticulum@1.5.0
32 /// RNS/Transport.py:850,855, so the answer here is the second after that
33 /// one.
34 pub fn dropsAt(self: *const Entry) Seconds {
35 if (!self.validated) return self.proof_deadline +| 1;
36 return self.timestamp +| validated_timeout +| 1;
37 }
38 };
39
40 const TableLimits = struct {
41 link_entries_max: usize,
42 };
43
44 const TableCapacity = struct {
45 link_entries_max: usize,
46 storage_bytes: usize,
47
48 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
49
50 pub fn derive(limits: TableLimits) DeriveError!TableCapacity {
51 if (limits.link_entries_max == 0) return error.InvalidLimit;
52 const storage_bytes = alloc_phase.capacity.mul(
53 usize,
54 limits.link_entries_max,
55 @sizeOf(Entry),
56 ) catch return error.CapacityOverflow;
57 return .{
58 .link_entries_max = limits.link_entries_max,
59 .storage_bytes = storage_bytes,
60 };
61 }
62 };
63
64 /// The store of links this node moves packets for, holding what Reticulum@1.5.0
65 /// RNS/Transport.py:1998-2009 keeps. Records sit in the order they were
66 /// written, and one link id appears at most once.
67 pub const Table = struct {
68 phase: alloc_phase.capacity.Phase,
69 capacity: Capacity,
70 storage: Storage,
71 entries: []Entry,
72 len: usize = 0,
73
74 pub const storage_alignment: usize = 8;
75 pub const Storage = []align(storage_alignment) u8;
76 pub const Limits: type = TableLimits;
77 pub const Capacity: type = TableCapacity;
78 pub const Exhaustion = error{Full};
79 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
80 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
81 .transition_steps_max = 65_536,
82 .cleanup_steps_per_call_max = 0,
83 .cleanup_calls_at_capacity_max = 0,
84 };
85 pub const claim: alloc_phase.capacity.Declaration = .{
86 .source = .{
87 .id = "reticulum.link_entries",
88 .kind = .phase_static,
89 .limit_source = .caller,
90 .storage = .{
91 .covered = &.{.{
92 .id = "caller_link_entry_table",
93 .lifetime = .transferred,
94 .detail = "caller storage for relayed links and their carriers",
95 }},
96 .excluded = &.{"relayed link frames in effect storage"},
97 },
98 .capacity = .{
99 .inputs = &.{alloc_phase.capacity.bindInput(
100 Limits,
101 "link_entries_max",
102 "link_entries_max",
103 )},
104 .type_selectors = &.{alloc_phase.capacity.bindType(Entry, "link_entry")},
105 .nodes = &.{
106 .{ .input = 0 },
107 .{ .scale = .{
108 .node = 0,
109 .coefficient = .{ .size_of_concrete_type = 0 },
110 } },
111 },
112 .assertions = &.{.{
113 .scope = .closure_total,
114 .measure = .retained,
115 .relation = .exact,
116 .expression = 1,
117 }},
118 },
119 .overload = .{
120 .kind = .reject_before_mutation,
121 .detail = "a full table drops the forwarded request and keeps every relay",
122 },
123 .risks = .{
124 .transitive = .{
125 .status = .excluded,
126 .detail = "link entry operations call no allocating owner",
127 },
128 .foreign = .{
129 .status = .excluded,
130 .detail = "link entry storage crosses no foreign boundary",
131 },
132 },
133 .work = .{ .equation = "operations scan at most link_entries_max entries" },
134 .obligations = &.{
135 .{ .key = "reticulum_link_entries_capacity", .role = .capacity_model },
136 .{ .key = "reticulum_link_entries_overload", .role = .overload },
137 .{ .key = "reticulum_link_entries_work", .role = .work_bound },
138 },
139 },
140 .bindings = .{
141 .owner = @This(),
142 .seal = .{
143 .family = alloc_phase.capacity.selector(@This().activate),
144 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
145 },
146 .teardown = .{
147 .family = alloc_phase.capacity.selector(@This().deinit),
148 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
149 },
150 },
151 };
152
153 pub fn init(storage: Storage, limits: Limits) InitError!Table {
154 const capacity = try Capacity.derive(limits);
155 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
156 const entries = std.mem.bytesAsSlice(Entry, storage);
157 std.debug.assert(entries.len == capacity.link_entries_max);
158 return .{
159 .phase = .initialization,
160 .capacity = capacity,
161 .storage = storage,
162 .entries = entries,
163 };
164 }
165
166 pub fn activate(self: *Table) void {
167 std.debug.assert(self.phase == .initialization);
168 std.debug.assert(self.len == 0);
169 self.phase = .steady;
170 }
171
172 /// Looks one link id up among the records, answering null when the id is
173 /// absent. The lookup asserts along the way that the id matched at most one
174 /// record.
175 pub fn find(self: *Table, link_id: [16]u8) ?*Entry {
176 std.debug.assert(self.phase == .steady);
177 std.debug.assert(self.len <= self.capacity.link_entries_max);
178 var found: ?*Entry = null;
179 for (self.entries[0..self.len]) |*entry| {
180 if (!std.mem.eql(u8, &entry.link_id, &link_id)) continue;
181 std.debug.assert(found == null);
182 found = entry;
183 }
184 return found;
185 }
186
187 /// Returns whether the table holds `link_entries_max` relays.
188 pub fn full(self: *const Table) bool {
189 std.debug.assert(self.phase == .steady);
190 std.debug.assert(self.len <= self.capacity.link_entries_max);
191 return self.len == self.capacity.link_entries_max;
192 }
193
194 /// Writes a record at the end of the store and hands back a pointer to it.
195 /// The write asserts that the link id is new to the store. A table already
196 /// holding `link_entries_max` relays returns `error.Full` and leaves every
197 /// relay as it was.
198 pub fn insert(self: *Table, entry: Entry) Exhaustion!*Entry {
199 std.debug.assert(self.phase == .steady);
200 std.debug.assert(self.find(entry.link_id) == null);
201 if (self.full()) return error.Full;
202 self.entries[self.len] = entry;
203 self.len += 1;
204 return &self.entries[self.len - 1];
205 }
206
207 /// Takes the record for one link id out and answers whether the id was
208 /// present. Records written after it move down one place, so the rest stay
209 /// in the order they were written. A pointer handed out earlier for that
210 /// place or a later one reaches a different record afterwards, so a caller
211 /// reads what it needs out of a record before it takes one out.
212 pub fn remove(self: *Table, link_id: [16]u8) bool {
213 std.debug.assert(self.phase == .steady);
214 for (self.entries[0..self.len], 0..) |entry, index| {
215 if (!std.mem.eql(u8, &entry.link_id, &link_id)) continue;
216 std.mem.copyForwards(
217 Entry,
218 self.entries[index .. self.len - 1],
219 self.entries[index + 1 .. self.len],
220 );
221 self.len -= 1;
222 std.debug.assert(self.find(link_id) == null);
223 return true;
224 }
225 return false;
226 }
227
228 /// Answers with the soonest second any record in the store leaves it. An
229 /// empty table gives null.
230 pub fn earliest(self: *const Table) ?Seconds {
231 std.debug.assert(self.phase == .steady);
232 var soonest: ?Seconds = null;
233 for (self.entries[0..self.len]) |*entry| {
234 const at = entry.dropsAt();
235 if (soonest == null or at < soonest.?) soonest = at;
236 }
237 return soonest;
238 }
239
240 /// Hands back the first record whose second has arrived by `now`, and null
241 /// once none has.
242 pub fn expired(self: *Table, now: Seconds) ?*Entry {
243 std.debug.assert(self.phase == .steady);
244 for (self.entries[0..self.len]) |*entry| {
245 if (now >= entry.dropsAt()) return entry;
246 }
247 return null;
248 }
249
250 pub fn count(self: *const Table) usize {
251 std.debug.assert(self.phase == .steady);
252 std.debug.assert(self.len <= self.capacity.link_entries_max);
253 return self.len;
254 }
255
256 pub fn deinit(self: *Table) Storage {
257 std.debug.assert(self.phase == .steady);
258 std.debug.assert(self.len <= self.capacity.link_entries_max);
259 self.phase = .teardown;
260 const storage = self.storage;
261 self.* = undefined;
262 return storage;
263 }
264 };
265
266 comptime {
267 alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Table);
268 }
269
270 fn entryFor(byte: u8) Entry {
271 return .{
272 .link_id = @splat(byte),
273 .destination = @splat(0xd0),
274 .next_hop = @splat(0xb0),
275 .timestamp = 100,
276 .proof_deadline = 112,
277 .next_hop_carrier = 1,
278 .receiving_carrier = 0,
279 .remaining_hops = 1,
280 .taken_hops = 1,
281 .validated = false,
282 };
283 }
284
285 test "link entries admit maximum and reject maximum plus one" {
286 comptime {
287 @stardustClaim(alloc_phase.capacity.witness(
288 Table,
289 "reticulum_link_entries_capacity",
290 ), null, null, null, null, null, null);
291 @stardustClaim(alloc_phase.capacity.witness(
292 Table,
293 "reticulum_link_entries_overload",
294 ), null, null, null, null, null, null);
295 @stardustClaim(alloc_phase.capacity.witness(
296 Table,
297 "reticulum_link_entries_work",
298 ), null, null, null, null, null, null);
299 }
300 const limits = TableLimits{ .link_entries_max = 3 };
301 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
302 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
303 var table = try Table.init(&bytes, limits);
304 table.activate();
305 defer _ = table.deinit();
306 for (1..4) |value| _ = try table.insert(entryFor(@intCast(value)));
307 try std.testing.expect(table.full());
308 try std.testing.expectError(error.Full, table.insert(entryFor(4)));
309 try std.testing.expectEqual(@as(usize, 3), table.count());
310 for (1..4) |value| try std.testing.expect(table.find(@splat(@intCast(value))) != null);
311 try std.testing.expect(table.find(@splat(4)) == null);
312 }
313
314 test "link entry removal keeps order and frees one slot" {
315 const limits = TableLimits{ .link_entries_max = 3 };
316 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
317 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
318 var table = try Table.init(&bytes, limits);
319 table.activate();
320 defer _ = table.deinit();
321 for (1..4) |value| _ = try table.insert(entryFor(@intCast(value)));
322 try std.testing.expect(table.remove(@splat(1)));
323 try std.testing.expect(!table.remove(@splat(1)));
324 try std.testing.expectEqual(@as(usize, 2), table.count());
325 try std.testing.expectEqual(@as(u8, 2), table.entries[0].link_id[0]);
326 try std.testing.expectEqual(@as(u8, 3), table.entries[1].link_id[0]);
327 _ = try table.insert(entryFor(4));
328 try std.testing.expect(table.full());
329 }
330
331 test "Reticulum@1.5.0 RNS/Transport.py:849-856 drops relays one second after each deadline" {
332 const limits = TableLimits{ .link_entries_max = 2 };
333 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
334 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
335 var table = try Table.init(&bytes, limits);
336 table.activate();
337 defer _ = table.deinit();
338 const unvalidated = try table.insert(entryFor(1));
339 try std.testing.expectEqual(@as(Seconds, 113), unvalidated.dropsAt());
340 try std.testing.expect(table.expired(112) == null);
341 try std.testing.expect(table.expired(113) != null);
342 unvalidated.validated = true;
343 unvalidated.timestamp = 200;
344 try std.testing.expectEqual(@as(Seconds, 201 + validated_timeout), unvalidated.dropsAt());
345 var later = entryFor(2);
346 later.proof_deadline = 300;
347 _ = try table.insert(later);
348 try std.testing.expectEqual(@as(Seconds, 301), table.earliest().?);
349 try std.testing.expect(table.expired(300) == null);
350 try std.testing.expect(table.expired(301) != null);
351 }
352
353 test "a relay deadline at the largest instant saturates and still sweeps" {
354 const limits = TableLimits{ .link_entries_max = 2 };
355 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
356 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
357 var table = try Table.init(&bytes, limits);
358 table.activate();
359 defer _ = table.deinit();
360 const last: Seconds = std.math.maxInt(Seconds);
361 var unproved = entryFor(1);
362 unproved.proof_deadline = last;
363 const held = try table.insert(unproved);
364 try std.testing.expectEqual(last, held.dropsAt());
365 var proved = entryFor(2);
366 proved.validated = true;
367 proved.timestamp = last;
368 const kept = try table.insert(proved);
369 try std.testing.expectEqual(last, kept.dropsAt());
370 try std.testing.expectEqual(last, table.earliest().?);
371 try std.testing.expect(table.expired(last - 1) == null);
372 try std.testing.expect(table.expired(last) != null);
373 }
374
375 test "link entry capacity rejects zero and overflowing limits" {
376 try std.testing.expectError(
377 error.InvalidLimit,
378 TableCapacity.derive(.{ .link_entries_max = 0 }),
379 );
380 const overflowing = std.math.maxInt(usize) / @sizeOf(Entry) + 1;
381 try std.testing.expectError(
382 error.CapacityOverflow,
383 TableCapacity.derive(.{ .link_entries_max = overflowing }),
384 );
385 }