/src/openssl/ssl/quic/quic_fc.c
Line  | Count  | Source  | 
1  |  | /*  | 
2  |  |  * Copyright 2022-2024 The OpenSSL Project Authors. All Rights Reserved.  | 
3  |  |  *  | 
4  |  |  * Licensed under the Apache License 2.0 (the "License").  You may not use  | 
5  |  |  * this file except in compliance with the License.  You can obtain a copy  | 
6  |  |  * in the file LICENSE in the source distribution or at  | 
7  |  |  * https://www.openssl.org/source/license.html  | 
8  |  |  */  | 
9  |  |  | 
10  |  | #include "internal/quic_fc.h"  | 
11  |  | #include "internal/quic_error.h"  | 
12  |  | #include "internal/common.h"  | 
13  |  | #include "internal/safe_math.h"  | 
14  |  | #include <assert.h>  | 
15  |  |  | 
16  |  | OSSL_SAFE_MATH_UNSIGNED(uint64_t, uint64_t)  | 
17  |  |  | 
18  |  | /*  | 
19  |  |  * TX Flow Controller (TXFC)  | 
20  |  |  * =========================  | 
21  |  |  */  | 
22  |  |  | 
23  |  | int ossl_quic_txfc_init(QUIC_TXFC *txfc, QUIC_TXFC *conn_txfc)  | 
24  | 0  | { | 
25  | 0  |     if (conn_txfc != NULL && conn_txfc->parent != NULL)  | 
26  | 0  |         return 0;  | 
27  |  |  | 
28  | 0  |     txfc->swm                   = 0;  | 
29  | 0  |     txfc->cwm                   = 0;  | 
30  | 0  |     txfc->parent                = conn_txfc;  | 
31  | 0  |     txfc->has_become_blocked    = 0;  | 
32  | 0  |     return 1;  | 
33  | 0  | }  | 
34  |  |  | 
35  |  | QUIC_TXFC *ossl_quic_txfc_get_parent(QUIC_TXFC *txfc)  | 
36  | 0  | { | 
37  | 0  |     return txfc->parent;  | 
38  | 0  | }  | 
39  |  |  | 
40  |  | int ossl_quic_txfc_bump_cwm(QUIC_TXFC *txfc, uint64_t cwm)  | 
41  | 0  | { | 
42  | 0  |     if (cwm <= txfc->cwm)  | 
43  | 0  |         return 0;  | 
44  |  |  | 
45  | 0  |     txfc->cwm = cwm;  | 
46  | 0  |     return 1;  | 
47  | 0  | }  | 
48  |  |  | 
49  |  | uint64_t ossl_quic_txfc_get_credit_local(QUIC_TXFC *txfc, uint64_t consumed)  | 
50  | 0  | { | 
51  | 0  |     assert((txfc->swm + consumed) <= txfc->cwm);  | 
52  | 0  |     return txfc->cwm - (consumed + txfc->swm);  | 
53  | 0  | }  | 
54  |  |  | 
55  |  | uint64_t ossl_quic_txfc_get_credit(QUIC_TXFC *txfc, uint64_t consumed)  | 
56  | 0  | { | 
57  | 0  |     uint64_t r, conn_r;  | 
58  |  | 
  | 
59  | 0  |     r = ossl_quic_txfc_get_credit_local(txfc, 0);  | 
60  |  | 
  | 
61  | 0  |     if (txfc->parent != NULL) { | 
62  | 0  |         assert(txfc->parent->parent == NULL);  | 
63  | 0  |         conn_r = ossl_quic_txfc_get_credit_local(txfc->parent, consumed);  | 
64  | 0  |         if (conn_r < r)  | 
65  | 0  |             r = conn_r;  | 
66  | 0  |     }  | 
67  |  | 
  | 
68  | 0  |     return r;  | 
69  | 0  | }  | 
70  |  |  | 
71  |  | int ossl_quic_txfc_consume_credit_local(QUIC_TXFC *txfc, uint64_t num_bytes)  | 
72  | 0  | { | 
73  | 0  |     int ok = 1;  | 
74  | 0  |     uint64_t credit = ossl_quic_txfc_get_credit_local(txfc, 0);  | 
75  |  | 
  | 
76  | 0  |     if (num_bytes > credit) { | 
77  | 0  |         ok = 0;  | 
78  | 0  |         num_bytes = credit;  | 
79  | 0  |     }  | 
80  |  | 
  | 
81  | 0  |     if (num_bytes > 0 && num_bytes == credit)  | 
82  | 0  |         txfc->has_become_blocked = 1;  | 
83  |  | 
  | 
84  | 0  |     txfc->swm += num_bytes;  | 
85  | 0  |     return ok;  | 
86  | 0  | }  | 
87  |  |  | 
88  |  | int ossl_quic_txfc_consume_credit(QUIC_TXFC *txfc, uint64_t num_bytes)  | 
89  | 0  | { | 
90  | 0  |     int ok = ossl_quic_txfc_consume_credit_local(txfc, num_bytes);  | 
91  |  | 
  | 
92  | 0  |     if (txfc->parent != NULL) { | 
93  | 0  |         assert(txfc->parent->parent == NULL);  | 
94  | 0  |         if (!ossl_quic_txfc_consume_credit_local(txfc->parent, num_bytes))  | 
95  | 0  |             return 0;  | 
96  | 0  |     }  | 
97  |  |  | 
98  | 0  |     return ok;  | 
99  | 0  | }  | 
100  |  |  | 
101  |  | int ossl_quic_txfc_has_become_blocked(QUIC_TXFC *txfc, int clear)  | 
102  | 0  | { | 
103  | 0  |     int r = txfc->has_become_blocked;  | 
104  |  | 
  | 
105  | 0  |     if (clear)  | 
106  | 0  |         txfc->has_become_blocked = 0;  | 
107  |  | 
  | 
108  | 0  |     return r;  | 
109  | 0  | }  | 
110  |  |  | 
111  |  | uint64_t ossl_quic_txfc_get_cwm(QUIC_TXFC *txfc)  | 
112  | 0  | { | 
113  | 0  |     return txfc->cwm;  | 
114  | 0  | }  | 
115  |  |  | 
116  |  | uint64_t ossl_quic_txfc_get_swm(QUIC_TXFC *txfc)  | 
117  | 0  | { | 
118  | 0  |     return txfc->swm;  | 
119  | 0  | }  | 
120  |  |  | 
121  |  | /*  | 
122  |  |  * RX Flow Controller (RXFC)  | 
123  |  |  * =========================  | 
124  |  |  */  | 
125  |  |  | 
126  |  | int ossl_quic_rxfc_init(QUIC_RXFC *rxfc, QUIC_RXFC *conn_rxfc,  | 
127  |  |                         uint64_t initial_window_size,  | 
128  |  |                         uint64_t max_window_size,  | 
129  |  |                         OSSL_TIME (*now)(void *now_arg),  | 
130  |  |                         void *now_arg)  | 
131  | 0  | { | 
132  | 0  |     if (conn_rxfc != NULL && conn_rxfc->parent != NULL)  | 
133  | 0  |         return 0;  | 
134  |  |  | 
135  | 0  |     rxfc->swm               = 0;  | 
136  | 0  |     rxfc->cwm               = initial_window_size;  | 
137  | 0  |     rxfc->rwm               = 0;  | 
138  | 0  |     rxfc->esrwm             = 0;  | 
139  | 0  |     rxfc->hwm               = 0;  | 
140  | 0  |     rxfc->cur_window_size   = initial_window_size;  | 
141  | 0  |     rxfc->max_window_size   = max_window_size;  | 
142  | 0  |     rxfc->parent            = conn_rxfc;  | 
143  | 0  |     rxfc->error_code        = 0;  | 
144  | 0  |     rxfc->has_cwm_changed   = 0;  | 
145  | 0  |     rxfc->epoch_start       = ossl_time_zero();  | 
146  | 0  |     rxfc->now               = now;  | 
147  | 0  |     rxfc->now_arg           = now_arg;  | 
148  | 0  |     rxfc->is_fin            = 0;  | 
149  | 0  |     rxfc->standalone        = 0;  | 
150  | 0  |     return 1;  | 
151  | 0  | }  | 
152  |  |  | 
153  |  | int ossl_quic_rxfc_init_standalone(QUIC_RXFC *rxfc,  | 
154  |  |                                    uint64_t initial_window_size,  | 
155  |  |                                    OSSL_TIME (*now)(void *arg),  | 
156  |  |                                    void *now_arg)  | 
157  | 0  | { | 
158  | 0  |     if (!ossl_quic_rxfc_init(rxfc, NULL,  | 
159  | 0  |                              initial_window_size, initial_window_size,  | 
160  | 0  |                              now, now_arg))  | 
161  | 0  |         return 0;  | 
162  |  |  | 
163  | 0  |     rxfc->standalone = 1;  | 
164  | 0  |     return 1;  | 
165  | 0  | }  | 
166  |  |  | 
167  |  | QUIC_RXFC *ossl_quic_rxfc_get_parent(QUIC_RXFC *rxfc)  | 
168  | 0  | { | 
169  | 0  |     return rxfc->parent;  | 
170  | 0  | }  | 
171  |  |  | 
172  |  | void ossl_quic_rxfc_set_max_window_size(QUIC_RXFC *rxfc,  | 
173  |  |                                         size_t max_window_size)  | 
174  | 0  | { | 
175  | 0  |     rxfc->max_window_size = max_window_size;  | 
176  | 0  | }  | 
177  |  |  | 
178  |  | static void rxfc_start_epoch(QUIC_RXFC *rxfc)  | 
179  | 0  | { | 
180  | 0  |     rxfc->epoch_start   = rxfc->now(rxfc->now_arg);  | 
181  | 0  |     rxfc->esrwm         = rxfc->rwm;  | 
182  | 0  | }  | 
183  |  |  | 
184  |  | static int on_rx_controlled_bytes(QUIC_RXFC *rxfc, uint64_t num_bytes)  | 
185  | 0  | { | 
186  | 0  |     int ok = 1;  | 
187  | 0  |     uint64_t credit = rxfc->cwm - rxfc->swm;  | 
188  |  | 
  | 
189  | 0  |     if (num_bytes > credit) { | 
190  | 0  |         ok = 0;  | 
191  | 0  |         num_bytes = credit;  | 
192  | 0  |         rxfc->error_code = OSSL_QUIC_ERR_FLOW_CONTROL_ERROR;  | 
193  | 0  |     }  | 
194  |  | 
  | 
195  | 0  |     rxfc->swm += num_bytes;  | 
196  | 0  |     return ok;  | 
197  | 0  | }  | 
198  |  |  | 
199  |  | int ossl_quic_rxfc_on_rx_stream_frame(QUIC_RXFC *rxfc, uint64_t end, int is_fin)  | 
200  | 0  | { | 
201  | 0  |     uint64_t delta;  | 
202  |  | 
  | 
203  | 0  |     if (!rxfc->standalone && rxfc->parent == NULL)  | 
204  | 0  |         return 0;  | 
205  |  |  | 
206  | 0  |     if (rxfc->is_fin && ((is_fin && rxfc->hwm != end) || end > rxfc->hwm)) { | 
207  |  |         /* Stream size cannot change after the stream is finished */  | 
208  | 0  |         rxfc->error_code = OSSL_QUIC_ERR_FINAL_SIZE_ERROR;  | 
209  | 0  |         return 1; /* not a caller error */  | 
210  | 0  |     }  | 
211  |  |  | 
212  | 0  |     if (is_fin)  | 
213  | 0  |         rxfc->is_fin = 1;  | 
214  |  | 
  | 
215  | 0  |     if (end > rxfc->hwm) { | 
216  | 0  |         delta = end - rxfc->hwm;  | 
217  | 0  |         rxfc->hwm = end;  | 
218  |  | 
  | 
219  | 0  |         on_rx_controlled_bytes(rxfc, delta);             /* result ignored */  | 
220  | 0  |         if (rxfc->parent != NULL)  | 
221  | 0  |             on_rx_controlled_bytes(rxfc->parent, delta); /* result ignored */  | 
222  | 0  |     } else if (end < rxfc->hwm && is_fin) { | 
223  | 0  |         rxfc->error_code = OSSL_QUIC_ERR_FINAL_SIZE_ERROR;  | 
224  | 0  |         return 1; /* not a caller error */  | 
225  | 0  |     }  | 
226  |  |  | 
227  | 0  |     return 1;  | 
228  | 0  | }  | 
229  |  |  | 
230  |  | /* threshold = 3/4 */  | 
231  | 0  | #define WINDOW_THRESHOLD_NUM 3  | 
232  | 0  | #define WINDOW_THRESHOLD_DEN 4  | 
233  |  |  | 
234  |  | static int rxfc_cwm_bump_desired(QUIC_RXFC *rxfc)  | 
235  | 0  | { | 
236  | 0  |     int err = 0;  | 
237  | 0  |     uint64_t window_rem = rxfc->cwm - rxfc->rwm;  | 
238  | 0  |     uint64_t threshold  | 
239  | 0  |         = safe_muldiv_uint64_t(rxfc->cur_window_size,  | 
240  | 0  |                                WINDOW_THRESHOLD_NUM, WINDOW_THRESHOLD_DEN, &err);  | 
241  |  | 
  | 
242  | 0  |     if (err)  | 
243  |  |         /*  | 
244  |  |          * Extremely large window should never occur, but if it does, just use  | 
245  |  |          * 1/2 as the threshold.  | 
246  |  |          */  | 
247  | 0  |         threshold = rxfc->cur_window_size / 2;  | 
248  |  |  | 
249  |  |     /*  | 
250  |  |      * No point emitting a new MAX_STREAM_DATA frame if the stream has a final  | 
251  |  |      * size.  | 
252  |  |      */  | 
253  | 0  |     return !rxfc->is_fin && window_rem <= threshold;  | 
254  | 0  | }  | 
255  |  |  | 
256  |  | static int rxfc_should_bump_window_size(QUIC_RXFC *rxfc, OSSL_TIME rtt)  | 
257  | 0  | { | 
258  |  |     /*  | 
259  |  |      * dt: time since start of epoch  | 
260  |  |      * b:  bytes of window consumed since start of epoch  | 
261  |  |      * dw: proportion of window consumed since start of epoch  | 
262  |  |      * T_window: time it will take to use up the entire window, based on dt, dw  | 
263  |  |      * RTT: The current estimated RTT.  | 
264  |  |      *  | 
265  |  |      * b        = rwm - esrwm  | 
266  |  |      * dw       = b / window_size  | 
267  |  |      * T_window = dt / dw  | 
268  |  |      * T_window = dt / (b / window_size)  | 
269  |  |      * T_window = (dt * window_size) / b  | 
270  |  |      *  | 
271  |  |      * We bump the window size if T_window < 4 * RTT.  | 
272  |  |      *  | 
273  |  |      * We leave the division by b on the LHS to reduce the risk of overflowing  | 
274  |  |      * our 64-bit nanosecond representation, which will afford plenty of  | 
275  |  |      * precision left over after the division anyway.  | 
276  |  |      */  | 
277  | 0  |     uint64_t  b = rxfc->rwm - rxfc->esrwm;  | 
278  | 0  |     OSSL_TIME now, dt, t_window;  | 
279  |  | 
  | 
280  | 0  |     if (b == 0)  | 
281  | 0  |         return 0;  | 
282  |  |  | 
283  | 0  |     now      = rxfc->now(rxfc->now_arg);  | 
284  | 0  |     dt       = ossl_time_subtract(now, rxfc->epoch_start);  | 
285  | 0  |     t_window = ossl_time_muldiv(dt, rxfc->cur_window_size, b);  | 
286  |  | 
  | 
287  | 0  |     return ossl_time_compare(t_window, ossl_time_multiply(rtt, 4)) < 0;  | 
288  | 0  | }  | 
289  |  |  | 
290  |  | static void rxfc_adjust_window_size(QUIC_RXFC *rxfc, uint64_t min_window_size,  | 
291  |  |                                     OSSL_TIME rtt)  | 
292  | 0  | { | 
293  |  |     /* Are we sending updates too often? */  | 
294  | 0  |     uint64_t new_window_size;  | 
295  |  | 
  | 
296  | 0  |     new_window_size = rxfc->cur_window_size;  | 
297  |  | 
  | 
298  | 0  |     if (rxfc_should_bump_window_size(rxfc, rtt))  | 
299  | 0  |         new_window_size *= 2;  | 
300  |  | 
  | 
301  | 0  |     if (new_window_size < min_window_size)  | 
302  | 0  |         new_window_size = min_window_size;  | 
303  | 0  |     if (new_window_size > rxfc->max_window_size) /* takes precedence over min size */  | 
304  | 0  |         new_window_size = rxfc->max_window_size;  | 
305  |  | 
  | 
306  | 0  |     rxfc->cur_window_size = new_window_size;  | 
307  | 0  |     rxfc_start_epoch(rxfc);  | 
308  | 0  | }  | 
309  |  |  | 
310  |  | static void rxfc_update_cwm(QUIC_RXFC *rxfc, uint64_t min_window_size,  | 
311  |  |                             OSSL_TIME rtt)  | 
312  | 0  | { | 
313  | 0  |     uint64_t new_cwm;  | 
314  |  | 
  | 
315  | 0  |     if (!rxfc_cwm_bump_desired(rxfc))  | 
316  | 0  |         return;  | 
317  |  |  | 
318  | 0  |     rxfc_adjust_window_size(rxfc, min_window_size, rtt);  | 
319  |  | 
  | 
320  | 0  |     new_cwm = rxfc->rwm + rxfc->cur_window_size;  | 
321  | 0  |     if (new_cwm > rxfc->cwm) { | 
322  | 0  |         rxfc->cwm = new_cwm;  | 
323  | 0  |         rxfc->has_cwm_changed = 1;  | 
324  | 0  |     }  | 
325  | 0  | }  | 
326  |  |  | 
327  |  | static int rxfc_on_retire(QUIC_RXFC *rxfc, uint64_t num_bytes,  | 
328  |  |                           uint64_t min_window_size,  | 
329  |  |                           OSSL_TIME rtt)  | 
330  | 0  | { | 
331  | 0  |     if (ossl_time_is_zero(rxfc->epoch_start))  | 
332  |  |         /* This happens when we retire our first ever bytes. */  | 
333  | 0  |         rxfc_start_epoch(rxfc);  | 
334  |  | 
  | 
335  | 0  |     rxfc->rwm += num_bytes;  | 
336  | 0  |     rxfc_update_cwm(rxfc, min_window_size, rtt);  | 
337  | 0  |     return 1;  | 
338  | 0  | }  | 
339  |  |  | 
340  |  | int ossl_quic_rxfc_on_retire(QUIC_RXFC *rxfc,  | 
341  |  |                              uint64_t num_bytes,  | 
342  |  |                              OSSL_TIME rtt)  | 
343  | 0  | { | 
344  | 0  |     if (rxfc->parent == NULL && !rxfc->standalone)  | 
345  | 0  |         return 0;  | 
346  |  |  | 
347  | 0  |     if (num_bytes == 0)  | 
348  | 0  |         return 1;  | 
349  |  |  | 
350  | 0  |     if (rxfc->rwm + num_bytes > rxfc->swm)  | 
351  |  |         /* Impossible for us to retire more bytes than we have received. */  | 
352  | 0  |         return 0;  | 
353  |  |  | 
354  | 0  |     rxfc_on_retire(rxfc, num_bytes, 0, rtt);  | 
355  |  | 
  | 
356  | 0  |     if (!rxfc->standalone)  | 
357  | 0  |         rxfc_on_retire(rxfc->parent, num_bytes, rxfc->cur_window_size, rtt);  | 
358  |  | 
  | 
359  | 0  |     return 1;  | 
360  | 0  | }  | 
361  |  |  | 
362  |  | uint64_t ossl_quic_rxfc_get_cwm(const QUIC_RXFC *rxfc)  | 
363  | 0  | { | 
364  | 0  |     return rxfc->cwm;  | 
365  | 0  | }  | 
366  |  |  | 
367  |  | uint64_t ossl_quic_rxfc_get_swm(const QUIC_RXFC *rxfc)  | 
368  | 0  | { | 
369  | 0  |     return rxfc->swm;  | 
370  | 0  | }  | 
371  |  |  | 
372  |  | uint64_t ossl_quic_rxfc_get_rwm(const QUIC_RXFC *rxfc)  | 
373  | 0  | { | 
374  | 0  |     return rxfc->rwm;  | 
375  | 0  | }  | 
376  |  |  | 
377  |  | uint64_t ossl_quic_rxfc_get_credit(const QUIC_RXFC *rxfc)  | 
378  | 0  | { | 
379  | 0  |     return ossl_quic_rxfc_get_cwm(rxfc) - ossl_quic_rxfc_get_swm(rxfc);  | 
380  | 0  | }  | 
381  |  |  | 
382  |  | int ossl_quic_rxfc_has_cwm_changed(QUIC_RXFC *rxfc, int clear)  | 
383  | 0  | { | 
384  | 0  |     int r = rxfc->has_cwm_changed;  | 
385  |  | 
  | 
386  | 0  |     if (clear)  | 
387  | 0  |         rxfc->has_cwm_changed = 0;  | 
388  |  | 
  | 
389  | 0  |     return r;  | 
390  | 0  | }  | 
391  |  |  | 
392  |  | int ossl_quic_rxfc_get_error(QUIC_RXFC *rxfc, int clear)  | 
393  | 0  | { | 
394  | 0  |     int r = rxfc->error_code;  | 
395  |  | 
  | 
396  | 0  |     if (clear)  | 
397  | 0  |         rxfc->error_code = 0;  | 
398  |  | 
  | 
399  | 0  |     return r;  | 
400  | 0  | }  | 
401  |  |  | 
402  |  | int ossl_quic_rxfc_get_final_size(const QUIC_RXFC *rxfc, uint64_t *final_size)  | 
403  | 0  | { | 
404  | 0  |     if (!rxfc->is_fin)  | 
405  | 0  |         return 0;  | 
406  |  |  | 
407  | 0  |     if (final_size != NULL)  | 
408  | 0  |         *final_size = rxfc->hwm;  | 
409  |  | 
  | 
410  | 0  |     return 1;  | 
411  | 0  | }  |