tiny.reticulum.node.transport.inflight

1const std = @import("std");2const alloc_phase = @import("alloc_phase");34pub const Seconds = u64;56/// Forty-five seconds, after which Reticulum@1.5.0 RNS/Transport.py:132,9687/// clears a gate.8pub const timeout: Seconds = 45;910/// One destination the node has asked after and has yet to hear back on.11pub const Entry = struct {12    destination: [16]u8,13    timestamp: Seconds,14};1516/// Reports whether a gate still counts. This port keeps a gate through the17/// second it was stamped plus forty-five and clears it at plus forty-six.18fn live(entry: *const Entry, now: Seconds) bool {19    return now -| entry.timestamp <= timeout;20}2122const TableLimits = struct {23    inflight_requests_max: usize,24};2526const TableCapacity = struct {27    inflight_requests_max: usize,28    storage_bytes: usize,2930    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };3132    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};4546/// In-flight path request gates, matching Reticulum@1.5.047/// RNS/Transport.py:1770-1776.48pub const Table = struct {49    phase: alloc_phase.capacity.Phase,50    capacity: Capacity,51    storage: Storage,52    entries: []Entry,53    len: usize = 0,5455    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    };132133    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    }143144    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    }149150    /// Reports the live gate for one destination, following Reticulum@1.5.0151    /// 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    }159160    /// Opens a gate at the second of the request, following Reticulum@1.5.0161    /// RNS/Transport.py:1774-1776. A full table gives the slot to the162    /// destination's own gate, else to a gate past its wait, else to the163    /// 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    }170171    /// Closes the gate for one destination, following Reticulum@1.5.0172    /// RNS/Transport.py:2395-2397,3520-3524. The call reports whether a gate173    /// 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    }181182    pub fn count(self: *const Table) usize {183        std.debug.assert(self.phase == .steady);184        return self.len;185    }186187    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    }194195    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    }202203    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};219220comptime {221    alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);222}223224test "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}252253test "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}267268test "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}

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