1/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#ifndef WIN32
7#include <sys/time.h>
8#endif
9
10#include "lsquic_types.h"
11#include "lsquic_parse.h"
12#include "lsquic_rechist.h"
13#include "lsquic_util.h"
14#include "lsquic.h"
15
16static const struct parse_funcs *const pf = select_pf_by_ver(LSQVER_035);
17
18static lsquic_packno_t
19n_acked (const ack_info_t *acki)
20{
21    lsquic_packno_t n = 0;
22    unsigned i;
23    for (i = 0; i < acki->n_ranges; ++i)
24        n += acki->ranges[i].high - acki->ranges[i].low + 1;
25    return n;
26}
27
28
29static void
30test1 (void)
31{
32    /* Test taken from quic_framer_test.cc -- NewAckFrameOneAckBlock */
33    unsigned char ack_buf[] = {
34        0x45,
35        0x34, 0x12,             /* Largest acked */
36        0x00, 0x00,             /* Delta time */
37        0x34, 0x12,             /* Block length */
38        0x00,                   /* Number of timestamps */
39    };
40
41    ack_info_t acki;
42    memset(&acki, 0xF1, sizeof(acki));
43
44    int len = pf->pf_parse_ack_frame(ack_buf, sizeof(ack_buf), &acki);
45    assert(("Parsed length is correct (8)", len == sizeof(ack_buf)));
46    assert(("Number of ranges is 1", acki.n_ranges == 1));
47    assert(("Largest acked is 0x1234", acki.ranges[0].high == 0x1234));
48    assert(("Lowest acked is 1", acki.ranges[0].low == 1));
49    assert(("Number of timestamps is 0", acki.n_timestamps == 0));
50    unsigned n = n_acked(&acki);
51    assert(("Number of acked packets is 0x1234", n == 0x1234));
52
53    {
54        size_t sz;
55        for (sz = 1; sz < sizeof(ack_buf); ++sz)
56        {
57            len = pf->pf_parse_ack_frame(ack_buf, sz, &acki);
58            assert(("Parsing truncated frame failed", len < 0));
59        }
60    }
61}
62
63
64static void
65test2 (void)
66{
67    /* Test taken from quic_framer_test.cc -- NewAckFrameOneAckBlock */
68    unsigned char ack_buf[] = {
69        0x65,
70        0x34, 0x12,                 /* Largest acked */
71        0x00, 0x00,                 /* Zero delta time. */
72        0x04,                       /* Num ack blocks ranges. */
73        0x01, 0x00,                 /* First ack block length. */
74        0x01,                       /* Gap to next block. */
75        0xaf, 0x0e,                 /* Ack block length. */
76        0xff,                       /* Gap to next block. */
77        0x00, 0x00,                 /* Ack block length. */
78        0x91,                       /* Gap to next block. */
79        0xea, 0x01,                 /* Ack block length. */
80        0x05,                       /* Gap to next block. */
81        0x04, 0x00,                 /* Ack block length. */
82        0x02,                       /* Number of timestamps. */
83        0x01,                       /* Delta from largest observed. */
84        0x10, 0x32, 0x54, 0x76,     /* Delta time. */
85        0x02,                       /* Delta from largest observed. */
86        0x10, 0x32,                 /* Delta time. */
87    };
88
89    /* We should get the following array of ranges:
90     *    high      low
91     *    0x1234    0x1234
92     *    0x1232    0x384
93     *    0x1F3     0xA
94     *    0x4       0x1
95     */
96    static const struct { unsigned high, low; } ranges[] = {
97        {   0x1234, 0x1234 },
98        {   0x1232, 0x384 },
99        {   0x1F3,  0xA },
100        {   0x4,    0x1 },
101    };
102
103    ack_info_t acki;
104    memset(&acki, 0xF1, sizeof(acki));
105
106    int len = pf->pf_parse_ack_frame(ack_buf, sizeof(ack_buf), &acki);
107    assert(("Parsed length is correct (29)", len == sizeof(ack_buf)));
108    assert(("Number of ranges is 4", acki.n_ranges == 4));
109    assert(("Largest acked is 0x1234", acki.ranges[0].high == 0x1234));
110    assert(("Number of timestamps is 2", acki.n_timestamps == 2));
111    unsigned n = n_acked(&acki);
112    assert(("Number of acked packets is 4254", n == 4254));
113
114    for (n = 0; n < 4; ++n)
115        assert(("Range checks out", ranges[n].high == acki.ranges[n].high
116                                &&  ranges[n].low  == acki.ranges[n].low));
117
118    {
119        size_t sz;
120        for (sz = 1; sz < sizeof(ack_buf); ++sz)
121        {
122            len = pf->pf_parse_ack_frame(ack_buf, sz, &acki);
123            assert(("Parsing truncated frame failed", len < 0));
124        }
125    }
126}
127
128
129static void
130test3 (void)
131{
132    /* Generated by our own code, but failed to parse... */
133    unsigned char ack_buf[] = {
134        0x60,         /* More than one ack block, 1 byte largest observed, 1 byte block length */
135        0x06,         /* Largest ACKed */
136        0x00, 0x00,   /* Delta time */
137        0x01,         /* Num ACK block ranges */
138        0x01,         /* First ACK block length */
139        0x02,         /* Gap to next block */
140        0x03,         /* Ack block length */
141        0x00          /* Number of timestamps */
142    };
143
144    /* We should get the following array of ranges:
145     *    high      low
146     *    6         6
147     *    3         1
148     */
149    static const struct { unsigned high, low; } ranges[] = {
150        {   6,      6, },
151        {   3,      1, },
152    };
153
154    ack_info_t acki;
155    memset(&acki, 0xF1, sizeof(acki));
156
157    int len = pf->pf_parse_ack_frame(ack_buf, sizeof(ack_buf), &acki);
158    assert(("Parsed length is correct (9)", len == sizeof(ack_buf)));
159    assert(("Number of ranges is 2", acki.n_ranges == 2));
160    assert(("Largest acked is 6", acki.ranges[0].high == 6));
161    assert(("Number of timestamps is 0", acki.n_timestamps == 0));
162    unsigned n = n_acked(&acki);
163    assert(("Number of acked packets is 4", n == 4));
164
165    for (n = 0; n < 2; ++n)
166        assert(("Range checks out", ranges[n].high == acki.ranges[n].high
167                                &&  ranges[n].low  == acki.ranges[n].low));
168
169    {
170        size_t sz;
171        for (sz = 1; sz < sizeof(ack_buf); ++sz)
172        {
173            len = pf->pf_parse_ack_frame(ack_buf, sz, &acki);
174            assert(("Parsing truncated frame failed", len < 0));
175        }
176    }
177}
178
179
180static void
181test4 (void)
182{
183    unsigned char ack_buf[] = {
184        0x60,       /* More than one ack block, 1 byte largest observed, 1 byte block length */
185        0x03,       /* Largest ACKed */
186        0x23, 0x00, /* Delta time */
187        0x01,       /* Num ACK block ranges */
188        0x01,       /* First ack block length */
189        0x01,       /* Gap */
190        0x01,       /* Ack block length */
191        0x00,       /* Number of timestamps */
192    };
193
194    /* We should get the following array of ranges:
195     *    high      low
196     *    6         6
197     *    3         1
198     */
199    static const struct { unsigned high, low; } ranges[] = {
200        {   3,      3, },
201        {   1,      1, },
202    };
203
204    ack_info_t acki;
205    memset(&acki, 0xF1, sizeof(acki));
206
207    int len = pf->pf_parse_ack_frame(ack_buf, sizeof(ack_buf), &acki);
208    assert(("Parsed length is correct (9)", len == sizeof(ack_buf)));
209    assert(("Number of ranges is 2", acki.n_ranges == 2));
210    assert(("Largest acked is 3", acki.ranges[0].high == 3));
211    assert(("Number of timestamps is 0", acki.n_timestamps == 0));
212    unsigned n = n_acked(&acki);
213    assert(("Number of acked packets is 2", n == 2));
214
215    for (n = 0; n < 2; ++n)
216        assert(("Range checks out", ranges[n].high == acki.ranges[n].high
217                                &&  ranges[n].low  == acki.ranges[n].low));
218
219    {
220        size_t sz;
221        for (sz = 1; sz < sizeof(ack_buf); ++sz)
222        {
223            len = pf->pf_parse_ack_frame(ack_buf, sz, &acki);
224            assert(("Parsing truncated frame failed", len < 0));
225        }
226    }
227}
228
229
230/* Four-byte packet numbers */
231static void
232test5 (void)
233{
234    unsigned char ack_buf[] = {
235        0x60
236            | (2 << 2)  /* Four-byte largest acked */
237            | (2 << 0)  /* Four-byte ACK block length */
238        ,
239        0x89, 0x67, 0x45, 0x23,
240        0x00, 0x00,                 /* Zero delta time. */
241        0x01,                       /* Num ack blocks ranges. */
242        0x01, 0x00, 0x00, 0x00,     /* First ack block length. */
243        33 - 1,                     /* Gap to next block. */
244        0x68, 0x67, 0x45, 0x23,     /* Ack block length. */
245        0x00,                       /* Number of timestamps. */
246    };
247
248    /* We should get the following array of ranges:
249     *    high      low
250     *    6         6
251     *    3         1
252     */
253    static const struct { unsigned high, low; } ranges[] = {
254        {   0x23456789,      0x23456789, },
255        {   0x23456768,      1, },
256    };
257
258    ack_info_t acki;
259    memset(&acki, 0xF1, sizeof(acki));
260
261    int len = pf->pf_parse_ack_frame(ack_buf, sizeof(ack_buf), &acki);
262    assert(("Parsed length is correct (9)", len == sizeof(ack_buf)));
263    assert(("Number of ranges is 2", acki.n_ranges == 2));
264    assert(("Largest acked is 0x23456789", acki.ranges[0].high == 0x23456789));
265    assert(("Number of timestamps is 0", acki.n_timestamps == 0));
266    lsquic_packno_t n = n_acked(&acki);
267    assert(("Number of acked packets is correct", n == 0x23456768 + 1));
268
269    for (n = 0; n < 2; ++n)
270        assert(("Range checks out", ranges[n].high == acki.ranges[n].high
271                                &&  ranges[n].low  == acki.ranges[n].low));
272
273    {
274        size_t sz;
275        for (sz = 1; sz < sizeof(ack_buf); ++sz)
276        {
277            len = pf->pf_parse_ack_frame(ack_buf, sz, &acki);
278            assert(("Parsing truncated frame failed", len < 0));
279        }
280    }
281}
282
283
284/* Six-byte packet numbers */
285static void
286test6 (void)
287{
288    unsigned char ack_buf[] = {
289        0x60
290            | (3 << 2)  /* Six-byte largest acked */
291            | (3 << 0)  /* Six-byte ACK block length */
292        ,
293        0x89, 0x67, 0x45, 0x23, 0xCD, 0xAB,
294        0x00, 0x00,                 /* Zero delta time. */
295        0x01,                       /* Num ack blocks ranges. */
296        0x01, 0x00, 0x00, 0x00, 0x00, 0x00,    /* First ack block length. */
297        33 - 1,                     /* Gap to next block. */
298        0x68, 0x67, 0x45, 0x23, 0xCD, 0xAB,   /* Ack block length. */
299        0x00,                       /* Number of timestamps. */
300    };
301
302    static const struct { lsquic_packno_t high, low; } ranges[] = {
303        {   0xABCD23456789,      0xABCD23456789, },
304        {   0xABCD23456768,      1, },
305    };
306
307    ack_info_t acki;
308    memset(&acki, 0xF1, sizeof(acki));
309
310    int len = pf->pf_parse_ack_frame(ack_buf, sizeof(ack_buf), &acki);
311    assert(("Parsed length is correct", len == sizeof(ack_buf)));
312    assert(("Number of ranges is 2", acki.n_ranges == 2));
313    assert(("Largest acked is 0xABCD23456789", acki.ranges[0].high == 0xABCD23456789));
314    assert(("Number of timestamps is 0", acki.n_timestamps == 0));
315    lsquic_packno_t n = n_acked(&acki);
316    assert(("Number of acked packets is correct", n == 0xABCD23456768 + 1));
317
318    for (n = 0; n < 2; ++n)
319        assert(("Range checks out", ranges[n].high == acki.ranges[n].high
320                                &&  ranges[n].low  == acki.ranges[n].low));
321
322    {
323        size_t sz;
324        for (sz = 1; sz < sizeof(ack_buf); ++sz)
325        {
326            len = pf->pf_parse_ack_frame(ack_buf, sz, &acki);
327            assert(("Parsing truncated frame failed", len < 0));
328        }
329    }
330}
331
332
333static void
334test_max_ack (void)
335{
336    lsquic_rechist_t rechist;
337    lsquic_time_t now;
338    unsigned i;
339    int has_missing, sz[2];
340    const struct lsquic_packno_range *range;
341    unsigned char buf[1500];
342    struct ack_info acki;
343
344    lsquic_rechist_init(&rechist, 12345);
345    now = lsquic_time_now();
346
347    for (i = 1; i <= 300; ++i)
348    {
349        lsquic_rechist_received(&rechist, i * 10, now);
350        now += i * 1000;
351    }
352
353    memset(buf, 0xAA, sizeof(buf));
354
355    lsquic_packno_t largest = 0;
356    sz[0] = pf->pf_gen_ack_frame(buf, sizeof(buf),
357        (gaf_rechist_first_f)        lsquic_rechist_first,
358        (gaf_rechist_next_f)         lsquic_rechist_next,
359        (gaf_rechist_largest_recv_f) lsquic_rechist_largest_recv,
360        &rechist, now, &has_missing, &largest);
361    assert(sz[0] > 0);
362    assert(sz[0] <= (int) sizeof(buf));
363    assert(has_missing);
364
365    assert(0 == buf[ sz[0] - 1 ]);  /* Number of timestamps */
366    assert(0xAA == buf[ sz[0] ]);
367
368    sz[1] = pf->pf_parse_ack_frame(buf, sizeof(buf), &acki);
369    assert(sz[1] == sz[0]);
370    assert(256 == acki.n_ranges);
371
372    for (range = lsquic_rechist_first(&rechist), i = 0;
373                        range && i < acki.n_ranges;
374                                    range = lsquic_rechist_next(&rechist), ++i)
375    {
376        assert(range->high == acki.ranges[i].high);
377        assert(range->low  == acki.ranges[i].low);
378    }
379    assert(i == 256);
380
381    lsquic_rechist_cleanup(&rechist);
382}
383
384
385static void
386test_ack_truncation (void)
387{
388    lsquic_rechist_t rechist;
389    lsquic_time_t now;
390    unsigned i;
391    int has_missing, sz[2];
392    const struct lsquic_packno_range *range;
393    unsigned char buf[1500];
394    struct ack_info acki;
395    size_t bufsz;
396
397    lsquic_rechist_init(&rechist, 12345);
398    now = lsquic_time_now();
399
400    for (i = 1; i <= 300; ++i)
401    {
402        lsquic_rechist_received(&rechist, i * 10, now);
403        now += i * 1000;
404    }
405
406    for (bufsz = 200; bufsz < 210; ++bufsz)
407    {
408        memset(buf, 0xAA, sizeof(buf));
409        lsquic_packno_t largest = 0;
410        sz[0] = pf->pf_gen_ack_frame(buf, bufsz,
411            (gaf_rechist_first_f)        lsquic_rechist_first,
412            (gaf_rechist_next_f)         lsquic_rechist_next,
413            (gaf_rechist_largest_recv_f) lsquic_rechist_largest_recv,
414            &rechist, now, &has_missing, &largest);
415        assert(sz[0] > 0);
416        assert(sz[0] <= (int) bufsz);
417        assert(has_missing);
418
419        assert(0 == buf[ sz[0] - 1 ]);  /* Number of timestamps */
420        assert(0xAA == buf[ sz[0] ]);
421
422        sz[1] = pf->pf_parse_ack_frame(buf, sizeof(buf), &acki);
423        assert(sz[1] == sz[0]);
424        assert(acki.n_ranges < 256);
425
426        for (range = lsquic_rechist_first(&rechist), i = 0;
427                            range && i < acki.n_ranges;
428                                        range = lsquic_rechist_next(&rechist), ++i)
429        {
430            assert(range->high == acki.ranges[i].high);
431            assert(range->low  == acki.ranges[i].low);
432        }
433    }
434
435    lsquic_rechist_cleanup(&rechist);
436}
437
438
439int
440main (void)
441{
442    lsquic_global_init(LSQUIC_GLOBAL_SERVER);
443    test1();
444    test2();
445    test3();
446    test4();
447    test5();
448    test6();
449    test_max_ack();
450    test_ack_truncation();
451    return 0;
452}
453