quiche/
flowcontrol.rs

1// Copyright (C) 2021, 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::time::Duration;
28use std::time::Instant;
29
30// When autotuning the receiver window, decide how much
31// we increase the window.
32const WINDOW_INCREASE_FACTOR: u64 = 2;
33
34// When autotuning the receiver window, check if the last
35// update is within RTT * this constant.
36const WINDOW_TRIGGER_FACTOR: u32 = 2;
37
38#[derive(Default, Debug)]
39pub struct FlowControl {
40    /// Total consumed bytes by the receiver.
41    consumed: u64,
42
43    /// Flow control limit.
44    max_data: u64,
45
46    /// The receive window. This value is used for updating
47    /// flow control limit.
48    window: u64,
49
50    /// The maximum receive window.
51    max_window: u64,
52
53    /// Last update time of max_data for autotuning the window.
54    last_update: Option<Instant>,
55}
56
57impl FlowControl {
58    pub fn new(max_data: u64, window: u64, max_window: u64) -> Self {
59        Self {
60            max_data,
61
62            window: std::cmp::min(window, max_window),
63
64            max_window,
65
66            ..Default::default()
67        }
68    }
69
70    /// Returns the current window size.
71    pub fn window(&self) -> u64 {
72        self.window
73    }
74
75    /// Returns the current flow limit.
76    pub fn max_data(&self) -> u64 {
77        self.max_data
78    }
79
80    /// Returns the consumed bytes by the receiver.
81    #[cfg(test)]
82    pub fn consumed(&self) -> u64 {
83        self.consumed
84    }
85
86    /// Update consumed bytes.
87    pub fn add_consumed(&mut self, consumed: u64) {
88        self.consumed += consumed;
89    }
90
91    /// Returns true if the flow control needs to update max_data.
92    ///
93    /// This happens when the available window is smaller than the half
94    /// of the current window.
95    pub fn should_update_max_data(&self) -> bool {
96        let available_window = self.max_data - self.consumed;
97
98        available_window < (self.window / 2)
99    }
100
101    /// Returns the new max_data limit.
102    pub fn max_data_next(&self) -> u64 {
103        self.consumed + self.window
104    }
105
106    /// Commits the new max_data limit.
107    pub fn update_max_data(&mut self, now: Instant) {
108        self.max_data = self.max_data_next();
109        self.last_update = Some(now);
110    }
111
112    /// Autotune the window size. When there is an another update
113    /// within RTT x 2, bump the window x 2, capped by
114    /// max_window.
115    pub fn autotune_window(&mut self, now: Instant, rtt: Duration) {
116        if let Some(last_update) = self.last_update {
117            if now - last_update < rtt * WINDOW_TRIGGER_FACTOR {
118                self.set_window(self.window * WINDOW_INCREASE_FACTOR);
119            }
120        }
121    }
122
123    fn set_window(&mut self, window: u64) {
124        self.window = std::cmp::min(window, self.max_window);
125    }
126
127    /// If the current window has not yet been updated by `autotune_window`
128    pub fn set_window_if_not_tuned_yet(&mut self, window: u64) {
129        if self.last_update.is_none() {
130            self.set_window(window);
131        }
132    }
133
134    /// Make sure the lower bound of the window is same to
135    /// the current window.
136    pub fn ensure_window_lower_bound(&mut self, min_window: u64) {
137        if min_window > self.window {
138            // ... we still need to clamp to `max_window`
139            self.set_window(min_window);
140        }
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147
148    #[test]
149    fn max_window_in_new() {
150        let fc = FlowControl::new(100, 100, 50);
151        assert_eq!(fc.max_data(), 100);
152        assert_eq!(fc.window, 50);
153    }
154
155    #[test]
156    fn max_data() {
157        let fc = FlowControl::new(100, 20, 100);
158
159        assert_eq!(fc.max_data(), 100);
160    }
161
162    #[test]
163    fn should_update_max_data() {
164        let mut fc = FlowControl::new(100, 20, 100);
165
166        fc.add_consumed(85);
167        assert!(!fc.should_update_max_data());
168
169        fc.add_consumed(10);
170        assert!(fc.should_update_max_data());
171    }
172
173    #[test]
174    fn max_data_next() {
175        let mut fc = FlowControl::new(100, 20, 100);
176
177        let consumed = 95;
178
179        fc.add_consumed(consumed);
180        assert!(fc.should_update_max_data());
181        assert_eq!(fc.max_data_next(), consumed + 20);
182    }
183
184    #[test]
185    fn update_max_data() {
186        let mut fc = FlowControl::new(100, 20, 100);
187
188        let consumed = 95;
189
190        fc.add_consumed(consumed);
191        assert!(fc.should_update_max_data());
192
193        let max_data_next = fc.max_data_next();
194        assert_eq!(fc.max_data_next(), consumed + 20);
195
196        fc.update_max_data(Instant::now());
197        assert_eq!(fc.max_data(), max_data_next);
198    }
199
200    #[test]
201    fn autotune_window() {
202        let w = 20;
203        let mut fc = FlowControl::new(100, w, 100);
204
205        let consumed = 95;
206
207        fc.add_consumed(consumed);
208        assert!(fc.should_update_max_data());
209
210        let max_data_next = fc.max_data_next();
211        assert_eq!(max_data_next, consumed + w);
212
213        fc.update_max_data(Instant::now());
214        assert_eq!(fc.max_data(), max_data_next);
215
216        // Window size should be doubled.
217        fc.autotune_window(Instant::now(), Duration::from_millis(100));
218
219        let w = w * 2;
220        let consumed_inc = 15;
221
222        fc.add_consumed(consumed_inc);
223        assert!(fc.should_update_max_data());
224
225        let max_data_next = fc.max_data_next();
226        assert_eq!(max_data_next, consumed + consumed_inc + w);
227    }
228
229    #[test]
230    fn ensure_window_lower_bound() {
231        let w = 20;
232        let mut fc = FlowControl::new(100, w, 100);
233
234        // Window doesn't change.
235        fc.ensure_window_lower_bound(w);
236        assert_eq!(fc.window(), 20);
237
238        // Window changed to the new value.
239        fc.ensure_window_lower_bound(w * 2);
240        assert_eq!(fc.window(), 40);
241
242        // Window clamped to max_window
243        fc.ensure_window_lower_bound(101);
244        assert_eq!(fc.window(), 100);
245    }
246}
quiche/flowcontrol.rs

quiche/
flowcontrol.rs
