lsquic_rechist.c revision b62ec17f 
1/* Copyright (c) 2017 - 2020 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{
29    memset(rechist, 0, sizeof(*rechist));
30    rechist->rh_cutoff = ietf ? 0 : 1;
31}
32
33
34void
35lsquic_rechist_cleanup (lsquic_rechist_t *rechist)
36{
37    free(rechist->rh_elems);
38    memset(rechist, 0, sizeof(*rechist));
39}
40
41
42static void
43rechist_free_elem (struct lsquic_rechist *rechist, unsigned idx)
44{
45    rechist->rh_masks[idx >> LOG2_BITS] &=
46                                ~(1ull << (idx & ((1u << LOG2_BITS) - 1)));
47    --rechist->rh_n_used;
48}
49
50
51#define RE_HIGH(el_) ((el_)->re_low + (el_)->re_count - 1)
52
53
54static unsigned
55find_free_slot (uintptr_t slots)
56{
57#if __GNUC__
58    if (slots)
59#if UINTPTR_MAX == 18446744073709551615UL
60        return __builtin_ctzll(~slots);
61#else
62        return __builtin_ctzl(~slots);
63#endif
64    else
65        return 0;
66#else
67    unsigned n;
68
69    slots =~ slots;
70    n = 0;
71
72#if UINTPTR_MAX == 18446744073709551615UL
73    if (0 == (slots & ((1ULL << 32) - 1))) { n += 32; slots >>= 32; }
74#endif
75    if (0 == (slots & ((1ULL << 16) - 1))) { n += 16; slots >>= 16; }
76    if (0 == (slots & ((1ULL <<  8) - 1))) { n +=  8; slots >>=  8; }
77    if (0 == (slots & ((1ULL <<  4) - 1))) { n +=  4; slots >>=  4; }
78    if (0 == (slots & ((1ULL <<  2) - 1))) { n +=  2; slots >>=  2; }
79    if (0 == (slots & ((1ULL <<  1) - 1))) { n +=  1; slots >>=  1; }
80    return n;
81#endif
82}
83
84
85static int
86rechist_grow (struct lsquic_rechist *rechist)
87{
88    unsigned n_masks, nelems;
89    size_t size;
90    ptrdiff_t moff;
91    char *mem;
92
93    moff = (char *) rechist->rh_masks - (char *) rechist->rh_elems;
94    if (rechist->rh_n_alloced)
95        nelems = rechist->rh_n_alloced * 2;
96    else
97        nelems = 4;
98    n_masks = (nelems + (-nelems & (BITS_PER_MASK - 1))) / BITS_PER_MASK;
99    size = sizeof(struct rechist_elem) * nelems + sizeof(uintptr_t) * n_masks;
100    mem = realloc(rechist->rh_elems, size);
101    if (!mem)
102        return -1;
103    if (moff)
104        memcpy(mem + size - n_masks * sizeof(rechist->rh_masks[0]),
105            (char *) mem + moff,
106            rechist->rh_n_masks * sizeof(rechist->rh_masks[0]));
107    if (rechist->rh_n_masks < n_masks)
108        memset(mem + nelems * sizeof(rechist->rh_elems[0])
109            + rechist->rh_n_masks * sizeof(rechist->rh_masks[0]),
110            0, (n_masks - rechist->rh_n_masks) * sizeof(rechist->rh_masks[0]));
111    rechist->rh_n_alloced = nelems;
112    rechist->rh_n_masks = n_masks;
113    rechist->rh_elems = (void *) mem;
114    rechist->rh_masks = (void *) (mem + size
115                                    - n_masks * sizeof(rechist->rh_masks[0]));
116    return 0;
117}
118
119
120static int
121rechist_alloc_elem (struct lsquic_rechist *rechist)
122{
123    unsigned i, idx;
124    uintptr_t *mask;
125
126    if (rechist->rh_n_used == rechist->rh_n_alloced
127                                            && 0 != rechist_grow(rechist))
128        return -1;
129
130    for (mask = rechist->rh_masks; *mask == UINTPTR_MAX; ++mask)
131        ;
132
133    i = mask - rechist->rh_masks;
134    assert(i < rechist->rh_n_masks);
135
136    idx = find_free_slot(*mask);
137    *mask |= 1ull << idx;
138    ++rechist->rh_n_used;
139    return idx + i * BITS_PER_MASK;
140}
141
142
143#if LSQUIC_TEST
144/* When compiled as unit test, run sanity check every 127 operations
145 * (127 is better than 128, as the latter aligns too well with the
146 * regular rechist data structure sizes).
147 */
148static void
149rechist_test_sanity (const struct lsquic_rechist *rechist)
150{
151    const struct rechist_elem *el;
152    ptrdiff_t idx;
153    uint64_t *masks;
154    unsigned n_elems;
155
156    masks = calloc(rechist->rh_n_masks, sizeof(masks[0]));
157
158    n_elems = 0;
159    if (rechist->rh_n_used)
160    {
161        el = &rechist->rh_elems[rechist->rh_head];
162        while (1)
163        {
164            ++n_elems;
165            idx = el - rechist->rh_elems;
166            masks[idx >> LOG2_BITS] |= 1ull << (idx & ((1u << LOG2_BITS) - 1));
167            if (el->re_next != UINT_MAX)
168                el = &rechist->rh_elems[el->re_next];
169            else
170                break;
171        }
172    }
173
174    assert(rechist->rh_n_used == n_elems);
175    assert(0 == memcmp(masks, rechist->rh_masks,
176                                    sizeof(masks[0]) * rechist->rh_n_masks));
177    free(masks);
178}
179#define rechist_sanity_check(rechist_) do {                         \
180    if (0 == ++(rechist_)->rh_n_ops % 127)                          \
181        rechist_test_sanity(rechist_);                              \
182} while (0)
183#else
184#define rechist_sanity_check(rechist)
185#endif
186
187
188enum received_st
189lsquic_rechist_received (lsquic_rechist_t *rechist, lsquic_packno_t packno,
190                         lsquic_time_t now)
191{
192    struct rechist_elem *el, *prev;
193    ptrdiff_t next_idx, prev_idx;
194    int idx;
195
196    if (rechist->rh_n_alloced == 0)
197        goto first_elem;
198
199    if (packno < rechist->rh_cutoff)
200        return REC_ST_DUP;
201
202    el = &rechist->rh_elems[rechist->rh_head];
203    prev = NULL;
204
205    if (packno > RE_HIGH(el))
206        rechist->rh_largest_acked_received = now;
207
208    while (1)
209    {
210        if (packno > RE_HIGH(el) + 1)
211            goto insert_before;
212        if (packno == el->re_low - 1)
213        {
214            --el->re_low;
215            ++el->re_count;
216            if (el->re_next != UINT_MAX
217                && el->re_low == RE_HIGH(&rechist->rh_elems[el->re_next]) + 1)
218            {
219                rechist_free_elem(rechist, el->re_next);
220                el->re_count += rechist->rh_elems[el->re_next].re_count;
221                el->re_low    = rechist->rh_elems[el->re_next].re_low;
222                el->re_next   = rechist->rh_elems[el->re_next].re_next;
223            }
224            rechist_sanity_check(rechist);
225            return REC_ST_OK;
226        }
227        if (packno == RE_HIGH(el) + 1)
228        {
229            ++el->re_count;
230            rechist_sanity_check(rechist);
231            return REC_ST_OK;
232        }
233        if (packno >= el->re_low && packno <= RE_HIGH(el))
234            return REC_ST_DUP;
235        if (el->re_next == UINT_MAX)
236            break;  /* insert tail */
237        prev = el;
238        el = &rechist->rh_elems[el->re_next];
239    }
240
241    prev_idx = el - rechist->rh_elems;
242    idx = rechist_alloc_elem(rechist);
243    if (idx < 0)
244        return REC_ST_ERR;
245
246    rechist->rh_elems[idx].re_low   = packno;
247    rechist->rh_elems[idx].re_count = 1;
248    rechist->rh_elems[idx].re_next  = UINT_MAX;
249    rechist->rh_elems[prev_idx].re_next  = idx;
250    rechist_sanity_check(rechist);
251    return REC_ST_OK;
252
253  first_elem:
254    if (packno < rechist->rh_cutoff)
255        return REC_ST_ERR;
256    idx = rechist_alloc_elem(rechist);
257    if (idx < 0)
258        return REC_ST_ERR;
259
260    rechist->rh_elems[idx].re_low   = packno;
261    rechist->rh_elems[idx].re_count = 1;
262    rechist->rh_elems[idx].re_next  = UINT_MAX;
263    rechist->rh_head = idx;
264    rechist->rh_largest_acked_received = now;
265    rechist_sanity_check(rechist);
266    return REC_ST_OK;
267
268  insert_before:
269    prev_idx = prev - rechist->rh_elems;
270    next_idx = el - rechist->rh_elems;
271    idx = rechist_alloc_elem(rechist);
272    if (idx < 0)
273        return REC_ST_ERR;
274
275    rechist->rh_elems[idx].re_low   = packno;
276    rechist->rh_elems[idx].re_count = 1;
277    rechist->rh_elems[idx].re_next  = next_idx;
278    if (next_idx == rechist->rh_head)
279        rechist->rh_head = idx;
280    else
281        rechist->rh_elems[prev_idx].re_next  = idx;
282
283    rechist_sanity_check(rechist);
284    return REC_ST_OK;
285}
286
287
288void
289lsquic_rechist_stop_wait (lsquic_rechist_t *rechist, lsquic_packno_t cutoff)
290{
291    struct rechist_elem *el, *prev;
292
293    if (rechist->rh_flags & RH_CUTOFF_SET)
294    {
295        assert(cutoff >= rechist->rh_cutoff);  /* Check performed in full_conn */
296        if (cutoff <= rechist->rh_cutoff)
297            return;
298    }
299
300    rechist->rh_cutoff = cutoff;
301    rechist->rh_flags |= RH_CUTOFF_SET;
302
303    if (rechist->rh_n_used == 0)
304        return;
305
306    el = &rechist->rh_elems[rechist->rh_head];
307    prev = NULL;
308    while (1)
309    {
310        if (cutoff > RE_HIGH(el))
311        {
312            if (prev)
313                prev->re_next = UINT_MAX;
314            break;
315        }
316        else if (cutoff > el->re_low)
317        {
318            el->re_count = RE_HIGH(el) - cutoff + 1;
319            el->re_low = cutoff;
320            if (el->re_next != UINT_MAX)
321            {
322                prev = el;
323                el = &rechist->rh_elems[el->re_next];
324                prev->re_next = UINT_MAX;
325                break;
326            }
327            else
328                goto end;
329        }
330        else if (el->re_next == UINT_MAX)
331            goto end;
332        prev = el;
333        el = &rechist->rh_elems[el->re_next];
334    }
335
336    assert(el);
337    while (1)
338    {
339        rechist_free_elem(rechist, el - rechist->rh_elems);
340        if (el->re_next != UINT_MAX)
341            el = &rechist->rh_elems[el->re_next];
342        else
343            break;
344    }
345
346  end:
347    rechist_sanity_check(rechist);
348}
349
350
351lsquic_packno_t
352lsquic_rechist_largest_packno (const lsquic_rechist_t *rechist)
353{
354    if (rechist->rh_n_used)
355        return RE_HIGH(&rechist->rh_elems[rechist->rh_head]);
356    else
357        return 0;   /* Don't call this function if history is empty */
358}
359
360
361lsquic_packno_t
362lsquic_rechist_cutoff (const lsquic_rechist_t *rechist)
363{
364    if (rechist->rh_flags & RH_CUTOFF_SET)
365        return rechist->rh_cutoff;
366    else
367        return 0;
368}
369
370
371lsquic_time_t
372lsquic_rechist_largest_recv (const lsquic_rechist_t *rechist)
373{
374    return rechist->rh_largest_acked_received;
375}
376
377
378const struct lsquic_packno_range *
379lsquic_rechist_first (lsquic_rechist_t *rechist)
380{
381    unsigned idx;
382
383    if (rechist->rh_n_used)
384    {
385        idx = rechist->rh_head;
386        rechist->rh_iter.range.low  = rechist->rh_elems[idx].re_low;
387        rechist->rh_iter.range.high = RE_HIGH(&rechist->rh_elems[idx]);
388        rechist->rh_iter.next       = rechist->rh_elems[idx].re_next;
389        return &rechist->rh_iter.range;
390    }
391    else
392        return NULL;
393}
394
395
396const struct lsquic_packno_range *
397lsquic_rechist_next (lsquic_rechist_t *rechist)
398{
399    unsigned idx;
400
401    idx = rechist->rh_iter.next;
402    if (idx != UINT_MAX)
403    {
404        rechist->rh_iter.range.low  = rechist->rh_elems[idx].re_low;
405        rechist->rh_iter.range.high = RE_HIGH(&rechist->rh_elems[idx]);
406        rechist->rh_iter.next       = rechist->rh_elems[idx].re_next;
407        return &rechist->rh_iter.range;
408    }
409    else
410        return NULL;
411}
412
413
414size_t
415lsquic_rechist_mem_used (const struct lsquic_rechist *rechist)
416{
417    return sizeof(*rechist)
418         + rechist->rh_n_alloced * sizeof(rechist->rh_elems[0])
419         + rechist->rh_n_masks * sizeof(rechist->rh_masks[0]);
420}
421
422
423const struct lsquic_packno_range *
424lsquic_rechist_peek (struct lsquic_rechist *rechist)
425{
426    if (rechist->rh_n_used)
427    {
428        rechist->rh_iter.range.low
429                            = rechist->rh_elems[rechist->rh_head].re_low;
430        rechist->rh_iter.range.high
431                            = RE_HIGH(&rechist->rh_elems[rechist->rh_head]);
432        return &rechist->rh_iter.range;
433    }
434    else
435        return NULL;
436}
437