granicus.if.org Git - apache/blob - modules/http2/h2_push.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 <stdio.h>
  18
  19 #include <apr_lib.h>
  20 #include <apr_strings.h>
  21 #include <apr_hash.h>
  22 #include <apr_time.h>
  23
  24 #ifdef H2_OPENSSL
  25 #include <openssl/sha.h>
  26 #endif
  27
  28 #include <httpd.h>
  29 #include <http_core.h>
  30 #include <http_log.h>
  31
  32 #include "h2_private.h"
  33 #include "h2_h2.h"
  34 #include "h2_util.h"
  35 #include "h2_push.h"
  36 #include "h2_request.h"
  37 #include "h2_headers.h"
  38 #include "h2_session.h"
  39 #include "h2_stream.h"
  40
  41 /*******************************************************************************
  42  * link header handling
  43  ******************************************************************************/
  44
  45 static const char *policy_str(h2_push_policy policy)
  46 {
  47     switch (policy) {
  48         case H2_PUSH_NONE:
  49             return "none";
  50         case H2_PUSH_FAST_LOAD:
  51             return "fast-load";
  52         case H2_PUSH_HEAD:
  53             return "head";
  54         default:
  55             return "default";
  56     }
  57 }
  58
  59 typedef struct {
  60     const h2_request *req;
  61     int push_policy;
  62     apr_pool_t *pool;
  63     apr_array_header_t *pushes;
  64     const char *s;
  65     size_t slen;
  66     size_t i;
  67
  68     const char *link;
  69     apr_table_t *params;
  70     char b[4096];
  71 } link_ctx;
  72
  73 static int attr_char(char c)
  74 {
  75     switch (c) {
  76         case '!':
  77         case '#':
  78         case '$':
  79         case '&':
  80         case '+':
  81         case '-':
  82         case '.':
  83         case '^':
  84         case '_':
  85         case '`':
  86         case '|':
  87         case '~':
  88             return 1;
  89         default:
  90             return apr_isalnum(c);
  91     }
  92 }
  93
  94 static int ptoken_char(char c)
  95 {
  96     switch (c) {
  97         case '!':
  98         case '#':
  99         case '$':
 100         case '&':
 101         case '\'':
 102         case '(':
 103         case ')':
 104         case '*':
 105         case '+':
 106         case '-':
 107         case '.':
 108         case '/':
 109         case ':':
 110         case '<':
 111         case '=':
 112         case '>':
 113         case '?':
 114         case '@':
 115         case '[':
 116         case ']':
 117         case '^':
 118         case '_':
 119         case '`':
 120         case '{':
 121         case '|':
 122         case '}':
 123         case '~':
 124             return 1;
 125         default:
 126             return apr_isalnum(c);
 127     }
 128 }
 129
 130 static int skip_ws(link_ctx *ctx)
 131 {
 132     char c;
 133     while (ctx->i < ctx->slen
 134            && (((c = ctx->s[ctx->i]) == ' ') || (c == '\t'))) {
 135         ++ctx->i;
 136     }
 137     return (ctx->i < ctx->slen);
 138 }
 139
 140 static int find_chr(link_ctx *ctx, char c, size_t *pidx)
 141 {
 142     size_t j;
 143     for (j = ctx->i; j < ctx->slen; ++j) {
 144         if (ctx->s[j] == c) {
 145             *pidx = j;
 146             return 1;
 147         }
 148     }
 149     return 0;
 150 }
 151
 152 static int read_chr(link_ctx *ctx, char c)
 153 {
 154     if (ctx->i < ctx->slen && ctx->s[ctx->i] == c) {
 155         ++ctx->i;
 156         return 1;
 157     }
 158     return 0;
 159 }
 160
 161 static char *mk_str(link_ctx *ctx, size_t end)
 162 {
 163     if (ctx->i < end) {
 164         return apr_pstrndup(ctx->pool, ctx->s + ctx->i, end - ctx->i);
 165     }
 166     return (char*)"";
 167 }
 168
 169 static int read_qstring(link_ctx *ctx, const char **ps)
 170 {
 171     if (skip_ws(ctx) && read_chr(ctx, '\"')) {
 172         size_t end;
 173         if (find_chr(ctx, '\"', &end)) {
 174             *ps = mk_str(ctx, end);
 175             ctx->i = end + 1;
 176             return 1;
 177         }
 178     }
 179     return 0;
 180 }
 181
 182 static int read_ptoken(link_ctx *ctx, const char **ps)
 183 {
 184     if (skip_ws(ctx)) {
 185         size_t i;
 186         for (i = ctx->i; i < ctx->slen && ptoken_char(ctx->s[i]); ++i) {
 187             /* nop */
 188         }
 189         if (i > ctx->i) {
 190             *ps = mk_str(ctx, i);
 191             ctx->i = i;
 192             return 1;
 193         }
 194     }
 195     return 0;
 196 }
 197
 198
 199 static int read_link(link_ctx *ctx)
 200 {
 201     if (skip_ws(ctx) && read_chr(ctx, '<')) {
 202         size_t end;
 203         if (find_chr(ctx, '>', &end)) {
 204             ctx->link = mk_str(ctx, end);
 205             ctx->i = end + 1;
 206             return 1;
 207         }
 208     }
 209     return 0;
 210 }
 211
 212 static int read_pname(link_ctx *ctx, const char **pname)
 213 {
 214     if (skip_ws(ctx)) {
 215         size_t i;
 216         for (i = ctx->i; i < ctx->slen && attr_char(ctx->s[i]); ++i) {
 217             /* nop */
 218         }
 219         if (i > ctx->i) {
 220             *pname = mk_str(ctx, i);
 221             ctx->i = i;
 222             return 1;
 223         }
 224     }
 225     return 0;
 226 }
 227
 228 static int read_pvalue(link_ctx *ctx, const char **pvalue)
 229 {
 230     if (skip_ws(ctx) && read_chr(ctx, '=')) {
 231         if (read_qstring(ctx, pvalue) || read_ptoken(ctx, pvalue)) {
 232             return 1;
 233         }
 234     }
 235     return 0;
 236 }
 237
 238 static int read_param(link_ctx *ctx)
 239 {
 240     if (skip_ws(ctx) && read_chr(ctx, ';')) {
 241         const char *name, *value = "";
 242         if (read_pname(ctx, &name)) {
 243             read_pvalue(ctx, &value); /* value is optional */
 244             apr_table_setn(ctx->params, name, value);
 245             return 1;
 246         }
 247     }
 248     return 0;
 249 }
 250
 251 static int read_sep(link_ctx *ctx)
 252 {
 253     if (skip_ws(ctx) && read_chr(ctx, ',')) {
 254         return 1;
 255     }
 256     return 0;
 257 }
 258
 259 static void init_params(link_ctx *ctx)
 260 {
 261     if (!ctx->params) {
 262         ctx->params = apr_table_make(ctx->pool, 5);
 263     }
 264     else {
 265         apr_table_clear(ctx->params);
 266     }
 267 }
 268
 269 static int same_authority(const h2_request *req, const apr_uri_t *uri)
 270 {
 271     if (uri->scheme != NULL && strcmp(uri->scheme, req->scheme)) {
 272         return 0;
 273     }
 274     if (uri->hostinfo != NULL && strcmp(uri->hostinfo, req->authority)) {
 275         return 0;
 276     }
 277     return 1;
 278 }
 279
 280 static int set_push_header(void *ctx, const char *key, const char *value)
 281 {
 282     size_t klen = strlen(key);
 283     if (H2_HD_MATCH_LIT("User-Agent", key, klen)
 284         || H2_HD_MATCH_LIT("Accept", key, klen)
 285         || H2_HD_MATCH_LIT("Accept-Encoding", key, klen)
 286         || H2_HD_MATCH_LIT("Accept-Language", key, klen)
 287         || H2_HD_MATCH_LIT("Cache-Control", key, klen)) {
 288         apr_table_setn(ctx, key, value);
 289     }
 290     return 1;
 291 }
 292
 293 static int has_param(link_ctx *ctx, const char *param)
 294 {
 295     const char *p = apr_table_get(ctx->params, param);
 296     return !!p;
 297 }
 298
 299 static int has_relation(link_ctx *ctx, const char *rel)
 300 {
 301     const char *s, *val = apr_table_get(ctx->params, "rel");
 302     if (val) {
 303         if (!strcmp(rel, val)) {
 304             return 1;
 305         }
 306         s = ap_strstr_c(val, rel);
 307         if (s && (s == val || s[-1] == ' ')) {
 308             s += strlen(rel);
 309             if (!*s || *s == ' ') {
 310                 return 1;
 311             }
 312         }
 313     }
 314     return 0;
 315 }
 316
 317 static int add_push(link_ctx *ctx)
 318 {
 319     /* so, we have read a Link header and need to decide
 320      * if we transform it into a push.
 321      */
 322     if (has_relation(ctx, "preload") && !has_param(ctx, "nopush")) {
 323         apr_uri_t uri;
 324         if (apr_uri_parse(ctx->pool, ctx->link, &uri) == APR_SUCCESS) {
 325             if (uri.path && same_authority(ctx->req, &uri)) {
 326                 char *path;
 327                 const char *method;
 328                 apr_table_t *headers;
 329                 h2_request *req;
 330                 h2_push *push;
 331
 332                 /* We only want to generate pushes for resources in the
 333                  * same authority than the original request.
 334                  * icing: i think that is wise, otherwise we really need to
 335                  * check that the vhost/server is available and uses the same
 336                  * TLS (if any) parameters.
 337                  */
 338                 path = apr_uri_unparse(ctx->pool, &uri, APR_URI_UNP_OMITSITEPART);
 339                 push = apr_pcalloc(ctx->pool, sizeof(*push));
 340                 switch (ctx->push_policy) {
 341                     case H2_PUSH_HEAD:
 342                         method = "HEAD";
 343                         break;
 344                     default:
 345                         method = "GET";
 346                         break;
 347                 }
 348                 headers = apr_table_make(ctx->pool, 5);
 349                 apr_table_do(set_push_header, headers, ctx->req->headers, NULL);
 350                 req = h2_req_create(0, ctx->pool, method, ctx->req->scheme,
 351                                     ctx->req->authority, path, headers,
 352                                     ctx->req->serialize);
 353                 /* atm, we do not push on pushes */
 354                 h2_request_end_headers(req, ctx->pool, 1);
 355                 push->req = req;
 356                 if (has_param(ctx, "critical")) {
 357                     h2_priority *prio = apr_pcalloc(ctx->pool, sizeof(*prio));
 358                     prio->dependency = H2_DEPENDANT_BEFORE;
 359                     push->priority = prio;
 360                 }
 361                 if (!ctx->pushes) {
 362                     ctx->pushes = apr_array_make(ctx->pool, 5, sizeof(h2_push*));
 363                 }
 364                 APR_ARRAY_PUSH(ctx->pushes, h2_push*) = push;
 365             }
 366         }
 367     }
 368     return 0;
 369 }
 370
 371 static void inspect_link(link_ctx *ctx, const char *s, size_t slen)
 372 {
 373     /* RFC 5988 <https://tools.ietf.org/html/rfc5988#section-6.2.1>
 374       Link           = "Link" ":" #link-value
 375       link-value     = "<" URI-Reference ">" *( ";" link-param )
 376       link-param     = ( ( "rel" "=" relation-types )
 377                      | ( "anchor" "=" <"> URI-Reference <"> )
 378                      | ( "rev" "=" relation-types )
 379                      | ( "hreflang" "=" Language-Tag )
 380                      | ( "media" "=" ( MediaDesc | ( <"> MediaDesc <"> ) ) )
 381                      | ( "title" "=" quoted-string )
 382                      | ( "title*" "=" ext-value )
 383                      | ( "type" "=" ( media-type | quoted-mt ) )
 384                      | ( link-extension ) )
 385       link-extension = ( parmname [ "=" ( ptoken | quoted-string ) ] )
 386                      | ( ext-name-star "=" ext-value )
 387       ext-name-star  = parmname "*" ; reserved for RFC2231-profiled
 388                                     ; extensions.  Whitespace NOT
 389                                     ; allowed in between.
 390       ptoken         = 1*ptokenchar
 391       ptokenchar     = "!" | "#" | "$" | "%" | "&" | "'" | "("
 392                      | ")" | "*" | "+" | "-" | "." | "/" | DIGIT
 393                      | ":" | "<" | "=" | ">" | "?" | "@" | ALPHA
 394                      | "[" | "]" | "^" | "_" | "`" | "{" | "|"
 395                      | "}" | "~"
 396       media-type     = type-name "/" subtype-name
 397       quoted-mt      = <"> media-type <">
 398       relation-types = relation-type
 399                      | <"> relation-type *( 1*SP relation-type ) <">
 400       relation-type  = reg-rel-type | ext-rel-type
 401       reg-rel-type   = LOALPHA *( LOALPHA | DIGIT | "." | "-" )
 402       ext-rel-type   = URI
 403
 404       and from <https://tools.ietf.org/html/rfc5987>
 405       parmname      = 1*attr-char
 406       attr-char     = ALPHA / DIGIT
 407                        / "!" / "#" / "$" / "&" / "+" / "-" / "."
 408                        / "^" / "_" / "`" / "|" / "~"
 409      */
 410
 411      ctx->s = s;
 412      ctx->slen = slen;
 413      ctx->i = 0;
 414
 415      while (read_link(ctx)) {
 416         init_params(ctx);
 417         while (read_param(ctx)) {
 418             /* nop */
 419         }
 420         add_push(ctx);
 421         if (!read_sep(ctx)) {
 422             break;
 423         }
 424      }
 425 }
 426
 427 static int head_iter(void *ctx, const char *key, const char *value)
 428 {
 429     if (!apr_strnatcasecmp("link", key)) {
 430         inspect_link(ctx, value, strlen(value));
 431     }
 432     return 1;
 433 }
 434
 435 apr_array_header_t *h2_push_collect(apr_pool_t *p, const h2_request *req,
 436                                     int push_policy, const h2_headers *res)
 437 {
 438     if (req && push_policy != H2_PUSH_NONE) {
 439         /* Collect push candidates from the request/response pair.
 440          *
 441          * One source for pushes are "rel=preload" link headers
 442          * in the response.
 443          *
 444          * TODO: This may be extended in the future by hooks or callbacks
 445          * where other modules can provide push information directly.
 446          */
 447         if (res->headers) {
 448             link_ctx ctx;
 449
 450             memset(&ctx, 0, sizeof(ctx));
 451             ctx.req = req;
 452             ctx.push_policy = push_policy;
 453             ctx.pool = p;
 454
 455             apr_table_do(head_iter, &ctx, res->headers, NULL);
 456             if (ctx.pushes) {
 457                 apr_table_setn(res->headers, "push-policy",
 458                                policy_str(push_policy));
 459             }
 460             return ctx.pushes;
 461         }
 462     }
 463     return NULL;
 464 }
 465
 466 /*******************************************************************************
 467  * push diary
 468  *
 469  * - The push diary keeps track of resources already PUSHed via HTTP/2 on this
 470  *   connection. It records a hash value from the absolute URL of the resource
 471  *   pushed.
 472  * - Lacking openssl, it uses 'apr_hashfunc_default' for the value
 473  * - with openssl, it uses SHA256 to calculate the hash value
 474  * - whatever the method to generate the hash, the diary keeps a maximum of 64
 475  *   bits per hash, limiting the memory consumption to about
 476  *      H2PushDiarySize * 8
 477  *   bytes. Entries are sorted by most recently used and oldest entries are
 478  *   forgotten first.
 479  * - Clients can initialize/replace the push diary by sending a 'Cache-Digest'
 480  *   header. Currently, this is the base64url encoded value of the cache digest
 481  *   as specified in https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
 482  *   This draft can be expected to evolve and the definition of the header
 483  *   will be added there and refined.
 484  * - The cache digest header is a Golomb Coded Set of hash values, but it may
 485  *   limit the amount of bits per hash value even further. For a good description
 486  *   of GCS, read here:
 487  *      http://giovanni.bajo.it/post/47119962313/golomb-coded-sets-smaller-than-bloom-filters
 488  * - The means that the push diary might be initialized with hash values of much
 489  *   less than 64 bits, leading to more false positives, but smaller digest size.
 490  ******************************************************************************/
 491
 492
 493 #define GCSLOG_LEVEL   APLOG_TRACE1
 494
 495 typedef struct h2_push_diary_entry {
 496     apr_uint64_t hash;
 497 } h2_push_diary_entry;
 498
 499
 500 #ifdef H2_OPENSSL
 501 static void sha256_update(SHA256_CTX *ctx, const char *s)
 502 {
 503     SHA256_Update(ctx, s, strlen(s));
 504 }
 505
 506 static void calc_sha256_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push)
 507 {
 508     SHA256_CTX sha256;
 509     apr_uint64_t val;
 510     unsigned char hash[SHA256_DIGEST_LENGTH];
 511     int i;
 512
 513     SHA256_Init(&sha256);
 514     sha256_update(&sha256, push->req->scheme);
 515     sha256_update(&sha256, "://");
 516     sha256_update(&sha256, push->req->authority);
 517     sha256_update(&sha256, push->req->path);
 518     SHA256_Final(hash, &sha256);
 519
 520     val = 0;
 521     for (i = 0; i != sizeof(val); ++i)
 522         val = val * 256 + hash[i];
 523     *phash = val >> (64 - diary->mask_bits);
 524 }
 525 #endif
 526
 527
 528 static unsigned int val_apr_hash(const char *str)
 529 {
 530     apr_ssize_t len = strlen(str);
 531     return apr_hashfunc_default(str, &len);
 532 }
 533
 534 static void calc_apr_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push)
 535 {
 536     apr_uint64_t val;
 537 #if APR_UINT64_MAX > UINT_MAX
 538     val = ((apr_uint64_t)(val_apr_hash(push->req->scheme)) << 32);
 539     val ^= ((apr_uint64_t)(val_apr_hash(push->req->authority)) << 16);
 540     val ^= val_apr_hash(push->req->path);
 541 #else
 542     val = val_apr_hash(push->req->scheme);
 543     val ^= val_apr_hash(push->req->authority);
 544     val ^= val_apr_hash(push->req->path);
 545 #endif
 546     *phash = val;
 547 }
 548
 549 static apr_int32_t ceil_power_of_2(apr_int32_t n)
 550 {
 551     if (n <= 2) return 2;
 552     --n;
 553     n |= n >> 1;
 554     n |= n >> 2;
 555     n |= n >> 4;
 556     n |= n >> 8;
 557     n |= n >> 16;
 558     return ++n;
 559 }
 560
 561 static h2_push_diary *diary_create(apr_pool_t *p, h2_push_digest_type dtype,
 562                                    int N)
 563 {
 564     h2_push_diary *diary = NULL;
 565
 566     if (N > 0) {
 567         diary = apr_pcalloc(p, sizeof(*diary));
 568
 569         diary->NMax        = ceil_power_of_2(N);
 570         diary->N           = diary->NMax;
 571         /* the mask we use in value comparison depends on where we got
 572          * the values from. If we calculate them ourselves, we can use
 573          * the full 64 bits.
 574          * If we set the diary via a compressed golomb set, we have less
 575          * relevant bits and need to use a smaller mask. */
 576         diary->mask_bits   = 64;
 577         /* grows by doubling, start with a power of 2 */
 578         diary->entries     = apr_array_make(p, 16, sizeof(h2_push_diary_entry));
 579
 580         switch (dtype) {
 581 #ifdef H2_OPENSSL
 582             case H2_PUSH_DIGEST_SHA256:
 583                 diary->dtype       = H2_PUSH_DIGEST_SHA256;
 584                 diary->dcalc       = calc_sha256_hash;
 585                 break;
 586 #endif /* ifdef H2_OPENSSL */
 587             default:
 588                 diary->dtype       = H2_PUSH_DIGEST_APR_HASH;
 589                 diary->dcalc       = calc_apr_hash;
 590                 break;
 591         }
 592     }
 593
 594     return diary;
 595 }
 596
 597 h2_push_diary *h2_push_diary_create(apr_pool_t *p, int N)
 598 {
 599     return diary_create(p, H2_PUSH_DIGEST_SHA256, N);
 600 }
 601
 602 static int h2_push_diary_find(h2_push_diary *diary, apr_uint64_t hash)
 603 {
 604     if (diary) {
 605         h2_push_diary_entry *e;
 606         int i;
 607
 608         /* search from the end, where the last accessed digests are */
 609         for (i = diary->entries->nelts-1; i >= 0; --i) {
 610             e = &APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry);
 611             if (e->hash == hash) {
 612                 return i;
 613             }
 614         }
 615     }
 616     return -1;
 617 }
 618
 619 static h2_push_diary_entry *move_to_last(h2_push_diary *diary, apr_size_t idx)
 620 {
 621     h2_push_diary_entry *entries = (h2_push_diary_entry*)diary->entries->elts;
 622     h2_push_diary_entry e;
 623     apr_size_t lastidx = diary->entries->nelts-1;
 624
 625     /* move entry[idx] to the end */
 626     if (idx < lastidx) {
 627         e =  entries[idx];
 628         memmove(entries+idx, entries+idx+1, sizeof(e) * (lastidx - idx));
 629         entries[lastidx] = e;
 630     }
 631     return &entries[lastidx];
 632 }
 633
 634 static void h2_push_diary_append(h2_push_diary *diary, h2_push_diary_entry *e)
 635 {
 636     h2_push_diary_entry *ne;
 637
 638     if (diary->entries->nelts < diary->N) {
 639         /* append a new diary entry at the end */
 640         APR_ARRAY_PUSH(diary->entries, h2_push_diary_entry) = *e;
 641         ne = &APR_ARRAY_IDX(diary->entries, diary->entries->nelts-1, h2_push_diary_entry);
 642     }
 643     else {
 644         /* replace content with new digest. keeps memory usage constant once diary is full */
 645         ne = move_to_last(diary, 0);
 646         *ne = *e;
 647     }
 648     /* Intentional no APLOGNO */
 649     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, diary->entries->pool,
 650                   "push_diary_append: %"APR_UINT64_T_HEX_FMT, ne->hash);
 651 }
 652
 653 apr_array_header_t *h2_push_diary_update(h2_session *session, apr_array_header_t *pushes)
 654 {
 655     apr_array_header_t *npushes = pushes;
 656     h2_push_diary_entry e;
 657     int i, idx;
 658
 659     if (session->push_diary && pushes) {
 660         npushes = NULL;
 661
 662         for (i = 0; i < pushes->nelts; ++i) {
 663             h2_push *push;
 664
 665             push = APR_ARRAY_IDX(pushes, i, h2_push*);
 666             session->push_diary->dcalc(session->push_diary, &e.hash, push);
 667             idx = h2_push_diary_find(session->push_diary, e.hash);
 668             if (idx >= 0) {
 669                 /* Intentional no APLOGNO */
 670                 ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c,
 671                               "push_diary_update: already there PUSH %s", push->req->path);
 672                 move_to_last(session->push_diary, idx);
 673             }
 674             else {
 675                 /* Intentional no APLOGNO */
 676                 ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c,
 677                               "push_diary_update: adding PUSH %s", push->req->path);
 678                 if (!npushes) {
 679                     npushes = apr_array_make(pushes->pool, 5, sizeof(h2_push_diary_entry*));
 680                 }
 681                 APR_ARRAY_PUSH(npushes, h2_push*) = push;
 682                 h2_push_diary_append(session->push_diary, &e);
 683             }
 684         }
 685     }
 686     return npushes;
 687 }
 688
 689 apr_array_header_t *h2_push_collect_update(h2_stream *stream,
 690                                            const struct h2_request *req,
 691                                            const struct h2_headers *res)
 692 {
 693     h2_session *session = stream->session;
 694     const char *cache_digest = apr_table_get(req->headers, "Cache-Digest");
 695     apr_array_header_t *pushes;
 696     apr_status_t status;
 697
 698     if (cache_digest && session->push_diary) {
 699         status = h2_push_diary_digest64_set(session->push_diary, req->authority,
 700                                             cache_digest, stream->pool);
 701         if (status != APR_SUCCESS) {
 702             ap_log_cerror(APLOG_MARK, APLOG_DEBUG, status, session->c,
 703                           H2_SSSN_LOG(APLOGNO(03057), session,
 704                           "push diary set from Cache-Digest: %s"), cache_digest);
 705         }
 706     }
 707     pushes = h2_push_collect(stream->pool, req, stream->push_policy, res);
 708     return h2_push_diary_update(stream->session, pushes);
 709 }
 710
 711 static apr_int32_t h2_log2inv(unsigned char log2)
 712 {
 713     return log2? (1 << log2) : 1;
 714 }
 715
 716
 717 typedef struct {
 718     h2_push_diary *diary;
 719     unsigned char log2p;
 720     int mask_bits;
 721     int delta_bits;
 722     int fixed_bits;
 723     apr_uint64_t fixed_mask;
 724     apr_pool_t *pool;
 725     unsigned char *data;
 726     apr_size_t datalen;
 727     apr_size_t offset;
 728     unsigned int bit;
 729     apr_uint64_t last;
 730 } gset_encoder;
 731
 732 static int cmp_puint64(const void *p1, const void *p2)
 733 {
 734     const apr_uint64_t *pu1 = p1, *pu2 = p2;
 735     return (*pu1 > *pu2)? 1 : ((*pu1 == *pu2)? 0 : -1);
 736 }
 737
 738 /* in golomb bit stream encoding, bit 0 is the 8th of the first char, or
 739  * more generally:
 740  *      char(bit/8) & cbit_mask[(bit % 8)]
 741  */
 742 static unsigned char cbit_mask[] = {
 743     0x80u,
 744     0x40u,
 745     0x20u,
 746     0x10u,
 747     0x08u,
 748     0x04u,
 749     0x02u,
 750     0x01u,
 751 };
 752
 753 static apr_status_t gset_encode_bit(gset_encoder *encoder, int bit)
 754 {
 755     if (++encoder->bit >= 8) {
 756         if (++encoder->offset >= encoder->datalen) {
 757             apr_size_t nlen = encoder->datalen*2;
 758             unsigned char *ndata = apr_pcalloc(encoder->pool, nlen);
 759             if (!ndata) {
 760                 return APR_ENOMEM;
 761             }
 762             memcpy(ndata, encoder->data, encoder->datalen);
 763             encoder->data = ndata;
 764             encoder->datalen = nlen;
 765         }
 766         encoder->bit = 0;
 767         encoder->data[encoder->offset] = 0xffu;
 768     }
 769     if (!bit) {
 770         encoder->data[encoder->offset] &= ~cbit_mask[encoder->bit];
 771     }
 772     return APR_SUCCESS;
 773 }
 774
 775 static apr_status_t gset_encode_next(gset_encoder *encoder, apr_uint64_t pval)
 776 {
 777     apr_uint64_t delta, flex_bits;
 778     apr_status_t status = APR_SUCCESS;
 779     int i;
 780
 781     delta = pval - encoder->last;
 782     encoder->last = pval;
 783     flex_bits = (delta >> encoder->fixed_bits);
 784     /* Intentional no APLOGNO */
 785     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, encoder->pool,
 786                   "h2_push_diary_enc: val=%"APR_UINT64_T_HEX_FMT", delta=%"
 787                   APR_UINT64_T_HEX_FMT" flex_bits=%"APR_UINT64_T_FMT", "
 788                   ", fixed_bits=%d, fixed_val=%"APR_UINT64_T_HEX_FMT,
 789                   pval, delta, flex_bits, encoder->fixed_bits, delta&encoder->fixed_mask);
 790     for (; flex_bits != 0; --flex_bits) {
 791         status = gset_encode_bit(encoder, 1);
 792         if (status != APR_SUCCESS) {
 793             return status;
 794         }
 795     }
 796     status = gset_encode_bit(encoder, 0);
 797     if (status != APR_SUCCESS) {
 798         return status;
 799     }
 800
 801     for (i = encoder->fixed_bits-1; i >= 0; --i) {
 802         status = gset_encode_bit(encoder, (delta >> i) & 1);
 803         if (status != APR_SUCCESS) {
 804             return status;
 805         }
 806     }
 807     return APR_SUCCESS;
 808 }
 809
 810 /**
 811  * Get a cache digest as described in
 812  * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
 813  * from the contents of the push diary.
 814  *
 815  * @param diary the diary to calculdate the digest from
 816  * @param p the pool to use
 817  * @param pdata on successful return, the binary cache digest
 818  * @param plen on successful return, the length of the binary data
 819  */
 820 apr_status_t h2_push_diary_digest_get(h2_push_diary *diary, apr_pool_t *pool,
 821                                       int maxP, const char *authority,
 822                                       const char **pdata, apr_size_t *plen)
 823 {
 824     int nelts, N, i;
 825     unsigned char log2n, log2pmax;
 826     gset_encoder encoder;
 827     apr_uint64_t *hashes;
 828     apr_size_t hash_count;
 829
 830     nelts = diary->entries->nelts;
 831
 832     if (nelts > APR_UINT32_MAX) {
 833         /* should not happen */
 834         return APR_ENOTIMPL;
 835     }
 836     N = ceil_power_of_2(nelts);
 837     log2n = h2_log2(N);
 838
 839     /* Now log2p is the max number of relevant bits, so that
 840      * log2p + log2n == mask_bits. We can uise a lower log2p
 841      * and have a shorter set encoding...
 842      */
 843     log2pmax = h2_log2(ceil_power_of_2(maxP));
 844
 845     memset(&encoder, 0, sizeof(encoder));
 846     encoder.diary = diary;
 847     encoder.log2p = H2MIN(diary->mask_bits - log2n, log2pmax);
 848     encoder.mask_bits = log2n + encoder.log2p;
 849     encoder.delta_bits = diary->mask_bits - encoder.mask_bits;
 850     encoder.fixed_bits = encoder.log2p;
 851     encoder.fixed_mask = 1;
 852     encoder.fixed_mask = (encoder.fixed_mask << encoder.fixed_bits) - 1;
 853     encoder.pool = pool;
 854     encoder.datalen = 512;
 855     encoder.data = apr_pcalloc(encoder.pool, encoder.datalen);
 856
 857     encoder.data[0] = log2n;
 858     encoder.data[1] = encoder.log2p;
 859     encoder.offset = 1;
 860     encoder.bit = 8;
 861     encoder.last = 0;
 862
 863     /* Intentional no APLOGNO */
 864     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
 865                   "h2_push_diary_digest_get: %d entries, N=%d, log2n=%d, "
 866                   "mask_bits=%d, enc.mask_bits=%d, delta_bits=%d, enc.log2p=%d, authority=%s",
 867                   (int)nelts, (int)N, (int)log2n, diary->mask_bits,
 868                   (int)encoder.mask_bits, (int)encoder.delta_bits,
 869                   (int)encoder.log2p, authority);
 870
 871     if (!authority || !diary->authority
 872         || !strcmp("*", authority) || !strcmp(diary->authority, authority)) {
 873         hash_count = diary->entries->nelts;
 874         hashes = apr_pcalloc(encoder.pool, hash_count);
 875         for (i = 0; i < hash_count; ++i) {
 876             hashes[i] = ((&APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry))->hash
 877                          >> encoder.delta_bits);
 878         }
 879
 880         qsort(hashes, hash_count, sizeof(apr_uint64_t), cmp_puint64);
 881         for (i = 0; i < hash_count; ++i) {
 882             if (!i || (hashes[i] != hashes[i-1])) {
 883                 gset_encode_next(&encoder, hashes[i]);
 884             }
 885         }
 886         /* Intentional no APLOGNO */
 887         ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
 888                       "h2_push_diary_digest_get: golomb compressed hashes, %d bytes",
 889                       (int)encoder.offset + 1);
 890     }
 891     *pdata = (const char *)encoder.data;
 892     *plen = encoder.offset + 1;
 893
 894     return APR_SUCCESS;
 895 }
 896
 897 typedef struct {
 898     h2_push_diary *diary;
 899     apr_pool_t *pool;
 900     unsigned char log2p;
 901     const unsigned char *data;
 902     apr_size_t datalen;
 903     apr_size_t offset;
 904     unsigned int bit;
 905     apr_uint64_t last_val;
 906 } gset_decoder;
 907
 908 static int gset_decode_next_bit(gset_decoder *decoder)
 909 {
 910     if (++decoder->bit >= 8) {
 911         if (++decoder->offset >= decoder->datalen) {
 912             return -1;
 913         }
 914         decoder->bit = 0;
 915     }
 916     return (decoder->data[decoder->offset] & cbit_mask[decoder->bit])? 1 : 0;
 917 }
 918
 919 static apr_status_t gset_decode_next(gset_decoder *decoder, apr_uint64_t *phash)
 920 {
 921     apr_uint64_t flex = 0, fixed = 0, delta;
 922     int i;
 923
 924     /* read 1 bits until we encounter 0, then read log2n(diary-P) bits.
 925      * On a malformed bit-string, this will not fail, but produce results
 926      * which are pbly too large. Luckily, the diary will modulo the hash.
 927      */
 928     while (1) {
 929         int bit = gset_decode_next_bit(decoder);
 930         if (bit == -1) {
 931             return APR_EINVAL;
 932         }
 933         if (!bit) {
 934             break;
 935         }
 936         ++flex;
 937     }
 938
 939     for (i = 0; i < decoder->log2p; ++i) {
 940         int bit = gset_decode_next_bit(decoder);
 941         if (bit == -1) {
 942             return APR_EINVAL;
 943         }
 944         fixed = (fixed << 1) | bit;
 945     }
 946
 947     delta = (flex << decoder->log2p) | fixed;
 948     *phash = delta + decoder->last_val;
 949     decoder->last_val = *phash;
 950
 951     /* Intentional no APLOGNO */
 952     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, decoder->pool,
 953                   "h2_push_diary_digest_dec: val=%"APR_UINT64_T_HEX_FMT", delta=%"
 954                   APR_UINT64_T_HEX_FMT", flex=%d, fixed=%"APR_UINT64_T_HEX_FMT,
 955                   *phash, delta, (int)flex, fixed);
 956
 957     return APR_SUCCESS;
 958 }
 959
 960 /**
 961  * Initialize the push diary by a cache digest as described in
 962  * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
 963  * .
 964  * @param diary the diary to set the digest into
 965  * @param data the binary cache digest
 966  * @param len the length of the cache digest
 967  * @return APR_EINVAL if digest was not successfully parsed
 968  */
 969 apr_status_t h2_push_diary_digest_set(h2_push_diary *diary, const char *authority,
 970                                       const char *data, apr_size_t len)
 971 {
 972     gset_decoder decoder;
 973     unsigned char log2n, log2p;
 974     int N, i;
 975     apr_pool_t *pool = diary->entries->pool;
 976     h2_push_diary_entry e;
 977     apr_status_t status = APR_SUCCESS;
 978
 979     if (len < 2) {
 980         /* at least this should be there */
 981         return APR_EINVAL;
 982     }
 983     log2n = data[0];
 984     log2p = data[1];
 985     diary->mask_bits = log2n + log2p;
 986     if (diary->mask_bits > 64) {
 987         /* cannot handle */
 988         return APR_ENOTIMPL;
 989     }
 990
 991     /* whatever is in the digest, it replaces the diary entries */
 992     apr_array_clear(diary->entries);
 993     if (!authority || !strcmp("*", authority)) {
 994         diary->authority = NULL;
 995     }
 996     else if (!diary->authority || strcmp(diary->authority, authority)) {
 997         diary->authority = apr_pstrdup(diary->entries->pool, authority);
 998     }
 999
1000     N = h2_log2inv(log2n + log2p);
1001
1002     decoder.diary    = diary;
1003     decoder.pool     = pool;
1004     decoder.log2p    = log2p;
1005     decoder.data     = (const unsigned char*)data;
1006     decoder.datalen  = len;
1007     decoder.offset   = 1;
1008     decoder.bit      = 8;
1009     decoder.last_val = 0;
1010
1011     diary->N = N;
1012     /* Determine effective N we use for storage */
1013     if (!N) {
1014         /* a totally empty cache digest. someone tells us that she has no
1015          * entries in the cache at all. Use our own preferences for N+mask
1016          */
1017         diary->N = diary->NMax;
1018         return APR_SUCCESS;
1019     }
1020     else if (N > diary->NMax) {
1021         /* Store not more than diary is configured to hold. We open us up
1022          * to DOS attacks otherwise. */
1023         diary->N = diary->NMax;
1024     }
1025
1026     /* Intentional no APLOGNO */
1027     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
1028                   "h2_push_diary_digest_set: N=%d, log2n=%d, "
1029                   "diary->mask_bits=%d, dec.log2p=%d",
1030                   (int)diary->N, (int)log2n, diary->mask_bits,
1031                   (int)decoder.log2p);
1032
1033     for (i = 0; i < diary->N; ++i) {
1034         if (gset_decode_next(&decoder, &e.hash) != APR_SUCCESS) {
1035             /* the data may have less than N values */
1036             break;
1037         }
1038         h2_push_diary_append(diary, &e);
1039     }
1040
1041     /* Intentional no APLOGNO */
1042     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
1043                   "h2_push_diary_digest_set: diary now with %d entries, mask_bits=%d",
1044                   (int)diary->entries->nelts, diary->mask_bits);
1045     return status;
1046 }
1047
1048 apr_status_t h2_push_diary_digest64_set(h2_push_diary *diary, const char *authority,
1049                                         const char *data64url, apr_pool_t *pool)
1050 {
1051     const char *data;
1052     apr_size_t len = h2_util_base64url_decode(&data, data64url, pool);
1053     /* Intentional no APLOGNO */
1054     ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
1055                   "h2_push_diary_digest64_set: digest=%s, dlen=%d",
1056                   data64url, (int)len);
1057     return h2_push_diary_digest_set(diary, authority, data, len);
1058 }
1059