lsquic_spi.c revision 229fce07
1229fce07SDmitri Tikhonov/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
250aadb33SDmitri Tikhonov/*
350aadb33SDmitri Tikhonov * lsquic_spi.c - implementation of Stream Priority Iterator.
450aadb33SDmitri Tikhonov */
550aadb33SDmitri Tikhonov
650aadb33SDmitri Tikhonov#include <assert.h>
750aadb33SDmitri Tikhonov#include <inttypes.h>
850aadb33SDmitri Tikhonov#include <stdint.h>
950aadb33SDmitri Tikhonov#include <stdlib.h>
10c51ce338SDmitri Tikhonov#include <string.h>
1150aadb33SDmitri Tikhonov#include <sys/queue.h>
1250aadb33SDmitri Tikhonov#include <sys/types.h>
13461e84d8SAmol Deshpande#ifdef WIN32
14461e84d8SAmol Deshpande#include <vc_compat.h>
15461e84d8SAmol Deshpande#endif
1650aadb33SDmitri Tikhonov
1750aadb33SDmitri Tikhonov#include "lsquic_types.h"
1850aadb33SDmitri Tikhonov#include "lsquic_int_types.h"
1950aadb33SDmitri Tikhonov#include "lsquic_sfcw.h"
2050aadb33SDmitri Tikhonov#include "lsquic_stream.h"
2150aadb33SDmitri Tikhonov#include "lsquic_spi.h"
2250aadb33SDmitri Tikhonov
2350aadb33SDmitri Tikhonov#define LSQUIC_LOGGER_MODULE LSQLM_SPI
2450aadb33SDmitri Tikhonov#define LSQUIC_LOG_CONN_ID iter->spi_cid
2550aadb33SDmitri Tikhonov#include "lsquic_logger.h"
2650aadb33SDmitri Tikhonov
27461e84d8SAmol Deshpande#define SPI_DEBUG(fmt, ...) LSQ_DEBUG("%s: " fmt, iter->spi_name, __VA_ARGS__)
2850aadb33SDmitri Tikhonov
2950aadb33SDmitri Tikhonov#define NEXT_STREAM(stream, off) \
3050aadb33SDmitri Tikhonov    (* (struct lsquic_stream **) ((unsigned char *) (stream) + (off)))
3150aadb33SDmitri Tikhonov
3250aadb33SDmitri Tikhonov
3350aadb33SDmitri Tikhonovstatic void
3450aadb33SDmitri Tikhonovadd_stream_to_spi (struct stream_prio_iter *iter, lsquic_stream_t *stream)
3550aadb33SDmitri Tikhonov{
3650aadb33SDmitri Tikhonov    unsigned set, bit;
3750aadb33SDmitri Tikhonov    set = stream->sm_priority >> 6;
3850aadb33SDmitri Tikhonov    bit = stream->sm_priority & 0x3F;
3950aadb33SDmitri Tikhonov    if (!(iter->spi_set[set] & (1ULL << bit)))
4050aadb33SDmitri Tikhonov    {
4150aadb33SDmitri Tikhonov        iter->spi_set[set] |= 1ULL << bit;
4250aadb33SDmitri Tikhonov        TAILQ_INIT(&iter->spi_streams[ stream->sm_priority ]);
4350aadb33SDmitri Tikhonov    }
4450aadb33SDmitri Tikhonov    TAILQ_INSERT_TAIL(&iter->spi_streams[ stream->sm_priority ],
4550aadb33SDmitri Tikhonov                                                stream, next_prio_stream);
4650aadb33SDmitri Tikhonov}
4750aadb33SDmitri Tikhonov
4850aadb33SDmitri Tikhonov
4950aadb33SDmitri Tikhonovvoid
50c51ce338SDmitri Tikhonovlsquic_spi_init (struct stream_prio_iter *iter, struct lsquic_stream *first,
51c51ce338SDmitri Tikhonov        struct lsquic_stream *last, uintptr_t next_ptr_offset,
52c51ce338SDmitri Tikhonov        enum stream_flags onlist_mask, lsquic_cid_t cid, const char *name)
5350aadb33SDmitri Tikhonov{
5450aadb33SDmitri Tikhonov    struct lsquic_stream *stream;
5550aadb33SDmitri Tikhonov    unsigned count;
5650aadb33SDmitri Tikhonov
5750aadb33SDmitri Tikhonov    iter->spi_cid           = cid;
5850aadb33SDmitri Tikhonov    iter->spi_name          = name ? name : "UNSET";
5950aadb33SDmitri Tikhonov    iter->spi_set[0]        = 0;
6050aadb33SDmitri Tikhonov    iter->spi_set[1]        = 0;
6150aadb33SDmitri Tikhonov    iter->spi_set[2]        = 0;
6250aadb33SDmitri Tikhonov    iter->spi_set[3]        = 0;
6350aadb33SDmitri Tikhonov    iter->spi_onlist_mask   = onlist_mask;
6450aadb33SDmitri Tikhonov    iter->spi_cur_prio      = 0;
6550aadb33SDmitri Tikhonov    iter->spi_prev_stream   = NULL;
6650aadb33SDmitri Tikhonov    iter->spi_next_stream   = NULL;
6750aadb33SDmitri Tikhonov
6850aadb33SDmitri Tikhonov    stream = first;
6950aadb33SDmitri Tikhonov    count = 0;
7050aadb33SDmitri Tikhonov
71c51ce338SDmitri Tikhonov    while (1)
72c51ce338SDmitri Tikhonov    {
73c51ce338SDmitri Tikhonov        add_stream_to_spi(iter, stream);
74c51ce338SDmitri Tikhonov        ++count;
75c51ce338SDmitri Tikhonov        if (stream == last)
76c51ce338SDmitri Tikhonov            break;
77c51ce338SDmitri Tikhonov        stream = NEXT_STREAM(stream, next_ptr_offset);
78c51ce338SDmitri Tikhonov    }
79c51ce338SDmitri Tikhonov
8050aadb33SDmitri Tikhonov    if (count > 2)
8150aadb33SDmitri Tikhonov        SPI_DEBUG("initialized; # elems: %u; sets: [ %016"PRIX64", %016"PRIX64
8250aadb33SDmitri Tikhonov            ", %016"PRIX64", %016"PRIX64" ]", count, iter->spi_set[0],
8350aadb33SDmitri Tikhonov            iter->spi_set[1], iter->spi_set[2], iter->spi_set[3]);
8450aadb33SDmitri Tikhonov}
8550aadb33SDmitri Tikhonov
8650aadb33SDmitri Tikhonov
8750aadb33SDmitri Tikhonovstatic int
8850aadb33SDmitri Tikhonovfind_and_set_lowest_priority (struct stream_prio_iter *iter)
8950aadb33SDmitri Tikhonov{
9050aadb33SDmitri Tikhonov    unsigned set, prio;
9150aadb33SDmitri Tikhonov    uint64_t mask;
9250aadb33SDmitri Tikhonov
9350aadb33SDmitri Tikhonov    for (set = 0, prio = 0; set < 4; ++set, prio += 64)
9450aadb33SDmitri Tikhonov        if (iter->spi_set[ set ])
9550aadb33SDmitri Tikhonov            break;
9650aadb33SDmitri Tikhonov
9750aadb33SDmitri Tikhonov    if (set == 4)
9850aadb33SDmitri Tikhonov    {
9950aadb33SDmitri Tikhonov        //SPI_DEBUG("%s: cannot find any", __func__);
10050aadb33SDmitri Tikhonov        return -1;
10150aadb33SDmitri Tikhonov    }
10250aadb33SDmitri Tikhonov
10350aadb33SDmitri Tikhonov    mask = iter->spi_set[set];
10450aadb33SDmitri Tikhonov    if (!(mask & ((1ULL << 32) - 1))) { prio += 32; mask >>= 32; }
10550aadb33SDmitri Tikhonov    if (!(mask & ((1ULL << 16) - 1))) { prio += 16; mask >>= 16; }
10650aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  8) - 1))) { prio +=  8; mask >>=  8; }
10750aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  4) - 1))) { prio +=  4; mask >>=  4; }
10850aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  2) - 1))) { prio +=  2; mask >>=  2; }
10950aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  1) - 1))) { prio +=  1;              }
11050aadb33SDmitri Tikhonov
11150aadb33SDmitri Tikhonov#ifndef NDEBUG
11250aadb33SDmitri Tikhonov    unsigned bit;
11350aadb33SDmitri Tikhonov    set = prio >> 6;
11450aadb33SDmitri Tikhonov    bit = prio & 0x3F;
11550aadb33SDmitri Tikhonov    assert(iter->spi_set[ set ] & (1ULL << bit));
11650aadb33SDmitri Tikhonov#endif
11750aadb33SDmitri Tikhonov
11850aadb33SDmitri Tikhonov    SPI_DEBUG("%s: prio %u -> %u", __func__, iter->spi_cur_prio, prio);
11950aadb33SDmitri Tikhonov    iter->spi_cur_prio = prio;
12050aadb33SDmitri Tikhonov    return 0;
12150aadb33SDmitri Tikhonov}
12250aadb33SDmitri Tikhonov
12350aadb33SDmitri Tikhonov
12450aadb33SDmitri Tikhonovstatic int
12550aadb33SDmitri Tikhonovfind_and_set_next_priority (struct stream_prio_iter *iter)
12650aadb33SDmitri Tikhonov{
12750aadb33SDmitri Tikhonov    unsigned set, bit, prio;
12850aadb33SDmitri Tikhonov    uint64_t mask;
12950aadb33SDmitri Tikhonov
13050aadb33SDmitri Tikhonov    /* Examine values in the same set first */
13150aadb33SDmitri Tikhonov    set = iter->spi_cur_prio >> 6;
13250aadb33SDmitri Tikhonov    bit = iter->spi_cur_prio & 0x3F;
13350aadb33SDmitri Tikhonov    prio = 64 * set;
13450aadb33SDmitri Tikhonov
13550aadb33SDmitri Tikhonov    if (bit < 63)
13650aadb33SDmitri Tikhonov    {
13750aadb33SDmitri Tikhonov        mask = iter->spi_set[set];
13850aadb33SDmitri Tikhonov        mask &= ~((1ULL << (bit + 1)) - 1);
13950aadb33SDmitri Tikhonov        if (mask)
14050aadb33SDmitri Tikhonov            goto calc_priority;
14150aadb33SDmitri Tikhonov    }
14250aadb33SDmitri Tikhonov
14350aadb33SDmitri Tikhonov    ++set;
14450aadb33SDmitri Tikhonov    prio += 64;
14550aadb33SDmitri Tikhonov    for (; set < 4; ++set, prio += 64)
14650aadb33SDmitri Tikhonov        if (iter->spi_set[ set ])
14750aadb33SDmitri Tikhonov            break;
14850aadb33SDmitri Tikhonov
14950aadb33SDmitri Tikhonov    if (set == 4)
15050aadb33SDmitri Tikhonov    {
15150aadb33SDmitri Tikhonov        //SPI_DEBUG("%s: cannot find any", __func__);
15250aadb33SDmitri Tikhonov        return -1;
15350aadb33SDmitri Tikhonov    }
15450aadb33SDmitri Tikhonov
15550aadb33SDmitri Tikhonov    mask = iter->spi_set[set];
15650aadb33SDmitri Tikhonov
15750aadb33SDmitri Tikhonov  calc_priority:
15850aadb33SDmitri Tikhonov    if (!(mask & ((1ULL << 32) - 1))) { prio += 32; mask >>= 32; }
15950aadb33SDmitri Tikhonov    if (!(mask & ((1ULL << 16) - 1))) { prio += 16; mask >>= 16; }
16050aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  8) - 1))) { prio +=  8; mask >>=  8; }
16150aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  4) - 1))) { prio +=  4; mask >>=  4; }
16250aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  2) - 1))) { prio +=  2; mask >>=  2; }
16350aadb33SDmitri Tikhonov    if (!(mask & ((1ULL <<  1) - 1))) { prio +=  1;              }
16450aadb33SDmitri Tikhonov
16550aadb33SDmitri Tikhonov#ifndef NDEBUG
16650aadb33SDmitri Tikhonov    set = prio >> 6;
16750aadb33SDmitri Tikhonov    bit = prio & 0x3F;
16850aadb33SDmitri Tikhonov    assert(iter->spi_set[ set ] & (1ULL << bit));
16950aadb33SDmitri Tikhonov#endif
17050aadb33SDmitri Tikhonov
17150aadb33SDmitri Tikhonov    SPI_DEBUG("%s: prio %u -> %u", __func__, iter->spi_cur_prio, prio);
17250aadb33SDmitri Tikhonov    iter->spi_cur_prio = prio;
17350aadb33SDmitri Tikhonov    return 0;
17450aadb33SDmitri Tikhonov}
17550aadb33SDmitri Tikhonov
17650aadb33SDmitri Tikhonov
17750aadb33SDmitri Tikhonov/* Each stream returned by the iterator is processed in some fashion.  If,
17850aadb33SDmitri Tikhonov * as a result of this, the stream gets taken off the original list, we
17950aadb33SDmitri Tikhonov * have to follow suit and remove it from the iterator's set of streams.
18050aadb33SDmitri Tikhonov */
18150aadb33SDmitri Tikhonovstatic void
18250aadb33SDmitri Tikhonovmaybe_evict_prev (struct stream_prio_iter *iter)
18350aadb33SDmitri Tikhonov{
18450aadb33SDmitri Tikhonov    unsigned set, bit;
18550aadb33SDmitri Tikhonov
18650aadb33SDmitri Tikhonov    if (0 == (iter->spi_prev_stream->stream_flags & iter->spi_onlist_mask))
18750aadb33SDmitri Tikhonov    {
18850aadb33SDmitri Tikhonov        SPI_DEBUG("evict stream %u", iter->spi_prev_stream->id);
18950aadb33SDmitri Tikhonov        TAILQ_REMOVE(&iter->spi_streams[ iter->spi_prev_prio ],
19050aadb33SDmitri Tikhonov                                    iter->spi_prev_stream, next_prio_stream);
19150aadb33SDmitri Tikhonov        if (TAILQ_EMPTY(&iter->spi_streams[ iter->spi_prev_prio ]))
19250aadb33SDmitri Tikhonov        {
19350aadb33SDmitri Tikhonov            set = iter->spi_prev_prio >> 6;
19450aadb33SDmitri Tikhonov            bit = iter->spi_prev_prio & 0x3F;
19550aadb33SDmitri Tikhonov            iter->spi_set[ set ] &= ~(1ULL << bit);
19650aadb33SDmitri Tikhonov            SPI_DEBUG("priority %u now has no elements", iter->spi_prev_prio);
19750aadb33SDmitri Tikhonov        }
19850aadb33SDmitri Tikhonov        iter->spi_prev_stream = NULL;
19950aadb33SDmitri Tikhonov    }
20050aadb33SDmitri Tikhonov}
20150aadb33SDmitri Tikhonov
20250aadb33SDmitri Tikhonov
20350aadb33SDmitri Tikhonovlsquic_stream_t *
20450aadb33SDmitri Tikhonovlsquic_spi_first (struct stream_prio_iter *iter)
20550aadb33SDmitri Tikhonov{
20650aadb33SDmitri Tikhonov    lsquic_stream_t *stream;
20750aadb33SDmitri Tikhonov    unsigned set, bit;
20850aadb33SDmitri Tikhonov
20950aadb33SDmitri Tikhonov    if (iter->spi_prev_stream)
21050aadb33SDmitri Tikhonov        maybe_evict_prev(iter);
21150aadb33SDmitri Tikhonov
21250aadb33SDmitri Tikhonov    iter->spi_cur_prio = 0;
21350aadb33SDmitri Tikhonov    set = iter->spi_cur_prio >> 6;
21450aadb33SDmitri Tikhonov    bit = iter->spi_cur_prio & 0x3F;
21550aadb33SDmitri Tikhonov
21650aadb33SDmitri Tikhonov    if (!(iter->spi_set[set] & (1ULL << bit)))
21750aadb33SDmitri Tikhonov    {
21850aadb33SDmitri Tikhonov        if (0 != find_and_set_lowest_priority(iter))
21950aadb33SDmitri Tikhonov        {
22050aadb33SDmitri Tikhonov            SPI_DEBUG("%s: return NULL", __func__);
22150aadb33SDmitri Tikhonov            return NULL;
22250aadb33SDmitri Tikhonov        }
22350aadb33SDmitri Tikhonov    }
22450aadb33SDmitri Tikhonov
22550aadb33SDmitri Tikhonov    stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]);
22650aadb33SDmitri Tikhonov    iter->spi_prev_prio   = iter->spi_cur_prio;
22750aadb33SDmitri Tikhonov    iter->spi_prev_stream = stream;
22850aadb33SDmitri Tikhonov    iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream);
22950aadb33SDmitri Tikhonov    if (stream->id != 1 && stream->id != 3)
23050aadb33SDmitri Tikhonov        SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id,
23150aadb33SDmitri Tikhonov                                                            iter->spi_cur_prio);
23250aadb33SDmitri Tikhonov    return stream;
23350aadb33SDmitri Tikhonov}
23450aadb33SDmitri Tikhonov
23550aadb33SDmitri Tikhonov
23650aadb33SDmitri Tikhonovlsquic_stream_t *
23750aadb33SDmitri Tikhonovlsquic_spi_next (struct stream_prio_iter *iter)
23850aadb33SDmitri Tikhonov{
23950aadb33SDmitri Tikhonov    lsquic_stream_t *stream;
24050aadb33SDmitri Tikhonov
24150aadb33SDmitri Tikhonov    if (iter->spi_prev_stream)
24250aadb33SDmitri Tikhonov        maybe_evict_prev(iter);
24350aadb33SDmitri Tikhonov
24450aadb33SDmitri Tikhonov    stream = iter->spi_next_stream;
24550aadb33SDmitri Tikhonov    if (stream)
24650aadb33SDmitri Tikhonov    {
24750aadb33SDmitri Tikhonov        assert(iter->spi_prev_prio == iter->spi_cur_prio);
24850aadb33SDmitri Tikhonov        iter->spi_prev_stream = stream;
24950aadb33SDmitri Tikhonov        iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream);
25050aadb33SDmitri Tikhonov        if (stream->id != 1 && stream->id != 3)
25150aadb33SDmitri Tikhonov            SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id,
25250aadb33SDmitri Tikhonov                                                            iter->spi_cur_prio);
25350aadb33SDmitri Tikhonov        return stream;
25450aadb33SDmitri Tikhonov    }
25550aadb33SDmitri Tikhonov
25650aadb33SDmitri Tikhonov    if (0 != find_and_set_next_priority(iter))
25750aadb33SDmitri Tikhonov    {
25850aadb33SDmitri Tikhonov        //SPI_DEBUG("%s: return NULL", __func__);
25950aadb33SDmitri Tikhonov        return NULL;
26050aadb33SDmitri Tikhonov    }
26150aadb33SDmitri Tikhonov
26250aadb33SDmitri Tikhonov    stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]);
26350aadb33SDmitri Tikhonov    iter->spi_prev_prio   = iter->spi_cur_prio;
26450aadb33SDmitri Tikhonov    iter->spi_prev_stream = stream;
26550aadb33SDmitri Tikhonov    iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream);
26650aadb33SDmitri Tikhonov
267c51ce338SDmitri Tikhonov    if (!lsquic_stream_is_critical(stream))
26850aadb33SDmitri Tikhonov        SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id,
26950aadb33SDmitri Tikhonov                                                        iter->spi_cur_prio);
27050aadb33SDmitri Tikhonov    return stream;
27150aadb33SDmitri Tikhonov}
27250aadb33SDmitri Tikhonov
27350aadb33SDmitri Tikhonov
274c51ce338SDmitri Tikhonovstatic int
275c51ce338SDmitri Tikhonovhave_non_critical_streams (const struct stream_prio_iter *iter)
276c51ce338SDmitri Tikhonov{
277c51ce338SDmitri Tikhonov    const struct lsquic_stream *stream;
278c51ce338SDmitri Tikhonov    TAILQ_FOREACH(stream, &iter->spi_streams[ iter->spi_cur_prio ],
279c51ce338SDmitri Tikhonov                                                        next_prio_stream)
280c51ce338SDmitri Tikhonov        if (!lsquic_stream_is_critical(stream))
281c51ce338SDmitri Tikhonov            return 1;
282c51ce338SDmitri Tikhonov    return 0;
283c51ce338SDmitri Tikhonov}
284c51ce338SDmitri Tikhonov
285c51ce338SDmitri Tikhonov
286c51ce338SDmitri Tikhonovstatic void
287c51ce338SDmitri Tikhonovspi_drop_high_or_non_high (struct stream_prio_iter *iter, int drop_high)
288c51ce338SDmitri Tikhonov{
289c51ce338SDmitri Tikhonov    uint64_t new_set[ sizeof(iter->spi_set) / sizeof(iter->spi_set[0]) ];
290c51ce338SDmitri Tikhonov    unsigned bit, set, n;
291c51ce338SDmitri Tikhonov
292c51ce338SDmitri Tikhonov    memset(new_set, 0, sizeof(new_set));
293c51ce338SDmitri Tikhonov
294c51ce338SDmitri Tikhonov    find_and_set_lowest_priority(iter);
295c51ce338SDmitri Tikhonov    set = iter->spi_cur_prio >> 6;
296c51ce338SDmitri Tikhonov    bit = iter->spi_cur_prio & 0x3F;
297c51ce338SDmitri Tikhonov    new_set[set] |= 1ULL << bit;
298c51ce338SDmitri Tikhonov
299c51ce338SDmitri Tikhonov    if (!have_non_critical_streams(iter))
300c51ce338SDmitri Tikhonov    {
301c51ce338SDmitri Tikhonov        ++iter->spi_cur_prio;
302c51ce338SDmitri Tikhonov        find_and_set_lowest_priority(iter);
303c51ce338SDmitri Tikhonov        set = iter->spi_cur_prio >> 6;
304c51ce338SDmitri Tikhonov        bit = iter->spi_cur_prio & 0x3F;
305c51ce338SDmitri Tikhonov        new_set[set] |= 1ULL << bit;
306c51ce338SDmitri Tikhonov    }
307c51ce338SDmitri Tikhonov
308c51ce338SDmitri Tikhonov    for (n = 0; n < sizeof(new_set) / sizeof(new_set[0]); ++n)
309c51ce338SDmitri Tikhonov        if (drop_high)
310c51ce338SDmitri Tikhonov            iter->spi_set[n] &= ~new_set[n];
311c51ce338SDmitri Tikhonov        else
312c51ce338SDmitri Tikhonov            iter->spi_set[n] = new_set[n];
313c51ce338SDmitri Tikhonov}
314c51ce338SDmitri Tikhonov
315c51ce338SDmitri Tikhonov
316c51ce338SDmitri Tikhonovvoid
317c51ce338SDmitri Tikhonovlsquic_spi_drop_high (struct stream_prio_iter *iter)
318c51ce338SDmitri Tikhonov{
319c51ce338SDmitri Tikhonov    spi_drop_high_or_non_high(iter, 1);
320c51ce338SDmitri Tikhonov}
321c51ce338SDmitri Tikhonov
322c51ce338SDmitri Tikhonov
32350aadb33SDmitri Tikhonovvoid
324c51ce338SDmitri Tikhonovlsquic_spi_drop_non_high (struct stream_prio_iter *iter)
32550aadb33SDmitri Tikhonov{
326c51ce338SDmitri Tikhonov    spi_drop_high_or_non_high(iter, 0);
32750aadb33SDmitri Tikhonov}
328