httpd-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ic...@apache.org
Subject svn commit: r1724206 - in /httpd/httpd/trunk/modules/http2: h2_config.c h2_push.c h2_push.h h2_session.c
Date Tue, 12 Jan 2016 11:20:54 GMT
Author: icing
Date: Tue Jan 12 11:20:54 2016
New Revision: 1724206

URL: http://svn.apache.org/viewvc?rev=1724206&view=rev
Log:
push diary work, introduction of N/P for cache digest handling

Modified:
    httpd/httpd/trunk/modules/http2/h2_config.c
    httpd/httpd/trunk/modules/http2/h2_push.c
    httpd/httpd/trunk/modules/http2/h2_push.h
    httpd/httpd/trunk/modules/http2/h2_session.c

Modified: httpd/httpd/trunk/modules/http2/h2_config.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/modules/http2/h2_config.c?rev=1724206&r1=1724205&r2=1724206&view=diff
==============================================================================
--- httpd/httpd/trunk/modules/http2/h2_config.c (original)
+++ httpd/httpd/trunk/modules/http2/h2_config.c Tue Jan 12 11:20:54 2016
@@ -541,6 +541,12 @@ static const char *h2_conf_set_push_diar
     if (cfg->push_diary_size < 0) {
         return "value must be >= 0";
     }
+    if (cfg->push_diary_size > 0 && (cfg->push_diary_size & (cfg->push_diary_size-1)))
{
+        return "value must a power of 2";
+    }
+    if (cfg->push_diary_size > (1 << 15)) {
+        return "value must <= 65536";
+    }
     return NULL;
 }
 

Modified: httpd/httpd/trunk/modules/http2/h2_push.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/modules/http2/h2_push.c?rev=1724206&r1=1724205&r2=1724206&view=diff
==============================================================================
--- httpd/httpd/trunk/modules/http2/h2_push.c (original)
+++ httpd/httpd/trunk/modules/http2/h2_push.c Tue Jan 12 11:20:54 2016
@@ -34,6 +34,10 @@
 #include "h2_session.h"
 #include "h2_stream.h"
 
+/*******************************************************************************
+ * link header handling 
+ ******************************************************************************/
+
 static const char *policy_str(h2_push_policy policy)
 {
     switch (policy) {
@@ -456,13 +460,28 @@ void h2_push_policy_determine(struct h2_
     req->push_policy = policy;
 }
 
-static unsigned int val_apr_hash(const char *str) 
+/*******************************************************************************
+ * push diary 
+ ******************************************************************************/
+ 
+struct h2_push_digest {
+    union {
+        uint32_t hash;
+    } val;
+};
+
+typedef struct h2_push_diary_entry {
+    h2_push_digest digest;
+} h2_push_diary_entry;
+
+
+static uint32_t 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_digest *d, h2_push *push) 
+static void calc_apr_hash(h2_push_diary *diary, h2_push_digest *d, h2_push *push) 
 {
     unsigned int val;
     
@@ -470,69 +489,85 @@ static void calc_apr_hash(h2_push_digest
     val ^= val_apr_hash(push->req->authority);
     val ^= val_apr_hash(push->req->path);
     
-    d->val.apr_hash = val;
+    d->val.hash = val % (diary->N * diary->P);
+}
+
+static int cmp_hash(h2_push_digest *d1, h2_push_digest *d2) 
+{
+    return (d1->val.hash > d2->val.hash)? 1 : ((d1->val.hash == d2->val.hash)?
0 : -1);
 }
 
-static int cmp_apr_hash(h2_push_digest *d1, h2_push_digest *d2) 
+static uint32_t ceil_power_of_2(uint32_t n)
 {
-    return d1->val.apr_hash - d2->val.apr_hash;
+    --n;
+    n |= n >> 1;
+    n |= n >> 2;
+    n |= n >> 4;
+    n |= n >> 8;
+    n |= n >> 16;
+    return ++n;
 }
 
-h2_push_diary *h2_push_diary_create(apr_pool_t *p, apr_size_t max_entries)
+h2_push_diary *h2_push_diary_create(apr_pool_t *p, uint32_t N, uint32_t P)
 {
     h2_push_diary *diary = NULL;
     
-    if (max_entries > 0) {
+    if (N > 0) {
         diary = apr_pcalloc(p, sizeof(*diary));
         
-        diary->entries     = apr_array_make(p, 10, sizeof(h2_push_diary_entry*));
-        diary->max_entries = max_entries;
+        diary->N           = ceil_power_of_2(N);
+        diary->P           = ceil_power_of_2(P? P : ((1<<31)/diary->N));
+        diary->entries     = apr_array_make(p, 16, sizeof(void*));
         diary->dtype       = H2_PUSH_DIGEST_APR_HASH;
         diary->dcalc       = calc_apr_hash;
-        diary->dcmp        = cmp_apr_hash;
+        diary->dcmp        = cmp_hash;
     }
     
     return diary;
 }
 
-static h2_push_diary_entry *h2_push_diary_find(h2_push_diary *diary, h2_push_digest *d)
+static int h2_push_diary_find(h2_push_diary *diary, h2_push_digest *d)
 {
     if (diary) {
         h2_push_diary_entry *e;
         int i;
-
-        for (i = 0; i < diary->entries->nelts; ++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 (!diary->dcmp(&e->digest, d)) {
-                return e;
+                return i;
             }
         }
     }
-    return NULL;
+    return -1;
 }
 
-static h2_push_diary_entry *h2_push_diary_insert(h2_push_diary *diary, h2_push_digest *d)
+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 = entries[idx];
+    /* move entry[idx] to the end */
+    if (idx < (diary->entries->nelts-1)) {
+        memmove(entries+idx, entries+idx+1, sizeof(h2_push_diary_entry *) * diary->entries->nelts-idx-1);
+        entries[diary->entries->nelts-1] = e;
+    }
+    return e;
+}
+
+static h2_push_diary_entry *h2_push_diary_append(h2_push_diary *diary, h2_push_digest *digest)
 {
     h2_push_diary_entry *e;
-    int i;
     
-    if (diary->entries->nelts < diary->max_entries) {
+    if (diary->entries->nelts < diary->N) {
+        /* append a new diary entry at the end */
         e = apr_pcalloc(diary->entries->pool, sizeof(*e));
         APR_ARRAY_PUSH(diary->entries, h2_push_diary_entry*) = e;
     }
-    else {        
-        h2_push_diary_entry *oldest = NULL;
-        for (i = 0; i < diary->entries->nelts; ++i) {
-            e = APR_ARRAY_IDX(diary->entries, i, h2_push_diary_entry*);
-            if (!oldest || oldest->last_accessed > e->last_accessed) {
-                oldest = e;
-            }
-        }
-        e = oldest;
+    else {
+        e = move_to_last(diary, 0);
     }
-    
-    memcpy(&e->digest, d, sizeof(*d));
-    e->last_accessed = apr_time_now();
+    /* replace content with new digest. keeps memory usage constant once diary is full */
+    memcpy(&e->digest, digest, sizeof(*digest));
     return e;
 }
 
@@ -540,8 +575,7 @@ apr_array_header_t *h2_push_diary_update
 {
     apr_array_header_t *npushes = pushes;
     h2_push_digest d;
-    h2_push_diary_entry *e;
-    int i;
+    int i, idx;
     
     if (session->push_diary && pushes) {
         npushes = NULL;
@@ -550,12 +584,12 @@ apr_array_header_t *h2_push_diary_update
             h2_push *push;
             
             push = APR_ARRAY_IDX(pushes, i, h2_push*);
-            session->push_diary->dcalc(&d, push);
-            e = h2_push_diary_find(session->push_diary, &d);
-            if (e) {
+            session->push_diary->dcalc(session->push_diary, &d, push);
+            idx = h2_push_diary_find(session->push_diary, &d);
+            if (idx >= 0) {
                 ap_log_cerror(APLOG_MARK, APLOG_TRACE2, 0, session->c,
                               "push_diary_update: already there PUSH %s", push->req->path);
-                e->last_accessed = apr_time_now();
+                move_to_last(session->push_diary, idx);
             }
             else {
                 ap_log_cerror(APLOG_MARK, APLOG_TRACE2, 0, session->c,
@@ -564,7 +598,7 @@ apr_array_header_t *h2_push_diary_update
                     npushes = apr_array_make(pushes->pool, 5, sizeof(h2_push_diary_entry*));
                 }
                 APR_ARRAY_PUSH(npushes, h2_push*) = push;
-                h2_push_diary_insert(session->push_diary, &d);
+                h2_push_diary_append(session->push_diary, &d);
             }
         }
     }

Modified: httpd/httpd/trunk/modules/http2/h2_push.h
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/modules/http2/h2_push.h?rev=1724206&r1=1724205&r2=1724206&view=diff
==============================================================================
--- httpd/httpd/trunk/modules/http2/h2_push.h (original)
+++ httpd/httpd/trunk/modules/http2/h2_push.h Tue Jan 12 11:20:54 2016
@@ -35,31 +35,22 @@ typedef struct h2_push {
 typedef enum {
     H2_PUSH_DIGEST_APR_HASH,
     H2_PUSH_DIGEST_SHA256
-} h2_push_digest_t;
+} h2_push_digest_type;
 
-typedef struct h2_push_digest {
-    union {
-        unsigned int apr_hash;
-        unsigned char sha256[32];
-    } val;
-} h2_push_digest;
+typedef struct h2_push_digest h2_push_digest;
+typedef struct h2_push_diary h2_push_diary;
 
-typedef void h2_push_digest_calc(h2_push_digest *d, h2_push *push);
+typedef void h2_push_digest_calc(h2_push_diary *diary, h2_push_digest *d, h2_push *push);
 typedef int h2_push_digest_cmp(h2_push_digest *d1, h2_push_digest *d2);
 
-typedef struct h2_push_diary_entry {
-    h2_push_digest digest;
-    apr_time_t last_accessed;
-} h2_push_diary_entry;
-
-
-typedef struct h2_push_diary {
+struct h2_push_diary {
     apr_array_header_t  *entries;
-    apr_size_t           max_entries;
-    h2_push_digest_t     dtype;
+    uint32_t             N;   /* Max + of entries, power of 2 */
+    uint32_t             P;   /* Probability 1/P of false positive, power of 2 */
+    h2_push_digest_type  dtype;
     h2_push_digest_calc *dcalc;
     h2_push_digest_cmp  *dcmp;
-} h2_push_diary;
+};
 
 /**
  * Determine the list of h2_push'es to send to the client on behalf of
@@ -89,10 +80,12 @@ void h2_push_policy_determine(struct h2_
  * Create a new push diary for the given maximum number of entries.
  * 
  * @oaram p the pool to use
- * @param max_entries the maximum number of entries the diary should hold
+ * @param N the max number of entries, rounded up to 2^x
+ * @param P false positives with 1/P probability, rounded up to 2^x, if 0
+ *          diary will itself choose the best value
  * @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 max_entries);
+h2_push_diary *h2_push_diary_create(apr_pool_t *p, uint32_t N, uint32_t P);
 
 /**
  * Filters the given pushes against the diary and returns only those pushes

Modified: httpd/httpd/trunk/modules/http2/h2_session.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/modules/http2/h2_session.c?rev=1724206&r1=1724205&r2=1724206&view=diff
==============================================================================
--- httpd/httpd/trunk/modules/http2/h2_session.c (original)
+++ httpd/httpd/trunk/modules/http2/h2_session.c Tue Jan 12 11:20:54 2016
@@ -781,7 +781,7 @@ static h2_session *h2_session_create_int
 {
     nghttp2_session_callbacks *callbacks = NULL;
     nghttp2_option *options = NULL;
-    apr_size_t diary_size;
+    uint32_t n;
 
     apr_pool_t *pool = NULL;
     apr_status_t status = apr_pool_create(&pool, c->pool);
@@ -884,16 +884,16 @@ static h2_session *h2_session_create_int
             return NULL;
         }
          
-        diary_size = h2_config_geti(session->config, H2_CONF_PUSH_DIARY_SIZE);
-        session->push_diary = h2_push_diary_create(session->pool, diary_size);
+        n = h2_config_geti(session->config, H2_CONF_PUSH_DIARY_SIZE);
+        session->push_diary = h2_push_diary_create(session->pool, n, 0);
         
         if (APLOGcdebug(c)) {
             ap_log_cerror(APLOG_MARK, APLOG_DEBUG, 0, c,
                           "session(%ld) created, timeout=%d, keepalive_timeout=%d, "
-                          "max_streams=%d, stream_mem=%d, push_diary_size=%d",
+                          "max_streams=%d, stream_mem=%d, push_diary(N=%d,P=%d)",
                           session->id, session->timeout_secs, session->keepalive_secs,
                           (int)session->max_stream_count, (int)session->max_stream_mem,
-                          (int)diary_size);
+                          (int)session->push_diary->N, (int)session->push_diary->P);
         }
     }
     return session;



Mime
View raw message