xref: /openssl/ssl/quic/quic_sf_list.c (revision da1c088f)
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