1 /*
2 * Copyright 2022-2023 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/uint_set.h"
11 #include "internal/common.h"
12 #include "internal/quic_sf_list.h"
13
14 struct stream_frame_st {
15 struct stream_frame_st *prev, *next;
16 UINT_RANGE range;
17 OSSL_QRX_PKT *pkt;
18 const unsigned char *data;
19 };
20
stream_frame_free(SFRAME_LIST * fl,STREAM_FRAME * sf)21 static void stream_frame_free(SFRAME_LIST *fl, STREAM_FRAME *sf)
22 {
23 if (fl->cleanse && sf->data != NULL)
24 OPENSSL_cleanse((unsigned char *)sf->data,
25 (size_t)(sf->range.end - sf->range.start));
26 ossl_qrx_pkt_release(sf->pkt);
27 OPENSSL_free(sf);
28 }
29
stream_frame_new(UINT_RANGE * range,OSSL_QRX_PKT * pkt,const unsigned char * data)30 static STREAM_FRAME *stream_frame_new(UINT_RANGE *range, OSSL_QRX_PKT *pkt,
31 const unsigned char *data)
32 {
33 STREAM_FRAME *sf = OPENSSL_zalloc(sizeof(*sf));
34
35 if (sf == NULL)
36 return NULL;
37
38 if (pkt != NULL)
39 ossl_qrx_pkt_up_ref(pkt);
40
41 sf->range = *range;
42 sf->pkt = pkt;
43 sf->data = data;
44
45 return sf;
46 }
47
ossl_sframe_list_init(SFRAME_LIST * fl)48 void ossl_sframe_list_init(SFRAME_LIST *fl)
49 {
50 memset(fl, 0, sizeof(*fl));
51 }
52
ossl_sframe_list_destroy(SFRAME_LIST * fl)53 void ossl_sframe_list_destroy(SFRAME_LIST *fl)
54 {
55 STREAM_FRAME *sf, *next_frame;
56
57 for (sf = fl->head; sf != NULL; sf = next_frame) {
58 next_frame = sf->next;
59 stream_frame_free(fl, sf);
60 }
61 }
62
append_frame(SFRAME_LIST * fl,UINT_RANGE * range,OSSL_QRX_PKT * pkt,const unsigned char * data)63 static int append_frame(SFRAME_LIST *fl, UINT_RANGE *range,
64 OSSL_QRX_PKT *pkt,
65 const unsigned char *data)
66 {
67 STREAM_FRAME *new_frame;
68
69 if ((new_frame = stream_frame_new(range, pkt, data)) == NULL)
70 return 0;
71 new_frame->prev = fl->tail;
72 if (fl->tail != NULL)
73 fl->tail->next = new_frame;
74 fl->tail = new_frame;
75 ++fl->num_frames;
76 return 1;
77 }
78
ossl_sframe_list_insert(SFRAME_LIST * fl,UINT_RANGE * range,OSSL_QRX_PKT * pkt,const unsigned char * data,int fin)79 int ossl_sframe_list_insert(SFRAME_LIST *fl, UINT_RANGE *range,
80 OSSL_QRX_PKT *pkt,
81 const unsigned char *data, int fin)
82 {
83 STREAM_FRAME *sf, *new_frame, *prev_frame, *next_frame;
84 #ifndef NDEBUG
85 uint64_t curr_end = fl->tail != NULL ? fl->tail->range.end
86 : fl->offset;
87
88 /* This check for FINAL_SIZE_ERROR is handled by QUIC FC already */
89 assert((!fin || curr_end <= range->end)
90 && (!fl->fin || curr_end >= range->end));
91 #endif
92
93 if (fl->offset >= range->end)
94 goto end;
95
96 /* nothing there yet */
97 if (fl->tail == NULL) {
98 fl->tail = fl->head = stream_frame_new(range, pkt, data);
99 if (fl->tail == NULL)
100 return 0;
101
102 ++fl->num_frames;
103 goto end;
104 }
105
106 /* optimize insertion at the end */
107 if (fl->tail->range.start < range->start) {
108 if (fl->tail->range.end >= range->end)
109 goto end;
110
111 if (!append_frame(fl, range, pkt, data))
112 return 0;
113 goto end;
114 }
115
116 prev_frame = NULL;
117 for (sf = fl->head; sf != NULL && sf->range.start < range->start;
118 sf = sf->next)
119 prev_frame = sf;
120
121 if (!ossl_assert(sf != NULL))
122 /* frame list invariant broken */
123 return 0;
124
125 if (prev_frame != NULL && prev_frame->range.end >= range->end)
126 goto end;
127
128 /*
129 * Now we must create a new frame although in the end we might drop it,
130 * because we will be potentially dropping existing overlapping frames.
131 */
132 new_frame = stream_frame_new(range, pkt, data);
133 if (new_frame == NULL)
134 return 0;
135
136 for (next_frame = sf;
137 next_frame != NULL && next_frame->range.end <= range->end;) {
138 STREAM_FRAME *drop_frame = next_frame;
139
140 next_frame = next_frame->next;
141 if (next_frame != NULL)
142 next_frame->prev = drop_frame->prev;
143 if (prev_frame != NULL)
144 prev_frame->next = drop_frame->next;
145 if (fl->head == drop_frame)
146 fl->head = next_frame;
147 if (fl->tail == drop_frame)
148 fl->tail = prev_frame;
149 --fl->num_frames;
150 stream_frame_free(fl, drop_frame);
151 }
152
153 if (next_frame != NULL) {
154 /* check whether the new_frame is redundant because there is no gap */
155 if (prev_frame != NULL
156 && next_frame->range.start <= prev_frame->range.end) {
157 stream_frame_free(fl, new_frame);
158 goto end;
159 }
160 next_frame->prev = new_frame;
161 } else {
162 fl->tail = new_frame;
163 }
164
165 new_frame->next = next_frame;
166 new_frame->prev = prev_frame;
167
168 if (prev_frame != NULL)
169 prev_frame->next = new_frame;
170 else
171 fl->head = new_frame;
172
173 ++fl->num_frames;
174
175 end:
176 fl->fin = fin || fl->fin;
177
178 return 1;
179 }
180
ossl_sframe_list_peek(const SFRAME_LIST * fl,void ** iter,UINT_RANGE * range,const unsigned char ** data,int * fin)181 int ossl_sframe_list_peek(const SFRAME_LIST *fl, void **iter,
182 UINT_RANGE *range, const unsigned char **data,
183 int *fin)
184 {
185 STREAM_FRAME *sf = *iter;
186 uint64_t start;
187
188 if (sf == NULL) {
189 start = fl->offset;
190 sf = fl->head;
191 } else {
192 start = sf->range.end;
193 sf = sf->next;
194 }
195
196 range->start = start;
197
198 if (sf == NULL || sf->range.start > start
199 || !ossl_assert(start < sf->range.end)) {
200 range->end = start;
201 *data = NULL;
202 *iter = NULL;
203 /* set fin only if we are at the end */
204 *fin = sf == NULL ? fl->fin : 0;
205 return 0;
206 }
207
208 range->end = sf->range.end;
209 if (sf->data != NULL)
210 *data = sf->data + (start - sf->range.start);
211 else
212 *data = NULL;
213 *fin = sf->next == NULL ? fl->fin : 0;
214 *iter = sf;
215 return 1;
216 }
217
ossl_sframe_list_drop_frames(SFRAME_LIST * fl,uint64_t limit)218 int ossl_sframe_list_drop_frames(SFRAME_LIST *fl, uint64_t limit)
219 {
220 STREAM_FRAME *sf;
221
222 /* offset cannot move back or past the data received */
223 if (!ossl_assert(limit >= fl->offset)
224 || !ossl_assert(fl->tail == NULL
225 || limit <= fl->tail->range.end)
226 || !ossl_assert(fl->tail != NULL
227 || limit == fl->offset))
228 return 0;
229
230 fl->offset = limit;
231
232 for (sf = fl->head; sf != NULL && sf->range.end <= limit;) {
233 STREAM_FRAME *drop_frame = sf;
234
235 sf = sf->next;
236 --fl->num_frames;
237 stream_frame_free(fl, drop_frame);
238 }
239 fl->head = sf;
240
241 if (sf != NULL)
242 sf->prev = NULL;
243 else
244 fl->tail = NULL;
245
246 fl->head_locked = 0;
247
248 return 1;
249 }
250
ossl_sframe_list_lock_head(SFRAME_LIST * fl,UINT_RANGE * range,const unsigned char ** data,int * fin)251 int ossl_sframe_list_lock_head(SFRAME_LIST *fl, UINT_RANGE *range,
252 const unsigned char **data,
253 int *fin)
254 {
255 int ret;
256 void *iter = NULL;
257
258 if (fl->head_locked)
259 return 0;
260
261 ret = ossl_sframe_list_peek(fl, &iter, range, data, fin);
262 if (ret)
263 fl->head_locked = 1;
264 return ret;
265 }
266
ossl_sframe_list_is_head_locked(SFRAME_LIST * fl)267 int ossl_sframe_list_is_head_locked(SFRAME_LIST *fl)
268 {
269 return fl->head_locked;
270 }
271
ossl_sframe_list_move_data(SFRAME_LIST * fl,sframe_list_write_at_cb * write_at_cb,void * cb_arg)272 int ossl_sframe_list_move_data(SFRAME_LIST *fl,
273 sframe_list_write_at_cb *write_at_cb,
274 void *cb_arg)
275 {
276 STREAM_FRAME *sf = fl->head, *prev_frame = NULL;
277 uint64_t limit = fl->offset;
278
279 if (sf == NULL)
280 return 1;
281
282 if (fl->head_locked)
283 sf = sf->next;
284
285 for (; sf != NULL; sf = sf->next) {
286 size_t len;
287 const unsigned char *data = sf->data;
288
289 if (limit < sf->range.start)
290 limit = sf->range.start;
291
292 if (data != NULL) {
293 if (limit > sf->range.start)
294 data += (size_t)(limit - sf->range.start);
295 len = (size_t)(sf->range.end - limit);
296
297 if (!write_at_cb(limit, data, len, cb_arg))
298 /* data did not fit */
299 return 0;
300
301 if (fl->cleanse)
302 OPENSSL_cleanse((unsigned char *)sf->data,
303 (size_t)(sf->range.end - sf->range.start));
304
305 /* release the packet */
306 sf->data = NULL;
307 ossl_qrx_pkt_release(sf->pkt);
308 sf->pkt = NULL;
309 }
310
311 limit = sf->range.end;
312
313 /* merge contiguous frames */
314 if (prev_frame != NULL
315 && prev_frame->range.end >= sf->range.start) {
316 prev_frame->range.end = sf->range.end;
317 prev_frame->next = sf->next;
318
319 if (sf->next != NULL)
320 sf->next->prev = prev_frame;
321 else
322 fl->tail = prev_frame;
323
324 --fl->num_frames;
325 stream_frame_free(fl, sf);
326 sf = prev_frame;
327 continue;
328 }
329
330 prev_frame = sf;
331 }
332
333 return 1;
334 }
335
