Debian Codegraph @

third_party/rust/neqo-transport/src/send_stream.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 // Buffering data to send until it is acked.
8
9 #![allow(
10 clippy::module_name_repetitions,
11 reason = "<https://github.com/mozilla/neqo/issues/2284#issuecomment-2782711813>"
12 )]
13
14 use std::{
15 cell::RefCell,
16 cmp::{max, min, Ordering},
17 collections::{btree_map::Entry, BTreeMap, VecDeque},
18 fmt::{self, Display, Formatter},
19 mem,
20 num::NonZeroUsize,
21 ops::Add,
22 rc::Rc,
23 };
24
25 use indexmap::IndexMap;
26 use neqo_common::{qdebug, qerror, qtrace, Encoder, Role};
27 use smallvec::SmallVec;
28
29 use crate::{
30 events::ConnectionEvents,
31 fc::SenderFlowControl,
32 frame::{Frame, FrameType},
33 packet::PacketBuilder,
34 recovery::{RecoveryToken, StreamRecoveryToken},
35 stats::FrameStats,
36 stream_id::StreamId,
37 streams::SendOrder,
38 tparams::{
39 TransportParameterId::{InitialMaxStreamDataBidiRemote, InitialMaxStreamDataUni},
40 TransportParameters,
41 },
42 AppError, Error, Res,
43 };
44
45 /// The maximum stream send buffer size.
46 ///
47 /// See [`crate::recv_stream::MAX_RECV_WINDOW_SIZE`] for an explanation of this
48 /// concrete value.
49 ///
50 /// Keep in sync with [`crate::recv_stream::MAX_RECV_WINDOW_SIZE`].
51 pub const MAX_SEND_BUFFER_SIZE: usize = 10 * 1024 * 1024;
52
53 /// The priority that is assigned to sending data for the stream.
54 #[derive(Debug, Clone, Copy, PartialEq, Eq, Default, PartialOrd, Ord)]
55 pub enum TransmissionPriority {
56 /// This stream is more important than the functioning of the connection.
57 /// Don't use this priority unless the stream really is that important.
58 /// A stream at this priority can starve out other connection functions,
59 /// including flow control, which could be very bad.
60 Critical,
61 /// The stream is very important. Stream data will be written ahead of
62 /// some of the less critical connection functions, like path validation,
63 /// connection ID management, and session tickets.
64 Important,
65 /// High priority streams are important, but not enough to disrupt
66 /// connection operation. They go ahead of session tickets though.
67 High,
68 /// The default priority.
69 #[default]
70 Normal,
71 /// Low priority streams get sent last.
72 Low,
73 }
74
75 impl Add<RetransmissionPriority> for TransmissionPriority {
76 type Output = Self;
77 fn add(self, rhs: RetransmissionPriority) -> Self::Output {
78 match rhs {
79 RetransmissionPriority::Fixed(fixed) => fixed,
80 RetransmissionPriority::Same => self,
81 RetransmissionPriority::Higher => match self {
82 Self::Critical => Self::Critical,
83 Self::Important | Self::High => Self::Important,
84 Self::Normal => Self::High,
85 Self::Low => Self::Normal,
86 },
87 RetransmissionPriority::MuchHigher => match self {
88 Self::Critical | Self::Important => Self::Critical,
89 Self::High | Self::Normal => Self::Important,
90 Self::Low => Self::High,
91 },
92 }
93 }
94 }
95
96 /// If data is lost, this determines the priority that applies to retransmissions
97 /// of that data.
98 #[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
99 pub enum RetransmissionPriority {
100 /// Prioritize retransmission at a fixed priority.
101 /// With this, it is possible to prioritize retransmissions lower than transmissions.
102 /// Doing that can create a deadlock with flow control which might cause the connection
103 /// to stall unless new data stops arriving fast enough that retransmissions can complete.
104 Fixed(TransmissionPriority),
105 /// Don't increase priority for retransmission. This is probably not a good idea
106 /// as it could mean starving flow control.
107 Same,
108 /// Increase the priority of retransmissions (the default).
109 /// Retransmissions of `Critical` or `Important` aren't elevated at all.
110 #[default]
111 Higher,
112 /// Increase the priority of retransmissions a lot.
113 /// This is useful for streams that are particularly exposed to head-of-line blocking.
114 MuchHigher,
115 }
116
117 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
118 enum RangeState {
119 Sent,
120 Acked,
121 }
122
123 /// Track ranges in the stream as sent or acked. Acked implies sent. Not in a
124 /// range implies needing-to-be-sent, either initially or as a retransmission.
125 #[derive(Debug, Default, PartialEq, Eq)]
126 pub struct RangeTracker {
127 /// The number of bytes that have been acknowledged starting from offset 0.
128 acked: u64,
129 /// A map that tracks the state of ranges.
130 /// Keys are the offset of the start of the range.
131 /// Values is a tuple of the range length and its state.
132 used: BTreeMap<u64, (u64, RangeState)>,
133 /// This is a cache for the output of `first_unmarked_range`, which we check a lot.
134 first_unmarked: Option<(u64, Option<u64>)>,
135 }
136
137 impl RangeTracker {
138 fn highest_offset(&self) -> u64 {
139 self.used
140 .last_key_value()
141 .map_or(self.acked, |(&k, &(v, _))| k + v)
142 }
143
144 const fn acked_from_zero(&self) -> u64 {
145 self.acked
146 }
147
148 /// Find the first unmarked range. If all are contiguous, this will return
149 /// (`highest_offset()`, None).
150 fn first_unmarked_range(&mut self) -> (u64, Option<u64>) {
151 if let Some(first_unmarked) = self.first_unmarked {
152 return first_unmarked;
153 }
154
155 let mut prev_end = self.acked;
156
157 for (&cur_off, &(cur_len, _)) in &self.used {
158 if prev_end == cur_off {
159 prev_end = cur_off + cur_len;
160 } else {
161 let res = (prev_end, Some(cur_off - prev_end));
162 self.first_unmarked = Some(res);
163 return res;
164 }
165 }
166 self.first_unmarked = Some((prev_end, None));
167 (prev_end, None)
168 }
169
170 /// When the range of acknowledged bytes from zero increases, we need to drop any
171 /// ranges within that span AND maybe extend it to include any adjacent acknowledged ranges.
172 fn coalesce_acked(&mut self) {
173 while let Some(e) = self.used.first_entry() {
174 match self.acked.cmp(e.key()) {
175 Ordering::Greater => {
176 let (off, (len, state)) = e.remove_entry();
177 let overflow = (off + len).saturating_sub(self.acked);
178 if overflow > 0 {
179 if state == RangeState::Acked {
180 self.acked += overflow;
181 } else {
182 self.used.insert(self.acked, (overflow, state));
183 }
184 break;
185 }
186 }
187 Ordering::Equal => {
188 if e.get().1 == RangeState::Acked {
189 let (len, _) = e.remove();
190 self.acked += len;
191 }
192 break;
193 }
194 Ordering::Less => break,
195 }
196 }
197 }
198
199 /// Mark a range as acknowledged. This is simpler than marking a range as sent
200 /// because an acknowledged range can never turn back into a sent range, so
201 /// this function can just override the entire range.
202 ///
203 /// The only tricky parts are making sure that we maintain `self.acked`,
204 /// which is the first acknowledged range. And making sure that we don't create
205 /// ranges of the same type that are adjacent; these need to be merged.
206 #[allow(
207 clippy::allow_attributes,
208 clippy::missing_panics_doc,
209 reason = "OK here."
210 )]
211 pub fn mark_acked(&mut self, new_off: u64, new_len: usize) {
212 let end = new_off + u64::try_from(new_len).expect("usize fits in u64");
213 let new_off = max(self.acked, new_off);
214 let mut new_len = end.saturating_sub(new_off);
215 if new_len == 0 {
216 return;
217 }
218
219 self.first_unmarked = None;
220 if new_off == self.acked {
221 self.acked += new_len;
222 self.coalesce_acked();
223 return;
224 }
225 let mut new_end = new_off + new_len;
226
227 // Get all existing ranges that start within this new range.
228 let mut covered = self
229 .used
230 .range(new_off..new_end)
231 .map(|(&k, _)| k)
232 .collect::<SmallVec<[_; 8]>>();
233
234 if let Entry::Occupied(next_entry) = self.used.entry(new_end) {
235 // Check if the very next entry is the same type as this.
236 if next_entry.get().1 == RangeState::Acked {
237 // If is is acked, drop it and extend this new range.
238 let (extra_len, _) = next_entry.remove();
239 new_len += extra_len;
240 new_end += extra_len;
241 }
242 } else if let Some(last) = covered.pop() {
243 // Otherwise, the last of the existing ranges might overhang this one by some.
244 let (old_off, (old_len, old_state)) =
245 self.used.remove_entry(&last).expect("entry exists"); // can't fail
246 let remainder = (old_off + old_len).saturating_sub(new_end);
247 if remainder > 0 {
248 if old_state == RangeState::Acked {
249 // Just extend the current range.
250 new_len += remainder;
251 new_end += remainder;
252 } else {
253 self.used.insert(new_end, (remainder, RangeState::Sent));
254 }
255 }
256 }
257 // All covered ranges can just be trashed.
258 for k in covered {
259 self.used.remove(&k);
260 }
261
262 // Now either merge with a preceding acked range
263 // or cut a preceding sent range as needed.
264 let prev = self.used.range_mut(..new_off).next_back();
265 if let Some((prev_off, (prev_len, prev_state))) = prev {
266 let prev_end = *prev_off + *prev_len;
267 if prev_end >= new_off {
268 if *prev_state == RangeState::Sent {
269 *prev_len = new_off - *prev_off;
270 if prev_end > new_end {
271 // There is some extra sent range after the new acked range.
272 self.used
273 .insert(new_end, (prev_end - new_end, RangeState::Sent));
274 }
275 } else {
276 *prev_len = max(prev_end, new_end) - *prev_off;
277 return;
278 }
279 }
280 }
281 self.used.insert(new_off, (new_len, RangeState::Acked));
282 }
283
284 /// Turn a single sent range into a list of subranges that align with existing
285 /// acknowledged ranges.
286 ///
287 /// This is more complicated than adding acked ranges because any acked ranges
288 /// need to be kept in place, with sent ranges filling the gaps.
289 ///
290 /// This means:
291 /// ```ignore
292 /// AAA S AAAS AAAAA
293 /// + SSSSSSSSSSSSS
294 /// = AAASSSAAASSAAAAA
295 /// ```
296 ///
297 /// But we also have to ensure that:
298 /// ```ignore
299 /// SSSS
300 /// + SS
301 /// = SSSSSS
302 /// ```
303 /// and
304 /// ```ignore
305 /// SSSSS
306 /// + SS
307 /// = SSSSSS
308 /// ```
309 #[allow(
310 clippy::allow_attributes,
311 clippy::missing_panics_doc,
312 reason = "OK here."
313 )]
314 pub fn mark_sent(&mut self, mut new_off: u64, new_len: usize) {
315 let new_end = new_off + u64::try_from(new_len).expect("usize fits in u64");
316 new_off = max(self.acked, new_off);
317 let mut new_len = new_end.saturating_sub(new_off);
318 if new_len == 0 {
319 return;
320 }
321
322 self.first_unmarked = None;
323
324 // Get all existing ranges that start within this new range.
325 let covered = self
326 .used
327 .range(new_off..(new_off + new_len))
328 .map(|(&k, _)| k)
329 .collect::<SmallVec<[u64; 8]>>();
330
331 if let Entry::Occupied(next_entry) = self.used.entry(new_end) {
332 if next_entry.get().1 == RangeState::Sent {
333 // Check if the very next entry is the same type as this, so it can be merged.
334 let (extra_len, _) = next_entry.remove();
335 new_len += extra_len;
336 }
337 }
338
339 // Merge with any preceding sent range that might overlap,
340 // or cut the head of this if the preceding range is acked.
341 let prev = self.used.range(..new_off).next_back();
342 if let Some((&prev_off, &(prev_len, prev_state))) = prev {
343 if prev_off + prev_len >= new_off {
344 let overlap = prev_off + prev_len - new_off;
345 new_len = new_len.saturating_sub(overlap);
346 if new_len == 0 {
347 // The previous range completely covers this one (no more to do).
348 return;
349 }
350
351 if prev_state == RangeState::Acked {
352 // The previous range is acked, so it cuts this one.
353 new_off += overlap;
354 } else {
355 // Extend the current range backwards.
356 new_off = prev_off;
357 new_len += prev_len;
358 // The previous range will be updated below.
359 // It might need to be cut because of a covered acked range.
360 }
361 }
362 }
363
364 // Now interleave new sent chunks with any existing acked chunks.
365 for old_off in covered {
366 let Entry::Occupied(e) = self.used.entry(old_off) else {
367 unreachable!();
368 };
369 let &(old_len, old_state) = e.get();
370 if old_state == RangeState::Acked {
371 // Now we have to insert a chunk ahead of this acked chunk.
372 let chunk_len = old_off - new_off;
373 if chunk_len > 0 {
374 self.used.insert(new_off, (chunk_len, RangeState::Sent));
375 }
376 let included = chunk_len + old_len;
377 new_len = new_len.saturating_sub(included);
378 if new_len == 0 {
379 return;
380 }
381 new_off += included;
382 } else {
383 let overhang = (old_off + old_len).saturating_sub(new_off + new_len);
384 new_len += overhang;
385 if *e.key() != new_off {
386 // Retain a sent entry at `new_off`.
387 // This avoids the work of removing and re-creating an entry.
388 // The value will be overwritten when the next insert occurs,
389 // either when this loop hits an acked range (above)
390 // or for any remainder (below).
391 e.remove();
392 }
393 }
394 }
395
396 self.used.insert(new_off, (new_len, RangeState::Sent));
397 }
398
399 fn unmark_range(&mut self, off: u64, len: usize) {
400 if len == 0 {
401 qdebug!("unmark 0-length range at {off}");
402 return;
403 }
404
405 self.first_unmarked = None;
406 let len = u64::try_from(len).expect("usize fits in u64");
407 let end_off = off + len;
408
409 let mut to_remove = SmallVec::<[_; 8]>::new();
410 let mut to_add = None;
411
412 // Walk backwards through possibly affected existing ranges
413 for (cur_off, (cur_len, cur_state)) in self.used.range_mut(..off + len).rev() {
414 // Maybe fixup range preceding the removed range
415 if *cur_off < off {
416 // Check for overlap
417 if *cur_off + *cur_len > off {
418 if *cur_state == RangeState::Acked {
419 qdebug!(
420 "Attempted to unmark Acked range {cur_off}-{cur_len} with unmark_range {off}-{}",
421 off + len
422 );
423 } else {
424 *cur_len = off - cur_off;
425 }
426 }
427 break;
428 }
429
430 if *cur_state == RangeState::Acked {
431 qdebug!(
432 "Attempted to unmark Acked range {cur_off}-{cur_len} with unmark_range {off}-{}",
433 off + len
434 );
435 continue;
436 }
437
438 // Add a new range for old subrange extending beyond
439 // to-be-unmarked range
440 let cur_end_off = cur_off + *cur_len;
441 if cur_end_off > end_off {
442 let new_cur_off = off + len;
443 let new_cur_len = cur_end_off - end_off;
444 assert_eq!(to_add, None);
445 to_add = Some((new_cur_off, new_cur_len, *cur_state));
446 }
447
448 to_remove.push(*cur_off);
449 }
450
451 for remove_off in to_remove {
452 self.used.remove(&remove_off);
453 }
454
455 if let Some((new_cur_off, new_cur_len, cur_state)) = to_add {
456 self.used.insert(new_cur_off, (new_cur_len, cur_state));
457 }
458 }
459
460 /// Unmark all sent ranges.
461 /// # Panics
462 /// On 32-bit machines where far too much is sent before calling this.
463 /// Note that this should not be called for handshakes, which should never exceed that limit.
464 pub fn unmark_sent(&mut self) {
465 self.unmark_range(
466 0,
467 usize::try_from(self.highest_offset()).expect("u64 fits in usize"),
468 );
469 }
470 }
471
472 /// Buffer to contain queued bytes and track their state.
473 #[derive(Debug, Default, PartialEq, Eq)]
474 pub struct TxBuffer {
475 send_buf: VecDeque<u8>, // buffer of not-acked bytes
476 ranges: RangeTracker, // ranges in buffer that have been sent or acked
477 }
478
479 impl TxBuffer {
480 #[must_use]
481 pub fn new() -> Self {
482 Self::default()
483 }
484
485 /// Attempt to add some or all of the passed-in buffer to the `TxBuffer`.
486 pub fn send(&mut self, buf: &[u8]) -> usize {
487 let can_buffer = min(MAX_SEND_BUFFER_SIZE - self.buffered(), buf.len());
488 if can_buffer > 0 {
489 self.send_buf.extend(&buf[..can_buffer]);
490 debug_assert!(self.send_buf.len() <= MAX_SEND_BUFFER_SIZE);
491 }
492 can_buffer
493 }
494
495 fn first_unmarked_range(&mut self) -> Option<(u64, Option<u64>)> {
496 let (start, maybe_len) = self.ranges.first_unmarked_range();
497 let buffered = u64::try_from(self.buffered()).ok()?;
498 (start != self.retired() + buffered).then_some((start, maybe_len))
499 }
500
501 pub fn is_empty(&mut self) -> bool {
502 self.first_unmarked_range().is_none()
503 }
504
505 pub fn next_bytes(&mut self) -> Option<(u64, &[u8])> {
506 let (start, maybe_len) = self.first_unmarked_range()?;
507
508 // Convert from ranges-relative-to-zero to
509 // ranges-relative-to-buffer-start
510 let buff_off = usize::try_from(start - self.retired()).ok()?;
511
512 // Deque returns two slices. Create a subslice from whichever
513 // one contains the first unmarked data.
514 let slc = if buff_off < self.send_buf.as_slices().0.len() {
515 &self.send_buf.as_slices().0[buff_off..]
516 } else {
517 &self.send_buf.as_slices().1[buff_off - self.send_buf.as_slices().0.len()..]
518 };
519
520 let len = maybe_len.map_or(slc.len(), |range_len| {
521 min(usize::try_from(range_len).unwrap_or(usize::MAX), slc.len())
522 });
523
524 debug_assert!(len > 0);
525 debug_assert!(len <= slc.len());
526
527 Some((start, &slc[..len]))
528 }
529
530 pub fn mark_as_sent(&mut self, offset: u64, len: usize) {
531 self.ranges.mark_sent(offset, len);
532 }
533
534 #[allow(
535 clippy::allow_attributes,
536 clippy::missing_panics_doc,
537 reason = "OK here."
538 )]
539 pub fn mark_as_acked(&mut self, offset: u64, len: usize) {
540 let prev_retired = self.retired();
541 self.ranges.mark_acked(offset, len);
542
543 // Any newly-retired bytes can be dropped from the buffer.
544 let new_retirable = self.retired() - prev_retired;
545 debug_assert!(new_retirable <= self.buffered() as u64);
546 let keep = self.buffered() - usize::try_from(new_retirable).expect("u64 fits in usize");
547
548 // Truncate front
549 self.send_buf.rotate_left(self.buffered() - keep);
550 self.send_buf.truncate(keep);
551 }
552
553 pub fn mark_as_lost(&mut self, offset: u64, len: usize) {
554 self.ranges.unmark_range(offset, len);
555 }
556
557 /// Forget about anything that was marked as sent.
558 pub fn unmark_sent(&mut self) {
559 self.ranges.unmark_sent();
560 }
561
562 #[must_use]
563 pub const fn retired(&self) -> u64 {
564 self.ranges.acked_from_zero()
565 }
566
567 fn buffered(&self) -> usize {
568 self.send_buf.len()
569 }
570
571 fn avail(&self) -> usize {
572 MAX_SEND_BUFFER_SIZE - self.buffered()
573 }
574
575 fn used(&self) -> u64 {
576 self.retired() + u64::try_from(self.buffered()).expect("usize fits in u64")
577 }
578 }
579
580 /// QUIC sending stream states, based on -transport 3.1.
581 #[derive(Debug)]
582 pub enum SendStreamState {
583 Ready {
584 fc: SenderFlowControl<StreamId>,
585 conn_fc: Rc<RefCell<SenderFlowControl<()>>>,
586 },
587 Send {
588 fc: SenderFlowControl<StreamId>,
589 conn_fc: Rc<RefCell<SenderFlowControl<()>>>,
590 send_buf: TxBuffer,
591 },
592 // Note: `DataSent` is entered when the stream is closed, not when all data has been
593 // sent for the first time.
594 DataSent {
595 send_buf: TxBuffer,
596 fin_sent: bool,
597 fin_acked: bool,
598 },
599 DataRecvd {
600 retired: u64,
601 written: u64,
602 },
603 ResetSent {
604 err: AppError,
605 final_size: u64,
606 priority: Option<TransmissionPriority>,
607 final_retired: u64,
608 final_written: u64,
609 },
610 ResetRecvd {
611 final_retired: u64,
612 final_written: u64,
613 },
614 }
615
616 impl SendStreamState {
617 fn tx_buf_mut(&mut self) -> Option<&mut TxBuffer> {
618 match self {
619 Self::Send { send_buf, .. } | Self::DataSent { send_buf, .. } => Some(send_buf),
620 Self::Ready { .. }
621 | Self::DataRecvd { .. }
622 | Self::ResetSent { .. }
623 | Self::ResetRecvd { .. } => None,
624 }
625 }
626
627 fn tx_avail(&self) -> usize {
628 match self {
629 // In Ready, TxBuffer not yet allocated but size is known
630 Self::Ready { .. } => MAX_SEND_BUFFER_SIZE,
631 Self::Send { send_buf, .. } | Self::DataSent { send_buf, .. } => send_buf.avail(),
632 Self::DataRecvd { .. } | Self::ResetSent { .. } | Self::ResetRecvd { .. } => 0,
633 }
634 }
635
636 fn transition(&mut self, new_state: Self) {
637 qtrace!("SendStream state {:?} -> {:?}", self, new_state);
638 *self = new_state;
639 }
640 }
641
642 // See https://www.w3.org/TR/webtransport/#send-stream-stats.
643 #[derive(Debug, Clone, Copy)]
644 pub struct SendStreamStats {
645 // The total number of bytes the consumer has successfully written to
646 // this stream. This number can only increase.
647 pub bytes_written: u64,
648 // An indicator of progress on how many of the consumer bytes written to
649 // this stream has been sent at least once. This number can only increase,
650 // and is always less than or equal to bytes_written.
651 pub bytes_sent: u64,
652 // An indicator of progress on how many of the consumer bytes written to
653 // this stream have been sent and acknowledged as received by the server
654 // using QUIC’s ACK mechanism. Only sequential bytes up to,
655 // but not including, the first non-acknowledged byte, are counted.
656 // This number can only increase and is always less than or equal to
657 // bytes_sent.
658 pub bytes_acked: u64,
659 }
660
661 impl SendStreamStats {
662 #[must_use]
663 pub const fn new(bytes_written: u64, bytes_sent: u64, bytes_acked: u64) -> Self {
664 Self {
665 bytes_written,
666 bytes_sent,
667 bytes_acked,
668 }
669 }
670
671 #[must_use]
672 pub const fn bytes_written(&self) -> u64 {
673 self.bytes_written
674 }
675
676 #[must_use]
677 pub const fn bytes_sent(&self) -> u64 {
678 self.bytes_sent
679 }
680
681 #[must_use]
682 pub const fn bytes_acked(&self) -> u64 {
683 self.bytes_acked
684 }
685 }
686
687 /// Implement a QUIC send stream.
688 #[derive(Debug)]
689 pub struct SendStream {
690 stream_id: StreamId,
691 state: SendStreamState,
692 conn_events: ConnectionEvents,
693 priority: TransmissionPriority,
694 retransmission_priority: RetransmissionPriority,
695 retransmission_offset: u64,
696 sendorder: Option<SendOrder>,
697 bytes_sent: u64,
698 fair: bool,
699 writable_event_low_watermark: NonZeroUsize,
700 }
701
702 impl SendStream {
703 pub fn new(
704 stream_id: StreamId,
705 max_stream_data: u64,
706 conn_fc: Rc<RefCell<SenderFlowControl<()>>>,
707 conn_events: ConnectionEvents,
708 ) -> Self {
709 let ss = Self {
710 stream_id,
711 state: SendStreamState::Ready {
712 fc: SenderFlowControl::new(stream_id, max_stream_data),
713 conn_fc,
714 },
715 conn_events,
716 priority: TransmissionPriority::default(),
717 retransmission_priority: RetransmissionPriority::default(),
718 retransmission_offset: 0,
719 sendorder: None,
720 bytes_sent: 0,
721 fair: false,
722 writable_event_low_watermark: NonZeroUsize::MIN,
723 };
724 if ss.avail() > 0 {
725 ss.conn_events.send_stream_writable(stream_id);
726 }
727 ss
728 }
729
730 pub fn write_frames(
731 &mut self,
732 priority: TransmissionPriority,
733 builder: &mut PacketBuilder,
734 tokens: &mut Vec<RecoveryToken>,
735 stats: &mut FrameStats,
736 ) {
737 qtrace!("write STREAM frames at priority {priority:?}");
738 if !self.write_reset_frame(priority, builder, tokens, stats) {
739 self.write_blocked_frame(priority, builder, tokens, stats);
740 self.write_stream_frame(priority, builder, tokens, stats);
741 }
742 }
743
744 // return false if the builder is full and the caller should stop iterating
745 pub fn write_frames_with_early_return(
746 &mut self,
747 priority: TransmissionPriority,
748 builder: &mut PacketBuilder,
749 tokens: &mut Vec<RecoveryToken>,
750 stats: &mut FrameStats,
751 ) -> bool {
752 if !self.write_reset_frame(priority, builder, tokens, stats) {
753 self.write_blocked_frame(priority, builder, tokens, stats);
754 if builder.is_full() {
755 return false;
756 }
757 self.write_stream_frame(priority, builder, tokens, stats);
758 if builder.is_full() {
759 return false;
760 }
761 }
762 true
763 }
764
765 pub fn set_fairness(&mut self, make_fair: bool) {
766 self.fair = make_fair;
767 }
768
769 #[must_use]
770 pub const fn is_fair(&self) -> bool {
771 self.fair
772 }
773
774 pub fn set_priority(
775 &mut self,
776 transmission: TransmissionPriority,
777 retransmission: RetransmissionPriority,
778 ) {
779 self.priority = transmission;
780 self.retransmission_priority = retransmission;
781 }
782
783 #[must_use]
784 pub const fn sendorder(&self) -> Option<SendOrder> {
785 self.sendorder
786 }
787
788 pub fn set_sendorder(&mut self, sendorder: Option<SendOrder>) {
789 self.sendorder = sendorder;
790 }
791
792 /// If all data has been buffered or written, how much was sent.
793 #[must_use]
794 pub fn final_size(&self) -> Option<u64> {
795 match &self.state {
796 SendStreamState::DataSent { send_buf, .. } => Some(send_buf.used()),
797 SendStreamState::ResetSent { final_size, .. } => Some(*final_size),
798 _ => None,
799 }
800 }
801
802 #[must_use]
803 pub fn stats(&self) -> SendStreamStats {
804 SendStreamStats::new(self.bytes_written(), self.bytes_sent, self.bytes_acked())
805 }
806
807 #[must_use]
808 #[allow(
809 clippy::allow_attributes,
810 clippy::missing_panics_doc,
811 reason = "OK here."
812 )]
813 pub fn bytes_written(&self) -> u64 {
814 match &self.state {
815 SendStreamState::Send { send_buf, .. } | SendStreamState::DataSent { send_buf, .. } => {
816 send_buf.retired() + u64::try_from(send_buf.buffered()).expect("usize fits in u64")
817 }
818 SendStreamState::DataRecvd {
819 retired, written, ..
820 } => *retired + *written,
821 SendStreamState::ResetSent {
822 final_retired,
823 final_written,
824 ..
825 }
826 | SendStreamState::ResetRecvd {
827 final_retired,
828 final_written,
829 ..
830 } => *final_retired + *final_written,
831 SendStreamState::Ready { .. } => 0,
832 }
833 }
834
835 #[must_use]
836 pub const fn bytes_acked(&self) -> u64 {
837 match &self.state {
838 SendStreamState::Send { send_buf, .. } | SendStreamState::DataSent { send_buf, .. } => {
839 send_buf.retired()
840 }
841 SendStreamState::DataRecvd { retired, .. } => *retired,
842 SendStreamState::ResetSent { final_retired, .. }
843 | SendStreamState::ResetRecvd { final_retired, .. } => *final_retired,
844 SendStreamState::Ready { .. } => 0,
845 }
846 }
847
848 /// Return the next range to be sent, if any.
849 /// If this is a retransmission, cut off what is sent at the retransmission
850 /// offset.
851 fn next_bytes(&mut self, retransmission_only: bool) -> Option<(u64, &[u8])> {
852 match self.state {
853 SendStreamState::Send {
854 ref mut send_buf, ..
855 } => {
856 let (offset, slice) = send_buf.next_bytes()?;
857 if retransmission_only {
858 qtrace!(
859 "next_bytes apply retransmission limit at {}",
860 self.retransmission_offset
861 );
862 (self.retransmission_offset > offset).then(|| {
863 let Ok(delta) = usize::try_from(self.retransmission_offset - offset) else {
864 return None;
865 };
866 let len = min(delta, slice.len());
867 Some((offset, &slice[..len]))
868 })?
869 } else {
870 Some((offset, slice))
871 }
872 }
873 SendStreamState::DataSent {
874 ref mut send_buf,
875 fin_sent,
876 ..
877 } => {
878 let used = send_buf.used(); // immutable first
879 let bytes = send_buf.next_bytes();
880 if bytes.is_some() {
881 bytes
882 } else if fin_sent {
883 None
884 } else {
885 // Send empty stream frame with fin set
886 Some((used, &[]))
887 }
888 }
889 SendStreamState::Ready { .. }
890 | SendStreamState::DataRecvd { .. }
891 | SendStreamState::ResetSent { .. }
892 | SendStreamState::ResetRecvd { .. } => None,
893 }
894 }
895
896 /// Calculate how many bytes (length) can fit into available space and whether
897 /// the remainder of the space can be filled (or if a length field is needed).
898 fn length_and_fill(data_len: usize, space: usize) -> (usize, bool) {
899 if data_len >= space {
900 // More data than space allows, or an exact fit => fast path.
901 qtrace!("SendStream::length_and_fill fill {space}");
902 return (space, true);
903 }
904
905 // Estimate size of the length field based on the available space,
906 // less 1, which is the worst case.
907 let length = min(space.saturating_sub(1), data_len);
908 let length_len = Encoder::varint_len(u64::try_from(length).expect("usize fits in u64"));
909 debug_assert!(length_len <= space); // We don't depend on this being true, but it is true.
910
911 // From here we can always fit `data_len`, but we might as well fill
912 // if there is no space for the length field plus another frame.
913 let fill = data_len + length_len + PacketBuilder::MINIMUM_FRAME_SIZE > space;
914 qtrace!("SendStream::length_and_fill {data_len} fill {fill}");
915 (data_len, fill)
916 }
917
918 /// Maybe write a `STREAM` frame.
919 #[allow(
920 clippy::allow_attributes,
921 clippy::missing_panics_doc,
922 reason = "OK here."
923 )]
924 pub fn write_stream_frame(
925 &mut self,
926 priority: TransmissionPriority,
927 builder: &mut PacketBuilder,
928 tokens: &mut Vec<RecoveryToken>,
929 stats: &mut FrameStats,
930 ) {
931 let retransmission = if priority == self.priority {
932 false
933 } else if priority == self.priority + self.retransmission_priority {
934 true
935 } else {
936 return;
937 };
938
939 let id = self.stream_id;
940 let final_size = self.final_size();
941 if let Some((offset, data)) = self.next_bytes(retransmission) {
942 let overhead = 1 // Frame type
943 + Encoder::varint_len(id.as_u64())
944 + if offset > 0 {
945 Encoder::varint_len(offset)
946 } else {
947 0
948 };
949 if overhead > builder.remaining() {
950 qtrace!("[{self}] write_frame no space for header");
951 return;
952 }
953
954 let (length, fill) = Self::length_and_fill(data.len(), builder.remaining() - overhead);
955 let fin = final_size
956 .is_some_and(|fs| fs == offset + u64::try_from(length).expect("usize fits in u64"));
957 if length == 0 && !fin {
958 qtrace!("[{self}] write_frame no data, no fin");
959 return;
960 }
961
962 // Write the stream out.
963 builder.encode_varint(Frame::stream_type(fin, offset > 0, fill));
964 builder.encode_varint(id.as_u64());
965 if offset > 0 {
966 builder.encode_varint(offset);
967 }
968 if fill {
969 builder.encode(&data[..length]);
970 builder.mark_full();
971 } else {
972 builder.encode_vvec(&data[..length]);
973 }
974 debug_assert!(builder.len() <= builder.limit());
975
976 self.mark_as_sent(offset, length, fin);
977 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::Stream(
978 SendStreamRecoveryToken {
979 id,
980 offset,
981 length,
982 fin,
983 },
984 )));
985 stats.stream += 1;
986 }
987 }
988
989 pub fn reset_acked(&mut self) {
990 match self.state {
991 SendStreamState::Ready { .. }
992 | SendStreamState::Send { .. }
993 | SendStreamState::DataSent { .. }
994 | SendStreamState::DataRecvd { .. } => {
995 qtrace!("[{self}] Reset acked while in {:?} state?", self.state);
996 }
997 SendStreamState::ResetSent {
998 final_retired,
999 final_written,
1000 ..
1001 } => self.state.transition(SendStreamState::ResetRecvd {
1002 final_retired,
1003 final_written,
1004 }),
1005 SendStreamState::ResetRecvd { .. } => qtrace!("[{self}] already in ResetRecvd state"),
1006 }
1007 }
1008
1009 pub fn reset_lost(&mut self) {
1010 match self.state {
1011 SendStreamState::ResetSent {
1012 ref mut priority, ..
1013 } => {
1014 *priority = Some(self.priority + self.retransmission_priority);
1015 }
1016 SendStreamState::ResetRecvd { .. } => (),
1017 _ => unreachable!(),
1018 }
1019 }
1020
1021 /// Maybe write a `RESET_STREAM` frame.
1022 pub fn write_reset_frame(
1023 &mut self,
1024 p: TransmissionPriority,
1025 builder: &mut PacketBuilder,
1026 tokens: &mut Vec<RecoveryToken>,
1027 stats: &mut FrameStats,
1028 ) -> bool {
1029 if let SendStreamState::ResetSent {
1030 final_size,
1031 err,
1032 ref mut priority,
1033 ..
1034 } = self.state
1035 {
1036 if *priority != Some(p) {
1037 return false;
1038 }
1039 if builder.write_varint_frame(&[
1040 FrameType::ResetStream.into(),
1041 self.stream_id.as_u64(),
1042 err,
1043 final_size,
1044 ]) {
1045 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::ResetStream {
1046 stream_id: self.stream_id,
1047 }));
1048 stats.reset_stream += 1;
1049 *priority = None;
1050 true
1051 } else {
1052 false
1053 }
1054 } else {
1055 false
1056 }
1057 }
1058
1059 pub fn blocked_lost(&mut self, limit: u64) {
1060 if let SendStreamState::Ready { fc, .. } | SendStreamState::Send { fc, .. } =
1061 &mut self.state
1062 {
1063 fc.frame_lost(limit);
1064 } else {
1065 qtrace!("[{self}] Ignoring lost STREAM_DATA_BLOCKED({limit})");
1066 }
1067 }
1068
1069 /// Maybe write a `STREAM_DATA_BLOCKED` frame.
1070 pub fn write_blocked_frame(
1071 &mut self,
1072 priority: TransmissionPriority,
1073 builder: &mut PacketBuilder,
1074 tokens: &mut Vec<RecoveryToken>,
1075 stats: &mut FrameStats,
1076 ) {
1077 // Send STREAM_DATA_BLOCKED at normal priority always.
1078 if priority == self.priority {
1079 if let SendStreamState::Ready { fc, .. } | SendStreamState::Send { fc, .. } =
1080 &mut self.state
1081 {
1082 fc.write_frames(builder, tokens, stats);
1083 }
1084 }
1085 }
1086
1087 #[allow(
1088 clippy::allow_attributes,
1089 clippy::missing_panics_doc,
1090 reason = "OK here."
1091 )]
1092 pub fn mark_as_sent(&mut self, offset: u64, len: usize, fin: bool) {
1093 self.bytes_sent = max(
1094 self.bytes_sent,
1095 offset + u64::try_from(len).expect("usize fits in u64"),
1096 );
1097
1098 if let Some(buf) = self.state.tx_buf_mut() {
1099 buf.mark_as_sent(offset, len);
1100 self.send_blocked_if_space_needed(0);
1101 }
1102
1103 if fin {
1104 if let SendStreamState::DataSent { fin_sent, .. } = &mut self.state {
1105 *fin_sent = true;
1106 }
1107 }
1108 }
1109
1110 #[allow(
1111 clippy::allow_attributes,
1112 clippy::missing_panics_doc,
1113 reason = "OK here."
1114 )]
1115 pub fn mark_as_acked(&mut self, offset: u64, len: usize, fin: bool) {
1116 match self.state {
1117 SendStreamState::Send {
1118 ref mut send_buf, ..
1119 } => {
1120 let previous_limit = send_buf.avail();
1121 send_buf.mark_as_acked(offset, len);
1122 let current_limit = send_buf.avail();
1123 self.maybe_emit_writable_event(previous_limit, current_limit);
1124 }
1125 SendStreamState::DataSent {
1126 ref mut send_buf,
1127 ref mut fin_acked,
1128 ..
1129 } => {
1130 send_buf.mark_as_acked(offset, len);
1131 if fin {
1132 *fin_acked = true;
1133 }
1134 if *fin_acked && send_buf.buffered() == 0 {
1135 self.conn_events.send_stream_complete(self.stream_id);
1136 let retired = send_buf.retired();
1137 let buffered = u64::try_from(send_buf.buffered()).expect("usize fits in u64");
1138 self.state.transition(SendStreamState::DataRecvd {
1139 retired,
1140 written: buffered,
1141 });
1142 }
1143 }
1144 _ => qtrace!("[{self}] mark_as_acked called from state {:?}", self.state),
1145 }
1146 }
1147
1148 #[allow(
1149 clippy::allow_attributes,
1150 clippy::missing_panics_doc,
1151 reason = "OK here."
1152 )]
1153 pub fn mark_as_lost(&mut self, offset: u64, len: usize, fin: bool) {
1154 self.retransmission_offset = max(
1155 self.retransmission_offset,
1156 offset + u64::try_from(len).expect("usize fits in u64"),
1157 );
1158 qtrace!(
1159 "[{self}] mark_as_lost retransmission offset={}",
1160 self.retransmission_offset
1161 );
1162 if let Some(buf) = self.state.tx_buf_mut() {
1163 buf.mark_as_lost(offset, len);
1164 }
1165
1166 if fin {
1167 if let SendStreamState::DataSent {
1168 fin_sent,
1169 fin_acked,
1170 ..
1171 } = &mut self.state
1172 {
1173 *fin_sent = *fin_acked;
1174 }
1175 }
1176 }
1177
1178 /// Bytes sendable on stream. Constrained by stream credit available,
1179 /// connection credit available, and space in the tx buffer.
1180 #[must_use]
1181 pub fn avail(&self) -> usize {
1182 if let SendStreamState::Ready { fc, conn_fc } | SendStreamState::Send { fc, conn_fc, .. } =
1183 &self.state
1184 {
1185 min(
1186 min(fc.available(), conn_fc.borrow().available()),
1187 self.state.tx_avail(),
1188 )
1189 } else {
1190 0
1191 }
1192 }
1193
1194 /// Set low watermark for [`crate::ConnectionEvent::SendStreamWritable`]
1195 /// event.
1196 ///
1197 /// See [`crate::Connection::stream_set_writable_event_low_watermark`].
1198 pub fn set_writable_event_low_watermark(&mut self, watermark: NonZeroUsize) {
1199 self.writable_event_low_watermark = watermark;
1200 }
1201
1202 pub fn set_max_stream_data(&mut self, limit: u64) {
1203 qdebug!("setting max_stream_data to {limit}");
1204 if let SendStreamState::Ready { fc, .. } | SendStreamState::Send { fc, .. } =
1205 &mut self.state
1206 {
1207 let previous_limit = fc.available();
1208 if let Some(current_limit) = fc.update(limit) {
1209 self.maybe_emit_writable_event(previous_limit, current_limit);
1210 }
1211 }
1212 }
1213
1214 #[must_use]
1215 pub const fn is_terminal(&self) -> bool {
1216 matches!(
1217 self.state,
1218 SendStreamState::DataRecvd { .. } | SendStreamState::ResetRecvd { .. }
1219 )
1220 }
1221
1222 /// # Errors
1223 /// When `buf` is empty or when the stream is already closed.
1224 pub fn send(&mut self, buf: &[u8]) -> Res<usize> {
1225 self.send_internal(buf, false)
1226 }
1227
1228 /// # Errors
1229 /// When `buf` is empty or when the stream is already closed.
1230 pub fn send_atomic(&mut self, buf: &[u8]) -> Res<usize> {
1231 self.send_internal(buf, true)
1232 }
1233
1234 fn send_blocked_if_space_needed(&mut self, needed_space: usize) {
1235 if let SendStreamState::Ready { fc, conn_fc } | SendStreamState::Send { fc, conn_fc, .. } =
1236 &mut self.state
1237 {
1238 if fc.available() <= needed_space {
1239 fc.blocked();
1240 }
1241
1242 if conn_fc.borrow().available() <= needed_space {
1243 conn_fc.borrow_mut().blocked();
1244 }
1245 }
1246 }
1247
1248 fn send_internal(&mut self, buf: &[u8], atomic: bool) -> Res<usize> {
1249 if buf.is_empty() {
1250 qerror!("[{self}] zero-length send on stream");
1251 return Err(Error::InvalidInput);
1252 }
1253
1254 if let SendStreamState::Ready { fc, conn_fc } = &mut self.state {
1255 let owned_fc = mem::replace(fc, SenderFlowControl::new(self.stream_id, 0));
1256 let owned_conn_fc = Rc::clone(conn_fc);
1257 self.state.transition(SendStreamState::Send {
1258 fc: owned_fc,
1259 conn_fc: owned_conn_fc,
1260 send_buf: TxBuffer::new(),
1261 });
1262 }
1263
1264 if !matches!(self.state, SendStreamState::Send { .. }) {
1265 return Err(Error::FinalSizeError);
1266 }
1267
1268 let buf = if self.avail() == 0 {
1269 return Ok(0);
1270 } else if self.avail() < buf.len() {
1271 if atomic {
1272 self.send_blocked_if_space_needed(buf.len());
1273 return Ok(0);
1274 }
1275
1276 &buf[..self.avail()]
1277 } else {
1278 buf
1279 };
1280
1281 match &mut self.state {
1282 SendStreamState::Ready { .. } => unreachable!(),
1283 SendStreamState::Send {
1284 fc,
1285 conn_fc,
1286 send_buf,
1287 } => {
1288 let sent = send_buf.send(buf);
1289 fc.consume(sent);
1290 conn_fc.borrow_mut().consume(sent);
1291 Ok(sent)
1292 }
1293 _ => Err(Error::FinalSizeError),
1294 }
1295 }
1296
1297 pub fn close(&mut self) {
1298 match &mut self.state {
1299 SendStreamState::Ready { .. } => {
1300 self.state.transition(SendStreamState::DataSent {
1301 send_buf: TxBuffer::new(),
1302 fin_sent: false,
1303 fin_acked: false,
1304 });
1305 }
1306 SendStreamState::Send { send_buf, .. } => {
1307 let owned_buf = mem::replace(send_buf, TxBuffer::new());
1308 self.state.transition(SendStreamState::DataSent {
1309 send_buf: owned_buf,
1310 fin_sent: false,
1311 fin_acked: false,
1312 });
1313 }
1314 SendStreamState::DataSent { .. } => qtrace!("[{self}] already in DataSent state"),
1315 SendStreamState::DataRecvd { .. } => qtrace!("[{self}] already in DataRecvd state"),
1316 SendStreamState::ResetSent { .. } => qtrace!("[{self}] already in ResetSent state"),
1317 SendStreamState::ResetRecvd { .. } => qtrace!("[{self}] already in ResetRecvd state"),
1318 }
1319 }
1320
1321 #[allow(
1322 clippy::allow_attributes,
1323 clippy::missing_panics_doc,
1324 reason = "OK here."
1325 )]
1326 pub fn reset(&mut self, err: AppError) {
1327 match &self.state {
1328 SendStreamState::Ready { fc, .. } => {
1329 let final_size = fc.used();
1330 self.state.transition(SendStreamState::ResetSent {
1331 err,
1332 final_size,
1333 priority: Some(self.priority),
1334 final_retired: 0,
1335 final_written: 0,
1336 });
1337 }
1338 SendStreamState::Send { fc, send_buf, .. } => {
1339 let final_size = fc.used();
1340 let final_retired = send_buf.retired();
1341 let buffered = u64::try_from(send_buf.buffered()).expect("usize fits in u64");
1342 self.state.transition(SendStreamState::ResetSent {
1343 err,
1344 final_size,
1345 priority: Some(self.priority),
1346 final_retired,
1347 final_written: buffered,
1348 });
1349 }
1350 SendStreamState::DataSent { send_buf, .. } => {
1351 let final_size = send_buf.used();
1352 let final_retired = send_buf.retired();
1353 let buffered = u64::try_from(send_buf.buffered()).expect("usize fits in u64");
1354 self.state.transition(SendStreamState::ResetSent {
1355 err,
1356 final_size,
1357 priority: Some(self.priority),
1358 final_retired,
1359 final_written: buffered,
1360 });
1361 }
1362 SendStreamState::DataRecvd { .. } => qtrace!("[{self}] already in DataRecvd state"),
1363 SendStreamState::ResetSent { .. } => qtrace!("[{self}] already in ResetSent state"),
1364 SendStreamState::ResetRecvd { .. } => qtrace!("[{self}] already in ResetRecvd state"),
1365 }
1366 }
1367
1368 #[cfg(test)]
1369 pub(crate) fn state(&mut self) -> &mut SendStreamState {
1370 &mut self.state
1371 }
1372
1373 pub(crate) fn maybe_emit_writable_event(&self, previous_limit: usize, current_limit: usize) {
1374 let low_watermark = self.writable_event_low_watermark.get();
1375
1376 // Skip if:
1377 // - stream was not constrained by limit before,
1378 // - or stream is still constrained by limit,
1379 // - or stream is constrained by different limit.
1380 if low_watermark < previous_limit
1381 || current_limit < low_watermark
1382 || self.avail() < low_watermark
1383 {
1384 return;
1385 }
1386
1387 self.conn_events.send_stream_writable(self.stream_id);
1388 }
1389 }
1390
1391 impl Display for SendStream {
1392 fn fmt(&self, f: &mut Formatter) -> fmt::Result {
1393 write!(f, "SendStream {}", self.stream_id)
1394 }
1395 }
1396
1397 #[derive(Debug, Default)]
1398 pub struct OrderGroup {
1399 // This vector is sorted by StreamId
1400 vec: Vec<StreamId>,
1401
1402 // Since we need to remember where we were, we'll store the iterator next
1403 // position in the object. This means there can only be a single iterator active
1404 // at a time!
1405 next: usize,
1406 // This is used when an iterator is created to set the start/stop point for the
1407 // iteration. The iterator must iterate from this entry to the end, and then
1408 // wrap and iterate from 0 until before the initial value of next.
1409 // This value may need to be updated after insertion and removal; in theory we should
1410 // track the target entry across modifications, but in practice it should be good
1411 // enough to simply leave it alone unless it points past the end of the
1412 // Vec, and re-initialize to 0 in that case.
1413 }
1414
1415 pub struct OrderGroupIter<'a> {
1416 group: &'a mut OrderGroup,
1417 // We store the next position in the OrderGroup.
1418 // Otherwise we'd need an explicit "done iterating" call to be made, or implement Drop to
1419 // copy the value back.
1420 // This is where next was when we iterated for the first time; when we get back to that we
1421 // stop.
1422 started_at: Option<usize>,
1423 }
1424
1425 impl OrderGroup {
1426 pub fn iter(&mut self) -> OrderGroupIter {
1427 // Ids may have been deleted since we last iterated
1428 if self.next >= self.vec.len() {
1429 self.next = 0;
1430 }
1431 OrderGroupIter {
1432 started_at: None,
1433 group: self,
1434 }
1435 }
1436
1437 #[must_use]
1438 pub const fn stream_ids(&self) -> &Vec<StreamId> {
1439 &self.vec
1440 }
1441
1442 pub fn clear(&mut self) {
1443 self.vec.clear();
1444 }
1445
1446 pub fn push(&mut self, stream_id: StreamId) {
1447 self.vec.push(stream_id);
1448 }
1449
1450 #[cfg(test)]
1451 pub fn truncate(&mut self, position: usize) {
1452 self.vec.truncate(position);
1453 }
1454
1455 fn update_next(&mut self) -> usize {
1456 let next = self.next;
1457 self.next = (self.next + 1) % self.vec.len();
1458 next
1459 }
1460
1461 /// # Panics
1462 /// If the stream ID is already present.
1463 pub fn insert(&mut self, stream_id: StreamId) {
1464 let Err(pos) = self.vec.binary_search(&stream_id) else {
1465 // element already in vector @ `pos`
1466 panic!("Duplicate stream_id {stream_id}");
1467 };
1468 self.vec.insert(pos, stream_id);
1469 }
1470
1471 /// # Panics
1472 /// If the stream ID is not present.
1473 pub fn remove(&mut self, stream_id: StreamId) {
1474 let Ok(pos) = self.vec.binary_search(&stream_id) else {
1475 // element already in vector @ `pos`
1476 panic!("Missing stream_id {stream_id}");
1477 };
1478 self.vec.remove(pos);
1479 }
1480 }
1481
1482 impl Iterator for OrderGroupIter<'_> {
1483 type Item = StreamId;
1484 fn next(&mut self) -> Option<Self::Item> {
1485 // Stop when we would return the started_at element on the next
1486 // call. Note that this must take into account wrapping.
1487 if self.started_at == Some(self.group.next) || self.group.vec.is_empty() {
1488 return None;
1489 }
1490 self.started_at = self.started_at.or(Some(self.group.next));
1491 let orig = self.group.update_next();
1492 Some(self.group.vec[orig])
1493 }
1494 }
1495
1496 #[derive(Debug, Default)]
1497 pub struct SendStreams {
1498 map: IndexMap<StreamId, SendStream>,
1499
1500 // What we really want is a Priority Queue that we can do arbitrary
1501 // removes from (so we can reprioritize). BinaryHeap doesn't work,
1502 // because there's no remove(). BTreeMap doesn't work, since you can't
1503 // duplicate keys. PriorityQueue does have what we need, except for an
1504 // ordered iterator that doesn't consume the queue. So we roll our own.
1505
1506 // Added complication: We want to have Fairness for streams of the same
1507 // 'group' (for WebTransport), but for H3 (and other non-WT streams) we
1508 // tend to get better pageload performance by prioritizing by creation order.
1509 //
1510 // Two options are to walk the 'map' first, ignoring WebTransport
1511 // streams, then process the unordered and ordered WebTransport
1512 // streams. The second is to have a sorted Vec for unfair streams (and
1513 // use a normal iterator for that), and then chain the iterators for
1514 // the unordered and ordered WebTranport streams. The first works very
1515 // well for H3, and for WebTransport nodes are visited twice on every
1516 // processing loop. The second adds insertion and removal costs, but
1517 // avoids a CPU penalty for WebTransport streams. For now we'll do #1.
1518 //
1519 // So we use a sorted Vec<> for the regular streams (that's usually all of
1520 // them), and then a BTreeMap of an entry for each SendOrder value, and
1521 // for each of those entries a Vec of the stream_ids at that
1522 // sendorder. In most cases (such as stream-per-frame), there will be
1523 // a single stream at a given sendorder.
1524
1525 // These both store stream_ids, which need to be looked up in 'map'.
1526 // This avoids the complexity of trying to hold references to the
1527 // Streams which are owned by the IndexMap.
1528 sendordered: BTreeMap<SendOrder, OrderGroup>,
1529 regular: OrderGroup, // streams with no SendOrder set, sorted in stream_id order
1530 }
1531
1532 impl SendStreams {
1533 #[allow(
1534 clippy::allow_attributes,
1535 clippy::missing_errors_doc,
1536 reason = "OK here."
1537 )]
1538 pub fn get(&self, id: StreamId) -> Res<&SendStream> {
1539 self.map.get(&id).ok_or(Error::InvalidStreamId)
1540 }
1541
1542 #[allow(
1543 clippy::allow_attributes,
1544 clippy::missing_errors_doc,
1545 reason = "OK here."
1546 )]
1547 pub fn get_mut(&mut self, id: StreamId) -> Res<&mut SendStream> {
1548 self.map.get_mut(&id).ok_or(Error::InvalidStreamId)
1549 }
1550
1551 #[must_use]
1552 pub fn exists(&self, id: StreamId) -> bool {
1553 self.map.contains_key(&id)
1554 }
1555
1556 pub fn insert(&mut self, id: StreamId, stream: SendStream) {
1557 self.map.insert(id, stream);
1558 }
1559
1560 fn group_mut(&mut self, sendorder: Option<SendOrder>) -> &mut OrderGroup {
1561 if let Some(order) = sendorder {
1562 self.sendordered.entry(order).or_default()
1563 } else {
1564 &mut self.regular
1565 }
1566 }
1567
1568 #[allow(
1569 clippy::allow_attributes,
1570 clippy::missing_errors_doc,
1571 reason = "OK here."
1572 )]
1573 pub fn set_sendorder(&mut self, stream_id: StreamId, sendorder: Option<SendOrder>) -> Res<()> {
1574 self.set_fairness(stream_id, true)?;
1575 if let Some(stream) = self.map.get_mut(&stream_id) {
1576 // don't grab stream here; causes borrow errors
1577 let old_sendorder = stream.sendorder();
1578 if old_sendorder != sendorder {
1579 // we have to remove it from the list it was in, and reinsert it with the new
1580 // sendorder key
1581 let mut group = self.group_mut(old_sendorder);
1582 group.remove(stream_id);
1583 self.get_mut(stream_id)?.set_sendorder(sendorder);
1584 group = self.group_mut(sendorder);
1585 group.insert(stream_id);
1586 qtrace!(
1587 "ordering of stream_ids: {:?}",
1588 self.sendordered.values().collect::<Vec::<_>>()
1589 );
1590 }
1591 Ok(())
1592 } else {
1593 Err(Error::InvalidStreamId)
1594 }
1595 }
1596
1597 #[allow(
1598 clippy::allow_attributes,
1599 clippy::missing_errors_doc,
1600 reason = "OK here."
1601 )]
1602 pub fn set_fairness(&mut self, stream_id: StreamId, make_fair: bool) -> Res<()> {
1603 let stream: &mut SendStream = self.map.get_mut(&stream_id).ok_or(Error::InvalidStreamId)?;
1604 let was_fair = stream.fair;
1605 stream.set_fairness(make_fair);
1606 if !was_fair && make_fair {
1607 // Move to the regular OrderGroup.
1608
1609 // We know sendorder can't have been set, since
1610 // set_sendorder() will call this routine if it's not
1611 // already set as fair.
1612
1613 // This normally is only called when a new stream is created. If
1614 // so, because of how we allocate StreamIds, it should always have
1615 // the largest value. This means we can just append it to the
1616 // regular vector. However, if we were ever to change this
1617 // invariant, things would break subtly.
1618
1619 // To be safe we can try to insert at the end and if not
1620 // fall back to binary-search insertion
1621 if matches!(self.regular.stream_ids().last(), Some(last) if stream_id > *last) {
1622 self.regular.push(stream_id);
1623 } else {
1624 self.regular.insert(stream_id);
1625 }
1626 } else if was_fair && !make_fair {
1627 // remove from the OrderGroup
1628 let group = if let Some(sendorder) = stream.sendorder {
1629 self.sendordered
1630 .get_mut(&sendorder)
1631 .ok_or(Error::InternalError)?
1632 } else {
1633 &mut self.regular
1634 };
1635 group.remove(stream_id);
1636 }
1637 Ok(())
1638 }
1639
1640 pub fn acked(&mut self, token: &SendStreamRecoveryToken) {
1641 if let Some(ss) = self.map.get_mut(&token.id) {
1642 ss.mark_as_acked(token.offset, token.length, token.fin);
1643 }
1644 }
1645
1646 pub fn reset_acked(&mut self, id: StreamId) {
1647 if let Some(ss) = self.map.get_mut(&id) {
1648 ss.reset_acked();
1649 }
1650 }
1651
1652 pub fn lost(&mut self, token: &SendStreamRecoveryToken) {
1653 if let Some(ss) = self.map.get_mut(&token.id) {
1654 ss.mark_as_lost(token.offset, token.length, token.fin);
1655 }
1656 }
1657
1658 pub fn reset_lost(&mut self, stream_id: StreamId) {
1659 if let Some(ss) = self.map.get_mut(&stream_id) {
1660 ss.reset_lost();
1661 }
1662 }
1663
1664 pub fn blocked_lost(&mut self, stream_id: StreamId, limit: u64) {
1665 if let Some(ss) = self.map.get_mut(&stream_id) {
1666 ss.blocked_lost(limit);
1667 }
1668 }
1669
1670 pub fn clear(&mut self) {
1671 self.map.clear();
1672 self.sendordered.clear();
1673 self.regular.clear();
1674 }
1675
1676 pub fn remove_terminal(&mut self) {
1677 self.map.retain(|stream_id, stream| {
1678 if stream.is_terminal() {
1679 if stream.is_fair() {
1680 match stream.sendorder() {
1681 None => self.regular.remove(*stream_id),
1682 Some(sendorder) => {
1683 if let Some(group) = self.sendordered.get_mut(&sendorder) {
1684 group.remove(*stream_id);
1685 }
1686 }
1687 }
1688 }
1689 // if unfair, we're done
1690 return false;
1691 }
1692 true
1693 });
1694 }
1695
1696 pub(crate) fn write_frames(
1697 &mut self,
1698 priority: TransmissionPriority,
1699 builder: &mut PacketBuilder,
1700 tokens: &mut Vec<RecoveryToken>,
1701 stats: &mut FrameStats,
1702 ) {
1703 qtrace!("write STREAM frames at priority {priority:?}");
1704 // WebTransport data (which is Normal) may have a SendOrder
1705 // priority attached. The spec states (6.3 write-chunk 6.1):
1706
1707 // First, we send any streams without Fairness defined, with
1708 // ordering defined by StreamId. (Http3 streams used for
1709 // e.g. pageload benefit from being processed in order of creation
1710 // so the far side can start acting on a datum/request sooner. All
1711 // WebTransport streams MUST have fairness set.) Then we send
1712 // streams with fairness set (including all WebTransport streams)
1713 // as follows:
1714
1715 // If stream.[[SendOrder]] is null then this sending MUST NOT
1716 // starve except for flow control reasons or error. If
1717 // stream.[[SendOrder]] is not null then this sending MUST starve
1718 // until all bytes queued for sending on WebTransportSendStreams
1719 // with a non-null and higher [[SendOrder]], that are neither
1720 // errored nor blocked by flow control, have been sent.
1721
1722 // So data without SendOrder goes first. Then the highest priority
1723 // SendOrdered streams.
1724 //
1725 // Fairness is implemented by a round-robining or "statefully
1726 // iterating" within a single sendorder/unordered vector. We do
1727 // this by recording where we stopped in the previous pass, and
1728 // starting there the next pass. If we store an index into the
1729 // vec, this means we can't use a chained iterator, since we want
1730 // to retain our place-in-the-vector. If we rotate the vector,
1731 // that would let us use the chained iterator, but would require
1732 // more expensive searches for insertion and removal (since the
1733 // sorted order would be lost).
1734
1735 // Iterate the map, but only those without fairness, then iterate
1736 // OrderGroups, then iterate each group
1737 qtrace!("processing streams... unfair:");
1738 for stream in self.map.values_mut() {
1739 if !stream.is_fair() {
1740 qtrace!(" {stream}");
1741 if !stream.write_frames_with_early_return(priority, builder, tokens, stats) {
1742 break;
1743 }
1744 }
1745 }
1746 qtrace!("fair streams:");
1747 let stream_ids = self.regular.iter().chain(
1748 self.sendordered
1749 .values_mut()
1750 .rev()
1751 .flat_map(|group| group.iter()),
1752 );
1753 for stream_id in stream_ids {
1754 if let Some(stream) = self.map.get_mut(&stream_id) {
1755 if let Some(order) = stream.sendorder() {
1756 qtrace!(" {stream_id} ({order})");
1757 } else {
1758 qtrace!(" None");
1759 }
1760 if !stream.write_frames_with_early_return(priority, builder, tokens, stats) {
1761 break;
1762 }
1763 }
1764 }
1765 }
1766
1767 #[allow(
1768 clippy::allow_attributes,
1769 clippy::missing_panics_doc,
1770 reason = "OK here."
1771 )]
1772 pub fn update_initial_limit(&mut self, remote: &TransportParameters) {
1773 for (id, ss) in &mut self.map {
1774 let limit = if id.is_bidi() {
1775 assert!(!id.is_remote_initiated(Role::Client));
1776 remote.get_integer(InitialMaxStreamDataBidiRemote)
1777 } else {
1778 remote.get_integer(InitialMaxStreamDataUni)
1779 };
1780 ss.set_max_stream_data(limit);
1781 }
1782 }
1783 }
1784
1785 #[allow(
1786 clippy::allow_attributes,
1787 clippy::into_iter_without_iter,
1788 reason = "OK here."
1789 )]
1790 impl<'a> IntoIterator for &'a mut SendStreams {
1791 type Item = (&'a StreamId, &'a mut SendStream);
1792 type IntoIter = indexmap::map::IterMut<'a, StreamId, SendStream>;
1793
1794 fn into_iter(self) -> indexmap::map::IterMut<'a, StreamId, SendStream> {
1795 self.map.iter_mut()
1796 }
1797 }
1798
1799 #[derive(Debug, Clone)]
1800 pub struct SendStreamRecoveryToken {
1801 id: StreamId,
1802 offset: u64,
1803 length: usize,
1804 fin: bool,
1805 }
1806
1807 #[cfg(test)]
1808 mod tests {
1809 use std::{cell::RefCell, collections::VecDeque, num::NonZeroUsize, rc::Rc};
1810
1811 use neqo_common::{event::Provider as _, hex_with_len, qtrace, Encoder, MAX_VARINT};
1812
1813 use super::SendStreamRecoveryToken;
1814 use crate::{
1815 connection::{RetransmissionPriority, TransmissionPriority},
1816 events::ConnectionEvent,
1817 fc::SenderFlowControl,
1818 packet::PacketBuilder,
1819 recovery::{RecoveryToken, StreamRecoveryToken},
1820 send_stream::{
1821 RangeState, RangeTracker, SendStream, SendStreamState, SendStreams, TxBuffer,
1822 MAX_SEND_BUFFER_SIZE,
1823 },
1824 stats::FrameStats,
1825 ConnectionEvents, StreamId, INITIAL_RECV_WINDOW_SIZE,
1826 };
1827
1828 fn connection_fc(limit: u64) -> Rc<RefCell<SenderFlowControl<()>>> {
1829 Rc::new(RefCell::new(SenderFlowControl::new((), limit)))
1830 }
1831
1832 #[test]
1833 fn mark_acked_from_zero() {
1834 let mut rt = RangeTracker::default();
1835
1836 // ranges can go from nothing->Sent if queued for retrans and then
1837 // acks arrive
1838 rt.mark_acked(5, 5);
1839 assert_eq!(rt.highest_offset(), 10);
1840 assert_eq!(rt.acked_from_zero(), 0);
1841 rt.mark_acked(10, 4);
1842 assert_eq!(rt.highest_offset(), 14);
1843 assert_eq!(rt.acked_from_zero(), 0);
1844
1845 rt.mark_sent(0, 5);
1846 assert_eq!(rt.highest_offset(), 14);
1847 assert_eq!(rt.acked_from_zero(), 0);
1848 rt.mark_acked(0, 5);
1849 assert_eq!(rt.highest_offset(), 14);
1850 assert_eq!(rt.acked_from_zero(), 14);
1851
1852 rt.mark_acked(12, 20);
1853 assert_eq!(rt.highest_offset(), 32);
1854 assert_eq!(rt.acked_from_zero(), 32);
1855
1856 // ack the lot
1857 rt.mark_acked(0, 400);
1858 assert_eq!(rt.highest_offset(), 400);
1859 assert_eq!(rt.acked_from_zero(), 400);
1860
1861 // acked trumps sent
1862 rt.mark_sent(0, 200);
1863 assert_eq!(rt.highest_offset(), 400);
1864 assert_eq!(rt.acked_from_zero(), 400);
1865 }
1866
1867 /// Check that `marked_acked` correctly handles all paths.
1868 /// ```ignore
1869 /// SSS SSSAAASSS
1870 /// + AAAAAAAAA
1871 /// = SSSAAAAAAAAASS
1872 /// ```
1873 #[test]
1874 fn mark_acked_1() {
1875 let mut rt = RangeTracker::default();
1876 rt.mark_sent(0, 3);
1877 rt.mark_sent(6, 3);
1878 rt.mark_acked(9, 3);
1879 rt.mark_sent(12, 3);
1880
1881 rt.mark_acked(3, 10);
1882
1883 let mut canon = RangeTracker::default();
1884 canon.used.insert(0, (3, RangeState::Sent));
1885 canon.used.insert(3, (10, RangeState::Acked));
1886 canon.used.insert(13, (2, RangeState::Sent));
1887 assert_eq!(rt, canon);
1888 }
1889
1890 /// Check that `marked_acked` correctly handles all paths.
1891 /// ```ignore
1892 /// SSS SSS AAA
1893 /// + AAAAAAAAA
1894 /// = SSAAAAAAAAAAAA
1895 /// ```
1896 #[test]
1897 fn mark_acked_2() {
1898 let mut rt = RangeTracker::default();
1899 rt.mark_sent(0, 3);
1900 rt.mark_sent(6, 3);
1901 rt.mark_acked(12, 3);
1902
1903 rt.mark_acked(2, 10);
1904
1905 let mut canon = RangeTracker::default();
1906 canon.used.insert(0, (2, RangeState::Sent));
1907 canon.used.insert(2, (13, RangeState::Acked));
1908 assert_eq!(rt, canon);
1909 }
1910
1911 /// Check that `marked_acked` correctly handles all paths.
1912 /// ```ignore
1913 /// AASSS AAAA
1914 /// + AAAAAAAAA
1915 /// = AAAAAAAAAAAA
1916 /// ```
1917 #[test]
1918 fn mark_acked_3() {
1919 let mut rt = RangeTracker::default();
1920 rt.mark_acked(1, 2);
1921 rt.mark_sent(3, 3);
1922 rt.mark_acked(8, 4);
1923
1924 rt.mark_acked(0, 9);
1925
1926 let canon = RangeTracker {
1927 acked: 12,
1928 ..RangeTracker::default()
1929 };
1930 assert_eq!(rt, canon);
1931 }
1932
1933 /// Check that `marked_acked` correctly handles all paths.
1934 /// ```ignore
1935 /// SSS
1936 /// + AAAA
1937 /// = AAAASS
1938 /// ```
1939 #[test]
1940 fn mark_acked_4() {
1941 let mut rt = RangeTracker::default();
1942 rt.mark_sent(3, 3);
1943
1944 rt.mark_acked(0, 4);
1945
1946 let mut canon = RangeTracker {
1947 acked: 4,
1948 ..Default::default()
1949 };
1950 canon.used.insert(4, (2, RangeState::Sent));
1951 assert_eq!(rt, canon);
1952 }
1953
1954 /// Check that `marked_acked` correctly handles all paths.
1955 /// ```ignore
1956 /// AAAAAASSS
1957 /// + AAA
1958 /// = AAAAAASSS
1959 /// ```
1960 #[test]
1961 fn mark_acked_5() {
1962 let mut rt = RangeTracker::default();
1963 rt.mark_acked(0, 6);
1964 rt.mark_sent(6, 3);
1965
1966 rt.mark_acked(3, 3);
1967
1968 let mut canon = RangeTracker {
1969 acked: 6,
1970 ..RangeTracker::default()
1971 };
1972 canon.used.insert(6, (3, RangeState::Sent));
1973 assert_eq!(rt, canon);
1974 }
1975
1976 /// Check that `marked_acked` correctly handles all paths.
1977 /// ```ignore
1978 /// AAA AAA AAA
1979 /// + AAAAAAA
1980 /// = AAAAAAAAAAAAA
1981 /// ```
1982 #[test]
1983 fn mark_acked_6() {
1984 let mut rt = RangeTracker::default();
1985 rt.mark_acked(3, 3);
1986 rt.mark_acked(8, 3);
1987 rt.mark_acked(13, 3);
1988
1989 rt.mark_acked(6, 7);
1990
1991 let mut canon = RangeTracker::default();
1992 canon.used.insert(3, (13, RangeState::Acked));
1993 assert_eq!(rt, canon);
1994 }
1995
1996 /// Check that `marked_acked` correctly handles all paths.
1997 /// ```ignore
1998 /// AAA AAA
1999 /// + AAA
2000 /// = AAAAAAAA
2001 /// ```
2002 #[test]
2003 fn mark_acked_7() {
2004 let mut rt = RangeTracker::default();
2005 rt.mark_acked(3, 3);
2006 rt.mark_acked(8, 3);
2007
2008 rt.mark_acked(6, 3);
2009
2010 let mut canon = RangeTracker::default();
2011 canon.used.insert(3, (8, RangeState::Acked));
2012 assert_eq!(rt, canon);
2013 }
2014
2015 /// Check that `marked_acked` correctly handles all paths.
2016 /// ```ignore
2017 /// SSSSSSSS
2018 /// + AAAA
2019 /// = SSAAAASS
2020 /// ```
2021 #[test]
2022 fn mark_acked_8() {
2023 let mut rt = RangeTracker::default();
2024 rt.mark_sent(0, 8);
2025
2026 rt.mark_acked(2, 4);
2027
2028 let mut canon = RangeTracker::default();
2029 canon.used.insert(0, (2, RangeState::Sent));
2030 canon.used.insert(2, (4, RangeState::Acked));
2031 canon.used.insert(6, (2, RangeState::Sent));
2032 assert_eq!(rt, canon);
2033 }
2034
2035 /// Check that `marked_acked` correctly handles all paths.
2036 /// ```ignore
2037 /// SSS
2038 /// + AAA
2039 /// = AAA SSS
2040 /// ```
2041 #[test]
2042 fn mark_acked_9() {
2043 let mut rt = RangeTracker::default();
2044 rt.mark_sent(5, 3);
2045
2046 rt.mark_acked(0, 3);
2047
2048 let mut canon = RangeTracker {
2049 acked: 3,
2050 ..Default::default()
2051 };
2052 canon.used.insert(5, (3, RangeState::Sent));
2053 assert_eq!(rt, canon);
2054 }
2055
2056 /// Check that `marked_sent` correctly handles all paths.
2057 /// ```ignore
2058 /// AAA AAA SSS
2059 /// + SSSSSSSSSSSS
2060 /// = AAASSSAAASSSSSS
2061 /// ```
2062 #[test]
2063 fn mark_sent_1() {
2064 let mut rt = RangeTracker::default();
2065 rt.mark_acked(0, 3);
2066 rt.mark_acked(6, 3);
2067 rt.mark_sent(12, 3);
2068
2069 rt.mark_sent(0, 12);
2070
2071 let mut canon = RangeTracker {
2072 acked: 3,
2073 ..RangeTracker::default()
2074 };
2075 canon.used.insert(3, (3, RangeState::Sent));
2076 canon.used.insert(6, (3, RangeState::Acked));
2077 canon.used.insert(9, (6, RangeState::Sent));
2078 assert_eq!(rt, canon);
2079 }
2080
2081 /// Check that `marked_sent` correctly handles all paths.
2082 /// ```ignore
2083 /// AAASS AAA S SSSS
2084 /// + SSSSSSSSSSSSS
2085 /// = AAASSSAAASSSSSSS
2086 /// ```
2087 #[test]
2088 fn mark_sent_2() {
2089 let mut rt = RangeTracker::default();
2090 rt.mark_acked(0, 3);
2091 rt.mark_sent(3, 2);
2092 rt.mark_acked(6, 3);
2093 rt.mark_sent(10, 1);
2094 rt.mark_sent(12, 4);
2095
2096 rt.mark_sent(0, 13);
2097
2098 let mut canon = RangeTracker {
2099 acked: 3,
2100 ..RangeTracker::default()
2101 };
2102 canon.used.insert(3, (3, RangeState::Sent));
2103 canon.used.insert(6, (3, RangeState::Acked));
2104 canon.used.insert(9, (7, RangeState::Sent));
2105 assert_eq!(rt, canon);
2106 }
2107
2108 /// Check that `marked_sent` correctly handles all paths.
2109 /// ```ignore
2110 /// AAA AAA
2111 /// + SSSS
2112 /// = AAASSAAA
2113 /// ```
2114 #[test]
2115 fn mark_sent_3() {
2116 let mut rt = RangeTracker::default();
2117 rt.mark_acked(0, 3);
2118 rt.mark_acked(5, 3);
2119
2120 rt.mark_sent(2, 4);
2121
2122 let mut canon = RangeTracker {
2123 acked: 3,
2124 ..RangeTracker::default()
2125 };
2126 canon.used.insert(3, (2, RangeState::Sent));
2127 canon.used.insert(5, (3, RangeState::Acked));
2128 assert_eq!(rt, canon);
2129 }
2130
2131 /// Check that `marked_sent` correctly handles all paths.
2132 /// ```ignore
2133 /// SSS AAA SS
2134 /// + SSSSSSSS
2135 /// = SSSSSAAASSSS
2136 /// ```
2137 #[test]
2138 fn mark_sent_4() {
2139 let mut rt = RangeTracker::default();
2140 rt.mark_sent(0, 3);
2141 rt.mark_acked(5, 3);
2142 rt.mark_sent(10, 2);
2143
2144 rt.mark_sent(2, 8);
2145
2146 let mut canon = RangeTracker::default();
2147 canon.used.insert(0, (5, RangeState::Sent));
2148 canon.used.insert(5, (3, RangeState::Acked));
2149 canon.used.insert(8, (4, RangeState::Sent));
2150 assert_eq!(rt, canon);
2151 }
2152
2153 /// Check that `marked_sent` correctly handles all paths.
2154 /// ```ignore
2155 /// AAA
2156 /// + SSSSSS
2157 /// = AAASSS
2158 /// ```
2159 #[test]
2160 fn mark_sent_5() {
2161 let mut rt = RangeTracker::default();
2162 rt.mark_acked(3, 3);
2163
2164 rt.mark_sent(3, 6);
2165
2166 let mut canon = RangeTracker::default();
2167 canon.used.insert(3, (3, RangeState::Acked));
2168 canon.used.insert(6, (3, RangeState::Sent));
2169 assert_eq!(rt, canon);
2170 }
2171
2172 /// Check that `marked_sent` correctly handles all paths.
2173 /// ```ignore
2174 /// SSSSS
2175 /// + SSS
2176 /// = SSSSS
2177 /// ```
2178 #[test]
2179 fn mark_sent_6() {
2180 let mut rt = RangeTracker::default();
2181 rt.mark_sent(0, 5);
2182
2183 rt.mark_sent(1, 3);
2184
2185 let mut canon = RangeTracker::default();
2186 canon.used.insert(0, (5, RangeState::Sent));
2187 assert_eq!(rt, canon);
2188 }
2189
2190 #[test]
2191 fn unmark_sent_start() {
2192 let mut rt = RangeTracker::default();
2193
2194 rt.mark_sent(0, 5);
2195 assert_eq!(rt.highest_offset(), 5);
2196 assert_eq!(rt.acked_from_zero(), 0);
2197
2198 rt.unmark_sent();
2199 assert_eq!(rt.highest_offset(), 0);
2200 assert_eq!(rt.acked_from_zero(), 0);
2201 assert_eq!(rt.first_unmarked_range(), (0, None));
2202 }
2203
2204 #[test]
2205 fn unmark_sent_middle() {
2206 let mut rt = RangeTracker::default();
2207
2208 rt.mark_acked(0, 5);
2209 assert_eq!(rt.highest_offset(), 5);
2210 assert_eq!(rt.acked_from_zero(), 5);
2211 rt.mark_sent(5, 5);
2212 assert_eq!(rt.highest_offset(), 10);
2213 assert_eq!(rt.acked_from_zero(), 5);
2214 rt.mark_acked(10, 5);
2215 assert_eq!(rt.highest_offset(), 15);
2216 assert_eq!(rt.acked_from_zero(), 5);
2217 assert_eq!(rt.first_unmarked_range(), (15, None));
2218
2219 rt.unmark_sent();
2220 assert_eq!(rt.highest_offset(), 15);
2221 assert_eq!(rt.acked_from_zero(), 5);
2222 assert_eq!(rt.first_unmarked_range(), (5, Some(5)));
2223 }
2224
2225 #[test]
2226 fn unmark_sent_end() {
2227 let mut rt = RangeTracker::default();
2228
2229 rt.mark_acked(0, 5);
2230 assert_eq!(rt.highest_offset(), 5);
2231 assert_eq!(rt.acked_from_zero(), 5);
2232 rt.mark_sent(5, 5);
2233 assert_eq!(rt.highest_offset(), 10);
2234 assert_eq!(rt.acked_from_zero(), 5);
2235 assert_eq!(rt.first_unmarked_range(), (10, None));
2236
2237 rt.unmark_sent();
2238 assert_eq!(rt.highest_offset(), 5);
2239 assert_eq!(rt.acked_from_zero(), 5);
2240 assert_eq!(rt.first_unmarked_range(), (5, None));
2241 }
2242
2243 #[test]
2244 fn truncate_front() {
2245 let mut v = VecDeque::new();
2246 v.push_back(5);
2247 v.push_back(6);
2248 v.push_back(7);
2249 v.push_front(4usize);
2250
2251 v.rotate_left(1);
2252 v.truncate(3);
2253 assert_eq!(*v.front().unwrap(), 5);
2254 assert_eq!(*v.back().unwrap(), 7);
2255 }
2256
2257 #[test]
2258 fn unmark_range() {
2259 let mut rt = RangeTracker::default();
2260
2261 rt.mark_acked(5, 5);
2262 rt.mark_sent(10, 5);
2263
2264 // Should unmark sent but not acked range
2265 rt.unmark_range(7, 6);
2266
2267 let res = rt.first_unmarked_range();
2268 assert_eq!(res, (0, Some(5)));
2269 assert_eq!(
2270 rt.used.iter().next().unwrap(),
2271 (&5, &(5, RangeState::Acked))
2272 );
2273 assert_eq!(
2274 rt.used.iter().nth(1).unwrap(),
2275 (&13, &(2, RangeState::Sent))
2276 );
2277 assert!(rt.used.iter().nth(2).is_none());
2278 rt.mark_sent(0, 5);
2279
2280 let res = rt.first_unmarked_range();
2281 assert_eq!(res, (10, Some(3)));
2282 rt.mark_sent(10, 3);
2283
2284 let res = rt.first_unmarked_range();
2285 assert_eq!(res, (15, None));
2286 }
2287
2288 #[test]
2289 fn tx_buffer_next_bytes_1() {
2290 let mut txb = TxBuffer::new();
2291
2292 // Fill the buffer
2293 let big_buf = vec![1; INITIAL_RECV_WINDOW_SIZE];
2294 assert_eq!(txb.send(&big_buf), INITIAL_RECV_WINDOW_SIZE);
2295 assert!(matches!(txb.next_bytes(),
2296 Some((0, x)) if x.len() == INITIAL_RECV_WINDOW_SIZE
2297 && x.iter().all(|ch| *ch == 1)));
2298
2299 // Mark almost all as sent. Get what's left
2300 let one_byte_from_end = INITIAL_RECV_WINDOW_SIZE as u64 - 1;
2301 txb.mark_as_sent(0, usize::try_from(one_byte_from_end).unwrap());
2302 assert!(matches!(txb.next_bytes(),
2303 Some((start, x)) if x.len() == 1
2304 && start == one_byte_from_end
2305 && x.iter().all(|ch| *ch == 1)));
2306
2307 // Mark all as sent. Get nothing
2308 txb.mark_as_sent(0, INITIAL_RECV_WINDOW_SIZE);
2309 assert!(txb.next_bytes().is_none());
2310
2311 // Mark as lost. Get it again
2312 txb.mark_as_lost(one_byte_from_end, 1);
2313 assert!(matches!(txb.next_bytes(),
2314 Some((start, x)) if x.len() == 1
2315 && start == one_byte_from_end
2316 && x.iter().all(|ch| *ch == 1)));
2317
2318 // Mark a larger range lost, including beyond what's in the buffer even.
2319 // Get a little more
2320 let five_bytes_from_end = INITIAL_RECV_WINDOW_SIZE as u64 - 5;
2321 txb.mark_as_lost(five_bytes_from_end, 100);
2322 assert!(matches!(txb.next_bytes(),
2323 Some((start, x)) if x.len() == 5
2324 && start == five_bytes_from_end
2325 && x.iter().all(|ch| *ch == 1)));
2326
2327 // Contig acked range at start means it can be removed from buffer
2328 // Impl of vecdeque should now result in a split buffer when more data
2329 // is sent
2330 txb.mark_as_acked(0, usize::try_from(five_bytes_from_end).unwrap());
2331 assert_eq!(txb.send(&[2; 30]), 30);
2332 // Just get 5 even though there is more
2333 assert!(matches!(txb.next_bytes(),
2334 Some((start, x)) if x.len() == 5
2335 && start == five_bytes_from_end
2336 && x.iter().all(|ch| *ch == 1)));
2337 assert_eq!(txb.retired(), five_bytes_from_end);
2338 assert_eq!(txb.buffered(), 35);
2339
2340 // Marking that bit as sent should let the last contig bit be returned
2341 // when called again
2342 txb.mark_as_sent(five_bytes_from_end, 5);
2343 assert!(matches!(txb.next_bytes(),
2344 Some((start, x)) if x.len() == 30
2345 && start == INITIAL_RECV_WINDOW_SIZE as u64
2346 && x.iter().all(|ch| *ch == 2)));
2347 }
2348
2349 #[test]
2350 fn tx_buffer_next_bytes_2() {
2351 let mut txb = TxBuffer::new();
2352
2353 // Fill the buffer
2354 let big_buf = vec![1; INITIAL_RECV_WINDOW_SIZE];
2355 assert_eq!(txb.send(&big_buf), INITIAL_RECV_WINDOW_SIZE);
2356 assert!(matches!(txb.next_bytes(),
2357 Some((0, x)) if x.len()==INITIAL_RECV_WINDOW_SIZE
2358 && x.iter().all(|ch| *ch == 1)));
2359
2360 // As above
2361 let forty_bytes_from_end = INITIAL_RECV_WINDOW_SIZE as u64 - 40;
2362
2363 txb.mark_as_acked(0, usize::try_from(forty_bytes_from_end).unwrap());
2364 assert!(matches!(txb.next_bytes(),
2365 Some((start, x)) if x.len() == 40
2366 && start == forty_bytes_from_end
2367 ));
2368
2369 // Valid new data placed in split locations
2370 assert_eq!(txb.send(&[2; 100]), 100);
2371
2372 // Mark a little more as sent
2373 txb.mark_as_sent(forty_bytes_from_end, 10);
2374 let thirty_bytes_from_end = forty_bytes_from_end + 10;
2375 assert!(matches!(txb.next_bytes(),
2376 Some((start, x)) if x.len() == 30
2377 && start == thirty_bytes_from_end
2378 && x.iter().all(|ch| *ch == 1)));
2379
2380 // Mark a range 'A' in second slice as sent. Should still return the same
2381 let range_a_start = INITIAL_RECV_WINDOW_SIZE as u64 + 30;
2382 let range_a_end = range_a_start + 10;
2383 txb.mark_as_sent(range_a_start, 10);
2384 assert!(matches!(txb.next_bytes(),
2385 Some((start, x)) if x.len() == 30
2386 && start == thirty_bytes_from_end
2387 && x.iter().all(|ch| *ch == 1)));
2388
2389 // Ack entire first slice and into second slice
2390 let ten_bytes_past_end = INITIAL_RECV_WINDOW_SIZE as u64 + 10;
2391 txb.mark_as_acked(0, usize::try_from(ten_bytes_past_end).unwrap());
2392
2393 // Get up to marked range A
2394 assert!(matches!(txb.next_bytes(),
2395 Some((start, x)) if x.len() == 20
2396 && start == ten_bytes_past_end
2397 && x.iter().all(|ch| *ch == 2)));
2398
2399 txb.mark_as_sent(ten_bytes_past_end, 20);
2400
2401 // Get bit after earlier marked range A
2402 assert!(matches!(txb.next_bytes(),
2403 Some((start, x)) if x.len() == 60
2404 && start == range_a_end
2405 && x.iter().all(|ch| *ch == 2)));
2406
2407 // No more bytes.
2408 txb.mark_as_sent(range_a_end, 60);
2409 assert!(txb.next_bytes().is_none());
2410 }
2411
2412 #[test]
2413 fn stream_tx() {
2414 let conn_fc = connection_fc(4096);
2415 let conn_events = ConnectionEvents::default();
2416
2417 let mut s = SendStream::new(4.into(), 1024, Rc::clone(&conn_fc), conn_events);
2418
2419 let res = s.send(&[4; 100]).unwrap();
2420 assert_eq!(res, 100);
2421 s.mark_as_sent(0, 50, false);
2422 if let SendStreamState::Send { fc, .. } = s.state() {
2423 assert_eq!(fc.used(), 100);
2424 } else {
2425 panic!("unexpected stream state");
2426 }
2427
2428 // Should hit stream flow control limit before filling up send buffer
2429 let big_buf = vec![4; INITIAL_RECV_WINDOW_SIZE + 100];
2430 let res = s.send(&big_buf[..INITIAL_RECV_WINDOW_SIZE]).unwrap();
2431 assert_eq!(res, 1024 - 100);
2432
2433 // should do nothing, max stream data already 1024
2434 s.set_max_stream_data(1024);
2435 let res = s.send(&big_buf[..INITIAL_RECV_WINDOW_SIZE]).unwrap();
2436 assert_eq!(res, 0);
2437
2438 // should now hit the conn flow control (4096)
2439 s.set_max_stream_data(1_048_576);
2440 let res = s.send(&big_buf[..INITIAL_RECV_WINDOW_SIZE]).unwrap();
2441 assert_eq!(res, 3072);
2442
2443 // should now hit the tx buffer size
2444 conn_fc.borrow_mut().update(INITIAL_RECV_WINDOW_SIZE as u64);
2445 let res = s.send(&big_buf).unwrap();
2446 assert_eq!(res, INITIAL_RECV_WINDOW_SIZE - 4096);
2447
2448 // TODO([email protected]): test ooo acks somehow
2449 s.mark_as_acked(0, 40, false);
2450 }
2451
2452 #[test]
2453 fn tx_buffer_acks() {
2454 let mut tx = TxBuffer::new();
2455 assert_eq!(tx.send(&[4; 100]), 100);
2456 let res = tx.next_bytes().unwrap();
2457 assert_eq!(res.0, 0);
2458 assert_eq!(res.1.len(), 100);
2459 tx.mark_as_sent(0, 100);
2460 let res = tx.next_bytes();
2461 assert_eq!(res, None);
2462
2463 tx.mark_as_acked(0, 100);
2464 let res = tx.next_bytes();
2465 assert_eq!(res, None);
2466 }
2467
2468 #[test]
2469 fn send_stream_writable_event_gen() {
2470 let conn_fc = connection_fc(2);
2471 let mut conn_events = ConnectionEvents::default();
2472
2473 let mut s = SendStream::new(4.into(), 0, Rc::clone(&conn_fc), conn_events.clone());
2474
2475 // Stream is initially blocked (conn:2, stream:0)
2476 // and will not accept data.
2477 assert_eq!(s.send(b"hi").unwrap(), 0);
2478
2479 // increasing to (conn:2, stream:2) will allow 2 bytes, and also
2480 // generate a SendStreamWritable event.
2481 s.set_max_stream_data(2);
2482 let evts = conn_events.events().collect::<Vec<_>>();
2483 assert_eq!(evts.len(), 1);
2484 assert!(matches!(
2485 evts[0],
2486 ConnectionEvent::SendStreamWritable { .. }
2487 ));
2488 assert_eq!(s.send(b"hello").unwrap(), 2);
2489
2490 // increasing to (conn:2, stream:4) will not generate an event or allow
2491 // sending anything.
2492 s.set_max_stream_data(4);
2493 assert_eq!(conn_events.events().count(), 0);
2494 assert_eq!(s.send(b"hello").unwrap(), 0);
2495
2496 // Increasing conn max (conn:4, stream:4) will unblock but not emit
2497 // event b/c that happens in Connection::emit_frame() (tested in
2498 // connection.rs)
2499 assert!(conn_fc.borrow_mut().update(4).is_some());
2500 assert_eq!(conn_events.events().count(), 0);
2501 assert_eq!(s.avail(), 2);
2502 assert_eq!(s.send(b"hello").unwrap(), 2);
2503
2504 // No event because still blocked by conn
2505 s.set_max_stream_data(1_000_000_000);
2506 assert_eq!(conn_events.events().count(), 0);
2507
2508 // No event because happens in emit_frame()
2509 conn_fc.borrow_mut().update(1_000_000_000);
2510 assert_eq!(conn_events.events().count(), 0);
2511
2512 let big_buf = vec![b'a'; INITIAL_RECV_WINDOW_SIZE];
2513 assert_eq!(s.send(&big_buf).unwrap(), INITIAL_RECV_WINDOW_SIZE);
2514 }
2515
2516 #[test]
2517 fn send_stream_writable_event_gen_with_watermark() {
2518 let conn_fc = connection_fc(0);
2519 let mut conn_events = ConnectionEvents::default();
2520
2521 let mut s = SendStream::new(4.into(), 0, Rc::clone(&conn_fc), conn_events.clone());
2522 // Set watermark at 3.
2523 s.set_writable_event_low_watermark(NonZeroUsize::new(3).unwrap());
2524
2525 // Stream is initially blocked (conn:0, stream:0, watermark: 3) and will
2526 // not accept data.
2527 assert_eq!(s.avail(), 0);
2528 assert_eq!(s.send(b"hi!").unwrap(), 0);
2529
2530 // Increasing the connection limit (conn:10, stream:0, watermark: 3) will not generate
2531 // event or allow sending anything. Stream is constrained by stream limit.
2532 assert!(conn_fc.borrow_mut().update(10).is_some());
2533 assert_eq!(s.avail(), 0);
2534 assert_eq!(conn_events.events().count(), 0);
2535
2536 // Increasing the connection limit further (conn:11, stream:0, watermark: 3) will not
2537 // generate event or allow sending anything. Stream wasn't constrained by connection
2538 // limit before.
2539 assert!(conn_fc.borrow_mut().update(11).is_some());
2540 assert_eq!(s.avail(), 0);
2541 assert_eq!(conn_events.events().count(), 0);
2542
2543 // Increasing to (conn:11, stream:2, watermark: 3) will allow 2 bytes
2544 // but not generate a SendStreamWritable event as it is still below the
2545 // configured watermark.
2546 s.set_max_stream_data(2);
2547 assert_eq!(conn_events.events().count(), 0);
2548 assert_eq!(s.avail(), 2);
2549
2550 // Increasing to (conn:11, stream:3, watermark: 3) will generate an
2551 // event as available sendable bytes are >= watermark.
2552 s.set_max_stream_data(3);
2553 let evts = conn_events.events().collect::<Vec<_>>();
2554 assert_eq!(evts.len(), 1);
2555 assert!(matches!(
2556 evts[0],
2557 ConnectionEvent::SendStreamWritable { .. }
2558 ));
2559
2560 assert_eq!(s.send(b"hi!").unwrap(), 3);
2561 }
2562
2563 #[test]
2564 fn send_stream_writable_event_new_stream() {
2565 let conn_fc = connection_fc(2);
2566 let mut conn_events = ConnectionEvents::default();
2567
2568 let _s = SendStream::new(4.into(), 100, conn_fc, conn_events.clone());
2569
2570 // Creating a new stream with conn and stream credits should result in
2571 // an event.
2572 let evts = conn_events.events().collect::<Vec<_>>();
2573 assert_eq!(evts.len(), 1);
2574 assert!(matches!(
2575 evts[0],
2576 ConnectionEvent::SendStreamWritable { .. }
2577 ));
2578 }
2579
2580 const fn as_stream_token(t: &RecoveryToken) -> &SendStreamRecoveryToken {
2581 if let RecoveryToken::Stream(StreamRecoveryToken::Stream(rt)) = &t {
2582 rt
2583 } else {
2584 panic!();
2585 }
2586 }
2587
2588 #[test]
2589 // Verify lost frames handle fin properly
2590 fn send_stream_get_frame_data() {
2591 let conn_fc = connection_fc(100);
2592 let conn_events = ConnectionEvents::default();
2593
2594 let mut s = SendStream::new(0.into(), 100, conn_fc, conn_events);
2595 s.send(&[0; 10]).unwrap();
2596 s.close();
2597
2598 let mut ss = SendStreams::default();
2599 ss.insert(StreamId::from(0), s);
2600
2601 let mut tokens = Vec::new();
2602 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
2603
2604 // Write a small frame: no fin.
2605 let written = builder.len();
2606 builder.set_limit(written + 6);
2607 ss.write_frames(
2608 TransmissionPriority::default(),
2609 &mut builder,
2610 &mut tokens,
2611 &mut FrameStats::default(),
2612 );
2613 assert_eq!(builder.len(), written + 6);
2614 assert_eq!(tokens.len(), 1);
2615 let f1_token = tokens.remove(0);
2616 assert!(!as_stream_token(&f1_token).fin);
2617
2618 // Write the rest: fin.
2619 let written = builder.len();
2620 builder.set_limit(written + 200);
2621 ss.write_frames(
2622 TransmissionPriority::default(),
2623 &mut builder,
2624 &mut tokens,
2625 &mut FrameStats::default(),
2626 );
2627 assert_eq!(builder.len(), written + 10);
2628 assert_eq!(tokens.len(), 1);
2629 let f2_token = tokens.remove(0);
2630 assert!(as_stream_token(&f2_token).fin);
2631
2632 // Should be no more data to frame.
2633 let written = builder.len();
2634 ss.write_frames(
2635 TransmissionPriority::default(),
2636 &mut builder,
2637 &mut tokens,
2638 &mut FrameStats::default(),
2639 );
2640 assert_eq!(builder.len(), written);
2641 assert!(tokens.is_empty());
2642
2643 // Mark frame 1 as lost
2644 ss.lost(as_stream_token(&f1_token));
2645
2646 // Next frame should not set fin even though stream has fin but frame
2647 // does not include end of stream
2648 let written = builder.len();
2649 ss.write_frames(
2650 TransmissionPriority::default() + RetransmissionPriority::default(),
2651 &mut builder,
2652 &mut tokens,
2653 &mut FrameStats::default(),
2654 );
2655 assert_eq!(builder.len(), written + 7); // Needs a length this time.
2656 assert_eq!(tokens.len(), 1);
2657 let f4_token = tokens.remove(0);
2658 assert!(!as_stream_token(&f4_token).fin);
2659
2660 // Mark frame 2 as lost
2661 ss.lost(as_stream_token(&f2_token));
2662
2663 // Next frame should set fin because it includes end of stream
2664 let written = builder.len();
2665 ss.write_frames(
2666 TransmissionPriority::default() + RetransmissionPriority::default(),
2667 &mut builder,
2668 &mut tokens,
2669 &mut FrameStats::default(),
2670 );
2671 assert_eq!(builder.len(), written + 10);
2672 assert_eq!(tokens.len(), 1);
2673 let f5_token = tokens.remove(0);
2674 assert!(as_stream_token(&f5_token).fin);
2675 }
2676
2677 #[test]
2678 // Verify lost frames handle fin properly with zero length fin
2679 fn send_stream_get_frame_zerolength_fin() {
2680 let conn_fc = connection_fc(100);
2681 let conn_events = ConnectionEvents::default();
2682
2683 let mut s = SendStream::new(0.into(), 100, conn_fc, conn_events);
2684 s.send(&[0; 10]).unwrap();
2685
2686 let mut ss = SendStreams::default();
2687 ss.insert(StreamId::from(0), s);
2688
2689 let mut tokens = Vec::new();
2690 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
2691 ss.write_frames(
2692 TransmissionPriority::default(),
2693 &mut builder,
2694 &mut tokens,
2695 &mut FrameStats::default(),
2696 );
2697 let f1_token = tokens.remove(0);
2698 assert_eq!(as_stream_token(&f1_token).offset, 0);
2699 assert_eq!(as_stream_token(&f1_token).length, 10);
2700 assert!(!as_stream_token(&f1_token).fin);
2701
2702 // Should be no more data to frame
2703 ss.write_frames(
2704 TransmissionPriority::default(),
2705 &mut builder,
2706 &mut tokens,
2707 &mut FrameStats::default(),
2708 );
2709 assert!(tokens.is_empty());
2710
2711 ss.get_mut(StreamId::from(0)).unwrap().close();
2712
2713 ss.write_frames(
2714 TransmissionPriority::default(),
2715 &mut builder,
2716 &mut tokens,
2717 &mut FrameStats::default(),
2718 );
2719 let f2_token = tokens.remove(0);
2720 assert_eq!(as_stream_token(&f2_token).offset, 10);
2721 assert_eq!(as_stream_token(&f2_token).length, 0);
2722 assert!(as_stream_token(&f2_token).fin);
2723
2724 // Mark frame 2 as lost
2725 ss.lost(as_stream_token(&f2_token));
2726
2727 // Next frame should set fin
2728 ss.write_frames(
2729 TransmissionPriority::default(),
2730 &mut builder,
2731 &mut tokens,
2732 &mut FrameStats::default(),
2733 );
2734 let f3_token = tokens.remove(0);
2735 assert_eq!(as_stream_token(&f3_token).offset, 10);
2736 assert_eq!(as_stream_token(&f3_token).length, 0);
2737 assert!(as_stream_token(&f3_token).fin);
2738
2739 // Mark frame 1 as lost
2740 ss.lost(as_stream_token(&f1_token));
2741
2742 // Next frame should set fin and include all data
2743 ss.write_frames(
2744 TransmissionPriority::default(),
2745 &mut builder,
2746 &mut tokens,
2747 &mut FrameStats::default(),
2748 );
2749 let f4_token = tokens.remove(0);
2750 assert_eq!(as_stream_token(&f4_token).offset, 0);
2751 assert_eq!(as_stream_token(&f4_token).length, 10);
2752 assert!(as_stream_token(&f4_token).fin);
2753 }
2754
2755 #[test]
2756 fn data_blocked() {
2757 let conn_fc = connection_fc(5);
2758 let conn_events = ConnectionEvents::default();
2759
2760 let stream_id = StreamId::from(4);
2761 let mut s = SendStream::new(stream_id, 2, Rc::clone(&conn_fc), conn_events);
2762
2763 // Only two bytes can be sent due to the stream limit.
2764 assert_eq!(s.send(b"abc").unwrap(), 2);
2765 assert_eq!(s.next_bytes(false), Some((0, &b"ab"[..])));
2766
2767 // This doesn't report blocking yet.
2768 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
2769 let mut tokens = Vec::new();
2770 let mut stats = FrameStats::default();
2771 s.write_blocked_frame(
2772 TransmissionPriority::default(),
2773 &mut builder,
2774 &mut tokens,
2775 &mut stats,
2776 );
2777 assert_eq!(stats.stream_data_blocked, 0);
2778
2779 // Blocking is reported after sending the last available credit.
2780 s.mark_as_sent(0, 2, false);
2781 s.write_blocked_frame(
2782 TransmissionPriority::default(),
2783 &mut builder,
2784 &mut tokens,
2785 &mut stats,
2786 );
2787 assert_eq!(stats.stream_data_blocked, 1);
2788
2789 // Now increase the stream limit and test the connection limit.
2790 s.set_max_stream_data(10);
2791
2792 assert_eq!(s.send(b"abcd").unwrap(), 3);
2793 assert_eq!(s.next_bytes(false), Some((2, &b"abc"[..])));
2794 // DATA_BLOCKED is not sent yet.
2795 conn_fc
2796 .borrow_mut()
2797 .write_frames(&mut builder, &mut tokens, &mut stats);
2798 assert_eq!(stats.data_blocked, 0);
2799
2800 // DATA_BLOCKED is queued once bytes using all credit are sent.
2801 s.mark_as_sent(2, 3, false);
2802 conn_fc
2803 .borrow_mut()
2804 .write_frames(&mut builder, &mut tokens, &mut stats);
2805 assert_eq!(stats.data_blocked, 1);
2806 }
2807
2808 #[test]
2809 fn max_send_buffer_size() {
2810 // Huge FC limit. Thus buffer size limited only.
2811 const FC_LIMIT: u64 = 1024 * 1024 * 1024;
2812 let s = SendStream::new(
2813 StreamId::from(4),
2814 FC_LIMIT,
2815 connection_fc(FC_LIMIT),
2816 ConnectionEvents::default(),
2817 );
2818 assert_eq!(s.avail(), MAX_SEND_BUFFER_SIZE);
2819 }
2820
2821 #[test]
2822 fn data_blocked_atomic() {
2823 let conn_fc = connection_fc(5);
2824 let conn_events = ConnectionEvents::default();
2825
2826 let stream_id = StreamId::from(4);
2827 let mut s = SendStream::new(stream_id, 2, Rc::clone(&conn_fc), conn_events);
2828
2829 // Stream is initially blocked (conn:5, stream:2)
2830 // and will not accept atomic write of 3 bytes.
2831 assert_eq!(s.send_atomic(b"abc").unwrap(), 0);
2832
2833 // Assert that STREAM_DATA_BLOCKED is sent.
2834 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
2835 let mut tokens = Vec::new();
2836 let mut stats = FrameStats::default();
2837 s.write_blocked_frame(
2838 TransmissionPriority::default(),
2839 &mut builder,
2840 &mut tokens,
2841 &mut stats,
2842 );
2843 assert_eq!(stats.stream_data_blocked, 1);
2844
2845 // Assert that a non-atomic write works.
2846 assert_eq!(s.send(b"abc").unwrap(), 2);
2847 assert_eq!(s.next_bytes(false), Some((0, &b"ab"[..])));
2848 s.mark_as_sent(0, 2, false);
2849
2850 // Set limits to (conn:5, stream:10).
2851 s.set_max_stream_data(10);
2852
2853 // An atomic write of 4 bytes exceeds the remaining limit of 3.
2854 assert_eq!(s.send_atomic(b"abcd").unwrap(), 0);
2855
2856 // Assert that DATA_BLOCKED is sent.
2857 conn_fc
2858 .borrow_mut()
2859 .write_frames(&mut builder, &mut tokens, &mut stats);
2860 assert_eq!(stats.data_blocked, 1);
2861
2862 // Check that a non-atomic write works.
2863 assert_eq!(s.send(b"abcd").unwrap(), 3);
2864 assert_eq!(s.next_bytes(false), Some((2, &b"abc"[..])));
2865 s.mark_as_sent(2, 3, false);
2866
2867 // Increase limits to (conn:15, stream:15).
2868 s.set_max_stream_data(15);
2869 conn_fc.borrow_mut().update(15);
2870
2871 // Check that atomic writing right up to the limit works.
2872 assert_eq!(s.send_atomic(b"abcdefghij").unwrap(), 10);
2873 }
2874
2875 #[test]
2876 fn ack_fin_first() {
2877 const MESSAGE: &[u8] = b"hello";
2878 let len_u64 = u64::try_from(MESSAGE.len()).unwrap();
2879
2880 let conn_fc = connection_fc(len_u64);
2881 let conn_events = ConnectionEvents::default();
2882
2883 let mut s = SendStream::new(StreamId::new(100), 0, conn_fc, conn_events);
2884 s.set_max_stream_data(len_u64);
2885
2886 // Send all the data, then the fin.
2887 _ = s.send(MESSAGE).unwrap();
2888 s.mark_as_sent(0, MESSAGE.len(), false);
2889 s.close();
2890 s.mark_as_sent(len_u64, 0, true);
2891
2892 // Ack the fin, then the data.
2893 s.mark_as_acked(len_u64, 0, true);
2894 s.mark_as_acked(0, MESSAGE.len(), false);
2895 assert!(s.is_terminal());
2896 }
2897
2898 #[test]
2899 fn ack_then_lose_fin() {
2900 const MESSAGE: &[u8] = b"hello";
2901 let len_u64 = u64::try_from(MESSAGE.len()).unwrap();
2902
2903 let conn_fc = connection_fc(len_u64);
2904 let conn_events = ConnectionEvents::default();
2905
2906 let id = StreamId::new(100);
2907 let mut s = SendStream::new(id, 0, conn_fc, conn_events);
2908 s.set_max_stream_data(len_u64);
2909
2910 // Send all the data, then the fin.
2911 _ = s.send(MESSAGE).unwrap();
2912 s.mark_as_sent(0, MESSAGE.len(), false);
2913 s.close();
2914 s.mark_as_sent(len_u64, 0, true);
2915
2916 // Ack the fin, then mark it lost.
2917 s.mark_as_acked(len_u64, 0, true);
2918 s.mark_as_lost(len_u64, 0, true);
2919
2920 // No frame should be sent here.
2921 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
2922 let mut tokens = Vec::new();
2923 let mut stats = FrameStats::default();
2924 s.write_stream_frame(
2925 TransmissionPriority::default(),
2926 &mut builder,
2927 &mut tokens,
2928 &mut stats,
2929 );
2930 assert_eq!(stats.stream, 0);
2931 }
2932
2933 /// Create a `SendStream` and force it into a state where it believes that
2934 /// `offset` bytes have already been sent and acknowledged.
2935 fn stream_with_sent(stream: u64, offset: usize) -> SendStream {
2936 let conn_fc = connection_fc(MAX_VARINT);
2937 let mut s = SendStream::new(
2938 StreamId::from(stream),
2939 MAX_VARINT,
2940 conn_fc,
2941 ConnectionEvents::default(),
2942 );
2943
2944 let mut send_buf = TxBuffer::new();
2945 send_buf.ranges.mark_acked(0, offset);
2946 let mut fc = SenderFlowControl::new(StreamId::from(stream), MAX_VARINT);
2947 fc.consume(offset);
2948 let conn_fc = Rc::new(RefCell::new(SenderFlowControl::new((), MAX_VARINT)));
2949 s.state = SendStreamState::Send {
2950 fc,
2951 conn_fc,
2952 send_buf,
2953 };
2954 s
2955 }
2956
2957 fn frame_sent_sid(stream: u64, offset: usize, len: usize, fin: bool, space: usize) -> bool {
2958 const BUF: &[u8] = &[0x42; 128];
2959
2960 qtrace!("frame_sent stream={stream} offset={offset} len={len} fin={fin}, space={space}");
2961
2962 let mut s = stream_with_sent(stream, offset);
2963
2964 // Now write out the proscribed data and maybe close.
2965 if len > 0 {
2966 s.send(&BUF[..len]).unwrap();
2967 }
2968 if fin {
2969 s.close();
2970 }
2971
2972 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
2973 let header_len = builder.len();
2974 builder.set_limit(header_len + space);
2975
2976 let mut tokens = Vec::new();
2977 let mut stats = FrameStats::default();
2978 s.write_stream_frame(
2979 TransmissionPriority::default(),
2980 &mut builder,
2981 &mut tokens,
2982 &mut stats,
2983 );
2984 qtrace!(
2985 "STREAM frame: {}",
2986 hex_with_len(&builder.as_ref()[header_len..])
2987 );
2988 stats.stream > 0
2989 }
2990
2991 fn frame_sent(offset: usize, len: usize, fin: bool, space: usize) -> bool {
2992 frame_sent_sid(0, offset, len, fin, space)
2993 }
2994
2995 #[test]
2996 fn stream_frame_empty() {
2997 // Stream frames with empty data and no fin never work.
2998 assert!(!frame_sent(10, 0, false, 2));
2999 assert!(!frame_sent(10, 0, false, 3));
3000 assert!(!frame_sent(10, 0, false, 4));
3001 assert!(!frame_sent(10, 0, false, 5));
3002 assert!(!frame_sent(10, 0, false, 100));
3003
3004 // Empty data with fin is only a problem if there is no space.
3005 assert!(!frame_sent(0, 0, true, 1));
3006 assert!(frame_sent(0, 0, true, 2));
3007 assert!(!frame_sent(10, 0, true, 2));
3008 assert!(frame_sent(10, 0, true, 3));
3009 assert!(frame_sent(10, 0, true, 4));
3010 assert!(frame_sent(10, 0, true, 5));
3011 assert!(frame_sent(10, 0, true, 100));
3012 }
3013
3014 #[test]
3015 fn stream_frame_minimum() {
3016 // Add minimum data
3017 assert!(!frame_sent(10, 1, false, 3));
3018 assert!(!frame_sent(10, 1, true, 3));
3019 assert!(frame_sent(10, 1, false, 4));
3020 assert!(frame_sent(10, 1, true, 4));
3021 assert!(frame_sent(10, 1, false, 5));
3022 assert!(frame_sent(10, 1, true, 5));
3023 assert!(frame_sent(10, 1, false, 100));
3024 assert!(frame_sent(10, 1, true, 100));
3025 }
3026
3027 #[test]
3028 fn stream_frame_more() {
3029 // Try more data
3030 assert!(!frame_sent(10, 100, false, 3));
3031 assert!(!frame_sent(10, 100, true, 3));
3032 assert!(frame_sent(10, 100, false, 4));
3033 assert!(frame_sent(10, 100, true, 4));
3034 assert!(frame_sent(10, 100, false, 5));
3035 assert!(frame_sent(10, 100, true, 5));
3036 assert!(frame_sent(10, 100, false, 100));
3037 assert!(frame_sent(10, 100, true, 100));
3038
3039 assert!(frame_sent(10, 100, false, 1000));
3040 assert!(frame_sent(10, 100, true, 1000));
3041 }
3042
3043 #[test]
3044 fn stream_frame_big_id() {
3045 // A value that encodes to the largest varint.
3046 const BIG: u64 = 1 << 30;
3047 const BIGSZ: usize = 1 << 30;
3048
3049 assert!(!frame_sent_sid(BIG, BIGSZ, 0, false, 16));
3050 assert!(!frame_sent_sid(BIG, BIGSZ, 0, true, 16));
3051 assert!(!frame_sent_sid(BIG, BIGSZ, 0, false, 17));
3052 assert!(frame_sent_sid(BIG, BIGSZ, 0, true, 17));
3053 assert!(!frame_sent_sid(BIG, BIGSZ, 0, false, 18));
3054 assert!(frame_sent_sid(BIG, BIGSZ, 0, true, 18));
3055
3056 assert!(!frame_sent_sid(BIG, BIGSZ, 1, false, 17));
3057 assert!(!frame_sent_sid(BIG, BIGSZ, 1, true, 17));
3058 assert!(frame_sent_sid(BIG, BIGSZ, 1, false, 18));
3059 assert!(frame_sent_sid(BIG, BIGSZ, 1, true, 18));
3060 assert!(frame_sent_sid(BIG, BIGSZ, 1, false, 19));
3061 assert!(frame_sent_sid(BIG, BIGSZ, 1, true, 19));
3062 assert!(frame_sent_sid(BIG, BIGSZ, 1, false, 100));
3063 assert!(frame_sent_sid(BIG, BIGSZ, 1, true, 100));
3064 }
3065
3066 fn stream_frame_at_boundary(data: &[u8]) {
3067 fn send_with_extra_capacity(data: &[u8], extra: usize, expect_full: bool) -> Vec<u8> {
3068 qtrace!("send_with_extra_capacity {} + {extra}", data.len());
3069 let mut s = stream_with_sent(0, 0);
3070 s.send(data).unwrap();
3071 s.close();
3072
3073 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
3074 let header_len = builder.len();
3075 // Add 2 for the frame type and stream ID, then add the extra.
3076 builder.set_limit(header_len + data.len() + 2 + extra);
3077 let mut tokens = Vec::new();
3078 let mut stats = FrameStats::default();
3079 s.write_stream_frame(
3080 TransmissionPriority::default(),
3081 &mut builder,
3082 &mut tokens,
3083 &mut stats,
3084 );
3085 assert_eq!(stats.stream, 1);
3086 assert_eq!(builder.is_full(), expect_full);
3087 Vec::from(Encoder::from(builder)).split_off(header_len)
3088 }
3089
3090 // The minimum amount of extra space for getting another frame in.
3091 let mut enc = Encoder::new();
3092 enc.encode_varint(u64::try_from(data.len()).unwrap());
3093 let len_buf = Vec::from(enc);
3094 let minimum_extra = len_buf.len() + PacketBuilder::MINIMUM_FRAME_SIZE;
3095
3096 // For anything short of the minimum extra, the frame should fill the packet.
3097 for i in 0..minimum_extra {
3098 let frame = send_with_extra_capacity(data, i, true);
3099 let (header, body) = frame.split_at(2);
3100 assert_eq!(header, &[0b1001, 0]);
3101 assert_eq!(body, data);
3102 }
3103
3104 // Once there is space for another packet AND a length field,
3105 // then a length will be added.
3106 let frame = send_with_extra_capacity(data, minimum_extra, false);
3107 let (header, rest) = frame.split_at(2);
3108 assert_eq!(header, &[0b1011, 0]);
3109 let (len, body) = rest.split_at(len_buf.len());
3110 assert_eq!(len, &len_buf);
3111 assert_eq!(body, data);
3112 }
3113
3114 /// 16383/16384 is an odd boundary in STREAM frame construction.
3115 /// That is the boundary where a length goes from 2 bytes to 4 bytes.
3116 /// Test that we correctly add a length field to the frame; and test
3117 /// that if we don't, then we don't allow other frames to be added.
3118 #[test]
3119 fn stream_frame_16384() {
3120 stream_frame_at_boundary(&[4; 16383]);
3121 stream_frame_at_boundary(&[4; 16384]);
3122 }
3123
3124 /// 63/64 is the other odd boundary.
3125 #[test]
3126 fn stream_frame_64() {
3127 stream_frame_at_boundary(&[2; 63]);
3128 stream_frame_at_boundary(&[2; 64]);
3129 }
3130
3131 fn check_stats(
3132 stream: &SendStream,
3133 expected_written: u64,
3134 expected_sent: u64,
3135 expected_acked: u64,
3136 ) {
3137 let stream_stats = stream.stats();
3138 assert_eq!(stream_stats.bytes_written(), expected_written);
3139 assert_eq!(stream_stats.bytes_sent(), expected_sent);
3140 assert_eq!(stream_stats.bytes_acked(), expected_acked);
3141 }
3142
3143 #[test]
3144 fn send_stream_stats() {
3145 const MESSAGE: &[u8] = b"hello";
3146 let len_u64 = u64::try_from(MESSAGE.len()).unwrap();
3147
3148 let conn_fc = connection_fc(len_u64);
3149 let conn_events = ConnectionEvents::default();
3150
3151 let id = StreamId::new(100);
3152 let mut s = SendStream::new(id, 0, conn_fc, conn_events);
3153 s.set_max_stream_data(len_u64);
3154
3155 // Initial stats should be all 0.
3156 check_stats(&s, 0, 0, 0);
3157 // Adter sending the data, bytes_written should be increased.
3158 _ = s.send(MESSAGE).unwrap();
3159 check_stats(&s, len_u64, 0, 0);
3160
3161 // Adter calling mark_as_sent, bytes_sent should be increased.
3162 s.mark_as_sent(0, MESSAGE.len(), false);
3163 check_stats(&s, len_u64, len_u64, 0);
3164
3165 s.close();
3166 s.mark_as_sent(len_u64, 0, true);
3167
3168 // In the end, check bytes_acked.
3169 s.mark_as_acked(0, MESSAGE.len(), false);
3170 check_stats(&s, len_u64, len_u64, len_u64);
3171
3172 s.mark_as_acked(len_u64, 0, true);
3173 assert!(s.is_terminal());
3174 }
3175 }