You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@httpd.apache.org by ic...@apache.org on 2016/01/12 12:20:54 UTC
svn commit: r1724206 - in /httpd/httpd/trunk/modules/http2: h2_config.c
h2_push.c h2_push.h h2_session.c
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;