test_trechist.c revision fbc6cc04 
1/* Copyright (c) 2017 - 2020 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
19static void
20test_clone (trechist_mask_t src_mask, struct trechist_elem *src_elems)
21{
22    trechist_mask_t       hist_mask;
23    struct trechist_elem *hist_elems;
24    const struct lsquic_packno_range *ranges[2];
25    struct trechist_iter iters[2];
26    int s;
27
28    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
29
30    lsquic_trechist_iter(&iters[0], src_mask, src_elems);
31    s = lsquic_trechist_copy_ranges(&hist_mask, hist_elems, &iters[0],
32                        lsquic_trechist_first, lsquic_trechist_next);
33    assert(s == 0);
34
35    lsquic_trechist_iter(&iters[0], src_mask, src_elems);
36    lsquic_trechist_iter(&iters[1], hist_mask, hist_elems);
37
38    for (ranges[0] = lsquic_trechist_first(&iters[0]),
39         ranges[1] = lsquic_trechist_first(&iters[1]);
40
41         ranges[0] && ranges[1];
42
43         ranges[0] = lsquic_trechist_next(&iters[0]),
44         ranges[1] = lsquic_trechist_next(&iters[1]))
45    {
46        assert(ranges[0]->low == ranges[1]->low);
47        assert(ranges[0]->high == ranges[1]->high);
48    }
49
50    assert(!ranges[0] && !ranges[1]);
51
52    free(hist_elems);
53}
54
55
56static void
57test4 (void)
58{
59    trechist_mask_t       hist_mask;
60    struct trechist_elem *hist_elems;
61    const struct lsquic_packno_range *range;
62    struct trechist_iter iter;
63    lsquic_packno_t packno;
64
65    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
66    hist_mask = 0;
67    test_clone(hist_mask, hist_elems);
68
69    for (packno = 11917; packno <= 11941; ++packno)
70        lsquic_trechist_insert(&hist_mask, hist_elems, packno);
71    for (packno = 11946; packno <= 11994; ++packno)
72        lsquic_trechist_insert(&hist_mask, hist_elems, packno);
73
74    test_clone(hist_mask, hist_elems);
75    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
76    range = lsquic_trechist_first(&iter);
77    assert(range);
78    assert(range->high == 11994);
79    assert(range->low == 11946);
80    range = lsquic_trechist_next(&iter);
81    assert(range);
82    assert(range->high == 11941);
83    assert(range->low == 11917);
84    range = lsquic_trechist_next(&iter);
85    assert(!range);
86
87    lsquic_trechist_insert(&hist_mask, hist_elems, 11995);
88    lsquic_trechist_insert(&hist_mask, hist_elems, 11996);
89    test_clone(hist_mask, hist_elems);
90
91    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
92    range = lsquic_trechist_first(&iter);
93    assert(range);
94    assert(range->high == 11996);
95    assert(range->low == 11946);
96    range = lsquic_trechist_next(&iter);
97    assert(range);
98    assert(range->high == 11941);
99    assert(range->low == 11917);
100    range = lsquic_trechist_next(&iter);
101    assert(!range);
102    test_clone(hist_mask, hist_elems);
103
104    lsquic_trechist_insert(&hist_mask, hist_elems, 11912);
105
106    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
107    range = lsquic_trechist_first(&iter);
108    assert(range);
109    assert(range->high == 11996);
110    assert(range->low == 11946);
111    range = lsquic_trechist_next(&iter);
112    assert(range);
113    assert(range->high == 11941);
114    assert(range->low == 11917);
115    range = lsquic_trechist_next(&iter);
116    assert(range);
117    assert(range->high == 11912);
118    assert(range->low == 11912);
119    range = lsquic_trechist_next(&iter);
120    assert(!range);
121
122    for (packno = 12169; packno <= 12193; ++packno)
123        lsquic_trechist_insert(&hist_mask, hist_elems, packno);
124
125    test_clone(hist_mask, hist_elems);
126
127    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
128    range = lsquic_trechist_first(&iter);
129    assert(range);
130    assert(range->high == 12193);
131    assert(range->low == 12169);
132    range = lsquic_trechist_next(&iter);
133    assert(range);
134    assert(range->high == 11996);
135    assert(range->low == 11946);
136    range = lsquic_trechist_next(&iter);
137    assert(range);
138    assert(range->high == 11941);
139    assert(range->low == 11917);
140    range = lsquic_trechist_next(&iter);
141    assert(range);
142    assert(range->high == 11912);
143    assert(range->low == 11912);
144    range = lsquic_trechist_next(&iter);
145    assert(!range);
146
147    test_clone(hist_mask, hist_elems);
148
149    free(hist_elems);
150}
151
152
153static void
154rechist2str (trechist_mask_t hist_mask, const struct trechist_elem *hist_elems,
155                                                        char *buf, size_t bufsz)
156{
157    const struct lsquic_packno_range *range;
158    struct trechist_iter iter;
159    size_t off;
160    int n;
161
162    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
163    for (off = 0, range = lsquic_trechist_first(&iter);
164            range && off < bufsz;
165                off += n, range = lsquic_trechist_next(&iter))
166    {
167        n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
168                                                    range->high, range->low);
169        if (n < 0 || (size_t) n >= bufsz - off)
170            break;
171    }
172}
173
174
175static void
176test5 (void)
177{
178    trechist_mask_t       hist_mask;
179    struct trechist_elem *hist_elems;
180    char buf[100];
181
182    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
183    hist_mask = 0;
184
185    lsquic_trechist_insert(&hist_mask, hist_elems, 1);
186    /* Packet 2 omitted because it could not be decrypted */
187    lsquic_trechist_insert(&hist_mask, hist_elems, 3);
188    lsquic_trechist_insert(&hist_mask, hist_elems, 12);
189
190    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
191    assert(0 == strcmp(buf, "[12-12][3-3][1-1]"));
192
193    lsquic_trechist_insert(&hist_mask, hist_elems, 4);
194    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
195    assert(0 == strcmp(buf, "[12-12][4-3][1-1]"));
196
197    lsquic_trechist_insert(&hist_mask, hist_elems, 10);
198    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
199    assert(0 == strcmp(buf, "[12-12][10-10][4-3][1-1]"));
200
201    lsquic_trechist_insert(&hist_mask, hist_elems, 6);
202
203    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
204    assert(0 == strcmp(buf, "[12-12][10-10][6-6][4-3][1-1]"));
205
206    lsquic_trechist_insert(&hist_mask, hist_elems, 7);
207    lsquic_trechist_insert(&hist_mask, hist_elems, 8);
208
209    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
210    assert(0 == strcmp(buf, "[12-12][10-10][8-6][4-3][1-1]"));
211    test_clone(hist_mask, hist_elems);
212    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 0)));
213    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 9)));
214    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 20)));
215    assert(lsquic_trechist_contains(hist_mask, hist_elems, 4));
216    assert(lsquic_trechist_contains(hist_mask, hist_elems, 1));
217    assert(lsquic_trechist_contains(hist_mask, hist_elems, 7));
218    assert(lsquic_trechist_contains(hist_mask, hist_elems, 8));
219    assert(lsquic_trechist_contains(hist_mask, hist_elems, 6));
220
221    lsquic_trechist_insert(&hist_mask, hist_elems, 9);
222
223    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
224    assert(0 == strcmp(buf, "[12-12][10-6][4-3][1-1]"));
225    test_clone(hist_mask, hist_elems);
226
227    lsquic_trechist_insert(&hist_mask, hist_elems, 5);
228    lsquic_trechist_insert(&hist_mask, hist_elems, 11);
229
230    rechist2str(hist_mask, hist_elems, buf, sizeof(buf));
231    assert(0 == strcmp(buf, "[12-3][1-1]"));
232
233    free(hist_elems);
234}
235
236
237static void
238basic_test (void)
239{
240    trechist_mask_t       hist_mask;
241    struct trechist_elem *hist_elems;
242    const struct lsquic_packno_range *range;
243    struct trechist_iter iter;
244    unsigned i;
245    int s;
246
247    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
248    hist_mask = 0;
249
250    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
251    range = lsquic_trechist_first(&iter);
252    assert(!range);
253
254    s = lsquic_trechist_insert(&hist_mask, hist_elems, 1);
255    assert(("inserting packet number one is successful", 0 == s));
256
257    s = lsquic_trechist_insert(&hist_mask, hist_elems, 1);
258    assert(("inserting packet number one again results in duplicate error",
259                                                            s == 1));
260
261    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
262    range = lsquic_trechist_first(&iter);
263    assert(("first range returned correctly", range));
264    assert(("first range low value checks out", range->low == 1));
265    assert(("first range high value checks out", range->high == 1));
266    range = lsquic_trechist_next(&iter);
267    assert(!range);
268    assert(("second range does not exist", !range));
269
270    for (i = 3; i <= 5; ++i)
271    {
272        s = lsquic_trechist_insert(&hist_mask, hist_elems, i);
273        assert(("inserting packet", s == 0));
274    }
275
276    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
277    range = lsquic_trechist_first(&iter);
278    assert(("first range returned correctly", range));
279    assert(("first range low value checks out", range->low == 3));
280    assert(("first range high value checks out", range->high == 5));
281    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 7)));
282    assert(!(lsquic_trechist_contains(hist_mask, hist_elems, 2)));
283    assert(lsquic_trechist_contains(hist_mask, hist_elems, 4));
284    range = lsquic_trechist_next(&iter);
285    assert(("second range returned correctly", range));
286    assert(("second range low value checks out", range->low == 1));
287    assert(("second range high value checks out", range->high == 1));
288    range = lsquic_trechist_next(&iter);
289    assert(("third range does not exist", !range));
290
291    assert(5 == lsquic_trechist_max(hist_mask, hist_elems));
292
293    s = lsquic_trechist_insert(&hist_mask, hist_elems, 10);
294    assert(("inserting packet", s == 0));
295
296    assert(10 == lsquic_trechist_max(hist_mask, hist_elems));
297
298    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
299    range = lsquic_trechist_first(&iter);
300    assert(("first range returned correctly", range));
301    assert(("first range low value checks out", range->low == 10));
302    assert(("first range high value checks out", range->high == 10));
303    test_clone(hist_mask, hist_elems);
304
305    s = lsquic_trechist_insert(&hist_mask, hist_elems, 8);
306    assert(("inserting packet", s == 0));
307    s = lsquic_trechist_insert(&hist_mask, hist_elems, 9);
308    assert(("inserting packet", s == 0));
309
310    /* Check merge */
311    lsquic_trechist_iter(&iter, hist_mask, hist_elems);
312    range = lsquic_trechist_first(&iter);
313    assert(("first range returned correctly", range));
314    assert(("first range low value checks out", range->low == 8));
315    assert(("first range high value checks out", range->high == 10));
316
317    free(hist_elems);
318}
319
320
321static void
322test_limits (void)
323{
324    trechist_mask_t       hist_mask;
325    struct trechist_elem *hist_elems;
326    unsigned i;
327    int s;
328
329    hist_elems = malloc(sizeof(hist_elems[0]) * TRECHIST_MAX_RANGES);
330    hist_mask = 0;
331
332    for (i = 1; i <= UCHAR_MAX; ++i)
333    {
334        s = lsquic_trechist_insert(&hist_mask, hist_elems, i);
335        assert(s == 0);
336    }
337
338    s = lsquic_trechist_insert(&hist_mask, hist_elems, i);
339    assert(s == -1);    /* Overflow */
340
341    for (i = 0; i < TRECHIST_MAX_RANGES - 1; ++i)
342    {
343        s = lsquic_trechist_insert(&hist_mask, hist_elems, 1000 + 2 * i);
344        assert(s == 0);
345    }
346
347    s = lsquic_trechist_insert(&hist_mask, hist_elems, 1000 + 2 * i);
348    assert(s == -1);    /* Out of ranges */
349
350    free(hist_elems);
351}
352
353int
354main (void)
355{
356    basic_test();
357    test4();
358    test5();
359    test_limits();
360
361    return 0;
362}
363