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