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