lsquic_spi.c revision c51ce338 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_spi.c - implementation of Stream Priority Iterator.
4 */
5
6#include <assert.h>
7#include <inttypes.h>
8#include <stdint.h>
9#include <stdlib.h>
10#include <string.h>
11#include <sys/queue.h>
12#include <sys/types.h>
13
14#include "lsquic_types.h"
15#include "lsquic_int_types.h"
16#include "lsquic_sfcw.h"
17#include "lsquic_stream.h"
18#include "lsquic_spi.h"
19
20#define LSQUIC_LOGGER_MODULE LSQLM_SPI
21#define LSQUIC_LOG_CONN_ID iter->spi_cid
22#include "lsquic_logger.h"
23
24#define SPI_DEBUG(fmt, a...) LSQ_DEBUG("%s: " fmt, iter->spi_name, a)
25
26#define NEXT_STREAM(stream, off) \
27    (* (struct lsquic_stream **) ((unsigned char *) (stream) + (off)))
28
29
30static void
31add_stream_to_spi (struct stream_prio_iter *iter, lsquic_stream_t *stream)
32{
33    unsigned set, bit;
34    set = stream->sm_priority >> 6;
35    bit = stream->sm_priority & 0x3F;
36    if (!(iter->spi_set[set] & (1ULL << bit)))
37    {
38        iter->spi_set[set] |= 1ULL << bit;
39        TAILQ_INIT(&iter->spi_streams[ stream->sm_priority ]);
40    }
41    TAILQ_INSERT_TAIL(&iter->spi_streams[ stream->sm_priority ],
42                                                stream, next_prio_stream);
43}
44
45
46void
47lsquic_spi_init (struct stream_prio_iter *iter, struct lsquic_stream *first,
48        struct lsquic_stream *last, uintptr_t next_ptr_offset,
49        enum stream_flags onlist_mask, lsquic_cid_t cid, const char *name)
50{
51    struct lsquic_stream *stream;
52    unsigned count;
53
54    iter->spi_cid           = cid;
55    iter->spi_name          = name ? name : "UNSET";
56    iter->spi_set[0]        = 0;
57    iter->spi_set[1]        = 0;
58    iter->spi_set[2]        = 0;
59    iter->spi_set[3]        = 0;
60    iter->spi_onlist_mask   = onlist_mask;
61    iter->spi_cur_prio      = 0;
62    iter->spi_prev_stream   = NULL;
63    iter->spi_next_stream   = NULL;
64
65    stream = first;
66    count = 0;
67
68    while (1)
69    {
70        add_stream_to_spi(iter, stream);
71        ++count;
72        if (stream == last)
73            break;
74        stream = NEXT_STREAM(stream, next_ptr_offset);
75    }
76
77    if (count > 2)
78        SPI_DEBUG("initialized; # elems: %u; sets: [ %016"PRIX64", %016"PRIX64
79            ", %016"PRIX64", %016"PRIX64" ]", count, iter->spi_set[0],
80            iter->spi_set[1], iter->spi_set[2], iter->spi_set[3]);
81}
82
83
84static int
85find_and_set_lowest_priority (struct stream_prio_iter *iter)
86{
87    unsigned set, prio;
88    uint64_t mask;
89
90    for (set = 0, prio = 0; set < 4; ++set, prio += 64)
91        if (iter->spi_set[ set ])
92            break;
93
94    if (set == 4)
95    {
96        //SPI_DEBUG("%s: cannot find any", __func__);
97        return -1;
98    }
99
100    mask = iter->spi_set[set];
101    if (!(mask & ((1ULL << 32) - 1))) { prio += 32; mask >>= 32; }
102    if (!(mask & ((1ULL << 16) - 1))) { prio += 16; mask >>= 16; }
103    if (!(mask & ((1ULL <<  8) - 1))) { prio +=  8; mask >>=  8; }
104    if (!(mask & ((1ULL <<  4) - 1))) { prio +=  4; mask >>=  4; }
105    if (!(mask & ((1ULL <<  2) - 1))) { prio +=  2; mask >>=  2; }
106    if (!(mask & ((1ULL <<  1) - 1))) { prio +=  1;              }
107
108#ifndef NDEBUG
109    unsigned bit;
110    set = prio >> 6;
111    bit = prio & 0x3F;
112    assert(iter->spi_set[ set ] & (1ULL << bit));
113#endif
114
115    SPI_DEBUG("%s: prio %u -> %u", __func__, iter->spi_cur_prio, prio);
116    iter->spi_cur_prio = prio;
117    return 0;
118}
119
120
121static int
122find_and_set_next_priority (struct stream_prio_iter *iter)
123{
124    unsigned set, bit, prio;
125    uint64_t mask;
126
127    /* Examine values in the same set first */
128    set = iter->spi_cur_prio >> 6;
129    bit = iter->spi_cur_prio & 0x3F;
130    prio = 64 * set;
131
132    if (bit < 63)
133    {
134        mask = iter->spi_set[set];
135        mask &= ~((1ULL << (bit + 1)) - 1);
136        if (mask)
137            goto calc_priority;
138    }
139
140    ++set;
141    prio += 64;
142    for (; set < 4; ++set, prio += 64)
143        if (iter->spi_set[ set ])
144            break;
145
146    if (set == 4)
147    {
148        //SPI_DEBUG("%s: cannot find any", __func__);
149        return -1;
150    }
151
152    mask = iter->spi_set[set];
153
154  calc_priority:
155    if (!(mask & ((1ULL << 32) - 1))) { prio += 32; mask >>= 32; }
156    if (!(mask & ((1ULL << 16) - 1))) { prio += 16; mask >>= 16; }
157    if (!(mask & ((1ULL <<  8) - 1))) { prio +=  8; mask >>=  8; }
158    if (!(mask & ((1ULL <<  4) - 1))) { prio +=  4; mask >>=  4; }
159    if (!(mask & ((1ULL <<  2) - 1))) { prio +=  2; mask >>=  2; }
160    if (!(mask & ((1ULL <<  1) - 1))) { prio +=  1;              }
161
162#ifndef NDEBUG
163    set = prio >> 6;
164    bit = prio & 0x3F;
165    assert(iter->spi_set[ set ] & (1ULL << bit));
166#endif
167
168    SPI_DEBUG("%s: prio %u -> %u", __func__, iter->spi_cur_prio, prio);
169    iter->spi_cur_prio = prio;
170    return 0;
171}
172
173
174/* Each stream returned by the iterator is processed in some fashion.  If,
175 * as a result of this, the stream gets taken off the original list, we
176 * have to follow suit and remove it from the iterator's set of streams.
177 */
178static void
179maybe_evict_prev (struct stream_prio_iter *iter)
180{
181    unsigned set, bit;
182
183    if (0 == (iter->spi_prev_stream->stream_flags & iter->spi_onlist_mask))
184    {
185        SPI_DEBUG("evict stream %u", iter->spi_prev_stream->id);
186        TAILQ_REMOVE(&iter->spi_streams[ iter->spi_prev_prio ],
187                                    iter->spi_prev_stream, next_prio_stream);
188        if (TAILQ_EMPTY(&iter->spi_streams[ iter->spi_prev_prio ]))
189        {
190            set = iter->spi_prev_prio >> 6;
191            bit = iter->spi_prev_prio & 0x3F;
192            iter->spi_set[ set ] &= ~(1ULL << bit);
193            SPI_DEBUG("priority %u now has no elements", iter->spi_prev_prio);
194        }
195        iter->spi_prev_stream = NULL;
196    }
197}
198
199
200lsquic_stream_t *
201lsquic_spi_first (struct stream_prio_iter *iter)
202{
203    lsquic_stream_t *stream;
204    unsigned set, bit;
205
206    if (iter->spi_prev_stream)
207        maybe_evict_prev(iter);
208
209    iter->spi_cur_prio = 0;
210    set = iter->spi_cur_prio >> 6;
211    bit = iter->spi_cur_prio & 0x3F;
212
213    if (!(iter->spi_set[set] & (1ULL << bit)))
214    {
215        if (0 != find_and_set_lowest_priority(iter))
216        {
217            SPI_DEBUG("%s: return NULL", __func__);
218            return NULL;
219        }
220    }
221
222    stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]);
223    iter->spi_prev_prio   = iter->spi_cur_prio;
224    iter->spi_prev_stream = stream;
225    iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream);
226    if (stream->id != 1 && stream->id != 3)
227        SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id,
228                                                            iter->spi_cur_prio);
229    return stream;
230}
231
232
233lsquic_stream_t *
234lsquic_spi_next (struct stream_prio_iter *iter)
235{
236    lsquic_stream_t *stream;
237
238    if (iter->spi_prev_stream)
239        maybe_evict_prev(iter);
240
241    stream = iter->spi_next_stream;
242    if (stream)
243    {
244        assert(iter->spi_prev_prio == iter->spi_cur_prio);
245        iter->spi_prev_stream = stream;
246        iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream);
247        if (stream->id != 1 && stream->id != 3)
248            SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id,
249                                                            iter->spi_cur_prio);
250        return stream;
251    }
252
253    if (0 != find_and_set_next_priority(iter))
254    {
255        //SPI_DEBUG("%s: return NULL", __func__);
256        return NULL;
257    }
258
259    stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]);
260    iter->spi_prev_prio   = iter->spi_cur_prio;
261    iter->spi_prev_stream = stream;
262    iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream);
263
264    if (!lsquic_stream_is_critical(stream))
265        SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id,
266                                                        iter->spi_cur_prio);
267    return stream;
268}
269
270
271static int
272have_non_critical_streams (const struct stream_prio_iter *iter)
273{
274    const struct lsquic_stream *stream;
275    TAILQ_FOREACH(stream, &iter->spi_streams[ iter->spi_cur_prio ],
276                                                        next_prio_stream)
277        if (!lsquic_stream_is_critical(stream))
278            return 1;
279    return 0;
280}
281
282
283static void
284spi_drop_high_or_non_high (struct stream_prio_iter *iter, int drop_high)
285{
286    uint64_t new_set[ sizeof(iter->spi_set) / sizeof(iter->spi_set[0]) ];
287    unsigned bit, set, n;
288
289    memset(new_set, 0, sizeof(new_set));
290
291    find_and_set_lowest_priority(iter);
292    set = iter->spi_cur_prio >> 6;
293    bit = iter->spi_cur_prio & 0x3F;
294    new_set[set] |= 1ULL << bit;
295
296    if (!have_non_critical_streams(iter))
297    {
298        ++iter->spi_cur_prio;
299        find_and_set_lowest_priority(iter);
300        set = iter->spi_cur_prio >> 6;
301        bit = iter->spi_cur_prio & 0x3F;
302        new_set[set] |= 1ULL << bit;
303    }
304
305    for (n = 0; n < sizeof(new_set) / sizeof(new_set[0]); ++n)
306        if (drop_high)
307            iter->spi_set[n] &= ~new_set[n];
308        else
309            iter->spi_set[n] = new_set[n];
310}
311
312
313void
314lsquic_spi_drop_high (struct stream_prio_iter *iter)
315{
316    spi_drop_high_or_non_high(iter, 1);
317}
318
319
320void
321lsquic_spi_drop_non_high (struct stream_prio_iter *iter)
322{
323    spi_drop_high_or_non_high(iter, 0);
324}
325