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