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 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 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 48 void ossl_sframe_list_init(SFRAME_LIST *fl) 49 { 50 memset(fl, 0, sizeof(*fl)); 51 } 52 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 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 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 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 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 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 267 int ossl_sframe_list_is_head_locked(SFRAME_LIST *fl) 268 { 269 return fl->head_locked; 270 } 271 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