lsquic_trechist.c revision 26e8f082
106b2a236SDmitri Tikhonov/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
2fbc6cc04SDmitri Tikhonov#include <assert.h>
3fbc6cc04SDmitri Tikhonov#include <limits.h>
4fbc6cc04SDmitri Tikhonov#include <stddef.h>
5fbc6cc04SDmitri Tikhonov#include <stdint.h>
6fbc6cc04SDmitri Tikhonov
7fbc6cc04SDmitri Tikhonov#include "lsquic_int_types.h"
8fbc6cc04SDmitri Tikhonov#include "lsquic_trechist.h"
9fbc6cc04SDmitri Tikhonov
10fbc6cc04SDmitri Tikhonov
11fbc6cc04SDmitri Tikhonovstatic unsigned
12fbc6cc04SDmitri Tikhonovfind_free_slot (uint32_t slots)
13fbc6cc04SDmitri Tikhonov{
14fbc6cc04SDmitri Tikhonov#if __GNUC__
15fbc6cc04SDmitri Tikhonov    return __builtin_ctz(~slots);
16fbc6cc04SDmitri Tikhonov#else
17fbc6cc04SDmitri Tikhonov    unsigned n;
18fbc6cc04SDmitri Tikhonov
19fbc6cc04SDmitri Tikhonov    slots =~ slots;
20fbc6cc04SDmitri Tikhonov    n = 0;
21fbc6cc04SDmitri Tikhonov
22fbc6cc04SDmitri Tikhonov    if (0 == (slots & ((1ULL << 16) - 1))) { n += 16; slots >>= 16; }
23fbc6cc04SDmitri Tikhonov    if (0 == (slots & ((1ULL <<  8) - 1))) { n +=  8; slots >>=  8; }
24fbc6cc04SDmitri Tikhonov    if (0 == (slots & ((1ULL <<  4) - 1))) { n +=  4; slots >>=  4; }
25fbc6cc04SDmitri Tikhonov    if (0 == (slots & ((1ULL <<  2) - 1))) { n +=  2; slots >>=  2; }
26fbc6cc04SDmitri Tikhonov    if (0 == (slots & ((1ULL <<  1) - 1))) { n +=  1; slots >>=  1; }
27fbc6cc04SDmitri Tikhonov    return n;
28fbc6cc04SDmitri Tikhonov#endif
29fbc6cc04SDmitri Tikhonov}
30fbc6cc04SDmitri Tikhonov
31fbc6cc04SDmitri Tikhonov
3226e8f082SDmitri Tikhonov/* When capacity is reached, smallest element is removed.  When the number
3326e8f082SDmitri Tikhonov * of elements in a single range cannot be represented by te_count, an
3426e8f082SDmitri Tikhonov * error is returned.  This is the only error this function returns.
3526e8f082SDmitri Tikhonov */
36fbc6cc04SDmitri Tikhonovint
37fbc6cc04SDmitri Tikhonovlsquic_trechist_insert (trechist_mask_t *mask, struct trechist_elem *elems,
38fbc6cc04SDmitri Tikhonov                                                            uint32_t packno)
39fbc6cc04SDmitri Tikhonov{
4026e8f082SDmitri Tikhonov    struct trechist_elem *el, *prev, *cur, *next;
41fbc6cc04SDmitri Tikhonov    unsigned idx;
42fbc6cc04SDmitri Tikhonov
43fbc6cc04SDmitri Tikhonov    if (*mask == 0)
44fbc6cc04SDmitri Tikhonov    {
45fbc6cc04SDmitri Tikhonov        elems[0].te_low   = packno;
46fbc6cc04SDmitri Tikhonov        elems[0].te_count = 1;
47fbc6cc04SDmitri Tikhonov        elems[0].te_next  = 0;
48fbc6cc04SDmitri Tikhonov        *mask |= 1;
49fbc6cc04SDmitri Tikhonov        return 0;
50fbc6cc04SDmitri Tikhonov    }
51fbc6cc04SDmitri Tikhonov
52fbc6cc04SDmitri Tikhonov    el = elems;
53fbc6cc04SDmitri Tikhonov    prev = NULL;
54fbc6cc04SDmitri Tikhonov    while (1)
55fbc6cc04SDmitri Tikhonov    {
56fbc6cc04SDmitri Tikhonov        if (packno > TE_HIGH(el) + 1)
57fbc6cc04SDmitri Tikhonov            goto insert_before;
58fbc6cc04SDmitri Tikhonov        if (packno == el->te_low - 1)
59fbc6cc04SDmitri Tikhonov        {
6026e8f082SDmitri Tikhonov            if (el->te_next && el->te_low == TE_HIGH(&elems[el->te_next]) + 2)
61fbc6cc04SDmitri Tikhonov            {
6226e8f082SDmitri Tikhonov                if (el->te_count + elems[el->te_next].te_count - 1 > UCHAR_MAX)
6326e8f082SDmitri Tikhonov                    return -1;
64fbc6cc04SDmitri Tikhonov                *mask &= ~(1u << el->te_next);
6526e8f082SDmitri Tikhonov                el->te_count += elems[el->te_next].te_count + 1;
66fbc6cc04SDmitri Tikhonov                el->te_low    = elems[el->te_next].te_low;
67fbc6cc04SDmitri Tikhonov                el->te_next   = elems[el->te_next].te_next;
68fbc6cc04SDmitri Tikhonov            }
6926e8f082SDmitri Tikhonov            else
7026e8f082SDmitri Tikhonov            {
7126e8f082SDmitri Tikhonov                if (el->te_count == UCHAR_MAX)
7226e8f082SDmitri Tikhonov                    return -1;
7326e8f082SDmitri Tikhonov                --el->te_low;
7426e8f082SDmitri Tikhonov                ++el->te_count;
7526e8f082SDmitri Tikhonov            }
76fbc6cc04SDmitri Tikhonov            return 0;
77fbc6cc04SDmitri Tikhonov        }
78fbc6cc04SDmitri Tikhonov        if (packno == TE_HIGH(el) + 1)
79fbc6cc04SDmitri Tikhonov        {
80fbc6cc04SDmitri Tikhonov            if (el->te_count == UCHAR_MAX)
81fbc6cc04SDmitri Tikhonov                return -1;
82fbc6cc04SDmitri Tikhonov            ++el->te_count;
83fbc6cc04SDmitri Tikhonov            return 0;
84fbc6cc04SDmitri Tikhonov        }
85fbc6cc04SDmitri Tikhonov        if (packno >= el->te_low && packno <= TE_HIGH(el))
8626e8f082SDmitri Tikhonov            return 0;   /* Dup */
87fbc6cc04SDmitri Tikhonov        if (!el->te_next)
88fbc6cc04SDmitri Tikhonov            break;  /* insert tail */
89fbc6cc04SDmitri Tikhonov        prev = el;
90fbc6cc04SDmitri Tikhonov        el = &elems[el->te_next];
91fbc6cc04SDmitri Tikhonov    }
92fbc6cc04SDmitri Tikhonov
9326e8f082SDmitri Tikhonov    if (*mask == TRECHIST_MAX_RANGES_MASK)
9426e8f082SDmitri Tikhonov        /* No need to insert element smaller than the smallest element
9526e8f082SDmitri Tikhonov         * already in our list.  The new element "overflows".
9626e8f082SDmitri Tikhonov         */
9726e8f082SDmitri Tikhonov        return 0;
98fbc6cc04SDmitri Tikhonov
99fbc6cc04SDmitri Tikhonov    idx = find_free_slot(*mask);
100fbc6cc04SDmitri Tikhonov    elems[idx].te_low   = packno;
101fbc6cc04SDmitri Tikhonov    elems[idx].te_count = 1;
102fbc6cc04SDmitri Tikhonov    elems[idx].te_next  = 0;
103fbc6cc04SDmitri Tikhonov    *mask |= 1u << idx;;
104fbc6cc04SDmitri Tikhonov    el->te_next = idx;
105fbc6cc04SDmitri Tikhonov    return 0;
106fbc6cc04SDmitri Tikhonov
107fbc6cc04SDmitri Tikhonov  insert_before:
108fbc6cc04SDmitri Tikhonov
10926e8f082SDmitri Tikhonov    if (*mask != TRECHIST_MAX_RANGES_MASK)
11026e8f082SDmitri Tikhonov        idx = find_free_slot(*mask);
11126e8f082SDmitri Tikhonov    else
11226e8f082SDmitri Tikhonov    {   /* Drop last element and reuse its slot */
11326e8f082SDmitri Tikhonov        for (next = &elems[el->te_next], cur = el; next->te_next;
11426e8f082SDmitri Tikhonov                                cur = next, next = &elems[cur->te_next])
11526e8f082SDmitri Tikhonov            ;
11626e8f082SDmitri Tikhonov        idx = cur->te_next;
11726e8f082SDmitri Tikhonov        cur->te_next = 0;
11826e8f082SDmitri Tikhonov    }
119fbc6cc04SDmitri Tikhonov
120fbc6cc04SDmitri Tikhonov    *mask |= 1u << idx;;
121fbc6cc04SDmitri Tikhonov    if (el == elems)
122fbc6cc04SDmitri Tikhonov    {
123fbc6cc04SDmitri Tikhonov        elems[idx] = *el;
124fbc6cc04SDmitri Tikhonov        elems[0].te_low   = packno;
125fbc6cc04SDmitri Tikhonov        elems[0].te_count = 1;
126fbc6cc04SDmitri Tikhonov        elems[0].te_next  = idx;
127fbc6cc04SDmitri Tikhonov    }
128fbc6cc04SDmitri Tikhonov    else
129fbc6cc04SDmitri Tikhonov    {
130fbc6cc04SDmitri Tikhonov        assert(prev);
131fbc6cc04SDmitri Tikhonov        elems[idx].te_low   = packno;
132fbc6cc04SDmitri Tikhonov        elems[idx].te_count = 1;
133fbc6cc04SDmitri Tikhonov        elems[idx].te_next  = prev->te_next;
134fbc6cc04SDmitri Tikhonov        prev->te_next = idx;
135fbc6cc04SDmitri Tikhonov    }
136fbc6cc04SDmitri Tikhonov
137fbc6cc04SDmitri Tikhonov    return 0;
138fbc6cc04SDmitri Tikhonov}
139fbc6cc04SDmitri Tikhonov
140fbc6cc04SDmitri Tikhonov
141fbc6cc04SDmitri Tikhonovvoid
142fbc6cc04SDmitri Tikhonovlsquic_trechist_iter (struct trechist_iter *iter, trechist_mask_t mask,
143fbc6cc04SDmitri Tikhonov                                            const struct trechist_elem *elems)
144fbc6cc04SDmitri Tikhonov{
145fbc6cc04SDmitri Tikhonov    iter->mask = mask;
146fbc6cc04SDmitri Tikhonov    iter->elems = elems;
147fbc6cc04SDmitri Tikhonov}
148fbc6cc04SDmitri Tikhonov
149fbc6cc04SDmitri Tikhonov
150fbc6cc04SDmitri Tikhonovconst struct lsquic_packno_range *
151fbc6cc04SDmitri Tikhonovlsquic_trechist_first (void *iter_p)
152fbc6cc04SDmitri Tikhonov{
153fbc6cc04SDmitri Tikhonov    struct trechist_iter *const iter = iter_p;
154fbc6cc04SDmitri Tikhonov
155fbc6cc04SDmitri Tikhonov    if (iter->mask == 0)
156fbc6cc04SDmitri Tikhonov        return NULL;
157fbc6cc04SDmitri Tikhonov
158fbc6cc04SDmitri Tikhonov    iter->next = iter->elems[0].te_next;
159fbc6cc04SDmitri Tikhonov    iter->range.low = iter->elems[0].te_low;
160fbc6cc04SDmitri Tikhonov    iter->range.high = TE_HIGH(&iter->elems[0]);
161fbc6cc04SDmitri Tikhonov    return &iter->range;
162fbc6cc04SDmitri Tikhonov}
163fbc6cc04SDmitri Tikhonov
164fbc6cc04SDmitri Tikhonov
165fbc6cc04SDmitri Tikhonovconst struct lsquic_packno_range *
166fbc6cc04SDmitri Tikhonovlsquic_trechist_next (void *iter_p)
167fbc6cc04SDmitri Tikhonov{
168fbc6cc04SDmitri Tikhonov    struct trechist_iter *const iter = iter_p;
169fbc6cc04SDmitri Tikhonov
170fbc6cc04SDmitri Tikhonov    if (iter->next == 0)
171fbc6cc04SDmitri Tikhonov        return NULL;
172fbc6cc04SDmitri Tikhonov
173fbc6cc04SDmitri Tikhonov    iter->range.low = iter->elems[iter->next].te_low;
174fbc6cc04SDmitri Tikhonov    iter->range.high = TE_HIGH(&iter->elems[iter->next]);
175fbc6cc04SDmitri Tikhonov    iter->next = iter->elems[iter->next].te_next;
176fbc6cc04SDmitri Tikhonov    return &iter->range;
177fbc6cc04SDmitri Tikhonov}
178fbc6cc04SDmitri Tikhonov
179fbc6cc04SDmitri Tikhonov
18026e8f082SDmitri Tikhonov/* First TRECHIST_MAX_RANGES ranges are copied */
18126e8f082SDmitri Tikhonovvoid
182fbc6cc04SDmitri Tikhonovlsquic_trechist_copy_ranges (trechist_mask_t *mask,
183fbc6cc04SDmitri Tikhonov                    struct trechist_elem *elems, void *src_rechist,
184fbc6cc04SDmitri Tikhonov                    const struct lsquic_packno_range * (*first) (void *),
185fbc6cc04SDmitri Tikhonov                    const struct lsquic_packno_range * (*next) (void *))
186fbc6cc04SDmitri Tikhonov{
187fbc6cc04SDmitri Tikhonov    const struct lsquic_packno_range *range;
188fbc6cc04SDmitri Tikhonov    struct trechist_elem *el;
189fbc6cc04SDmitri Tikhonov    unsigned i;
190fbc6cc04SDmitri Tikhonov
191fbc6cc04SDmitri Tikhonov    for (el = NULL, i = 0, range = first(src_rechist);
192fbc6cc04SDmitri Tikhonov            i < TRECHIST_MAX_RANGES && range;
193fbc6cc04SDmitri Tikhonov                range = next(src_rechist), ++i)
194fbc6cc04SDmitri Tikhonov    {
195fbc6cc04SDmitri Tikhonov        /* This should never happen: */
196fbc6cc04SDmitri Tikhonov        assert(range->high - range->low + 1 <= UINT_MAX);
197fbc6cc04SDmitri Tikhonov
198fbc6cc04SDmitri Tikhonov        el = &elems[i];
199fbc6cc04SDmitri Tikhonov        el->te_low = range->low;
200fbc6cc04SDmitri Tikhonov        el->te_count = range->high - range->low + 1;
201fbc6cc04SDmitri Tikhonov        el->te_next = i + 1;
202fbc6cc04SDmitri Tikhonov    }
203fbc6cc04SDmitri Tikhonov
20426e8f082SDmitri Tikhonov    if (el)
205fbc6cc04SDmitri Tikhonov        el->te_next = 0;
20626e8f082SDmitri Tikhonov
20726e8f082SDmitri Tikhonov    if (i < 32)
208fbc6cc04SDmitri Tikhonov        *mask = (1u << i) - 1;
209fbc6cc04SDmitri Tikhonov    else
21026e8f082SDmitri Tikhonov        *mask = UINT32_MAX;
211fbc6cc04SDmitri Tikhonov}
212fbc6cc04SDmitri Tikhonov
213fbc6cc04SDmitri Tikhonov
214fbc6cc04SDmitri Tikhonovint
215fbc6cc04SDmitri Tikhonovlsquic_trechist_contains (trechist_mask_t mask,
216fbc6cc04SDmitri Tikhonov                    const struct trechist_elem *elems, uint32_t packno)
217fbc6cc04SDmitri Tikhonov{
218fbc6cc04SDmitri Tikhonov    const struct trechist_elem *el;
219fbc6cc04SDmitri Tikhonov    if (mask == 0)
220fbc6cc04SDmitri Tikhonov        return 0;
221fbc6cc04SDmitri Tikhonov
222fbc6cc04SDmitri Tikhonov    el = &elems[0];
223fbc6cc04SDmitri Tikhonov    while (1)
224fbc6cc04SDmitri Tikhonov    {
225fbc6cc04SDmitri Tikhonov        if (packno > TE_HIGH(el))
226fbc6cc04SDmitri Tikhonov            return 0;
227fbc6cc04SDmitri Tikhonov        if (packno >= el->te_low)
228fbc6cc04SDmitri Tikhonov            return 1;
229fbc6cc04SDmitri Tikhonov        if (el->te_next)
230fbc6cc04SDmitri Tikhonov            el = &elems[el->te_next];
231fbc6cc04SDmitri Tikhonov        else
232fbc6cc04SDmitri Tikhonov            break;
233fbc6cc04SDmitri Tikhonov    }
234fbc6cc04SDmitri Tikhonov
235fbc6cc04SDmitri Tikhonov    return 0;
236fbc6cc04SDmitri Tikhonov}
237fbc6cc04SDmitri Tikhonov
238fbc6cc04SDmitri Tikhonov
239fbc6cc04SDmitri Tikhonovuint32_t
240fbc6cc04SDmitri Tikhonovlsquic_trechist_max (trechist_mask_t mask, const struct trechist_elem *elems)
241fbc6cc04SDmitri Tikhonov{
242fbc6cc04SDmitri Tikhonov    if (mask)
243fbc6cc04SDmitri Tikhonov    {
244fbc6cc04SDmitri Tikhonov        assert(mask & 1);
245fbc6cc04SDmitri Tikhonov        return TE_HIGH(&elems[0]);
246fbc6cc04SDmitri Tikhonov    }
247fbc6cc04SDmitri Tikhonov    else
248fbc6cc04SDmitri Tikhonov        return 0;
249fbc6cc04SDmitri Tikhonov}
250