From 9b2bc4e9055fec4980c7b4b2ce7b16fb316cb36c Mon Sep 17 00:00:00 2001 From: phk Date: Mon, 2 Mar 2009 11:22:24 +0000 Subject: [PATCH] Add a debug facility for substituting digests with hand-created digests with edge-bit conditions and run the critbit through them. git-svn-id: svn+ssh://projects.linpro.no/svn/varnish/trunk@3849 d4fa192b-c00b-0410-8231-f00ffab90ce4 --- varnish-cache/bin/varnishd/cache_hash.c | 79 +++++++++ varnish-cache/bin/varnishd/hash_critbit.c | 18 +- varnish-cache/bin/varnishd/mgt_param.c | 1 + .../bin/varnishtest/tests/c00023.vtc | 156 ++++++++++++++++++ 4 files changed, 242 insertions(+), 12 deletions(-) create mode 100644 varnish-cache/bin/varnishtest/tests/c00023.vtc diff --git a/varnish-cache/bin/varnishd/cache_hash.c b/varnish-cache/bin/varnishd/cache_hash.c index 5fce8464..96fd47a4 100644 --- a/varnish-cache/bin/varnishd/cache_hash.c +++ b/varnish-cache/bin/varnishd/cache_hash.c @@ -272,6 +272,83 @@ HSH_AddString(struct sess *sp, const char *str) sp->lhashptr += l + 1; } +/********************************************************************** + * This is a debugging hack to enable testing of boundary conditions + * in the hash algorithm. + * We trap the first 9 different digests and translate them to different + * digests with edge bit conditions + */ + +static struct hsh_magiclist { + unsigned char was[SHA256_LEN]; + unsigned char now[SHA256_LEN]; +} hsh_magiclist[] = { + { .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } }, + { .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01 } }, + { .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02 } }, + { .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x40 } }, + { .now = { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x80 } }, + { .now = { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } }, + { .now = { 0x02, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } }, + { .now = { 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } }, + { .now = { 0x40, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 } }, +}; + +#define HSH_NMAGIC (sizeof hsh_magiclist / sizeof hsh_magiclist[0]) + +static void +hsh_testmagic(void *result) +{ + int i, j; + static int nused; + + for (i = 0; i < nused; i++) + if (!memcmp(hsh_magiclist[i].was, result, SHA256_LEN)) + break; + if (i == nused && i < HSH_NMAGIC) + memcpy(hsh_magiclist[nused++].was, result, SHA256_LEN); + if (i == nused) + return; + fprintf(stderr, "HASHMAGIC: <"); + for (j = 0; j < SHA256_LEN; j++) + fprintf(stderr, "%02x", ((unsigned char*)result)[j]); + fprintf(stderr, "> -> <"); + memcpy(result, hsh_magiclist[i].now, SHA256_LEN); + for (j = 0; j < SHA256_LEN; j++) + fprintf(stderr, "%02x", ((unsigned char*)result)[j]); + fprintf(stderr, ">\n"); +} + +/**********************************************************************/ + + struct objcore * HSH_Lookup(struct sess *sp, struct objhead **poh) { @@ -289,6 +366,8 @@ HSH_Lookup(struct sess *sp, struct objhead **poh) HSH_Prealloc(sp); SHA256_Final(sp->wrk->nobjhead->digest, sp->wrk->sha256ctx); + if (params->diag_bitmap & 0x80000000) + hsh_testmagic(sp->wrk->nobjhead->digest); if (sp->objhead != NULL) { CHECK_OBJ_NOTNULL(sp->objhead, OBJHEAD_MAGIC); diff --git a/varnish-cache/bin/varnishd/hash_critbit.c b/varnish-cache/bin/varnishd/hash_critbit.c index 5b3f4fbe..9273e839 100644 --- a/varnish-cache/bin/varnishd/hash_critbit.c +++ b/varnish-cache/bin/varnishd/hash_critbit.c @@ -197,10 +197,8 @@ hcb_insert(struct hcb_root *root, struct objhead *oh, int has_lock) while(hcb_is_y(*p)) { y = hcb_l_y(*p); - if (y->ptr > DIGEST_LEN) - s = 0; - else - s = (oh->digest[y->ptr] & y->bitmask) != 0; + assert(y->ptr < DIGEST_LEN); + s = (oh->digest[y->ptr] & y->bitmask) != 0; assert(s < 2); root->cmps++; p = &y->leaf[s]; @@ -233,10 +231,8 @@ hcb_insert(struct hcb_root *root, struct objhead *oh, int has_lock) y = hcb_l_y(*p); if (y->critbit > y2->critbit) break; - if (y->ptr > DIGEST_LEN) - s = 0; - else - s = (oh->digest[y->ptr] & y->bitmask) != 0; + assert(y->ptr < DIGEST_LEN); + s = (oh->digest[y->ptr] & y->bitmask) != 0; assert(s < 2); root->cmps++; p = &y->leaf[s]; @@ -266,10 +262,8 @@ hcb_delete(struct hcb_root *r, struct objhead *oh) while(1) { assert(hcb_is_y(*p)); y = hcb_l_y(*p); - if (y->ptr > DIGEST_LEN) - s = 0; - else - s = (oh->digest[y->ptr] & y->bitmask) != 0; + assert(y->ptr < DIGEST_LEN); + s = (oh->digest[y->ptr] & y->bitmask) != 0; assert(s < 2); if (y->leaf[s] == hcb_r_node(oh)) { *p = y->leaf[1 - s]; diff --git a/varnish-cache/bin/varnishd/mgt_param.c b/varnish-cache/bin/varnishd/mgt_param.c index 0de756a0..1d44cd12 100644 --- a/varnish-cache/bin/varnishd/mgt_param.c +++ b/varnish-cache/bin/varnishd/mgt_param.c @@ -746,6 +746,7 @@ static const struct parspec input_parspec[] = { " 0x00008000 - panic to abort2().\n" #endif " 0x00010000 - synchronize shmlog.\n" + " 0x80000000 - do edge-detection on digest.\n" "Use 0x notation and do the bitor in your head :-)\n", 0, "0", "bitmap" }, diff --git a/varnish-cache/bin/varnishtest/tests/c00023.vtc b/varnish-cache/bin/varnishtest/tests/c00023.vtc new file mode 100644 index 00000000..e8ed65aa --- /dev/null +++ b/varnish-cache/bin/varnishtest/tests/c00023.vtc @@ -0,0 +1,156 @@ +# $Id$ + +test "Test -h critbit for digest edges" + +server s1 { + rxreq + expect req.url == "/1" + txresp -body "\n" + rxreq + expect req.url == "/2" + txresp -body "x\n" + rxreq + expect req.url == "/3" + txresp -body "xx\n" + rxreq + expect req.url == "/4" + txresp -body "xxx\n" + rxreq + expect req.url == "/5" + txresp -body "xxxx\n" + rxreq + expect req.url == "/6" + txresp -body "xxxxx\n" + rxreq + expect req.url == "/7" + txresp -body "xxxxxx\n" + rxreq + expect req.url == "/8" + txresp -body "xxxxxxx\n" + rxreq + expect req.url == "/9" + txresp -body "xxxxxxxx\n" +} -start + +varnish v1 -arg "-hcritbit" -vcl+backend { } -start +varnish v1 -cliok "param.set diag_bitmap 0x8000000" + +client c1 { + txreq -url "/1" + rxresp + expect resp.status == 200 + expect resp.bodylen == 1 + expect resp.http.X-Varnish == "1001" + + txreq -url "/2" + rxresp + expect resp.bodylen == 2 + expect resp.status == 200 + expect resp.http.X-Varnish == "1002" + + txreq -url "/3" + rxresp + expect resp.bodylen == 3 + expect resp.status == 200 + expect resp.http.X-Varnish == "1003" + + txreq -url "/4" + rxresp + expect resp.bodylen == 4 + expect resp.status == 200 + expect resp.http.X-Varnish == "1004" + + txreq -url "/5" + rxresp + expect resp.bodylen == 5 + expect resp.status == 200 + expect resp.http.X-Varnish == "1005" + + txreq -url "/6" + rxresp + expect resp.bodylen == 6 + expect resp.status == 200 + expect resp.http.X-Varnish == "1006" + + txreq -url "/7" + rxresp + expect resp.bodylen == 7 + expect resp.status == 200 + expect resp.http.X-Varnish == "1007" + + txreq -url "/8" + rxresp + expect resp.bodylen == 8 + expect resp.status == 200 + expect resp.http.X-Varnish == "1008" + + txreq -url "/9" + rxresp + expect resp.bodylen == 9 + expect resp.status == 200 + expect resp.http.X-Varnish == "1009" +} -run + + +client c1 { + txreq -url "/1" + rxresp + expect resp.status == 200 + expect resp.bodylen == 1 + expect resp.http.X-Varnish == "1010 1001" + + txreq -url "/2" + rxresp + expect resp.bodylen == 2 + expect resp.status == 200 + expect resp.http.X-Varnish == "1011 1002" + + txreq -url "/3" + rxresp + expect resp.bodylen == 3 + expect resp.status == 200 + expect resp.http.X-Varnish == "1012 1003" + + txreq -url "/4" + rxresp + expect resp.bodylen == 4 + expect resp.status == 200 + expect resp.http.X-Varnish == "1013 1004" + + txreq -url "/5" + rxresp + expect resp.bodylen == 5 + expect resp.status == 200 + expect resp.http.X-Varnish == "1014 1005" + + txreq -url "/6" + rxresp + expect resp.bodylen == 6 + expect resp.status == 200 + expect resp.http.X-Varnish == "1015 1006" + + txreq -url "/7" + rxresp + expect resp.bodylen == 7 + expect resp.status == 200 + expect resp.http.X-Varnish == "1016 1007" + + txreq -url "/8" + rxresp + expect resp.bodylen == 8 + expect resp.status == 200 + expect resp.http.X-Varnish == "1017 1008" + + txreq -url "/9" + rxresp + expect resp.bodylen == 9 + expect resp.status == 200 + expect resp.http.X-Varnish == "1018 1009" +} -run + +varnish v1 -cliok "hcb.dump" + +varnish v1 -expect client_conn == 2 +varnish v1 -expect cache_hit == 9 +varnish v1 -expect cache_miss == 9 +varnish v1 -expect client_req == 18 -- 2.39.5