granicus.if.org Git - apache/blob - modules/http2/h2_util.c

   1 /* Copyright 2015 greenbytes GmbH (https://www.greenbytes.de)
   2  *
   3  * Licensed under the Apache License, Version 2.0 (the "License");
   4  * you may not use this file except in compliance with the License.
   5  * You may obtain a copy of the License at
   6  *
   7  * http://www.apache.org/licenses/LICENSE-2.0
   8
   9  * Unless required by applicable law or agreed to in writing, software
  10  * distributed under the License is distributed on an "AS IS" BASIS,
  11  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12  * See the License for the specific language governing permissions and
  13  * limitations under the License.
  14  */
  15
  16 #include <assert.h>
  17 #include <apr_strings.h>
  18 #include <apr_thread_mutex.h>
  19 #include <apr_thread_cond.h>
  20
  21 #include <httpd.h>
  22 #include <http_core.h>
  23 #include <http_log.h>
  24 #include <http_request.h>
  25
  26 #include <nghttp2/nghttp2.h>
  27
  28 #include "h2.h"
  29 #include "h2_util.h"
  30
  31 /* h2_log2(n) iff n is a power of 2 */
  32 unsigned char h2_log2(int n)
  33 {
  34     int lz = 0;
  35     if (!n) {
  36         return 0;
  37     }
  38     if (!(n & 0xffff0000u)) {
  39         lz += 16;
  40         n = (n << 16);
  41     }
  42     if (!(n & 0xff000000u)) {
  43         lz += 8;
  44         n = (n << 8);
  45     }
  46     if (!(n & 0xf0000000u)) {
  47         lz += 4;
  48         n = (n << 4);
  49     }
  50     if (!(n & 0xc0000000u)) {
  51         lz += 2;
  52         n = (n << 2);
  53     }
  54     if (!(n & 0x80000000u)) {
  55         lz += 1;
  56     }
  57
  58     return 31 - lz;
  59 }
  60
  61 size_t h2_util_hex_dump(char *buffer, size_t maxlen,
  62                         const char *data, size_t datalen)
  63 {
  64     size_t offset = 0;
  65     size_t maxoffset = (maxlen-4);
  66     size_t i;
  67     for (i = 0; i < datalen && offset < maxoffset; ++i) {
  68         const char *sep = (i && i % 16 == 0)? "\n" : " ";
  69         int n = apr_snprintf(buffer+offset, maxoffset-offset,
  70                              "%2x%s", ((unsigned int)data[i]&0xff), sep);
  71         offset += n;
  72     }
  73     strcpy(buffer+offset, (i<datalen)? "..." : "");
  74     return strlen(buffer);
  75 }
  76
  77 size_t h2_util_header_print(char *buffer, size_t maxlen,
  78                             const char *name, size_t namelen,
  79                             const char *value, size_t valuelen)
  80 {
  81     size_t offset = 0;
  82     size_t i;
  83     for (i = 0; i < namelen && offset < maxlen; ++i, ++offset) {
  84         buffer[offset] = name[i];
  85     }
  86     for (i = 0; i < 2 && offset < maxlen; ++i, ++offset) {
  87         buffer[offset] = ": "[i];
  88     }
  89     for (i = 0; i < valuelen && offset < maxlen; ++i, ++offset) {
  90         buffer[offset] = value[i];
  91     }
  92     buffer[offset] = '\0';
  93     return offset;
  94 }
  95
  96
  97 void h2_util_camel_case_header(char *s, size_t len)
  98 {
  99     size_t start = 1;
 100     size_t i;
 101     for (i = 0; i < len; ++i) {
 102         if (start) {
 103             if (s[i] >= 'a' && s[i] <= 'z') {
 104                 s[i] -= 'a' - 'A';
 105             }
 106
 107             start = 0;
 108         }
 109         else if (s[i] == '-') {
 110             start = 1;
 111         }
 112     }
 113 }
 114
 115 /* base64 url encoding */
 116
 117 static const int BASE64URL_UINT6[] = {
 118 /*   0   1   2   3   4   5   6   7   8   9   a   b   c   d   e   f        */
 119     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  0 */
 120     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  1 */
 121     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 62, -1, -1, /*  2 */
 122     52, 53, 54, 55, 56, 57, 58, 59, 60, 61, -1, -1, -1, -1, -1, -1, /*  3 */
 123     -1, 0,  1,  2,  3,  4,  5,  6,   7,  8,  9, 10, 11, 12, 13, 14, /*  4 */
 124     15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1, 63, /*  5 */
 125     -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, /*  6 */
 126     41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1, /*  7 */
 127     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  8 */
 128     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  9 */
 129     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  a */
 130     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  b */
 131     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  c */
 132     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  d */
 133     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, /*  e */
 134     -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1  /*  f */
 135 };
 136 static const char BASE64URL_CHARS[] = {
 137     'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', /*  0 -  9 */
 138     'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', /* 10 - 19 */
 139     'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', /* 20 - 29 */
 140     'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', /* 30 - 39 */
 141     'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', /* 40 - 49 */
 142     'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', /* 50 - 59 */
 143     '8', '9', '-', '_', ' ', ' ', ' ', ' ', ' ', ' ', /* 60 - 69 */
 144 };
 145
 146 apr_size_t h2_util_base64url_decode(const char **decoded, const char *encoded,
 147                                     apr_pool_t *pool)
 148 {
 149     const unsigned char *e = (const unsigned char *)encoded;
 150     const unsigned char *p = e;
 151     unsigned char *d;
 152     int n;
 153     apr_size_t len, mlen, remain, i;
 154
 155     while (*p && BASE64URL_UINT6[ *p ] != -1) {
 156         ++p;
 157     }
 158     len = p - e;
 159     mlen = (len/4)*4;
 160     *decoded = apr_pcalloc(pool, len+1);
 161
 162     i = 0;
 163     d = (unsigned char*)*decoded;
 164     for (; i < mlen; i += 4) {
 165         n = ((BASE64URL_UINT6[ e[i+0] ] << 18) +
 166              (BASE64URL_UINT6[ e[i+1] ] << 12) +
 167              (BASE64URL_UINT6[ e[i+2] ] << 6) +
 168              (BASE64URL_UINT6[ e[i+3] ]));
 169         *d++ = n >> 16;
 170         *d++ = n >> 8 & 0xffu;
 171         *d++ = n & 0xffu;
 172     }
 173     remain = len - mlen;
 174     switch (remain) {
 175         case 2:
 176             n = ((BASE64URL_UINT6[ e[mlen+0] ] << 18) +
 177                  (BASE64URL_UINT6[ e[mlen+1] ] << 12));
 178             *d++ = n >> 16;
 179             remain = 1;
 180             break;
 181         case 3:
 182             n = ((BASE64URL_UINT6[ e[mlen+0] ] << 18) +
 183                  (BASE64URL_UINT6[ e[mlen+1] ] << 12) +
 184                  (BASE64URL_UINT6[ e[mlen+2] ] << 6));
 185             *d++ = n >> 16;
 186             *d++ = n >> 8 & 0xffu;
 187             remain = 2;
 188             break;
 189         default: /* do nothing */
 190             break;
 191     }
 192     return mlen/4*3 + remain;
 193 }
 194
 195 const char *h2_util_base64url_encode(const char *data,
 196                                      apr_size_t dlen, apr_pool_t *pool)
 197 {
 198     long i, len = (int)dlen;
 199     apr_size_t slen = ((dlen+2)/3)*4 + 1; /* 0 terminated */
 200     const unsigned char *udata = (const unsigned char*)data;
 201     char *enc, *p = apr_pcalloc(pool, slen);
 202
 203     enc = p;
 204     for (i = 0; i < len-2; i+= 3) {
 205         *p++ = BASE64URL_CHARS[ (udata[i] >> 2) & 0x3fu ];
 206         *p++ = BASE64URL_CHARS[ ((udata[i] << 4) + (udata[i+1] >> 4)) & 0x3fu ];
 207         *p++ = BASE64URL_CHARS[ ((udata[i+1] << 2) + (udata[i+2] >> 6)) & 0x3fu ];
 208         *p++ = BASE64URL_CHARS[ udata[i+2] & 0x3fu ];
 209     }
 210
 211     if (i < len) {
 212         *p++ = BASE64URL_CHARS[ (udata[i] >> 2) & 0x3fu ];
 213         if (i == (len - 1)) {
 214             *p++ = BASE64URL_CHARS[ (udata[i] << 4) & 0x3fu ];
 215         }
 216         else {
 217             *p++ = BASE64URL_CHARS[ ((udata[i] << 4) + (udata[i+1] >> 4)) & 0x3fu ];
 218             *p++ = BASE64URL_CHARS[ (udata[i+1] << 2) & 0x3fu ];
 219         }
 220     }
 221     *p++ = '\0';
 222     return enc;
 223 }
 224
 225 /*******************************************************************************
 226  * ihash - hash for structs with int identifier
 227  ******************************************************************************/
 228 struct h2_ihash_t {
 229     apr_hash_t *hash;
 230     size_t ioff;
 231 };
 232
 233 static unsigned int ihash(const char *key, apr_ssize_t *klen)
 234 {
 235     return (unsigned int)(*((int*)key));
 236 }
 237
 238 h2_ihash_t *h2_ihash_create(apr_pool_t *pool, size_t offset_of_int)
 239 {
 240     h2_ihash_t *ih = apr_pcalloc(pool, sizeof(h2_ihash_t));
 241     ih->hash = apr_hash_make_custom(pool, ihash);
 242     ih->ioff = offset_of_int;
 243     return ih;
 244 }
 245
 246 size_t h2_ihash_count(h2_ihash_t *ih)
 247 {
 248     return apr_hash_count(ih->hash);
 249 }
 250
 251 int h2_ihash_empty(h2_ihash_t *ih)
 252 {
 253     return apr_hash_count(ih->hash) == 0;
 254 }
 255
 256 void *h2_ihash_get(h2_ihash_t *ih, int id)
 257 {
 258     return apr_hash_get(ih->hash, &id, sizeof(id));
 259 }
 260
 261 typedef struct {
 262     h2_ihash_iter_t *iter;
 263     void *ctx;
 264 } iter_ctx;
 265
 266 static int ihash_iter(void *ctx, const void *key, apr_ssize_t klen,
 267                      const void *val)
 268 {
 269     iter_ctx *ictx = ctx;
 270     return ictx->iter(ictx->ctx, (void*)val); /* why is this passed const?*/
 271 }
 272
 273 int h2_ihash_iter(h2_ihash_t *ih, h2_ihash_iter_t *fn, void *ctx)
 274 {
 275     iter_ctx ictx;
 276     ictx.iter = fn;
 277     ictx.ctx = ctx;
 278     return apr_hash_do(ihash_iter, &ictx, ih->hash);
 279 }
 280
 281 void h2_ihash_add(h2_ihash_t *ih, void *val)
 282 {
 283     apr_hash_set(ih->hash, ((char *)val + ih->ioff), sizeof(int), val);
 284 }
 285
 286 void h2_ihash_remove(h2_ihash_t *ih, int id)
 287 {
 288     apr_hash_set(ih->hash, &id, sizeof(id), NULL);
 289 }
 290
 291 void h2_ihash_remove_val(h2_ihash_t *ih, void *val)
 292 {
 293     int id = *((int*)((char *)val + ih->ioff));
 294     apr_hash_set(ih->hash, &id, sizeof(id), NULL);
 295 }
 296
 297
 298 void h2_ihash_clear(h2_ihash_t *ih)
 299 {
 300     apr_hash_clear(ih->hash);
 301 }
 302
 303 typedef struct {
 304     h2_ihash_t *ih;
 305     void **buffer;
 306     size_t max;
 307     size_t len;
 308 } collect_ctx;
 309
 310 static int collect_iter(void *x, void *val)
 311 {
 312     collect_ctx *ctx = x;
 313     if (ctx->len < ctx->max) {
 314         ctx->buffer[ctx->len++] = val;
 315         return 1;
 316     }
 317     return 0;
 318 }
 319
 320 size_t h2_ihash_shift(h2_ihash_t *ih, void **buffer, size_t max)
 321 {
 322     collect_ctx ctx;
 323     size_t i;
 324
 325     ctx.ih = ih;
 326     ctx.buffer = buffer;
 327     ctx.max = max;
 328     ctx.len = 0;
 329     h2_ihash_iter(ih, collect_iter, &ctx);
 330     for (i = 0; i < ctx.len; ++i) {
 331         h2_ihash_remove_val(ih, buffer[i]);
 332     }
 333     return ctx.len;
 334 }
 335
 336 /*******************************************************************************
 337  * iqueue - sorted list of int
 338  ******************************************************************************/
 339
 340 static void iq_grow(h2_iqueue *q, int nlen);
 341 static void iq_swap(h2_iqueue *q, int i, int j);
 342 static int iq_bubble_up(h2_iqueue *q, int i, int top,
 343                         h2_iq_cmp *cmp, void *ctx);
 344 static int iq_bubble_down(h2_iqueue *q, int i, int bottom,
 345                           h2_iq_cmp *cmp, void *ctx);
 346
 347 h2_iqueue *h2_iq_create(apr_pool_t *pool, int capacity)
 348 {
 349     h2_iqueue *q = apr_pcalloc(pool, sizeof(h2_iqueue));
 350     if (q) {
 351         q->pool = pool;
 352         iq_grow(q, capacity);
 353         q->nelts = 0;
 354     }
 355     return q;
 356 }
 357
 358 int h2_iq_empty(h2_iqueue *q)
 359 {
 360     return q->nelts == 0;
 361 }
 362
 363 int h2_iq_count(h2_iqueue *q)
 364 {
 365     return q->nelts;
 366 }
 367
 368
 369 int h2_iq_add(h2_iqueue *q, int sid, h2_iq_cmp *cmp, void *ctx)
 370 {
 371     int i;
 372
 373     if (h2_iq_contains(q, sid)) {
 374         return 0;
 375     }
 376     if (q->nelts >= q->nalloc) {
 377         iq_grow(q, q->nalloc * 2);
 378     }
 379     i = (q->head + q->nelts) % q->nalloc;
 380     q->elts[i] = sid;
 381     ++q->nelts;
 382
 383     if (cmp) {
 384         /* bubble it to the front of the queue */
 385         iq_bubble_up(q, i, q->head, cmp, ctx);
 386     }
 387     return 1;
 388 }
 389
 390 int h2_iq_append(h2_iqueue *q, int sid)
 391 {
 392     return h2_iq_add(q, sid, NULL, NULL);
 393 }
 394
 395 int h2_iq_remove(h2_iqueue *q, int sid)
 396 {
 397     int i;
 398     for (i = 0; i < q->nelts; ++i) {
 399         if (sid == q->elts[(q->head + i) % q->nalloc]) {
 400             break;
 401         }
 402     }
 403
 404     if (i < q->nelts) {
 405         ++i;
 406         for (; i < q->nelts; ++i) {
 407             q->elts[(q->head+i-1)%q->nalloc] = q->elts[(q->head+i)%q->nalloc];
 408         }
 409         --q->nelts;
 410         return 1;
 411     }
 412     return 0;
 413 }
 414
 415 void h2_iq_clear(h2_iqueue *q)
 416 {
 417     q->nelts = 0;
 418 }
 419
 420 void h2_iq_sort(h2_iqueue *q, h2_iq_cmp *cmp, void *ctx)
 421 {
 422     /* Assume that changes in ordering are minimal. This needs,
 423      * best case, q->nelts - 1 comparisions to check that nothing
 424      * changed.
 425      */
 426     if (q->nelts > 0) {
 427         int i, ni, prev, last;
 428
 429         /* Start at the end of the queue and create a tail of sorted
 430          * entries. Make that tail one element longer in each iteration.
 431          */
 432         last = i = (q->head + q->nelts - 1) % q->nalloc;
 433         while (i != q->head) {
 434             prev = (q->nalloc + i - 1) % q->nalloc;
 435
 436             ni = iq_bubble_up(q, i, prev, cmp, ctx);
 437             if (ni == prev) {
 438                 /* i bubbled one up, bubble the new i down, which
 439                  * keeps all tasks below i sorted. */
 440                 iq_bubble_down(q, i, last, cmp, ctx);
 441             }
 442             i = prev;
 443         };
 444     }
 445 }
 446
 447
 448 int h2_iq_shift(h2_iqueue *q)
 449 {
 450     int sid;
 451
 452     if (q->nelts <= 0) {
 453         return 0;
 454     }
 455
 456     sid = q->elts[q->head];
 457     q->head = (q->head + 1) % q->nalloc;
 458     q->nelts--;
 459
 460     return sid;
 461 }
 462
 463 size_t h2_iq_mshift(h2_iqueue *q, int *pint, size_t max)
 464 {
 465     int i;
 466     for (i = 0; i < max; ++i) {
 467         pint[i] = h2_iq_shift(q);
 468         if (pint[i] == 0) {
 469             break;
 470         }
 471     }
 472     return i;
 473 }
 474
 475 static void iq_grow(h2_iqueue *q, int nlen)
 476 {
 477     if (nlen > q->nalloc) {
 478         int *nq = apr_pcalloc(q->pool, sizeof(int) * nlen);
 479         if (q->nelts > 0) {
 480             int l = ((q->head + q->nelts) % q->nalloc) - q->head;
 481
 482             memmove(nq, q->elts + q->head, sizeof(int) * l);
 483             if (l < q->nelts) {
 484                 /* elts wrapped, append elts in [0, remain] to nq */
 485                 int remain = q->nelts - l;
 486                 memmove(nq + l, q->elts, sizeof(int) * remain);
 487             }
 488         }
 489         q->elts = nq;
 490         q->nalloc = nlen;
 491         q->head = 0;
 492     }
 493 }
 494
 495 static void iq_swap(h2_iqueue *q, int i, int j)
 496 {
 497     int x = q->elts[i];
 498     q->elts[i] = q->elts[j];
 499     q->elts[j] = x;
 500 }
 501
 502 static int iq_bubble_up(h2_iqueue *q, int i, int top,
 503                         h2_iq_cmp *cmp, void *ctx)
 504 {
 505     int prev;
 506     while (((prev = (q->nalloc + i - 1) % q->nalloc), i != top)
 507            && (*cmp)(q->elts[i], q->elts[prev], ctx) < 0) {
 508         iq_swap(q, prev, i);
 509         i = prev;
 510     }
 511     return i;
 512 }
 513
 514 static int iq_bubble_down(h2_iqueue *q, int i, int bottom,
 515                           h2_iq_cmp *cmp, void *ctx)
 516 {
 517     int next;
 518     while (((next = (q->nalloc + i + 1) % q->nalloc), i != bottom)
 519            && (*cmp)(q->elts[i], q->elts[next], ctx) > 0) {
 520         iq_swap(q, next, i);
 521         i = next;
 522     }
 523     return i;
 524 }
 525
 526 int h2_iq_contains(h2_iqueue *q, int sid)
 527 {
 528     int i;
 529     for (i = 0; i < q->nelts; ++i) {
 530         if (sid == q->elts[(q->head + i) % q->nalloc]) {
 531             return 1;
 532         }
 533     }
 534     return 0;
 535 }
 536
 537 /*******************************************************************************
 538  * FIFO queue
 539  ******************************************************************************/
 540
 541 struct h2_fifo {
 542     void **elems;
 543     int nelems;
 544     int set;
 545     int head;
 546     int count;
 547     int aborted;
 548     apr_thread_mutex_t *lock;
 549     apr_thread_cond_t  *not_empty;
 550     apr_thread_cond_t  *not_full;
 551 };
 552
 553 static int nth_index(h2_fifo *fifo, int n)
 554 {
 555     return (fifo->head + n) % fifo->nelems;
 556 }
 557
 558 static apr_status_t fifo_destroy(void *data)
 559 {
 560     h2_fifo *fifo = data;
 561
 562     apr_thread_cond_destroy(fifo->not_empty);
 563     apr_thread_cond_destroy(fifo->not_full);
 564     apr_thread_mutex_destroy(fifo->lock);
 565
 566     return APR_SUCCESS;
 567 }
 568
 569 static int index_of(h2_fifo *fifo, void *elem)
 570 {
 571     int i;
 572
 573     for (i = 0; i < fifo->count; ++i) {
 574         if (elem == fifo->elems[nth_index(fifo, i)]) {
 575             return i;
 576         }
 577     }
 578     return -1;
 579 }
 580
 581 static apr_status_t create_int(h2_fifo **pfifo, apr_pool_t *pool,
 582                                int capacity, int as_set)
 583 {
 584     apr_status_t rv;
 585     h2_fifo *fifo;
 586
 587     fifo = apr_pcalloc(pool, sizeof(*fifo));
 588     if (fifo == NULL) {
 589         return APR_ENOMEM;
 590     }
 591
 592     rv = apr_thread_mutex_create(&fifo->lock,
 593                                  APR_THREAD_MUTEX_UNNESTED, pool);
 594     if (rv != APR_SUCCESS) {
 595         return rv;
 596     }
 597
 598     rv = apr_thread_cond_create(&fifo->not_empty, pool);
 599     if (rv != APR_SUCCESS) {
 600         return rv;
 601     }
 602
 603     rv = apr_thread_cond_create(&fifo->not_full, pool);
 604     if (rv != APR_SUCCESS) {
 605         return rv;
 606     }
 607
 608     fifo->elems = apr_pcalloc(pool, capacity * sizeof(void*));
 609     if (fifo->elems == NULL) {
 610         return APR_ENOMEM;
 611     }
 612     fifo->nelems = capacity;
 613     fifo->set = as_set;
 614
 615     *pfifo = fifo;
 616     apr_pool_cleanup_register(pool, fifo, fifo_destroy, apr_pool_cleanup_null);
 617
 618     return APR_SUCCESS;
 619 }
 620
 621 apr_status_t h2_fifo_create(h2_fifo **pfifo, apr_pool_t *pool, int capacity)
 622 {
 623     return create_int(pfifo, pool, capacity, 0);
 624 }
 625
 626 apr_status_t h2_fifo_set_create(h2_fifo **pfifo, apr_pool_t *pool, int capacity)
 627 {
 628     return create_int(pfifo, pool, capacity, 1);
 629 }
 630
 631 apr_status_t h2_fifo_term(h2_fifo *fifo)
 632 {
 633     apr_status_t rv;
 634     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 635         fifo->aborted = 1;
 636         apr_thread_mutex_unlock(fifo->lock);
 637     }
 638     return rv;
 639 }
 640
 641 apr_status_t h2_fifo_interrupt(h2_fifo *fifo)
 642 {
 643     apr_status_t rv;
 644     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 645         apr_thread_cond_broadcast(fifo->not_empty);
 646         apr_thread_cond_broadcast(fifo->not_full);
 647         apr_thread_mutex_unlock(fifo->lock);
 648     }
 649     return rv;
 650 }
 651
 652 int h2_fifo_count(h2_fifo *fifo)
 653 {
 654     return fifo->count;
 655 }
 656
 657 static apr_status_t check_not_empty(h2_fifo *fifo, int block)
 658 {
 659     while (fifo->count == 0) {
 660         if (!block) {
 661             return APR_EAGAIN;
 662         }
 663         if (fifo->aborted) {
 664             return APR_EOF;
 665         }
 666         apr_thread_cond_wait(fifo->not_empty, fifo->lock);
 667     }
 668     return APR_SUCCESS;
 669 }
 670
 671 static apr_status_t fifo_push_int(h2_fifo *fifo, void *elem, int block)
 672 {
 673     if (fifo->aborted) {
 674         return APR_EOF;
 675     }
 676
 677     if (fifo->set && index_of(fifo, elem) >= 0) {
 678         /* set mode, elem already member */
 679         return APR_EEXIST;
 680     }
 681     else if (fifo->count == fifo->nelems) {
 682         if (block) {
 683             while (fifo->count == fifo->nelems) {
 684                 if (fifo->aborted) {
 685                     return APR_EOF;
 686                 }
 687                 apr_thread_cond_wait(fifo->not_full, fifo->lock);
 688             }
 689         }
 690         else {
 691             return APR_EAGAIN;
 692         }
 693     }
 694
 695     ap_assert(fifo->count < fifo->nelems);
 696     fifo->elems[nth_index(fifo, fifo->count)] = elem;
 697     ++fifo->count;
 698     if (fifo->count == 1) {
 699         apr_thread_cond_broadcast(fifo->not_empty);
 700     }
 701     return APR_SUCCESS;
 702 }
 703
 704 static apr_status_t fifo_push(h2_fifo *fifo, void *elem, int block)
 705 {
 706     apr_status_t rv;
 707
 708     if (fifo->aborted) {
 709         return APR_EOF;
 710     }
 711
 712     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 713         rv = fifo_push_int(fifo, elem, block);
 714         apr_thread_mutex_unlock(fifo->lock);
 715     }
 716     return rv;
 717 }
 718
 719 apr_status_t h2_fifo_push(h2_fifo *fifo, void *elem)
 720 {
 721     return fifo_push(fifo, elem, 1);
 722 }
 723
 724 apr_status_t h2_fifo_try_push(h2_fifo *fifo, void *elem)
 725 {
 726     return fifo_push(fifo, elem, 0);
 727 }
 728
 729 static apr_status_t pull_head(h2_fifo *fifo, void **pelem, int block)
 730 {
 731     apr_status_t rv;
 732
 733     if ((rv = check_not_empty(fifo, block)) != APR_SUCCESS) {
 734         *pelem = NULL;
 735         return rv;
 736     }
 737     *pelem = fifo->elems[fifo->head];
 738     --fifo->count;
 739     if (fifo->count > 0) {
 740         fifo->head = nth_index(fifo, 1);
 741         if (fifo->count+1 == fifo->nelems) {
 742             apr_thread_cond_broadcast(fifo->not_full);
 743         }
 744     }
 745     return APR_SUCCESS;
 746 }
 747
 748 static apr_status_t fifo_pull(h2_fifo *fifo, void **pelem, int block)
 749 {
 750     apr_status_t rv;
 751
 752     if (fifo->aborted) {
 753         return APR_EOF;
 754     }
 755
 756     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 757         rv = pull_head(fifo, pelem, block);
 758         apr_thread_mutex_unlock(fifo->lock);
 759     }
 760     return rv;
 761 }
 762
 763 apr_status_t h2_fifo_pull(h2_fifo *fifo, void **pelem)
 764 {
 765     return fifo_pull(fifo, pelem, 1);
 766 }
 767
 768 apr_status_t h2_fifo_try_pull(h2_fifo *fifo, void **pelem)
 769 {
 770     return fifo_pull(fifo, pelem, 0);
 771 }
 772
 773 static apr_status_t fifo_peek(h2_fifo *fifo, h2_fifo_peek_fn *fn, void *ctx, int block)
 774 {
 775     apr_status_t rv;
 776     void *elem;
 777
 778     if (fifo->aborted) {
 779         return APR_EOF;
 780     }
 781
 782     if (APR_SUCCESS == (rv = apr_thread_mutex_lock(fifo->lock))) {
 783         if (APR_SUCCESS == (rv = pull_head(fifo, &elem, block))) {
 784             switch (fn(elem, ctx)) {
 785                 case H2_FIFO_OP_PULL:
 786                     break;
 787                 case H2_FIFO_OP_REPUSH:
 788                     rv = fifo_push_int(fifo, elem, block);
 789                     break;
 790             }
 791         }
 792         apr_thread_mutex_unlock(fifo->lock);
 793     }
 794     return rv;
 795 }
 796
 797 apr_status_t h2_fifo_peek(h2_fifo *fifo, h2_fifo_peek_fn *fn, void *ctx)
 798 {
 799     return fifo_peek(fifo, fn, ctx, 1);
 800 }
 801
 802 apr_status_t h2_fifo_try_peek(h2_fifo *fifo, h2_fifo_peek_fn *fn, void *ctx)
 803 {
 804     return fifo_peek(fifo, fn, ctx, 0);
 805 }
 806
 807 apr_status_t h2_fifo_remove(h2_fifo *fifo, void *elem)
 808 {
 809     apr_status_t rv;
 810
 811     if (fifo->aborted) {
 812         return APR_EOF;
 813     }
 814
 815     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 816         int i, rc;
 817         void *e;
 818
 819         rc = 0;
 820         for (i = 0; i < fifo->count; ++i) {
 821             e = fifo->elems[nth_index(fifo, i)];
 822             if (e == elem) {
 823                 ++rc;
 824             }
 825             else if (rc) {
 826                 fifo->elems[nth_index(fifo, i-rc)] = e;
 827             }
 828         }
 829         if (rc) {
 830             fifo->count -= rc;
 831             if (fifo->count + rc == fifo->nelems) {
 832                 apr_thread_cond_broadcast(fifo->not_full);
 833             }
 834             rv = APR_SUCCESS;
 835         }
 836         else {
 837             rv = APR_EAGAIN;
 838         }
 839
 840         apr_thread_mutex_unlock(fifo->lock);
 841     }
 842     return rv;
 843 }
 844
 845 /*******************************************************************************
 846  * FIFO int queue
 847  ******************************************************************************/
 848
 849 struct h2_ififo {
 850     int *elems;
 851     int nelems;
 852     int set;
 853     int head;
 854     int count;
 855     int aborted;
 856     apr_thread_mutex_t *lock;
 857     apr_thread_cond_t  *not_empty;
 858     apr_thread_cond_t  *not_full;
 859 };
 860
 861 static int inth_index(h2_ififo *fifo, int n)
 862 {
 863     return (fifo->head + n) % fifo->nelems;
 864 }
 865
 866 static apr_status_t ififo_destroy(void *data)
 867 {
 868     h2_ififo *fifo = data;
 869
 870     apr_thread_cond_destroy(fifo->not_empty);
 871     apr_thread_cond_destroy(fifo->not_full);
 872     apr_thread_mutex_destroy(fifo->lock);
 873
 874     return APR_SUCCESS;
 875 }
 876
 877 static int iindex_of(h2_ififo *fifo, int id)
 878 {
 879     int i;
 880
 881     for (i = 0; i < fifo->count; ++i) {
 882         if (id == fifo->elems[inth_index(fifo, i)]) {
 883             return i;
 884         }
 885     }
 886     return -1;
 887 }
 888
 889 static apr_status_t icreate_int(h2_ififo **pfifo, apr_pool_t *pool,
 890                                 int capacity, int as_set)
 891 {
 892     apr_status_t rv;
 893     h2_ififo *fifo;
 894
 895     fifo = apr_pcalloc(pool, sizeof(*fifo));
 896     if (fifo == NULL) {
 897         return APR_ENOMEM;
 898     }
 899
 900     rv = apr_thread_mutex_create(&fifo->lock,
 901                                  APR_THREAD_MUTEX_UNNESTED, pool);
 902     if (rv != APR_SUCCESS) {
 903         return rv;
 904     }
 905
 906     rv = apr_thread_cond_create(&fifo->not_empty, pool);
 907     if (rv != APR_SUCCESS) {
 908         return rv;
 909     }
 910
 911     rv = apr_thread_cond_create(&fifo->not_full, pool);
 912     if (rv != APR_SUCCESS) {
 913         return rv;
 914     }
 915
 916     fifo->elems = apr_pcalloc(pool, capacity * sizeof(int));
 917     if (fifo->elems == NULL) {
 918         return APR_ENOMEM;
 919     }
 920     fifo->nelems = capacity;
 921     fifo->set = as_set;
 922
 923     *pfifo = fifo;
 924     apr_pool_cleanup_register(pool, fifo, ififo_destroy, apr_pool_cleanup_null);
 925
 926     return APR_SUCCESS;
 927 }
 928
 929 apr_status_t h2_ififo_create(h2_ififo **pfifo, apr_pool_t *pool, int capacity)
 930 {
 931     return icreate_int(pfifo, pool, capacity, 0);
 932 }
 933
 934 apr_status_t h2_ififo_set_create(h2_ififo **pfifo, apr_pool_t *pool, int capacity)
 935 {
 936     return icreate_int(pfifo, pool, capacity, 1);
 937 }
 938
 939 apr_status_t h2_ififo_term(h2_ififo *fifo)
 940 {
 941     apr_status_t rv;
 942     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 943         fifo->aborted = 1;
 944         apr_thread_mutex_unlock(fifo->lock);
 945     }
 946     return rv;
 947 }
 948
 949 apr_status_t h2_ififo_interrupt(h2_ififo *fifo)
 950 {
 951     apr_status_t rv;
 952     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
 953         apr_thread_cond_broadcast(fifo->not_empty);
 954         apr_thread_cond_broadcast(fifo->not_full);
 955         apr_thread_mutex_unlock(fifo->lock);
 956     }
 957     return rv;
 958 }
 959
 960 int h2_ififo_count(h2_ififo *fifo)
 961 {
 962     return fifo->count;
 963 }
 964
 965 static apr_status_t icheck_not_empty(h2_ififo *fifo, int block)
 966 {
 967     while (fifo->count == 0) {
 968         if (!block) {
 969             return APR_EAGAIN;
 970         }
 971         if (fifo->aborted) {
 972             return APR_EOF;
 973         }
 974         apr_thread_cond_wait(fifo->not_empty, fifo->lock);
 975     }
 976     return APR_SUCCESS;
 977 }
 978
 979 static apr_status_t ififo_push_int(h2_ififo *fifo, int id, int block)
 980 {
 981     if (fifo->aborted) {
 982         return APR_EOF;
 983     }
 984
 985     if (fifo->set && iindex_of(fifo, id) >= 0) {
 986         /* set mode, elem already member */
 987         return APR_EEXIST;
 988     }
 989     else if (fifo->count == fifo->nelems) {
 990         if (block) {
 991             while (fifo->count == fifo->nelems) {
 992                 if (fifo->aborted) {
 993                     return APR_EOF;
 994                 }
 995                 apr_thread_cond_wait(fifo->not_full, fifo->lock);
 996             }
 997         }
 998         else {
 999             return APR_EAGAIN;
1000         }
1001     }
1002
1003     ap_assert(fifo->count < fifo->nelems);
1004     fifo->elems[inth_index(fifo, fifo->count)] = id;
1005     ++fifo->count;
1006     if (fifo->count == 1) {
1007         apr_thread_cond_broadcast(fifo->not_empty);
1008     }
1009     return APR_SUCCESS;
1010 }
1011
1012 static apr_status_t ififo_push(h2_ififo *fifo, int id, int block)
1013 {
1014     apr_status_t rv;
1015
1016     if (fifo->aborted) {
1017         return APR_EOF;
1018     }
1019
1020     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
1021         rv = ififo_push_int(fifo, id, block);
1022         apr_thread_mutex_unlock(fifo->lock);
1023     }
1024     return rv;
1025 }
1026
1027 apr_status_t h2_ififo_push(h2_ififo *fifo, int id)
1028 {
1029     return ififo_push(fifo, id, 1);
1030 }
1031
1032 apr_status_t h2_ififo_try_push(h2_ififo *fifo, int id)
1033 {
1034     return ififo_push(fifo, id, 0);
1035 }
1036
1037 static apr_status_t ipull_head(h2_ififo *fifo, int *pi, int block)
1038 {
1039     apr_status_t rv;
1040
1041     if ((rv = icheck_not_empty(fifo, block)) != APR_SUCCESS) {
1042         *pi = 0;
1043         return rv;
1044     }
1045     *pi = fifo->elems[fifo->head];
1046     --fifo->count;
1047     if (fifo->count > 0) {
1048         fifo->head = inth_index(fifo, 1);
1049         if (fifo->count+1 == fifo->nelems) {
1050             apr_thread_cond_broadcast(fifo->not_full);
1051         }
1052     }
1053     return APR_SUCCESS;
1054 }
1055
1056 static apr_status_t ififo_pull(h2_ififo *fifo, int *pi, int block)
1057 {
1058     apr_status_t rv;
1059
1060     if (fifo->aborted) {
1061         return APR_EOF;
1062     }
1063
1064     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
1065         rv = ipull_head(fifo, pi, block);
1066         apr_thread_mutex_unlock(fifo->lock);
1067     }
1068     return rv;
1069 }
1070
1071 apr_status_t h2_ififo_pull(h2_ififo *fifo, int *pi)
1072 {
1073     return ififo_pull(fifo, pi, 1);
1074 }
1075
1076 apr_status_t h2_ififo_try_pull(h2_ififo *fifo, int *pi)
1077 {
1078     return ififo_pull(fifo, pi, 0);
1079 }
1080
1081 static apr_status_t ififo_peek(h2_ififo *fifo, h2_ififo_peek_fn *fn, void *ctx, int block)
1082 {
1083     apr_status_t rv;
1084     int id;
1085
1086     if (fifo->aborted) {
1087         return APR_EOF;
1088     }
1089
1090     if (APR_SUCCESS == (rv = apr_thread_mutex_lock(fifo->lock))) {
1091         if (APR_SUCCESS == (rv = ipull_head(fifo, &id, block))) {
1092             switch (fn(id, ctx)) {
1093                 case H2_FIFO_OP_PULL:
1094                     break;
1095                 case H2_FIFO_OP_REPUSH:
1096                     rv = ififo_push_int(fifo, id, block);
1097                     break;
1098             }
1099         }
1100         apr_thread_mutex_unlock(fifo->lock);
1101     }
1102     return rv;
1103 }
1104
1105 apr_status_t h2_ififo_peek(h2_ififo *fifo, h2_ififo_peek_fn *fn, void *ctx)
1106 {
1107     return ififo_peek(fifo, fn, ctx, 1);
1108 }
1109
1110 apr_status_t h2_ififo_try_peek(h2_ififo *fifo, h2_ififo_peek_fn *fn, void *ctx)
1111 {
1112     return ififo_peek(fifo, fn, ctx, 0);
1113 }
1114
1115 apr_status_t h2_ififo_remove(h2_ififo *fifo, int id)
1116 {
1117     apr_status_t rv;
1118
1119     if (fifo->aborted) {
1120         return APR_EOF;
1121     }
1122
1123     if ((rv = apr_thread_mutex_lock(fifo->lock)) == APR_SUCCESS) {
1124         int i, rc;
1125         int e;
1126
1127         rc = 0;
1128         for (i = 0; i < fifo->count; ++i) {
1129             e = fifo->elems[inth_index(fifo, i)];
1130             if (e == id) {
1131                 ++rc;
1132             }
1133             else if (rc) {
1134                 fifo->elems[inth_index(fifo, i-rc)] = e;
1135             }
1136         }
1137         if (rc) {
1138             fifo->count -= rc;
1139             if (fifo->count + rc == fifo->nelems) {
1140                 apr_thread_cond_broadcast(fifo->not_full);
1141             }
1142             rv = APR_SUCCESS;
1143         }
1144         else {
1145             rv = APR_EAGAIN;
1146         }
1147
1148         apr_thread_mutex_unlock(fifo->lock);
1149     }
1150     return rv;
1151 }
1152
1153 /*******************************************************************************
1154  * h2_util for apt_table_t
1155  ******************************************************************************/
1156
1157 typedef struct {
1158     apr_size_t bytes;
1159     apr_size_t pair_extra;
1160 } table_bytes_ctx;
1161
1162 static int count_bytes(void *x, const char *key, const char *value)
1163 {
1164     table_bytes_ctx *ctx = x;
1165     if (key) {
1166         ctx->bytes += strlen(key);
1167     }
1168     if (value) {
1169         ctx->bytes += strlen(value);
1170     }
1171     ctx->bytes += ctx->pair_extra;
1172     return 1;
1173 }
1174
1175 apr_size_t h2_util_table_bytes(apr_table_t *t, apr_size_t pair_extra)
1176 {
1177     table_bytes_ctx ctx;
1178
1179     ctx.bytes = 0;
1180     ctx.pair_extra = pair_extra;
1181     apr_table_do(count_bytes, &ctx, t, NULL);
1182     return ctx.bytes;
1183 }
1184
1185
1186 /*******************************************************************************
1187  * h2_util for bucket brigades
1188  ******************************************************************************/
1189
1190 static apr_status_t last_not_included(apr_bucket_brigade *bb,
1191                                       apr_off_t maxlen,
1192                                       int same_alloc,
1193                                       apr_size_t *pfile_buckets_allowed,
1194                                       apr_bucket **pend)
1195 {
1196     apr_bucket *b;
1197     apr_status_t status = APR_SUCCESS;
1198     int files_allowed = pfile_buckets_allowed? (int)*pfile_buckets_allowed : 0;
1199
1200     if (maxlen >= 0) {
1201         /* Find the bucket, up to which we reach maxlen/mem bytes */
1202         for (b = APR_BRIGADE_FIRST(bb);
1203              (b != APR_BRIGADE_SENTINEL(bb));
1204              b = APR_BUCKET_NEXT(b)) {
1205
1206             if (APR_BUCKET_IS_METADATA(b)) {
1207                 /* included */
1208             }
1209             else {
1210                 if (b->length == ((apr_size_t)-1)) {
1211                     const char *ign;
1212                     apr_size_t ilen;
1213                     status = apr_bucket_read(b, &ign, &ilen, APR_BLOCK_READ);
1214                     if (status != APR_SUCCESS) {
1215                         return status;
1216                     }
1217                 }
1218
1219                 if (maxlen == 0 && b->length > 0) {
1220                     *pend = b;
1221                     return status;
1222                 }
1223
1224                 if (same_alloc && APR_BUCKET_IS_FILE(b)) {
1225                     /* we like it move it, always */
1226                 }
1227                 else if (files_allowed > 0 && APR_BUCKET_IS_FILE(b)) {
1228                     /* this has no memory footprint really unless
1229                      * it is read, disregard it in length count,
1230                      * unless we do not move the file buckets */
1231                     --files_allowed;
1232                 }
1233                 else if (maxlen < (apr_off_t)b->length) {
1234                     apr_bucket_split(b, (apr_size_t)maxlen);
1235                     maxlen = 0;
1236                 }
1237                 else {
1238                     maxlen -= b->length;
1239                 }
1240             }
1241         }
1242     }
1243     *pend = APR_BRIGADE_SENTINEL(bb);
1244     return status;
1245 }
1246
1247 apr_status_t h2_brigade_concat_length(apr_bucket_brigade *dest,
1248                                       apr_bucket_brigade *src,
1249                                       apr_off_t length)
1250 {
1251     apr_bucket *b;
1252     apr_off_t remain = length;
1253     apr_status_t status = APR_SUCCESS;
1254
1255     while (!APR_BRIGADE_EMPTY(src)) {
1256         b = APR_BRIGADE_FIRST(src);
1257
1258         if (APR_BUCKET_IS_METADATA(b)) {
1259             APR_BUCKET_REMOVE(b);
1260             APR_BRIGADE_INSERT_TAIL(dest, b);
1261         }
1262         else {
1263             if (remain == b->length) {
1264                 /* fall through */
1265             }
1266             else if (remain <= 0) {
1267                 return status;
1268             }
1269             else {
1270                 if (b->length == ((apr_size_t)-1)) {
1271                     const char *ign;
1272                     apr_size_t ilen;
1273                     status = apr_bucket_read(b, &ign, &ilen, APR_BLOCK_READ);
1274                     if (status != APR_SUCCESS) {
1275                         return status;
1276                     }
1277                 }
1278
1279                 if (remain < b->length) {
1280                     apr_bucket_split(b, remain);
1281                 }
1282             }
1283             APR_BUCKET_REMOVE(b);
1284             APR_BRIGADE_INSERT_TAIL(dest, b);
1285             remain -= b->length;
1286         }
1287     }
1288     return status;
1289 }
1290
1291 apr_status_t h2_brigade_copy_length(apr_bucket_brigade *dest,
1292                                     apr_bucket_brigade *src,
1293                                     apr_off_t length)
1294 {
1295     apr_bucket *b, *next;
1296     apr_off_t remain = length;
1297     apr_status_t status = APR_SUCCESS;
1298
1299     for (b = APR_BRIGADE_FIRST(src);
1300          b != APR_BRIGADE_SENTINEL(src);
1301          b = next) {
1302         next = APR_BUCKET_NEXT(b);
1303
1304         if (APR_BUCKET_IS_METADATA(b)) {
1305             /* fall through */
1306         }
1307         else {
1308             if (remain == b->length) {
1309                 /* fall through */
1310             }
1311             else if (remain <= 0) {
1312                 return status;
1313             }
1314             else {
1315                 if (b->length == ((apr_size_t)-1)) {
1316                     const char *ign;
1317                     apr_size_t ilen;
1318                     status = apr_bucket_read(b, &ign, &ilen, APR_BLOCK_READ);
1319                     if (status != APR_SUCCESS) {
1320                         return status;
1321                     }
1322                 }
1323
1324                 if (remain < b->length) {
1325                     apr_bucket_split(b, remain);
1326                 }
1327             }
1328         }
1329         status = apr_bucket_copy(b, &b);
1330         if (status != APR_SUCCESS) {
1331             return status;
1332         }
1333         APR_BRIGADE_INSERT_TAIL(dest, b);
1334         remain -= b->length;
1335     }
1336     return status;
1337 }
1338
1339 int h2_util_has_eos(apr_bucket_brigade *bb, apr_off_t len)
1340 {
1341     apr_bucket *b, *end;
1342
1343     apr_status_t status = last_not_included(bb, len, 0, 0, &end);
1344     if (status != APR_SUCCESS) {
1345         return status;
1346     }
1347
1348     for (b = APR_BRIGADE_FIRST(bb);
1349          b != APR_BRIGADE_SENTINEL(bb) && b != end;
1350          b = APR_BUCKET_NEXT(b))
1351     {
1352         if (APR_BUCKET_IS_EOS(b)) {
1353             return 1;
1354         }
1355     }
1356     return 0;
1357 }
1358
1359 apr_status_t h2_util_bb_avail(apr_bucket_brigade *bb,
1360                               apr_off_t *plen, int *peos)
1361 {
1362     apr_status_t status;
1363     apr_off_t blen = 0;
1364
1365     /* test read to determine available length */
1366     status = apr_brigade_length(bb, 1, &blen);
1367     if (status != APR_SUCCESS) {
1368         return status;
1369     }
1370     else if (blen == 0) {
1371         /* brigade without data, does it have an EOS bucket somwhere? */
1372         *plen = 0;
1373         *peos = h2_util_has_eos(bb, -1);
1374     }
1375     else {
1376         /* data in the brigade, limit the length returned. Check for EOS
1377          * bucket only if we indicate data. This is required since plen == 0
1378          * means "the whole brigade" for h2_util_hash_eos()
1379          */
1380         if (blen < *plen || *plen < 0) {
1381             *plen = blen;
1382         }
1383         *peos = h2_util_has_eos(bb, *plen);
1384     }
1385     return APR_SUCCESS;
1386 }
1387
1388 apr_status_t h2_util_bb_readx(apr_bucket_brigade *bb,
1389                               h2_util_pass_cb *cb, void *ctx,
1390                               apr_off_t *plen, int *peos)
1391 {
1392     apr_status_t status = APR_SUCCESS;
1393     int consume = (cb != NULL);
1394     apr_off_t written = 0;
1395     apr_off_t avail = *plen;
1396     apr_bucket *next, *b;
1397
1398     /* Pass data in our brigade through the callback until the length
1399      * is satisfied or we encounter an EOS.
1400      */
1401     *peos = 0;
1402     for (b = APR_BRIGADE_FIRST(bb);
1403          (status == APR_SUCCESS) && (b != APR_BRIGADE_SENTINEL(bb));
1404          b = next) {
1405
1406         if (APR_BUCKET_IS_METADATA(b)) {
1407             if (APR_BUCKET_IS_EOS(b)) {
1408                 *peos = 1;
1409             }
1410             else {
1411                 /* ignore */
1412             }
1413         }
1414         else if (avail <= 0) {
1415             break;
1416         }
1417         else {
1418             const char *data = NULL;
1419             apr_size_t data_len;
1420
1421             if (b->length == ((apr_size_t)-1)) {
1422                 /* read to determine length */
1423                 status = apr_bucket_read(b, &data, &data_len, APR_NONBLOCK_READ);
1424             }
1425             else {
1426                 data_len = b->length;
1427             }
1428
1429             if (data_len > avail) {
1430                 apr_bucket_split(b, avail);
1431                 data_len = (apr_size_t)avail;
1432             }
1433
1434             if (consume) {
1435                 if (!data) {
1436                     status = apr_bucket_read(b, &data, &data_len,
1437                                              APR_NONBLOCK_READ);
1438                 }
1439                 if (status == APR_SUCCESS) {
1440                     status = cb(ctx, data, data_len);
1441                 }
1442             }
1443             else {
1444                 data_len = b->length;
1445             }
1446             avail -= data_len;
1447             written += data_len;
1448         }
1449
1450         next = APR_BUCKET_NEXT(b);
1451         if (consume) {
1452             apr_bucket_delete(b);
1453         }
1454     }
1455
1456     *plen = written;
1457     if (status == APR_SUCCESS && !*peos && !*plen) {
1458         return APR_EAGAIN;
1459     }
1460     return status;
1461 }
1462
1463 apr_size_t h2_util_bucket_print(char *buffer, apr_size_t bmax,
1464                                 apr_bucket *b, const char *sep)
1465 {
1466     apr_size_t off = 0;
1467     if (sep && *sep) {
1468         off += apr_snprintf(buffer+off, bmax-off, "%s", sep);
1469     }
1470
1471     if (bmax <= off) {
1472         return off;
1473     }
1474     else if (APR_BUCKET_IS_METADATA(b)) {
1475         off += apr_snprintf(buffer+off, bmax-off, "%s", b->type->name);
1476     }
1477     else if (bmax > off) {
1478         off += apr_snprintf(buffer+off, bmax-off, "%s[%ld]",
1479                             b->type->name,
1480                             (long)(b->length == ((apr_size_t)-1)?
1481                                    -1 : b->length));
1482     }
1483     return off;
1484 }
1485
1486 apr_size_t h2_util_bb_print(char *buffer, apr_size_t bmax,
1487                             const char *tag, const char *sep,
1488                             apr_bucket_brigade *bb)
1489 {
1490     apr_size_t off = 0;
1491     const char *sp = "";
1492     apr_bucket *b;
1493
1494     if (bmax > 1) {
1495         if (bb) {
1496             memset(buffer, 0, bmax--);
1497             off += apr_snprintf(buffer+off, bmax-off, "%s(", tag);
1498             for (b = APR_BRIGADE_FIRST(bb);
1499                  (bmax > off) && (b != APR_BRIGADE_SENTINEL(bb));
1500                  b = APR_BUCKET_NEXT(b)) {
1501
1502                 off += h2_util_bucket_print(buffer+off, bmax-off, b, sp);
1503                 sp = " ";
1504             }
1505             if (bmax > off) {
1506                 off += apr_snprintf(buffer+off, bmax-off, ")%s", sep);
1507             }
1508         }
1509         else {
1510             off += apr_snprintf(buffer+off, bmax-off, "%s(null)%s", tag, sep);
1511         }
1512     }
1513     return off;
1514 }
1515
1516 apr_status_t h2_append_brigade(apr_bucket_brigade *to,
1517                                apr_bucket_brigade *from,
1518                                apr_off_t *plen,
1519                                int *peos,
1520                                h2_bucket_gate *should_append)
1521 {
1522     apr_bucket *e;
1523     apr_off_t len = 0, remain = *plen;
1524     apr_status_t rv;
1525
1526     *peos = 0;
1527
1528     while (!APR_BRIGADE_EMPTY(from)) {
1529         e = APR_BRIGADE_FIRST(from);
1530
1531         if (!should_append(e)) {
1532             goto leave;
1533         }
1534         else if (APR_BUCKET_IS_METADATA(e)) {
1535             if (APR_BUCKET_IS_EOS(e)) {
1536                 *peos = 1;
1537                 apr_bucket_delete(e);
1538                 continue;
1539             }
1540         }
1541         else {
1542             if (remain > 0 && e->length == ((apr_size_t)-1)) {
1543                 const char *ign;
1544                 apr_size_t ilen;
1545                 rv = apr_bucket_read(e, &ign, &ilen, APR_BLOCK_READ);
1546                 if (rv != APR_SUCCESS) {
1547                     return rv;
1548                 }
1549             }
1550
1551             if (remain < e->length) {
1552                 if (remain <= 0) {
1553                     goto leave;
1554                 }
1555                 apr_bucket_split(e, (apr_size_t)remain);
1556             }
1557         }
1558
1559         APR_BUCKET_REMOVE(e);
1560         APR_BRIGADE_INSERT_TAIL(to, e);
1561         len += e->length;
1562         remain -= e->length;
1563     }
1564 leave:
1565     *plen = len;
1566     return APR_SUCCESS;
1567 }
1568
1569 apr_off_t h2_brigade_mem_size(apr_bucket_brigade *bb)
1570 {
1571     apr_bucket *b;
1572     apr_off_t total = 0;
1573
1574     for (b = APR_BRIGADE_FIRST(bb);
1575          b != APR_BRIGADE_SENTINEL(bb);
1576          b = APR_BUCKET_NEXT(b))
1577     {
1578         total += sizeof(*b);
1579         if (b->length > 0) {
1580             if (APR_BUCKET_IS_HEAP(b)
1581                 || APR_BUCKET_IS_POOL(b)) {
1582                 total += b->length;
1583             }
1584         }
1585     }
1586     return total;
1587 }
1588
1589
1590 /*******************************************************************************
1591  * h2_ngheader
1592  ******************************************************************************/
1593
1594 int h2_util_ignore_header(const char *name)
1595 {
1596     /* never forward, ch. 8.1.2.2 */
1597     return (H2_HD_MATCH_LIT_CS("connection", name)
1598             || H2_HD_MATCH_LIT_CS("proxy-connection", name)
1599             || H2_HD_MATCH_LIT_CS("upgrade", name)
1600             || H2_HD_MATCH_LIT_CS("keep-alive", name)
1601             || H2_HD_MATCH_LIT_CS("transfer-encoding", name));
1602 }
1603
1604 static int count_header(void *ctx, const char *key, const char *value)
1605 {
1606     if (!h2_util_ignore_header(key)) {
1607         (*((size_t*)ctx))++;
1608     }
1609     return 1;
1610 }
1611
1612 static const char *inv_field_name_chr(const char *token)
1613 {
1614     const char *p = ap_scan_http_token(token);
1615     if (p == token && *p == ':') {
1616         p = ap_scan_http_token(++p);
1617     }
1618     return (p && *p)? p : NULL;
1619 }
1620
1621 static const char *inv_field_value_chr(const char *token)
1622 {
1623     const char *p = ap_scan_http_field_content(token);
1624     return (p && *p)? p : NULL;
1625 }
1626
1627 typedef struct ngh_ctx {
1628     apr_pool_t *p;
1629     int unsafe;
1630     h2_ngheader *ngh;
1631     apr_status_t status;
1632 } ngh_ctx;
1633
1634 static int add_header(ngh_ctx *ctx, const char *key, const char *value)
1635 {
1636     nghttp2_nv *nv = &(ctx->ngh)->nv[(ctx->ngh)->nvlen++];
1637     const char *p;
1638
1639     if (!ctx->unsafe) {
1640         if ((p = inv_field_name_chr(key))) {
1641             ap_log_perror(APLOG_MARK, APLOG_TRACE1, APR_EINVAL, ctx->p,
1642                           "h2_request: head field '%s: %s' has invalid char %s",
1643                           key, value, p);
1644             ctx->status = APR_EINVAL;
1645             return 0;
1646         }
1647         if ((p = inv_field_value_chr(value))) {
1648             ap_log_perror(APLOG_MARK, APLOG_TRACE1, APR_EINVAL, ctx->p,
1649                           "h2_request: head field '%s: %s' has invalid char %s",
1650                           key, value, p);
1651             ctx->status = APR_EINVAL;
1652             return 0;
1653         }
1654     }
1655     nv->name = (uint8_t*)key;
1656     nv->namelen = strlen(key);
1657     nv->value = (uint8_t*)value;
1658     nv->valuelen = strlen(value);
1659
1660     return 1;
1661 }
1662
1663 static int add_table_header(void *ctx, const char *key, const char *value)
1664 {
1665     if (!h2_util_ignore_header(key)) {
1666         add_header(ctx, key, value);
1667     }
1668     return 1;
1669 }
1670
1671 static apr_status_t ngheader_create(h2_ngheader **ph, apr_pool_t *p,
1672                                     int unsafe, size_t key_count,
1673                                     const char *keys[], const char *values[],
1674                                     apr_table_t *headers)
1675 {
1676     ngh_ctx ctx;
1677     size_t n, i;
1678
1679     ctx.p = p;
1680     ctx.unsafe = unsafe;
1681
1682     n = key_count;
1683     apr_table_do(count_header, &n, headers, NULL);
1684
1685     *ph = ctx.ngh = apr_pcalloc(p, sizeof(h2_ngheader));
1686     if (!ctx.ngh) {
1687         return APR_ENOMEM;
1688     }
1689
1690     ctx.ngh->nv =  apr_pcalloc(p, n * sizeof(nghttp2_nv));
1691     if (!ctx.ngh->nv) {
1692         return APR_ENOMEM;
1693     }
1694
1695     ctx.status = APR_SUCCESS;
1696     for (i = 0; i < key_count; ++i) {
1697         if (!add_header(&ctx, keys[i], values[i])) {
1698             return ctx.status;
1699         }
1700     }
1701
1702     apr_table_do(add_table_header, &ctx, headers, NULL);
1703
1704     return ctx.status;
1705 }
1706
1707 static int is_unsafe(h2_headers *h)
1708 {
1709     const char *v = apr_table_get(h->notes, H2_HDR_CONFORMANCE);
1710     return (v && !strcmp(v, H2_HDR_CONFORMANCE_UNSAFE));
1711 }
1712
1713 apr_status_t h2_res_create_ngtrailer(h2_ngheader **ph, apr_pool_t *p,
1714                                     h2_headers *headers)
1715 {
1716     return ngheader_create(ph, p, is_unsafe(headers),
1717                            0, NULL, NULL, headers->headers);
1718 }
1719
1720 apr_status_t h2_res_create_ngheader(h2_ngheader **ph, apr_pool_t *p,
1721                                     h2_headers *headers)
1722 {
1723     const char *keys[] = {
1724         ":status"
1725     };
1726     const char *values[] = {
1727         apr_psprintf(p, "%d", headers->status)
1728     };
1729     return ngheader_create(ph, p, is_unsafe(headers),
1730                            H2_ALEN(keys), keys, values, headers->headers);
1731 }
1732
1733 apr_status_t h2_req_create_ngheader(h2_ngheader **ph, apr_pool_t *p,
1734                                     const struct h2_request *req)
1735 {
1736
1737     const char *keys[] = {
1738         ":scheme",
1739         ":authority",
1740         ":path",
1741         ":method",
1742     };
1743     const char *values[] = {
1744         req->scheme,
1745         req->authority,
1746         req->path,
1747         req->method,
1748     };
1749
1750     ap_assert(req->scheme);
1751     ap_assert(req->authority);
1752     ap_assert(req->path);
1753     ap_assert(req->method);
1754
1755     return ngheader_create(ph, p, 0, H2_ALEN(keys), keys, values, req->headers);
1756 }
1757
1758 /*******************************************************************************
1759  * header HTTP/1 <-> HTTP/2 conversions
1760  ******************************************************************************/
1761
1762
1763 typedef struct {
1764     const char *name;
1765     size_t len;
1766 } literal;
1767
1768 #define H2_DEF_LITERAL(n)   { (n), (sizeof(n)-1) }
1769 #define H2_LIT_ARGS(a)      (a),H2_ALEN(a)
1770
1771 static literal IgnoredRequestHeaders[] = {
1772     H2_DEF_LITERAL("upgrade"),
1773     H2_DEF_LITERAL("connection"),
1774     H2_DEF_LITERAL("keep-alive"),
1775     H2_DEF_LITERAL("http2-settings"),
1776     H2_DEF_LITERAL("proxy-connection"),
1777     H2_DEF_LITERAL("transfer-encoding"),
1778 };
1779 static literal IgnoredRequestTrailers[] = { /* Ignore, see rfc7230, ch. 4.1.2 */
1780     H2_DEF_LITERAL("te"),
1781     H2_DEF_LITERAL("host"),
1782     H2_DEF_LITERAL("range"),
1783     H2_DEF_LITERAL("cookie"),
1784     H2_DEF_LITERAL("expect"),
1785     H2_DEF_LITERAL("pragma"),
1786     H2_DEF_LITERAL("max-forwards"),
1787     H2_DEF_LITERAL("cache-control"),
1788     H2_DEF_LITERAL("authorization"),
1789     H2_DEF_LITERAL("content-length"),
1790     H2_DEF_LITERAL("proxy-authorization"),
1791 };
1792 static literal IgnoredResponseTrailers[] = {
1793     H2_DEF_LITERAL("age"),
1794     H2_DEF_LITERAL("date"),
1795     H2_DEF_LITERAL("vary"),
1796     H2_DEF_LITERAL("cookie"),
1797     H2_DEF_LITERAL("expires"),
1798     H2_DEF_LITERAL("warning"),
1799     H2_DEF_LITERAL("location"),
1800     H2_DEF_LITERAL("retry-after"),
1801     H2_DEF_LITERAL("cache-control"),
1802     H2_DEF_LITERAL("www-authenticate"),
1803     H2_DEF_LITERAL("proxy-authenticate"),
1804 };
1805
1806 static int ignore_header(const literal *lits, size_t llen,
1807                          const char *name, size_t nlen)
1808 {
1809     const literal *lit;
1810     size_t i;
1811
1812     for (i = 0; i < llen; ++i) {
1813         lit = &lits[i];
1814         if (lit->len == nlen && !apr_strnatcasecmp(lit->name, name)) {
1815             return 1;
1816         }
1817     }
1818     return 0;
1819 }
1820
1821 int h2_req_ignore_header(const char *name, size_t len)
1822 {
1823     return ignore_header(H2_LIT_ARGS(IgnoredRequestHeaders), name, len);
1824 }
1825
1826 int h2_req_ignore_trailer(const char *name, size_t len)
1827 {
1828     return (h2_req_ignore_header(name, len)
1829             || ignore_header(H2_LIT_ARGS(IgnoredRequestTrailers), name, len));
1830 }
1831
1832 int h2_res_ignore_trailer(const char *name, size_t len)
1833 {
1834     return ignore_header(H2_LIT_ARGS(IgnoredResponseTrailers), name, len);
1835 }
1836
1837 apr_status_t h2_req_add_header(apr_table_t *headers, apr_pool_t *pool,
1838                                const char *name, size_t nlen,
1839                                const char *value, size_t vlen)
1840 {
1841     char *hname, *hvalue;
1842
1843     if (h2_req_ignore_header(name, nlen)) {
1844         return APR_SUCCESS;
1845     }
1846     else if (H2_HD_MATCH_LIT("cookie", name, nlen)) {
1847         const char *existing = apr_table_get(headers, "cookie");
1848         if (existing) {
1849             char *nval;
1850
1851             /* Cookie header come separately in HTTP/2, but need
1852              * to be merged by "; " (instead of default ", ")
1853              */
1854             hvalue = apr_pstrndup(pool, value, vlen);
1855             nval = apr_psprintf(pool, "%s; %s", existing, hvalue);
1856             apr_table_setn(headers, "Cookie", nval);
1857             return APR_SUCCESS;
1858         }
1859     }
1860     else if (H2_HD_MATCH_LIT("host", name, nlen)) {
1861         if (apr_table_get(headers, "Host")) {
1862             return APR_SUCCESS; /* ignore duplicate */
1863         }
1864     }
1865
1866     hname = apr_pstrndup(pool, name, nlen);
1867     hvalue = apr_pstrndup(pool, value, vlen);
1868     h2_util_camel_case_header(hname, nlen);
1869     apr_table_mergen(headers, hname, hvalue);
1870
1871     return APR_SUCCESS;
1872 }
1873
1874 /*******************************************************************************
1875  * h2 request handling
1876  ******************************************************************************/
1877
1878 h2_request *h2_req_create(int id, apr_pool_t *pool, const char *method,
1879                           const char *scheme, const char *authority,
1880                           const char *path, apr_table_t *header, int serialize)
1881 {
1882     h2_request *req = apr_pcalloc(pool, sizeof(h2_request));
1883
1884     req->method         = method;
1885     req->scheme         = scheme;
1886     req->authority      = authority;
1887     req->path           = path;
1888     req->headers        = header? header : apr_table_make(pool, 10);
1889     req->request_time   = apr_time_now();
1890     req->serialize      = serialize;
1891
1892     return req;
1893 }
1894
1895 /*******************************************************************************
1896  * frame logging
1897  ******************************************************************************/
1898
1899 int h2_util_frame_print(const nghttp2_frame *frame, char *buffer, size_t maxlen)
1900 {
1901     char scratch[128];
1902     size_t s_len = sizeof(scratch)/sizeof(scratch[0]);
1903
1904     switch (frame->hd.type) {
1905         case NGHTTP2_DATA: {
1906             return apr_snprintf(buffer, maxlen,
1907                                 "DATA[length=%d, flags=%d, stream=%d, padlen=%d]",
1908                                 (int)frame->hd.length, frame->hd.flags,
1909                                 frame->hd.stream_id, (int)frame->data.padlen);
1910         }
1911         case NGHTTP2_HEADERS: {
1912             return apr_snprintf(buffer, maxlen,
1913                                 "HEADERS[length=%d, hend=%d, stream=%d, eos=%d]",
1914                                 (int)frame->hd.length,
1915                                 !!(frame->hd.flags & NGHTTP2_FLAG_END_HEADERS),
1916                                 frame->hd.stream_id,
1917                                 !!(frame->hd.flags & NGHTTP2_FLAG_END_STREAM));
1918         }
1919         case NGHTTP2_PRIORITY: {
1920             return apr_snprintf(buffer, maxlen,
1921                                 "PRIORITY[length=%d, flags=%d, stream=%d]",
1922                                 (int)frame->hd.length,
1923                                 frame->hd.flags, frame->hd.stream_id);
1924         }
1925         case NGHTTP2_RST_STREAM: {
1926             return apr_snprintf(buffer, maxlen,
1927                                 "RST_STREAM[length=%d, flags=%d, stream=%d]",
1928                                 (int)frame->hd.length,
1929                                 frame->hd.flags, frame->hd.stream_id);
1930         }
1931         case NGHTTP2_SETTINGS: {
1932             if (frame->hd.flags & NGHTTP2_FLAG_ACK) {
1933                 return apr_snprintf(buffer, maxlen,
1934                                     "SETTINGS[ack=1, stream=%d]",
1935                                     frame->hd.stream_id);
1936             }
1937             return apr_snprintf(buffer, maxlen,
1938                                 "SETTINGS[length=%d, stream=%d]",
1939                                 (int)frame->hd.length, frame->hd.stream_id);
1940         }
1941         case NGHTTP2_PUSH_PROMISE: {
1942             return apr_snprintf(buffer, maxlen,
1943                                 "PUSH_PROMISE[length=%d, hend=%d, stream=%d]",
1944                                 (int)frame->hd.length,
1945                                 !!(frame->hd.flags & NGHTTP2_FLAG_END_HEADERS),
1946                                 frame->hd.stream_id);
1947         }
1948         case NGHTTP2_PING: {
1949             return apr_snprintf(buffer, maxlen,
1950                                 "PING[length=%d, ack=%d, stream=%d]",
1951                                 (int)frame->hd.length,
1952                                 frame->hd.flags&NGHTTP2_FLAG_ACK,
1953                                 frame->hd.stream_id);
1954         }
1955         case NGHTTP2_GOAWAY: {
1956             size_t len = (frame->goaway.opaque_data_len < s_len)?
1957                 frame->goaway.opaque_data_len : s_len-1;
1958             memcpy(scratch, frame->goaway.opaque_data, len);
1959             scratch[len] = '\0';
1960             return apr_snprintf(buffer, maxlen, "GOAWAY[error=%d, reason='%s', "
1961                                 "last_stream=%d]", frame->goaway.error_code,
1962                                 scratch, frame->goaway.last_stream_id);
1963         }
1964         case NGHTTP2_WINDOW_UPDATE: {
1965             return apr_snprintf(buffer, maxlen,
1966                                 "WINDOW_UPDATE[stream=%d, incr=%d]",
1967                                 frame->hd.stream_id,
1968                                 frame->window_update.window_size_increment);
1969         }
1970         default:
1971             return apr_snprintf(buffer, maxlen,
1972                                 "type=%d[length=%d, flags=%d, stream=%d]",
1973                                 frame->hd.type, (int)frame->hd.length,
1974                                 frame->hd.flags, frame->hd.stream_id);
1975     }
1976 }
1977
1978 /*******************************************************************************
1979  * push policy
1980  ******************************************************************************/
1981 int h2_push_policy_determine(apr_table_t *headers, apr_pool_t *p, int push_enabled)
1982 {
1983     h2_push_policy policy = H2_PUSH_NONE;
1984     if (push_enabled) {
1985         const char *val = apr_table_get(headers, "accept-push-policy");
1986         if (val) {
1987             if (ap_find_token(p, val, "fast-load")) {
1988                 policy = H2_PUSH_FAST_LOAD;
1989             }
1990             else if (ap_find_token(p, val, "head")) {
1991                 policy = H2_PUSH_HEAD;
1992             }
1993             else if (ap_find_token(p, val, "default")) {
1994                 policy = H2_PUSH_DEFAULT;
1995             }
1996             else if (ap_find_token(p, val, "none")) {
1997                 policy = H2_PUSH_NONE;
1998             }
1999             else {
2000                 /* nothing known found in this header, go by default */
2001                 policy = H2_PUSH_DEFAULT;
2002             }
2003         }
2004         else {
2005             policy = H2_PUSH_DEFAULT;
2006         }
2007     }
2008     return policy;
2009 }
2010