tiny.reticulum.node.transport.link.entries

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const carrier = @import("../../../carrier/root.zig");45pub const Seconds = u64;67/// Nine hundred seconds, the lifetime Reticulum@1.5.0 RNS/Transport.py:1498/// gives a validated relay. The figure is the stale time of Reticulum@1.5.09/// RNS/Link.py:97-99 multiplied by 1.25, and this package computes the same10/// stale time as twice a keepalive period of at most 360 seconds.11pub const validated_timeout: Seconds = 900;1213/// One link between two other nodes whose packets this node moves. A record14/// appears at the moment the node sends an arriving link request onward. The15/// record turns validated once the node has sent the answering proof back. The16/// record leaves the store at whichever second falls first: the one its proof17/// was due by, or the one 900 seconds past its last traffic.18pub const Entry = struct {19    link_id: [16]u8,20    destination: [16]u8,21    next_hop: [16]u8,22    timestamp: Seconds,23    proof_deadline: Seconds,24    next_hop_carrier: carrier.Index,25    receiving_carrier: carrier.Index,26    remaining_hops: u8,27    taken_hops: u8,28    validated: bool,2930    /// The earliest second at which this record leaves the store. A record31    /// lives out the second its deadline names under Reticulum@1.5.032    /// RNS/Transport.py:850,855, so the answer here is the second after that33    /// one.34    pub fn dropsAt(self: *const Entry) Seconds {35        if (!self.validated) return self.proof_deadline +| 1;36        return self.timestamp +| validated_timeout +| 1;37    }38};3940const TableLimits = struct {41    link_entries_max: usize,42};4344const TableCapacity = struct {45    link_entries_max: usize,46    storage_bytes: usize,4748    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };4950    pub fn derive(limits: TableLimits) DeriveError!TableCapacity {51        if (limits.link_entries_max == 0) return error.InvalidLimit;52        const storage_bytes = alloc_phase.capacity.mul(53            usize,54            limits.link_entries_max,55            @sizeOf(Entry),56        ) catch return error.CapacityOverflow;57        return .{58            .link_entries_max = limits.link_entries_max,59            .storage_bytes = storage_bytes,60        };61    }62};6364/// The store of links this node moves packets for, holding what Reticulum@1.5.065/// RNS/Transport.py:1998-2009 keeps. Records sit in the order they were66/// written, and one link id appears at most once.67pub const Table = struct {68    phase: alloc_phase.capacity.Phase,69    capacity: Capacity,70    storage: Storage,71    entries: []Entry,72    len: usize = 0,7374    pub const storage_alignment: usize = 8;75    pub const Storage = []align(storage_alignment) u8;76    pub const Limits: type = TableLimits;77    pub const Capacity: type = TableCapacity;78    pub const Exhaustion = error{Full};79    pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};80    pub const work_limits: alloc_phase.capacity.WorkLimits = .{81        .transition_steps_max = 65_536,82        .cleanup_steps_per_call_max = 0,83        .cleanup_calls_at_capacity_max = 0,84    };85    pub const claim: alloc_phase.capacity.Declaration = .{86        .source = .{87            .id = "reticulum.link_entries",88            .kind = .phase_static,89            .limit_source = .caller,90            .storage = .{91                .covered = &.{.{92                    .id = "caller_link_entry_table",93                    .lifetime = .transferred,94                    .detail = "caller storage for relayed links and their carriers",95                }},96                .excluded = &.{"relayed link frames in effect storage"},97            },98            .capacity = .{99                .inputs = &.{alloc_phase.capacity.bindInput(100                    Limits,101                    "link_entries_max",102                    "link_entries_max",103                )},104                .type_selectors = &.{alloc_phase.capacity.bindType(Entry, "link_entry")},105                .nodes = &.{106                    .{ .input = 0 },107                    .{ .scale = .{108                        .node = 0,109                        .coefficient = .{ .size_of_concrete_type = 0 },110                    } },111                },112                .assertions = &.{.{113                    .scope = .closure_total,114                    .measure = .retained,115                    .relation = .exact,116                    .expression = 1,117                }},118            },119            .overload = .{120                .kind = .reject_before_mutation,121                .detail = "a full table drops the forwarded request and keeps every relay",122            },123            .risks = .{124                .transitive = .{125                    .status = .excluded,126                    .detail = "link entry operations call no allocating owner",127                },128                .foreign = .{129                    .status = .excluded,130                    .detail = "link entry storage crosses no foreign boundary",131                },132            },133            .work = .{ .equation = "operations scan at most link_entries_max entries" },134            .obligations = &.{135                .{ .key = "reticulum_link_entries_capacity", .role = .capacity_model },136                .{ .key = "reticulum_link_entries_overload", .role = .overload },137                .{ .key = "reticulum_link_entries_work", .role = .work_bound },138            },139        },140        .bindings = .{141            .owner = @This(),142            .seal = .{143                .family = alloc_phase.capacity.selector(@This().activate),144                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },145            },146            .teardown = .{147                .family = alloc_phase.capacity.selector(@This().deinit),148                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },149            },150        },151    };152153    pub fn init(storage: Storage, limits: Limits) InitError!Table {154        const capacity = try Capacity.derive(limits);155        if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;156        const entries = std.mem.bytesAsSlice(Entry, storage);157        std.debug.assert(entries.len == capacity.link_entries_max);158        return .{159            .phase = .initialization,160            .capacity = capacity,161            .storage = storage,162            .entries = entries,163        };164    }165166    pub fn activate(self: *Table) void {167        std.debug.assert(self.phase == .initialization);168        std.debug.assert(self.len == 0);169        self.phase = .steady;170    }171172    /// Looks one link id up among the records, answering null when the id is173    /// absent. The lookup asserts along the way that the id matched at most one174    /// record.175    pub fn find(self: *Table, link_id: [16]u8) ?*Entry {176        std.debug.assert(self.phase == .steady);177        std.debug.assert(self.len <= self.capacity.link_entries_max);178        var found: ?*Entry = null;179        for (self.entries[0..self.len]) |*entry| {180            if (!std.mem.eql(u8, &entry.link_id, &link_id)) continue;181            std.debug.assert(found == null);182            found = entry;183        }184        return found;185    }186187    /// Returns whether the table holds `link_entries_max` relays.188    pub fn full(self: *const Table) bool {189        std.debug.assert(self.phase == .steady);190        std.debug.assert(self.len <= self.capacity.link_entries_max);191        return self.len == self.capacity.link_entries_max;192    }193194    /// Writes a record at the end of the store and hands back a pointer to it.195    /// The write asserts that the link id is new to the store. A table already196    /// holding `link_entries_max` relays returns `error.Full` and leaves every197    /// relay as it was.198    pub fn insert(self: *Table, entry: Entry) Exhaustion!*Entry {199        std.debug.assert(self.phase == .steady);200        std.debug.assert(self.find(entry.link_id) == null);201        if (self.full()) return error.Full;202        self.entries[self.len] = entry;203        self.len += 1;204        return &self.entries[self.len - 1];205    }206207    /// Takes the record for one link id out and answers whether the id was208    /// present. Records written after it move down one place, so the rest stay209    /// in the order they were written. A pointer handed out earlier for that210    /// place or a later one reaches a different record afterwards, so a caller211    /// reads what it needs out of a record before it takes one out.212    pub fn remove(self: *Table, link_id: [16]u8) bool {213        std.debug.assert(self.phase == .steady);214        for (self.entries[0..self.len], 0..) |entry, index| {215            if (!std.mem.eql(u8, &entry.link_id, &link_id)) continue;216            std.mem.copyForwards(217                Entry,218                self.entries[index .. self.len - 1],219                self.entries[index + 1 .. self.len],220            );221            self.len -= 1;222            std.debug.assert(self.find(link_id) == null);223            return true;224        }225        return false;226    }227228    /// Answers with the soonest second any record in the store leaves it. An229    /// empty table gives null.230    pub fn earliest(self: *const Table) ?Seconds {231        std.debug.assert(self.phase == .steady);232        var soonest: ?Seconds = null;233        for (self.entries[0..self.len]) |*entry| {234            const at = entry.dropsAt();235            if (soonest == null or at < soonest.?) soonest = at;236        }237        return soonest;238    }239240    /// Hands back the first record whose second has arrived by `now`, and null241    /// once none has.242    pub fn expired(self: *Table, now: Seconds) ?*Entry {243        std.debug.assert(self.phase == .steady);244        for (self.entries[0..self.len]) |*entry| {245            if (now >= entry.dropsAt()) return entry;246        }247        return null;248    }249250    pub fn count(self: *const Table) usize {251        std.debug.assert(self.phase == .steady);252        std.debug.assert(self.len <= self.capacity.link_entries_max);253        return self.len;254    }255256    pub fn deinit(self: *Table) Storage {257        std.debug.assert(self.phase == .steady);258        std.debug.assert(self.len <= self.capacity.link_entries_max);259        self.phase = .teardown;260        const storage = self.storage;261        self.* = undefined;262        return storage;263    }264};265266comptime {267    alloc_phase.capacity.requireProvisionedRejectingOwnerShape(Table);268}269270fn entryFor(byte: u8) Entry {271    return .{272        .link_id = @splat(byte),273        .destination = @splat(0xd0),274        .next_hop = @splat(0xb0),275        .timestamp = 100,276        .proof_deadline = 112,277        .next_hop_carrier = 1,278        .receiving_carrier = 0,279        .remaining_hops = 1,280        .taken_hops = 1,281        .validated = false,282    };283}284285test "link entries admit maximum and reject maximum plus one" {286    comptime {287        @stardustClaim(alloc_phase.capacity.witness(288            Table,289            "reticulum_link_entries_capacity",290        ), null, null, null, null, null, null);291        @stardustClaim(alloc_phase.capacity.witness(292            Table,293            "reticulum_link_entries_overload",294        ), null, null, null, null, null, null);295        @stardustClaim(alloc_phase.capacity.witness(296            Table,297            "reticulum_link_entries_work",298        ), null, null, null, null, null, null);299    }300    const limits = TableLimits{ .link_entries_max = 3 };301    const capacity = comptime TableCapacity.derive(limits) catch unreachable;302    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;303    var table = try Table.init(&bytes, limits);304    table.activate();305    defer _ = table.deinit();306    for (1..4) |value| _ = try table.insert(entryFor(@intCast(value)));307    try std.testing.expect(table.full());308    try std.testing.expectError(error.Full, table.insert(entryFor(4)));309    try std.testing.expectEqual(@as(usize, 3), table.count());310    for (1..4) |value| try std.testing.expect(table.find(@splat(@intCast(value))) != null);311    try std.testing.expect(table.find(@splat(4)) == null);312}313314test "link entry removal keeps order and frees one slot" {315    const limits = TableLimits{ .link_entries_max = 3 };316    const capacity = comptime TableCapacity.derive(limits) catch unreachable;317    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;318    var table = try Table.init(&bytes, limits);319    table.activate();320    defer _ = table.deinit();321    for (1..4) |value| _ = try table.insert(entryFor(@intCast(value)));322    try std.testing.expect(table.remove(@splat(1)));323    try std.testing.expect(!table.remove(@splat(1)));324    try std.testing.expectEqual(@as(usize, 2), table.count());325    try std.testing.expectEqual(@as(u8, 2), table.entries[0].link_id[0]);326    try std.testing.expectEqual(@as(u8, 3), table.entries[1].link_id[0]);327    _ = try table.insert(entryFor(4));328    try std.testing.expect(table.full());329}330331test "Reticulum@1.5.0 RNS/Transport.py:849-856 drops relays one second after each deadline" {332    const limits = TableLimits{ .link_entries_max = 2 };333    const capacity = comptime TableCapacity.derive(limits) catch unreachable;334    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;335    var table = try Table.init(&bytes, limits);336    table.activate();337    defer _ = table.deinit();338    const unvalidated = try table.insert(entryFor(1));339    try std.testing.expectEqual(@as(Seconds, 113), unvalidated.dropsAt());340    try std.testing.expect(table.expired(112) == null);341    try std.testing.expect(table.expired(113) != null);342    unvalidated.validated = true;343    unvalidated.timestamp = 200;344    try std.testing.expectEqual(@as(Seconds, 201 + validated_timeout), unvalidated.dropsAt());345    var later = entryFor(2);346    later.proof_deadline = 300;347    _ = try table.insert(later);348    try std.testing.expectEqual(@as(Seconds, 301), table.earliest().?);349    try std.testing.expect(table.expired(300) == null);350    try std.testing.expect(table.expired(301) != null);351}352353test "a relay deadline at the largest instant saturates and still sweeps" {354    const limits = TableLimits{ .link_entries_max = 2 };355    const capacity = comptime TableCapacity.derive(limits) catch unreachable;356    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;357    var table = try Table.init(&bytes, limits);358    table.activate();359    defer _ = table.deinit();360    const last: Seconds = std.math.maxInt(Seconds);361    var unproved = entryFor(1);362    unproved.proof_deadline = last;363    const held = try table.insert(unproved);364    try std.testing.expectEqual(last, held.dropsAt());365    var proved = entryFor(2);366    proved.validated = true;367    proved.timestamp = last;368    const kept = try table.insert(proved);369    try std.testing.expectEqual(last, kept.dropsAt());370    try std.testing.expectEqual(last, table.earliest().?);371    try std.testing.expect(table.expired(last - 1) == null);372    try std.testing.expect(table.expired(last) != null);373}374375test "link entry capacity rejects zero and overflowing limits" {376    try std.testing.expectError(377        error.InvalidLimit,378        TableCapacity.derive(.{ .link_entries_max = 0 }),379    );380    const overflowing = std.math.maxInt(usize) / @sizeOf(Entry) + 1;381    try std.testing.expectError(382        error.CapacityOverflow,383        TableCapacity.derive(.{ .link_entries_max = overflowing }),384    );385}

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