ssl/quic/quic_cfq.c

   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/quic_cfq.h"
  11 #include "internal/numbers.h"
  12
  13 typedef struct quic_cfq_item_ex_st QUIC_CFQ_ITEM_EX;
  14
  15 struct quic_cfq_item_ex_st {
  16     QUIC_CFQ_ITEM           public;
  17     QUIC_CFQ_ITEM_EX       *prev, *next;
  18     unsigned char          *encoded;
  19     cfq_free_cb            *free_cb;
  20     void                   *free_cb_arg;
  21     uint64_t                frame_type;
  22     size_t                  encoded_len;
  23     uint32_t                priority, pn_space, flags;
  24     int                     state;
  25 };
  26
  27 uint64_t ossl_quic_cfq_item_get_frame_type(const QUIC_CFQ_ITEM *item)
  28 {
  29     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
  30
  31     return ex->frame_type;
  32 }
  33
  34 const unsigned char *ossl_quic_cfq_item_get_encoded(const QUIC_CFQ_ITEM *item)
  35 {
  36     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
  37
  38     return ex->encoded;
  39 }
  40
  41 size_t ossl_quic_cfq_item_get_encoded_len(const QUIC_CFQ_ITEM *item)
  42 {
  43     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
  44
  45     return ex->encoded_len;
  46 }
  47
  48 int ossl_quic_cfq_item_get_state(const QUIC_CFQ_ITEM *item)
  49 {
  50     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
  51
  52     return ex->state;
  53 }
  54
  55 uint32_t ossl_quic_cfq_item_get_pn_space(const QUIC_CFQ_ITEM *item)
  56 {
  57     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
  58
  59     return ex->pn_space;
  60 }
  61
  62 int ossl_quic_cfq_item_is_unreliable(const QUIC_CFQ_ITEM *item)
  63 {
  64     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
  65
  66     return (ex->flags & QUIC_CFQ_ITEM_FLAG_UNRELIABLE) != 0;
  67 }
  68
  69 typedef struct quic_cfq_item_list_st {
  70     QUIC_CFQ_ITEM_EX *head, *tail;
  71 } QUIC_CFQ_ITEM_LIST;
  72
  73 struct quic_cfq_st {
  74     /*
  75      * Invariant: A CFQ item is always in exactly one of these lists, never more
  76      * or less than one.
  77      *
  78      * Invariant: The list the CFQ item is determined exactly by the state field
  79      * of the item.
  80      */
  81     QUIC_CFQ_ITEM_LIST                      new_list, tx_list, free_list;
  82 };
  83
  84 static int compare(const QUIC_CFQ_ITEM_EX *a, const QUIC_CFQ_ITEM_EX *b)
  85 {
  86     if (a->pn_space < b->pn_space)
  87         return -1;
  88     else if (a->pn_space > b->pn_space)
  89         return 1;
  90
  91     if (a->priority > b->priority)
  92         return -1;
  93     else if (a->priority < b->priority)
  94         return 1;
  95
  96     return 0;
  97 }
  98
  99 static void list_remove(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
 100 {
 101     if (l->head == n)
 102         l->head = n->next;
 103     if (l->tail == n)
 104         l->tail = n->prev;
 105     if (n->prev != NULL)
 106         n->prev->next = n->next;
 107     if (n->next != NULL)
 108         n->next->prev = n->prev;
 109     n->prev = n->next = NULL;
 110 }
 111
 112 static void list_insert_head(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
 113 {
 114     n->next = l->head;
 115     n->prev = NULL;
 116     l->head = n;
 117     if (n->next != NULL)
 118         n->next->prev = n;
 119     if (l->tail == NULL)
 120         l->tail = n;
 121 }
 122
 123 static void list_insert_tail(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
 124 {
 125     n->prev = l->tail;
 126     n->next = NULL;
 127     l->tail = n;
 128     if (n->prev != NULL)
 129         n->prev->next = n;
 130     if (l->head == NULL)
 131         l->head = n;
 132 }
 133
 134 static void list_insert_after(QUIC_CFQ_ITEM_LIST *l,
 135                               QUIC_CFQ_ITEM_EX *ref,
 136                               QUIC_CFQ_ITEM_EX *n)
 137 {
 138     n->prev = ref;
 139     n->next = ref->next;
 140     if (ref->next != NULL)
 141         ref->next->prev = n;
 142     ref->next = n;
 143     if (l->tail == ref)
 144         l->tail = n;
 145 }
 146
 147 static void list_insert_sorted(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n,
 148                                int (*cmp)(const QUIC_CFQ_ITEM_EX *a,
 149                                           const QUIC_CFQ_ITEM_EX *b))
 150 {
 151     QUIC_CFQ_ITEM_EX *p = l->head, *pprev = NULL;
 152
 153     if (p == NULL) {
 154         l->head = l->tail = n;
 155         n->prev = n->next = NULL;
 156         return;
 157     }
 158
 159     for (; p != NULL && cmp(p, n) < 0; pprev = p, p = p->next);
 160
 161     if (p == NULL)
 162         list_insert_tail(l, n);
 163     else if (pprev == NULL)
 164         list_insert_head(l, n);
 165     else
 166         list_insert_after(l, pprev, n);
 167 }
 168
 169 QUIC_CFQ *ossl_quic_cfq_new(void)
 170 {
 171     QUIC_CFQ *cfq = OPENSSL_zalloc(sizeof(*cfq));
 172
 173     if (cfq == NULL)
 174         return NULL;
 175
 176     return cfq;
 177 }
 178
 179 static void clear_item(QUIC_CFQ_ITEM_EX *item)
 180 {
 181     if (item->free_cb != NULL) {
 182         item->free_cb(item->encoded, item->encoded_len, item->free_cb_arg);
 183
 184         item->free_cb       = NULL;
 185         item->encoded       = NULL;
 186         item->encoded_len   = 0;
 187     }
 188
 189     item->state = -1;
 190 }
 191
 192 static void free_list_items(QUIC_CFQ_ITEM_LIST *l)
 193 {
 194     QUIC_CFQ_ITEM_EX *p, *pnext;
 195
 196     for (p = l->head; p != NULL; p = pnext) {
 197         pnext = p->next;
 198         clear_item(p);
 199         OPENSSL_free(p);
 200     }
 201 }
 202
 203 void ossl_quic_cfq_free(QUIC_CFQ *cfq)
 204 {
 205     if (cfq == NULL)
 206         return;
 207
 208     free_list_items(&cfq->new_list);
 209     free_list_items(&cfq->tx_list);
 210     free_list_items(&cfq->free_list);
 211     OPENSSL_free(cfq);
 212 }
 213
 214 static QUIC_CFQ_ITEM_EX *cfq_get_free(QUIC_CFQ *cfq)
 215 {
 216     QUIC_CFQ_ITEM_EX *item = cfq->free_list.head;
 217
 218     if (item != NULL)
 219         return item;
 220
 221     item = OPENSSL_zalloc(sizeof(*item));
 222     if (item == NULL)
 223         return NULL;
 224
 225     item->state = -1;
 226     list_insert_tail(&cfq->free_list, item);
 227     return item;
 228 }
 229
 230 QUIC_CFQ_ITEM *ossl_quic_cfq_add_frame(QUIC_CFQ            *cfq,
 231                                        uint32_t             priority,
 232                                        uint32_t             pn_space,
 233                                        uint64_t             frame_type,
 234                                        uint32_t             flags,
 235                                        const unsigned char *encoded,
 236                                        size_t               encoded_len,
 237                                        cfq_free_cb         *free_cb,
 238                                        void                *free_cb_arg)
 239 {
 240     QUIC_CFQ_ITEM_EX *item = cfq_get_free(cfq);
 241
 242     if (item == NULL)
 243         return NULL;
 244
 245     item->priority      = priority;
 246     item->frame_type    = frame_type;
 247     item->pn_space      = pn_space;
 248     item->encoded       = (unsigned char *)encoded;
 249     item->encoded_len   = encoded_len;
 250     item->free_cb       = free_cb;
 251     item->free_cb_arg   = free_cb_arg;
 252
 253     item->state = QUIC_CFQ_STATE_NEW;
 254     item->flags = flags;
 255     list_remove(&cfq->free_list, item);
 256     list_insert_sorted(&cfq->new_list, item, compare);
 257     return &item->public;
 258 }
 259
 260 void ossl_quic_cfq_mark_tx(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item)
 261 {
 262     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
 263
 264     switch (ex->state) {
 265     case QUIC_CFQ_STATE_NEW:
 266         list_remove(&cfq->new_list, ex);
 267         list_insert_tail(&cfq->tx_list, ex);
 268         ex->state = QUIC_CFQ_STATE_TX;
 269         break;
 270     case QUIC_CFQ_STATE_TX:
 271         break; /* nothing to do */
 272     default:
 273         assert(0); /* invalid state (e.g. in free state) */
 274         break;
 275     }
 276 }
 277
 278 void ossl_quic_cfq_mark_lost(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item,
 279                              uint32_t priority)
 280 {
 281     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
 282
 283     if (ossl_quic_cfq_item_is_unreliable(item)) {
 284         ossl_quic_cfq_release(cfq, item);
 285         return;
 286     }
 287
 288     switch (ex->state) {
 289     case QUIC_CFQ_STATE_NEW:
 290         if (priority != UINT32_MAX && priority != ex->priority) {
 291             list_remove(&cfq->new_list, ex);
 292             ex->priority = priority;
 293             list_insert_sorted(&cfq->new_list, ex, compare);
 294         }
 295         break; /* nothing to do */
 296     case QUIC_CFQ_STATE_TX:
 297         if (priority != UINT32_MAX)
 298             ex->priority = priority;
 299         list_remove(&cfq->tx_list, ex);
 300         list_insert_sorted(&cfq->new_list, ex, compare);
 301         ex->state = QUIC_CFQ_STATE_NEW;
 302         break;
 303     default:
 304         assert(0); /* invalid state (e.g. in free state) */
 305         break;
 306     }
 307 }
 308
 309 /*
 310  * Releases a CFQ item. The item may be in either state (NEW or TX) prior to the
 311  * call. The QUIC_CFQ_ITEM pointer must not be used following this call.
 312  */
 313 void ossl_quic_cfq_release(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item)
 314 {
 315     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
 316
 317     switch (ex->state) {
 318     case QUIC_CFQ_STATE_NEW:
 319         list_remove(&cfq->new_list, ex);
 320         list_insert_tail(&cfq->free_list, ex);
 321         clear_item(ex);
 322         break;
 323     case QUIC_CFQ_STATE_TX:
 324         list_remove(&cfq->tx_list, ex);
 325         list_insert_tail(&cfq->free_list, ex);
 326         clear_item(ex);
 327         break;
 328     default:
 329         assert(0); /* invalid state (e.g. in free state) */
 330         break;
 331     }
 332 }
 333
 334 QUIC_CFQ_ITEM *ossl_quic_cfq_get_priority_head(const QUIC_CFQ *cfq,
 335                                                uint32_t pn_space)
 336 {
 337     QUIC_CFQ_ITEM_EX *item = cfq->new_list.head;
 338
 339     for (; item != NULL && item->pn_space != pn_space; item = item->next);
 340
 341     if (item == NULL)
 342         return NULL;
 343
 344     return &item->public;
 345 }
 346
 347 QUIC_CFQ_ITEM *ossl_quic_cfq_item_get_priority_next(const QUIC_CFQ_ITEM *item,
 348                                                     uint32_t pn_space)
 349 {
 350     QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;
 351
 352     if (ex == NULL)
 353         return NULL;
 354
 355      ex = ex->next;
 356
 357      for (; ex != NULL && ex->pn_space != pn_space; ex = ex->next);
 358
 359      if (ex == NULL)
 360          return NULL; /* ubsan */
 361
 362      return &ex->public;
 363 }