Mailing-List: contact cvs-help@httpd.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@httpd.apache.org
Content-Type: text/plain; charset="utf-8"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Subject: svn commit: r1725301 [3/6] - in /httpd/httpd/branches/2.4.x: ./
 docs/manual/mod/ modules/http2/
Date: Mon, 18 Jan 2016 16:22:58 -0000
To: cvs@httpd.apache.org
From: icing@apache.org
Message-Id: <20160118162258.9CD073A1E39@svn01-us-west.apache.org>

Modified: httpd/httpd/branches/2.4.x/modules/http2/h2_push.c
URL: http://svn.apache.org/viewvc/httpd/httpd/branches/2.4.x/modules/http2/h2_push.c?rev=1725301&r1=1725300&r2=1725301&view=diff
==============================================================================
--- httpd/httpd/branches/2.4.x/modules/http2/h2_push.c (original)
+++ httpd/httpd/branches/2.4.x/modules/http2/h2_push.c Mon Jan 18 16:22:57 2016
@@ -16,8 +16,14 @@
 #include <assert.h>
 #include <stdio.h>
 
-#include <apr_strings.h>
 #include <apr_lib.h>
+#include <apr_strings.h>
+#include <apr_hash.h>
+#include <apr_time.h>
+
+#ifdef H2_OPENSSL
+#include <openssl/sha.h>
+#endif
 
 #include <httpd.h>
 #include <http_core.h>
@@ -29,7 +35,26 @@
 #include "h2_push.h"
 #include "h2_request.h"
 #include "h2_response.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;
@@ -269,6 +294,7 @@ static int add_push(link_ctx *ctx)
         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;
@@ -283,6 +309,14 @@ static int add_push(link_ctx *ctx)
                 
                 push = apr_pcalloc(ctx->pool, sizeof(*push));
                 
+                switch (ctx->req->push_policy) {
+                    case H2_PUSH_HEAD:
+                        method = "HEAD";
+                        break;
+                    default:
+                        method = "GET";
+                        break;
+                }
                 headers = apr_table_make(ctx->pool, 5);
                 apr_table_do(set_header, headers, ctx->req->headers,
                              "User-Agent",
@@ -290,10 +324,11 @@ static int add_push(link_ctx *ctx)
                              "Accept-Language",
                              NULL);
                 req = h2_request_createn(0, ctx->pool, ctx->req->config, 
-                                         "GET", ctx->req->scheme,
+                                         method, ctx->req->scheme,
                                          ctx->req->authority, 
                                          path, headers);
-                h2_request_end_headers(req, ctx->pool, 1);
+                /* atm, we do not push on pushes */
+                h2_request_end_headers(req, ctx->pool, 1, 0);
                 push->req = req;
                 
                 if (!ctx->pushes) {
@@ -373,23 +408,651 @@ static int head_iter(void *ctx, const ch
 apr_array_header_t *h2_push_collect(apr_pool_t *p, const h2_request *req, 
                                     const h2_response *res)
 {
-    /* 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 (req && 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.pool = p;
+            
+            apr_table_do(head_iter, &ctx, res->headers, NULL);
+            if (ctx.pushes) {
+                apr_table_setn(res->headers, "push-policy", policy_str(req->push_policy));
+            }
+            return ctx.pushes;
+        }
+    }
+    return NULL;
+}
+
+void h2_push_policy_determine(struct h2_request *req, apr_pool_t *p, int push_enabled)
+{
+    h2_push_policy policy = H2_PUSH_NONE;
+    if (push_enabled) {
+        const char *val = apr_table_get(req->headers, "accept-push-policy");
+        if (val) {
+            if (ap_find_token(p, val, "fast-load")) {
+                policy = H2_PUSH_FAST_LOAD;
+            }
+            else if (ap_find_token(p, val, "head")) {
+                policy = H2_PUSH_HEAD;
+            }
+            else if (ap_find_token(p, val, "default")) {
+                policy = H2_PUSH_DEFAULT;
+            }
+            else if (ap_find_token(p, val, "none")) {
+                policy = H2_PUSH_NONE;
+            }
+            else {
+                /* nothing known found in this header, go by default */
+                policy = H2_PUSH_DEFAULT;
+            }
+        }
+        else {
+            policy = H2_PUSH_DEFAULT;
+        }
+    }
+    req->push_policy = policy;
+}
+
+/*******************************************************************************
+ * push diary 
+ ******************************************************************************/
+ 
+ 
+#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(SHA256_CTX *ctx, const char *s)
+{
+    SHA256_Update(ctx, s, strlen(s));
+}
+
+static void calc_sha256_hash(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push) 
+{
+    SHA256_CTX sha256;
+    apr_uint64_t val;
+    unsigned char hash[SHA256_DIGEST_LENGTH];
+    int i;
+    
+    SHA256_Init(&sha256);
+    sha256_update(&sha256, push->req->scheme);
+    sha256_update(&sha256, "://");
+    sha256_update(&sha256, push->req->authority);
+    sha256_update(&sha256, push->req->path);
+    SHA256_Final(hash, &sha256);
+
+    val = 0;
+    for (i = 0; i != sizeof(val); ++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 = 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;
+#if APR_UINT64MAX > APR_UINT_MAX
+    val = (val_apr_hash(push->req->scheme) << 32);
+    val ^= (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, 
+                                   apr_size_t 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 comparision 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, apr_size_t 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 h2_push_diary_entry *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 = diary->entries->nelts-1;
+    
+    /* move entry[idx] to the end */
+    if (idx < lastidx) {
+        e =  entries[idx];
+        memmove(entries+idx, entries+idx+1, sizeof(e) * (lastidx - idx));
+        entries[lastidx] = e;
+    }
+    return &entries[lastidx];
+}
+
+static void h2_push_diary_append(h2_push_diary *diary, h2_push_diary_entry *e)
+{
+    h2_push_diary_entry *ne;
+    
+    if (diary->entries->nelts < diary->N) {
+        /* append a new diary entry at the end */
+        APR_ARRAY_PUSH(diary->entries, h2_push_diary_entry) = *e;
+        ne = &APR_ARRAY_IDX(diary->entries, diary->entries->nelts-1, h2_push_diary_entry);
+    }
+    else {
+        /* replace content with new digest. keeps memory usage constant once diary is full */
+        ne = move_to_last(diary, 0);
+        *ne = *e;
+    }
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, diary->entries->pool,
+                  "push_diary_append: %"APR_UINT64_T_HEX_FMT, ne->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) {
+                ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c,
+                              "push_diary_update: already there PUSH %s", push->req->path);
+                move_to_last(session->push_diary, idx);
+            }
+            else {
+                ap_log_cerror(APLOG_MARK, GCSLOG_LEVEL, 0, session->c,
+                              "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;
+}
+    
+apr_array_header_t *h2_push_collect_update(h2_stream *stream, 
+                                           const struct h2_request *req, 
+                                           const struct h2_response *res)
+{
+    h2_session *session = stream->session;
+    const char *cache_digest = apr_table_get(req->headers, "Cache-Digest");
+    apr_array_header_t *pushes;
+    apr_status_t status;
+    
+    if (cache_digest && session->push_diary) {
+        status = h2_push_diary_digest64_set(session->push_diary, req->authority, 
+                                            cache_digest, stream->pool);
+        if (status != APR_SUCCESS) {
+            ap_log_cerror(APLOG_MARK, APLOG_DEBUG, status, session->c,
+                          "h2_session(%ld): push diary set from Cache-Digest: %s", 
+                          session->id, cache_digest);
+        }
+    }
+    pushes = h2_push_collect(stream->pool, req, res);
+    return h2_push_diary_update(stream->session, pushes);
+}
+
+/* h2_log2(n) iff n is a power of 2 */
+static unsigned char h2_log2(apr_uint32_t n)
+{
+    int lz = 0;
+    if (!n) {
+        return 0;
+    }
+    if (!(n & 0xffff0000u)) {
+        lz += 16;
+        n = (n << 16);
+    }
+    if (!(n & 0xff000000u)) {
+        lz += 8;
+        n = (n << 8);
+    }
+    if (!(n & 0xf0000000u)) {
+        lz += 4;
+        n = (n << 4);
+    }
+    if (!(n & 0xc0000000u)) {
+        lz += 2;
+        n = (n << 2);
+    }
+    if (!(n & 0x80000000u)) {
+        lz += 1;
+    }
+    
+    return 31 - lz;
+}
+
+static apr_int32_t h2_log2inv(unsigned char log2)
+{
+    return log2? (1 << log2) : 1;
+}
+
+
+typedef struct {
+    h2_push_diary *diary;
+    unsigned char log2p;
+    apr_uint32_t mask_bits;
+    apr_uint32_t delta_bits;
+    apr_uint32_t fixed_bits;
+    apr_uint64_t fixed_mask;
+    apr_pool_t *pool;
+    unsigned char *data;
+    apr_size_t datalen;
+    apr_size_t offset;
+    unsigned int bit;
+    apr_uint64_t last;
+} gset_encoder;
+
+static int cmp_puint64(const void *p1, const void *p2)
+{
+    const apr_uint64_t *pu1 = p1, *pu2 = p2;
+    return (*pu1 > *pu2)? 1 : ((*pu1 == *pu2)? 0 : -1);
+}
+
+/* in golomb bit stream encoding, bit 0 is the 8th of the first char, or
+ * more generally: 
+ *      char(bit/8) & cbit_mask[(bit % 8)]
+ */
+static unsigned char cbit_mask[] = {
+    0x80u,
+    0x40u,
+    0x20u,
+    0x10u,
+    0x08u,
+    0x04u,
+    0x02u,
+    0x01u,
+};
+
+static apr_status_t gset_encode_bit(gset_encoder *encoder, int bit)
+{
+    if (++encoder->bit >= 8) {
+        if (++encoder->offset >= encoder->datalen) {
+            apr_size_t nlen = encoder->datalen*2;
+            unsigned char *ndata = apr_pcalloc(encoder->pool, nlen);
+            if (!ndata) {
+                return APR_ENOMEM;
+            }
+            memcpy(ndata, encoder->data, encoder->datalen);
+            encoder->data = ndata;
+            encoder->datalen = nlen;
+        }
+        encoder->bit = 0;
+        encoder->data[encoder->offset] = 0xffu;
+    }
+    if (!bit) {
+        encoder->data[encoder->offset] &= ~cbit_mask[encoder->bit];
+    }
+    return APR_SUCCESS;
+}
+
+static apr_status_t gset_encode_next(gset_encoder *encoder, apr_uint64_t pval)
+{
+    apr_uint64_t delta, flex_bits;
+    apr_status_t status = APR_SUCCESS;
+    int i;
+    
+    delta = pval - encoder->last;
+    encoder->last = pval;
+    flex_bits = (delta >> encoder->fixed_bits);
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, encoder->pool,
+                  "h2_push_diary_enc: val=%"APR_UINT64_T_HEX_FMT", delta=%"
+                  APR_UINT64_T_HEX_FMT" flex_bits=%ld, "
+                  "fixed_bits=%d, fixed_val=%"APR_UINT64_T_HEX_FMT, 
+                  pval, delta, flex_bits, encoder->fixed_bits, delta&encoder->fixed_mask);
+    for (; flex_bits != 0; --flex_bits) {
+        status = gset_encode_bit(encoder, 1);
+        if (status != APR_SUCCESS) {
+            return status;
+        }
+    }
+    status = gset_encode_bit(encoder, 0);
+    if (status != APR_SUCCESS) {
+        return status;
+    }
+
+    for (i = encoder->fixed_bits-1; i >= 0; --i) {
+        status = gset_encode_bit(encoder, (delta >> i) & 1);
+        if (status != APR_SUCCESS) {
+            return status;
+        }
+    }
+    return APR_SUCCESS;
+}
+
+/**
+ * Get a cache digest as described in 
+ * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ * from the contents of the push diary.
+ * 
+ * @param diary the diary to calculdate the digest from
+ * @param p the pool to use
+ * @param pdata on successful return, the binary cache digest
+ * @param plen on successful return, the length of the binary data
+ */
+apr_status_t h2_push_diary_digest_get(h2_push_diary *diary, apr_pool_t *pool, 
+                                      apr_uint32_t maxP, const char *authority, 
+                                      const char **pdata, apr_size_t *plen)
+{
+    apr_size_t nelts, N, i;
+    unsigned char log2n, log2pmax;
+    gset_encoder encoder;
+    apr_uint64_t *hashes;
+    apr_size_t hash_count;
+    
+    nelts = diary->entries->nelts;
+    
+    if (nelts > APR_UINT32_MAX) {
+        /* should not happen */
+        return APR_ENOTIMPL;
+    }
+    N = ceil_power_of_2(nelts);
+    log2n = h2_log2(N);
+    
+    /* Now log2p is the max number of relevant bits, so that
+     * log2p + log2n == mask_bits. We can uise a lower log2p
+     * and have a shorter set encoding...
      */
-    if (res->headers) {
-        link_ctx ctx;
+    log2pmax = h2_log2(ceil_power_of_2(maxP));
+    
+    memset(&encoder, 0, sizeof(encoder));
+    encoder.diary = diary;
+    encoder.log2p = H2MIN(diary->mask_bits - log2n, log2pmax);
+    encoder.mask_bits = log2n + encoder.log2p;
+    encoder.delta_bits = diary->mask_bits - encoder.mask_bits;
+    encoder.fixed_bits = encoder.log2p;
+    encoder.fixed_mask = 1;
+    encoder.fixed_mask = (encoder.fixed_mask << encoder.fixed_bits) - 1;
+    encoder.pool = pool;
+    encoder.datalen = 512;
+    encoder.data = apr_pcalloc(encoder.pool, encoder.datalen);
+    
+    encoder.data[0] = log2n;
+    encoder.data[1] = encoder.log2p;
+    encoder.offset = 1;
+    encoder.bit = 8;
+    encoder.last = 0;
+    
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest_get: %d entries, N=%d, log2n=%d, "
+                  "mask_bits=%d, enc.mask_bits=%d, delta_bits=%d, enc.log2p=%d, authority=%s", 
+                  (int)nelts, (int)N, (int)log2n, diary->mask_bits, 
+                  (int)encoder.mask_bits, (int)encoder.delta_bits, 
+                  (int)encoder.log2p, authority);
+                  
+    if (!authority || !diary->authority 
+        || !strcmp("*", authority) || !strcmp(diary->authority, authority)) {
+        hash_count = diary->entries->nelts;
+        hashes = apr_pcalloc(encoder.pool, hash_count);
+        for (i = 0; i < hash_count; ++i) {
+            hashes[i] = ((&APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry))->hash 
+                         >> encoder.delta_bits);
+        }
         
-        memset(&ctx, 0, sizeof(ctx));
-        ctx.req = req;
-        ctx.pool = p;
+        qsort(hashes, hash_count, sizeof(apr_uint64_t), cmp_puint64);
+        for (i = 0; i < hash_count; ++i) {
+            if (!i || (hashes[i] != hashes[i-1])) {
+                gset_encode_next(&encoder, hashes[i]);
+            }
+        }
+        ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                      "h2_push_diary_digest_get: golomb compressed hashes, %d bytes",
+                      (int)encoder.offset + 1);
+    }
+    *pdata = (const char *)encoder.data;
+    *plen = encoder.offset + 1;
     
-        apr_table_do(head_iter, &ctx, res->headers, NULL);
-        return ctx.pushes;
+    return APR_SUCCESS;
+}
+
+typedef struct {
+    h2_push_diary *diary;
+    apr_pool_t *pool;
+    unsigned char log2p;
+    const unsigned char *data;
+    apr_size_t datalen;
+    apr_size_t offset;
+    unsigned int bit;
+    apr_uint64_t last_val;
+} gset_decoder;
+
+static int gset_decode_next_bit(gset_decoder *decoder)
+{
+    if (++decoder->bit >= 8) {
+        if (++decoder->offset >= decoder->datalen) {
+            return -1;
+        }
+        decoder->bit = 0;
     }
-    return NULL;
+    return (decoder->data[decoder->offset] & cbit_mask[decoder->bit])? 1 : 0;
+}
+
+static apr_status_t gset_decode_next(gset_decoder *decoder, apr_uint64_t *phash)
+{
+    apr_uint64_t flex = 0, fixed = 0, delta;
+    int i;
+    
+    /* read 1 bits until we encounter 0, then read log2n(diary-P) bits.
+     * On a malformed bit-string, this will not fail, but produce results
+     * which are pbly too large. Luckily, the diary will modulo the hash.
+     */
+    while (1) {
+        int bit = gset_decode_next_bit(decoder);
+        if (bit == -1) {
+            return APR_EINVAL;
+        }
+        if (!bit) {
+            break;
+        }
+        ++flex;
+    }
+    
+    for (i = 0; i < decoder->log2p; ++i) {
+        int bit = gset_decode_next_bit(decoder);
+        if (bit == -1) {
+            return APR_EINVAL;
+        }
+        fixed = (fixed << 1) | bit;
+    }
+    
+    delta = (flex << decoder->log2p) | fixed;
+    *phash = delta + decoder->last_val;
+    decoder->last_val = *phash;
+    
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, decoder->pool,
+                  "h2_push_diary_digest_dec: val=%"APR_UINT64_T_HEX_FMT", delta=%"
+                  APR_UINT64_T_HEX_FMT", flex=%d, fixed=%"APR_UINT64_T_HEX_FMT, 
+                  *phash, delta, (int)flex, fixed);
+                  
+    return APR_SUCCESS;
 }
+
+/**
+ * Initialize the push diary by a cache digest as described in 
+ * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ * .
+ * @param diary the diary to set the digest into
+ * @param data the binary cache digest
+ * @param len the length of the cache digest
+ * @return APR_EINVAL if digest was not successfully parsed
+ */
+apr_status_t h2_push_diary_digest_set(h2_push_diary *diary, const char *authority, 
+                                      const char *data, apr_size_t len)
+{
+    gset_decoder decoder;
+    unsigned char log2n, log2p;
+    apr_size_t N, i;
+    apr_pool_t *pool = diary->entries->pool;
+    h2_push_diary_entry e;
+    apr_status_t status = APR_SUCCESS;
+    
+    if (len < 2) {
+        /* at least this should be there */
+        return APR_EINVAL;
+    }
+    log2n = data[0];
+    log2p = data[1];
+    diary->mask_bits = log2n + log2p;
+    if (diary->mask_bits > 64) {
+        /* cannot handle */
+        return APR_ENOTIMPL;
+    }
+    
+    /* whatever is in the digest, it replaces the diary entries */
+    apr_array_clear(diary->entries);
+    if (!authority || !strcmp("*", authority)) {
+        diary->authority = NULL;
+    }
+    else if (!diary->authority || strcmp(diary->authority, authority)) {
+        diary->authority = apr_pstrdup(diary->entries->pool, authority);
+    }
+
+    N = h2_log2inv(log2n + log2p);
+
+    decoder.diary    = diary;
+    decoder.pool     = pool;
+    decoder.log2p    = log2p;
+    decoder.data     = (const unsigned char*)data;
+    decoder.datalen  = len;
+    decoder.offset   = 1;
+    decoder.bit      = 8;
+    decoder.last_val = 0;
+    
+    diary->N = N;
+    /* Determine effective N we use for storage */
+    if (!N) {
+        /* a totally empty cache digest. someone tells us that she has no
+         * entries in the cache at all. Use our own preferences for N+mask 
+         */
+        diary->N = diary->NMax;
+        return APR_SUCCESS;
+    }
+    else if (N > diary->NMax) {
+        /* Store not more than diary is configured to hold. We open us up
+         * to DOS attacks otherwise. */
+        diary->N = diary->NMax;
+    }
+    
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest_set: N=%d, log2n=%d, "
+                  "diary->mask_bits=%d, dec.log2p=%d", 
+                  (int)diary->N, (int)log2n, diary->mask_bits, 
+                  (int)decoder.log2p);
+                  
+    for (i = 0; i < diary->N; ++i) {
+        if (gset_decode_next(&decoder, &e.hash) != APR_SUCCESS) {
+            /* the data may have less than N values */
+            break;
+        }
+        h2_push_diary_append(diary, &e);
+    }
+    
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest_set: diary now with %d entries, mask_bits=%d", 
+                  (int)diary->entries->nelts, diary->mask_bits);
+    return status;
+}
+
+apr_status_t h2_push_diary_digest64_set(h2_push_diary *diary, const char *authority, 
+                                        const char *data64url, apr_pool_t *pool)
+{
+    const char *data;
+    apr_size_t len = h2_util_base64url_decode(&data, data64url, pool);
+    ap_log_perror(APLOG_MARK, GCSLOG_LEVEL, 0, pool,
+                  "h2_push_diary_digest64_set: digest=%s, dlen=%d", 
+                  data64url, (int)len);
+    return h2_push_diary_digest_set(diary, authority, data, len);
+}
+

Modified: httpd/httpd/branches/2.4.x/modules/http2/h2_push.h
URL: http://svn.apache.org/viewvc/httpd/httpd/branches/2.4.x/modules/http2/h2_push.h?rev=1725301&r1=1725300&r2=1725301&view=diff
==============================================================================
--- httpd/httpd/branches/2.4.x/modules/http2/h2_push.h (original)
+++ httpd/httpd/branches/2.4.x/modules/http2/h2_push.h Mon Jan 18 16:22:57 2016
@@ -18,14 +18,115 @@
 struct h2_request;
 struct h2_response;
 struct h2_ngheader;
+struct h2_session;
+struct h2_stream;
+
+typedef enum {
+    H2_PUSH_NONE,
+    H2_PUSH_DEFAULT,
+    H2_PUSH_HEAD,
+    H2_PUSH_FAST_LOAD,
+} h2_push_policy;
 
 typedef struct h2_push {
     const struct h2_request *req;
 } h2_push;
 
+typedef enum {
+    H2_PUSH_DIGEST_APR_HASH,
+    H2_PUSH_DIGEST_SHA256
+} h2_push_digest_type;
+
+typedef struct h2_push_diary h2_push_diary;
+
+typedef void h2_push_digest_calc(h2_push_diary *diary, apr_uint64_t *phash, h2_push *push);
 
+struct h2_push_diary {
+    apr_array_header_t  *entries;
+    apr_size_t           NMax; /* Maximum for N, should size change be necessary */
+    apr_size_t           N;    /* Current maximum number of entries, power of 2 */
+    apr_uint64_t         mask; /* mask for relevant bits */
+    unsigned int         mask_bits; /* number of relevant bits */
+    const char          *authority;
+    h2_push_digest_type  dtype;
+    h2_push_digest_calc *dcalc;
+};
+
+/**
+ * Determine the list of h2_push'es to send to the client on behalf of
+ * the given request/response pair.
+ *
+ * @param p the pool to use
+ * @param req the requst from the client
+ * @param res the response from the server
+ * @return array of h2_push addresses or NULL
+ */
 apr_array_header_t *h2_push_collect(apr_pool_t *p, 
                                     const struct h2_request *req, 
                                     const struct h2_response *res);
 
+/**
+ * Set the push policy for the given request. Takes request headers into 
+ * account, see draft https://tools.ietf.org/html/draft-ruellan-http-accept-push-policy-00
+ * for details.
+ * 
+ * @param req the request to determine the policy for
+ * @param p the pool to use
+ * @param push_enabled if HTTP/2 server push is generally enabled for this request
+ */
+void h2_push_policy_determine(struct h2_request *req, apr_pool_t *p, int push_enabled);
+
+/**
+ * Create a new push diary for the given maximum number of entries.
+ * 
+ * @oaram p the pool to use
+ * @param N the max number of entries, rounded up to 2^x
+ * @return the created diary, might be NULL of max_entries is 0
+ */
+h2_push_diary *h2_push_diary_create(apr_pool_t *p, apr_size_t N);
+
+/**
+ * Filters the given pushes against the diary and returns only those pushes
+ * that were newly entered in the diary.
+ */
+apr_array_header_t *h2_push_diary_update(struct h2_session *session, apr_array_header_t *pushes);
+
+/**
+ * Collect pushes for the given request/response pair, enter them into the
+ * diary and return those pushes newly entered.
+ */
+apr_array_header_t *h2_push_collect_update(struct h2_stream *stream, 
+                                           const struct h2_request *req, 
+                                           const struct h2_response *res);
+/**
+ * Get a cache digest as described in 
+ * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ * from the contents of the push diary.
+ * 
+ * @param diary the diary to calculdate the digest from
+ * @param p the pool to use
+ * @param authority the authority to get the data for, use NULL/"*" for all
+ * @param pdata on successful return, the binary cache digest
+ * @param plen on successful return, the length of the binary data
+ */
+apr_status_t h2_push_diary_digest_get(h2_push_diary *diary, apr_pool_t *p, 
+                                      apr_uint32_t maxP, const char *authority, 
+                                      const char **pdata, apr_size_t *plen);
+
+/**
+ * Initialize the push diary by a cache digest as described in 
+ * https://datatracker.ietf.org/doc/draft-kazuho-h2-cache-digest/
+ * .
+ * @param diary the diary to set the digest into
+ * @param authority the authority to set the data for
+ * @param data the binary cache digest
+ * @param len the length of the cache digest
+ * @return APR_EINVAL if digest was not successfully parsed
+ */
+apr_status_t h2_push_diary_digest_set(h2_push_diary *diary, const char *authority, 
+                                      const char *data, apr_size_t len);
+
+apr_status_t h2_push_diary_digest64_set(h2_push_diary *diary, const char *authority, 
+                                        const char *data64url, apr_pool_t *pool);
+
 #endif /* defined(__mod_h2__h2_push__) */

Modified: httpd/httpd/branches/2.4.x/modules/http2/h2_request.c
URL: http://svn.apache.org/viewvc/httpd/httpd/branches/2.4.x/modules/http2/h2_request.c?rev=1725301&r1=1725300&r2=1725301&view=diff
==============================================================================
--- httpd/httpd/branches/2.4.x/modules/http2/h2_request.c (original)
+++ httpd/httpd/branches/2.4.x/modules/http2/h2_request.c Mon Jan 18 16:22:57 2016
@@ -32,6 +32,7 @@
 #include "h2_private.h"
 #include "h2_config.h"
 #include "h2_mplx.h"
+#include "h2_push.h"
 #include "h2_request.h"
 #include "h2_task.h"
 #include "h2_util.h"
@@ -227,7 +228,8 @@ apr_status_t h2_request_add_header(h2_re
     return status;
 }
 
-apr_status_t h2_request_end_headers(h2_request *req, apr_pool_t *pool, int eos)
+apr_status_t h2_request_end_headers(h2_request *req, apr_pool_t *pool, 
+                                    int eos, int push)
 {
     const char *s;
     
@@ -271,6 +273,7 @@ apr_status_t h2_request_end_headers(h2_r
     }
 
     req->eoh = 1;
+    h2_push_policy_determine(req, pool, push);
     
     /* In the presence of trailers, force behaviour of chunked encoding */
     s = apr_table_get(req->headers, "Trailer");

Modified: httpd/httpd/branches/2.4.x/modules/http2/h2_request.h
URL: http://svn.apache.org/viewvc/httpd/httpd/branches/2.4.x/modules/http2/h2_request.h?rev=1725301&r1=1725300&r2=1725301&view=diff
==============================================================================
--- httpd/httpd/branches/2.4.x/modules/http2/h2_request.h (original)
+++ httpd/httpd/branches/2.4.x/modules/http2/h2_request.h Mon Jan 18 16:22:57 2016
@@ -28,10 +28,9 @@ struct h2_task;
 typedef struct h2_request h2_request;
 
 struct h2_request {
-    int id;                 /* stream id */
+    int id;             /* stream id */
 
-    /* pseudo header values, see ch. 8.1.2.3 */
-    const char *method;
+    const char *method; /* pseudo header values, see ch. 8.1.2.3 */
     const char *scheme;
     const char *authority;
     const char *path;
@@ -41,9 +40,11 @@ struct h2_request {
 
     apr_time_t request_time;
     apr_off_t content_length;
-    int chunked;
-    int eoh;
     
+    unsigned int chunked : 1; /* iff requst body needs to be forwarded as chunked */
+    unsigned int eoh     : 1; /* iff end-of-headers has been seen and request is complete */
+    unsigned int body    : 1; /* iff this request has a body */
+    unsigned int push_policy; /* which push policy to use for this request */
     const struct h2_config *config;
 };
 
@@ -68,7 +69,8 @@ apr_status_t h2_request_add_trailer(h2_r
                                     const char *name, size_t nlen,
                                     const char *value, size_t vlen);
 
-apr_status_t h2_request_end_headers(h2_request *req, apr_pool_t *pool, int eos);
+apr_status_t h2_request_end_headers(h2_request *req, apr_pool_t *pool, 
+                                    int eos, int push);
 
 void h2_request_copy(apr_pool_t *p, h2_request *dst, const h2_request *src);
 

Modified: httpd/httpd/branches/2.4.x/modules/http2/h2_response.c
URL: http://svn.apache.org/viewvc/httpd/httpd/branches/2.4.x/modules/http2/h2_response.c?rev=1725301&r1=1725300&r2=1725301&view=diff
==============================================================================
--- httpd/httpd/branches/2.4.x/modules/http2/h2_response.c (original)
+++ httpd/httpd/branches/2.4.x/modules/http2/h2_response.c Mon Jan 18 16:22:57 2016
@@ -26,6 +26,7 @@
 #include <nghttp2/nghttp2.h>
 
 #include "h2_private.h"
+#include "h2_filter.h"
 #include "h2_h2.h"
 #include "h2_util.h"
 #include "h2_request.h"
@@ -64,10 +65,16 @@ static apr_table_t *parse_headers(apr_ar
     }
 }
 
+static const char *get_sos_filter(apr_table_t *notes) 
+{
+    return notes? apr_table_get(notes, H2_RESP_SOS_NOTE) : NULL;
+}
+
 static h2_response *h2_response_create_int(int stream_id,
                                            int rst_error,
                                            int http_status,
                                            apr_table_t *headers,
+                                           apr_table_t *notes,
                                            apr_pool_t *pool)
 {
     h2_response *response;
@@ -82,11 +89,12 @@ static h2_response *h2_response_create_i
         return NULL;
     }
     
-    response->stream_id = stream_id;
-    response->rst_error = rst_error;
-    response->http_status = http_status? http_status : 500;
+    response->stream_id      = stream_id;
+    response->rst_error      = rst_error;
+    response->http_status    = http_status? http_status : 500;
     response->content_length = -1;
-    response->headers = headers;
+    response->headers        = headers;
+    response->sos_filter     = get_sos_filter(notes);
     
     s = apr_table_get(headers, "Content-Length");
     if (s) {
@@ -109,10 +117,11 @@ h2_response *h2_response_create(int stre
                                 int rst_error,
                                 int http_status,
                                 apr_array_header_t *hlines,
+                                apr_table_t *notes,
                                 apr_pool_t *pool)
 {
     return h2_response_create_int(stream_id, rst_error, http_status,
-                                  parse_headers(hlines, pool), pool);
+                                  parse_headers(hlines, pool), notes, pool);
 }
 
 h2_response *h2_response_rcreate(int stream_id, request_rec *r,
@@ -123,10 +132,11 @@ h2_response *h2_response_rcreate(int str
         return NULL;
     }
     
-    response->stream_id = stream_id;
-    response->http_status = r->status;
+    response->stream_id      = stream_id;
+    response->http_status    = r->status;
     response->content_length = -1;
-    response->headers = header;
+    response->headers        = header;
+    response->sos_filter     = get_sos_filter(r->notes);
 
     if (response->http_status == HTTP_FORBIDDEN) {
         const char *cause = apr_table_get(r->notes, "ssl-renegotiate-forbidden");
@@ -155,20 +165,22 @@ h2_response *h2_response_die(int stream_
     apr_table_setn(headers, "Date", date);
     apr_table_setn(headers, "Server", ap_get_server_banner());
     
-    return h2_response_create_int(stream_id, 0, 500, headers, pool);
+    return h2_response_create_int(stream_id, 0, 500, headers, NULL, pool);
 }
 
 h2_response *h2_response_clone(apr_pool_t *pool, h2_response *from)
 {
     h2_response *to = apr_pcalloc(pool, sizeof(h2_response));
-    to->stream_id = from->stream_id;
-    to->http_status = from->http_status;
+    
+    to->stream_id      = from->stream_id;
+    to->http_status    = from->http_status;
     to->content_length = from->content_length;
+    to->sos_filter     = from->sos_filter;
     if (from->headers) {
-        to->headers = apr_table_clone(pool, from->headers);
+        to->headers    = apr_table_clone(pool, from->headers);
     }
     if (from->trailers) {
-        to->trailers = apr_table_clone(pool, from->trailers);
+        to->trailers   = apr_table_clone(pool, from->trailers);
     }
     return to;
 }

Modified: httpd/httpd/branches/2.4.x/modules/http2/h2_response.h
URL: http://svn.apache.org/viewvc/httpd/httpd/branches/2.4.x/modules/http2/h2_response.h?rev=1725301&r1=1725300&r2=1725301&view=diff
==============================================================================
--- httpd/httpd/branches/2.4.x/modules/http2/h2_response.h (original)
+++ httpd/httpd/branches/2.4.x/modules/http2/h2_response.h Mon Jan 18 16:22:57 2016
@@ -20,12 +20,13 @@ struct h2_request;
 struct h2_push;
 
 typedef struct h2_response {
-    int stream_id;
-    int rst_error;
-    int http_status;
-    apr_off_t content_length;
+    int         stream_id;
+    int         rst_error;
+    int         http_status;
+    apr_off_t   content_length;
     apr_table_t *headers;
     apr_table_t *trailers;
+    const char  *sos_filter;
 } h2_response;
 
 /**
@@ -40,6 +41,7 @@ h2_response *h2_response_create(int stre
                                 int rst_error,
                                 int http_status,
                                 apr_array_header_t *hlines,
+                                apr_table_t *notes,
                                 apr_pool_t *pool);
 
 /**