lib/nghttp2_stream.c

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