test_packno_len.c revision f07b3eae 
1/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <sys/queue.h>
7#ifndef WIN32
8#include <sys/time.h>
9#endif
10
11#include "lsquic.h"
12#include "lsquic_types.h"
13#include "lsquic_packet_common.h"
14#include "lsquic_parse.h"
15
16
17//static const struct parse_funcs *const pf = select_pf_by_ver(LSQVER_043); // will not work on MSVC
18#define pf ((const struct parse_funcs *const)select_pf_by_ver(LSQVER_043))
19
20
21struct packno_bits_test {
22    int             pbt_lineno;
23    /* Inputs: */
24    lsquic_packno_t pbt_packno,
25                    pbt_least_unacked;
26    uint64_t        pbt_n_in_flight;
27    /* Output: */
28    enum packno_bits pbt_packno_bits;
29};
30
31
32static const struct packno_bits_test pb_tests[] = {
33
34    {   .pbt_lineno         = __LINE__,
35        .pbt_packno         = 1,
36        .pbt_least_unacked  = 0,
37        .pbt_n_in_flight    = 0,
38        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
39    },
40
41    {   .pbt_lineno         = __LINE__,
42        .pbt_packno         = 101,
43        .pbt_least_unacked  = 100,
44        .pbt_n_in_flight    = 0,
45        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
46    },
47
48    {   .pbt_lineno         = __LINE__,
49        .pbt_packno         = 10001,
50        .pbt_least_unacked  = 10000,
51        .pbt_n_in_flight    = 1 << 6,
52        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
53    },
54
55    {   .pbt_lineno         = __LINE__,
56        .pbt_packno         = 10001,
57        .pbt_least_unacked  = 10000,
58        .pbt_n_in_flight    = (1 << 6) + 1,
59        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
60    },
61
62    {   .pbt_lineno         = __LINE__,
63        .pbt_packno         = (1 << 16) + 1,
64        .pbt_least_unacked  = 1 << 16,
65        .pbt_n_in_flight    = 1 << 14,
66        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
67    },
68
69    {   .pbt_lineno         = __LINE__,
70        .pbt_packno         = (1 << 16) + 1,
71        .pbt_least_unacked  = 1 << 16,
72        .pbt_n_in_flight    = (1 << 14) + 1,
73        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
74    },
75
76    {   .pbt_lineno         = __LINE__,
77        .pbt_packno         = (1ULL << 33) + 1,
78        .pbt_least_unacked  = 1ULL << 33,
79        .pbt_n_in_flight    = 1ULL << 30,
80        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
81    },
82
83    {   .pbt_lineno         = __LINE__,
84        .pbt_packno         = (1ULL << 33) + 1,
85        .pbt_least_unacked  = 1ULL << 33,
86        .pbt_n_in_flight    = (1ULL << 30) + 1,
87        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
88    },
89
90    {   .pbt_lineno         = __LINE__,
91        .pbt_packno         = 100,
92        .pbt_least_unacked  = 1,
93        .pbt_n_in_flight    = 3,
94        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
95    },
96
97    {   .pbt_lineno         = __LINE__,
98        .pbt_packno         = 100,
99        .pbt_least_unacked  = 1,
100        .pbt_n_in_flight    = 99,
101        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
102    },
103
104    {   .pbt_lineno         = __LINE__,
105        .pbt_packno         = 1 + (1 << 6),
106        .pbt_least_unacked  = 1,
107        .pbt_n_in_flight    = 0,
108        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
109    },
110
111    {   .pbt_lineno         = __LINE__,
112        .pbt_packno         = 1 + (1 << 6) + 1,
113        .pbt_least_unacked  = 1,
114        .pbt_n_in_flight    = 0,
115        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
116    },
117
118    {   .pbt_lineno         = __LINE__,
119        .pbt_packno         = (1 << 20) + (1 << 14),
120        .pbt_least_unacked  = 1 << 20,
121        .pbt_n_in_flight    = 0,
122        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
123    },
124
125    {   .pbt_lineno         = __LINE__,
126        .pbt_packno         = (1 << 20) + (1 << 14) + 1,
127        .pbt_least_unacked  = 1 << 20,
128        .pbt_n_in_flight    = 0,
129        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
130    },
131
132    {   .pbt_lineno         = __LINE__,
133        .pbt_packno         = (1 << 20) + (1ULL << 30),
134        .pbt_least_unacked  = 1 << 20,
135        .pbt_n_in_flight    = 0,
136        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
137    },
138
139    {   .pbt_lineno         = __LINE__,
140        .pbt_packno         = (1 << 20) + (1ULL << 30) + 1,
141        .pbt_least_unacked  = 1 << 20,
142        .pbt_n_in_flight    = 0,
143        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
144    },
145
146    /* Tests from Chrome: */
147    {   .pbt_lineno         = __LINE__,
148        .pbt_packno         = 65,
149        .pbt_least_unacked  = 2,
150        .pbt_n_in_flight    = 7,
151        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
152    },
153
154    {   .pbt_lineno         = __LINE__,
155        .pbt_packno         = 64 * 256 - 1,
156        .pbt_least_unacked  = 2,
157        .pbt_n_in_flight    = 7,
158        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
159    },
160
161    {   .pbt_lineno         = __LINE__,
162        .pbt_packno         = 64 * 256 * 256 - 1,
163        .pbt_least_unacked  = 2,
164        .pbt_n_in_flight    = 7,
165        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
166    },
167
168    {   .pbt_lineno         = __LINE__,
169        .pbt_packno         = 64ULL * 256 * 256 * 256 * 256 - 1,
170        .pbt_least_unacked  = 2,
171        .pbt_n_in_flight    = 7,
172        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
173    },
174
175    {   .pbt_lineno         = __LINE__,
176        .pbt_packno         = 2,
177        .pbt_least_unacked  = 1,
178        .pbt_n_in_flight    = 7,
179        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
180    },
181
182    {   .pbt_lineno         = __LINE__,
183        .pbt_packno         = 2,
184        .pbt_least_unacked  = 1,
185        .pbt_n_in_flight    = 1896,
186        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
187    },
188
189    {   .pbt_lineno         = __LINE__,
190        .pbt_packno         = 2,
191        .pbt_least_unacked  = 1,
192        .pbt_n_in_flight    = 48545,
193        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
194    },
195
196    {   .pbt_lineno         = __LINE__,
197        .pbt_packno         = 2,
198        .pbt_least_unacked  = 1,
199        .pbt_n_in_flight    = 3181457256ULL,
200        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
201    },
202
203};
204
205
206static void
207run_pbt (int i)
208{
209    const struct packno_bits_test *const pbt = &pb_tests[i];
210    enum packno_bits packno_bits = pf->pf_calc_packno_bits(pbt->pbt_packno,
211                                pbt->pbt_least_unacked, pbt->pbt_n_in_flight);
212    assert(packno_bits == pbt->pbt_packno_bits);
213    unsigned packet_len = pf->pf_packno_bits2len(packno_bits);
214    /* Now see if we can restore it back: */
215    lsquic_packno_t cur_packno = pbt->pbt_packno &
216                        ((1ULL << (packet_len << 3)) - 1);
217    lsquic_packno_t orig_packno = lsquic_restore_packno(cur_packno, packet_len,
218                                                    pbt->pbt_least_unacked);
219    assert(orig_packno == pbt->pbt_packno);
220}
221
222
223struct lsquic_restore_packno_test {
224    int                         rpt_lineno;
225    /* Input */
226    enum packno_bits     rpt_packno_bits;
227    lsquic_packno_t             rpt_cur_packno;
228    lsquic_packno_t             rpt_max_packno;
229    /* Output */
230    lsquic_packno_t             rpt_orig_packno;
231};
232
233static const struct lsquic_restore_packno_test rp_tests[] =
234{
235
236    {   .rpt_lineno         = __LINE__,
237        .rpt_max_packno     = 0,
238        .rpt_cur_packno     = 1,
239        .rpt_packno_bits    = GQUIC_PACKNO_LEN_1,
240        .rpt_orig_packno    = 1,
241    },
242
243};
244
245
246static void
247run_rpt (int i)
248{
249    const struct lsquic_restore_packno_test *const rpt = &rp_tests[i];
250    unsigned packet_len = pf->pf_packno_bits2len(rpt->rpt_packno_bits);
251    lsquic_packno_t orig_packno = lsquic_restore_packno(rpt->rpt_cur_packno,
252                            packet_len, rpt->rpt_max_packno);
253    assert(orig_packno == rpt->rpt_orig_packno);
254}
255
256
257static void
258test_restore (enum packno_bits bits)
259{
260    unsigned len, n;
261    enum { OP_PLUS, OP_MINUS, N_OPS } op;
262    uint64_t epoch, epoch_delta;
263    lsquic_packno_t orig_packno, cur_packno, restored_packno;
264
265#ifdef WIN32
266    orig_packno = 0;
267#endif
268    len = pf->pf_packno_bits2len(bits);
269    epoch_delta = 1ULL << (len << 3);
270    epoch = epoch_delta * 11 /* Just some number */;
271
272    /* Test current epoch: */
273    for (op = 0; op < N_OPS; ++op)
274        for (n = 0; n < 5; ++n)
275        {
276            /* Test at the ends of the epoch */
277            if (op == OP_MINUS)
278                orig_packno = epoch - epoch_delta / 2 + n;
279            else if (op == OP_PLUS)
280                orig_packno = epoch + epoch_delta / 2 - n - 1;
281            else
282                assert(0);
283            cur_packno = orig_packno & (epoch_delta - 1);
284            restored_packno = lsquic_restore_packno(cur_packno, len, epoch);
285            assert(orig_packno == restored_packno);
286            /* Test in the middle of the epoch */
287            if (op == OP_MINUS)
288                orig_packno = epoch - n;
289            else
290                orig_packno = epoch + n;
291            cur_packno = orig_packno & (epoch_delta - 1);
292            restored_packno = lsquic_restore_packno(cur_packno, len, epoch);
293            assert(orig_packno == restored_packno);
294        }
295
296    /* Test previous epoch (max is to the left) */
297    for (n = 0; n < 5; ++n)
298    {
299        /* Test at the end of the epoch */
300        orig_packno = epoch + epoch_delta / 2 - n - 1;
301        cur_packno = orig_packno & (epoch_delta - 1);
302        restored_packno = lsquic_restore_packno(cur_packno, len, epoch - epoch_delta * 3 / 4);
303        assert(orig_packno == restored_packno + epoch_delta);
304        /* Test in the middle of the epoch */
305        orig_packno = epoch + 2 - n;
306        cur_packno = orig_packno & (epoch_delta - 1);
307        restored_packno = lsquic_restore_packno(cur_packno, len, epoch - epoch_delta * 3 / 4);
308        assert(orig_packno == restored_packno + epoch_delta);
309    }
310
311    /* Test previous epoch (max is to the right) */
312    for (n = 0; n < 5; ++n)
313    {
314        /* Test at the end of the epoch */
315        orig_packno = epoch - epoch_delta / 2 + n;
316        cur_packno = orig_packno & (epoch_delta - 1);
317        restored_packno = lsquic_restore_packno(cur_packno, len, epoch + epoch_delta * 3 / 4);
318        assert(orig_packno == restored_packno - epoch_delta);
319        /* Test in the middle of the epoch */
320        orig_packno = epoch + 2 - n;
321        cur_packno = orig_packno & (epoch_delta - 1);
322        restored_packno = lsquic_restore_packno(cur_packno, len, epoch + epoch_delta * 3 / 4);
323        assert(orig_packno == restored_packno - epoch_delta);
324    }
325
326}
327
328
329int
330main (void)
331{
332    unsigned i;
333    for (i = 0; i < sizeof(pb_tests) / sizeof(pb_tests[0]); ++i)
334        run_pbt(i);
335    for (i = 0; i < sizeof(rp_tests) / sizeof(rp_tests[0]); ++i)
336        run_rpt(i);
337    test_restore(GQUIC_PACKNO_LEN_1);
338    test_restore(GQUIC_PACKNO_LEN_2);
339    test_restore(GQUIC_PACKNO_LEN_4);
340    test_restore(GQUIC_PACKNO_LEN_6);
341    return 0;
342}
343