lib/quic/src/connection/stream/flow.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 /// Tracks what the peer has allowed this endpoint to send, over one stream or over the whole
4 /// connection. The sending part of a stream and the connection each hold one so every byte sent is
5 /// charged against it. Its fields are that allowance, how much of it has gone, and the figure a
6 /// BLOCKED frame last reported. What has gone stays inside the allowance.
7 pub const Credit = struct {
8 limit: u62,
9 used: u62 = 0,
10 blocked_limit: ?u62 = null,
11
12 pub fn init(limit: u62) Credit {
13 return .{ .limit = limit };
14 }
15
16 /// Counts what is left to send under the allowance so the send path sizes each chunk against
17 /// it.
18 pub fn available(self: Credit) u62 {
19 std.debug.assert(self.used <= self.limit);
20 return self.limit - self.used;
21 }
22
23 /// Lifts the allowance to a larger figure the peer has granted. An arriving MAX_DATA or
24 /// MAX_STREAM_DATA frame reaches the credit through this call. A figure at or under the
25 /// allowance in hand leaves it alone, so a frame arriving behind its neighbors is harmless.
26 pub fn raise(self: *Credit, maximum: u62) void {
27 std.debug.assert(self.used <= self.limit);
28 if (maximum <= self.limit) return;
29 self.limit = maximum;
30 }
31
32 /// Charges bytes that have gone out against the allowance so the send path records each newly
33 /// sent byte here. The count stays inside what was left.
34 pub fn consume(self: *Credit, count: u62) void {
35 std.debug.assert(count <= self.available());
36 self.used += count;
37 std.debug.assert(self.used <= self.limit);
38 }
39
40 /// Hands back the figure a BLOCKED frame would report so the send path decides whether that
41 /// frame belongs in the packet it is building. The call answers while bytes are waiting and the
42 /// allowance is spent. Each figure is reported once: one a sent frame already carried yields
43 /// nothing until the peer lifts the allowance.
44 pub fn blocked(self: Credit, waiting: bool) ?u62 {
45 if (!waiting) return null;
46 if (self.available() != 0) return null;
47 const reported = self.blocked_limit orelse return self.limit;
48 return if (reported == self.limit) null else self.limit;
49 }
50
51 /// Notes which figure a BLOCKED frame has carried. The send path calls this once the frame is
52 /// in a sealed packet. That figure stays at or under the allowance in force.
53 pub fn markBlocked(self: *Credit, limit: u62) void {
54 std.debug.assert(limit <= self.limit);
55 self.blocked_limit = limit;
56 }
57
58 /// Forgets the figure noted for the loss path so a sender still held up reports itself a second
59 /// time after the report is lost. A lost frame carrying a stale figure leaves the note alone,
60 /// because a later frame has carried the figure in force since.
61 pub fn loseBlocked(self: *Credit, limit: u62) void {
62 const reported = self.blocked_limit orelse return;
63 std.debug.assert(reported <= self.limit);
64 if (reported != limit) return;
65 self.blocked_limit = null;
66 }
67 };
68
69 /// Tracks what this endpoint has told the peer it will take, over one stream or over the whole
70 /// connection. The receiving part of a stream and the connection each hold one so the window
71 /// decides both what arriving data is allowed and when a limit frame goes out. Its fields are the
72 /// window width, the figure in force, the totals arrived and given up to the application, and the
73 /// given-up total at which that figure was set. `init` opens with the figure set to the window
74 /// width.
75 pub const Window = struct {
76 size: u62,
77 limit: u62,
78 received: u62 = 0,
79 consumed: u62 = 0,
80 update_base: u62 = 0,
81 /// Flag set when the packet carrying the figure in force was lost, so a window with no new room
82 /// still asks for a limit frame by having `update` offer that same figure a second time.
83 /// `advertise` clears it.
84 limit_lost: bool = false,
85
86 pub fn init(size: u62) Window {
87 return .{ .size = size, .limit = size };
88 }
89
90 /// Says whether an arrived total is still inside what this endpoint offered so the receiving
91 /// part checks arriving data before accepting it, because a false answer closes the connection
92 /// with FLOW_CONTROL_ERROR. A total level with the figure is taken, and one byte beyond it is
93 /// turned away.
94 pub fn allows(self: Window, received: u64) bool {
95 return received <= self.limit;
96 }
97
98 /// Notes an arrived total for the receiving part after `allows` has accepted the data. The
99 /// total stays inside the figure in force. A total under one already noted leaves it alone.
100 pub fn record(self: *Window, received: u62) void {
101 std.debug.assert(received <= self.limit);
102 if (received > self.received) self.received = received;
103 }
104
105 /// Notes bytes the application has taken, or bytes a reset has thrown away, so reading stream
106 /// bytes earns the peer more room. The given-up total climbs and stays at or under the arrived
107 /// total.
108 pub fn release(self: *Window, consumed: u62) void {
109 std.debug.assert(consumed >= self.consumed);
110 std.debug.assert(consumed <= self.received);
111 self.consumed = consumed;
112 }
113
114 /// Offers a larger figure once the application has taken half a window so the send path decides
115 /// whether a MAX_DATA or MAX_STREAM_DATA frame belongs in the packet it is building. That
116 /// figure is the given-up total plus one window width, stopping at the largest u62 value. With
117 /// `limit_lost` set and no larger figure due, the call offers the figure in force a second
118 /// time. The call offers nothing when no frame is called for.
119 pub fn update(self: Window) ?u62 {
120 std.debug.assert(self.consumed >= self.update_base);
121 const progress: u64 = self.consumed - self.update_base;
122 if (progress * 2 >= self.size) {
123 const next = std.math.add(u62, self.consumed, self.size) catch std.math.maxInt(u62);
124 if (next > self.limit) return next;
125 }
126 return if (self.limit_lost) self.limit else null;
127 }
128
129 /// Notes the figure carried by a MAX_DATA frame, or by a MAX_STREAM_DATA frame, that has gone
130 /// out, then clears `limit_lost`. The send path calls this once the limit frame is in a sealed
131 /// packet. The figure climbs, save when a loss forces the same one out a second time. Noting a
132 /// larger figure moves the mark that the next half window is counted from.
133 pub fn advertise(self: *Window, limit: u62) void {
134 std.debug.assert(limit <= std.math.add(u62, self.consumed, self.size) catch limit);
135 if (limit == self.limit) {
136 std.debug.assert(self.limit_lost);
137 self.limit_lost = false;
138 return;
139 }
140 std.debug.assert(limit > self.limit);
141 self.limit_lost = false;
142 self.limit = limit;
143 self.update_base = self.consumed;
144 }
145
146 /// Marks the figure in force as lost for the loss path when the lost frame carried it, so the
147 /// peer still learns a limit whose frame was lost. A lost frame carrying a stale figure calls
148 /// for nothing, because a later frame has carried the figure in force since.
149 pub fn loseLimit(self: *Window, limit: u62) void {
150 std.debug.assert(limit <= self.limit);
151 if (limit != self.limit) return;
152 self.limit_lost = true;
153 }
154 };
155
156 test "RFC 9000 section 4.1 credit ignores smaller limits and reports blocked once per limit" {
157 var credit = Credit.init(4);
158 credit.raise(3);
159 try std.testing.expectEqual(@as(u62, 4), credit.limit);
160 try std.testing.expectEqual(@as(?u62, null), credit.blocked(true));
161 credit.consume(4);
162 try std.testing.expectEqual(@as(?u62, null), credit.blocked(false));
163 try std.testing.expectEqual(@as(?u62, 4), credit.blocked(true));
164 credit.markBlocked(4);
165 try std.testing.expectEqual(@as(?u62, null), credit.blocked(true));
166 credit.raise(6);
167 try std.testing.expectEqual(@as(u62, 2), credit.available());
168 credit.consume(2);
169 try std.testing.expectEqual(@as(?u62, 6), credit.blocked(true));
170 }
171
172 test "RFC 9000 section 13.3 a lost BLOCKED frame reports again only while blocked at its limit" {
173 var credit = Credit.init(4);
174 credit.consume(4);
175 credit.markBlocked(4);
176 credit.loseBlocked(3);
177 try std.testing.expectEqual(@as(?u62, null), credit.blocked(true));
178 credit.loseBlocked(4);
179 try std.testing.expectEqual(@as(?u62, 4), credit.blocked(true));
180 try std.testing.expectEqual(@as(?u62, null), credit.blocked(false));
181 credit.markBlocked(4);
182 credit.raise(6);
183 credit.loseBlocked(4);
184 try std.testing.expectEqual(@as(?u62, null), credit.blocked(true));
185 }
186
187 test "RFC 9000 section 4.2 window update waits for half the window" {
188 var window = Window.init(8);
189 try std.testing.expect(window.allows(8));
190 try std.testing.expect(!window.allows(9));
191 window.record(8);
192 window.release(3);
193 try std.testing.expectEqual(@as(?u62, null), window.update());
194 window.release(4);
195 try std.testing.expectEqual(@as(?u62, 12), window.update());
196 window.release(6);
197 const next = window.update().?;
198 try std.testing.expectEqual(@as(u62, 14), next);
199 window.advertise(next);
200 try std.testing.expectEqual(@as(?u62, null), window.update());
201 var closed = Window.init(0);
202 try std.testing.expectEqual(@as(?u62, null), closed.update());
203 try std.testing.expect(!closed.allows(1));
204 }
205
206 test "RFC 9000 section 13.3 a lost limit frame repeats only the current limit" {
207 var window = Window.init(8);
208 window.record(8);
209 window.release(4);
210 const first = window.update() orelse return error.NoUpdate;
211 window.advertise(first);
212 try std.testing.expectEqual(@as(?u62, null), window.update());
213 window.loseLimit(first);
214 try std.testing.expectEqual(@as(?u62, first), window.update());
215 window.advertise(first);
216 try std.testing.expectEqual(first, window.limit);
217 try std.testing.expectEqual(@as(?u62, null), window.update());
218 window.record(12);
219 window.release(8);
220 const second = window.update() orelse return error.NoUpdate;
221 try std.testing.expect(second > first);
222 window.advertise(second);
223 window.loseLimit(first);
224 try std.testing.expectEqual(@as(?u62, null), window.update());
225 }