Coverage Report

Created: 2025-06-22 06:19

/src/h2o/lib/http2/scheduler.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright (c) 2015 DeNA Co., Ltd.
3
 *
4
 * Permission is hereby granted, free of charge, to any person obtaining a copy
5
 * of this software and associated documentation files (the "Software"), to
6
 * deal in the Software without restriction, including without limitation the
7
 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
8
 * sell copies of the Software, and to permit persons to whom the Software is
9
 * furnished to do so, subject to the following conditions:
10
 *
11
 * The above copyright notice and this permission notice shall be included in
12
 * all copies or substantial portions of the Software.
13
 *
14
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
20
 * IN THE SOFTWARE.
21
 */
22
#include "h2o.h"
23
#include "h2o/http2_internal.h"
24
#include "h2o/http2_scheduler.h"
25
26
struct st_h2o_http2_scheduler_queue_t {
27
    uint64_t bits;
28
    size_t offset;
29
    h2o_linklist_t anchors[64];
30
    h2o_linklist_t anchor257;
31
};
32
33
static void queue_init(h2o_http2_scheduler_queue_t *queue)
34
4.52k
{
35
4.52k
    size_t i;
36
4.52k
    queue->bits = 0;
37
4.52k
    queue->offset = 0;
38
293k
    for (i = 0; i != sizeof(queue->anchors) / sizeof(queue->anchors[0]); ++i)
39
289k
        h2o_linklist_init_anchor(queue->anchors + i);
40
4.52k
    h2o_linklist_init_anchor(&queue->anchor257);
41
4.52k
}
42
43
static int queue_is_empty(h2o_http2_scheduler_queue_t *queue)
44
7.05k
{
45
7.05k
    return queue->bits == 0 && h2o_linklist_is_empty(&queue->anchor257);
46
7.05k
}
47
48
static void queue_set(h2o_http2_scheduler_queue_t *queue, h2o_http2_scheduler_queue_node_t *node, uint16_t weight)
49
48.6k
{
50
    /* holds 257 entries of offsets (multiplied by 65536) where nodes with weights between 1..257 should go into
51
     * each entry (except for weight=256) is calculated as: round(N / weight), where N is adjusted so that the
52
     * value would become 63*65536 for weight=0.
53
     * weight=257 is used internally to send data before any of the streams being pulled, and therefore has the offset set to zero.
54
     */
55
48.6k
    static const unsigned OFFSET_TABLE[] = {
56
48.6k
        4128768, 2064384, 1376256, 1032192, 825754, 688128, 589824, 516096, 458752, 412877, 375343, 344064, 317598, 294912, 275251,
57
48.6k
        258048,  242869,  229376,  217304,  206438, 196608, 187671, 179512, 172032, 165151, 158799, 152917, 147456, 142371, 137626,
58
48.6k
        133186,  129024,  125114,  121434,  117965, 114688, 111588, 108652, 105866, 103219, 100702, 98304,  96018,  93836,  91750,
59
48.6k
        89756,   87846,   86016,   84261,   82575,  80956,  79399,  77901,  76459,  75069,  73728,  72435,  71186,  69979,  68813,
60
48.6k
        67685,   66593,   65536,   64512,   63520,  62557,  61623,  60717,  59837,  58982,  58152,  57344,  56558,  55794,  55050,
61
48.6k
        54326,   53620,   52933,   52263,   51610,  50972,  50351,  49744,  49152,  48574,  48009,  47457,  46918,  46391,  45875,
62
48.6k
        45371,   44878,   44395,   43923,   43461,  43008,  42565,  42130,  41705,  41288,  40879,  40478,  40085,  39700,  39322,
63
48.6k
        38951,   38587,   38229,   37879,   37534,  37196,  36864,  36538,  36217,  35902,  35593,  35289,  34990,  34696,  34406,
64
48.6k
        34122,   33842,   33567,   33297,   33030,  32768,  32510,  32256,  32006,  31760,  31517,  31279,  31043,  30812,  30583,
65
48.6k
        30359,   30137,   29919,   29703,   29491,  29282,  29076,  28873,  28672,  28474,  28279,  28087,  27897,  27710,  27525,
66
48.6k
        27343,   27163,   26985,   26810,   26637,  26466,  26298,  26131,  25967,  25805,  25645,  25486,  25330,  25175,  25023,
67
48.6k
        24872,   24723,   24576,   24431,   24287,  24145,  24004,  23866,  23729,  23593,  23459,  23326,  23195,  23066,  22938,
68
48.6k
        22811,   22686,   22562,   22439,   22318,  22198,  22079,  21962,  21845,  21730,  21617,  21504,  21393,  21282,  21173,
69
48.6k
        21065,   20958,   20852,   20748,   20644,  20541,  20439,  20339,  20239,  20140,  20043,  19946,  19850,  19755,  19661,
70
48.6k
        19568,   19475,   19384,   19293,   19204,  19115,  19027,  18939,  18853,  18767,  18682,  18598,  18515,  18432,  18350,
71
48.6k
        18269,   18188,   18109,   18030,   17951,  17873,  17796,  17720,  17644,  17569,  17495,  17421,  17348,  17275,  17203,
72
48.6k
        17132,   17061,   16991,   16921,   16852,  16784,  16716,  16648,  16581,  16515,  16449,  16384,  16319,  16255,  16191,
73
48.6k
        16128,   0};
74
75
48.6k
    assert(!h2o_linklist_is_linked(&node->_link));
76
77
48.6k
    if (weight > 256) {
78
79
0
        h2o_linklist_insert(&queue->anchor257, &node->_link);
80
81
48.6k
    } else {
82
83
48.6k
        assert(1 <= weight);
84
85
48.6k
        size_t offset = OFFSET_TABLE[weight - 1] + node->_deficit;
86
48.6k
        node->_deficit = offset % 65536;
87
48.6k
        offset = offset / 65536;
88
89
48.6k
        queue->bits |= 1ULL << (sizeof(queue->bits) * 8 - 1 - offset);
90
48.6k
        h2o_linklist_insert(queue->anchors + (queue->offset + offset) % (sizeof(queue->anchors) / sizeof(queue->anchors[0])),
91
48.6k
                            &node->_link);
92
48.6k
    }
93
48.6k
}
94
95
static void queue_unset(h2o_http2_scheduler_queue_node_t *node)
96
41.3k
{
97
41.3k
    assert(h2o_linklist_is_linked(&node->_link));
98
41.3k
    h2o_linklist_unlink(&node->_link);
99
41.3k
}
100
101
static h2o_http2_scheduler_queue_node_t *queue_pop(h2o_http2_scheduler_queue_t *queue)
102
7.59k
{
103
7.59k
    if (!h2o_linklist_is_empty(&queue->anchor257)) {
104
0
        h2o_http2_scheduler_queue_node_t *node =
105
0
            H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_queue_node_t, _link, queue->anchor257.next);
106
0
        h2o_linklist_unlink(&node->_link);
107
0
        return node;
108
0
    }
109
110
8.50k
    while (queue->bits != 0) {
111
8.21k
        int zeroes = __builtin_clzll(queue->bits);
112
8.21k
        queue->bits <<= zeroes;
113
8.21k
        queue->offset = (queue->offset + zeroes) % (sizeof(queue->anchors) / sizeof(queue->anchors[0]));
114
8.21k
        if (!h2o_linklist_is_empty(queue->anchors + queue->offset)) {
115
7.30k
            h2o_http2_scheduler_queue_node_t *node =
116
7.30k
                H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_queue_node_t, _link, queue->anchors[queue->offset].next);
117
7.30k
            h2o_linklist_unlink(&node->_link);
118
7.30k
            if (h2o_linklist_is_empty(queue->anchors + queue->offset))
119
4.88k
                queue->bits &= (1ULL << (sizeof(queue->bits) * 8 - 1)) - 1;
120
7.30k
            return node;
121
7.30k
        }
122
906
        queue->bits &= (1ULL << (sizeof(queue->bits) * 8 - 1)) - 1;
123
906
    }
124
291
    return NULL;
125
7.59k
}
126
127
static void init_node(h2o_http2_scheduler_node_t *node, h2o_http2_scheduler_node_t *parent)
128
52.3k
{
129
52.3k
    *node = (h2o_http2_scheduler_node_t){parent};
130
52.3k
    h2o_linklist_init_anchor(&node->_all_refs);
131
52.3k
}
132
133
static h2o_http2_scheduler_queue_t *get_queue(h2o_http2_scheduler_node_t *node)
134
45.0k
{
135
45.0k
    if (node->_queue == NULL) {
136
4.52k
        node->_queue = h2o_mem_alloc(sizeof(*node->_queue));
137
4.52k
        queue_init(node->_queue);
138
4.52k
    }
139
45.0k
    return node->_queue;
140
45.0k
}
141
142
static void incr_active_cnt(h2o_http2_scheduler_node_t *node)
143
51.3k
{
144
51.3k
    h2o_http2_scheduler_openref_t *ref;
145
146
    /* do nothing if node is the root */
147
51.3k
    if (node->_parent == NULL)
148
11.2k
        return;
149
150
40.1k
    ref = (h2o_http2_scheduler_openref_t *)node;
151
40.1k
    if (++ref->_active_cnt != 1)
152
4.23k
        return;
153
    /* just changed to active */
154
35.8k
    queue_set(get_queue(ref->node._parent), &ref->_queue_node, ref->weight);
155
    /* delegate the change towards root */
156
35.8k
    incr_active_cnt(ref->node._parent);
157
35.8k
}
158
159
static void decr_active_cnt(h2o_http2_scheduler_node_t *node)
160
47.4k
{
161
47.4k
    h2o_http2_scheduler_openref_t *ref;
162
163
    /* do nothing if node is the root */
164
47.4k
    if (node->_parent == NULL)
165
11.2k
        return;
166
167
36.2k
    ref = (h2o_http2_scheduler_openref_t *)node;
168
36.2k
    if (--ref->_active_cnt != 0)
169
4.15k
        return;
170
    /* just changed to inactive */
171
32.0k
    queue_unset(&ref->_queue_node);
172
    /* delegate the change towards root */
173
32.0k
    decr_active_cnt(ref->node._parent);
174
32.0k
}
175
176
static void convert_to_exclusive(h2o_http2_scheduler_node_t *parent, h2o_http2_scheduler_openref_t *added)
177
8.41k
{
178
16.0k
    while (!h2o_linklist_is_empty(&parent->_all_refs)) {
179
16.0k
        h2o_http2_scheduler_openref_t *child_ref =
180
16.0k
            H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, parent->_all_refs.next);
181
16.0k
        if (child_ref == added) {
182
            /* precond: the added node should exist as the last item within parent */
183
8.41k
            assert(parent->_all_refs.prev == &added->_all_link);
184
8.41k
            break;
185
8.41k
        }
186
7.65k
        h2o_http2_scheduler_rebind(child_ref, &added->node, h2o_http2_scheduler_get_weight(child_ref), 0);
187
7.65k
    }
188
8.41k
}
189
190
void h2o_http2_scheduler_open(h2o_http2_scheduler_openref_t *ref, h2o_http2_scheduler_node_t *parent, uint16_t weight,
191
                              int exclusive)
192
23.3k
{
193
23.3k
    init_node(&ref->node, parent);
194
23.3k
    ref->weight = weight;
195
23.3k
    ref->_all_link = (h2o_linklist_t){NULL};
196
23.3k
    ref->_active_cnt = 0;
197
23.3k
    ref->_self_is_active = 0;
198
23.3k
    ref->_queue_node = (h2o_http2_scheduler_queue_node_t){{NULL}};
199
23.3k
    ref->_is_relocated = 0;
200
201
23.3k
    h2o_linklist_insert(&parent->_all_refs, &ref->_all_link);
202
203
23.3k
    if (exclusive)
204
4.58k
        convert_to_exclusive(parent, ref);
205
23.3k
}
206
207
void h2o_http2_scheduler_close(h2o_http2_scheduler_openref_t *ref)
208
23.3k
{
209
23.3k
    assert(h2o_http2_scheduler_is_open(ref));
210
211
    /* move dependents to parent */
212
23.3k
    if (!h2o_linklist_is_empty(&ref->node._all_refs)) {
213
        /* proportionally distribute the weight to the children (draft-16 5.3.4) */
214
4.19k
        uint32_t total_weight = 0, factor;
215
4.19k
        h2o_linklist_t *link;
216
11.4k
        for (link = ref->node._all_refs.next; link != &ref->node._all_refs; link = link->next) {
217
7.21k
            h2o_http2_scheduler_openref_t *child_ref = H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, link);
218
7.21k
            total_weight += child_ref->weight;
219
7.21k
        }
220
4.19k
        assert(total_weight != 0);
221
4.19k
        factor = ((uint32_t)ref->weight * 65536 + total_weight / 2) / total_weight;
222
7.21k
        do {
223
7.21k
            h2o_http2_scheduler_openref_t *child_ref =
224
7.21k
                H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, ref->node._all_refs.next);
225
7.21k
            uint16_t weight = (child_ref->weight * factor / 32768 + 1) / 2;
226
7.21k
            if (weight < 1)
227
989
                weight = 1;
228
6.23k
            else if (weight > 256)
229
0
                weight = 256;
230
7.21k
            h2o_http2_scheduler_rebind(child_ref, ref->node._parent, weight, 0);
231
7.21k
        } while (!h2o_linklist_is_empty(&ref->node._all_refs));
232
4.19k
    }
233
234
23.3k
    free(ref->node._queue);
235
23.3k
    ref->node._queue = NULL;
236
237
    /* detach self */
238
23.3k
    h2o_linklist_unlink(&ref->_all_link);
239
23.3k
    if (ref->_self_is_active) {
240
0
        assert(ref->_active_cnt == 1);
241
0
        queue_unset(&ref->_queue_node);
242
0
        decr_active_cnt(ref->node._parent);
243
23.3k
    } else {
244
23.3k
        assert(ref->_active_cnt == 0);
245
23.3k
    }
246
23.3k
}
247
248
void h2o_http2_scheduler_relocate(h2o_http2_scheduler_openref_t *dst, h2o_http2_scheduler_openref_t *src)
249
23.3k
{
250
23.3k
    init_node(&dst->node, src->node._parent);
251
23.3k
    dst->weight = src->weight;
252
23.3k
    dst->_all_link = (h2o_linklist_t){NULL};
253
23.3k
    dst->_active_cnt = src->_active_cnt;
254
23.3k
    dst->_self_is_active = src->_self_is_active;
255
23.3k
    dst->_queue_node._link = (h2o_linklist_t){NULL};
256
23.3k
    dst->_queue_node._deficit = src->_queue_node._deficit;
257
23.3k
    dst->_is_relocated = 1;
258
259
    /* update refs from descendants */
260
23.3k
    if (!h2o_linklist_is_empty(&src->node._all_refs)) {
261
4.44k
        h2o_linklist_t *link;
262
        /* update back reference */
263
11.2k
        for (link = src->node._all_refs.next; link != &src->node._all_refs; link = link->next) {
264
6.85k
            h2o_http2_scheduler_openref_t *child = H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, link);
265
6.85k
            assert(child->node._parent == &src->node);
266
6.85k
            child->node._parent = &dst->node;
267
6.85k
        }
268
        /* attach the list to dst */
269
4.44k
        h2o_linklist_insert_list(&dst->node._all_refs, &src->node._all_refs);
270
        /* node._queue */
271
4.44k
        dst->node._queue = src->node._queue;
272
18.8k
    } else {
273
18.8k
        free(src->node._queue);
274
18.8k
    }
275
23.3k
    src->node._queue = NULL;
276
277
    /* swap all_link */
278
23.3k
    h2o_linklist_insert(&src->_all_link, &dst->_all_link);
279
23.3k
    h2o_linklist_unlink(&src->_all_link);
280
281
    /* swap _queue_node._link */
282
23.3k
    if (h2o_linklist_is_linked(&src->_queue_node._link)) {
283
5.23k
        h2o_linklist_insert(&src->_queue_node._link, &dst->_queue_node._link);
284
5.23k
        h2o_linklist_unlink(&src->_queue_node._link);
285
5.23k
    }
286
23.3k
}
287
288
static void do_rebind(h2o_http2_scheduler_openref_t *ref, h2o_http2_scheduler_node_t *new_parent, int exclusive)
289
20.3k
{
290
    /* rebind _all_link */
291
20.3k
    h2o_linklist_unlink(&ref->_all_link);
292
20.3k
    h2o_linklist_insert(&new_parent->_all_refs, &ref->_all_link);
293
    /* rebind to WRR (as well as adjust active_cnt) */
294
20.3k
    if (ref->_active_cnt != 0) {
295
9.21k
        queue_unset(&ref->_queue_node);
296
9.21k
        queue_set(get_queue(new_parent), &ref->_queue_node, ref->weight);
297
9.21k
        decr_active_cnt(ref->node._parent);
298
9.21k
        incr_active_cnt(new_parent);
299
9.21k
    }
300
    /* update the backlinks */
301
20.3k
    ref->node._parent = new_parent;
302
303
20.3k
    if (exclusive)
304
3.82k
        convert_to_exclusive(new_parent, ref);
305
20.3k
}
306
307
void h2o_http2_scheduler_rebind(h2o_http2_scheduler_openref_t *ref, h2o_http2_scheduler_node_t *new_parent, uint16_t weight,
308
                                int exclusive)
309
24.0k
{
310
24.0k
    assert(h2o_http2_scheduler_is_open(ref));
311
24.0k
    assert(&ref->node != new_parent);
312
24.0k
    assert(1 <= weight);
313
24.0k
    assert(weight <= 257);
314
315
    /* do nothing if there'd be no change at all */
316
24.0k
    if (ref->node._parent == new_parent && ref->weight == weight && !exclusive)
317
4.48k
        return;
318
319
19.5k
    ref->weight = weight;
320
321
    /* if new_parent is dependent to ref, make new_parent a sibling of ref before applying the final transition (see draft-16
322
       5.3.3) */
323
19.5k
    if (!h2o_linklist_is_empty(&ref->node._all_refs)) {
324
8.64k
        h2o_http2_scheduler_node_t *t;
325
20.5k
        for (t = new_parent; t->_parent != NULL; t = t->_parent) {
326
12.6k
            if (t->_parent == &ref->node) {
327
                /* quoting the spec: "The moved dependency retains its weight." */
328
722
                h2o_http2_scheduler_openref_t *new_parent_ref = (void *)new_parent;
329
722
                do_rebind(new_parent_ref, ref->node._parent, 0);
330
722
                break;
331
722
            }
332
12.6k
        }
333
8.64k
    }
334
335
19.5k
    do_rebind(ref, new_parent, exclusive);
336
19.5k
}
337
338
void h2o_http2_scheduler_init(h2o_http2_scheduler_node_t *root)
339
5.75k
{
340
5.75k
    init_node(root, NULL);
341
5.75k
}
342
343
void h2o_http2_scheduler_dispose(h2o_http2_scheduler_node_t *root)
344
5.25k
{
345
5.25k
    free(root->_queue);
346
5.25k
    root->_queue = NULL;
347
5.25k
}
348
349
void h2o_http2_scheduler_deactivate(h2o_http2_scheduler_openref_t *ref)
350
23.3k
{
351
23.3k
    if (!ref->_self_is_active)
352
20.9k
        return;
353
2.37k
    ref->_self_is_active = 0;
354
2.37k
    decr_active_cnt(&ref->node);
355
2.37k
}
356
357
void h2o_http2_scheduler_activate(h2o_http2_scheduler_openref_t *ref)
358
6.32k
{
359
6.32k
    if (ref->_self_is_active)
360
103
        return;
361
6.22k
    ref->_self_is_active = 1;
362
6.22k
    incr_active_cnt(&ref->node);
363
6.22k
}
364
365
static int proceed(h2o_http2_scheduler_node_t *node, h2o_http2_scheduler_run_cb cb, void *cb_arg)
366
4.14k
{
367
7.59k
Redo:
368
7.59k
    if (node->_queue == NULL)
369
0
        return 0;
370
371
7.59k
    h2o_http2_scheduler_queue_node_t *drr_node = queue_pop(node->_queue);
372
7.59k
    if (drr_node == NULL)
373
291
        return 0;
374
375
7.30k
    h2o_http2_scheduler_openref_t *ref = H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _queue_node, drr_node);
376
377
7.30k
    if (!ref->_self_is_active) {
378
        /* run the children (manually-unrolled tail recursion) */
379
3.45k
        queue_set(node->_queue, &ref->_queue_node, ref->weight);
380
3.45k
        node = &ref->node;
381
3.45k
        goto Redo;
382
3.45k
    }
383
3.84k
    assert(ref->_active_cnt != 0);
384
385
    /* call the callbacks */
386
3.84k
    int still_is_active, bail_out = cb(ref, &still_is_active, cb_arg);
387
3.84k
    if (still_is_active) {
388
0
        queue_set(node->_queue, &ref->_queue_node, ref->weight);
389
3.84k
    } else {
390
3.84k
        ref->_self_is_active = 0;
391
3.84k
        if (--ref->_active_cnt != 0) {
392
75
            queue_set(node->_queue, &ref->_queue_node, ref->weight);
393
3.77k
        } else if (ref->node._parent != NULL) {
394
3.77k
            decr_active_cnt(ref->node._parent);
395
3.77k
        }
396
3.84k
    }
397
398
3.84k
    return bail_out;
399
3.84k
}
400
401
int h2o_http2_scheduler_run(h2o_http2_scheduler_node_t *root, h2o_http2_scheduler_run_cb cb, void *cb_arg)
402
4.32k
{
403
4.32k
    if (root->_queue != NULL) {
404
5.63k
        while (!queue_is_empty(root->_queue)) {
405
4.14k
            int bail_out = proceed(root, cb, cb_arg);
406
4.14k
            if (bail_out)
407
0
                return bail_out;
408
4.14k
        }
409
1.49k
    }
410
4.32k
    return 0;
411
4.32k
}
412
413
int h2o_http2_scheduler_is_active(h2o_http2_scheduler_node_t *root)
414
4.15k
{
415
4.15k
    return root->_queue != NULL && !queue_is_empty(root->_queue);
416
4.15k
}
417
418
h2o_http2_scheduler_node_t *h2o_http2_scheduler_find_parent_by_weight(h2o_http2_scheduler_node_t *root, uint16_t new_weight)
419
1.42k
{
420
1.42k
    h2o_http2_scheduler_node_t *node = root;
421
422
10.0k
    while (!h2o_linklist_is_empty(&node->_all_refs)) {
423
        /* This function (for now) assumes Chromium's dependency tree -- each stream shall have
424
         * no more than one child. Thus it only looks at the first child (`_all_refs.next`) */
425
9.00k
        h2o_http2_scheduler_openref_t *child_ref =
426
9.00k
            H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, node->_all_refs.next);
427
9.00k
        if (!child_ref->_is_relocated && child_ref->weight < new_weight) {
428
            /* found a new parent */
429
358
            break;
430
358
        }
431
8.64k
        node = &child_ref->node;
432
8.64k
    }
433
1.42k
    return node;
434
1.42k
}