Skip to main content

quiche/stream/
mod.rs

1// Copyright (C) 2018-2019, Cloudflare, Inc.
2// All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8//     * Redistributions of source code must retain the above copyright notice,
9//       this list of conditions and the following disclaimer.
10//
11//     * Redistributions in binary form must reproduce the above copyright
12//       notice, this list of conditions and the following disclaimer in the
13//       documentation and/or other materials provided with the distribution.
14//
15// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
16// IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
17// THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
18// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
19// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
20// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
21// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26
27use std::cmp;
28
29use std::sync::Arc;
30
31use std::collections::hash_map;
32use std::collections::HashMap;
33use std::collections::HashSet;
34
35use intrusive_collections::intrusive_adapter;
36use intrusive_collections::KeyAdapter;
37use intrusive_collections::RBTree;
38use intrusive_collections::RBTreeAtomicLink;
39
40use smallvec::SmallVec;
41
42use crate::buffers::DefaultBufFactory;
43use crate::ranges::RangeSet;
44use crate::BufFactory;
45use crate::Error;
46use crate::Result;
47
48pub(crate) use self::send_buf::PeerStopSendingState;
49
50const DEFAULT_URGENCY: u8 = 127;
51
52/// The maximum size of the receiver stream flow control window.
53pub const MAX_STREAM_WINDOW: u64 = 16 * 1024 * 1024;
54
55/// A simple no-op hasher for Stream IDs.
56///
57/// The QUIC protocol and quiche library guarantees stream ID uniqueness, so
58/// we can save effort by avoiding using a more complicated algorithm.
59#[derive(Default)]
60pub struct StreamIdHasher {
61    id: u64,
62}
63
64/// Return value type of `RecvBuf::reset()`
65#[derive(Debug, PartialEq, Clone, Copy)]
66pub struct RecvBufResetReturn {
67    /// Returns the difference between the previous max_data offset
68    /// received and the final size reported by the reset
69    pub max_data_delta: u64,
70
71    /// The amount of flow control credit that should be returned to the
72    /// connection level flow control.
73    pub consumed_flowcontrol: u64,
74}
75
76impl RecvBufResetReturn {
77    pub fn zero() -> Self {
78        Self {
79            max_data_delta: 0,
80            consumed_flowcontrol: 0,
81        }
82    }
83}
84
85/// Action to perform when reading from a stream's receive buffer.
86pub enum RecvAction<T: bytes::BufMut> {
87    /// Emit data by copying it into the provided buffer.
88    Emit { out: T },
89    /// Discard up to the specified number of bytes without copying.
90    Discard { len: usize },
91}
92
93impl std::hash::Hasher for StreamIdHasher {
94    #[inline]
95    fn finish(&self) -> u64 {
96        self.id
97    }
98
99    #[inline]
100    fn write_u64(&mut self, id: u64) {
101        self.id = id;
102    }
103
104    #[inline]
105    fn write(&mut self, _: &[u8]) {
106        // We need a default write() for the trait but stream IDs will always
107        // be a u64 so we just delegate to write_u64.
108        unimplemented!()
109    }
110}
111
112type BuildStreamIdHasher = std::hash::BuildHasherDefault<StreamIdHasher>;
113
114pub type StreamIdHashMap<V> = HashMap<u64, V, BuildStreamIdHasher>;
115pub type StreamIdHashSet = HashSet<u64, BuildStreamIdHasher>;
116
117/// Tracks collected stream sequences separately for each stream type.
118#[derive(Default)]
119struct CollectedStreams {
120    // Defer allocation until the first stream is collected. The range capacity
121    // is unlimited because evicting a tombstone would allow a collected stream
122    // to be recreated.
123    ranges: Option<Box<[RangeSet; 4]>>,
124}
125
126impl CollectedStreams {
127    fn insert(&mut self, stream_id: u64) {
128        // Same-type stream IDs advance by four, so store their sequences to
129        // allow adjacent collected streams to merge into a single range.
130        let ranges = self.ranges.get_or_insert_with(Default::default);
131        ranges[(stream_id & 0x3) as usize].push_item(stream_id >> 2);
132    }
133
134    fn contains(&self, stream_id: u64) -> bool {
135        let Some(ranges) = &self.ranges else {
136            return false;
137        };
138
139        ranges[(stream_id & 0x3) as usize].contains(stream_id >> 2)
140    }
141}
142
143/// Keeps track of QUIC streams and enforces stream limits.
144#[derive(Default)]
145pub struct StreamMap<F: BufFactory = DefaultBufFactory> {
146    /// Map of streams indexed by stream ID.
147    streams: StreamIdHashMap<Stream<F>>,
148
149    /// Set of streams that were completed and garbage collected.
150    ///
151    /// Instead of keeping the full stream state forever, we collect completed
152    /// streams to save memory, but we still need to keep track of previously
153    /// created streams, to prevent peers from re-creating them.
154    collected: CollectedStreams,
155
156    /// Peer's maximum bidirectional stream count limit.
157    peer_max_streams_bidi: u64,
158
159    /// Peer's maximum unidirectional stream count limit.
160    peer_max_streams_uni: u64,
161
162    /// The total number of bidirectional streams opened by the peer.
163    peer_opened_streams_bidi: u64,
164
165    /// The total number of unidirectional streams opened by the peer.
166    peer_opened_streams_uni: u64,
167
168    /// Local maximum bidirectional stream count limit.
169    local_max_streams_bidi: u64,
170    local_max_streams_bidi_next: u64,
171
172    /// Initial maximum bidirectional stream count.
173    initial_max_streams_bidi: u64,
174
175    /// Local maximum unidirectional stream count limit.
176    local_max_streams_uni: u64,
177    local_max_streams_uni_next: u64,
178
179    /// Initial maximum unidirectional stream count.
180    initial_max_streams_uni: u64,
181
182    /// The total number of bidirectional streams opened by the local endpoint.
183    local_opened_streams_bidi: u64,
184
185    /// The total number of unidirectional streams opened by the local endpoint.
186    local_opened_streams_uni: u64,
187
188    /// Queue of stream IDs corresponding to streams that have buffered data
189    /// ready to be sent to the peer. This also implies that the stream has
190    /// enough flow control credits to send at least some of that data.
191    flushable: RBTree<StreamFlushablePriorityAdapter>,
192
193    /// Set of stream IDs corresponding to streams that have outstanding data
194    /// to read. This is used to generate a `StreamIter` of streams without
195    /// having to iterate over the full list of streams.
196    pub readable: RBTree<StreamReadablePriorityAdapter>,
197
198    /// Set of streams queued for writable notification. A stopped stream can
199    /// be removed before its error is reported to the application.
200    pub writable: RBTree<StreamWritablePriorityAdapter>,
201
202    /// Stopped streams still queued for writable notification.
203    stopped_writable: RBTree<StreamStoppedWritablePriorityAdapter>,
204
205    /// Set of stream IDs corresponding to streams that are almost out of flow
206    /// control credit and need to send MAX_STREAM_DATA. This is used to
207    /// generate a `StreamIter` of streams without having to iterate over the
208    /// full list of streams.
209    almost_full: StreamIdHashSet,
210
211    /// Set of stream IDs corresponding to streams that are blocked. The value
212    /// of the map elements represents the offset of the stream at which the
213    /// blocking occurred.
214    blocked: StreamIdHashMap<u64>,
215
216    /// Set of stream IDs corresponding to streams that are reset. The value
217    /// of the map elements is a tuple of the error code and final size values
218    /// to include in the RESET_STREAM frame.
219    reset: StreamIdHashMap<(u64, u64)>,
220
221    /// Set of stream IDs corresponding to streams that are shutdown on the
222    /// receive side, and need to send a STOP_SENDING frame. The value of the
223    /// map elements is the error code to include in the STOP_SENDING frame.
224    stopped: StreamIdHashMap<u64>,
225
226    /// The maximum size of a stream window.
227    max_stream_window: u64,
228
229    /// Total number of bytes in send buffers across all streams.
230    tx_buffered: usize,
231}
232
233impl<F: BufFactory> StreamMap<F> {
234    pub fn new(
235        max_streams_bidi: u64, max_streams_uni: u64, max_stream_window: u64,
236    ) -> Self {
237        StreamMap {
238            local_max_streams_bidi: max_streams_bidi,
239            local_max_streams_bidi_next: max_streams_bidi,
240            initial_max_streams_bidi: max_streams_bidi,
241
242            local_max_streams_uni: max_streams_uni,
243            local_max_streams_uni_next: max_streams_uni,
244            initial_max_streams_uni: max_streams_uni,
245
246            max_stream_window,
247
248            ..StreamMap::default()
249        }
250    }
251
252    /// Returns the stream with the given ID if it exists.
253    pub fn get(&self, id: u64) -> Option<&Stream<F>> {
254        self.streams.get(&id)
255    }
256
257    /// Returns the mutable stream with the given ID if it exists.
258    pub fn get_mut(&mut self, id: u64) -> Option<&mut Stream<F>> {
259        self.streams.get_mut(&id)
260    }
261
262    /// Returns the mutable stream with the given ID if it exists, or creates
263    /// a new one otherwise.
264    ///
265    /// The `local` parameter indicates whether the stream is locally
266    /// initiated. It validates the stream ID and selects the initial flow
267    /// control values from the local and remote transport parameters.
268    ///
269    /// This also takes care of enforcing both local and the peer's stream
270    /// count limits. If one of these limits is violated, the `StreamLimit`
271    /// error is returned.
272    pub(crate) fn get_or_create(
273        &mut self, id: u64, local_params: &crate::TransportParams,
274        peer_params: &crate::TransportParams, local: bool, is_server: bool,
275    ) -> Result<&mut Stream<F>> {
276        let (stream, is_new_and_writable) = match self.streams.entry(id) {
277            hash_map::Entry::Vacant(v) => {
278                // Stream has already been closed and garbage collected.
279                if self.collected.contains(id) {
280                    return Err(Error::Done);
281                }
282
283                if local != is_local(id, is_server) {
284                    return Err(Error::InvalidStreamState(id));
285                }
286
287                let (max_rx_data, max_tx_data) = match (local, is_bidi(id)) {
288                    // Locally-initiated bidirectional stream.
289                    (true, true) => (
290                        local_params.initial_max_stream_data_bidi_local,
291                        peer_params.initial_max_stream_data_bidi_remote,
292                    ),
293
294                    // Locally-initiated unidirectional stream.
295                    (true, false) => (0, peer_params.initial_max_stream_data_uni),
296
297                    // Remotely-initiated bidirectional stream.
298                    (false, true) => (
299                        local_params.initial_max_stream_data_bidi_remote,
300                        peer_params.initial_max_stream_data_bidi_local,
301                    ),
302
303                    // Remotely-initiated unidirectional stream.
304                    (false, false) =>
305                        (local_params.initial_max_stream_data_uni, 0),
306                };
307
308                // The two least significant bits from a stream id identify the
309                // type of stream. Truncate those bits to get the sequence for
310                // that stream type.
311                let stream_sequence = id >> 2;
312
313                // Enforce stream count limits.
314                match (is_local(id, is_server), is_bidi(id)) {
315                    (true, true) => {
316                        let n = cmp::max(
317                            self.local_opened_streams_bidi,
318                            stream_sequence + 1,
319                        );
320
321                        if n > self.peer_max_streams_bidi {
322                            return Err(Error::StreamLimit);
323                        }
324
325                        self.local_opened_streams_bidi = n;
326                    },
327
328                    (true, false) => {
329                        let n = cmp::max(
330                            self.local_opened_streams_uni,
331                            stream_sequence + 1,
332                        );
333
334                        if n > self.peer_max_streams_uni {
335                            return Err(Error::StreamLimit);
336                        }
337
338                        self.local_opened_streams_uni = n;
339                    },
340
341                    (false, true) => {
342                        let n = cmp::max(
343                            self.peer_opened_streams_bidi,
344                            stream_sequence + 1,
345                        );
346
347                        if n > self.local_max_streams_bidi {
348                            return Err(Error::StreamLimit);
349                        }
350
351                        self.peer_opened_streams_bidi = n;
352                    },
353
354                    (false, false) => {
355                        let n = cmp::max(
356                            self.peer_opened_streams_uni,
357                            stream_sequence + 1,
358                        );
359
360                        if n > self.local_max_streams_uni {
361                            return Err(Error::StreamLimit);
362                        }
363
364                        self.peer_opened_streams_uni = n;
365                    },
366                };
367
368                let initial_window = max_rx_data;
369                let s = Stream::new(
370                    id,
371                    max_rx_data,
372                    max_tx_data,
373                    local,
374                    initial_window,
375                    self.max_stream_window,
376                );
377
378                let is_writable = s.is_writable();
379
380                (v.insert(s), is_writable)
381            },
382
383            hash_map::Entry::Occupied(v) => (v.into_mut(), false),
384        };
385
386        // Newly created stream might already be writable due to initial flow
387        // control limits.
388        if is_new_and_writable {
389            self.writable.insert(Arc::clone(&stream.priority_key));
390        }
391
392        Ok(stream)
393    }
394
395    /// Adds the stream ID to the readable streams set.
396    ///
397    /// If the stream was already in the list, this does nothing.
398    pub fn insert_readable(&mut self, priority_key: &Arc<StreamPriorityKey>) {
399        if !priority_key.readable.is_linked() {
400            self.readable.insert(Arc::clone(priority_key));
401        }
402    }
403
404    /// Removes the stream ID from the readable streams set.
405    pub fn remove_readable(&mut self, priority_key: &Arc<StreamPriorityKey>) {
406        if !priority_key.readable.is_linked() {
407            return;
408        }
409
410        let mut c = {
411            let ptr = Arc::as_ptr(priority_key);
412            unsafe { self.readable.cursor_mut_from_ptr(ptr) }
413        };
414
415        c.remove();
416    }
417
418    /// Adds the stream ID to the writable streams set.
419    ///
420    /// This should also be called anytime a new stream is created, in addition
421    /// to when an existing stream becomes writable.
422    ///
423    /// If the stream was already in the list, this does nothing.
424    pub fn insert_writable(&mut self, priority_key: &Arc<StreamPriorityKey>) {
425        if !priority_key.writable.is_linked() {
426            self.writable.insert(Arc::clone(priority_key));
427        }
428    }
429
430    /// Marks a newly stopped stream as queued for writable notification.
431    pub fn insert_stopped_writable(
432        &mut self, priority_key: &Arc<StreamPriorityKey>,
433    ) {
434        if !priority_key.stopped_writable.is_linked() {
435            self.stopped_writable.insert(Arc::clone(priority_key));
436        }
437
438        self.insert_writable(priority_key);
439    }
440
441    /// Removes the stream ID from the writable streams set.
442    ///
443    /// This should also be called anytime an existing stream stops being
444    /// writable.
445    pub fn remove_writable(&mut self, priority_key: &Arc<StreamPriorityKey>) {
446        if priority_key.stopped_writable.is_linked() {
447            let ptr = Arc::as_ptr(priority_key);
448            // SAFETY: `priority_key` originates from this `StreamMap`, and its
449            // `stopped_writable` link is only inserted into this map's
450            // corresponding tree. The link is linked, and the `Arc` keeps the
451            // allocation alive, so `ptr` identifies an element of this tree.
452            let mut c = unsafe { self.stopped_writable.cursor_mut_from_ptr(ptr) };
453            c.remove();
454        }
455
456        if !priority_key.writable.is_linked() {
457            return;
458        }
459
460        let mut c = {
461            let ptr = Arc::as_ptr(priority_key);
462            unsafe { self.writable.cursor_mut_from_ptr(ptr) }
463        };
464
465        c.remove();
466    }
467
468    /// Adds the stream ID to the flushable streams set.
469    ///
470    /// If the stream was already in the list, this does nothing.
471    pub fn insert_flushable(&mut self, priority_key: &Arc<StreamPriorityKey>) {
472        if !priority_key.flushable.is_linked() {
473            self.flushable.insert(Arc::clone(priority_key));
474        }
475    }
476
477    /// Removes the stream ID from the flushable streams set.
478    pub fn remove_flushable(&mut self, priority_key: &Arc<StreamPriorityKey>) {
479        if !priority_key.flushable.is_linked() {
480            return;
481        }
482
483        let mut c = {
484            let ptr = Arc::as_ptr(priority_key);
485            unsafe { self.flushable.cursor_mut_from_ptr(ptr) }
486        };
487
488        c.remove();
489    }
490
491    pub fn peek_flushable(&self) -> Option<Arc<StreamPriorityKey>> {
492        self.flushable.front().clone_pointer()
493    }
494
495    /// Updates the priorities of a stream.
496    pub fn update_priority(
497        &mut self, old: &Arc<StreamPriorityKey>, new: &Arc<StreamPriorityKey>,
498    ) {
499        if old.readable.is_linked() {
500            self.remove_readable(old);
501            self.readable.insert(Arc::clone(new));
502        }
503
504        if old.writable.is_linked() {
505            let stopped = old.stopped_writable.is_linked();
506            self.remove_writable(old);
507            if stopped {
508                self.insert_stopped_writable(new);
509            } else {
510                self.insert_writable(new);
511            }
512        }
513
514        if old.flushable.is_linked() {
515            self.remove_flushable(old);
516            self.flushable.insert(Arc::clone(new));
517        }
518    }
519
520    /// Adds the stream ID to the almost full streams set.
521    ///
522    /// If the stream was already in the list, this does nothing.
523    pub fn insert_almost_full(&mut self, stream_id: u64) {
524        self.almost_full.insert(stream_id);
525    }
526
527    /// Removes the stream ID from the almost full streams set.
528    pub fn remove_almost_full(&mut self, stream_id: u64) {
529        self.almost_full.remove(&stream_id);
530    }
531
532    /// Adds the stream ID to the blocked streams set with the
533    /// given offset value.
534    ///
535    /// If the stream was already in the list, this does nothing.
536    pub fn insert_blocked(&mut self, stream_id: u64, off: u64) {
537        self.blocked.insert(stream_id, off);
538    }
539
540    /// Removes the stream ID from the blocked streams set.
541    pub fn remove_blocked(&mut self, stream_id: u64) {
542        self.blocked.remove(&stream_id);
543    }
544
545    /// Queues RESET_STREAM unless the send side is already complete or the
546    /// stream has been collected.
547    pub fn insert_reset(
548        &mut self, stream_id: u64, error_code: u64, final_size: u64,
549    ) {
550        if let Some(stream) = self.streams.get(&stream_id) {
551            if !stream.send.is_complete() {
552                self.reset.insert(stream_id, (error_code, final_size));
553            }
554        }
555    }
556
557    /// Removes the stream ID from the reset streams set.
558    pub fn remove_reset(&mut self, stream_id: u64) {
559        self.reset.remove(&stream_id);
560    }
561
562    /// Adds the stream ID to the stopped streams set with the
563    /// given error code.
564    ///
565    /// If the stream was already in the list, this does nothing.
566    pub fn insert_stopped(&mut self, stream_id: u64, error_code: u64) {
567        self.stopped.insert(stream_id, error_code);
568    }
569
570    /// Removes the stream ID from the stopped streams set.
571    pub fn remove_stopped(&mut self, stream_id: u64) {
572        self.stopped.remove(&stream_id);
573    }
574
575    /// Updates the peer's maximum bidirectional stream count limit.
576    pub fn update_peer_max_streams_bidi(&mut self, v: u64) {
577        self.peer_max_streams_bidi = cmp::max(self.peer_max_streams_bidi, v);
578    }
579
580    /// Updates the peer's maximum unidirectional stream count limit.
581    pub fn update_peer_max_streams_uni(&mut self, v: u64) {
582        self.peer_max_streams_uni = cmp::max(self.peer_max_streams_uni, v);
583    }
584
585    /// Commits the new max_streams_bidi limit.
586    pub fn update_max_streams_bidi(&mut self) {
587        self.local_max_streams_bidi = self.local_max_streams_bidi_next;
588    }
589
590    /// Sets the max_streams_bidi limit to the given value.
591    pub fn set_max_streams_bidi(&mut self, max: u64) {
592        self.local_max_streams_bidi = max;
593        self.local_max_streams_bidi_next = max;
594        self.initial_max_streams_bidi = max;
595    }
596
597    /// Returns the current max_streams_bidi limit.
598    pub fn max_streams_bidi(&self) -> u64 {
599        self.local_max_streams_bidi
600    }
601
602    /// Returns the new max_streams_bidi limit.
603    pub fn max_streams_bidi_next(&mut self) -> u64 {
604        self.local_max_streams_bidi_next
605    }
606
607    /// Commits the new max_streams_uni limit.
608    pub fn update_max_streams_uni(&mut self) {
609        self.local_max_streams_uni = self.local_max_streams_uni_next;
610    }
611
612    /// Returns the new max_streams_uni limit.
613    pub fn max_streams_uni_next(&mut self) -> u64 {
614        self.local_max_streams_uni_next
615    }
616
617    /// Returns the peer's current maximum bidirectional stream count limit.
618    pub fn peer_max_streams_bidi(&self) -> u64 {
619        self.peer_max_streams_bidi
620    }
621
622    /// Returns the number of bidirectional streams that can be created
623    /// before the peer's stream count limit is reached.
624    pub fn peer_streams_left_bidi(&self) -> u64 {
625        self.peer_max_streams_bidi - self.local_opened_streams_bidi
626    }
627
628    /// Returns the peer's current maximum unidirectional stream count limit.
629    pub fn peer_max_streams_uni(&self) -> u64 {
630        self.peer_max_streams_uni
631    }
632
633    /// Returns the number of unidirectional streams that can be created
634    /// before the peer's stream count limit is reached.
635    pub fn peer_streams_left_uni(&self) -> u64 {
636        self.peer_max_streams_uni - self.local_opened_streams_uni
637    }
638
639    /// Collects or disarms a stream after reporting STOP_SENDING to the caller.
640    pub fn on_stop_sending_reported(&mut self, stream_id: u64) {
641        let Some(stream) = self.streams.get_mut(&stream_id) else {
642            return;
643        };
644
645        if stream.state() == StreamState::Collectable {
646            let local = stream.local;
647            self.collect(stream_id, local);
648        } else {
649            let priority_key = Arc::clone(&stream.priority_key);
650            self.remove_writable(&priority_key);
651        }
652    }
653
654    /// Drops completed stream.
655    ///
656    /// This should only be called when Stream::state() returns Collectable
657    /// for the given stream.
658    pub fn collect(&mut self, stream_id: u64, local: bool) {
659        if !local {
660            // If the stream was created by the peer, give back a max streams
661            // credit.
662            if is_bidi(stream_id) {
663                self.local_max_streams_bidi_next =
664                    self.local_max_streams_bidi_next.saturating_add(1);
665            } else {
666                self.local_max_streams_uni_next =
667                    self.local_max_streams_uni_next.saturating_add(1);
668            }
669        }
670
671        let s = self.streams.remove(&stream_id).unwrap();
672
673        self.remove_readable(&s.priority_key);
674
675        self.remove_writable(&s.priority_key);
676
677        self.remove_flushable(&s.priority_key);
678
679        self.collected.insert(stream_id);
680    }
681
682    /// Collects a completed stream when no application notification remains.
683    pub(crate) fn try_collect(&mut self, stream_id: u64) {
684        let Some(stream) = self.get(stream_id) else {
685            return;
686        };
687
688        let local = stream.local;
689
690        if stream.state() == StreamState::Collectable {
691            self.collect(stream_id, local);
692        }
693    }
694
695    /// Creates an iterator over streams that have outstanding data to read.
696    pub fn readable(&self) -> StreamIter {
697        StreamIter {
698            streams: self.readable.iter().map(|s| s.id).collect(),
699            index: 0,
700        }
701    }
702
703    /// Creates an iterator over streams that can be written to.
704    pub fn writable(&self) -> StreamIter {
705        StreamIter {
706            streams: self.writable.iter().map(|s| s.id).collect(),
707            index: 0,
708        }
709    }
710
711    /// Creates an iterator over stopped streams in the writable queue.
712    pub fn stopped_writable(&self) -> StreamIter {
713        if self.stopped_writable.is_empty() {
714            return StreamIter::default();
715        }
716
717        StreamIter {
718            streams: self.stopped_writable.iter().map(|key| key.id).collect(),
719            index: 0,
720        }
721    }
722
723    /// Returns and unlinks the next stopped stream awaiting notification.
724    pub fn pop_stopped_writable(&mut self) -> Option<u64> {
725        let priority_key = self.stopped_writable.front().clone_pointer()?;
726        self.remove_writable(&priority_key);
727        Some(priority_key.id)
728    }
729
730    /// Returns true if the given local stream has been opened.
731    ///
732    /// Opening a local stream implicitly opens all lower-numbered local streams
733    /// of the same type, even if they do not have `Stream` objects yet.
734    pub fn local_stream_opened(&self, stream_id: u64) -> bool {
735        let opened = if is_bidi(stream_id) {
736            self.local_opened_streams_bidi
737        } else {
738            self.local_opened_streams_uni
739        };
740
741        stream_id >> 2 < opened
742    }
743
744    /// Creates an iterator over streams that need to send MAX_STREAM_DATA.
745    pub fn almost_full(&self) -> StreamIter {
746        StreamIter::from(&self.almost_full)
747    }
748
749    /// Creates an iterator over streams that need to send STREAM_DATA_BLOCKED.
750    pub fn blocked(&self) -> hash_map::Iter<'_, u64, u64> {
751        self.blocked.iter()
752    }
753
754    /// Creates an iterator over streams that need to send RESET_STREAM.
755    pub fn reset(&self) -> hash_map::Iter<'_, u64, (u64, u64)> {
756        self.reset.iter()
757    }
758
759    /// Creates an iterator over streams that need to send STOP_SENDING.
760    pub fn stopped(&self) -> hash_map::Iter<'_, u64, u64> {
761        self.stopped.iter()
762    }
763
764    /// Returns true if the stream has been collected.
765    pub fn is_collected(&self, stream_id: u64) -> bool {
766        self.collected.contains(stream_id)
767    }
768
769    /// Returns true if there are any streams that have data to write.
770    pub fn has_flushable(&self) -> bool {
771        !self.flushable.is_empty()
772    }
773
774    /// Returns true if there are any streams that have data to read.
775    pub fn has_readable(&self) -> bool {
776        !self.readable.is_empty()
777    }
778
779    /// Returns true if there are any streams that need to update the local
780    /// flow control limit.
781    pub fn has_almost_full(&self) -> bool {
782        !self.almost_full.is_empty()
783    }
784
785    /// Returns true if there are any streams that are blocked.
786    pub fn has_blocked(&self) -> bool {
787        !self.blocked.is_empty()
788    }
789
790    /// Returns true if there are any streams that are reset.
791    pub fn has_reset(&self) -> bool {
792        !self.reset.is_empty()
793    }
794
795    /// Returns true if there are any streams that need to send STOP_SENDING.
796    pub fn has_stopped(&self) -> bool {
797        !self.stopped.is_empty()
798    }
799
800    /// Returns true if the max bidirectional streams count needs to be updated
801    /// by sending a MAX_STREAMS frame to the peer.
802    ///
803    /// This only sends MAX_STREAMS when available capacity is at or below 50%
804    /// of the initial maximum streams target.
805    pub fn should_update_max_streams_bidi(&self) -> bool {
806        let available = self
807            .local_max_streams_bidi
808            .saturating_sub(self.peer_opened_streams_bidi);
809        self.local_max_streams_bidi_next != self.local_max_streams_bidi &&
810            available <= self.initial_max_streams_bidi / 2
811    }
812
813    /// Returns true if the max unidirectional streams count needs to be updated
814    /// by sending a MAX_STREAMS frame to the peer.
815    ///
816    /// This only send MAX_STREAMS when available capacity is at or below 50% of
817    /// the initial maximum streams target.
818    pub fn should_update_max_streams_uni(&self) -> bool {
819        let available = self
820            .local_max_streams_uni
821            .saturating_sub(self.peer_opened_streams_uni);
822        self.local_max_streams_uni_next != self.local_max_streams_uni &&
823            available <= self.initial_max_streams_uni / 2
824    }
825
826    /// Returns the number of active streams in the map.
827    #[cfg(test)]
828    pub fn len(&self) -> usize {
829        self.streams.len()
830    }
831
832    /// Returns the total number of bytes buffered across all streams.
833    pub(crate) fn tx_buffered(&self) -> usize {
834        self.tx_buffered
835    }
836
837    /// Computes the actual number of bytes in send buffers by summing across
838    /// all streams. This is used for debugging to verify that tx_buffered
839    /// is accurate.
840    fn tx_buffered_actual(&self) -> usize {
841        self.streams
842            .values()
843            .map(|s| s.send.buffered_bytes() as usize)
844            .sum()
845    }
846
847    /// Checks if the stored tx_buffered matches the actual value.
848    /// Returns true if they match, false otherwise.
849    pub(crate) fn tx_buffered_is_consistent(&self) -> bool {
850        self.tx_buffered == self.tx_buffered_actual()
851    }
852
853    /// Updates the tx_buffered value by adding the delta.
854    pub(crate) fn add_tx_buffered(&mut self, delta: usize) {
855        self.tx_buffered += delta;
856
857        #[cfg(debug_assertions)]
858        self.debug_check_tx_buffered_consistency();
859    }
860
861    /// Updates the tx_buffered value by subtracting the delta.
862    pub(crate) fn sub_tx_buffered(&mut self, delta: usize) {
863        debug_assert!(self.tx_buffered >= delta);
864        self.tx_buffered = self.tx_buffered.saturating_sub(delta);
865
866        #[cfg(debug_assertions)]
867        self.debug_check_tx_buffered_consistency();
868    }
869
870    /// Verifies that the stored tx_buffered value matches the actual bytes in
871    /// send buffers across all streams. Enabled in debug builds to catch
872    /// inconsistencies early.
873    #[cfg(debug_assertions)]
874    pub(crate) fn debug_check_tx_buffered_consistency(&self) {
875        if !self.tx_buffered_is_consistent() {
876            let buffered_per_stream = self
877                .streams
878                .iter()
879                .map(|(id, s)| (*id, s.send.buffered_bytes()))
880                .collect::<Vec<_>>();
881
882            let actual = self.tx_buffered_actual();
883            let stored = self.tx_buffered;
884            panic!(
885                "tx_buffered mismatch: stored={}, actual={}, diff={}, buffered_per_stream={:?}",
886                stored,
887                actual,
888                stored as i64 - actual as i64,
889                buffered_per_stream
890            );
891        }
892    }
893}
894
895/// Completion derived from transport buffers and pending app notifications.
896#[derive(Clone, Copy, Debug, PartialEq, Eq)]
897pub(crate) enum StreamState {
898    /// At least one relevant direction is not complete.
899    Incomplete,
900    /// Directions are complete, but receive data or a STOP error remains.
901    CompleteWithPendingDelivery,
902    /// No transport work or application notification remains.
903    Collectable,
904}
905
906/// A QUIC stream.
907pub struct Stream<F: BufFactory = DefaultBufFactory> {
908    /// Receive-side stream buffer.
909    pub recv: recv_buf::RecvBuf,
910
911    /// Send-side stream buffer.
912    pub send: send_buf::SendBuf<F>,
913
914    pub send_lowat: usize,
915
916    /// Whether the stream is bidirectional.
917    pub bidi: bool,
918
919    /// Whether the stream was created by the local endpoint.
920    pub local: bool,
921
922    /// The stream's urgency (lower is better). Default is `DEFAULT_URGENCY`.
923    pub urgency: u8,
924
925    /// Whether the stream can be flushed incrementally. Default is `true`.
926    pub incremental: bool,
927
928    pub priority_key: Arc<StreamPriorityKey>,
929}
930
931impl<F: BufFactory> Stream<F> {
932    /// Creates a new stream with the given flow control limits.
933    pub fn new(
934        id: u64, max_rx_data: u64, max_tx_data: u64, local: bool,
935        initial_window: u64, max_window: u64,
936    ) -> Self {
937        let priority_key = Arc::new(StreamPriorityKey {
938            id,
939            ..Default::default()
940        });
941
942        Stream {
943            recv: recv_buf::RecvBuf::new(max_rx_data, initial_window, max_window),
944            send: send_buf::SendBuf::new(max_tx_data),
945            send_lowat: 1,
946            bidi: is_bidi(id),
947            local,
948            urgency: priority_key.urgency,
949            incremental: priority_key.incremental,
950            priority_key,
951        }
952    }
953
954    /// Returns true if the stream has data to read.
955    pub fn is_readable(&self) -> bool {
956        self.recv.ready()
957    }
958
959    /// Returns true if the stream has enough flow control capacity to be
960    /// written to, and is not finished.
961    pub fn is_writable(&self) -> bool {
962        !self.send.is_shutdown() &&
963            !self.send.is_fin() &&
964            (self.send.off_back() + self.send_lowat as u64) <
965                self.send.max_off()
966    }
967
968    /// Returns true if the stream has data to send and is allowed to send at
969    /// least some of it, or if only its final size remains to be sent.
970    pub fn is_flushable(&self) -> bool {
971        let off_front = self.send.off_front();
972
973        // A pending FIN can be sent on its own only once there is no data left
974        // to send before the final offset, e.g. when retransmitted data ends
975        // before an already acknowledged tail.
976        if self.send.is_fin_pending() && off_front == self.send.off_back() {
977            return true;
978        }
979
980        !self.send.is_empty() &&
981            off_front < self.send.off_back() &&
982            off_front < self.send.max_off()
983    }
984
985    /// Derives completion without duplicating buffer or acknowledgement state.
986    ///
987    /// For bidirectional streams this happens when both the receive and send
988    /// sides are complete. That is when all incoming data has been read by the
989    /// application, and when all outgoing data has been acked by the peer.
990    ///
991    /// For unidirectional streams this happens when either the receive or send
992    /// side is complete, depending on whether the stream was created locally
993    /// or not.
994    pub(crate) fn state(&self) -> StreamState {
995        let complete = match (self.bidi, self.local) {
996            // For bidirectional streams we need to check both receive and send
997            // sides for completion.
998            (true, _) => self.recv.is_fin() && self.send.is_complete(),
999
1000            // For unidirectional streams generated locally, we only need to
1001            // check the send side for completion.
1002            (false, true) => self.send.is_complete(),
1003
1004            // For unidirectional streams generated by the peer, we only need
1005            // to check the receive side for completion.
1006            (false, false) => self.recv.is_fin(),
1007        };
1008
1009        let pending_stop_sending = match self.send.peer_stop_sending_state() {
1010            PeerStopSendingState::NotReported(_) => !self.send.is_shutdown(),
1011            PeerStopSendingState::NotReceived |
1012            PeerStopSendingState::Reported(_) => false,
1013        };
1014
1015        if !complete {
1016            StreamState::Incomplete
1017        } else if self.is_readable() || pending_stop_sending {
1018            StreamState::CompleteWithPendingDelivery
1019        } else {
1020            StreamState::Collectable
1021        }
1022    }
1023}
1024
1025/// Returns true if the stream was created locally.
1026pub fn is_local(stream_id: u64, is_server: bool) -> bool {
1027    (stream_id & 0x1) == (is_server as u64)
1028}
1029
1030/// Returns true if the stream is bidirectional.
1031pub fn is_bidi(stream_id: u64) -> bool {
1032    (stream_id & 0x2) == 0
1033}
1034
1035#[derive(Clone, Debug)]
1036pub struct StreamPriorityKey {
1037    pub urgency: u8,
1038    pub incremental: bool,
1039    pub id: u64,
1040
1041    pub readable: RBTreeAtomicLink,
1042    pub writable: RBTreeAtomicLink,
1043    pub stopped_writable: RBTreeAtomicLink,
1044    pub flushable: RBTreeAtomicLink,
1045}
1046
1047impl Default for StreamPriorityKey {
1048    fn default() -> Self {
1049        Self {
1050            urgency: DEFAULT_URGENCY,
1051            incremental: true,
1052            id: Default::default(),
1053            readable: Default::default(),
1054            writable: Default::default(),
1055            stopped_writable: Default::default(),
1056            flushable: Default::default(),
1057        }
1058    }
1059}
1060
1061impl PartialEq for StreamPriorityKey {
1062    fn eq(&self, other: &Self) -> bool {
1063        self.id == other.id
1064    }
1065}
1066
1067impl Eq for StreamPriorityKey {}
1068
1069impl PartialOrd for StreamPriorityKey {
1070    fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
1071        Some(self.cmp(other))
1072    }
1073}
1074
1075impl Ord for StreamPriorityKey {
1076    fn cmp(&self, other: &Self) -> cmp::Ordering {
1077        // Ignore priority if ID matches.
1078        if self.id == other.id {
1079            return cmp::Ordering::Equal;
1080        }
1081
1082        // First, order by urgency...
1083        if self.urgency != other.urgency {
1084            return self.urgency.cmp(&other.urgency);
1085        }
1086
1087        // ...when the urgency is the same, and both are not incremental, order
1088        // by stream ID...
1089        if !self.incremental && !other.incremental {
1090            return self.id.cmp(&other.id);
1091        }
1092
1093        // ...non-incremental takes priority over incremental...
1094        if self.incremental && !other.incremental {
1095            return cmp::Ordering::Greater;
1096        }
1097        if !self.incremental && other.incremental {
1098            return cmp::Ordering::Less;
1099        }
1100
1101        // ...finally, when both are incremental, `other` takes precedence (so
1102        // `self` is always sorted after other same-urgency incremental
1103        // entries).
1104        cmp::Ordering::Greater
1105    }
1106}
1107
1108intrusive_adapter!(pub StreamWritablePriorityAdapter = Arc<StreamPriorityKey>: StreamPriorityKey { writable => RBTreeAtomicLink });
1109
1110impl KeyAdapter<'_> for StreamWritablePriorityAdapter {
1111    type Key = StreamPriorityKey;
1112
1113    fn get_key(&self, s: &StreamPriorityKey) -> Self::Key {
1114        s.clone()
1115    }
1116}
1117
1118intrusive_adapter!(pub StreamStoppedWritablePriorityAdapter = Arc<StreamPriorityKey>: StreamPriorityKey { stopped_writable => RBTreeAtomicLink });
1119
1120impl KeyAdapter<'_> for StreamStoppedWritablePriorityAdapter {
1121    type Key = StreamPriorityKey;
1122
1123    fn get_key(&self, s: &StreamPriorityKey) -> Self::Key {
1124        s.clone()
1125    }
1126}
1127
1128intrusive_adapter!(pub StreamReadablePriorityAdapter = Arc<StreamPriorityKey>: StreamPriorityKey { readable => RBTreeAtomicLink });
1129
1130impl KeyAdapter<'_> for StreamReadablePriorityAdapter {
1131    type Key = StreamPriorityKey;
1132
1133    fn get_key(&self, s: &StreamPriorityKey) -> Self::Key {
1134        s.clone()
1135    }
1136}
1137
1138intrusive_adapter!(pub StreamFlushablePriorityAdapter = Arc<StreamPriorityKey>: StreamPriorityKey { flushable => RBTreeAtomicLink });
1139
1140impl KeyAdapter<'_> for StreamFlushablePriorityAdapter {
1141    type Key = StreamPriorityKey;
1142
1143    fn get_key(&self, s: &StreamPriorityKey) -> Self::Key {
1144        s.clone()
1145    }
1146}
1147
1148/// An iterator over QUIC streams.
1149#[derive(Default)]
1150pub struct StreamIter {
1151    streams: SmallVec<[u64; 8]>,
1152    index: usize,
1153}
1154
1155impl StreamIter {
1156    #[inline]
1157    fn from(streams: &StreamIdHashSet) -> Self {
1158        StreamIter {
1159            streams: streams.iter().copied().collect(),
1160            index: 0,
1161        }
1162    }
1163}
1164
1165impl Iterator for StreamIter {
1166    type Item = u64;
1167
1168    #[inline]
1169    fn next(&mut self) -> Option<Self::Item> {
1170        let v = self.streams.get(self.index)?;
1171        self.index += 1;
1172        Some(*v)
1173    }
1174}
1175
1176impl ExactSizeIterator for StreamIter {
1177    #[inline]
1178    fn len(&self) -> usize {
1179        self.streams.len() - self.index
1180    }
1181}
1182
1183#[cfg(test)]
1184mod tests {
1185    use rstest::rstest;
1186
1187    use crate::range_buf::RangeBuf;
1188    use crate::test_utils::Pipe;
1189
1190    use super::*;
1191
1192    /// The default size of the receiver stream flow control window.
1193    const DEFAULT_STREAM_WINDOW: u64 = 32 * 1024;
1194
1195    #[rstest]
1196    fn collected_streams_per_type(#[values(0, 1, 2, 3)] stream_type: u64) {
1197        let mut collected = CollectedStreams::default();
1198        assert!(collected.ranges.is_none());
1199
1200        for id in 0..4 {
1201            assert!(!collected.contains(id));
1202        }
1203        assert!(collected.ranges.is_none());
1204
1205        collected.insert(stream_type);
1206        assert!(collected.ranges.is_some());
1207
1208        for id in 0..4 {
1209            assert_eq!(collected.contains(id), id == stream_type);
1210        }
1211
1212        collected.insert(8 | stream_type);
1213        assert!(!collected.contains(4 | stream_type));
1214        assert_eq!(
1215            collected.ranges.as_ref().unwrap()[stream_type as usize].len(),
1216            2
1217        );
1218
1219        collected.insert(4 | stream_type);
1220        collected.insert(4 | stream_type);
1221        assert_eq!(
1222            collected.ranges.as_ref().unwrap()[stream_type as usize],
1223            0..3
1224        );
1225
1226        for id in 0..12 {
1227            assert_eq!(collected.contains(id), id & 0x3 == stream_type);
1228        }
1229    }
1230
1231    #[test]
1232    fn collected_streams_preserve_fragmented_and_large_ids() {
1233        let mut collected = CollectedStreams::default();
1234
1235        for sequence in (0..2048).step_by(2) {
1236            for stream_type in 0..4 {
1237                collected.insert((sequence << 2) | stream_type);
1238            }
1239        }
1240
1241        for sequence in 0..2048 {
1242            for stream_type in 0..4 {
1243                assert_eq!(
1244                    collected.contains((sequence << 2) | stream_type),
1245                    sequence % 2 == 0
1246                );
1247            }
1248        }
1249
1250        for stream_type in 0..4 {
1251            assert_eq!(
1252                collected.ranges.as_ref().unwrap()[stream_type as usize].len(),
1253                1024
1254            );
1255
1256            let stream_id = ((1u64 << 62) - 4) | stream_type;
1257            assert!(!collected.contains(stream_id));
1258            collected.insert(stream_id);
1259            assert!(collected.contains(stream_id));
1260            assert!(!collected.contains(stream_id - 4));
1261            assert!(!collected.contains((1u64 << 40) | stream_type));
1262        }
1263    }
1264
1265    /// Completes a client-initiated stream and processes returned stream
1266    /// credit.
1267    fn collect_pipe_stream(pipe: &mut Pipe, stream_id: u64) {
1268        let mut buf = [0; 1];
1269
1270        assert_eq!(pipe.client.stream_send(stream_id, b"a", true), Ok(1));
1271        assert_eq!(pipe.advance(), Ok(()));
1272        assert_eq!(pipe.server.stream_recv(stream_id, &mut buf), Ok((1, true)));
1273
1274        if is_bidi(stream_id) {
1275            assert_eq!(pipe.server.stream_send(stream_id, b"a", true), Ok(1));
1276            assert_eq!(pipe.advance(), Ok(()));
1277            assert_eq!(
1278                pipe.client.stream_recv(stream_id, &mut buf),
1279                Ok((1, true))
1280            );
1281        }
1282
1283        assert_eq!(pipe.advance(), Ok(()));
1284    }
1285
1286    #[rstest]
1287    fn collected_streams_out_of_order(
1288        #[values("cubic", "bbr2_gcongestion")] cc_algorithm_name: &str,
1289        #[values(0, 2)] stream_type: u64,
1290    ) {
1291        let mut pipe = Pipe::new(cc_algorithm_name).unwrap();
1292        assert_eq!(pipe.handshake(), Ok(()));
1293
1294        for sequence in [2, 0, 1] {
1295            let stream_id = (sequence << 2) | stream_type;
1296            collect_pipe_stream(&mut pipe, stream_id);
1297
1298            for conn in [&mut pipe.client, &mut pipe.server] {
1299                assert!(conn.streams.get(stream_id).is_none());
1300                assert!(conn.streams.is_collected(stream_id));
1301                assert!(conn.stream_closed(stream_id));
1302                assert_eq!(
1303                    conn.streams
1304                        .get_or_create(
1305                            stream_id,
1306                            &conn.local_transport_params,
1307                            &conn.peer_transport_params,
1308                            !conn.is_server,
1309                            conn.is_server,
1310                        )
1311                        .err(),
1312                    Some(Error::Done)
1313                );
1314            }
1315        }
1316
1317        assert_eq!(
1318            pipe.server.streams.collected.ranges.as_ref().unwrap()
1319                [stream_type as usize],
1320            0..3
1321        );
1322
1323        // Late STREAM frames must not materialize a collected stream again.
1324        let frames = [crate::frame::Frame::Stream {
1325            stream_id: 8 | stream_type,
1326            data: RangeBuf::from(b"a", 0, true),
1327        }];
1328        assert!(pipe
1329            .send_pkt_to_server(crate::Type::Short, &frames, &mut [0; 1280])
1330            .is_ok());
1331        assert_eq!(pipe.server.streams.len(), 0);
1332    }
1333
1334    #[rstest]
1335    fn collected_streams_sparse_peer_credit(
1336        #[values("cubic", "bbr2_gcongestion")] cc_algorithm_name: &str,
1337        #[values(0, 2)] stream_type: u64, #[values(1, 8)] initial_limit: u64,
1338    ) {
1339        let mut config = Pipe::default_config(cc_algorithm_name).unwrap();
1340        config.set_initial_max_streams_bidi(initial_limit);
1341        config.set_initial_max_streams_uni(initial_limit);
1342
1343        let mut pipe = Pipe::with_config(&mut config).unwrap();
1344        assert_eq!(pipe.handshake(), Ok(()));
1345
1346        for index in 0..initial_limit {
1347            let stream_id = (index << 3) | stream_type;
1348            collect_pipe_stream(&mut pipe, stream_id);
1349
1350            assert_eq!(
1351                pipe.server.streams.collected.ranges.as_ref().unwrap()
1352                    [stream_type as usize]
1353                    .len(),
1354                index as usize + 1
1355            );
1356            assert!(pipe.server.stream_closed(stream_id));
1357            assert!(pipe.client.stream_closed(stream_id));
1358            assert_eq!(pipe.server.streams.len(), 0);
1359        }
1360
1361        let peer_limit = if is_bidi(stream_type) {
1362            pipe.client.streams.peer_max_streams_bidi()
1363        } else {
1364            pipe.client.streams.peer_max_streams_uni()
1365        };
1366        assert_eq!(peer_limit, 2 * initial_limit);
1367
1368        // The odd sequences consume credit but have never had Stream objects.
1369        for sequence in (1..2 * initial_limit - 1).step_by(2) {
1370            let stream_id = (sequence << 2) | stream_type;
1371
1372            for conn in [&pipe.client, &pipe.server] {
1373                assert!(conn.streams.get(stream_id).is_none());
1374                assert!(!conn.streams.is_collected(stream_id));
1375                assert!(!conn.stream_closed(stream_id));
1376            }
1377        }
1378
1379        // Filling the implicit gaps is still permitted and merges all ranges.
1380        for sequence in (1..2 * initial_limit - 1).step_by(2) {
1381            collect_pipe_stream(&mut pipe, (sequence << 2) | stream_type);
1382        }
1383
1384        assert_eq!(
1385            pipe.server.streams.collected.ranges.as_ref().unwrap()
1386                [stream_type as usize],
1387            0..2 * initial_limit - 1
1388        );
1389    }
1390
1391    #[rstest]
1392    fn collected_streams_fragmented_local(
1393        #[values("cubic", "bbr2_gcongestion")] cc_algorithm_name: &str,
1394        #[values(0, 2)] stream_type: u64,
1395    ) {
1396        let mut client_config = Pipe::default_config(cc_algorithm_name).unwrap();
1397        client_config.set_initial_max_streams_bidi(1);
1398        client_config.set_initial_max_streams_uni(1);
1399
1400        let mut server_config = Pipe::default_config(cc_algorithm_name).unwrap();
1401        server_config.set_initial_max_streams_bidi(32);
1402        server_config.set_initial_max_streams_uni(32);
1403
1404        let mut pipe = Pipe::with_client_and_server_config(
1405            &mut client_config,
1406            &mut server_config,
1407        )
1408        .unwrap();
1409        assert_eq!(pipe.handshake(), Ok(()));
1410
1411        // Local fragmentation follows the peer's allowance and application
1412        // behavior, not the client's initial incoming stream limit of one.
1413        for index in 0..32 {
1414            collect_pipe_stream(&mut pipe, (index << 3) | stream_type);
1415            assert_eq!(
1416                pipe.client.streams.collected.ranges.as_ref().unwrap()
1417                    [stream_type as usize]
1418                    .len(),
1419                index as usize + 1
1420            );
1421            assert_eq!(pipe.client.streams.len(), 0);
1422        }
1423    }
1424
1425    #[rstest]
1426    fn stream_limit_does_not_collect(
1427        #[values(0, 1, 2, 3)] stream_type: u64,
1428        #[values(true, false)] local: bool,
1429    ) {
1430        let params = crate::TransportParams::default();
1431        let mut streams = <StreamMap>::new(1, 1, DEFAULT_STREAM_WINDOW);
1432        streams.update_peer_max_streams_bidi(1);
1433        streams.update_peer_max_streams_uni(1);
1434
1435        let stream_id = 4 | stream_type;
1436        let is_server = (stream_type & 1 != 0) == local;
1437        assert_eq!(
1438            streams
1439                .get_or_create(stream_id, &params, &params, local, is_server)
1440                .err(),
1441            Some(Error::StreamLimit)
1442        );
1443        assert!(!streams.is_collected(stream_id));
1444        assert_eq!(streams.len(), 0);
1445        assert!(streams.collected.ranges.is_none());
1446
1447        if local {
1448            streams.update_peer_max_streams_bidi(2);
1449            streams.update_peer_max_streams_uni(2);
1450        } else {
1451            streams.local_max_streams_bidi_next = 2;
1452            streams.local_max_streams_uni_next = 2;
1453            streams.update_max_streams_bidi();
1454            streams.update_max_streams_uni();
1455        }
1456
1457        assert!(streams
1458            .get_or_create(stream_id, &params, &params, local, is_server)
1459            .is_ok());
1460        assert!(streams.collected.ranges.is_none());
1461    }
1462
1463    #[test]
1464    fn recv_flow_control() {
1465        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1466        assert!(!stream.recv.almost_full());
1467
1468        let mut buf = [0; 32];
1469
1470        let first = RangeBuf::from(b"hello", 0, false);
1471        let second = RangeBuf::from(b"world", 5, false);
1472        let third = RangeBuf::from(b"something", 10, false);
1473
1474        assert_eq!(stream.recv.write(second), Ok(()));
1475        assert_eq!(stream.recv.write(first), Ok(()));
1476        assert!(!stream.recv.almost_full());
1477
1478        assert_eq!(stream.recv.write(third), Err(Error::FlowControl));
1479
1480        let (len, fin) = stream.recv.emit(&mut buf).unwrap();
1481        assert_eq!(&buf[..len], b"helloworld");
1482        assert!(!fin);
1483
1484        assert!(stream.recv.almost_full());
1485
1486        stream.recv.update_max_data(std::time::Instant::now());
1487        assert_eq!(stream.recv.max_data_next(), 25);
1488        assert!(!stream.recv.almost_full());
1489
1490        let third = RangeBuf::from(b"something", 10, false);
1491        assert_eq!(stream.recv.write(third), Ok(()));
1492    }
1493
1494    #[test]
1495    fn recv_past_fin() {
1496        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1497        assert!(!stream.recv.almost_full());
1498
1499        let first = RangeBuf::from(b"hello", 0, true);
1500        let second = RangeBuf::from(b"world", 5, false);
1501
1502        assert_eq!(stream.recv.write(first), Ok(()));
1503        assert_eq!(stream.recv.write(second), Err(Error::FinalSize));
1504    }
1505
1506    #[test]
1507    fn recv_fin_dup() {
1508        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1509        assert!(!stream.recv.almost_full());
1510
1511        let first = RangeBuf::from(b"hello", 0, true);
1512        let second = RangeBuf::from(b"hello", 0, true);
1513
1514        assert_eq!(stream.recv.write(first), Ok(()));
1515        assert_eq!(stream.recv.write(second), Ok(()));
1516
1517        let mut buf = [0; 32];
1518
1519        let (len, fin) = stream.recv.emit(&mut buf).unwrap();
1520        assert_eq!(&buf[..len], b"hello");
1521        assert!(fin);
1522    }
1523
1524    #[test]
1525    fn recv_fin_change() {
1526        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1527        assert!(!stream.recv.almost_full());
1528
1529        let first = RangeBuf::from(b"hello", 0, true);
1530        let second = RangeBuf::from(b"world", 5, true);
1531
1532        assert_eq!(stream.recv.write(second), Ok(()));
1533        assert_eq!(stream.recv.write(first), Err(Error::FinalSize));
1534    }
1535
1536    #[test]
1537    fn recv_fin_lower_than_received() {
1538        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1539        assert!(!stream.recv.almost_full());
1540
1541        let first = RangeBuf::from(b"hello", 0, true);
1542        let second = RangeBuf::from(b"world", 5, false);
1543
1544        assert_eq!(stream.recv.write(second), Ok(()));
1545        assert_eq!(stream.recv.write(first), Err(Error::FinalSize));
1546    }
1547
1548    #[test]
1549    fn recv_fin_flow_control() {
1550        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1551        assert!(!stream.recv.almost_full());
1552
1553        let mut buf = [0; 32];
1554
1555        let first = RangeBuf::from(b"hello", 0, false);
1556        let second = RangeBuf::from(b"world", 5, true);
1557
1558        assert_eq!(stream.recv.write(first), Ok(()));
1559        assert_eq!(stream.recv.write(second), Ok(()));
1560
1561        let (len, fin) = stream.recv.emit(&mut buf).unwrap();
1562        assert_eq!(&buf[..len], b"helloworld");
1563        assert!(fin);
1564
1565        assert!(!stream.recv.almost_full());
1566    }
1567
1568    #[test]
1569    fn recv_fin_reset_mismatch() {
1570        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1571        assert!(!stream.recv.almost_full());
1572
1573        let first = RangeBuf::from(b"hello", 0, true);
1574
1575        assert_eq!(stream.recv.write(first), Ok(()));
1576        assert_eq!(stream.recv.reset(0, 10), Err(Error::FinalSize));
1577    }
1578
1579    #[test]
1580    fn recv_reset_with_gap() {
1581        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1582        assert!(!stream.recv.almost_full());
1583
1584        let first = RangeBuf::from(b"hello", 0, false);
1585
1586        assert_eq!(stream.recv.write(first), Ok(()));
1587        // Read one byte.
1588        assert_eq!(stream.recv.emit(&mut [0; 1]), Ok((1, false)));
1589        // Reset with a final size > than max previously received
1590        assert_eq!(
1591            stream.recv.reset(0, 10),
1592            Ok(RecvBufResetReturn {
1593                max_data_delta: 5,
1594                // consumed_flowcontrol is 9, since we already read 1 byte
1595                consumed_flowcontrol: 9
1596            })
1597        );
1598        assert_eq!(stream.recv.reset(0, 10), Ok(RecvBufResetReturn::zero()));
1599    }
1600
1601    #[test]
1602    fn recv_reset_dup() {
1603        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1604        assert!(!stream.recv.almost_full());
1605
1606        let first = RangeBuf::from(b"hello", 0, false);
1607
1608        assert_eq!(stream.recv.write(first), Ok(()));
1609        assert_eq!(
1610            stream.recv.reset(0, 5),
1611            Ok(RecvBufResetReturn {
1612                max_data_delta: 0,
1613                consumed_flowcontrol: 5
1614            })
1615        );
1616        assert_eq!(stream.recv.reset(0, 5), Ok(RecvBufResetReturn::zero()));
1617    }
1618
1619    #[test]
1620    fn recv_reset_change() {
1621        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1622        assert!(!stream.recv.almost_full());
1623
1624        let first = RangeBuf::from(b"hello", 0, false);
1625
1626        assert_eq!(stream.recv.write(first), Ok(()));
1627        assert_eq!(
1628            stream.recv.reset(0, 5),
1629            Ok(RecvBufResetReturn {
1630                max_data_delta: 0,
1631                consumed_flowcontrol: 5
1632            })
1633        );
1634        assert_eq!(stream.recv.reset(0, 10), Err(Error::FinalSize));
1635    }
1636
1637    #[test]
1638    fn recv_reset_lower_than_received() {
1639        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1640        assert!(!stream.recv.almost_full());
1641
1642        let first = RangeBuf::from(b"hello", 0, false);
1643
1644        assert_eq!(stream.recv.write(first), Ok(()));
1645        assert_eq!(stream.recv.reset(0, 4), Err(Error::FinalSize));
1646    }
1647
1648    #[test]
1649    fn send_flow_control() {
1650        let mut buf = [0; 25];
1651
1652        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1653
1654        let first = b"hello";
1655        let second = b"world";
1656        let third = b"something";
1657
1658        assert!(stream.send.write(first, false).is_ok());
1659        assert!(stream.send.write(second, false).is_ok());
1660        assert!(stream.send.write(third, false).is_ok());
1661
1662        assert_eq!(stream.send.off_front(), 0);
1663
1664        let (written, fin) = stream.send.emit(&mut buf[..25]).unwrap();
1665        assert_eq!(written, 15);
1666        assert!(!fin);
1667        assert_eq!(&buf[..written], b"helloworldsomet");
1668
1669        assert_eq!(stream.send.off_front(), 15);
1670
1671        let (written, fin) = stream.send.emit(&mut buf[..25]).unwrap();
1672        assert_eq!(written, 0);
1673        assert!(!fin);
1674        assert_eq!(&buf[..written], b"");
1675
1676        stream.send.retransmit(0, 15);
1677
1678        assert_eq!(stream.send.off_front(), 0);
1679
1680        let (written, fin) = stream.send.emit(&mut buf[..10]).unwrap();
1681        assert_eq!(written, 10);
1682        assert!(!fin);
1683        assert_eq!(&buf[..written], b"helloworld");
1684
1685        assert_eq!(stream.send.off_front(), 10);
1686
1687        let (written, fin) = stream.send.emit(&mut buf[..10]).unwrap();
1688        assert_eq!(written, 5);
1689        assert!(!fin);
1690        assert_eq!(&buf[..written], b"somet");
1691    }
1692
1693    #[test]
1694    fn send_past_fin() {
1695        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1696
1697        let first = b"hello";
1698        let second = b"world";
1699        let third = b"third";
1700
1701        assert_eq!(stream.send.write(first, false), Ok(5));
1702
1703        assert_eq!(stream.send.write(second, true), Ok(5));
1704        assert!(stream.send.is_fin());
1705
1706        assert_eq!(stream.send.write(third, false), Err(Error::FinalSize));
1707    }
1708
1709    #[test]
1710    fn send_fin_dup() {
1711        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1712
1713        assert_eq!(stream.send.write(b"hello", true), Ok(5));
1714        assert!(stream.send.is_fin());
1715
1716        assert_eq!(stream.send.write(b"", true), Ok(0));
1717        assert!(stream.send.is_fin());
1718    }
1719
1720    #[test]
1721    fn send_undo_fin() {
1722        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1723
1724        assert_eq!(stream.send.write(b"hello", true), Ok(5));
1725        assert!(stream.send.is_fin());
1726
1727        assert_eq!(
1728            stream.send.write(b"helloworld", true),
1729            Err(Error::FinalSize)
1730        );
1731    }
1732
1733    #[test]
1734    fn send_fin_max_data_match() {
1735        let mut buf = [0; 15];
1736
1737        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1738
1739        let slice = b"hellohellohello";
1740
1741        assert!(stream.send.write(slice, true).is_ok());
1742
1743        let (written, fin) = stream.send.emit(&mut buf[..15]).unwrap();
1744        assert_eq!(written, 15);
1745        assert!(fin);
1746        assert_eq!(&buf[..written], slice);
1747    }
1748
1749    #[test]
1750    fn send_fin_zero_length() {
1751        let mut buf = [0; 5];
1752
1753        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1754
1755        assert_eq!(stream.send.write(b"hello", false), Ok(5));
1756        assert_eq!(stream.send.write(b"", true), Ok(0));
1757        assert!(stream.send.is_fin());
1758
1759        let (written, fin) = stream.send.emit(&mut buf[..5]).unwrap();
1760        assert_eq!(written, 5);
1761        assert!(fin);
1762        assert_eq!(&buf[..written], b"hello");
1763    }
1764
1765    #[test]
1766    fn send_ack() {
1767        let mut buf = [0; 5];
1768
1769        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1770
1771        assert_eq!(stream.send.write(b"hello", false), Ok(5));
1772        assert_eq!(stream.send.write(b"world", false), Ok(5));
1773        assert_eq!(stream.send.write(b"", true), Ok(0));
1774        assert!(stream.send.is_fin());
1775
1776        assert_eq!(stream.send.off_front(), 0);
1777
1778        let (written, fin) = stream.send.emit(&mut buf[..5]).unwrap();
1779        assert_eq!(written, 5);
1780        assert!(!fin);
1781        assert_eq!(&buf[..written], b"hello");
1782
1783        stream.send.ack_and_drop(0, 5);
1784
1785        stream.send.retransmit(0, 5);
1786
1787        assert_eq!(stream.send.off_front(), 5);
1788
1789        let (written, fin) = stream.send.emit(&mut buf[..5]).unwrap();
1790        assert_eq!(written, 5);
1791        assert!(fin);
1792        assert_eq!(&buf[..written], b"world");
1793    }
1794
1795    #[test]
1796    fn send_ack_reordering() {
1797        let mut buf = [0; 5];
1798
1799        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1800
1801        assert_eq!(stream.send.write(b"hello", false), Ok(5));
1802        assert_eq!(stream.send.write(b"world", false), Ok(5));
1803        assert_eq!(stream.send.write(b"", true), Ok(0));
1804        assert!(stream.send.is_fin());
1805
1806        assert_eq!(stream.send.off_front(), 0);
1807
1808        let (written, fin) = stream.send.emit(&mut buf[..5]).unwrap();
1809        assert_eq!(written, 5);
1810        assert!(!fin);
1811        assert_eq!(&buf[..written], b"hello");
1812
1813        assert_eq!(stream.send.off_front(), 5);
1814
1815        let (written, fin) = stream.send.emit(&mut buf[..1]).unwrap();
1816        assert_eq!(written, 1);
1817        assert!(!fin);
1818        assert_eq!(&buf[..written], b"w");
1819
1820        stream.send.ack_and_drop(5, 1);
1821        stream.send.ack_and_drop(0, 5);
1822
1823        stream.send.retransmit(0, 5);
1824        stream.send.retransmit(5, 1);
1825
1826        assert_eq!(stream.send.off_front(), 6);
1827
1828        let (written, fin) = stream.send.emit(&mut buf[..5]).unwrap();
1829        assert_eq!(written, 4);
1830        assert!(fin);
1831        assert_eq!(&buf[..written], b"orld");
1832    }
1833
1834    #[test]
1835    fn recv_data_below_off() {
1836        let mut stream = <Stream>::new(0, 15, 0, true, 15, DEFAULT_STREAM_WINDOW);
1837
1838        let first = RangeBuf::from(b"hello", 0, false);
1839
1840        assert_eq!(stream.recv.write(first), Ok(()));
1841
1842        let mut buf = [0; 10];
1843
1844        let (len, fin) = stream.recv.emit(&mut buf).unwrap();
1845        assert_eq!(&buf[..len], b"hello");
1846        assert!(!fin);
1847
1848        let first = RangeBuf::from(b"elloworld", 1, true);
1849        assert_eq!(stream.recv.write(first), Ok(()));
1850
1851        let (len, fin) = stream.recv.emit(&mut buf).unwrap();
1852        assert_eq!(&buf[..len], b"world");
1853        assert!(fin);
1854    }
1855
1856    #[test]
1857    fn stream_complete() {
1858        let mut stream =
1859            <Stream>::new(0, 30, 30, true, 30, DEFAULT_STREAM_WINDOW);
1860
1861        assert_eq!(stream.send.write(b"hello", false), Ok(5));
1862        assert_eq!(stream.send.write(b"world", false), Ok(5));
1863
1864        assert!(!stream.send.is_complete());
1865        assert!(!stream.send.is_fin());
1866
1867        assert_eq!(stream.send.write(b"", true), Ok(0));
1868
1869        assert!(!stream.send.is_complete());
1870        assert!(stream.send.is_fin());
1871
1872        assert_eq!(stream.send.emit(&mut [0; 10]), Ok((10, true)));
1873
1874        let buf = RangeBuf::from(b"hello", 0, true);
1875        assert!(stream.recv.write(buf).is_ok());
1876        assert!(!stream.recv.is_fin());
1877
1878        stream.send.ack(6, 4);
1879        assert!(!stream.send.is_complete());
1880
1881        let mut buf = [0; 2];
1882        assert_eq!(stream.recv.emit(&mut buf), Ok((2, false)));
1883        assert!(!stream.recv.is_fin());
1884
1885        stream.send.ack(1, 5);
1886        assert!(!stream.send.is_complete());
1887
1888        stream.send.ack(0, 1);
1889        assert!(!stream.send.is_complete());
1890
1891        stream.send.ack_fin();
1892        assert!(stream.send.is_complete());
1893
1894        assert_eq!(stream.state(), StreamState::Incomplete);
1895
1896        let mut buf = [0; 3];
1897        assert_eq!(stream.recv.emit(&mut buf), Ok((3, true)));
1898        assert!(stream.recv.is_fin());
1899
1900        assert_eq!(stream.state(), StreamState::Collectable);
1901
1902        // A completed stream must retain each undelivered terminal event.
1903        stream.send.stop(42).unwrap();
1904        assert_eq!(stream.state(), StreamState::CompleteWithPendingDelivery);
1905        assert_eq!(
1906            stream.send.cap_and_report_stop_sending(),
1907            Err(Error::StreamStopped(42))
1908        );
1909        assert_eq!(stream.state(), StreamState::Collectable);
1910
1911        let mut stream =
1912            <Stream>::new(0, 30, 30, true, 30, DEFAULT_STREAM_WINDOW);
1913        stream.send.shutdown().unwrap();
1914        stream.send.ack_reset_stream();
1915        stream.recv.reset(43, 5).unwrap();
1916        assert_eq!(stream.state(), StreamState::CompleteWithPendingDelivery);
1917        assert_eq!(stream.recv.emit(&mut buf), Err(Error::StreamReset(43)));
1918        assert_eq!(stream.state(), StreamState::Collectable);
1919
1920        // Local shutdown permits collection without reporting a later peer
1921        // STOP.
1922        stream.send.stop(42).unwrap();
1923        assert_eq!(stream.state(), StreamState::Collectable);
1924        assert_eq!(
1925            stream.send.peer_stop_sending_state(),
1926            PeerStopSendingState::NotReported(42)
1927        );
1928    }
1929
1930    #[test]
1931    fn send_fin_zero_length_output() {
1932        let mut buf = [0; 5];
1933
1934        let mut stream = <Stream>::new(0, 0, 15, true, 0, DEFAULT_STREAM_WINDOW);
1935
1936        assert_eq!(stream.send.write(b"hello", false), Ok(5));
1937        assert_eq!(stream.send.off_front(), 0);
1938        assert!(!stream.send.is_fin());
1939
1940        let (written, fin) = stream.send.emit(&mut buf).unwrap();
1941        assert_eq!(written, 5);
1942        assert!(!fin);
1943        assert_eq!(&buf[..written], b"hello");
1944
1945        assert_eq!(stream.send.write(b"", true), Ok(0));
1946        assert!(stream.send.is_fin());
1947        assert_eq!(stream.send.off_front(), 5);
1948
1949        let (written, fin) = stream.send.emit(&mut buf).unwrap();
1950        assert_eq!(written, 0);
1951        assert!(fin);
1952        assert_eq!(&buf[..written], b"");
1953    }
1954
1955    fn stream_send_ready(stream: &Stream) -> bool {
1956        !stream.send.is_empty() &&
1957            stream.send.off_front() < stream.send.off_back()
1958    }
1959
1960    #[test]
1961    fn send_emit() {
1962        let mut buf = [0; 5];
1963
1964        let mut stream = <Stream>::new(0, 0, 20, true, 0, DEFAULT_STREAM_WINDOW);
1965
1966        assert_eq!(stream.send.write(b"hello", false), Ok(5));
1967        assert_eq!(stream.send.write(b"world", false), Ok(5));
1968        assert_eq!(stream.send.write(b"olleh", false), Ok(5));
1969        assert_eq!(stream.send.write(b"dlrow", true), Ok(5));
1970        assert_eq!(stream.send.off_front(), 0);
1971        assert_eq!(stream.send.bufs_count(), 4);
1972
1973        assert!(stream.is_flushable());
1974
1975        assert!(stream_send_ready(&stream));
1976        assert_eq!(stream.send.emit(&mut buf[..4]), Ok((4, false)));
1977        assert_eq!(stream.send.off_front(), 4);
1978        assert_eq!(&buf[..4], b"hell");
1979
1980        assert!(stream_send_ready(&stream));
1981        assert_eq!(stream.send.emit(&mut buf[..4]), Ok((4, false)));
1982        assert_eq!(stream.send.off_front(), 8);
1983        assert_eq!(&buf[..4], b"owor");
1984
1985        assert!(stream_send_ready(&stream));
1986        assert_eq!(stream.send.emit(&mut buf[..2]), Ok((2, false)));
1987        assert_eq!(stream.send.off_front(), 10);
1988        assert_eq!(&buf[..2], b"ld");
1989
1990        assert!(stream_send_ready(&stream));
1991        assert_eq!(stream.send.emit(&mut buf[..1]), Ok((1, false)));
1992        assert_eq!(stream.send.off_front(), 11);
1993        assert_eq!(&buf[..1], b"o");
1994
1995        assert!(stream_send_ready(&stream));
1996        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
1997        assert_eq!(stream.send.off_front(), 16);
1998        assert_eq!(&buf[..5], b"llehd");
1999
2000        assert!(stream_send_ready(&stream));
2001        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((4, true)));
2002        assert_eq!(stream.send.off_front(), 20);
2003        assert_eq!(&buf[..4], b"lrow");
2004
2005        assert!(!stream.is_flushable());
2006
2007        assert!(!stream_send_ready(&stream));
2008        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((0, true)));
2009        assert_eq!(stream.send.off_front(), 20);
2010    }
2011
2012    #[test]
2013    fn send_emit_ack() {
2014        let mut buf = [0; 5];
2015
2016        let mut stream = <Stream>::new(0, 0, 20, true, 0, DEFAULT_STREAM_WINDOW);
2017
2018        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2019        assert_eq!(stream.send.write(b"world", false), Ok(5));
2020        assert_eq!(stream.send.write(b"olleh", false), Ok(5));
2021        assert_eq!(stream.send.write(b"dlrow", true), Ok(5));
2022        assert_eq!(stream.send.off_front(), 0);
2023        assert_eq!(stream.send.bufs_count(), 4);
2024
2025        assert!(stream.is_flushable());
2026
2027        assert!(stream_send_ready(&stream));
2028        assert_eq!(stream.send.emit(&mut buf[..4]), Ok((4, false)));
2029        assert_eq!(stream.send.off_front(), 4);
2030        assert_eq!(&buf[..4], b"hell");
2031
2032        assert!(stream_send_ready(&stream));
2033        assert_eq!(stream.send.emit(&mut buf[..4]), Ok((4, false)));
2034        assert_eq!(stream.send.off_front(), 8);
2035        assert_eq!(&buf[..4], b"owor");
2036
2037        stream.send.ack_and_drop(0, 5);
2038        assert_eq!(stream.send.bufs_count(), 3);
2039
2040        assert!(stream_send_ready(&stream));
2041        assert_eq!(stream.send.emit(&mut buf[..2]), Ok((2, false)));
2042        assert_eq!(stream.send.off_front(), 10);
2043        assert_eq!(&buf[..2], b"ld");
2044
2045        stream.send.ack_and_drop(7, 5);
2046        assert_eq!(stream.send.bufs_count(), 3);
2047
2048        assert!(stream_send_ready(&stream));
2049        assert_eq!(stream.send.emit(&mut buf[..1]), Ok((1, false)));
2050        assert_eq!(stream.send.off_front(), 11);
2051        assert_eq!(&buf[..1], b"o");
2052
2053        assert!(stream_send_ready(&stream));
2054        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
2055        assert_eq!(stream.send.off_front(), 16);
2056        assert_eq!(&buf[..5], b"llehd");
2057
2058        stream.send.ack_and_drop(5, 7);
2059        assert_eq!(stream.send.bufs_count(), 2);
2060
2061        assert!(stream_send_ready(&stream));
2062        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((4, true)));
2063        assert_eq!(stream.send.off_front(), 20);
2064        assert_eq!(&buf[..4], b"lrow");
2065
2066        assert!(!stream.is_flushable());
2067
2068        assert!(!stream_send_ready(&stream));
2069        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((0, true)));
2070        assert_eq!(stream.send.off_front(), 20);
2071
2072        stream.send.ack_and_drop(22, 4);
2073        assert_eq!(stream.send.bufs_count(), 2);
2074
2075        stream.send.ack_and_drop(20, 1);
2076        assert_eq!(stream.send.bufs_count(), 2);
2077    }
2078
2079    #[test]
2080    fn send_emit_retransmit() {
2081        let mut buf = [0; 5];
2082
2083        let mut stream = <Stream>::new(
2084            0,
2085            0,
2086            20,
2087            true,
2088            DEFAULT_STREAM_WINDOW,
2089            DEFAULT_STREAM_WINDOW,
2090        );
2091
2092        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2093        assert_eq!(stream.send.write(b"world", false), Ok(5));
2094        assert_eq!(stream.send.write(b"olleh", false), Ok(5));
2095        assert_eq!(stream.send.write(b"dlrow", true), Ok(5));
2096        assert_eq!(stream.send.off_front(), 0);
2097        assert_eq!(stream.send.bufs_count(), 4);
2098
2099        assert!(stream.is_flushable());
2100
2101        assert!(stream_send_ready(&stream));
2102        assert_eq!(stream.send.emit(&mut buf[..4]), Ok((4, false)));
2103        assert_eq!(stream.send.off_front(), 4);
2104        assert_eq!(&buf[..4], b"hell");
2105
2106        assert!(stream_send_ready(&stream));
2107        assert_eq!(stream.send.emit(&mut buf[..4]), Ok((4, false)));
2108        assert_eq!(stream.send.off_front(), 8);
2109        assert_eq!(&buf[..4], b"owor");
2110
2111        stream.send.retransmit(3, 3);
2112        assert_eq!(stream.send.off_front(), 3);
2113
2114        assert!(stream_send_ready(&stream));
2115        assert_eq!(stream.send.emit(&mut buf[..3]), Ok((3, false)));
2116        assert_eq!(stream.send.off_front(), 8);
2117        assert_eq!(&buf[..3], b"low");
2118
2119        assert!(stream_send_ready(&stream));
2120        assert_eq!(stream.send.emit(&mut buf[..2]), Ok((2, false)));
2121        assert_eq!(stream.send.off_front(), 10);
2122        assert_eq!(&buf[..2], b"ld");
2123
2124        stream.send.ack_and_drop(7, 2);
2125
2126        stream.send.retransmit(8, 2);
2127
2128        assert!(stream_send_ready(&stream));
2129        assert_eq!(stream.send.emit(&mut buf[..2]), Ok((2, false)));
2130        assert_eq!(stream.send.off_front(), 10);
2131        assert_eq!(&buf[..2], b"ld");
2132
2133        assert!(stream_send_ready(&stream));
2134        assert_eq!(stream.send.emit(&mut buf[..1]), Ok((1, false)));
2135        assert_eq!(stream.send.off_front(), 11);
2136        assert_eq!(&buf[..1], b"o");
2137
2138        assert!(stream_send_ready(&stream));
2139        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
2140        assert_eq!(stream.send.off_front(), 16);
2141        assert_eq!(&buf[..5], b"llehd");
2142
2143        stream.send.retransmit(12, 2);
2144
2145        assert!(stream_send_ready(&stream));
2146        assert_eq!(stream.send.emit(&mut buf[..2]), Ok((2, false)));
2147        assert_eq!(stream.send.off_front(), 16);
2148        assert_eq!(&buf[..2], b"le");
2149
2150        assert!(stream_send_ready(&stream));
2151        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((4, true)));
2152        assert_eq!(stream.send.off_front(), 20);
2153        assert_eq!(&buf[..4], b"lrow");
2154
2155        assert!(!stream.is_flushable());
2156
2157        assert!(!stream_send_ready(&stream));
2158        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((0, true)));
2159        assert_eq!(stream.send.off_front(), 20);
2160
2161        stream.send.retransmit(7, 12);
2162
2163        assert!(stream_send_ready(&stream));
2164        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
2165        assert_eq!(stream.send.off_front(), 12);
2166        assert_eq!(&buf[..5], b"rldol");
2167
2168        assert!(stream_send_ready(&stream));
2169        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
2170        assert_eq!(stream.send.off_front(), 17);
2171        assert_eq!(&buf[..5], b"lehdl");
2172
2173        assert!(stream_send_ready(&stream));
2174        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((2, false)));
2175        assert_eq!(stream.send.off_front(), 20);
2176        assert_eq!(&buf[..2], b"ro");
2177
2178        stream.send.ack_and_drop(12, 7);
2179
2180        stream.send.retransmit(7, 12);
2181
2182        assert!(stream_send_ready(&stream));
2183        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
2184        assert_eq!(stream.send.off_front(), 12);
2185        assert_eq!(&buf[..5], b"rldol");
2186
2187        assert!(stream_send_ready(&stream));
2188        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((5, false)));
2189        assert_eq!(stream.send.off_front(), 17);
2190        assert_eq!(&buf[..5], b"lehdl");
2191
2192        assert!(stream_send_ready(&stream));
2193        assert_eq!(stream.send.emit(&mut buf[..5]), Ok((2, false)));
2194        assert_eq!(stream.send.off_front(), 20);
2195        assert_eq!(&buf[..2], b"ro");
2196    }
2197
2198    #[test]
2199    fn send_buf_empty_fin_next() {
2200        let mut stream = <Stream>::new(0, 0, 20, true, 0, DEFAULT_STREAM_WINDOW);
2201
2202        assert!(!stream.send.empty_fin_next());
2203        assert!(!stream.is_flushable());
2204        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2205        assert!(stream.is_flushable());
2206
2207        let mut buf = [0; 5];
2208        assert_eq!(stream.send.emit(&mut buf), Ok((5, false)));
2209        assert!(!stream.send.empty_fin_next());
2210        assert!(!stream.is_flushable());
2211
2212        assert_eq!(stream.send.write(b"", true), Ok(0));
2213        assert!(stream.send.empty_fin_next());
2214
2215        // The pending FIN is the only thing left to send.
2216        assert!(stream.is_flushable());
2217
2218        let mut empty = [];
2219        assert_eq!(stream.send.emit(&mut empty), Ok((0, true)));
2220        assert!(!stream.is_flushable());
2221
2222        // Writing the FIN again doesn't schedule another one.
2223        assert_eq!(stream.send.write(b"", true), Ok(0));
2224        assert!(!stream.is_flushable());
2225    }
2226
2227    #[test]
2228    fn rangebuf_split_off() {
2229        let mut buf = <RangeBuf>::from(b"helloworld", 5, true);
2230        assert_eq!(buf.start, 0);
2231        assert_eq!(buf.pos, 0);
2232        assert_eq!(buf.len, 10);
2233        assert_eq!(buf.off, 5);
2234        assert!(buf.fin);
2235
2236        assert_eq!(buf.len(), 10);
2237        assert_eq!(buf.off(), 5);
2238        assert!(buf.fin());
2239
2240        assert_eq!(&buf[..], b"helloworld");
2241
2242        // Advance buffer.
2243        buf.consume(5);
2244
2245        assert_eq!(buf.start, 0);
2246        assert_eq!(buf.pos, 5);
2247        assert_eq!(buf.len, 10);
2248        assert_eq!(buf.off, 5);
2249        assert!(buf.fin);
2250
2251        assert_eq!(buf.len(), 5);
2252        assert_eq!(buf.off(), 10);
2253        assert!(buf.fin());
2254
2255        assert_eq!(&buf[..], b"world");
2256
2257        // Split buffer before position.
2258        let mut new_buf = buf.split_off(3);
2259
2260        assert_eq!(buf.start, 0);
2261        assert_eq!(buf.pos, 3);
2262        assert_eq!(buf.len, 3);
2263        assert_eq!(buf.off, 5);
2264        assert!(!buf.fin);
2265
2266        assert_eq!(buf.len(), 0);
2267        assert_eq!(buf.off(), 8);
2268        assert!(!buf.fin());
2269
2270        assert_eq!(&buf[..], b"");
2271
2272        assert_eq!(new_buf.start, 3);
2273        assert_eq!(new_buf.pos, 5);
2274        assert_eq!(new_buf.len, 7);
2275        assert_eq!(new_buf.off, 8);
2276        assert!(new_buf.fin);
2277
2278        assert_eq!(new_buf.len(), 5);
2279        assert_eq!(new_buf.off(), 10);
2280        assert!(new_buf.fin());
2281
2282        assert_eq!(&new_buf[..], b"world");
2283
2284        // Advance buffer.
2285        new_buf.consume(2);
2286
2287        assert_eq!(new_buf.start, 3);
2288        assert_eq!(new_buf.pos, 7);
2289        assert_eq!(new_buf.len, 7);
2290        assert_eq!(new_buf.off, 8);
2291        assert!(new_buf.fin);
2292
2293        assert_eq!(new_buf.len(), 3);
2294        assert_eq!(new_buf.off(), 12);
2295        assert!(new_buf.fin());
2296
2297        assert_eq!(&new_buf[..], b"rld");
2298
2299        // Split buffer after position.
2300        let mut new_new_buf = new_buf.split_off(5);
2301
2302        assert_eq!(new_buf.start, 3);
2303        assert_eq!(new_buf.pos, 7);
2304        assert_eq!(new_buf.len, 5);
2305        assert_eq!(new_buf.off, 8);
2306        assert!(!new_buf.fin);
2307
2308        assert_eq!(new_buf.len(), 1);
2309        assert_eq!(new_buf.off(), 12);
2310        assert!(!new_buf.fin());
2311
2312        assert_eq!(&new_buf[..], b"r");
2313
2314        assert_eq!(new_new_buf.start, 8);
2315        assert_eq!(new_new_buf.pos, 8);
2316        assert_eq!(new_new_buf.len, 2);
2317        assert_eq!(new_new_buf.off, 13);
2318        assert!(new_new_buf.fin);
2319
2320        assert_eq!(new_new_buf.len(), 2);
2321        assert_eq!(new_new_buf.off(), 13);
2322        assert!(new_new_buf.fin());
2323
2324        assert_eq!(&new_new_buf[..], b"ld");
2325
2326        // Advance buffer.
2327        new_new_buf.consume(2);
2328
2329        assert_eq!(new_new_buf.start, 8);
2330        assert_eq!(new_new_buf.pos, 10);
2331        assert_eq!(new_new_buf.len, 2);
2332        assert_eq!(new_new_buf.off, 13);
2333        assert!(new_new_buf.fin);
2334
2335        assert_eq!(new_new_buf.len(), 0);
2336        assert_eq!(new_new_buf.off(), 15);
2337        assert!(new_new_buf.fin());
2338
2339        assert_eq!(&new_new_buf[..], b"");
2340    }
2341
2342    /// RFC9000 2.1: A stream ID that is used out of order results in all
2343    /// streams of that type with lower-numbered stream IDs also being opened.
2344    #[test]
2345    fn stream_limit_auto_open() {
2346        let local_tp = crate::TransportParams::default();
2347        let peer_tp = crate::TransportParams::default();
2348
2349        let mut streams = <StreamMap>::new(5, 5, 5);
2350
2351        let stream_id = 500;
2352        assert!(!is_local(stream_id, true), "stream id is peer initiated");
2353        assert!(is_bidi(stream_id), "stream id is bidirectional");
2354        assert_eq!(
2355            streams
2356                .get_or_create(stream_id, &local_tp, &peer_tp, false, true)
2357                .err(),
2358            Some(Error::StreamLimit),
2359            "stream limit should be exceeded"
2360        );
2361    }
2362
2363    /// Stream limit should be satisfied regardless of what order we open
2364    /// streams
2365    #[test]
2366    fn stream_create_out_of_order() {
2367        let local_tp = crate::TransportParams::default();
2368        let peer_tp = crate::TransportParams::default();
2369
2370        let mut streams = <StreamMap>::new(5, 5, 5);
2371
2372        for stream_id in [8, 12, 4] {
2373            assert!(is_local(stream_id, false), "stream id is client initiated");
2374            assert!(is_bidi(stream_id), "stream id is bidirectional");
2375            assert!(streams
2376                .get_or_create(stream_id, &local_tp, &peer_tp, false, true)
2377                .is_ok());
2378        }
2379    }
2380
2381    /// Check stream limit boundary cases
2382    #[test]
2383    fn stream_limit_edge() {
2384        let local_tp = crate::TransportParams::default();
2385        let peer_tp = crate::TransportParams::default();
2386
2387        let mut streams = <StreamMap>::new(3, 3, 3);
2388
2389        // Highest permitted
2390        let stream_id = 8;
2391        assert!(streams
2392            .get_or_create(stream_id, &local_tp, &peer_tp, false, true)
2393            .is_ok());
2394
2395        // One more than highest permitted
2396        let stream_id = 12;
2397        assert_eq!(
2398            streams
2399                .get_or_create(stream_id, &local_tp, &peer_tp, false, true)
2400                .err(),
2401            Some(Error::StreamLimit)
2402        );
2403    }
2404
2405    fn cycle_stream_priority(stream_id: u64, streams: &mut StreamMap) {
2406        let key = streams.get(stream_id).unwrap().priority_key.clone();
2407        streams.update_priority(&key.clone(), &key);
2408    }
2409
2410    #[test]
2411    fn writable_prioritized_default_priority() {
2412        let local_tp = crate::TransportParams::default();
2413        let peer_tp = crate::TransportParams {
2414            initial_max_stream_data_bidi_local: 100,
2415            initial_max_stream_data_uni: 100,
2416            ..Default::default()
2417        };
2418
2419        let mut streams = StreamMap::new(100, 100, 100);
2420
2421        for id in [0, 4, 8, 12] {
2422            assert!(streams
2423                .get_or_create(id, &local_tp, &peer_tp, false, true)
2424                .is_ok());
2425        }
2426
2427        let walk_1: Vec<u64> = streams.writable().collect();
2428        cycle_stream_priority(*walk_1.first().unwrap(), &mut streams);
2429        let walk_2: Vec<u64> = streams.writable().collect();
2430        cycle_stream_priority(*walk_2.first().unwrap(), &mut streams);
2431        let walk_3: Vec<u64> = streams.writable().collect();
2432        cycle_stream_priority(*walk_3.first().unwrap(), &mut streams);
2433        let walk_4: Vec<u64> = streams.writable().collect();
2434        cycle_stream_priority(*walk_4.first().unwrap(), &mut streams);
2435        let walk_5: Vec<u64> = streams.writable().collect();
2436
2437        // All streams are non-incremental and same urgency by default. Multiple
2438        // visits shuffle their order.
2439        assert_eq!(walk_1, vec![0, 4, 8, 12]);
2440        assert_eq!(walk_2, vec![4, 8, 12, 0]);
2441        assert_eq!(walk_3, vec![8, 12, 0, 4]);
2442        assert_eq!(walk_4, vec![12, 0, 4, 8,]);
2443        assert_eq!(walk_5, vec![0, 4, 8, 12]);
2444    }
2445
2446    #[test]
2447    fn writable_prioritized_insert_order() {
2448        let local_tp = crate::TransportParams::default();
2449        let peer_tp = crate::TransportParams {
2450            initial_max_stream_data_bidi_local: 100,
2451            initial_max_stream_data_uni: 100,
2452            ..Default::default()
2453        };
2454
2455        let mut streams = StreamMap::new(100, 100, 100);
2456
2457        // Inserting same-urgency incremental streams in a "random" order yields
2458        // same order to start with.
2459        for id in [12, 4, 8, 0] {
2460            assert!(streams
2461                .get_or_create(id, &local_tp, &peer_tp, false, true)
2462                .is_ok());
2463        }
2464
2465        let walk_1: Vec<u64> = streams.writable().collect();
2466        cycle_stream_priority(*walk_1.first().unwrap(), &mut streams);
2467        let walk_2: Vec<u64> = streams.writable().collect();
2468        cycle_stream_priority(*walk_2.first().unwrap(), &mut streams);
2469        let walk_3: Vec<u64> = streams.writable().collect();
2470        cycle_stream_priority(*walk_3.first().unwrap(), &mut streams);
2471        let walk_4: Vec<u64> = streams.writable().collect();
2472        cycle_stream_priority(*walk_4.first().unwrap(), &mut streams);
2473        let walk_5: Vec<u64> = streams.writable().collect();
2474        assert_eq!(walk_1, vec![12, 4, 8, 0]);
2475        assert_eq!(walk_2, vec![4, 8, 0, 12]);
2476        assert_eq!(walk_3, vec![8, 0, 12, 4,]);
2477        assert_eq!(walk_4, vec![0, 12, 4, 8]);
2478        assert_eq!(walk_5, vec![12, 4, 8, 0]);
2479    }
2480
2481    #[test]
2482    fn writable_prioritized_mixed_urgency() {
2483        let local_tp = crate::TransportParams::default();
2484        let peer_tp = crate::TransportParams {
2485            initial_max_stream_data_bidi_local: 100,
2486            initial_max_stream_data_uni: 100,
2487            ..Default::default()
2488        };
2489
2490        let mut streams = <StreamMap>::new(100, 100, 100);
2491
2492        // Streams where the urgency descends (becomes more important). No
2493        // stream shares an urgency.
2494        let input = vec![
2495            (0, 100),
2496            (4, 90),
2497            (8, 80),
2498            (12, 70),
2499            (16, 60),
2500            (20, 50),
2501            (24, 40),
2502            (28, 30),
2503            (32, 20),
2504            (36, 10),
2505            (40, 0),
2506        ];
2507
2508        for (id, urgency) in input.clone() {
2509            // this duplicates some code from stream_priority in order to access
2510            // streams and the collection they're in
2511            let stream = streams
2512                .get_or_create(id, &local_tp, &peer_tp, false, true)
2513                .unwrap();
2514
2515            stream.urgency = urgency;
2516
2517            let new_priority_key = Arc::new(StreamPriorityKey {
2518                urgency: stream.urgency,
2519                incremental: stream.incremental,
2520                id,
2521                ..Default::default()
2522            });
2523
2524            let old_priority_key = std::mem::replace(
2525                &mut stream.priority_key,
2526                new_priority_key.clone(),
2527            );
2528
2529            streams.update_priority(&old_priority_key, &new_priority_key);
2530        }
2531
2532        let walk_1: Vec<u64> = streams.writable().collect();
2533        assert_eq!(walk_1, vec![40, 36, 32, 28, 24, 20, 16, 12, 8, 4, 0]);
2534
2535        // Re-applying priority to a stream does not cause duplication.
2536        for (id, urgency) in input {
2537            // this duplicates some code from stream_priority in order to access
2538            // streams and the collection they're in
2539            let stream = streams
2540                .get_or_create(id, &local_tp, &peer_tp, false, true)
2541                .unwrap();
2542
2543            stream.urgency = urgency;
2544
2545            let new_priority_key = Arc::new(StreamPriorityKey {
2546                urgency: stream.urgency,
2547                incremental: stream.incremental,
2548                id,
2549                ..Default::default()
2550            });
2551
2552            let old_priority_key = std::mem::replace(
2553                &mut stream.priority_key,
2554                new_priority_key.clone(),
2555            );
2556
2557            streams.update_priority(&old_priority_key, &new_priority_key);
2558        }
2559
2560        let walk_2: Vec<u64> = streams.writable().collect();
2561        assert_eq!(walk_2, vec![40, 36, 32, 28, 24, 20, 16, 12, 8, 4, 0]);
2562
2563        // Removing streams doesn't break expected ordering.
2564        streams.collect(24, true);
2565
2566        let walk_3: Vec<u64> = streams.writable().collect();
2567        assert_eq!(walk_3, vec![40, 36, 32, 28, 20, 16, 12, 8, 4, 0]);
2568
2569        streams.collect(40, true);
2570        streams.collect(0, true);
2571
2572        let walk_4: Vec<u64> = streams.writable().collect();
2573        assert_eq!(walk_4, vec![36, 32, 28, 20, 16, 12, 8, 4]);
2574
2575        // Adding streams doesn't break expected ordering.
2576        streams
2577            .get_or_create(44, &local_tp, &peer_tp, false, true)
2578            .unwrap();
2579
2580        let walk_5: Vec<u64> = streams.writable().collect();
2581        assert_eq!(walk_5, vec![36, 32, 28, 20, 16, 12, 8, 4, 44]);
2582    }
2583
2584    #[test]
2585    fn writable_prioritized_mixed_urgencies_incrementals() {
2586        let local_tp = crate::TransportParams::default();
2587        let peer_tp = crate::TransportParams {
2588            initial_max_stream_data_bidi_local: 100,
2589            initial_max_stream_data_uni: 100,
2590            ..Default::default()
2591        };
2592
2593        let mut streams = StreamMap::new(100, 100, 100);
2594
2595        // Streams that share some urgency level
2596        let input = vec![
2597            (0, 100),
2598            (4, 20),
2599            (8, 100),
2600            (12, 20),
2601            (16, 90),
2602            (20, 25),
2603            (24, 90),
2604            (28, 30),
2605            (32, 80),
2606            (36, 20),
2607            (40, 0),
2608        ];
2609
2610        for (id, urgency) in input.clone() {
2611            // this duplicates some code from stream_priority in order to access
2612            // streams and the collection they're in
2613            let stream = streams
2614                .get_or_create(id, &local_tp, &peer_tp, false, true)
2615                .unwrap();
2616
2617            stream.urgency = urgency;
2618
2619            let new_priority_key = Arc::new(StreamPriorityKey {
2620                urgency: stream.urgency,
2621                incremental: stream.incremental,
2622                id,
2623                ..Default::default()
2624            });
2625
2626            let old_priority_key = std::mem::replace(
2627                &mut stream.priority_key,
2628                new_priority_key.clone(),
2629            );
2630
2631            streams.update_priority(&old_priority_key, &new_priority_key);
2632        }
2633
2634        let walk_1: Vec<u64> = streams.writable().collect();
2635        cycle_stream_priority(4, &mut streams);
2636        cycle_stream_priority(16, &mut streams);
2637        cycle_stream_priority(0, &mut streams);
2638        let walk_2: Vec<u64> = streams.writable().collect();
2639        cycle_stream_priority(12, &mut streams);
2640        cycle_stream_priority(24, &mut streams);
2641        cycle_stream_priority(8, &mut streams);
2642        let walk_3: Vec<u64> = streams.writable().collect();
2643        cycle_stream_priority(36, &mut streams);
2644        cycle_stream_priority(16, &mut streams);
2645        cycle_stream_priority(0, &mut streams);
2646        let walk_4: Vec<u64> = streams.writable().collect();
2647        cycle_stream_priority(4, &mut streams);
2648        cycle_stream_priority(24, &mut streams);
2649        cycle_stream_priority(8, &mut streams);
2650        let walk_5: Vec<u64> = streams.writable().collect();
2651        cycle_stream_priority(12, &mut streams);
2652        cycle_stream_priority(16, &mut streams);
2653        cycle_stream_priority(0, &mut streams);
2654        let walk_6: Vec<u64> = streams.writable().collect();
2655        cycle_stream_priority(36, &mut streams);
2656        cycle_stream_priority(24, &mut streams);
2657        cycle_stream_priority(8, &mut streams);
2658        let walk_7: Vec<u64> = streams.writable().collect();
2659        cycle_stream_priority(4, &mut streams);
2660        cycle_stream_priority(16, &mut streams);
2661        cycle_stream_priority(0, &mut streams);
2662        let walk_8: Vec<u64> = streams.writable().collect();
2663        cycle_stream_priority(12, &mut streams);
2664        cycle_stream_priority(24, &mut streams);
2665        cycle_stream_priority(8, &mut streams);
2666        let walk_9: Vec<u64> = streams.writable().collect();
2667        cycle_stream_priority(36, &mut streams);
2668        cycle_stream_priority(16, &mut streams);
2669        cycle_stream_priority(0, &mut streams);
2670
2671        assert_eq!(walk_1, vec![40, 4, 12, 36, 20, 28, 32, 16, 24, 0, 8]);
2672        assert_eq!(walk_2, vec![40, 12, 36, 4, 20, 28, 32, 24, 16, 8, 0]);
2673        assert_eq!(walk_3, vec![40, 36, 4, 12, 20, 28, 32, 16, 24, 0, 8]);
2674        assert_eq!(walk_4, vec![40, 4, 12, 36, 20, 28, 32, 24, 16, 8, 0]);
2675        assert_eq!(walk_5, vec![40, 12, 36, 4, 20, 28, 32, 16, 24, 0, 8]);
2676        assert_eq!(walk_6, vec![40, 36, 4, 12, 20, 28, 32, 24, 16, 8, 0]);
2677        assert_eq!(walk_7, vec![40, 4, 12, 36, 20, 28, 32, 16, 24, 0, 8]);
2678        assert_eq!(walk_8, vec![40, 12, 36, 4, 20, 28, 32, 24, 16, 8, 0]);
2679        assert_eq!(walk_9, vec![40, 36, 4, 12, 20, 28, 32, 16, 24, 0, 8]);
2680
2681        // Removing streams doesn't break expected ordering.
2682        streams.collect(20, true);
2683
2684        let walk_10: Vec<u64> = streams.writable().collect();
2685        assert_eq!(walk_10, vec![40, 4, 12, 36, 28, 32, 24, 16, 8, 0]);
2686
2687        // Adding streams doesn't break expected ordering.
2688        let stream = streams
2689            .get_or_create(44, &local_tp, &peer_tp, false, true)
2690            .unwrap();
2691
2692        stream.urgency = 20;
2693        stream.incremental = true;
2694
2695        let new_priority_key = Arc::new(StreamPriorityKey {
2696            urgency: stream.urgency,
2697            incremental: stream.incremental,
2698            id: 44,
2699            ..Default::default()
2700        });
2701
2702        let old_priority_key =
2703            std::mem::replace(&mut stream.priority_key, new_priority_key.clone());
2704
2705        streams.update_priority(&old_priority_key, &new_priority_key);
2706
2707        let walk_11: Vec<u64> = streams.writable().collect();
2708        assert_eq!(walk_11, vec![40, 4, 12, 36, 44, 28, 32, 24, 16, 8, 0]);
2709    }
2710
2711    #[test]
2712    fn priority_tree_dupes() {
2713        let mut prioritized_writable: RBTree<StreamWritablePriorityAdapter> =
2714            Default::default();
2715
2716        for id in [0, 4, 8, 12] {
2717            let s = Arc::new(StreamPriorityKey {
2718                urgency: 0,
2719                incremental: false,
2720                id,
2721                ..Default::default()
2722            });
2723
2724            prioritized_writable.insert(s);
2725        }
2726
2727        let walk_1: Vec<u64> =
2728            prioritized_writable.iter().map(|s| s.id).collect();
2729        assert_eq!(walk_1, vec![0, 4, 8, 12]);
2730
2731        // Default keys could cause duplicate entries. `StreamMap` normally
2732        // prevents this.
2733        for id in [0, 4, 8, 12] {
2734            let s = Arc::new(StreamPriorityKey {
2735                urgency: 0,
2736                incremental: false,
2737                id,
2738                ..Default::default()
2739            });
2740
2741            prioritized_writable.insert(s);
2742        }
2743
2744        let walk_2: Vec<u64> =
2745            prioritized_writable.iter().map(|s| s.id).collect();
2746        assert_eq!(walk_2, vec![0, 0, 4, 4, 8, 8, 12, 12]);
2747    }
2748
2749    #[test]
2750    fn retransmit_returns_zero_when_already_acked() {
2751        let mut stream = <Stream>::new(0, 15, 15, true, 0, 15);
2752
2753        // Write and emit some data, with the final size.
2754        assert_eq!(stream.send.write(b"hello", true), Ok(5));
2755        assert_eq!(stream.send.buffered_bytes(), 5);
2756        assert!(stream.is_flushable());
2757
2758        let mut buf = [0; 10];
2759        let (written, _) = stream.send.emit(&mut buf).unwrap();
2760        assert_eq!(written, 5);
2761        assert_eq!(stream.send.buffered_bytes(), 0);
2762        assert!(!stream.is_flushable());
2763
2764        // Mark data for retransmission.
2765        let retransmitted = stream.send.retransmit(0, 5);
2766        assert_eq!(retransmitted, 5);
2767        assert_eq!(stream.send.buffered_bytes(), 5);
2768        assert!(stream.is_flushable());
2769
2770        // Ack the data and the FIN.
2771        stream.send.ack_and_drop(0, 5);
2772        stream.send.ack_fin();
2773        assert_eq!(stream.send.buffered_bytes(), 0);
2774        assert!(!stream.is_flushable());
2775
2776        // Try to retransmit again - should return 0 since data is acked.
2777        let retransmitted = stream.send.retransmit(0, 5);
2778        stream.send.retransmit_fin();
2779        assert_eq!(retransmitted, 0);
2780        assert_eq!(stream.send.buffered_bytes(), 0);
2781        assert!(!stream.is_flushable());
2782
2783        // A stale queue entry can still emit the FIN after it was acked.
2784        stream.send.emit(&mut buf).unwrap();
2785        assert!(stream.send.is_complete());
2786    }
2787
2788    #[test]
2789    fn retransmit_returns_partial_when_some_acked() {
2790        let mut stream = <Stream>::new(0, 15, 15, true, 0, 15);
2791
2792        // Write and emit 10 bytes.
2793        assert_eq!(stream.send.write(b"helloworld", false), Ok(10));
2794        assert_eq!(stream.send.buffered_bytes(), 10);
2795
2796        let mut buf = [0; 10];
2797        let (written, _) = stream.send.emit(&mut buf).unwrap();
2798        assert_eq!(written, 10);
2799        assert_eq!(stream.send.buffered_bytes(), 0);
2800
2801        // Mark all data for retransmission.
2802        let retransmitted = stream.send.retransmit(0, 10);
2803        assert_eq!(retransmitted, 10);
2804        assert_eq!(stream.send.buffered_bytes(), 10);
2805
2806        // Ack first 5 bytes and drop them.
2807        let dropped = stream.send.ack_and_drop(0, 5);
2808        assert_eq!(dropped, 5);
2809        assert_eq!(stream.send.buffered_bytes(), 5);
2810
2811        // Try to retransmit all 10 bytes - should return 5 since first 5 are
2812        // acked.
2813        let retransmitted = stream.send.retransmit(0, 10);
2814        assert_eq!(retransmitted, 0); // Already marked, so no change
2815        assert_eq!(stream.send.buffered_bytes(), 5);
2816    }
2817
2818    #[test]
2819    fn ack_and_drop_decrements_len_and_returns_dropped() {
2820        let mut stream = <Stream>::new(0, 15, 15, true, 0, 15);
2821
2822        // Write some data.
2823        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2824        assert_eq!(stream.send.buffered_bytes(), 5);
2825
2826        // Emit it.
2827        let mut buf = [0; 10];
2828        let (written, _) = stream.send.emit(&mut buf).unwrap();
2829        assert_eq!(written, 5);
2830        assert_eq!(stream.send.buffered_bytes(), 0);
2831
2832        // Mark for retransmission.
2833        let retransmitted = stream.send.retransmit(0, 5);
2834        assert_eq!(retransmitted, 5);
2835        assert_eq!(stream.send.buffered_bytes(), 5);
2836
2837        // Ack and drop - should decrement len and return dropped amount.
2838        let dropped = stream.send.ack_and_drop(0, 5);
2839        assert_eq!(dropped, 5);
2840        assert_eq!(stream.send.buffered_bytes(), 0);
2841    }
2842
2843    #[test]
2844    fn ack_and_drop_partial_buffer() {
2845        let mut stream = <Stream>::new(0, 30, 30, true, 0, 30);
2846
2847        // Write and emit two chunks.
2848        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2849        assert_eq!(stream.send.write(b"world", false), Ok(5));
2850        assert_eq!(stream.send.buffered_bytes(), 10);
2851
2852        let mut buf = [0; 10];
2853        let (written, _) = stream.send.emit(&mut buf).unwrap();
2854        assert_eq!(written, 10);
2855        assert_eq!(stream.send.buffered_bytes(), 0);
2856
2857        // Mark both chunks for retransmission.
2858        let retransmitted = stream.send.retransmit(0, 10);
2859        assert_eq!(retransmitted, 10);
2860        assert_eq!(stream.send.buffered_bytes(), 10);
2861
2862        // Ack and drop only first chunk.
2863        let dropped = stream.send.ack_and_drop(0, 5);
2864        assert_eq!(dropped, 5);
2865        assert_eq!(stream.send.buffered_bytes(), 5);
2866
2867        // Ack and drop second chunk.
2868        let dropped = stream.send.ack_and_drop(5, 5);
2869        assert_eq!(dropped, 5);
2870        assert_eq!(stream.send.buffered_bytes(), 0);
2871    }
2872
2873    #[test]
2874    fn ack_and_drop_returns_zero_when_nothing_dropped() {
2875        let mut stream = <Stream>::new(0, 15, 15, true, 0, 15);
2876
2877        // Write and emit data.
2878        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2879        let mut buf = [0; 10];
2880        let (written, _) = stream.send.emit(&mut buf).unwrap();
2881        assert_eq!(written, 5);
2882
2883        // Ack data that's already been fully emitted and not retransmitted.
2884        // Nothing should be dropped since there's no buffered data.
2885        let dropped = stream.send.ack_and_drop(0, 5);
2886        assert_eq!(dropped, 0);
2887        assert_eq!(stream.send.buffered_bytes(), 0);
2888    }
2889
2890    #[test]
2891    fn cache_consistency_through_full_lifecycle() {
2892        // This test verifies that StreamMap.tx_buffered stays in sync with
2893        // actual buffered data through a full lifecycle: write → emit →
2894        // retransmit → ack.
2895        let mut streams = <StreamMap>::new(5, 5, 15);
2896
2897        // Create a stream using low-level StreamMap interface.
2898        let local_params = crate::TransportParams {
2899            initial_max_data: 30,
2900            initial_max_stream_data_bidi_local: 15,
2901            initial_max_stream_data_bidi_remote: 15,
2902            initial_max_stream_data_uni: 10,
2903            initial_max_streams_bidi: 5,
2904            initial_max_streams_uni: 5,
2905            ..Default::default()
2906        };
2907        let peer_params = local_params.clone();
2908
2909        // Update peer stream limits to allow locally-initiated streams.
2910        streams.update_peer_max_streams_bidi(5);
2911        streams.update_peer_max_streams_uni(5);
2912
2913        let stream_id = 0u64;
2914
2915        // Writing raises `stream.send.buffered_bytes()` and `tx_buffered`.
2916        {
2917            let stream = streams
2918                .get_or_create(
2919                    stream_id,
2920                    &local_params,
2921                    &peer_params,
2922                    true,
2923                    false,
2924                )
2925                .unwrap();
2926            assert_eq!(stream.send.write(b"hello", false), Ok(5));
2927        }
2928        streams.add_tx_buffered(5);
2929        assert_eq!(streams.get(stream_id).unwrap().send.buffered_bytes(), 5);
2930        assert_eq!(streams.tx_buffered(), 5);
2931        assert!(streams.tx_buffered_is_consistent());
2932
2933        // Emitting lowers `stream.send.buffered_bytes()` and `tx_buffered`.
2934        let mut buf = [0; 10];
2935        let written = {
2936            let stream = streams.get_mut(stream_id).unwrap();
2937            let (written, _) = stream.send.emit(&mut buf).unwrap();
2938            written
2939        };
2940        assert_eq!(written, 5);
2941        streams.sub_tx_buffered(5);
2942        assert_eq!(streams.get(stream_id).unwrap().send.buffered_bytes(), 0);
2943        assert_eq!(streams.tx_buffered(), 0);
2944        assert!(streams.tx_buffered_is_consistent());
2945
2946        // Retransmitting raises both values by the amount retransmitted.
2947        let retransmitted = {
2948            let stream = streams.get_mut(stream_id).unwrap();
2949            stream.send.retransmit(0, 5)
2950        };
2951        assert_eq!(retransmitted, 5);
2952        streams.add_tx_buffered(retransmitted);
2953        assert_eq!(streams.get(stream_id).unwrap().send.buffered_bytes(), 5);
2954        assert_eq!(streams.tx_buffered(), 5);
2955        assert!(streams.tx_buffered_is_consistent());
2956
2957        // Ack and drop: both stream.send.buffered_bytes() and tx_buffered
2958        // decrease by actual amount dropped.
2959        let dropped = {
2960            let stream = streams.get_mut(stream_id).unwrap();
2961            stream.send.ack_and_drop(0, 5)
2962        };
2963        assert_eq!(dropped, 5);
2964        streams.sub_tx_buffered(dropped);
2965        assert_eq!(streams.get(stream_id).unwrap().send.buffered_bytes(), 0);
2966        assert_eq!(streams.tx_buffered(), 0);
2967        assert!(streams.tx_buffered_is_consistent());
2968    }
2969
2970    #[test]
2971    fn send_buf_len_reflects_buffered_data() {
2972        let mut stream = <Stream>::new(0, 15, 15, true, 0, 15);
2973
2974        // Initially empty.
2975        assert_eq!(stream.send.buffered_bytes(), 0);
2976
2977        // After write.
2978        assert_eq!(stream.send.write(b"hello", false), Ok(5));
2979        assert_eq!(stream.send.buffered_bytes(), 5);
2980
2981        // After emit.
2982        let mut buf = [0; 10];
2983        let (written, _) = stream.send.emit(&mut buf).unwrap();
2984        assert_eq!(written, 5);
2985        assert_eq!(stream.send.buffered_bytes(), 0);
2986
2987        // After retransmit.
2988        let retransmitted = stream.send.retransmit(0, 5);
2989        assert_eq!(retransmitted, 5);
2990        assert_eq!(stream.send.buffered_bytes(), 5);
2991
2992        // After ack_and_drop.
2993        let dropped = stream.send.ack_and_drop(0, 5);
2994        assert_eq!(dropped, 5);
2995        assert_eq!(stream.send.buffered_bytes(), 0);
2996    }
2997}
2998
2999mod recv_buf;
3000mod send_buf;