test_packno_len.c revision 06b2a236 
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
17static const struct parse_funcs *const pf = select_pf_by_ver(LSQVER_043);
18
19
20struct packno_bits_test {
21    int             pbt_lineno;
22    /* Inputs: */
23    lsquic_packno_t pbt_packno,
24                    pbt_least_unacked;
25    uint64_t        pbt_n_in_flight;
26    /* Output: */
27    enum packno_bits pbt_packno_bits;
28};
29
30
31static const struct packno_bits_test pb_tests[] = {
32
33    {   .pbt_lineno         = __LINE__,
34        .pbt_packno         = 1,
35        .pbt_least_unacked  = 0,
36        .pbt_n_in_flight    = 0,
37        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
38    },
39
40    {   .pbt_lineno         = __LINE__,
41        .pbt_packno         = 101,
42        .pbt_least_unacked  = 100,
43        .pbt_n_in_flight    = 0,
44        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
45    },
46
47    {   .pbt_lineno         = __LINE__,
48        .pbt_packno         = 10001,
49        .pbt_least_unacked  = 10000,
50        .pbt_n_in_flight    = 1 << 6,
51        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
52    },
53
54    {   .pbt_lineno         = __LINE__,
55        .pbt_packno         = 10001,
56        .pbt_least_unacked  = 10000,
57        .pbt_n_in_flight    = (1 << 6) + 1,
58        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
59    },
60
61    {   .pbt_lineno         = __LINE__,
62        .pbt_packno         = (1 << 16) + 1,
63        .pbt_least_unacked  = 1 << 16,
64        .pbt_n_in_flight    = 1 << 14,
65        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
66    },
67
68    {   .pbt_lineno         = __LINE__,
69        .pbt_packno         = (1 << 16) + 1,
70        .pbt_least_unacked  = 1 << 16,
71        .pbt_n_in_flight    = (1 << 14) + 1,
72        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
73    },
74
75    {   .pbt_lineno         = __LINE__,
76        .pbt_packno         = (1ULL << 33) + 1,
77        .pbt_least_unacked  = 1ULL << 33,
78        .pbt_n_in_flight    = 1ULL << 30,
79        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
80    },
81
82    {   .pbt_lineno         = __LINE__,
83        .pbt_packno         = (1ULL << 33) + 1,
84        .pbt_least_unacked  = 1ULL << 33,
85        .pbt_n_in_flight    = (1ULL << 30) + 1,
86        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
87    },
88
89    {   .pbt_lineno         = __LINE__,
90        .pbt_packno         = 100,
91        .pbt_least_unacked  = 1,
92        .pbt_n_in_flight    = 3,
93        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
94    },
95
96    {   .pbt_lineno         = __LINE__,
97        .pbt_packno         = 100,
98        .pbt_least_unacked  = 1,
99        .pbt_n_in_flight    = 99,
100        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
101    },
102
103    {   .pbt_lineno         = __LINE__,
104        .pbt_packno         = 1 + (1 << 6),
105        .pbt_least_unacked  = 1,
106        .pbt_n_in_flight    = 0,
107        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
108    },
109
110    {   .pbt_lineno         = __LINE__,
111        .pbt_packno         = 1 + (1 << 6) + 1,
112        .pbt_least_unacked  = 1,
113        .pbt_n_in_flight    = 0,
114        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
115    },
116
117    {   .pbt_lineno         = __LINE__,
118        .pbt_packno         = (1 << 20) + (1 << 14),
119        .pbt_least_unacked  = 1 << 20,
120        .pbt_n_in_flight    = 0,
121        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
122    },
123
124    {   .pbt_lineno         = __LINE__,
125        .pbt_packno         = (1 << 20) + (1 << 14) + 1,
126        .pbt_least_unacked  = 1 << 20,
127        .pbt_n_in_flight    = 0,
128        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
129    },
130
131    {   .pbt_lineno         = __LINE__,
132        .pbt_packno         = (1 << 20) + (1ULL << 30),
133        .pbt_least_unacked  = 1 << 20,
134        .pbt_n_in_flight    = 0,
135        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
136    },
137
138    {   .pbt_lineno         = __LINE__,
139        .pbt_packno         = (1 << 20) + (1ULL << 30) + 1,
140        .pbt_least_unacked  = 1 << 20,
141        .pbt_n_in_flight    = 0,
142        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
143    },
144
145    /* Tests from Chrome: */
146    {   .pbt_lineno         = __LINE__,
147        .pbt_packno         = 65,
148        .pbt_least_unacked  = 2,
149        .pbt_n_in_flight    = 7,
150        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
151    },
152
153    {   .pbt_lineno         = __LINE__,
154        .pbt_packno         = 64 * 256 - 1,
155        .pbt_least_unacked  = 2,
156        .pbt_n_in_flight    = 7,
157        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
158    },
159
160    {   .pbt_lineno         = __LINE__,
161        .pbt_packno         = 64 * 256 * 256 - 1,
162        .pbt_least_unacked  = 2,
163        .pbt_n_in_flight    = 7,
164        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
165    },
166
167    {   .pbt_lineno         = __LINE__,
168        .pbt_packno         = 64ULL * 256 * 256 * 256 * 256 - 1,
169        .pbt_least_unacked  = 2,
170        .pbt_n_in_flight    = 7,
171        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
172    },
173
174    {   .pbt_lineno         = __LINE__,
175        .pbt_packno         = 2,
176        .pbt_least_unacked  = 1,
177        .pbt_n_in_flight    = 7,
178        .pbt_packno_bits    = GQUIC_PACKNO_LEN_1,
179    },
180
181    {   .pbt_lineno         = __LINE__,
182        .pbt_packno         = 2,
183        .pbt_least_unacked  = 1,
184        .pbt_n_in_flight    = 1896,
185        .pbt_packno_bits    = GQUIC_PACKNO_LEN_2,
186    },
187
188    {   .pbt_lineno         = __LINE__,
189        .pbt_packno         = 2,
190        .pbt_least_unacked  = 1,
191        .pbt_n_in_flight    = 48545,
192        .pbt_packno_bits    = GQUIC_PACKNO_LEN_4,
193    },
194
195    {   .pbt_lineno         = __LINE__,
196        .pbt_packno         = 2,
197        .pbt_least_unacked  = 1,
198        .pbt_n_in_flight    = 3181457256ULL,
199        .pbt_packno_bits    = GQUIC_PACKNO_LEN_6,
200    },
201
202};
203
204
205static void
206run_pbt (int i)
207{
208    const struct parse_funcs *pf = select_pf_by_ver(LSQVER_043);
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