test_trechist.c revision a74702c6 
1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2/* Tests based on rechist tests */
3
4#include <assert.h>
5#include <inttypes.h>
6#include <limits.h>
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11#ifdef WIN32
12#include "vc_compat.h"
13#endif
14
15#include "lsquic_int_types.h"
16#include "lsquic_trechist.h"
17
18
19struct str_range_iter
20{
21    char                        *str;
22    struct lsquic_packno_range   range;
23};
24
25
26static const struct lsquic_packno_range *
27next_str_range (void *ctx)
28{
29    struct str_range_iter *const str_iter = ctx;
30
31    if (str_iter->str && str_iter->str[0] == '[')
32    {
33        str_iter->range.high = strtoul(str_iter->str + 1, &str_iter->str, 10);
34        assert('-' == *str_iter->str);
35        str_iter->range.low = strtoul(str_iter->str + 1, &str_iter->str, 10);
36        assert(']' == *str_iter->str);
37        ++str_iter->str;
38        return &str_iter->range;
39    }
40    else
41        return NULL;
42}
43
44
45static void
46test_clone (trechist_mask_t src_mask, struct trechist_elem *src_elems)
47{
48    trechist_mask_t       hist_mask;
49    struct trechist_elem *hist_elems;
50    const struct lsquic_packno_range *ranges[2];
51    struct trechist_iter iters[2];
52
53    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
54
55    lsquic_trechist_iter(&iters[0], src_mask, src_elems);
56    lsquic_trechist_copy_ranges(&hist_mask, hist_elems, &iters[0],
57                        lsquic_trechist_first, lsquic_trechist_next);
58
59    lsquic_trechist_iter(&iters[0], src_mask, src_elems);
60    lsquic_trechist_iter(&iters[1], hist_mask, hist_elems);
61
62    for (ranges[0] = lsquic_trechist_first(&iters[0]),
63         ranges[1] = lsquic_trechist_first(&iters[1]);
64
65         ranges[0] && ranges[1];
66
67         ranges[0] = lsquic_trechist_next(&iters[0]),
68         ranges[1] = lsquic_trechist_next(&iters[1]))
69    {
70        assert(ranges[0]->low == ranges[1]->low);
71        assert(ranges[0]->high == ranges[1]->high);
72    }
73
74    assert(!ranges[0] && !ranges[1]);
75
76    free(hist_elems);
77}
78
79
80static void
81test4 (void)
82{
83    trechist_mask_t       hist_mask;
84    struct trechist_elem *hist_elems;
85    const struct lsquic_packno_range *range;
86    struct trechist_iter iter;
87    lsquic_packno_t packno;
88
89    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
90    hist_mask = 0;
91    test_clone(hist_mask, hist_elems);
92
93    for (packno = 11917; packno <= 11941; ++packno)
94        lsquic_trechist_insert(&hist_mask, hist_elems, packno);
95    for (packno = 11946; packno <= 11994; ++packno)
96        lsquic_trechist_insert(&hist_mask, hist_elems, packno);
97
98    test_clone(hist_mask, hist_elems);
99    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
100    range = lsquic_trechist_first(&iter);
101    assert(range);
102    assert(range->high == 11994);
103    assert(range->low == 11946);
104    range = lsquic_trechist_next(&iter);
105    assert(range);
106    assert(range->high == 11941);
107    assert(range->low == 11917);
108    range = lsquic_trechist_next(&iter);
109    assert(!range);
110
111    lsquic_trechist_insert(&hist_mask, hist_elems, 11995);
112    lsquic_trechist_insert(&hist_mask, hist_elems, 11996);
113    test_clone(hist_mask, hist_elems);
114
115    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
116    range = lsquic_trechist_first(&iter);
117    assert(range);
118    assert(range->high == 11996);
119    assert(range->low == 11946);
120    range = lsquic_trechist_next(&iter);
121    assert(range);
122    assert(range->high == 11941);
123    assert(range->low == 11917);
124    range = lsquic_trechist_next(&iter);
125    assert(!range);
126    test_clone(hist_mask, hist_elems);
127
128    lsquic_trechist_insert(&hist_mask, hist_elems, 11912);
129
130    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
131    range = lsquic_trechist_first(&iter);
132    assert(range);
133    assert(range->high == 11996);
134    assert(range->low == 11946);
135    range = lsquic_trechist_next(&iter);
136    assert(range);
137    assert(range->high == 11941);
138    assert(range->low == 11917);
139    range = lsquic_trechist_next(&iter);
140    assert(range);
141    assert(range->high == 11912);
142    assert(range->low == 11912);
143    range = lsquic_trechist_next(&iter);
144    assert(!range);
145
146    for (packno = 12169; packno <= 12193; ++packno)
147        lsquic_trechist_insert(&hist_mask, hist_elems, packno);
148
149    test_clone(hist_mask, hist_elems);
150
151    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
152    range = lsquic_trechist_first(&iter);
153    assert(range);
154    assert(range->high == 12193);
155    assert(range->low == 12169);
156    range = lsquic_trechist_next(&iter);
157    assert(range);
158    assert(range->high == 11996);
159    assert(range->low == 11946);
160    range = lsquic_trechist_next(&iter);
161    assert(range);
162    assert(range->high == 11941);
163    assert(range->low == 11917);
164    range = lsquic_trechist_next(&iter);
165    assert(range);
166    assert(range->high == 11912);
167    assert(range->low == 11912);
168    range = lsquic_trechist_next(&iter);
169    assert(!range);
170
171    test_clone(hist_mask, hist_elems);
172
173    free(hist_elems);
174}
175
176
177static void
178rechist2str (trechist_mask_t hist_mask, const struct trechist_elem *hist_elems,
179                                                        char *buf, size_t bufsz)
180{
181    const struct lsquic_packno_range *range;
182    struct trechist_iter iter;
183    size_t off;
184    int n;
185
186    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
187    for (off = 0, range = lsquic_trechist_first(&iter);
188            range && off < bufsz;
189                off += n, range = lsquic_trechist_next(&iter))
190    {
191        n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
192                                                    range->high, range->low);
193        if (n < 0 || (size_t) n >= bufsz - off)
194            break;
195    }
196}
197
198
199static void
200test5 (void)
201{
202    trechist_mask_t       hist_mask;
203    struct trechist_elem *hist_elems;
204    char buf[100];
205
206    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
207    hist_mask = 0;
208
209    lsquic_trechist_insert(&hist_mask, hist_elems, 1);
210    /* Packet 2 omitted because it could not be decrypted */
211    lsquic_trechist_insert(&hist_mask, hist_elems, 3);
212    lsquic_trechist_insert(&hist_mask, hist_elems, 12);
213
214    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
215    assert(0 == strcmp(buf, "[12-12][3-3][1-1]"));
216
217    lsquic_trechist_insert(&hist_mask, hist_elems, 4);
218    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
219    assert(0 == strcmp(buf, "[12-12][4-3][1-1]"));
220
221    lsquic_trechist_insert(&hist_mask, hist_elems, 10);
222    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
223    assert(0 == strcmp(buf, "[12-12][10-10][4-3][1-1]"));
224
225    lsquic_trechist_insert(&hist_mask, hist_elems, 6);
226
227    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
228    assert(0 == strcmp(buf, "[12-12][10-10][6-6][4-3][1-1]"));
229
230    lsquic_trechist_insert(&hist_mask, hist_elems, 7);
231    lsquic_trechist_insert(&hist_mask, hist_elems, 8);
232
233    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
234    assert(0 == strcmp(buf, "[12-12][10-10][8-6][4-3][1-1]"));
235    test_clone(hist_mask, hist_elems);
236    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 0)));
237    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 9)));
238    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 20)));
239    assert(lsquic_trechist_contains(hist_mask, hist_elems, 4));
240    assert(lsquic_trechist_contains(hist_mask, hist_elems, 1));
241    assert(lsquic_trechist_contains(hist_mask, hist_elems, 7));
242    assert(lsquic_trechist_contains(hist_mask, hist_elems, 8));
243    assert(lsquic_trechist_contains(hist_mask, hist_elems, 6));
244
245    lsquic_trechist_insert(&hist_mask, hist_elems, 9);
246
247    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
248    assert(0 == strcmp(buf, "[12-12][10-6][4-3][1-1]"));
249    test_clone(hist_mask, hist_elems);
250
251    lsquic_trechist_insert(&hist_mask, hist_elems, 5);
252    lsquic_trechist_insert(&hist_mask, hist_elems, 11);
253
254    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
255    assert(0 == strcmp(buf, "[12-3][1-1]"));
256
257    free(hist_elems);
258}
259
260
261static void
262basic_test (void)
263{
264    trechist_mask_t       hist_mask;
265    struct trechist_elem *hist_elems;
266    const struct lsquic_packno_range *range;
267    struct trechist_iter iter;
268    unsigned i;
269    int s;
270
271    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
272    hist_mask = 0;
273
274    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
275    range = lsquic_trechist_first(&iter);
276    assert(!range);
277
278    s = lsquic_trechist_insert(&hist_mask, hist_elems, 1);
279    assert(("inserting packet number one is successful", 0 == s));
280
281    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
282    range = lsquic_trechist_first(&iter);
283    assert(("first range returned correctly", range));
284    assert(("first range low value checks out", range->low == 1));
285    assert(("first range high value checks out", range->high == 1));
286    range = lsquic_trechist_next(&iter);
287    assert(!range);
288    assert(("second range does not exist", !range));
289
290    for (i = 3; i <= 5; ++i)
291    {
292        s = lsquic_trechist_insert(&hist_mask, hist_elems, i);
293        assert(("inserting packet", s == 0));
294    }
295
296    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
297    range = lsquic_trechist_first(&iter);
298    assert(("first range returned correctly", range));
299    assert(("first range low value checks out", range->low == 3));
300    assert(("first range high value checks out", range->high == 5));
301    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 7)));
302    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 2)));
303    assert(lsquic_trechist_contains(hist_mask, hist_elems, 4));
304    range = lsquic_trechist_next(&iter);
305    assert(("second range returned correctly", range));
306    assert(("second range low value checks out", range->low == 1));
307    assert(("second range high value checks out", range->high == 1));
308    range = lsquic_trechist_next(&iter);
309    assert(("third range does not exist", !range));
310
311    assert(5 == lsquic_trechist_max(hist_mask, hist_elems));
312
313    s = lsquic_trechist_insert(&hist_mask, hist_elems, 10);
314    assert(("inserting packet", s == 0));
315
316    assert(10 == lsquic_trechist_max(hist_mask, hist_elems));
317
318    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
319    range = lsquic_trechist_first(&iter);
320    assert(("first range returned correctly", range));
321    assert(("first range low value checks out", range->low == 10));
322    assert(("first range high value checks out", range->high == 10));
323    test_clone(hist_mask, hist_elems);
324
325    s = lsquic_trechist_insert(&hist_mask, hist_elems, 8);
326    assert(("inserting packet", s == 0));
327    s = lsquic_trechist_insert(&hist_mask, hist_elems, 9);
328    assert(("inserting packet", s == 0));
329
330    /* Check merge */
331    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
332    range = lsquic_trechist_first(&iter);
333    assert(("first range returned correctly", range));
334    assert(("first range low value checks out", range->low == 8));
335    assert(("first range high value checks out", range->high == 10));
336
337    free(hist_elems);
338}
339
340
341static void
342test_limits (void)
343{
344    trechist_mask_t       hist_mask;
345    struct trechist_elem *hist_elems;
346    unsigned i;
347    int s;
348
349    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
350    hist_mask = 0;
351
352    for (i = 1; i <= UCHAR_MAX; ++i)
353    {
354        s = lsquic_trechist_insert(&hist_mask, hist_elems, i);
355        assert(s == 0);
356    }
357
358    s = lsquic_trechist_insert(&hist_mask, hist_elems, i);
359    assert(s == -1);    /* Overflow */
360
361    /* Always successful inserting new entries: */
362    for (i = 0; i < TRECHIST_MAX_RANGES * 2; ++i)
363    {
364        s = lsquic_trechist_insert(&hist_mask, hist_elems, 1000 + 2 * i);
365        assert(s == 0);
366    }
367
368    /* Always successful inserting new entries in descending order, too: */
369    for (i = 0; i < TRECHIST_MAX_RANGES * 2; ++i)
370    {
371        s = lsquic_trechist_insert(&hist_mask, hist_elems, 10000 - 2 * i);
372        assert(s == 0);
373    }
374
375    /* Test merge where count exceeds max: */
376    hist_mask = 0;
377    lsquic_trechist_copy_ranges(&hist_mask, hist_elems,
378        & (struct str_range_iter) { .str = "[400-202][200-1]", },
379        next_str_range, next_str_range);
380    s = lsquic_trechist_insert(&hist_mask, hist_elems, 201);
381    assert(s == -1);
382
383    free(hist_elems);
384}
385
386
387static void
388test_overflow (void)
389{
390    trechist_mask_t       mask;
391    struct trechist_elem *elems;
392    int s;
393    char buf[0x1000];
394
395    struct str_range_iter str_iter = { .str =
396        "[395-390]"     /* 1 */
397        "[385-380]"
398        "[375-370]"
399        "[365-360]"
400        "[355-350]"     /* 5 */
401        "[345-340]"
402        "[335-330]"
403        "[325-320]"
404        "[315-310]"
405        "[305-300]"     /* 10 */
406        "[295-290]"
407        "[285-280]"
408        "[275-270]"
409        "[265-260]"
410        "[255-250]"     /* 15 */
411        "[245-240]"     /* 16 */
412        "[235-230]"     /* Overflow vvvvvv */
413        "[225-220]"
414        "[215-210]"
415        "[205-200]"
416        "[195-190]"
417        "[185-180]" };
418
419    elems = malloc(sizeof(elems[0]) * TRECHIST_MAX_RANGES);
420    lsquic_trechist_copy_ranges(&mask, elems, &str_iter, next_str_range,
421                                                         next_str_range);
422
423    rechist2str(mask, elems, buf, sizeof(buf));
424    assert(0 == strcmp(buf,
425        "[395-390]"     /* 1 */
426        "[385-380]"
427        "[375-370]"
428        "[365-360]"
429        "[355-350]"     /* 5 */
430        "[345-340]"
431        "[335-330]"
432        "[325-320]"
433        "[315-310]"
434        "[305-300]"     /* 10 */
435        "[295-290]"
436        "[285-280]"
437        "[275-270]"
438        "[265-260]"
439        "[255-250]"     /* 15 */
440        "[245-240]"     /* 16 */));
441
442    s = lsquic_trechist_insert(&mask, elems, 400);
443    assert(s == 0);
444    rechist2str(mask, elems, buf, sizeof(buf));
445    assert(0 == strcmp(buf,
446        "[400-400]"
447        "[395-390]"
448        "[385-380]"
449        "[375-370]"
450        "[365-360]"
451        "[355-350]"
452        "[345-340]"
453        "[335-330]"
454        "[325-320]"
455        "[315-310]"
456        "[305-300]"
457        "[295-290]"
458        "[285-280]"
459        "[275-270]"
460        "[265-260]"
461        "[255-250]"
462    ));
463
464    /* One more for a good measure */
465    s = lsquic_trechist_insert(&mask, elems, 402);
466    assert(s == 0);
467    rechist2str(mask, elems, buf, sizeof(buf));
468    assert(0 == strcmp(buf,
469        "[402-402]"
470        "[400-400]"
471        "[395-390]"
472        "[385-380]"
473        "[375-370]"
474        "[365-360]"
475        "[355-350]"
476        "[345-340]"
477        "[335-330]"
478        "[325-320]"
479        "[315-310]"
480        "[305-300]"
481        "[295-290]"
482        "[285-280]"
483        "[275-270]"
484        "[265-260]"
485    ));
486
487    s = lsquic_trechist_insert(&mask, elems, 401);
488    assert(s == 0);
489    s = lsquic_trechist_insert(&mask, elems, 500);
490    assert(s == 0);
491    s = lsquic_trechist_insert(&mask, elems, 200);
492    assert(s == 0);
493    s = lsquic_trechist_insert(&mask, elems, 267);
494    assert(s == 0);
495
496    /* One more for a good measure */
497    s = lsquic_trechist_insert(&mask, elems, 402);
498    assert(s == 0);
499    rechist2str(mask, elems, buf, sizeof(buf));
500    assert(0 == strcmp(buf,
501        "[500-500]"
502        "[402-400]"
503        "[395-390]"
504        "[385-380]"
505        "[375-370]"
506        "[365-360]"
507        "[355-350]"
508        "[345-340]"
509        "[335-330]"
510        "[325-320]"
511        "[315-310]"
512        "[305-300]"
513        "[295-290]"
514        "[285-280]"
515        "[275-270]"
516        "[267-267]"
517    ));
518
519    free(elems);
520}
521
522
523int
524main (void)
525{
526    basic_test();
527    test4();
528    test5();
529    test_limits();
530    test_overflow();
531
532    return 0;
533}
534