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

/*
 * Copyright 2022-2023 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/uint_set.h"
#include "internal/common.h"
#include <assert.h>

/*
 * uint64_t Integer Sets
 * =====================
 *
 * This data structure supports the following operations:
 *
 *   Insert Range: Adds an inclusive range of integers [start, end]
 *                 to the set. Equivalent to Insert for each number
 *                 in the range.
 *
 *   Remove Range: Removes an inclusive range of integers [start, end]
 *                 from the set. Not all of the range need already be in
 *                 the set, but any part of the range in the set is removed.
 *
 *   Query:        Is an integer in the data structure?
 *
 * The data structure can be iterated.
 *
 * For greater efficiency in tracking large numbers of contiguous integers, we
 * track integer ranges rather than individual integers. The data structure
 * manages a list of integer ranges [[start, end]...]. Internally this is
 * implemented as a doubly linked sorted list of range structures, which are
 * automatically split and merged as necessary.
 *
 * This data structure requires O(n) traversal of the list for insertion,
 * removal and query when we are not adding/removing ranges which are near the
 * beginning or end of the set of ranges. For the applications for which this
 * data structure is used (e.g. QUIC PN tracking for ACK generation), it is
 * expected that the number of integer ranges needed at any given time will
 * generally be small and that most operations will be close to the beginning or
 * end of the range.
 *
 * Invariant: The data structure is always sorted in ascending order by value.
 *
 * Invariant: No two adjacent ranges ever 'border' one another (have no
 *            numerical gap between them) as the data structure always ensures
 *            such ranges are merged.
 *
 * Invariant: No two ranges ever overlap.
 *
 * Invariant: No range [a, b] ever has a > b.
 *
 * Invariant: Since ranges are represented using inclusive bounds, no range
 *            item inside the data structure can represent a span of zero
 *            integers.
 */
void ossl_uint_set_init(UINT_SET *s)
{
    ossl_list_uint_set_init(s);
}

void ossl_uint_set_destroy(UINT_SET *s)
{
    UINT_SET_ITEM *x, *xnext;

    for (x = ossl_list_uint_set_head(s); x != NULL; x = xnext) {
        xnext = ossl_list_uint_set_next(x);
        OPENSSL_free(x);
    }
}

/* Possible merge of x, prev(x) */
static void uint_set_merge_adjacent(UINT_SET *s, UINT_SET_ITEM *x)
{
    UINT_SET_ITEM *xprev = ossl_list_uint_set_prev(x);

    if (xprev == NULL)
        return;

    if (x->range.start - 1 != xprev->range.end)
        return;

    x->range.start = xprev->range.start;
    ossl_list_uint_set_remove(s, xprev);
    OPENSSL_free(xprev);
}

static uint64_t u64_min(uint64_t x, uint64_t y)
{
    return x < y ? x : y;
}

static uint64_t u64_max(uint64_t x, uint64_t y)
{
    return x > y ? x : y;
}

/*
 * Returns 1 if there exists an integer x which falls within both ranges a and
 * b.
 */
static int uint_range_overlaps(const UINT_RANGE *a,
                               const UINT_RANGE *b)
{
    return u64_min(a->end, b->end)
        >= u64_max(a->start, b->start);
}

static UINT_SET_ITEM *create_set_item(uint64_t start, uint64_t end)
{
    UINT_SET_ITEM *x = OPENSSL_malloc(sizeof(UINT_SET_ITEM));

    if (x == NULL)
        return NULL;

    ossl_list_uint_set_init_elem(x);
    x->range.start = start;
    x->range.end   = end;
    return x;
}

int ossl_uint_set_insert(UINT_SET *s, const UINT_RANGE *range)
{
    UINT_SET_ITEM *x, *xnext, *z, *zprev, *f;
    uint64_t start = range->start, end = range->end;

    if (!ossl_assert(start <= end))
        return 0;

    if (ossl_list_uint_set_is_empty(s)) {
        /* Nothing in the set yet, so just add this range. */
        x = create_set_item(start, end);
        if (x == NULL)
            return 0;
        ossl_list_uint_set_insert_head(s, x);
        return 1;
    }

    z = ossl_list_uint_set_tail(s);
    if (start > z->range.end) {
        /*
         * Range is after the latest range in the set, so append.
         *
         * Note: The case where the range is before the earliest range in the
         * set is handled as a degenerate case of the final case below. See
         * optimization note (*) below.
         */
        if (z->range.end + 1 == start) {
            z->range.end = end;
            return 1;
        }

        x = create_set_item(start, end);
        if (x == NULL)
            return 0;
        ossl_list_uint_set_insert_tail(s, x);
        return 1;
    }

    f = ossl_list_uint_set_head(s);
    if (start <= f->range.start && end >= z->range.end) {
        /*
         * New range dwarfs all ranges in our set.
         *
         * Free everything except the first range in the set, which we scavenge
         * and reuse.
         */
        x = ossl_list_uint_set_head(s);
        x->range.start = start;
        x->range.end = end;
        for (x = ossl_list_uint_set_next(x); x != NULL; x = xnext) {
            xnext = ossl_list_uint_set_next(x);
            ossl_list_uint_set_remove(s, x);
        }
        return 1;
    }

    /*
     * Walk backwards since we will most often be inserting at the end. As an
     * optimization, test the head node first and skip iterating over the
     * entire list if we are inserting at the start. The assumption is that
     * insertion at the start and end of the space will be the most common
     * operations. (*)
     */
    z = end < f->range.start ? f : z;

    for (; z != NULL; z = zprev) {
        zprev = ossl_list_uint_set_prev(z);

        /* An existing range dwarfs our new range (optimisation). */
        if (z->range.start <= start && z->range.end >= end)
            return 1;

        if (uint_range_overlaps(&z->range, range)) {
            /*
             * Our new range overlaps an existing range, or possibly several
             * existing ranges.
             */
            UINT_SET_ITEM *ovend = z;

            ovend->range.end = u64_max(end, z->range.end);

            /* Get earliest overlapping range. */
            while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {
                z = zprev;
                zprev = ossl_list_uint_set_prev(z);
            }

            ovend->range.start = u64_min(start, z->range.start);

            /* Replace sequence of nodes z..ovend with updated ovend only. */
            while (z != ovend) {
                z = ossl_list_uint_set_next(x = z);
                ossl_list_uint_set_remove(s, x);
                OPENSSL_free(x);
            }
            break;
        } else if (end < z->range.start
                    && (zprev == NULL || start > zprev->range.end)) {
            if (z->range.start == end + 1) {
                /* We can extend the following range backwards. */
                z->range.start = start;

                /*
                 * If this closes a gap we now need to merge
                 * consecutive nodes.
                 */
                uint_set_merge_adjacent(s, z);
            } else if (zprev != NULL && zprev->range.end + 1 == start) {
                /* We can extend the preceding range forwards. */
                zprev->range.end = end;

                /*
                 * If this closes a gap we now need to merge
                 * consecutive nodes.
                 */
                uint_set_merge_adjacent(s, z);
            } else {
                /*
                 * The new interval is between intervals without overlapping or
                 * touching them, so insert between, preserving sort.
                 */
                x = create_set_item(start, end);
                if (x == NULL)
                    return 0;
                ossl_list_uint_set_insert_before(s, z, x);
            }
            break;
        }
    }

    return 1;
}

int ossl_uint_set_remove(UINT_SET *s, const UINT_RANGE *range)
{
    UINT_SET_ITEM *z, *zprev, *y;
    uint64_t start = range->start, end = range->end;

    if (!ossl_assert(start <= end))
        return 0;

    /* Walk backwards since we will most often be removing at the end. */
    for (z = ossl_list_uint_set_tail(s); z != NULL; z = zprev) {
        zprev = ossl_list_uint_set_prev(z);

        if (start > z->range.end)
            /* No overlapping ranges can exist beyond this point, so stop. */
            break;

        if (start <= z->range.start && end >= z->range.end) {
            /*
             * The range being removed dwarfs this range, so it should be
             * removed.
             */
            ossl_list_uint_set_remove(s, z);
            OPENSSL_free(z);
        } else if (start <= z->range.start && end >= z->range.start) {
            /*
             * The range being removed includes start of this range, but does
             * not cover the entire range (as this would be caught by the case
             * above). Shorten the range.
             */
            assert(end < z->range.end);
            z->range.start = end + 1;
        } else if (end >= z->range.end) {
            /*
             * The range being removed includes the end of this range, but does
             * not cover the entire range (as this would be caught by the case
             * above). Shorten the range. We can also stop iterating.
             */
            assert(start > z->range.start);
            assert(start > 0);
            z->range.end = start - 1;
            break;
        } else if (start > z->range.start && end < z->range.end) {
            /*
             * The range being removed falls entirely in this range, so cut it
             * into two. Cases where a zero-length range would be created are
             * handled by the above cases.
             */
            y = create_set_item(end + 1, z->range.end);
            ossl_list_uint_set_insert_after(s, z, y);
            z->range.end = start - 1;
            break;
        } else {
            /* Assert no partial overlap; all cases should be covered above. */
            assert(!uint_range_overlaps(&z->range, range));
        }
    }

    return 1;
}

int ossl_uint_set_query(const UINT_SET *s, uint64_t v)
{
    UINT_SET_ITEM *x;

    if (ossl_list_uint_set_is_empty(s))
        return 0;

    for (x = ossl_list_uint_set_tail(s); x != NULL; x = ossl_list_uint_set_prev(x))
        if (x->range.start <= v && x->range.end >= v)
            return 1;
        else if (x->range.end < v)
            return 0;

    return 0;
}
Commit	Line	Data
83022590	1	/*
da1c088f	2	* Copyright 2022-2023 The OpenSSL Project Authors. All Rights Reserved.
83022590 HL	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/uint_set.h"
	11	#include "internal/common.h"
	12	#include <assert.h>
	13
	14	/*
	15	* uint64_t Integer Sets
	16	* =====================
	17	*
	18	* This data structure supports the following operations:
	19	*
	20	* Insert Range: Adds an inclusive range of integers [start, end]
	21	* to the set. Equivalent to Insert for each number
	22	* in the range.
	23	*
	24	* Remove Range: Removes an inclusive range of integers [start, end]
	25	* from the set. Not all of the range need already be in
	26	* the set, but any part of the range in the set is removed.
	27	*
	28	* Query: Is an integer in the data structure?
	29	*
	30	* The data structure can be iterated.
	31	*
	32	* For greater efficiency in tracking large numbers of contiguous integers, we
	33	* track integer ranges rather than individual integers. The data structure
	34	* manages a list of integer ranges [[start, end]...]. Internally this is
	35	* implemented as a doubly linked sorted list of range structures, which are
	36	* automatically split and merged as necessary.
	37	*
	38	* This data structure requires O(n) traversal of the list for insertion,
	39	* removal and query when we are not adding/removing ranges which are near the
	40	* beginning or end of the set of ranges. For the applications for which this
	41	* data structure is used (e.g. QUIC PN tracking for ACK generation), it is
	42	* expected that the number of integer ranges needed at any given time will
	43	* generally be small and that most operations will be close to the beginning or
	44	* end of the range.
	45	*
	46	* Invariant: The data structure is always sorted in ascending order by value.
	47	*
	48	* Invariant: No two adjacent ranges ever 'border' one another (have no
	49	* numerical gap between them) as the data structure always ensures
	50	* such ranges are merged.
	51	*
	52	* Invariant: No two ranges ever overlap.
	53	*
	54	* Invariant: No range [a, b] ever has a > b.
	55	*
	56	* Invariant: Since ranges are represented using inclusive bounds, no range
	57	* item inside the data structure can represent a span of zero
	58	* integers.
	59	*/
	60	void ossl_uint_set_init(UINT_SET *s)
	61	{
c5ca7180	62	ossl_list_uint_set_init(s);
83022590 HL	63	}
	64
	65	void ossl_uint_set_destroy(UINT_SET *s)
	66	{
	67	UINT_SET_ITEM x, xnext;
	68
c5ca7180 P	69	for (x = ossl_list_uint_set_head(s); x != NULL; x = xnext) {
c5ca7180 P	70	xnext = ossl_list_uint_set_next(x);
83022590 HL	71	OPENSSL_free(x);
	72	}
	73	}
	74
c5ca7180	75	/* Possible merge of x, prev(x) */
83022590 HL	76	static void uint_set_merge_adjacent(UINT_SET s, UINT_SET_ITEM x)
83022590 HL	77	{
c5ca7180	78	UINT_SET_ITEM *xprev = ossl_list_uint_set_prev(x);
83022590 HL	79
	80	if (xprev == NULL)
	81	return;
	82
	83	if (x->range.start - 1 != xprev->range.end)
	84	return;
	85
	86	x->range.start = xprev->range.start;
c5ca7180	87	ossl_list_uint_set_remove(s, xprev);
83022590	88	OPENSSL_free(xprev);
83022590 HL	89	}
	90
	91	static uint64_t u64_min(uint64_t x, uint64_t y)
	92	{
	93	return x < y ? x : y;
	94	}
	95
	96	static uint64_t u64_max(uint64_t x, uint64_t y)
	97	{
	98	return x > y ? x : y;
	99	}
	100
	101	/*
	102	* Returns 1 if there exists an integer x which falls within both ranges a and
	103	* b.
	104	*/
	105	static int uint_range_overlaps(const UINT_RANGE *a,
	106	const UINT_RANGE *b)
	107	{
	108	return u64_min(a->end, b->end)
	109	>= u64_max(a->start, b->start);
	110	}
	111
c5ca7180 P	112	static UINT_SET_ITEM *create_set_item(uint64_t start, uint64_t end)
c5ca7180 P	113	{
8761efb2 HL	114	UINT_SET_ITEM *x = OPENSSL_malloc(sizeof(UINT_SET_ITEM));
	115
	116	if (x == NULL)
	117	return NULL;
	118
	119	ossl_list_uint_set_init_elem(x);
	120	x->range.start = start;
	121	x->range.end = end;
	122	return x;
c5ca7180 P	123	}
c5ca7180 P	124
83022590 HL	125	int ossl_uint_set_insert(UINT_SET s, const UINT_RANGE range)
83022590 HL	126	{
c5ca7180	127	UINT_SET_ITEM x, xnext, z, zprev, *f;
83022590 HL	128	uint64_t start = range->start, end = range->end;
	129
	130	if (!ossl_assert(start <= end))
	131	return 0;
	132
c5ca7180	133	if (ossl_list_uint_set_is_empty(s)) {
83022590	134	/* Nothing in the set yet, so just add this range. */
c5ca7180	135	x = create_set_item(start, end);
83022590 HL	136	if (x == NULL)
83022590 HL	137	return 0;
c5ca7180	138	ossl_list_uint_set_insert_head(s, x);
83022590 HL	139	return 1;
	140	}
	141
c5ca7180 P	142	z = ossl_list_uint_set_tail(s);
c5ca7180 P	143	if (start > z->range.end) {
83022590 HL	144	/*
	145	* Range is after the latest range in the set, so append.
	146	*
	147	* Note: The case where the range is before the earliest range in the
	148	* set is handled as a degenerate case of the final case below. See
	149	* optimization note (*) below.
	150	*/
c5ca7180 P	151	if (z->range.end + 1 == start) {
c5ca7180 P	152	z->range.end = end;
83022590 HL	153	return 1;
	154	}
	155
c5ca7180	156	x = create_set_item(start, end);
83022590 HL	157	if (x == NULL)
83022590 HL	158	return 0;
c5ca7180	159	ossl_list_uint_set_insert_tail(s, x);
83022590 HL	160	return 1;
	161	}
	162
c5ca7180 P	163	f = ossl_list_uint_set_head(s);
c5ca7180 P	164	if (start <= f->range.start && end >= z->range.end) {
83022590 HL	165	/*
	166	* New range dwarfs all ranges in our set.
	167	*
	168	* Free everything except the first range in the set, which we scavenge
	169	* and reuse.
	170	*/
c5ca7180 P	171	x = ossl_list_uint_set_head(s);
	172	x->range.start = start;
	173	x->range.end = end;
	174	for (x = ossl_list_uint_set_next(x); x != NULL; x = xnext) {
	175	xnext = ossl_list_uint_set_next(x);
	176	ossl_list_uint_set_remove(s, x);
83022590	177	}
83022590 HL	178	return 1;
	179	}
	180
	181	/*
	182	* Walk backwards since we will most often be inserting at the end. As an
	183	* optimization, test the head node first and skip iterating over the
	184	* entire list if we are inserting at the start. The assumption is that
	185	* insertion at the start and end of the space will be the most common
	186	* operations. (*)
	187	*/
c5ca7180 P	188	z = end < f->range.start ? f : z;
	189
	190	for (; z != NULL; z = zprev) {
	191	zprev = ossl_list_uint_set_prev(z);
83022590	192
83022590 HL	193	/* An existing range dwarfs our new range (optimisation). */
	194	if (z->range.start <= start && z->range.end >= end)
	195	return 1;
	196
	197	if (uint_range_overlaps(&z->range, range)) {
	198	/*
	199	* Our new range overlaps an existing range, or possibly several
	200	* existing ranges.
	201	*/
	202	UINT_SET_ITEM *ovend = z;
83022590	203
c5ca7180	204	ovend->range.end = u64_max(end, z->range.end);
83022590 HL	205
83022590 HL	206	/* Get earliest overlapping range. */
c5ca7180 P	207	while (zprev != NULL && uint_range_overlaps(&zprev->range, range)) {
	208	z = zprev;
	209	zprev = ossl_list_uint_set_prev(z);
83022590 HL	210	}
83022590 HL	211
c5ca7180 P	212	ovend->range.start = u64_min(start, z->range.start);
	213
	214	/* Replace sequence of nodes z..ovend with updated ovend only. */
	215	while (z != ovend) {
	216	z = ossl_list_uint_set_next(x = z);
	217	ossl_list_uint_set_remove(s, x);
	218	OPENSSL_free(x);
	219	}
83022590 HL	220	break;
83022590 HL	221	} else if (end < z->range.start
c5ca7180	222	&& (zprev == NULL \|\| start > zprev->range.end)) {
83022590 HL	223	if (z->range.start == end + 1) {
	224	/* We can extend the following range backwards. */
	225	z->range.start = start;
	226
	227	/*
	228	* If this closes a gap we now need to merge
	229	* consecutive nodes.
	230	*/
	231	uint_set_merge_adjacent(s, z);
c5ca7180	232	} else if (zprev != NULL && zprev->range.end + 1 == start) {
83022590	233	/* We can extend the preceding range forwards. */
c5ca7180	234	zprev->range.end = end;
83022590 HL	235
	236	/*
	237	* If this closes a gap we now need to merge
	238	* consecutive nodes.
	239	*/
	240	uint_set_merge_adjacent(s, z);
	241	} else {
	242	/*
	243	* The new interval is between intervals without overlapping or
	244	* touching them, so insert between, preserving sort.
	245	*/
c5ca7180	246	x = create_set_item(start, end);
83022590 HL	247	if (x == NULL)
83022590 HL	248	return 0;
c5ca7180	249	ossl_list_uint_set_insert_before(s, z, x);
83022590 HL	250	}
	251	break;
	252	}
	253	}
	254
	255	return 1;
	256	}
	257
	258	int ossl_uint_set_remove(UINT_SET s, const UINT_RANGE range)
	259	{
	260	UINT_SET_ITEM z, zprev, *y;
	261	uint64_t start = range->start, end = range->end;
	262
	263	if (!ossl_assert(start <= end))
	264	return 0;
	265
	266	/* Walk backwards since we will most often be removing at the end. */
c5ca7180 P	267	for (z = ossl_list_uint_set_tail(s); z != NULL; z = zprev) {
c5ca7180 P	268	zprev = ossl_list_uint_set_prev(z);
83022590 HL	269
	270	if (start > z->range.end)
	271	/* No overlapping ranges can exist beyond this point, so stop. */
	272	break;
	273
	274	if (start <= z->range.start && end >= z->range.end) {
	275	/*
	276	* The range being removed dwarfs this range, so it should be
	277	* removed.
	278	*/
c5ca7180	279	ossl_list_uint_set_remove(s, z);
83022590	280	OPENSSL_free(z);
dc5e5c51	281	} else if (start <= z->range.start && end >= z->range.start) {
83022590 HL	282	/*
	283	* The range being removed includes start of this range, but does
	284	* not cover the entire range (as this would be caught by the case
	285	* above). Shorten the range.
	286	*/
	287	assert(end < z->range.end);
	288	z->range.start = end + 1;
	289	} else if (end >= z->range.end) {
	290	/*
	291	* The range being removed includes the end of this range, but does
	292	* not cover the entire range (as this would be caught by the case
	293	* above). Shorten the range. We can also stop iterating.
	294	*/
	295	assert(start > z->range.start);
	296	assert(start > 0);
	297	z->range.end = start - 1;
	298	break;
	299	} else if (start > z->range.start && end < z->range.end) {
	300	/*
	301	* The range being removed falls entirely in this range, so cut it
	302	* into two. Cases where a zero-length range would be created are
	303	* handled by the above cases.
	304	*/
c5ca7180 P	305	y = create_set_item(end + 1, z->range.end);
c5ca7180 P	306	ossl_list_uint_set_insert_after(s, z, y);
dc5e5c51	307	z->range.end = start - 1;
83022590 HL	308	break;
	309	} else {
	310	/* Assert no partial overlap; all cases should be covered above. */
	311	assert(!uint_range_overlaps(&z->range, range));
	312	}
	313	}
	314
dc5e5c51	315	return 1;
83022590 HL	316	}
	317
	318	int ossl_uint_set_query(const UINT_SET *s, uint64_t v)
	319	{
	320	UINT_SET_ITEM *x;
	321
c5ca7180	322	if (ossl_list_uint_set_is_empty(s))
83022590 HL	323	return 0;
83022590 HL	324
c5ca7180	325	for (x = ossl_list_uint_set_tail(s); x != NULL; x = ossl_list_uint_set_prev(x))
83022590 HL	326	if (x->range.start <= v && x->range.end >= v)
	327	return 1;
	328	else if (x->range.end < v)
	329	return 0;
	330
	331	return 0;
	332	}