lib/quic/src/connection/recovery/pto.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const rtt = @import("rtt.zig");
3
4 /// The wait may double sixteen times as probes go unanswered, and past that count the wait holds
5 /// steady. Holding the wait there keeps the shift under the 64 bits the period is held in, which a
6 /// compile-time check enforces.
7 pub const backoff_max: u32 = 16;
8
9 comptime {
10 std.debug.assert(backoff_max < 64);
11 }
12
13 /// Two packets, each one the peer owes an answer to, fix what the connection owes the peer when a
14 /// probe deadline passes with packets still outstanding. With nothing outstanding the connection
15 /// owes one.
16 pub const probe_packets: u8 = 2;
17
18 /// Works out how long to wait for an answer for one space, then doubles that wait once per
19 /// unanswered probe up to the ceiling. The connection works out one wait per space and arms the
20 /// soonest deadline they produce. The wait itself is the smoothed estimate, plus four times the
21 /// variation, plus whatever delay the peer has told this endpoint to expect. The variation term is
22 /// held at or above the one millisecond floor under the timing rules, the timer granularity. Only
23 /// the application space passes a nonzero delay, and only after the handshake is confirmed, so
24 /// every other caller passes zero. Each sum and each shift holds at the maximum once it reaches it.
25 pub fn periodNs(smoothed_ns: u64, variation_ns: u64, max_ack_delay_ns: u64, count: u32) u64 {
26 const variance_ns = @max(variation_ns *| 4, rtt.granularity_ns);
27 const base_ns = smoothed_ns +| variance_ns +| max_ack_delay_ns;
28 std.debug.assert(base_ns >= rtt.granularity_ns);
29 const shift: u6 = @intCast(@min(count, backoff_max));
30 const period_ns = base_ns <<| shift;
31 std.debug.assert(period_ns >= base_ns);
32 return period_ns;
33 }
34
35 /// Adds the wait to the instant it is measured from so the connection keeps the answer as the probe
36 /// deadline `nextTimeout` offers. A sum that runs over stops at the largest u64 value. The instant
37 /// measured from is when the space last sent a packet the peer owes an answer to, or, with nothing
38 /// outstanding, the anchor the anti-deadlock probe holds.
39 pub fn deadlineNs(sent_ns: u64, period_ns: u64) u64 {
40 const deadline_ns = std.math.add(u64, sent_ns, period_ns) catch std.math.maxInt(u64);
41 std.debug.assert(deadline_ns >= sent_ns);
42 return deadline_ns;
43 }
44
45 test "RFC 9002 section 6.2.1 the period sums the estimate, four variations, and the delay" {
46 const smoothed_ns = 100 * std.time.ns_per_ms;
47 const variation_ns = 10 * std.time.ns_per_ms;
48 const delay_ns = 25 * std.time.ns_per_ms;
49 try std.testing.expectEqual(
50 smoothed_ns + 4 * variation_ns,
51 periodNs(smoothed_ns, variation_ns, 0, 0),
52 );
53 try std.testing.expectEqual(
54 smoothed_ns + 4 * variation_ns + delay_ns,
55 periodNs(smoothed_ns, variation_ns, delay_ns, 0),
56 );
57 }
58
59 test "RFC 9002 section 6.2.1 the variation term never falls below the granularity" {
60 try std.testing.expectEqual(rtt.granularity_ns, periodNs(0, 0, 0, 0));
61 const smoothed_ns = 5 * std.time.ns_per_ms;
62 try std.testing.expectEqual(smoothed_ns + rtt.granularity_ns, periodNs(smoothed_ns, 0, 0, 0));
63 }
64
65 test "RFC 9002 section 6.2.1 consecutive expiries double the period" {
66 const smoothed_ns = 100 * std.time.ns_per_ms;
67 const variation_ns = 10 * std.time.ns_per_ms;
68 const base_ns = smoothed_ns + 4 * variation_ns;
69 try std.testing.expectEqual(base_ns, periodNs(smoothed_ns, variation_ns, 0, 0));
70 try std.testing.expectEqual(base_ns * 2, periodNs(smoothed_ns, variation_ns, 0, 1));
71 try std.testing.expectEqual(base_ns * 4, periodNs(smoothed_ns, variation_ns, 0, 2));
72 try std.testing.expectEqual(base_ns * 8, periodNs(smoothed_ns, variation_ns, 0, 3));
73 }
74
75 test "RFC 9002 section 6.2.1 the backoff stops at the pinned maximum" {
76 const smoothed_ns = 10 * std.time.ns_per_ms;
77 const capped = periodNs(smoothed_ns, 0, 0, backoff_max);
78 try std.testing.expectEqual(capped, periodNs(smoothed_ns, 0, 0, backoff_max + 1));
79 try std.testing.expectEqual(capped, periodNs(smoothed_ns, 0, 0, std.math.maxInt(u32)));
80 const base_ns = smoothed_ns + rtt.granularity_ns;
81 try std.testing.expectEqual(base_ns << backoff_max, capped);
82 }
83
84 test "RFC 9002 section 6.2.1 an extreme estimate saturates the period and the deadline" {
85 const maximum = std.math.maxInt(u64);
86 try std.testing.expectEqual(maximum, periodNs(maximum, maximum, maximum, 0));
87 try std.testing.expectEqual(maximum, periodNs(maximum, 0, 0, std.math.maxInt(u32)));
88 try std.testing.expectEqual(maximum, deadlineNs(maximum, 1));
89 try std.testing.expectEqual(@as(u64, 101), deadlineNs(100, 1));
90 }