diff options
Diffstat (limited to 'debian/vendor-h2o/lib/http2/scheduler.c')
-rw-r--r-- | debian/vendor-h2o/lib/http2/scheduler.c | 365 |
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); -} |