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 { 25 if (conn_txfc != NULL && conn_txfc->parent != NULL) 26 return 0; 27 28 txfc->swm = 0; 29 txfc->cwm = 0; 30 txfc->parent = conn_txfc; 31 txfc->has_become_blocked = 0; 32 return 1; 33 } 34 35 QUIC_TXFC *ossl_quic_txfc_get_parent(QUIC_TXFC *txfc) 36 { 37 return txfc->parent; 38 } 39 40 int ossl_quic_txfc_bump_cwm(QUIC_TXFC *txfc, uint64_t cwm) 41 { 42 if (cwm <= txfc->cwm) 43 return 0; 44 45 txfc->cwm = cwm; 46 return 1; 47 } 48 49 uint64_t ossl_quic_txfc_get_credit_local(QUIC_TXFC *txfc, uint64_t consumed) 50 { 51 assert((txfc->swm + consumed) <= txfc->cwm); 52 return txfc->cwm - (consumed + txfc->swm); 53 } 54 55 uint64_t ossl_quic_txfc_get_credit(QUIC_TXFC *txfc, uint64_t consumed) 56 { 57 uint64_t r, conn_r; 58 59 r = ossl_quic_txfc_get_credit_local(txfc, 0); 60 61 if (txfc->parent != NULL) { 62 assert(txfc->parent->parent == NULL); 63 conn_r = ossl_quic_txfc_get_credit_local(txfc->parent, consumed); 64 if (conn_r < r) 65 r = conn_r; 66 } 67 68 return r; 69 } 70 71 int ossl_quic_txfc_consume_credit_local(QUIC_TXFC *txfc, uint64_t num_bytes) 72 { 73 int ok = 1; 74 uint64_t credit = ossl_quic_txfc_get_credit_local(txfc, 0); 75 76 if (num_bytes > credit) { 77 ok = 0; 78 num_bytes = credit; 79 } 80 81 if (num_bytes > 0 && num_bytes == credit) 82 txfc->has_become_blocked = 1; 83 84 txfc->swm += num_bytes; 85 return ok; 86 } 87 88 int ossl_quic_txfc_consume_credit(QUIC_TXFC *txfc, uint64_t num_bytes) 89 { 90 int ok = ossl_quic_txfc_consume_credit_local(txfc, num_bytes); 91 92 if (txfc->parent != NULL) { 93 assert(txfc->parent->parent == NULL); 94 if (!ossl_quic_txfc_consume_credit_local(txfc->parent, num_bytes)) 95 return 0; 96 } 97 98 return ok; 99 } 100 101 int ossl_quic_txfc_has_become_blocked(QUIC_TXFC *txfc, int clear) 102 { 103 int r = txfc->has_become_blocked; 104 105 if (clear) 106 txfc->has_become_blocked = 0; 107 108 return r; 109 } 110 111 uint64_t ossl_quic_txfc_get_cwm(QUIC_TXFC *txfc) 112 { 113 return txfc->cwm; 114 } 115 116 uint64_t ossl_quic_txfc_get_swm(QUIC_TXFC *txfc) 117 { 118 return txfc->swm; 119 } 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 { 132 if (conn_rxfc != NULL && conn_rxfc->parent != NULL) 133 return 0; 134 135 rxfc->swm = 0; 136 rxfc->cwm = initial_window_size; 137 rxfc->rwm = 0; 138 rxfc->esrwm = 0; 139 rxfc->hwm = 0; 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(); 146 rxfc->now = now; 147 rxfc->now_arg = now_arg; 148 rxfc->is_fin = 0; 149 rxfc->standalone = 0; 150 return 1; 151 } 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 { 158 if (!ossl_quic_rxfc_init(rxfc, NULL, 159 initial_window_size, initial_window_size, 160 now, now_arg)) 161 return 0; 162 163 rxfc->standalone = 1; 164 return 1; 165 } 166 167 QUIC_RXFC *ossl_quic_rxfc_get_parent(QUIC_RXFC *rxfc) 168 { 169 return rxfc->parent; 170 } 171 172 void ossl_quic_rxfc_set_max_window_size(QUIC_RXFC *rxfc, 173 size_t max_window_size) 174 { 175 rxfc->max_window_size = max_window_size; 176 } 177 178 static void rxfc_start_epoch(QUIC_RXFC *rxfc) 179 { 180 rxfc->epoch_start = rxfc->now(rxfc->now_arg); 181 rxfc->esrwm = rxfc->rwm; 182 } 183 184 static int on_rx_controlled_bytes(QUIC_RXFC *rxfc, uint64_t num_bytes) 185 { 186 int ok = 1; 187 uint64_t credit = rxfc->cwm - rxfc->swm; 188 189 if (num_bytes > credit) { 190 ok = 0; 191 num_bytes = credit; 192 rxfc->error_code = OSSL_QUIC_ERR_FLOW_CONTROL_ERROR; 193 } 194 195 rxfc->swm += num_bytes; 196 return ok; 197 } 198 199 int ossl_quic_rxfc_on_rx_stream_frame(QUIC_RXFC *rxfc, uint64_t end, int is_fin) 200 { 201 uint64_t delta; 202 203 if (!rxfc->standalone && rxfc->parent == NULL) 204 return 0; 205 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 */ 210 } 211 212 if (is_fin) 213 rxfc->is_fin = 1; 214 215 if (end > rxfc->hwm) { 216 delta = end - rxfc->hwm; 217 rxfc->hwm = end; 218 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 */ 225 } 226 227 return 1; 228 } 229 230 /* threshold = 3/4 */ 231 #define WINDOW_THRESHOLD_NUM 3 232 #define WINDOW_THRESHOLD_DEN 4 233 234 static int rxfc_cwm_bump_desired(QUIC_RXFC *rxfc) 235 { 236 int err = 0; 237 uint64_t window_rem = rxfc->cwm - rxfc->rwm; 238 uint64_t threshold 239 = safe_muldiv_uint64_t(rxfc->cur_window_size, 240 WINDOW_THRESHOLD_NUM, WINDOW_THRESHOLD_DEN, &err); 241 242 if (err) 243 /* 244 * Extremely large window should never occur, but if it does, just use 245 * 1/2 as the threshold. 246 */ 247 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 return !rxfc->is_fin && window_rem <= threshold; 254 } 255 256 static int rxfc_should_bump_window_size(QUIC_RXFC *rxfc, OSSL_TIME rtt) 257 { 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 uint64_t b = rxfc->rwm - rxfc->esrwm; 278 OSSL_TIME now, dt, t_window; 279 280 if (b == 0) 281 return 0; 282 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); 286 287 return ossl_time_compare(t_window, ossl_time_multiply(rtt, 4)) < 0; 288 } 289 290 static void rxfc_adjust_window_size(QUIC_RXFC *rxfc, uint64_t min_window_size, 291 OSSL_TIME rtt) 292 { 293 /* Are we sending updates too often? */ 294 uint64_t new_window_size; 295 296 new_window_size = rxfc->cur_window_size; 297 298 if (rxfc_should_bump_window_size(rxfc, rtt)) 299 new_window_size *= 2; 300 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; 305 306 rxfc->cur_window_size = new_window_size; 307 rxfc_start_epoch(rxfc); 308 } 309 310 static void rxfc_update_cwm(QUIC_RXFC *rxfc, uint64_t min_window_size, 311 OSSL_TIME rtt) 312 { 313 uint64_t new_cwm; 314 315 if (!rxfc_cwm_bump_desired(rxfc)) 316 return; 317 318 rxfc_adjust_window_size(rxfc, min_window_size, rtt); 319 320 new_cwm = rxfc->rwm + rxfc->cur_window_size; 321 if (new_cwm > rxfc->cwm) { 322 rxfc->cwm = new_cwm; 323 rxfc->has_cwm_changed = 1; 324 } 325 } 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 { 331 if (ossl_time_is_zero(rxfc->epoch_start)) 332 /* This happens when we retire our first ever bytes. */ 333 rxfc_start_epoch(rxfc); 334 335 rxfc->rwm += num_bytes; 336 rxfc_update_cwm(rxfc, min_window_size, rtt); 337 return 1; 338 } 339 340 int ossl_quic_rxfc_on_retire(QUIC_RXFC *rxfc, 341 uint64_t num_bytes, 342 OSSL_TIME rtt) 343 { 344 if (rxfc->parent == NULL && !rxfc->standalone) 345 return 0; 346 347 if (num_bytes == 0) 348 return 1; 349 350 if (rxfc->rwm + num_bytes > rxfc->swm) 351 /* Impossible for us to retire more bytes than we have received. */ 352 return 0; 353 354 rxfc_on_retire(rxfc, num_bytes, 0, rtt); 355 356 if (!rxfc->standalone) 357 rxfc_on_retire(rxfc->parent, num_bytes, rxfc->cur_window_size, rtt); 358 359 return 1; 360 } 361 362 uint64_t ossl_quic_rxfc_get_cwm(const QUIC_RXFC *rxfc) 363 { 364 return rxfc->cwm; 365 } 366 367 uint64_t ossl_quic_rxfc_get_swm(const QUIC_RXFC *rxfc) 368 { 369 return rxfc->swm; 370 } 371 372 uint64_t ossl_quic_rxfc_get_rwm(const QUIC_RXFC *rxfc) 373 { 374 return rxfc->rwm; 375 } 376 377 uint64_t ossl_quic_rxfc_get_credit(const QUIC_RXFC *rxfc) 378 { 379 return ossl_quic_rxfc_get_cwm(rxfc) - ossl_quic_rxfc_get_swm(rxfc); 380 } 381 382 int ossl_quic_rxfc_has_cwm_changed(QUIC_RXFC *rxfc, int clear) 383 { 384 int r = rxfc->has_cwm_changed; 385 386 if (clear) 387 rxfc->has_cwm_changed = 0; 388 389 return r; 390 } 391 392 int ossl_quic_rxfc_get_error(QUIC_RXFC *rxfc, int clear) 393 { 394 int r = rxfc->error_code; 395 396 if (clear) 397 rxfc->error_code = 0; 398 399 return r; 400 } 401 402 int ossl_quic_rxfc_get_final_size(const QUIC_RXFC *rxfc, uint64_t *final_size) 403 { 404 if (!rxfc->is_fin) 405 return 0; 406 407 if (final_size != NULL) 408 *final_size = rxfc->hwm; 409 410 return 1; 411 } 412