1/* Copyright (c) 2017 - 2022 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    size_t len;
125
126    rechist2str(orig, orig_str, sizeof(orig_str));
127
128    lsquic_rechist_init(&new, ietf, 0);
129    lsquic_rechist_copy_ranges(&new, orig,
130        (const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_first,
131        (const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_next);
132    rechist2str(&new, new_str, sizeof(new_str));
133    assert(0 == strcmp(orig_str, new_str));
134    lsquic_rechist_cleanup(&new);
135
136    /* This tests that lower-numbered ranges do not overwrite higher-numbered
137     * ranges.
138     */
139    lsquic_rechist_init(&new, ietf, 10);
140    lsquic_rechist_copy_ranges(&new, orig,
141        (const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_first,
142        (const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_next);
143    rechist2str(&new, new_str, sizeof(new_str));
144    len = strlen(new_str);
145    assert(0 == strncmp(orig_str, new_str, len));
146    lsquic_rechist_cleanup(&new);
147}
148
149
150static void
151test5 (void)
152{
153    lsquic_rechist_t rechist;
154    char buf[100];
155
156    lsquic_rechist_init(&rechist, 0, 0);
157
158    lsquic_rechist_received(&rechist, 1, 0);
159    /* Packet 2 omitted because it could not be decrypted */
160    lsquic_rechist_received(&rechist, 3, 0);
161    lsquic_rechist_received(&rechist, 12, 0);
162
163    rechist2str(&rechist, buf, sizeof(buf));
164    assert(0 == strcmp(buf, "[12-12][3-3][1-1]"));
165
166    lsquic_rechist_received(&rechist, 4, 0);
167    lsquic_rechist_received(&rechist, 10, 0);
168
169    rechist2str(&rechist, buf, sizeof(buf));
170    assert(0 == strcmp(buf, "[12-12][10-10][4-3][1-1]"));
171
172    lsquic_rechist_received(&rechist, 6, 0);
173
174    rechist2str(&rechist, buf, sizeof(buf));
175    assert(0 == strcmp(buf, "[12-12][10-10][6-6][4-3][1-1]"));
176
177    lsquic_rechist_received(&rechist, 7, 0);
178    lsquic_rechist_received(&rechist, 8, 0);
179
180    rechist2str(&rechist, buf, sizeof(buf));
181    assert(0 == strcmp(buf, "[12-12][10-10][8-6][4-3][1-1]"));
182
183    lsquic_rechist_received(&rechist, 9, 0);
184    test_range_copy(&rechist, 0);
185
186    rechist2str(&rechist, buf, sizeof(buf));
187    assert(0 == strcmp(buf, "[12-12][10-6][4-3][1-1]"));
188
189    lsquic_rechist_received(&rechist, 5, 0);
190    lsquic_rechist_received(&rechist, 11, 0);
191
192    rechist2str(&rechist, buf, sizeof(buf));
193    assert(0 == strcmp(buf, "[12-3][1-1]"));
194
195    lsquic_rechist_cleanup(&rechist);
196}
197
198
199static void
200test_rand_sequence (unsigned seed, unsigned max)
201{
202    struct lsquic_rechist rechist;
203    const struct lsquic_packno_range *range;
204    lsquic_packno_t prev_low;
205    enum received_st st;
206    unsigned i, count;
207
208    lsquic_rechist_init(&rechist, 1, max);
209    srand(seed);
210
211    for (i = 0; i < 10000; ++i)
212    {
213        st = lsquic_rechist_received(&rechist, (unsigned) rand(), 0);
214        assert(st == REC_ST_OK || st == REC_ST_DUP);
215    }
216
217    test_range_copy(&rechist, 1);
218
219    range = lsquic_rechist_first(&rechist);
220    assert(range);
221    assert(range->high >= range->low);
222    prev_low = range->low;
223    count = 1;
224
225    while (range = lsquic_rechist_next(&rechist), range != NULL)
226    {
227        ++count;
228        assert(range->high >= range->low);
229        assert(range->high < prev_low);
230        prev_low = range->low;
231    }
232    if (max)
233        assert(count <= max);
234
235    lsquic_rechist_cleanup(&rechist);
236}
237
238
239struct shuffle_elem {
240    unsigned    packno;
241    int         rand;
242};
243
244
245static int
246comp_els (const void *a_p, const void *b_p)
247{
248    const struct shuffle_elem *a = a_p, *b = b_p;
249    if (a->rand < b->rand)
250        return -1;
251    if (a->rand > b->rand)
252        return 1;
253    return (a->packno > b->packno) - (b->packno > a->packno);
254}
255
256
257static void
258test_shuffle_1000 (unsigned seed)
259{
260    struct lsquic_rechist rechist;
261    const struct lsquic_packno_range *range;
262    enum received_st st;
263    unsigned i;
264    struct shuffle_elem *els;
265
266    els = malloc(sizeof(els[0]) * 10000);
267    lsquic_rechist_init(&rechist, 1, 0);
268    srand(seed);
269
270    for (i = 0; i < 10000; ++i)
271    {
272        els[i].packno = i;
273        els[i].rand   = rand();
274    }
275
276    qsort(els, 10000, sizeof(els[0]), comp_els);
277
278    for (i = 0; i < 10000; ++i)
279    {
280        st = lsquic_rechist_received(&rechist, els[i].packno, 0);
281        assert(st == REC_ST_OK || st == REC_ST_DUP);
282    }
283    test_range_copy(&rechist, 1);
284
285    range = lsquic_rechist_first(&rechist);
286    assert(range);
287    assert(range->high == 9999);
288    assert(range->low == 0);
289    range = lsquic_rechist_next(&rechist);
290    assert(!range);
291
292    lsquic_rechist_cleanup(&rechist);
293    free(els);
294}
295
296
297int
298main (void)
299{
300    enum received_st st;
301    lsquic_rechist_t rechist;
302    unsigned i;
303    const struct lsquic_packno_range *range;
304
305    lsquic_rechist_init(&rechist, 0, 0);
306
307    lsquic_time_t now = 1234;
308    st = lsquic_rechist_received(&rechist, 0, now);
309    assert(("inserting packet number zero results in error", st == REC_ST_ERR));
310
311    st = lsquic_rechist_received(&rechist, 1, now);
312    assert(("inserting packet number one is successful", st == REC_ST_OK));
313
314    st = lsquic_rechist_received(&rechist, 1, now);
315    assert(("inserting packet number one again results in duplicate error",
316                                                            st == REC_ST_DUP));
317
318    range = lsquic_rechist_first(&rechist);
319    assert(("first range returned correctly", range));
320    assert(("first range low value checks out", range->low == 1));
321    assert(("first range high value checks out", range->high == 1));
322    range = lsquic_rechist_next(&rechist);
323    assert(("second range does not exist", !range));
324
325    for (i = 3; i <= 5; ++i)
326    {
327        st = lsquic_rechist_received(&rechist, i, now);
328        assert(("inserting packet", st == REC_ST_OK));
329    }
330
331    range = lsquic_rechist_first(&rechist);
332    assert(("first range returned correctly", range));
333    assert(("first range low value checks out", range->low == 3));
334    assert(("first range high value checks out", range->high == 5));
335    range = lsquic_rechist_next(&rechist);
336    assert(("second range returned correctly", range));
337    assert(("second range low value checks out", range->low == 1));
338    assert(("second range high value checks out", range->high == 1));
339    range = lsquic_rechist_next(&rechist);
340    assert(("third range does not exist", !range));
341
342    lsquic_rechist_stop_wait(&rechist, 3);
343
344    st = lsquic_rechist_received(&rechist, 1, now);
345    assert(("inserting packet number one is unsuccessful after cutoff 3",
346                                                            st == REC_ST_DUP));
347
348    range = lsquic_rechist_first(&rechist);
349    assert(("first range returned correctly", range));
350    assert(("first range low value checks out", range->low == 3));
351    assert(("first range high value checks out", range->high == 5));
352    range = lsquic_rechist_next(&rechist);
353    assert(("second range does not exist", !range));
354
355    for (i = 9; i >= 7; --i)
356    {
357        st = lsquic_rechist_received(&rechist, i, now);
358        assert(("inserting packet", st == REC_ST_OK));
359    }
360
361    range = lsquic_rechist_first(&rechist);
362    assert(("first range returned correctly", range));
363    assert(("first range low value checks out", range->low == 7));
364    assert(("first range high value checks out", range->high == 9));
365    range = lsquic_rechist_next(&rechist);
366    assert(("second range returned correctly", range));
367    assert(("second range low value checks out", range->low == 3));
368    assert(("second range high value checks out", range->high == 5));
369    range = lsquic_rechist_next(&rechist);
370    assert(("third range does not exist", !range));
371
372    lsquic_rechist_stop_wait(&rechist, 5);
373
374    range = lsquic_rechist_first(&rechist);
375    range = lsquic_rechist_next(&rechist);
376    assert(("second range returned correctly", range));
377    assert(("second range low value checks out", range->low == 5));
378    assert(("second range high value checks out", range->high == 5));
379    range = lsquic_rechist_next(&rechist);
380    assert(("third range does not exist", !range));
381
382    lsquic_rechist_stop_wait(&rechist, 8);
383
384    range = lsquic_rechist_first(&rechist);
385    assert(("first range returned correctly", range));
386    assert(("first range low value checks out", range->low == 8));
387    assert(("first range high value checks out", range->high == 9));
388    range = lsquic_rechist_next(&rechist);
389    assert(("second range does not exist", !range));
390
391    lsquic_rechist_cleanup(&rechist);
392
393    test4();
394
395    test5();
396
397    for (i = 0; i < 10; ++i)
398        test_rand_sequence(i, 0);
399
400    for (i = 0; i < 10; ++i)
401        test_rand_sequence(i, 111 + i * 3 /* Just something arbitrary */);
402
403    for (i = 0; i < 10; ++i)
404        test_shuffle_1000(i);
405
406    return 0;
407}
408