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