test_rechist.c revision b62ec17f 
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);
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);
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)
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;
175
176    lsquic_rechist_init(&rechist, 1);
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
190    while (range = lsquic_rechist_next(&rechist), range != NULL)
191    {
192        assert(range->high >= range->low);
193        assert(range->high < prev_low);
194        prev_low = range->low;
195    }
196
197    lsquic_rechist_cleanup(&rechist);
198}
199
200
201struct shuffle_elem {
202    unsigned    packno;
203    int         rand;
204};
205
206
207static int
208comp_els (const void *a_p, const void *b_p)
209{
210    const struct shuffle_elem *a = a_p, *b = b_p;
211    if (a->rand < b->rand)
212        return -1;
213    if (a->rand > b->rand)
214        return 1;
215    return (a->packno > b->packno) - (b->packno > a->packno);
216}
217
218
219static void
220test_shuffle_1000 (unsigned seed)
221{
222    struct lsquic_rechist rechist;
223    const struct lsquic_packno_range *range;
224    enum received_st st;
225    unsigned i;
226    struct shuffle_elem *els;
227
228    els = malloc(sizeof(els[0]) * 10000);
229    lsquic_rechist_init(&rechist, 1);
230    srand(seed);
231
232    for (i = 0; i < 10000; ++i)
233    {
234        els[i].packno = i;
235        els[i].rand   = rand();
236    }
237
238    qsort(els, 10000, sizeof(els[0]), comp_els);
239
240    for (i = 0; i < 10000; ++i)
241    {
242        st = lsquic_rechist_received(&rechist, els[i].packno, 0);
243        assert(st == REC_ST_OK || st == REC_ST_DUP);
244    }
245
246    range = lsquic_rechist_first(&rechist);
247    assert(range);
248    assert(range->high == 9999);
249    assert(range->low == 0);
250    range = lsquic_rechist_next(&rechist);
251    assert(!range);
252
253    lsquic_rechist_cleanup(&rechist);
254    free(els);
255}
256
257
258int
259main (void)
260{
261    enum received_st st;
262    lsquic_rechist_t rechist;
263    unsigned i;
264    const struct lsquic_packno_range *range;
265
266    lsquic_rechist_init(&rechist, 0);
267
268    lsquic_time_t now = 1234;
269    st = lsquic_rechist_received(&rechist, 0, now);
270    assert(("inserting packet number zero results in error", st == REC_ST_ERR));
271
272    st = lsquic_rechist_received(&rechist, 1, now);
273    assert(("inserting packet number one is successful", st == REC_ST_OK));
274
275    st = lsquic_rechist_received(&rechist, 1, now);
276    assert(("inserting packet number one again results in duplicate error",
277                                                            st == REC_ST_DUP));
278
279    range = lsquic_rechist_first(&rechist);
280    assert(("first range returned correctly", range));
281    assert(("first range low value checks out", range->low == 1));
282    assert(("first range high value checks out", range->high == 1));
283    range = lsquic_rechist_next(&rechist);
284    assert(("second range does not exist", !range));
285
286    for (i = 3; i <= 5; ++i)
287    {
288        st = lsquic_rechist_received(&rechist, i, now);
289        assert(("inserting packet", st == REC_ST_OK));
290    }
291
292    range = lsquic_rechist_first(&rechist);
293    assert(("first range returned correctly", range));
294    assert(("first range low value checks out", range->low == 3));
295    assert(("first range high value checks out", range->high == 5));
296    range = lsquic_rechist_next(&rechist);
297    assert(("second range returned correctly", range));
298    assert(("second range low value checks out", range->low == 1));
299    assert(("second range high value checks out", range->high == 1));
300    range = lsquic_rechist_next(&rechist);
301    assert(("third range does not exist", !range));
302
303    lsquic_rechist_stop_wait(&rechist, 3);
304
305    st = lsquic_rechist_received(&rechist, 1, now);
306    assert(("inserting packet number one is unsuccessful after cutoff 3",
307                                                            st == REC_ST_DUP));
308
309    range = lsquic_rechist_first(&rechist);
310    assert(("first range returned correctly", range));
311    assert(("first range low value checks out", range->low == 3));
312    assert(("first range high value checks out", range->high == 5));
313    range = lsquic_rechist_next(&rechist);
314    assert(("second range does not exist", !range));
315
316    for (i = 9; i >= 7; --i)
317    {
318        st = lsquic_rechist_received(&rechist, i, now);
319        assert(("inserting packet", st == REC_ST_OK));
320    }
321
322    range = lsquic_rechist_first(&rechist);
323    assert(("first range returned correctly", range));
324    assert(("first range low value checks out", range->low == 7));
325    assert(("first range high value checks out", range->high == 9));
326    range = lsquic_rechist_next(&rechist);
327    assert(("second range returned correctly", range));
328    assert(("second range low value checks out", range->low == 3));
329    assert(("second range high value checks out", range->high == 5));
330    range = lsquic_rechist_next(&rechist);
331    assert(("third range does not exist", !range));
332
333    lsquic_rechist_stop_wait(&rechist, 5);
334
335    range = lsquic_rechist_first(&rechist);
336    range = lsquic_rechist_next(&rechist);
337    assert(("second range returned correctly", range));
338    assert(("second range low value checks out", range->low == 5));
339    assert(("second range high value checks out", range->high == 5));
340    range = lsquic_rechist_next(&rechist);
341    assert(("third range does not exist", !range));
342
343    lsquic_rechist_stop_wait(&rechist, 8);
344
345    range = lsquic_rechist_first(&rechist);
346    assert(("first range returned correctly", range));
347    assert(("first range low value checks out", range->low == 8));
348    assert(("first range high value checks out", range->high == 9));
349    range = lsquic_rechist_next(&rechist);
350    assert(("second range does not exist", !range));
351
352    lsquic_rechist_cleanup(&rechist);
353
354    test4();
355
356    test5();
357
358    for (i = 0; i < 10; ++i)
359        test_rand_sequence(i);
360
361    for (i = 0; i < 10; ++i)
362        test_shuffle_1000(i);
363
364    return 0;
365}
366