1/* Copyright (c) 2017 - 2022 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_public.h"
27#include "lsquic_spi.h"
28#include "lsquic_logger.h"
29
30
31/* Sharing the same SPI tests safety of reusing the same iterator object
32 * (no need to deinitialize it).
33 */
34static struct stream_prio_iter spi;
35
36static struct lsquic_conn lconn = LSCONN_INITIALIZER_CIDLEN(lconn, 0);
37
38static struct lsquic_conn_public conn_pub = { .lconn = &lconn, };
39
40
41static lsquic_stream_t *
42new_stream (unsigned priority)
43{
44    lsquic_stream_t *stream = calloc(1, sizeof(*stream));
45    stream->sm_priority = priority;
46    return stream;
47}
48
49
50static void
51free_streams (lsquic_stream_t **streams, size_t count)
52{
53    size_t n;
54    for (n = 0; n < count; ++n)
55        free(streams[n]);
56}
57
58
59static void
60test_same_priority (unsigned priority)
61{
62    lsquic_stream_t *stream_arr[4] = {
63        new_stream(priority),
64        new_stream(priority),
65        new_stream(priority),
66        new_stream(priority),
67    };
68    struct lsquic_streams_tailq streams;
69    lsquic_stream_t *stream;
70
71    TAILQ_INIT(&streams);
72    TAILQ_INSERT_TAIL(&streams, stream_arr[0], next_write_stream);
73    TAILQ_INSERT_TAIL(&streams, stream_arr[1], next_write_stream);
74    TAILQ_INSERT_TAIL(&streams, stream_arr[2], next_write_stream);
75    TAILQ_INSERT_TAIL(&streams, stream_arr[3], next_write_stream);
76
77    lsquic_spi_init(&spi, TAILQ_FIRST(&streams),
78        TAILQ_LAST(&streams, lsquic_streams_tailq),
79        (uintptr_t) &TAILQ_NEXT((lsquic_stream_t *) NULL, next_write_stream),
80        &conn_pub, __func__, NULL, NULL);
81
82    stream = lsquic_spi_first(&spi);
83    assert(stream == stream_arr[0]);
84    stream = lsquic_spi_next(&spi);
85    assert(stream == stream_arr[1]);
86    stream = lsquic_spi_next(&spi);
87    assert(stream == stream_arr[2]);
88    stream = lsquic_spi_next(&spi);
89    assert(stream == stream_arr[3]);
90    stream = lsquic_spi_next(&spi);
91    assert(stream == NULL);
92
93    /* Test reinitialization: */
94    lsquic_spi_init(&spi, stream_arr[0], stream_arr[1],
95        (uintptr_t) &TAILQ_NEXT((lsquic_stream_t *) NULL, next_write_stream),
96        &conn_pub, __func__, NULL, NULL);
97    stream = lsquic_spi_first(&spi);
98    assert(stream == stream_arr[0]);
99    stream = lsquic_spi_next(&spi);
100    assert(stream == stream_arr[1]);
101    stream = lsquic_spi_next(&spi);
102    assert(stream == NULL);
103
104    free_streams(stream_arr, sizeof(stream_arr) / sizeof(stream_arr[0]));
105}
106
107
108static void
109test_different_priorities (int *priority)
110{
111    struct lsquic_streams_tailq streams;
112    lsquic_stream_t *stream;
113    int prio, prev_prio, count, n_streams = 0;
114
115    TAILQ_INIT(&streams);
116
117    for ( ; *priority >= 0; ++priority)
118    {
119        assert(*priority < 256);
120        stream = new_stream(*priority);
121        TAILQ_INSERT_TAIL(&streams, stream, next_send_stream);
122        ++n_streams;
123    }
124
125    lsquic_spi_init(&spi, TAILQ_FIRST(&streams),
126        TAILQ_LAST(&streams, lsquic_streams_tailq),
127        (uintptr_t) &TAILQ_NEXT((lsquic_stream_t *) NULL, next_send_stream),
128        &conn_pub, __func__, NULL, NULL);
129    for (prev_prio = -1, count = 0, stream = lsquic_spi_first(&spi); stream;
130                                        stream = lsquic_spi_next(&spi), ++count)
131    {
132        prio = stream->sm_priority;
133        assert(prio >= prev_prio);
134        if (prio > prev_prio)
135            prev_prio = prio;
136    }
137
138    assert(count == n_streams);
139
140    while ((stream = TAILQ_FIRST(&streams)))
141    {
142        TAILQ_REMOVE(&streams, stream, next_send_stream);
143        free(stream);
144    }
145}
146
147
148struct stream_info
149{
150    uint32_t        stream_id;
151    enum stream_b_flags bflags;
152    unsigned char   prio;
153};
154
155
156const struct stream_info infos1[] = {
157    { 1,                                SMBF_CRITICAL, 0, },
158    { 3,                                SMBF_CRITICAL, 0, },
159    { 5,                                0, 0, },
160    { 7,                                0, 1, },
161    { 127,                              0, 200, },
162};
163
164
165const struct stream_info infos2[] = {
166    { 1,                                SMBF_CRITICAL, 0, },
167    { 3,                                SMBF_CRITICAL, 0, },
168    { 5,                                0, 4, },
169    { 7,                                0, 1, },
170    { 127,                              0, 200, },
171};
172
173
174const struct stream_info infos3[] = {
175    { 0,    0,  0, },
176};
177
178
179struct drop_test
180{
181    const struct stream_info    *infos;
182    unsigned                     n_infos;
183    unsigned                     high_streams;
184};
185
186
187static const struct drop_test drop_tests[] = {
188    { infos1, 5, 0x7, },
189    { infos2, 5, 0x3, },
190    { infos3, 1, 0x0, },
191};
192
193
194static void
195test_drop (const struct drop_test *test)
196{
197
198    struct lsquic_stream stream_arr[20];
199    unsigned seen_mask, n;
200    struct lsquic_streams_tailq streams;
201    lsquic_stream_t *stream;
202    int drop_high;
203
204    TAILQ_INIT(&streams);
205    for (n = 0; n < test->n_infos; ++n)
206    {
207        stream_arr[n].sm_priority = test->infos[n].prio;
208        stream_arr[n].id          = test->infos[n].stream_id;
209        stream_arr[n].sm_bflags   = SMBF_USE_HEADERS | test->infos[n].bflags;
210    }
211
212    for (drop_high = 0; drop_high < 2; ++drop_high)
213    {
214        TAILQ_INIT(&streams);
215        for (n = 0; n < test->n_infos; ++n)
216            TAILQ_INSERT_TAIL(&streams, &stream_arr[n], next_write_stream);
217
218        lsquic_spi_init(&spi, TAILQ_FIRST(&streams),
219            TAILQ_LAST(&streams, lsquic_streams_tailq),
220            (uintptr_t) &TAILQ_NEXT((lsquic_stream_t *) NULL, next_write_stream),
221            &conn_pub, __func__, NULL, NULL);
222
223        if (drop_high)
224            lsquic_spi_drop_high(&spi);
225        else
226            lsquic_spi_drop_non_high(&spi);
227
228        seen_mask = 0;
229        for (stream = lsquic_spi_first(&spi); stream;
230                                            stream = lsquic_spi_next(&spi))
231            seen_mask |= 1 << (stream - stream_arr);
232
233        if (test->n_infos == 1)
234            assert(seen_mask == (1u << test->infos[0].stream_id));
235        else if (drop_high)
236            assert((((1 << test->n_infos) - 1) & ~test->high_streams) == seen_mask);
237        else
238            assert(test->high_streams == seen_mask);
239    }
240}
241
242
243#define MAGIC 0x12312312U
244
245struct my_filter_ctx
246{
247    unsigned magic;
248};
249
250
251static int
252filter_out_odd_priorities (void *ctx, lsquic_stream_t *stream)
253{
254    struct my_filter_ctx *fctx = ctx;
255    assert(fctx->magic == MAGIC);
256    return 0 == (stream->sm_priority & 1);
257}
258
259
260static void
261test_different_priorities_filter_odd (int *priority)
262{
263    struct lsquic_streams_tailq streams;
264    lsquic_stream_t *stream;
265    int prio, prev_prio, count, n_streams = 0;
266
267    TAILQ_INIT(&streams);
268
269    for ( ; *priority >= 0; ++priority)
270    {
271        assert(*priority < 256);
272        stream = new_stream(*priority);
273        TAILQ_INSERT_TAIL(&streams, stream, next_send_stream);
274        ++n_streams;
275    }
276
277    struct my_filter_ctx my_filter_ctx = { MAGIC };
278
279    lsquic_spi_init(&spi, TAILQ_FIRST(&streams),
280        TAILQ_LAST(&streams, lsquic_streams_tailq),
281        (uintptr_t) &TAILQ_NEXT((lsquic_stream_t *) NULL, next_send_stream),
282        &conn_pub, __func__, filter_out_odd_priorities, &my_filter_ctx);
283
284    for (prev_prio = -1, count = 0, stream = lsquic_spi_first(&spi); stream;
285                                        stream = lsquic_spi_next(&spi), ++count)
286    {
287        prio = stream->sm_priority;
288        assert(0 == (prio & 1));
289        assert(prio >= prev_prio);
290        if (prio > prev_prio)
291            prev_prio = prio;
292    }
293
294    assert(count < n_streams);
295
296    while ((stream = TAILQ_FIRST(&streams)))
297    {
298        TAILQ_REMOVE(&streams, stream, next_send_stream);
299        free(stream);
300    }
301}
302
303
304int
305main (int argc, char **argv)
306{
307    lsquic_log_to_fstream(stderr, LLTS_NONE);
308    lsq_log_levels[LSQLM_SPI] = LSQ_LOG_DEBUG;
309
310    test_same_priority(0);
311    test_same_priority(99);
312    test_same_priority(255);
313
314    {
315        int prio[] = { 1, 2, 3, 4, 5, 6, 7, -1 };
316        test_different_priorities(prio);
317    }
318
319    {
320        int prio[] = { 7, 6, 5, 4, 3, 2, 1, -1 };
321        test_different_priorities(prio);
322    }
323
324    {
325        int prio[] = { 7, 100, 80, 1, 0, 0, 20, 23, 255, 30, 2, 101, -1 };
326        test_different_priorities(prio);
327    }
328
329    {
330        int prio[] = { 200, 202, 240, 201, 200, 199, -1 };
331        test_different_priorities(prio);
332    }
333
334    {
335        int prio[] = { 200, 202, 240, 201, 200, 199, -1 };
336        test_different_priorities_filter_odd(prio);
337    }
338
339    unsigned n;
340    for (n = 0; n < sizeof(drop_tests) / sizeof(drop_tests[0]); ++n)
341        test_drop(&drop_tests[n]);
342
343    return 0;
344}
345