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