2 * Copyright 2022-2024 The OpenSSL Project Authors. All Rights Reserved.
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
10 #include "internal/quic_fc.h"
11 #include "internal/quic_error.h"
12 #include "internal/common.h"
13 #include "internal/safe_math.h"
16 OSSL_SAFE_MATH_UNSIGNED(uint64_t, uint64_t)
19 * TX Flow Controller (TXFC)
20 * =========================
23 int ossl_quic_txfc_init(QUIC_TXFC
*txfc
, QUIC_TXFC
*conn_txfc
)
25 if (conn_txfc
!= NULL
&& conn_txfc
->parent
!= NULL
)
30 txfc
->parent
= conn_txfc
;
31 txfc
->has_become_blocked
= 0;
35 QUIC_TXFC
*ossl_quic_txfc_get_parent(QUIC_TXFC
*txfc
)
40 int ossl_quic_txfc_bump_cwm(QUIC_TXFC
*txfc
, uint64_t cwm
)
49 uint64_t ossl_quic_txfc_get_credit_local(QUIC_TXFC
*txfc
, uint64_t consumed
)
51 assert((txfc
->swm
+ consumed
) <= txfc
->cwm
);
52 return txfc
->cwm
- (consumed
+ txfc
->swm
);
55 uint64_t ossl_quic_txfc_get_credit(QUIC_TXFC
*txfc
, uint64_t consumed
)
59 r
= ossl_quic_txfc_get_credit_local(txfc
, 0);
61 if (txfc
->parent
!= NULL
) {
62 assert(txfc
->parent
->parent
== NULL
);
63 conn_r
= ossl_quic_txfc_get_credit_local(txfc
->parent
, consumed
);
71 int ossl_quic_txfc_consume_credit_local(QUIC_TXFC
*txfc
, uint64_t num_bytes
)
74 uint64_t credit
= ossl_quic_txfc_get_credit_local(txfc
, 0);
76 if (num_bytes
> credit
) {
81 if (num_bytes
> 0 && num_bytes
== credit
)
82 txfc
->has_become_blocked
= 1;
84 txfc
->swm
+= num_bytes
;
88 int ossl_quic_txfc_consume_credit(QUIC_TXFC
*txfc
, uint64_t num_bytes
)
90 int ok
= ossl_quic_txfc_consume_credit_local(txfc
, num_bytes
);
92 if (txfc
->parent
!= NULL
) {
93 assert(txfc
->parent
->parent
== NULL
);
94 if (!ossl_quic_txfc_consume_credit_local(txfc
->parent
, num_bytes
))
101 int ossl_quic_txfc_has_become_blocked(QUIC_TXFC
*txfc
, int clear
)
103 int r
= txfc
->has_become_blocked
;
106 txfc
->has_become_blocked
= 0;
111 uint64_t ossl_quic_txfc_get_cwm(QUIC_TXFC
*txfc
)
116 uint64_t ossl_quic_txfc_get_swm(QUIC_TXFC
*txfc
)
122 * RX Flow Controller (RXFC)
123 * =========================
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
),
132 if (conn_rxfc
!= NULL
&& conn_rxfc
->parent
!= NULL
)
136 rxfc
->cwm
= initial_window_size
;
140 rxfc
->cur_window_size
= initial_window_size
;
141 rxfc
->max_window_size
= max_window_size
;
142 rxfc
->parent
= conn_rxfc
;
143 rxfc
->error_code
= 0;
144 rxfc
->has_cwm_changed
= 0;
145 rxfc
->epoch_start
= ossl_time_zero();
147 rxfc
->now_arg
= now_arg
;
149 rxfc
->standalone
= 0;
153 int ossl_quic_rxfc_init_standalone(QUIC_RXFC
*rxfc
,
154 uint64_t initial_window_size
,
155 OSSL_TIME (*now
)(void *arg
),
158 if (!ossl_quic_rxfc_init(rxfc
, NULL
,
159 initial_window_size
, initial_window_size
,
163 rxfc
->standalone
= 1;
167 QUIC_RXFC
*ossl_quic_rxfc_get_parent(QUIC_RXFC
*rxfc
)
172 void ossl_quic_rxfc_set_max_window_size(QUIC_RXFC
*rxfc
,
173 size_t max_window_size
)
175 rxfc
->max_window_size
= max_window_size
;
178 static void rxfc_start_epoch(QUIC_RXFC
*rxfc
)
180 rxfc
->epoch_start
= rxfc
->now(rxfc
->now_arg
);
181 rxfc
->esrwm
= rxfc
->rwm
;
184 static int on_rx_controlled_bytes(QUIC_RXFC
*rxfc
, uint64_t num_bytes
)
187 uint64_t credit
= rxfc
->cwm
- rxfc
->swm
;
189 if (num_bytes
> credit
) {
192 rxfc
->error_code
= OSSL_QUIC_ERR_FLOW_CONTROL_ERROR
;
195 rxfc
->swm
+= num_bytes
;
199 int ossl_quic_rxfc_on_rx_stream_frame(QUIC_RXFC
*rxfc
, uint64_t end
, int is_fin
)
203 if (!rxfc
->standalone
&& rxfc
->parent
== NULL
)
206 if (rxfc
->is_fin
&& ((is_fin
&& rxfc
->hwm
!= end
) || end
> rxfc
->hwm
)) {
207 /* Stream size cannot change after the stream is finished */
208 rxfc
->error_code
= OSSL_QUIC_ERR_FINAL_SIZE_ERROR
;
209 return 1; /* not a caller error */
215 if (end
> rxfc
->hwm
) {
216 delta
= end
- rxfc
->hwm
;
219 on_rx_controlled_bytes(rxfc
, delta
); /* result ignored */
220 if (rxfc
->parent
!= NULL
)
221 on_rx_controlled_bytes(rxfc
->parent
, delta
); /* result ignored */
222 } else if (end
< rxfc
->hwm
&& is_fin
) {
223 rxfc
->error_code
= OSSL_QUIC_ERR_FINAL_SIZE_ERROR
;
224 return 1; /* not a caller error */
230 /* threshold = 3/4 */
231 #define WINDOW_THRESHOLD_NUM 3
232 #define WINDOW_THRESHOLD_DEN 4
234 static int rxfc_cwm_bump_desired(QUIC_RXFC
*rxfc
)
237 uint64_t window_rem
= rxfc
->cwm
- rxfc
->rwm
;
239 = safe_muldiv_uint64_t(rxfc
->cur_window_size
,
240 WINDOW_THRESHOLD_NUM
, WINDOW_THRESHOLD_DEN
, &err
);
244 * Extremely large window should never occur, but if it does, just use
245 * 1/2 as the threshold.
247 threshold
= rxfc
->cur_window_size
/ 2;
250 * No point emitting a new MAX_STREAM_DATA frame if the stream has a final
253 return !rxfc
->is_fin
&& window_rem
<= threshold
;
256 static int rxfc_should_bump_window_size(QUIC_RXFC
*rxfc
, OSSL_TIME rtt
)
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.
266 * dw = b / window_size
268 * T_window = dt / (b / window_size)
269 * T_window = (dt * window_size) / b
271 * We bump the window size if T_window < 4 * RTT.
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.
277 uint64_t b
= rxfc
->rwm
- rxfc
->esrwm
;
278 OSSL_TIME now
, dt
, t_window
;
283 now
= rxfc
->now(rxfc
->now_arg
);
284 dt
= ossl_time_subtract(now
, rxfc
->epoch_start
);
285 t_window
= ossl_time_muldiv(dt
, rxfc
->cur_window_size
, b
);
287 return ossl_time_compare(t_window
, ossl_time_multiply(rtt
, 4)) < 0;
290 static void rxfc_adjust_window_size(QUIC_RXFC
*rxfc
, uint64_t min_window_size
,
293 /* Are we sending updates too often? */
294 uint64_t new_window_size
;
296 new_window_size
= rxfc
->cur_window_size
;
298 if (rxfc_should_bump_window_size(rxfc
, rtt
))
299 new_window_size
*= 2;
301 if (new_window_size
< min_window_size
)
302 new_window_size
= min_window_size
;
303 if (new_window_size
> rxfc
->max_window_size
) /* takes precedence over min size */
304 new_window_size
= rxfc
->max_window_size
;
306 rxfc
->cur_window_size
= new_window_size
;
307 rxfc_start_epoch(rxfc
);
310 static void rxfc_update_cwm(QUIC_RXFC
*rxfc
, uint64_t min_window_size
,
315 if (!rxfc_cwm_bump_desired(rxfc
))
318 rxfc_adjust_window_size(rxfc
, min_window_size
, rtt
);
320 new_cwm
= rxfc
->rwm
+ rxfc
->cur_window_size
;
321 if (new_cwm
> rxfc
->cwm
) {
323 rxfc
->has_cwm_changed
= 1;
327 static int rxfc_on_retire(QUIC_RXFC
*rxfc
, uint64_t num_bytes
,
328 uint64_t min_window_size
,
331 if (ossl_time_is_zero(rxfc
->epoch_start
))
332 /* This happens when we retire our first ever bytes. */
333 rxfc_start_epoch(rxfc
);
335 rxfc
->rwm
+= num_bytes
;
336 rxfc_update_cwm(rxfc
, min_window_size
, rtt
);
340 int ossl_quic_rxfc_on_retire(QUIC_RXFC
*rxfc
,
344 if (rxfc
->parent
== NULL
&& !rxfc
->standalone
)
350 if (rxfc
->rwm
+ num_bytes
> rxfc
->swm
)
351 /* Impossible for us to retire more bytes than we have received. */
354 rxfc_on_retire(rxfc
, num_bytes
, 0, rtt
);
356 if (!rxfc
->standalone
)
357 rxfc_on_retire(rxfc
->parent
, num_bytes
, rxfc
->cur_window_size
, rtt
);
362 uint64_t ossl_quic_rxfc_get_cwm(const QUIC_RXFC
*rxfc
)
367 uint64_t ossl_quic_rxfc_get_swm(const QUIC_RXFC
*rxfc
)
372 uint64_t ossl_quic_rxfc_get_rwm(const QUIC_RXFC
*rxfc
)
377 uint64_t ossl_quic_rxfc_get_credit(const QUIC_RXFC
*rxfc
)
379 return ossl_quic_rxfc_get_cwm(rxfc
) - ossl_quic_rxfc_get_swm(rxfc
);
382 int ossl_quic_rxfc_has_cwm_changed(QUIC_RXFC
*rxfc
, int clear
)
384 int r
= rxfc
->has_cwm_changed
;
387 rxfc
->has_cwm_changed
= 0;
392 int ossl_quic_rxfc_get_error(QUIC_RXFC
*rxfc
, int clear
)
394 int r
= rxfc
->error_code
;
397 rxfc
->error_code
= 0;
402 int ossl_quic_rxfc_get_final_size(const QUIC_RXFC
*rxfc
, uint64_t *final_size
)
407 if (final_size
!= NULL
)
408 *final_size
= rxfc
->hwm
;