Mailing List Archive

Author: phk
Date: 2007-08-06 11:25:20 +0200 (Mon, 06 Aug 2007)
New Revision: 1805

Modified:
trunk/varnish-cache/bin/varnishd/cache.h
trunk/varnish-cache/bin/varnishd/cache_center.c
trunk/varnish-cache/bin/varnishd/cache_hash.c
trunk/varnish-cache/bin/varnishd/cache_vrt.c
trunk/varnish-cache/bin/varnishd/hash_classic.c
trunk/varnish-cache/bin/varnishd/hash_simple_list.c
trunk/varnish-cache/bin/varnishd/hash_slinger.h
Log:
Rewrite the req.hash implmentation:

Instead of assembling the entire hash-string in the workspace, use
a scatter gather approach, hinted by the VCL compiler.

This eliminates the workspace reservation which prevented regsub() from
working in vcl_hash, and reduces the size of the necessary workspace a
fair bit as well, at the cost of a little bit of complexity in the
hash implmentations.

Closes ticket 137 and possibly 141



Modified: trunk/varnish-cache/bin/varnishd/cache.h
===================================================================
--- trunk/varnish-cache/bin/varnishd/cache.h 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/cache.h 2007-08-06 09:25:20 UTC (rev 1805)
@@ -315,8 +315,11 @@
struct workreq workreq;
struct acct acct;

- char *hash_b; /* Start of hash string */
- char *hash_e; /* End of hash string */
+ /* pointers to hash string components */
+ unsigned nhashptr;
+ unsigned ihashptr;
+ unsigned lhashptr;
+ const char **hashptr;
};

struct backend {
@@ -390,6 +393,8 @@

/* cache_hash.c */
void HSH_Prealloc(struct sess *sp);
+int HSH_Compare(struct sess *sp, const char *b, const char *e);
+void HSH_Copy(struct sess *sp, char *b, const char *e);
struct object *HSH_Lookup(struct sess *sp);
void HSH_Unbusy(struct object *o);
void HSH_Ref(struct object *o);

Modified: trunk/varnish-cache/bin/varnishd/cache_center.c
===================================================================
--- trunk/varnish-cache/bin/varnishd/cache_center.c 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/cache_center.c 2007-08-06 09:25:20 UTC (rev 1805)
@@ -469,15 +469,26 @@
cnt_lookup(struct sess *sp)
{
struct object *o;
+ char *p;
+ uintptr_t u;

CHECK_OBJ_NOTNULL(sp, SESS_MAGIC);

if (sp->obj == NULL) {
- WS_Reserve(sp->http->ws, 0);
- sp->hash_b = sp->http->ws->f;
- sp->hash_e = sp->hash_b;
+
+ /* Allocate the pointers we need, align properly. */
+ sp->lhashptr = 1; /* space for NUL */
+ sp->ihashptr = 0;
+ sp->nhashptr = sp->vcl->nhashcount * 2;
+ p = WS_Alloc(sp->http->ws,
+ sizeof(const char *) * (sp->nhashptr + 1));
+ u = (uintptr_t)p;
+ u &= sizeof(const char *) - 1;
+ if (u)
+ p += sizeof(const char *) - u;
+ sp->hashptr = (void*)p;
+
VCL_hash_method(sp); /* XXX: no-op for now */
- WS_ReleaseP(sp->http->ws, sp->hash_e);
/* XXX check error */
}

@@ -494,9 +505,6 @@
return (1);
}

- WS_Return(sp->http->ws, sp->hash_b, sp->hash_e);
- sp->hash_b = sp->hash_e = NULL;
-
sp->obj = o;

/* If we inserted a new object it's a miss */

Modified: trunk/varnish-cache/bin/varnishd/cache_hash.c
===================================================================
--- trunk/varnish-cache/bin/varnishd/cache_hash.c 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/cache_hash.c 2007-08-06 09:25:20 UTC (rev 1805)
@@ -109,6 +109,47 @@
}
}

+int
+HSH_Compare(struct sess *sp, const char *b, const char *e)
+{
+ int i;
+ unsigned u, v;
+
+ i = sp->lhashptr - (e - b);
+ if (i)
+ return (i);
+ for (u = 0; u < sp->ihashptr; u += 2) {
+ v = sp->hashptr[u + 1] - sp->hashptr[u];
+ i = memcmp(sp->hashptr[u], b, v);
+ if (i)
+ return (i);
+ b += v;
+ i = '#' - *b++;
+ if (i)
+ return (i);
+ }
+ assert(*b == '\0');
+ b++;
+ assert(b == e);
+ return (0);
+}
+
+void
+HSH_Copy(struct sess *sp, char *b, const char *e)
+{
+ unsigned u, v;
+
+ assert((e - b) >= sp->lhashptr);
+ for (u = 0; u < sp->ihashptr; u += 2) {
+ v = sp->hashptr[u + 1] - sp->hashptr[u];
+ memcpy(b, sp->hashptr[u], v);
+ b += v;
+ *b++ = '#';
+ }
+ *b++ = '\0';
+ assert(b <= e);
+}
+
struct object *
HSH_Lookup(struct sess *sp)
{
@@ -133,9 +174,8 @@
LOCK(&oh->mtx);
goto were_back;
}
-VSLR(SLT_Debug, sp->fd, sp->hash_b, sp->hash_e);

- oh = hash->lookup(sp->hash_b, sp->hash_e, w->nobjhead);
+ oh = hash->lookup(sp, w->nobjhead);
CHECK_OBJ_NOTNULL(oh, OBJHEAD_MAGIC);
if (oh == w->nobjhead)
w->nobjhead = NULL;

Modified: trunk/varnish-cache/bin/varnishd/cache_vrt.c
===================================================================
--- trunk/varnish-cache/bin/varnishd/cache_vrt.c 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/cache_vrt.c 2007-08-06 09:25:20 UTC (rev 1805)
@@ -456,7 +456,9 @@
return (sp->mysockaddr);
}

-/*--------------------------------------------------------------------*/
+/*--------------------------------------------------------------------
+ * Add an element to the array/list of hash bits.
+ */

void
VRT_l_req_hash(struct sess *sp, const char *str)
@@ -466,10 +468,18 @@
if (str == NULL)
str = "";
l = strlen(str);
- xxxassert (sp->hash_e + l + 1 <= sp->http->ws->e);
- memcpy(sp->hash_e, str, l);
- sp->hash_e[l] = '#';
- sp->hash_e += l + 1;
+
+ /*
+ * XXX: handle this by bouncing sp->vcl->nhashcount when it fails
+ * XXX: and dispose of this request either by reallocating the
+ * XXX: hashptr (if possible) or restarting/error the request
+ */
+ xxxassert(sp->ihashptr < sp->nhashptr);
+
+ sp->hashptr[sp->ihashptr] = str;
+ sp->hashptr[sp->ihashptr + 1] = str + l;
+ sp->ihashptr += 2;
+ sp->lhashptr += l + 1;
}

/*--------------------------------------------------------------------*/

Modified: trunk/varnish-cache/bin/varnishd/hash_classic.c
===================================================================
--- trunk/varnish-cache/bin/varnishd/hash_classic.c 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/hash_classic.c 2007-08-06 09:25:20 UTC (rev 1805)
@@ -121,36 +121,44 @@
*/

static struct objhead *
-hcl_lookup(const char *b, const char *e, struct objhead *noh)
+hcl_lookup(struct sess *sp, struct objhead *noh)
{
struct hcl_entry *he, *he2;
struct hcl_hd *hp;
- unsigned u1, digest, kl, r;
+ unsigned u1, digest, r;
+ unsigned u, v;
int i;

CHECK_OBJ_NOTNULL(noh, OBJHEAD_MAGIC);

- digest = crc32_l(b, e - b);
+ digest = ~0U;
+ for (u = 0; u < sp->ihashptr; u += 2) {
+ v = sp->hashptr[u + 1] - sp->hashptr[u];
+ digest = crc32(digest, sp->hashptr[u], v);
+ }
+ digest ^= ~0U;

u1 = digest % hcl_nhash;
hp = &hcl_head[u1];
- kl = e - b;
he2 = NULL;

for (r = 0; r < 2; r++ ) {
LOCK(&hp->mtx);
TAILQ_FOREACH(he, &hp->head, list) {
CHECK_OBJ_NOTNULL(he, HCL_ENTRY_MAGIC);
- if (kl < he->klen)
+ if (sp->lhashptr < he->klen)
continue;
- if (kl > he->klen)
+ if (sp->lhashptr > he->klen)
break;
if (he->digest < digest)
continue;
if (he->digest > digest)
break;
- if (memcmp(he->key, b, kl))
+ i = HSH_Compare(sp, he->key, he->key + he->klen);
+ if (i < 0)
continue;
+ if (i > 0)
+ break;
he->refcnt++;
noh = he->oh;
UNLOCK(&hp->mtx);
@@ -174,7 +182,7 @@
}
UNLOCK(&hp->mtx);

- i = sizeof *he2 + kl;
+ i = sizeof *he2 + sp->lhashptr;
he2 = calloc(i, 1);
XXXAN(he2);
he2->magic = HCL_ENTRY_MAGIC;
@@ -182,11 +190,11 @@
he2->digest = digest;
he2->hash = u1;
he2->head = hp;
- he2->klen = kl;
+ he2->klen = sp->lhashptr;
noh->hashpriv = he2;

he2->key = (void*)(he2 + 1);
- memcpy(he2->key, b, kl);
+ HSH_Copy(sp, he2->key, he2->key + sp->lhashptr);
}
assert(he2 == NULL); /* FlexeLint */
INCOMPL();

Modified: trunk/varnish-cache/bin/varnishd/hash_simple_list.c
===================================================================
--- trunk/varnish-cache/bin/varnishd/hash_simple_list.c 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/hash_simple_list.c 2007-08-06 09:25:20 UTC (rev 1805)
@@ -73,26 +73,20 @@
*/

static struct objhead *
-hsl_lookup(const char *b, const char *e, struct objhead *nobj)
+hsl_lookup(struct sess *sp, struct objhead *nobj)
{
struct hsl_entry *he, *he2;
- int i, l;
+ int i;

- l = e - b;
LOCK(&hsl_mutex);
TAILQ_FOREACH(he, &hsl_head, list) {
- if (l > he->keylen)
- continue;
- if (l < he->keylen)
- break;;
- i = memcmp(b, he->key, l);
+ i = HSH_Compare(sp, he->key, he->key + he->keylen);
if (i < 0)
continue;
if (i > 0)
break;
he->refcnt++;
nobj = he->obj;
- nobj->hashpriv = he;
UNLOCK(&hsl_mutex);
return (nobj);
}
@@ -100,13 +94,13 @@
UNLOCK(&hsl_mutex);
return (NULL);
}
- he2 = calloc(sizeof *he2 + l, 1);
+ he2 = calloc(sizeof *he2 + sp->lhashptr, 1);
XXXAN(he2);
he2->obj = nobj;
he2->refcnt = 1;
he2->key = (void*)(he2 + 1);
- he2->keylen = l;
- memcpy(he2->key, b, l);
+ he2->keylen = sp->lhashptr;
+ HSH_Copy(sp, he2->key, he2->key + he2->keylen);
nobj->hashpriv = he2;
if (he != NULL)
TAILQ_INSERT_BEFORE(he, he2, list);

Modified: trunk/varnish-cache/bin/varnishd/hash_slinger.h
===================================================================
--- trunk/varnish-cache/bin/varnishd/hash_slinger.h 2007-08-06 09:19:20 UTC (rev 1804)
+++ trunk/varnish-cache/bin/varnishd/hash_slinger.h 2007-08-06 09:25:20 UTC (rev 1805)
@@ -29,9 +29,11 @@
* $Id$
*/

+struct sess;
+
typedef int hash_init_f(const char *);
typedef void hash_start_f(void);
-typedef struct objhead *hash_lookup_f(const char *key1, const char *key2, struct objhead *nobj);
+typedef struct objhead *hash_lookup_f(struct sess *sp, struct objhead *nobj);
typedef int hash_deref_f(struct objhead *obj);

struct hash_slinger {