test_hpi.c revision 06b2a236 
1/* Copyright (c) 2017 - 2021 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <errno.h>
4#include <stdio.h>
5#include <stdlib.h>
6#include <string.h>
7#include <sys/queue.h>
8#ifndef WIN32
9#include <unistd.h>
10#endif
11
12#include "lsquic.h"
13
14#include "lsquic_int_types.h"
15#include "lsquic_packet_common.h"
16#include "lsquic_packet_in.h"
17#include "lsquic_conn_flow.h"
18#include "lsquic_sfcw.h"
19#include "lsquic_varint.h"
20#include "lsquic_hq.h"
21#include "lsquic_hash.h"
22#include "lsquic_conn.h"
23#include "lsquic_stream.h"
24#include "lsquic_types.h"
25#include "lsquic_rtt.h"
26#include "lsquic_conn_flow.h"
27#include "lsquic_conn_public.h"
28#include "lsquic_mm.h"
29#include "lsquic_min_heap.h"
30#include "lsquic_hpi.h"
31#include "lsquic_logger.h"
32
33
34/*
35 * DSL:
36 *
37 * S\d+:\d+:\d+     Create stream and insert it into list.  The three numbers
38 *                    are stream ID, priority, and incremental boolean flag.
39 *                    Priority can be negative, which indicates a critical
40 *                    stream.  Otherwise, the priorirty should be in the range
41 *                    [0, MAX_HTTP_PRIORITY].  The incremental flag is ignored
42 *                    for critical streams.
43 *
44 * F\d+             Use filter identified by the number.  For "F" to take
45 *                    effect, it should be called before "I".
46 *
47 * I                Initialize the iterator.
48 *
49 * D[hH]            Call drop high (h) or drop non-high (H).
50 *
51 * N\d+             Call "next" and verify that the stream ID is this number.
52 *                    If "next" returns NULL, the test fails.
53 *
54 */
55
56static const struct test_spec {
57    int          lineno;
58    const char  *prog;
59} test_specs[] = {
60
61    {   __LINE__,
62        "S0:3:0;"
63        "I;"
64        "N0;"
65    },
66
67    {   __LINE__,
68        /* Insert non-incremental streams with same priority, check that
69         * they come back out in the order of stream IDs.
70         */
71        "S1:3:0;" "S0:3:0;" "S2:3:0;"
72        "I;"
73        "N0;" "N1;" "N2;"
74    },
75
76    {   __LINE__,
77        /* Insert incremental streams with same priority, check that they
78         * come back out in the same order.
79         */
80        "S1:3:1;" "S0:3:1;" "S2:3:1;"
81        "I;"
82        "N1;" "N0;" "N2;"
83    },
84
85    {   __LINE__,
86        /* Insert incremental streams with same priority, filter out out odd
87         * IDs, check that they come back out in the same order and without
88         * the odd stream ID"
89         */
90        "S1:3:1;" "S0:3:1;" "S2:3:1;"
91        "F;"
92        "I;"
93        "N0;" "N2;"
94    },
95
96    {   __LINE__,
97        /* Insert incremental and non-incremental streams with same priority.
98         * Check that non-incrementals are returned first.
99         */
100        "S1:3:1;" "S0:3:1;" "S2:3:1;"
101        "S6:3:0;" "S10:3:0;" "S3:3:0;"
102        "I;"
103        "N3;N6;N10;"
104        "N1;N0;N2;"
105    },
106
107    {   __LINE__,
108        /* Drop high with same priority: nothing should be dropped */
109        "S1:3:1;" "S0:3:1;" "S2:3:1;"
110        "I;"
111        "Dh;"
112        "N1;" "N0;" "N2;"
113    },
114
115    {   __LINE__,
116        /* Drop non-high with same priority: nothing should be dropped */
117        "S1:3:1;" "S0:3:1;" "S2:3:1;"
118        "I;"
119        "DH;"
120        "N1;" "N0;" "N2;"
121    },
122
123    {   __LINE__,
124        /* Drop high with same priority: drop non-incrementals */
125        "S1:3:1;" "S0:3:1;" "S2:3:1;"
126        "S6:3:0;" "S10:3:0;" "S3:3:0;"
127        "I;"
128        "Dh;"
129        "N1;" "N0;" "N2;"
130    },
131
132    {   __LINE__,
133        /* Drop non-high with same priority: drop incrementals */
134        "S1:3:1;" "S0:3:1;" "S2:3:1;"
135        "S6:3:0;" "S10:3:0;" "S3:3:0;"
136        "I;"
137        "DH;"
138        "N3;N6;N10;"
139    },
140
141    {   __LINE__,
142        /* Insert streams with different priorities */
143        "S1:1:1;" "S2:2:1;" "S3:3:1;"
144        "S6:6:0;" "S5:5:0;" "S4:4:0;"
145        "I;"
146        "N1;N2;N3;N4;N5;N6;"
147    },
148
149    {   __LINE__,
150        /* Insert regular and critical streams */
151        "S1:1:1;" "S2:2:1;" "S3333:-1:1;"
152        "S6:6:0;" "S2222:-1:0;" "S4:4:0;"
153        "I;"
154        "N3333;N2222;N1;N2;N4;N6;"
155    },
156
157    {   __LINE__,
158        /* Insert regular and critical streams; drop high */
159        "S1:1:1;" "S2:2:1;" "S3333:-1:1;"
160        "S6:6:0;" "S2222:-1:0;" "S4:4:0;"
161        "I;"
162        "Dh;"
163        "N1;N2;N4;N6;"
164    },
165
166    {   __LINE__,
167        /* Insert regular and critical streams; drop non-high */
168        "S1:1:1;" "S2:2:1;" "S3333:-1:1;"
169        "S6:6:0;" "S2222:-1:0;" "S4:4:0;"
170        "I;"
171        "DH;"
172        "N3333;N2222;"
173    },
174
175    {   __LINE__,
176        /* Insert streams with different priorities, non-incremental,
177         * several per bucket.
178         */
179        "S1:1:0;" "S4:2:0;" "S3:2:0;"
180        "S6:1:0;" "S5:1:0;" "S2:2:0;"
181        "I;"
182        "N1;N5;N6;N2;N3;N4;"
183    },
184
185};
186
187/* Sharing the same HPI tests safety of reusing the same iterator object
188 * (no need to deinitialize it).
189 */
190static struct http_prio_iter hpi;
191
192static struct lsquic_conn lconn = LSCONN_INITIALIZER_CIDLEN(lconn, 0);
193
194static struct lsquic_conn_public conn_pub = { .lconn = &lconn, };
195
196
197static struct lsquic_stream *
198new_stream (lsquic_stream_id_t stream_id, int priority, int incr)
199{
200    struct lsquic_stream *stream = calloc(1, sizeof(*stream));
201    stream->id = stream_id;
202    if (priority >= 0)
203    {
204        stream->sm_priority = priority;
205        if (incr)
206            stream->sm_bflags |= SMBF_INCREMENTAL;
207    }
208    else
209        stream->sm_bflags |= SMBF_CRITICAL;
210        /* Critical streams are never incremental */
211    return stream;
212}
213
214
215#define MAGIC 0x12312312U
216
217struct my_filter_ctx
218{
219    unsigned magic;
220};
221
222static int
223filter_out_odd_stream_ids (void *ctx, struct lsquic_stream *stream)
224{
225    struct my_filter_ctx *fctx = ctx;
226    assert(fctx->magic == MAGIC);
227    return 0 == (stream->id & 1);
228}
229
230
231static int (*const filters[])(void *, struct lsquic_stream *) = {
232    filter_out_odd_stream_ids,
233};
234
235/* Just pick one (as long as it's not next_prio_stream) */
236#define next_field next_write_stream
237
238
239static void
240run_test (const struct test_spec *spec)
241{
242    struct lsquic_streams_tailq streams;
243    struct lsquic_stream *stream;
244    lsquic_stream_id_t stream_id;
245    long incr, priority, tmp;
246    const char *pc;
247    char cmd;
248    char name[20];
249    struct my_filter_ctx filter_ctx = { MAGIC };
250    int (*filter_cb)(void *, struct lsquic_stream *) = NULL;
251    int first_called = 0;
252    struct lsquic_mm mm;
253
254    lsquic_mm_init(&mm);
255    conn_pub.mm = &mm;
256    TAILQ_INIT(&streams);
257    snprintf(name, sizeof(name), "line-%d", spec->lineno);
258
259    for (pc = spec->prog; *pc; ++pc)
260    {
261        cmd = *pc++;
262        switch (cmd)
263        {
264        case 'S':
265            stream_id = strtol(pc, (char **) &pc, 10);
266            assert(':' == *pc);
267            priority = strtol(pc + 1, (char **) &pc, 10);
268            assert(':' == *pc);
269            incr = strtol(pc + 1, (char **) &pc, 10);
270            stream = new_stream(stream_id, priority, incr);
271            TAILQ_INSERT_TAIL(&streams, stream, next_field);
272            break;
273        case 'I':
274            lsquic_hpi_init(&hpi, TAILQ_FIRST(&streams),
275                TAILQ_LAST(&streams, lsquic_streams_tailq),
276                (uintptr_t) &TAILQ_NEXT((lsquic_stream_t *) NULL, next_field),
277                &conn_pub, name, filter_cb, &filter_ctx);
278            break;
279        case 'N':
280            stream_id = strtol(pc, (char **) &pc, 10);
281            if (first_called)
282                stream = lsquic_hpi_next(&hpi);
283            else
284            {
285                stream = lsquic_hpi_first(&hpi);
286                first_called = 1;
287            }
288            assert(stream);
289            assert(stream->id == stream_id);
290            break;
291        case 'F':
292            tmp = strtol(pc, (char **) &pc, 10);
293            assert(tmp >= 0
294                && (size_t) tmp < sizeof(filters) / sizeof(filters[0]));
295            filter_cb = filters[tmp];
296            break;
297        case 'D':
298            switch (*pc++)
299            {
300            case 'h':
301                lsquic_hpi_drop_high(&hpi);
302                break;
303            case 'H':
304                lsquic_hpi_drop_non_high(&hpi);
305                break;
306            default:
307                assert(0);
308                break;
309            }
310            break;
311        default:
312            assert(0);
313        }
314        assert(*pc == ';');
315    }
316    lsquic_hpi_cleanup(&hpi);
317
318    while (stream = TAILQ_FIRST(&streams), stream != NULL)
319    {
320        TAILQ_REMOVE(&streams, stream, next_field);
321        free(stream);
322    }
323    lsquic_mm_cleanup(&mm);
324}
325
326
327int
328main (int argc, char **argv)
329{
330    unsigned n;
331
332    lsquic_log_to_fstream(stderr, LLTS_NONE);
333    lsq_log_levels[LSQLM_HPI] = LSQ_LOG_DEBUG;
334
335    for (n = 0; n < sizeof(test_specs) / sizeof(test_specs[0]); ++n)
336        run_test(&test_specs[n]);
337
338    lsquic_hpi_set_heap_test(LSQUIC_HPI_HEAP_TEST_STACK_OK);
339    for (n = 0; n < sizeof(test_specs) / sizeof(test_specs[0]); ++n)
340        run_test(&test_specs[n]);
341
342    lsquic_hpi_set_heap_test(LSQUIC_HPI_HEAP_TEST_4K_OK);
343    for (n = 0; n < sizeof(test_specs) / sizeof(test_specs[0]); ++n)
344        run_test(&test_specs[n]);
345
346    lsquic_hpi_set_heap_test(0);
347    for (n = 0; n < sizeof(test_specs) / sizeof(test_specs[0]); ++n)
348        run_test(&test_specs[n]);
349
350    return 0;
351}
352