tiny.reticulum.node.transport.reverse

1const std = @import("std");2const alloc_phase = @import("alloc_phase");3const carrier = @import("../../carrier/root.zig");45pub const Seconds = u64;67/// Four hundred and eighty seconds, the lifetime Reticulum@1.5.08/// RNS/Transport.py:151 gives a reverse entry.9pub const timeout: Seconds = 480;1011/// One packet this node moved onward, held until its proof comes back.12pub const Entry = struct {13    truncated: [16]u8,14    timestamp: Seconds,15    receiving: carrier.Index,16    outbound: carrier.Index,17};1819/// Reports whether an entry still counts. An entry stops counting 480 seconds20/// past the second it was written, the age Reticulum@1.5.021/// RNS/Transport.py:834-841 sets.22fn live(entry: *const Entry, now: Seconds) bool {23    return now -| entry.timestamp <= timeout;24}2526const TableLimits = struct {27    reverse_entries_max: usize,28};2930const TableCapacity = struct {31    reverse_entries_max: usize,32    storage_bytes: usize,3334    pub const DeriveError = error{ InvalidLimit, CapacityOverflow };3536    pub fn derive(limits: TableLimits) DeriveError!TableCapacity {37        if (limits.reverse_entries_max == 0) return error.InvalidLimit;38        const storage_bytes = alloc_phase.capacity.mul(39            usize,40            limits.reverse_entries_max,41            @sizeOf(Entry),42        ) catch return error.CapacityOverflow;43        return .{44            .reverse_entries_max = limits.reverse_entries_max,45            .storage_bytes = storage_bytes,46        };47    }48};4950/// Relayed packet carriers, matching Reticulum@1.5.051/// RNS/Transport.py:2012-2018.52pub const Table = struct {53    phase: alloc_phase.capacity.Phase,54    capacity: Capacity,55    storage: Storage,56    entries: []Entry,57    len: usize = 0,5859    pub const storage_alignment: usize = 8;60    pub const Storage = []align(storage_alignment) u8;61    pub const Limits: type = TableLimits;62    pub const Capacity: type = TableCapacity;63    pub const InitError = Capacity.DeriveError || error{StorageLengthMismatch};64    pub const work_limits: alloc_phase.capacity.WorkLimits = .{65        .transition_steps_max = 65_536,66        .cleanup_steps_per_call_max = 0,67        .cleanup_calls_at_capacity_max = 0,68    };69    pub const claim: alloc_phase.capacity.Declaration = .{70        .source = .{71            .id = "reticulum.reverse_entries",72            .kind = .phase_static,73            .limit_source = .caller,74            .storage = .{75                .covered = &.{.{76                    .id = "caller_reverse_table",77                    .lifetime = .transferred,78                    .detail = "caller storage for relayed packet hashes and carriers",79                }},80                .excluded = &.{"relayed frames in effect storage"},81            },82            .capacity = .{83                .inputs = &.{alloc_phase.capacity.bindInput(84                    Limits,85                    "reverse_entries_max",86                    "reverse_entries_max",87                )},88                .type_selectors = &.{alloc_phase.capacity.bindType(Entry, "reverse_entry")},89                .nodes = &.{90                    .{ .input = 0 },91                    .{ .scale = .{92                        .node = 0,93                        .coefficient = .{ .size_of_concrete_type = 0 },94                    } },95                },96                .assertions = &.{.{97                    .scope = .closure_total,98                    .measure = .retained,99                    .relation = .exact,100                    .expression = 1,101                }},102            },103            .overload = .{104                .kind = .not_applicable,105                .detail = "a new entry replaces its key, an expired entry, else the oldest",106            },107            .risks = .{108                .transitive = .{109                    .status = .excluded,110                    .detail = "reverse operations call no allocating owner",111                },112                .foreign = .{113                    .status = .excluded,114                    .detail = "reverse storage crosses no foreign boundary",115                },116            },117            .work = .{ .equation = "operations scan at most reverse_entries_max entries" },118            .obligations = &.{119                .{ .key = "reticulum_reverse_entries_capacity", .role = .capacity_model },120                .{ .key = "reticulum_reverse_entries_replace", .role = .overload },121                .{ .key = "reticulum_reverse_entries_work", .role = .work_bound },122            },123        },124        .bindings = .{125            .owner = @This(),126            .seal = .{127                .family = alloc_phase.capacity.selector(@This().activate),128                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },129            },130            .teardown = .{131                .family = alloc_phase.capacity.selector(@This().deinit),132                .premise = .{ .class = .checked_semantic_fact, .authority = .checker },133            },134        },135    };136137    pub fn init(storage: Storage, limits: Limits) InitError!Table {138        const capacity = try Capacity.derive(limits);139        if (storage.len != capacity.storage_bytes) return error.StorageLengthMismatch;140        return .{141            .phase = .initialization,142            .capacity = capacity,143            .storage = storage,144            .entries = std.mem.bytesAsSlice(Entry, storage),145        };146    }147148    pub fn activate(self: *Table) void {149        std.debug.assert(self.phase == .initialization);150        std.debug.assert(self.len == 0);151        self.phase = .steady;152    }153154    /// Records the carriers of one relayed packet, following Reticulum@1.5.0155    /// RNS/Transport.py:2012-2018. A full table gives the slot to the packet's156    /// own entry, else to an entry past its wait, else to the oldest.157    pub fn insert(self: *Table, value: Entry) void {158        std.debug.assert(self.phase == .steady);159        const target = self.reclaim(value.truncated, value.timestamp);160        target.* = value;161        std.debug.assert(self.len <= self.capacity.reverse_entries_max);162    }163164    /// Hands back the entry for one proof destination while that entry sits165    /// inside its age, and the store keeps it.166    pub fn find(self: *const Table, truncated: [16]u8, now: Seconds) ?Entry {167        std.debug.assert(self.phase == .steady);168        const index = self.indexOf(truncated) orelse return null;169        const entry = self.entries[index];170        if (!live(&entry, now)) return null;171        return entry;172    }173174    /// Removes the entry for one proof, following Reticulum@1.5.0175    /// RNS/Transport.py:2669-2671. The call reports whether an entry was there.176    pub fn remove(self: *Table, truncated: [16]u8) bool {177        std.debug.assert(self.phase == .steady);178        const index = self.indexOf(truncated) orelse return false;179        self.len -= 1;180        self.entries[index] = self.entries[self.len];181        return true;182    }183184    pub fn count(self: *const Table) usize {185        std.debug.assert(self.phase == .steady);186        return self.len;187    }188189    pub fn deinit(self: *Table) Storage {190        std.debug.assert(self.phase == .steady);191        self.phase = .teardown;192        const storage = self.storage;193        self.* = undefined;194        return storage;195    }196197    fn indexOf(self: *const Table, truncated: [16]u8) ?usize {198        std.debug.assert(self.len <= self.capacity.reverse_entries_max);199        for (self.entries[0..self.len], 0..) |*entry, index| {200            if (std.mem.eql(u8, &entry.truncated, &truncated)) return index;201        }202        return null;203    }204205    fn reclaim(self: *Table, truncated: [16]u8, now: Seconds) *Entry {206        if (self.indexOf(truncated)) |index| return &self.entries[index];207        for (self.entries[0..self.len]) |*entry| {208            if (!live(entry, now)) return entry;209        }210        if (self.len < self.capacity.reverse_entries_max) {211            self.len += 1;212            return &self.entries[self.len - 1];213        }214        var oldest = &self.entries[0];215        for (self.entries[1..self.len]) |*entry| {216            if (entry.timestamp < oldest.timestamp) oldest = entry;217        }218        return oldest;219    }220};221222comptime {223    alloc_phase.capacity.requireProvisionedExactOwnerShape(Table);224}225226fn relayed(byte: u8, timestamp: Seconds) Entry {227    return .{228        .truncated = @splat(byte),229        .timestamp = timestamp,230        .receiving = 0,231        .outbound = 1,232    };233}234235test "reverse entries admit maximum and replace the oldest at maximum plus one" {236    comptime {237        @stardustClaim(alloc_phase.capacity.witness(238            Table,239            "reticulum_reverse_entries_capacity",240        ), null, null, null, null, null, null);241        @stardustClaim(alloc_phase.capacity.witness(242            Table,243            "reticulum_reverse_entries_replace",244        ), null, null, null, null, null, null);245        @stardustClaim(alloc_phase.capacity.witness(246            Table,247            "reticulum_reverse_entries_work",248        ), null, null, null, null, null, null);249    }250    const limits = TableLimits{ .reverse_entries_max = 3 };251    const capacity = comptime TableCapacity.derive(limits) catch unreachable;252    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;253    var table = try Table.init(&bytes, limits);254    table.activate();255    defer _ = table.deinit();256    for (1..4) |value| table.insert(relayed(@intCast(value), 100 + value));257    try std.testing.expectEqual(@as(usize, 3), table.count());258    table.insert(relayed(4, 200));259    try std.testing.expectEqual(@as(usize, 3), table.count());260    try std.testing.expect(table.find(@splat(1), 200) == null);261    for (2..5) |value| try std.testing.expect(table.find(@splat(@intCast(value)), 200) != null);262}263264test "Reticulum@1.5.0 RNS/Transport.py:834-841 expires a reverse entry at plus 481" {265    const limits = TableLimits{ .reverse_entries_max = 2 };266    const capacity = comptime TableCapacity.derive(limits) catch unreachable;267    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;268    var table = try Table.init(&bytes, limits);269    table.activate();270    defer _ = table.deinit();271    table.insert(relayed(7, 1_000));272    try std.testing.expect(table.find(@splat(7), 1_000 + timeout) != null);273    try std.testing.expect(table.find(@splat(7), 1_000 + timeout + 1) == null);274    table.insert(relayed(8, 1_000 + timeout + 1));275    try std.testing.expectEqual(@as(usize, 1), table.count());276    try std.testing.expect(table.find(@splat(8), 1_000 + timeout + 1) != null);277}278279test "reverse entries replace their key and remove one proof destination" {280    const limits = TableLimits{ .reverse_entries_max = 2 };281    const capacity = comptime TableCapacity.derive(limits) catch unreachable;282    var bytes: [capacity.storage_bytes]u8 align(Table.storage_alignment) = undefined;283    var table = try Table.init(&bytes, limits);284    table.activate();285    defer _ = table.deinit();286    table.insert(relayed(5, 10));287    var moved = relayed(5, 11);288    moved.receiving = 2;289    table.insert(moved);290    try std.testing.expectEqual(@as(usize, 1), table.count());291    try std.testing.expectEqual(@as(carrier.Index, 2), table.find(@splat(5), 11).?.receiving);292    try std.testing.expect(table.remove(@splat(5)));293    try std.testing.expect(!table.remove(@splat(5)));294    try std.testing.expectEqual(@as(usize, 0), table.count());295}

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