ssl/quic/quic_fc.c

   1 /*
   2  * Copyright 2022 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)
  50 {
  51     assert(txfc->swm <= txfc->cwm);
  52     return txfc->cwm - txfc->swm;
  53 }
  54
  55 uint64_t ossl_quic_txfc_get_credit(QUIC_TXFC *txfc)
  56 {
  57     uint64_t r, conn_r;
  58
  59     r = ossl_quic_txfc_get_credit_local(txfc);
  60
  61     if (txfc->parent != NULL) {
  62         assert(txfc->parent->parent == NULL);
  63         conn_r = ossl_quic_txfc_get_credit_local(txfc->parent);
  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);
  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 = 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 = 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 = 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(QUIC_RXFC *rxfc)
 363 {
 364     return rxfc->cwm;
 365 }
 366
 367 uint64_t ossl_quic_rxfc_get_swm(QUIC_RXFC *rxfc)
 368 {
 369     return rxfc->swm;
 370 }
 371
 372 uint64_t ossl_quic_rxfc_get_rwm(QUIC_RXFC *rxfc)
 373 {
 374     return rxfc->rwm;
 375 }
 376
 377 int ossl_quic_rxfc_has_cwm_changed(QUIC_RXFC *rxfc, int clear)
 378 {
 379     int r = rxfc->has_cwm_changed;
 380
 381     if (clear)
 382         rxfc->has_cwm_changed = 0;
 383
 384     return r;
 385 }
 386
 387 int ossl_quic_rxfc_get_error(QUIC_RXFC *rxfc, int clear)
 388 {
 389     int r = rxfc->error_code;
 390
 391     if (clear)
 392         rxfc->error_code = 0;
 393
 394     return r;
 395 }
 396
 397 int ossl_quic_rxfc_get_final_size(const QUIC_RXFC *rxfc, uint64_t *final_size)
 398 {
 399     if (!rxfc->is_fin)
 400         return 0;
 401
 402     if (final_size != NULL)
 403         *final_size = rxfc->hwm;
 404
 405     return 1;
 406 }