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