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
ossl_quic_cfq_item_get_frame_type(const QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_item_get_encoded(const QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_item_get_encoded_len(const QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_item_get_state(const QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_item_get_pn_space(const QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_item_is_unreliable(const QUIC_CFQ_ITEM * item)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
compare(const QUIC_CFQ_ITEM_EX * a,const QUIC_CFQ_ITEM_EX * b)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
list_remove(QUIC_CFQ_ITEM_LIST * l,QUIC_CFQ_ITEM_EX * n)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
list_insert_head(QUIC_CFQ_ITEM_LIST * l,QUIC_CFQ_ITEM_EX * n)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
list_insert_tail(QUIC_CFQ_ITEM_LIST * l,QUIC_CFQ_ITEM_EX * n)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
list_insert_after(QUIC_CFQ_ITEM_LIST * l,QUIC_CFQ_ITEM_EX * ref,QUIC_CFQ_ITEM_EX * n)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
list_insert_sorted(QUIC_CFQ_ITEM_LIST * l,QUIC_CFQ_ITEM_EX * n,int (* cmp)(const QUIC_CFQ_ITEM_EX * a,const QUIC_CFQ_ITEM_EX * b))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
ossl_quic_cfq_new(void)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
clear_item(QUIC_CFQ_ITEM_EX * item)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
free_list_items(QUIC_CFQ_ITEM_LIST * l)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
ossl_quic_cfq_free(QUIC_CFQ * cfq)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
cfq_get_free(QUIC_CFQ * cfq)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
ossl_quic_cfq_add_frame(QUIC_CFQ * cfq,uint32_t priority,uint32_t pn_space,uint64_t frame_type,uint32_t flags,const unsigned char * encoded,size_t encoded_len,cfq_free_cb * free_cb,void * free_cb_arg)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
ossl_quic_cfq_mark_tx(QUIC_CFQ * cfq,QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_mark_lost(QUIC_CFQ * cfq,QUIC_CFQ_ITEM * item,uint32_t priority)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 */
ossl_quic_cfq_release(QUIC_CFQ * cfq,QUIC_CFQ_ITEM * item)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
ossl_quic_cfq_get_priority_head(const QUIC_CFQ * cfq,uint32_t pn_space)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
ossl_quic_cfq_item_get_priority_next(const QUIC_CFQ_ITEM * item,uint32_t pn_space)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
