lib/quic/src/connection/sent.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const quic = @import("../root.zig");
3
4 const recovery = quic.connection.recovery;
5
6 pub const CryptoSummary = struct {
7 offset: u62,
8 length: u20,
9 };
10
11 /// Records which stream bytes one STREAM frame put on the wire and whether that frame closed the
12 /// stream, so the sending half of stream 0 receives this summary once the packet that carried that
13 /// frame is resolved. The summary names the stream, the offset, the byte count, and the FIN.
14 pub const StreamSummary = struct {
15 stream_id: u62,
16 offset: u62,
17 length: u16,
18 fin: bool,
19 };
20
21 /// Keeps, for one sent packet, whatever a later loss must act on, so loss recovery finds what one
22 /// lost packet can put back in the queue. The stream and flow control fields hold the figures that
23 /// went out, so a lost frame can be weighed against the state as it stands now before anything is
24 /// sent again. The ACK, PING, HANDSHAKE_DONE, and CONNECTION_CLOSE fields need one bit each,
25 /// because those frames lack recovery data for the sender.
26 pub const FrameSummary = struct {
27 crypto: ?CryptoSummary = null,
28 stream: ?StreamSummary = null,
29 reset_stream: ?quic.frame.ResetStream = null,
30 stop_sending: ?quic.frame.StopSending = null,
31 max_data: ?u62 = null,
32 max_stream_data: ?quic.frame.StreamData = null,
33 /// A connection in this package sends no MAX_STREAMS, because the one stream the server offers
34 /// leaves the count nothing to grow into, so the loss path asserts this field stays empty.
35 max_streams: ?quic.frame.StreamLimit = null,
36 data_blocked: ?u62 = null,
37 stream_data_blocked: ?quic.frame.StreamData = null,
38 streams_blocked: ?quic.frame.StreamLimit = null,
39 ack: bool = false,
40 ping: bool = false,
41 handshake_done: bool = false,
42 connection_close: bool = false,
43 };
44
45 /// Holds one sent packet until an acknowledgment or a loss settles it, so both the acknowledgment
46 /// path and the loss path work over this record. The record keeps the number, the send time,
47 /// whether the peer owes an answer, the byte cost, the key phase, and what the packet carried. Once
48 /// settled, the packet stops counting against the space's outstanding bytes.
49 pub const SentRecord = struct {
50 packet_number: u62,
51 time_sent_ns: u64,
52 ack_eliciting: bool,
53 acknowledged: bool,
54 lost: bool,
55 in_flight_bytes: u32,
56 key_phase: bool,
57 key_phase_present: bool,
58 frames: FrameSummary,
59
60 pub fn empty() SentRecord {
61 return .{
62 .packet_number = 0,
63 .time_sent_ns = 0,
64 .ack_eliciting = false,
65 .acknowledged = false,
66 .lost = false,
67 .in_flight_bytes = 0,
68 .key_phase = false,
69 .key_phase_present = false,
70 .frames = .{},
71 };
72 }
73
74 /// Reports whether this packet still counts against the space's outstanding bytes, so both
75 /// passes can skip a record that stopped counting. The packet counts while awaiting settlement
76 /// from an acknowledgment or a loss.
77 pub fn inFlight(self: SentRecord) bool {
78 return !self.acknowledged and !self.lost;
79 }
80 };
81
82 /// Reports what one detection pass took out and when the next pass is due, so the space can store
83 /// that pass's deadline. The report carries a packet count, a byte total, and a deadline.
84 pub const Lost = struct {
85 records: u16 = 0,
86 bytes: u64 = 0,
87 /// Holds the soonest moment at which the time threshold will reach a packet the pass left
88 /// alone, offered by `nextTimeout` so a caller knows when to call back. The field stays empty
89 /// when the pass left nothing outstanding under the largest acknowledged number.
90 deadline_ns: ?u64 = null,
91 };
92
93 /// Reports what one ACK frame settled for the first time, so the connection can take a round-trip
94 /// sample that needs both of its facts. The summary carries a packet count, whether any of those
95 /// packets was one the peer owed an answer to, and when the largest of them went out.
96 pub const Acknowledged = struct {
97 records: u16 = 0,
98 ack_eliciting: bool = false,
99 /// Holds when the ACK frame's largest number went out so the connection can sample round-trip
100 /// time, populated only when this ACK settles that packet for the first time. When an earlier
101 /// ACK already settled that largest number, the field stays empty, and the connection skips
102 /// round-trip sampling.
103 largest_sent_ns: ?u64 = null,
104 };
105
106 pub const Sent = struct {
107 records: []SentRecord,
108 head: u16 = 0,
109 count: u16 = 0,
110 /// Holds what this space has outstanding, in bytes, to supply this space's share of what the
111 /// connection has outstanding. The count climbs as packets go out and falls as each is settled.
112 in_flight_bytes: u64 = 0,
113
114 pub const AddError = error{Full};
115
116 pub fn init(records: []SentRecord) Sent {
117 std.debug.assert(records.len <= std.math.maxInt(u16));
118 for (records) |*record| record.* = SentRecord.empty();
119 return .{ .records = records };
120 }
121
122 pub fn hasCapacity(self: *Sent) bool {
123 self.retirePrefix();
124 return self.count < self.records.len;
125 }
126
127 pub fn add(self: *Sent, record: SentRecord) AddError!void {
128 std.debug.assert(record.inFlight());
129 self.retirePrefix();
130 if (self.count == self.records.len) return error.Full;
131 const slot = self.slotIndex(self.count);
132 self.records[slot] = record;
133 self.count += 1;
134 self.in_flight_bytes += record.in_flight_bytes;
135 }
136
137 /// Settles every held packet the ACK frame covers and hands each one to the caller-supplied
138 /// sink's `onAcknowledged` method, so the arriving frame reaches the stream and CRYPTO state
139 /// that settled packets carried. A packet the same ACK has already settled is passed over, so
140 /// the sink sees each one once. The ring retires settled packets at its front, freeing their
141 /// slots for later sends. The function reports back what this ACK settled for the first time.
142 pub fn acknowledge(self: *Sent, value: quic.frame.Ack, sink: anytype) Acknowledged {
143 var result = Acknowledged{};
144 for (0..self.records.len) |offset| {
145 if (offset >= self.count) break;
146 const record = &self.records[self.slotIndex(@intCast(offset))];
147 if (!record.inFlight()) continue;
148 if (!acknowledges(value, record.packet_number)) continue;
149 record.acknowledged = true;
150 self.release(record.in_flight_bytes);
151 result.records +|= 1;
152 result.ack_eliciting = result.ack_eliciting or record.ack_eliciting;
153 if (record.packet_number == value.largest) result.largest_sent_ns = record.time_sent_ns;
154 sink.onAcknowledged(record.*);
155 }
156 self.retirePrefix();
157 return result;
158 }
159
160 /// Empties the ring and returns the outstanding byte count to zero when the space drops its
161 /// keys, because subsequent arrivals lack keys to settle those packets.
162 pub fn clear(self: *Sent) void {
163 for (self.records) |*record| record.* = SentRecord.empty();
164 self.head = 0;
165 self.count = 0;
166 self.in_flight_bytes = 0;
167 }
168
169 /// Walks the held packets at or under the largest acknowledged number and settles each one that
170 /// either rule reaches, moving the frames of each lost packet back into the send queues. The
171 /// rule that declares a packet lost once three later packets are acknowledged, the packet
172 /// threshold, reaches a packet three or more below that number, and the time threshold reaches
173 /// one whose loss delay has run out. Each packet the pass settles goes to the caller-supplied
174 /// sink's `onLost` method. The pass reports the soonest moment at which the time rule will
175 /// reach one of the packets it left alone.
176 pub fn detectLost(
177 self: *Sent,
178 largest_acknowledged: u62,
179 now_ns: u64,
180 delay_ns: u64,
181 sink: anytype,
182 ) Lost {
183 var result = Lost{};
184 for (0..self.records.len) |offset| {
185 if (offset >= self.count) break;
186 const record = &self.records[self.slotIndex(@intCast(offset))];
187 if (!record.inFlight()) continue;
188 if (record.packet_number > largest_acknowledged) continue;
189 const deadline_ns = recovery.lossDeadlineNs(record.time_sent_ns, delay_ns);
190 const threshold = recovery.reordered(record.packet_number, largest_acknowledged);
191 if (!threshold and now_ns < deadline_ns) {
192 result.deadline_ns = earlier(result.deadline_ns, deadline_ns);
193 continue;
194 }
195 record.lost = true;
196 self.release(record.in_flight_bytes);
197 result.records +|= 1;
198 result.bytes +|= record.in_flight_bytes;
199 sink.onLost(record.*);
200 }
201 self.retirePrefix();
202 return result;
203 }
204
205 fn release(self: *Sent, bytes: u32) void {
206 std.debug.assert(self.in_flight_bytes >= bytes);
207 self.in_flight_bytes -= bytes;
208 }
209
210 fn retirePrefix(self: *Sent) void {
211 for (0..self.records.len) |_| {
212 if (self.count == 0) break;
213 if (self.records[self.head].inFlight()) break;
214 self.records[self.head] = SentRecord.empty();
215 self.head = @intCast((@as(usize, self.head) + 1) % self.records.len);
216 self.count -= 1;
217 }
218 }
219
220 fn slotIndex(self: *const Sent, offset: u16) usize {
221 std.debug.assert(offset <= self.count);
222 std.debug.assert(offset < self.records.len);
223 return (@as(usize, self.head) + offset) % self.records.len;
224 }
225 };
226
227 fn earlier(current: ?u64, candidate: u64) u64 {
228 return if (current) |value| @min(value, candidate) else candidate;
229 }
230
231 pub fn acknowledges(value: quic.frame.Ack, packet_number: u62) bool {
232 var largest = value.largest;
233 var smallest = largest - value.first_range;
234 if (packet_number >= smallest and packet_number <= largest) return true;
235 var iterator = value.iterator();
236 for (0..quic.frame.ack_ranges_max) |index| {
237 if (index >= value.range_count) break;
238 const range = (iterator.next() catch return false) orelse return false;
239 largest = smallest - range.gap - 2;
240 smallest = largest - range.length;
241 if (packet_number >= smallest and packet_number <= largest) return true;
242 }
243 return false;
244 }
245
246 test "sent record maximum and maximum plus one" {
247 var records: [1]SentRecord = undefined;
248 var sent = Sent.init(&records);
249 var record = SentRecord.empty();
250 record.ack_eliciting = true;
251 try sent.add(record);
252 try std.testing.expectError(error.Full, sent.add(record));
253 }
254
255 const StreamCounter = struct {
256 streams: u32 = 0,
257
258 pub fn onAcknowledged(self: *StreamCounter, record: SentRecord) void {
259 if (record.frames.stream != null) self.streams += 1;
260 }
261 };
262
263 test "RFC 9000 section 13.3 acknowledgment reports each record's frames once" {
264 var records: [2]SentRecord = undefined;
265 var sent = Sent.init(&records);
266 var record = SentRecord.empty();
267 record.ack_eliciting = true;
268 record.frames.stream = .{ .stream_id = 0, .offset = 0, .length = 4, .fin = false };
269 try sent.add(record);
270 record.packet_number = 1;
271 try sent.add(record);
272 const ack = quic.frame.Ack{
273 .largest = 1,
274 .delay = 0,
275 .first_range = 1,
276 .range_count = 0,
277 .ranges = &.{},
278 .ecn = null,
279 };
280 var counter = StreamCounter{};
281 const first = sent.acknowledge(ack, &counter);
282 const second = sent.acknowledge(ack, &counter);
283 try std.testing.expectEqual(@as(u32, 2), counter.streams);
284 try std.testing.expectEqual(@as(u16, 0), sent.count);
285 try std.testing.expectEqual(@as(u16, 2), first.records);
286 try std.testing.expectEqual(@as(u16, 0), second.records);
287 try std.testing.expect(first.ack_eliciting);
288 try std.testing.expectEqual(@as(?u64, 0), first.largest_sent_ns);
289 try std.testing.expectEqual(@as(?u64, null), second.largest_sent_ns);
290 }
291
292 test "RFC 9002 section 2 bytes in flight follow the sent records" {
293 var records: [2]SentRecord = undefined;
294 var sent = Sent.init(&records);
295 var record = SentRecord.empty();
296 record.ack_eliciting = true;
297 record.in_flight_bytes = 1_200;
298 try sent.add(record);
299 record.packet_number = 1;
300 record.in_flight_bytes = 900;
301 try sent.add(record);
302 try std.testing.expectEqual(@as(u64, 2_100), sent.in_flight_bytes);
303 const ack = quic.frame.Ack{
304 .largest = 0,
305 .delay = 0,
306 .first_range = 0,
307 .range_count = 0,
308 .ranges = &.{},
309 .ecn = null,
310 };
311 var counter = StreamCounter{};
312 _ = sent.acknowledge(ack, &counter);
313 try std.testing.expectEqual(@as(u64, 900), sent.in_flight_bytes);
314 sent.clear();
315 try std.testing.expectEqual(@as(u64, 0), sent.in_flight_bytes);
316 }
317
318 test "RFC 9001 section 4.9.1 key discard drops sent records" {
319 var records: [1]SentRecord = undefined;
320 var sent = Sent.init(&records);
321 var record = SentRecord.empty();
322 record.ack_eliciting = true;
323 try sent.add(record);
324 try std.testing.expect(!sent.hasCapacity());
325 sent.clear();
326 try std.testing.expect(sent.hasCapacity());
327 }