Coverage Report

Created: 2024-07-24 06:31

/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
}