[thirdparty/openssl.git] / ssl / quic / quic_cfq.c

/*
 * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
 *
 * Licensed under the Apache License 2.0 (the "License").  You may not use
 * this file except in compliance with the License.  You can obtain a copy
 * in the file LICENSE in the source distribution or at
 * https://www.openssl.org/source/license.html
 */

#include "internal/quic_cfq.h"

typedef struct quic_cfq_item_ex_st QUIC_CFQ_ITEM_EX;

struct quic_cfq_item_ex_st {
    QUIC_CFQ_ITEM           public;
    QUIC_CFQ_ITEM_EX       *prev, *next;
    unsigned char          *encoded;
    cfq_free_cb            *free_cb;
    void                   *free_cb_arg;
    uint64_t                frame_type;
    size_t                  encoded_len;
    uint32_t                priority, pn_space;
    int                     state;
};

uint64_t ossl_quic_cfq_item_get_frame_type(const QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    return ex->frame_type;
}

const unsigned char *ossl_quic_cfq_item_get_encoded(const QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    return ex->encoded;
}

size_t ossl_quic_cfq_item_get_encoded_len(const QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    return ex->encoded_len;
}

int ossl_quic_cfq_item_get_state(const QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    return ex->state;
}

uint32_t ossl_quic_cfq_item_get_pn_space(const QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    return ex->pn_space;
}

typedef struct quic_cfq_item_list_st {
    QUIC_CFQ_ITEM_EX *head, *tail;
} QUIC_CFQ_ITEM_LIST;

struct quic_cfq_st {
    /* 
     * Invariant: A CFQ item is always in exactly one of these lists, never more
     * or less than one.
     *
     * Invariant: The list the CFQ item is determined exactly by the state field
     * of the item.
     */
    QUIC_CFQ_ITEM_LIST                      new_list, tx_list, free_list;
};

static int compare(const QUIC_CFQ_ITEM_EX *a, const QUIC_CFQ_ITEM_EX *b)
{
    if (a->pn_space < b->pn_space)
        return -1;
    else if (a->pn_space > b->pn_space)
        return 1;

    if (a->priority > b->priority)
        return -1;
    else if (a->priority < b->priority)
        return 1;

    return 0;
}

static void list_remove(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
{
    if (l->head == n)
        l->head = n->next;
    if (l->tail == n)
        l->tail = n->prev;
    if (n->prev != NULL)
        n->prev->next = n->next;
    if (n->next != NULL)
        n->next->prev = n->prev;
    n->prev = n->next = NULL;
}

static void list_insert_head(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
{
    n->next = l->head;
    n->prev = NULL;
    l->head = n;
    if (n->next != NULL)
        n->next->prev = n;
    if (l->tail == NULL)
        l->tail = n;
}

static void list_insert_tail(QUIC_CFQ_ITEM_LIST *l, QUIC_CFQ_ITEM_EX *n)
{
    n->prev = l->tail;
    n->next = NULL;
    l->tail = n;
    if (n->prev != NULL)
        n->prev->next = n;
    if (l->head == NULL)
        l->head = n;
}

static void list_insert_after(QUIC_CFQ_ITEM_LIST *l,
                              QUIC_CFQ_ITEM_EX *ref,
                              QUIC_CFQ_ITEM_EX *n)
{
    n->prev = ref;
    n->next = ref->next;
    if (ref->next != NULL)
        ref->next->prev = n;
    ref->next = n;
    if (l->tail == ref)
        l->tail = n;
}

static void 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))
{
    QUIC_CFQ_ITEM_EX *p = l->head, *pprev = NULL;

    if (p == NULL) {
        l->head = l->tail = n;
        n->prev = n->next = NULL;
        return;
    }

    for (; p != NULL && cmp(p, n) < 0; pprev = p, p = p->next);

    if (p == NULL)
        list_insert_tail(l, n);
    else if (pprev == NULL)
        list_insert_head(l, n);
    else
        list_insert_after(l, pprev, n);
}

QUIC_CFQ *ossl_quic_cfq_new(void)
{
    QUIC_CFQ *cfq = OPENSSL_zalloc(sizeof(*cfq));

    if (cfq == NULL)
        return NULL;

    return cfq;
}

static void clear_item(QUIC_CFQ_ITEM_EX *item)
{
    if (item->free_cb != NULL) {
        item->free_cb(item->encoded, item->encoded_len, item->free_cb_arg);

        item->free_cb       = NULL;
        item->encoded       = NULL;
        item->encoded_len   = 0;
    }

    item->state = -1;
}

static void free_list_items(QUIC_CFQ_ITEM_LIST *l)
{
    QUIC_CFQ_ITEM_EX *p, *pnext;

    for (p = l->head; p != NULL; p = pnext) {
        pnext = p->next;
        clear_item(p);
        OPENSSL_free(p);
    }
}

void ossl_quic_cfq_free(QUIC_CFQ *cfq)
{
    if (cfq == NULL)
        return;

    free_list_items(&cfq->new_list);
    free_list_items(&cfq->tx_list);
    free_list_items(&cfq->free_list);
    OPENSSL_free(cfq);
}

static QUIC_CFQ_ITEM_EX *cfq_get_free(QUIC_CFQ *cfq)
{
    QUIC_CFQ_ITEM_EX *item = cfq->free_list.head;

    if (item != NULL)
        return item;

    item = OPENSSL_zalloc(sizeof(*item));
    if (item == NULL)
        return NULL;

    item->state = -1;
    list_insert_tail(&cfq->free_list, item);
    return item;
}

QUIC_CFQ_ITEM *ossl_quic_cfq_add_frame(QUIC_CFQ            *cfq,
                                       uint32_t             priority,
                                       uint32_t             pn_space,
                                       uint64_t             frame_type,
                                       const unsigned char *encoded,
                                       size_t               encoded_len,
                                       cfq_free_cb         *free_cb,
                                       void                *free_cb_arg)
{
    QUIC_CFQ_ITEM_EX *item = cfq_get_free(cfq);

    if (item == NULL)
        return NULL;

    item->priority      = priority;
    item->frame_type    = frame_type;
    item->pn_space      = pn_space;
    item->encoded       = (unsigned char *)encoded;
    item->encoded_len   = encoded_len;
    item->free_cb       = free_cb;
    item->free_cb_arg   = free_cb_arg;

    item->state = QUIC_CFQ_STATE_NEW;
    list_remove(&cfq->free_list, item);
    list_insert_sorted(&cfq->new_list, item, compare);
    return &item->public;
}

void ossl_quic_cfq_mark_tx(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    switch (ex->state) {
    case QUIC_CFQ_STATE_NEW:
        list_remove(&cfq->new_list, ex);
        list_insert_tail(&cfq->tx_list, ex);
        ex->state = QUIC_CFQ_STATE_TX;
        break;
    case QUIC_CFQ_STATE_TX:
        break; /* nothing to do */
    default:
        assert(0); /* invalid state (e.g. in free state) */
        break;
    }
}

void ossl_quic_cfq_mark_lost(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item,
                             uint32_t priority)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    switch (ex->state) {
    case QUIC_CFQ_STATE_NEW:
        if (priority != UINT32_MAX && priority != ex->priority) {
            list_remove(&cfq->new_list, ex);
            ex->priority = priority;
            list_insert_sorted(&cfq->new_list, ex, compare);
        }
        break; /* nothing to do */
    case QUIC_CFQ_STATE_TX:
        if (priority != UINT32_MAX)
            ex->priority = priority;
        list_remove(&cfq->tx_list, ex);
        list_insert_sorted(&cfq->new_list, ex, compare);
        ex->state = QUIC_CFQ_STATE_NEW;
        break;
    default:
        assert(0); /* invalid state (e.g. in free state) */
        break;
    }
}

/*
 * Releases a CFQ item. The item may be in either state (NEW or TX) prior to the
 * call. The QUIC_CFQ_ITEM pointer must not be used following this call.
 */
void ossl_quic_cfq_release(QUIC_CFQ *cfq, QUIC_CFQ_ITEM *item)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    switch (ex->state) {
    case QUIC_CFQ_STATE_NEW:
        list_remove(&cfq->new_list, ex);
        list_insert_tail(&cfq->free_list, ex);
        clear_item(ex);
        break;
    case QUIC_CFQ_STATE_TX:
        list_remove(&cfq->tx_list, ex);
        list_insert_tail(&cfq->free_list, ex);
        clear_item(ex);
        break;
    default:
        assert(0); /* invalid state (e.g. in free state) */
        break;
    }
}

QUIC_CFQ_ITEM *ossl_quic_cfq_get_priority_head(const QUIC_CFQ *cfq,
                                               uint32_t pn_space)
{
    QUIC_CFQ_ITEM_EX *item = cfq->new_list.head;

    for (; item != NULL && item->pn_space != pn_space; item = item->next);

    if (item == NULL)
        return NULL;

    return &item->public;
}

QUIC_CFQ_ITEM *ossl_quic_cfq_item_get_priority_next(const QUIC_CFQ_ITEM *item,
                                                    uint32_t pn_space)
{
    QUIC_CFQ_ITEM_EX *ex = (QUIC_CFQ_ITEM_EX *)item;

    if (ex == NULL)
        return NULL;

     ex = ex->next;

     for (; ex != NULL && ex->pn_space != pn_space; ex = ex->next);

     if (ex == NULL)
         return NULL; /* ubsan */

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