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