Debian Codegraph @

third_party/rust/neqo-transport/src/fc.rs

raw
1 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
2 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
3 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
4 // option. This file may not be copied, modified, or distributed
5 // except according to those terms.
6
7 // Tracks possibly-redundant flow control signals from other code and converts
8 // into flow control frames needing to be sent to the remote.
9
10 use std::{
11 cmp::min,
12 fmt::Debug,
13 num::NonZeroU64,
14 ops::{Deref, DerefMut, Index, IndexMut},
15 time::{Duration, Instant},
16 };
17
18 use neqo_common::{qdebug, qtrace, Role, MAX_VARINT};
19
20 use crate::{
21 frame::FrameType,
22 packet::PacketBuilder,
23 recovery::{RecoveryToken, StreamRecoveryToken},
24 recv_stream::MAX_RECV_WINDOW_SIZE,
25 stats::FrameStats,
26 stream_id::{StreamId, StreamType},
27 Error, Res,
28 };
29
30 /// Fraction of a flow control window after which a receiver sends a window
31 /// update.
32 ///
33 /// In steady-state and max utilization, a value of 4 leads to 4 window updates
34 /// per RTT.
35 ///
36 /// Value aligns with [`crate::connection::params::DEFAULT_ACK_RATIO`].
37 pub const WINDOW_UPDATE_FRACTION: u64 = 4;
38
39 /// Multiplier for auto-tuning the stream receive window.
40 ///
41 /// See [`ReceiverFlowControl::auto_tune`].
42 ///
43 /// Note that the flow control window should grow at least as fast as the
44 /// congestion control window, in order to not unnecessarily limit throughput.
45 const WINDOW_INCREASE_MULTIPLIER: u64 = 4;
46
47 #[derive(Debug)]
48 pub struct SenderFlowControl<T>
49 where
50 T: Debug + Sized,
51 {
52 /// The thing that we're counting for.
53 subject: T,
54 /// The limit.
55 limit: u64,
56 /// How much of that limit we've used.
57 used: u64,
58 /// The point at which blocking occurred. This is updated each time
59 /// the sender decides that it is blocked. It only ever changes
60 /// when blocking occurs. This ensures that blocking at any given limit
61 /// is only reported once.
62 /// Note: All values are one greater than the corresponding `limit` to
63 /// allow distinguishing between blocking at a limit of 0 and no blocking.
64 blocked_at: u64,
65 /// Whether a blocked frame should be sent.
66 blocked_frame: bool,
67 }
68
69 impl<T> SenderFlowControl<T>
70 where
71 T: Debug + Sized,
72 {
73 /// Make a new instance with the initial value and subject.
74 pub const fn new(subject: T, initial: u64) -> Self {
75 Self {
76 subject,
77 limit: initial,
78 used: 0,
79 blocked_at: 0,
80 blocked_frame: false,
81 }
82 }
83
84 /// Update the maximum. Returns `Some` with the updated available flow
85 /// control if the change was an increase and `None` otherwise.
86 pub fn update(&mut self, limit: u64) -> Option<usize> {
87 debug_assert!(limit < u64::MAX);
88 (limit > self.limit).then(|| {
89 self.limit = limit;
90 self.blocked_frame = false;
91 self.available()
92 })
93 }
94
95 /// Consume flow control.
96 pub fn consume(&mut self, count: usize) {
97 let amt = u64::try_from(count).expect("usize fits into u64");
98 debug_assert!(self.used + amt <= self.limit);
99 self.used += amt;
100 }
101
102 /// Get available flow control.
103 pub fn available(&self) -> usize {
104 usize::try_from(self.limit - self.used).unwrap_or(usize::MAX)
105 }
106
107 /// How much data has been written.
108 pub const fn used(&self) -> u64 {
109 self.used
110 }
111
112 /// Mark flow control as blocked.
113 /// This only does something if the current limit exceeds the last reported blocking limit.
114 pub fn blocked(&mut self) {
115 if self.limit >= self.blocked_at {
116 self.blocked_at = self.limit + 1;
117 self.blocked_frame = true;
118 }
119 }
120
121 /// Return whether a blocking frame needs to be sent.
122 /// This is `Some` with the active limit if `blocked` has been called,
123 /// if a blocking frame has not been sent (or it has been lost), and
124 /// if the blocking condition remains.
125 fn blocked_needed(&self) -> Option<u64> {
126 (self.blocked_frame && self.limit < self.blocked_at).then(|| self.blocked_at - 1)
127 }
128
129 /// Clear the need to send a blocked frame.
130 fn blocked_sent(&mut self) {
131 self.blocked_frame = false;
132 }
133
134 /// Mark a blocked frame as having been lost.
135 /// Only send again if value of `self.blocked_at` hasn't increased since sending.
136 /// That would imply that the limit has since increased.
137 pub fn frame_lost(&mut self, limit: u64) {
138 if self.blocked_at == limit + 1 {
139 self.blocked_frame = true;
140 }
141 }
142 }
143
144 impl SenderFlowControl<()> {
145 pub fn write_frames(
146 &mut self,
147 builder: &mut PacketBuilder,
148 tokens: &mut Vec<RecoveryToken>,
149 stats: &mut FrameStats,
150 ) {
151 if let Some(limit) = self.blocked_needed() {
152 if builder.write_varint_frame(&[FrameType::DataBlocked.into(), limit]) {
153 stats.data_blocked += 1;
154 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::DataBlocked(
155 limit,
156 )));
157 self.blocked_sent();
158 }
159 }
160 }
161 }
162
163 impl SenderFlowControl<StreamId> {
164 pub fn write_frames(
165 &mut self,
166 builder: &mut PacketBuilder,
167 tokens: &mut Vec<RecoveryToken>,
168 stats: &mut FrameStats,
169 ) {
170 if let Some(limit) = self.blocked_needed() {
171 if builder.write_varint_frame(&[
172 FrameType::StreamDataBlocked.into(),
173 self.subject.as_u64(),
174 limit,
175 ]) {
176 stats.stream_data_blocked += 1;
177 tokens.push(RecoveryToken::Stream(
178 StreamRecoveryToken::StreamDataBlocked {
179 stream_id: self.subject,
180 limit,
181 },
182 ));
183 self.blocked_sent();
184 }
185 }
186 }
187 }
188
189 impl SenderFlowControl<StreamType> {
190 pub fn write_frames(
191 &mut self,
192 builder: &mut PacketBuilder,
193 tokens: &mut Vec<RecoveryToken>,
194 stats: &mut FrameStats,
195 ) {
196 if let Some(limit) = self.blocked_needed() {
197 let frame = match self.subject {
198 StreamType::BiDi => FrameType::StreamsBlockedBiDi,
199 StreamType::UniDi => FrameType::StreamsBlockedUniDi,
200 };
201 if builder.write_varint_frame(&[frame.into(), limit]) {
202 stats.streams_blocked += 1;
203 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::StreamsBlocked {
204 stream_type: self.subject,
205 limit,
206 }));
207 self.blocked_sent();
208 }
209 }
210 }
211 }
212
213 #[derive(Debug, Default)]
214 pub struct ReceiverFlowControl<T>
215 where
216 T: Debug + Sized,
217 {
218 /// The thing that we're counting for.
219 subject: T,
220 /// The maximum amount of items that can be active (e.g., the size of the receive buffer).
221 max_active: u64,
222 /// Last max allowed sent.
223 max_allowed: u64,
224 /// Last time a flow control update was sent.
225 ///
226 /// Only used in [`ReceiverFlowControl<StreamId>`] implementation for
227 /// receive window auto-tuning.
228 last_update: Option<Instant>,
229 /// Item received, but not retired yet.
230 /// This will be used for byte flow control: each stream will remember its largest byte
231 /// offset received and session flow control will remember the sum of all bytes consumed
232 /// by all streams.
233 consumed: u64,
234 /// Retired items.
235 retired: u64,
236 frame_pending: bool,
237 }
238
239 impl<T> ReceiverFlowControl<T>
240 where
241 T: Debug + Sized,
242 {
243 /// Make a new instance with the initial value and subject.
244 pub const fn new(subject: T, max: u64) -> Self {
245 Self {
246 subject,
247 max_active: max,
248 max_allowed: max,
249 last_update: None,
250 consumed: 0,
251 retired: 0,
252 frame_pending: false,
253 }
254 }
255
256 /// Retire some items and maybe send flow control
257 /// update.
258 pub fn retire(&mut self, retired: u64) {
259 if retired <= self.retired {
260 return;
261 }
262
263 self.retired = retired;
264 if self.should_send_update() {
265 self.frame_pending = true;
266 }
267 }
268
269 /// This function is called when `STREAM_DATA_BLOCKED` frame is received.
270 /// The flow control will try to send an update if possible.
271 pub fn send_flowc_update(&mut self) {
272 if self.retired + self.max_active > self.max_allowed {
273 self.frame_pending = true;
274 }
275 }
276
277 const fn should_send_update(&self) -> bool {
278 let window_bytes_unused = self.max_allowed - self.retired;
279 window_bytes_unused < self.max_active - self.max_active / WINDOW_UPDATE_FRACTION
280 }
281
282 pub const fn frame_needed(&self) -> bool {
283 self.frame_pending
284 }
285
286 pub fn next_limit(&self) -> u64 {
287 min(
288 self.retired + self.max_active,
289 // Flow control limits are encoded as QUIC varints and are thus
290 // limited to the maximum QUIC varint value.
291 MAX_VARINT,
292 )
293 }
294
295 pub const fn max_active(&self) -> u64 {
296 self.max_active
297 }
298
299 pub fn frame_lost(&mut self, maximum_data: u64) {
300 if maximum_data == self.max_allowed {
301 self.frame_pending = true;
302 }
303 }
304
305 fn frame_sent(&mut self, new_max: u64) {
306 self.max_allowed = new_max;
307 self.frame_pending = false;
308 }
309
310 pub fn set_max_active(&mut self, max: u64) {
311 // If max_active has been increased, send an update immediately.
312 self.frame_pending |= self.max_active < max;
313 self.max_active = max;
314 }
315
316 pub const fn retired(&self) -> u64 {
317 self.retired
318 }
319
320 pub const fn consumed(&self) -> u64 {
321 self.consumed
322 }
323 }
324
325 impl ReceiverFlowControl<()> {
326 pub fn write_frames(
327 &mut self,
328 builder: &mut PacketBuilder,
329 tokens: &mut Vec<RecoveryToken>,
330 stats: &mut FrameStats,
331 ) {
332 if !self.frame_needed() {
333 return;
334 }
335 let max_allowed = self.next_limit();
336 if builder.write_varint_frame(&[FrameType::MaxData.into(), max_allowed]) {
337 stats.max_data += 1;
338 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::MaxData(
339 max_allowed,
340 )));
341 self.frame_sent(max_allowed);
342 }
343 }
344
345 pub fn add_retired(&mut self, count: u64) {
346 debug_assert!(self.retired + count <= self.consumed);
347 self.retired += count;
348 if self.should_send_update() {
349 self.frame_pending = true;
350 }
351 }
352
353 pub fn consume(&mut self, count: u64) -> Res<()> {
354 if self.consumed + count > self.max_allowed {
355 qtrace!(
356 "Session RX window exceeded: consumed:{} new:{count} limit:{}",
357 self.consumed,
358 self.max_allowed
359 );
360 return Err(Error::FlowControlError);
361 }
362 self.consumed += count;
363 Ok(())
364 }
365 }
366
367 impl ReceiverFlowControl<StreamId> {
368 pub fn write_frames(
369 &mut self,
370 builder: &mut PacketBuilder,
371 tokens: &mut Vec<RecoveryToken>,
372 stats: &mut FrameStats,
373 now: Instant,
374 rtt: Duration,
375 ) {
376 if !self.frame_needed() {
377 return;
378 }
379
380 self.auto_tune(now, rtt);
381
382 let max_allowed = self.next_limit();
383 if builder.write_varint_frame(&[
384 FrameType::MaxStreamData.into(),
385 self.subject.as_u64(),
386 max_allowed,
387 ]) {
388 stats.max_stream_data += 1;
389 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::MaxStreamData {
390 stream_id: self.subject,
391 max_data: max_allowed,
392 }));
393 self.frame_sent(max_allowed);
394 self.last_update = Some(now);
395 }
396 }
397
398 /// Auto-tune [`ReceiverFlowControl::max_active`], i.e. the stream flow
399 /// control window.
400 ///
401 /// If the sending rate (`window_bytes_used`) exceeds the rate allowed by
402 /// the maximum flow control window and the current rtt
403 /// (`window_bytes_expected`), try to increase the maximum flow control
404 /// window ([`ReceiverFlowControl::max_active`]).
405 fn auto_tune(&mut self, now: Instant, rtt: Duration) {
406 let Some(max_allowed_sent_at) = self.last_update else {
407 return;
408 };
409
410 let Ok(elapsed): Result<u64, _> = now
411 .duration_since(max_allowed_sent_at)
412 .as_micros()
413 .try_into()
414 else {
415 return;
416 };
417
418 let Ok(rtt): Result<NonZeroU64, _> = rtt
419 .as_micros()
420 .try_into()
421 .and_then(|rtt: u64| NonZeroU64::try_from(rtt))
422 else {
423 // RTT is zero, no need for tuning.
424 return;
425 };
426
427 // Compute the amount of bytes we have received in excess
428 // of what `max_active` might allow.
429 let window_bytes_expected = self.max_active * elapsed / rtt;
430 let window_bytes_used = self.max_active - (self.max_allowed - self.retired);
431 let Some(excess) = window_bytes_used.checked_sub(window_bytes_expected) else {
432 // Used below expected. No auto-tuning needed.
433 return;
434 };
435
436 let prev_max_active = self.max_active;
437 self.max_active = min(
438 self.max_active + excess * WINDOW_INCREASE_MULTIPLIER,
439 MAX_RECV_WINDOW_SIZE,
440 );
441 qdebug!(
442 "Increasing max stream receive window by {} B, \
443 previous max_active: {} MiB, \
444 new max_active: {} MiB, \
445 last update: {:?}, \
446 rtt: {rtt:?}, \
447 stream_id: {}",
448 self.max_active - prev_max_active,
449 prev_max_active / 1024 / 1024,
450 self.max_active / 1024 / 1024,
451 now - max_allowed_sent_at,
452 self.subject,
453 );
454 }
455
456 pub fn add_retired(&mut self, count: u64) {
457 debug_assert!(self.retired + count <= self.consumed);
458 self.retired += count;
459 if self.should_send_update() {
460 self.frame_pending = true;
461 }
462 }
463
464 pub fn set_consumed(&mut self, consumed: u64) -> Res<u64> {
465 if consumed <= self.consumed {
466 return Ok(0);
467 }
468
469 if consumed > self.max_allowed {
470 qtrace!("Stream RX window exceeded: {consumed}");
471 return Err(Error::FlowControlError);
472 }
473 let new_consumed = consumed - self.consumed;
474 self.consumed = consumed;
475 Ok(new_consumed)
476 }
477 }
478
479 impl ReceiverFlowControl<StreamType> {
480 pub fn write_frames(
481 &mut self,
482 builder: &mut PacketBuilder,
483 tokens: &mut Vec<RecoveryToken>,
484 stats: &mut FrameStats,
485 ) {
486 if !self.frame_needed() {
487 return;
488 }
489 let max_streams = self.next_limit();
490 let frame = match self.subject {
491 StreamType::BiDi => FrameType::MaxStreamsBiDi,
492 StreamType::UniDi => FrameType::MaxStreamsUniDi,
493 };
494 if builder.write_varint_frame(&[frame.into(), max_streams]) {
495 stats.max_streams += 1;
496 tokens.push(RecoveryToken::Stream(StreamRecoveryToken::MaxStreams {
497 stream_type: self.subject,
498 max_streams,
499 }));
500 self.frame_sent(max_streams);
501 }
502 }
503
504 /// Check if received item exceeds the allowed flow control limit.
505 pub const fn check_allowed(&self, new_end: u64) -> bool {
506 new_end < self.max_allowed
507 }
508
509 /// Retire given amount of additional data.
510 /// This function will send flow updates immediately.
511 pub fn add_retired(&mut self, count: u64) {
512 self.retired += count;
513 if count > 0 {
514 self.send_flowc_update();
515 }
516 }
517 }
518
519 pub struct RemoteStreamLimit {
520 streams_fc: ReceiverFlowControl<StreamType>,
521 next_stream: StreamId,
522 }
523
524 impl RemoteStreamLimit {
525 pub const fn new(stream_type: StreamType, max_streams: u64, role: Role) -> Self {
526 Self {
527 streams_fc: ReceiverFlowControl::new(stream_type, max_streams),
528 // // This is for a stream created by a peer, therefore we use role.remote().
529 next_stream: StreamId::init(stream_type, role.remote()),
530 }
531 }
532
533 pub const fn is_allowed(&self, stream_id: StreamId) -> bool {
534 let stream_idx = stream_id.as_u64() >> 2;
535 self.streams_fc.check_allowed(stream_idx)
536 }
537
538 pub fn is_new_stream(&self, stream_id: StreamId) -> Res<bool> {
539 if !self.is_allowed(stream_id) {
540 return Err(Error::StreamLimitError);
541 }
542 Ok(stream_id >= self.next_stream)
543 }
544
545 pub fn take_stream_id(&mut self) -> StreamId {
546 let new_stream = self.next_stream;
547 self.next_stream.next();
548 assert!(self.is_allowed(new_stream));
549 new_stream
550 }
551 }
552
553 impl Deref for RemoteStreamLimit {
554 type Target = ReceiverFlowControl<StreamType>;
555 fn deref(&self) -> &Self::Target {
556 &self.streams_fc
557 }
558 }
559
560 impl DerefMut for RemoteStreamLimit {
561 fn deref_mut(&mut self) -> &mut Self::Target {
562 &mut self.streams_fc
563 }
564 }
565
566 pub struct RemoteStreamLimits {
567 bidirectional: RemoteStreamLimit,
568 unidirectional: RemoteStreamLimit,
569 }
570
571 impl RemoteStreamLimits {
572 pub const fn new(local_max_stream_bidi: u64, local_max_stream_uni: u64, role: Role) -> Self {
573 Self {
574 bidirectional: RemoteStreamLimit::new(StreamType::BiDi, local_max_stream_bidi, role),
575 unidirectional: RemoteStreamLimit::new(StreamType::UniDi, local_max_stream_uni, role),
576 }
577 }
578 }
579
580 impl Index<StreamType> for RemoteStreamLimits {
581 type Output = RemoteStreamLimit;
582
583 fn index(&self, index: StreamType) -> &Self::Output {
584 match index {
585 StreamType::BiDi => &self.bidirectional,
586 StreamType::UniDi => &self.unidirectional,
587 }
588 }
589 }
590
591 impl IndexMut<StreamType> for RemoteStreamLimits {
592 fn index_mut(&mut self, index: StreamType) -> &mut Self::Output {
593 match index {
594 StreamType::BiDi => &mut self.bidirectional,
595 StreamType::UniDi => &mut self.unidirectional,
596 }
597 }
598 }
599
600 pub struct LocalStreamLimits {
601 bidirectional: SenderFlowControl<StreamType>,
602 unidirectional: SenderFlowControl<StreamType>,
603 role_bit: u64,
604 }
605
606 impl LocalStreamLimits {
607 pub const fn new(role: Role) -> Self {
608 Self {
609 bidirectional: SenderFlowControl::new(StreamType::BiDi, 0),
610 unidirectional: SenderFlowControl::new(StreamType::UniDi, 0),
611 role_bit: StreamId::role_bit(role),
612 }
613 }
614
615 pub fn take_stream_id(&mut self, stream_type: StreamType) -> Option<StreamId> {
616 let fc = match stream_type {
617 StreamType::BiDi => &mut self.bidirectional,
618 StreamType::UniDi => &mut self.unidirectional,
619 };
620 if fc.available() > 0 {
621 let new_stream = fc.used();
622 fc.consume(1);
623 let type_bit = match stream_type {
624 StreamType::BiDi => 0,
625 StreamType::UniDi => 2,
626 };
627 Some(StreamId::from((new_stream << 2) + type_bit + self.role_bit))
628 } else {
629 fc.blocked();
630 None
631 }
632 }
633 }
634
635 impl Index<StreamType> for LocalStreamLimits {
636 type Output = SenderFlowControl<StreamType>;
637
638 fn index(&self, index: StreamType) -> &Self::Output {
639 match index {
640 StreamType::BiDi => &self.bidirectional,
641 StreamType::UniDi => &self.unidirectional,
642 }
643 }
644 }
645
646 impl IndexMut<StreamType> for LocalStreamLimits {
647 fn index_mut(&mut self, index: StreamType) -> &mut Self::Output {
648 match index {
649 StreamType::BiDi => &mut self.bidirectional,
650 StreamType::UniDi => &mut self.unidirectional,
651 }
652 }
653 }
654
655 #[cfg(test)]
656 mod test {
657 use std::{
658 cmp::min,
659 collections::VecDeque,
660 time::{Duration, Instant},
661 };
662
663 use neqo_common::{qdebug, Encoder, Role, MAX_VARINT};
664 use neqo_crypto::random;
665
666 use super::{LocalStreamLimits, ReceiverFlowControl, RemoteStreamLimits, SenderFlowControl};
667 use crate::{
668 fc::WINDOW_UPDATE_FRACTION,
669 packet::PacketBuilder,
670 recv_stream::MAX_RECV_WINDOW_SIZE,
671 stats::FrameStats,
672 stream_id::{StreamId, StreamType},
673 ConnectionParameters, Error, Res, INITIAL_RECV_WINDOW_SIZE,
674 };
675
676 #[test]
677 fn blocked_at_zero() {
678 let mut fc = SenderFlowControl::new((), 0);
679 fc.blocked();
680 assert_eq!(fc.blocked_needed(), Some(0));
681 }
682
683 #[test]
684 fn blocked() {
685 let mut fc = SenderFlowControl::new((), 10);
686 fc.blocked();
687 assert_eq!(fc.blocked_needed(), Some(10));
688 }
689
690 #[test]
691 fn update_consume() {
692 let mut fc = SenderFlowControl::new((), 10);
693 fc.consume(10);
694 assert_eq!(fc.available(), 0);
695 fc.update(5); // An update lower than the current limit does nothing.
696 assert_eq!(fc.available(), 0);
697 fc.update(15);
698 assert_eq!(fc.available(), 5);
699 fc.consume(3);
700 assert_eq!(fc.available(), 2);
701 }
702
703 #[test]
704 fn update_clears_blocked() {
705 let mut fc = SenderFlowControl::new((), 10);
706 fc.blocked();
707 assert_eq!(fc.blocked_needed(), Some(10));
708 fc.update(5); // An update lower than the current limit does nothing.
709 assert_eq!(fc.blocked_needed(), Some(10));
710 fc.update(11);
711 assert_eq!(fc.blocked_needed(), None);
712 }
713
714 #[test]
715 fn lost_blocked_resent() {
716 let mut fc = SenderFlowControl::new((), 10);
717 fc.blocked();
718 fc.blocked_sent();
719 assert_eq!(fc.blocked_needed(), None);
720 fc.frame_lost(10);
721 assert_eq!(fc.blocked_needed(), Some(10));
722 }
723
724 #[test]
725 fn lost_after_increase() {
726 let mut fc = SenderFlowControl::new((), 10);
727 fc.blocked();
728 fc.blocked_sent();
729 assert_eq!(fc.blocked_needed(), None);
730 fc.update(11);
731 fc.frame_lost(10);
732 assert_eq!(fc.blocked_needed(), None);
733 }
734
735 #[test]
736 fn lost_after_higher_blocked() {
737 let mut fc = SenderFlowControl::new((), 10);
738 fc.blocked();
739 fc.blocked_sent();
740 fc.update(11);
741 fc.blocked();
742 assert_eq!(fc.blocked_needed(), Some(11));
743 fc.blocked_sent();
744 fc.frame_lost(10);
745 assert_eq!(fc.blocked_needed(), None);
746 }
747
748 #[test]
749 fn do_no_need_max_allowed_frame_at_start() {
750 let fc = ReceiverFlowControl::new((), 0);
751 assert!(!fc.frame_needed());
752 }
753
754 #[test]
755 fn max_allowed_after_items_retired() {
756 let window = 100;
757 let trigger = window / WINDOW_UPDATE_FRACTION;
758 let mut fc = ReceiverFlowControl::new((), window);
759 fc.retire(trigger);
760 assert!(!fc.frame_needed());
761 fc.retire(trigger + 1);
762 assert!(fc.frame_needed());
763 assert_eq!(fc.next_limit(), window + trigger + 1);
764 }
765
766 #[test]
767 fn need_max_allowed_frame_after_loss() {
768 let mut fc = ReceiverFlowControl::new((), 100);
769 fc.retire(100);
770 assert!(fc.frame_needed());
771 assert_eq!(fc.next_limit(), 200);
772 fc.frame_sent(200);
773 assert!(!fc.frame_needed());
774 fc.frame_lost(200);
775 assert!(fc.frame_needed());
776 assert_eq!(fc.next_limit(), 200);
777 }
778
779 #[test]
780 fn no_max_allowed_frame_after_old_loss() {
781 let mut fc = ReceiverFlowControl::new((), 100);
782 fc.retire(51);
783 assert!(fc.frame_needed());
784 assert_eq!(fc.next_limit(), 151);
785 fc.frame_sent(151);
786 assert!(!fc.frame_needed());
787 fc.retire(102);
788 assert!(fc.frame_needed());
789 assert_eq!(fc.next_limit(), 202);
790 fc.frame_sent(202);
791 assert!(!fc.frame_needed());
792 fc.frame_lost(151);
793 assert!(!fc.frame_needed());
794 }
795
796 #[test]
797 fn force_send_max_allowed() {
798 let mut fc = ReceiverFlowControl::new((), 100);
799 fc.retire(10);
800 assert!(!fc.frame_needed());
801 }
802
803 #[test]
804 fn multiple_retries_after_frame_pending_is_set() {
805 let mut fc = ReceiverFlowControl::new((), 100);
806 fc.retire(51);
807 assert!(fc.frame_needed());
808 assert_eq!(fc.next_limit(), 151);
809 fc.retire(61);
810 assert!(fc.frame_needed());
811 assert_eq!(fc.next_limit(), 161);
812 fc.retire(88);
813 assert!(fc.frame_needed());
814 assert_eq!(fc.next_limit(), 188);
815 fc.retire(90);
816 assert!(fc.frame_needed());
817 assert_eq!(fc.next_limit(), 190);
818 fc.frame_sent(190);
819 assert!(!fc.frame_needed());
820 fc.retire(141);
821 assert!(fc.frame_needed());
822 assert_eq!(fc.next_limit(), 241);
823 fc.frame_sent(241);
824 assert!(!fc.frame_needed());
825 }
826
827 #[test]
828 fn new_retired_before_loss() {
829 let mut fc = ReceiverFlowControl::new((), 100);
830 fc.retire(51);
831 assert!(fc.frame_needed());
832 assert_eq!(fc.next_limit(), 151);
833 fc.frame_sent(151);
834 assert!(!fc.frame_needed());
835 fc.retire(62);
836 assert!(!fc.frame_needed());
837 fc.frame_lost(151);
838 assert!(fc.frame_needed());
839 assert_eq!(fc.next_limit(), 162);
840 }
841
842 #[test]
843 fn changing_max_active() {
844 let mut fc = ReceiverFlowControl::new((), 100);
845 fc.set_max_active(50);
846
847 // There is no MAX_STREAM_DATA frame needed.
848 assert!(!fc.frame_needed());
849
850 // We can still retire more than 50.
851 fc.consume(60).unwrap();
852 fc.retire(60);
853
854 // There is no MAX_STREAM_DATA frame needed yet.
855 assert!(!fc.frame_needed());
856 fc.consume(16).unwrap();
857 fc.retire(76);
858 assert!(fc.frame_needed());
859 assert_eq!(fc.next_limit(), 126);
860
861 // Increase max_active.
862 fc.set_max_active(60);
863 assert!(fc.frame_needed());
864 let new_max = fc.next_limit();
865 assert_eq!(new_max, 136);
866
867 // Sent update, accounting for the new `max_active`.
868 fc.frame_sent(new_max);
869
870 // We can retire more than 60.
871 fc.consume(60).unwrap();
872 fc.retire(136);
873 assert!(fc.frame_needed());
874 assert_eq!(fc.next_limit(), 196);
875 }
876
877 fn remote_stream_limits(role: Role, bidi: u64, unidi: u64) {
878 let mut fc = RemoteStreamLimits::new(2, 1, role);
879 assert!(fc[StreamType::BiDi]
880 .is_new_stream(StreamId::from(bidi))
881 .unwrap());
882 assert!(fc[StreamType::BiDi]
883 .is_new_stream(StreamId::from(bidi + 4))
884 .unwrap());
885 assert!(fc[StreamType::UniDi]
886 .is_new_stream(StreamId::from(unidi))
887 .unwrap());
888
889 // Exceed limits
890 assert_eq!(
891 fc[StreamType::BiDi].is_new_stream(StreamId::from(bidi + 8)),
892 Err(Error::StreamLimitError)
893 );
894 assert_eq!(
895 fc[StreamType::UniDi].is_new_stream(StreamId::from(unidi + 4)),
896 Err(Error::StreamLimitError)
897 );
898
899 assert_eq!(fc[StreamType::BiDi].take_stream_id(), StreamId::from(bidi));
900 assert_eq!(
901 fc[StreamType::BiDi].take_stream_id(),
902 StreamId::from(bidi + 4)
903 );
904 assert_eq!(
905 fc[StreamType::UniDi].take_stream_id(),
906 StreamId::from(unidi)
907 );
908
909 fc[StreamType::BiDi].add_retired(1);
910 fc[StreamType::BiDi].send_flowc_update();
911 // consume the frame
912 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
913 let mut tokens = Vec::new();
914 fc[StreamType::BiDi].write_frames(&mut builder, &mut tokens, &mut FrameStats::default());
915 assert_eq!(tokens.len(), 1);
916
917 // Now 9 can be a new StreamId.
918 assert!(fc[StreamType::BiDi]
919 .is_new_stream(StreamId::from(bidi + 8))
920 .unwrap());
921 assert_eq!(
922 fc[StreamType::BiDi].take_stream_id(),
923 StreamId::from(bidi + 8)
924 );
925 // 13 still exceeds limits
926 assert_eq!(
927 fc[StreamType::BiDi].is_new_stream(StreamId::from(bidi + 12)),
928 Err(Error::StreamLimitError)
929 );
930
931 fc[StreamType::UniDi].add_retired(1);
932 fc[StreamType::UniDi].send_flowc_update();
933 // consume the frame
934 fc[StreamType::UniDi].write_frames(&mut builder, &mut tokens, &mut FrameStats::default());
935 assert_eq!(tokens.len(), 2);
936
937 // Now 7 can be a new StreamId.
938 assert!(fc[StreamType::UniDi]
939 .is_new_stream(StreamId::from(unidi + 4))
940 .unwrap());
941 assert_eq!(
942 fc[StreamType::UniDi].take_stream_id(),
943 StreamId::from(unidi + 4)
944 );
945 // 11 exceeds limits
946 assert_eq!(
947 fc[StreamType::UniDi].is_new_stream(StreamId::from(unidi + 8)),
948 Err(Error::StreamLimitError)
949 );
950 }
951
952 #[test]
953 fn remote_stream_limits_new_stream_client() {
954 remote_stream_limits(Role::Client, 1, 3);
955 }
956
957 #[test]
958 fn remote_stream_limits_new_stream_server() {
959 remote_stream_limits(Role::Server, 0, 2);
960 }
961
962 #[should_panic(expected = ".is_allowed")]
963 #[test]
964 fn remote_stream_limits_asserts_if_limit_exceeded() {
965 let mut fc = RemoteStreamLimits::new(2, 1, Role::Client);
966 assert_eq!(fc[StreamType::BiDi].take_stream_id(), StreamId::from(1));
967 assert_eq!(fc[StreamType::BiDi].take_stream_id(), StreamId::from(5));
968 _ = fc[StreamType::BiDi].take_stream_id();
969 }
970
971 fn local_stream_limits(role: Role, bidi: u64, unidi: u64) {
972 let mut fc = LocalStreamLimits::new(role);
973
974 fc[StreamType::BiDi].update(2);
975 fc[StreamType::UniDi].update(1);
976
977 // Add streams
978 assert_eq!(
979 fc.take_stream_id(StreamType::BiDi).unwrap(),
980 StreamId::from(bidi)
981 );
982 assert_eq!(
983 fc.take_stream_id(StreamType::BiDi).unwrap(),
984 StreamId::from(bidi + 4)
985 );
986 assert_eq!(fc.take_stream_id(StreamType::BiDi), None);
987 assert_eq!(
988 fc.take_stream_id(StreamType::UniDi).unwrap(),
989 StreamId::from(unidi)
990 );
991 assert_eq!(fc.take_stream_id(StreamType::UniDi), None);
992
993 // Increase limit
994 fc[StreamType::BiDi].update(3);
995 fc[StreamType::UniDi].update(2);
996 assert_eq!(
997 fc.take_stream_id(StreamType::BiDi).unwrap(),
998 StreamId::from(bidi + 8)
999 );
1000 assert_eq!(fc.take_stream_id(StreamType::BiDi), None);
1001 assert_eq!(
1002 fc.take_stream_id(StreamType::UniDi).unwrap(),
1003 StreamId::from(unidi + 4)
1004 );
1005 assert_eq!(fc.take_stream_id(StreamType::UniDi), None);
1006 }
1007
1008 #[test]
1009 fn local_stream_limits_new_stream_client() {
1010 local_stream_limits(Role::Client, 0, 2);
1011 }
1012
1013 #[test]
1014 fn local_stream_limits_new_stream_server() {
1015 local_stream_limits(Role::Server, 1, 3);
1016 }
1017
1018 fn write_frames(fc: &mut ReceiverFlowControl<StreamId>, rtt: Duration, now: Instant) -> usize {
1019 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
1020 let mut tokens = Vec::new();
1021 fc.write_frames(
1022 &mut builder,
1023 &mut tokens,
1024 &mut FrameStats::default(),
1025 now,
1026 rtt,
1027 );
1028 tokens.len()
1029 }
1030
1031 #[test]
1032 fn trigger_factor() -> Res<()> {
1033 let rtt = Duration::from_millis(40);
1034 let now = Instant::now();
1035 let mut fc = ReceiverFlowControl::new(StreamId::new(0), INITIAL_RECV_WINDOW_SIZE as u64);
1036
1037 let fraction = INITIAL_RECV_WINDOW_SIZE as u64 / WINDOW_UPDATE_FRACTION;
1038
1039 let consumed = fc.set_consumed(fraction)?;
1040 fc.add_retired(consumed);
1041 assert_eq!(write_frames(&mut fc, rtt, now), 0);
1042
1043 let consumed = fc.set_consumed(fraction + 1)?;
1044 assert_eq!(write_frames(&mut fc, rtt, now), 0);
1045
1046 fc.add_retired(consumed);
1047 assert_eq!(write_frames(&mut fc, rtt, now), 1);
1048
1049 Ok(())
1050 }
1051
1052 #[test]
1053 fn auto_tuning_increase_no_decrease() -> Res<()> {
1054 let rtt = Duration::from_millis(40);
1055 let mut now = Instant::now();
1056 let mut fc = ReceiverFlowControl::new(StreamId::new(0), INITIAL_RECV_WINDOW_SIZE as u64);
1057 let initial_max_active = fc.max_active();
1058
1059 // Consume and retire multiple receive windows without increasing time.
1060 for _ in 1..11 {
1061 let consumed = fc.set_consumed(fc.next_limit())?;
1062 fc.add_retired(consumed);
1063 write_frames(&mut fc, rtt, now);
1064 }
1065 let increased_max_active = fc.max_active();
1066
1067 assert!(
1068 initial_max_active < increased_max_active,
1069 "expect receive window auto-tuning to increase max_active on full utilization of high bdp connection"
1070 );
1071
1072 // Huge idle time.
1073 now += Duration::from_secs(60 * 60); // 1h
1074 let consumed = fc.set_consumed(fc.next_limit()).unwrap();
1075 fc.add_retired(consumed);
1076
1077 assert_eq!(write_frames(&mut fc, rtt, now), 1);
1078 assert_eq!(
1079 increased_max_active,
1080 fc.max_active(),
1081 "expect receive window auto-tuning never to decrease max_active on low utilization"
1082 );
1083
1084 Ok(())
1085 }
1086
1087 #[test]
1088 fn stream_data_blocked_triggers_auto_tuning() -> Res<()> {
1089 let rtt = Duration::from_millis(40);
1090 let now = Instant::now();
1091 let mut fc = ReceiverFlowControl::new(StreamId::new(0), INITIAL_RECV_WINDOW_SIZE as u64);
1092
1093 // Send first window update to give auto-tuning algorithm a baseline.
1094 let consumed = fc.set_consumed(fc.next_limit())?;
1095 fc.add_retired(consumed);
1096 assert_eq!(write_frames(&mut fc, rtt, now), 1);
1097
1098 // Use up a single byte only, i.e. way below WINDOW_UPDATE_FRACTION.
1099 let consumed = fc.set_consumed(fc.retired + 1)?;
1100 fc.add_retired(consumed);
1101 assert_eq!(
1102 write_frames(&mut fc, rtt, now),
1103 0,
1104 "expect receiver to not send window update unprompted"
1105 );
1106
1107 // Receive STREAM_DATA_BLOCKED frame.
1108 fc.send_flowc_update();
1109 let previous_max_active = fc.max_active();
1110 assert_eq!(
1111 write_frames(&mut fc, rtt, now),
1112 1,
1113 "expect receiver to send window update"
1114 );
1115 assert!(
1116 previous_max_active < fc.max_active(),
1117 "expect receiver to auto-tune (i.e. increase) max_active"
1118 );
1119
1120 Ok(())
1121 }
1122
1123 #[expect(clippy::cast_precision_loss, reason = "This is test code.")]
1124 #[test]
1125 fn auto_tuning_approximates_bandwidth_delay_product() -> Res<()> {
1126 const DATA_FRAME_SIZE: u64 = 1_500;
1127 /// Allow auto-tuning algorithm to be off from actual bandwidth-delay
1128 /// product by up to 1KiB.
1129 const TOLERANCE: u64 = 1024;
1130
1131 test_fixture::fixture_init();
1132
1133 // Run multiple iterations with randomized bandwidth and rtt.
1134 for _ in 0..1_000 {
1135 // Random bandwidth between 1 Mbit/s and 1 Gbit/s.
1136 let bandwidth =
1137 u64::from(u16::from_be_bytes(random::<2>()) % 1_000 + 1) * 1_000 * 1_000;
1138 // Random delay between 1 ms and 256 ms.
1139 let rtt = Duration::from_millis(u64::from(random::<1>()[0]) + 1);
1140 let bdp = bandwidth * u64::try_from(rtt.as_millis()).unwrap() / 1_000 / 8;
1141
1142 let mut now = Instant::now();
1143
1144 let mut send_to_recv = VecDeque::new();
1145 let mut recv_to_send = VecDeque::new();
1146
1147 let mut last_max_active = INITIAL_RECV_WINDOW_SIZE as u64;
1148 let mut last_max_active_changed = now;
1149
1150 let mut sender_window = INITIAL_RECV_WINDOW_SIZE as u64;
1151 let mut fc =
1152 ReceiverFlowControl::new(StreamId::new(0), INITIAL_RECV_WINDOW_SIZE as u64);
1153
1154 loop {
1155 // Sender receives window updates.
1156 if recv_to_send.front().is_some_and(|(at, _)| *at <= now) {
1157 let (_, update) = recv_to_send.pop_front().unwrap();
1158 sender_window += update;
1159 }
1160
1161 // Sender sends data frames.
1162 let sender_progressed = if sender_window > 0 {
1163 let to_send = min(DATA_FRAME_SIZE, sender_window);
1164 send_to_recv.push_back((now, to_send));
1165 sender_window -= to_send;
1166 now += Duration::from_secs_f64(to_send as f64 * 8.0 / bandwidth as f64);
1167 true
1168 } else {
1169 false
1170 };
1171
1172 // Receiver receives data frames.
1173 let mut receiver_progressed = false;
1174 if send_to_recv.front().is_some_and(|(at, _)| *at <= now) {
1175 let (_, data) = send_to_recv.pop_front().unwrap();
1176 let consumed = fc.set_consumed(fc.retired() + data)?;
1177 fc.add_retired(consumed);
1178
1179 // Receiver sends window updates.
1180 let prev_max_allowed = fc.max_allowed;
1181 if write_frames(&mut fc, rtt, now) == 1 {
1182 recv_to_send.push_front((now, fc.max_allowed - prev_max_allowed));
1183 receiver_progressed = true;
1184 if last_max_active < fc.max_active() {
1185 last_max_active = fc.max_active();
1186 last_max_active_changed = now;
1187 }
1188 }
1189 }
1190
1191 // When idle, travel in (simulated) time.
1192 if !sender_progressed && !receiver_progressed {
1193 now = [recv_to_send.front(), send_to_recv.front()]
1194 .into_iter()
1195 .flatten()
1196 .map(|(at, _)| *at)
1197 .min()
1198 .expect("both are None");
1199 }
1200
1201 // Consider auto-tuning done once receive window hasn't changed for 4 RTT.
1202 if now.duration_since(last_max_active_changed) > 4 * rtt {
1203 break;
1204 }
1205 }
1206
1207 let summary = format!(
1208 "Got receive window of {} MiB on connection with bandwidth {} MBit/s ({bandwidth} Bit/s), delay {rtt:?}, bdp {} MiB.",
1209 fc.max_active() / 1024 / 1024,
1210 bandwidth / 1_000 / 1_000,
1211 bdp / 1024 / 1024,
1212 );
1213
1214 assert!(
1215 fc.max_active() + TOLERANCE >= bdp || fc.max_active() == MAX_RECV_WINDOW_SIZE,
1216 "{summary} Receive window is smaller than the bdp."
1217 );
1218 assert!(
1219 fc.max_active - TOLERANCE <= bdp
1220 || fc.max_active == INITIAL_RECV_WINDOW_SIZE as u64,
1221 "{summary} Receive window is larger than the bdp."
1222 );
1223
1224 qdebug!("{summary}");
1225 }
1226
1227 Ok(())
1228 }
1229
1230 #[test]
1231 fn max_active_larger_max_varint() {
1232 // Instead of doing proper connection flow control, Neqo simply sets
1233 // the largest connection flow control limit possible.
1234 let max_data = ConnectionParameters::default().get_max_data();
1235 assert_eq!(max_data, MAX_VARINT);
1236 let mut fc = ReceiverFlowControl::new((), max_data);
1237
1238 // Say that the remote consumes 1 byte of that connection flow control
1239 // limit and then requests a connection flow control update.
1240 fc.consume(1).unwrap();
1241 fc.add_retired(1);
1242 fc.send_flowc_update();
1243
1244 // Neqo should never attempt writing a connection flow control update
1245 // larger than the largest possible QUIC varint value.
1246 let mut builder = PacketBuilder::short(Encoder::new(), false, None::<&[u8]>);
1247 let mut tokens = Vec::new();
1248 fc.write_frames(&mut builder, &mut tokens, &mut FrameStats::default());
1249 }
1250 }