tiny.reticulum.node.fixture

1/// The access codes for the A to B link and the B to C link.2pub const Codes = struct {3    a_b: ?node.Access = null,4    b_c: ?node.Access = null,5};

1pub const Delivery = struct {2    at: Seconds,3    link: LinkId,4    ordinal: u32,5    frame: carrier.Frame,6};

1/// One scripted failure on one directed link. Three of the four identify a frame by ordinal, the2/// number of frames that link was offered ahead of it, counted from 0, with the frames the link3/// loses counted in. Every frame a fault names is one the link has yet to be offered. Departure4/// follows the delivery second, and two frames due in one second depart by place. A frame's place5/// is its ordinal until a swap trades it.6pub const Fault = union(enum) {7    /// The link drops the frame sitting at this ordinal.8    drop: u32,9    /// The frame sitting at this ordinal departs `seconds` later than the second that offered it. A10    /// swap leaves this delivery second with its own frame.11    delay: struct { ordinal: u32, seconds: Seconds },12    /// The two frames at ordinals `first` and `second` exchange their places on the single occasion13    /// when both sit in the queue, so a frame that left or was lost first blocks the swap. A14    /// delivery second stays with its frame through the exchange, and a place moves.15    swap: struct { first: u32, second: u32 },16    /// The link drops each frame it was offered in the seconds `from` up to `until`, with both of17    /// those seconds inside the span.18    partition: struct { from: Seconds, until: Seconds },19};

1/// The effect kinds the world logs beside the carrier frames it carries.2pub const Kind = enum {3    delivery,4    announce,5    path_request,6    receipt,7    diagnostic,8    timer,9    link_requested,10    link_established,11    link_delivery,12    link_closed,13};

1/// One directed link, holding a queue of at most eight frames, the second each is due, and its2/// scripted faults. The link counts the frames it was offered and the frames it lost.3pub const Link = struct {4    queue: carrier.Memory,5    due: [frames_max]Seconds = @splat(0),6    order: [frames_max]u32 = @splat(0),7    /// Each queued frame's tie-break among the frames due in the same second. A place starts out as8    /// the frame's ordinal, a swap trades it, and it travels with the frame when the queue rotates.9    place: [frames_max]u32 = @splat(0),10    faults: [faults_max]Fault = @splat(.{ .drop = std.math.maxInt(u32) }),11    consumed: [faults_max]bool = @splat(false),12    fault_count: usize = 0,13    offered: u32 = 0,14    dropped: u32 = 0,1516    pub fn fault(self: *Link, value: Fault) void {17        std.debug.assert(self.fault_count < faults_max);18        switch (value) {19            .drop => |ordinal| std.debug.assert(ordinal >= self.offered),20            .delay => |late| std.debug.assert(late.ordinal >= self.offered),21            .swap => |pair| {22                std.debug.assert(pair.first != pair.second);23                std.debug.assert(@min(pair.first, pair.second) >= self.offered);24            },25            .partition => |window| std.debug.assert(window.from <= window.until),26        }27        self.faults[self.fault_count] = value;28        self.consumed[self.fault_count] = false;29        self.fault_count += 1;30    }31};

1/// The four one-way links between neighboring nodes. Within one second the world drains them in2/// the order they are written here.3pub const LinkId = enum(u2) { a_to_b, b_to_a, b_to_c, c_to_b };

1/// The world's three nodes, with B between A and C as the one that carries traffic for the other2/// two.3pub const NodeId = enum(u2) { a, b, c };

1pub const Options = struct {2    start: Seconds,3    transport_hash: [16]u8,4    codes: Codes = .{},5    discover_paths: ?carrier.Index = null,6    entropy: Entropy = .{},7};

1pub const Record = struct {2    at: Seconds,3    owner: NodeId,4    kind: Kind,5    interface: carrier.Index = 0,6    key: [16]u8 = @splat(0),7    hops: u8 = 0,8    tag: Tag = .receipt,9    deadline: Seconds = 0,10    path_response: bool = false,11    proof_requested: bool = false,12    code: ?node.Code = null,13    status: ?packet.receipt.Status = null,14    role: ?node.LinkRole = null,15    reason: ?node.LinkCloseReason = null,16    payload: [payload_bytes_max]u8 = @splat(0),17    payload_len: u8 = 0,1819    pub fn plaintext(self: *const Record) []const u8 {20        std.debug.assert(self.payload_len <= payload_bytes_max);21        return self.payload[0..self.payload_len];22    }23};

1/// What a timer record names.2pub const Tag = enum(u8) { receipt, hashlist, announces, link, link_entries };

1/// Three nodes joined by four one-way links, with one clock, the frame queues, the timer copies,2/// and the log. The caller initializes this value in place, because each node holds slices that3/// point into the world's storage.4pub const World = struct {5    clock: Seconds = 0,6    nodes: [node_count]node.Node = undefined,7    links: [4]Link = undefined,8    timers: [timers_max]Scheduled = undefined,9    timer_count: usize = 0,10    deliveries: [deliveries_max]Delivery = undefined,11    delivery_count: usize = 0,12    log: [records_max]Record = undefined,13    record_count: usize = 0,14    entropy_count: u64 = 0,15    entropy: Entropy = .{},16    regions: [node_count]NodeRegion = undefined,17    link_regions: [4]LinkRegion = undefined,1819    pub fn init(self: *World, options: Options) Error!void {20        self.clock = options.start;21        self.timer_count = 0;22        self.delivery_count = 0;23        self.record_count = 0;24        self.entropy_count = 0;25        self.entropy = options.entropy;26        for (&self.nodes, &self.regions) |*owner, *region| {27            owner.* = try node.Node.init(&region.bytes, limits);28            owner.activate();29        }30        for (&self.links, &self.link_regions) |*link, *region| {31            link.* = .{32                .queue = try carrier.Memory.init(&region.bytes, link_limits),33            };34            link.queue.activate();35        }36        try self.register(options);37        std.debug.assert(self.clock == options.start);38    }3940    fn register(self: *World, options: Options) Error!void {41        try self.at(.a).registerCarrier(0, true, options.codes.a_b);42        try self.at(.b).registerCarrier(0, true, options.codes.a_b);43        try self.at(.b).registerCarrier(1, true, options.codes.b_c);44        try self.at(.c).registerCarrier(0, true, options.codes.b_c);45        self.at(.b).setTransport(options.transport_hash, true);46        if (options.discover_paths) |index| try self.at(.b).setPathDiscovery(index, true);47    }4849    pub fn deinit(self: *World) void {50        for (&self.links) |*link| _ = link.queue.deinit();51        for (&self.nodes) |*owner| _ = owner.deinit();52    }5354    pub fn at(self: *World, id: NodeId) *node.Node {55        return &self.nodes[@backingInt(id)];56    }5758    pub fn linkAt(self: *World, id: LinkId) *Link {59        return &self.links[@backingInt(id)];60    }6162    /// Applies one caller event to one node at the current second and settles what follows.63    pub fn step(self: *World, id: NodeId, value: node.Event) Error!void {64        try self.apply(id, try self.at(id).step(value));65        try self.settle();66    }6768    /// Runs each second that falls due through the target second, and leaves the clock at the69    /// target. A world that has not quieted down after sixty-four rounds returns70    /// `error.WorldDidNotSettle`.71    pub fn runTo(self: *World, target: Seconds) Error!void {72        std.debug.assert(target >= self.clock);73        var steps: usize = 0;74        while (steps < settle_steps_max) : (steps += 1) {75            const due = self.nextDue() orelse break;76            if (due > target) break;77            self.clock = @max(self.clock, due);78            try self.settle();79        }80        if (steps == settle_steps_max) return error.WorldDidNotSettle;81        self.clock = target;82    }8384    pub fn frameCount(self: *const World, id: LinkId) usize {85        var count: usize = 0;86        for (self.deliveries[0..self.delivery_count]) |delivery| {87            if (delivery.link == id) count += 1;88        }89        return count;90    }9192    pub fn frameOn(self: *const World, id: LinkId, index: usize) ?*const Delivery {93        var seen: usize = 0;94        for (self.deliveries[0..self.delivery_count]) |*delivery| {95            if (delivery.link != id) continue;96            if (seen == index) return delivery;97            seen += 1;98        }99        return null;100    }101102    pub fn timerCount(self: *const World, id: NodeId) usize {103        std.debug.assert(self.timer_count <= timers_max);104        var count: usize = 0;105        for (self.timers[0..self.timer_count]) |entry| {106            if (entry.owner == id) count += 1;107        }108        return count;109    }110111    pub fn records(self: *const World) []const Record {112        std.debug.assert(self.record_count <= records_max);113        return self.log[0..self.record_count];114    }115116    pub fn recordCount(self: *const World, id: NodeId, kind: Kind) usize {117        var count: usize = 0;118        for (self.records()) |record| {119            if (record.owner == id and record.kind == kind) count += 1;120        }121        return count;122    }123124    pub fn lastRecord(self: *const World, id: NodeId, kind: Kind) ?Record {125        var found: ?Record = null;126        for (self.records()) |record| {127            if (record.owner == id and record.kind == kind) found = record;128        }129        return found;130    }131132    fn settle(self: *World) Error!void {133        var steps: usize = 0;134        while (steps < settle_steps_max) : (steps += 1) {135            const moved = try self.deliverDue();136            const fired = try self.fireDue();137            if (!moved and !fired) return;138        }139        return error.WorldDidNotSettle;140    }141142    fn nextDue(self: *const World) ?Seconds {143        var best: ?Seconds = null;144        for (&self.links) |*link| {145            var offset: usize = 0;146            while (offset < link.queue.len) : (offset += 1) {147                const slot = (link.queue.start + offset) % frames_max;148                best = if (best) |value| @min(value, link.due[slot]) else link.due[slot];149            }150        }151        for (self.timers[0..self.timer_count]) |entry| {152            best = if (best) |value| @min(value, entry.at) else entry.at;153        }154        return best;155    }156157    fn deliverDue(self: *World) Error!bool {158        var moved = false;159        for (&self.links, 0..) |*link, index| {160            var pending = frames_max;161            while (pending > 0) : (pending -= 1) {162                const offset = dueOffset(link, self.clock) orelse break;163                var spins: usize = 0;164                while (spins < offset) : (spins += 1) rotate(link);165                std.debug.assert(link.queue.len >= 1);166                std.debug.assert(link.due[link.queue.start] <= self.clock);167                const order = link.order[link.queue.start];168                const frame = link.queue.pop() orelse unreachable;169                self.keep(@fromBackingInt(@intCast(index)), order, frame);170                try self.arrive(@fromBackingInt(@intCast(index)), frame);171                moved = true;172            }173        }174        return moved;175    }176177    fn arrive(self: *World, id: LinkId, frame: carrier.Frame) Error!void {178        const target = wires[@backingInt(id)];179        const effects = try self.at(target.target).step(.{ .carrier_frame = .{180            .interface = target.target_carrier,181            .now = self.clock,182            .bytes = frame.slice(),183            .entropy = self.entropyFor(target.target),184        } });185        try self.apply(target.target, effects);186    }187188    fn fireDue(self: *World) Error!bool {189        var chosen: ?usize = null;190        for (self.timers[0..self.timer_count], 0..) |entry, index| {191            if (entry.at > self.clock) continue;192            if (chosen == null or before(entry, self.timers[chosen.?])) chosen = index;193        }194        const index = chosen orelse return false;195        const entry = self.timers[index];196        self.timer_count -= 1;197        self.timers[index] = self.timers[self.timer_count];198        const effects = try self.at(entry.owner).step(.{ .timer_expired = .{199            .id = entry.id,200            .now = self.clock,201            .entropy = self.entropyFor(entry.owner),202        } });203        try self.apply(entry.owner, effects);204        return true;205    }206207    fn entropyFor(self: *World, id: NodeId) [32]u8 {208        if (self.entropy.forNode(id)) |fixed| return fixed;209        return self.nextEntropy();210    }211212    fn nextEntropy(self: *World) [32]u8 {213        var counter: [8]u8 = undefined;214        std.mem.writeInt(u64, &counter, self.entropy_count, .little);215        self.entropy_count += 1;216        var entropy: [32]u8 = undefined;217        std.crypto.hash.sha2.Sha256.hash(&counter, &entropy, .{});218        return entropy;219    }220221    fn apply(self: *World, id: NodeId, effects: []const node.Effect) Error!void {222        self.forget(id);223        for (effects) |effect| switch (effect) {224            .carrier_send => |send| try self.offer(id, send.interface, send.frame),225            .schedule_timer => |scheduled| {226                self.schedule(id, scheduled.id, scheduled.at);227                self.note(.{228                    .at = self.clock,229                    .owner = id,230                    .kind = .timer,231                    .tag = tagOf(scheduled.id),232                    .deadline = scheduled.at,233                });234            },235            .application_delivery => |delivery| self.note(delivered(self.clock, id, delivery)),236            .announce_received => |announce| self.note(.{237                .at = self.clock,238                .owner = id,239                .kind = .announce,240                .key = announce.destination_hash,241                .hops = announce.hops,242                .path_response = announce.path_response,243            }),244            .path_request => |request| self.note(.{245                .at = self.clock,246                .owner = id,247                .kind = .path_request,248                .interface = request.interface,249                .key = request.destination,250            }),251            .receipt_update => |update| self.note(.{252                .at = self.clock,253                .owner = id,254                .kind = .receipt,255                .key = update.packet_hash[0..16].*,256                .status = update.status,257            }),258            .diagnostic => |value| self.note(.{259                .at = self.clock,260                .owner = id,261                .kind = .diagnostic,262                .code = value.code,263            }),264            .link_requested => |requested| self.note(.{265                .at = self.clock,266                .owner = id,267                .kind = .link_requested,268                .key = requested.link_id,269            }),270            .link_established => |established| self.note(.{271                .at = self.clock,272                .owner = id,273                .kind = .link_established,274                .interface = established.interface,275                .key = established.link_id,276                .role = established.role,277            }),278            .link_delivery => |delivery| self.note(linkDelivered(self.clock, id, delivery)),279            .link_closed => |closed| self.note(.{280                .at = self.clock,281                .owner = id,282                .kind = .link_closed,283                .key = closed.link_id,284                .reason = closed.reason,285            }),286            .persist => {},287        };288    }289290    fn offer(self: *World, id: NodeId, interface: carrier.Index, frame: []const u8) Error!void {291        std.debug.assert(frame.len >= 1);292        const index = wireOf(id, interface);293        const link = &self.links[index];294        const ordinal = link.offered;295        link.offered += 1;296        var due = self.clock;297        var blocked = false;298        for (link.faults[0..link.fault_count]) |value| switch (value) {299            .drop => |lost| blocked = blocked or lost == ordinal,300            .delay => |late| if (late.ordinal == ordinal) {301                due = self.clock +| late.seconds;302            },303            .partition => |window| {304                const inside = self.clock >= window.from and self.clock <= window.until;305                blocked = blocked or inside;306            },307            .swap => {},308        };309        if (blocked) {310            link.dropped += 1;311            return;312        }313        const slot = (link.queue.start + link.queue.len) % frames_max;314        try link.queue.push(try carrier.Frame.init(frame));315        link.due[slot] = due;316        link.order[slot] = ordinal;317        link.place[slot] = ordinal;318        swapQueued(link);319    }320321    fn schedule(self: *World, id: NodeId, timer_id: node.TimerId, due: Seconds) void {322        std.debug.assert(self.at(id).timers.contains(timer_id));323        for (self.timers[0..self.timer_count]) |*entry| {324            if (entry.owner != id) continue;325            if (!entry.id.eql(timer_id)) continue;326            entry.at = due;327            return;328        }329        std.debug.assert(self.timer_count < timers_max);330        self.timers[self.timer_count] = .{ .owner = id, .id = timer_id, .at = due };331        self.timer_count += 1;332        std.debug.assert(self.timerCount(id) <= limits.timers_max);333    }334335    /// Drops the world's copies of the timers that node has dropped, and keeps the rest in order.336    /// Cancelling a receipt timer produces no effect that announces it, and a node cancels one on337    /// two occasions: a proof concluding the receipt, and a newer receipt culling it. The world338    /// makes this call once a node's step returns, holding that step's effects until afterwards, so339    /// it spares a timer the step armed.340    fn forget(self: *World, id: NodeId) void {341        const owner = self.at(id);342        var index: usize = 0;343        for (0..timers_max) |_| {344            if (index == self.timer_count) break;345            const entry = self.timers[index];346            if (entry.owner == id and !owner.timers.contains(entry.id)) {347                std.mem.copyForwards(348                    Scheduled,349                    self.timers[index .. self.timer_count - 1],350                    self.timers[index + 1 .. self.timer_count],351                );352                self.timer_count -= 1;353            } else {354                index += 1;355            }356        }357        std.debug.assert(index == self.timer_count);358        std.debug.assert(self.timerCount(id) <= owner.timers.count());359    }360361    fn note(self: *World, value: Record) void {362        std.debug.assert(self.record_count < records_max);363        self.log[self.record_count] = value;364        self.record_count += 1;365    }366367    fn keep(self: *World, id: LinkId, ordinal: u32, frame: carrier.Frame) void {368        std.debug.assert(self.delivery_count < deliveries_max);369        self.deliveries[self.delivery_count] = .{370            .at = self.clock,371            .link = id,372            .ordinal = ordinal,373            .frame = frame,374        };375        self.delivery_count += 1;376    }377};

1pub const deliveries_max: usize = 48;

1pub const faults_max: usize = 4;

1pub const frames_max: usize = 8;

1/// The entry maxima each of the world's nodes runs under. Every node holds two carriers, so B sits2/// between A and C at the same time.3pub const limits = node.Limits{4    .interfaces_max = 2,5    .destinations_max = 1,6    .known_identities_max = 2,7    .known_ratchets_max = 1,8    .receipts_max = 2,9    .duplicate_hashes_max = 32,10    .timers_max = 4,11    .effects_max = 8,12    .effect_frames_max = 4,13    .paths_max = 2,14    .announces_max = 2,15    .reverse_entries_max = 2,16    .path_request_tags_max = 8,17    .inflight_requests_max = 2,18    .discoveries_max = 2,19    .links_max = 2,20    .link_entries_max = 2,21};

1pub const records_max: usize = 128;

1//! Three nodes of a mesh network are held inside one value, which runs them from a single clock and2//! can lose, delay, reorder, or cut off the traffic between them. The middle node carries traffic3//! for the two outer ones, so a packet from one end to the other crosses it in both directions.4//!5//! A test of a mesh protocol has to watch a packet cross an intermediate node and has to see the6//! answer come back the way it went. The test also has to put the protocol under loss, delay,7//! reordering, and a cut link, because the protocol exists to survive them. Every such run has to8//! give the same answer each time, so that a failure can be reproduced and the bytes can be9//! compared against a reference.10//!11//! Real interfaces and real clocks give a different interleaving on every run. Each node needs its12//! own storage before the test starts, because a node calls no allocator. A node reports what it13//! wants done and does none of it, so something has to carry its traffic, hold its deadlines, and14//! hand back each thing it asked for.15//!16//! The package follows *Reticulum 1.5.0* (the reference implementation this package ports, pinned17//! to one upstream commit), generates reference bytes and clocks from that release (a *conformance18//! corpus*), and replays those vectors in this world for a packet forwarded through the middle19//! node.20//!21//! That value (the *world*) owns the three nodes' storage and runs from one clock that drives22//! everything: it advances to the next packet or deadline that falls due and parks at the second23//! the caller asked for. Each of the four one-way paths between neighboring nodes (a *directed24//! link*) holds a queue of at most eight frames with the second each is due, so a test scripts its25//! loss, delay, and reordering in advance. The 32 bytes each input carries, drawn fresh for each26//! carrier frame and each timer event (the *step entropy*), come from a counter hashed with27//! SHA-256, so two runs of the same script derive the same keys. A transition expands those bytes28//! with HKDF-SHA256 whenever it needs a key or an initialization vector. Every request a node29//! returns, such as a frame to send on a carrier or a deadline to arm (an *effect*), stands in for30//! input or output the node does not do itself. The world writes each effect to its log as one31//! line, which the test reads back by node and kind. The test runs the world until no frame is due32//! and no deadline falls due (it *settles*). A run still busy after sixty-four rounds fails with33//! `error.WorldDidNotSettle`.34//!35//! - *node*: the state machine that holds one Reticulum node's tables, one packet of scratch space,36//!   and its effect list.37//! - *transport node*: a node that carries traffic on behalf of other nodes, as well as sending and38//!   receiving its own.39//! - *timer*: a deadline the node holds, naming what comes due and the whole second it comes due40//!   at.41//! - *record*: one line of the world's log, holding the second, the node, the effect kind, and the42//!   fields that kind carries.43//! - *relay*: forwarding a packet that names this node as its next hop toward the destination its44//!   path gives, rewriting only the header.4546const world = @import("world.zig");4748pub const World = world.World;49pub const Link = world.Link;50pub const NodeId = world.NodeId;51pub const LinkId = world.LinkId;52pub const Fault = world.Fault;53pub const Options = world.Options;54pub const Codes = world.Codes;55pub const Record = world.Record;56pub const Kind = world.Kind;57pub const Tag = world.Tag;58pub const Delivery = world.Delivery;59pub const Seconds = world.Seconds;60pub const limits = world.limits;61pub const records_max = world.records_max;62pub const deliveries_max = world.deliveries_max;63pub const frames_max = world.frames_max;64pub const faults_max = world.faults_max;

1pub const fixture = @import("fixture/root.zig");