lib/quic/src/connection/recovery/loss.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const rtt = @import("rtt.zig");
3
4 /// Three is how far under the largest acknowledged number a packet has to sit before reordering
5 /// alone condemns it, so the constant fixes how many later packets have to be acknowledged before
6 /// an earlier one is given up on. `reordered` measures that distance against it.
7 pub const packet_threshold: u62 = 3;
8
9 /// Nine eighths of a round trip is held as a numerator beside a denominator of eight, so the
10 /// constant fixes how much of a round trip a packet is given before elapsed time alone condemns it.
11 /// `delayNs` scales the larger of the two estimates by that fraction.
12 pub const time_threshold_numerator: u64 = 9;
13 pub const time_threshold_denominator: u64 = 8;
14
15 /// Works out how long a packet is given before elapsed time condemns it, so the connection hands
16 /// one delay to every space's detection pass. The calculation takes whichever of the two estimates
17 /// is larger and stretches it by nine eighths. The answer stays at or above the one millisecond
18 /// floor under the timing rules, the timer granularity. An estimate large enough to run the product
19 /// over stops at the largest u64 value.
20 pub fn delayNs(latest_ns: u64, smoothed_ns: u64) u64 {
21 const base = @max(latest_ns, smoothed_ns);
22 const scaled = @as(u128, base) * time_threshold_numerator / time_threshold_denominator;
23 const bounded = std.math.cast(u64, scaled) orelse std.math.maxInt(u64);
24 return @max(bounded, rtt.granularity_ns);
25 }
26
27 /// Says whether enough later packets have been acknowledged to condemn this one, so the detection
28 /// pass runs this reordering test over each held packet. Three is enough to give up on a packet
29 /// sitting that far under the largest acknowledged number. A number above the largest acknowledged
30 /// one is safe.
31 pub fn reordered(packet_number: u62, largest_acknowledged: u62) bool {
32 if (largest_acknowledged < packet_number) return false;
33 return largest_acknowledged - packet_number >= packet_threshold;
34 }
35
36 /// Works out the moment at which elapsed time will condemn a packet that went out at `sent_ns`, so
37 /// the space keeps the answer as the deadline `nextTimeout` offers. The calculation adds the delay
38 /// to the send time. A sum that runs over stops at the largest u64 value.
39 pub fn deadlineNs(sent_ns: u64, delay_ns: u64) u64 {
40 return std.math.add(u64, sent_ns, delay_ns) catch std.math.maxInt(u64);
41 }
42
43 /// Says whether elapsed time has already condemned a packet that went out at `sent_ns`, so the
44 /// caller settles the time question outright and avoids comparing deadlines itself. The answer
45 /// turns at the deadline itself, so a packet stands condemned from that moment on.
46 pub fn expired(sent_ns: u64, now_ns: u64, delay_ns: u64) bool {
47 return now_ns >= deadlineNs(sent_ns, delay_ns);
48 }
49
50 test "RFC 9002 section 6.1.1 the packet threshold declares three earlier packets lost" {
51 try std.testing.expect(!reordered(7, 5));
52 try std.testing.expect(!reordered(5, 5));
53 try std.testing.expect(!reordered(5, 7));
54 try std.testing.expect(reordered(5, 8));
55 try std.testing.expect(reordered(0, packet_threshold));
56 try std.testing.expect(!reordered(std.math.maxInt(u62), 0));
57 }
58
59 test "RFC 9002 section 6.1.2 the loss delay is nine eighths of the larger estimate" {
60 const latest_ns = 80 * std.time.ns_per_ms;
61 const smoothed_ns = 40 * std.time.ns_per_ms;
62 try std.testing.expectEqual(latest_ns * 9 / 8, delayNs(latest_ns, smoothed_ns));
63 try std.testing.expectEqual(latest_ns * 9 / 8, delayNs(smoothed_ns, latest_ns));
64 }
65
66 test "RFC 9002 section 6.1.2 the loss delay never falls below the granularity" {
67 try std.testing.expectEqual(rtt.granularity_ns, delayNs(0, 0));
68 try std.testing.expectEqual(rtt.granularity_ns, delayNs(1, 1));
69 }
70
71 test "RFC 9002 section 6.1.2 an extreme estimate saturates the loss delay" {
72 const maximum = std.math.maxInt(u64);
73 try std.testing.expectEqual(maximum, delayNs(maximum, maximum));
74 try std.testing.expectEqual(maximum, deadlineNs(maximum, 1));
75 try std.testing.expect(!expired(maximum, maximum - 1, 1));
76 }
77
78 test "RFC 9002 section 6.1.2 the time threshold compares against the send time" {
79 const delay_ns = 10 * std.time.ns_per_ms;
80 try std.testing.expect(!expired(100, 100 + delay_ns - 1, delay_ns));
81 try std.testing.expect(expired(100, 100 + delay_ns, delay_ns));
82 try std.testing.expect(!expired(100, 99, delay_ns));
83 }