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