test_rechist.c revision 1a0003e3 
1/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <inttypes.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7
8#ifdef WIN32
9#include "vc_compat.h"
10#endif
11
12#include "lsquic_int_types.h"
13#include "lsquic_rechist.h"
14#include "lsquic_util.h"
15
16
17static void
18test4 (void)
19{
20    lsquic_rechist_t rechist;
21    const struct lsquic_packno_range *range;
22    lsquic_packno_t packno;
23
24    lsquic_rechist_init(&rechist, 0, 0);
25
26    for (packno = 11917; packno <= 11941; ++packno)
27        lsquic_rechist_received(&rechist, packno, 0);
28    for (packno = 11946; packno <= 11994; ++packno)
29        lsquic_rechist_received(&rechist, packno, 0);
30
31    range = lsquic_rechist_first(&rechist);
32    assert(range);
33    assert(range->high == 11994);
34    assert(range->low == 11946);
35    range = lsquic_rechist_next(&rechist);
36    assert(range);
37    assert(range->high == 11941);
38    assert(range->low == 11917);
39    range = lsquic_rechist_next(&rechist);
40    assert(!range);
41
42    lsquic_rechist_received(&rechist, 11995, 0);
43    lsquic_rechist_received(&rechist, 11996, 0);
44
45    range = lsquic_rechist_first(&rechist);
46    assert(range);
47    assert(range->high == 11996);
48    assert(range->low == 11946);
49    range = lsquic_rechist_next(&rechist);
50    assert(range);
51    assert(range->high == 11941);
52    assert(range->low == 11917);
53    range = lsquic_rechist_next(&rechist);
54    assert(!range);
55
56    lsquic_rechist_received(&rechist, 11912, 0);
57    lsquic_rechist_stop_wait(&rechist, 11860);
58
59    range = lsquic_rechist_first(&rechist);
60    assert(range);
61    assert(range->high == 11996);
62    assert(range->low == 11946);
63    range = lsquic_rechist_next(&rechist);
64    assert(range);
65    assert(range->high == 11941);
66    assert(range->low == 11917);
67    range = lsquic_rechist_next(&rechist);
68    assert(range);
69    assert(range->high == 11912);
70    assert(range->low == 11912);
71    range = lsquic_rechist_next(&rechist);
72    assert(!range);
73
74    for (packno = 12169; packno <= 12193; ++packno)
75        lsquic_rechist_received(&rechist, packno, 0);
76
77    range = lsquic_rechist_first(&rechist);
78    assert(range);
79    assert(range->high == 12193);
80    assert(range->low == 12169);
81    range = lsquic_rechist_next(&rechist);
82    assert(range);
83    assert(range->high == 11996);
84    assert(range->low == 11946);
85    range = lsquic_rechist_next(&rechist);
86    assert(range);
87    assert(range->high == 11941);
88    assert(range->low == 11917);
89    range = lsquic_rechist_next(&rechist);
90    assert(range);
91    assert(range->high == 11912);
92    assert(range->low == 11912);
93    range = lsquic_rechist_next(&rechist);
94    assert(!range);
95
96    lsquic_rechist_cleanup(&rechist);
97}
98
99
100static void
101rechist2str (lsquic_rechist_t *rechist, char *buf, size_t bufsz)
102{
103    const struct lsquic_packno_range *range;
104    size_t off;
105    int n;
106
107    for (off = 0, range = lsquic_rechist_first(rechist);
108            range && off < bufsz;
109                off += n, range = lsquic_rechist_next(rechist))
110    {
111        n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
112                                                    range->high, range->low);
113        if (n < 0 || (size_t) n >= bufsz - off)
114            break;
115    }
116}
117
118
119static void
120test_range_copy (struct lsquic_rechist *orig, int ietf)
121{
122    char orig_str[0x1000], new_str[0x1000];
123    struct lsquic_rechist new;
124
125    rechist2str(orig, orig_str, sizeof(orig_str));
126
127    lsquic_rechist_init(&new, ietf, 0);
128    lsquic_rechist_copy_ranges(&new, orig,
129        (const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_first,
130        (const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_next);
131    rechist2str(&new, new_str, sizeof(new_str));
132    assert(0 == strcmp(orig_str, new_str));
133}
134
135
136static void
137test5 (void)
138{
139    lsquic_rechist_t rechist;
140    char buf[100];
141
142    lsquic_rechist_init(&rechist, 0, 0);
143
144    lsquic_rechist_received(&rechist, 1, 0);
145    /* Packet 2 omitted because it could not be decrypted */
146    lsquic_rechist_received(&rechist, 3, 0);
147    lsquic_rechist_received(&rechist, 12, 0);
148
149    rechist2str(&rechist, buf, sizeof(buf));
150    assert(0 == strcmp(buf, "[12-12][3-3][1-1]"));
151
152    lsquic_rechist_received(&rechist, 4, 0);
153    lsquic_rechist_received(&rechist, 10, 0);
154
155    rechist2str(&rechist, buf, sizeof(buf));
156    assert(0 == strcmp(buf, "[12-12][10-10][4-3][1-1]"));
157
158    lsquic_rechist_received(&rechist, 6, 0);
159
160    rechist2str(&rechist, buf, sizeof(buf));
161    assert(0 == strcmp(buf, "[12-12][10-10][6-6][4-3][1-1]"));
162
163    lsquic_rechist_received(&rechist, 7, 0);
164    lsquic_rechist_received(&rechist, 8, 0);
165
166    rechist2str(&rechist, buf, sizeof(buf));
167    assert(0 == strcmp(buf, "[12-12][10-10][8-6][4-3][1-1]"));
168
169    lsquic_rechist_received(&rechist, 9, 0);
170    test_range_copy(&rechist, 0);
171
172    rechist2str(&rechist, buf, sizeof(buf));
173    assert(0 == strcmp(buf, "[12-12][10-6][4-3][1-1]"));
174
175    lsquic_rechist_received(&rechist, 5, 0);
176    lsquic_rechist_received(&rechist, 11, 0);
177
178    rechist2str(&rechist, buf, sizeof(buf));
179    assert(0 == strcmp(buf, "[12-3][1-1]"));
180
181    lsquic_rechist_cleanup(&rechist);
182}
183
184
185static void
186test_rand_sequence (unsigned seed, unsigned max)
187{
188    struct lsquic_rechist rechist;
189    const struct lsquic_packno_range *range;
190    lsquic_packno_t prev_low;
191    enum received_st st;
192    unsigned i, count;
193
194    lsquic_rechist_init(&rechist, 1, max);
195    srand(seed);
196
197    for (i = 0; i < 10000; ++i)
198    {
199        st = lsquic_rechist_received(&rechist, (unsigned) rand(), 0);
200        assert(st == REC_ST_OK || st == REC_ST_DUP);
201    }
202
203    test_range_copy(&rechist, 1);
204
205    range = lsquic_rechist_first(&rechist);
206    assert(range);
207    assert(range->high >= range->low);
208    prev_low = range->low;
209    count = 1;
210
211    while (range = lsquic_rechist_next(&rechist), range != NULL)
212    {
213        ++count;
214        assert(range->high >= range->low);
215        assert(range->high < prev_low);
216        prev_low = range->low;
217    }
218    if (max)
219        assert(count <= max);
220
221    lsquic_rechist_cleanup(&rechist);
222}
223
224
225struct shuffle_elem {
226    unsigned    packno;
227    int         rand;
228};
229
230
231static int
232comp_els (const void *a_p, const void *b_p)
233{
234    const struct shuffle_elem *a = a_p, *b = b_p;
235    if (a->rand < b->rand)
236        return -1;
237    if (a->rand > b->rand)
238        return 1;
239    return (a->packno > b->packno) - (b->packno > a->packno);
240}
241
242
243static void
244test_shuffle_1000 (unsigned seed)
245{
246    struct lsquic_rechist rechist;
247    const struct lsquic_packno_range *range;
248    enum received_st st;
249    unsigned i;
250    struct shuffle_elem *els;
251
252    els = malloc(sizeof(els[0]) * 10000);
253    lsquic_rechist_init(&rechist, 1, 0);
254    srand(seed);
255
256    for (i = 0; i < 10000; ++i)
257    {
258        els[i].packno = i;
259        els[i].rand   = rand();
260    }
261
262    qsort(els, 10000, sizeof(els[0]), comp_els);
263
264    for (i = 0; i < 10000; ++i)
265    {
266        st = lsquic_rechist_received(&rechist, els[i].packno, 0);
267        assert(st == REC_ST_OK || st == REC_ST_DUP);
268    }
269    test_range_copy(&rechist, 1);
270
271    range = lsquic_rechist_first(&rechist);
272    assert(range);
273    assert(range->high == 9999);
274    assert(range->low == 0);
275    range = lsquic_rechist_next(&rechist);
276    assert(!range);
277
278    lsquic_rechist_cleanup(&rechist);
279    free(els);
280}
281
282
283int
284main (void)
285{
286    enum received_st st;
287    lsquic_rechist_t rechist;
288    unsigned i;
289    const struct lsquic_packno_range *range;
290
291    lsquic_rechist_init(&rechist, 0, 0);
292
293    lsquic_time_t now = 1234;
294    st = lsquic_rechist_received(&rechist, 0, now);
295    assert(("inserting packet number zero results in error", st == REC_ST_ERR));
296
297    st = lsquic_rechist_received(&rechist, 1, now);
298    assert(("inserting packet number one is successful", st == REC_ST_OK));
299
300    st = lsquic_rechist_received(&rechist, 1, now);
301    assert(("inserting packet number one again results in duplicate error",
302                                                            st == REC_ST_DUP));
303
304    range = lsquic_rechist_first(&rechist);
305    assert(("first range returned correctly", range));
306    assert(("first range low value checks out", range->low == 1));
307    assert(("first range high value checks out", range->high == 1));
308    range = lsquic_rechist_next(&rechist);
309    assert(("second range does not exist", !range));
310
311    for (i = 3; i <= 5; ++i)
312    {
313        st = lsquic_rechist_received(&rechist, i, now);
314        assert(("inserting packet", st == REC_ST_OK));
315    }
316
317    range = lsquic_rechist_first(&rechist);
318    assert(("first range returned correctly", range));
319    assert(("first range low value checks out", range->low == 3));
320    assert(("first range high value checks out", range->high == 5));
321    range = lsquic_rechist_next(&rechist);
322    assert(("second range returned correctly", range));
323    assert(("second range low value checks out", range->low == 1));
324    assert(("second range high value checks out", range->high == 1));
325    range = lsquic_rechist_next(&rechist);
326    assert(("third range does not exist", !range));
327
328    lsquic_rechist_stop_wait(&rechist, 3);
329
330    st = lsquic_rechist_received(&rechist, 1, now);
331    assert(("inserting packet number one is unsuccessful after cutoff 3",
332                                                            st == REC_ST_DUP));
333
334    range = lsquic_rechist_first(&rechist);
335    assert(("first range returned correctly", range));
336    assert(("first range low value checks out", range->low == 3));
337    assert(("first range high value checks out", range->high == 5));
338    range = lsquic_rechist_next(&rechist);
339    assert(("second range does not exist", !range));
340
341    for (i = 9; i >= 7; --i)
342    {
343        st = lsquic_rechist_received(&rechist, i, now);
344        assert(("inserting packet", st == REC_ST_OK));
345    }
346
347    range = lsquic_rechist_first(&rechist);
348    assert(("first range returned correctly", range));
349    assert(("first range low value checks out", range->low == 7));
350    assert(("first range high value checks out", range->high == 9));
351    range = lsquic_rechist_next(&rechist);
352    assert(("second range returned correctly", range));
353    assert(("second range low value checks out", range->low == 3));
354    assert(("second range high value checks out", range->high == 5));
355    range = lsquic_rechist_next(&rechist);
356    assert(("third range does not exist", !range));
357
358    lsquic_rechist_stop_wait(&rechist, 5);
359
360    range = lsquic_rechist_first(&rechist);
361    range = lsquic_rechist_next(&rechist);
362    assert(("second range returned correctly", range));
363    assert(("second range low value checks out", range->low == 5));
364    assert(("second range high value checks out", range->high == 5));
365    range = lsquic_rechist_next(&rechist);
366    assert(("third range does not exist", !range));
367
368    lsquic_rechist_stop_wait(&rechist, 8);
369
370    range = lsquic_rechist_first(&rechist);
371    assert(("first range returned correctly", range));
372    assert(("first range low value checks out", range->low == 8));
373    assert(("first range high value checks out", range->high == 9));
374    range = lsquic_rechist_next(&rechist);
375    assert(("second range does not exist", !range));
376
377    lsquic_rechist_cleanup(&rechist);
378
379    test4();
380
381    test5();
382
383    for (i = 0; i < 10; ++i)
384        test_rand_sequence(i, 0);
385
386    for (i = 0; i < 10; ++i)
387        test_rand_sequence(i, 111 + i * 3 /* Just something arbitrary */);
388
389    for (i = 0; i < 10; ++i)
390        test_shuffle_1000(i);
391
392    return 0;
393}
394