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