lib/reticulum/src/node/transport/reverse.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 /// Four hundred and eighty seconds, the lifetime Reticulum@1.5.0
8 /// RNS/Transport.py:151 gives a reverse entry.
9 pub const timeout: Seconds = 480;
10
11 /// One packet this node moved onward, held until its proof comes back.
12 pub const Entry = struct {
13 truncated: [16]u8,
14 timestamp: Seconds,
15 receiving: carrier.Index,
16 outbound: carrier.Index,
17 };
18
19 /// Reports whether an entry still counts. An entry stops counting 480 seconds
20 /// past the second it was written, the age Reticulum@1.5.0
21 /// RNS/Transport.py:834-841 sets.
22 fn live(entry: *const Entry, now: Seconds) bool {
23 return now -| entry.timestamp <= timeout;
24 }
25
26 const TableLimits = struct {
27 reverse_entries_max: usize,
28 };
29
30 const TableCapacity = struct {
31 reverse_entries_max: usize,
32 storage_bytes: usize,
33
34 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
35
36 pub fn derive(limits: TableLimits) DeriveError!TableCapacity {
37 if (limits.reverse_entries_max == 0) return error.InvalidLimit;
38 const storage_bytes = alloc_phase.capacity.mul(
39 usize,
40 limits.reverse_entries_max,
41 @sizeOf(Entry),
42 ) catch return error.CapacityOverflow;
43 return .{
44 .reverse_entries_max = limits.reverse_entries_max,
45 .storage_bytes = storage_bytes,
46 };
47 }
48 };
49
50 /// Relayed packet carriers, matching Reticulum@1.5.0
51 /// RNS/Transport.py:2012-2018.
52 pub const Table = struct {
53 phase: alloc_phase.capacity.Phase,
54 capacity: Capacity,
55 storage: Storage,
56 entries: []Entry,
57 len: usize = 0,
58
59 pub const storage_alignment: usize = 8;
60 pub const Storage = []align(storage_alignment) u8;
61 pub const Limits: type = TableLimits;
62 pub const Capacity: type = TableCapacity;
63 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
64 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
65 .transition_steps_max = 65_536,
66 .cleanup_steps_per_call_max = 0,
67 .cleanup_calls_at_capacity_max = 0,
68 };
69 pub const claim: alloc_phase.capacity.Declaration = .{
70 .source = .{
71 .id = "reticulum.reverse_entries",
72 .kind = .phase_static,
73 .limit_source = .caller,
74 .storage = .{
75 .covered = &.{.{
76 .id = "caller_reverse_table",
77 .lifetime = .transferred,
78 .detail = "caller storage for relayed packet hashes and carriers",
79 }},
80 .excluded = &.{"relayed frames in effect storage"},
81 },
82 .capacity = .{
83 .inputs = &.{alloc_phase.capacity.bindInput(
84 Limits,
85 "reverse_entries_max",
86 "reverse_entries_max",
87 )},
88 .type_selectors = &.{alloc_phase.capacity.bindType(Entry, "reverse_entry")},
89 .nodes = &.{
90 .{ .input = 0 },
91 .{ .scale = .{
92 .node = 0,
93 .coefficient = .{ .size_of_concrete_type = 0 },
94 } },
95 },
96 .assertions = &.{.{
97 .scope = .closure_total,
98 .measure = .retained,
99 .relation = .exact,
100 .expression = 1,
101 }},
102 },
103 .overload = .{
104 .kind = .not_applicable,
105 .detail = "a new entry replaces its key, an expired entry, else the oldest",
106 },
107 .risks = .{
108 .transitive = .{
109 .status = .excluded,
110 .detail = "reverse operations call no allocating owner",
111 },
112 .foreign = .{
113 .status = .excluded,
114 .detail = "reverse storage crosses no foreign boundary",
115 },
116 },
117 .work = .{ .equation = "operations scan at most reverse_entries_max entries" },
118 .obligations = &.{
119 .{ .key = "reticulum_reverse_entries_capacity", .role = .capacity_model },
120 .{ .key = "reticulum_reverse_entries_replace", .role = .overload },
121 .{ .key = "reticulum_reverse_entries_work", .role = .work_bound },
122 },
123 },
124 .bindings = .{
125 .owner = @This(),
126 .seal = .{
127 .family = alloc_phase.capacity.selector(@This().activate),
128 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
129 },
130 .teardown = .{
131 .family = alloc_phase.capacity.selector(@This().deinit),
132 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
133 },
134 },
135 };
136
137 pub fn init(storage: Storage, limits: Limits) InitError!Table {
138 const capacity = try Capacity.derive(limits);
139 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
140 return .{
141 .phase = .initialization,
142 .capacity = capacity,
143 .storage = storage,
144 .entries = std.mem.bytesAsSlice(Entry, storage),
145 };
146 }
147
148 pub fn activate(self: *Table) void {
149 std.debug.assert(self.phase == .initialization);
150 std.debug.assert(self.len == 0);
151 self.phase = .steady;
152 }
153
154 /// Records the carriers of one relayed packet, following Reticulum@1.5.0
155 /// RNS/Transport.py:2012-2018. A full table gives the slot to the packet's
156 /// own entry, else to an entry past its wait, else to the oldest.
157 pub fn insert(self: *Table, value: Entry) void {
158 std.debug.assert(self.phase == .steady);
159 const target = self.reclaim(value.truncated, value.timestamp);
160 target.* = value;
161 std.debug.assert(self.len <= self.capacity.reverse_entries_max);
162 }
163
164 /// Hands back the entry for one proof destination while that entry sits
165 /// inside its age, and the store keeps it.
166 pub fn find(self: *const Table, truncated: [16]u8, now: Seconds) ?Entry {
167 std.debug.assert(self.phase == .steady);
168 const index = self.indexOf(truncated) orelse return null;
169 const entry = self.entries[index];
170 if (!live(&entry, now)) return null;
171 return entry;
172 }
173
174 /// Removes the entry for one proof, following Reticulum@1.5.0
175 /// RNS/Transport.py:2669-2671. The call reports whether an entry was there.
176 pub fn remove(self: *Table, truncated: [16]u8) bool {
177 std.debug.assert(self.phase == .steady);
178 const index = self.indexOf(truncated) orelse return false;
179 self.len -= 1;
180 self.entries[index] = self.entries[self.len];
181 return true;
182 }
183
184 pub fn count(self: *const Table) usize {
185 std.debug.assert(self.phase == .steady);
186 return self.len;
187 }
188
189 pub fn deinit(self: *Table) Storage {
190 std.debug.assert(self.phase == .steady);
191 self.phase = .teardown;
192 const storage = self.storage;
193 self.* = undefined;
194 return storage;
195 }
196
197 fn indexOf(self: *const Table, truncated: [16]u8) ?usize {
198 std.debug.assert(self.len <= self.capacity.reverse_entries_max);
199 for (self.entries[0..self.len], 0..) |*entry, index| {
200 if (std.mem.eql(u8, &entry.truncated, &truncated)) return index;
201 }
202 return null;
203 }
204
205 fn reclaim(self: *Table, truncated: [16]u8, now: Seconds) *Entry {
206 if (self.indexOf(truncated)) |index| return &self.entries[index];
207 for (self.entries[0..self.len]) |*entry| {
208 if (!live(entry, now)) return entry;
209 }
210 if (self.len < self.capacity.reverse_entries_max) {
211 self.len += 1;
212 return &self.entries[self.len - 1];
213 }
214 var oldest = &self.entries[0];
215 for (self.entries[1..self.len]) |*entry| {
216 if (entry.timestamp < oldest.timestamp) oldest = entry;
217 }
218 return oldest;
219 }
220 };
221
222 comptime {
223 alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);
224 }
225
226 fn relayed(byte: u8, timestamp: Seconds) Entry {
227 return .{
228 .truncated = @splat(byte),
229 .timestamp = timestamp,
230 .receiving = 0,
231 .outbound = 1,
232 };
233 }
234
235 test "reverse entries admit maximum and replace the oldest at maximum plus one" {
236 comptime {
237 @stardustClaim(alloc_phase.capacity.witness(
238 Table,
239 "reticulum_reverse_entries_capacity",
240 ), null, null, null, null, null, null);
241 @stardustClaim(alloc_phase.capacity.witness(
242 Table,
243 "reticulum_reverse_entries_replace",
244 ), null, null, null, null, null, null);
245 @stardustClaim(alloc_phase.capacity.witness(
246 Table,
247 "reticulum_reverse_entries_work",
248 ), null, null, null, null, null, null);
249 }
250 const limits = TableLimits{ .reverse_entries_max = 3 };
251 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
252 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
253 var table = try Table.init(&bytes, limits);
254 table.activate();
255 defer _ = table.deinit();
256 for (1..4) |value| table.insert(relayed(@intCast(value), 100 + value));
257 try std.testing.expectEqual(@as(usize, 3), table.count());
258 table.insert(relayed(4, 200));
259 try std.testing.expectEqual(@as(usize, 3), table.count());
260 try std.testing.expect(table.find(@splat(1), 200) == null);
261 for (2..5) |value| try std.testing.expect(table.find(@splat(@intCast(value)), 200) != null);
262 }
263
264 test "Reticulum@1.5.0 RNS/Transport.py:834-841 expires a reverse entry at plus 481" {
265 const limits = TableLimits{ .reverse_entries_max = 2 };
266 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
267 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
268 var table = try Table.init(&bytes, limits);
269 table.activate();
270 defer _ = table.deinit();
271 table.insert(relayed(7, 1_000));
272 try std.testing.expect(table.find(@splat(7), 1_000 + timeout) != null);
273 try std.testing.expect(table.find(@splat(7), 1_000 + timeout + 1) == null);
274 table.insert(relayed(8, 1_000 + timeout + 1));
275 try std.testing.expectEqual(@as(usize, 1), table.count());
276 try std.testing.expect(table.find(@splat(8), 1_000 + timeout + 1) != null);
277 }
278
279 test "reverse entries replace their key and remove one proof destination" {
280 const limits = TableLimits{ .reverse_entries_max = 2 };
281 const capacity = comptime TableCapacity.derive(limits) catch unreachable;
282 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
283 var table = try Table.init(&bytes, limits);
284 table.activate();
285 defer _ = table.deinit();
286 table.insert(relayed(5, 10));
287 var moved = relayed(5, 11);
288 moved.receiving = 2;
289 table.insert(moved);
290 try std.testing.expectEqual(@as(usize, 1), table.count());
291 try std.testing.expectEqual(@as(carrier.Index, 2), table.find(@splat(5), 11).?.receiving);
292 try std.testing.expect(table.remove(@splat(5)));
293 try std.testing.expect(!table.remove(@splat(5)));
294 try std.testing.expectEqual(@as(usize, 0), table.count());
295 }