summaryrefslogtreecommitdiffstats
path: root/debian/vendor-h2o/lib/http2/scheduler.c
diff options
context:
space:
mode:
Diffstat (limited to 'debian/vendor-h2o/lib/http2/scheduler.c')
-rw-r--r--debian/vendor-h2o/lib/http2/scheduler.c365
1 files changed, 0 insertions, 365 deletions
diff --git a/debian/vendor-h2o/lib/http2/scheduler.c b/debian/vendor-h2o/lib/http2/scheduler.c
deleted file mode 100644
index 0ea7e45..0000000
--- a/debian/vendor-h2o/lib/http2/scheduler.c
+++ /dev/null
@@ -1,365 +0,0 @@
-/*
- * Copyright (c) 2015 DeNA Co., Ltd.
- *
- * Permission is hereby granted, free of charge, to any person obtaining a copy
- * of this software and associated documentation files (the "Software"), to
- * deal in the Software without restriction, including without limitation the
- * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
- * sell copies of the Software, and to permit persons to whom the Software is
- * furnished to do so, subject to the following conditions:
- *
- * The above copyright notice and this permission notice shall be included in
- * all copies or substantial portions of the Software.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
- * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
- * IN THE SOFTWARE.
- */
-#include "h2o.h"
-#include "h2o/http2_scheduler.h"
-
-struct st_h2o_http2_scheduler_queue_t {
- uint64_t bits;
- size_t offset;
- h2o_linklist_t anchors[64];
- h2o_linklist_t anchor257;
-};
-
-static void queue_init(h2o_http2_scheduler_queue_t *queue)
-{
- size_t i;
- queue->bits = 0;
- queue->offset = 0;
- for (i = 0; i != sizeof(queue->anchors) / sizeof(queue->anchors[0]); ++i)
- h2o_linklist_init_anchor(queue->anchors + i);
- h2o_linklist_init_anchor(&queue->anchor257);
-}
-
-static int queue_is_empty(h2o_http2_scheduler_queue_t *queue)
-{
- return queue->bits == 0 && h2o_linklist_is_empty(&queue->anchor257);
-}
-
-static void queue_set(h2o_http2_scheduler_queue_t *queue, h2o_http2_scheduler_queue_node_t *node, uint16_t weight)
-{
- /* holds 257 entries of offsets (multiplied by 65536) where nodes with weights between 1..257 should go into
- * each entry (expect for weight=256) is calculated as: round(N / weight), where N is adjusted so that the
- * value would become 63*65536 for weight=0.
- * weight=257 is used internally to send data before any of the streams being pulled, and therefore has the offset set to zero.
- */
- static const unsigned OFFSET_TABLE[] = {
- 4128768, 2064384, 1376256, 1032192, 825754, 688128, 589824, 516096, 458752, 412877, 375343, 344064, 317598, 294912, 275251,
- 258048, 242869, 229376, 217304, 206438, 196608, 187671, 179512, 172032, 165151, 158799, 152917, 147456, 142371, 137626,
- 133186, 129024, 125114, 121434, 117965, 114688, 111588, 108652, 105866, 103219, 100702, 98304, 96018, 93836, 91750,
- 89756, 87846, 86016, 84261, 82575, 80956, 79399, 77901, 76459, 75069, 73728, 72435, 71186, 69979, 68813,
- 67685, 66593, 65536, 64512, 63520, 62557, 61623, 60717, 59837, 58982, 58152, 57344, 56558, 55794, 55050,
- 54326, 53620, 52933, 52263, 51610, 50972, 50351, 49744, 49152, 48574, 48009, 47457, 46918, 46391, 45875,
- 45371, 44878, 44395, 43923, 43461, 43008, 42565, 42130, 41705, 41288, 40879, 40478, 40085, 39700, 39322,
- 38951, 38587, 38229, 37879, 37534, 37196, 36864, 36538, 36217, 35902, 35593, 35289, 34990, 34696, 34406,
- 34122, 33842, 33567, 33297, 33030, 32768, 32510, 32256, 32006, 31760, 31517, 31279, 31043, 30812, 30583,
- 30359, 30137, 29919, 29703, 29491, 29282, 29076, 28873, 28672, 28474, 28279, 28087, 27897, 27710, 27525,
- 27343, 27163, 26985, 26810, 26637, 26466, 26298, 26131, 25967, 25805, 25645, 25486, 25330, 25175, 25023,
- 24872, 24723, 24576, 24431, 24287, 24145, 24004, 23866, 23729, 23593, 23459, 23326, 23195, 23066, 22938,
- 22811, 22686, 22562, 22439, 22318, 22198, 22079, 21962, 21845, 21730, 21617, 21504, 21393, 21282, 21173,
- 21065, 20958, 20852, 20748, 20644, 20541, 20439, 20339, 20239, 20140, 20043, 19946, 19850, 19755, 19661,
- 19568, 19475, 19384, 19293, 19204, 19115, 19027, 18939, 18853, 18767, 18682, 18598, 18515, 18432, 18350,
- 18269, 18188, 18109, 18030, 17951, 17873, 17796, 17720, 17644, 17569, 17495, 17421, 17348, 17275, 17203,
- 17132, 17061, 16991, 16921, 16852, 16784, 16716, 16648, 16581, 16515, 16449, 16384, 16319, 16255, 16191,
- 16128, 0};
-
- assert(!h2o_linklist_is_linked(&node->_link));
-
- if (weight > 256) {
-
- h2o_linklist_insert(&queue->anchor257, &node->_link);
-
- } else {
-
- assert(1 <= weight);
-
- size_t offset = OFFSET_TABLE[weight - 1] + node->_deficit;
- node->_deficit = offset % 65536;
- offset = offset / 65536;
-
- queue->bits |= 1ULL << (sizeof(queue->bits) * 8 - 1 - offset);
- h2o_linklist_insert(queue->anchors + (queue->offset + offset) % (sizeof(queue->anchors) / sizeof(queue->anchors[0])),
- &node->_link);
- }
-}
-
-static void queue_unset(h2o_http2_scheduler_queue_node_t *node)
-{
- assert(h2o_linklist_is_linked(&node->_link));
- h2o_linklist_unlink(&node->_link);
-}
-
-static h2o_http2_scheduler_queue_node_t *queue_pop(h2o_http2_scheduler_queue_t *queue)
-{
- if (!h2o_linklist_is_empty(&queue->anchor257)) {
- h2o_http2_scheduler_queue_node_t *node =
- H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_queue_node_t, _link, queue->anchor257.next);
- h2o_linklist_unlink(&node->_link);
- return node;
- }
-
- while (queue->bits != 0) {
- int zeroes = __builtin_clzll(queue->bits);
- queue->bits <<= zeroes;
- queue->offset = (queue->offset + zeroes) % (sizeof(queue->anchors) / sizeof(queue->anchors[0]));
- if (!h2o_linklist_is_empty(queue->anchors + queue->offset)) {
- h2o_http2_scheduler_queue_node_t *node =
- H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_queue_node_t, _link, queue->anchors[queue->offset].next);
- h2o_linklist_unlink(&node->_link);
- if (h2o_linklist_is_empty(queue->anchors + queue->offset))
- queue->bits &= (1ULL << (sizeof(queue->bits) * 8 - 1)) - 1;
- return node;
- }
- queue->bits &= (1ULL << (sizeof(queue->bits) * 8 - 1)) - 1;
- }
- return NULL;
-}
-
-static void init_node(h2o_http2_scheduler_node_t *node, h2o_http2_scheduler_node_t *parent)
-{
- *node = (h2o_http2_scheduler_node_t){parent};
- h2o_linklist_init_anchor(&node->_all_refs);
-}
-
-static h2o_http2_scheduler_queue_t *get_queue(h2o_http2_scheduler_node_t *node)
-{
- if (node->_queue == NULL) {
- node->_queue = h2o_mem_alloc(sizeof(*node->_queue));
- queue_init(node->_queue);
- }
- return node->_queue;
-}
-
-static void incr_active_cnt(h2o_http2_scheduler_node_t *node)
-{
- h2o_http2_scheduler_openref_t *ref;
-
- /* do nothing if node is the root */
- if (node->_parent == NULL)
- return;
-
- ref = (h2o_http2_scheduler_openref_t *)node;
- if (++ref->_active_cnt != 1)
- return;
- /* just changed to active */
- queue_set(get_queue(ref->node._parent), &ref->_queue_node, ref->weight);
- /* delegate the change towards root */
- incr_active_cnt(ref->node._parent);
-}
-
-static void decr_active_cnt(h2o_http2_scheduler_node_t *node)
-{
- h2o_http2_scheduler_openref_t *ref;
-
- /* do notnig if node is the root */
- if (node->_parent == NULL)
- return;
-
- ref = (h2o_http2_scheduler_openref_t *)node;
- if (--ref->_active_cnt != 0)
- return;
- /* just changed to inactive */
- queue_unset(&ref->_queue_node);
- /* delegate the change towards root */
- decr_active_cnt(ref->node._parent);
-}
-
-static void convert_to_exclusive(h2o_http2_scheduler_node_t *parent, h2o_http2_scheduler_openref_t *added)
-{
- while (!h2o_linklist_is_empty(&parent->_all_refs)) {
- h2o_http2_scheduler_openref_t *child_ref =
- H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, parent->_all_refs.next);
- if (child_ref == added) {
- /* precond: the added node should exist as the last item within parent */
- assert(parent->_all_refs.prev == &added->_all_link);
- break;
- }
- h2o_http2_scheduler_rebind(child_ref, &added->node, h2o_http2_scheduler_get_weight(child_ref), 0);
- }
-}
-
-void h2o_http2_scheduler_open(h2o_http2_scheduler_openref_t *ref, h2o_http2_scheduler_node_t *parent, uint16_t weight,
- int exclusive)
-{
- init_node(&ref->node, parent);
- ref->weight = weight;
- ref->_all_link = (h2o_linklist_t){NULL};
- ref->_active_cnt = 0;
- ref->_self_is_active = 0;
- ref->_queue_node = (h2o_http2_scheduler_queue_node_t){{NULL}};
-
- h2o_linklist_insert(&parent->_all_refs, &ref->_all_link);
-
- if (exclusive)
- convert_to_exclusive(parent, ref);
-}
-
-void h2o_http2_scheduler_close(h2o_http2_scheduler_openref_t *ref)
-{
- assert(h2o_http2_scheduler_is_open(ref));
-
- /* move dependents to parent */
- if (!h2o_linklist_is_empty(&ref->node._all_refs)) {
- /* proportionally distribute the weight to the children (draft-16 5.3.4) */
- uint32_t total_weight = 0, factor;
- h2o_linklist_t *link;
- for (link = ref->node._all_refs.next; link != &ref->node._all_refs; link = link->next) {
- h2o_http2_scheduler_openref_t *child_ref = H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, link);
- total_weight += child_ref->weight;
- }
- assert(total_weight != 0);
- factor = ((uint32_t)ref->weight * 65536 + total_weight / 2) / total_weight;
- do {
- h2o_http2_scheduler_openref_t *child_ref =
- H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _all_link, ref->node._all_refs.next);
- uint16_t weight = (child_ref->weight * factor / 32768 + 1) / 2;
- if (weight < 1)
- weight = 1;
- else if (weight > 256)
- weight = 256;
- h2o_http2_scheduler_rebind(child_ref, ref->node._parent, weight, 0);
- } while (!h2o_linklist_is_empty(&ref->node._all_refs));
- }
-
- free(ref->node._queue);
- ref->node._queue = NULL;
-
- /* detach self */
- h2o_linklist_unlink(&ref->_all_link);
- if (ref->_self_is_active) {
- assert(ref->_active_cnt == 1);
- queue_unset(&ref->_queue_node);
- decr_active_cnt(ref->node._parent);
- } else {
- assert(ref->_active_cnt == 0);
- }
-}
-
-static void do_rebind(h2o_http2_scheduler_openref_t *ref, h2o_http2_scheduler_node_t *new_parent, int exclusive)
-{
- /* rebind _all_link */
- h2o_linklist_unlink(&ref->_all_link);
- h2o_linklist_insert(&new_parent->_all_refs, &ref->_all_link);
- /* rebind to WRR (as well as adjust active_cnt) */
- if (ref->_active_cnt != 0) {
- queue_unset(&ref->_queue_node);
- queue_set(get_queue(new_parent), &ref->_queue_node, ref->weight);
- decr_active_cnt(ref->node._parent);
- incr_active_cnt(new_parent);
- }
- /* update the backlinks */
- ref->node._parent = new_parent;
-
- if (exclusive)
- convert_to_exclusive(new_parent, ref);
-}
-
-void h2o_http2_scheduler_rebind(h2o_http2_scheduler_openref_t *ref, h2o_http2_scheduler_node_t *new_parent, uint16_t weight,
- int exclusive)
-{
- assert(h2o_http2_scheduler_is_open(ref));
- assert(&ref->node != new_parent);
- assert(1 <= weight);
- assert(weight <= 257);
-
- /* do nothing if there'd be no change at all */
- if (ref->node._parent == new_parent && ref->weight == weight && !exclusive)
- return;
-
- ref->weight = weight;
-
- { /* if new_parent is dependent to ref, make new_parent a sibling of ref before applying the final transition (see draft-16
- 5.3.3) */
- h2o_http2_scheduler_node_t *t;
- for (t = new_parent; t->_parent != NULL; t = t->_parent) {
- if (t->_parent == &ref->node) {
- /* quoting the spec: "The moved dependency retains its weight." */
- h2o_http2_scheduler_openref_t *new_parent_ref = (void *)new_parent;
- do_rebind(new_parent_ref, ref->node._parent, 0);
- break;
- }
- }
- }
-
- do_rebind(ref, new_parent, exclusive);
-}
-
-void h2o_http2_scheduler_init(h2o_http2_scheduler_node_t *root)
-{
- init_node(root, NULL);
-}
-
-void h2o_http2_scheduler_dispose(h2o_http2_scheduler_node_t *root)
-{
- free(root->_queue);
- root->_queue = NULL;
-}
-
-void h2o_http2_scheduler_activate(h2o_http2_scheduler_openref_t *ref)
-{
- if (ref->_self_is_active)
- return;
- ref->_self_is_active = 1;
- incr_active_cnt(&ref->node);
-}
-
-static int proceed(h2o_http2_scheduler_node_t *node, h2o_http2_scheduler_run_cb cb, void *cb_arg)
-{
-Redo:
- if (node->_queue == NULL)
- return 0;
-
- h2o_http2_scheduler_queue_node_t *drr_node = queue_pop(node->_queue);
- if (drr_node == NULL)
- return 0;
-
- h2o_http2_scheduler_openref_t *ref = H2O_STRUCT_FROM_MEMBER(h2o_http2_scheduler_openref_t, _queue_node, drr_node);
-
- if (!ref->_self_is_active) {
- /* run the children (manually-unrolled tail recursion) */
- queue_set(node->_queue, &ref->_queue_node, ref->weight);
- node = &ref->node;
- goto Redo;
- }
- assert(ref->_active_cnt != 0);
-
- /* call the callbacks */
- int still_is_active, bail_out = cb(ref, &still_is_active, cb_arg);
- if (still_is_active) {
- queue_set(node->_queue, &ref->_queue_node, ref->weight);
- } else {
- ref->_self_is_active = 0;
- if (--ref->_active_cnt != 0) {
- queue_set(node->_queue, &ref->_queue_node, ref->weight);
- } else if (ref->node._parent != NULL) {
- decr_active_cnt(ref->node._parent);
- }
- }
-
- return bail_out;
-}
-
-int h2o_http2_scheduler_run(h2o_http2_scheduler_node_t *root, h2o_http2_scheduler_run_cb cb, void *cb_arg)
-{
- if (root->_queue != NULL) {
- while (!queue_is_empty(root->_queue)) {
- int bail_out = proceed(root, cb, cb_arg);
- if (bail_out)
- return bail_out;
- }
- }
- return 0;
-}
-
-int h2o_http2_scheduler_is_active(h2o_http2_scheduler_node_t *root)
-{
- return root->_queue != NULL && !queue_is_empty(root->_queue);
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-24 20:05:33 +0000