Debian Codegraph @

third_party/rust/neqo-transport/src/recovery/sent.rs

raw
1 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4 // option. This file may not be copied, modified, or distributed
5 // except according to those terms.
6
7 // A collection for sent packets.
8
9 use std::{
10 collections::BTreeMap,
11 ops::RangeInclusive,
12 time::{Duration, Instant},
13 };
14
15 use crate::{
16 packet::{PacketNumber, PacketType},
17 recovery::RecoveryToken,
18 };
19
20 #[derive(Debug, Clone)]
21 pub struct SentPacket {
22 pt: PacketType,
23 pn: PacketNumber,
24 ack_eliciting: bool,
25 time_sent: Instant,
26 primary_path: bool,
27 tokens: Vec<RecoveryToken>,
28
29 time_declared_lost: Option<Instant>,
30 /// After a PTO, this is true when the packet has been released.
31 pto: bool,
32
33 len: usize,
34 }
35
36 impl SentPacket {
37 #[must_use]
38 pub const fn new(
39 pt: PacketType,
40 pn: PacketNumber,
41 time_sent: Instant,
42 ack_eliciting: bool,
43 tokens: Vec<RecoveryToken>,
44 len: usize,
45 ) -> Self {
46 Self {
47 pt,
48 pn,
49 time_sent,
50 ack_eliciting,
51 primary_path: true,
52 tokens,
53 time_declared_lost: None,
54 pto: false,
55 len,
56 }
57 }
58
59 /// The type of this packet.
60 #[must_use]
61 pub const fn packet_type(&self) -> PacketType {
62 self.pt
63 }
64
65 /// The number of the packet.
66 #[must_use]
67 pub const fn pn(&self) -> PacketNumber {
68 self.pn
69 }
70
71 /// The ECN mark of the packet.
72 #[must_use]
73 pub fn ecn_marked_ect0(&self) -> bool {
74 self.tokens
75 .iter()
76 .any(|t| matches!(t, RecoveryToken::EcnEct0))
77 }
78
79 /// The time that this packet was sent.
80 #[must_use]
81 pub const fn time_sent(&self) -> Instant {
82 self.time_sent
83 }
84
85 /// Returns `true` if the packet will elicit an ACK.
86 #[must_use]
87 pub const fn ack_eliciting(&self) -> bool {
88 self.ack_eliciting
89 }
90
91 /// Returns `true` if the packet was sent on the primary path.
92 #[must_use]
93 pub const fn on_primary_path(&self) -> bool {
94 self.primary_path
95 }
96
97 /// The length of the packet that was sent.
98 #[allow(
99 clippy::allow_attributes,
100 clippy::len_without_is_empty,
101 reason = "OK here."
102 )]
103 #[must_use]
104 pub const fn len(&self) -> usize {
105 self.len
106 }
107
108 /// Access the recovery tokens that this holds.
109 #[must_use]
110 pub fn tokens(&self) -> &[RecoveryToken] {
111 &self.tokens
112 }
113
114 /// Clears the flag that had this packet on the primary path.
115 /// Used when migrating to clear out state.
116 pub fn clear_primary_path(&mut self) {
117 self.primary_path = false;
118 }
119
120 /// For Initial packets, it is possible that the packet builder needs to amend the length.
121 pub fn track_padding(&mut self, padding: usize) {
122 debug_assert_eq!(self.pt, PacketType::Initial);
123 self.len += padding;
124 }
125
126 /// Whether the packet has been declared lost.
127 #[must_use]
128 pub const fn lost(&self) -> bool {
129 self.time_declared_lost.is_some()
130 }
131
132 /// Whether accounting for the loss or acknowledgement in the
133 /// congestion controller is pending.
134 /// Returns `true` if the packet counts as being "in flight",
135 /// and has not previously been declared lost.
136 /// Note that this should count packets that contain only ACK and PADDING,
137 /// but we don't send PADDING, so we don't track that.
138 #[must_use]
139 pub const fn cc_outstanding(&self) -> bool {
140 self.ack_eliciting() && self.on_primary_path() && !self.lost()
141 }
142
143 /// Whether the packet should be tracked as in-flight.
144 #[must_use]
145 pub const fn cc_in_flight(&self) -> bool {
146 self.ack_eliciting() && self.on_primary_path()
147 }
148
149 /// Declare the packet as lost. Returns `true` if this is the first time.
150 pub fn declare_lost(&mut self, now: Instant) -> bool {
151 if self.lost() {
152 false
153 } else {
154 self.time_declared_lost = Some(now);
155 true
156 }
157 }
158
159 /// Ask whether this tracked packet has been declared lost for long enough
160 /// that it can be expired and no longer tracked.
161 #[must_use]
162 pub fn expired(&self, now: Instant, expiration_period: Duration) -> bool {
163 self.time_declared_lost
164 .is_some_and(|loss_time| (loss_time + expiration_period) <= now)
165 }
166
167 /// Whether the packet contents were cleared out after a PTO.
168 #[must_use]
169 pub const fn pto_fired(&self) -> bool {
170 self.pto
171 }
172
173 /// On PTO, we need to get the recovery tokens so that we can ensure that
174 /// the frames we sent can be sent again in the PTO packet(s). Do that just once.
175 #[must_use]
176 pub fn pto(&mut self) -> bool {
177 if self.pto || self.lost() {
178 false
179 } else {
180 self.pto = true;
181 true
182 }
183 }
184 }
185
186 /// A collection for packets that we have sent that haven't been acknowledged.
187 #[derive(Debug, Default)]
188 pub struct SentPackets {
189 /// The collection.
190 packets: BTreeMap<u64, SentPacket>,
191 }
192
193 impl SentPackets {
194 #[allow(
195 clippy::allow_attributes,
196 clippy::len_without_is_empty,
197 reason = "OK here."
198 )]
199 #[must_use]
200 pub fn len(&self) -> usize {
201 self.packets.len()
202 }
203
204 pub fn track(&mut self, packet: SentPacket) {
205 self.packets.insert(packet.pn, packet);
206 }
207
208 pub fn iter_mut(&mut self) -> impl Iterator<Item = &mut SentPacket> {
209 self.packets.values_mut()
210 }
211
212 /// Take values from specified ranges of packet numbers.
213 /// The values returned will be reversed, so that the most recent packet appears first.
214 /// This is because ACK frames arrive with ranges starting from the largest acknowledged
215 /// and we want to match that.
216 pub fn take_ranges<R>(&mut self, acked_ranges: R) -> Vec<SentPacket>
217 where
218 R: IntoIterator<Item = RangeInclusive<PacketNumber>>,
219 R::IntoIter: ExactSizeIterator,
220 {
221 let mut result = Vec::new();
222
223 // Start with all packets. We will add unacknowledged packets back.
224 // [---------------------------packets----------------------------]
225 let mut packets = std::mem::take(&mut self.packets);
226
227 let mut previous_range_start: Option<PacketNumber> = None;
228
229 for range in acked_ranges {
230 // Split off at the end of the acked range.
231 //
232 // [---------packets--------][----------after_acked_range---------]
233 let after_acked_range = packets.split_off(&(*range.end() + 1));
234
235 // Split off at the start of the acked range.
236 //
237 // [-packets-][-acked_range-][----------after_acked_range---------]
238 let acked_range = packets.split_off(range.start());
239
240 // According to RFC 9000 19.3.1 ACK ranges are in descending order:
241 //
242 // > Each ACK Range consists of alternating Gap and ACK Range Length
243 // > values in **descending packet number order**.
244 //
245 // <https://www.rfc-editor.org/rfc/rfc9000.html#section-19.3.1>
246 debug_assert!(previous_range_start.is_none_or(|s| s > *range.end()));
247 previous_range_start = Some(*range.start());
248
249 // Thus none of the following ACK ranges will acknowledge packets in
250 // `after_acked_range`. Let's put those back early.
251 //
252 // [-packets-][-acked_range-][------------self.packets------------]
253 if self.packets.is_empty() {
254 // Don't re-insert un-acked packets into empty collection, but
255 // instead replace the empty one entirely.
256 self.packets = after_acked_range;
257 } else {
258 // Need to extend existing one. Not the first iteration, thus
259 // `after_acked_range` should be small.
260 self.packets.extend(after_acked_range);
261 }
262
263 // Take the acked packets.
264 result.extend(acked_range.into_values().rev());
265 }
266
267 // Put remaining non-acked packets back.
268 //
269 // This is inefficient if the acknowledged packets include the last sent
270 // packet AND there is a large unacknowledged span of packets. That's
271 // rare enough that we won't do anything special for that case.
272 self.packets.extend(packets);
273
274 result
275 }
276
277 /// Empty out the packets, but keep the offset.
278 pub fn drain_all(&mut self) -> impl Iterator<Item = SentPacket> {
279 std::mem::take(&mut self.packets).into_values()
280 }
281
282 /// See `LossRecoverySpace::remove_old_lost` for details on `now` and `cd`.
283 /// Returns the number of ack-eliciting packets removed.
284 pub fn remove_expired(&mut self, now: Instant, cd: Duration) -> usize {
285 let mut it = self.packets.iter();
286 // If the first item is not expired, do nothing (the most common case).
287 if it.next().is_some_and(|(_, p)| p.expired(now, cd)) {
288 // Find the index of the first unexpired packet.
289 let to_remove = if let Some(first_keep) =
290 it.find_map(|(i, p)| if p.expired(now, cd) { None } else { Some(*i) })
291 {
292 // Some packets haven't expired, so keep those.
293 let keep = self.packets.split_off(&first_keep);
294 std::mem::replace(&mut self.packets, keep)
295 } else {
296 // All packets are expired.
297 std::mem::take(&mut self.packets)
298 };
299 to_remove
300 .into_values()
301 .filter(SentPacket::ack_eliciting)
302 .count()
303 } else {
304 0
305 }
306 }
307 }
308
309 #[cfg(test)]
310 mod tests {
311 use std::{
312 cell::OnceCell,
313 time::{Duration, Instant},
314 };
315
316 use super::{SentPacket, SentPackets};
317 use crate::packet::{PacketNumber, PacketType};
318
319 const PACKET_GAP: Duration = Duration::from_secs(1);
320 fn start_time() -> Instant {
321 thread_local!(static STARTING_TIME: OnceCell<Instant> = const { OnceCell::new() });
322 STARTING_TIME.with(|t| *t.get_or_init(Instant::now))
323 }
324
325 fn pkt(n: u32) -> SentPacket {
326 SentPacket::new(
327 PacketType::Short,
328 PacketNumber::from(n),
329 start_time() + (PACKET_GAP * n),
330 true,
331 Vec::new(),
332 100,
333 )
334 }
335
336 fn pkts() -> SentPackets {
337 let mut pkts = SentPackets::default();
338 pkts.track(pkt(0));
339 pkts.track(pkt(1));
340 pkts.track(pkt(2));
341 assert_eq!(pkts.len(), 3);
342 pkts
343 }
344
345 trait HasPacketNumber {
346 fn pn(&self) -> PacketNumber;
347 }
348 impl HasPacketNumber for SentPacket {
349 fn pn(&self) -> PacketNumber {
350 self.pn
351 }
352 }
353 impl HasPacketNumber for &'_ SentPacket {
354 fn pn(&self) -> PacketNumber {
355 self.pn
356 }
357 }
358 impl HasPacketNumber for &'_ mut SentPacket {
359 fn pn(&self) -> PacketNumber {
360 self.pn
361 }
362 }
363
364 fn remove_one(pkts: &mut SentPackets, idx: PacketNumber) {
365 assert_eq!(pkts.len(), 3);
366 let store = pkts.take_ranges([idx..=idx]);
367 let mut it = store.into_iter();
368 assert_eq!(idx, it.next().unwrap().pn());
369 assert!(it.next().is_none());
370 drop(it);
371 assert_eq!(pkts.len(), 2);
372 }
373
374 fn assert_zero_and_two<'a, 'b: 'a>(
375 mut it: impl Iterator<Item = impl HasPacketNumber + 'b> + 'a,
376 ) {
377 assert_eq!(it.next().unwrap().pn(), 0);
378 assert_eq!(it.next().unwrap().pn(), 2);
379 assert!(it.next().is_none());
380 }
381
382 #[test]
383 fn iterate_skipped() {
384 let mut pkts = pkts();
385 for (i, p) in pkts.packets.values().enumerate() {
386 assert_eq!(i, usize::try_from(p.pn).unwrap());
387 }
388 remove_one(&mut pkts, 1);
389
390 // Validate the merged result multiple ways.
391 assert_zero_and_two(pkts.iter_mut());
392
393 {
394 // Reverse the expectations here as this iterator reverses its output.
395 let store = pkts.take_ranges([0..=2]);
396 let mut it = store.into_iter();
397 assert_eq!(it.next().unwrap().pn(), 2);
398 assert_eq!(it.next().unwrap().pn(), 0);
399 assert!(it.next().is_none());
400 };
401
402 // The None values are still there in this case, so offset is 0.
403 assert_eq!(pkts.packets.len(), 0);
404 assert_eq!(pkts.len(), 0);
405 }
406
407 #[test]
408 fn drain() {
409 let mut pkts = pkts();
410 remove_one(&mut pkts, 1);
411
412 assert_zero_and_two(pkts.drain_all());
413 assert_eq!(pkts.len(), 0);
414 }
415
416 #[test]
417 fn remove_expired() {
418 let mut pkts = pkts();
419 remove_one(&mut pkts, 0);
420
421 for p in pkts.iter_mut() {
422 p.declare_lost(p.time_sent); // just to keep things simple.
423 }
424
425 // Expire up to pkt(1).
426 let count = pkts.remove_expired(start_time() + PACKET_GAP, Duration::new(0, 0));
427 assert_eq!(count, 1);
428 assert_eq!(pkts.len(), 1);
429 }
430
431 #[test]
432 fn first_skipped_ok() {
433 let mut pkts = SentPackets::default();
434 pkts.track(pkt(4)); // This is fine.
435 assert_eq!(pkts.len(), 1);
436 }
437
438 #[test]
439 fn ignore_unknown() {
440 let mut pkts = SentPackets::default();
441 pkts.track(pkt(0));
442 assert!(pkts.take_ranges([1..=1]).is_empty());
443 }
444 }