tiny.quic.connection.recovery

1/// Marks off the stretch of a stream that a loss has put back in the queue. The sending half of2/// stream 0 and each space's CRYPTO stream hold one, and the send path reads it to empty that3/// stretch before it takes anything new. Holding a single stretch keeps the bookkeeping to two4/// numbers whatever the pattern of loss. Two losses with a settled stretch between them therefore5/// widen into one, and the bytes in the middle travel a second time.6pub const LostRange = struct {7    start: u62 = 0,8    end: u62 = 0,910    /// Says whether anything is waiting to travel a second time, so the send path chooses between11    /// resending and reaching for new bytes.12    pub fn isEmpty(self: LostRange) bool {13        std.debug.assert(self.start <= self.end);14        return self.start == self.end;15    }1617    /// Counts the bytes waiting to travel a second time, so the send path sizes a resent frame18    /// against it.19    pub fn length(self: LostRange) u62 {20        std.debug.assert(self.start <= self.end);21        return self.end - self.start;22    }2324    /// Widens the stretch until it reaches over `count` bytes from `offset`. The loss path calls it25    /// with the stretch each lost frame covered. A call carrying no bytes leaves the stretch as it26    /// was.27    pub fn add(self: *LostRange, offset: u62, count: u62) void {28        std.debug.assert(count <= std.math.maxInt(u62) - offset);29        if (count == 0) return;30        const end = offset + count;31        if (self.isEmpty()) {32            self.* = .{ .start = offset, .end = end };33        } else {34            self.start = @min(self.start, offset);35            self.end = @max(self.end, end);36        }37        std.debug.assert(self.start <= offset);38        std.debug.assert(end <= self.end);39    }4041    /// Pulls in whichever end of the stretch the settled bytes reach, so an acknowledgment arriving42    /// after the loss keeps those bytes from traveling a third time. Bytes settled in the middle43    /// change nothing, because a single stretch has no way to hold a hole. A stretch pulled in from44    /// both ends until it is bare returns to empty.45    pub fn acknowledge(self: *LostRange, offset: u62, count: u62) void {46        std.debug.assert(count <= std.math.maxInt(u62) - offset);47        if (self.isEmpty()) return;48        const waiting = self.length();49        const end = offset + count;50        if (offset <= self.start and self.start < end) self.start = @min(end, self.end);51        if (offset < self.end and self.end <= end) self.end = @max(offset, self.start);52        if (self.start == self.end) self.* = .{};53        std.debug.assert(self.start <= self.end);54        std.debug.assert(self.length() <= waiting);55    }5657    /// Drops `count` bytes off the front. The send path calls it once a packet carries the resent58    /// bytes. The count stays within what was waiting.59    pub fn advance(self: *LostRange, count: u62) void {60        std.debug.assert(count <= self.length());61        self.start += count;62        if (self.start == self.end) self.* = .{};63        std.debug.assert(self.start <= self.end);64    }65};

1/// Holds what one connection has learned about how long the path takes, so the loss and probe rules2/// can read its fields once `Connection.roundTrip` hands one back. The struct keeps the most recent3/// measurement, the smallest seen, a smoothed value, a measure of spread, and whether anything has4/// been measured yet.5pub const Estimator = struct {6    latest_ns: u64 = 0,7    minimum_ns: u64 = 0,8    smoothed_ns: u64 = initial_ns,9    variation_ns: u64 = initial_ns / 2,10    sampled: bool = false,1112    /// Folds one fresh measurement into what the connection already knows for each ACK that settles13    /// a packet the peer owed an answer to. The very first measurement seeds the smallest and the14    /// smoothed value with itself, and the spread with half of itself. Each later measurement moves15    /// the smoothed value by an eighth and the spread by a quarter, so a single odd measurement16    /// cannot swing either far. The caller settles the peer's delay before it calls, so the figure17    /// arriving here has already met the cap and been reduced to zero when the space demands it.18    /// That delay comes off the measurement only while the answer stays at or above the smallest19    /// seen. Each product and sum holds at the maximum once it reaches it.20    pub fn update(self: *Estimator, latest_ns: u64, delay_ns: u64) void {21        std.debug.assert(latest_ns != 0);22        self.latest_ns = latest_ns;23        if (!self.sampled) {24            self.sampled = true;25            self.minimum_ns = latest_ns;26            self.smoothed_ns = latest_ns;27            self.variation_ns = latest_ns / 2;28            return;29        }30        self.minimum_ns = @min(self.minimum_ns, latest_ns);31        const adjusted_ns = adjusted(latest_ns, self.minimum_ns, delay_ns);32        const deviation_ns = difference(self.smoothed_ns, adjusted_ns);33        self.variation_ns = (self.variation_ns *| 3 +| deviation_ns) / 4;34        self.smoothed_ns = (self.smoothed_ns *| 7 +| adjusted_ns) / 8;35    }36};

1/// Works out the moment at which elapsed time will condemn a packet that went out at `sent_ns`, so2/// the space keeps the answer as the deadline `nextTimeout` offers. The calculation adds the delay3/// to the send time. A sum that runs over stops at the largest u64 value.4pub fn deadlineNs(sent_ns: u64, delay_ns: u64) u64 {5    return std.math.add(u64, sent_ns, delay_ns) catch std.math.maxInt(u64);6}

1/// Works out how long a packet is given before elapsed time condemns it, so the connection hands2/// one delay to every space's detection pass. The calculation takes whichever of the two estimates3/// is larger and stretches it by nine eighths. The answer stays at or above the one millisecond4/// floor under the timing rules, the timer granularity. An estimate large enough to run the product5/// over stops at the largest u64 value.6pub fn delayNs(latest_ns: u64, smoothed_ns: u64) u64 {7    const base = @max(latest_ns, smoothed_ns);8    const scaled = @as(u128, base) * time_threshold_numerator / time_threshold_denominator;9    const bounded = std.math.cast(u64, scaled) orelse std.math.maxInt(u64);10    return @max(bounded, rtt.granularity_ns);11}

1/// Says whether elapsed time has already condemned a packet that went out at `sent_ns`, so the2/// caller settles the time question outright and avoids comparing deadlines itself. The answer3/// turns at the deadline itself, so a packet stands condemned from that moment on.4pub fn expired(sent_ns: u64, now_ns: u64, delay_ns: u64) bool {5    return now_ns >= deadlineNs(sent_ns, delay_ns);6}

1/// Three is how far under the largest acknowledged number a packet has to sit before reordering2/// alone condemns it, so the constant fixes how many later packets have to be acknowledged before3/// an earlier one is given up on. `reordered` measures that distance against it.4pub const packet_threshold: u62 = 3;

1/// Says whether enough later packets have been acknowledged to condemn this one, so the detection2/// pass runs this reordering test over each held packet. Three is enough to give up on a packet3/// sitting that far under the largest acknowledged number. A number above the largest acknowledged4/// one is safe.5pub fn reordered(packet_number: u62, largest_acknowledged: u62) bool {6    if (largest_acknowledged < packet_number) return false;7    return largest_acknowledged - packet_number >= packet_threshold;8}

1pub const time_threshold_denominator: u64 = 8;

1/// Nine eighths of a round trip is held as a numerator beside a denominator of eight, so the2/// constant fixes how much of a round trip a packet is given before elapsed time alone condemns it.3/// `delayNs` scales the larger of the two estimates by that fraction.4pub const time_threshold_numerator: u64 = 9;

1/// The wait may double sixteen times as probes go unanswered, and past that count the wait holds2/// steady. Holding the wait there keeps the shift under the 64 bits the period is held in, which a3/// compile-time check enforces.4pub const backoff_max: u32 = 16;

1/// Adds the wait to the instant it is measured from so the connection keeps the answer as the probe2/// deadline `nextTimeout` offers. A sum that runs over stops at the largest u64 value. The instant3/// measured from is when the space last sent a packet the peer owes an answer to, or, with nothing4/// outstanding, the anchor the anti-deadlock probe holds.5pub fn deadlineNs(sent_ns: u64, period_ns: u64) u64 {6    const deadline_ns = std.math.add(u64, sent_ns, period_ns) catch std.math.maxInt(u64);7    std.debug.assert(deadline_ns >= sent_ns);8    return deadline_ns;9}

1/// Works out how long to wait for an answer for one space, then doubles that wait once per2/// unanswered probe up to the ceiling. The connection works out one wait per space and arms the3/// soonest deadline they produce. The wait itself is the smoothed estimate, plus four times the4/// variation, plus whatever delay the peer has told this endpoint to expect. The variation term is5/// held at or above the one millisecond floor under the timing rules, the timer granularity. Only6/// the application space passes a nonzero delay, and only after the handshake is confirmed, so7/// every other caller passes zero. Each sum and each shift holds at the maximum once it reaches it.8pub fn periodNs(smoothed_ns: u64, variation_ns: u64, max_ack_delay_ns: u64, count: u32) u64 {9    const variance_ns = @max(variation_ns *| 4, rtt.granularity_ns);10    const base_ns = smoothed_ns +| variance_ns +| max_ack_delay_ns;11    std.debug.assert(base_ns >= rtt.granularity_ns);12    const shift: u6 = @intCast(@min(count, backoff_max));13    const period_ns = base_ns <<| shift;14    std.debug.assert(period_ns >= base_ns);15    return period_ns;16}

1/// Two packets, each one the peer owes an answer to, fix what the connection owes the peer when a2/// probe deadline passes with packets still outstanding. With nothing outstanding the connection3/// owes one.4pub const probe_packets: u8 = 2;

1/// Turns one ACK frame's delay field into nanoseconds, because an ACK frame carries its delay2/// scaled by the sender's own exponent. The field counts microseconds shifted left by the peer's3/// exponent. A figure too large for 64 bits stops at the largest u64 value.4pub fn delayNs(encoded: u62, exponent: u5) u64 {5    const microseconds = @as(u128, encoded) << exponent;6    const nanoseconds = microseconds * std.time.ns_per_us;7    return std.math.cast(u64, nanoseconds) orelse std.math.maxInt(u64);8}

1/// A connection assumes the path costs 333 milliseconds until it measures, so the first probe2/// deadline rests on this value before any acknowledgment arrives. A fresh estimator opens with3/// that duration as its smoothed value and half of it as its variation.4pub const initial_ns: u64 = 333 * std.time.ns_per_ms;

1/// Works out how much of the gap the peer says it spent before answering. The call settles the two2/// questions that decide whether an ACK's delay counts at all, so the caller hands the answer3/// straight to `update`. Initial and Handshake acknowledgments carry no delay field, and the caller4/// passes false to say so, so the call yields zero. A cap applies only after the handshake is5/// confirmed, so the caller passes none before then.6pub fn reportedDelayNs(reported: bool, encoded: u62, exponent: u5, maximum_ns: ?u64) u64 {7    if (!reported) return 0;8    const delay_ns = delayNs(encoded, exponent);9    const maximum = maximum_ns orelse return delay_ns;10    return @min(delay_ns, maximum);11}

1/// Measures the gap between a packet going out and its answer coming back, so the connection can2/// turn one settled packet into a measurement. A clock that has not moved yields nothing to3/// measure, and the call offers none.4pub fn sample(sent_ns: u64, received_ns: u64) ?u64 {5    if (received_ns <= sent_ns) return null;6    return received_ns - sent_ns;7}

1const loss = @import("loss.zig");2const pto = @import("pto.zig");3const resend = @import("resend.zig");4const rtt = @import("rtt.zig");56pub const granularity_ns = rtt.granularity_ns;7pub const initial_rtt_ns = rtt.initial_ns;8pub const Estimator = rtt.Estimator;9pub const sample = rtt.sample;10pub const ackDelayNs = rtt.delayNs;11pub const reportedDelayNs = rtt.reportedDelayNs;1213pub const packet_threshold = loss.packet_threshold;14pub const time_threshold_numerator = loss.time_threshold_numerator;15pub const time_threshold_denominator = loss.time_threshold_denominator;16pub const lossDelayNs = loss.delayNs;17pub const reordered = loss.reordered;18pub const lossDeadlineNs = loss.deadlineNs;19pub const expired = loss.expired;2021pub const backoff_max = pto.backoff_max;22pub const probe_packets = pto.probe_packets;23pub const probePeriodNs = pto.periodNs;24pub const probeDeadlineNs = pto.deadlineNs;2526pub const LostRange = resend.LostRange;

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

1/// One millisecond establishes how fine the timing rules are willing to be, so the loss delay and2/// the probe wait are each held at or above it.3pub const granularity_ns: u64 = std.time.ns_per_ms;