lib/quic/src/connection/space.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const quic = @import("../root.zig");
3
4 pub const Kind = enum(u2) {
5 initial,
6 handshake,
7 application,
8
9 pub fn level(self: Kind) quic.tls.Level {
10 return switch (self) {
11 .initial => .initial,
12 .handshake => .handshake,
13 .application => .one_rtt,
14 };
15 }
16 };
17
18 pub const NumberEncoding = struct {
19 packet_number: u62,
20 bits: u6,
21 value: u32,
22 };
23
24 pub const Space = struct {
25 kind: Kind,
26 next_packet_number: u62 = 0,
27 largest_acknowledged: ?u62 = null,
28 largest_received: ?u62 = null,
29 received: quic.connection.Ranges,
30 sent: quic.connection.Sent,
31 ack_pending: bool = false,
32 largest_received_at_ns: u64 = 0,
33 ack_due_at_ns: ?u64 = null,
34 /// Holds when this space last sent a packet the peer owes an answer to. The probe period is
35 /// added to it to reach the probe deadline for this space. Discarding the space's keys wipes
36 /// it.
37 last_ack_eliciting_sent_ns: ?u64 = null,
38 /// Holds when the oldest packet still outstanding under the largest acknowledged number will
39 /// fall to the time rule, so `nextTimeout` offers this instant to the connection. Each
40 /// detection pass writes it afresh. The deadline is empty until an acknowledgment has arrived,
41 /// and empty again once every packet the rules can reach has gone.
42 loss_deadline_ns: ?u64 = null,
43
44 pub const NumberError = error{ PacketNumberExhausted, PacketNumberDistance };
45 pub const AckError = error{AcknowledgesUnsent};
46
47 pub fn init(
48 kind: Kind,
49 ranges: []quic.connection.Range,
50 records: []quic.connection.SentRecord,
51 ) Space {
52 return .{
53 .kind = kind,
54 .received = quic.connection.Ranges.init(ranges),
55 .sent = quic.connection.Sent.init(records),
56 };
57 }
58
59 pub fn numberEncoding(self: *const Space) NumberError!NumberEncoding {
60 const packet_number = self.next_packet_number;
61 if (packet_number >= std.math.maxInt(u62)) return error.PacketNumberExhausted;
62 if (self.largest_acknowledged) |largest| {
63 if (packet_number <= largest) return error.PacketNumberDistance;
64 const distance = packet_number - largest;
65 if (distance >= @as(u62, 1) << 31) return error.PacketNumberDistance;
66 const truncated = quic.packet.Number.truncate(packet_number, largest);
67 return .{
68 .packet_number = packet_number,
69 .bits = truncated.bits,
70 .value = truncated.value,
71 };
72 }
73 return .{ .packet_number = packet_number, .bits = 32, .value = @truncate(packet_number) };
74 }
75
76 pub fn recordSent(self: *Space, record: quic.connection.SentRecord) !void {
77 std.debug.assert(record.packet_number == self.next_packet_number);
78 try self.sent.add(record);
79 self.next_packet_number += 1;
80 if (record.ack_eliciting) self.last_ack_eliciting_sent_ns = record.time_sent_ns;
81 }
82
83 pub fn processAck(
84 self: *Space,
85 value: quic.frame.Ack,
86 sink: anytype,
87 ) AckError!quic.connection.Acknowledged {
88 if (value.largest >= self.next_packet_number) return error.AcknowledgesUnsent;
89 const result = self.sent.acknowledge(value, sink);
90 if (self.largest_acknowledged == null) self.largest_acknowledged = value.largest;
91 if (self.largest_acknowledged) |largest| {
92 if (value.largest > largest) self.largest_acknowledged = value.largest;
93 }
94 return result;
95 }
96
97 /// Reports what this space has outstanding, in bytes, so the connection sums it over the three
98 /// spaces and the timer reads it to choose which probe to arm.
99 pub fn bytesInFlight(self: *const Space) u64 {
100 return self.sent.in_flight_bytes;
101 }
102
103 /// Walks this space's outstanding packets once, hands the sink each one that either rule
104 /// reaches, and writes the space's deadline afresh. The connection runs this pass after each
105 /// ACK and again once a deadline passes, so the sink queues the frames of a lost packet. Before
106 /// any acknowledgment has arrived the call removes nothing, because both rules are measured
107 /// against the largest acknowledged number. In that case the call also empties the space's
108 /// deadline.
109 pub fn detectLost(
110 self: *Space,
111 now_ns: u64,
112 delay_ns: u64,
113 sink: anytype,
114 ) quic.connection.Lost {
115 const largest = self.largest_acknowledged orelse {
116 self.loss_deadline_ns = null;
117 return .{};
118 };
119 const result = self.sent.detectLost(largest, now_ns, delay_ns, sink);
120 self.loss_deadline_ns = result.deadline_ns;
121 return result;
122 }
123
124 /// Throws away this space's outstanding packets and both of its timers, so no timer outlives
125 /// the space it belongs to. The call also clears the pending acknowledgment, so nothing is owed
126 /// in a space that can no longer send. The received ranges are left alone, because nothing
127 /// reads them once the keys are gone.
128 pub fn discard(self: *Space) void {
129 self.clearAck();
130 self.sent.clear();
131 self.loss_deadline_ns = null;
132 self.last_ack_eliciting_sent_ns = null;
133 }
134
135 pub fn recordReceived(
136 self: *Space,
137 packet_number: u62,
138 ack_eliciting: bool,
139 now_ns: u64,
140 maximum_delay_ns: u64,
141 ) bool {
142 if (!self.received.insert(packet_number)) return false;
143 if (self.largest_received == null) self.largest_received = packet_number;
144 if (self.largest_received) |largest| {
145 if (packet_number >= largest) {
146 self.largest_received = packet_number;
147 self.largest_received_at_ns = now_ns;
148 }
149 }
150 if (!ack_eliciting) return true;
151 self.ack_pending = true;
152 const delay = if (self.kind == .application) maximum_delay_ns else 0;
153 self.ack_due_at_ns = std.math.add(u64, now_ns, delay) catch std.math.maxInt(u64);
154 return true;
155 }
156
157 pub fn ackDue(self: *const Space, now_ns: u64) bool {
158 if (!self.ack_pending) return false;
159 const due = self.ack_due_at_ns orelse return false;
160 return due <= now_ns;
161 }
162
163 pub fn ackDelay(self: *const Space, now_ns: u64, exponent: u5) u62 {
164 if (now_ns <= self.largest_received_at_ns) return 0;
165 const delay_us = (now_ns - self.largest_received_at_ns) / std.time.ns_per_us;
166 const encoded = delay_us >> exponent;
167 return @intCast(@min(encoded, std.math.maxInt(u62)));
168 }
169
170 pub fn markAckSent(self: *Space) void {
171 std.debug.assert(self.ack_pending);
172 self.ack_pending = false;
173 self.ack_due_at_ns = null;
174 }
175
176 pub fn clearAck(self: *Space) void {
177 self.ack_pending = false;
178 self.ack_due_at_ns = null;
179 }
180 };
181
182 test "RFC 9000 section 17.1 packet number distance permits 2^31 minus one" {
183 var ranges: [1]quic.connection.Range = undefined;
184 var records: [1]quic.connection.SentRecord = undefined;
185 var space = Space.init(.application, &ranges, &records);
186 space.largest_acknowledged = 0;
187 space.next_packet_number = (@as(u62, 1) << 31) - 1;
188 _ = try space.numberEncoding();
189 }
190
191 test "RFC 9000 section 17.1 packet number distance rejects 2^31" {
192 var ranges: [1]quic.connection.Range = undefined;
193 var records: [1]quic.connection.SentRecord = undefined;
194 var space = Space.init(.application, &ranges, &records);
195 space.largest_acknowledged = 0;
196 space.next_packet_number = @as(u62, 1) << 31;
197 try std.testing.expectError(error.PacketNumberDistance, space.numberEncoding());
198 }
199
200 test "RFC 9000 section 12.3 packet number maximum rejects before encoding" {
201 var ranges: [1]quic.connection.Range = undefined;
202 var records: [1]quic.connection.SentRecord = undefined;
203 var space = Space.init(.application, &ranges, &records);
204 space.next_packet_number = std.math.maxInt(u62);
205 try std.testing.expectError(error.PacketNumberExhausted, space.numberEncoding());
206 }