Coverage Report

Created: 2024-02-25 06:15

/src/h2o/deps/quicly/lib/local_cid.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright (c) 2020 Fastly, Inc.
3
 *
4
 * Permission is hereby granted, free of charge, to any person obtaining a copy
5
 * of this software and associated documentation files (the "Software"), to
6
 * deal in the Software without restriction, including without limitation the
7
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8
 * sell copies of the Software, and to permit persons to whom the Software is
9
 * furnished to do so, subject to the following conditions:
10
 *
11
 * The above copyright notice and this permission notice shall be included in
12
 * all copies or substantial portions of the Software.
13
 *
14
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20
 * IN THE SOFTWARE.
21
 */
22
#include "quicly/local_cid.h"
23
24
static int has_pending(quicly_local_cid_set_t *set)
25
0
{
26
0
    return set->cids[0].state == QUICLY_LOCAL_CID_STATE_PENDING;
27
0
}
28
29
/**
30
 * generates a new CID and increments path_id. returns true if successfully generated.
31
 */
32
static int generate_cid(quicly_local_cid_set_t *set, size_t idx)
33
0
{
34
0
    if (set->_encryptor == NULL || set->plaintext.path_id >= QUICLY_MAX_PATH_ID)
35
0
        return 0;
36
37
0
    set->_encryptor->encrypt_cid(set->_encryptor, &set->cids[idx].cid, set->cids[idx].stateless_reset_token, &set->plaintext);
38
0
    set->cids[idx].sequence = set->plaintext.path_id++;
39
40
0
    return 1;
41
0
}
42
43
static void swap_cids(quicly_local_cid_t *a, quicly_local_cid_t *b)
44
0
{
45
0
    quicly_local_cid_t tmp = *b;
46
0
    *b = *a;
47
0
    *a = tmp;
48
0
}
49
50
/**
51
 * change the state of a CID to PENDING, and move it forward so CIDs in pending state form FIFO
52
 */
53
static void do_mark_pending(quicly_local_cid_set_t *set, size_t idx)
54
0
{
55
0
    set->cids[idx].state = QUICLY_LOCAL_CID_STATE_PENDING;
56
0
    for (size_t j = 0; j < idx; j++) {
57
0
        if (set->cids[j].state != QUICLY_LOCAL_CID_STATE_PENDING) {
58
0
            swap_cids(&set->cids[idx], &set->cids[j]);
59
0
            break;
60
0
        }
61
0
    }
62
0
}
63
64
static void do_mark_delivered(quicly_local_cid_set_t *set, size_t idx)
65
0
{
66
0
    if (set->cids[idx].state == QUICLY_LOCAL_CID_STATE_PENDING) {
67
        /* if transitioning from PENDING, move it backward so the remaining PENDING CIDs come first */
68
0
        while (idx + 1 < set->_size && set->cids[idx + 1].state == QUICLY_LOCAL_CID_STATE_PENDING) {
69
0
            swap_cids(&set->cids[idx], &set->cids[idx + 1]);
70
0
            idx++;
71
0
        }
72
0
    }
73
0
    set->cids[idx].state = QUICLY_LOCAL_CID_STATE_DELIVERED;
74
0
}
75
76
void quicly_local_cid_init_set(quicly_local_cid_set_t *set, quicly_cid_encryptor_t *encryptor,
77
                               const quicly_cid_plaintext_t *new_cid)
78
0
{
79
0
    *set = (quicly_local_cid_set_t){
80
0
        ._encryptor = encryptor,
81
0
        ._size = 1,
82
0
    };
83
84
    /* if provided, set master id */
85
0
    if (new_cid != NULL) {
86
0
        assert(new_cid->path_id == 0);
87
0
        set->plaintext = *new_cid;
88
0
    }
89
90
    /* initialize cids[0] */
91
0
    if (encryptor != NULL) {
92
0
        assert(new_cid != NULL && "master CID must be specified when a non-zero length CID is to be used");
93
0
        generate_cid(set, 0);
94
0
    }
95
0
    set->cids[0].state =
96
0
        QUICLY_LOCAL_CID_STATE_DELIVERED; /* no need to use NCID frames, the use delivers this CID to the remote peer */
97
98
0
    for (size_t i = 1; i < PTLS_ELEMENTSOF(set->cids); i++)
99
0
        set->cids[i].sequence = UINT64_MAX;
100
0
}
101
102
int quicly_local_cid_set_size(quicly_local_cid_set_t *set, size_t size)
103
0
{
104
0
    int is_pending = 0;
105
106
0
    assert(size <= PTLS_ELEMENTSOF(set->cids));
107
0
    assert(set->_size <= size);
108
109
0
    for (size_t i = set->_size; i < size; i++)
110
0
        set->cids[i].state = QUICLY_LOCAL_CID_STATE_IDLE;
111
112
0
    set->_size = size;
113
114
    /* First we prepare N CIDs (to be precise here we prepare N-1, as we already had one upon initialization).
115
     * Later, every time one of the CIDs is retired, we immediately prepare one additional CID
116
     * to always fill the CID list. */
117
0
    for (size_t i = 0; i < size; i++) {
118
0
        if (set->cids[i].state != QUICLY_LOCAL_CID_STATE_IDLE)
119
0
            continue;
120
121
0
        if (!generate_cid(set, i))
122
0
            break;
123
0
        do_mark_pending(set, i);
124
0
        is_pending = 1;
125
0
    }
126
127
0
    return is_pending;
128
0
}
129
130
void quicly_local_cid_on_sent(quicly_local_cid_set_t *set, size_t num_sent)
131
0
{
132
0
    assert(num_sent <= set->_size);
133
134
    /* first, mark the first `num_sent` CIDs as INFLIGHT */
135
0
    for (size_t i = 0; i < num_sent; i++) {
136
0
        assert(set->cids[i].state == QUICLY_LOCAL_CID_STATE_PENDING);
137
0
        set->cids[i].state = QUICLY_LOCAL_CID_STATE_INFLIGHT;
138
0
    }
139
140
    /* then move the remaining PENDING CIDs (if any) to the front of the array */
141
0
    for (size_t i = num_sent; i < set->_size; i++) {
142
0
        if (set->cids[i].state != QUICLY_LOCAL_CID_STATE_PENDING)
143
0
            break;
144
0
        swap_cids(&set->cids[i], &set->cids[i - num_sent]);
145
0
    }
146
0
}
147
148
static size_t find_index(const quicly_local_cid_set_t *set, uint64_t sequence)
149
0
{
150
0
    for (size_t i = 0; i < set->_size; i++) {
151
0
        if (set->cids[i].sequence == sequence)
152
0
            return i;
153
0
    }
154
155
0
    return SIZE_MAX;
156
0
}
157
158
void quicly_local_cid_on_acked(quicly_local_cid_set_t *set, uint64_t sequence)
159
0
{
160
0
    size_t i = find_index(set, sequence);
161
0
    if (i == SIZE_MAX)
162
0
        return;
163
164
0
    do_mark_delivered(set, i);
165
0
}
166
167
int quicly_local_cid_on_lost(quicly_local_cid_set_t *set, uint64_t sequence)
168
0
{
169
0
    size_t i = find_index(set, sequence);
170
0
    if (i == SIZE_MAX)
171
0
        return has_pending(set);
172
173
    /* if it's already delivered, ignore the packet loss event (no need for retransmission) */
174
0
    if (set->cids[i].state == QUICLY_LOCAL_CID_STATE_DELIVERED)
175
0
        return has_pending(set);
176
177
0
    do_mark_pending(set, i);
178
179
0
    return 1;
180
0
}
181
182
int quicly_local_cid_retire(quicly_local_cid_set_t *set, uint64_t sequence, int *_has_pending)
183
0
{
184
    /* find the CID to be retired, also check if there is at least one CID that has been issued */
185
0
    size_t retired_at = set->_size;
186
0
    int becomes_empty = 1;
187
0
    for (size_t i = 0; i < set->_size; i++) {
188
0
        if (set->cids[i].state == QUICLY_LOCAL_CID_STATE_IDLE)
189
0
            continue;
190
0
        if (set->cids[i].sequence == sequence) {
191
0
            assert(retired_at == set->_size);
192
0
            retired_at = i;
193
0
        } else {
194
0
            becomes_empty = 0;
195
0
        }
196
0
    }
197
198
    /* nothing to do if given CID has been retired already */
199
0
    if (retired_at == set->_size) {
200
0
        *_has_pending = has_pending(set);
201
0
        return 0;
202
0
    }
203
204
    /* it is a protocol violation for the remote peer to retire the only CID that is available to it */
205
0
    if (becomes_empty)
206
0
        return QUICLY_TRANSPORT_ERROR_PROTOCOL_VIOLATION;
207
208
    /* retire given CID */
209
0
    set->cids[retired_at].state = QUICLY_LOCAL_CID_STATE_IDLE;
210
0
    set->cids[retired_at].sequence = UINT64_MAX;
211
212
    /* move following PENDING CIDs to front */
213
0
    for (size_t i = retired_at + 1; i < set->_size; i++) {
214
0
        if (set->cids[i].state != QUICLY_LOCAL_CID_STATE_PENDING)
215
0
            break;
216
0
        swap_cids(&set->cids[i], &set->cids[retired_at]);
217
0
        retired_at = i;
218
0
    }
219
220
    /* generate one new CID */
221
0
    if (generate_cid(set, retired_at)) {
222
0
        do_mark_pending(set, retired_at);
223
0
        *_has_pending = 1;
224
0
    } else {
225
0
        *_has_pending = has_pending(set);
226
0
    }
227
228
0
    return 0;
229
0
}