lsquic_rechist.c revision 06b2a236 
1/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_rechist.c -- History of received packets.
4 */
5
6#include <assert.h>
7#include <limits.h>
8#include <stddef.h>
9#include <stdint.h>
10#include <stdlib.h>
11#include <string.h>
12
13#include "lsquic_int_types.h"
14#include "lsquic_rechist.h"
15
16
17#define BITS_PER_MASK (sizeof(uintptr_t) * 8)
18
19#if UINTPTR_MAX == 18446744073709551615UL
20#define LOG2_BITS 6
21#else
22#define LOG2_BITS 5
23#endif
24
25
26void
27lsquic_rechist_init (struct lsquic_rechist *rechist, int ietf,
28                                                        unsigned max_ranges)
29{
30    memset(rechist, 0, sizeof(*rechist));
31    rechist->rh_cutoff = ietf ? 0 : 1;
32    /* '1' is an odd case that would add an extra conditional in
33     * rechist_reuse_last_elem(), so we prohibit it.
34     */
35    if (max_ranges == 1)
36        max_ranges = 2;
37    rechist->rh_max_ranges = max_ranges;
38}
39
40
41void
42lsquic_rechist_cleanup (lsquic_rechist_t *rechist)
43{
44    free(rechist->rh_elems);
45    memset(rechist, 0, sizeof(*rechist));
46}
47
48
49static void
50rechist_free_elem (struct lsquic_rechist *rechist, unsigned idx)
51{
52    rechist->rh_masks[idx >> LOG2_BITS] &=
53                                ~(1ull << (idx & ((1u << LOG2_BITS) - 1)));
54    --rechist->rh_n_used;
55}
56
57
58#define RE_HIGH(el_) ((el_)->re_low + (el_)->re_count - 1)
59
60
61static unsigned
62find_free_slot (uintptr_t slots)
63{
64#if __GNUC__
65    if (slots)
66#if UINTPTR_MAX == 18446744073709551615UL
67        return __builtin_ctzll(~slots);
68#else
69        return __builtin_ctzl(~slots);
70#endif
71    else
72        return 0;
73#else
74    unsigned n;
75
76    slots =~ slots;
77    n = 0;
78
79#if UINTPTR_MAX == 18446744073709551615UL
80    if (0 == (slots & ((1ULL << 32) - 1))) { n += 32; slots >>= 32; }
81#endif
82    if (0 == (slots & ((1ULL << 16) - 1))) { n += 16; slots >>= 16; }
83    if (0 == (slots & ((1ULL <<  8) - 1))) { n +=  8; slots >>=  8; }
84    if (0 == (slots & ((1ULL <<  4) - 1))) { n +=  4; slots >>=  4; }
85    if (0 == (slots & ((1ULL <<  2) - 1))) { n +=  2; slots >>=  2; }
86    if (0 == (slots & ((1ULL <<  1) - 1))) { n +=  1; slots >>=  1; }
87    return n;
88#endif
89}
90
91
92static int
93rechist_grow (struct lsquic_rechist *rechist)
94{
95    unsigned n_masks, nelems;
96    size_t size;
97    ptrdiff_t moff;
98    char *mem;
99
100    moff = (char *) rechist->rh_masks - (char *) rechist->rh_elems;
101    if (rechist->rh_n_alloced)
102        nelems = rechist->rh_n_alloced * 2;
103    else
104        nelems = 4;
105    if (rechist->rh_max_ranges && nelems > rechist->rh_max_ranges)
106        nelems = rechist->rh_max_ranges;
107    n_masks = (nelems + (-nelems & (BITS_PER_MASK - 1))) / BITS_PER_MASK;
108    size = sizeof(struct rechist_elem) * nelems + sizeof(uintptr_t) * n_masks;
109    mem = realloc(rechist->rh_elems, size);
110    if (!mem)
111        return -1;
112    if (moff)
113        memcpy(mem + size - n_masks * sizeof(rechist->rh_masks[0]),
114            (char *) mem + moff,
115            rechist->rh_n_masks * sizeof(rechist->rh_masks[0]));
116    if (rechist->rh_n_masks < n_masks)
117        memset(mem + nelems * sizeof(rechist->rh_elems[0])
118            + rechist->rh_n_masks * sizeof(rechist->rh_masks[0]),
119            0, (n_masks - rechist->rh_n_masks) * sizeof(rechist->rh_masks[0]));
120    rechist->rh_n_alloced = nelems;
121    rechist->rh_n_masks = n_masks;
122    rechist->rh_elems = (void *) mem;
123    rechist->rh_masks = (void *) (mem + size
124                                    - n_masks * sizeof(rechist->rh_masks[0]));
125    return 0;
126}
127
128
129/* We hit maximum number of elements.  To allocate a new element, we drop
130 * the last element and return its index, reusing the slot.
131 */
132static int
133rechist_reuse_last_elem (struct lsquic_rechist *rechist)
134{
135    struct rechist_elem *last, *penultimate;
136    unsigned last_idx;
137
138    /* No need to check bitmask anywhere: the array is full! */
139    last = rechist->rh_elems;
140    while (last->re_next != UINT_MAX)
141        ++last;
142
143    last_idx = last - rechist->rh_elems;
144    penultimate = rechist->rh_elems;
145    while (penultimate->re_next != last_idx)
146        ++penultimate;
147
148    penultimate->re_next = UINT_MAX;
149    return last_idx;
150}
151
152
153static int
154rechist_alloc_elem (struct lsquic_rechist *rechist)
155{
156    unsigned i, idx;
157    uintptr_t *mask;
158
159    if (rechist->rh_n_used == rechist->rh_n_alloced)
160    {
161        if (rechist->rh_max_ranges
162                            && rechist->rh_n_used >= rechist->rh_max_ranges)
163            return rechist_reuse_last_elem(rechist);
164        if (0 != rechist_grow(rechist))
165            return -1;
166    }
167
168    for (mask = rechist->rh_masks; *mask == UINTPTR_MAX; ++mask)
169        ;
170
171    i = mask - rechist->rh_masks;
172    assert(i < rechist->rh_n_masks);
173
174    idx = find_free_slot(*mask);
175    *mask |= 1ull << idx;
176    ++rechist->rh_n_used;
177    return idx + i * BITS_PER_MASK;
178}
179
180
181#if LSQUIC_TEST
182/* When compiled as unit test, run sanity check every 127 operations
183 * (127 is better than 128, as the latter aligns too well with the
184 * regular rechist data structure sizes).
185 */
186static void
187rechist_test_sanity (const struct lsquic_rechist *rechist)
188{
189    const struct rechist_elem *el;
190    ptrdiff_t idx;
191    uint64_t *masks;
192    unsigned n_elems;
193
194    masks = calloc(rechist->rh_n_masks, sizeof(masks[0]));
195
196    n_elems = 0;
197    if (rechist->rh_n_used)
198    {
199        el = &rechist->rh_elems[rechist->rh_head];
200        while (1)
201        {
202            ++n_elems;
203            idx = el - rechist->rh_elems;
204            masks[idx >> LOG2_BITS] |= 1ull << (idx & ((1u << LOG2_BITS) - 1));
205            if (el->re_next != UINT_MAX)
206                el = &rechist->rh_elems[el->re_next];
207            else
208                break;
209        }
210    }
211
212    assert(rechist->rh_n_used == n_elems);
213    assert(0 == memcmp(masks, rechist->rh_masks,
214                                    sizeof(masks[0]) * rechist->rh_n_masks));
215    free(masks);
216}
217#define rechist_sanity_check(rechist_) do {                         \
218    if (0 == ++(rechist_)->rh_n_ops % 127)                          \
219        rechist_test_sanity(rechist_);                              \
220} while (0)
221#else
222#define rechist_sanity_check(rechist)
223#endif
224
225
226enum received_st
227lsquic_rechist_received (lsquic_rechist_t *rechist, lsquic_packno_t packno,
228                         lsquic_time_t now)
229{
230    struct rechist_elem *el, *prev;
231    ptrdiff_t next_idx, prev_idx;
232    int idx;
233
234    if (rechist->rh_n_alloced == 0)
235        goto first_elem;
236
237    if (packno < rechist->rh_cutoff)
238        return REC_ST_DUP;
239
240    el = &rechist->rh_elems[rechist->rh_head];
241    prev = NULL;
242
243    if (packno > RE_HIGH(el))
244        rechist->rh_largest_acked_received = now;
245
246    while (1)
247    {
248        if (packno > RE_HIGH(el) + 1)
249            goto insert_before;
250        if (packno == el->re_low - 1)
251        {
252            --el->re_low;
253            ++el->re_count;
254            if (el->re_next != UINT_MAX
255                && el->re_low == RE_HIGH(&rechist->rh_elems[el->re_next]) + 1)
256            {
257                rechist_free_elem(rechist, el->re_next);
258                el->re_count += rechist->rh_elems[el->re_next].re_count;
259                el->re_low    = rechist->rh_elems[el->re_next].re_low;
260                el->re_next   = rechist->rh_elems[el->re_next].re_next;
261            }
262            rechist_sanity_check(rechist);
263            return REC_ST_OK;
264        }
265        if (packno == RE_HIGH(el) + 1)
266        {
267            ++el->re_count;
268            rechist_sanity_check(rechist);
269            return REC_ST_OK;
270        }
271        if (packno >= el->re_low && packno <= RE_HIGH(el))
272            return REC_ST_DUP;
273        if (el->re_next == UINT_MAX)
274            break;  /* insert tail */
275        prev = el;
276        el = &rechist->rh_elems[el->re_next];
277    }
278
279    if (rechist->rh_max_ranges && rechist->rh_n_used >= rechist->rh_max_ranges)
280        goto replace_last_el;
281    prev_idx = el - rechist->rh_elems;
282    idx = rechist_alloc_elem(rechist);
283    if (idx < 0)
284        return REC_ST_ERR;
285
286    rechist->rh_elems[idx].re_low   = packno;
287    rechist->rh_elems[idx].re_count = 1;
288    rechist->rh_elems[idx].re_next  = UINT_MAX;
289    rechist->rh_elems[prev_idx].re_next  = idx;
290    rechist_sanity_check(rechist);
291    return REC_ST_OK;
292
293  first_elem:
294    if (packno < rechist->rh_cutoff)
295        return REC_ST_ERR;
296    idx = rechist_alloc_elem(rechist);
297    if (idx < 0)
298        return REC_ST_ERR;
299
300    rechist->rh_elems[idx].re_low   = packno;
301    rechist->rh_elems[idx].re_count = 1;
302    rechist->rh_elems[idx].re_next  = UINT_MAX;
303    rechist->rh_head = idx;
304    rechist->rh_largest_acked_received = now;
305    rechist_sanity_check(rechist);
306    return REC_ST_OK;
307
308  insert_before:
309    if (el->re_next == UINT_MAX && rechist->rh_max_ranges
310                            && rechist->rh_n_used >= rechist->rh_max_ranges)
311        goto replace_last_el;
312    prev_idx = prev - rechist->rh_elems;
313    next_idx = el - rechist->rh_elems;
314    idx = rechist_alloc_elem(rechist);
315    if (idx < 0)
316        return REC_ST_ERR;
317
318    rechist->rh_elems[idx].re_low   = packno;
319    rechist->rh_elems[idx].re_count = 1;
320    rechist->rh_elems[idx].re_next  = next_idx;
321    if (next_idx == rechist->rh_head)
322        rechist->rh_head = idx;
323    else
324        rechist->rh_elems[prev_idx].re_next  = idx;
325
326    rechist_sanity_check(rechist);
327    return REC_ST_OK;
328
329  replace_last_el:
330    /* Special case: replace last element if chopping, because we cannot
331     * realloc the "prev_idx" hook
332     */
333    assert(el->re_next == UINT_MAX);
334    el->re_low   = packno;
335    el->re_count = 1;
336    rechist_sanity_check(rechist);
337    return REC_ST_OK;
338}
339
340
341void
342lsquic_rechist_stop_wait (lsquic_rechist_t *rechist, lsquic_packno_t cutoff)
343{
344    struct rechist_elem *el, *prev;
345
346    if (rechist->rh_flags & RH_CUTOFF_SET)
347    {
348        assert(cutoff >= rechist->rh_cutoff);  /* Check performed in full_conn */
349        if (cutoff <= rechist->rh_cutoff)
350            return;
351    }
352
353    rechist->rh_cutoff = cutoff;
354    rechist->rh_flags |= RH_CUTOFF_SET;
355
356    if (rechist->rh_n_used == 0)
357        return;
358
359    el = &rechist->rh_elems[rechist->rh_head];
360    prev = NULL;
361    while (1)
362    {
363        if (cutoff > RE_HIGH(el))
364        {
365            if (prev)
366                prev->re_next = UINT_MAX;
367            break;
368        }
369        else if (cutoff > el->re_low)
370        {
371            el->re_count = RE_HIGH(el) - cutoff + 1;
372            el->re_low = cutoff;
373            if (el->re_next != UINT_MAX)
374            {
375                prev = el;
376                el = &rechist->rh_elems[el->re_next];
377                prev->re_next = UINT_MAX;
378                break;
379            }
380            else
381                goto end;
382        }
383        else if (el->re_next == UINT_MAX)
384            goto end;
385        prev = el;
386        el = &rechist->rh_elems[el->re_next];
387    }
388
389    assert(el);
390    while (1)
391    {
392        rechist_free_elem(rechist, el - rechist->rh_elems);
393        if (el->re_next != UINT_MAX)
394            el = &rechist->rh_elems[el->re_next];
395        else
396            break;
397    }
398
399  end:
400    rechist_sanity_check(rechist);
401}
402
403
404lsquic_packno_t
405lsquic_rechist_largest_packno (const lsquic_rechist_t *rechist)
406{
407    if (rechist->rh_n_used)
408        return RE_HIGH(&rechist->rh_elems[rechist->rh_head]);
409    else
410        return 0;   /* Don't call this function if history is empty */
411}
412
413
414lsquic_packno_t
415lsquic_rechist_cutoff (const lsquic_rechist_t *rechist)
416{
417    if (rechist->rh_flags & RH_CUTOFF_SET)
418        return rechist->rh_cutoff;
419    else
420        return 0;
421}
422
423
424lsquic_time_t
425lsquic_rechist_largest_recv (const lsquic_rechist_t *rechist)
426{
427    return rechist->rh_largest_acked_received;
428}
429
430
431const struct lsquic_packno_range *
432lsquic_rechist_first (lsquic_rechist_t *rechist)
433{
434    unsigned idx;
435
436    if (rechist->rh_n_used)
437    {
438        idx = rechist->rh_head;
439        rechist->rh_iter.range.low  = rechist->rh_elems[idx].re_low;
440        rechist->rh_iter.range.high = RE_HIGH(&rechist->rh_elems[idx]);
441        rechist->rh_iter.next       = rechist->rh_elems[idx].re_next;
442        return &rechist->rh_iter.range;
443    }
444    else
445        return NULL;
446}
447
448
449const struct lsquic_packno_range *
450lsquic_rechist_next (lsquic_rechist_t *rechist)
451{
452    unsigned idx;
453
454    idx = rechist->rh_iter.next;
455    if (idx != UINT_MAX)
456    {
457        rechist->rh_iter.range.low  = rechist->rh_elems[idx].re_low;
458        rechist->rh_iter.range.high = RE_HIGH(&rechist->rh_elems[idx]);
459        rechist->rh_iter.next       = rechist->rh_elems[idx].re_next;
460        return &rechist->rh_iter.range;
461    }
462    else
463        return NULL;
464}
465
466
467size_t
468lsquic_rechist_mem_used (const struct lsquic_rechist *rechist)
469{
470    return sizeof(*rechist)
471         + rechist->rh_n_alloced * sizeof(rechist->rh_elems[0])
472         + rechist->rh_n_masks * sizeof(rechist->rh_masks[0]);
473}
474
475
476const struct lsquic_packno_range *
477lsquic_rechist_peek (struct lsquic_rechist *rechist)
478{
479    if (rechist->rh_n_used)
480    {
481        rechist->rh_iter.range.low
482                            = rechist->rh_elems[rechist->rh_head].re_low;
483        rechist->rh_iter.range.high
484                            = RE_HIGH(&rechist->rh_elems[rechist->rh_head]);
485        return &rechist->rh_iter.range;
486    }
487    else
488        return NULL;
489}
490
491
492int
493lsquic_rechist_copy_ranges (struct lsquic_rechist *rechist, void *src_rechist,
494    const struct lsquic_packno_range * (*first) (void *),
495    const struct lsquic_packno_range * (*next) (void *))
496{
497    const struct lsquic_packno_range *range;
498    struct rechist_elem *el;
499    unsigned *next_idx;
500    int idx;
501
502    /* This function only works if rechist contains no elements */
503    assert(rechist->rh_n_used == 0);
504
505    next_idx = &rechist->rh_head;
506    for (range = first(src_rechist); range; range = next(src_rechist))
507    {
508        idx = rechist_alloc_elem(rechist);
509        if (idx < 0)
510            return -1;
511        el = &rechist->rh_elems[idx];
512        el->re_low = range->low;
513        el->re_count = range->high - range->low + 1;
514        el->re_next = UINT_MAX;
515        *next_idx = idx;
516        next_idx = &el->re_next;
517    }
518
519    return 0;
520}
521