/src/openssl/ssl/quic/quic_fc.c
Line | Count | Source (jump to first uncovered line) |
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 | } |