/src/nghttp2/lib/nghttp2_stream.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * nghttp2 - HTTP/2 C Library |
3 | | * |
4 | | * Copyright (c) 2012 Tatsuhiro Tsujikawa |
5 | | * |
6 | | * Permission is hereby granted, free of charge, to any person obtaining |
7 | | * a copy of this software and associated documentation files (the |
8 | | * "Software"), to deal in the Software without restriction, including |
9 | | * without limitation the rights to use, copy, modify, merge, publish, |
10 | | * distribute, sublicense, and/or sell copies of the Software, and to |
11 | | * permit persons to whom the Software is furnished to do so, subject to |
12 | | * the following conditions: |
13 | | * |
14 | | * The above copyright notice and this permission notice shall be |
15 | | * included in all copies or substantial portions of the Software. |
16 | | * |
17 | | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
18 | | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
19 | | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
20 | | * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE |
21 | | * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION |
22 | | * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION |
23 | | * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
24 | | */ |
25 | | #include "nghttp2_stream.h" |
26 | | |
27 | | #include <assert.h> |
28 | | #include <stdio.h> |
29 | | |
30 | | #include "nghttp2_session.h" |
31 | | #include "nghttp2_helper.h" |
32 | | #include "nghttp2_debug.h" |
33 | | #include "nghttp2_frame.h" |
34 | | |
35 | | /* Maximum distance between any two stream's cycle in the same |
36 | | prirority queue. Imagine stream A's cycle is A, and stream B's |
37 | | cycle is B, and A < B. The cycle is unsigned 32 bit integer, it |
38 | | may get overflow. Because of how we calculate the next cycle |
39 | | value, if B - A is less than or equals to |
40 | | NGHTTP2_MAX_CYCLE_DISTANCE, A and B are in the same scale, in other |
41 | | words, B is really greater than or equal to A. Otherwise, A is a |
42 | | result of overflow, and it is actually A > B if we consider that |
43 | | fact. */ |
44 | | #define NGHTTP2_MAX_CYCLE_DISTANCE \ |
45 | 0 | ((uint64_t)NGHTTP2_MAX_FRAME_SIZE_MAX * 256 + 255) |
46 | | |
47 | 0 | static int stream_less(const void *lhsx, const void *rhsx) { |
48 | 0 | const nghttp2_stream *lhs, *rhs; |
49 | |
|
50 | 0 | lhs = nghttp2_struct_of(lhsx, nghttp2_stream, pq_entry); |
51 | 0 | rhs = nghttp2_struct_of(rhsx, nghttp2_stream, pq_entry); |
52 | |
|
53 | 0 | if (lhs->cycle == rhs->cycle) { |
54 | 0 | return lhs->seq < rhs->seq; |
55 | 0 | } |
56 | | |
57 | 0 | return rhs->cycle - lhs->cycle <= NGHTTP2_MAX_CYCLE_DISTANCE; |
58 | 0 | } |
59 | | |
60 | | void nghttp2_stream_init(nghttp2_stream *stream, int32_t stream_id, |
61 | | uint8_t flags, nghttp2_stream_state initial_state, |
62 | | int32_t weight, int32_t remote_initial_window_size, |
63 | | int32_t local_initial_window_size, |
64 | 0 | void *stream_user_data, nghttp2_mem *mem) { |
65 | 0 | nghttp2_map_entry_init(&stream->map_entry, (key_type)stream_id); |
66 | 0 | nghttp2_pq_init(&stream->obq, stream_less, mem); |
67 | |
|
68 | 0 | stream->stream_id = stream_id; |
69 | 0 | stream->flags = flags; |
70 | 0 | stream->state = initial_state; |
71 | 0 | stream->shut_flags = NGHTTP2_SHUT_NONE; |
72 | 0 | stream->stream_user_data = stream_user_data; |
73 | 0 | stream->item = NULL; |
74 | 0 | stream->remote_window_size = remote_initial_window_size; |
75 | 0 | stream->local_window_size = local_initial_window_size; |
76 | 0 | stream->recv_window_size = 0; |
77 | 0 | stream->consumed_size = 0; |
78 | 0 | stream->recv_reduction = 0; |
79 | 0 | stream->window_update_queued = 0; |
80 | |
|
81 | 0 | stream->dep_prev = NULL; |
82 | 0 | stream->dep_next = NULL; |
83 | 0 | stream->sib_prev = NULL; |
84 | 0 | stream->sib_next = NULL; |
85 | |
|
86 | 0 | stream->closed_prev = NULL; |
87 | 0 | stream->closed_next = NULL; |
88 | |
|
89 | 0 | stream->weight = weight; |
90 | 0 | stream->sum_dep_weight = 0; |
91 | |
|
92 | 0 | stream->http_flags = NGHTTP2_HTTP_FLAG_NONE; |
93 | 0 | stream->content_length = -1; |
94 | 0 | stream->recv_content_length = 0; |
95 | 0 | stream->status_code = -1; |
96 | |
|
97 | 0 | stream->queued = 0; |
98 | 0 | stream->descendant_last_cycle = 0; |
99 | 0 | stream->cycle = 0; |
100 | 0 | stream->pending_penalty = 0; |
101 | 0 | stream->descendant_next_seq = 0; |
102 | 0 | stream->seq = 0; |
103 | 0 | stream->last_writelen = 0; |
104 | 0 | } |
105 | | |
106 | 0 | void nghttp2_stream_free(nghttp2_stream *stream) { |
107 | 0 | nghttp2_pq_free(&stream->obq); |
108 | | /* We don't free stream->item. If it is assigned to aob, then |
109 | | active_outbound_item_reset() will delete it. Otherwise, |
110 | | nghttp2_stream_close() or session_del() will delete it. */ |
111 | 0 | } |
112 | | |
113 | 0 | void nghttp2_stream_shutdown(nghttp2_stream *stream, nghttp2_shut_flag flag) { |
114 | 0 | stream->shut_flags = (uint8_t)(stream->shut_flags | flag); |
115 | 0 | } |
116 | | |
117 | | /* |
118 | | * Returns nonzero if |stream| is active. This function does not take |
119 | | * into account its descendants. |
120 | | */ |
121 | 0 | static int stream_active(nghttp2_stream *stream) { |
122 | 0 | return stream->item && |
123 | 0 | (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL) == 0; |
124 | 0 | } |
125 | | |
126 | | /* |
127 | | * Returns nonzero if |stream| or one of its descendants is active |
128 | | */ |
129 | 0 | static int stream_subtree_active(nghttp2_stream *stream) { |
130 | 0 | return stream_active(stream) || !nghttp2_pq_empty(&stream->obq); |
131 | 0 | } |
132 | | |
133 | | /* |
134 | | * Returns next cycle for |stream|. |
135 | | */ |
136 | 0 | static void stream_next_cycle(nghttp2_stream *stream, uint64_t last_cycle) { |
137 | 0 | uint64_t penalty; |
138 | |
|
139 | 0 | penalty = (uint64_t)stream->last_writelen * NGHTTP2_MAX_WEIGHT + |
140 | 0 | stream->pending_penalty; |
141 | |
|
142 | 0 | stream->cycle = last_cycle + penalty / (uint32_t)stream->weight; |
143 | 0 | stream->pending_penalty = (uint32_t)(penalty % (uint32_t)stream->weight); |
144 | 0 | } |
145 | | |
146 | 0 | static int stream_obq_push(nghttp2_stream *dep_stream, nghttp2_stream *stream) { |
147 | 0 | int rv; |
148 | |
|
149 | 0 | for (; dep_stream && !stream->queued; |
150 | 0 | stream = dep_stream, dep_stream = dep_stream->dep_prev) { |
151 | 0 | stream_next_cycle(stream, dep_stream->descendant_last_cycle); |
152 | 0 | stream->seq = dep_stream->descendant_next_seq++; |
153 | |
|
154 | 0 | DEBUGF("stream: stream=%d obq push cycle=%lu\n", stream->stream_id, |
155 | 0 | stream->cycle); |
156 | |
|
157 | 0 | DEBUGF("stream: push stream %d to stream %d\n", stream->stream_id, |
158 | 0 | dep_stream->stream_id); |
159 | |
|
160 | 0 | rv = nghttp2_pq_push(&dep_stream->obq, &stream->pq_entry); |
161 | 0 | if (rv != 0) { |
162 | 0 | return rv; |
163 | 0 | } |
164 | 0 | stream->queued = 1; |
165 | 0 | } |
166 | | |
167 | 0 | return 0; |
168 | 0 | } |
169 | | |
170 | | /* |
171 | | * Removes |stream| from parent's obq. If removal of |stream| makes |
172 | | * parent's obq empty, and parent is not active, then parent is also |
173 | | * removed. This process is repeated recursively. |
174 | | */ |
175 | 0 | static void stream_obq_remove(nghttp2_stream *stream) { |
176 | 0 | nghttp2_stream *dep_stream; |
177 | |
|
178 | 0 | dep_stream = stream->dep_prev; |
179 | |
|
180 | 0 | if (!stream->queued) { |
181 | 0 | return; |
182 | 0 | } |
183 | | |
184 | 0 | for (; dep_stream; stream = dep_stream, dep_stream = dep_stream->dep_prev) { |
185 | 0 | DEBUGF("stream: remove stream %d from stream %d\n", stream->stream_id, |
186 | 0 | dep_stream->stream_id); |
187 | |
|
188 | 0 | nghttp2_pq_remove(&dep_stream->obq, &stream->pq_entry); |
189 | |
|
190 | 0 | assert(stream->queued); |
191 | | |
192 | 0 | stream->queued = 0; |
193 | 0 | stream->cycle = 0; |
194 | 0 | stream->pending_penalty = 0; |
195 | 0 | stream->descendant_last_cycle = 0; |
196 | 0 | stream->last_writelen = 0; |
197 | |
|
198 | 0 | if (stream_subtree_active(dep_stream)) { |
199 | 0 | return; |
200 | 0 | } |
201 | 0 | } |
202 | 0 | } |
203 | | |
204 | | /* |
205 | | * Moves |stream| from |src|'s obq to |dest|'s obq. Removal from |
206 | | * |src|'s obq is just done calling nghttp2_pq_remove(), so it does |
207 | | * not recursively remove |src| and ancestors, like |
208 | | * stream_obq_remove(). |
209 | | */ |
210 | | static int stream_obq_move(nghttp2_stream *dest, nghttp2_stream *src, |
211 | 0 | nghttp2_stream *stream) { |
212 | 0 | if (!stream->queued) { |
213 | 0 | return 0; |
214 | 0 | } |
215 | | |
216 | 0 | DEBUGF("stream: remove stream %d from stream %d (move)\n", stream->stream_id, |
217 | 0 | src->stream_id); |
218 | |
|
219 | 0 | nghttp2_pq_remove(&src->obq, &stream->pq_entry); |
220 | 0 | stream->queued = 0; |
221 | |
|
222 | 0 | return stream_obq_push(dest, stream); |
223 | 0 | } |
224 | | |
225 | 0 | void nghttp2_stream_reschedule(nghttp2_stream *stream) { |
226 | 0 | nghttp2_stream *dep_stream; |
227 | |
|
228 | 0 | assert(stream->queued); |
229 | | |
230 | 0 | dep_stream = stream->dep_prev; |
231 | |
|
232 | 0 | for (; dep_stream; stream = dep_stream, dep_stream = dep_stream->dep_prev) { |
233 | 0 | nghttp2_pq_remove(&dep_stream->obq, &stream->pq_entry); |
234 | |
|
235 | 0 | stream_next_cycle(stream, dep_stream->descendant_last_cycle); |
236 | 0 | stream->seq = dep_stream->descendant_next_seq++; |
237 | |
|
238 | 0 | nghttp2_pq_push(&dep_stream->obq, &stream->pq_entry); |
239 | |
|
240 | 0 | DEBUGF("stream: stream=%d obq resched cycle=%lu\n", stream->stream_id, |
241 | 0 | stream->cycle); |
242 | |
|
243 | 0 | dep_stream->last_writelen = stream->last_writelen; |
244 | 0 | } |
245 | 0 | } |
246 | | |
247 | 0 | void nghttp2_stream_change_weight(nghttp2_stream *stream, int32_t weight) { |
248 | 0 | nghttp2_stream *dep_stream; |
249 | 0 | uint64_t last_cycle; |
250 | 0 | int32_t old_weight; |
251 | 0 | uint64_t wlen_penalty; |
252 | |
|
253 | 0 | if (stream->weight == weight) { |
254 | 0 | return; |
255 | 0 | } |
256 | | |
257 | 0 | old_weight = stream->weight; |
258 | 0 | stream->weight = weight; |
259 | |
|
260 | 0 | dep_stream = stream->dep_prev; |
261 | |
|
262 | 0 | if (!dep_stream) { |
263 | 0 | return; |
264 | 0 | } |
265 | | |
266 | 0 | dep_stream->sum_dep_weight += weight - old_weight; |
267 | |
|
268 | 0 | if (!stream->queued) { |
269 | 0 | return; |
270 | 0 | } |
271 | | |
272 | 0 | nghttp2_pq_remove(&dep_stream->obq, &stream->pq_entry); |
273 | |
|
274 | 0 | wlen_penalty = (uint64_t)stream->last_writelen * NGHTTP2_MAX_WEIGHT; |
275 | | |
276 | | /* Compute old stream->pending_penalty we used to calculate |
277 | | stream->cycle */ |
278 | 0 | stream->pending_penalty = |
279 | 0 | (uint32_t)((stream->pending_penalty + (uint32_t)old_weight - |
280 | 0 | (wlen_penalty % (uint32_t)old_weight)) % |
281 | 0 | (uint32_t)old_weight); |
282 | |
|
283 | 0 | last_cycle = stream->cycle - |
284 | 0 | (wlen_penalty + stream->pending_penalty) / (uint32_t)old_weight; |
285 | | |
286 | | /* Now we have old stream->pending_penalty and new stream->weight in |
287 | | place */ |
288 | 0 | stream_next_cycle(stream, last_cycle); |
289 | |
|
290 | 0 | if (dep_stream->descendant_last_cycle - stream->cycle <= |
291 | 0 | NGHTTP2_MAX_CYCLE_DISTANCE) { |
292 | 0 | stream->cycle = dep_stream->descendant_last_cycle; |
293 | 0 | } |
294 | | |
295 | | /* Continue to use same stream->seq */ |
296 | |
|
297 | 0 | nghttp2_pq_push(&dep_stream->obq, &stream->pq_entry); |
298 | |
|
299 | 0 | DEBUGF("stream: stream=%d obq resched cycle=%lu\n", stream->stream_id, |
300 | 0 | stream->cycle); |
301 | 0 | } |
302 | | |
303 | 0 | static nghttp2_stream *stream_last_sib(nghttp2_stream *stream) { |
304 | 0 | for (; stream->sib_next; stream = stream->sib_next) |
305 | 0 | ; |
306 | |
|
307 | 0 | return stream; |
308 | 0 | } |
309 | | |
310 | | int32_t nghttp2_stream_dep_distributed_weight(nghttp2_stream *stream, |
311 | 0 | int32_t weight) { |
312 | 0 | weight = stream->weight * weight / stream->sum_dep_weight; |
313 | |
|
314 | 0 | return nghttp2_max(1, weight); |
315 | 0 | } |
316 | | |
317 | | #ifdef STREAM_DEP_DEBUG |
318 | | |
319 | | static void ensure_inactive(nghttp2_stream *stream) { |
320 | | nghttp2_stream *si; |
321 | | |
322 | | if (stream->queued) { |
323 | | fprintf(stderr, "stream(%p)=%d, stream->queued = 1; want 0\n", stream, |
324 | | stream->stream_id); |
325 | | assert(0); |
326 | | } |
327 | | |
328 | | if (stream_active(stream)) { |
329 | | fprintf(stderr, "stream(%p)=%d, stream_active(stream) = 1; want 0\n", |
330 | | stream, stream->stream_id); |
331 | | assert(0); |
332 | | } |
333 | | |
334 | | if (!nghttp2_pq_empty(&stream->obq)) { |
335 | | fprintf(stderr, "stream(%p)=%d, nghttp2_pq_size() = %zu; want 0\n", stream, |
336 | | stream->stream_id, nghttp2_pq_size(&stream->obq)); |
337 | | assert(0); |
338 | | } |
339 | | |
340 | | for (si = stream->dep_next; si; si = si->sib_next) { |
341 | | ensure_inactive(si); |
342 | | } |
343 | | } |
344 | | |
345 | | static void check_queued(nghttp2_stream *stream) { |
346 | | nghttp2_stream *si; |
347 | | int queued; |
348 | | |
349 | | if (stream->queued) { |
350 | | if (!stream_subtree_active(stream)) { |
351 | | fprintf(stderr, |
352 | | "stream(%p)=%d, stream->queued == 1, but " |
353 | | "stream_active() == %d and nghttp2_pq_size(&stream->obq) = %zu\n", |
354 | | stream, stream->stream_id, stream_active(stream), |
355 | | nghttp2_pq_size(&stream->obq)); |
356 | | assert(0); |
357 | | } |
358 | | if (!stream_active(stream)) { |
359 | | queued = 0; |
360 | | for (si = stream->dep_next; si; si = si->sib_next) { |
361 | | if (si->queued) { |
362 | | ++queued; |
363 | | } |
364 | | } |
365 | | if (queued == 0) { |
366 | | fprintf(stderr, |
367 | | "stream(%p)=%d, stream->queued == 1, and " |
368 | | "!stream_active(), but no descendants is queued\n", |
369 | | stream, stream->stream_id); |
370 | | assert(0); |
371 | | } |
372 | | } |
373 | | |
374 | | for (si = stream->dep_next; si; si = si->sib_next) { |
375 | | check_queued(si); |
376 | | } |
377 | | } else { |
378 | | if (stream_active(stream) || !nghttp2_pq_empty(&stream->obq)) { |
379 | | fprintf(stderr, |
380 | | "stream(%p) = %d, stream->queued == 0, but " |
381 | | "stream_active(stream) == %d and " |
382 | | "nghttp2_pq_size(&stream->obq) = %zu\n", |
383 | | stream, stream->stream_id, stream_active(stream), |
384 | | nghttp2_pq_size(&stream->obq)); |
385 | | assert(0); |
386 | | } |
387 | | for (si = stream->dep_next; si; si = si->sib_next) { |
388 | | ensure_inactive(si); |
389 | | } |
390 | | } |
391 | | } |
392 | | |
393 | | static void check_sum_dep(nghttp2_stream *stream) { |
394 | | nghttp2_stream *si; |
395 | | int32_t n = 0; |
396 | | for (si = stream->dep_next; si; si = si->sib_next) { |
397 | | n += si->weight; |
398 | | } |
399 | | if (n != stream->sum_dep_weight) { |
400 | | fprintf(stderr, "stream(%p)=%d, sum_dep_weight = %d; want %d\n", stream, |
401 | | stream->stream_id, n, stream->sum_dep_weight); |
402 | | assert(0); |
403 | | } |
404 | | for (si = stream->dep_next; si; si = si->sib_next) { |
405 | | check_sum_dep(si); |
406 | | } |
407 | | } |
408 | | |
409 | | static void check_dep_prev(nghttp2_stream *stream) { |
410 | | nghttp2_stream *si; |
411 | | for (si = stream->dep_next; si; si = si->sib_next) { |
412 | | if (si->dep_prev != stream) { |
413 | | fprintf(stderr, "si->dep_prev = %p; want %p\n", si->dep_prev, stream); |
414 | | assert(0); |
415 | | } |
416 | | check_dep_prev(si); |
417 | | } |
418 | | } |
419 | | |
420 | | #endif /* STREAM_DEP_DEBUG */ |
421 | | |
422 | | #ifdef STREAM_DEP_DEBUG |
423 | | static void validate_tree(nghttp2_stream *stream) { |
424 | | nghttp2_stream *si; |
425 | | |
426 | | if (!stream) { |
427 | | return; |
428 | | } |
429 | | |
430 | | for (; stream->dep_prev; stream = stream->dep_prev) |
431 | | ; |
432 | | |
433 | | assert(stream->stream_id == 0); |
434 | | assert(!stream->queued); |
435 | | |
436 | | fprintf(stderr, "checking...\n"); |
437 | | if (nghttp2_pq_empty(&stream->obq)) { |
438 | | fprintf(stderr, "root obq empty\n"); |
439 | | for (si = stream->dep_next; si; si = si->sib_next) { |
440 | | ensure_inactive(si); |
441 | | } |
442 | | } else { |
443 | | for (si = stream->dep_next; si; si = si->sib_next) { |
444 | | check_queued(si); |
445 | | } |
446 | | } |
447 | | |
448 | | check_sum_dep(stream); |
449 | | check_dep_prev(stream); |
450 | | } |
451 | | #else /* !STREAM_DEP_DEBUG */ |
452 | 0 | static void validate_tree(nghttp2_stream *stream) { (void)stream; } |
453 | | #endif /* !STREAM_DEP_DEBUG*/ |
454 | | |
455 | 0 | static int stream_update_dep_on_attach_item(nghttp2_stream *stream) { |
456 | 0 | int rv; |
457 | |
|
458 | 0 | rv = stream_obq_push(stream->dep_prev, stream); |
459 | 0 | if (rv != 0) { |
460 | 0 | return rv; |
461 | 0 | } |
462 | | |
463 | 0 | validate_tree(stream); |
464 | 0 | return 0; |
465 | 0 | } |
466 | | |
467 | 0 | static int stream_update_dep_on_detach_item(nghttp2_stream *stream) { |
468 | 0 | if (nghttp2_pq_empty(&stream->obq)) { |
469 | 0 | stream_obq_remove(stream); |
470 | 0 | } |
471 | |
|
472 | 0 | validate_tree(stream); |
473 | |
|
474 | 0 | return 0; |
475 | 0 | } |
476 | | |
477 | | int nghttp2_stream_attach_item(nghttp2_stream *stream, |
478 | 0 | nghttp2_outbound_item *item) { |
479 | 0 | int rv; |
480 | |
|
481 | 0 | assert((stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL) == 0); |
482 | 0 | assert(stream->item == NULL); |
483 | | |
484 | 0 | DEBUGF("stream: stream=%d attach item=%p\n", stream->stream_id, item); |
485 | |
|
486 | 0 | stream->item = item; |
487 | |
|
488 | 0 | rv = stream_update_dep_on_attach_item(stream); |
489 | 0 | if (rv != 0) { |
490 | | /* This may relave stream->queued == 1, but stream->item == NULL. |
491 | | But only consequence of this error is fatal one, and session |
492 | | destruction. In that execution path, these inconsistency does |
493 | | not matter. */ |
494 | 0 | stream->item = NULL; |
495 | 0 | return rv; |
496 | 0 | } |
497 | | |
498 | 0 | return 0; |
499 | 0 | } |
500 | | |
501 | 0 | int nghttp2_stream_detach_item(nghttp2_stream *stream) { |
502 | 0 | DEBUGF("stream: stream=%d detach item=%p\n", stream->stream_id, stream->item); |
503 | |
|
504 | 0 | stream->item = NULL; |
505 | 0 | stream->flags = (uint8_t)(stream->flags & ~NGHTTP2_STREAM_FLAG_DEFERRED_ALL); |
506 | |
|
507 | 0 | return stream_update_dep_on_detach_item(stream); |
508 | 0 | } |
509 | | |
510 | 0 | int nghttp2_stream_defer_item(nghttp2_stream *stream, uint8_t flags) { |
511 | 0 | assert(stream->item); |
512 | | |
513 | 0 | DEBUGF("stream: stream=%d defer item=%p cause=%02x\n", stream->stream_id, |
514 | 0 | stream->item, flags); |
515 | |
|
516 | 0 | stream->flags |= flags; |
517 | |
|
518 | 0 | return stream_update_dep_on_detach_item(stream); |
519 | 0 | } |
520 | | |
521 | 0 | int nghttp2_stream_resume_deferred_item(nghttp2_stream *stream, uint8_t flags) { |
522 | 0 | assert(stream->item); |
523 | | |
524 | 0 | DEBUGF("stream: stream=%d resume item=%p flags=%02x\n", stream->stream_id, |
525 | 0 | stream->item, flags); |
526 | |
|
527 | 0 | stream->flags = (uint8_t)(stream->flags & ~flags); |
528 | |
|
529 | 0 | if (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL) { |
530 | 0 | return 0; |
531 | 0 | } |
532 | | |
533 | 0 | return stream_update_dep_on_attach_item(stream); |
534 | 0 | } |
535 | | |
536 | 0 | int nghttp2_stream_check_deferred_item(nghttp2_stream *stream) { |
537 | 0 | return stream->item && (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL); |
538 | 0 | } |
539 | | |
540 | 0 | int nghttp2_stream_check_deferred_by_flow_control(nghttp2_stream *stream) { |
541 | 0 | return stream->item && |
542 | 0 | (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_FLOW_CONTROL); |
543 | 0 | } |
544 | | |
545 | | static int update_initial_window_size(int32_t *window_size_ptr, |
546 | | int32_t new_initial_window_size, |
547 | 0 | int32_t old_initial_window_size) { |
548 | 0 | int64_t new_window_size = (int64_t)(*window_size_ptr) + |
549 | 0 | new_initial_window_size - old_initial_window_size; |
550 | 0 | if (INT32_MIN > new_window_size || |
551 | 0 | new_window_size > NGHTTP2_MAX_WINDOW_SIZE) { |
552 | 0 | return -1; |
553 | 0 | } |
554 | 0 | *window_size_ptr = (int32_t)new_window_size; |
555 | 0 | return 0; |
556 | 0 | } |
557 | | |
558 | | int nghttp2_stream_update_remote_initial_window_size( |
559 | | nghttp2_stream *stream, int32_t new_initial_window_size, |
560 | 0 | int32_t old_initial_window_size) { |
561 | 0 | return update_initial_window_size(&stream->remote_window_size, |
562 | 0 | new_initial_window_size, |
563 | 0 | old_initial_window_size); |
564 | 0 | } |
565 | | |
566 | | int nghttp2_stream_update_local_initial_window_size( |
567 | | nghttp2_stream *stream, int32_t new_initial_window_size, |
568 | 0 | int32_t old_initial_window_size) { |
569 | 0 | return update_initial_window_size(&stream->local_window_size, |
570 | 0 | new_initial_window_size, |
571 | 0 | old_initial_window_size); |
572 | 0 | } |
573 | | |
574 | 0 | void nghttp2_stream_promise_fulfilled(nghttp2_stream *stream) { |
575 | 0 | stream->state = NGHTTP2_STREAM_OPENED; |
576 | 0 | stream->flags = (uint8_t)(stream->flags & ~NGHTTP2_STREAM_FLAG_PUSH); |
577 | 0 | } |
578 | | |
579 | | int nghttp2_stream_dep_find_ancestor(nghttp2_stream *stream, |
580 | 0 | nghttp2_stream *target) { |
581 | 0 | for (; stream; stream = stream->dep_prev) { |
582 | 0 | if (stream == target) { |
583 | 0 | return 1; |
584 | 0 | } |
585 | 0 | } |
586 | 0 | return 0; |
587 | 0 | } |
588 | | |
589 | | int nghttp2_stream_dep_insert(nghttp2_stream *dep_stream, |
590 | 0 | nghttp2_stream *stream) { |
591 | 0 | nghttp2_stream *si; |
592 | 0 | int rv; |
593 | |
|
594 | 0 | DEBUGF("stream: dep_insert dep_stream(%p)=%d, stream(%p)=%d\n", dep_stream, |
595 | 0 | dep_stream->stream_id, stream, stream->stream_id); |
596 | |
|
597 | 0 | stream->sum_dep_weight = dep_stream->sum_dep_weight; |
598 | 0 | dep_stream->sum_dep_weight = stream->weight; |
599 | |
|
600 | 0 | if (dep_stream->dep_next) { |
601 | 0 | for (si = dep_stream->dep_next; si; si = si->sib_next) { |
602 | 0 | si->dep_prev = stream; |
603 | 0 | if (si->queued) { |
604 | 0 | rv = stream_obq_move(stream, dep_stream, si); |
605 | 0 | if (rv != 0) { |
606 | 0 | return rv; |
607 | 0 | } |
608 | 0 | } |
609 | 0 | } |
610 | | |
611 | 0 | if (stream_subtree_active(stream)) { |
612 | 0 | rv = stream_obq_push(dep_stream, stream); |
613 | 0 | if (rv != 0) { |
614 | 0 | return rv; |
615 | 0 | } |
616 | 0 | } |
617 | | |
618 | 0 | stream->dep_next = dep_stream->dep_next; |
619 | 0 | } |
620 | | |
621 | 0 | dep_stream->dep_next = stream; |
622 | 0 | stream->dep_prev = dep_stream; |
623 | |
|
624 | 0 | validate_tree(stream); |
625 | |
|
626 | 0 | return 0; |
627 | 0 | } |
628 | | |
629 | 0 | static void set_dep_prev(nghttp2_stream *stream, nghttp2_stream *dep) { |
630 | 0 | for (; stream; stream = stream->sib_next) { |
631 | 0 | stream->dep_prev = dep; |
632 | 0 | } |
633 | 0 | } |
634 | | |
635 | 0 | static void link_dep(nghttp2_stream *dep_stream, nghttp2_stream *stream) { |
636 | 0 | dep_stream->dep_next = stream; |
637 | 0 | if (stream) { |
638 | 0 | stream->dep_prev = dep_stream; |
639 | 0 | } |
640 | 0 | } |
641 | | |
642 | 0 | static void link_sib(nghttp2_stream *a, nghttp2_stream *b) { |
643 | 0 | a->sib_next = b; |
644 | 0 | if (b) { |
645 | 0 | b->sib_prev = a; |
646 | 0 | } |
647 | 0 | } |
648 | | |
649 | | static void insert_link_dep(nghttp2_stream *dep_stream, |
650 | 0 | nghttp2_stream *stream) { |
651 | 0 | nghttp2_stream *sib_next; |
652 | |
|
653 | 0 | assert(stream->sib_prev == NULL); |
654 | | |
655 | 0 | sib_next = dep_stream->dep_next; |
656 | |
|
657 | 0 | link_sib(stream, sib_next); |
658 | |
|
659 | 0 | link_dep(dep_stream, stream); |
660 | 0 | } |
661 | | |
662 | 0 | static void unlink_sib(nghttp2_stream *stream) { |
663 | 0 | nghttp2_stream *prev, *next, *dep_next; |
664 | |
|
665 | 0 | prev = stream->sib_prev; |
666 | 0 | dep_next = stream->dep_next; |
667 | |
|
668 | 0 | assert(prev); |
669 | | |
670 | 0 | if (dep_next) { |
671 | | /* |
672 | | * prev--stream(--sib_next--...) |
673 | | * | |
674 | | * dep_next |
675 | | */ |
676 | |
|
677 | 0 | link_sib(prev, dep_next); |
678 | |
|
679 | 0 | set_dep_prev(dep_next, stream->dep_prev); |
680 | |
|
681 | 0 | if (stream->sib_next) { |
682 | 0 | link_sib(stream_last_sib(dep_next), stream->sib_next); |
683 | 0 | } |
684 | 0 | } else { |
685 | | /* |
686 | | * prev--stream(--sib_next--...) |
687 | | */ |
688 | 0 | next = stream->sib_next; |
689 | |
|
690 | 0 | prev->sib_next = next; |
691 | |
|
692 | 0 | if (next) { |
693 | 0 | next->sib_prev = prev; |
694 | 0 | } |
695 | 0 | } |
696 | 0 | } |
697 | | |
698 | 0 | static void unlink_dep(nghttp2_stream *stream) { |
699 | 0 | nghttp2_stream *prev, *next, *dep_next; |
700 | |
|
701 | 0 | prev = stream->dep_prev; |
702 | 0 | dep_next = stream->dep_next; |
703 | |
|
704 | 0 | assert(prev); |
705 | | |
706 | 0 | if (dep_next) { |
707 | | /* |
708 | | * prev |
709 | | * | |
710 | | * stream(--sib_next--...) |
711 | | * | |
712 | | * dep_next |
713 | | */ |
714 | 0 | link_dep(prev, dep_next); |
715 | |
|
716 | 0 | set_dep_prev(dep_next, stream->dep_prev); |
717 | |
|
718 | 0 | if (stream->sib_next) { |
719 | 0 | link_sib(stream_last_sib(dep_next), stream->sib_next); |
720 | 0 | } |
721 | |
|
722 | 0 | } else if (stream->sib_next) { |
723 | | /* |
724 | | * prev |
725 | | * | |
726 | | * stream--sib_next |
727 | | */ |
728 | 0 | next = stream->sib_next; |
729 | |
|
730 | 0 | next->sib_prev = NULL; |
731 | |
|
732 | 0 | link_dep(prev, next); |
733 | 0 | } else { |
734 | 0 | prev->dep_next = NULL; |
735 | 0 | } |
736 | 0 | } |
737 | | |
738 | | void nghttp2_stream_dep_add(nghttp2_stream *dep_stream, |
739 | 0 | nghttp2_stream *stream) { |
740 | 0 | DEBUGF("stream: dep_add dep_stream(%p)=%d, stream(%p)=%d\n", dep_stream, |
741 | 0 | dep_stream->stream_id, stream, stream->stream_id); |
742 | |
|
743 | 0 | dep_stream->sum_dep_weight += stream->weight; |
744 | |
|
745 | 0 | if (dep_stream->dep_next == NULL) { |
746 | 0 | link_dep(dep_stream, stream); |
747 | 0 | } else { |
748 | 0 | insert_link_dep(dep_stream, stream); |
749 | 0 | } |
750 | |
|
751 | 0 | validate_tree(stream); |
752 | 0 | } |
753 | | |
754 | 0 | int nghttp2_stream_dep_remove(nghttp2_stream *stream) { |
755 | 0 | nghttp2_stream *dep_prev, *si; |
756 | 0 | int32_t sum_dep_weight_delta; |
757 | 0 | int rv; |
758 | |
|
759 | 0 | DEBUGF("stream: dep_remove stream(%p)=%d\n", stream, stream->stream_id); |
760 | | |
761 | | /* Distribute weight of |stream| to direct descendants */ |
762 | 0 | sum_dep_weight_delta = -stream->weight; |
763 | |
|
764 | 0 | for (si = stream->dep_next; si; si = si->sib_next) { |
765 | 0 | si->weight = nghttp2_stream_dep_distributed_weight(stream, si->weight); |
766 | |
|
767 | 0 | sum_dep_weight_delta += si->weight; |
768 | |
|
769 | 0 | if (si->queued) { |
770 | 0 | rv = stream_obq_move(stream->dep_prev, stream, si); |
771 | 0 | if (rv != 0) { |
772 | 0 | return rv; |
773 | 0 | } |
774 | 0 | } |
775 | 0 | } |
776 | | |
777 | 0 | assert(stream->dep_prev); |
778 | | |
779 | 0 | dep_prev = stream->dep_prev; |
780 | |
|
781 | 0 | dep_prev->sum_dep_weight += sum_dep_weight_delta; |
782 | |
|
783 | 0 | if (stream->queued) { |
784 | 0 | stream_obq_remove(stream); |
785 | 0 | } |
786 | |
|
787 | 0 | if (stream->sib_prev) { |
788 | 0 | unlink_sib(stream); |
789 | 0 | } else { |
790 | 0 | unlink_dep(stream); |
791 | 0 | } |
792 | |
|
793 | 0 | stream->sum_dep_weight = 0; |
794 | |
|
795 | 0 | stream->dep_prev = NULL; |
796 | 0 | stream->dep_next = NULL; |
797 | 0 | stream->sib_prev = NULL; |
798 | 0 | stream->sib_next = NULL; |
799 | |
|
800 | 0 | validate_tree(dep_prev); |
801 | |
|
802 | 0 | return 0; |
803 | 0 | } |
804 | | |
805 | | int nghttp2_stream_dep_insert_subtree(nghttp2_stream *dep_stream, |
806 | 0 | nghttp2_stream *stream) { |
807 | 0 | nghttp2_stream *last_sib; |
808 | 0 | nghttp2_stream *dep_next; |
809 | 0 | nghttp2_stream *si; |
810 | 0 | int rv; |
811 | |
|
812 | 0 | DEBUGF("stream: dep_insert_subtree dep_stream(%p)=%d stream(%p)=%d\n", |
813 | 0 | dep_stream, dep_stream->stream_id, stream, stream->stream_id); |
814 | |
|
815 | 0 | stream->sum_dep_weight += dep_stream->sum_dep_weight; |
816 | 0 | dep_stream->sum_dep_weight = stream->weight; |
817 | |
|
818 | 0 | if (dep_stream->dep_next) { |
819 | 0 | dep_next = dep_stream->dep_next; |
820 | |
|
821 | 0 | link_dep(dep_stream, stream); |
822 | |
|
823 | 0 | if (stream->dep_next) { |
824 | 0 | last_sib = stream_last_sib(stream->dep_next); |
825 | |
|
826 | 0 | link_sib(last_sib, dep_next); |
827 | 0 | } else { |
828 | 0 | link_dep(stream, dep_next); |
829 | 0 | } |
830 | |
|
831 | 0 | for (si = dep_next; si; si = si->sib_next) { |
832 | 0 | si->dep_prev = stream; |
833 | 0 | if (si->queued) { |
834 | 0 | rv = stream_obq_move(stream, dep_stream, si); |
835 | 0 | if (rv != 0) { |
836 | 0 | return rv; |
837 | 0 | } |
838 | 0 | } |
839 | 0 | } |
840 | 0 | } else { |
841 | 0 | link_dep(dep_stream, stream); |
842 | 0 | } |
843 | | |
844 | 0 | if (stream_subtree_active(stream)) { |
845 | 0 | rv = stream_obq_push(dep_stream, stream); |
846 | 0 | if (rv != 0) { |
847 | 0 | return rv; |
848 | 0 | } |
849 | 0 | } |
850 | | |
851 | 0 | validate_tree(dep_stream); |
852 | |
|
853 | 0 | return 0; |
854 | 0 | } |
855 | | |
856 | | int nghttp2_stream_dep_add_subtree(nghttp2_stream *dep_stream, |
857 | 0 | nghttp2_stream *stream) { |
858 | 0 | int rv; |
859 | |
|
860 | 0 | DEBUGF("stream: dep_add_subtree dep_stream(%p)=%d stream(%p)=%d\n", |
861 | 0 | dep_stream, dep_stream->stream_id, stream, stream->stream_id); |
862 | |
|
863 | 0 | dep_stream->sum_dep_weight += stream->weight; |
864 | |
|
865 | 0 | if (dep_stream->dep_next) { |
866 | 0 | insert_link_dep(dep_stream, stream); |
867 | 0 | } else { |
868 | 0 | link_dep(dep_stream, stream); |
869 | 0 | } |
870 | |
|
871 | 0 | if (stream_subtree_active(stream)) { |
872 | 0 | rv = stream_obq_push(dep_stream, stream); |
873 | 0 | if (rv != 0) { |
874 | 0 | return rv; |
875 | 0 | } |
876 | 0 | } |
877 | | |
878 | 0 | validate_tree(dep_stream); |
879 | |
|
880 | 0 | return 0; |
881 | 0 | } |
882 | | |
883 | 0 | void nghttp2_stream_dep_remove_subtree(nghttp2_stream *stream) { |
884 | 0 | nghttp2_stream *next, *dep_prev; |
885 | |
|
886 | 0 | DEBUGF("stream: dep_remove_subtree stream(%p)=%d\n", stream, |
887 | 0 | stream->stream_id); |
888 | |
|
889 | 0 | assert(stream->dep_prev); |
890 | | |
891 | 0 | dep_prev = stream->dep_prev; |
892 | |
|
893 | 0 | if (stream->sib_prev) { |
894 | 0 | link_sib(stream->sib_prev, stream->sib_next); |
895 | 0 | } else { |
896 | 0 | next = stream->sib_next; |
897 | |
|
898 | 0 | link_dep(dep_prev, next); |
899 | |
|
900 | 0 | if (next) { |
901 | 0 | next->sib_prev = NULL; |
902 | 0 | } |
903 | 0 | } |
904 | |
|
905 | 0 | dep_prev->sum_dep_weight -= stream->weight; |
906 | |
|
907 | 0 | if (stream->queued) { |
908 | 0 | stream_obq_remove(stream); |
909 | 0 | } |
910 | |
|
911 | 0 | validate_tree(dep_prev); |
912 | |
|
913 | 0 | stream->sib_prev = NULL; |
914 | 0 | stream->sib_next = NULL; |
915 | 0 | stream->dep_prev = NULL; |
916 | 0 | } |
917 | | |
918 | 0 | int nghttp2_stream_in_dep_tree(nghttp2_stream *stream) { |
919 | 0 | return stream->dep_prev || stream->dep_next || stream->sib_prev || |
920 | 0 | stream->sib_next; |
921 | 0 | } |
922 | | |
923 | | nghttp2_outbound_item * |
924 | 0 | nghttp2_stream_next_outbound_item(nghttp2_stream *stream) { |
925 | 0 | nghttp2_pq_entry *ent; |
926 | 0 | nghttp2_stream *si; |
927 | |
|
928 | 0 | for (;;) { |
929 | 0 | if (stream_active(stream)) { |
930 | | /* Update ascendant's descendant_last_cycle here, so that we can |
931 | | assure that new stream is scheduled based on it. */ |
932 | 0 | for (si = stream; si->dep_prev; si = si->dep_prev) { |
933 | 0 | si->dep_prev->descendant_last_cycle = si->cycle; |
934 | 0 | } |
935 | 0 | return stream->item; |
936 | 0 | } |
937 | 0 | ent = nghttp2_pq_top(&stream->obq); |
938 | 0 | if (!ent) { |
939 | 0 | return NULL; |
940 | 0 | } |
941 | 0 | stream = nghttp2_struct_of(ent, nghttp2_stream, pq_entry); |
942 | 0 | } |
943 | 0 | } |
944 | | |
945 | 0 | nghttp2_stream_proto_state nghttp2_stream_get_state(nghttp2_stream *stream) { |
946 | 0 | if (stream->flags & NGHTTP2_STREAM_FLAG_CLOSED) { |
947 | 0 | return NGHTTP2_STREAM_STATE_CLOSED; |
948 | 0 | } |
949 | | |
950 | 0 | if (stream->flags & NGHTTP2_STREAM_FLAG_PUSH) { |
951 | 0 | if (stream->shut_flags & NGHTTP2_SHUT_RD) { |
952 | 0 | return NGHTTP2_STREAM_STATE_RESERVED_LOCAL; |
953 | 0 | } |
954 | | |
955 | 0 | if (stream->shut_flags & NGHTTP2_SHUT_WR) { |
956 | 0 | return NGHTTP2_STREAM_STATE_RESERVED_REMOTE; |
957 | 0 | } |
958 | 0 | } |
959 | | |
960 | 0 | if (stream->shut_flags & NGHTTP2_SHUT_RD) { |
961 | 0 | return NGHTTP2_STREAM_STATE_HALF_CLOSED_REMOTE; |
962 | 0 | } |
963 | | |
964 | 0 | if (stream->shut_flags & NGHTTP2_SHUT_WR) { |
965 | 0 | return NGHTTP2_STREAM_STATE_HALF_CLOSED_LOCAL; |
966 | 0 | } |
967 | | |
968 | 0 | if (stream->state == NGHTTP2_STREAM_IDLE) { |
969 | 0 | return NGHTTP2_STREAM_STATE_IDLE; |
970 | 0 | } |
971 | | |
972 | 0 | return NGHTTP2_STREAM_STATE_OPEN; |
973 | 0 | } |
974 | | |
975 | 0 | nghttp2_stream *nghttp2_stream_get_parent(nghttp2_stream *stream) { |
976 | 0 | return stream->dep_prev; |
977 | 0 | } |
978 | | |
979 | 0 | nghttp2_stream *nghttp2_stream_get_next_sibling(nghttp2_stream *stream) { |
980 | 0 | return stream->sib_next; |
981 | 0 | } |
982 | | |
983 | 0 | nghttp2_stream *nghttp2_stream_get_previous_sibling(nghttp2_stream *stream) { |
984 | 0 | return stream->sib_prev; |
985 | 0 | } |
986 | | |
987 | 0 | nghttp2_stream *nghttp2_stream_get_first_child(nghttp2_stream *stream) { |
988 | 0 | return stream->dep_next; |
989 | 0 | } |
990 | | |
991 | 0 | int32_t nghttp2_stream_get_weight(nghttp2_stream *stream) { |
992 | 0 | return stream->weight; |
993 | 0 | } |
994 | | |
995 | 0 | int32_t nghttp2_stream_get_sum_dependency_weight(nghttp2_stream *stream) { |
996 | 0 | return stream->sum_dep_weight; |
997 | 0 | } |
998 | | |
999 | 0 | int32_t nghttp2_stream_get_stream_id(nghttp2_stream *stream) { |
1000 | 0 | return stream->stream_id; |
1001 | 0 | } |