lib/reticulum/src/node/timer.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_phase = @import("alloc_phase");
3 const packet = @import("../packet/root.zig");
4
5 pub const Seconds = u64;
6
7 pub const TimerId = union(enum) {
8 receipt: packet.Hash,
9 hashlist: void,
10 announces: void,
11 link: [16]u8,
12 link_entries: void,
13
14 pub fn eql(left: TimerId, right: TimerId) bool {
15 return switch (left) {
16 .receipt => |left_hash| switch (right) {
17 .receipt => |right_hash| std.mem.eql(u8, &left_hash, &right_hash),
18 .hashlist, .announces, .link, .link_entries => false,
19 },
20 .hashlist => right == .hashlist,
21 .announces => right == .announces,
22 .link_entries => right == .link_entries,
23 .link => |left_id| switch (right) {
24 .link => |right_id| std.mem.eql(u8, &left_id, &right_id),
25 .receipt, .hashlist, .announces, .link_entries => false,
26 },
27 };
28 }
29 };
30
31 pub const Timer = struct {
32 id: TimerId,
33 at: Seconds,
34 };
35
36 const TableLimits = struct {
37 timers_max: usize,
38 };
39
40 const TableCapacity = struct {
41 timers_max: usize,
42 storage_bytes: usize,
43
44 pub const DeriveError = error{ InvalidLimit, CapacityOverflow };
45
46 pub fn derive(limits: TableLimits) DeriveError!TableCapacity {
47 if (limits.timers_max == 0) return error.InvalidLimit;
48 const timers_max = limits.timers_max;
49 const storage_bytes = alloc_phase.capacity.mul(
50 usize,
51 timers_max,
52 @sizeOf(Timer),
53 ) catch return error.CapacityOverflow;
54 return .{ .timers_max = timers_max, .storage_bytes = storage_bytes };
55 }
56 };
57
58 pub const Table = struct {
59 phase: alloc_phase.capacity.Phase,
60 capacity: Capacity,
61 storage: Storage,
62 entries: []Timer,
63 len: usize = 0,
64
65 pub const storage_alignment: usize = 8;
66 pub const Storage = []align(storage_alignment) u8;
67 pub const Limits: type = TableLimits;
68 pub const Capacity: type = TableCapacity;
69 pub const Exhaustion = error{Full};
70 pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};
71 pub const work_limits: alloc_phase.capacity.WorkLimits = .{
72 .transition_steps_max = 131_072,
73 .cleanup_steps_per_call_max = 65_536,
74 .cleanup_calls_at_capacity_max = 1,
75 };
76 pub const claim: alloc_phase.capacity.Declaration = .{
77 .source = .{
78 .id = "reticulum.timers",
79 .kind = .phase_static,
80 .limit_source = .caller,
81 .storage = .{
82 .covered = &.{.{
83 .id = "caller_timer_table",
84 .lifetime = .transferred,
85 .detail = "caller storage for bounded node timers",
86 }},
87 .excluded = &.{
88 "event timestamps",
89 "operating-system clocks and scheduler state",
90 },
91 },
92 .capacity = .{
93 .inputs = &.{alloc_phase.capacity.bindInput(
94 TableLimits,
95 "timers_max",
96 "timers_max",
97 )},
98 .type_selectors = &.{alloc_phase.capacity.bindType(Timer, "timer")},
99 .nodes = &.{
100 .{ .input = 0 },
101 .{ .scale = .{
102 .node = 0,
103 .coefficient = .{ .size_of_concrete_type = 0 },
104 } },
105 },
106 .assertions = &.{.{
107 .scope = .closure_total,
108 .measure = .retained,
109 .relation = .exact,
110 .expression = 1,
111 }},
112 },
113 .overload = .{
114 .kind = .reject_before_mutation,
115 .detail = "full timer admission preserves scheduled timers",
116 },
117 .risks = .{
118 .transitive = .{
119 .status = .excluded,
120 .detail = "timer operations call no allocating owner",
121 },
122 .foreign = .{
123 .status = .excluded,
124 .detail = "the timer table reads no external clock",
125 },
126 },
127 .work = .{ .equation = "timer operations scan at most timers_max entries" },
128 .obligations = &.{
129 .{ .key = "reticulum_timers_capacity", .role = .capacity_model },
130 .{ .key = "reticulum_timers_overload", .role = .overload },
131 .{ .key = "reticulum_timers_work", .role = .work_bound },
132 },
133 },
134 .bindings = .{
135 .owner = @This(),
136 .seal = .{
137 .family = alloc_phase.capacity.selector(@This().activate),
138 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
139 },
140 .teardown = .{
141 .family = alloc_phase.capacity.selector(@This().deinit),
142 .premise = .{ .class = .checked_semantic_fact, .authority = .checker },
143 },
144 },
145 };
146
147 pub fn init(storage: Storage, limits: Limits) InitError!Table {
148 const capacity = try Capacity.derive(limits);
149 if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;
150 return .{
151 .phase = .initialization,
152 .capacity = capacity,
153 .storage = storage,
154 .entries = std.mem.bytesAsSlice(Timer, storage),
155 };
156 }
157
158 pub fn activate(self: *Table) void {
159 std.debug.assert(self.phase == .initialization);
160 std.debug.assert(self.len == 0);
161 self.phase = .steady;
162 }
163
164 pub fn schedule(self: *Table, id: TimerId, at: Seconds) Exhaustion!void {
165 std.debug.assert(self.phase == .steady);
166 for (self.entries[0..self.len]) |*entry| {
167 if (!entry.id.eql(id)) continue;
168 entry.at = at;
169 return;
170 }
171 if (self.len == self.capacity.timers_max) return error.Full;
172 self.entries[self.len] = .{ .id = id, .at = at };
173 self.len += 1;
174 }
175
176 pub fn cancel(self: *Table, id: TimerId) bool {
177 std.debug.assert(self.phase == .steady);
178 for (self.entries[0..self.len], 0..) |entry, index| {
179 if (!entry.id.eql(id)) continue;
180 self.removeAt(index);
181 return true;
182 }
183 return false;
184 }
185
186 pub fn contains(self: *const Table, id: TimerId) bool {
187 std.debug.assert(self.phase == .steady);
188 for (self.entries[0..self.len]) |entry| {
189 if (entry.id.eql(id)) return true;
190 }
191 return false;
192 }
193
194 /// Gives the second one named timer comes due at, so a caller checks the deadline the node
195 /// armed for one timer. A name the table holds no timer for gives null.
196 pub fn scheduledAt(self: *const Table, id: TimerId) ?Seconds {
197 std.debug.assert(self.phase == .steady);
198 for (self.entries[0..self.len]) |entry| {
199 if (entry.id.eql(id)) return entry.at;
200 }
201 return null;
202 }
203
204 pub fn canScheduleAfterCancel(self: *const Table, id: TimerId, cancelled_id: ?TimerId) bool {
205 std.debug.assert(self.phase == .steady);
206 if (self.contains(id)) return true;
207 if (self.len < self.capacity.timers_max) return true;
208 const cancelled = cancelled_id orelse return false;
209 return self.contains(cancelled);
210 }
211
212 pub fn due(self: *Table, now: Seconds) Due {
213 std.debug.assert(self.phase == .steady);
214 return .{ .table = self, .now = now };
215 }
216
217 pub fn count(self: *const Table) usize {
218 std.debug.assert(self.phase == .steady);
219 return self.len;
220 }
221
222 pub fn deinit(self: *Table) Storage {
223 std.debug.assert(self.phase == .steady);
224 self.phase = .teardown;
225 const storage = self.storage;
226 self.* = undefined;
227 return storage;
228 }
229
230 fn removeAt(self: *Table, index: usize) void {
231 std.debug.assert(index < self.len);
232 std.mem.copyForwards(
233 Timer,
234 self.entries[index .. self.len - 1],
235 self.entries[index + 1 .. self.len],
236 );
237 self.len -= 1;
238 }
239 };
240
241 pub const Due = struct {
242 table: *Table,
243 now: Seconds,
244
245 pub fn next(self: *Due) ?Timer {
246 std.debug.assert(self.table.phase == .steady);
247 var earliest: ?usize = null;
248 for (0..self.table.capacity.timers_max) |index| {
249 if (index == self.table.len) break;
250 const candidate = self.table.entries[index];
251 if (candidate.at > self.now) continue;
252 if (earliest) |selected| {
253 if (candidate.at >= self.table.entries[selected].at) continue;
254 }
255 earliest = index;
256 }
257 const index = earliest orelse return null;
258 const value = self.table.entries[index];
259 self.table.removeAt(index);
260 return value;
261 }
262 };
263
264 comptime {
265 alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Table);
266 }
267
268 test "timers admit maximum and reject maximum plus one" {
269 comptime {
270 @stardustClaim(alloc_phase.capacity.witness(
271 Table,
272 "reticulum_timers_capacity",
273 ), null, null, null, null, null, null);
274 @stardustClaim(alloc_phase.capacity.witness(
275 Table,
276 "reticulum_timers_overload",
277 ), null, null, null, null, null, null);
278 @stardustClaim(alloc_phase.capacity.witness(
279 Table,
280 "reticulum_timers_work",
281 ), null, null, null, null, null, null);
282 }
283 const capacity = comptime TableCapacity.derive(.{ .timers_max = 3 }) catch unreachable;
284 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
285 var table = try Table.init(&bytes, .{ .timers_max = 3 });
286 table.activate();
287 defer _ = table.deinit();
288 try table.schedule(.{ .receipt = @splat(1) }, 30);
289 try table.schedule(.{ .receipt = @splat(2) }, 10);
290 try table.schedule(.{ .receipt = @splat(3) }, 20);
291 try std.testing.expectError(error.Full, table.schedule(.hashlist, 40));
292 try std.testing.expectEqual(@as(usize, 3), table.count());
293 }
294
295 test "timers iterate due entries in deadline order" {
296 const capacity = comptime TableCapacity.derive(.{ .timers_max = 3 }) catch unreachable;
297 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
298 var table = try Table.init(&bytes, .{ .timers_max = 3 });
299 table.activate();
300 defer _ = table.deinit();
301 try table.schedule(.{ .receipt = @splat(1) }, 30);
302 try table.schedule(.{ .receipt = @splat(2) }, 10);
303 try table.schedule(.{ .receipt = @splat(3) }, 20);
304 var due = table.due(20);
305 try std.testing.expect(due.next().?.id.eql(.{ .receipt = @splat(2) }));
306 try std.testing.expect(due.next().?.id.eql(.{ .receipt = @splat(3) }));
307 try std.testing.expect(due.next() == null);
308 try std.testing.expect(table.cancel(.{ .receipt = @splat(1) }));
309 }
310
311 test "timer admission accounts for one cancelled receipt timer" {
312 const capacity = comptime TableCapacity.derive(.{ .timers_max = 1 }) catch unreachable;
313 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
314 var table = try Table.init(&bytes, .{ .timers_max = 1 });
315 table.activate();
316 defer _ = table.deinit();
317 const old = TimerId{ .receipt = @splat(1) };
318 const new = TimerId{ .receipt = @splat(2) };
319 try table.schedule(old, 10);
320 try std.testing.expect(table.canScheduleAfterCancel(new, old));
321 try std.testing.expect(!table.canScheduleAfterCancel(new, null));
322 }
323
324 test "timers keep one deadline per link id" {
325 const capacity = comptime TableCapacity.derive(.{ .timers_max = 2 }) catch unreachable;
326 var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;
327 var table = try Table.init(&bytes, .{ .timers_max = 2 });
328 table.activate();
329 defer _ = table.deinit();
330 const first = TimerId{ .link = @splat(1) };
331 const second = TimerId{ .link = @splat(2) };
332 try table.schedule(first, 10);
333 try table.schedule(second, 20);
334 try table.schedule(first, 30);
335 try std.testing.expectEqual(@as(usize, 2), table.count());
336 try std.testing.expectEqual(@as(?Seconds, 30), table.scheduledAt(first));
337 try std.testing.expect(!table.contains(.{ .receipt = @splat(1) }));
338 try std.testing.expect(table.cancel(second));
339 try std.testing.expect(!table.contains(second));
340 }