modules/http2/h2_push.c

/* Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
 
#include <assert.h>
#include <stdio.h>

#include <apr_lib.h>
#include <apr_strings.h>
#include <apr_hash.h>
#include <apr_time.h>

#ifdef H2_OPENSSL
#include <openssl/evp.h>
#endif

#include <httpd.h>
#include <http_core.h>
#include <http_log.h>
#include <http_protocol.h>

#include "h2_private.h"
#include "h2_protocol.h"
#include "h2_util.h"
#include "h2_push.h"
#include "h2_request.h"
#include "h2_session.h"
#include "h2_stream.h"

/*******************************************************************************
 * link header handling 
 ******************************************************************************/

static const char *policy_str(h2_push_policy policy)
{
    switch (policy) {
        case H2_PUSH_NONE:
            return "none";
        case H2_PUSH_FAST_LOAD:
            return "fast-load";
        case H2_PUSH_HEAD:
            return "head";
        default:
            return "default";
    }
}

typedef struct {
    const h2_request *req;
    apr_uint32_t push_policy;
    apr_pool_t *pool;
    apr_array_header_t *pushes;
    const char *s;
    size_t slen;
    size_t i;
    
    const char *link;
    apr_table_t *params;
    char b[4096];
} link_ctx;

static int attr_char(char c) 
{
    switch (c) {
        case '!':
        case '#':
        case '$':
        case '&':
        case '+':
        case '-':
        case '.':
        case '^':
        case '_':
        case '`':
        case '|':
        case '~':
            return 1;
        default:
            return apr_isalnum(c);
    }
}

static int ptoken_char(char c) 
{
    switch (c) {
        case '!':
        case '#':
        case '$':
        case '&':
        case '\'':
        case '(':
        case ')':
        case '*':
        case '+':
        case '-':
        case '.':
        case '/':
        case ':':
        case '<':
        case '=':
        case '>':
        case '?':
        case '@':
        case '[':
        case ']':
        case '^':
        case '_':
        case '`':
        case '{':
        case '|':
        case '}':
        case '~':
            return 1;
        default:
            return apr_isalnum(c);
    }
}

static int skip_ws(link_ctx *ctx)
{
    char c;
    while (ctx->i < ctx->slen 
           && (((c = ctx->s[ctx->i]) == ' ') || (c == '\t'))) {
        ++ctx->i;
    }
    return (ctx->i < ctx->slen);
}

static int find_chr(link_ctx *ctx, char c, size_t *pidx)
{
    size_t j;
    for (j = ctx->i; j < ctx->slen; ++j) {
        if (ctx->s[j] == c) {
            *pidx = j;
            return 1;
        }
    } 
    return 0;
}

static int read_chr(link_ctx *ctx, char c)
{
    if (ctx->i < ctx->slen && ctx->s[ctx->i] == c) {
        ++ctx->i;
        return 1;
    }
    return 0;
}

static char *mk_str(link_ctx *ctx, size_t end) 
{
    if (ctx->i < end) {
        return apr_pstrndup(ctx->pool, ctx->s + ctx->i, end - ctx->i);
    }
    return (char*)"";
}

static int read_qstring(link_ctx *ctx, const char **ps)
{
    if (skip_ws(ctx) && read_chr(ctx, '\"')) {
        size_t end;
        if (find_chr(ctx, '\"', &end)) {
            *ps = mk_str(ctx, end);
            ctx->i = end + 1;
            return 1;
        }
    }
    return 0;
}

static int read_ptoken(link_ctx *ctx, const char **ps)
{
    if (skip_ws(ctx)) {
        size_t i;
        for (i = ctx->i; i < ctx->slen && ptoken_char(ctx->s[i]); ++i) {
            /* nop */
        }
        if (i > ctx->i) {
            *ps = mk_str(ctx, i);
            ctx->i = i;
            return 1;
        }
    }
    return 0;
}


static int read_link(link_ctx *ctx)
{
    if (skip_ws(ctx) && read_chr(ctx, '<')) {
        size_t end;
        if (find_chr(ctx, '>', &end)) {
            ctx->link = mk_str(ctx, end);
            ctx->i = end + 1;
            return 1;
        }
    }
    return 0;
}

static int read_pname(link_ctx *ctx, const char **pname)
{
    if (skip_ws(ctx)) {
        size_t i;
        for (i = ctx->i; i < ctx->slen && attr_char(ctx->s[i]); ++i) {
            /* nop */
        }
        if (i > ctx->i) {
            *pname = mk_str(ctx, i);
            ctx->i = i;
            return 1;
        }
    }
    return 0;
}

static int read_pvalue(link_ctx *ctx, const char **pvalue)
{
    if (skip_ws(ctx) && read_chr(ctx, '=')) {
        if (read_qstring(ctx, pvalue) || read_ptoken(ctx, pvalue)) {
            return 1;
        }
    }
    return 0;
}

static int read_param(link_ctx *ctx)
{
    if (skip_ws(ctx) && read_chr(ctx, ';')) {
        const char *name, *value = "";
        if (read_pname(ctx, &name)) {
            read_pvalue(ctx, &value); /* value is optional */
            apr_table_setn(ctx->params, name, value);
            return 1;
        }
    }
    return 0;
}

static int read_sep(link_ctx *ctx)
{
    if (skip_ws(ctx) && read_chr(ctx, ',')) {
        return 1;
    }
    return 0;
}

static void init_params(link_ctx *ctx) 
{
    if (!ctx->params) {
        ctx->params = apr_table_make(ctx->pool, 5);
    }
    else {
        apr_table_clear(ctx->params);
    }
}

static int same_authority(const h2_request *req, const apr_uri_t *uri)
{
    if (uri->scheme != NULL && strcmp(uri->scheme, req->scheme)) {
        return 0;
    }
    if (uri->hostinfo != NULL && strcmp(uri->hostinfo, req->authority)) {
        return 0;
    }
    return 1;
}

static int set_push_header(void *ctx, const char *key, const char *value) 
{
    size_t klen = strlen(key);
    if (H2_HD_MATCH_LIT("User-Agent", key, klen)
        || H2_HD_MATCH_LIT("Accept", key, klen)
        || H2_HD_MATCH_LIT("Accept-Encoding", key, klen)
        || H2_HD_MATCH_LIT("Accept-Language", key, klen)
        || H2_HD_MATCH_LIT("Cache-Control", key, klen)) {
        apr_table_setn(ctx, key, value);
    }
    return 1;
}

static int has_param(link_ctx *ctx, const char *param)
{
    const char *p = apr_table_get(ctx->params, param);
    return !!p;
}

static int has_relation(link_ctx *ctx, const char *rel)
{
    const char *s, *val = apr_table_get(ctx->params, "rel");
    if (val) {
        if (!strcmp(rel, val)) {
            return 1;
        }
        s = ap_strstr_c(val, rel);
        if (s && (s == val || s[-1] == ' ')) {
            s += strlen(rel);
            if (!*s || *s == ' ') {
                return 1;
            }
        }
    }
    return 0;
}

static int add_push(link_ctx *ctx)
{
    /* so, we have read a Link header and need to decide
     * if we transform it into a push.
     */
    if (has_relation(ctx, "preload") && !has_param(ctx, "nopush")) {
        apr_uri_t uri;
        if (apr_uri_parse(ctx->pool, ctx->link, &uri) == APR_SUCCESS) {
            if (uri.path && same_authority(ctx->req, &uri)) {
                char *path;
                const char *method;
                apr_table_t *headers;
                h2_request *req;
                h2_push *push;
                
                /* We only want to generate pushes for resources in the
                 * same authority than the original request.
                 * icing: i think that is wise, otherwise we really need to
                 * check that the vhost/server is available and uses the same
                 * TLS (if any) parameters.
                 */
                path = apr_uri_unparse(ctx->pool, &uri, APR_URI_UNP_OMITSITEPART);
                push = apr_pcalloc(ctx->pool, sizeof(*push));
                switch (ctx->push_policy) {
                    case H2_PUSH_HEAD:
                        method = "HEAD";
                        break;
                    default:
                        method = "GET";
                        break;
                }
                headers = apr_table_make(ctx->pool, 5);
                apr_table_do(set_push_header, headers, ctx->req->headers, NULL);
                req = h2_request_create(0, ctx->pool, method, ctx->req->scheme,
                                        ctx->req->authority, path, headers);
                /* atm, we do not push on pushes */
                h2_request_end_headers(req, ctx->pool, 0);
                push->req = req;
                if (has_param(ctx, "critical")) {
                    h2_priority *prio = apr_pcalloc(ctx->pool, sizeof(*prio));
                    prio->dependency = H2_DEPENDANT_BEFORE;
                    push->priority = prio;
                }
                if (!ctx->pushes) {
                    ctx->pushes = apr_array_make(ctx->pool, 5, sizeof(h2_push*));
                }
                APR_ARRAY_PUSH(ctx->pushes, h2_push*) = push;
            }
        }
    }
    return 0;
}

static void inspect_link(link_ctx *ctx, const char *s, size_t slen)
{
    /* RFC 5988 <https://tools.ietf.org/html/rfc5988#section-6.2.1>
      Link           = "Link" ":" #link-value
      link-value     = "<" URI-Reference ">" *( ";" link-param )
      link-param     = ( ( "rel" "=" relation-types )
                     | ( "anchor" "=" <"> URI-Reference <"> )
                     | ( "rev" "=" relation-types )
                     | ( "hreflang" "=" Language-Tag )
                     | ( "media" "=" ( MediaDesc | ( <"> MediaDesc <"> ) ) )
                     | ( "title" "=" quoted-string )
                     | ( "title*" "=" ext-value )
                     | ( "type" "=" ( media-type | quoted-mt ) )
                     | ( link-extension ) )
      link-extension = ( parmname [ "=" ( ptoken | quoted-string ) ] )
                     | ( ext-name-star "=" ext-value )
      ext-name-star  = parmname "*" ; reserved for RFC2231-profiled
                                    ; extensions.  Whitespace NOT
                                    ; allowed in between.
      ptoken         = 1*ptokenchar
      ptokenchar     = "!" | "#" | "$" | "%" | "&" | "'" | "("
                     | ")" | "*" | "+" | "-" | "." | "/" | DIGIT
                     | ":" | "<" | "=" | ">" | "?" | "@" | ALPHA
                     | "[" | "]" | "^" | "_" | "`" | "{" | "|"
                     | "}" | "~"
      media-type     = type-name "/" subtype-name
      quoted-mt      = <"> media-type <">
      relation-types = relation-type
                     | <"> relation-type *( 1*SP relation-type ) <">
      relation-type  = reg-rel-type | ext-rel-type
      reg-rel-type   = LOALPHA *( LOALPHA | DIGIT | "." | "-" )
      ext-rel-type   = URI
      
      and from <https://tools.ietf.org/html/rfc5987>
      parmname      = 1*attr-char
      attr-char     = ALPHA / DIGIT
                       / "!" / "#" / "$" / "&" / "+" / "-" / "."
                       / "^" / "_" / "`" / "|" / "~"
     */

     ctx->s = s;
     ctx->slen = slen;
     ctx->i = 0;
     
     while (read_link(ctx)) {
        init_params(ctx);
        while (read_param(ctx)) {
            /* nop */
        }
        add_push(ctx);
        if (!read_sep(ctx)) {
            break;
        }
     }
}

static int head_iter(void *ctx, const char *key, const char *value) 
{
    if (!ap_cstr_casecmp("link", key)) {
        inspect_link(ctx, value, strlen(value));
    }
    return 1;
}

#if AP_HAS_RESPONSE_BUCKETS
apr_array_header_t *h2_push_collect(apr_pool_t *p,
                                    const struct h2_request *req,
                                    apr_uint32_t push_policy,
                                    const ap_bucket_response *res)
#else
apr_array_header_t *h2_push_collect(apr_pool_t *p,
                                    const struct h2_request *req,
                                    apr_uint32_t push_policy,
                                    const struct h2_headers *res)
#endif
{
    if (req && push_policy != H2_PUSH_NONE) {
        /* Collect push candidates from the request/response pair.
         * 
         * One source for pushes are "rel=preload" link headers
         * in the response.
         * 
         * TODO: This may be extended in the future by hooks or callbacks
         * where other modules can provide push information directly.
         */
        if (res->headers) {
            link_ctx ctx;
            
            memset(&ctx, 0, sizeof(ctx));
            ctx.req = req;
            ctx.push_policy = push_policy;
            ctx.pool = p;
            
            apr_table_do(head_iter, &ctx, res->headers, NULL);
            if (ctx.pushes) {
                apr_table_setn(res->headers, "push-policy", 
                               policy_str(push_policy));
            }
            return ctx.pushes;
        }
    }
    return NULL;
}

#define GCSLOG_LEVEL   APLOG_TRACE1

typedef struct h2_push_diary_entry {
    apr_uint64_t hash;
} h2_push_diary_entry;


#ifdef H2_OPENSSL
static void sha256_update(EVP_MD_CTX *ctx, const char *s)
{
    EVP_DigestUpdate(ctx, s, strlen(s));
}

static void calc_sha256_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push) 
{
    EVP_MD_CTX *md;
    apr_uint64_t val;
    unsigned char hash[EVP_MAX_MD_SIZE];
    unsigned len, i;

    md = EVP_MD_CTX_create();
    ap_assert(md != NULL);

    i = EVP_DigestInit_ex(md, EVP_sha256(), NULL);
    ap_assert(i == 1);
    sha256_update(md, push->req->scheme);
    sha256_update(md, "://");
    sha256_update(md, push->req->authority);
    sha256_update(md, push->req->path);
    EVP_DigestFinal(md, hash, &len);
    EVP_MD_CTX_destroy(md);

    val = 0;
    for (i = 0; i != len; ++i)
        val = val * 256 + hash[i];
    *phash = val >> (64 - diary->mask_bits);
}
#endif


static unsigned int val_apr_hash(const char *str) 
{
    apr_ssize_t len = (apr_ssize_t)strlen(str);
    return apr_hashfunc_default(str, &len);
}

static void calc_apr_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push) 
{
    apr_uint64_t val;
    (void)diary;
#if APR_UINT64_MAX > UINT_MAX
    val = ((apr_uint64_t)(val_apr_hash(push->req->scheme)) << 32);
    val ^= ((apr_uint64_t)(val_apr_hash(push->req->authority)) << 16);
    val ^= val_apr_hash(push->req->path);
#else
    val = val_apr_hash(push->req->scheme);
    val ^= val_apr_hash(push->req->authority);
    val ^= val_apr_hash(push->req->path);
#endif
    *phash = val;
}

static apr_int32_t ceil_power_of_2(apr_int32_t n)
{
    if (n <= 2) return 2;
    --n;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    return ++n;
}

static h2_push_diary *diary_create(apr_pool_t *p, h2_push_digest_type dtype, 
                                   int N)
{
    h2_push_diary *diary = NULL;
    
    if (N > 0) {
        diary = apr_pcalloc(p, sizeof(*diary));
        
        diary->NMax        = ceil_power_of_2(N);
        diary->N           = diary->NMax;
        /* the mask we use in value comparison depends on where we got
         * the values from. If we calculate them ourselves, we can use
         * the full 64 bits.
         * If we set the diary via a compressed golomb set, we have less
         * relevant bits and need to use a smaller mask. */
        diary->mask_bits   = 64;
        /* grows by doubling, start with a power of 2 */
        diary->entries     = apr_array_make(p, 16, sizeof(h2_push_diary_entry));
        
        switch (dtype) {
#ifdef H2_OPENSSL
            case H2_PUSH_DIGEST_SHA256:
                diary->dtype       = H2_PUSH_DIGEST_SHA256;
                diary->dcalc       = calc_sha256_hash;
                break;
#endif /* ifdef H2_OPENSSL */
            default:
                diary->dtype       = H2_PUSH_DIGEST_APR_HASH;
                diary->dcalc       = calc_apr_hash;
                break;
        }
    }
    
    return diary;
}

h2_push_diary *h2_push_diary_create(apr_pool_t *p, int N)
{
    return diary_create(p, H2_PUSH_DIGEST_SHA256, N);
}

static int h2_push_diary_find(h2_push_diary *diary, apr_uint64_t hash)
{
    if (diary) {
        h2_push_diary_entry *e;
        int i;

        /* search from the end, where the last accessed digests are */
        for (i = diary->entries->nelts-1; i >= 0; --i) {
            e = &APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry);
            if (e->hash == hash) {
                return i;
            }
        }
    }
    return -1;
}

static void move_to_last(h2_push_diary *diary, apr_size_t idx)
{
    h2_push_diary_entry *entries = (h2_push_diary_entry*)diary->entries->elts;
    h2_push_diary_entry e;
    apr_size_t lastidx;
    
    /* Move an existing entry to the last place */
    if (diary->entries->nelts <= 0)
        return;

    /* move entry[idx] to the end */
    lastidx = diary->entries->nelts - 1;
    if (idx < lastidx) {
        e =  entries[idx];
        memmove(entries+idx, entries+idx+1, sizeof(h2_push_diary_entry) * (lastidx - idx));
        entries[lastidx] = e;
    }
}

static void remove_first(h2_push_diary *diary)
{
    h2_push_diary_entry *entries = (h2_push_diary_entry*)diary->entries->elts;
    int lastidx;
    
    /* move remaining entries to index 0 */
    lastidx = diary->entries->nelts - 1;
    if (lastidx > 0) {
        --diary->entries->nelts;
        memmove(entries, entries+1, sizeof(h2_push_diary_entry) * diary->entries->nelts);
    }
}

static void h2_push_diary_append(h2_push_diary *diary, h2_push_diary_entry *e)
{
    while (diary->entries->nelts >= diary->N) {
        remove_first(diary);
    }
    /* append a new diary entry at the end */
    APR_ARRAY_PUSH(diary->entries, h2_push_diary_entry) = *e;
    /* Intentional no APLOGNO */
    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, diary->entries->pool,
                  "push_diary_append: %"APR_UINT64_T_HEX_FMT, e->hash);
}

apr_array_header_t *h2_push_diary_update(h2_session *session, apr_array_header_t *pushes)
{
    apr_array_header_t *npushes = pushes;
    h2_push_diary_entry e;
    int i, idx;
    
    if (session->push_diary && pushes) {
        npushes = NULL;
        
        for (i = 0; i < pushes->nelts; ++i) {
            h2_push *push;
            
            push = APR_ARRAY_IDX(pushes, i, h2_push*);
            session->push_diary->dcalc(session->push_diary, &e.hash, push);
            idx = h2_push_diary_find(session->push_diary, e.hash);
            if (idx >= 0) {
                /* Intentional no APLOGNO */
                ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c1,
                              "push_diary_update: already there PUSH %s", push->req->path);
                move_to_last(session->push_diary, (apr_size_t)idx);
            }
            else {
                /* Intentional no APLOGNO */
                ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c1,
                              "push_diary_update: adding PUSH %s", push->req->path);
                if (!npushes) {
                    npushes = apr_array_make(pushes->pool, 5, sizeof(h2_push_diary_entry*));
                }
                APR_ARRAY_PUSH(npushes, h2_push*) = push;
                h2_push_diary_append(session->push_diary, &e);
            }
        }
    }
    return npushes;
}
    
#if AP_HAS_RESPONSE_BUCKETS
apr_array_header_t *h2_push_collect_update(struct h2_stream *stream,
                                           const struct h2_request *req,
                                           const ap_bucket_response *res)
#else
apr_array_header_t *h2_push_collect_update(struct h2_stream *stream,
                                           const struct h2_request *req,
                                           const struct h2_headers *res)
#endif
{
    apr_array_header_t *pushes;
    
    pushes = h2_push_collect(stream->pool, req, stream->push_policy, res);
    return h2_push_diary_update(stream->session, pushes);
}