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