1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_hpi.c - implementation of (Extensible) HTTP 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.h"
18#include "lsquic_types.h"
19#include "lsquic_int_types.h"
20#include "lsquic_sfcw.h"
21#include "lsquic_varint.h"
22#include "lsquic_hq.h"
23#include "lsquic_hash.h"
24#include "lsquic_stream.h"
25#include "lsquic_conn_flow.h"
26#include "lsquic_rtt.h"
27#include "lsquic_conn_public.h"
28#include "lsquic_min_heap.h"
29#include "lsquic_mm.h"
30#include "lsquic_hpi.h"
31
32#define LSQUIC_LOGGER_MODULE LSQLM_HPI
33#define LSQUIC_LOG_CONN_ID lsquic_conn_log_cid(iter->hpi_conn_pub->lconn)
34#include "lsquic_logger.h"
35
36#define HPI_DEBUG(fmt, ...) LSQ_DEBUG("%s: " fmt, iter->hpi_name, __VA_ARGS__)
37
38#define NEXT_STREAM(stream, off) \
39    (* (struct lsquic_stream **) ((unsigned char *) (stream) + (off)))
40
41#define MIN(a, b) ((a) < (b) ? (a) : (b))
42
43static void
44add_stream_to_hpi (struct http_prio_iter *iter,
45                                            struct lsquic_stream *new_stream)
46{
47    unsigned prio, incr;
48
49    if (lsquic_stream_is_critical(new_stream))
50    {
51        prio = 0;
52        incr = 1;   /* Place in incremental bucket: these do not need to be
53                     * ordered by stream ID.
54                     */
55    }
56    else
57    {
58        prio = 1 + MIN(new_stream->sm_priority, LSQUIC_MAX_HTTP_URGENCY);
59        incr = !!(new_stream->sm_bflags & SMBF_INCREMENTAL);
60    }
61
62    if (!(iter->hpi_set[incr] & (1u << prio)))
63    {
64        iter->hpi_set[incr] |= 1u << prio;
65        if (0 == incr)
66            iter->hpi_counts[prio] = 0;
67        TAILQ_INIT(&iter->hpi_streams[incr][prio]);
68    }
69
70    if (0 == incr)
71        ++iter->hpi_counts[prio];
72    TAILQ_INSERT_TAIL(&iter->hpi_streams[incr][prio],
73                                                new_stream, next_prio_stream);
74}
75
76
77void
78lsquic_hpi_init (void *iter_p, struct lsquic_stream *first,
79         struct lsquic_stream *last, uintptr_t next_ptr_offset,
80         struct lsquic_conn_public *conn_pub, const char *name,
81         int (*filter)(void *filter_ctx, struct lsquic_stream *),
82         void *filter_ctx)
83{
84    struct http_prio_iter *const iter = iter_p;
85    struct lsquic_stream *stream;
86    unsigned count;
87
88    iter->hpi_conn_pub      = conn_pub;
89    iter->hpi_name          = name ? name : "UNSET";
90    iter->hpi_flags         = 0;
91    iter->hpi_heaped        = 0;
92    iter->hpi_set[0]        = 0;
93    iter->hpi_set[1]        = 0;
94    memset(&iter->hpi_min_heap, 0, sizeof(iter->hpi_min_heap));
95
96    stream = first;
97    count = 0;
98
99    if (filter)
100        while (1)
101        {
102            if (filter(filter_ctx, stream))
103            {
104                add_stream_to_hpi(iter, stream);
105                ++count;
106            }
107            if (stream == last)
108                break;
109            stream = NEXT_STREAM(stream, next_ptr_offset);
110        }
111    else
112        while (1)
113        {
114            add_stream_to_hpi(iter, stream);
115            ++count;
116            if (stream == last)
117                break;
118            stream = NEXT_STREAM(stream, next_ptr_offset);
119        }
120
121    if (count > 2)
122        HPI_DEBUG("initialized; # elems: %u; sets: [ %08X, %08X ]",
123            count, iter->hpi_set[0], iter->hpi_set[1]);
124}
125
126
127/* Number of trailing zeroes */
128static const unsigned char ntz[] = {
129    9, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0,
130    1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0,
131    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0,
132    1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0,
133    3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
134    1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
135    2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
136    1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
137    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0,
138    1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
139    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0,
140    1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
141    3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0,
142    1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
143    2, 0, 1, 0, 8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
144    1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
145    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0,
146    1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0,
147    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0,
148    1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
149    3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0,
150    1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0,
151    2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0,
152    1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
153    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0,
154    1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0,
155    2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0,
156    1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
157    3, 0, 1, 0, 2, 0, 1, 0,
158};
159
160
161/* Sets prio_ and incr_ */
162#define calc_next_prio_and_incr(iter_, prio_, incr_) do {               \
163    prio_ = ntz[iter_->hpi_set[0]];                                     \
164    if (prio_ <= ntz[iter_->hpi_set[1]])                                \
165        incr_ = 0;                                                      \
166    else                                                                \
167    {                                                                   \
168        prio_ = ntz[iter_->hpi_set[1]];                                 \
169        incr_ = 1;                                                      \
170    }                                                                   \
171} while (0)
172
173
174struct lsquic_stream *
175lsquic_hpi_first (void *iter_p)
176{
177    struct http_prio_iter *const iter = iter_p;
178
179    assert(!(iter->hpi_set[0] & ~((1 << N_HPI_PRIORITIES) - 1)));
180    assert(!(iter->hpi_set[1] & ~((1 << N_HPI_PRIORITIES) - 1)));
181
182    return lsquic_hpi_next(iter);
183}
184
185
186static struct lsquic_stream *
187next_incr (struct http_prio_iter *iter, unsigned prio)
188{
189    struct lsquic_stream *stream;
190
191    stream = TAILQ_FIRST(&iter->hpi_streams[1][prio]);
192    TAILQ_REMOVE(&iter->hpi_streams[1][prio], stream, next_prio_stream);
193    if (TAILQ_EMPTY(&iter->hpi_streams[1][prio]))
194        iter->hpi_set[1] &= ~(1u << prio);
195
196    return stream;
197}
198
199
200static void
201free_heap_elems (struct http_prio_iter *iter)
202{
203    if (0 == (iter->hpi_flags & (HPI_MH_4K|HPI_MH_MALLOC)))
204        /* Expected condition: nothing to do */ ;
205    else if (iter->hpi_flags & HPI_MH_4K)
206    {
207        lsquic_mm_put_4k(iter->hpi_conn_pub->mm, iter->hpi_min_heap.mh_elems);
208        iter->hpi_flags &= ~HPI_MH_4K;
209    }
210    else
211    {
212        assert(iter->hpi_flags & HPI_MH_MALLOC);
213        iter->hpi_flags &= ~HPI_MH_MALLOC;
214        free(iter->hpi_min_heap.mh_elems);
215    }
216    iter->hpi_min_heap.mh_elems = NULL;
217}
218
219
220#ifndef NDEBUG
221static int lsquic_hpi_heap_test = (
222                LSQUIC_HPI_HEAP_TEST_STACK_OK | LSQUIC_HPI_HEAP_TEST_4K_OK);
223void
224lsquic_hpi_set_heap_test (int val)
225{
226    lsquic_hpi_heap_test = val;
227}
228#endif
229
230
231static int
232heap_nonincr_bucket (struct http_prio_iter *iter, unsigned prio)
233{
234    struct lsquic_stream *stream;
235    size_t need;
236
237    if (iter->hpi_counts[prio] <= sizeof(iter->hpi_min_heap_els)
238                                        / sizeof(iter->hpi_min_heap_els[0])
239#ifndef NDEBUG
240        && (lsquic_hpi_heap_test & LSQUIC_HPI_HEAP_TEST_STACK_OK)
241#endif
242                                                                           )
243        iter->hpi_min_heap.mh_elems = iter->hpi_min_heap_els;
244    else if (need = iter->hpi_counts[prio] * sizeof(struct min_heap_elem),
245                                                            need <= 0x1000
246#ifndef NDEBUG
247        && (lsquic_hpi_heap_test & LSQUIC_HPI_HEAP_TEST_4K_OK)
248#endif
249                                                                           )
250    {
251        iter->hpi_min_heap.mh_elems = lsquic_mm_get_4k(iter->hpi_conn_pub->mm);
252        if (!iter->hpi_min_heap.mh_elems)
253            return -1;
254        iter->hpi_flags |= HPI_MH_4K;
255    }
256    else
257    {
258        iter->hpi_min_heap.mh_elems = malloc(need);
259        if (!iter->hpi_min_heap.mh_elems)
260            return -1;
261        iter->hpi_flags |= HPI_MH_MALLOC;
262    }
263
264    iter->hpi_min_heap.mh_nalloc = iter->hpi_counts[prio];
265    TAILQ_FOREACH(stream, &iter->hpi_streams[0][prio], next_prio_stream)
266        lsquic_mh_insert(&iter->hpi_min_heap, stream, stream->id);
267    iter->hpi_heaped |= 1u << prio;
268
269    return 0;
270}
271
272
273static struct lsquic_stream *
274next_nonincr (struct http_prio_iter *iter, unsigned prio)
275{
276    struct lsquic_stream *stream;
277
278    if (iter->hpi_heaped & (1u << prio))
279    {
280  pop_stream:
281        stream = lsquic_mh_pop(&iter->hpi_min_heap);
282        if (lsquic_mh_count(&iter->hpi_min_heap) == 0)
283        {
284            free_heap_elems(iter);
285            iter->hpi_set[0] &= ~(1u << prio);
286        }
287    }
288    else if (iter->hpi_counts[prio] > 1)
289    {
290        if (0 == heap_nonincr_bucket(iter, prio))
291            goto pop_stream;
292        /* Handle memory allocation failure by abandoning attempts to order
293         * the streams:
294         */
295        iter->hpi_counts[prio] = 1;
296        goto first_stream;
297    }
298    else
299    {
300  first_stream:
301        stream = TAILQ_FIRST(&iter->hpi_streams[0][prio]);
302        TAILQ_REMOVE(&iter->hpi_streams[0][prio], stream, next_prio_stream);
303        if (TAILQ_EMPTY(&iter->hpi_streams[0][prio]))
304            iter->hpi_set[0] &= ~(1u << prio);
305    }
306
307    return stream;
308}
309
310
311struct lsquic_stream *
312lsquic_hpi_next (void *iter_p)
313{
314    struct http_prio_iter *const iter = iter_p;
315    struct lsquic_stream *stream;
316    unsigned prio, incr;
317
318    calc_next_prio_and_incr(iter, prio, incr);
319
320    if (prio >= N_HPI_PRIORITIES)
321        return NULL;
322
323    if (incr)
324        stream = next_incr(iter, prio);
325    else
326        stream = next_nonincr(iter, prio);
327
328    if (LSQ_LOG_ENABLED(LSQ_LOG_DEBUG))
329        HPI_DEBUG("%s: return stream %"PRIu64", incr: %u, priority %u",
330                                            __func__, stream->id, incr, prio);
331    return stream;
332}
333
334
335#if __GNUC__
336#   define popcount __builtin_popcount
337#else
338static int
339popcount (unsigned v)
340{
341    int count;
342    unsigned i;
343    for (i = 0, count = 0; i < sizeof(v) * 8; ++i)
344        if (v & (1 << i))
345            ++count;
346    return count;
347}
348#endif
349
350
351static void
352hpi_drop_high_or_non_high (void *iter_p, int drop_high)
353{
354    struct http_prio_iter *const iter = iter_p;
355    unsigned prio, incr;
356
357    /* Nothing to drop if there is only one bucket */
358    if (popcount(iter->hpi_set[0]) + popcount(iter->hpi_set[1]) < 2)
359        return;
360
361    calc_next_prio_and_incr(iter, prio, incr);
362
363    if (drop_high)
364        iter->hpi_set[incr] &= ~(1u << prio);
365    else
366    {
367        iter->hpi_set[incr] = 1u << prio;
368        iter->hpi_set[!incr] = 0;
369    }
370}
371
372
373void
374lsquic_hpi_drop_high (void *iter_p)
375{
376    hpi_drop_high_or_non_high(iter_p, 1);
377}
378
379
380void
381lsquic_hpi_drop_non_high (void *iter_p)
382{
383    hpi_drop_high_or_non_high(iter_p, 0);
384}
385
386
387void
388lsquic_hpi_cleanup (void *iter_p)
389{
390    struct http_prio_iter *const iter = iter_p;
391
392    if (iter->hpi_min_heap.mh_elems)
393        free_heap_elems(iter);
394}
395