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
  33 void nghttp2_stream_init(nghttp2_stream *stream, int32_t stream_id,
  34                          uint8_t flags, nghttp2_stream_state initial_state,
  35                          int32_t weight, nghttp2_stream_roots *roots,
  36                          int32_t remote_initial_window_size,
  37                          int32_t local_initial_window_size,
  38                          void *stream_user_data) {
  39   nghttp2_map_entry_init(&stream->map_entry, stream_id);
  40   stream->stream_id = stream_id;
  41   stream->flags = flags;
  42   stream->state = initial_state;
  43   stream->shut_flags = NGHTTP2_SHUT_NONE;
  44   stream->stream_user_data = stream_user_data;
  45   stream->item = NULL;
  46   stream->remote_window_size = remote_initial_window_size;
  47   stream->local_window_size = local_initial_window_size;
  48   stream->recv_window_size = 0;
  49   stream->consumed_size = 0;
  50   stream->recv_reduction = 0;
  51
  52   stream->dep_prev = NULL;
  53   stream->dep_next = NULL;
  54   stream->sib_prev = NULL;
  55   stream->sib_next = NULL;
  56
  57   stream->closed_prev = NULL;
  58   stream->closed_next = NULL;
  59
  60   stream->dpri = NGHTTP2_STREAM_DPRI_NO_ITEM;
  61   stream->num_substreams = 1;
  62   stream->weight = weight;
  63   stream->effective_weight = stream->weight;
  64   stream->sum_dep_weight = 0;
  65   stream->sum_norest_weight = 0;
  66   stream->sum_top_weight = 0;
  67
  68   stream->roots = roots;
  69   stream->root_prev = NULL;
  70   stream->root_next = NULL;
  71 }
  72
  73 void nghttp2_stream_free(nghttp2_stream *stream _U_) {
  74   /* We don't free stream->item.  If it is assigned to aob, then
  75      active_outbound_item_reset() will delete it.  If it is queued,
  76      then it is deleted when pq is deleted in nghttp2_session_del().
  77      Otherwise, nghttp2_session_del() will delete it. */
  78 }
  79
  80 void nghttp2_stream_shutdown(nghttp2_stream *stream, nghttp2_shut_flag flag) {
  81   stream->shut_flags |= flag;
  82 }
  83
  84 static int stream_push_item(nghttp2_stream *stream, nghttp2_session *session) {
  85   int rv;
  86   nghttp2_outbound_item *item;
  87
  88   assert(stream->item);
  89   assert(stream->item->queued == 0);
  90
  91   item = stream->item;
  92
  93   /* If item is now sent, don't push it to the queue.  Otherwise, we
  94      may push same item twice. */
  95   if (session->aob.item == item) {
  96     return 0;
  97   }
  98
  99   if (item->weight > stream->effective_weight) {
 100     item->weight = stream->effective_weight;
 101   }
 102
 103   item->cycle = session->last_cycle;
 104
 105   switch (item->frame.hd.type) {
 106   case NGHTTP2_DATA:
 107     rv = nghttp2_pq_push(&session->ob_da_pq, item);
 108     break;
 109   case NGHTTP2_HEADERS:
 110     if (stream->state == NGHTTP2_STREAM_RESERVED) {
 111       rv = nghttp2_pq_push(&session->ob_ss_pq, item);
 112     } else {
 113       rv = nghttp2_pq_push(&session->ob_pq, item);
 114     }
 115     break;
 116   default:
 117     /* should not reach here */
 118     assert(0);
 119   }
 120
 121   if (rv != 0) {
 122     return rv;
 123   }
 124
 125   item->queued = 1;
 126
 127   return 0;
 128 }
 129
 130 static nghttp2_stream *stream_first_sib(nghttp2_stream *stream) {
 131   for (; stream->sib_prev; stream = stream->sib_prev)
 132     ;
 133
 134   return stream;
 135 }
 136
 137 static nghttp2_stream *stream_last_sib(nghttp2_stream *stream) {
 138   for (; stream->sib_next; stream = stream->sib_next)
 139     ;
 140
 141   return stream;
 142 }
 143
 144 static nghttp2_stream *stream_update_dep_length(nghttp2_stream *stream,
 145                                                 ssize_t delta) {
 146   stream->num_substreams += delta;
 147
 148   stream = stream_first_sib(stream);
 149
 150   if (stream->dep_prev) {
 151     return stream_update_dep_length(stream->dep_prev, delta);
 152   }
 153
 154   return stream;
 155 }
 156
 157 int32_t nghttp2_stream_dep_distributed_weight(nghttp2_stream *stream,
 158                                               int32_t weight) {
 159   weight = stream->weight * weight / stream->sum_dep_weight;
 160
 161   return nghttp2_max(1, weight);
 162 }
 163
 164 int32_t nghttp2_stream_dep_distributed_effective_weight(nghttp2_stream *stream,
 165                                                         int32_t weight) {
 166   if (stream->sum_norest_weight == 0) {
 167     return stream->effective_weight;
 168   }
 169
 170   weight = stream->effective_weight * weight / stream->sum_norest_weight;
 171
 172   return nghttp2_max(1, weight);
 173 }
 174
 175 static int32_t
 176 stream_dep_distributed_top_effective_weight(nghttp2_stream *stream,
 177                                             int32_t weight) {
 178   if (stream->sum_top_weight == 0) {
 179     return stream->effective_weight;
 180   }
 181
 182   weight = stream->effective_weight * weight / stream->sum_top_weight;
 183
 184   return nghttp2_max(1, weight);
 185 }
 186
 187 static void stream_update_dep_set_rest(nghttp2_stream *stream);
 188
 189 /* Updates effective_weight of descendant streams in subtree of
 190    |stream|.  We assume that stream->effective_weight is already set
 191    right. */
 192 static void stream_update_dep_effective_weight(nghttp2_stream *stream) {
 193   nghttp2_stream *si;
 194
 195   DEBUGF(fprintf(stderr, "stream: update_dep_effective_weight "
 196                          "stream(%p)=%d, weight=%d, sum_norest_weight=%d, "
 197                          "sum_top_weight=%d\n",
 198                  stream, stream->stream_id, stream->weight,
 199                  stream->sum_norest_weight, stream->sum_top_weight));
 200
 201   /* stream->sum_norest_weight == 0 means there is no
 202      NGHTTP2_STREAM_DPRI_TOP under stream */
 203   if (stream->dpri != NGHTTP2_STREAM_DPRI_NO_ITEM ||
 204       stream->sum_norest_weight == 0) {
 205     return;
 206   }
 207
 208   /* If there is no direct descendant whose dpri is
 209      NGHTTP2_STREAM_DPRI_TOP, indirect descendants have the chance to
 210      send data, so recursively set weight for descendants. */
 211   if (stream->sum_top_weight == 0) {
 212     for (si = stream->dep_next; si; si = si->sib_next) {
 213       if (si->dpri != NGHTTP2_STREAM_DPRI_REST) {
 214         si->effective_weight =
 215             nghttp2_stream_dep_distributed_effective_weight(stream, si->weight);
 216       }
 217
 218       stream_update_dep_effective_weight(si);
 219     }
 220     return;
 221   }
 222
 223   /* If there is at least one direct descendant whose dpri is
 224      NGHTTP2_STREAM_DPRI_TOP, we won't give a chance to indirect
 225      descendants, since closed or blocked stream's weight is
 226      distributed among its siblings */
 227   for (si = stream->dep_next; si; si = si->sib_next) {
 228     if (si->dpri == NGHTTP2_STREAM_DPRI_TOP) {
 229       si->effective_weight =
 230           stream_dep_distributed_top_effective_weight(stream, si->weight);
 231
 232       DEBUGF(fprintf(stderr, "stream: stream=%d top eweight=%d\n",
 233                      si->stream_id, si->effective_weight));
 234
 235       continue;
 236     }
 237
 238     if (si->dpri == NGHTTP2_STREAM_DPRI_NO_ITEM) {
 239       DEBUGF(fprintf(stderr, "stream: stream=%d no_item, ignored\n",
 240                      si->stream_id));
 241
 242       /* Since we marked NGHTTP2_STREAM_DPRI_TOP under si, we make
 243          them NGHTTP2_STREAM_DPRI_REST again. */
 244       stream_update_dep_set_rest(si->dep_next);
 245     } else {
 246       DEBUGF(
 247           fprintf(stderr, "stream: stream=%d rest, ignored\n", si->stream_id));
 248     }
 249   }
 250 }
 251
 252 static void stream_update_dep_set_rest(nghttp2_stream *stream) {
 253   if (stream == NULL) {
 254     return;
 255   }
 256
 257   DEBUGF(fprintf(stderr, "stream: stream=%d is rest\n", stream->stream_id));
 258
 259   if (stream->dpri == NGHTTP2_STREAM_DPRI_REST) {
 260     return;
 261   }
 262
 263   if (stream->dpri == NGHTTP2_STREAM_DPRI_TOP) {
 264     stream->dpri = NGHTTP2_STREAM_DPRI_REST;
 265
 266     stream_update_dep_set_rest(stream->sib_next);
 267
 268     return;
 269   }
 270
 271   stream_update_dep_set_rest(stream->sib_next);
 272   stream_update_dep_set_rest(stream->dep_next);
 273 }
 274
 275 /*
 276  * Performs dfs starting |stream|, search stream which can become
 277  * NGHTTP2_STREAM_DPRI_TOP and set its dpri.
 278  */
 279 static void stream_update_dep_set_top(nghttp2_stream *stream) {
 280   nghttp2_stream *si;
 281
 282   if (stream->dpri == NGHTTP2_STREAM_DPRI_TOP) {
 283     return;
 284   }
 285
 286   if (stream->dpri == NGHTTP2_STREAM_DPRI_REST) {
 287     DEBUGF(
 288         fprintf(stderr, "stream: stream=%d item is top\n", stream->stream_id));
 289
 290     stream->dpri = NGHTTP2_STREAM_DPRI_TOP;
 291
 292     return;
 293   }
 294
 295   for (si = stream->dep_next; si; si = si->sib_next) {
 296     stream_update_dep_set_top(si);
 297   }
 298 }
 299
 300 /*
 301  * Performs dfs starting |stream|, and dueue stream whose dpri is
 302  * NGHTTP2_STREAM_DPRI_TOP and has not been queued yet.
 303  *
 304  * This function returns 0 if it succeeds, or one of the following
 305  * negative error codes:
 306  *
 307  * NGHTTP2_ERR_NOMEM
 308  *     Out of memory.
 309  */
 310 static int stream_update_dep_queue_top(nghttp2_stream *stream,
 311                                        nghttp2_session *session) {
 312   int rv;
 313   nghttp2_stream *si;
 314
 315   if (stream->dpri == NGHTTP2_STREAM_DPRI_REST) {
 316     return 0;
 317   }
 318
 319   if (stream->dpri == NGHTTP2_STREAM_DPRI_TOP) {
 320     if (!stream->item->queued) {
 321       DEBUGF(fprintf(stderr, "stream: stream=%d enqueue\n", stream->stream_id));
 322       rv = stream_push_item(stream, session);
 323
 324       if (rv != 0) {
 325         return rv;
 326       }
 327     }
 328
 329     return 0;
 330   }
 331
 332   for (si = stream->dep_next; si; si = si->sib_next) {
 333     rv = stream_update_dep_queue_top(si, session);
 334
 335     if (rv != 0) {
 336       return rv;
 337     }
 338   }
 339
 340   return 0;
 341 }
 342
 343 /*
 344  * Updates stream->sum_norest_weight and stream->sum_top_weight
 345  * recursively.  We have to gather effective sum of weight of
 346  * descendants.  If stream->dpri == NGHTTP2_STREAM_DPRI_NO_ITEM, we
 347  * have to go deeper and check that any of its descendants has dpri
 348  * value of NGHTTP2_STREAM_DPRI_TOP.  If so, we have to add weight of
 349  * its direct descendants to stream->sum_norest_weight.  To make this
 350  * work, this function returns 1 if any of its descendants has dpri
 351  * value of NGHTTP2_STREAM_DPRI_TOP, otherwise 0.
 352  *
 353  * Calculating stream->sum_top-weight is very simple compared to
 354  * stream->sum_norest_weight.  It just adds up the weight of direct
 355  * descendants whose dpri is NGHTTP2_STREAM_DPRI_TOP.
 356  */
 357 static int stream_update_dep_sum_norest_weight(nghttp2_stream *stream) {
 358   nghttp2_stream *si;
 359   int rv;
 360
 361   stream->sum_norest_weight = 0;
 362   stream->sum_top_weight = 0;
 363
 364   if (stream->dpri == NGHTTP2_STREAM_DPRI_TOP) {
 365     return 1;
 366   }
 367
 368   if (stream->dpri == NGHTTP2_STREAM_DPRI_REST) {
 369     return 0;
 370   }
 371
 372   rv = 0;
 373
 374   for (si = stream->dep_next; si; si = si->sib_next) {
 375
 376     if (stream_update_dep_sum_norest_weight(si)) {
 377       rv = 1;
 378       stream->sum_norest_weight += si->weight;
 379     }
 380
 381     if (si->dpri == NGHTTP2_STREAM_DPRI_TOP) {
 382       stream->sum_top_weight += si->weight;
 383     }
 384   }
 385
 386   return rv;
 387 }
 388
 389 static int stream_update_dep_on_attach_item(nghttp2_stream *stream,
 390                                             nghttp2_session *session) {
 391   nghttp2_stream *root_stream;
 392
 393   stream->dpri = NGHTTP2_STREAM_DPRI_REST;
 394
 395   stream_update_dep_set_rest(stream->dep_next);
 396
 397   root_stream = nghttp2_stream_get_dep_root(stream);
 398
 399   DEBUGF(fprintf(stderr, "root=%p, stream=%p\n", root_stream, stream));
 400
 401   stream_update_dep_set_top(root_stream);
 402
 403   stream_update_dep_sum_norest_weight(root_stream);
 404   stream_update_dep_effective_weight(root_stream);
 405
 406   return stream_update_dep_queue_top(root_stream, session);
 407 }
 408
 409 static int stream_update_dep_on_detach_item(nghttp2_stream *stream,
 410                                             nghttp2_session *session) {
 411   nghttp2_stream *root_stream;
 412
 413   stream->dpri = NGHTTP2_STREAM_DPRI_NO_ITEM;
 414
 415   root_stream = nghttp2_stream_get_dep_root(stream);
 416
 417   stream_update_dep_set_top(root_stream);
 418
 419   stream_update_dep_sum_norest_weight(root_stream);
 420   stream_update_dep_effective_weight(root_stream);
 421
 422   return stream_update_dep_queue_top(root_stream, session);
 423 }
 424
 425 int nghttp2_stream_attach_item(nghttp2_stream *stream,
 426                                nghttp2_outbound_item *item,
 427                                nghttp2_session *session) {
 428   assert((stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL) == 0);
 429   assert(stream->item == NULL);
 430
 431   DEBUGF(fprintf(stderr, "stream: stream=%d attach item=%p\n",
 432                  stream->stream_id, item));
 433
 434   stream->item = item;
 435
 436   return stream_update_dep_on_attach_item(stream, session);
 437 }
 438
 439 int nghttp2_stream_detach_item(nghttp2_stream *stream,
 440                                nghttp2_session *session) {
 441   DEBUGF(fprintf(stderr, "stream: stream=%d detach item=%p\n",
 442                  stream->stream_id, stream->item));
 443
 444   stream->item = NULL;
 445   stream->flags &= ~NGHTTP2_STREAM_FLAG_DEFERRED_ALL;
 446
 447   return stream_update_dep_on_detach_item(stream, session);
 448 }
 449
 450 int nghttp2_stream_defer_item(nghttp2_stream *stream, uint8_t flags,
 451                               nghttp2_session *session) {
 452   assert(stream->item);
 453
 454   DEBUGF(fprintf(stderr, "stream: stream=%d defer item=%p cause=%02x\n",
 455                  stream->stream_id, stream->item, flags));
 456
 457   stream->flags |= flags;
 458
 459   return stream_update_dep_on_detach_item(stream, session);
 460 }
 461
 462 int nghttp2_stream_resume_deferred_item(nghttp2_stream *stream, uint8_t flags,
 463                                         nghttp2_session *session) {
 464   assert(stream->item);
 465
 466   DEBUGF(fprintf(stderr, "stream: stream=%d resume item=%p flags=%02x\n",
 467                  stream->stream_id, stream->item, flags));
 468
 469   stream->flags &= ~flags;
 470
 471   if (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL) {
 472     return 0;
 473   }
 474
 475   return stream_update_dep_on_attach_item(stream, session);
 476 }
 477
 478 int nghttp2_stream_check_deferred_item(nghttp2_stream *stream) {
 479   return stream->item && (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_ALL);
 480 }
 481
 482 int nghttp2_stream_check_deferred_by_flow_control(nghttp2_stream *stream) {
 483   return stream->item &&
 484          (stream->flags & NGHTTP2_STREAM_FLAG_DEFERRED_FLOW_CONTROL);
 485 }
 486
 487 static int update_initial_window_size(int32_t *window_size_ptr,
 488                                       int32_t new_initial_window_size,
 489                                       int32_t old_initial_window_size) {
 490   int64_t new_window_size = (int64_t)(*window_size_ptr) +
 491                             new_initial_window_size - old_initial_window_size;
 492   if (INT32_MIN > new_window_size ||
 493       new_window_size > NGHTTP2_MAX_WINDOW_SIZE) {
 494     return -1;
 495   }
 496   *window_size_ptr = (int32_t)new_window_size;
 497   return 0;
 498 }
 499
 500 int nghttp2_stream_update_remote_initial_window_size(
 501     nghttp2_stream *stream, int32_t new_initial_window_size,
 502     int32_t old_initial_window_size) {
 503   return update_initial_window_size(&stream->remote_window_size,
 504                                     new_initial_window_size,
 505                                     old_initial_window_size);
 506 }
 507
 508 int nghttp2_stream_update_local_initial_window_size(
 509     nghttp2_stream *stream, int32_t new_initial_window_size,
 510     int32_t old_initial_window_size) {
 511   return update_initial_window_size(&stream->local_window_size,
 512                                     new_initial_window_size,
 513                                     old_initial_window_size);
 514 }
 515
 516 void nghttp2_stream_promise_fulfilled(nghttp2_stream *stream) {
 517   stream->state = NGHTTP2_STREAM_OPENED;
 518 }
 519
 520 nghttp2_stream *nghttp2_stream_get_dep_root(nghttp2_stream *stream) {
 521   for (;;) {
 522     if (stream->sib_prev) {
 523       stream = stream->sib_prev;
 524
 525       continue;
 526     }
 527
 528     if (stream->dep_prev) {
 529       stream = stream->dep_prev;
 530
 531       continue;
 532     }
 533
 534     break;
 535   }
 536
 537   return stream;
 538 }
 539
 540 int nghttp2_stream_dep_subtree_find(nghttp2_stream *stream,
 541                                     nghttp2_stream *target) {
 542   if (stream == NULL) {
 543     return 0;
 544   }
 545
 546   if (stream == target) {
 547     return 1;
 548   }
 549
 550   if (nghttp2_stream_dep_subtree_find(stream->sib_next, target)) {
 551     return 1;
 552   }
 553
 554   return nghttp2_stream_dep_subtree_find(stream->dep_next, target);
 555 }
 556
 557 void nghttp2_stream_dep_insert(nghttp2_stream *dep_stream,
 558                                nghttp2_stream *stream) {
 559   nghttp2_stream *si;
 560   nghttp2_stream *root_stream;
 561
 562   assert(stream->item == NULL);
 563
 564   DEBUGF(fprintf(stderr,
 565                  "stream: dep_insert dep_stream(%p)=%d, stream(%p)=%d\n",
 566                  dep_stream, dep_stream->stream_id, stream, stream->stream_id));
 567
 568   stream->sum_dep_weight = dep_stream->sum_dep_weight;
 569   dep_stream->sum_dep_weight = stream->weight;
 570
 571   if (dep_stream->dep_next) {
 572     for (si = dep_stream->dep_next; si; si = si->sib_next) {
 573       stream->num_substreams += si->num_substreams;
 574     }
 575
 576     stream->dep_next = dep_stream->dep_next;
 577     stream->dep_next->dep_prev = stream;
 578   }
 579
 580   dep_stream->dep_next = stream;
 581   stream->dep_prev = dep_stream;
 582
 583   root_stream = stream_update_dep_length(dep_stream, 1);
 584
 585   stream_update_dep_sum_norest_weight(root_stream);
 586   stream_update_dep_effective_weight(root_stream);
 587
 588   ++stream->roots->num_streams;
 589 }
 590
 591 static void link_dep(nghttp2_stream *dep_stream, nghttp2_stream *stream) {
 592   dep_stream->dep_next = stream;
 593   stream->dep_prev = dep_stream;
 594 }
 595
 596 static void link_sib(nghttp2_stream *prev_stream, nghttp2_stream *stream) {
 597   prev_stream->sib_next = stream;
 598   stream->sib_prev = prev_stream;
 599 }
 600
 601 static void insert_link_dep(nghttp2_stream *dep_stream,
 602                             nghttp2_stream *stream) {
 603   nghttp2_stream *sib_next;
 604
 605   assert(stream->sib_prev == NULL);
 606
 607   sib_next = dep_stream->dep_next;
 608
 609   link_sib(stream, sib_next);
 610
 611   sib_next->dep_prev = NULL;
 612
 613   link_dep(dep_stream, stream);
 614 }
 615
 616 static void unlink_sib(nghttp2_stream *stream) {
 617   nghttp2_stream *prev, *next, *dep_next;
 618
 619   prev = stream->sib_prev;
 620   dep_next = stream->dep_next;
 621
 622   assert(prev);
 623
 624   if (dep_next) {
 625     /*
 626      *  prev--stream(--sib_next--...)
 627      *         |
 628      *        dep_next
 629      */
 630     dep_next->dep_prev = NULL;
 631
 632     link_sib(prev, dep_next);
 633
 634     if (stream->sib_next) {
 635       link_sib(stream_last_sib(dep_next), stream->sib_next);
 636     }
 637   } else {
 638     /*
 639      *  prev--stream(--sib_next--...)
 640      */
 641     next = stream->sib_next;
 642
 643     prev->sib_next = next;
 644
 645     if (next) {
 646       next->sib_prev = prev;
 647     }
 648   }
 649 }
 650
 651 static void unlink_dep(nghttp2_stream *stream) {
 652   nghttp2_stream *prev, *next, *dep_next;
 653
 654   prev = stream->dep_prev;
 655   dep_next = stream->dep_next;
 656
 657   assert(prev);
 658
 659   if (dep_next) {
 660     /*
 661      * prev
 662      *   |
 663      * stream(--sib_next--...)
 664      *   |
 665      * dep_next
 666      */
 667     link_dep(prev, dep_next);
 668
 669     if (stream->sib_next) {
 670       link_sib(stream_last_sib(dep_next), stream->sib_next);
 671     }
 672   } else if (stream->sib_next) {
 673     /*
 674      * prev
 675      *   |
 676      * stream--sib_next
 677      */
 678     next = stream->sib_next;
 679
 680     next->sib_prev = NULL;
 681
 682     link_dep(prev, next);
 683   } else {
 684     prev->dep_next = NULL;
 685   }
 686 }
 687
 688 void nghttp2_stream_dep_add(nghttp2_stream *dep_stream,
 689                             nghttp2_stream *stream) {
 690   nghttp2_stream *root_stream;
 691
 692   assert(stream->item == NULL);
 693
 694   DEBUGF(fprintf(stderr, "stream: dep_add dep_stream(%p)=%d, stream(%p)=%d\n",
 695                  dep_stream, dep_stream->stream_id, stream, stream->stream_id));
 696
 697   root_stream = stream_update_dep_length(dep_stream, 1);
 698
 699   dep_stream->sum_dep_weight += stream->weight;
 700
 701   if (dep_stream->dep_next == NULL) {
 702     link_dep(dep_stream, stream);
 703   } else {
 704     insert_link_dep(dep_stream, stream);
 705   }
 706
 707   stream_update_dep_sum_norest_weight(root_stream);
 708   stream_update_dep_effective_weight(root_stream);
 709
 710   ++stream->roots->num_streams;
 711 }
 712
 713 void nghttp2_stream_dep_remove(nghttp2_stream *stream) {
 714   nghttp2_stream *prev, *next, *dep_prev, *si, *root_stream;
 715   int32_t sum_dep_weight_delta;
 716
 717   root_stream = NULL;
 718
 719   DEBUGF(fprintf(stderr, "stream: dep_remove stream(%p)=%d\n", stream,
 720                  stream->stream_id));
 721
 722   /* Distribute weight of |stream| to direct descendants */
 723   sum_dep_weight_delta = -stream->weight;
 724
 725   for (si = stream->dep_next; si; si = si->sib_next) {
 726     si->weight = nghttp2_stream_dep_distributed_weight(stream, si->weight);
 727
 728     sum_dep_weight_delta += si->weight;
 729   }
 730
 731   prev = stream_first_sib(stream);
 732
 733   dep_prev = prev->dep_prev;
 734
 735   if (dep_prev) {
 736     root_stream = stream_update_dep_length(dep_prev, -1);
 737
 738     dep_prev->sum_dep_weight += sum_dep_weight_delta;
 739   }
 740
 741   if (stream->sib_prev) {
 742     unlink_sib(stream);
 743   } else if (stream->dep_prev) {
 744     unlink_dep(stream);
 745   } else {
 746     nghttp2_stream_roots_remove(stream->roots, stream);
 747
 748     /* stream is a root of tree.  Removing stream makes its
 749        descendants a root of its own subtree. */
 750
 751     for (si = stream->dep_next; si;) {
 752       next = si->sib_next;
 753
 754       si->dep_prev = NULL;
 755       si->sib_prev = NULL;
 756       si->sib_next = NULL;
 757
 758       /* We already distributed weight of |stream| to this. */
 759       si->effective_weight = si->weight;
 760
 761       nghttp2_stream_roots_add(si->roots, si);
 762
 763       si = next;
 764     }
 765   }
 766
 767   if (root_stream) {
 768     stream_update_dep_sum_norest_weight(root_stream);
 769     stream_update_dep_effective_weight(root_stream);
 770   }
 771
 772   stream->num_substreams = 1;
 773   stream->sum_dep_weight = 0;
 774
 775   stream->dep_prev = NULL;
 776   stream->dep_next = NULL;
 777   stream->sib_prev = NULL;
 778   stream->sib_next = NULL;
 779
 780   --stream->roots->num_streams;
 781 }
 782
 783 int nghttp2_stream_dep_insert_subtree(nghttp2_stream *dep_stream,
 784                                       nghttp2_stream *stream,
 785                                       nghttp2_session *session) {
 786   nghttp2_stream *last_sib;
 787   nghttp2_stream *dep_next;
 788   nghttp2_stream *root_stream;
 789   size_t delta_substreams;
 790
 791   DEBUGF(fprintf(stderr, "stream: dep_insert_subtree dep_stream(%p)=%d "
 792                          "stream(%p)=%d\n",
 793                  dep_stream, dep_stream->stream_id, stream, stream->stream_id));
 794
 795   delta_substreams = stream->num_substreams;
 796
 797   stream_update_dep_set_rest(stream);
 798
 799   if (dep_stream->dep_next) {
 800     /* dep_stream->num_substreams includes dep_stream itself */
 801     stream->num_substreams += dep_stream->num_substreams - 1;
 802
 803     stream->sum_dep_weight += dep_stream->sum_dep_weight;
 804     dep_stream->sum_dep_weight = stream->weight;
 805
 806     dep_next = dep_stream->dep_next;
 807
 808     stream_update_dep_set_rest(dep_next);
 809
 810     link_dep(dep_stream, stream);
 811
 812     if (stream->dep_next) {
 813       last_sib = stream_last_sib(stream->dep_next);
 814
 815       link_sib(last_sib, dep_next);
 816
 817       dep_next->dep_prev = NULL;
 818     } else {
 819       link_dep(stream, dep_next);
 820     }
 821   } else {
 822     link_dep(dep_stream, stream);
 823
 824     assert(dep_stream->sum_dep_weight == 0);
 825     dep_stream->sum_dep_weight = stream->weight;
 826   }
 827
 828   root_stream = stream_update_dep_length(dep_stream, delta_substreams);
 829
 830   stream_update_dep_set_top(root_stream);
 831
 832   stream_update_dep_sum_norest_weight(root_stream);
 833   stream_update_dep_effective_weight(root_stream);
 834
 835   return stream_update_dep_queue_top(root_stream, session);
 836 }
 837
 838 int nghttp2_stream_dep_add_subtree(nghttp2_stream *dep_stream,
 839                                    nghttp2_stream *stream,
 840                                    nghttp2_session *session) {
 841   nghttp2_stream *root_stream;
 842
 843   DEBUGF(fprintf(stderr, "stream: dep_add_subtree dep_stream(%p)=%d "
 844                          "stream(%p)=%d\n",
 845                  dep_stream, dep_stream->stream_id, stream, stream->stream_id));
 846
 847   stream_update_dep_set_rest(stream);
 848
 849   if (dep_stream->dep_next) {
 850     dep_stream->sum_dep_weight += stream->weight;
 851
 852     insert_link_dep(dep_stream, stream);
 853   } else {
 854     link_dep(dep_stream, stream);
 855
 856     assert(dep_stream->sum_dep_weight == 0);
 857     dep_stream->sum_dep_weight = stream->weight;
 858   }
 859
 860   root_stream = stream_update_dep_length(dep_stream, stream->num_substreams);
 861
 862   stream_update_dep_set_top(root_stream);
 863
 864   stream_update_dep_sum_norest_weight(root_stream);
 865   stream_update_dep_effective_weight(root_stream);
 866
 867   return stream_update_dep_queue_top(root_stream, session);
 868 }
 869
 870 void nghttp2_stream_dep_remove_subtree(nghttp2_stream *stream) {
 871   nghttp2_stream *prev, *next, *dep_prev, *root_stream;
 872
 873   DEBUGF(fprintf(stderr, "stream: dep_remove_subtree stream(%p)=%d\n", stream,
 874                  stream->stream_id));
 875
 876   if (stream->sib_prev) {
 877     prev = stream->sib_prev;
 878
 879     prev->sib_next = stream->sib_next;
 880     if (prev->sib_next) {
 881       prev->sib_next->sib_prev = prev;
 882     }
 883
 884     prev = stream_first_sib(prev);
 885
 886     dep_prev = prev->dep_prev;
 887
 888   } else if (stream->dep_prev) {
 889     dep_prev = stream->dep_prev;
 890     next = stream->sib_next;
 891
 892     dep_prev->dep_next = next;
 893
 894     if (next) {
 895       next->dep_prev = dep_prev;
 896
 897       next->sib_prev = NULL;
 898     }
 899
 900   } else {
 901     nghttp2_stream_roots_remove(stream->roots, stream);
 902
 903     dep_prev = NULL;
 904   }
 905
 906   if (dep_prev) {
 907     dep_prev->sum_dep_weight -= stream->weight;
 908
 909     root_stream = stream_update_dep_length(dep_prev, -stream->num_substreams);
 910
 911     stream_update_dep_sum_norest_weight(root_stream);
 912     stream_update_dep_effective_weight(root_stream);
 913   }
 914
 915   stream->sib_prev = NULL;
 916   stream->sib_next = NULL;
 917   stream->dep_prev = NULL;
 918 }
 919
 920 int nghttp2_stream_dep_make_root(nghttp2_stream *stream,
 921                                  nghttp2_session *session) {
 922   DEBUGF(fprintf(stderr, "stream: dep_make_root stream(%p)=%d\n", stream,
 923                  stream->stream_id));
 924
 925   nghttp2_stream_roots_add(stream->roots, stream);
 926
 927   stream_update_dep_set_rest(stream);
 928
 929   stream->effective_weight = stream->weight;
 930
 931   stream_update_dep_set_top(stream);
 932
 933   stream_update_dep_sum_norest_weight(stream);
 934   stream_update_dep_effective_weight(stream);
 935
 936   return stream_update_dep_queue_top(stream, session);
 937 }
 938
 939 int
 940 nghttp2_stream_dep_all_your_stream_are_belong_to_us(nghttp2_stream *stream,
 941                                                     nghttp2_session *session) {
 942   nghttp2_stream *first, *si;
 943
 944   DEBUGF(fprintf(stderr, "stream: ALL YOUR STREAM ARE BELONG TO US "
 945                          "stream(%p)=%d\n",
 946                  stream, stream->stream_id));
 947
 948   first = stream->roots->head;
 949
 950   /* stream must not be include in stream->roots->head list */
 951   assert(first != stream);
 952
 953   if (first) {
 954     nghttp2_stream *prev;
 955
 956     prev = first;
 957
 958     DEBUGF(fprintf(stderr, "stream: root stream(%p)=%d\n", first,
 959                    first->stream_id));
 960
 961     stream->sum_dep_weight += first->weight;
 962     stream->num_substreams += first->num_substreams;
 963
 964     for (si = first->root_next; si; si = si->root_next) {
 965
 966       assert(si != stream);
 967
 968       DEBUGF(
 969           fprintf(stderr, "stream: root stream(%p)=%d\n", si, si->stream_id));
 970
 971       stream->sum_dep_weight += si->weight;
 972       stream->num_substreams += si->num_substreams;
 973
 974       link_sib(prev, si);
 975
 976       prev = si;
 977     }
 978
 979     if (stream->dep_next) {
 980       nghttp2_stream *sib_next;
 981
 982       sib_next = stream->dep_next;
 983
 984       sib_next->dep_prev = NULL;
 985
 986       link_sib(first, sib_next);
 987       link_dep(stream, prev);
 988     } else {
 989       link_dep(stream, first);
 990     }
 991   }
 992
 993   nghttp2_stream_roots_remove_all(stream->roots);
 994
 995   return nghttp2_stream_dep_make_root(stream, session);
 996 }
 997
 998 int nghttp2_stream_in_dep_tree(nghttp2_stream *stream) {
 999   return stream->dep_prev || stream->dep_next || stream->sib_prev ||
1000          stream->sib_next || stream->root_next || stream->root_prev ||
1001          stream->roots->head == stream;
1002 }
1003
1004 void nghttp2_stream_roots_init(nghttp2_stream_roots *roots) {
1005   roots->head = NULL;
1006   roots->num_streams = 0;
1007 }
1008
1009 void nghttp2_stream_roots_free(nghttp2_stream_roots *roots _U_) {}
1010
1011 void nghttp2_stream_roots_add(nghttp2_stream_roots *roots,
1012                               nghttp2_stream *stream) {
1013   if (roots->head) {
1014     stream->root_next = roots->head;
1015     roots->head->root_prev = stream;
1016   }
1017
1018   roots->head = stream;
1019 }
1020
1021 void nghttp2_stream_roots_remove(nghttp2_stream_roots *roots,
1022                                  nghttp2_stream *stream) {
1023   nghttp2_stream *root_prev, *root_next;
1024
1025   root_prev = stream->root_prev;
1026   root_next = stream->root_next;
1027
1028   if (root_prev) {
1029     root_prev->root_next = root_next;
1030
1031     if (root_next) {
1032       root_next->root_prev = root_prev;
1033     }
1034   } else {
1035     if (root_next) {
1036       root_next->root_prev = NULL;
1037     }
1038
1039     roots->head = root_next;
1040   }
1041
1042   stream->root_prev = NULL;
1043   stream->root_next = NULL;
1044 }
1045
1046 void nghttp2_stream_roots_remove_all(nghttp2_stream_roots *roots) {
1047   nghttp2_stream *si, *next;
1048
1049   for (si = roots->head; si;) {
1050     next = si->root_next;
1051
1052     si->root_prev = NULL;
1053     si->root_next = NULL;
1054
1055     si = next;
1056   }
1057
1058   roots->head = NULL;
1059 }