/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 | } |