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