tiny.reticulum.node.timer

1pub const timer = @import("timer.zig");

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const packet = @import("../packet/root.zig");45pub const Seconds = u64;67pub const TimerId = union(enum) {8    receipt: packet.Hash,9    hashlist: void,10    announces: void,11    link: [16]u8,12    link_entries: void,1314    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};3031pub const Timer = struct {32    id: TimerId,33    at: Seconds,34};3536const TableLimits = struct {37    timers_max: usize,38};3940const TableCapacity = struct {41    timers_max: usize,42    storage_bytes: usize,4344    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };4546    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};5758pub const Table = struct {59    phase: alloc_phase.capacity.Phase,60    capacity: Capacity,61    storage: Storage,62    entries: []Timer,63    len: usize = 0,6465    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    };146147    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    }157158    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    }163164    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    }175176    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    }185186    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    }193194    /// Gives the second one named timer comes due at, so a caller checks the deadline the node195    /// 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    }203204    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    }211212    pub fn due(self: *Table, now: Seconds) Due {213        std.debug.assert(self.phase == .steady);214        return .{ .table = self, .now = now };215    }216217    pub fn count(self: *const Table) usize {218        std.debug.assert(self.phase == .steady);219        return self.len;220    }221222    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    }229230    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};240241pub const Due = struct {242    table: *Table,243    now: Seconds,244245    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};263264comptime {265    alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Table);266}267268test "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}294295test "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}310311test "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}323324test "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}