--------------------- PatchSet 4150 Date: 2002/05/21 02:46:41 Author: jkay Branch: push Tag: (none) Log: Version of push that passes 'put' test scripts (e.g., seems to work!) Members: doc/push.txt:1.1.2.1->1.1.2.2 src/HintCache.c:1.1.2.1->1.1.2.2 src/HintCacheDisk.c:1.1.2.1->1.1.2.2 src/HintCacheEndian.c:1.1.2.1->1.1.2.2 src/HintCacheHier.c:1.1.2.1->1.1.2.2 src/HintCacheNet.c:1.1.2.2->1.1.2.3 src/HintCacheNodes.c:1.1.2.1->1.1.2.2 src/HintCachePrim.c:1.1.2.1->1.1.2.2 src/Plaxton.c:1.1.2.1->1.1.2.2 src/cf.data.pre:1.43.2.2->1.43.2.3 src/defines.h:1.15.2.2->1.15.2.3 src/dist.c:1.1.2.4->1.1.2.5 src/enums.h:1.27.2.5->1.27.2.6 src/globals.h:1.14.2.2->1.14.2.3 src/http.c:1.17.2.4->1.17.2.5 src/main.c:1.28.2.4->1.28.2.5 src/protos.h:1.41.2.5->1.41.2.6 src/put.c:1.1.2.5->1.1.2.6 src/store.c:1.16.2.1->1.16.2.2 src/structs.h:1.47.2.5->1.47.2.6 src/typedefs.h:1.25.2.4->1.25.2.5 Index: squid/doc/push.txt =================================================================== RCS file: /cvsroot/squid-sf//squid/doc/Attic/push.txt,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/doc/push.txt 21 Nov 2001 01:06:51 -0000 1.1.2.1 +++ squid/doc/push.txt 21 May 2002 02:46:41 -0000 1.1.2.2 @@ -15,7 +15,6 @@ Arguably, there is no need for 'webpush.' You can do much the same thing by executing: - client -m PUT But most people find that just really tough to think about, so instead Index: squid/src/HintCache.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCache.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/HintCache.c 20 Nov 2001 06:47:11 -0000 1.1.2.1 +++ squid/src/HintCache.c 21 May 2002 02:46:41 -0000 1.1.2.2 @@ -1,8 +1,8 @@ /* - * $Date: 2001/11/20 06:47:11 $ $Id: HintCache.c,v 1.1.2.1 2001/11/20 06:47:11 jkay Exp $ + * $Date: 2002/05/21 02:46:41 $ $Id: HintCache.c,v 1.1.2.2 2002/05/21 02:46:41 jkay Exp $ * * AUTHOR: Mike Dahlin, UT Austin, 1998 - * DEBUG: section 54 Hint cache to Squid interface. + * DEBUG: section 84 Hint cache to Squid interface. * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ * -------------------------------------------------------- @@ -39,14 +39,14 @@ #include "squid.h" -static EVH hintCacheTimer; /* timeout to flush StoreEntries */ +static EVH hintCacheTimer; /* timeout to flush StoreEntries */ -#define HINT_CACHE_DEBUG 54 +#define HINT_CACHE_DEBUG 84 /* * Globals */ -#ifdef USE_DYNAMIC_HIERARCHY +#if USE_DYNAMIC_HIERARCHY HintCacheNet *parentOutgoingA = NULL; HintCacheNet *childrenOutgoingA = NULL; HintCacheNet *neighborsOutgoing = NULL; @@ -72,49 +72,53 @@ int hintCacheInit() { - peer *e; -#ifdef USE_DYNAMIC_HIERARCHY - int ii; + peer *e; +#if USE_DYNAMIC_HIERARCHY + int ii; #endif - - hcDisk = (HintCacheDisk *)xmalloc(sizeof(HintCacheDisk)); - assert(hcDisk); - hintCacheDiskInit(hcDisk, Config.Hints.cachefile); - + + hcDisk = (HintCacheDisk *) xmalloc(sizeof(HintCacheDisk)); + assert(hcDisk); + hintCacheDiskInit(hcDisk, Config.Hints.cache_file); + #if USE_DYNAMIC_HIERARCHY - /* - * Three sets of network buffers. Children and parents - * are the children and parents as determined by the - * dynamic hierarchy algorithm (HCHier.h). Neighbors - * are static squid neighbors (neighbors.h). The - * static neighbors are used to bootstrap the - * dynamic algorithm. - */ - neighborsOutgoing = (HintCacheNet *)xmalloc(sizeof(HintCacheNet)); - assert(neighborsOutgoing); - hintCacheNetInit(neighborsOutgoing); - hintCacheHierInit(); - - childrenOutgoingA = (HintCacheNet *)xmalloc(sizeof(HintCacheNet) * hintCacheHier_NChildrenQs()); - assert(childrenOutgoingA); - for(ii = 0; ii < hintCacheHierNChildrenQs(); ii++){ - hintCacheNet_Init(&childrenOutgoingA[ii]); - } - parentOutgoingA = (HintCacheNet *)xmalloc(sizeof(HintCacheNet) * hintCacheHier_NParentQs()); - assert(parentOutgoingA); - for(ii = 0; ii < hintCacheHierNParentQs(); ii++){ - hintCacheNetInit(&parentOutgoingA[ii]); - } + /* + * Three sets of network buffers. Children and parents + * are the children and parents as determined by the + * dynamic hierarchy algorithm (HCHier.h). Neighbors + * are static squid neighbors (neighbors.h). The + * static neighbors are used to bootstrap the + * dynamic algorithm. + */ + neighborsOutgoing = (HintCacheNet *) xmalloc(sizeof(HintCacheNet)); + assert(neighborsOutgoing); + hintCacheNetInit(neighborsOutgoing); + hintCacheHierInit(); + + childrenOutgoingA = + (HintCacheNet *) xmalloc(sizeof(HintCacheNet) * + hintCacheHier_NChildrenQs()); + assert(childrenOutgoingA); + for (ii = 0; ii < hintCacheHierNChildrenQs(); ii++) { + hintCacheNet_Init(&childrenOutgoingA[ii]); + } + parentOutgoingA = + (HintCacheNet *) xmalloc(sizeof(HintCacheNet) * + hintCacheHier_NParentQs()); + assert(parentOutgoingA); + for (ii = 0; ii < hintCacheHierNParentQs(); ii++) { + hintCacheNetInit(&parentOutgoingA[ii]); + } #else - for (e = getFirstPeer(); e; e = getNextPeer(e)) - hintCacheNetInit(&e->hcoutq); + for (e = getFirstPeer(); e; e = getNextPeer(e)) + hintCacheNetInit(&e->hcoutq); #endif - /* Start hint timer */ - eventAdd("hint timer", hintCacheTimer, NULL, - (double) (squid_random() % Config.Hints.intvl), 1); + /* Start hint timer */ + eventAdd("hint timer", hintCacheTimer, NULL, + (double) (squid_random() % Config.Hints.intvl), 1); - return 0; + return 0; } /* @@ -138,29 +142,29 @@ void hintCacheDestroy() { -#ifdef USE_DYNAMIC_HIERARCHY - int ii; +#if USE_DYNAMIC_HIERARCHY + int ii; - for(ii = 0; ii < hintCacheHier_NChildrenQs(); ii++){ - hintCacheNetDestroy(&childrenOutgoingA[ii]); - } - xfree(childrenOutgoingA); - childrenOutgoingA = NULL; - for(ii = 0; ii < hintCacheHier_NParentQs(); ii++){ - hintCacheNetDestroy(&parentOutgoingA[ii]); - } - xfree(parentOutgoingA); - parentOutgoingA = NULL; - hintCacheNetDestroy(neighborsOutgoing); - xfree(neighborsOutgoing); - neighborsOutgoing = NULL; + for (ii = 0; ii < hintCacheHier_NChildrenQs(); ii++) { + hintCacheNetDestroy(&childrenOutgoingA[ii]); + } + xfree(childrenOutgoingA); + childrenOutgoingA = NULL; + for (ii = 0; ii < hintCacheHier_NParentQs(); ii++) { + hintCacheNetDestroy(&parentOutgoingA[ii]); + } + xfree(parentOutgoingA); + parentOutgoingA = NULL; + hintCacheNetDestroy(neighborsOutgoing); + xfree(neighborsOutgoing); + neighborsOutgoing = NULL; #endif - hintCacheHierDestroy(); + hintCacheHierDestroy(); - hintCacheDiskClose(hcDisk); - xfree(hcDisk); - hcDisk = NULL; + hintCacheDiskClose(hcDisk); + xfree(hcDisk); + hcDisk = NULL; } /* @@ -182,14 +186,14 @@ * *------------------------------------------------------------------ */ -void +void hintCacheCreate(void) { - if (access(Config.Hints.cachefile, R_OK|W_OK) == -1) - hintCacheDiskCreateFile(Config.Hints.cachefile, Config.Hints.size, - Config.Hints.assoc); - - hintCacheInit(); + if (access(Config.Hints.cache_file, R_OK | W_OK) == -1) + hintCacheDiskCreateFile(Config.Hints.cache_file, Config.Hints.size, + Config.Hints.assoc); + + hintCacheInit(); } /* @@ -210,21 +214,23 @@ * *------------------------------------------------------------------ */ -void -hintCacheInformLocalCopy(char *url, StoreEntry *entry) +void +hintCacheInformLocalCopy(StoreEntry * entry) { + char *url = entry->mem_obj->url; struct sockaddr_in *me; HintCacheEntry myentry; - URLKey key; + URLKey *key; HintCacheUpdate update; - - debug(HINT_CACHE_DEBUG, 5) ("hintCacheinformLocalCopy: got %s\n", url); - + + debug(HINT_CACHE_DEBUG, 5) ("hintCacheinformLocalCopy: got %s\n", + url); + if (!HINT_CACHE_ACTIVE()) { /* Hint cache is inoperative. Nothing to do. */ return; } - + if (strstr(url, "//updates")) /* Routes handle their own updates */ return; @@ -232,45 +238,46 @@ me = &Config.Sockaddr.http->s; /* Prepare data structures */ - URLKey_Init(&key, url); - hintCacheEntryInit(&myentry, key, me, entry->lastmod); + key = HINT_CACHE_KEY(entry); + hintCacheEntryInit(&myentry, *key, me, entry->lastmod); hintCacheUpdateInit(&update, HC_InformToParent, &myentry, 0); - + /* * Update local and remote hint caches. */ - hintCacheProp_HandleInformToParent(&update, me, 1); + hintCachePropHandleInformToParent(&update, me, 1); update.action = HC_InformToChild; - hintCacheProp_HandleInformToChild(&update, me, 1); + hintCachePropHandleInformToChild(&update, me, 1); } - -void -hintCacheInvalLocalCopy(StoreEntry *entry) + +void +hintCacheInvalLocalCopy(StoreEntry * entry) { struct sockaddr_in *me; HintCacheEntry myentry; HintCacheUpdate update; - + if (!HINT_CACHE_ACTIVE()) { /* Hint cache is inoperative. Nothing to do. */ return; } - + me = &Config.Sockaddr.http->s; - + /* Prepare data structures */ - hintCacheEntryInit(&myentry, entry->key, me, entry->lastmod); - hintCacheUpdateInit(&update, HC_InvalToParent, &myentry, 0); - + hintCacheEntryInit(&myentry, *HINT_CACHE_KEY(entry), + me, entry->lastmod); + hintCacheUpdateInit(&update, HC_InvalToParent, &myentry, 0); + /* * Update local and remote hint caches. */ hintCacheHandleInvalToParent(&update, me, 1); update.action = HC_InvalToChild; hintCachePropHandleInvalToChild(&update, me, 1); - + debug(HINT_CACHE_DEBUG, 5) ("hintCacheinvalLocalCopy: lost 0x%qx\n", - entry->key.key); + ((URLKey *) &entry->hchash.key)->key); } @@ -296,45 +303,44 @@ *----------------------------------------------3.24.1998----------- */ struct sockaddr_in * -hintCacheFindNearest(char *url, struct sockaddr_in *saddr) +hintCacheFindNearest(StoreEntry *entry, struct sockaddr_in *saddr) { - const struct sockaddr_in *me; - URLKey urlKey; - HintCacheEntry nearest; - int found; - - if (!HINT_CACHE_ACTIVE()) { - /* Hint cache is inoperative. Nothing to do. */ - return(NULL); - } - - URLKey_Init(&urlKey, url); - found = hintCacheDiskFindNearest(hcDisk, urlKey, &nearest); - if(!found) - return NULL; - - saddr->sin_family = AF_INET; - saddr->sin_port = nearest.port; - saddr->sin_addr = nearest.ipaddr; - - /* Never return ourselves. */ - me = &Config.Sockaddr.http->s; - if (saddr->sin_port == me->sin_port) { - if (saddr->sin_addr.s_addr == me->sin_addr.s_addr) - return NULL; - if (saddr->sin_addr.s_addr == 0x7f000000) - return NULL; - } - -#if 0 /* Fixed? */ - /* XXX - shouldn't be needed, but is - noted in BUGS */ - /* Swap bytes to host format. */ - saddr->sin_addr.s_addr = ntohl(saddr->sin_addr.s_addr); - saddr->sin_port = ntohs(saddr->sin_port); + const struct sockaddr_in *me; + URLKey *urlKey; + HintCacheEntry nearest; + int found; + + if (!HINT_CACHE_ACTIVE()) { + /* Hint cache is inoperative. Nothing to do. */ + return (NULL); + } + + urlKey = HINT_CACHE_KEY(entry); + found = hintCacheDiskFindNearest(hcDisk, *urlKey, &nearest); + if (!found) + return NULL; + + saddr->sin_family = AF_INET; + saddr->sin_port = nearest.port; + saddr->sin_addr = nearest.ipaddr; + + /* Never return ourselves. */ + me = &Config.Sockaddr.http->s; + if (saddr->sin_port == me->sin_port) { + if (saddr->sin_addr.s_addr == me->sin_addr.s_addr) + return NULL; + if (saddr->sin_addr.s_addr == 0x7f000000) + return NULL; + } +#if 0 /* Fixed? */ + /* XXX - shouldn't be needed, but is - noted in BUGS */ + /* Swap bytes to host format. */ + saddr->sin_addr.s_addr = ntohl(saddr->sin_addr.s_addr); + saddr->sin_port = ntohs(saddr->sin_port); #endif - debug(HINT_CACHE_DEBUG, 5) ("hintCachefindNearest: %s is at <%s,%d>\n", - url, inet_ntoa(saddr->sin_addr), saddr->sin_port); - return(saddr); + debug(HINT_CACHE_DEBUG, 5) ("hintCachefindNearest: %s is at <%s,%d>\n", + entry->mem_obj->url, inet_ntoa(saddr->sin_addr), saddr->sin_port); + return (saddr); } @@ -357,11 +363,11 @@ * *------------------------------------------------------------------ */ -static void +static void hintCacheTimer(void *junk) { struct sockaddr_in sin; -#ifdef USE_DYNAMIC_HIERARCHY +#if USE_DYNAMIC_HIERARCHY struct sockaddr_in *childSinA = NULL; static int nextjoin = 0; int nchildren, ichild; @@ -373,42 +379,46 @@ /* Reload timer */ eventAdd("hint timer", hintCacheTimer, NULL, - (double) (squid_random() % Config.Hints.intvl), 1); - -#ifdef USE_DYNAMIC_HIERARCHY + (double) (squid_random() % Config.Hints.intvl), 1); + +#if USE_DYNAMIC_HIERARCHY /* Process peers */ /* Send enqueued updates */ - if(parentOutgoingA != NULL){ - for(ii = 0; ii < hintCacheHier_NParentQs(); ii++){ - if(hintCacheNetBytesReady(&parentOutgoingA[ii]) > sizeof(HintCacheNetHeader)){ + if (parentOutgoingA != NULL) { + for (ii = 0; ii < hintCacheHier_NParentQs(); ii++) { + if (hintCacheNetBytesReady(&parentOutgoingA[ii]) > + sizeof(HintCacheNetHeader)) { hintCacheNetComplete(&parentOutgoingA[ii]); error = hintCacheHierGetParentAddr(ii, &sin); debug(HINT_CACHE_DEBUG, 6) - ("Sending %d bytes from parentOutgoing[%d] to %s %s\n", - hintCacheNetbytesReady(&parentOutgoingA[ii]), ii, - inet_ntoa(sin.sin_addr), - error?"ERROR":""); - if(!error){ + ("Sending %d bytes from parentOutgoing[%d] to %s %s\n", + hintCacheNetbytesReady(&parentOutgoingA[ii]), ii, + inet_ntoa(sin.sin_addr), error ? "ERROR" : ""); + if (!error) { hintCacheNetSendTo(&parentOutgoingA[ii], &sin); } hintCacheNetDone(&parentOutgoingA[ii]); } } } - if (childrenOutgoingA != NULL){ - for(ii = 0; ii < hintCacheHierNChildrenQs(); ii++){ - if(hintCacheNet_bytesReady(&childrenOutgoingA[ii]) > sizeof(HintCacheNetHeader)){ + if (childrenOutgoingA != NULL) { + for (ii = 0; ii < hintCacheHierNChildrenQs(); ii++) { + if (hintCacheNet_bytesReady(&childrenOutgoingA[ii]) > + sizeof(HintCacheNetHeader)) { hintCacheNetComplete(&childrenOutgoingA[ii]); nchildren = hintCacheHierGetChildAddrs(ii, &childSinA); debug(HINT_CACHE_DEBUG, 6) - ("Sending %d bytes to %d children from childrenOutgoing[%d]:", - hintCacheNetBytesReady(&childrenOutgoingA[ii]), nchildren, ii); - - for(ichild = 0; ichild < nchildren; ichild++){ - debug(HINT_CACHE_DEBUG, 8) (" %s ", inet_ntoa(childSinA[ichild].sin_addr)); - hintCacheNetSendTo(&childrenOutgoingA[ii], &childSinA[ichild]); + ("Sending %d bytes to %d children from childrenOutgoing[%d]:", + hintCacheNetBytesReady(&childrenOutgoingA[ii]), nchildren, + ii); + + for (ichild = 0; ichild < nchildren; ichild++) { + debug(HINT_CACHE_DEBUG, 8) (" %s ", + inet_ntoa(childSinA[ichild].sin_addr)); + hintCacheNetSendTo(&childrenOutgoingA[ii], + &childSinA[ichild]); } - + hintCacheNetDone(&childrenOutgoingA[ii]); xfree(childSinA); } @@ -427,24 +437,24 @@ #endif /* USE_DYNAMIC_HIERARCHY */ -#ifdef USE_DYNAMIC_HIERARCHY +#if USE_DYNAMIC_HIERARCHY /* * Send out Joins once every few hours. */ - if(hintCacheNodelistMyStatus() == HC_Join){ + if (hintCacheNodelistMyStatus() == HC_Join) { if (squid_curtime >= nextjoin) { hintCacheNodelistLocalJoin(); - nextjoin = squid_curtime + (squid_random() % Config.Hints.joinintvl); + nextjoin = + squid_curtime + (squid_random() % Config.Hints.join_intvl); } } #endif #ifdef DOTEST - if(0){ /* XXX */ - if(!hintCacheHierSelfTestDone){ + if (0) { /* XXX */ + if (!hintCacheHierSelfTestDone) { hintCacheHierTestNetwork(); } } #endif } - Index: squid/src/HintCacheDisk.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCacheDisk.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/HintCacheDisk.c 20 Nov 2001 06:48:42 -0000 1.1.2.1 +++ squid/src/HintCacheDisk.c 21 May 2002 02:46:41 -0000 1.1.2.2 @@ -1,5 +1,5 @@ /* - * $Date: 2001/11/20 06:48:42 $ $Id: HintCacheDisk.c,v 1.1.2.1 2001/11/20 06:48:42 jkay Exp $ + * $Date: 2002/05/21 02:46:41 $ $Id: HintCacheDisk.c,v 1.1.2.2 2002/05/21 02:46:41 jkay Exp $ * * AUTHOR: Mike Dahlin, UT Austin, 1998 * DEBUG: section 82 On-disk hint cache @@ -51,20 +51,19 @@ static int readLine(int fd, char *buffer, int max); static void initializeFile(int dataFD, int nbuckets, int associativity); -static int findKey(HintCacheDisk *d, int b, URLKey key, - HintCacheDiskEntry *foundRet); -static int deleteKey(HintCacheDisk *d, int b, HintCacheDiskEntry *oldEntry, - HintCacheDiskEntry *survivingEntry); -static void insertKey(HintCacheDisk *d, int b, HintCacheDiskEntry *newEntry); +static int findKey(HintCacheDisk * d, int b, URLKey key, + HintCacheDiskEntry * foundRet); +static int deleteKey(HintCacheDisk * d, int b, HintCacheDiskEntry * oldEntry, + HintCacheDiskEntry * survivingEntry); +static void insertKey(HintCacheDisk * d, int b, HintCacheDiskEntry * newEntry); #ifdef MADV_RANDOM static caddr_t pageAddr(caddr_t e); #endif -static void sanityCheckMatch(HintCacheDisk *d, HintCacheDiskEntry *bucketp, - HintCacheDiskEntry *entry, - int expectFullMatch, int expectKeyMatch); -static int bucket(HintCacheDisk *d, URLKey key); -static HintCacheDiskEntry *readBucket(HintCacheDisk *d, int b); -static int writeBucket(HintCacheDisk *d, int b, HintCacheDiskEntry *bucketp); +static void sanityCheckMatch(HintCacheDisk * d, HintCacheDiskEntry * bucketp, + HintCacheDiskEntry * entry, int expectFullMatch, int expectKeyMatch); +static int bucket(HintCacheDisk * d, URLKey key); +static HintCacheDiskEntry *readBucket(HintCacheDisk * d, int b); +static int writeBucket(HintCacheDisk * d, int b, HintCacheDiskEntry * bucketp); #ifdef DOTEST static void timeMadvise(); #endif @@ -105,55 +104,49 @@ static const int DO_PREFETCH = 0; /* HintCacheDisk constructor */ -void -hintCacheDiskInit(HintCacheDisk *d, char *diskPath) +void +hintCacheDiskInit(HintCacheDisk * d, char *diskPath) { int header; int dataF; char buffer[BIG_ENOUGH], token[BIG_ENOUGH], dataFile[BIG_ENOUGH]; int version; int size, buckets, associativity; - int gotVersion = 0, gotData = 0, gotAssoc = 0, - gotSize = 0, gotBuckets = 0; + int gotVersion = 0, gotData = 0, gotAssoc = 0, gotSize = 0, gotBuckets = 0; - if((pageSize = sysconf(_SC_PAGESIZE)) < 0){ + if ((pageSize = sysconf(_SC_PAGESIZE)) < 0) { perror("Cannot determine page size\n"); exit(-1); } header = open(diskPath, O_RDONLY); - if(header < 0){ + if (header < 0) { debug(HCDISK_DEBUG, 1) ("warning: Can\'t open %s, hint caching disabled\n", diskPath); HCDisk = NULL; return; } - while(readLine(header, buffer, BIG_ENOUGH)){ - if(buffer[0] != '#'){ + while (readLine(header, buffer, BIG_ENOUGH)) { + if (buffer[0] != '#') { sscanf(buffer, "%s", token); - if(!strcmp(token, "VERSION")){ + if (!strcmp(token, "VERSION")) { gotVersion = sscanf(buffer, "VERSION %d\n", &version); assert(gotVersion == 1); assert(version == HCD_VERSION); - } - else if(!strcmp(token, "DATA_FILE")){ + } else if (!strcmp(token, "DATA_FILE")) { gotData = sscanf(buffer, "DATA_FILE %s\n", dataFile); assert(gotData == 1); - } - else if(!strcmp(token, "SIZE_BYTES")){ + } else if (!strcmp(token, "SIZE_BYTES")) { gotSize = sscanf(buffer, "SIZE_BYTES %d\n", &size); assert(gotSize == 1); - } - else if(!strcmp(token, "BUCKETS")){ + } else if (!strcmp(token, "BUCKETS")) { gotBuckets = sscanf(buffer, "BUCKETS %d\n", &buckets); assert(gotBuckets == 1); - } - else if(!strcmp(token, "ASSOCIATIVITY")){ + } else if (!strcmp(token, "ASSOCIATIVITY")) { gotAssoc = sscanf(buffer, "ASSOCIATIVITY %d\n", &associativity); assert(gotAssoc == 1); - } - else{ + } else { /* Ignore what we don't understand */ } } @@ -163,32 +156,32 @@ assert(size == buckets * associativity * sizeof(HintCacheDiskEntry)); d->nbuckets = buckets; d->entriesPerBucket = associativity; - dataF = open(dataFile, O_RDWR); - if(dataF < 0){ + dataF = open(dataFile, O_RDWR); + if (dataF < 0) { debug(HCDISK_DEBUG, 1) ("warning: Can\'t open %s, hint caching disabled\n", dataFile); HCDisk = NULL; return; } - if (Config.Hints.usemmap) { - d->mmappedArray = (HintCacheDiskEntry *)mmap(0, size, PROT_READ|PROT_WRITE, - MAP_SHARED, dataF, 0); - if(!d->mmappedArray){ + if (Config.onoff.hint_cache_use_mmap) { + d->mmappedArray = + (HintCacheDiskEntry *) mmap(0, size, PROT_READ | PROT_WRITE, + MAP_SHARED, dataF, 0); + if (!d->mmappedArray) { debug(HCDISK_DEBUG, 1) ("warning: Can\'t mmap %s, hint caching disabled\n", dataFile); HCDisk = NULL; return; } #ifdef MADV_RANDOM - if(madvise((char *)d->mmappedArray, size, MADV_RANDOM)){ + if (madvise((char *) d->mmappedArray, size, MADV_RANDOM)) { debug(HCDISK_DEBUG, 1) ("warning: madvise on hint cache data failed"); } #endif close(dataF); d->fd = -1; - } - else { + } else { d->fd = dataF; } } @@ -209,26 +202,26 @@ static int readLine(int fd, char *buffer, int max) { - ssize_t got; - int count = 0; + ssize_t got; + int count = 0; - assert(buffer); - assert(fd >= 0); - assert(fd <= 10000); - assert(max > 2); /* need room for \n\0 */ - - while(count < max-2){ - got = read(fd, &buffer[count], 1); - if(got != 1){ - return 0; - } - if(buffer[count] == '\n'){ - buffer[count+1] = '\0'; - return 1; - } - count++; - } - return 0; + assert(buffer); + assert(fd >= 0); + assert(fd <= 10000); + assert(max > 2); /* need room for \n\0 */ + + while (count < max - 2) { + got = read(fd, &buffer[count], 1); + if (got != 1) { + return 0; + } + if (buffer[count] == '\n') { + buffer[count + 1] = '\0'; + return 1; + } + count++; + } + return 0; } /* @@ -241,93 +234,95 @@ * files open, even if you are allowed to * have more open file descriptors than that). */ -void +void hintCacheDiskCreateFile(char *hcPath, int size, int associativity) { - char *dataPath; - int buckets; - int headerF, dataF; - char buffer[BIG_ENOUGH]; - int len; - - len = strlen(hcPath); - dataPath = (char *)xmalloc(len + strlen(suffix) + 1); - assert(dataPath); - snprintf(dataPath, len, "%s%s", hcPath, suffix); - - buckets = (size / associativity) / sizeof(HintCacheDiskEntry); - assert(buckets * associativity * sizeof(HintCacheDiskEntry) <= size); - size = buckets * associativity * sizeof(HintCacheDiskEntry); - - headerF = open(hcPath, O_WRONLY|O_CREAT|O_TRUNC, 0744); - if(headerF < 0){ - perror("Opening Hint Cache header"); - exit(-1); - } - - snprintf(buffer, BIG_ENOUGH, - "# *** Header for hint cache. Do not modify ***\n"); - write(headerF, buffer, strlen(buffer)); - snprintf(buffer, BIG_ENOUGH, "VERSION %d\n", HCD_VERSION); - write(headerF, buffer, strlen(buffer)); - snprintf(buffer, BIG_ENOUGH, "DATA_FILE %s\n", dataPath); - write(headerF, buffer, strlen(buffer)); - snprintf(buffer, BIG_ENOUGH, "SIZE_BYTES %d\n", size); - write(headerF, buffer, strlen(buffer)); - snprintf(buffer, BIG_ENOUGH, "BUCKETS %d\n", buckets); - write(headerF, buffer, strlen(buffer)); - snprintf(buffer, BIG_ENOUGH, "ASSOCIATIVITY %d\n", associativity); - write(headerF, buffer, strlen(buffer)); - - close(headerF); - - /* Open data file*/ - dataF = open(dataPath, O_WRONLY|O_CREAT|O_TRUNC, 0744); - if(dataF < 0){ - perror("Opening Hint Cache data"); - exit(-1); - } - - /* Need to pre-extend file to 'size' */ - lseek(dataF, size - 1, 0); - write(dataF, "\0", 1); - lseek(dataF, 0, 0); - - initializeFile(dataF, buckets, associativity); - close(dataF); - xfree(dataPath); + char *dataPath; + int buckets; + int headerF, dataF; + char buffer[BIG_ENOUGH]; + int len; + + len = strlen(hcPath); + dataPath = (char *) xmalloc(len + strlen(suffix) + 1); + assert(dataPath); + snprintf(dataPath, len, "%s%s", hcPath, suffix); + + buckets = (size / associativity) / sizeof(HintCacheDiskEntry); + assert(buckets * associativity * sizeof(HintCacheDiskEntry) <= size); + size = buckets * associativity * sizeof(HintCacheDiskEntry); + + headerF = open(hcPath, O_WRONLY | O_CREAT | O_TRUNC, 0744); + if (headerF < 0) { + perror("Opening Hint Cache header"); + exit(-1); + } + + snprintf(buffer, BIG_ENOUGH, + "# *** Header for hint cache. Do not modify ***\n"); + write(headerF, buffer, strlen(buffer)); + snprintf(buffer, BIG_ENOUGH, "VERSION %d\n", HCD_VERSION); + write(headerF, buffer, strlen(buffer)); + snprintf(buffer, BIG_ENOUGH, "DATA_FILE %s\n", dataPath); + write(headerF, buffer, strlen(buffer)); + snprintf(buffer, BIG_ENOUGH, "SIZE_BYTES %d\n", size); + write(headerF, buffer, strlen(buffer)); + snprintf(buffer, BIG_ENOUGH, "BUCKETS %d\n", buckets); + write(headerF, buffer, strlen(buffer)); + snprintf(buffer, BIG_ENOUGH, "ASSOCIATIVITY %d\n", associativity); + write(headerF, buffer, strlen(buffer)); + + close(headerF); + + /* Open data file */ + dataF = open(dataPath, O_WRONLY | O_CREAT | O_TRUNC, 0744); + if (dataF < 0) { + perror("Opening Hint Cache data"); + exit(-1); + } + + /* Need to pre-extend file to 'size' */ + lseek(dataF, size - 1, 0); + write(dataF, "\0", 1); + lseek(dataF, 0, 0); + + initializeFile(dataF, buckets, associativity); + close(dataF); + xfree(dataPath); } /* Set a file to empty by invalidating all entries. */ static void initializeFile(int fd, int nbuckets, int associativity) { - HintCacheDiskEntry invalidEntry; - int ibucket, ientry; - int count; - - HCE_INVALIDATE(&invalidEntry.entry); - - for(ibucket = 0; ibucket < nbuckets; ibucket++){ - for(ientry = 0; ientry < associativity; ientry++){ - count = write(fd, &invalidEntry, sizeof(HintCacheDiskEntry)); - if(count != sizeof(HintCacheDiskEntry)){ - perror("ERROR Creating HintCacheCache file"); - exit(-1); - } + HintCacheDiskEntry invalidEntry; + int ibucket, ientry; + int count; + + HCE_INVALIDATE(&invalidEntry.entry); + + for (ibucket = 0; ibucket < nbuckets; ibucket++) { + for (ientry = 0; ientry < associativity; ientry++) { + count = write(fd, &invalidEntry, sizeof(HintCacheDiskEntry)); + if (count != sizeof(HintCacheDiskEntry)) { + perror("ERROR Creating HintCacheCache file"); + exit(-1); + } + } } - } } /* Unmap the file. */ -void hintCacheDiskClose(HintCacheDisk *d) +void +hintCacheDiskClose(HintCacheDisk * d) { - munmap((char *)d->mmappedArray, d->nbuckets * d->entriesPerBucket); - d->mmappedArray = NULL; + munmap((char *) d->mmappedArray, d->nbuckets * d->entriesPerBucket); + d->mmappedArray = NULL; } /* Update data structures to reflect the fact a copy is cached locally. */ -void hintCacheDiskInformLocal(HintCacheDisk *d, URLKey key, unsigned mtime) +void +hintCacheDiskInformLocal(HintCacheDisk * d, URLKey key, unsigned mtime) { int b; HintCacheDiskEntry new, dummyRet, old; @@ -335,13 +330,13 @@ assert(d); - if(!URLKEY_COMPARE(key, INVALID_URL_KEY)){ + if (!URLKEY_COMPARE(key, INVALID_URL_KEY)) { return; } b = bucket(d, key); foundOld = findKey(d, b, key, &old); - if(foundOld){ + if (foundOld) { /* Delete old instead of replace to support multiversioning */ deleteKey(d, b, &old, &dummyRet); } @@ -349,9 +344,9 @@ new.rtime = squid_curtime; insertKey(d, b, &new); #ifdef MADV_RANDOM - if(!CACHE_RECENT_WRITES){ - if(madvise(pageAddr((caddr_t) (d->mmappedArray + b)), - pageSize, MADV_DONTNEED)){ + if (!CACHE_RECENT_WRITES) { + if (madvise(pageAddr((caddr_t) (d->mmappedArray + b)), + pageSize, MADV_DONTNEED)) { debug(HCDISK_DEBUG, 1) ("madvise DONTNEED failed\n"); } } @@ -362,15 +357,16 @@ /* Update local data structures to reflect the fact * that we no longer have a copy locally. */ -void hintCacheDiskInvalLocal(HintCacheDisk *d, URLKey key, - unsigned mtime) +void +hintCacheDiskInvalLocal(HintCacheDisk * d, URLKey key, unsigned mtime) { HintCacheDiskEntry myent, dummyRet; int b; - debug(HCDISK_DEBUG, 2) ("HintCacheDiskinvalLocalCopy: deleting %ll\n", key.key); + debug(HCDISK_DEBUG, 2) ("HintCacheDiskinvalLocalCopy: deleting %ll\n", + key.key); - if(!URLKEY_COMPARE(key, INVALID_URL_KEY)){ + if (!URLKEY_COMPARE(key, INVALID_URL_KEY)) { return; } @@ -379,9 +375,9 @@ b = bucket(d, key); deleteKey(d, b, &myent, &dummyRet); #ifdef MADV_RANDOM - if (Config.Hints.usemmap) { - if(madvise(pageAddr((caddr_t)(d->mmappedArray + b)), - pageSize, MADV_DONTNEED)){ + if (Config.onoff.hint_cache_use_mmap) { + if (madvise(pageAddr((caddr_t) (d->mmappedArray + b)), + pageSize, MADV_DONTNEED)) { debug(HCDISK_DEBUG, 1) ("Madvise DONTNEED failed\n"); } } @@ -390,23 +386,21 @@ /* Warn vm system that certain pages will be needed. These pages * hold or will hold object mentioned in this hint update. */ -void -hintCacheDiskprefetch(HintCacheDisk *d, - HintCacheUpdate *uArray, - int nupdates) +void +hintCacheDiskprefetch(HintCacheDisk * d, HintCacheUpdate * uArray, int nupdates) { #ifdef MADV_RANDOM int b; int ii; - if(DO_PREFETCH && Config.Hints.usemmap) { - for(ii = 0; ii < nupdates; ii++){ - if(uArray[ii].action == HC_InvalToParent || - uArray[ii].action == HC_InvalToChild || - uArray[ii].action == HC_InformToParent || - uArray[ii].action == HC_InformToChild){ + if (DO_PREFETCH && Config.onoff.hint_cache_use_mmap) { + for (ii = 0; ii < nupdates; ii++) { + if (uArray[ii].action == HC_InvalToParent || + uArray[ii].action == HC_InvalToChild || + uArray[ii].action == HC_InformToParent || + uArray[ii].action == HC_InformToChild) { b = bucket(d, uArray[ii].entry.key); - if(madvise(pageAddr((caddr_t) (d->mmappedArray + b)), - pageSize, MADV_WILLNEED)){ + if (madvise(pageAddr((caddr_t) (d->mmappedArray + b)), + pageSize, MADV_WILLNEED)) { debug(HCDISK_DEBUG, 1) ("madvise WILLNEED failed\n"); } } @@ -427,29 +421,28 @@ * from outside HintCacheDisk.c. */ int -hintCacheDisknetInvalRecord(HintCacheDisk *d, - HintCacheEntry *entry, - HintCacheEntry *survivor) +hintCacheDisknetInvalRecord(HintCacheDisk * d, + HintCacheEntry * entry, HintCacheEntry * survivor) { HintCacheDiskEntry dentry, dsurv; int remainingCopy; int b; - - if(!HCE_VALID(entry)) { + + if (!HCE_VALID(entry)) { survivor->key.key = 0; return 0; } dentry.entry = *entry; dentry.rtime = squid_curtime; - + b = bucket(d, entry->key); remainingCopy = deleteKey(d, b, &dentry, &dsurv); *survivor = dsurv.entry; #ifdef MADV_RANDOM - if (Config.Hints.usemmap) - if(madvise(pageAddr((caddr_t)(d->mmappedArray + b)), - pageSize, MADV_DONTNEED)){ + if (Config.onoff.hint_cache_use_mmap) + if (madvise(pageAddr((caddr_t) (d->mmappedArray + b)), + pageSize, MADV_DONTNEED)) { debug(HCDISK_DEBUG, 1) ("madvise DONTNEED failed\n"); } #endif @@ -464,8 +457,8 @@ * * Takes HintCacheEntrys as args because it's exported. */ -int -hintCacheDiskUpdateIfCloser(HintCacheDisk *d, HintCacheEntry *new) +int +hintCacheDiskUpdateIfCloser(HintCacheDisk * d, HintCacheEntry * new) { HintCacheDiskEntry old, dummyRet, dnew, *todelete; URLKey key = new->key; @@ -474,36 +467,33 @@ int ret = 0; int foundOld; int b; - - if(!HCE_VALID(new)){ + + if (!HCE_VALID(new)) { return 0; } dnew.entry = *new; dnew.rtime = squid_curtime; - + b = bucket(d, key); foundOld = findKey(d, b, key, &old); if (!foundOld) { insertKey(d, b, &dnew); todelete = &dnew; ret = 1; - } - else + } else todelete = &old; - - e = storeGet(key); + + e = hintCacheStoreGet(key); if (e && e->lastmod < new->mtime) { /* This hint is about a new version. Invalidate the old version */ storeRelease(e); dochange = 1; - } - else if (foundOld && squid_curtime >= old.rtime + Config.Hints.holddown) { + } else if (foundOld && squid_curtime >= old.rtime + Config.Hints.holddown) { /* Don't propagate hints about the same version more often - that once every fifteen minutes. */ + * that once every fifteen minutes. */ dochange = 1; - } - else if (hintCacheHierCompareDistance(new->ipaddr, old.entry.ipaddr) < 0) { + } else if (hintCacheHierCompareDistance(new->ipaddr, old.entry.ipaddr) < 0) { /* This hint is for cache closer than what we got */ dochange = 1; } @@ -514,9 +504,9 @@ ret = 1; } #ifdef MADV_RANDOM - if(!CACHE_RECENT_WRITES && Config.Hints.usemmap){ - if(madvise(pageAddr((caddr_t)(d->mmappedArray + b)), - pageSize, MADV_DONTNEED)){ + if (!CACHE_RECENT_WRITES && Config.onoff.hint_cache_use_mmap) { + if (madvise(pageAddr((caddr_t) (d->mmappedArray + b)), + pageSize, MADV_DONTNEED)) { perror("Madvise DONTNEED failed\n"); } } @@ -536,15 +526,14 @@ * Takes HintCacheEntry as arg because it is exported. */ int -hintCacheDiskFindNearest(HintCacheDisk *d, URLKey key, - HintCacheEntry *match) +hintCacheDiskFindNearest(HintCacheDisk * d, URLKey key, HintCacheEntry * match) { int b; int found; HintCacheDiskEntry dent; assert(match != 0); - if(!URLKEY_COMPARE(key, INVALID_URL_KEY)){ + if (!URLKEY_COMPARE(key, INVALID_URL_KEY)) { return 0; } @@ -553,9 +542,9 @@ if (found) *match = dent.entry; #ifdef MADV_RANDOM - if(!CACHE_RECENT_READS && Config.Hints.usemmap){ - if(madvise(pageAddr((caddr_t)(d->mmappedArray + b)), - pageSize, MADV_DONTNEED)){ + if (!CACHE_RECENT_READS && Config.onoff.hint_cache_use_mmap) { + if (madvise(pageAddr((caddr_t) (d->mmappedArray + b)), + pageSize, MADV_DONTNEED)) { perror("Madvise DONTNEED failed\n"); } } @@ -566,7 +555,7 @@ /* Return pointer to first entry in bucket for key. */ static int -bucket(HintCacheDisk *d, URLKey key) +bucket(HintCacheDisk * d, URLKey key) { int b; @@ -583,7 +572,7 @@ pageAddr(caddr_t e) { caddr_t ret; - ret = e - ((unsigned)e % pageSize); + ret = e - ((unsigned) e % pageSize); return ret; } #endif /* MADV_RANDOM */ @@ -602,24 +591,24 @@ * at any time. */ static int -deleteKey(HintCacheDisk *d, int b, HintCacheDiskEntry *entry, HintCacheDiskEntry *survivor) +deleteKey(HintCacheDisk * d, int b, HintCacheDiskEntry * entry, + HintCacheDiskEntry * survivor) { HintCacheDiskEntry *bucketp = d->mmappedArray + b; int ii; assert(survivor != NULL); - assert(entry != survivor); + assert(entry != survivor); assert(HintCacheE_VALID(&entry->entry)); bucketp = readBucket(d, b); - for(ii = 0; ii < d->entriesPerBucket; ii++){ - if(!URLKEY_COMPARE(bucketp[ii].entry.key, entry->entry.key)){ - if(!HCEntry_Compare(&entry->entry, &bucketp[ii].entry)){ + for (ii = 0; ii < d->entriesPerBucket; ii++) { + if (!URLKEY_COMPARE(bucketp[ii].entry.key, entry->entry.key)) { + if (!HCEntry_Compare(&entry->entry, &bucketp[ii].entry)) { HCE_INVALIDATE(&bucketp[ii].entry); sanityCheckMatch(d, bucketp, entry, 0, 0); break; - } - else{ + } else { /* * Matched key but not NodeId. */ @@ -647,7 +636,8 @@ * If all entries are full, entry d->entriesPerBucket - 1 * (the last entry) is lost. */ -static void insertKey(HintCacheDisk *d, int b, HintCacheDiskEntry *entry) +static void +insertKey(HintCacheDisk * d, int b, HintCacheDiskEntry * entry) { HintCacheDiskEntry *bucketp; int from, to; @@ -668,12 +658,12 @@ * emtpy if all earlier ones are empty (you are always * allowed to shift over the last entry.) */ - for(to = 0; to < d->entriesPerBucket - 1; to++){ - if(!HCE_VALID(&bucketp[to].entry)){ + for (to = 0; to < d->entriesPerBucket - 1; to++) { + if (!HCE_VALID(&bucketp[to].entry)) { break; } } - assert(to <= d->entriesPerBucket -1 ); + assert(to <= d->entriesPerBucket - 1); assert(!HCE_VALID(&bucketp[to].entry) || (to == d->entriesPerBucket - 1)); /* @@ -682,7 +672,7 @@ * which shifts into the last bucket (entriesPerBucket-1). * Don't go any farther, or we clobber the next bucket. */ - for(; to > 0; to--){ + for (; to > 0; to--) { from = to - 1; assert(from >= 0); bucketp[to] = bucketp[from]; @@ -697,17 +687,17 @@ * match specified key. */ static void -sanityCheckMatch(HintCacheDisk *d, HintCacheDiskEntry *bucketp, HintCacheDiskEntry *entry, - int expectFullMatch, int expectKeyMatch) +sanityCheckMatch(HintCacheDisk * d, HintCacheDiskEntry * bucketp, + HintCacheDiskEntry * entry, int expectFullMatch, int expectKeyMatch) { int ii; int fullMatch = 0, keyMatch = 0; - for(ii = 0; ii < d->entriesPerBucket; ii++){ - if(!hintCacheEntryCompare(&bucketp[ii].entry, &entry->entry)){ + for (ii = 0; ii < d->entriesPerBucket; ii++) { + if (!hintCacheEntryCompare(&bucketp[ii].entry, &entry->entry)) { fullMatch++; } - if(!URLKEY_COMPARE(bucketp[ii].entry.key, entry->entry.key)){ + if (!URLKEY_COMPARE(bucketp[ii].entry.key, entry->entry.key)) { keyMatch++; } } @@ -727,44 +717,44 @@ * at any time. */ static int -findKey(HintCacheDisk *d, int b, URLKey key, HintCacheDiskEntry *copy) +findKey(HintCacheDisk * d, int b, URLKey key, HintCacheDiskEntry * copy) { - HintCacheDiskEntry *bucketp; - int ii; - - bucketp = readBucket(d, b); - assert(copy != NULL); - assert(copy < bucketp || copy > &bucketp[d->entriesPerBucket-1]); - assert(URLKEY_COMPARE(key, INVALID_URL_KEY)); - for(ii = 0; ii < d->entriesPerBucket; ii++){ - if(!URLKEY_COMPARE(bucketp[ii].entry.key, key)){ - *copy = bucketp[ii]; - assert(!URLKEY_COMPARE(copy->entry.key, key)); - if(ii != 0){ - /* - * Move to front of LRU list by deleting entry and inserting - */ - HCE_INVALIDATE(&bucketp[ii].entry); - writeBucket(d, b, &bucketp[ii]); - insertKey(d, b, copy); - } - return 1; - } - } - HCE_INVALIDATE(©->entry); - return 0; + HintCacheDiskEntry *bucketp; + int ii; + + bucketp = readBucket(d, b); + assert(copy != NULL); + assert(copy < bucketp || copy > &bucketp[d->entriesPerBucket - 1]); + assert(URLKEY_COMPARE(key, INVALID_URL_KEY)); + for (ii = 0; ii < d->entriesPerBucket; ii++) { + if (!URLKEY_COMPARE(bucketp[ii].entry.key, key)) { + *copy = bucketp[ii]; + assert(!URLKEY_COMPARE(copy->entry.key, key)); + if (ii != 0) { + /* + * Move to front of LRU list by deleting entry and inserting + */ + HCE_INVALIDATE(&bucketp[ii].entry); + writeBucket(d, b, &bucketp[ii]); + insertKey(d, b, copy); + } + return 1; + } + } + HCE_INVALIDATE(©->entry); + return 0; } static HintCacheDiskEntry * -readBucket(HintCacheDisk *d, int b) +readBucket(HintCacheDisk * d, int b) { static HintCacheDiskEntry *bucketp = 0; int bucketlen; /* If using mmap, just return the pointer */ - if (Config.Hints.usemmap) - return(d->mmappedArray + b); - + if (Config.onoff.hint_cache_use_mmap) + return (d->mmappedArray + b); + /* Get a static buffer to put stuff in */ bucketlen = sizeof(HintCacheDiskEntry) * d->entriesPerBucket; if (bucketp == 0) { @@ -774,40 +764,41 @@ /* Fetch hint from disk by Unix I/O */ if (lseek(d->fd, b * sizeof(HintCacheDiskEntry), 0) == -1) { debug(HCDISK_DEBUG, 1) ("warning: can't seek to hint at offset %d\n", - b * sizeof(HintCacheDiskEntry)); + b * sizeof(HintCacheDiskEntry)); return 0; } if (read(d->fd, bucketp, bucketlen) == -1) { debug(HCDISK_DEBUG, 1) ("warning: can't read hint at offset %d\n", - b * sizeof(HintCacheDiskEntry)); + b * sizeof(HintCacheDiskEntry)); return 0; } - + return bucketp; } static int -writeBucket(HintCacheDisk *d, int b, HintCacheDiskEntry *bucketp) +writeBucket(HintCacheDisk * d, int b, HintCacheDiskEntry * bucketp) { /* If using mmap, no action is necessary - model is that - you modify stuff via direct pointer you got from read */ - if (Config.Hints.usemmap) + * you modify stuff via direct pointer you got from read */ + if (Config.onoff.hint_cache_use_mmap) return 0; - + /* Write bucket to disk by Unix I/O */ if (lseek(d->fd, b * sizeof(HintCacheDiskEntry), 0) == -1) { debug(HCDISK_DEBUG, 1) ("warning: can't seek to hint at offset %d\n", - b * sizeof(HintCacheDiskEntry)); + b * sizeof(HintCacheDiskEntry)); return -1; } - if (write(d->fd, bucketp, sizeof(HintCacheDiskEntry) * d->entriesPerBucket) == -1) { + if (write(d->fd, bucketp, + sizeof(HintCacheDiskEntry) * d->entriesPerBucket) == -1) { debug(HCDISK_DEBUG, 1) ("warning: can't write hint at offset %d\n", - b * sizeof(HintCacheDiskEntry)); + b * sizeof(HintCacheDiskEntry)); return -1; } - + return 0; } @@ -816,13 +807,11 @@ { char hcname[256]; - if (!Config.Hints.cachefile[0]) + if (!Config.Hints.cache_file[0]) return; - - unlink(Config.Hints.cachefile); - strcpy(hcname, Config.Hints.cachefile); + + unlink(Config.Hints.cache_file); + strcpy(hcname, Config.Hints.cache_file); strcat(hcname, ".theCache"); unlink(hcname); } - - Index: squid/src/HintCacheEndian.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCacheEndian.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/HintCacheEndian.c 20 Nov 2001 06:52:17 -0000 1.1.2.1 +++ squid/src/HintCacheEndian.c 21 May 2002 02:46:41 -0000 1.1.2.2 @@ -1,7 +1,7 @@ /* - * $Date: 2001/11/20 06:52:17 $ $Id: HintCacheEndian.c,v 1.1.2.1 2001/11/20 06:52:17 jkay Exp $ + * $Date: 2002/05/21 02:46:41 $ $Id: HintCacheEndian.c,v 1.1.2.2 2002/05/21 02:46:41 jkay Exp $ * - * DEBUG: section 15 Neighbor Routines + * DEBUG: section 85 Hint Cache Endianness conversion routines * AUTHOR: Mike Dahlin, UT Austin, 1998 * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ @@ -45,29 +45,29 @@ #include "squid.h" #include -long long unsigned +long long unsigned HCEndian_llNetToMachine(long long unsigned net) { - long unsigned *netLong = (long unsigned *)&net; - long long unsigned machine; - long unsigned *machineLong = (long unsigned *)&machine; - - machineLong[0] = ntohl(netLong[0]); - machineLong[1] = ntohl(netLong[1]); - return machine; + long unsigned *netLong = (long unsigned *) &net; + long long unsigned machine; + long unsigned *machineLong = (long unsigned *) &machine; + + machineLong[0] = ntohl(netLong[0]); + machineLong[1] = ntohl(netLong[1]); + return machine; } -long long unsigned +long long unsigned HCEndian_llMachineToNet(long long unsigned machine) { - long unsigned *machineLong = (long unsigned *)&machine; - long long unsigned net; - long unsigned *netLong = (long unsigned *)&net; - - netLong[0] = htonl(machineLong[0]); - netLong[1] = htonl(machineLong[1]); - return net; + long unsigned *machineLong = (long unsigned *) &machine; + long long unsigned net; + long unsigned *netLong = (long unsigned *) &net; + + netLong[0] = htonl(machineLong[0]); + netLong[1] = htonl(machineLong[1]); + return net; } @@ -75,23 +75,23 @@ void HCEndian_selfTest(void) { - static const int verbose = 0; - long long unsigned ll1 = (long long unsigned)0x3BCDEF0213579876; - long long unsigned ll2; - - printf("HCEndian_selfTest."); - if(verbose){ - printf("before: %llx\n", ll1); - } - ll2 = HCEndian_llMachineToNet(ll1); - if(verbose){ - printf("during: %llx\n", ll2); - } - ll2 = HCEndian_llNetToMachine(ll2); - if(verbose){ - printf("after: %llx\n", ll2); - } - assert(ll1 == ll2); - printf("..OK\n"); + static const int verbose = 0; + long long unsigned ll1 = (long long unsigned) 0x3BCDEF0213579876; + long long unsigned ll2; + + printf("HCEndian_selfTest."); + if (verbose) { + printf("before: %llx\n", ll1); + } + ll2 = HCEndian_llMachineToNet(ll1); + if (verbose) { + printf("during: %llx\n", ll2); + } + ll2 = HCEndian_llNetToMachine(ll2); + if (verbose) { + printf("after: %llx\n", ll2); + } + assert(ll1 == ll2); + printf("..OK\n"); } #endif Index: squid/src/HintCacheHier.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCacheHier.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/HintCacheHier.c 20 Nov 2001 06:50:12 -0000 1.1.2.1 +++ squid/src/HintCacheHier.c 21 May 2002 02:46:41 -0000 1.1.2.2 @@ -1,8 +1,8 @@ /* - * $Date: 2001/11/20 06:50:12 $ $Id: HintCacheHier.c,v 1.1.2.1 2001/11/20 06:50:12 jkay Exp $ + * $Date: 2002/05/21 02:46:41 $ $Id: HintCacheHier.c,v 1.1.2.2 2002/05/21 02:46:41 jkay Exp $ * * AUTHOR: Mike Dahlin, UT Austin, 1998 - * DEBUG: section 61, Hint cache hierarchy. + * DEBUG: section 86, Hint cache hierarchy. * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ * -------------------------------------------------------- @@ -76,20 +76,20 @@ * recv "I am not child" from child: remove child */ -#define HCHIER_DEBUG 61 +#define HCHIER_DEBUG 86 #ifdef DOTEST static int doTestBarrier(int barrier); static void writeTestBarrier(int barrier); static int readTestBarrier(int barrier); static void clearTestBarrier(); -static void testFindPeer(peer *p); +static void testFindPeer(peer * p); static void testPlax(void); static void testCreateStuff(char *tag); static void testFind(void); static void testFindStuff(char *tag, const struct sockaddr_in *expect); #endif /* DOTEST */ - + /* * These must be an set of values each one greater than the * last to define the series of states for the network test. @@ -106,43 +106,42 @@ #define BARRIER_FIND 1009 #define BARRIER_LAST 1010 #define BARRIER_DONE 9999 - -int HCHier_selfTestDone = 0; + +int HintCacheHier_selfTestDone = 0; -List_Links HCHier_Nodes; +dlink_list HintCacheHier_Nodes; -int scanIDs _PARAMS((List_Links *l, char *b, int *count)); -int scanIDDistances _PARAMS((List_Links *l, char *b, int *count)); +int scanIDs (dlink_list * l, char *b, int *count); +int scanIDDistances (dlink_list * l, char *b, int *count); void -HCHier_Init(void) +hintCacheHier_Init(void) { - HCNLIter iter; - struct sockaddr_in saddr; - /* - * This should be set in config file - */ - static int bitsPerLevelXXX = 8; - - HCNodelist_Init(); - HCPlax_Init(bitsPerLevelXXX); - HCNodelist_LocalJoin(); - for(HCNodeList_IterStart(&iter); - HCNodeList_IterCheck(iter); - HCNodeList_IterNext(&iter)){ - if(HCNodeList_IterGetAddr(iter, &saddr)){ - HCPlax_addNode(&saddr); + HintCacheNodeListIter iter; + struct sockaddr_in saddr; + /* + * This should be set in config file + */ + static int bitsPerLevelXXX = 8; + + HintCacheNodelist_Init(); + HintCachePlax_Init(bitsPerLevelXXX); + HintCacheNodelist_LocalJoin(); + for (HintCacheNodeList_IterStart(&iter); + hintCacheNodeList_IterCheck(iter); hintCacheNodeList_IterNext(&iter)) { + if (hintCacheNodeList_IterGetAddr(iter, &saddr)) { + hintCachePlax_addNode(&saddr); + } } - } } void -HCHier_Destroy(void) +hintCacheHier_Destroy(void) { - HCNodelist_LocalLeave(); - HCNodelist_Destroy(); - HCPlax_Destroy(); + hintCacheNodelist_LocalLeave(); + hintCacheNodelist_Destroy(); + hintCachePlax_Destroy(); } /* @@ -166,22 +165,17 @@ *----------------------------------------------------7.18.1998--------- */ void -HCHier_updateMembershipNeighbor(struct sockaddr_in *neighbor, - NeighborAction action) +hintCacheHierUpdateMembershipNeighbor(struct sockaddr_in *neighbor, + NeighborAction action) { - if(action == NEIGHBOR_ADD){ - HCNodelist_addMembershipNeighbor(neighbor); - } - else{ - HCNodelist_rmMembershipNeighbor(neighbor); - } + /* Currently nothing */ } /* *------------------------------------------------------------------ * - * HCHier_compareDistanceFromMe -- + * hintCacheHierCompareDistanceFromMe -- * * Return <0 if new node is closer than old node, 0 if same * distance, >0 if new node is closer than old node. @@ -201,7 +195,7 @@ *------------------------------------------------------------------ */ int -HCHier_compareDistanceFromMe(struct in_addr new, struct in_addr old) +hintCacheHierCompareDistanceFromMe(struct in_addr new, struct in_addr old) { int nrtt, ortt; int nhops, ohops; @@ -215,7 +209,7 @@ strcpy(name, inet_ntoa(old)); ortt = netdbHostRtt(name); if (nrtt && ortt) - return(nrtt - ortt); + return (nrtt - ortt); /* Otherwise compare hopcount */ nhops = netdbHintHops(new); @@ -223,15 +217,15 @@ /* If either host is unknown, say new one is nearer */ if (nhops == 0 || ohops == 0) - return(-1); - - return(nhops - ohops); + return (-1); + + return (nhops - ohops); } /* *------------------------------------------------------------------ * - * HCHier_newNode -- + * hintCacheHierNewNode -- * * This gets called when we hear about a new node in the system. * @@ -247,16 +241,15 @@ *-------------------------------------------------4.1.1998----------- */ void -HCHier_newNode(struct sockaddr_in *sin, int hops, - long long joinTimeNS) +hintCacheHierNewNode(struct sockaddr_in *sin, int hops, long long joinTimeNS) { - HCNodelist_NetJoin(sin, hops, joinTimeNS); + hintCacheNodelist_NetJoin(sin, hops, joinTimeNS); } /* *------------------------------------------------------------------ * - * HCHier_delNode -- + * hintCacheHierDelNode -- * * This gets called when we hear about a node leaving the system * @@ -272,16 +265,15 @@ *-------------------------------------------------4.1.1998----------- */ void -HCHier_delNode(struct sockaddr_in *sin, int hops, - long long joinTimeNS) +hintCacheHierDelNode(struct sockaddr_in *sin, int hops, long long joinTimeNS) { - HCNodelist_NetLeave(sin, hops, joinTimeNS); + hintCacheNodelist_NetLeave(sin, hops, joinTimeNS); } /* *------------------------------------------------------------------ * - * HCHier_CheckIfParent -- + * hintCacheHierCheckIfParent -- * * See if the specified node is really my parent. * @@ -296,11 +288,11 @@ * *---------------------------------------------------4.10.1998--------- */ -int -HCHier_CheckIfParent (URLKey key, struct sockaddr_in *candidate) +int +hintCacheHierCheckIfParent(URLKey key, struct sockaddr_in *candidate) { -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_CheckIfParent(key, candidate); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlax_CheckIfParent(key, candidate); #else /* * For static algorithm, anyone that wants to be my parent can @@ -313,7 +305,7 @@ /* *------------------------------------------------------------------ * - * HCHier_CheckIfChild -- + * hintCacheHier_CheckIfChild -- * * See if the specified node is really my child. * @@ -328,11 +320,11 @@ * *---------------------------------------------------4.10.1998--------- */ -int -HCHier_CheckIfChild (struct sockaddr_in *candidate) +int +hintCacheHierCheckIfChild(struct sockaddr_in *candidate) { -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_CheckIfChild(candidate); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlax_CheckIfChild(candidate); #else /* * For static algorithm, anyone that wants to be my child can @@ -345,7 +337,7 @@ /* *------------------------------------------------------------------ * - * HCHier_AddChild -- + * hintCacheHierAddChild -- * * This node has claimed to by my child, so add it * to the dynamic hierarchy. @@ -361,11 +353,11 @@ * *-----------------------------------------------------4.10.1998-------- */ -void -HCHier_AddChild (struct sockaddr_in *child) +void +hintCacheHierAddChild(struct sockaddr_in *child) { -#ifdef USE_DYNAMIC_HIERARCHY - HCPlax_AddChild(child); +#if USE_DYNAMIC_HIERARCHY + hintCachePlax_AddChild(child); #else /* * For static algorithm, I don't track children. @@ -378,7 +370,7 @@ /* *------------------------------------------------------------------ * - * HCHier_RemoveChild -- + * hintCacheHierRemoveChild -- * * This node denies paternity. Disinherit it. * @@ -393,10 +385,11 @@ * *---------------------------------------------------4.10.1998---------- */ -void HCHier_RemoveChild (struct sockaddr_in *child) +void +hintCacheHierRemoveChild(struct sockaddr_in *child) { -#ifdef USE_DYNAMIC_HIERARCHY - HCPlax_RemoveChild(child); +#if USE_DYNAMIC_HIERARCHY + hintCachePlax_RemoveChild(child); #else /* * For static algorithm, I don't track children. @@ -412,25 +405,25 @@ /* Each children queue holds messages that should go to a set of * "equivalent" children (eg. the children at some level of the - * hierarchy.) There are HCHier_NChildrenQs() such queues; - * Child queue q contains c = HCHier_ChildrenPerQ(q) children. + * hierarchy.) There are hintCacheHier_NChildrenQs() such queues; + * Child queue q contains c = hintCacheHier_ChildrenPerQ(q) children. * The addresses of the children can be found with the function - * HCHier_GetChildAddr(q, c); + * hintCacheHier_GetChildAddr(q, c); * * Each parent queue holds messages that should go to one parent. * In general, we may have different parents for different objects. * So, enqueue messages for an object in the queue - * HCHier_ParentQIndex(URLKey). + * hintCacheHier_ParentQIndex(URLKey). */ /* *------------------------------------------------------------------ * - * HCHier_ChildQIndex -- + * hintCacheHierChildQIndex -- * * Return the index into the array of queues of * children for children that are my children - * for this object. (See HCPlax for how + * for this object. (See hintCachePlax for how * children are grouped into levels.) * * Also, if I have no children for this object, @@ -447,12 +440,12 @@ * *-----------------------------------------------4.10.1998------------- */ -int -HCHier_ChildQIndex(URLKey *key, int iAmRoot, int *amILeaf) +int +hintCacheHierChildQIndex(URLKey * key, int iAmRoot, int *amILeaf) { - assert(amILeaf != NULL); -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_ChildQIndex(key, iAmRoot, amILeaf); + assert(amILeaf != NULL); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlax_ChildQIndex(key, iAmRoot, amILeaf); #else /* * For static algorithm, we have one set of children and @@ -466,12 +459,12 @@ /* *------------------------------------------------------------------ * - * HCHier_NChildrenQs -- + * hintCacheHierNChildrenQs -- * * Return the number of outgoing message queues * to different classes of children. Each * "class" corresponds to children for which - * I am a parent. (See HCPlax for how + * I am a parent. (See hintCachePlax for how * children are grouped into levels.) * * Arguments: @@ -485,10 +478,11 @@ * *------------------------------------------------4.10.1998------------ */ -int HCHier_NChildrenQs(void) +int +hintCacheHierNChildrenQs(void) { -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_NChildrenQs(); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlax_NChildrenQs(); #else /* * For static algorithm, we have one set of children and @@ -503,7 +497,7 @@ /* *------------------------------------------------------------------ * - * HCHier_GetChildAddrs -- + * hintCacheHierGetChildAddrs -- * * Return the number of children for the specified message * queue, allocate a buffer for that many addresses, @@ -527,29 +521,29 @@ * *------------------------------------------------4.16.1998------------ */ -int -HCHier_GetChildAddrs(int qIndex, struct sockaddr_in **retAddrAP) +int +hintCacheHierGetChildAddrs(int qIndex, struct sockaddr_in **retAddrAP) { #ifndef USE_DYNAMIC_HIERARCHY - peer *p; - int count = 0, nchildren = 0; + peer *p; + int count = 0, nchildren = 0; #endif - assert(retAddrAP); - assert(qIndex < HCHier_NChildrenQs()); + assert(retAddrAP); + assert(qIndex < hintCacheHierNChildrenQs()); -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_GetChildAddrs(qIndex, retAddrAP); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlaxGetChildAddrs(qIndex, retAddrAP); #else assert(qIndex == 0); for (p = getFirstPeer(); p; p = getNextPeer(p)) { - nchildren++; + nchildren++; } - *retAddrAP = (struct sockaddr_in *)xmalloc(nchildren - * sizeof(struct sockaddr_in)); + *retAddrAP = (struct sockaddr_in *) xmalloc(nchildren + * sizeof(struct sockaddr_in)); for (p = getFirstPeer(); p; p = getNextPeer(p)) { - (*retAddrAP)[count] = p->in_addr; - count++; + (*retAddrAP)[count] = p->in_addr; + count++; } /* * Squid promises that we run atomically @@ -562,7 +556,7 @@ /* *------------------------------------------------------------------ * - * HCHier_NParentQs -- + * hintCacheHierNParentQs -- * * How many different message queues are they for different * parents? @@ -578,10 +572,11 @@ * *--------------------------------------------------4.10.1998--------- */ -int HCHier_NParentQs(void) +int +hintCacheHierNParentQs(void) { -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_NParentQs(); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlaxNParentQs(); #else /* * For static algorithm, we have one parent @@ -595,7 +590,7 @@ /* *------------------------------------------------------------------ * - * HCHier_ParentQIndex -- + * hintCacheHierParentQIndex -- * * Return the index of the queue I should use to talk * to the parent for the specified object (set amIRoot @@ -612,11 +607,12 @@ * *---------------------------------------------------4.10.1998--------- */ -int HCHier_ParentQIndex(URLKey *key, int *amIRoot) +int +hintCacheHierParentQIndex(URLKey * key, int *amIRoot) { - assert(amIRoot != NULL); -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_ParentQIndex(key, amIRoot); + assert(amIRoot != NULL); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlaxParentQIndex(key, amIRoot); #else /* * For static algorithm, we have one parent @@ -630,7 +626,7 @@ /* *------------------------------------------------------------------ * - * HCHier_GetParentAddr -- + * hintCacheHierGetParentAddr -- * * Return the address of the node that is curerntly * the parent for the specified message queue. @@ -646,23 +642,24 @@ * *-----------------------------------------------------4.10.1998------- */ -int HCHier_GetParentAddr(int index, struct sockaddr_in *retAddr) +int +hintCacheHierGetParentAddr(int index, struct sockaddr_in *retAddr) { -#ifdef USE_DYNAMIC_HIERARCHY - return HCPlax_GetParentAddr(index, retAddr); +#if USE_DYNAMIC_HIERARCHY + return hintCachePlaxGetParentAddr(index, retAddr); #else peer *p; - + for (p = getFirstPeer(); p; p = getNextPeer(p)) { - if(p->type == PEER_PARENT){ - *retAddr = p->in_addr; - return 0; - } + if (p->type == PEER_PARENT) { + *retAddr = p->in_addr; + return 0; + } } p = getFirstPeer(); - if(p){ - *retAddr = p->in_addr; - return 0; + if (p) { + *retAddr = p->in_addr; + return 0; } return -1; #endif @@ -670,9 +667,9 @@ int -HCHier_SendToParent(struct sockaddr_in *src, HCUpdate *update, int msgtype) +hintCacheHierSendToParent(struct sockaddr_in *src, HintCacheUpdate * update, int msgtype) { -#ifdef USE_DYNAMIC_HIERARCHY +#if USE_DYNAMIC_HIERARCHY int stillHave; int pIndex, cIndex; int iAmRoot, iAmLeaf; @@ -680,52 +677,53 @@ peer *e; #endif -#ifdef USE_DYNAMIC_HIERARCHY - pIndex = HCHier_ParentQIndex(&update->entry.key, &iAmRoot); +#if USE_DYNAMIC_HIERARCHY + pIndex = hintCacheHierParentQIndex(&update->entry.key, &iAmRoot); #else for (e = getFirstPeer(); e; e = getNextPeer(e)) { if (e->type != PEER_PARENT) continue; if (e->in_addr.sin_addr.s_addr == src->sin_addr.s_addr && e->http_port == src->sin_port) { - if (e->type != PEER_PARENT) { + if (e->type != PEER_PARENT) { debug(HCHIER_DEBUG, 0, - "warning: got parental msg from non-parent <%s,%d>.\n", - inet_ntoa(src->sin_addr), src->sin_port); + "warning: got parental msg from non-parent <%s,%d>.\n", + inet_ntoa(src->sin_addr), src->sin_port); debug(HCHIER_DEBUG, 0, - " Not propagating it. Configuration mismatch?\n"); - return(-1); + " Not propagating it. Configuration mismatch?\n"); + return (-1); } continue; } - HCNet_Enqueue(&e->hcoutq, msgtype, &update->entry, update->hopcount + 1); + hintCacheNetEnqueue(&e->hcoutq, msgtype, &update->entry, + update->hopcount + 1); } if (e == 0) { /* Not found. */ - return(-1); + return (-1); /* Don't propagate */ } #endif - -#ifdef USE_DYNAMIC_HIERARCHY + +#if USE_DYNAMIC_HIERARCHY /* Send message */ - if(!iAmRoot) { - assert(pIndex < HCHier_NParentQs()); - HCNet_Enqueue(&parentOutgoingA[pIndex], msgtype, &update->entry, - update->hopcount+1); + if (!iAmRoot) { + assert(pIndex < hintCacheHier_NParentQs()); + hintCacheNetEnqueue(&parentOutgoingA[pIndex], msgtype, &update->entry, + update->hopcount + 1); } #endif - - return(0); + + return (0); } int -HCHier_SendToSiblings(struct sockaddr_in *src, HCUpdate *update, - int msgtype, int siblingtype) +hintCacheHierSendToSiblings(struct sockaddr_in *src, HintCacheUpdate * update, + int msgtype, int siblingtype) { -#ifdef USE_DYNAMIC_HIERARCHY +#if USE_DYNAMIC_HIERARCHY int stillHave; int pIndex, cIndex; int iAmRoot, iAmLeaf; @@ -733,835 +731,25 @@ peer *e; #endif -#ifdef USE_DYNAMIC_HIERARCHY - pIndex = HCHier_ParentQIndex(&update->entry.key, &iAmRoot); - cIndex = HCHier_ChildQIndex(&update->entry.key, iAmRoot, &iAmLeaf); - if(!iAmLeaf){ - assert(cIndex < HCHier_NChildrenQs()); - HCNet_Enqueue(&childrenOutgoingA[cIndex], msgtype, - &update->entry, update->hopcount+1); +#if USE_DYNAMIC_HIERARCHY + pIndex = hintCacheHierParentQIndex(&update->entry.key, &iAmRoot); + cIndex = hintCacheHierChildQIndex(&update->entry.key, iAmRoot, &iAmLeaf); + if (!iAmLeaf) { + assert(cIndex < hintCacheHierNChildrenQs()); + hintCacheNetEnqueue(&childrenOutgoingA[cIndex], msgtype, + &update->entry, update->hopcount + 1); } #else for (e = getFirstPeer(); e; e = getNextPeer(e)) { if (e->in_addr.sin_addr.s_addr != src->sin_addr.s_addr - || e->http_port != src->sin_port) { + || e->http_port != src->sin_port) { if (siblingtype == PEER_NONE || e->type == siblingtype) - HCNet_Enqueue(&e->hcoutq, msgtype, &update->entry, - update->hopcount + 1); + hintCacheNetEnqueue(&e->hcoutq, msgtype, &update->entry, + update->hopcount + 1); } } #endif - return(0); -} - - -#ifdef DOTEST -/* - *------------------------------------------------------------------ - * - * HCHier_selfTest -- - * - * description. - * - * Arguments: - * type1 arg1 -- description. - * - * Results: - * None. - * - * Side effects: - * None. - * - *---------------------------------------------------4.24.1998----------- - */ -void -HCHier_selfTest() -{ - HCNodelist_SelfTest(); - HCPlax_SelfTest(); - - /* - * Note: - * HCHier_testNetwork() gets called repeatedly elsewhere (from HCTimer) - * not from normal self test routines because it needs the - * network to be working, so it needs to "yield" to main event - * loop. - */ - -#ifdef DOTEST_NOTYET - char *testHier = "testHierarchyFile"; - char *testBadPath = "/nonexistantFileName"; - char *testBadFile = "testHierarchyFile.Bad"; - char *testLoopFile = "testHierarchyFile.loop"; - char *testBadChildrenFile = "testHierarchyFile.badChildren"; - - HCHier h; - NodeId myId, expect; - struct sockaddr *s; - NodeId n, n1, n2; - - printf("HCHier_selfTest()."); - - NodeId_Init(&myId, 0x80536F03, 2); - s = NodeId_copyAsSockAddr(&myId); - - assert(HCHier_Init(&h, testBadPath, s) == -1); - assert(HCHier_Init(&h, testHier, s) == 0); - assert(HCHier_nChildren(&h) == 3); - assert(HCHier_nParents(&h) == 1); - - /* - * Test children - */ - n = HCHier_getChild(&h, 0); - NodeId_Init(&expect, 0x80536F03, 5); - assert(!NodeId_Compare(&n, &expect)); - n = HCHier_getChild(&h, 1); - NodeId_Init(&expect, 0x80536F03, 4); - assert(!NodeId_Compare(&n, &expect)); - n = HCHier_getChild(&h, 2); - NodeId_Init(&expect, 0x80536F03, 3); - assert(!NodeId_Compare(&n, &expect)); - - /* - * Test parents - */ - n = HCHier_getParent(&h, 0); - NodeId_Init(&expect, 0x80536F03, 1); - assert(!NodeId_Compare(&n, &expect)); - - - /* - * Test distance - */ - NodeId_Init(&n1, 0x80536F03, 0); - NodeId_Init(&n2, 0x80536F03, 1); - assert(HCHier_compareDistanceFromMe(&h, n1, n2) > 0); - assert(HCHier_compareDistanceFromMe(&h, n2, n1) < 0); - - NodeId_Init(&n1, 0x80536F03, 5); - NodeId_Init(&n2, 0x80536F03, 6); - assert(HCHier_compareDistanceFromMe(&h, n1, n2) < 0); - assert(HCHier_compareDistanceFromMe(&h, n2, n1) > 0); - - NodeId_Init(&n1, 0x80536F03, 3); - NodeId_Init(&n2, 0x80536F03, 4); - assert(HCHier_compareDistanceFromMe(&h, n1, n2) == 0); - assert(HCHier_compareDistanceFromMe(&h, n2, n1) == 0); - - /* - * My node id - */ - n = HCHier_myNodeId(&h); - assert(!NodeId_Compare(&n, &myId)); - - - /* - * Subtree - */ - NodeId_Init(&n1, 0x80536F03, 1); - assert(!HCHier_inMySubtree(&h, n1)); - NodeId_Init(&n1, 0x80536F03, 2); - assert(!HCHier_inMySubtree(&h, n1)); - NodeId_Init(&n1, 0x80536F03, 4); - assert(HCHier_inMySubtree(&h, n1)); - NodeId_Init(&n1, 0x80536F03, 6); - assert(HCHier_inMySubtree(&h, n1)); - - HCHier_Destroy(&h); - printf("\nHCHier -- trying bad input files. Expect warnings\n"); - printf("\nHCHier -- bad input file (bad format): "); - assert(HCHier_Init(&h, testBadFile, s) == -1); - printf("\nHCHier -- bad input file (loop): "); - assert(HCHier_Init(&h, testLoopFile, s) == -1); - printf("\nHCHier -- bad input file (missing children): "); - assert(HCHier_Init(&h, testBadChildrenFile, s) == -1); - - printf("..OK\n"); -#endif /* DOTEST_NOTYET */ -} - - - -/* - *------------------------------------------------------------------ - * - * HCHier_testNetwork -- - * - * Test that we can create a hierarchy with another - * node on the network. - * - * Arguments: - * type1 arg1 -- description. - * - * Results: - * None. - * - * Side effects: - * None. - * - *-------------------------------------------------4.19.1998--------- - */ -void -HCHier_testNetwork(void) -{ - peer *p; - int ipeer = 0; - static int phase = BARRIER_START; - char tag[256]; - -#ifdef USE_DYNAMIC_HIERARCHY - - if(phase == BARRIER_START){ - printf("XXX Testing hint cache network stuff \n"); - - for (p = getFirstPeer(); p; p = getNextPeer(p)) { - printf("Peer %d: %s %s\n", ipeer, p->host, inet_ntoa(p->in_addr.sin_addr)); - ipeer++; - } - - printf("XXX My hostname %s address %s\n", getMyHostname(), - inet_ntoa(Config.Sockaddr.http->s.sin_addr)); - - clearTestBarrier(); - phase = BARRIER_READY; - return; - } - - if(phase == BARRIER_READY){ - if(!doTestBarrier(BARRIER_READY)){ - return; - } - phase = BARRIER_JOIN; - return; - } - - if(phase == BARRIER_JOIN){ - if(!doTestBarrier(BARRIER_JOIN)){ - return; - } - phase = BARRIER_JOIN2; - return; - } - - if(phase == BARRIER_JOIN2){ - if(!doTestBarrier(BARRIER_JOIN2)){ - return; - } - phase = BARRIER_NODELIST; - return; - } - - if(phase == BARRIER_NODELIST){ - for(p = getFirstPeer(); p; p = getNextPeer(p)){ - testFindPeer(p); - } - if(!doTestBarrier(BARRIER_NODELIST)){ - return; - } - phase = BARRIER_CREATE_STUFF; - return; - } - - if(phase == BARRIER_CREATE_STUFF){ - sprintf(tag, "%s", inet_ntoa(Config.Sockaddr.http.s_addr)); - testCreateStuff(tag); - testCreateStuff("shared"); - if(!doTestBarrier(BARRIER_CREATE_STUFF)){ - return; - } - phase = BARRIER_CREATE_STUFF2; - } - - if(phase == BARRIER_CREATE_STUFF2){ - /* - * Just making sure that data from last phase makes it around - * the system - */ - if(!doTestBarrier(BARRIER_CREATE_STUFF2)){ - return; - } - phase = BARRIER_CREATE_STUFF3; - } - - if(phase == BARRIER_CREATE_STUFF3){ - /* - * Just making sure that data from last phase makes it around - * the system - */ - static int passes = 0; - if(passes < 2){ - passes++; - return; - } - if(!doTestBarrier(BARRIER_CREATE_STUFF3)){ - return; - } - phase = BARRIER_PLAX; - } - - - if(phase == BARRIER_PLAX){ - testPlax(); - if(!doTestBarrier(BARRIER_PLAX)){ - return; - } - phase = BARRIER_FIND; - return; - } - - if(phase == BARRIER_FIND){ - testFind(); - if(!doTestBarrier(BARRIER_FIND)){ - return; - } - phase = BARRIER_LAST; - return; - } - - if(phase == BARRIER_LAST){ - if(!doTestBarrier(BARRIER_LAST)){ - return; - } - phase = BARRIER_DONE; - return; - } - - if(phase == BARRIER_DONE){ - if(!doTestBarrier(BARRIER_DONE)){ - return; - } - HCHier_selfTestDone = 1; - printf("HCHier multi-node selfTest Done\n"); - return; - } - -#endif /* USE_DYNAMIC_HIERARCHY */ -} - -/* - *------------------------------------------------------------------ - * - * doTestBarrier -- - * - * Write the flag to the barrier and then read - * the flag from the barrier files written - * by the other nodes. - * - * If all of the other barrier files show - * the expected flag or later, return true - * else return false. - * - * Arguments: - * type1 arg1 -- description. - * - * Results: - * None. - * - * Side effects: - * None. - * - *---------------------------------------------------4.19.1998-------- - */ -static int -doTestBarrier(int barrier) -{ - static int lastBarrier = 0; - - if(barrier != lastBarrier){ - printf("XXX To barrier %d\n", barrier); - lastBarrier = barrier; - } - writeTestBarrier(barrier); - return readTestBarrier(barrier); -} - -/* - *------------------------------------------------------------------ - * - * writeBarrier -- - * - * Write the specified flag to my barrier file - * - * Arguments: - * type1 arg1 -- description. - * - * Results: - * None. - * - * Side effects: - * None. - * - *---------------------------------------------------------4.19.1998-- - */ -static void -writeTestBarrier(int barrier) -{ - int fd; - char name[128]; - char data[128]; - int len, got; - - sprintf(name, "%s-%s", "tmp.barrier", getMyHostname()); - fd = open(name, O_WRONLY|O_CREAT|O_TRUNC, 0666); - if(fd < 0){ - perror("HCHier: open barrier"); - assert(0); - } - sprintf(data, "FLAG %d\n", barrier); - len = strlen(data); - got = write(fd, data, len); - assert(got == len); - close(fd); - return; -} - -/* - *------------------------------------------------------------------ - * - * readBarrier -- - * - * Read the neighbors' barrier files. If all neighbors - * show a flag with the value expected or one greater, - * return true. (One greater means -- we all reached - * this barrier, but the other node is now waiting at - * the next one.) - * Otherwise, return false. - * - * Arguments: - * type1 arg1 -- description. - * - * Results: - * None. - * - * Side effects: - * None. - * - *--------------------------------------------------------4.19.1998---- - */ -static int -readTestBarrier(int barrier) -{ - int fd; - char name[128]; - char data[128]; - int got; - peer *p; - int bval; - - for(p = getFirstPeer(); p; p = getNextPeer(p)){ - sprintf(name, "%s-%s", "tmp.barrier", p->host); - fd = open(name, O_RDONLY); - if(fd < 0){ /* other may not have gotten to barrier yet */ - return 0; - } - got = read(fd, data, 128); - if(got <= 0){ - close(fd); - return 0; - } - data[got]= '\0'; - if(sscanf(data, "FLAG %d", &bval) != 1){ - close(fd); - return 0; - } - if((bval != barrier) && (bval != barrier + 1) - && (barrier != BARRIER_LAST || bval != BARRIER_DONE)){ - close(fd); - return 0; - } - close(fd); - } - return 1; + return (0); } -/* - *------------------------------------------------------------------ - * - * clearTestBarrier -- - * - * Wipe out all test barriers. The first time I go through, - * I wipe out all barriers. This is OK. Even if others - * have written BARRIER_START to them, they will re-write - * the next time they come back. - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *--------------------------------------------------4.24.1998---------- - */ -static void -clearTestBarrier() -{ - int fd; - char name[128]; - peer *p; - - for(p = getFirstPeer(); p; p = getNextPeer(p)){ - sprintf(name, "%s-%s", "tmp.barrier", p->host); - fd = open(name, O_WRONLY|O_TRUNC|O_CREAT); - if(fd >= 0){ - close(fd); - } - } -} - -/* - *------------------------------------------------------------------ - * - * testFindPeer -- - * - * Test routine. Find the specified peer as a node - * on the nodelist or assert(0); - * - * Arguments: - * type1 arg1 -- description. - * - * Results: - * None. - * - * Side effects: - * None. - * - *------------------------------------------------------------------ - */ -static void -testFindPeer(peer *p) -{ - HCNLIter i; - struct sockaddr_in sin; - - for(HCNodeList_IterStart(&i); - HCNodeList_IterCheck(i); - HCNodeList_IterNext(&i)){ - if(HCNodeList_IterGetAddr(i, &sin)){ - printf("XXX testFindPeer() node found on node list %s\n", - inet_ntoa(sin.sin_addr)); - if(p->in_addr.sin_addr.s_addr == sin.sin_addr.s_addr){ - return; - } - } - else{ - printf("XXX testFindPeer() node found on node list (but it has left) %s\n", - inet_ntoa(sin.sin_addr)); - assert(0); - } - } - assert(0); /* Not found but should have been */ -} - - -/* - *------------------------------------------------------------------ - * - * testPlax -- - * - * For a set of objects, calculate who are parent/children - * should be by hand and see if things match expected. - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *----------------------------------------------------4.24.1998-------- - */ -static void -testPlax(void) -{ - int iurl; - char url[100]; - URLKey objKey; - int otherMatch, maxMatch, myMatch; - GenericKey otherKey; - HCNLIter i; - struct sockaddr_in sin, gotSin, *childrenA = NULL; - int qNdx, amIRoot; - int count = 0; - int iAmLeaf, nChildren; - - /* - * By now, we should have created a bunch of dummy objects and - * therefore found out about neighbors' dummy objects and - * more importantly found out about our neighbors existance. - * So, HCHier_CheckIfChild should work. - */ - for(HCNodeList_IterStart(&i); - HCNodeList_IterCheck(i); - HCNodeList_IterNext(&i)){ - if(HCNodeList_IterGetAddr(i, &sin)){ - /* Should be initialized from DNS by the time we get here */ - assert(sin.sin_addr.s_addr != 0); - assert(HCHier_CheckIfChild(&sin)); - count++; - } - } - - if(count != 1){ - printf("Skipping HCHier::testPlax b/c test only works in 2-node system\n"); - return; - } - - - /* - * Now, see if the system can figure out which nodes are our - * parents and which are our children for different objects. - */ - for(iurl = 0; iurl < 100; iurl++){ - sprintf(url, "http://www.cs.utexas.edu/%d", iurl); - URLKey_Init(&objKey, url); - - myMatch = HCPlax_matchBits(HCPlax_myNodeKey(), objKey.key); - maxMatch = myMatch; - - for(HCNodeList_IterStart(&i); - HCNodeList_IterCheck(i); - HCNodeList_IterNext(&i)){ - if(HCNodeList_IterGetAddr(i, &sin)){ - /* Should be initialized from DNS by the time we get here */ - assert(sin.sin_addr.s_addr != 0); - otherKey = NodeKK_Key(&sin); - otherMatch = HCPlax_matchBits(otherKey, objKey.key); - if(otherMatch > maxMatch){ - maxMatch = otherMatch; - } - - if(otherMatch > myMatch){ - if(otherMatch == maxMatch){ - /* - * Parents - */ - assert(HCHier_CheckIfParent(objKey, &sin)); - qNdx = HCHier_ParentQIndex(&objKey, &amIRoot); - assert(!amIRoot); - assert(!HCHier_GetParentAddr(qNdx, &gotSin)); - assert(!SINCMP(&gotSin, &sin)); - /* - * Children - */ - qNdx = HCHier_ChildQIndex(&objKey, amIRoot, &iAmLeaf); - assert(iAmLeaf); - } - else{ - assert(0); /* Tests work only for 2-node case right now */ - } - } - else if(otherMatch == myMatch){ - if(otherMatch == maxMatch){ - if(HCPlax_myNodeKey() > otherKey){ - /* - * I am root - */ - qNdx = HCHier_ParentQIndex(&objKey, &amIRoot); - assert(amIRoot); - qNdx = HCHier_ChildQIndex(&objKey, amIRoot, &iAmLeaf); - assert(!iAmLeaf); - nChildren = HCHier_GetChildAddrs(qNdx, &childrenA); - assert(nChildren == 1); /* Tests work only for 2-node case */ - assert(!SINCMP(&sin, &childrenA[0])); - xfree(childrenA); - } - else{ - /* - * Other node is root - */ - assert(HCHier_CheckIfParent(objKey, &sin)); - qNdx = HCHier_ParentQIndex(&objKey, &amIRoot); - assert(!amIRoot); - assert(!HCHier_GetParentAddr(qNdx, &gotSin)); - assert(!SINCMP(&gotSin, &sin)); - qNdx = HCHier_ChildQIndex(&objKey, amIRoot, &iAmLeaf); - assert(iAmLeaf); - } - } - else{ - assert(0); /* Tests work only for 2-node case right now */ - } - } - else{ - assert(otherMatch < myMatch); - if(myMatch == maxMatch){ - /* - * I am root (test only works in 2-node case) - */ - qNdx = HCHier_ParentQIndex(&objKey, &amIRoot); - assert(amIRoot); - qNdx = HCHier_ChildQIndex(&objKey, amIRoot, &iAmLeaf); - assert(!iAmLeaf); - nChildren = HCHier_GetChildAddrs(qNdx, &childrenA); - assert(nChildren == 1); /* Tests work only for 2-node case */ - assert(!SINCMP(&sin, &childrenA[0])); - xfree(childrenA); - } - else{ - assert(0); /* Tests work only for 2-node case right now */ - } - } - } - } - } -} - - -/* - *------------------------------------------------------------------ - * - * testCreateStuff -- - * - * Create and advertise a bunch of random objects. This is just - * to cause communication so that nodes learn about - * one another. We will never actually use these objects. - * - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *-----------------------------------------------------4.28.1998------ - */ -static const int STUFF_COUNT = 1000; - -static void -testCreateStuff(char *tag) -{ - int ii; - char name[128]; - - for(ii = 0; ii < STUFF_COUNT; ii++){ - sprintf(name, "http://foo.www.cs.utexas.edu/self-test-hchier/%d/%s\n", - ii, tag); - HCinformLocalCopy(name); - } -} - - -/* - *------------------------------------------------------------------ - * - * testFind -- - * - * See if a bunch of items are where we expect them to be. - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *---------------------------------------------------5.4.1998--------- - */ -static void -testFind(void) -{ - char tag[256]; - struct sockaddr_in sin; - HCNLIter i; - - /* - * The local stuff should NOT be found in the local index - * by convention. - */ - sprintf(tag, "%s", inet_ntoa(Config.Sockaddr.http->s.sin_addr); - testFindStuff(tag, NULL); - - /* - * Check to find the remote stuff - */ - for(HCNodeList_IterStart(&i); - HCNodeList_IterCheck(i); - HCNodeList_IterNext(&i)){ - if(HCNodeList_IterGetAddr(i, &sin)){ - /* Should be initialized from DNS by the time we get here */ - assert(sin.sin_addr.s_addr != 0); - sprintf(tag, "%s", inet_ntoa(sin.sin_addr)); - testFindStuff(tag, &sin); - } - } - - /* - * Shared stuff should be local to everyone and therefore - * not found - */ - testFindStuff("shared", NULL); -} - -/* - *------------------------------------------------------------------ - * - * testFindStuff -- - * - * See if a bunch of items are where we expect them to be. - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *-----------------------------------------------------5.4.1998------- - */ -static void -testFindStuff(char *tag, const struct sockaddr_in *expect) -{ - int ii; - char name[128]; - struct sockaddr_in found; - static float threshold = 0.05; /* Tolerate at most 5% collisions, etc */ - static int missCount = 0; - - for(ii = 0; ii < STUFF_COUNT; ii++){ - sprintf(name, "http://foo.www.cs.utexas.edu/self-test-hchier/%d/%s\n", - ii, tag); - if(HCfindNearest(name, &found) == NULL){ - if(expect != NULL){ - /* - * Miss could be from bug or could be due to limited - * associativity and/or size. See how many misses we get - * and decide if that is too many - */ - printf("HCHier warning: unexpected miss (could be cache effect)\n"); - missCount++; - } - } - else{ - if(expect == NULL){ - assert(0); /* found something we didn't expect to find */ - } - else if(SINCMP(expect, &found)){ - assert(expect != NULL); - /* - * Miss - found data but not where expected. - */ - assert(0); - } - } - } - if(missCount > threshold * STUFF_COUNT){ - /* too many misses */ - assert(0); - } - missCount = 0; -} -#endif /* DOTEST */ Index: squid/src/HintCacheNet.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCacheNet.c,v retrieving revision 1.1.2.2 retrieving revision 1.1.2.3 diff -u -r1.1.2.2 -r1.1.2.3 --- squid/src/HintCacheNet.c 7 Dec 2001 23:25:31 -0000 1.1.2.2 +++ squid/src/HintCacheNet.c 21 May 2002 02:46:41 -0000 1.1.2.3 @@ -1,7 +1,7 @@ /* - * $Date: 2001/12/07 23:25:31 $ $Id: HintCacheNet.c,v 1.1.2.2 2001/12/07 23:25:31 jkay Exp $ + * $Date: 2002/05/21 02:46:41 $ $Id: HintCacheNet.c,v 1.1.2.3 2002/05/21 02:46:41 jkay Exp $ * - * DEBUG: section 55 Hint cache networking. + * DEBUG: section 87 Hint cache networking. * AUTHOR: Mike Dahlin, UT Austin, 1998 * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ @@ -33,173 +33,178 @@ * Computer Sciences Department * University of Texas at Austin * - * HCNet --- Simple send interface built on squid async send stuff. + * hintCacheNet --- Simple send interface built on squid async send stuff. *------------------------------------------------------------------ */ #include "squid.h" #include -#define HCNET_DEBUG 55 +#define HCNET_DEBUG 87 #define RECV_DEBUG(type, u, hdr, src) \ - debug(HCNET_DEBUG, 2, "Got %s: 0x%x at <%s,%d> from <%s,%d>\n", \ + debug (HCNET_DEBUG, 2) ("Got %s: 0x%x at <%s,%d> from <%s,%d>\n", \ (type), *(int *) &(u)->entry.key.key, \ inet_ntoa((u)->entry.ipaddr), (u)->entry.port, \ inet_ntoa((src)->sin_addr), (hdr)->httpport) -static void enqueueBytes(HCNet *n, char *data, int nbytes); -static int copyToLocal(HCUpdate *updatesA, char *data, int len, - int oneUpdateSize); -static void clear(HCNet *n); -static void updateHierarchy(HCUpdate *updatesA, int nupdates, - struct sockaddr_in *source); -static void suppress(HCUpdate *updateA, int nupdates); +static void enqueueBytes(HintCacheNet * n, char *data, int nbytes); +static int copyToLocal(HintCacheUpdate * updatesA, char *data, int len, + int oneUpdateSize); +static void clear(HintCacheNet * n); +static void updateHierarchy(HintCacheUpdate * updatesA, int nupdates, + struct sockaddr_in *source); +static void suppress(HintCacheUpdate * updateA, int nupdates); static void scoldParent(struct sockaddr_in *parent); void -HCNet_Init(HCNet *n) +hintCacheNetInit(HintCacheNet * n) { #ifdef DOTEST - n->testMode = 0; - n->testCount = 0; + n->testMode = 0; + n->testCount = 0; #endif - clear(n); + clear(n); } static void -clear(HCNet *n) +clear(HintCacheNet * n) { - HCNetHeader hdr; - const char *url = "route://updates"; - int flags = 0; - - assert(n); - - /* Set up entry with request */ - EBIT_SET(flags, REQ_CACHABLE); - EBIT_SET(flags, ENTRY_SPECIAL); /* formerly set KEEP_INMEM */ -/* EBIT_SET(flags, DONT_FREE_FOR); */ - n->sendBuffer = storeCreateEntry(url, url, NULL, 0, flags, METHOD_GET); - n->sendBuffer->mem_obj->request = - requestLink(urlParse(METHOD_GET, (char *) url)); - - n->sendLength = 0; - - n->state = HC_filling; - - /* Prepare header for next transmission */ - hdr.httpport = htons(Config.Port.http); - hdr.updlen = htons(sizeof(Net_HCUpdate)); - enqueueBytes(n, (char *) &hdr, sizeof(hdr)); + HintCacheNetHeader hdr; + const char *url = "route://updates"; + request_flags rflags; + StoreEntry *entry; + + assert(n); + + /* Set up entry with request */ + *(unsigned int *) &rflags = 0; + rflags.cachable = 1; + entry = storeCreateEntry(url, url, rflags, METHOD_GET); + n->sendBuffer = entry; + EBIT_SET(entry->flags, ENTRY_SPECIAL); /* formerly set KEEP_INMEM */ +/* EBIT_SET(entry->flags, DONT_FREE_FOR); */ + n->sendBuffer->mem_obj->request = + requestLink(urlParse(METHOD_GET, (char *) url)); + + n->sendLength = 0; + + n->state = HC_filling; + + /* Prepare header for next transmission */ + hdr.httpport = htons(Config.Sockaddr.http->s.sin_port); + hdr.updlen = htons(sizeof(HintCacheUpdateNet)); + enqueueBytes(n, (char *) &hdr, sizeof(hdr)); } -void HCNet_Destroy(HCNet *n) +void +hintCacheNetDestroy(HintCacheNet * n) { - storeRelease(n->sendBuffer); - n->state = HC_destroyed; + storeRelease(n->sendBuffer); + n->state = HC_destroyed; } -void -HCNet_Enqueue(HCNet *n, int action, HCEntry *entry, int hopcount) +void +hintCacheNetEnqueue(HintCacheNet * n, int action, HintCacheEntry * entry, int hopcount) { - HCUpdate update; - Net_HCUpdate netUpdate; + HintCacheUpdate update; + HintCacheUpdateNet netUpdate; #ifdef DOTEST - if(n->testMode){ - n->testCount++; - return; - } + if (n->testMode) { + n->testCount++; + return; + } #endif - debug(HCNET_DEBUG, 4, - "HCNet_Enqueue onto 0x%x (action %d) (entry.key %llx entry.ipaddr %s port %d)\n", + debug(HCNET_DEBUG, 4) + ("HCNet_Enqueue onto 0x%x (action %d) (entry.key %llx entry.ipaddr %s port %d)\n", n, action, entry->key.key, inet_ntoa(entry->ipaddr), entry->port); - HCUpdate_Init(&update, action, entry, hopcount); - Net_HCUpdate_Init(&netUpdate, &update); - enqueueBytes(n, (char *)&netUpdate, sizeof(Net_HCUpdate)); + hintCacheUpdateInit(&update, action, entry, hopcount); + hintCacheUpdateNetInit(&netUpdate, &update); + enqueueBytes(n, (char *) &netUpdate, sizeof(HintCacheUpdateNet)); } static void -enqueueBytes(HCNet *n, char *data, int nbytes) +enqueueBytes(HintCacheNet * n, char *data, int nbytes) { - static enqreentrancy = 0; + static enqreentrancy = 0; - assert(n->state == HC_filling); - assert(!enqreentrancy); - ++enqreentrancy; - n->sendLength += nbytes; - storeAppend(n->sendBuffer, data, nbytes); - --enqreentrancy; + assert(n->state == HC_filling); + assert(!enqreentrancy); + ++enqreentrancy; + n->sendLength += nbytes; + storeAppend(n->sendBuffer, data, nbytes); + --enqreentrancy; } int -HCNet_bytesReady(HCNet *n) +hintCacheNetBytesReady(HintCacheNet * n) { - return n->sendLength; + return n->sendLength; } void -HCNet_Complete(HCNet *n) +hintCacheNetComplete(HintCacheNet * n) { - assert(n); - assert(n->state == HC_filling); - n->state = HC_full; - HCFinishHeader(n->sendBuffer); - storeComplete(n->sendBuffer); + assert(n); + assert(n->state == HC_filling); + n->state = HC_full; + hintCacheFinishHeader(n->sendBuffer); + storeComplete(n->sendBuffer); } void -HCNet_SendTo(HCNet *n, struct sockaddr_in *dest) +hintCacheNetSendTo(HintCacheNet * n, struct sockaddr_in *dest) { - assert(n->state == HC_full); - assert(n->sendLength > sizeof(HCNetHeader)); - debug(HCNET_DEBUG, 2, "HCNet_SendTo: sending routes on 0x%x to <%s,%d>\n", + assert(n->state == HC_full); + assert(n->sendLength > sizeof(HintCacheNetHeader)); + debug(HCNET_DEBUG, 2) ("HCNet_SendTo: sending routes on 0x%x to <%s,%d>\n", n, inet_ntoa(dest->sin_addr), dest->sin_port); - putSend(n->sendBuffer, dest, NULL, NULL, 0, 0); + putSend(n->sendBuffer, dest, NULL, NULL, 0); } void -HCNet_Done(HCNet *n) +hintCacheNetDone(HintCacheNet * n) { - StoreEntry *entry = n->sendBuffer; - - assert(n->state == HC_full); - - EBIT_CLR(entry->flag, KEEP_INMEM); - EBIT_SET(entry->flag, RELEASE_REQUEST); - storeUnlockObject(entry); - - clear(n); + StoreEntry *entry = n->sendBuffer; + + assert(n->state == HC_full); + + EBIT_CLR(entry->flags, ENTRY_SPECIAL); /* formerly KEEP_INMEM flag */ + + EBIT_SET(entry->flags, RELEASE_REQUEST); + storeUnlockObject(entry); + + clear(n); } #ifdef DOTEST void -HCNet_SetTestMode(HCNet *n) +hintCacheNetSetTestMode(HintCacheNet * n) { - n->testMode = 1; - n->testCount = 0; + n->testMode = 1; + n->testCount = 0; } int -HCNet_GetTestCount(HCNet *n) +hintCacheNetGetTestCount(HintCacheNet * n) { - return n->testCount; + return n->testCount; } #endif /* DOTEST */ /* *------------------------------------------------------------------ * - * HCNet_DataArrives -- + * hintCacheNetDataArrives -- * * Action to take when messages arrive from network. * * Arguments: - * char *data -- unaligned buffer of network-formatted HCNetUpdates + * char *data -- unaligned buffer of network-formatted hintCacheNetUpdates * int len -- number of bytes in that buffer * struct sockaddr *source -- who sent the buffer * @@ -212,11 +217,11 @@ *------------------------------------------------4.2.1998------------ */ void -HCNet_DataArrives(char *data, int len, HCNetHeader *hdr, - struct sockaddr_in *source) +hintCacheNetDataArrives(char *data, int len, HintCacheNetHeader * hdr, + struct sockaddr_in *source) { struct sockaddr_in sin; - HCUpdate *updatesA; + HintCacheUpdate *updatesA; int nupdates; int iupdate; @@ -228,12 +233,12 @@ assert(source->sin_family == AF_INET); assert(hdr->updlen >= HCU_MINLEN); - debug(HCNET_DEBUG, 3, - "HCDataArrives: got %d bytes of stuff (probably %d updates xtra=%d\n", - len, len / hdr->updlen, len % hdr->updlen); + debug(HCNET_DEBUG, 3) + ("HintCacheDataArrives: got %d bytes of stuff (probably %d updates xtra=%d\n", + len, len / hdr->updlen, len % hdr->updlen); /* Copy to alignment buffer and local format */ - updatesA = (HCUpdate *)xmalloc(len); + updatesA = (HintCacheUpdate *) xmalloc(len); nupdates = copyToLocal(updatesA, data, len, hdr->updlen); /* @@ -248,116 +253,116 @@ source->sin_port = hdr->httpport; updateHierarchy(updatesA, nupdates, source); - + /* * Prefetch if we have a large number of requests. * Idea is to tell OS to start bringing in the pages * that we are about to touch. */ - if (nupdates >= HCD_PREFETCH_THRESH){ - HCDisk_prefetch(hcDisk, updatesA, nupdates); + if (nupdates >= HCD_PREFETCH_THRESH) { + hintCacheDisk_prefetch(hcDisk, updatesA, nupdates); } /* * OK. Now we can start processing the messages. */ - for(iupdate = 0; iupdate < nupdates; iupdate++){ - switch(updatesA[iupdate].action){ - case HC_InvalToParent: - RECV_DEBUG("HC_InvalToParent", &updatesA[iupdate], hdr, source); - hcprop_handleInvalToParent(&updatesA[iupdate], source, 0); - break; - - case HC_InvalToChild: - RECV_DEBUG("HC_InvalToChild", &updatesA[iupdate], hdr, source); - hcprop_handleInvalToChild(&updatesA[iupdate], source, 0); - break; - - case HC_InformToParent: - RECV_DEBUG("HC_InformToParent", &updatesA[iupdate], hdr, source); - hcprop_handleInformToParent(&updatesA[iupdate], source, 0); - break; - - case HC_InformToChild: - RECV_DEBUG("HC_InformToChild", &updatesA[iupdate], hdr, source); - hcprop_handleInformToChild(&updatesA[iupdate], source, 0); - break; - - case HC_Join: - /* New cache node! Add to list. */ - RECV_DEBUG("HC_Join", &updatesA[iupdate], hdr, source); - /* - * MDD 7.18.1998 - * When a node relays a join/leave to us, make sure - * that we send future joins to that node by adding - * that node to the peer list if it's not already there. - */ - sin.sin_family = AF_INET; - sin.sin_addr = source->sin_addr; - sin.sin_port = hdr->httpport; - HCHier_updateMembershipNeighbor(&sin, NEIGHBOR_ADD); - - /* - * Now update local state for join - */ - sin.sin_family = AF_INET; - sin.sin_addr = updatesA[iupdate].entry.ipaddr; - sin.sin_port = updatesA[iupdate].entry.port; - HCHier_newNode(&sin, updatesA[iupdate].hopcount, - updatesA[iupdate].entry.key.key); - break; - - case HC_Leave: - /* Cache node is either dead or has been detected dead. */ - RECV_DEBUG("HC_Leave", &updatesA[iupdate], hdr, source); - sin.sin_family = AF_INET; - sin.sin_addr = updatesA[iupdate].entry.ipaddr; - sin.sin_port = updatesA[iupdate].entry.port; - HCHier_delNode(&sin, updatesA[iupdate].hopcount, updatesA[iupdate].entry -.key.key); - - /* - * MDD 7.18.1998 - * When we receive a join from a node, make sure - * that we send future joins to that node by adding - * that node to the peer list if it's not already there. - */ - HCHier_updateMembershipNeighbor(source, NEIGHBOR_ADD); - /* - * MDD 7.18.1998 - * And the node we just heard about is gone, so it must - * no longer be a neighbor across which to propagate changes - * in membership. - */ - HCHier_updateMembershipNeighbor(&sin, NEIGHBOR_REMOVE); - - break; - - case HC_NotChild: - /* - * This message should have been handled and suppressed - * (by making it "HC_Ignore") in the updateHierarchy() code. - */ - RECV_DEBUG("HC_NotChild", &updatesA[iupdate], hdr, source); - assert(0); - break; - - case HC_Ignore: - /* This message was suppressed either because it is - * part of a loop or because it came from a node that - * thinks it is my parent but isnt. - */ - break; - - default: - /* Ignore bad messages */ - debug(HCNET_DEBUG, 1, - "HCHintCache: unknown update action %d from net\n", - updatesA[iupdate].action); - break; - } + for (iupdate = 0; iupdate < nupdates; iupdate++) { + switch (updatesA[iupdate].action) { + case HC_InvalToParent: + RECV_DEBUG("hintCache_InvalToParent", &updatesA[iupdate], hdr, source); + hcprop_handleInvalToParent(&updatesA[iupdate], source, 0); + break; + + case HC_InvalToChild: + RECV_DEBUG("hintCache_InvalToChild", &updatesA[iupdate], hdr, source); + hcprop_handleInvalToChild(&updatesA[iupdate], source, 0); + break; + + case HC_InformToParent: + RECV_DEBUG("hintCache_InformToParent", &updatesA[iupdate], hdr, source); + hcprop_handleInformToParent(&updatesA[iupdate], source, 0); + break; + + case HC_InformToChild: + RECV_DEBUG("hintCache_InformToChild", &updatesA[iupdate], hdr, source); + hcprop_handleInformToChild(&updatesA[iupdate], source, 0); + break; + + case HC_Join: + /* New cache node! Add to list. */ + RECV_DEBUG("hintCache_Join", &updatesA[iupdate], hdr, source); + /* + * MDD 7.18.1998 + * When a node relays a join/leave to us, make sure + * that we send future joins to that node by adding + * that node to the peer list if it's not already there. + */ + sin.sin_family = AF_INET; + sin.sin_addr = source->sin_addr; + sin.sin_port = hdr->httpport; + hintCacheHier_updateMembershipNeighbor(&sin, NEIGHBOR_ADD); + + /* + * Now update local state for join + */ + sin.sin_family = AF_INET; + sin.sin_addr = updatesA[iupdate].entry.ipaddr; + sin.sin_port = updatesA[iupdate].entry.port; + hintCacheHier_newNode(&sin, updatesA[iupdate].hopcount, + updatesA[iupdate].entry.key.key); + break; + + case HC_Leave: + /* Cache node is either dead or has been detected dead. */ + RECV_DEBUG("hintCache_Leave", &updatesA[iupdate], hdr, source); + sin.sin_family = AF_INET; + sin.sin_addr = updatesA[iupdate].entry.ipaddr; + sin.sin_port = updatesA[iupdate].entry.port; + hintCacheHier_delNode(&sin, updatesA[iupdate].hopcount, + updatesA[iupdate].entry.key.key); + + /* + * MDD 7.18.1998 + * When we receive a join from a node, make sure + * that we send future joins to that node by adding + * that node to the peer list if it's not already there. + */ + hintCacheHier_updateMembershipNeighbor(source, NEIGHBOR_ADD); + /* + * MDD 7.18.1998 + * And the node we just heard about is gone, so it must + * no longer be a neighbor across which to propagate changes + * in membership. + */ + hintCacheHier_updateMembershipNeighbor(&sin, NEIGHBOR_REMOVE); + + break; + + case HC_NotChild: + /* + * This message should have been handled and suppressed + * (by making it "HC_Ignore") in the updateHierarchy() code. + */ + RECV_DEBUG("HC_NotChild", &updatesA[iupdate], hdr, source); + assert(0); + break; + + case HC_Ignore: + /* This message was suppressed either because it is + * part of a loop or because it came from a node that + * thinks it is my parent but isnt. + */ + break; + + default: + /* Ignore bad messages */ + debug(HCNET_DEBUG, 1) + ("HCHintCache: unknown update action %d from net\n", + updatesA[iupdate].action); + break; + } } - + xfree(updatesA); } @@ -381,22 +386,22 @@ *-----------------------------------------------3.31.1998----------- */ static int -copyToLocal(HCUpdate *updatesA, char *data, int len, int oneUpdateSize) +copyToLocal(HintCacheUpdate * updatesA, char *data, int len, int oneUpdateSize) { - char *alignbuf; - int uoff; - Net_HCUpdate *nupdatep; - int ii; - - alignbuf = xmalloc(len); - memcpy(alignbuf, data, len); - - for (uoff = 0, ii = 0; uoff < len; uoff += oneUpdateSize, ii++) { - nupdatep = (Net_HCUpdate *) (alignbuf + uoff); - Net_HCUpdate_LocalFormat(nupdatep, &updatesA[ii]); - } - xfree(alignbuf); - return ii; + char *alignbuf; + int uoff; + HintCacheUpdateNet *nupdatep; + int ii; + + alignbuf = xmalloc(len); + memcpy(alignbuf, data, len); + + for (uoff = 0, ii = 0; uoff < len; uoff += oneUpdateSize, ii++) { + nupdatep = (HintCacheUpdateNet *) (alignbuf + uoff); + hintCacheUpdateNetLocalFormat(nupdatep, &updatesA[ii]); + } + xfree(alignbuf); + return ii; } /* @@ -422,19 +427,19 @@ *-----------------------------------------------4.1.1998------------- */ static void -suppress(HCUpdate *updateA, int nupdates) +suppress(HintCacheUpdate * updateA, int nupdates) { #ifdef NOTYET /* Need to fill this in */ int iupdate; - - for(iupdate = 0; iupdate < nupdates; iupdate++){ + + for (iupdate = 0; iupdate < nupdates; iupdate++) { if (stoppable update) { updateA[iupdate].action = HC_Ignore; } } #endif - + return; } @@ -468,46 +473,46 @@ *------------------------------------------------4.1.1998------------ */ static void -updateHierarchy(HCUpdate *updatesA, int nupdates, struct sockaddr_in *source) +updateHierarchy(HintCacheUpdate * updatesA, int nupdates, struct sockaddr_in *source) { - int iupdate; - int parentScolded = 0; + int iupdate; + int parentScolded = 0; - for(iupdate = 0; iupdate < nupdates; iupdate++){ - switch(updatesA[iupdate].action){ - case HC_InformToChild: - case HC_InvalToChild: - if(!HCHier_CheckIfParent(updatesA[iupdate].entry.key, source)){ - if(!parentScolded){ - scoldParent(source); - parentScolded = 1; - } - updatesA[iupdate].action = HC_Ignore; - } - break; - - case HC_InformToParent: - case HC_InvalToParent: -#if 1 /* XXX! - disabling parent&child lists */ - if(!HCHier_CheckIfChild(source)){ - HCHier_AddChild(source); - } + for (iupdate = 0; iupdate < nupdates; iupdate++) { + switch (updatesA[iupdate].action) { + case HC_InformToChild: + case HC_InvalToChild: + if (!HCHier_CheckIfParent(updatesA[iupdate].entry.key, source)) { + if (!parentScolded) { + scoldParent(source); + parentScolded = 1; + } + updatesA[iupdate].action = HC_Ignore; + } + break; + + case HC_InformToParent: + case HC_InvalToParent: +#if 1 /* XXX! - disabling parent&child lists */ + if (!hintCacheHier_CheckIfChild(source)) { + hintCacheHier_AddChild(source); + } #endif - break; + break; - case HC_NotChild: - HCHier_RemoveChild(source); - updatesA[iupdate].action = HC_Ignore; - break; - - - default: - /* - * Other messages don't affect hierarchy. Ignore them here. - */ - break; + case HC_NotChild: + hintCacheHier_RemoveChild(source); + updatesA[iupdate].action = HC_Ignore; + break; + + + default: + /* + * Other messages don't affect hierarchy. Ignore them here. + */ + break; + } } - } } /* @@ -516,7 +521,7 @@ * scoldParent -- * * Tell parent "I am not child". Need to use - * our own private HCNet queue since all of the + * our own private HintCacheNet queue since all of the * other queues are associated with the hierarchy * and this message is to tell someone they * are *not* in the hierarchy. @@ -535,26 +540,24 @@ static void scoldParent(struct sockaddr_in *parent) { - static int initialized = 0; - static HCNet netBuf; - static HCEntry dummyEntry; - static URLKey dummyKey; - - debug(HCNET_DEBUG, 7, "In scoldParent %s\n", inet_ntoa(parent->sin_addr)); - - if(!initialized){ - HCNet_Init(&netBuf); - URLKey_Init(&dummyKey, NULL); - HCEntry_Init(&dummyEntry, dummyKey, - &Config.Sockaddr.http->s, - squid_curtime); - initialized = 1; - } - - HCNet_Enqueue(&netBuf, HC_NotChild, &dummyEntry, 1); - HCNet_Complete(&netBuf); - HCNet_SendTo(&netBuf, parent); - HCNet_Done(&netBuf); - return; -} + static int initialized = 0; + static HintCacheNet netBuf; + static HintCacheEntry dummyEntry; + static URLKey dummyKey; + + debug(HCNET_DEBUG, 7) ("In scoldParent %s\n", inet_ntoa(parent->sin_addr)); + + if (!initialized) { + hintCacheNetInit(&netBuf); + URLKey_Init(&dummyKey, NULL); + hintCacheEntry_Init(&dummyEntry, dummyKey, + &Config.Sockaddr.http->s, squid_curtime); + initialized = 1; + } + hintCacheNetEnqueue(&netBuf, HC_NotChild, &dummyEntry, 1); + hintCacheNetComplete(&netBuf); + hintCacheNetSendTo(&netBuf, parent); + hintCacheNetDone(&netBuf); + return; +} Index: squid/src/HintCacheNodes.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCacheNodes.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/HintCacheNodes.c 20 Nov 2001 06:54:24 -0000 1.1.2.1 +++ squid/src/HintCacheNodes.c 21 May 2002 02:46:41 -0000 1.1.2.2 @@ -1,7 +1,7 @@ /* - * $Date: 2001/11/20 06:54:24 $ $Id: HintCacheNodes.c,v 1.1.2.1 2001/11/20 06:54:24 jkay Exp $ + * $Date: 2002/05/21 02:46:41 $ $Id: HintCacheNodes.c,v 1.1.2.2 2002/05/21 02:46:41 jkay Exp $ * - * DEBUG: section 60 List of known caches. + * DEBUG: section 88 List of known caches. * AUTHOR: Mike Dahlin, UT Austin, 1998 * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ @@ -65,53 +65,57 @@ * static void HCNodelist_OutcallJoin() _PARAMS((struct sockaddr_in sin)); * e.g. The nodelist promises to tell Plaxton when a new node joins. * - * static void HCNodelist_OutcallLeave() _PARAMS((struct sockaddr_in sin)); + * static void hintCacheNodelist_OutcallLeave() _PARAMS((struct sockaddr_in sin)); * The nodelist promises to tell Plaxton when a node leaves. */ -typedef struct HierNodeElem{ - List_Links links; /* MUST be first element of structure */ - struct sockaddr_in sin; - int action; /* HC_Join or HC_Leave */ - long long timestamp_ns; /* time of action */ -}HierNodeElem; +#define HCNODES_DEBUG 88 -static List_Links nodes; +typedef struct HierNodeElem +{ + dlink_node links; + struct sockaddr_in sin; + int action; /* HC_Join or HC_Leave */ + long long timestamp_ns; /* time of action */ +} +HierNodeElem; + +static dlink_list nodes; static int myStatus = HC_Leave; static void HierNodeElem_Init _PARAMS((HierNodeElem *, struct sockaddr_in *, - int action, long long timestamp_ns)); + int action, long long timestamp_ns)); static HierNodeElem *nodeFind(struct sockaddr_in *sin); static long long currentTimeNS(); -static void floodEvent(int action, struct sockaddr_in *source, - long long timeNS, int hopcount); +static void floodEvent(int action, struct sockaddr_in *source, + long long timeNS, int hopcount); -static void HCNodelist_OutcallHops(struct sockaddr_in *sin, - int hops, long long timeNS); -static void HCNodelist_OutcallJoin(struct sockaddr_in *sin, - int hops, long long timeNS); -static void HCNodelist_OutcallLeave(struct sockaddr_in *sin, - int hops, long long timeNS); +static void hintCacheNodelistOutcallHops(struct sockaddr_in *sin, + int hops, long long timeNS); +static void hintCacheNodelistOutcallJoin(struct sockaddr_in *sin, + int hops, long long timeNS); +static void hintCacheNodelistOutcallLeave(struct sockaddr_in *sin, + int hops, long long timeNS); static void printList(); static void -HierNodeElem_Init(HierNodeElem *e, struct sockaddr_in *sin, int action, - long long timestamp_ns) +HierNodeElem_Init(HierNodeElem * e, struct sockaddr_in *sin, int action, + long long timestamp_ns) { - assert(action == HC_Join || action == HC_Leave); - List_InitElement(&e->links); - e->sin = *sin; - e->action = action; - e->timestamp_ns = timestamp_ns; + assert(action == HC_Join || action == HC_Leave); + List_InitElement(&e->links); + e->sin = *sin; + e->action = action; + e->timestamp_ns = timestamp_ns; } /* *------------------------------------------------------------------ * - * HCNodeList_Init -- + * hintCacheNodeList_Init -- * * Constructor. * @@ -126,16 +130,16 @@ * *----------------------------------------------3.31.1998------------- */ -void -HCNodelist_Init (void) +void +hintCacheNodelistInit(void) { - List_Init(&nodes); + nodes.head = nodes.tail = 0; } /* *------------------------------------------------------------------ * - * HCNodeList_Destroy -- + * hintCacheNodeListDestroy -- * * Deallocate all elements in list * @@ -150,22 +154,23 @@ * *--------------------------------------------------3.31.1998------- */ -void -HCNodelist_Destroy (void) +void +hintCacheNodelist_Destroy(void) { - List_Links *item; - while(!List_IsEmpty(&nodes)){ - item = List_First(&nodes); - List_Remove(item); - free(item); - } + dlink_node *item; + + while (nodes.head) { + item = nodes.head; + dlinkDelete(item, &nodes); + xfree(item); + } } /* *------------------------------------------------------------------ * - * HCNodeList_LocalJoin -- + * hintCacheNodeListLocalJoin -- * * Do a local join. This tells the algorithm * to flood "join" messages to the neighbors. @@ -181,45 +186,45 @@ * *-----------------------------------------------------4.1.1998---- */ -void -HCNodelist_LocalJoin(void) +void +hintCacheNodelistLocalJoin(void) { - struct sockaddr_in *myId; - int hopcount; - long long timeNS; + struct sockaddr_in *myId; + int hopcount; + long long timeNS; #if 0 - HCEntry hcEntry; - HCUpdate update; - URLKey key; - int nbpl; - int ii; + HintCacheEntry hcEntry; + HintCacheUpdate update; + URLKey key; + int nbpl; + int ii; #endif - myStatus = HC_Join; + myStatus = HC_Join; - myId = &Config.Sockaddr.http->s; - timeNS = currentTimeNS(); - hopcount = 1; - floodEvent(HC_Join, myId, timeNS, hopcount); + myId = &Config.Sockaddr.http->s; + timeNS = currentTimeNS(); + hopcount = 1; + floodEvent(HC_Join, myId, timeNS, hopcount); #if 0 - /* "Priming" code */ - if (parentOutgoingA) { - nbpl = (HCPlax_bucketsPerLevel > 0) ? HCPlax_bucketsPerLevel : 256; - for(ii = 0; ii < nbpl; ii++) { - key.key = ii; - HCEntry_Init(&hcEntry, key, &Config.Sockaddr.http->s; - HCUpdate_Init(&update, HC_InvalToParent, &hcEntry, 1); - hcprop_handleInvalToParent(&update, 1); - } - } + /* "Priming" code */ + if (parentOutgoingA) { + nbpl = (hintCachePlax_bucketsPerLevel > 0) ? hintCachePlax_bucketsPerLevel : 256; + for (ii = 0; ii < nbpl; ii++) { + key.key = ii; + hintCacheEntry_Init(&hcEntry, key, &Config.Sockaddr.http->s); + hintCacheUpdate_Init(&update, HC_InvalToParent, &hcEntry, 1); + hcprop_handleInvalToParent(&update, 1); + } + } #endif } /* *------------------------------------------------------------------ * - * HCNodeList_LocalLeave -- + * hintCacheNodeListLocalLeave -- * * Do a local leave. This tells the algorithm * to flood "leave" messages to the neighbors. @@ -235,25 +240,25 @@ * *-----------------------------------------------------4.1.1998---- */ -void -HCNodelist_LocalLeave(void) +void +hintCacheNodelistLocalLeave(void) { - struct sockaddr_in *myId; - int hopcount; - long long timeNS; - - myStatus = HC_Leave; - myId = &Config.Sockaddr.http->s; - timeNS = currentTimeNS(); - hopcount = 1; - floodEvent(HC_Leave, myId, timeNS, hopcount); + struct sockaddr_in *myId; + int hopcount; + long long timeNS; + + myStatus = HC_Leave; + myId = &Config.Sockaddr.http->s; + timeNS = currentTimeNS(); + hopcount = 1; + floodEvent(HC_Leave, myId, timeNS, hopcount); } /* *------------------------------------------------------------------ * - * HCNodeList_getMyStatus -- + * hintCacheNodelistgetMyStatus -- * * Am I currently in or out? * @@ -269,16 +274,16 @@ *----------------------------------------------------4.1.1998-------- */ int -HCNodelist_myStatus(void) +hintCacheNodelistmyStatus(void) { - return myStatus; + return myStatus; } /* *------------------------------------------------------------------ * - * HCNodeList_NetJoin -- + * hintCacheNodelistNetJoin -- * * Process a "join" received from the network. * If this is a new node, a new action for a node, @@ -298,101 +303,99 @@ * *------------------------------------------------------7.19.1998---- */ -void -HCNodelist_NetJoin(struct sockaddr_in *sin, int hops, long long joinTimeNS) +void +hintCacheNodelistNetJoin(struct sockaddr_in *sin, int hops, long long joinTimeNS) { - HierNodeElem *h, *oldCopy; - int oldHops; - int foundOldJoin = 0; - int joinIsNewer; - - assert(sin); - /* Ignore if it's already on list and either (1) a newer record - * or (2) a current record and at least as close as this - * update. Also ignore if it is me! - * For simplicity, rather than update a record in place, remove - * it and add a new record to front of list. This should be better - * for performance, too, since we expect to get a burst of - * notifications from all neighbors, so put record at front of list. - */ - if(!SINCMP(sin, &Config.Sockaddr.http->s)){ - return; - } - oldCopy = nodeFind(sin); - if (oldCopy != NULL){ - if(oldCopy->timestamp_ns > joinTimeNS){ - /* We got a stale message; ignore it */ - return; + HierNodeElem *h, *oldCopy; + int oldHops; + int foundOldJoin = 0; + int joinIsNewer; + + assert(sin); + /* Ignore if it's already on list and either (1) a newer record + * or (2) a current record and at least as close as this + * update. Also ignore if it is me! + * For simplicity, rather than update a record in place, remove + * it and add a new record to front of list. This should be better + * for performance, too, since we expect to get a burst of + * notifications from all neighbors, so put record at front of list. + */ + if (!SINCMP(sin, &Config.Sockaddr.http->s)) { + return; } - else if(oldCopy->action != HC_Join && oldCopy->timestamp_ns < joinTimeNS){ - /* Join supercedes an old HC_Leave */ - List_Remove((List_Links *)oldCopy); - free(oldCopy); - /* Fall through and add this join to nodelist */ + oldCopy = nodeFind(sin); + if (oldCopy != NULL) { + if (oldCopy->timestamp_ns > joinTimeNS) { + /* We got a stale message; ignore it */ + return; + } else if (oldCopy->action != HC_Join + && oldCopy->timestamp_ns < joinTimeNS) { + /* Join supercedes an old HC_Leave */ + dlinkDelete(&oldCopy->links, &nodes); + xfree(oldCopy); + /* Fall through and add this join to nodelist */ + } else { + assert(oldCopy->action == HC_Join); + foundOldJoin = 1; + assert(oldCopy->timestamp_ns <= joinTimeNS); + joinIsNewer = (oldCopy->timestamp_ns < joinTimeNS); + oldHops = netdbHintHops(sin->sin_addr); + + + if (oldHops > hops) { + dlinkDelete(&oldCopy->links, &nodes); + xfree(oldCopy); + /* Fall through and add this join to nodelist and flood */ + } else if (joinIsNewer) { + /* + * Join is newer but not closer. Propagate to neighbors + * but no need to do anything locally beyond updating + * the timestamp. + */ + oldCopy->timestamp_ns = joinTimeNS; + floodEvent(HC_Join, sin, joinTimeNS, hops + 1); + return; + } + } } - else{ - assert(oldCopy->action == HC_Join); - foundOldJoin = 1; - assert(oldCopy->timestamp_ns <= joinTimeNS); - joinIsNewer = (oldCopy->timestamp_ns < joinTimeNS); - oldHops = netdbHintHops(sin->sin_addr); + /* + * Only get here if new join supercedes and old join removed or + * nonexistant. Do the join and flood it to neighbors. + */ + assert(!nodeFind(sin)); + h = (HierNodeElem *) xmalloc(sizeof(HierNodeElem)); + HierNodeElem_Init(h, sin, HC_Join, joinTimeNS); + dlinkAdd(h, &h->links, &nodes); - if (oldHops > hops) { - List_Remove((List_Links *)oldCopy); - free(oldCopy); - /* Fall through and add this join to nodelist and flood */ - } - else if(joinIsNewer){ - /* - * Join is newer but not closer. Propagate to neighbors - * but no need to do anything locally beyond updating - * the timestamp. - */ - oldCopy->timestamp_ns = joinTimeNS; - floodEvent(HC_Join, sin, joinTimeNS, hops+1); - return; - } + /* + * Now tell everyone else (locally and network) about + * the new addition or new distance + */ + floodEvent(HC_Join, sin, joinTimeNS, hops + 1); + if (foundOldJoin) { + HintCacheNodelistOutcallHops(sin, hops, joinTimeNS); + } else { + hintCacheNodelistOutcallJoin(sin, hops, joinTimeNS); + } + + if (!foundOldJoin) { + debug(HCNODES_DEBUG, 2) + ("hintCacheNodelist::NetJoin() adds %d.%d.%d.%d; list is: \n", + (unsigned char) ((sin->sin_addr.s_addr & 0xFF000000) >> 24), + (unsigned char) ((sin->sin_addr.s_addr & 0x00FF0000) >> 16), + (unsigned char) ((sin->sin_addr.s_addr & 0x0000FF00) >> 8), + (unsigned char) ((sin->sin_addr.s_addr & 0x000000FF) >> 0)); + printList(); + debug(HCNODES_DEBUG, 2) ("\n"); } - } - /* - * Only get here if new join supercedes and old join removed or - * nonexistant. Do the join and flood it to neighbors. - */ - assert(!nodeFind(sin)); - - h = (HierNodeElem *)xmalloc(sizeof(HierNodeElem)); - HierNodeElem_Init(h, sin, HC_Join, joinTimeNS); - List_Insert((List_Links *)h, &nodes); - - /* - * Now tell everyone else (locally and network) about - * the new addition or new distance - */ - floodEvent(HC_Join, sin, joinTimeNS, hops+1); - if(foundOldJoin){ - HCNodelist_OutcallHops(sin, hops, joinTimeNS); - } - else{ - HCNodelist_OutcallJoin(sin, hops, joinTimeNS); - } - - if(!foundOldJoin){ - debug(60, 2, "HCNodelist::NetJoin() adds %d.%d.%d.%d; list is: \n", - (unsigned char)((sin->sin_addr.s_addr & 0xFF000000) >> 24), - (unsigned char)((sin->sin_addr.s_addr & 0x00FF0000) >> 16), - (unsigned char)((sin->sin_addr.s_addr & 0x0000FF00) >> 8), - (unsigned char)((sin->sin_addr.s_addr & 0x000000FF) >> 0)); - printList(); - debug(60, 2, "\n"); - } } /* *------------------------------------------------------------------ * - * HCNodelist_NetLeave -- + * hintCacheNodelistNetLeave -- * * Process a notification that a node has left the system * @@ -410,72 +413,71 @@ * *----------------------------------------------------7.19.1998-------------- */ -void -HCNodelist_NetLeave (struct sockaddr_in *sin, int hops, - long long leaveTimeNS) -{ - HierNodeElem *h, *oldCopy; - int foundOldLeave = 0; - - assert(sin); - - /* Ignore if it's already on list and a newer record. - * For simplicity, rather than update a record in place, remove - * it and add a new record to front of list. This should be better - * for performance, too, since we expect to get a burst of - * notifications from all neighbors, so put record at front of list. - */ - oldCopy = nodeFind(sin); - if (oldCopy){ - if(oldCopy->action == HC_Leave){ - foundOldLeave = 1; +void +hintCacheNodelistNetLeave(struct sockaddr_in *sin, int hops, long long leaveTimeNS) +{ + HierNodeElem *h, *oldCopy; + int foundOldLeave = 0; + + assert(sin); + + /* Ignore if it's already on list and a newer record. + * For simplicity, rather than update a record in place, remove + * it and add a new record to front of list. This should be better + * for performance, too, since we expect to get a burst of + * notifications from all neighbors, so put record at front of list. + */ + oldCopy = nodeFind(sin); + if (oldCopy) { + if (oldCopy->action == HC_Leave) { + foundOldLeave = 1; + } + if (oldCopy->timestamp_ns < leaveTimeNS) { + dlinkDelete(&oldCopy->links, &nodes); + xfree(oldCopy); + } else { + /* + * old copy is actually newer than this update. Ignore this + * update. + */ + return; + } } - if(oldCopy->timestamp_ns < leaveTimeNS){ - List_Remove((List_Links *)oldCopy); - free(oldCopy); + /* + * Only get here if new leave supercedes old record removed or + * nonexistant + */ + assert(!nodeFind(sin)); + + h = (HierNodeElem *) xmalloc(sizeof(HierNodeElem)); + HierNodeElem_Init(h, sin, HC_Leave, leaveTimeNS); + dlinkAdd(h, &h->links, &nodes); + + /* + * Now tell everyone else (locally and network) about + * the new addition or new distance + */ + floodEvent(HC_Leave, sin, leaveTimeNS, hops + 1); + if (!foundOldLeave) { + HCNodelist_OutcallLeave(sin, hops, leaveTimeNS); } - else{ - /* - * old copy is actually newer than this update. Ignore this - * update. - */ - return; + + if (!foundOldLeave) { + debug(HCNODES_DEBUG, 4) + ("HCNodelist::NetLeave() removes %d.%d.%d.%d; list is: \n", + (unsigned char) ((sin->sin_addr.s_addr & 0xFF000000) >> 24), + (unsigned char) ((sin->sin_addr.s_addr & 0x00FF0000) >> 16), + (unsigned char) ((sin->sin_addr.s_addr & 0x0000FF00) >> 8), + (unsigned char) ((sin->sin_addr.s_addr & 0x000000FF) >> 0)); + printList(); + debug(HCNODES_DEBUG, 4) ("\n"); } - } - /* - * Only get here if new leave supercedes old record removed or - * nonexistant - */ - assert(!nodeFind(sin)); - - h = (HierNodeElem *)xmalloc(sizeof(HierNodeElem)); - HierNodeElem_Init(h, sin, HC_Leave, leaveTimeNS); - List_Insert((List_Links *)h, &nodes); - - /* - * Now tell everyone else (locally and network) about - * the new addition or new distance - */ - floodEvent(HC_Leave, sin, leaveTimeNS, hops+1); - if(!foundOldLeave){ - HCNodelist_OutcallLeave(sin, hops, leaveTimeNS); - } - - if(!foundOldLeave){ - debug(60, 2, "HCNodelist::NetLeave() removes %d.%d.%d.%d; list is: \n", - (unsigned char)((sin->sin_addr.s_addr & 0xFF000000) >> 24), - (unsigned char)((sin->sin_addr.s_addr & 0x00FF0000) >> 16), - (unsigned char)((sin->sin_addr.s_addr & 0x0000FF00) >> 8), - (unsigned char)((sin->sin_addr.s_addr & 0x000000FF) >> 0)); - printList(); - debug(60, 2, "\n"); - } } /* *------------------------------------------------------------------ * - * HCNodelist_OutcallHops -- + * hintCacheNodelist_OutcallHops -- * * This function gets called whenever the number of hops * to a node *changes* due to network updates. This @@ -496,30 +498,30 @@ * *--------------------------------------------------------7.19.1998----- */ -static void -HCNodelist_OutcallHops(struct sockaddr_in *sin, int hops, long long timeNS) +static void +hintCacheNodelistOutcallHops(struct sockaddr_in *sin, int hops, long long timeNS) { - char name[16]; + char name[16]; - /* - * Tell netdb - */ - strcpy(name, inet_ntoa(sin->sin_addr)); - if(!netdbHintHops(sin->sin_addr)){ - netdbAdd(sin->sin_addr, name); - } - netdbUpdateHintHops(sin->sin_addr, hops); + /* + * Tell netdb + */ + strcpy(name, inet_ntoa(sin->sin_addr)); + if (!netdbHintHops(sin->sin_addr)) { + netdbAdd(sin->sin_addr, name); + } + netdbUpdateHintHops(sin->sin_addr, hops); - /* - * Tell plaxton algorithm - */ - HCPlax_changeDistance(sin); -} + /* + * Tell plaxton algorithm + */ + hintCachePlax_changeDistance(sin); +} /* *------------------------------------------------------------------ * - * HCNodelist_OutcallJoin -- + * hintCacheNodelistOutcallJoin -- * * This function gets called whenever a node joins the * sytsem. @@ -541,28 +543,28 @@ * *-------------------------------------------------7.19.1998----------- */ -static void -HCNodelist_OutcallJoin(struct sockaddr_in *sin, int hops, long long timeNS) +static void +hintCacheNodelistOutcallJoin(struct sockaddr_in *sin, int hops, long long timeNS) { - char name[16]; + char name[16]; - /* - * Tell netdb - */ - strcpy(name, inet_ntoa(sin->sin_addr)); - netdbAdd(sin->sin_addr, name); - netdbUpdateHintHops(sin->sin_addr, hops); - - /* - * Tell plaxton algorithm - */ - HCPlax_addNode(sin); + /* + * Tell netdb + */ + strcpy(name, inet_ntoa(sin->sin_addr)); + netdbAdd(sin->sin_addr, name); + netdbUpdateHintHops(sin->sin_addr, hops); + + /* + * Tell plaxton algorithm + */ + hintCachePlax_addNode(sin); } /* *------------------------------------------------------------------ * - * HCNodelist_OutcallLeave -- + * hintCacheNodelistOutcallLeave -- * * This function gets called whenever a node leaves the * sytsem. @@ -582,13 +584,13 @@ * *-----------------------------------------------------7.19.1998---------- */ -static void -HCNodelist_OutcallLeave(struct sockaddr_in *sin, int hops, long long timeNS) +static void +hintCacheNodelistOutcallLeave(struct sockaddr_in *sin, int hops, long long timeNS) { - /* - * Tell plaxton algorithm - */ - HCPlax_removeNode(sin); + /* + * Tell plaxton algorithm + */ + hintCachePlax_removeNode(sin); } @@ -613,16 +615,16 @@ static HierNodeElem * nodeFind(struct sockaddr_in *sin) { - HierNodeElem *e; - List_Links *item; + HierNodeElem *e; + dlink_node *item; - LIST_FORALL(&nodes, item) { - e = (HierNodeElem *) item; - if (!SINCMP(&e->sin, sin)){ - return(e); + for (item = nodes.head; item; item = item->next) { + e = (HierNodeElem *) item; + if (!SINCMP(&e->sin, sin)) { + return (e); + } } - } - return(NULL); + return (NULL); } /* @@ -648,166 +650,58 @@ *-------------------------------------------------3.31.1998-------- */ static void -floodEvent(int action, struct sockaddr_in *source, long long timeNS, - int hopcount) +floodEvent(int action, struct sockaddr_in *source, long long timeNS, + int hopcount) { #ifdef USE_DYNAMIC_HIERARCHY - HCEntry entry; - peer *p; - URLKey hackURLKey; - struct sockaddr_in dest; + HintCacheEntry entry; + peer *p; + URLKey hackURLKey; + struct sockaddr_in dest; - assert(action == HC_Join || action == HC_Leave); + assert(action == HC_Join || action == HC_Leave); - if(neighborsOutgoing == NULL){ - return; - } + if (neighborsOutgoing == NULL) { + return; + } - hackURLKey.key = timeNS; /* XXX Update should be a union XXX */ + hackURLKey.key = timeNS; /* XXX Update should be a union XXX */ - HCEntry_Init(&entry, hackURLKey, source); - HCNet_Enqueue(neighborsOutgoing, action, &entry, hopcount); + hintCacheEntry_Init(&entry, hackURLKey, source); + hintCacheNet_Enqueue(neighborsOutgoing, action, &entry, hopcount); #if 1 - HCNet_Complete(neighborsOutgoing); + hintCacheNet_Complete(neighborsOutgoing); - for (p = getFirstPeer(); p; p = getNextPeer(p)) { - if(p->in_addr.sin_addr.s_addr == 0){ - debug(60, 4, "HCNodelist warning: peer %s addr not set\n", - p->host); - continue; + for (p = getFirstPeer(); p; p = getNextPeer(p)) { + if (p->in_addr.sin_addr.s_addr == 0) { + debug(HCNODES_DEBUG, 4) + ("hintCacheNodelist warning: peer %s addr not set\n", p->host); + continue; + } + dest.sin_family = AF_INET; + dest.sin_addr = p->in_addr.sin_addr; + dest.sin_port = p->http_port; + hintCacheNet_SendTo(neighborsOutgoing, &dest); } - dest.sin_family = AF_INET; - dest.sin_addr = p->in_addr.sin_addr; - dest.sin_port = p->http_port; - HCNet_SendTo(neighborsOutgoing, &dest); - } - HCNet_Done(neighborsOutgoing); + hintCacheNet_Done(neighborsOutgoing); #endif #endif /* USE_DYNAMIC_HIERARCHY */ } -/* - *------------------------------------------------------------------ - * MDD 7.18.1998 - * HCNodelist_addMembershipNeighbor -- - * - * Add a node to the peerlist to which to flood - * events (if node not already on that list). - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *---------------------------------------------------7.18.1998---------- - */ -void -HCNodelist_addMembershipNeighbor(struct sockaddr_in *neighbor) -{ - char name[16]; - peer *p; - - sprintf(name, inet_ntoa(neighbor->sin_addr)); - for (p = getFirstPeer(); p; p = getNextPeer(p)) { - if(p->in_addr.sin_addr.s_addr == neighbor->sin_addr.s_addr - || !strcmp(p->host, name)){ - return; - } - } - debug(60, 2, "Nodelist_addMembership...: letting through %s (%s)\n", - p->host, inet_ntoa(p->in_addr.sin_addr)); - - neighborAdd(name, - "", /* const char *type */ - neighbor->sin_port, - 3130 /* XXX, though ICP is irrelevant in hint world */, - 0, /* options ??? */ - 1, /* weight */ - 1 /* mcast_ttl ?? */); - - /* - * Now lookup the ip address for this peer (the peerlist ip - * addresses get refreshed at the beginning of time - * and then once per hour. We don't want to wait that - * long. - */ - for (p = getFirstPeer(); p; p = getNextPeer(p)) { - if(!strcmp(p->host, name)){ - if(p->in_addr.sin_addr.s_addr == 0){ - p->ip_lookup_pending = 1; - /* some random, bogus FD for ipcache */ - p->ipcache_fd = Squid_MaxFD + current_time.tv_usec; - ipcache_nbgethostbyname(p->host, p->ipcache_fd, peerDNSConfigure, p); - return; - } - } - } - /* - * Should not get here. If neighbor on list, returned early. - * If we added neighbor, we should find it on peer list with - * no IP address yet and we returned after starting the - * gethostbyname() call. - */ - assert(0); - return; - -} - - - -/* - *------------------------------------------------------------------ - * MDD 7.18.1998 - * HCNodelist_removeMembershipNeighbor -- - * - * Remove a node to the peerlist to which to flood - * events. - * - * Arguments: - * None. - * - * Results: - * None. - * - * Side effects: - * None. - * - *---------------------------------------------------7.18.1998---------- - */ -void HCNodelist_rmMembershipNeighbor(struct sockaddr_in *neighbor) -{ - peer *p; - for (p = getFirstPeer(); p; p = getNextPeer(p)) { - if(p->in_addr.sin_addr.s_addr == neighbor->sin_addr.s_addr){ - /* - * XXX neighborRemove() is static so can't actually do this. - * Benign bug. - */ - /* neighborRemove(p); XXX */ - debug(60, 10, "HCnodelist_rmMembershipNeighbor not yet implemented\n"); - } - } -} - - /* *------------------------------------------------------------------ * - * HCNodeList_IterXXX -- + * hintCacheNodeListIterXXX -- * * Used for iterating through all addresses on list. * - * for(HCNodeList_IterStart(&iter); - * HCNodeList_IterCheck(&iter); - * HCNodeList_IterNext(&iter)){ - * valid = HCNOdeList_IterGetAddr(&iter, &addr); + * for(hintCacheNodeListIterStart(&iter); + * hintCacheNodeListIterCheck(&iter); + * hintCacheNodeListIterNext(&iter)){ + * valid = hintCacheNOdeListIterGetAddr(&iter, &addr); * } * * Arguments: @@ -826,47 +720,48 @@ * *------------------------------------------------------------------ */ -void -HCNodeList_IterStart(HCNLIter *iter) +void +hintCacheNodeListIterStart(HintCacheNodeListIter iter) { - *iter = (HCNLIter)List_First(&nodes); + iter = (HintCacheNodeListIter) nodes.head; } int -HCNodeList_IterCheck(HCNLIter iter) +hintCacheNodeList_IterCheck(HintCacheNodeListIter iter) { - return(!List_IsAtEnd(&nodes, iter)); + dlink_node *links = iter; + return (links->next != 0); } -void -HCNodeList_IterNext(HCNLIter *iter) +void +hintCacheNodeList_IterNext(HintCacheNodeListIter iter) { - HierNodeElem *elem; + HierNodeElem *elem; - if(List_IsAtEnd(&nodes, *iter)){ - return; - } - - while(1){ - *iter = (HCNLIter)List_Next(*iter); - /* - * Skip non-HC_Join elements by keeping going in that case. - */ - if(List_IsAtEnd(&nodes, *iter)){ - return; + if (iter->next == 0) { + return; } - elem = (HierNodeElem *)*iter; - if(elem->action == HC_Join){ - return; + + while (1) { + iter = iter->next; + /* + * Skip non-HC_Join elements by keeping going in that case. + */ + if (iter->next == 0) { + return; + } + elem = iter->data; + if (elem->action == HC_Join) { + return; + } } - } - + } /* *------------------------------------------------------------------ * - * HCNodeList_IterGetAddr -- + * hintCacheNodelistIterGetAddr -- * * description. * @@ -882,15 +777,15 @@ *------------------------------------------------------------------ */ int -HCNodeList_IterGetAddr(HCNLIter iter, struct sockaddr_in *ret) +hintCacheNodelistIterGetAddr(HintCacheNodeListIter iter, struct sockaddr_in *ret) { - HierNodeElem *elem; - elem = (HierNodeElem *)iter; - *ret = elem->sin; - if(elem->action == HC_Join){ - return 1; - } - return 0; + HierNodeElem *elem; + elem = iter->data; + *ret = elem->sin; + if (elem->action == HC_Join) { + return 1; + } + return 0; } @@ -915,17 +810,17 @@ static long long currentTimeNS() { - static const long long NS_PER_SEC = 1000000000; - static const long long NS_PER_USEC = 1000; - int error; - struct timeval time; - long long ret; - - error = gettimeofday(&time, NULL); - assert(error != -1); - ret = NS_PER_SEC * (long long)time.tv_sec - + NS_PER_USEC * (long long)time.tv_usec; - return ret; + static const long long NS_PER_SEC = 1000000000; + static const long long NS_PER_USEC = 1000; + int error; + struct timeval time; + long long ret; + + error = gettimeofday(&time, NULL); + assert(error != -1); + ret = NS_PER_SEC * (long long) time.tv_sec + + NS_PER_USEC * (long long) time.tv_usec; + return ret; } /* @@ -950,22 +845,22 @@ static void printList() { - HCNLIter iter; - struct sockaddr_in nodeAddr; - int valid; - - for(HCNodeList_IterStart(&iter); - HCNodeList_IterCheck(iter); - HCNodeList_IterNext(&iter)){ - valid = HCNodeList_IterGetAddr(iter, &nodeAddr); - if(valid){ - debug(60, 2, "\t%d.%d.%d.%d\n", - (unsigned char)((nodeAddr.sin_addr.s_addr & 0xFF000000) >> 24), - (unsigned char)((nodeAddr.sin_addr.s_addr & 0x00FF0000) >> 16), - (unsigned char)((nodeAddr.sin_addr.s_addr & 0x0000FF00) >> 8), - (unsigned char)((nodeAddr.sin_addr.s_addr & 0x000000FF) >> 0)); + HintCacheNodeListIter iter; + struct sockaddr_in nodeAddr; + int valid; + + for (hintCacheNodeListIterStart(iter); + hintCacheNodeListIterCheck(iter); hintCacheNodeListIterNext(&iter)) { + valid = hintCacheNodeListIterGetAddr(iter, &nodeAddr); + if (valid) { + debug(HCNODES_DEBUG, 2) + ("\t%d.%d.%d.%d\n", + (unsigned char) ((nodeAddr.sin_addr.s_addr & 0xFF000000) >> 24), + (unsigned char) ((nodeAddr.sin_addr.s_addr & 0x00FF0000) >> 16), + (unsigned char) ((nodeAddr.sin_addr.s_addr & 0x0000FF00) >> 8), + (unsigned char) ((nodeAddr.sin_addr.s_addr & 0x000000FF) >> 0)); + } } - } } @@ -973,7 +868,7 @@ /* *------------------------------------------------------------------ * - * HCNodelist_SelfTest -- + * hintCacheNodelistSelfTest -- * * description. * @@ -988,84 +883,87 @@ * *------------------------------------------------------------------ */ -void HCNodelist_SelfTest (void) +void +hintCacheNodelistSelfTest(void) { - struct sockaddr_in n0, n1, n2; - HCNLIter iter; - struct sockaddr_in nodeAddr; - int nhops; - int valid; - int found = 0; - - printf("HCNodelist_SelfTest..."); - n0.sin_addr.s_addr = 0x90536F00; n0.sin_port = 0; - n1.sin_addr.s_addr = 0x91536F01; n1.sin_port = 1; - n2.sin_addr.s_addr = 0x92536F02; n2.sin_port = 2; - - HCNodelist_Init(); - HCPlax_Init(8); - - assert(neighborsOutgoing == NULL); - neighborsOutgoing = (HCNet *)malloc(sizeof(HCNet)); - assert(neighborsOutgoing); - HCNet_Init(neighborsOutgoing); - HCNet_SetTestMode(neighborsOutgoing); - - - /* - * How to test if this really works? For now look at how many - * outgoing messages were enqueued. - */ - HCNodelist_LocalJoin(); - HCNodelist_LocalLeave(); - assert(HCNet_GetTestCount(neighborsOutgoing) == 2); - - /* - * Expected final state: - * n0 JOIN dist = 12 - * n1 LEAVE XXX - * n2 JOIN dist=20 - */ - HCNodelist_NetJoin(&n0, 10, 42); - HCNodelist_NetJoin(&n2, 20, 42); - HCNodelist_NetJoin(&n0, 13, 43); - HCNodelist_NetJoin(&n1, 20, 42); - HCNodelist_NetJoin(&n2, 20, 100); - HCNodelist_NetJoin(&n0, 9, 42); - HCNodelist_NetJoin(&n0, 12, 43); - HCNodelist_NetJoin(&n2, 20, 42); - HCNodelist_NetLeave(&n1, 999, 43); - HCNodelist_NetJoin(&n1, 19, 42); - - for(HCNodeList_IterStart(&iter); - HCNodeList_IterCheck(iter); - HCNodeList_IterNext(&iter)){ - valid = HCNodeList_IterGetAddr(iter, &nodeAddr); - if(valid){ - nhops = netdbHintHops(nodeAddr.sin_addr); - if(nodeAddr.sin_addr.s_addr == n0.sin_addr.s_addr){ - found++; - assert(nhops == 12); - } - if(nodeAddr.sin_addr.s_addr == n2.sin_addr.s_addr){ - found++; - assert(nhops = 20); - } - if(nodeAddr.sin_addr.s_addr == n1.sin_addr.s_addr){ - assert(0); - } - } - } - assert(found == 2); + struct sockaddr_in n0, n1, n2; + HintCacheNodeListIter iter; + struct sockaddr_in nodeAddr; + int nhops; + int valid; + int found = 0; + + printf("HintCacheNodelistSelfTest..."); + n0.sin_addr.s_addr = 0x90536F00; + n0.sin_port = 0; + n1.sin_addr.s_addr = 0x91536F01; + n1.sin_port = 1; + n2.sin_addr.s_addr = 0x92536F02; + n2.sin_port = 2; + + hintCacheNodelistInit(); + hintCachePlax_Init(8); + + assert(neighborsOutgoing == NULL); + neighborsOutgoing = (HintCacheNet *) xmalloc(sizeof(HintCacheNet)); + assert(neighborsOutgoing); + hintCacheNet_Init(neighborsOutgoing); + hintCacheNet_SetTestMode(neighborsOutgoing); + - HCNodelist_Destroy(); - HCPlax_Destroy(); + /* + * How to test if this really works? For now look at how many + * outgoing messages were enqueued. + */ + hintCacheNodelistLocalJoin(); + hintCacheNodelistLocalLeave(); + assert(hintCacheNet_GetTestCount(neighborsOutgoing) == 2); - HCNet_Destroy(neighborsOutgoing); - free(neighborsOutgoing); - neighborsOutgoing = NULL; + /* + * Expected final state: + * n0 JOIN dist = 12 + * n1 LEAVE XXX + * n2 JOIN dist=20 + */ + hintCacheNodelistNetJoin(&n0, 10, 42); + hintCacheNodelistNetJoin(&n2, 20, 42); + hintCacheNodelistNetJoin(&n0, 13, 43); + hintCacheNodelistNetJoin(&n1, 20, 42); + hintCacheNodelistNetJoin(&n2, 20, 100); + hintCacheNodelistNetJoin(&n0, 9, 42); + hintCacheNodelistNetJoin(&n0, 12, 43); + hintCacheNodelistNetJoin(&n2, 20, 42); + hintCacheNodelistNetLeave(&n1, 999, 43); + hintCacheNodelistNetJoin(&n1, 19, 42); + + for (hintCacheNodeListIterStart(&iter); + hintCacheNodeListIterCheck(iter); hintCacheNodeList_IterNext(&iter)) { + valid = hintCacheNodeListIterGetAddr(iter, &nodeAddr); + if (valid) { + nhops = netdbHintHops(nodeAddr.sin_addr); + if (nodeAddr.sin_addr.s_addr == n0.sin_addr.s_addr) { + found++; + assert(nhops == 12); + } + if (nodeAddr.sin_addr.s_addr == n2.sin_addr.s_addr) { + found++; + assert(nhops = 20); + } + if (nodeAddr.sin_addr.s_addr == n1.sin_addr.s_addr) { + assert(0); + } + } + } + assert(found == 2); + + hintCacheNodelistDestroy(); + hintCachePlaxDestroy(); + + hintCacheNetDestroy(neighborsOutgoing); + free(neighborsOutgoing); + neighborsOutgoing = NULL; - printf("..OK\n"); + printf("..OK\n"); } Index: squid/src/HintCachePrim.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/HintCachePrim.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/HintCachePrim.c 20 Nov 2001 06:56:54 -0000 1.1.2.1 +++ squid/src/HintCachePrim.c 21 May 2002 02:46:42 -0000 1.1.2.2 @@ -1,6 +1,7 @@ /* - * $Date: 2001/11/20 06:56:54 $ $Id: HintCachePrim.c,v 1.1.2.1 2001/11/20 06:56:54 jkay Exp $ + * $Date: 2002/05/21 02:46:42 $ $Id: HintCachePrim.c,v 1.1.2.2 2002/05/21 02:46:42 jkay Exp $ * + * DEBUG: section 89 List of known caches. * AUTHOR: Mike Dahlin, UT Austin, 1998 * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ @@ -39,54 +40,23 @@ #include -const URLKey INVALID_URL_KEY = {0}; +const URLKey INVALID_URL_KEY = { 0 }; -static GenericKey calculateStupidKey(char *url); -static GenericKey calculateMD5Key(char *url); +static HintCacheKey calculateStupidKey(char *url); static void makeLowerCase(char *url); -static GenericKey calculateKey(char *url); const static int useMD5 = 1; - + /* *------------------------------------------------------------------ * * URLKey -- * - * Constructor. Calculate a hash of the URL. - * This hash needs to be a good one; collisions - * must be rare because they get treated as misses - * or worse yet false hits. - * - * Be sure to convert the URL to a canonical form. - * We assume that the only canonicalizing that - * we need to do is making it all the same case. - * - * Arguments: - * char *url -- a URL. - * - * Results: - * None. - * - * Side effects: - * None. - * - *------------------------------------------------------------------ + * The first 64 bits of the 128-bit Squid/Cache Digest URL key. */ -void -URLKey_Init(URLKey *key, char *url) -{ - assert(key); - if(!url){ - key->key = 0; - return; - } - makeLowerCase(url); - key->key = calculateKey(url); -} /* * Make lower case, but stop at third '/' (e.g., after the hostname). @@ -94,107 +64,64 @@ static void makeLowerCase(char *url) { - int len, ii; - int slashCount = 0; + int len, ii; + int slashCount = 0; - assert(url); - len = strlen(url); - for(ii = 0; ii < len; ii++){ - /* - * Alignment. - */ - if(url[ii] == '/'){ - slashCount++; - if(slashCount == 3){ - return; - } + assert(url); + len = strlen(url); + for (ii = 0; ii < len; ii++) { + /* + * Alignment. + */ + if (url[ii] == '/') { + slashCount++; + if (slashCount == 3) { + return; + } + } + url[ii] = tolower(url[ii]); } - url[ii] = tolower(url[ii]); - } } -/* - * The hash function should be really good since we are counting - * on there being few collisions in our k-way associative - * table (for small k). The roll-your-own one I doubt is much - * good, so you should probably use the MD5 hash. Notice - * that machines send messages to each other that contain - * the hash only, so all machines must use the same calculateKey - * function. - */ -static GenericKey -calculateKey(char *url) +/* functional encapsulation of the ever-popular macro of the + same name. Needed for hash table. */ +int +hintCacheURLKeyCompare(URLKey *u1, URLKey *u2) { - const static int useMD5 = 1; - - if(useMD5){ - return calculateMD5Key(url); - } - else{ - return calculateStupidKey(url); - } - + return(URLKEY_COMPARE(*u1, *u2)); } - -static GenericKey -calculateMD5Key(char *url) -{ - MD5_CTX tCrypt; - static long long unsigned digestPart; - - assert(url); - MD5Init(&tCrypt); - MD5Update(&tCrypt, "this is my secret key, yeah right", strlen("this is my secret key, yeah right")); - MD5Update(&tCrypt, url, strlen(url)); - MD5Final(&tCrypt); - /* - * The digest MUST be smaller than a long long (otherwise we - * would be including undefined bytes past end of digest. - */ - assert(MD5_DIGEST_SIZE * sizeof(unsigned char) - >= sizeof(GenericKey)); - - memcpy(&digestPart, &(tCrypt.digest[0]), sizeof(digestPart)); - return digestPart; -} - -static GenericKey -calculateStupidKey(char *url) +/* + * Retrieve entry using hint_table. + * The hint_table keeps a pointer to the hchash part of th + * StoreEntry, so we apply the appropriate offset to + * retrieve the StoreEntry itself. + */ +StoreEntry * +hintCacheStoreGet(URLKey urlkey) { - static const GenericKey BIG_PRIME_1 = 193844587; - static const GenericKey BIG_PRIME_2 = 455899; - static const GenericKey BIG_PRIME_3 = 901367; - - int len, ii; - GenericKey key, chunk; - assert(url); - len = strlen(url); - key = 0; - for(ii = 0; ii < len-8; ii += 8){ - /* Make copy to guarantee alignment. */ - memcpy(&chunk, &url[ii], 8); - key = key + chunk * BIG_PRIME_1; - } - for( ; ii < len; ii++){ - key = key + (unsigned char)url[ii] * BIG_PRIME_2; - } - key = key + len * BIG_PRIME_3; - return key; + hash_link *hchash; + StoreEntry *entry; + int hchoff; + + hchash = (hash_link *) hash_lookup(store_table, &urlkey); + hchoff = (u_char *) &entry->hchash - (u_char *) entry; + entry = (StoreEntry *) ((u_char *) hchash - hchoff); + return(entry); } -void -Net_URLKey_Init(Net_URLKey *mungedKey, URLKey *key) +void +hintCacheNetURLKeyNetInit(URLKeyNet * mungedKey, URLKey * key) { - mungedKey->mungedKey = HCEndian_llMachineToNet(key->key); + mungedKey->mungedKey = hintCacheEndian_llMachineToNet(key->key); } void -Net_URLKey_LocalFormat(Net_URLKey *mungedKey, URLKey *key) +hintCacheNetURLKeyLocalFormat(URLKeyNet * mungedKey, URLKey * key) { - key->key = HCEndian_llNetToMachine(mungedKey->mungedKey); + key->key = hintCacheEndian_llNetToMachine(mungedKey->mungedKey); } @@ -219,55 +146,51 @@ *---------------------------------------------------4.9.1998-------- */ void -NodeKey_Init(NodeKey *k, const struct sockaddr_in *addrP) +hintCacheNodeKeyInit(NodeKey * k, const struct sockaddr_in *addrP) { - assert(k); - assert(addrP); - - List_Init((List_Links *)k); - k->key = NodeKK_Key(addrP); - k->addr = *addrP; + assert(k); + assert(addrP); + + k->links.data = k; + k->links.next = k->links.prev = 0; + k->key = hintCacheNodeKeyKey(addrP); + k->addr = *addrP; } int -NodeKey_Compare(const NodeKey *k1, const NodeKey *k2) +hintCacheNodeKeyCompare(const NodeKey * k1, const NodeKey * k2) { - assert(k1); - assert(k2); - if(k1->key != k2->key){ - return 1; - } - return 0; + assert(k1); + assert(k2); + if (k1->key != k2->key) { + return 1; + } + return 0; } -struct sockaddr_in -NodeKey_GetAddr (const NodeKey *k) +struct sockaddr_in +hintCacheNodeKeyGetAddr(const NodeKey * k) { - assert(k); - return k->addr; + assert(k); + return k->addr; } -GenericKey -NodeKK_Key(const struct sockaddr_in *addrP) +HintCacheKey +hintCacheNodeKeyKey(const struct sockaddr_in * addrP) { - GenericKey k; - char *name; + HintCacheKey k; + char *name; - name = inet_ntoa(addrP->sin_addr); - if(useMD5){ - k = calculateMD5Key(name); - } - else{ - k = calculateStupidKey(name); - } - return k; + name = inet_ntoa(addrP->sin_addr); + k = *(HintCacheKey *) storeKeyPublic(name, METHOD_PUT); + return k; } /* *------------------------------------------------------------------ * - * HCEntry -- + * hintCacheEntry -- * * A structure including a pair. Generally * points to the nearest copy of the specified url. @@ -283,63 +206,63 @@ * *------------------------------------------------------------------ */ -void -HCEntry_Init(HCEntry *entry, URLKey key, struct sockaddr_in *saddr, - unsigned int mtime) -{ - entry->key = key; - entry->ipaddr = saddr->sin_addr; - entry->port = saddr->sin_port; - entry->pad = 0; - entry->mtime = mtime; +void +hintCacheEntryInit(HintCacheEntry * entry, URLKey key, struct sockaddr_in *saddr, + unsigned int mtime) +{ + entry->key = key; + entry->ipaddr = saddr->sin_addr; + entry->port = saddr->sin_port; + entry->pad = 0; + entry->mtime = mtime; } int -HCEntry_Compare(HCEntry *e1, HCEntry *e2) +hintCacheEntryCompare(HintCacheEntry * e1, HintCacheEntry * e2) { - /* - * If you add a field, you must change this code. - */ - if(URLKEY_COMPARE(e1->key, e2->key)){ - return 1; - } + /* + * If you add a field, you must change this code. + */ + if (URLKEY_COMPARE(e1->key, e2->key)) { + return 1; + } - if (e1->ipaddr.s_addr != e2->ipaddr.s_addr) - return 1; + if (e1->ipaddr.s_addr != e2->ipaddr.s_addr) + return 1; - if (e1->port != e2->port) - return 1; + if (e1->port != e2->port) + return 1; - if (e1->mtime != e2->mtime) - return 1; + if (e1->mtime != e2->mtime) + return 1; - return 0; + return 0; } void -Net_HCEntry_Init(Net_HCEntry *mungedEntry, HCEntry *entry) +hintCacheNetEntryInit(HintCacheEntryNet * mungedEntry, HintCacheEntry * entry) { - /* - * If you add a field, you must change this code. - */ - Net_URLKey_Init(&mungedEntry->mungedKey, &entry->key); + /* + * If you add a field, you must change this code. + */ + URLKeyNetInit(&mungedEntry->mungedKey, &entry->key); /* mungedEntry->mungedIpaddr.s_addr = htonl(entry->ipaddr.s_addr);*/ - mungedEntry->mungedIpaddr.s_addr = entry->ipaddr.s_addr; - mungedEntry->mungedPort = htons(entry->port); - mungedEntry->mungedMtime = htonl(entry->mtime); + mungedEntry->mungedIpaddr.s_addr = entry->ipaddr.s_addr; + mungedEntry->mungedPort = htons(entry->port); + mungedEntry->mungedMtime = htonl(entry->mtime); } void -Net_HCEntry_LocalFormat(Net_HCEntry *mungedEntry, HCEntry *entry) +hintCacheEntryLocalFormatNet(HintCacheEntryNet * mungedEntry, HintCacheEntry * entry) { - /* - * If you add a field, you must change this code. - */ - Net_URLKey_LocalFormat(&mungedEntry->mungedKey, &entry->key); + /* + * If you add a field, you must change this code. + */ + URLKeyLocalFormatNet(&mungedEntry->mungedKey, &entry->key); /* entry->ipaddr.s_addr = ntohl(mungedEntry->mungedIpaddr.s_addr);*/ - entry->ipaddr.s_addr = mungedEntry->mungedIpaddr.s_addr; - entry->port = ntohs(mungedEntry->mungedPort); - entry->mtime = htonl(mungedEntry->mungedMtime); + entry->ipaddr.s_addr = mungedEntry->mungedIpaddr.s_addr; + entry->port = ntohs(mungedEntry->mungedPort); + entry->mtime = htonl(mungedEntry->mungedMtime); } @@ -348,7 +271,7 @@ * * HCUpdate -- * - * An update is a HCEntry and an action. + * An update is a HintCacheEntry and an action. * * Arguments: * type1 arg1 -- description. @@ -362,67 +285,67 @@ *------------------------------------------------------------------ */ void -hintCacheUpdateInit(HCUpdate *u, int action, HCEntry *entry, int hopcount) +hintCacheUpdateInit(HintCacheUpdate * u, int action, HintCacheEntry * entry, int hopcount) { - u->action = action; - u->hopcount = hopcount; - u->UNUSED = 0; /* remove this field sometime */ - u->entry = *entry; + u->action = action; + u->hopcount = hopcount; + u->UNUSED = 0; /* remove this field sometime */ + u->entry = *entry; } void hintCacheUpdateSelfTest() { - HCUpdate update; - Net_HCUpdate netupd; - - /* HCUpdate must be at least this min size */ - assert(sizeof(HCUpdate) >= HCU_MINLEN); + HintCacheUpdate update; + HintCacheUpdateNet netupd; + + /* HintCacheUpdate must be at least this min size */ + assert(sizeof(HintCacheUpdate) >= HCU_MINLEN); - /* Test that some field in update has expected offset */ - assert((char *) &update.entry - (char *) &update == 8); - assert((char *) &netupd.mungedEntry - (char *) &netupd == 8); - - /* Make sure net version of struct stays in sync. */ - assert(sizeof(HCUpdate) == sizeof(Net_HCUpdate)); + /* Test that some field in update has expected offset */ + assert((char *) &update.entry - (char *) &update == 8); + assert((char *) &netupd.mungedEntry - (char *) &netupd == 8); + + /* Make sure net version of struct stays in sync. */ + assert(sizeof(HintCacheUpdate) == sizeof(HintCacheUpdateNet)); } void -hintCacheUpdateInitNet (Net_HCUpdate *mupdate, HCUpdate *update) +hintCacheUpdateInitNet(HintCacheUpdateNet * mupdate, HintCacheUpdate * update) { /* No need for htonl on action, hopcount, or len - they are single bytes. */ - mupdate->mungedAction = update->action; - mupdate->mungedUNUSED = update->UNUSED; /* remove this field sometime */ + mupdate->mungedAction = update->action; + mupdate->mungedUNUSED = update->UNUSED; /* remove this field sometime */ mupdate->mungedHopcount = update->hopcount; - mupdate->mungedPad1 = -1; - mupdate->mungedPad2 = -1; + mupdate->mungedPad1 = -1; + mupdate->mungedPad2 = -1; /* mupdate->mungedCchange = htonl(update->cchange); XXX - NOTYET */ - + hintCacheEntryInitNet(&mupdate->mungedEntry, &update->entry); } void -hintCacheUpdateLocalFormatNet(Net_HCUpdate *mupdate, HCUpdate *update) +hintCacheUpdateLocalFormatNet(HintCacheUpdateNet * mupdate, HintCacheUpdate * update) { /* No need for htonl on action or len - they are single bytes. */ - update->action = mupdate->mungedAction; - update->UNUSED = mupdate->mungedUNUSED; ; + update->action = mupdate->mungedAction; + update->UNUSED = mupdate->mungedUNUSED;; update->hopcount = mupdate->mungedHopcount; /* update->cchange = ntohl(mupdate->mungedCchange); XXX - NOTYET */ - + hintCacheEntryLocalFormatNet(&mupdate->mungedEntry, &update->entry); } -int -hintCacheUpdateCompare (HCUpdate *u1, HCUpdate *u2) +int +hintCacheUpdateCompare(HintCacheUpdate * u1, HintCacheUpdate * u2) { - if((u1->action != u2->action) - || (u1->hopcount != u2->hopcount) - || (HCEntry_Compare(&u1->entry, &u2->entry))){ - return 1; - } - return 0; + if ((u1->action != u2->action) + || (u1->hopcount != u2->hopcount) + || (hintCacheEntry_Compare(&u1->entry, &u2->entry))) { + return 1; + } + return 0; } #ifdef DOTEST @@ -448,34 +371,34 @@ primitivesSelfTest() { - URLKey urlKey, urlKey2; - Net_URLKey netUrlKey; - char url[128]; - HintCachEntry hcEntry, hcEntry2; - HintCacheEntry netHCEntry; - HintCacheUpdate hcUpdate, hcUpdate2; - HintCacheUpdateNet netHCUpdate; - struct sockaddr_in saddr = { AF_INET, 0, { { { 0, 0, 0, 0 } } } }; - - printf("primitivesSelfTest().."); - - sprintf(url, "http://www.cs.Utexas.edu"); - URLKey_Init(&urlKey, url); - Net_URLKey_Init(&netUrlKey, &urlKey); - Net_URLKey_LocalFormat(&netUrlKey, &urlKey2); - assert(!URLKEY_COMPARE(urlKey, urlKey2)); - - hintCacheEntryInit(&hcEntry, urlKey, &saddr); - hintCacheEntryInitNet(&netHCEntry, &hcEntry); - hintCacheEntryLocalFormatNet(&netHCEntry, &hcEntry2); - assert(!hintCacheEntryCompare(&hcEntry, &hcEntry2)); - - HCUpdate_Init(&hcUpdate, HC_InvalToChild, &hcEntry, 1); - HCUpdate_selfTest(); - Net_HCUpdate_Init(&netHCUpdate, &hcUpdate); - Net_HCUpdate_LocalFormat(&netHCUpdate, &hcUpdate2); - assert(!HCUpdate_Compare(&hcUpdate, &hcUpdate2)); + URLKey urlKey, urlKey2; + URLKeyNet netUrlKey; + char url[128]; + HintCachEntry hcEntry, hcEntry2; + HintCacheEntry netHintCacheEntry; + HintCacheUpdate hcUpdate, hcUpdate2; + HintCacheUpdateNet netHintCacheUpdate; + struct sockaddr_in saddr = { AF_INET, 0, {{{0, 0, 0, 0}}} }; + + printf("primitivesSelfTest().."); + + sprintf(url, "http://www.cs.Utexas.edu"); + hintCacheURLKey_Init(&urlKey, url); + Net_URLKey_Init(&netUrlKey, &urlKey); + URLKeyLocalFormatNet(&netUrlKey, &urlKey2); + assert(!URLKEY_COMPARE(urlKey, urlKey2)); + + hintCacheEntryInit(&hcEntry, urlKey, &saddr); + hintCacheEntryInitNet(&netHintCacheEntry, &hcEntry); + hintCacheEntryLocalFormatNet(&netHintCacheEntry, &hcEntry2); + assert(!hintCacheEntryCompare(&hcEntry, &hcEntry2)); + + hintCacheUpdateInit(&hcUpdate, HC_InvalToChild, &hcEntry, 1); + hintCacheUpdate_selfTest(); + hintCacheUpdateInitNet(&netHintCacheUpdate, &hcUpdate); + hintCacheUpdateLocalFormatNet(&netHintCacheUpdate, &hcUpdate2); + assert(!HintCacheUpdate_Compare(&hcUpdate, &hcUpdate2)); - printf(".OK\n"); + printf(".OK\n"); } #endif /* DOTEST */ Index: squid/src/Plaxton.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/Plaxton.c,v retrieving revision 1.1.2.1 retrieving revision 1.1.2.2 diff -u -r1.1.2.1 -r1.1.2.2 --- squid/src/Plaxton.c 20 Nov 2001 06:59:14 -0000 1.1.2.1 +++ squid/src/Plaxton.c 21 May 2002 02:46:42 -0000 1.1.2.2 @@ -1,7 +1,7 @@ /* - * $Date: 2001/11/20 06:59:14 $ $Id: Plaxton.c,v 1.1.2.1 2001/11/20 06:59:14 jkay Exp $ + * $Date: 2002/05/21 02:46:42 $ $Id: Plaxton.c,v 1.1.2.2 2002/05/21 02:46:42 jkay Exp $ * - * DEBUG: section 56 Greg Plaxton's per-object hierarchy. + * DEBUG: section 91 Greg Plaxton's per-object hierarchy. * AUTHOR: Mike Dahlin, UT Austin, 1998 * * SQUID Internet Object Cache http://squid.nlanr.net/Squid/ @@ -72,15 +72,15 @@ #include "squid.h" -#define HCPLAX_DEBUG 56 +#define HCPLAX_DEBUG 91 /* - * Array [BITS_PER_BYTE * sizeof(NodeKeyKey) + 1] of List_Links. + * Array [BITS_PER_BYTE * sizeof(HintCacheNodeKeyKey) + 1] of dlink_nodes */ #define BITS_PER_BYTE 8 -#define BITS_PER_KEY (8 * sizeof(GenericKey)) +#define BITS_PER_KEY (8 * sizeof(HintCacheKey)) -static GenericKey myNodeKey; +static HintCacheKey myNodeKey; static int initialized = 0; @@ -88,9 +88,9 @@ * For keeping track of children */ static int nChildLists = -9999; -static List_Links *childrenListA; -static int *childrenCountA = NULL; /* Entry i is the number of children - * that match in i bits. */ +static dlink_list *childrenListA; +static int *childrenCountA = NULL; /* Entry i is the number of children + * that match in i bits. */ static int childrenCountTot = 0; /* @@ -116,7 +116,7 @@ * by their distance from me with the closest node always * at the head of its list. */ -static List_Links *parentListA = NULL; +static dlink_list *parentListA = NULL; /* * Special case of parent finding when I match in as many bits * as anyone. In case of a tie for root, @@ -135,32 +135,32 @@ * are sorted by the integer value of the key with the * largest value at the head of the list. */ -static List_Links *highestMatchA = NULL; - +static dlink_list *highestMatchA = NULL; + static int normalParentIndex(int bucket); -static int fullMatchIndex(GenericKey k); +static int fullMatchIndex(HintCacheKey k); static int firstLevelBucketForMatch(int matchBits); static int highestMatchIndex(int matchBits); -static void childAdd _PARAMS((NodeKey *key)); -static NodeKey *childFind _PARAMS((NodeKey *key)); -static void freeList(List_Links *list); +static void childAdd _PARAMS((HintCacheNodeKey * key)); +static HintCacheNodeKey *childFind _PARAMS((HintCacheNodeKey * key)); +static void freeList(dlink_list * list); static void addNodeParentList(struct sockaddr_in *addNode); static void removeNodeParentList(struct sockaddr_in *goneNode); static void changeDistanceParentList(struct sockaddr_in *changeDistNode); -static int parentListIndex(NodeKey *n); +static int parentListIndex(HintCacheNodeKey * n); static void addNodeHighestMatch(struct sockaddr_in *addNode); -static void matchInsert(List_Links *l, struct sockaddr_in *a); +static void matchInsert(dlink_list *l, struct sockaddr_in *a); static void removeNodeHighestMatch(struct sockaddr_in *goneNode); -static void matchRemove(List_Links *l, struct sockaddr_in *a); -static int scanForParentMatch(int maxTry, int minTry, const URLKey *key, - int *parentIndexRet, int *amIRootRet); -static GenericKey makeMatchKey(const URLKey *key, int matchBits, - int permuteVal); +static void matchRemove(dlink_list *l, struct sockaddr_in *a); +static int scanForParentMatch(int maxTry, int minTry, const URLKey * key, + int *parentIndexRet, int *amIRootRet); +static HintCacheKey makeMatchKey(const URLKey * key, int matchBits, + int permuteVal); #ifdef DOTEST static void selfTestChildren(); -static int selfTestFindAddr(int addr, struct sockaddr_in *childrenA, - int childCount); +static int selfTestFindAddr(int addr, struct sockaddr_in *childrenA, + int childCount); static void selfTestParents(); static void testParentsBinaryTree(void); static void testParentsMultiRootCase(void); @@ -188,63 +188,56 @@ * *-------------------------------------------------4.15.1998----------- */ -void plaxtonInit(int bitsPerLevel_) +void +plaxtonInit(int bitsPerLevel_) { - int ii; - int nParentBuckets; - struct sockaddr_in *me = &Config.Sockaddr.http->s; - NodeKey *key; - - assert(nChildLists < 0); /* We shouldn't be initialized yet */ - - assert(!initialized); - initialized = 1; - - myNodeKey = NodeKK_Key(me); - /* - * List i contains all children that match me in i bits. - * Legal values for i are [0, BITS_PER_KEY] - */ - nChildLists = BITS_PER_KEY + 1; - assert(childrenListA == NULL); - childrenListA = xmalloc(nChildLists * sizeof(List_Links)); - assert(childrenListA); - childrenCountA = xmalloc(nChildLists * sizeof(int)); - for(ii = 0; ii < nChildLists; ii++){ - List_Init(&childrenListA[ii]); - childrenCountA[ii] = 0; - } - childrenCountTot = 0; - - /* - * Parents - */ - bitsPerLevel = bitsPerLevel_; - nParentLevels = (BITS_PER_KEY) / bitsPerLevel; - if((BITS_PER_KEY) % bitsPerLevel != 0){ - nParentLevels++; - } - Plaxton_bucketsPerLevel = 1; - for(ii = 0; ii < bitsPerLevel; ii++){ - Plaxton_bucketsPerLevel *= 2; - } - nParentBuckets = Plaxton_bucketsPerLevel * nParentLevels; - maxParentBucket = nParentBuckets - 1; - assert(parentListA == NULL); - parentListA = (List_Links *)xmalloc(nParentBuckets * sizeof(List_Links)); - assert(parentListA); - for(ii = 0; ii < nParentBuckets; ii++){ - List_Init(&parentListA[ii]); - } - assert(highestMatchA == NULL); - highestMatchA = (List_Links *)xmalloc(BITS_PER_KEY * sizeof(List_Links)); - assert(highestMatchA); - for(ii = 0; ii < BITS_PER_KEY; ii++){ - List_Init(&highestMatchA[ii]); - key = (NodeKey *)xmalloc(sizeof(NodeKey)); - NodeKey_Init(key, me); - List_Insert((List_Links *)key, LIST_ATFRONT(&highestMatchA[ii])); - } + int ii; + int nParentBuckets; + struct sockaddr_in *me = &Config.Sockaddr.http->s; + HintCacheNodeKey *key; + + assert(nChildLists < 0); /* We shouldn't be initialized yet */ + + assert(!initialized); + initialized = 1; + + myNodeKey = NodeKK_Key(me); + /* + * List i contains all children that match me in i bits. + * Legal values for i are [0, BITS_PER_KEY] + */ + nChildLists = BITS_PER_KEY + 1; + assert(childrenListA == NULL); + childrenListA = (dlink_list *) xcalloc(nChildLists, sizeof(dlink_list)); + assert(childrenListA); + childrenCountA = (int *) xcalloc(nChildLists, sizeof(int)); + childrenCountTot = 0; + + /* + * Parents + */ + bitsPerLevel = bitsPerLevel_; + nParentLevels = (BITS_PER_KEY) / bitsPerLevel; + if ((BITS_PER_KEY) % bitsPerLevel != 0) { + nParentLevels++; + } + Plaxton_bucketsPerLevel = 1; + for (ii = 0; ii < bitsPerLevel; ii++) { + Plaxton_bucketsPerLevel *= 2; + } + nParentBuckets = Plaxton_bucketsPerLevel * nParentLevels; + maxParentBucket = nParentBuckets - 1; + assert(parentListA == NULL); + parentListA = (dlink_list *) xcalloc(nParentBuckets, sizeof(dlink_list)); + assert(parentListA); + assert(highestMatchA == NULL); + highestMatchA = (dlink_list *) xcalloc(BITS_PER_KEY, sizeof(dlink_list)); + assert(highestMatchA); + for (ii = 0; ii < BITS_PER_KEY; ii++) { + key = (HintCacheNodeKey *) xmalloc(sizeof(HintCacheNodeKey)); + hintCacheNodeKeyInit(key, &Config.Sockaddr.http->s); + dlinkAdd(key, &key->links, &highestMatchA[ii]); + } } /* @@ -265,40 +258,41 @@ * *---------------------------------------------------4.16.1998------ */ -void plaxtonDestroy(void) +void +plaxtonDestroy(void) { - int ii; + int ii; - assert(initialized); - initialized = 0; + assert(initialized); + initialized = 0; - assert(nChildLists > 0); /* Are we initialized? */ - for(ii = 0; ii < nChildLists; ii++){ - freeList(&childrenListA[ii]); - } - xfree(childrenListA); - childrenListA = NULL; - xfree(childrenCountA); - childrenCountA = NULL; - childrenCountTot = -999999; - nChildLists = -88888; - - /* - * Parents - */ - for(ii = 0; ii < nParentLevels * Plaxton_bucketsPerLevel; ii++){ - freeList(&parentListA[ii]); - } - xfree(parentListA); - parentListA = NULL; - nParentLevels = -8888; - bitsPerLevel = -8888; - Plaxton_bucketsPerLevel = -8888; - for(ii = 0; ii < BITS_PER_KEY; ii++){ - freeList(&highestMatchA[ii]); - } - xfree(highestMatchA); - highestMatchA = NULL; + assert(nChildLists > 0); /* Are we initialized? */ + for (ii = 0; ii < nChildLists; ii++) { + freeList(&childrenListA[ii]); + } + xfree(childrenListA); + childrenListA = NULL; + xfree(childrenCountA); + childrenCountA = NULL; + childrenCountTot = -999999; + nChildLists = -88888; + + /* + * Parents + */ + for (ii = 0; ii < nParentLevels * Plaxton_bucketsPerLevel; ii++) { + freeList(&parentListA[ii]); + } + xfree(parentListA); + parentListA = NULL; + nParentLevels = -8888; + bitsPerLevel = -8888; + Plaxton_bucketsPerLevel = -8888; + for (ii = 0; ii < BITS_PER_KEY; ii++) { + freeList(&highestMatchA[ii]); + } + xfree(highestMatchA); + highestMatchA = NULL; } @@ -307,7 +301,7 @@ * * freeList -- * - * Free all elements on a list of NodeKeys + * Free all elements on a list of HintCacheNodeKeys * * Arguments: * type1 arg1 -- description. @@ -321,15 +315,17 @@ *----------------------------------------------------4.16.1998-------- */ static void -freeList(List_Links *list) +freeList(dlink_list *list) { - NodeKey *k; - assert(list); - while(!List_IsEmpty(list)){ - k = (NodeKey *)List_First(list); - List_Remove((List_Links *)k); - xfree(k); - } + dlink_node *node; + HintCacheNodeKey *k; + + assert(list); + for (node = list->head ; node; node = node->next) { + k = node->data; + dlinkDelete(node, list); + xfree(k); + } } /* @@ -352,20 +348,20 @@ * *----------------------------------------------------4.9.1998--------- */ -void -plaxtonAddChild (struct sockaddr_in *child) +void +plaxtonAddChild(struct sockaddr_in *child) { - NodeKey *key; - - assert(initialized); - assert(nChildLists > 0); /* Are we initialized? */ - key = (NodeKey *)xmalloc(sizeof(NodeKey)); - NodeKey_Init(key, child); - if(childFind(key)){ - xfree(key); - return; - } - childAdd(key); + HintCacheNodeKey *key; + + assert(initialized); + assert(nChildLists > 0); /* Are we initialized? */ + key = (HintCacheNodeKey *) xmalloc(sizeof(HintCacheNodeKey)); + hintCacheNodeKeyInit(key, child); + if (childFind(key)) { + xfree(key); + return; + } + childAdd(key); } /* @@ -386,27 +382,28 @@ * *------------------------------------------------------4.9.1998----- */ -void +void plaxtonRemoveChild(struct sockaddr_in *child) { - NodeKey key, *found; - int match; + HintCacheNodeKey key, *found; + int match; - assert(initialized); - assert(nChildLists > 0); /* Are we initialized? */ - NodeKey_Init(&key, child); - found = childFind(&key); - if(found){ - List_Remove((List_Links*)found); - xfree(found); - match = plaxtonMatchBits(key.key, myNodeKey); - childrenCountA[match]--; - childrenCountTot--; - assert(childrenCountA[match] >= 0); - assert(childrenCountTot >= 0); + assert(initialized); + assert(nChildLists > 0); /* Are we initialized? */ + hintCacheNodeKeyInit(&key, child); + found = childFind(&key); + if (found) { + dlinkDelete(&found->links, + List_Remove((dlink_node *) found); + xfree(found); + match = plaxtonMatchBits(key.key, myNodeKey); + childrenCountA[match]--; + childrenCountTot--; + assert(childrenCountA[match] >= 0); + assert(childrenCountTot >= 0); + return; + } return; - } - return; } @@ -432,16 +429,16 @@ int plaxtonCheckIfChild(struct sockaddr_in *child) { - NodeKey key, *found; - - assert(initialized); - assert(nChildLists > 0); /* Are we initialized? */ - NodeKey_Init(&key, child); - found = childFind(&key); - if(found != NULL){ - return 1; - } - return 0; + HintCacheNodeKey key, *found; + + assert(initialized); + assert(nChildLists > 0); /* Are we initialized? */ + hintCacheNodeKeyInit(&key, child); + found = childFind(&key); + if (found != NULL) { + return 1; + } + return 0; } @@ -482,44 +479,43 @@ * *---------------------------------------------------5.1.1998------ */ -int -plaxtonChildQIndex (URLKey *key, int iAmRoot, int *amILeaf) +int +plaxtonChildQIndex(URLKey * key, int iAmRoot, int *amILeaf) { - int match; - int leafCheck; + int match; + int leafCheck; - assert(initialized); - assert(nChildLists > 0); /* Are we initialized? */ + assert(initialized); + assert(nChildLists > 0); /* Are we initialized? */ - if(iAmRoot){ - if(/*childrenCountTot > 0*/ 1){ /* XXX */ - *amILeaf = 0; - return nChildLists - 1; - } - else{ - *amILeaf = 1; - return -999; - } - } - - match = plaxtonMatchBits(key->key, myNodeKey); - /* - * Check to see if I am a leaf for this object by looking - * at all childlists for children that match me in fewer bits - * than this object. If all such lists are empty, than I am - * a leaf. This is less inefficient than it seems. The expected - * number of queues I have to check is less than (1 + .5 + .25 + ...) - * (since I match in 0 bits half the time, ... ) - */ - *amILeaf = 1; - for(leafCheck = match - 1; leafCheck >= 0; leafCheck--){ - if(!List_IsEmpty(&childrenListA[leafCheck])){ - *amILeaf = 0; - break; + if (iAmRoot) { + if ( /*childrenCountTot > 0 */ 1) { /* XXX */ + *amILeaf = 0; + return nChildLists - 1; + } else { + *amILeaf = 1; + return -999; + } + } + + match = plaxtonMatchBits(key->key, myNodeKey); + /* + * Check to see if I am a leaf for this object by looking + * at all childlists for children that match me in fewer bits + * than this object. If all such lists are empty, than I am + * a leaf. This is less inefficient than it seems. The expected + * number of queues I have to check is less than (1 + .5 + .25 + ...) + * (since I match in 0 bits half the time, ... ) + */ + *amILeaf = 1; + for (leafCheck = match - 1; leafCheck >= 0; leafCheck--) { + if (!List_IsEmpty(&childrenListA[leafCheck])) { + *amILeaf = 0; + break; + } } - } - return match; + return match; } /* @@ -541,11 +537,12 @@ * *-------------------------------------------------------4.10.1998--- */ -int plaxtonNChildrenQs (void) +int +plaxtonNChildrenQs(void) { - assert(initialized); - assert(nChildLists > 0); /* Are we initialized? */ - return nChildLists; + assert(initialized); + assert(nChildLists > 0); /* Are we initialized? */ + return nChildLists; } @@ -580,39 +577,39 @@ * *----------------------------------------------------4.10.1998------- */ -int -plaxtonGetChildAddrs (int qIndex, struct sockaddr_in **retAddrAP) +int +plaxtonGetChildAddrs(int qIndex, struct sockaddr_in **retAddrAP) { - int count; - int imatch; - NodeKey *current; - int check; - - assert(initialized); - for(imatch = 0, count = 0; - imatch <= qIndex; - imatch++){ - count += childrenCountA[imatch]; - } - if(!count){ - *retAddrAP = NULL; - return 0; - } - *retAddrAP=(struct sockaddr_in *)xmalloc(count * sizeof(struct sockaddr_in)); - for(imatch = 0, count = 0; - imatch <= qIndex; - imatch++){ - check = 0; - LIST_FORALL2(&childrenListA[imatch], NodeKey *, current){ - check++; - (*retAddrAP)[count] = NodeKey_GetAddr(current); - count++; - debug(HCPLAX_DEBUG, 2, "plaxtonGetChildAddrs: sending msg to child %s\n", - inet_ntoa((*retAddrAP)[count].sin_addr)); - } - assert(check == childrenCountA[imatch]); - } - return count; + dlink_node *node; + int count; + int imatch; + HintCacheNodeKey *current; + int check; + + assert(initialized); + for (imatch = 0, count = 0; imatch <= qIndex; imatch++) { + count += childrenCountA[imatch]; + } + if (!count) { + *retAddrAP = NULL; + return 0; + } + *retAddrAP = + (struct sockaddr_in *) xmalloc(count * sizeof(struct sockaddr_in)); + for (imatch = 0, count = 0; imatch <= qIndex; imatch++) { + check = 0; + for (node = childrenListA[imatch].head; node; node = node->next) { + current = node->data; + check++; + (*retAddrAP)[count] = hintCacheNodeKeyGetAddr(current); + count++; + debug(HCPLAX_DEBUG, 2) + ("plaxtonGetChildAddrs: sending msg to child %s\n", + inet_ntoa((*retAddrAP)[count].sin_addr)); + } + assert(check == childrenCountA[imatch]); + } + return count; } @@ -642,16 +639,16 @@ * *----------------------------------------------------4.15.1998------- */ -int -plaxtonNParentQs (void) +int +plaxtonNParentQs(void) { - int normalParentCount, rootCaseCount; - - assert(initialized); - assert(parentListA != NULL); - normalParentCount = nParentLevels * Plaxton_bucketsPerLevel; - rootCaseCount = BITS_PER_KEY; - return normalParentCount + rootCaseCount; + int normalParentCount, rootCaseCount; + + assert(initialized); + assert(parentListA != NULL); + normalParentCount = nParentLevels * Plaxton_bucketsPerLevel; + rootCaseCount = BITS_PER_KEY; + return normalParentCount + rootCaseCount; } @@ -703,57 +700,56 @@ *----------------------------------------------------4.19.1998--------- */ int -plaxtonParentQIndex(URLKey *key, int *amIRoot) +plaxtonParentQIndex(URLKey * key, int *amIRoot) { - int match; - int nextLevelMatch; - int found, pindex; - - assert(initialized); - /* XXX */ - match = plaxtonMatchBits(key->key, myNodeKey); - if(match == nParentLevels * bitsPerLevel){ + int match; + int nextLevelMatch; + int found, pindex; + + assert(initialized); + /* XXX */ + match = plaxtonMatchBits(key->key, myNodeKey); + if (match == nParentLevels * bitsPerLevel) { + /* + * Match all bits. I am root! + */ + *amIRoot = 1; + return -9999999; + } + + /* + * Try for full or partial match at next level. + */ + nextLevelMatch = ((match + bitsPerLevel) / bitsPerLevel) * bitsPerLevel; + found = scanForParentMatch(nextLevelMatch, match + 1, key, + &pindex, amIRoot); + if (found) { + assert(!*amIRoot); + return normalParentIndex(pindex); + } + + /* - * Match all bits. I am root! + * I match in match bits, and didn't find anyone that matches + * in more. But, there may be other nodes that match the object + * in the same number of bits (but differ from me in some higher bit). + * We all need to agree on whom among us is the root. We need + * to do so in a way that avoids loops (and hopefully which + * gets everyone to agree on the same root.) Solution: if + * an object matches me in k bits and I know of no node + * that matches the object in more than k bits, choose as + * the root for that object, the node that matches the + * object (and me) in k bits and which has the highest + * known HintCacheNodeKey. */ - *amIRoot = 1; - return -9999999; - } - - /* - * Try for full or partial match at next level. - */ - nextLevelMatch = ((match + bitsPerLevel) / bitsPerLevel) * bitsPerLevel; - found = scanForParentMatch(nextLevelMatch, match+1, key, - &pindex, amIRoot); - if(found){ - assert(!*amIRoot); - return normalParentIndex(pindex); - } - - - /* - * I match in match bits, and didn't find anyone that matches - * in more. But, there may be other nodes that match the object - * in the same number of bits (but differ from me in some higher bit). - * We all need to agree on whom among us is the root. We need - * to do so in a way that avoids loops (and hopefully which - * gets everyone to agree on the same root.) Solution: if - * an object matches me in k bits and I know of no node - * that matches the object in more than k bits, choose as - * the root for that object, the node that matches the - * object (and me) in k bits and which has the highest - * known NodeKey. - */ - assert(!List_IsEmpty(&highestMatchA[match])); - if(((NodeKey *)List_First(&highestMatchA[match]))->key == myNodeKey){ - *amIRoot = 1; - return -999999; - } - else{ - *amIRoot = 0; - return highestMatchIndex(match); - } + assert(!List_IsEmpty(&highestMatchA[match])); + if (((HintCacheNodeKey *) List_First(&highestMatchA[match]))->key == myNodeKey) { + *amIRoot = 1; + return -999999; + } else { + *amIRoot = 0; + return highestMatchIndex(match); + } } @@ -796,62 +792,62 @@ *------------------------------------------------------------------ */ static int -scanForParentMatch(int maxTry, int minTry, const URLKey *key, - int *parentIndexRet, int *amIRootRet) +scanForParentMatch(int maxTry, int minTry, const URLKey * key, + int *parentIndexRet, int *amIRootRet) { - GenericKey tryKey; - int matchBits, permuteBits, permuteMax, ipermute; - int tryIndex; - int found = 0, bestIndex = -999999; - struct sockaddr_in bestSin, trySin; - - /* - * This code assumes that we are looking to match - * a "level" in the tree. - */ - assert(maxTry % bitsPerLevel == 0); - assert(maxTry - minTry < bitsPerLevel); + HintCacheNodeKey *nk; + HintCacheKey tryKey; + int matchBits, permuteBits, permuteMax, ipermute; + int tryIndex; + int found = 0, bestIndex = -999999; + struct sockaddr_in bestSin, trySin; - for(matchBits = maxTry; matchBits >= minTry; matchBits--){ /* - * Split the address into two parts, a set of low-order bits - * that must match the target and a set of high-order - * bits that are "don't care" for which we'll try all - * permutations. + * This code assumes that we are looking to match + * a "level" in the tree. */ - permuteBits = maxTry - matchBits; - permuteMax = (1 << permuteBits) - 1; - for(ipermute = 0; ipermute <= permuteMax; ipermute++){ - tryKey = makeMatchKey(key, matchBits, ipermute); - tryIndex = fullMatchIndex(tryKey); - if(!List_IsEmpty(&parentListA[tryIndex])){ - if(!found){ - found = 1; - *amIRootRet = 0; - bestSin = NodeKey_GetAddr((NodeKey *) - List_First(&parentListA[tryIndex])); - bestIndex = tryIndex; - } - else{ - trySin = NodeKey_GetAddr((NodeKey *) - List_First(&parentListA[tryIndex])); - if(HCHier_compareDistanceFromMe(bestSin.sin_addr, - trySin.sin_addr) > 0){ - bestSin = trySin; - bestIndex = tryIndex; + assert(maxTry % bitsPerLevel == 0); + assert(maxTry - minTry < bitsPerLevel); + + for (matchBits = maxTry; matchBits >= minTry; matchBits--) { + /* + * Split the address into two parts, a set of low-order bits + * that must match the target and a set of high-order + * bits that are "don't care" for which we'll try all + * permutations. + */ + permuteBits = maxTry - matchBits; + permuteMax = (1 << permuteBits) - 1; + for (ipermute = 0; ipermute <= permuteMax; ipermute++) { + tryKey = makeMatchKey(key, matchBits, ipermute); + tryIndex = fullMatchIndex(tryKey); + if (parentListA[tryIndex].head != 0) { + /* parentListA[tryIndex] is not empty */ + nk = parentListA[tryIndex].head->data; + if (!found) { + found = 1; + *amIRootRet = 0; + bestSin = hintCacheNodeKeyGetAddr(nk); + bestIndex = tryIndex; + } else { + trySin = hintCacheNodeKeyGetAddr(nk); + if (HCHier_compareDistanceFromMe(bestSin.sin_addr, + trySin.sin_addr) > 0) { + bestSin = trySin; + bestIndex = tryIndex; + assert(*amIRootRet == 0); + } + } + } + } + if (found) { assert(*amIRootRet == 0); - } + *parentIndexRet = bestIndex; + return 1; } - } - } - if(found){ - assert(*amIRootRet == 0); - *parentIndexRet = bestIndex; - return 1; - } - } /* for matchBits */ - assert(!found); - return 0; + } /* for matchBits */ + assert(!found); + return 0; } @@ -878,16 +874,16 @@ * *------------------------------------------------------------------ */ -static GenericKey -makeMatchKey(const URLKey *key, int matchBits, int permuteVal) +static HintCacheKey +makeMatchKey(const URLKey * key, int matchBits, int permuteVal) { - GenericKey tryKey, matchMask; + HintCacheKey tryKey, matchMask; - matchMask = (((GenericKey)1) << matchBits) - 1; - tryKey = (key->key & matchMask) | (permuteVal << matchBits); - return tryKey; + matchMask = (((HintCacheKey) 1) << matchBits) - 1; + tryKey = (key->key & matchMask) | (permuteVal << matchBits); + return tryKey; } - + /* *------------------------------------------------------------------ @@ -914,7 +910,7 @@ static int highestMatchIndex(int match) { - return maxParentBucket + 1 + match; + return maxParentBucket + 1 + match; } /* @@ -941,8 +937,8 @@ static int normalParentIndex(int bucket) { - assert(bucket <= maxParentBucket); - return bucket; + assert(bucket <= maxParentBucket); + return bucket; } /* @@ -968,11 +964,11 @@ static int firstLevelBucketForMatch(int match) { - int level; - - assert(match <= BITS_PER_KEY); - level = (match/bitsPerLevel) * Plaxton_bucketsPerLevel; - return level; + int level; + + assert(match <= BITS_PER_KEY); + level = (match / bitsPerLevel) * Plaxton_bucketsPerLevel; + return level; } @@ -997,44 +993,41 @@ * *----------------------------------------------------4.16.1998-------- */ -int -plaxtonGetParentAddr (int index, struct sockaddr_in *retAddr) +int +plaxtonGetParentAddr(int index, struct sockaddr_in *retAddr) { - assert(initialized); - assert(index >= 0); - assert(parentListA != NULL); - if(index <= maxParentBucket){ - if(!List_IsEmpty(&parentListA[index])){ - *retAddr = ((NodeKey *)List_First(&parentListA[index]))->addr; - debug(HCPLAX_DEBUG, 2, - "plaxtonGetParentAddr: Sending msg to parent %s\n", - inet_ntoa(retAddr->sin_addr)); - return 0; - } - else{ - return 1; - } - } - else{ - /* XXX index = index - maxParentBucket; */ - index = index - maxParentBucket - 1; - assert(index < BITS_PER_KEY); + assert(initialized); assert(index >= 0); - /* - * List always contains at least me - */ - assert(!List_IsEmpty(&highestMatchA[index])); - if(((NodeKey *)List_First(&highestMatchA[index]))->key == myNodeKey){ - return 1; - } - else{ - *retAddr = ((NodeKey *)List_First(&highestMatchA[index]))->addr; - debug(HCPLAX_DEBUG, 2, - "plaxtonGetParentAddr: Sending msg to parent %s\n", - inet_ntoa(retAddr->sin_addr)); - return 0; + assert(parentListA != NULL); + if (index <= maxParentBucket) { + if (!List_IsEmpty(&parentListA[index])) { + *retAddr = ((HintCacheNodeKey *) List_First(&parentListA[index]))->addr; + debug(HCPLAX_DEBUG, 2) + ("plaxtonGetParentAddr: Sending msg to parent %s\n", + inet_ntoa(retAddr->sin_addr)); + return 0; + } else { + return 1; + } + } else { + /* XXX index = index - maxParentBucket; */ + index = index - maxParentBucket - 1; + assert(index < BITS_PER_KEY); + assert(index >= 0); + /* + * List always contains at least me + */ + assert(!List_IsEmpty(&highestMatchA[index])); + if (((HintCacheNodeKey *) List_First(&highestMatchA[index]))->key == myNodeKey) { + return 1; + } else { + *retAddr = ((HintCacheNodeKey *) List_First(&highestMatchA[index]))->addr; + debug(HCPLAX_DEBUG, 2) + ("plaxtonGetParentAddr: Sending msg to parent %s\n", + inet_ntoa(retAddr->sin_addr)); + return 0; + } } - } } /* @@ -1058,13 +1051,13 @@ void plaxtonAddNode(struct sockaddr_in *newNode) { - assert(initialized); - assert(newNode); -#if 1 /* XXX! - disabling parent&child lists */ - addNodeParentList(newNode); + assert(initialized); + assert(newNode); +#if 1 /* XXX! - disabling parent&child lists */ + addNodeParentList(newNode); #endif - addNodeHighestMatch(newNode); - return; + addNodeHighestMatch(newNode); + return; } /* @@ -1085,14 +1078,14 @@ * *-----------------------------------------------------4.16.1998------ */ -void +void plaxtonRemoveNode(struct sockaddr_in *goneNode) { - assert(initialized); - assert(goneNode); - removeNodeParentList(goneNode); - removeNodeHighestMatch(goneNode); - return; + assert(initialized); + assert(goneNode); + removeNodeParentList(goneNode); + removeNodeHighestMatch(goneNode); + return; } /* @@ -1114,17 +1107,17 @@ * *-----------------------------------------------------4.16.1998------- */ -void +void plaxtonchangeDistance(struct sockaddr_in *changeDistNode) { - assert(initialized); - assert(changeDistNode); - changeDistanceParentList(changeDistNode); - /* - * Don't need to tell HighestMatch list since that one is - * not sorted by distance. - */ - return; + assert(initialized); + assert(changeDistNode); + changeDistanceParentList(changeDistNode); + /* + * Don't need to tell HighestMatch list since that one is + * not sorted by distance. + */ + return; } /* @@ -1148,41 +1141,42 @@ static void addNodeParentList(struct sockaddr_in *addNode) { - NodeKey *n; - int index; - NodeKey *current; - struct sockaddr_in s1, s2; + HintCacheNodeKey *n; + int index; + HintCacheNodeKey *current; + struct sockaddr_in s1, s2; - n = (NodeKey *)xmalloc(sizeof(NodeKey)); - assert(n); - NodeKey_Init(n, addNode); + n = (HintCacheNodeKey *) xmalloc(sizeof(HintCacheNodeKey)); + assert(n); + hintCacheNodeKeyInit(n, addNode); - index = parentListIndex(n); + index = parentListIndex(n); - if(List_IsEmpty(&parentListA[index])){ - List_Insert((List_Links *)n, LIST_ATFRONT(&parentListA[index])); - return; - } - else{ - LIST_FORALL2(&parentListA[index], NodeKey *, current){ - if(HCHier_compareDistanceFromMe(NodeKey_GetAddr(current).sin_addr, - addNode->sin_addr) > 0){ - List_Insert((List_Links *)n, LIST_BEFORE(current)); + if (List_IsEmpty(&parentListA[index])) { + List_Insert((dlink_node *) n, LIST_ATFRONT(&parentListA[index])); return; - } - /* - * Check invariant that list is sorted by distance from me. - */ - if((List_Links *)current != LIST_ATREAR(&parentListA[index])){ - s1 = NodeKey_GetAddr(current); - s2 = NodeKey_GetAddr((NodeKey *)List_Next((List_Links *)current)); - assert( HCHier_compareDistanceFromMe(s1.sin_addr, s2.sin_addr) <= 0); - } - } - } - List_Insert((List_Links *)n, LIST_ATREAR(&parentListA[index])); - return; + } else { + LIST_FORALL2(&parentListA[index], HintCacheNodeKey *, current) { + if (HCHier_compareDistanceFromMe(hintCacheNodeKeyGetAddr(current).sin_addr, + addNode->sin_addr) > 0) { + List_Insert((dlink_node *) n, LIST_BEFORE(current)); + return; + } + /* + * Check invariant that list is sorted by distance from me. + */ + if ((dlink_node *) current != LIST_ATREAR(&parentListA[index])) { + s1 = hintCacheNodeKeyGetAddr(current); + s2 = hintCacheNodeKeyGetAddr((HintCacheNodeKey *) List_Next((dlink_node *) + current)); + assert(HCHier_compareDistanceFromMe(s1.sin_addr, + s2.sin_addr) <= 0); + } + } + } + List_Insert((dlink_node *) n, LIST_ATREAR(&parentListA[index])); + return; } /* @@ -1206,30 +1200,31 @@ static void removeNodeParentList(struct sockaddr_in *goneNode) { - int index; - NodeKey n, *current; - struct sockaddr_in s1, s2; - - NodeKey_Init(&n, goneNode); - - index = parentListIndex(&n); - - - LIST_FORALL2(&parentListA[index], NodeKey *, current){ - if(!NodeKey_Compare(&n, current)){ - List_Remove((List_Links *)current); - xfree(current); - return; - } - /* - * Check invariant that list is sorted by distance from me. - */ - if((List_Links *)current != LIST_ATREAR(&parentListA[index])){ - s1 = NodeKey_GetAddr(current); - s2 = NodeKey_GetAddr((NodeKey *)List_Next((List_Links *)current)); - assert(HCHier_compareDistanceFromMe(s1.sin_addr, s2.sin_addr) <= 0); + int index; + dlink_node *node; + HintCacheNodeKey n, *current; + struct sockaddr_in s1, s2; + + hintCacheNodeKeyInit(&n, goneNode); + + index = parentListIndex(&n); + + for (node = parentListA[index]; node; node = node->next) { + current = node->data; + if (!hintCacheNodeKeyCompare(&n, current)) { + dlinkDelete(node, &parentListA[index]); + xfree(current); + return; + } + /* + * Check invariant that list is sorted by distance from me. + */ + if ((dlink_node *) current != LIST_ATREAR(&parentListA[index])) { + s1 = hintCacheNodeKeyGetAddr(current); + s2 = hintCacheNodeKeyGetAddr((HintCacheNodeKey *) List_Next((dlink_node *) current)); + assert(hintCacheHierCompareDistanceFromMe(s1.sin_addr, s2.sin_addr) <= 0); + } } - } } /* @@ -1258,8 +1253,8 @@ static void changeDistanceParentList(struct sockaddr_in *changeDistNode) { - removeNodeParentList(changeDistNode); - addNodeParentList(changeDistNode); + removeNodeParentList(changeDistNode); + addNodeParentList(changeDistNode); } @@ -1283,9 +1278,9 @@ *----------------------------------------------------4.19.1998------ */ static int -parentListIndex(NodeKey *n) +parentListIndex(HintCacheNodeKey * n) { - return fullMatchIndex(n->key); + return fullMatchIndex(n->key); } /* @@ -1308,23 +1303,24 @@ *-----------------------------------------------------4.19.1998------ */ static int -fullMatchIndex(GenericKey k) +fullMatchIndex(HintCacheKey k) { - int bits, levelsThatMatch, indexInBucket, index; - - bits = plaxtonMatchBits(k, myNodeKey); - if(bits == nParentLevels * bitsPerLevel){ - /* - * I am root! want to match in all bits in last level - * This will force system to get right indexInBucket in - * last level. - */ - bits--; - } - levelsThatMatch = bits / bitsPerLevel; - indexInBucket = (k >> (levelsThatMatch * bitsPerLevel)) % Plaxton_bucketsPerLevel; - index = firstLevelBucketForMatch(bits) + indexInBucket; - return index; + int bits, levelsThatMatch, indexInBucket, index; + + bits = plaxtonMatchBits(k, myNodeKey); + if (bits == nParentLevels * bitsPerLevel) { + /* + * I am root! want to match in all bits in last level + * This will force system to get right indexInBucket in + * last level. + */ + bits--; + } + levelsThatMatch = bits / bitsPerLevel; + indexInBucket = + (k >> (levelsThatMatch * bitsPerLevel)) % Plaxton_bucketsPerLevel; + index = firstLevelBucketForMatch(bits) + indexInBucket; + return index; } @@ -1352,19 +1348,19 @@ static void addNodeHighestMatch(struct sockaddr_in *addNode) { - NodeKey n; - int match, imatch; + HintCacheNodeKey n; + int match, imatch; - NodeKey_Init(&n, addNode); + hintCacheNodeKeyInit(&n, addNode); - match = plaxtonMatchBits(n.key, myNodeKey); - if(match == BITS_PER_KEY){ - match--; - } - for(imatch = 0; imatch <= match; imatch++){ - matchInsert(&highestMatchA[imatch], addNode); - } - return; + match = plaxtonMatchBits(n.key, myNodeKey); + if (match == BITS_PER_KEY) { + match--; + } + for (imatch = 0; imatch <= match; imatch++) { + matchInsert(&highestMatchA[imatch], addNode); + } + return; } /* @@ -1386,30 +1382,35 @@ *-------------------------------------------------------4.16.1998---- */ static void -matchInsert(List_Links *l, struct sockaddr_in *a) +matchInsert(dlink_list *l, struct sockaddr_in *a) { - NodeKey *current, *n; + HintCacheNodeKey *current, *n; + dlink_node *node; + n = (HintCacheNodeKey *) xmalloc(sizeof(HintCacheNodeKey)); + assert(n); + hintCacheNodeKeyInit(n, a); + + /* + * Each list always contains at least me. + */ + assert(l->head != 0); - n = (NodeKey *)xmalloc(sizeof(NodeKey)); - assert(n); - NodeKey_Init(n, a); - - /* - * Each list always contains at least me. - */ - assert(!List_IsEmpty(l)); - - LIST_FORALL2(l, NodeKey *, current){ - assert(current->key != n->key); - if(current->key < n->key){ - List_Insert((List_Links *)n, LIST_BEFORE((List_Links *)current)); - return; - } - } - assert(((NodeKey *)List_Last(l))->key >= n->key); - List_Insert((List_Links *)n, LIST_ATREAR((l))); - return; + for (node = l->head; node; node = node->next) { + current = node->data; + assert(current->key != n->key); + if (current->key < n->key) { + /* Put 'n' right before 'current' */ + n->next = current; + n->prev = current->prev; + current->prev = current; + n->prev->next = n; + return; + } + } + assert(((HintCacheNodeKey *) l->tail->data)->key >= n->key); + dlinkAddTail(n, &n->links, l); + return; } /* @@ -1434,19 +1435,19 @@ static void removeNodeHighestMatch(struct sockaddr_in *goneNode) { - NodeKey n; - int match, imatch; + HintCacheNodeKey n; + int match, imatch; - NodeKey_Init(&n, goneNode); + hintCacheNodeKeyInit(&n, goneNode); - match = plaxtonMatchBits(n.key, myNodeKey); - if(match == BITS_PER_KEY){ - match --; - } - for(imatch = 0; imatch <= match; imatch++){ - matchRemove(&highestMatchA[imatch], goneNode); - } - return; + match = plaxtonMatchBits(n.key, myNodeKey); + if (match == BITS_PER_KEY) { + match--; + } + for (imatch = 0; imatch <= match; imatch++) { + matchRemove(&highestMatchA[imatch], goneNode); + } + return; } /* @@ -1468,24 +1469,26 @@ *--------------------------------------------------4.16.1998----------- */ static void -matchRemove(List_Links *l, struct sockaddr_in *a) +matchRemove(dlink_llist *list, struct sockaddr_in *a) { - NodeKey *current, n; + HintCacheNodeKey *current, n; + dlink_node *node; + + hintCacheNodeKeyInit(&n, a); + /* + * Each list always contains at least me. + */ + assert(list->head != 0); - NodeKey_Init(&n, a); - /* - * Each list always contains at least me. - */ - assert(!List_IsEmpty(l)); - - LIST_FORALL2(l, NodeKey *, current){ - if(!NodeKey_Compare(current, &n)){ - List_Remove((List_Links *)current); - xfree(current); - return; + for (node = list->head; node; node = node->next) { + current = node->data; + if (!hintCacheNodeKeyCompare(current, &n)) { + dlinkDelete(node, list); + xfree(current); + return; + } } - } - return; + return; } /* @@ -1507,24 +1510,24 @@ * *------------------------------------------------------------------ */ -int +int plaxtonCheckIfParent(URLKey key, struct sockaddr_in *candidate) { - int index, amIRoot; - struct sockaddr_in real; + int index, amIRoot; + struct sockaddr_in real; - assert(initialized); - index = plaxtonParentQIndex(&key, &amIRoot); - if(amIRoot){ - return 0; - } - if(plaxtonGetParentAddr(index, &real)){ + assert(initialized); + index = plaxtonParentQIndex(&key, &amIRoot); + if (amIRoot) { + return 0; + } + if (plaxtonGetParentAddr(index, &real)) { + return 0; + } + if (candidate->sin_addr.s_addr == real.sin_addr.s_addr) { + return 1; + } return 0; - } - if(candidate->sin_addr.s_addr == real.sin_addr.s_addr){ - return 1; - } - return 0; } @@ -1551,17 +1554,17 @@ *------------------------------------------------4.9.1998---------- */ static void -childAdd(NodeKey *key) +childAdd(HintCacheNodeKey * key) { - int l; + int l; - l = plaxtonMatchBits(key->key, myNodeKey); - assert(l <= nChildLists); - List_Insert((List_Links*)key, LIST_ATFRONT(&childrenListA[l])); - childrenCountA[l]++; - childrenCountTot++; - assert(childFind(key)); - return; + l = plaxtonMatchBits(key->key, myNodeKey); + assert(l <= nChildLists); + dlinkAdd(key, &key->links, childrenListA[l]); + childrenCountA[l]++; + childrenCountTot++; + assert(childFind(key)); + return; } /* @@ -1582,20 +1585,22 @@ * *-------------------------------------------------4.9.1998--------- */ -static NodeKey * -childFind(NodeKey *key) +static HintCacheNodeKey * +childFind(HintCacheNodeKey * key) { - int l; - NodeKey *current; - - l = plaxtonMatchBits(key->key, myNodeKey); - assert(l <= nChildLists); - LIST_FORALL2(&childrenListA[l], NodeKey *, current){ - if(!NodeKey_Compare(current, key)){ - return current; + HintCacheNodeKey *current; + dlink_node *node; + int l; + + l = plaxtonMatchBits(key->key, myNodeKey); + assert(l <= nChildLists); + for (node = childrenListA[l].head; node ; node = node->next) { + current = node->data; + if (!hintCacheNodeKeyCompare(current, key)) { + return current; + } } - } - return NULL; + return NULL; } @@ -1619,19 +1624,17 @@ *-----------------------------------------------------4.10.1998------- */ int -plaxtonMatchBits(GenericKey k1, GenericKey k2) +plaxtonMatchBits(HintCacheKey k1, HintCacheKey k2) { - int ibit; - GenericKey mask; - - for(ibit = 0, mask = 0x1; - ibit < nChildLists - 1; - ibit++, mask = mask << 1){ - if((k1 & mask) != (k2 & mask)){ - return ibit; + int ibit; + HintCacheKey mask; + + for (ibit = 0, mask = 0x1; ibit < nChildLists - 1; ibit++, mask = mask << 1) { + if ((k1 & mask) != (k2 & mask)) { + return ibit; + } } - } - return ibit; + return ibit; } @@ -1653,10 +1656,10 @@ * *------------------------------------------------------------------ */ -GenericKey +HintCacheKey plaxtonmyNodeKey(void) { - return myNodeKey; + return myNodeKey; } @@ -1683,21 +1686,26 @@ void plaxtonSelfTest() { - printf("plaxtonSelfTest..."); fflush(stdout); - testMakeMatchKey(); - neighborsOutgoing = (HCNet *)xmalloc(sizeof(HCNet)); - assert(neighborsOutgoing); - printf("."); fflush(stdout); - HCNet_Init(neighborsOutgoing); - HCNet_SetTestMode(neighborsOutgoing); - selfTestChildren(); - printf("."); fflush(stdout); - selfTestParents(); - printf("."); fflush(stdout); - HCNet_Destroy(neighborsOutgoing); - xfree(neighborsOutgoing); - printf(".Done.\n"); fflush(stdout); - return; + printf("plaxtonSelfTest..."); + fflush(stdout); + testMakeMatchKey(); + neighborsOutgoing = (HCNet *) xmalloc(sizeof(HCNet)); + assert(neighborsOutgoing); + printf("."); + fflush(stdout); + HCNet_Init(neighborsOutgoing); + HCNet_SetTestMode(neighborsOutgoing); + selfTestChildren(); + printf("."); + fflush(stdout); + selfTestParents(); + printf("."); + fflush(stdout); + HCNet_Destroy(neighborsOutgoing); + xfree(neighborsOutgoing); + printf(".Done.\n"); + fflush(stdout); + return; } /* @@ -1721,101 +1729,111 @@ static void selfTestChildren() { - int iaddr; - struct sockaddr_in n0; - static int CHECK_ADDR_BEGIN = 1000; - static int CHECK_ADDR_END = 2000; - static int CHECK_NOT_THERE_END = 3000; - static URLKey urlMatchAll, urlMatchNone, urlMatchOne, urlMatchEight; - int amILeaf = -1; - int childCount, allChildren; - struct sockaddr_in *childrenA = NULL; - - assert(CHECK_ADDR_END > CHECK_ADDR_BEGIN); - assert(CHECK_ADDR_END < CHECK_NOT_THERE_END); - - - - allChildren = CHECK_ADDR_END - CHECK_ADDR_BEGIN; - plaxtonInit(8); - - assert(sizeof(URLKey) == sizeof(GenericKey)); /* bypassing normal init */ - urlMatchAll.key = myNodeKey; - urlMatchNone.key = ~myNodeKey; - urlMatchOne.key = (~myNodeKey) ^ 0x1; - urlMatchEight.key = (~myNodeKey) ^ 0xFF; - - assert(plaxtonNChildrenQs() == sizeof(GenericKey) * 8 + 1); - amILeaf = -1; - assert(plaxtonChildQIndex(&urlMatchAll, 0, &amILeaf) == sizeof(GenericKey) * 8); - assert(amILeaf == 1); - amILeaf = -1; - assert(plaxtonChildQIndex(&urlMatchNone, 0, &amILeaf) == 0); - assert(amILeaf == 1); - amILeaf = -1; - assert(plaxtonChildQIndex(&urlMatchOne, 0, &amILeaf) == 1); - assert(amILeaf == 1); - amILeaf = -1; - assert(plaxtonChildQIndex(&urlMatchEight, 0, &amILeaf) == 8); - assert(amILeaf == 1); - childrenA = (struct sockaddr_in *)0x888888; - childCount = plaxtonGetChildAddrs(15, &childrenA); - assert(childCount == 0); - assert(childrenA == NULL); - - for(iaddr = CHECK_ADDR_BEGIN; iaddr < CHECK_ADDR_END; iaddr++){ - n0.sin_addr.s_addr = iaddr; n0.sin_port = 0; - plaxtonAddChild(&n0); - } - - childCount = plaxtonGetChildAddrs(sizeof(GenericKey) * 8, &childrenA); - assert(childCount == allChildren); - assert(childrenA != NULL); - assert(selfTestFindAddr(CHECK_ADDR_BEGIN, childrenA, childCount)); - assert(selfTestFindAddr((CHECK_ADDR_BEGIN + CHECK_ADDR_END) / 2, - childrenA, childCount)); - assert(selfTestFindAddr(CHECK_ADDR_END - 1, childrenA, childCount)); - assert(!selfTestFindAddr(CHECK_ADDR_END, childrenA, childCount)); - xfree(childrenA); - - /* - * The nodes we inserted as children were random. Assuming - * we inserted a reasonable number of them, it would be - * surprizing if more than, say, 60% matched us in the - * lowest bit or if fewer than, say, 40% match us in the - * lowest bit - */ - if(allChildren >= 1000){ - childCount = plaxtonGetChildAddrs(0, &childrenA); - if(allChildren * 0.6 < childCount){ - printf("WARNING WARNING WARNING WARNING\n"); - printf("WARNING: Plaxton saw unlikely distribution of random children.\n"); - printf("WARNING: (too many). This is very nearly an assertion failure.\n"); - } - if(allChildren * 0.4 > childCount){ - printf("WARNING WARNING WARNING WARNING\n"); - printf("WARNING: Plaxton saw unlikely distribution of random children.\n"); - printf("WARNING: (too few). This is very nearly an assertion failure.\n"); - } + int iaddr; + struct sockaddr_in n0; + static int CHECK_ADDR_BEGIN = 1000; + static int CHECK_ADDR_END = 2000; + static int CHECK_NOT_THERE_END = 3000; + static URLKey urlMatchAll, urlMatchNone, urlMatchOne, urlMatchEight; + int amILeaf = -1; + int childCount, allChildren; + struct sockaddr_in *childrenA = NULL; + + assert(CHECK_ADDR_END > CHECK_ADDR_BEGIN); + assert(CHECK_ADDR_END < CHECK_NOT_THERE_END); + + + + allChildren = CHECK_ADDR_END - CHECK_ADDR_BEGIN; + plaxtonInit(8); + + assert(sizeof(URLKey) == sizeof(HintCacheKey)); /* bypassing normal init */ + urlMatchAll.key = myNodeKey; + urlMatchNone.key = ~myNodeKey; + urlMatchOne.key = (~myNodeKey) ^ 0x1; + urlMatchEight.key = (~myNodeKey) ^ 0xFF; + + assert(plaxtonNChildrenQs() == sizeof(HintCacheKey) * 8 + 1); + amILeaf = -1; + assert(plaxtonChildQIndex(&urlMatchAll, 0, + &amILeaf) == sizeof(HintCacheKey) * 8); + assert(amILeaf == 1); + amILeaf = -1; + assert(plaxtonChildQIndex(&urlMatchNone, 0, &amILeaf) == 0); + assert(amILeaf == 1); + amILeaf = -1; + assert(plaxtonChildQIndex(&urlMatchOne, 0, &amILeaf) == 1); + assert(amILeaf == 1); + amILeaf = -1; + assert(plaxtonChildQIndex(&urlMatchEight, 0, &amILeaf) == 8); + assert(amILeaf == 1); + childrenA = (struct sockaddr_in *) 0x888888; + childCount = plaxtonGetChildAddrs(15, &childrenA); + assert(childCount == 0); + assert(childrenA == NULL); + + for (iaddr = CHECK_ADDR_BEGIN; iaddr < CHECK_ADDR_END; iaddr++) { + n0.sin_addr.s_addr = iaddr; + n0.sin_port = 0; + plaxtonAddChild(&n0); + } + + childCount = plaxtonGetChildAddrs(sizeof(HintCacheKey) * 8, &childrenA); + assert(childCount == allChildren); + assert(childrenA != NULL); + assert(selfTestFindAddr(CHECK_ADDR_BEGIN, childrenA, childCount)); + assert(selfTestFindAddr((CHECK_ADDR_BEGIN + CHECK_ADDR_END) / 2, + childrenA, childCount)); + assert(selfTestFindAddr(CHECK_ADDR_END - 1, childrenA, childCount)); + assert(!selfTestFindAddr(CHECK_ADDR_END, childrenA, childCount)); xfree(childrenA); - } - else{ - printf("\nWARNING: Plaxton selftest skipping random match check (too few samples\n"); - } - - printf(".");fflush(stdout); - for(iaddr = CHECK_ADDR_BEGIN; iaddr < CHECK_ADDR_END; iaddr++){ - n0.sin_addr.s_addr = iaddr; n0.sin_port = 0; - assert(plaxtonCheckIfChild(&n0)); - plaxtonRemoveChild(&n0); - } - printf(".");fflush(stdout); - for(iaddr = CHECK_ADDR_BEGIN; iaddr < CHECK_NOT_THERE_END; iaddr++){ - n0.sin_addr.s_addr = iaddr; n0.sin_port = 0; - assert(!plaxtonCheckIfChild(&n0)); - } - plaxtonDestroy(); - printf(".OK\n"); + + /* + * The nodes we inserted as children were random. Assuming + * we inserted a reasonable number of them, it would be + * surprizing if more than, say, 60% matched us in the + * lowest bit or if fewer than, say, 40% match us in the + * lowest bit + */ + if (allChildren >= 1000) { + childCount = plaxtonGetChildAddrs(0, &childrenA); + if (allChildren * 0.6 < childCount) { + printf("WARNING WARNING WARNING WARNING\n"); + printf + ("WARNING: Plaxton saw unlikely distribution of random children.\n"); + printf + ("WARNING: (too many). This is very nearly an assertion failure.\n"); + } + if (allChildren * 0.4 > childCount) { + printf("WARNING WARNING WARNING WARNING\n"); + printf + ("WARNING: Plaxton saw unlikely distribution of random children.\n"); + printf + ("WARNING: (too few). This is very nearly an assertion failure.\n"); + } + xfree(childrenA); + } else { + printf + ("\nWARNING: Plaxton selftest skipping random match check (too few samples\n"); + } + + printf("."); + fflush(stdout); + for (iaddr = CHECK_ADDR_BEGIN; iaddr < CHECK_ADDR_END; iaddr++) { + n0.sin_addr.s_addr = iaddr; + n0.sin_port = 0; + assert(plaxtonCheckIfChild(&n0)); + plaxtonRemoveChild(&n0); + } + printf("."); + fflush(stdout); + for (iaddr = CHECK_ADDR_BEGIN; iaddr < CHECK_NOT_THERE_END; iaddr++) { + n0.sin_addr.s_addr = iaddr; + n0.sin_port = 0; + assert(!plaxtonCheckIfChild(&n0)); + } + plaxtonDestroy(); + printf(".OK\n"); } @@ -1842,18 +1860,19 @@ static int selfTestFindAddr(int addr, struct sockaddr_in *childrenA, int childCount) { - struct sockaddr_in n0; - int ii; + struct sockaddr_in n0; + int ii; - assert(childrenA != NULL); - n0.sin_addr.s_addr = addr; n0.sin_port = 0; - for(ii = 0; ii < childCount; ii++){ - assert(childrenA[ii].sin_port == 0); - if(childrenA[ii].sin_addr.s_addr == n0.sin_addr.s_addr){ - return 1; + assert(childrenA != NULL); + n0.sin_addr.s_addr = addr; + n0.sin_port = 0; + for (ii = 0; ii < childCount; ii++) { + assert(childrenA[ii].sin_port == 0); + if (childrenA[ii].sin_addr.s_addr == n0.sin_addr.s_addr) { + return 1; + } } - } - return 0; + return 0; } @@ -1878,11 +1897,11 @@ static void selfTestParents(void) { - testParentsBinaryTree(); - testParentsMultiRootCase(); - testParentsInternals(); - testParentsInternals2(); - stressTestParents(); + testParentsBinaryTree(); + testParentsMultiRootCase(); + testParentsInternals(); + testParentsInternals2(); + stressTestParents(); } /* @@ -1907,120 +1926,119 @@ static void testParentsBinaryTree(void) { - int myId, targetId, caseCount; - struct sockaddr_in parents[4], retAddr; - int ii, hops, qIndex, iAmRoot; - NodeKey key; - URLKey targetURLKey; - - /* XXX Make sure that entire code merge happens. Funny little bug in - * tools.h that we fixed. - */ - parents[0].sin_addr.s_addr = 10; - parents[0].sin_port = 0; - parents[1].sin_addr.s_addr = 11; - parents[1].sin_port = 0; - assert(SINCMP(&parents[0], &parents[1])); /* if this fails, bug in SINCMP */ - - /* - * Try this test from every point of view - */ - for(myId = 0; myId < 4; myId++){ - plaxtonInit(1); - assert(plaxtonNParentQs() == 192); + int myId, targetId, caseCount; + struct sockaddr_in parents[4], retAddr; + int ii, hops, qIndex, iAmRoot; + HintCacheNodeKey key; + URLKey targetURLKey; + /* XXX Make sure that entire code merge happens. Funny little bug in + * tools.h that we fixed. + */ + parents[0].sin_addr.s_addr = 10; + parents[0].sin_port = 0; + parents[1].sin_addr.s_addr = 11; + parents[1].sin_port = 0; + assert(SINCMP(&parents[0], &parents[1])); /* if this fails, bug in SINCMP */ - /* - * Cheat to force my key to do right thing + /* + * Try this test from every point of view */ - myNodeKey = (GenericKey)myId; - for(ii = 0; ii < BITS_PER_KEY; ii++){ - assert(!List_IsEmpty(&highestMatchA[ii])); - ((NodeKey *)List_First(&highestMatchA[ii]))->key = myNodeKey; - } - - for(caseCount = 1; caseCount <= 3; caseCount++){ - /* - * Do all combinations of bottom two bits except my own - */ - targetId = myId ^ caseCount; - /* - * Search for a node that matches desired bits - */ - for(ii = 0; ; ii++){ - parents[caseCount].sin_addr.s_addr = myId * 1000 + ii; - parents[caseCount].sin_port = 0; - NodeKey_Init(&key, &parents[caseCount]); - if((key.key & 0x3) == targetId){ - if(caseCount == 1){ - assert((key.key & 0x2) == (myNodeKey & 0x2)); - assert((key.key & 0x1) != (myNodeKey & 0x1)); - hops = 1; - } - else{ - assert((key.key & 0x2) != (myNodeKey & 0x2)); - hops = 2; - } - HCHier_newNode(&parents[caseCount], hops, 999); + for (myId = 0; myId < 4; myId++) { + plaxtonInit(1); + assert(plaxtonNParentQs() == 192); + - break; + /* + * Cheat to force my key to do right thing + */ + myNodeKey = (HintCacheKey) myId; + for (ii = 0; ii < BITS_PER_KEY; ii++) { + assert(highestMatchA[ii].head != 0); + ((HintCacheNodeKey *) highestMatchA[ii].head->data)->key = myNodeKey; + } + + for (caseCount = 1; caseCount <= 3; caseCount++) { + /* + * Do all combinations of bottom two bits except my own + */ + targetId = myId ^ caseCount; + /* + * Search for a node that matches desired bits + */ + for (ii = 0;; ii++) { + parents[caseCount].sin_addr.s_addr = myId * 1000 + ii; + parents[caseCount].sin_port = 0; + hintCacheNodeKeyInit(&key, &parents[caseCount]); + if ((key.key & 0x3) == targetId) { + if (caseCount == 1) { + assert((key.key & 0x2) == (myNodeKey & 0x2)); + assert((key.key & 0x1) != (myNodeKey & 0x1)); + hops = 1; + } else { + assert((key.key & 0x2) != (myNodeKey & 0x2)); + hops = 2; + } + HCHier_newNode(&parents[caseCount], hops, 999); + + break; + } + } } - } - } - /* - * Case 0: same in all bits - */ - targetURLKey.key = myId; - qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); - assert(iAmRoot); + /* + * Case 0: same in all bits + */ + targetURLKey.key = myId; + qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); + assert(iAmRoot); - /* - * Case 1: differ in bit 0 --> queue is at level 0 - * and the (key & 0x1)th queue within level 0 - */ - targetURLKey.key = myId ^ 0x1; - qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); - assert(!iAmRoot); - assert(qIndex == ((unsigned)targetURLKey.key & 0x1)); - assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); - assert(retAddr.sin_addr.s_addr == parents[1].sin_addr.s_addr); - assert(plaxtonCheckIfParent(targetURLKey, &parents[1])); - assert(!plaxtonCheckIfParent(targetURLKey, &parents[2])); - assert(!plaxtonCheckIfParent(targetURLKey, &parents[3])); + /* + * Case 1: differ in bit 0 --> queue is at level 0 + * and the (key & 0x1)th queue within level 0 + */ + targetURLKey.key = myId ^ 0x1; + qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); + assert(!iAmRoot); + assert(qIndex == ((unsigned) targetURLKey.key & 0x1)); + assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); + assert(retAddr.sin_addr.s_addr == parents[1].sin_addr.s_addr); + assert(plaxtonCheckIfParent(targetURLKey, &parents[1])); + assert(!plaxtonCheckIfParent(targetURLKey, &parents[2])); + assert(!plaxtonCheckIfParent(targetURLKey, &parents[3])); - /* - * Case 2: differ in bit 1; same bit 0 --> queue is - * at level 1 and the (key & 0x1)the queue within level 1 - */ - targetURLKey.key = myId ^ 0x2; - qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); - assert(!iAmRoot); - assert(qIndex == 2 + (((unsigned)targetURLKey.key & 0x2)>>1)); - assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); - assert(retAddr.sin_addr.s_addr == parents[2].sin_addr.s_addr); - assert(!plaxtonCheckIfParent(targetURLKey, &parents[1])); - assert(plaxtonCheckIfParent(targetURLKey, &parents[2])); - assert(!plaxtonCheckIfParent(targetURLKey, &parents[3])); + /* + * Case 2: differ in bit 1; same bit 0 --> queue is + * at level 1 and the (key & 0x1)the queue within level 1 + */ + targetURLKey.key = myId ^ 0x2; + qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); + assert(!iAmRoot); + assert(qIndex == 2 + (((unsigned) targetURLKey.key & 0x2) >> 1)); + assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); + assert(retAddr.sin_addr.s_addr == parents[2].sin_addr.s_addr); + assert(!plaxtonCheckIfParent(targetURLKey, &parents[1])); + assert(plaxtonCheckIfParent(targetURLKey, &parents[2])); + assert(!plaxtonCheckIfParent(targetURLKey, &parents[3])); - /* - * Case 3: differ in bits 0 and 1; should be same as case 1 - */ - targetURLKey.key = myId ^ 0x3; - qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); - assert(!iAmRoot); - assert(qIndex == ((unsigned)targetURLKey.key & 0x1)); - assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); - assert(retAddr.sin_addr.s_addr == parents[1].sin_addr.s_addr); - assert(plaxtonCheckIfParent(targetURLKey, &parents[1])); - assert(!plaxtonCheckIfParent(targetURLKey, &parents[2])); - assert(!plaxtonCheckIfParent(targetURLKey, &parents[3])); - - plaxtonDestroy(); - } + /* + * Case 3: differ in bits 0 and 1; should be same as case 1 + */ + targetURLKey.key = myId ^ 0x3; + qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); + assert(!iAmRoot); + assert(qIndex == ((unsigned) targetURLKey.key & 0x1)); + assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); + assert(retAddr.sin_addr.s_addr == parents[1].sin_addr.s_addr); + assert(plaxtonCheckIfParent(targetURLKey, &parents[1])); + assert(!plaxtonCheckIfParent(targetURLKey, &parents[2])); + assert(!plaxtonCheckIfParent(targetURLKey, &parents[3])); + + plaxtonDestroy(); + } } /* @@ -2047,66 +2065,65 @@ static void testParentsMultiRootCase(void) { - int eligibleFound, ii; - struct sockaddr_in sin, maxAddr, retAddr; - static unsigned int nodeMask = 0xFF; - static unsigned int objMask = 0x3F; - GenericKey maxKey; - URLKey targetURLKey; - int qIndex, iAmRoot; - NodeKey anotherNodeKey; - - plaxtonInit(2); - - assert(objMask < nodeMask); - assert((objMask & nodeMask) == objMask); - - /* - * Create a bunch of nodes that are eligible to be the root for - * for an object that matches them (and us) in objMask bits - * and mismatches in the next bit - */ - /* XXX targetURLKey.key = (myNodeKey & objMask) ^ (nodeMask ^ objMask);*/ - targetURLKey.key = (myNodeKey & nodeMask) ^ (nodeMask ^ objMask); - - qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); - assert(iAmRoot); - - maxKey = myNodeKey; - maxAddr = Config.Sockaddr.http->s; - ii = 0; - eligibleFound = 0; - while(eligibleFound < 40){ - sin.sin_addr.s_addr = 10000 + ii; - sin.sin_port = 0; - NodeKey_Init(&anotherNodeKey, &sin); - if((anotherNodeKey.key & nodeMask) == (myNodeKey & nodeMask)){ - eligibleFound++; - HCHier_newNode(&sin, 1000, 999); - if(anotherNodeKey.key > maxKey){ - /* - * Found new root for object - */ - maxKey = anotherNodeKey.key; - maxAddr = sin; - } - } + int eligibleFound, ii; + struct sockaddr_in sin, maxAddr, retAddr; + static unsigned int nodeMask = 0xFF; + static unsigned int objMask = 0x3F; + HintCacheKey maxKey; + URLKey targetURLKey; + int qIndex, iAmRoot; + HintCacheNodeKey anotherNodeKey; + + plaxtonInit(2); + + assert(objMask < nodeMask); + assert((objMask & nodeMask) == objMask); + + /* + * Create a bunch of nodes that are eligible to be the root for + * for an object that matches them (and us) in objMask bits + * and mismatches in the next bit + */ + /* XXX targetURLKey.key = (myNodeKey & objMask) ^ (nodeMask ^ objMask); */ + targetURLKey.key = (myNodeKey & nodeMask) ^ (nodeMask ^ objMask); + qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); - if(maxKey == myNodeKey){ - assert(iAmRoot); - } - if(iAmRoot){ - assert(maxKey == myNodeKey); + assert(iAmRoot); + + maxKey = myNodeKey; + maxAddr = Config.Sockaddr.http->s; + ii = 0; + eligibleFound = 0; + while (eligibleFound < 40) { + sin.sin_addr.s_addr = 10000 + ii; + sin.sin_port = 0; + hintCacheNodeKeyInit(&anotherNodeKey, &sin); + if ((anotherNodeKey.key & nodeMask) == (myNodeKey & nodeMask)) { + eligibleFound++; + HCHier_newNode(&sin, 1000, 999); + if (anotherNodeKey.key > maxKey) { + /* + * Found new root for object + */ + maxKey = anotherNodeKey.key; + maxAddr = sin; + } + } + qIndex = plaxtonParentQIndex(&targetURLKey, &iAmRoot); + if (maxKey == myNodeKey) { + assert(iAmRoot); + } + if (iAmRoot) { + assert(maxKey == myNodeKey); + } else { + assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); + assert(qIndex >= nParentLevels * plaxtonbucketsPerLevel); + assert(retAddr.sin_addr.s_addr == maxAddr.sin_addr.s_addr); + } + ii++; } - else{ - assert(plaxtonGetParentAddr(qIndex, &retAddr) == 0); - assert(qIndex >= nParentLevels * plaxtonbucketsPerLevel); - assert(retAddr.sin_addr.s_addr == maxAddr.sin_addr.s_addr); - } - ii++; - } - plaxtonDestroy(); - + plaxtonDestroy(); + } @@ -2133,50 +2150,50 @@ static void stressTestParents(void) { - int ii; - URLKey targetURLKey; - int qIndex, iamRoot; - static int BIG = 100; /* should be much bigger for good test */ - struct sockaddr_in sin, retAddr; - - plaxtonInit(4); - - for(ii = 0; ii < BIG; ii++){ - sin.sin_addr.s_addr = 100000 + ii; - sin.sin_port = 0; - HCHier_newNode(&sin, 1000, 999); - } - - for(ii = 0; ii < BIG; ii++){ - sin.sin_addr.s_addr = 100000 + ii; - sin.sin_port = 0; - plaxtonchangeDistance(&sin); - } - - - for(ii = 0; ii < BIG; ii++){ - targetURLKey.key = ii; - qIndex = plaxtonParentQIndex(&targetURLKey, &iamRoot); - if(!iamRoot){ - assert(!plaxtonGetParentAddr(qIndex, &retAddr)); - } - } - - for(ii = 0; ii < BIG; ii++){ - sin.sin_addr.s_addr = 100000 + ii; - sin.sin_port = 0; - HCHier_delNode(&sin, 1000, 1999); - } - - for(ii = 0; ii < BIG; ii++){ - targetURLKey.key = ii; - qIndex = plaxtonParentQIndex(&targetURLKey, &iamRoot); - if(!iamRoot){ - assert(!plaxtonGetParentAddr(qIndex, &retAddr)); + int ii; + URLKey targetURLKey; + int qIndex, iamRoot; + static int BIG = 100; /* should be much bigger for good test */ + struct sockaddr_in sin, retAddr; + + plaxtonInit(4); + + for (ii = 0; ii < BIG; ii++) { + sin.sin_addr.s_addr = 100000 + ii; + sin.sin_port = 0; + HCHier_newNode(&sin, 1000, 999); } - } - plaxtonDestroy(); + for (ii = 0; ii < BIG; ii++) { + sin.sin_addr.s_addr = 100000 + ii; + sin.sin_port = 0; + plaxtonchangeDistance(&sin); + } + + + for (ii = 0; ii < BIG; ii++) { + targetURLKey.key = ii; + qIndex = plaxtonParentQIndex(&targetURLKey, &iamRoot); + if (!iamRoot) { + assert(!plaxtonGetParentAddr(qIndex, &retAddr)); + } + } + + for (ii = 0; ii < BIG; ii++) { + sin.sin_addr.s_addr = 100000 + ii; + sin.sin_port = 0; + HCHier_delNode(&sin, 1000, 1999); + } + + for (ii = 0; ii < BIG; ii++) { + targetURLKey.key = ii; + qIndex = plaxtonParentQIndex(&targetURLKey, &iamRoot); + if (!iamRoot) { + assert(!plaxtonGetParentAddr(qIndex, &retAddr)); + } + } + + plaxtonDestroy(); } @@ -2203,121 +2220,126 @@ * *------------------------------------------------------------------ */ -static void +static void testParentsInternals(void) { - int ii, targetKey; - NodeKey anotherNodeKey, *current, *next; - GenericKey k; - struct sockaddr_in sin, nodes[16]; - int iAmRoot; - URLKey urlKey; + int ii, targetKey; + HintCacheNodeKey anotherNodeKey, *current, *next; + HintCacheKey k; + struct sockaddr_in sin, nodes[16]; + int iAmRoot; + URLKey urlKey; + dlink_node *node; + + plaxtonInit(2); + myNodeKey = 0; /* Fake it out to make tests easier to write and read */ + + targetKey = 1; + ii = 0; + while (targetKey < 16) { + /* + * Note: netdb only keeps distance info on granularity of + * networks; we want to know what distances there are between + * nodes, so make nodes be on different (hopfully unused) subnets + */ + sin.sin_addr.s_addr = 15000 + ii * 255; + sin.sin_port = 0; + if (netdbHintHops(sin.sin_addr)) + !=0) { + ii++; + continue; /* Someone already used this address and gave it a distance */ + } + hintCacheNodeKeyInit(&anotherNodeKey, &sin); + if ((anotherNodeKey.key & 15) == targetKey) { + nodes[targetKey] = sin; + HCHier_newNode(&sin, targetKey * 1000, 999); + targetKey++; + } + ii++; + } - plaxtonInit(2); - myNodeKey = 0; /* Fake it out to make tests easier to write and read */ + /* + * The level-0 lists should be in sorted order + */ + for (ii = 1; ii <= 3; ii++) { + for (node = parentListA[ii].head; node; node = node->next) { + current = node->data; + if (current != (HintCacheNodeKey *) parentListA[ii].tail->data)) { + next = (HintCacheNodeKey *) List_Next((dlink_node *) current); + assert(!List_IsAtEnd(&parentListA[ii], (dlink_node *) next)); + assert(HCHier_compareDistanceFromMe(hintCacheNodeKeyGetAddr(current). + sin_addr, hintCacheNodeKeyGetAddr(next).sin_addr) + <= 0); + } + } + } - targetKey = 1; ii = 0; - while(targetKey < 16){ /* - * Note: netdb only keeps distance info on granularity of - * networks; we want to know what distances there are between - * nodes, so make nodes be on different (hopfully unused) subnets + * The level-0 lists XX01, XX10, and XX11 should each have + * four elements in the following order: 00--, 01--, 10--, + * and 11-- (where "--" is the index of the list) + */ + for (ii = 1; ii <= 3; ii++) { + assert((&parentListA[ii])->prevPtr + == (&parentListA[ii])->nextPtr->nextPtr->nextPtr->nextPtr); + + k = ((HintCacheNodeKey *) ((&parentListA[ii])->nextPtr))->key; + assert((k & 3) == ii); + assert(((k & 15) >> 2) == 0); /* 00 */ + + k = ((HintCacheNodeKey *) ((&parentListA[ii])->nextPtr->nextPtr))->key; + assert((k & 3) == ii); + assert(((k & 15) >> 2) == 1); /* 01 */ + + k = ((HintCacheNodeKey *) ((&parentListA[ii])->nextPtr->nextPtr->nextPtr))->key; + assert((k & 3) == ii); + assert(((k & 15) >> 2) == 2); /* 10 */ + + k = ((HintCacheNodeKey *) ((&parentListA[ii])->nextPtr->nextPtr->nextPtr-> + nextPtr))->key; + assert((k & 3) == ii); + assert(((k & 15) >> 2) == 3); /* 11 */ + + urlKey.key = 0xFFAA3400 | ii; + assert(plaxtonCheckIfParent(urlKey, &nodes[ii])); + assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == ii); + assert(!iAmRoot); + } + /* + * The level-1 lists 0100, 1000, 1100 should each + * have one element */ - sin.sin_addr.s_addr = 15000 + ii*255; - sin.sin_port = 0; - if(netdbHintHops(sin.sin_addr)) != 0){ - ii++; - continue; /* Someone already used this address and gave it a distance */ - } - NodeKey_Init(&anotherNodeKey, &sin); - if((anotherNodeKey.key & 15) == targetKey){ - nodes[targetKey] = sin; - HCHier_newNode(&sin, targetKey*1000, 999); - targetKey++; - } - ii++; - } - - /* - * The level-0 lists should be in sorted order - */ - for(ii = 1; ii <= 3; ii++){ - LIST_FORALL2(&parentListA[ii], NodeKey *, current){ - if(current != (NodeKey *)List_Last(&parentListA[ii])){ - next = (NodeKey *)List_Next((List_Links *)current); - assert(!List_IsAtEnd(&parentListA[ii], (List_Links *)next)); - assert(HCHier_compareDistanceFromMe(NodeKey_GetAddr(current).sin_addr, - NodeKey_GetAddr(next).sin_addr) - <= 0); - } - } - } - - /* - * The level-0 lists XX01, XX10, and XX11 should each have - * four elements in the following order: 00--, 01--, 10--, - * and 11-- (where "--" is the index of the list) - */ - for(ii = 1; ii <= 3; ii++){ - assert((&parentListA[ii])->prevPtr - == (&parentListA[ii])->nextPtr->nextPtr->nextPtr->nextPtr); - - k = ((NodeKey *)((&parentListA[ii])->nextPtr))->key; - assert((k & 3) == ii); - assert(((k & 15) >> 2) == 0); /* 00 */ - - k = ((NodeKey *)((&parentListA[ii])->nextPtr->nextPtr))->key; - assert((k & 3) == ii); - assert(((k & 15) >> 2) == 1); /* 01 */ - - k = ((NodeKey *)((&parentListA[ii])->nextPtr->nextPtr->nextPtr))->key; - assert((k & 3) == ii); - assert(((k & 15) >> 2) == 2); /* 10 */ - - k = ((NodeKey *)((&parentListA[ii])->nextPtr->nextPtr->nextPtr->nextPtr))->key; - assert((k & 3) == ii); - assert(((k & 15) >> 2) == 3); /* 11 */ - - urlKey.key = 0xFFAA3400 | ii; - assert(plaxtonCheckIfParent(urlKey, &nodes[ii])); - assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == ii); + /* 00 00 is list 4 and is empty */ + assert(List_IsEmpty(&parentListA[4])); + + /* 01 00 is list 5 and has one element "xxx0100" = 4 */ + assert(parentListA[5].nextPtr->nextPtr == &parentListA[5]); + k = ((HintCacheNodeKey *) ((&parentListA[5])->nextPtr))->key; + assert((k & 15) == 4); + urlKey.key = 0xFFAA1204; + assert(plaxtonCheckIfParent(urlKey, &nodes[4])); + assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 5); + assert(!iAmRoot); + + /* 10 00 is list 6 and has one element "xxx1000" = 8 */ + assert(parentListA[6].nextPtr->nextPtr == &parentListA[6]); + k = ((HintCacheNodeKey *) ((&parentListA[6])->nextPtr))->key; + assert((k & 15) == 8); + urlKey.key = 0xFFAA1208; + assert(plaxtonCheckIfParent(urlKey, &nodes[8])); + assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 6); assert(!iAmRoot); - } - /* - * The level-1 lists 0100, 1000, 1100 should each - * have one element - */ - /* 00 00 is list 4 and is empty */ - assert(List_IsEmpty(&parentListA[4])); - - /* 01 00 is list 5 and has one element "xxx0100" = 4 */ - assert(parentListA[5].nextPtr->nextPtr == &parentListA[5]); - k = ((NodeKey *)((&parentListA[5])->nextPtr))->key; - assert((k & 15) == 4); - urlKey.key = 0xFFAA1204; - assert(plaxtonCheckIfParent(urlKey, &nodes[4])); - assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 5); - assert(!iAmRoot); - - /* 10 00 is list 6 and has one element "xxx1000" = 8 */ - assert(parentListA[6].nextPtr->nextPtr == &parentListA[6]); - k = ((NodeKey *)((&parentListA[6])->nextPtr))->key; - assert((k & 15) == 8); - urlKey.key = 0xFFAA1208; - assert(plaxtonCheckIfParent(urlKey, &nodes[8])); - assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 6); - assert(!iAmRoot); - - /* 11 00 is list 7 and has one element "xxx1100" = 12 */ - assert(parentListA[7].nextPtr->nextPtr == &parentListA[7]); - k = ((NodeKey *)((&parentListA[7])->nextPtr))->key; - assert((k & 15) == 12); - urlKey.key = 0xFFAA120C; - assert(plaxtonCheckIfParent(urlKey, &nodes[12])); - assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 7); - assert(!iAmRoot); - plaxtonDestroy(); + /* 11 00 is list 7 and has one element "xxx1100" = 12 */ + assert(parentListA[7].nextPtr->nextPtr == &parentListA[7]); + k = ((HintCacheNodeKey *) ((&parentListA[7])->nextPtr))->key; + assert((k & 15) == 12); + urlKey.key = 0xFFAA120C; + assert(plaxtonCheckIfParent(urlKey, &nodes[12])); + assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 7); + assert(!iAmRoot); + + plaxtonDestroy(); } @@ -2340,46 +2362,47 @@ * *--------------------------------------------------------5.4.1998---- */ -static void -testParentsInternals2(void) +static void testParentsInternals2(void) { - int ii; - struct sockaddr_in sin; - NodeKey anotherNodeKey; - URLKey urlKey; - int iAmRoot; - - plaxtonInit(4); - myNodeKey = 0; /* Fake it out to make tests easier to write and read */ - - ii = 0; - while(1){ - /* - * Note: netdb only keeps distance info on granularity of - * networks; so make nodes be on different (hopfully unused) subnets - */ - sin.sin_addr.s_addr = 15000 + ii*255; - sin.sin_port = 0; - if(netdbHintHops(sin.sin_addr) != 0){ - ii++; - continue; /* Someone already used this address and gave it a distance */ + int ii; + struct sockaddr_in sin; + HintCacheNodeKey anotherNodeKey; + URLKey urlKey; + int iAmRoot; + + plaxtonInit(4); + myNodeKey = 0; /* Fake it out to make tests easier to write and read */ + + ii = 0; + while (1) + { + /* + * Note: netdb only keeps distance info on granularity of + * networks; so make nodes be on different (hopfully unused) subnets + */ + sin.sin_addr.s_addr = 15000 + ii * 255; + sin.sin_port = 0; + if (netdbHintHops(sin.sin_addr) != 0) + { + ii++; + continue; /* Someone already used this address and gave it a distance */ + } + hintCacheNodeKeyInit(&anotherNodeKey, &sin); + /* + * Want 0110 0000 + */ + if ((anotherNodeKey.key & 0xFF) == 0x60) { + HCHier_newNode(&sin, 1000, 999); + break; + } + ii++; } - NodeKey_Init(&anotherNodeKey, &sin); - /* - * Want 0110 0000 - */ - if((anotherNodeKey.key & 0xFF) == 0x60){ - HCHier_newNode(&sin, 1000, 999); - break; - } - ii++; - } - assert((anotherNodeKey.key & 0xFF) == 0x60); - urlKey.key = 0x20; - assert(plaxtonCheckIfParent(urlKey, &sin)); - assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 22); - assert(!iAmRoot); - plaxtonDestroy(); + assert((anotherNodeKey.key & 0xFF) == 0x60); + urlKey.key = 0x20; + assert(plaxtonCheckIfParent(urlKey, &sin)); + assert(plaxtonParentQIndex(&urlKey, &iAmRoot) == 22); + assert(!iAmRoot); + plaxtonDestroy(); } /* @@ -2400,20 +2423,18 @@ * *----------------------------------------------------5.4.1998------ */ -static void -testMakeMatchKey(void) +static void testMakeMatchKey(void) { - URLKey key; - GenericKey ret; + URLKey key; + HintCacheKey ret; - key.key = 0xFFAABBCC; - ret = makeMatchKey(&key, 4, 0); - assert(ret == 0xC); - ret = makeMatchKey(&key, 4, 0xD); - assert(ret = 0xDC); - ret = makeMatchKey(&key, 0, 0xD); - assert(ret = 0xD); + key.key = 0xFFAABBCC; + ret = makeMatchKey(&key, 4, 0); + assert(ret == 0xC); + ret = makeMatchKey(&key, 4, 0xD); + assert(ret = 0xDC); + ret = makeMatchKey(&key, 0, 0xD); + assert(ret = 0xD); } -#endif /* DOTEST */ - +#endif /* DOTEST */ Index: squid/src/cf.data.pre =================================================================== RCS file: /cvsroot/squid-sf//squid/src/cf.data.pre,v retrieving revision 1.43.2.2 retrieving revision 1.43.2.3 diff -u -r1.43.2.2 -r1.43.2.3 --- squid/src/cf.data.pre 8 Jan 2002 09:10:39 -0000 1.43.2.2 +++ squid/src/cf.data.pre 21 May 2002 02:46:42 -0000 1.43.2.3 @@ -1,6 +1,6 @@ # -# $Id: cf.data.pre,v 1.43.2.2 2002/01/08 09:10:39 hno Exp $ +# $Id: cf.data.pre,v 1.43.2.3 2002/05/21 02:46:42 jkay Exp $ # # # SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -3649,7 +3649,7 @@ COMMENT: bytes IFDEF: USE_HINT_CACHE TYPE: int -LOC: Config.Hints.size; +LOC: Config.Hints.size DEFAULT: 83886080 DOC_START This is the size of the hint cache, in bytes. It has to be @@ -3660,7 +3660,7 @@ NAME: hint_cache_assoc IFDEF: USE_HINT_CACHE TYPE: int -LOC: Config.Hints.assoc; +LOC: Config.Hints.assoc DEFAULT: 4 DOC_START Hint cache associativity. Index: squid/src/defines.h =================================================================== RCS file: /cvsroot/squid-sf//squid/src/defines.h,v retrieving revision 1.15.2.2 retrieving revision 1.15.2.3 diff -u -r1.15.2.2 -r1.15.2.3 --- squid/src/defines.h 7 Dec 2001 23:25:32 -0000 1.15.2.2 +++ squid/src/defines.h 21 May 2002 02:46:42 -0000 1.15.2.3 @@ -1,6 +1,6 @@ /* - * $Id: defines.h,v 1.15.2.2 2001/12/07 23:25:32 jkay Exp $ + * $Id: defines.h,v 1.15.2.3 2002/05/21 02:46:42 jkay Exp $ * * * SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -302,7 +302,9 @@ #if USE_HINT_CACHE /* Hint Cache Interface */ -#define HINT_CACHE_VERSION "1.0" /* Protocol version */ +/* Not QUITE compatible with 1.0 due to different tolower treatment + of URLs before md5 coding. */ +#define HINT_CACHE_VERSION "2.0" /* Protocol version */ /* Returns true iff the hint cache is in operation. */ #define HINT_CACHE_ACTIVE() (HCDisk != NULL) @@ -315,6 +317,7 @@ #define HCE_INVALIDATE(hce) ((hce)->ipaddr.s_addr = INADDR_ANY, \ (hce)->key = INVALID_URL_KEY); +#define HINT_CACHE_KEY(e) (((URLKey *) ((e)->hchash.key))) /* Hint protocol event types */ #define HC_InvalToParent 1 Index: squid/src/dist.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/dist.c,v retrieving revision 1.1.2.4 retrieving revision 1.1.2.5 diff -u -r1.1.2.4 -r1.1.2.5 --- squid/src/dist.c 22 Dec 2001 16:34:33 -0000 1.1.2.4 +++ squid/src/dist.c 21 May 2002 02:46:42 -0000 1.1.2.5 @@ -1,5 +1,5 @@ /* - * $Id: dist.c,v 1.1.2.4 2001/12/22 16:34:33 jkay Exp $ + * $Id: dist.c,v 1.1.2.5 2002/05/21 02:46:42 jkay Exp $ * * Distribution network algorithm. * @@ -35,6 +35,7 @@ static char urlbuf[MAX_URL + 48]; +peer *DistAllPeers = 0; /* Create new updatee ds & add to object's updatee list */ Updatee * Index: squid/src/enums.h =================================================================== RCS file: /cvsroot/squid-sf//squid/src/enums.h,v retrieving revision 1.27.2.5 retrieving revision 1.27.2.6 diff -u -r1.27.2.5 -r1.27.2.6 --- squid/src/enums.h 8 Jan 2002 09:10:40 -0000 1.27.2.5 +++ squid/src/enums.h 21 May 2002 02:46:42 -0000 1.27.2.6 @@ -1,6 +1,6 @@ /* - * $Id: enums.h,v 1.27.2.5 2002/01/08 09:10:40 hno Exp $ + * $Id: enums.h,v 1.27.2.6 2002/05/21 02:46:42 jkay Exp $ * * * SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -736,9 +736,18 @@ }; #if USE_HINT_CACHE -enum HintCacheNet_State {HC_uninitialized, HC_filling, HC_full, HC_destroyed}; +enum HintCacheNet_State { + HC_uninitialized, + HC_filling, + HC_full, + HC_destroyed +}; + -typedef enum HintCacheNeighborActionE {NEIGHBOR_ADD, NEIGHBOR_REMOVE} NeighborAction; +typedef enum HintCacheNeighborActionE { + NEIGHBOR_ADD, + NEIGHBOR_REMOVE +} NeighborAction; #endif /* USE_HINT_CACHE */ Index: squid/src/globals.h =================================================================== RCS file: /cvsroot/squid-sf//squid/src/globals.h,v retrieving revision 1.14.2.2 retrieving revision 1.14.2.3 diff -u -r1.14.2.2 -r1.14.2.3 --- squid/src/globals.h 7 Dec 2001 23:25:32 -0000 1.14.2.2 +++ squid/src/globals.h 21 May 2002 02:46:42 -0000 1.14.2.3 @@ -1,6 +1,6 @@ /* - * $Id: globals.h,v 1.14.2.2 2001/12/07 23:25:32 jkay Exp $ + * $Id: globals.h,v 1.14.2.3 2002/05/21 02:46:42 jkay Exp $ * * * SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -159,9 +159,17 @@ extern int incoming_sockets_accepted; extern peer *DistAllPeers; #if USE_HINT_CACHE +extern hash_table hint_table; extern const URLKey INVALID_URL_KEY; extern HintCacheDisk *HCDisk; -#endif +extern HintCacheNet *parentOutgoingA; +extern HintCacheNet *childrenOutgoingA; +extern HintCacheNet *neighborsOutgoing; +extern HintCacheDisk *hcDisk; +#if USE_DYNAMIC_HIERARCHY + +#endif /* USE_DYNAMIC_HIERARCHY */ +#endif /* USE_HINT_CACHE */ #if defined(_SQUID_MSWIN_) || defined(_SQUID_CYGWIN_) extern unsigned int WIN32_OS_version; /* 0 */ extern char *WIN32_OS_string; Index: squid/src/http.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/http.c,v retrieving revision 1.17.2.4 retrieving revision 1.17.2.5 diff -u -r1.17.2.4 -r1.17.2.5 --- squid/src/http.c 8 Jan 2002 09:10:40 -0000 1.17.2.4 +++ squid/src/http.c 21 May 2002 02:46:42 -0000 1.17.2.5 @@ -1,6 +1,6 @@ /* - * $Id: http.c,v 1.17.2.4 2002/01/08 09:10:40 hno Exp $ + * $Id: http.c,v 1.17.2.5 2002/05/21 02:46:42 jkay Exp $ * * DEBUG: section 11 Hypertext Transfer Protocol (HTTP) * AUTHOR: Harvest Derived @@ -1073,9 +1073,6 @@ storeReleaseRequest(httpState->entry); /* Use consistency protocol for this request */ if (peer->options.dist) { - distNewUpdatee(httpState->entry, - peer->in_addr.sin_addr, - htons(peer->http_port)); httpState->request->flags.distify = 1; } #if DELAY_POOLS Index: squid/src/main.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/main.c,v retrieving revision 1.28.2.4 retrieving revision 1.28.2.5 diff -u -r1.28.2.4 -r1.28.2.5 --- squid/src/main.c 8 Jan 2002 09:10:40 -0000 1.28.2.4 +++ squid/src/main.c 21 May 2002 02:46:42 -0000 1.28.2.5 @@ -1,6 +1,6 @@ /* - * $Id: main.c,v 1.28.2.4 2002/01/08 09:10:40 hno Exp $ + * $Id: main.c,v 1.28.2.5 2002/05/21 02:46:42 jkay Exp $ * * DEBUG: section 1 Startup and Main Loop * AUTHOR: Harvest Derived @@ -346,6 +346,7 @@ authenticateShutdown(); storeDirCloseSwapLogs(); errorClean(); + distInit(); parseConfigFile(ConfigFile); _db_init(Config.Log.log, Config.debugOptions); ipcache_restart(); /* clear stuck entries */ @@ -353,7 +354,6 @@ fqdncache_restart(); /* sigh, fqdncache too */ parseEtcHosts(); errorInitialize(); /* reload error pages */ - distInit(); #if USE_DNSSERVERS dnsInit(); #else @@ -492,7 +492,6 @@ httpReplyInitModule(); /* must go before accepting replies */ errorInitialize(); accessLogInit(); - distInit(); #if USE_IDENT identInit(); #endif @@ -644,6 +643,7 @@ eventInit(); /* eventInit() is required for config parsing */ storeFsInit(); /* required for config parsing */ authenticateSchemeInit(); /* required for config parsign */ + distInit(); /* Needed for fwdall list */ parse_err = parseConfigFile(ConfigFile); if (opt_parse_cfg_only) Index: squid/src/protos.h =================================================================== RCS file: /cvsroot/squid-sf//squid/src/protos.h,v retrieving revision 1.41.2.5 retrieving revision 1.41.2.6 diff -u -r1.41.2.5 -r1.41.2.6 --- squid/src/protos.h 8 Jan 2002 09:10:40 -0000 1.41.2.5 +++ squid/src/protos.h 21 May 2002 02:46:42 -0000 1.41.2.6 @@ -1,6 +1,6 @@ /* - * $Id: protos.h,v 1.41.2.5 2002/01/08 09:10:40 hno Exp $ + * $Id: protos.h,v 1.41.2.6 2002/05/21 02:46:42 jkay Exp $ * * * SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -1353,32 +1353,30 @@ int hintCacheInit(); void hintCacheCreate(); /* create new cache */ void hintCacheDestroy(); -void hintCacheInformLocalCopy(char *url, StoreEntry *); /* tell hierarchy I have a copy */ +void hintCacheInformLocalCopy(StoreEntry *); /* tell hierarchy I have a copy */ void hintCacheInvalLocalCopy(StoreEntry *); /* say I don't have a copy */ int hintCacheActive(); /* Ask hint cache if it is operational. */ struct sockaddr_in *hintCachefindNearest(char *url, struct sockaddr_in *); -/* Hint Cache Primitives */; -void URLKeyInit (URLKey *key, char *url); -void NetURLKeyInit(Net_URLKey *mungedKey, URLKey *key); -void NetURLKeyLocalFormat(Net_URLKey *mungedKey, URLKey *key); - -void NodeKeyInit(NodeKey *k, const struct sockaddr_in *addrP); -int NodeKeyCompare(const NodeKey *k1, const NodeKey *k2); -struct sockaddr_in NodeKeyGetAddr(const NodeKey *k); -GenericKey NodeKKKey(const struct sockaddr_in *addrP); +void hintCacheNodeKeyInit(NodeKey *k, const struct sockaddr_in *addrP); +int hintCacheNodeKeyCompare(const NodeKey *k1, const NodeKey *k2); +struct sockaddr_in hintCacheNodeKeyGetAddr(const NodeKey *k); +HintCacheKey hintCacheNodeKeyKey(const struct sockaddr_in *addrP); void hintCacheEntryInit(HintCacheEntry *, URLKey, struct sockaddr_in *, unsigned int mtime); int hintCacheEntryCompare(HintCacheEntry *e1, HintCacheEntry *e2); -void hintCacheEntryInitNet(Net_HintCacheEntry *mungedEntry, HintCacheEntry *entry); -void hintCacheEntryLocalFormatNet(Net_HintCacheEntry *mungedEntry, HintCacheEntry *entry); +void hintCacheEntryInitNet(HintCacheEntryNet *mungedEntry, HintCacheEntry *entry); +void hintCacheEntryLocalFormatNet(HintCacheEntryNet *mungedEntry, HintCacheEntry *entry); int hintCacheUpdateCompare(HintCacheUpdate *u1, HintCacheUpdate *u2); void hintCacheUpdateInit(HintCacheUpdate *, int action, HintCacheEntry *, int hopcount); -void hintCacheUpdateInitNet(Net_HintCacheUpdate *mungedUpdate, HintCacheUpdate *update); -void hintCacheUpdateLocalFormatNet(Net_HintCacheUpdate *mungedUpdate, HintCacheUpdate *update); +void hintCacheUpdateInitNet(HintCacheUpdateNet *mungedUpdate, HintCacheUpdate *update); +void hintCacheUpdateLocalFormatNet(HintCacheUpdateNet *mungedUpdate, HintCacheUpdate *update); +int hintCacheURLKeyCompare(URLKey *u1, URLKey *u2); +StoreEntry *hintCacheStoreGet(URLKey urlkey); + /* Hint Cache Disk */ void hintCacheDiskInit(HintCacheDisk *d, char *diskPath); @@ -1397,66 +1395,64 @@ void hintCacheEndian_selfTest(void); void hintCacheInitNet(HintCacheNet *n); -int hintCacheNet_IsInitialized(void); - void hintCacheNet_Destroy(HintCacheNet *n); -void hintCacheNet_Enqueue(HintCacheNet *, int action, +int hintCacheNetIsInitialized(void); + void hintCacheNetDestroy(HintCacheNet *n); +void hintCacheNetEnqueue(HintCacheNet *, int action, HintCacheEntry *, int hopcount); -int hintCacheNet_bytesReady(HintCacheNet *n); -void hintCacheNet_Complete(HintCacheNet *n); -void hintCacheNet_Done(HintCacheNet *n); -void hintCacheNet_SendTo(HintCacheNet *, struct sockaddr_in *); -void hintCacheNet_SendJoin(); -void hintCacheNet_DataArrives(char *data, int len, HintCacheNetHeader *hdr, +int hintCacheNetBytesReady(HintCacheNet *n); +void hintCacheNetComplete(HintCacheNet *n); +void hintCacheNetDone(HintCacheNet *n); +void hintCacheNetSendTo(HintCacheNet *, struct sockaddr_in *); +void hintCacheNetSendJoin(); +void hintCacheNetDataArrives(char *data, int len, HintCacheNetHeader *hdr, struct sockaddr_in *source); -void hintCacheNet_SetTestMode(HintCacheNet *n); -int hintCacheNet_GetTestCount(HintCacheNet *n); +void hintCacheNetSetTestMode(HintCacheNet *n); +int hintCacheNetGetTestCount(HintCacheNet *n); -void hintCacheProp_LocalAction(StoreEntry *, int action); -void hintCacheProp_HandleInvalToChild(HintCacheUpdate *update, +void hintCachePropLocalAction(StoreEntry *, int action); +void hintCachePropHandleInvalToChild(HintCacheUpdate *update, struct sockaddr_in *src, int local); -void hintCacheProp_HandleInformToChild(HintCacheUpdate *update, +void hintCachePropHandleInformToChild(HintCacheUpdate *update, struct sockaddr_in *src, int local) ; -void hintCacheProp_HandleInvalToParent(HintCacheUpdate *update, +void hintCachePropHandleInvalToParent(HintCacheUpdate *update, struct sockaddr_in *src, int local); -void hintCacheProp_HandleInformToParent(HintCacheUpdate *update, +void hintCachePropHandleInformToParent(HintCacheUpdate *update, struct sockaddr_in *src, int local); -void hintCacheNodelist_Init(); /* constructor */ -void hintCacheNodelist_Destroy(); /* destructor */ -void hintCacheNodelist_SelfTest(); -void hintCacheNodelist_LocalJoin(); /* I do a join */ -void hintCacheNodelist_LocalLeave(); /* I do a leave */ -int hintCacheNodelist_myStatus(); /* Am I in or out? */ -void hintCacheNodelist_NetJoin(struct sockaddr_in *sin, int hops, long long timeNS); -void hintCacheNodelist_NetLeave(struct sockaddr_in *sin, int hops, long long timeNS); -void hintCacheNodeList_IterStart(HintCacheNodeListIter *iter); -int hintCacheNodeList_IterCheck(HintCacheNodeListIter iter); -void hintCacheNodeList_IterNext(HintCacheNodeListIter *iter); -int hintCacheNodeList_IterGetAddr(HintCacheNodeListIter iter, +void hintCacheNodelistInit(); /* constructor */ +void hintCacheNodelistDestroy(); /* destructor */ +void hintCacheNodelistSelfTest(); +void hintCacheNodelistLocalJoin(); /* I do a join */ +void hintCacheNodelistLocalLeave(); /* I do a leave */ +int hintCacheNodelistMyStatus(); /* Am I in or out? */ +void hintCacheNodelistNetJoin(struct sockaddr_in *sin, int hops, long long timeNS); +void hintCacheNodelistNetLeave(struct sockaddr_in *sin, int hops, long long timeNS); +void hintCacheNodelistIterStart(HintCacheNodeListIter *iter); +int hintCacheNodelistIterCheck(HintCacheNodeListIter iter); +void hintCacheNodelistIterNext(HintCacheNodeListIter *iter); +int hintCacheNodelistIterGetAddr(HintCacheNodeListIter iter, struct sockaddr_in *ret); -void hintCacheNodelist_addMembershipNeighbor(struct sockaddr_in *neighbor); -void hintCacheNodelist_rmMembershipNeighbor(struct sockaddr_in *neighbor); -void hintCacheHier_updateMembershipNeighbor(struct sockaddr_in *neighbor, +void hintCacheHierUpdateMembershipNeighbor(struct sockaddr_in *neighbor, NeighborAction); -void hintCacheHier_Init(); -void hintCacheHier_Destroy(); -int hintCacheHier_compareDistanceFromMe(struct in_addr new, struct in_addr old); -void hintCacheHier_newNode(struct sockaddr_in *sin, int hops, long long time); -void hintCacheHier_delNode(struct sockaddr_in *sin, int hops, long long time); -int hintCacheHier_CheckIfParent(URLKey key, struct sockaddr_in *candidate); -int hintCacheHier_CheckIfChild(struct sockaddr_in *candidate); -void hintCacheHier_AddChild(struct sockaddr_in *child); -void hintCacheHier_RemoveChild(struct sockaddr_in *child); -int hintCacheHier_NChildrenQs(); -int hintCacheHier_ChildQIndex(URLKey *key, int iAmRoot, int *amILeaf); -int hintCacheHier_GetChildAddrs(int qIndex, struct sockaddr_in **retAddr); -int hintCacheHier_NParentQs(); -int hintCacheHier_ParentQIndex(URLKey *key, int *amIRoot); -int hintCacheHier_GetParentAddr(int index, struct sockaddr_in *retAddr); -int hintCacheHier_SendToParent(struct sockaddr_in *src, HintCacheUpdate *update, +void hintCacheHierInit(); +void hintCacheHierDestroy(); +int hintCacheHierCompareDistanceFromMe(struct in_addr new, struct in_addr old); +void hintCacheHierNewNode(struct sockaddr_in *sin, int hops, long long time); +void hintCacheHierDelNode(struct sockaddr_in *sin, int hops, long long time); +int hintCacheHierCheckIfParent(URLKey key, struct sockaddr_in *candidate); +int hintCacheHierCheckIfChild(struct sockaddr_in *candidate); +void hintCacheHierAddChild(struct sockaddr_in *child); +void hintCacheHierRemoveChild(struct sockaddr_in *child); +int hintCacheHierNChildrenQs(); +int hintCacheHierChildQIndex(URLKey *key, int iAmRoot, int *amILeaf); +int hintCacheHierGetChildAddrs(int qIndex, struct sockaddr_in **retAddr); +int hintCacheHierNParentQs(); +int hintCacheHierParentQIndex(URLKey *key, int *amIRoot); +int hintCacheHierGetParentAddr(int index, struct sockaddr_in *retAddr); +int hintCacheHierSendToParent(struct sockaddr_in *src, HintCacheUpdate *update, int msgtype); -int hintCacheHier_SendToSiblings(struct sockaddr_in *src, HintCacheUpdate *update, +int hintCacheHierSendToSiblings(struct sockaddr_in *src, HintCacheUpdate *update, int msgtype, int siblingtype); #ifdef USE_DYNAMIC_HIERARCHY @@ -1479,8 +1475,8 @@ int plaxtonCheckIfChild(struct sockaddr_in *candidate); void plaxtonAddChild(struct sockaddr_in *child); void plaxtonRemoveChild(struct sockaddr_in *child); -int plaxtonMatchBits(GenericKey k1, GenericKey k2); -GenericKey plaxtonMyNodeKey(); +int plaxtonMatchBits(HintCacheKey k1, HintCacheKey k2); +HintCacheKey plaxtonMyNodeKey(); extern int Plaxton_BucketsPerLevel; extern HintCacheNet *Plaxton_parentOutgoingA; Index: squid/src/put.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/Attic/put.c,v retrieving revision 1.1.2.5 retrieving revision 1.1.2.6 diff -u -r1.1.2.5 -r1.1.2.6 --- squid/src/put.c 22 Dec 2001 16:34:33 -0000 1.1.2.5 +++ squid/src/put.c 21 May 2002 02:46:43 -0000 1.1.2.6 @@ -1,5 +1,5 @@ /* - * $Id: put.c,v 1.1.2.5 2001/12/22 16:34:33 jkay Exp $ + * $Id: put.c,v 1.1.2.6 2002/05/21 02:46:43 jkay Exp $ * * DEBUG: section 81 PUT transmission and reception * AUTHOR: Jon Kay, 1997 @@ -147,7 +147,7 @@ sin.sin_family = AF_INET; sin.sin_addr = p->in_addr.sin_addr; - sin.sin_port = p->http_port; + sin.sin_port = htons(p->http_port); putSend(entry, &sin, NULL, NULL, 0); #if USE_ICP_DATA } Index: squid/src/store.c =================================================================== RCS file: /cvsroot/squid-sf//squid/src/store.c,v retrieving revision 1.16.2.1 retrieving revision 1.16.2.2 diff -u -r1.16.2.1 -r1.16.2.2 --- squid/src/store.c 24 Nov 2001 05:51:40 -0000 1.16.2.1 +++ squid/src/store.c 21 May 2002 02:46:43 -0000 1.16.2.2 @@ -1,6 +1,6 @@ /* - * $Id: store.c,v 1.16.2.1 2001/11/24 05:51:40 jkay Exp $ + * $Id: store.c,v 1.16.2.2 2002/05/21 02:46:43 jkay Exp $ * * DEBUG: section 20 Storage Manager * AUTHOR: Harvest Derived @@ -194,12 +194,22 @@ e, storeKeyText(key)); e->hash.key = storeKeyDup(key); hash_join(store_table, &e->hash); +#if USE_HINT_CACHE + if (HINT_CACHE_ACTIVE()) { + e->hchhash.key = e->hash.key; + hash_join(cache_table, &e->hchash); + } +#endif } static void storeHashDelete(StoreEntry * e) { hash_remove_link(store_table, &e->hash); +#if USE_HINT_CACHE + if (HINT_CACHE_ACTIVE()) + hash_remove_link(hint_table, &e->hchash); +#endif storeKeyFree(e->hash.key); e->hash.key = NULL; } @@ -1007,6 +1017,20 @@ storeInitHashValues(); store_table = hash_create(storeKeyHashCmp, store_hash_buckets, storeKeyHashHash); +#if USE_HINT_CACHE + /* + * Need to be able to look up objects from hint + * cache key so we can invalidate obsolete objects + * based on hint cache updates. + * Note: the hint cache key is just the first 8 bytes + * of the 16-byte cache key, so storeKeyHashHash will + * always work. Although, right now, sKHH only looks + * at the first 32 bits anyway, giving double protection. + */ + if (HINT_CACHE_ACTIVE()) + hint_table = hash_create(hintCacheURLKeyCompare, + store_hash_buckets, storeKeyHashHash); +#endif mem_policy = createRemovalPolicy(Config.memPolicy); storeDigestInit(); storeLogOpen(); @@ -1063,6 +1087,12 @@ if (store_digest) cacheDigestDestroy(store_digest); #endif +#if USE_HINT_CACHE + if (HINT_CACHE_ACTIVE()) { + hashFreeMemory(hint_table); + hint_table = NULL; + } +#endif store_digest = NULL; } Index: squid/src/structs.h =================================================================== RCS file: /cvsroot/squid-sf//squid/src/structs.h,v retrieving revision 1.47.2.5 retrieving revision 1.47.2.6 diff -u -r1.47.2.5 -r1.47.2.6 --- squid/src/structs.h 8 Jan 2002 09:10:40 -0000 1.47.2.5 +++ squid/src/structs.h 21 May 2002 02:46:43 -0000 1.47.2.6 @@ -1,6 +1,6 @@ /* - * $Id: structs.h,v 1.47.2.5 2002/01/08 09:10:40 hno Exp $ + * $Id: structs.h,v 1.47.2.6 2002/05/21 02:46:43 jkay Exp $ * * * SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -339,7 +339,7 @@ #if USE_HINT_CACHE struct _URLKey { - GenericKey key; + HintCacheKey key; }; #endif @@ -1555,7 +1555,7 @@ swap_status_t swap_status:3; Updatee *updatees; #if USE_HINT_CACHE - URLKey key; /* 64-bit MD5 hash of URL */ + hash_link hchash; #endif }; @@ -2264,18 +2264,18 @@ /* Hint Cache Interface */ /* - * Primitive data types. All have a Net_ format which has an + * Primitive data types. All have a -Net format which has an * agreed-upon endian-ness. */ -struct _Net_URLKey { - GenericKey mungedKey; +struct _URLKeyNet { + HintCacheKey mungedKey; }; struct _NodeKey { - List_Links links; /* MUST BE FIRST FIELD OF STRUCT */ - GenericKey key; + dlink_node links; + HintCacheKey key; struct sockaddr_in addr; }; @@ -2288,8 +2288,8 @@ }; /* This is what goes onto the net */ -struct _Net_HintCacheEntry { - Net_URLKey mungedKey; +struct _HintCacheEntryNet { + URLKeyNet mungedKey; struct in_addr mungedIpaddr; unsigned short mungedPort; short mungedPad; @@ -2305,13 +2305,13 @@ HintCacheEntry entry; }; -struct _Net_HintCacheUpdate { +struct _HintCacheUpdateNet { unsigned char mungedAction; char mungedHopcount; char mungedUNUSED; char mungedPad1; int mungedPad2; - Net_HintCacheEntry mungedEntry; + HintCacheEntryNet mungedEntry; }; /* Hint Cache Disk */ Index: squid/src/typedefs.h =================================================================== RCS file: /cvsroot/squid-sf//squid/src/typedefs.h,v retrieving revision 1.25.2.4 retrieving revision 1.25.2.5 diff -u -r1.25.2.4 -r1.25.2.5 --- squid/src/typedefs.h 22 Dec 2001 16:34:34 -0000 1.25.2.4 +++ squid/src/typedefs.h 21 May 2002 02:46:43 -0000 1.25.2.5 @@ -1,6 +1,6 @@ /* - * $Id: typedefs.h,v 1.25.2.4 2001/12/22 16:34:34 jkay Exp $ + * $Id: typedefs.h,v 1.25.2.5 2002/05/21 02:46:43 jkay Exp $ * * * SQUID Web Proxy Cache http://www.squid-cache.org/ @@ -371,20 +371,20 @@ /* Hint Cache Interface */ typedef unsigned Net_unsigned; typedef long long unsigned Net_longlong; -typedef unsigned long long GenericKey; +typedef unsigned long long HintCacheKey; typedef struct _URLKey URLKey; -typedef struct _Net_URLKey Net_URLKey; +typedef struct _URLKeyNet URLKeyNet; typedef struct _NodeKey NodeKey; typedef struct _HintCacheEntry HintCacheEntry; -typedef struct _Net_HintCacheEntry Net_HintCacheEntry; +typedef struct _HintCacheEntryNet HintCacheEntryNet; typedef struct _HintCacheUpdate HintCacheUpdate; -typedef struct _Net_HintCacheUpdate Net_HintCacheUpdate; +typedef struct _HintCacheUpdateNet HintCacheUpdateNet; /* Hint Cache Disk */ typedef struct _HintCacheDiskEntry HintCacheDiskEntry; typedef struct _HintCacheDisk HintCacheDisk; -typedef List_Links *HintCacheNodeListIter; +typedef dlink_node *HintCacheNodeListIter; #endif /* USE_HINT_CACHE */ #if USE_ICP_DATA