lib/quic/src/connection/recovery/resend.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 /// Marks off the stretch of a stream that a loss has put back in the queue. The sending half of
4 /// stream 0 and each space's CRYPTO stream hold one, and the send path reads it to empty that
5 /// stretch before it takes anything new. Holding a single stretch keeps the bookkeeping to two
6 /// numbers whatever the pattern of loss. Two losses with a settled stretch between them therefore
7 /// widen into one, and the bytes in the middle travel a second time.
8 pub const LostRange = struct {
9 start: u62 = 0,
10 end: u62 = 0,
11
12 /// Says whether anything is waiting to travel a second time, so the send path chooses between
13 /// resending and reaching for new bytes.
14 pub fn isEmpty(self: LostRange) bool {
15 std.debug.assert(self.start <= self.end);
16 return self.start == self.end;
17 }
18
19 /// Counts the bytes waiting to travel a second time, so the send path sizes a resent frame
20 /// against it.
21 pub fn length(self: LostRange) u62 {
22 std.debug.assert(self.start <= self.end);
23 return self.end - self.start;
24 }
25
26 /// Widens the stretch until it reaches over `count` bytes from `offset`. The loss path calls it
27 /// with the stretch each lost frame covered. A call carrying no bytes leaves the stretch as it
28 /// was.
29 pub fn add(self: *LostRange, offset: u62, count: u62) void {
30 std.debug.assert(count <= std.math.maxInt(u62) - offset);
31 if (count == 0) return;
32 const end = offset + count;
33 if (self.isEmpty()) {
34 self.* = .{ .start = offset, .end = end };
35 } else {
36 self.start = @min(self.start, offset);
37 self.end = @max(self.end, end);
38 }
39 std.debug.assert(self.start <= offset);
40 std.debug.assert(end <= self.end);
41 }
42
43 /// Pulls in whichever end of the stretch the settled bytes reach, so an acknowledgment arriving
44 /// after the loss keeps those bytes from traveling a third time. Bytes settled in the middle
45 /// change nothing, because a single stretch has no way to hold a hole. A stretch pulled in from
46 /// both ends until it is bare returns to empty.
47 pub fn acknowledge(self: *LostRange, offset: u62, count: u62) void {
48 std.debug.assert(count <= std.math.maxInt(u62) - offset);
49 if (self.isEmpty()) return;
50 const waiting = self.length();
51 const end = offset + count;
52 if (offset <= self.start and self.start < end) self.start = @min(end, self.end);
53 if (offset < self.end and self.end <= end) self.end = @max(offset, self.start);
54 if (self.start == self.end) self.* = .{};
55 std.debug.assert(self.start <= self.end);
56 std.debug.assert(self.length() <= waiting);
57 }
58
59 /// Drops `count` bytes off the front. The send path calls it once a packet carries the resent
60 /// bytes. The count stays within what was waiting.
61 pub fn advance(self: *LostRange, count: u62) void {
62 std.debug.assert(count <= self.length());
63 self.start += count;
64 if (self.start == self.end) self.* = .{};
65 std.debug.assert(self.start <= self.end);
66 }
67 };
68
69 test "RFC 9000 section 13.3 a lost range covers each lost frame and trims acknowledged ends" {
70 var lost = LostRange{};
71 lost.add(100, 0);
72 try std.testing.expect(lost.isEmpty());
73 lost.add(40, 20);
74 lost.add(10, 10);
75 try std.testing.expectEqual(LostRange{ .start = 10, .end = 60 }, lost);
76 lost.acknowledge(30, 5);
77 try std.testing.expectEqual(LostRange{ .start = 10, .end = 60 }, lost);
78 lost.acknowledge(0, 15);
79 lost.acknowledge(50, 20);
80 try std.testing.expectEqual(LostRange{ .start = 15, .end = 50 }, lost);
81 lost.acknowledge(50, 10);
82 lost.acknowledge(5, 10);
83 try std.testing.expectEqual(LostRange{ .start = 15, .end = 50 }, lost);
84 lost.advance(30);
85 try std.testing.expectEqual(@as(u62, 5), lost.length());
86 lost.acknowledge(40, 10);
87 try std.testing.expect(lost.isEmpty());
88 try std.testing.expectEqual(LostRange{}, lost);
89 }
90
91 test "RFC 9000 section 19.8 a lost range reaches the largest stream offset" {
92 const last: u62 = std.math.maxInt(u62);
93 var lost = LostRange{};
94 lost.add(last - 1, 1);
95 try std.testing.expectEqual(@as(u62, 1), lost.length());
96 lost.advance(1);
97 try std.testing.expect(lost.isEmpty());
98 lost.add(last - 2, 2);
99 lost.acknowledge(last - 1, 1);
100 try std.testing.expectEqual(LostRange{ .start = last - 2, .end = last - 1 }, lost);
101 }