ssl/quic/quic_sf_list.c

   1 /*
   2  * Copyright 2022 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 }