Dynamic Hierarchical Caching for the World Wide Web

Martha H Greenberg AUP Supervisor: David R. Karger

February 6, 1997

1 The Project

The World Wide Web is a system for distributing documents, including hypertext, images, sound files, plain text, audio, animations and applications. One of the most visible problems for the web today is slow response time due to overloaded networks and servers. Very popular web sites get too many queries at once and respond very slowly or not at all.

A web document is uniquely identified by a Uniform Resource Locator (URL). The URL for a document contains the protocol that should be used to ask for the document, the name of the machine which has the document (the content server), and the pathname by which the machine can identify the document. In the simplest web scheme, a client will directly request the document from the content server every time the user requests to see the document.

Caching is the storage of retrieved documents locally for further use. Therefore, it is not necessary to connect to the content server the next time that document is requested. This technique reduces the number of requests the content server must process. A proxy server is a machine that receives requests from a number of machines; it then either serves the request itself, denies the request or forwards the request to the real server. A proxy cache server is a proxy server that caches the information that went through the proxy. Since the proxy server is usually closer (in terms of network throughput) and less loaded than the content server, the client sees a faster response to their query. Caching also saves network bandwidth to the content server.

In current hierarchical caching schemes, the hierarchy of machines is fixed. Neighbors are other caches which are on the same level of the hierarchy. Parents are on a higher level, and children on a lower level. A cache will make a request to another cache, usually its parent, if it does not have a valid copy of the document being requested. If no other caches have the document, it will request the document from the content server. Machines higher in the hierarchy are responsible indirectly for more clients and will be asked for more distinct documents.

In the Harvest/Squid scheme, each machine knows a list of neighbors and parents to whom it can make requests. The network administrator must give the cache a list of what other caches it can ask, and whether they are neighbors or parents. This list is the same for all documents, so if the cache receives multiple requests for different documents that it does not have, it asks the same set of caches for all of them.

A major problem with current hierarchical caching schemes is that caches near the top of the hierarchy are responsible for a very large number of distinct documents and may become overloaded processing queries for those documents. The ultimate goal of this project is to set up a system in which it is very unlikely for a single caching server to become overloaded with queries relative to other caching servers.

I have been working for David R. Karger in the Algorithms groups of the Theory of Computation Group of the Laboratory for Computer Science. He has designed an algorithm that may solve this problem. My project was intended to determine if this algorithm would work in the current Internet, and if it would be more efficient than the schemes that are currently in use.

The proposed new algorithm differs in that there is a unique hierarchy of parents for each URL. The cache builds this hierarchy in a number of steps. First, an abstract tree of degree d is constructed. This tree and the degree d depend on only on the number of caching servers. Then a hashing function maps (tree node, URL) pairs to caching servers. When the cache gets a request for a document, it picks a random leaf in the abstract tree, computes the path from the leaf to the root, and then maps the abstract tree nodes onto actual caching servers using the URL. The cost to the new algorithm is that the cache must have a near-recent list of all the proxy servers in the cache system. This is a benefit, since no caching server is at the top of any fixed hierarchy, all caching servers will be responsible for about the same number of distinct documents and queries.

I have implemented this algorithm by modifying the Squid caching and proxying system from the National Laboratory for Applied Network Research (developed from the Harvest project at the University of Colorado). In order to do this, I have also extended the currently used cache protocol to allow the machines to communicate which machines on the network are using this algorithm. They also have to pass along where they are in the hierarchy for a particular document, so that the next machine does not have to recompute the entire hierarchy.

I have implemented this algorithm for determining what cache to ask for a particular document. I have also integrated it with Squid so that Squid uses this algorithm for determining what other caches to ask for a document, rather than using its fixed hierarchy.

2 Code Overview

All changes are against Squid version 1.1.3. All the changes to the Squid code are set off by the comments (DH stands for Dynamic Hierarchy):

/* begin DH changes */
/* end DH changes */

When Squid starts up, if it is run with the -d option, the variable opt dynamic hierarchy get set. The rest of the changes are conditional on that variable.

At the startup, Squid gets an initial list of all the hosts in network from another server. Right now, only one server can be specified.

Squid then goes through its primary select loop. In this loop, it checks how long it has been since the last update. If it is longer than the set time, it gets a list of all the changes since the last update.

When Squid gets a request that is not in cache, Squid is told that there is only one neighbor, a parent. Instead of getting this parent from the configuration file, as would be normally done, it calls dhGetParent(). This procedure builds a tree, maps the URL against the unit interval and finds the correct parent for this machine in that tree. This is done in proto.c.

3 Netserv

Netserv uses a simple TCP based protocol to let hosts participate in the network. The client makes a TCP connection to the netserv server on the assigned port (port 8999 was used for this implementation), and sends a request. The possible requests are: join [⟨points⟩], dele, list, since ⟨time⟩, and help. Join adds the host to the network, dele deletes it from the network, list lists all the hosts in the network, since returns all the changes since the specified time and help prints a help message. Join takes an optional argument of the number of points on the unit interval that the host wants to take. Since takes a mandatory argument of a time in seconds since 00:00:00 UTC, January 1, 1970 (the Unix epoch).

The server responds with a three-digit response code followed by a human-readable explanation. In the cases of list, since and help, it also is followed by the requested information. A response code of the form 1xx indicates a usage message, 2xx indicates a successful request and 4xx indicates a failed request.

4 Modified files from the Squid distribution

src/squid.h src/main.c src/proto.c src/Makefile.in squid.h - add the global variables and include files needed for the new functions. main.c - add a flag (-d) to Squid to use the dynamic hierarchy code. get the list of hosts in the network, and keep it updated. proto.c - change the code to call the dynamic functions when necessary, rather than the Squid ones. tell Squid there is only a single parent, and generate that. Makefile.in - Add the new object files to the list of ones needed to generate the Squid binary and build the netserv program.

5 Files added to Squid

chash.h chash.c common.h crc.h crc.c deal.h deal.c dhrand.h dhrand.c getnet.h getnet.c netserv.c

5.1 Procedures

chash.h - includes, defines, structures and procedure declarations that are used in chash.c chash.c - procedures for making a consistent hash.

/* get a number of points for a machine */
int dhGetMachinePoints(char *hostname, int points);

/* add a machine,point pair to the unit interval */
int dhAddMachineToInterval(char *hostname, double d );
/* find the nearest machine to any point on the unit interval */
struct machplace * dhFindNearestMachine(double point);
/* construct the unit interval and fill it with hosts */
int dhBuildUI();
/* construct the tree until we find ourself in it */
int dhBuildTree(char *url, int n);
/* take a hostname, and make an edge out of it.
edge * dhMakeEdge(char *host);
/* take a url and find the immediate parent */
edge * dhGetParent(char *url);
/* return the number of neighbors */
int dhNeighborsCount(edge *dhparent);

common.h - definitions and structures that used in deal.c, getnet.c and netserv.c crc.h - includes, defines, structures and procedure declarations that are used in crc.c crc.c - procedures for generating a crc32 hash.

/* compute the crc32 hash for a string */
long crc32(char *buf, int len);
/* initialization procedure that must be called before crc32 */
void init_crc32();

deal.h - includes, defines, structures and procedure declarations that are used in deal.c deal.c - Handle the requests made in netserv.c or getnet.c.

/* add a host to the host table, check for duplicates */
int addhost(char address[MAXADDR], time_t ntime, int np);

/* delete a host from the host table if it is there */
int delhost(char address[MAXADDR]);
/* print a list that represents the current network state */
int list(int newsockfd);
/* print out all the changes since time stime */
int since(int newsockfd, time_t stime);
/* dump the current network state to the dump file */
int dump();
/* read a dump file and construct a host table from it */
int readdump();

dhrand.h - includes, defines, structures and procedure declarations that are used in dhrand.c dhrand.c - non-system specific version of rand and srand, so that we get reliable results across platforms

/* generate a pseudo-random number */
int dhRand();
/* seed for generating a pseudo-random number */
void dhSrand(seed);

getnet.h - includes, defines, structures and procedure declarations that are used in getnet.c getnet.c - Get what other machines are on the network, and keep this updated.

/* get the initial network */
int getnet();
/* get the changes since ltime */
int getupdate(time_t ltime);
/* parse the log file and do the changes indicated */
int readupdate();

/* add this host to the network */
int addself();
/* delete this host from the network */
int delself();
/* open a socket to the server */
int sopen();

netserv.c - Separate program that will maintain and serve the list of who is on the network.

/* main loop. start up, wait for connections and deal with them */
int main(int argc, char *argv[]);
/* print a usage message */
void nsusage(char *name);
/* check what we received and call the appropriate function */
int deal(char caddr_new[MAXADDR], int newsockfd, time_t ntime,
char buf[MAXLINE], FILE *logPtr);
/* dump and exit on a signal */
int myexit();

A New code

A.1 chash.h

#ifndef CHASH H #define CHASH H

/* the degree of the tree */ #define DEGREE OF TREE 2;

/* structure for a point, machine pair on unit interval */ struct machplace { double position;

char *name;  10

struct machplace *nextmach; }; int dhGetMachinePoints PARAMS((char *hostname, int points)); int dhAddMachineToInterval PARAMS((char *hostname, double d )); char * dhFindNearestMachine PARAMS((double point)); int dhBuildUI PARAMS(()); int dhBuildTree PARAMS((char *url, int n)); edge * dhMakeEdge PARAMS((char *host));

edge * dhGetParent PARAMS((char *url));  20

int dhNeighborsCount PARAMS((edge *dhparent));

#endif /* CHASH H */

A.2 chash.c

#include "squid.h"

extern int num hosts; extern const char *myhostname; extern struct hostinfo *tablePtr; extern struct machplace *uiPtr;

/* get a number of points for a machine */ int

dhGetMachinePoints(char *hostname, int points) {  10

int f; int len = (int) strlen(hostname); /* get the crc32 hash for that hostname */ long init = crc32(hostname,len); /* and use that to seed the pseudo−random numbers */ dhSrand(init);

/* get one pseudo−random number between 0 and 1 for each point */ for(f=0;f<points;f++) {

unsigned int i = dhRand();  20

double d = ((double)i) / ((double)DH RAND MAX);

/* add the machine,point pair to the unit interval */

dhAddMachineToInterval(hostname,d); } return 0; }

/* add a machine,point pair to the unit interval */ int

dhAddMachineToInterval(char *hostname, double d ) {  30

struct machplace *newmach, *lastPtr, *currPtr =uiPtr;

/* go through the unit interval */ while (currPtr != NULL) {

/* save the current place for the next round */ lastPtr = currPtr;

/* deal with duplicates − they will happen eventually */

if (currPtr−>position == d) {  40

int i; d = d + 0.000001; i = dhAddMachineToInterval(hostname,d); return i; } /* find the first higher position in the unit interval */ else if (currPtr−>position > d) {

/* malloc space for a new entry in the table */

newmach = (struct machplace *) malloc(sizeof(struct machplace));  50

if (newmach == NULL){ perror("malloc"); return(−1);

} /* malloc the space for the machine name */ newmach−>name = malloc(strlen(hostname) + 1); if (newmach−>name == NULL) {

perror("malloc"); return(−1);

}  60

/* put the new address and time in the malloc’d space, and point the

* entry’s nexthost pointer to the next entry */ strcpy(newmach−>name,hostname); newmach−>position = d; newmach−>nextmach = currPtr;

lastPtr−>nextmach = newmach;

return(0);

}  70

/* increment to the next entry */ currPtr = currPtr−>nextmach; } /* this should never be reached. */ return −1; }

/* find the nearest machine to any point on the unit interval */ char *

dhFindNearestMachine(double point) {  80

struct machplace *lastPtr, *currPtr =uiPtr;

/* go through the unit interval */ while (currPtr != NULL) {

/* save the current place for the next round */ lastPtr = currPtr; /* find the first higher point */ if (currPtr−>position >= point) {

/* compute the differences between the two nearest points */  90

double upper, lower;

upper = currPtr−>position − point;

lower = lastPtr−>position − point;

/* return the closer point */

if (upper > lower) {

return lastPtr−>name; } else {

return currPtr−>name;

}  100

} } /* if no point is higher, return the last point */ return lastPtr−>name; }

/* construct the unit interval and fill it with hosts */ int dhBuildUI() {

struct hostinfo *thisPtr = tablePtr;  110

int n=0;

/* go through the host table and add the points for each machine */ while (thisPtr != NULL) { dhGetMachinePoints(thisPtr−>addr,3); n++; thisPtr = thisPtr−>nexthost; } return n;

}  120

/* construct the tree until we find outself in it */ int dhBuildTree(char *url, int n) { int i; /* loop through the number of hosts until we find the first occurance

* of ourself */ for (i=1;i>=n;i++) { char u[MAX URL+ sizeof(long)];

double d;  130

char *name; /* calculate the point for that url,number pair */ sprintf(u, "%d%s", i, url); d = crc32(u,sizeof(u)) % ((u int)DH RAND MAX + 1); /* find which machine is closest to this point */ name = dhFindNearestMachine(d); /* when we find ourself, return our position in the tree */ if (name == myhostname) { return n;

}  140

} /* if we never find ourself */ return 0; }

/* take a hostname, and make an edge out of it. */ edge * dhMakeEdge(char *host) { u short http port = CACHE HTTP PORT;

u short icp port = CACHE ICP PORT;  150

int options = 0; int weight = 1; int mcast ttl = 0;

edge *e = NULL; e = xcalloc(1, sizeof(edge)); e−>http port = http port; e−>icp port = icp port; e−>mcast ttl = mcast ttl;

e−>options = options;  160

e−>weight = weight; e−>host = xstrdup(host); e−>pinglist = NULL; e−>typelist = NULL; e−>acls = NULL; e−>icp version = ICP VERSION CURRENT; e−>type = parseNeighborType("parent");

return e;

}  170

/* take a url and find the immediate parent */ edge * dhGetParent(char *url) { int myplace, parentplace; double d; char *name, u[MAX URL+ sizeof(long)]; edge *edge answer; int deg = DEGREE OF TREE;

180

myplace = dhBuildTree(url,num hosts);

if (myplace > 1) { parentplace = myplace / deg;

sprintf(u, "%d%s", parentplace, url); d = crc32(u,sizeof(u)) % ((u int)DH RAND MAX + 1);

name = dhFindNearestMachine(d);  190

edge answer = dhMakeEdge(name); return edge answer; } else { /* we are either at the top of the tree, or not in the tree at all */ return NULL; } }

/* return the number of neighbors */  200

int dhNeighborsCount(edge *dhparent) { /* only one neighbor, else we are at the top of the tree, then none */ if (dhparent == NULL) { return 0; } else { return 1; }

}  210

A.3 common.h

/* definitions that are used in multiple source files */

#ifndef COMMON H #define COMMON H

#define MAXLINE 1024 #define MAXADDR 512 #define SERVER "localhost"

#define SERV PORT 8999  10

#define GLOG FILE "getnet.log" #define DUMP FILE "dump" #define NLOG FILE "netserv.log" #define TIMEOUT 5 #define U TIMEOUT 0 #define UPDATE TIME 600

struct hostinfo { char addr[MAXADDR];

time t time;  20

int num points; struct hostinfo *nexthost; };

struct list { int num; time t ctime; struct list *next; };

30

#endif /* COMMON H */

A.4 crc.h

#ifndef CRC H #define CRC H

void init crc32 PARAMS(()); long crc32 PARAMS((char *buf, int len));

#endif /* CRC H */

A.5 crc.c

#include "squid.h"

/* As its name implies (Cyclic Redundancy Check) a crc adds redundancywhereas the topic of this group is to remove it. But since thisquestion comes up often, here is some code (by Rob Warnock <rpw3@sgi.com>).The following C code does CRC−32 in BigEndian/BigEndian byte/bit order.That is, the data is sent most significant byte first, and each of the bitswithin a byte is sent most significant bit first, as in FDDI. You will needto twiddle with it to

do Ethernet CRC, i.e., BigEndian/LittleEndian byte/bitorder. [Left as  10

an exercise for the reader.]The CRCs this code generates agree with the vendor−supplied Verilog modelsof several of the popular FDDI ”MAC” chips. */

long crc32 table[256];

long crc32(char *buf, int len) { char *p; long crc;

if (!crc32 table[1]) /* if not already done, */  20

init crc32(); /* build table */

crc = 0xffffffff; /* preload shift register, per CRC−32 spec */

for (p = buf; len > 0; ++p, −−len)

crc = (crc << 8) ˆ crc32 table[(crc >> 24) ˆ *p]; return ˜ crc; /* transmit complement, per CRC−32 spec */}

/* Build auxiliary table for parallel byte−at−a−time CRC−32. */

30

#define CRC32 POLY 0x04c11db7 /* AUTODIN II, Ethernet, & FDDI */

void init crc32() { int i, j; long c; for (i = 0; i < 256; ++i) { for (c = i << 24, j = 8; j > 0; −−j) c = c & 0x80000000 ? (c << 1) ˆ CRC32 POLY : (c << 1); crc32 table[i] = c;

}  40

}

A.6 deal.h

#ifndef DEAL H #define DEAL H

int addhost(char address[1024], time t ntime, int np); int delhost(char address[1024]); int list(int newsockfd); int since(int newsockfd, time t stime); int dump(); int readdump();

10

#endif /* DEAL H */

A.7 deal.c

#include "squid.h"

/* global variable that points to the main host table */ struct hostinfo *tablePtr;

/* add a host to the host table, check for duplicates */ int addhost(char address[MAXADDR], time t ntime, int np){

/* go through the table and check that the address is not already there */

struct hostinfo *machinfo, *currPtr = tablePtr;  10

while (currPtr != NULL) { if ((strcmp(currPtr−>addr,address)) == 0){

   debug(1,0,"Duplicate address %s.\n",address);

return(1); } else { currPtr = currPtr−>nexthost; } }

20

/* malloc space for a new entry in the table */ machinfo = (struct hostinfo *) malloc(sizeof(struct hostinfo)); if (machinfo == NULL){ perror("malloc"); return(−1); } else { /* put the new address and time in the malloc’d space, and point the

* entry’s nexthost pointer to the beginning of the old table */

strcpy(machinfo−>addr,address);  30

machinfo−>time = ntime; machinfo−>num points = np; machinfo−>nexthost = tablePtr; }

/* change the table to point to the new entry */ tablePtr = machinfo; return(0); }

40

/* delete a host from the host table if it is there */ int delhost(char address[MAXADDR]) { int found = 1; struct hostinfo *freePtr, **lastPtr = &tablePtr;

/* go through the table, and if you find a match, point the previous entry’s

* nexthost pointer to the following entry, then free the memory that * contained the current entry */ while (*lastPtr != NULL) {

if ((strcmp((*lastPtr)−>addr,address)) == 0) {  50

freePtr = *lastPtr;

*lastPtr = (*lastPtr)−>nexthost;

free(freePtr);

/* set found to zero and stop looking through the table */ found = 0; break; } lastPtr = &(*lastPtr)−>nexthost;

}  60

/* return zero if the host is found, and one if it is not */ return(found); }

/* print a list that represents the current network state */ int list(int newsockfd) { int reply len; char reply[MAXLINE] = "\0";

struct hostinfo *currPtr = tablePtr;  70

/* print header line */

sprintf(reply, "200 Listing follows:\n");

reply len = strlen(reply); write(newsockfd,reply,reply len);

/* go through the host table and print out a line for every entry */ while (currPtr != NULL) { sprintf(reply, "%s %d %d\n", currPtr−>addr,(int) currPtr−>time, currPtr−>num points);

reply len = strlen(reply);  80

write(newsockfd,reply,reply len); currPtr = currPtr−>nexthost; } return(0); }

/* print out all the changes since time stime */ int since(int newsockfd, time t stime) { int reply len;

FILE *logPtr;  90

char reply[MAXLINE] = "\0"; char x[1], f[MAXADDR], s[MAXLINE]; int *ftimePtr = malloc(sizeof(int)); /* print the header line */ sprintf(reply,"200 Changes since %i:\n",(int) stime); reply len = strlen(reply); write(newsockfd,reply,reply len);

/* open the log file for reading */  100

if ((logPtr = fopen(NLOG FILE,"r")) == NULL) {

 perror("Error opening NLOG_FILE");

exit(−1); }

/* go through the log file and parse it */ while (fgets(s,sizeof(s),logPtr) != NULL) { sscanf(s,"%s %s %d",x,f,ftimePtr);

/* if the time the change was made is since stime, print out that line */  110

if (stime <= *ftimePtr) {

sprintf(reply, "%s",s);

reply len = strlen(reply);

write(newsockfd,reply,reply len); } } fclose(logPtr); return(0); }

120

/* dump the current network state to the dump file */ int dump() { FILE *dumpPtr; int dumpfd;

/* open the dump file to write */ if ((dumpPtr = fopen(DUMP FILE,"w")) == NULL) {

 perror("Couldn't open dump file");

return (1);

}  130

dumpfd = fileno(dumpPtr);

debug(1,0,"Dumping list.\n");

/* do a list out to the dump file */ if ((list(dumpfd)) != 0) {

 debug(1,0,"Error in dumping list.\n");

return(1); }

140

/* close the dump file */ if((fclose(dumpPtr)) != 0) {

 perror("Couldn't close dump file");

return(1); } return(0); }

/* read a dump file and construct a host table from it */

int readdump() {  150

FILE *dumpPtr; char line[MAXLINE]; char addr[MAXADDR]; int *np=malloc(sizeof(int)), *ptime=malloc(sizeof(int));

/* open the dump file to read */ if ((dumpPtr = fopen(DUMP FILE,"r")) == NULL) {

 perror("Couldn't open dump file, continuing without it.");

return(1);

}  160

/* get and throw away the header line */ fgets(line,MAXLINE,dumpPtr);

/* go through the rest of the file and add any hosts found */ while((fgets(line,MAXLINE,dumpPtr)) != NULL) { sscanf(line,"%s %d %d",addr,ptime,np); addhost(addr,(time t)*ptime,*np); }

fclose(dumpPtr);  170

return(0); }

A.8 dhrand.h

#ifndef DHRAND H #define DHRAND H

#define DH RAND MAX 0x7fffffff

int dhRand PARAMS(()); void dhSrand PARAMS((u int seed));

#endif /* DHRAND H */

A.9 dhrand.c

#include "squid.h"

static u long next = 1;

/* generate a psuedo−random number */ int dhRand() {

return ((next = next * 1103515245 + 12345) % ((u int)DH RAND MAX + 1));

}  10

/* seed for generating a psuedo−random number */ void dhSrand(u int seed) {

next = seed; }

A.10 getnet.h

#ifndef GETNET H #define GETNET H

int sopen PARAMS(()); int getnet PARAMS(()); int getupdate PARAMS((time t ltime)); int readupdate PARAMS(()); int addself PARAMS(());

int delself PARAMS(());  10

int myexit PARAMS(());

#endif /* GETNET H */

A.11 getnet.c

#include "squid.h"

/* default number of points to assign a host */ int opt points = 1;

/* set the default servername from the .h file */ char opt server[MAXADDR] = SERVER;

/* get the initial network */

int getnet() {  10

int n, sockfd; char buf[MAXLINE]; FILE *dumpPtr; int dumpfd;

/* open the dump file to write */ if ((dumpPtr = fopen(DUMP FILE,"w")) == NULL) {

 perror("Couldn't open dump file");

return (1);

}  20

dumpfd = fileno(dumpPtr);

/* open a socket to the server */ if ((sockfd = sopen()) == 0) {

 debug(1,0,"Couldn't open socket to server.\n");

return(1); }

debug(1,0,"Getting initial listing.\n");

30

/* send the request */ write(sockfd,"list\n",5);

/* read the response and write it out the dump file */ n = MAXLINE; while(n != 0) { n = read(sockfd,buf,MAXLINE); n = write(dumpfd,buf,n); }

40

/* read the dump file that we have just written */ readdump(); close(sockfd); fclose(dumpPtr); return(0); }

/* get the changes since ltime */ int getupdate(time t ltime) {

int sockfd, logfd, n;  50

FILE *logPtr; char buf[MAXLINE];

/* open the log file for writing */ if ((logPtr = fopen(GLOG FILE,"w")) == NULL) {

 perror("Can't open GLOG_FILE");

return(1); } logfd = fileno(logPtr);

60

/* open a socket to the server */ if ((sockfd = sopen()) == 0) {

 debug(1,0,"Couldn't open socket to server.\n");

return(1); }

debug(1,0,"Getting update.\n");

/* send the request */ sprintf(buf,"since %d\n",(int) ltime);

write(sockfd,buf,MAXLINE);  70

/* read the response and write it out the log file */ n = MAXLINE; while(n != 0) { n = read(sockfd,buf,MAXLINE); n = write(logfd,buf,n); }

/* close the log file */

fclose(logPtr);  80

/* read the log file that we have just written */ readupdate(); close(sockfd); return(0); }

/* parse the log file and do the changes indicated */ int readupdate() {

int changed = 1;  90

int *ptime = malloc(sizeof(int)), *np = malloc(sizeof(int)); char line[MAXLINE], x[1], addr[MAXADDR]; FILE *logPtr;

/* open the log file for reading */ if ((logPtr = fopen(GLOG FILE,"r")) == NULL) {

 perror("Can't open GLOG_FILE");

return(1); }

100

/* get and throw away the header line */ fgets(line,MAXLINE,logPtr);

/* go through the rest of the log file and parse it */ while((fgets(line,MAXLINE,logPtr)) != NULL) { sscanf(line,"%s %s %d %d",x,addr,ptime,np);

/* if there were any changes, set this variable */ changed = 0;

110

/* if the line begins with a plus sign, add the host */ if ((strcmp(x,"+")) == 0) { addhost(addr,(time t)*ptime,*np); debug(1,0,"Adding %s %d %d.\n",addr,*ptime, *np); }

/* if the line begins with a minus sign, delete the host */ else if ((strcmp(x,"-")) == 0) { delhost(addr);

debug(1,0,"Deleting %s.\n",addr);  120

}

/* otherwise, we have a badly formatted line */ else {

 debug(1,0,"Error in parsing results from since.\n");

} }

/* if anything changed, do a dump */

if (changed == 0) {  130

debug(1,0,"Changes made, doing a dump.\n");

dump(); }

/* close the log file */ fclose(logPtr); return(0); }

/* add this host to the network */  140

int addself() { int sockfd, message len; char message[MAXLINE], buf[MAXLINE];

/* open a socket to the server */ if ((sockfd = sopen()) == 0) {

debug(1,0,"Couldn't open socket to server.\n");

return(1); }

debug(1,0,"Joining network.\n");  150

/* message is join and the number of points to grab */ sprintf(message,"join %d\n",opt points); message len = strlen(message);

/* send the request */ write(sockfd,message,message len);

/* read the response */

read(sockfd,buf,MAXLINE);  160

debug(1,0,"%s",buf);

close(sockfd); return(0); }

/* delete this host from the network */ int delself() { int sockfd;

char buf[MAXLINE];  170

/* open a socket to the server */ if ((sockfd = sopen()) == 0) {

 debug(1,0,"Couldn't open socket to server.\n");

return(1); }

debug(1,0,"Leaving network.\n");

/* send the request */

write(sockfd,"dele\n",5);  180

/* read the response */ read(sockfd,buf,MAXLINE); debug(1,0,"%s",buf); close(sockfd); return(0); }

/* open a socket to the server */

int sopen() {  190

int sockfd; struct sockaddr in serv addr; struct hostent *hostPtr; int one = 1;

/* translate the server’s name to an IP address */ if ((hostPtr = gethostbyname(opt server)) == NULL) {

 perror("gethostbyname");

return(0);

}  200

/* open the socket */ if ((sockfd = socket(AF INET,SOCK STREAM,0)) < 0) { perror("socket"); return(0); }

/* clear out and set the struct for the server address */ memset(&serv addr, 0, sizeof(serv addr));

serv addr.sin family = AF INET;  210

memcpy(&serv addr.sin addr, hostPtr−>h addr,sizeof(struct in addr)); serv addr.sin port = htons(SERV PORT);

/* allow the socket to be reused immediately */ setsockopt(sockfd, SOL SOCKET, SO REUSEADDR, (char *)&one, sizeof(one));

/* connect to the server */ if (connect(sockfd,(struct sockaddr *)&serv addr,sizeof(serv addr)) < 0) {

   perror("connect");

return(0);  220

} return(sockfd); }

A.12 netserv.c

#include "squid.h"

/* global variable that points to the main host table */ struct hostinfo *tablePtr = NULL;

/* default number of points to assign a host */ int opt points = 1;

/* Junk so we can link with debug.o */

int opt syslog enable = 0;  10

volatile int unbuffered logs = 1; const char *const appname = "netserv"; struct timeval current time; time t squid curtime; struct SquidConfig Config;

void nsusage PARAMS((char *name)); int deal PARAMS((char caddr new[MAXADDR], int newsockfd, time t ntime, char buf[MAXLINE], FILE *logPtr)); int myexit PARAMS(());

20

/* main loop. start up, wait for connections and deal with them */ int main(int argc, char *argv[]) { int sockfd, newsockfd, cli len, count; struct sockaddr in serv addr, cli addr; int one = 1; FILE *logPtr; struct list *fdlist = NULL; struct timeval timeout;

extern char *optarg;  30

int c;

while ((c = getopt(argc, argv, "hp:?")) != −1) { switch (c) { case 'h': nsusage(argv[0]); break; case 'p': opt points = atoi(optarg);

break;  40

case '?': default: nsusage(argv[0]); break; } } /* debugging message */

debug(1,0,"Starting up...\n");

/* open the log file for appending */  50

if ((logPtr = fopen(NLOG FILE,"a")) == NULL) {

 debug(1,0,"Can't open log file %s.\n",NLOG FILE);

exit(−1); }

/* open a socket */ if( (sockfd = socket(AF INET, SOCK STREAM,0)) < 0) { perror("socket"); exit(−1);

}  60

/* clear out and set the struct for the server address */ memset(&serv addr, 0, sizeof(serv addr)); serv addr.sin family = AF INET; serv addr.sin addr.s addr = htonl(INADDR ANY); serv addr.sin port = htons(SERV PORT); /* allow the socket to be reused immediately */ setsockopt(sockfd, SOL SOCKET, SO REUSEADDR, (char *)&one, sizeof(one));

70

/* bind to the socket */ if (bind(sockfd, (struct sockaddr *) &serv addr, sizeof(serv addr)) < 0) { perror("bind"); exit(−1); }

/* list on the socket */ listen(sockfd,5);

/* read in the saved network status from the dump file */  80

readdump();

/* catch SIGINT and SIGHUP and exit if you get them */ signal(SIGINT,(void *) myexit); signal(SIGHUP,(void *) myexit);

/* select loop */ for(;;){ fd set fdvar;

struct list *listPtr, **lastPtr, *currPtr = fdlist;  90

FD ZERO(&fdvar); FD SET(sockfd,&fdvar);

while (currPtr != NULL) { FD SET(currPtr−>num,&fdvar); currPtr = currPtr−>next; }

/* set the timeout to wait for the client to send something */  100

timeout.tv sec = TIMEOUT; timeout.tv usec = U TIMEOUT;

/* check what file descriptors need managing */ count = select(NOFILE,(fd set *)&fdvar,(fd set *)0,(fd set *)0,&timeout); if (count < 0) { perror("select"); exit(−1); }

if (count == 0){  110

time t currtime = time((time t *)0); lastPtr = &fdlist; while (*lastPtr != NULL) {

if ((currtime − TIMEOUT) > (*lastPtr)−>ctime) { debug(1,0,"Timeout on sockfd %d.\n",(*lastPtr)−>num); close((*lastPtr)−>num); currPtr= *lastPtr; *lastPtr = (*lastPtr)−>next; free(currPtr);

}  120

else {

lastPtr = &(*lastPtr)−>next; } } } else { char caddr new[MAXADDR]; struct hostent *hp; if (FD ISSET(sockfd,&fdvar)) {

cli len = sizeof(cli addr);  130

if ((newsockfd = accept(sockfd, (struct sockaddr *) &cli addr,

&cli len)) < 0) {

perror("accept"); exit(−1); } /* convert the IP address of the host that connected to its cname. */ hp = gethostbyaddr((const char *) &cli addr.sin addr, sizeof(cli addr.sin addr), AF INET); strcpy(caddr new,hp−>h name);

debug(1,0,"%s connected.\n",caddr new);  140

listPtr = (struct list *) malloc(sizeof(struct list)); listPtr−>num = newsockfd; listPtr−>ctime = time((time t *)0); listPtr−>next = fdlist; fdlist = listPtr;

}

lastPtr = &fdlist;

while (*lastPtr != NULL) {  150

if (FD ISSET((*lastPtr)−>num,&fdvar)) { char buf[MAXLINE] = "\0"; read((*lastPtr)−>num, buf, MAXLINE); deal(caddr new, (*lastPtr)−>num, (*lastPtr)−>ctime,buf,logPtr); close((*lastPtr)−>num); currPtr= *lastPtr; *lastPtr = (*lastPtr)−>next; free(currPtr); }

else {  160

lastPtr = &(*lastPtr)−>next;

}

} } } close(sockfd); fclose(logPtr); }

/* print a usage message */  170

void nsusage(char *name) {

fprintf(stderr, "Usage:  %s [-h] [-p points]\n"
    "       -p points Set the default number of points.\n"
    "       -h        Get this help message.\n",name);

myexit(); }

/* check what we received and call the appropriate function */ int deal(char caddr new[MAXADDR], int newsockfd, time t ntime, char buf[MAXLINE], FILE *logPtr) {

int reply len, retval;  180

char reply[MAXLINE] = "\0"; ntime = time((time t *)0);

/* check for a join request */ if ((strncmp(buf,"join",4)) == 0) {

/* get the number of points if given */ int num; char s[5];

if (sscanf(buf, "%s %d", s, &num) != 2) {  190

num = opt points; } /* try to add the host to the network */ retval = addhost(caddr new,ntime,num);

/* if the host was added... */ if ( retval == 0) {

/* Write this to the log file and flush it */

fprintf(logPtr,"+ %s %d %d\n",caddr new,(int) ntime, num);  200

fflush(logPtr);

/* reply to the client */

 sprintf(reply, "200 You have been added to the network.\n");

reply len = strlen(reply); write(newsockfd,reply,reply len); debug(1,0,"%s joined at %d with %d points.\n",caddr new,(int) ntime,num); }

/* if the host is already in the network, tell the client that */  210

else if (retval == 1){

sprintf(reply, "401 Duplicate address, not added.\n");

reply len = strlen(reply); write(newsockfd,reply,reply len); debug(1,0,"Duplicate request from %s at %d.\n",caddr new,(int) ntime); } /* for other errors */ else {

debug(1,0,"Couldn't add new host %s to network at %d.\n", caddr new,(int) ntime);

}  220

}

/* check for dele requests */ else if ((strncmp(buf,"dele",4)) == 0) {

/* try to delete the host from the network */ retval = delhost(caddr new);

/* if it was successfully deleted... */

if ( retval == 0 ){  230

/* write this to the log file and flush it */ fprintf(logPtr,"- %s %d\n",caddr new,(int) ntime); fflush(logPtr);

/* reply to the client */

sprintf(reply, "200 You have been deleted from the network.\n");

reply len = strlen(reply); write(newsockfd,reply,reply len);

debug(1,0,"%s deleted at %d.\n",caddr new,(int) ntime);  240

}

/* if the address was not in the network, tell the client that */ else if (retval == 1){

sprintf(reply, "401 No such address, not deleted.\n");

reply len = strlen(reply); write(newsockfd,reply,reply len);

debug(1,0,"No such address to delete as %s at %d.\n",caddr new,(int) ntime);

}

250

/* for other errors */ else {

debug(1,0,"Couldn't delete host %s from network at %d.\n",caddr new,(int) ntime);

} } /* check for list requests */ else if ((strncmp(buf,"list",4)) == 0){

/* print the list out to this connection */  260

if ((list(newsockfd)) == 0){ debug(1,0,"%s requested a listing at %d.\n",caddr new,(int) ntime); } }

/* check for help requests */ else if ((strncmp(buf,"help",4)) == 0){

/* reply to the client */

sprintf(reply,"100 Possible commands are:\n\t join [<points>]\n\t dele\n\t list\n\t since <time>\n\t help\n");

270

reply len = strlen(reply); write(newsockfd,reply,reply len); debug(1,0,"Help request from %s at %d.\n",caddr new,(int) ntime); }

/* check for since requests */ else if ((strncmp(buf,"since",5)) == 0) { /* get the time argument */ int *stimePtr = malloc(sizeof(int));

char s[6];  280

if (sscanf(buf,"%s %d",s,stimePtr) == 2) {

/* print the since information out to this connection */ if ((since(newsockfd,*stimePtr)) == 0) {

debug(1,0,"Since %d request from %s at %d.\n",*stimePtr,caddr new,(int) ntime); } }

/* for other errors */

else {  290

 sprintf(reply, "400 Invalid since request.\n");

reply len = strlen(reply); write(newsockfd,reply,reply len);

 debug(1,0,"Invalid since request from %s at %d.\n",caddr new,(int) ntime);

} }

/* otherwise, we have an unknown request */ else {

/* reply to the client */  300

sprintf(reply, "400 Unknown request.\n");

reply len = strlen(reply); write(newsockfd,reply,reply len); debug(1,0,"Unknown request from %s at %d.\n",caddr new,(int) ntime); } return(0); }

/* dump and exit on a signal */  310

int myexit() {

 debug(1,0,"exiting.\n");

if ((dump()) != 0) {

  debug(1,0,"Error in dumping network status, data may be lost.\n");

} exit(0); }

B Modified Squid Code

B.1 squid.h

/*

* $Id: squid.h,v 1.4 1997/01/08 04:56:58 marthag Exp $ *

* AUTHOR: Duane Wessels *

* SQUID Internet Object Cache http://squid.nlanr.net/Squid/

* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− *

* Squid is the result of efforts by numerous individuals from the  10

* Internet community. Development is led by Duane Wessels of the

* National Laboratory for Applied Network Research and funded by

* the National Science Foundation. *

* This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation; either version 2 of the License, or

* (at your option) any later version. *

* This program is distributed in the hope that it will be useful,  20

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

* GNU General Public License for more details. *

* You should have received a copy of the GNU General Public License

* along with this program; if not, write to the Free Software * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * */

30

#ifndef SQUID H #define SQUID H

#include "config.h"

/*

* On some systems, FD SETSIZE is set to something lower than the

* actual number of files which can be opened. IRIX is one case,

* NetBSD is another. So here we increase FD SETSIZE to our

* configure−discovered maximum *before* any system includes.  40

*/

/*

* Linux (2.x only?) always defines FD SETSIZE in <linux/time.h> so

* we get in trouble if we try to increase it. barf. */

#ifndef SQUID LINUX #if SQUID MAXFD > FD SETSIZE

#define FD SETSIZE SQUID MAXFD  50

#endif #endif /* SQUID LINUX */

#if HAVE UNISTD H #include <unistd.h> #endif #if HAVE STDLIB H #include <stdlib.h> #endif

#if HAVE STDIO H  60

#include <stdio.h> #endif #if HAVE SYS TYPES H #include <sys/types.h> #endif #if HAVE CTYPE H #include <ctype.h> #endif #if HAVE ERRNO H

#include <errno.h>  70

#endif #if HAVE FCNTL H #include <fcntl.h> #endif #if HAVE GRP H #include <grp.h> #endif #if HAVE MALLOC H && !defined( SQUID FREEBSD ) && !defined( SQUID NEXT ) #include <malloc.h>

#endif  80

#if HAVE MEMORY H #include <memory.h> #endif #if HAVE NETDB H && !defined( SQUID NETDB H ) /* protect NEXTSTEP */ #define SQUID NETDB H #ifdef SQUID NEXT #include <netinet/in systm.h> #endif #include <netdb.h>

#endif  90

#if HAVE PWD H #include <pwd.h> #endif #if HAVE SIGNAL H #include <signal.h> #endif #if HAVE TIME H #include <time.h> #endif

#if HAVE SYS PARAM H  100

#include <sys/param.h> #endif #if HAVE SYS TIME H #include <sys/time.h> #endif #if HAVE SYS RESOURCE H #include <sys/resource.h> /* needs sys/time.h above it */ #endif #if HAVE SYS SOCKET H

#include <sys/socket.h>  110

#endif #if HAVE NETINET IN H #include <netinet/in.h> #endif #if HAVE ARPA INET H #include <arpa/inet.h> #endif #if HAVE SYS STAT H #include <sys/stat.h>

#endif  120

#if HAVE SYS UN H #include <sys/un.h> #endif #if HAVE SYS WAIT H #include <sys/wait.h> #endif #if HAVE LIBC H #include <libc.h> #endif

#ifdef HAVE SYS SYSCALL H  130

#include <sys/syscall.h> #endif #ifdef HAVE STRING H #include <string.h> #endif #ifdef HAVE STRINGS H #include <strings.h> #endif #if HAVE BSTRING H

#include <bstring.h>  140

#endif #ifdef HAVE CRYPT H #include <crypt.h> #endif #if HAVE SYS SELECT H #include <sys/select.h> #endif #if HAVE GETOPT H #include <getopt.h>

#endif  150

#if defined(USE POLL) && HAVE POLL #if HAVE POLL H #include <poll.h> #endif /* HAVE POLL H */ #else #undef USE POLL #endif

#ifdef STDC  160

#include <stdarg.h> #else #include <varargs.h> #endif

/* Make sure syslog goes after stdarg/varargs */ #ifdef HAVE SYSLOG H #include <syslog.h> #endif

170

#if HAVE SHADOW H #include <shadow.h> #endif

#if !defined(MAXHOSTNAMELEN) || (MAXHOSTNAMELEN < 128) #define SQUIDHOSTNAMELEN 128 #else #define SQUIDHOSTNAMELEN MAXHOSTNAMELEN #endif

180

#define SQUID MAXPATHLEN 256 #ifndef MAXPATHLEN #define MAXPATHLEN SQUID MAXPATHLEN #endif

#if !defined(HAVE GETRUSAGE) && defined( SQUID HPUX ) #define HAVE GETRUSAGE 1 #define getrusage(a, b) syscall(SYS GETRUSAGE, a, b) #endif

190

#if !defined(HAVE GETPAGESIZE) && defined( SQUID HPUX ) #define HAVE GETPAGESIZE #define getpagesize( ) sysconf( SC PAGE SIZE) #endif

#ifndef BUFSIZ #define BUFSIZ 4096 /* make reasonable guess */ #endif

#ifndef SA RESTART  200

#define SA RESTART 0 #endif #ifndef SA NODEFER #define SA NODEFER 0 #endif #ifndef SA RESETHAND #define SA RESETHAND 0 #endif #if SA RESETHAND == 0 && defined(SA ONESHOT)

#undef SA RESETHAND  210

#define SA RESETHAND SA ONESHOT #endif

typedef struct sentry StoreEntry; typedef struct mem hdr *mem ptr; typedef struct edge edge; typedef struct icp common s icp common t; typedef struct cacheinfo cacheinfo; typedef struct aclCheck t aclCheck t;

typedef struct request request t;  220

typedef struct MemObject MemObject; typedef struct cachemgr passwd cachemgr passwd;

/* 32 bit integer compatability hack */ #if SIZEOF INT == 4 typedef int num32; typedef unsigned int u num32; #elif SIZEOF LONG == 4 typedef long num32;

typedef unsigned long u num32;  230

#else typedef long num32; /* assume that long’s are 32bit */ typedef unsigned long u num32; #endif #define NUM32LEN sizeof(num32) /* this should always be 4 */

#if PURIFY #define LOCAL ARRAY(type,name,size) \

static type *local ##name=NULL; \

type *name = local ##name ? local ##name : \  240

( local ##name = (type *)xcalloc(size, sizeof(type)) )

#else #define LOCAL ARRAY(type,name,size) static type name[size] #endif

#include "ansiproto.h"

#if HAVE REGEX H #include <regex.h>

#else /* HAVE REGEX H */  250

#include "GNUregex.h"

#endif /* HAVE REGEX H */

/*

* So if FD SETSIZE is less than SQUID MAXFD we’d probably better

* shrink SQUID MAXFD so that select(2) doesn’t puke even though

* we might really be able to open more than FD SETSIZE descriptors.

* happy happy happy joy joy joy. */

#if FD SETSIZE < SQUID MAXFD  260

#undef SQUID MAXFD #define SQUID MAXFD FD SETSIZE #endif

typedef void (*SIH) (int, void *); /* swap in */ typedef int (*QS) (const void *, const void *);

#include "cache_cf.h"
#include "comm.h"

#include "debug.h"  270

#include "disk.h"
#include "fdstat.h"
#include "filemap.h"
#include "hash.h"

#include "proto.h" /* must go before neighbors.h */ #include "neighbors.h" /* must go before url.h */ /* DH Additions to original SQUID cache release */

#include "chash.h"

#include "crc.h"

#include "common.h"  280

#include "deal.h"
#include "dhrand.h"
#include "getnet.h"

/* end DH changes */ #include "url.h" #include "icp.h" #include "errorpage.h" /* must go after icp.h */ #include "dns.h"

#include "ipcache.h"

#include "fqdncache.h"  290

#include "mime.h"
#include "stack.h"
#include "stat.h"
#include "stmem.h"
#include "store.h"
#include "tools.h"
#include "http.h"

#include "ftp.h"

#include "gopher.h"

#include "util.h"  300

#include "event.h"

#include "acl.h"

#include "async_io.h"
#include "redirect.h"
#include "client_side.h"
#include "useragent.h"
#include "icmp.h"
#include "net_db.h"

#include "client_db.h"

#include "objcache.h"  310

#include "refresh.h"

#if !HAVE TEMPNAM

#include "tempnam.h"

#endif

extern void serverConnectionsClose PARAMS((void)); extern void shut down PARAMS((int));

320

extern time t squid starttime; /* main.c */ extern int do reuse; /* main.c */ extern int theHttpConnection; /* main.c */ extern int theInIcpConnection; /* main.c */ extern int theOutIcpConnection; /* main.c */ extern int vizSock; extern volatile int shutdown pending; /* main.c */ extern volatile int reread pending; /* main.c */ extern int opt unlink on reload; /* main.c */

extern int opt reload hit only; /* main.c */ 330

extern int opt dns tests; /* main.c */ extern int opt foreground rebuild; /* main.c */ extern int opt zap disk store; /* main.c */ extern int opt syslog enable; /* main.c */ extern int opt catch signals; /* main.c */ extern int opt no ipcache; /* main.c */ /* begin DH changes */ extern int opt dynamic hierarchy; /* main.c − DH option */ /* end DH changes */

extern int vhost mode; /* main.c */ 340

extern const char *const version string; /* main.c */ extern const char *const appname; /* main.c */ extern struct in addr local addr; /* main.c */ extern struct in addr theOutICPAddr; /* main.c */ extern const char *const localhost; extern unsigned int inaddr none; extern struct in addr any addr; /* comm.c */ extern struct in addr no addr; /* comm.c */ extern int opt udp hit obj; /* main.c */

extern int opt mem pools; /* main.c */ 350

extern int opt forwarded for; /* main.c */ extern int opt accel uses host; /* main.c */ extern char ThisCache[]; /* main.c */

/* Prototypes and definitions which don’t really deserve a seaprate * include file */

#define CONNECT PORT 443

extern int objcacheStart PARAMS((int, const char *, StoreEntry *));  360

extern void send announce PARAMS((void *unused)); extern int sslStart PARAMS((int fd, const char *, request t *, char *, int *sz)); extern const char *storeToString PARAMS((const StoreEntry *)); extern int waisStart PARAMS((int, const char *, method t, char *, StoreEntry *)); extern void storeDirClean PARAMS((void *unused)); extern int passStart PARAMS((int fd,

const char *url, request t * request, char *buf,

int buflen,  370

int *size ptr));

extern void identStart PARAMS((int, icpStateData *, void (*callback) PARAMS((void *))));

extern const char *const dash str; extern const char *const null string;

#define OR(A,B) (A ? A : B)

#endif /* SQUID H */  380

B.2 main.c

/*

* $Id: main.c,v 1.3 1997/01/08 04:56:46 marthag Exp $ *

* DEBUG: section 1 Startup and Main Loop

* AUTHOR: Harvest Derived *

* SQUID Internet Object Cache http://squid.nlanr.net/Squid/

* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−− *

* Squid is the result of efforts by numerous individuals from the  10

* Internet community. Development is led by Duane Wessels of the

* National Laboratory for Applied Network Research and funded by

* the National Science Foundation. *

* This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation; either version 2 of the License, or

* (at your option) any later version. *

* This program is distributed in the hope that it will be useful,  20

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. *

* You should have received a copy of the GNU General Public License

* along with this program; if not, write to the Free Software

* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. * */

30

/*

* Copyright (c) 1994, 1995. All rights reserved. *

* The Harvest software was developed by the Internet Research Task

* Force Research Group on Resource Discovery (IRTF−RD): *

* Mic Bowman of Transarc Corporation.

* Peter Danzig of the University of Southern California.

* Darren R. Hardy of the University of Colorado at Boulder.

* Udi Manber of the University of Arizona. 40

* Michael F. Schwartz of the University of Colorado at Boulder.

* Duane Wessels of the University of Colorado at Boulder. *

* This copyright notice applies to software in the Harvest

* “src/” directory only. Users should consult the individual

* copyright notices in the “components/” subdirectories for

* copyright information about other software bundled with the

* Harvest source code distribution. *

* TERMS OF USE  50

*

* The Harvest software may be used and re−distributed without

* charge, provided that the software origin and research team are

* cited in any use of the system. Most commonly this is

* accomplished by including a link to the Harvest Home Page

* (http://harvest.cs.colorado.edu/) from the query page of any

* Broker you deploy, as well as in the query result pages. These

* links are generated automatically by the standard Broker

* software distribution.

*  60

* The Harvest software is provided “as is”, without express or

* implied warranty, and with no support nor obligation to assist

* in its use, correction, modification or enhancement. We assume

* no liability with respect to the infringement of copyrights,

* trade secrets, or any patents, and are not responsible for

* consequential damages. Proper use of the Harvest software is * entirely the responsibility of the user. *

* DERIVATIVE WORKS

*  70

* Users may make derivative works from the Harvest software, subject

* to the following constraints: *

* − You must include the above copyright notice and these

* accompanying paragraphs in all forms of derivative works,

* and any documentation and other materials related to such

* distribution and use acknowledge that the software was

* developed at the above institutions. *

* − You must notify IRTF−RD regarding your distribution of  80

* the derivative work. *

* − You must clearly notify users that your are distributing

* a modified version and not the original Harvest software. *

* − Any derivative product is also subject to these copyright

* and use restrictions. *

* Note that the Harvest software is NOT in the public domain. We

* retain copyright, as specified above.  90

*

* HISTORY OF FREE SOFTWARE STATUS *

* Originally we required sites to license the software in cases

* where they were going to build commercial products/services

* around Harvest. In June 1995 we changed this policy. We now

* allow people to use the core Harvest software (the code found in

* the Harvest “src/” directory) for free. We made this change

* in the interest of encouraging the widest possible deployment of

* the technology. The Harvest software is really a reference  100

* implementation of a set of protocols and formats, some of which

* we intend to standardize. We encourage commercial

* re−implementations of code complying to this set of standards. */

#include "squid.h"

time t squid starttime = 0; int theHttpConnection = −1;

int theInIcpConnection = −1;  110

int theOutIcpConnection = −1; int vizSock = −1; int do reuse = 1; int opt unlink on reload = 0; int opt reload hit only = 0; /* only UDP HIT during store relaod */ int opt catch signals = 1; int opt dns tests = 1; int opt foreground rebuild = 0; int opt zap disk store = 0;

int opt syslog enable = 0; /* disabled by default */ 120

int opt no ipcache = 0; /* use ipcache by default */ static int opt send signal = −1; /* no signal to send */ int opt udp hit obj = 0; /* ask for HIT OBJ’s */ int opt mem pools = 1; int opt forwarded for = 1; int opt accel uses host = 0; /* begin DH changes */ int opt dynamic hierarchy = 0; /* by default, don’t use dynamic hierarchy */ int num hosts = 0;

struct hostinfo *tablePtr = NULL;  130

/* global variable that points to the list of machines in the unit interval */ struct machplace *uiPtr = NULL; const char *myhostname; /* end DH changes */ int vhost mode = 0; volatile int unbuffered logs = 1; /* debug and hierarchy unbuffered by default */ volatile int shutdown pending = 0; /* set by SIGTERM handler (shut down()) */ volatile int reread pending = 0; /* set by SIGHUP handler */ const char *const version string = SQUID VERSION;

const char *const appname = "squid";  140

const char *const localhost = "127.0.0.1"; struct in addr local addr; struct in addr no addr; struct in addr any addr; struct in addr theOutICPAddr; const char *const dash str = "-"; const char *const null string = ""; char ThisCache[SQUIDHOSTNAMELEN << 1]; unsigned int inaddr none;

150

/* for error reporting from xmalloc and friends */ extern void (*failure notify) PARAMS((const char *));

static volatile int rotate pending = 0; /* set by SIGUSR1 handler */ static int httpPortNumOverride = 1; static int icpPortNumOverride = 1; /* Want to detect ”−u 0” */ #if MALLOC DBG static int malloc debug level = 0; #endif

160

static void rotate logs PARAMS((int)); static void reconfigure PARAMS((int)); static void mainInitialize PARAMS((void)); static void mainReinitialize PARAMS((void)); static void usage PARAMS((void)); static void mainParseOptions PARAMS((int, char **)); static void sendSignal PARAMS((void)); static void serverConnectionsOpen PARAMS((void));

static void  170

usage(void) {

fprintf(stderr, /* begin DH changes */

   "Usage:  %s [-dhsvzCDFRUVY] [-f config-file] [-[au] port] [-k signal]\n"
"       -a port   Specify ASCII port number (default:  %d).\n"
"       -d        Use dynamic hierarchy.\n"

/* end DH changes */

"       -f file   Use given config-file instead of\n"

"                 %s\n"  180

"       -h        Print help message.\n"
"       -i        Disable IP caching.\n"
"       -k reconfigure|rotate|shutdown|interrupt|kill|debug|check\n"
"                 Send signal to running copy and exit.\n"
"       -s        Enable logging to syslog.\n"
"       -u port   Specify ICP port number (default:  %d), disable with 0.\n"
"       -v        Print version.\n"
"       -z        Zap disk storage -- deletes all objects in disk cache.\n"
"       -C        Do not catch fatal signals.\n"

"       -D        Disable initial DNS tests.\n"  190

"       -F        Foreground fast store rebuild.\n"
"       -R        Do not set REUSEADDR on port.\n"
"       -U        Unlink expired objects on reload.\n"
"       -V        Virtual host httpd-accelerator.\n"
"       -Y        Only return UDP_HIT or UDP_RELOADING during fast reload.\n",

appname, CACHE HTTP PORT, DefaultConfigFile, CACHE ICP PORT); exit(1);

}

static void  200

mainParseOptions(int argc, char *argv[]) {

extern char *optarg; int c;

/* begin DH changes */ while ((c = getopt(argc, argv, "CDFRUVYa:bdf:hik:m:su:vz?")) != −1) { /* end DH changes */

switch (c) {

case 'C':  210

opt catch signals = 0; break;

case 'D':

opt dns tests = 0; break;

case 'F':

opt foreground rebuild = 1; break;

case 'R':

do reuse = 0;  220

break; case 'U':

opt unlink on reload = 1; break;

case 'V':

vhost mode = 1; break;

case 'Y':

opt reload hit only = 1;

break;  230

case 'a':

httpPortNumOverride = atoi(optarg); break;

case 'b':

unbuffered logs = 0; break; /* begin DH changes */

case 'd':

opt dynamic hierarchy = 0;

break;  240

/* end DH changes */ case 'f':

xfree(ConfigFile); ConfigFile = xstrdup(optarg); break;

case 'h':

usage(); break;

case 'i':

opt no ipcache = 1;  250

break; case 'k':

if ((int) strlen(optarg) < 1)

usage(); if (!strncmp(optarg, "reconfigure", strlen(optarg)))

opt send signal = SIGHUP; else if (!strncmp(optarg, "rotate", strlen(optarg)))

opt send signal = SIGUSR1; else if (!strncmp(optarg, "debug", strlen(optarg)))

opt send signal = SIGUSR2;  260

else if (!strncmp(optarg, "shutdown", strlen(optarg)))

opt send signal = SIGTERM; else if (!strncmp(optarg, "interrupt", strlen(optarg)))

opt send signal = SIGINT; else if (!strncmp(optarg, "kill", strlen(optarg)))

opt send signal = SIGKILL; else if (!strncmp(optarg, "check", strlen(optarg)))

opt send signal = 0; /* SIGNULL */ else

usage();  270

break; case 'm':

#if MALLOC DBG malloc debug level = atoi(optarg); /* NOTREACHED */ break;

#else

fatal("Need to add -DMALLOC_DBG when compiling to use -m option");

/* NOTREACHED */

#endif  280

case 's':

opt syslog enable = 1; break;

case 'u':

icpPortNumOverride = atoi(optarg); if (icpPortNumOverride < 0)

icpPortNumOverride = 0; break;

case 'v':

printf("Squid Cache:  Version %s\n", version string);  290

exit(0); /* NOTREACHED */

case 'z':

opt zap disk store = 1; break;

case '?': default:

usage(); break;

}  300

} }

static void rotate logs(int sig) {

   debug(1, 1, "rotate_logs:  SIGUSR1 received.\n");

rotate pending = 1; #if !HAVE SIGACTION

signal(sig, rotate logs);  310

#endif }

static void reconfigure(int sig) {

   debug(1, 1, "reconfigure:  SIGHUP received\n");
   debug(1, 1, "Waiting %d seconds for active connections to finish\n",

Config.lifetimeShutdown);

reread pending = 1;  320

#if !HAVE SIGACTION

signal(sig, reconfigure); #endif }

void shut down(int sig) {

shutdown pending = sig == SIGINT ? −1 : 1;

   debug(1, 1, "Preparing for shutdown after %d connections\n",  330

ntcpconn + nudpconn); if (opt dynamic hierarchy) { /* remove self from the network */ delself(); if ((dump()) != 0) {

        debug(1,1,"Error in dumping network status, data may be lost.\n");

}

}

   debug(1, 1, "Waiting %d seconds for active connections to finish\n",

shutdown pending > 0 ? Config.lifetimeShutdown : 0);  340

#ifdef KILL PARENT OPT

   debug(1, 1, "Killing RunCache, pid %d\n", getppid());

kill(getppid(), sig); #endif #if SA RESETHAND == 0

signal(SIGTERM, SIG DFL);

signal(SIGINT, SIG DFL); #endif }

350

static void serverConnectionsOpen(void) {

struct in addr addr; struct sockaddr in xaddr; u short port; int len; int x; enter suid();

theHttpConnection = comm open(SOCK STREAM,  360

0,

Config.Addrs.tcp incoming,

Config.Port.http,

COMM NONBLOCKING,

     "HTTP Port");

leave suid(); if (theHttpConnection < 0) {

     fatal("Cannot open HTTP Port");

}

fd note(theHttpConnection, "HTTP socket");  370

comm listen(theHttpConnection); commSetSelect(theHttpConnection,

COMM SELECT READ,

asciiHandleConn,

NULL, 0);

debug(1, 1, "Accepting HTTP connections on FD %d.\n",

theHttpConnection);

if (!httpd accel mode || Config.Accel.withProxy) {

if ((port = Config.Port.icp) > (u short) 0) {  380

enter suid();

theInIcpConnection = comm open(SOCK DGRAM, 0, Config.Addrs.udp incoming, port, COMM NONBLOCKING,

             "ICP Port");

leave suid();

if (theInIcpConnection < 0)

             fatal("Cannot open ICP Port");  390

fd note(theInIcpConnection, "ICP socket"); commSetSelect(theInIcpConnection, COMM SELECT READ, icpHandleUdp, NULL, 0); comm join mcast groups(theInIcpConnection);

debug(1, 1, "Accepting ICP connections on FD %d.\n",

theInIcpConnection);

if ((addr = Config.Addrs.udp outgoing).s addr != inaddr none) {  400

enter suid();

theOutIcpConnection = comm open(SOCK DGRAM, 0, addr, port, COMM NONBLOCKING,

        "ICP Port");

leave suid();

if (theOutIcpConnection < 0)

        fatal("Cannot open Outgoing ICP Port");  410

commSetSelect(theOutIcpConnection, COMM SELECT READ, icpHandleUdp, NULL, 0);

     debug(1, 1, "Accepting ICP connections on FD %d.\n",

theOutIcpConnection); fd note(theOutIcpConnection, "Outgoing ICP socket"); fd note(theInIcpConnection, "Incoming ICP socket");

} else {

theOutIcpConnection = theInIcpConnection;  420

} memset(&theOutICPAddr, '\0', sizeof(struct in addr)); len = sizeof(struct sockaddr in); memset(&xaddr, '\0', len); x = getsockname(theOutIcpConnection,

(struct sockaddr *) &xaddr, &len); if (x < 0)

     debug(50, 1, "theOutIcpConnection FD %d:  getsockname:  %s\n",

theOutIcpConnection, xstrerror());

else  430

theOutICPAddr = xaddr.sin addr;

} } if (Config.vizHack.port) {

vizSock = comm open(SOCK DGRAM, 0, any addr, 0, COMM NONBLOCKING,

"VizHack Port");  440

if (vizSock < 0)

fatal("Could not open Viz Socket");

#if defined(IP ADD MEMBERSHIP) && defined(IP MULTICAST TTL)

if (Config.vizHack.addr.s addr > inet addr("224.0.0.0")) { struct ip mreq mr; char ttl = (char) Config.vizHack.mcast ttl; memset((char *) &mr, '\0', sizeof(struct ip mreq)); mr.imr multiaddr.s addr = Config.vizHack.addr.s addr; mr.imr interface.s addr = INADDR ANY;

x = setsockopt(vizSock,  450

IPPROTO IP,

IP ADD MEMBERSHIP,

(char *) &mr,

sizeof(struct ip mreq)); if (x < 0)

     debug(50, 1, "IP_ADD_MEMBERSHIP: FD %d, addr %s:  %s\n",

vizSock, inet ntoa(Config.vizHack.addr), xstrerror());

x = setsockopt(vizSock, IPPROTO IP,

IP MULTICAST TTL,  460

&ttl,

sizeof(char)); if (x < 0)

     debug(50, 1, "IP_MULTICAST_TTL: FD %d, TTL %d:  %s\n",

vizSock, Config.vizHack.mcast ttl, xstrerror());

ttl = 0; x = sizeof(char); getsockopt(vizSock, IPPROTO IP, IP MULTICAST TTL, &ttl, &x); debug(1, 0, "vizSock on FD %d, ttl=%d\n", vizSock, (int) ttl);

}  470

#else

debug(1, 0, "vizSock:  Could not join multicast group\n");

#endif memset((char *) &Config.vizHack.S, '\0', sizeof(struct sockaddr in)); Config.vizHack.S.sin family = AF INET; Config.vizHack.S.sin addr = Config.vizHack.addr; Config.vizHack.S.sin port = htons(Config.vizHack.port);

} clientdbInit();

icmpOpen();  480

netdbInit(); }

void serverConnectionsClose(void) {

/* NOTE, this function will be called repeatedly while shutdown

* is pending */ if (theHttpConnection >= 0) {

     debug(1, 1, "FD %d Closing HTTP connection\n",  490

theHttpConnection); comm close(theHttpConnection); commSetSelect(theHttpConnection, COMM SELECT READ, NULL, NULL, 0);

theHttpConnection = −1; } if (theInIcpConnection >= 0) {

/* NOTE, don’t close outgoing ICP connection, we need to write to  500

* it during shutdown */

     debug(1, 1, "FD %d Closing ICP connection\n",

theInIcpConnection); if (theInIcpConnection != theOutIcpConnection)

comm close(theInIcpConnection); commSetSelect(theInIcpConnection, COMM SELECT READ, NULL, NULL, 0);

if (theInIcpConnection != theOutIcpConnection)  510

commSetSelect(theOutIcpConnection, COMM SELECT READ, NULL, NULL, 0); theInIcpConnection = −1;

} if (icmp sock > −1)

icmpClose();

}

520

static void mainReinitialize(void) {

debug(1, 0, "Restarting Squid Cache (version %s)...\n", version string);

/* Already called serverConnectionsClose and ipcacheShutdownServers() */ neighborsDestroy(); parseConfigFile(ConfigFile); db init(Config.Log.log, Config.debugOptions); dnsOpenServers();

redirectOpenServers();  530

serverConnectionsOpen(); (void) ftpInitialize(); if (theOutIcpConnection >= 0 && (!httpd accel mode || Config.Accel.withProxy))

neighbors open(theOutIcpConnection);

debug(1, 0, "Ready to serve requests.\n");

} static void mainInitialize(void)

{  540

static int first time = 1; if (opt catch signals) {

squid signal(SIGSEGV, death, SA NODEFER | SA RESETHAND); squid signal(SIGBUS, death, SA NODEFER | SA RESETHAND);

} squid signal(SIGPIPE, SIG IGN, SA RESTART); squid signal(SIGCHLD, sig child, SA NODEFER | SA RESTART);

if (ConfigFile == NULL)

ConfigFile = xstrdup(DefaultConfigFile);  550

parseConfigFile(ConfigFile);

leave suid(); /* Run as non privilegied user */

if (httpPortNumOverride != 1)

Config.Port.http = (u short) httpPortNumOverride; if (icpPortNumOverride != 1)

Config.Port.icp = (u short) icpPortNumOverride;

db init(Config.Log.log, Config.debugOptions);  560

fdstat open(fileno(debug log), FD LOG); fd note(fileno(debug log), Config.Log.log);

debug(1, 0, "Starting Squid Cache version %s for %s...\n",

version string,

CONFIG HOST TYPE);

debug(1, 1, "With %d file descriptors available\n", SQUID MAXFD);

if (first time) {

stmemInit(); /* stmem must go before at least redirect */ 570

disk init(); /* disk init must go before ipcache init() */ } ipcache init(); fqdncache init(); dnsOpenServers(); redirectOpenServers(); useragentOpenLog(); (void) ftpInitialize();

#if MALLOC DBG  580

malloc debug(0, malloc debug level); #endif if (first time) {

/* module initialization */ urlInitialize(); stat init(&HTTPCacheInfo, Config.Log.access); stat init(&ICPCacheInfo, NULL); storeInit();

590

if (Config.effectiveUser) { /* we were probably started as root, so cd to a swap

* directory in case we dump core */ if (chdir(swappath(0)) < 0) {

debug(50, 0, "%s: %s\n", swappath(0), xstrerror());

        fatal dump("Cannot cd to swap directory?");

} } /* after this point we want to see the mallinfo() output */

do mallinfo = 1;  600

} serverConnectionsOpen(); if (theOutIcpConnection >= 0 && (!httpd accel mode || Config.Accel.withProxy))

neighbors open(theOutIcpConnection);

if (first time)

writePidFile(); /* write PID file */

squid signal(SIGUSR1, rotate logs, SA RESTART);

squid signal(SIGUSR2, sigusr2 handle, SA RESTART);  610

squid signal(SIGHUP, reconfigure, SA RESTART); squid signal(SIGTERM, shut down, SA NODEFER | SA RESETHAND | SA RESTART); squid signal(SIGINT, shut down, SA NODEFER | SA RESETHAND | SA RESTART);

debug(1, 0, "Ready to serve requests.\n");

if (first time) { eventAdd("storePurgeOld", storePurgeOld, NULL, Config.cleanRate); eventAdd("storeMaintain", storeMaintainSwapSpace, NULL, 1); eventAdd("storeDirClean", storeDirClean, NULL, 15);

if (Config.Announce.on)  620

eventAdd("send_announce", send announce, NULL, 3600); eventAdd("ipcache_purgelru", (EVH) ipcache purgelru, NULL, 10);

} first time = 0;

}

int main(int argc, char **argv) {

int errcount = 0;  630

int n; /* # of GC’d objects */ time t loop delay; /* begin DH changes */ time t ltime, ctime; /* end DH changes */

/* call mallopt() before anything else */ #if HAVE MALLOPT #ifdef M GRAIN

/* Round up all sizes to a multiple of this */  640

mallopt(M GRAIN, 16); #endif #ifdef M MXFAST

/* biggest size that is considered a small block */ mallopt(M MXFAST, 256);

#endif #ifdef M NBLKS

/* allocate this many small blocks at once */ mallopt(M NLBLKS, 32);

#endif  650

#endif /* HAVE MALLOPT */

memset(&local addr, '\0', sizeof(struct in addr)); local addr.s addr = inet addr(localhost); memset(&any addr, '\0', sizeof(struct in addr)); any addr.s addr = inet addr("0.0.0.0"); memset(&no addr, '\0', sizeof(struct in addr)); no addr.s addr = inet addr("255.255.255.255"); inaddr none = inet addr("X");

660

errorInitialize();

squid starttime = getCurrentTime(); failure notify = fatal dump;

mainParseOptions(argc, argv);

/* send signal to running copy and exit */ if (opt send signal != −1) {

sendSignal();  670

/* NOTREACHED */ } setMaxFD();

if (opt catch signals)

for (n = SQUID MAXFD; n > 2; n−−)

close(n); /*init comm module */

comm init();  680

/* we have to init fdstat here. */ fdstat init(PREOPEN FD); fdstat open(0, FD LOG); fdstat open(1, FD LOG); fdstat open(2, FD LOG); fd note(0, "STDIN"); fd note(1, "STDOUT"); fd note(2, "STDERR");

690

/* preinit for debug module */ debug log = stderr; hash init(0);

mainInitialize();

/* begin DH changes */ if (opt dynamic hierarchy) { const char *myhostname = getMyHostname();

if ((addself()) != 0) {  700

     debug(1,0, "Couldn't join network.\n");

} ltime = squid starttime; /* get the listing */ if ((getnet()) != 0) {

     debug(1, 0, "Error in getting new network status.\n");

} num hosts = dhBuildUI(); }

/* end DH changes */  710

/* main loop */ for (;;) { if (rotate pending) {

ftpServerClose(); icmpClose(); db rotate log(); /* cache.log */ storeWriteCleanLog(); storeRotateLog(); /* store.log */

stat rotate log(); /* access.log */ 720

useragentRotateLog(); /* useragent.log */

(void) ftpInitialize();

icmpOpen();

rotate pending = 0; } eventRun(); if ((loop delay = eventNextTime()) < 0)

loop delay = 0;

/* begin DH changes */  730

ctime = getCurrentTime(); if ((ctime − ltime)>= UPDATE TIME) {

getupdate(ltime); ltime = ctime; num hosts = dhBuildUI();

} /* end DH changes*/

switch (comm select(loop delay)) {

case COMM OK:  740

errcount = 0; /* reset if successful */ break;

case COMM ERROR:

errcount++;

debug(1, 0, "Select loop Error.  Retry %d\n", errcount);

if (errcount == 10)

 fatal dump("Select Loop failed!");

break; case COMM SHUTDOWN:

/* delayed close so we can transmit while shutdown pending */  750

if (theOutIcpConnection > 0) { comm close(theOutIcpConnection); theOutIcpConnection = −1; } if (shutdown pending) { normal shutdown(); exit(0); } else if (reread pending) { mainReinitialize();

reread pending = 0; /* reset */ 760

} else {

 fatal dump("MAIN: SHUTDOWN from comm_select, but nothing pending.");

} break;

case COMM TIMEOUT:

break; default:

fatal dump("MAIN: Internal error -- this should never happen.");

break;

}  770

} /* NOTREACHED */ return 0;

}

static void sendSignal(void) {

pid t pid;

debug log = stderr;  780

if (ConfigFile == NULL)

ConfigFile = xstrdup(DefaultConfigFile); parseConfigFile(ConfigFile); pid = readPidFile(); if (pid > 1) {

if (kill(pid, opt send signal) &&

/* ignore permissions if just running check */ !(opt send signal == 0 && errno == EPERM)) { fprintf(stderr, "%s: ERROR: Could not send ", appname);

          fprintf(stderr, "signal %d to process %d:  %s\n",  790

opt send signal, (int) pid, xstrerror()); exit(1);

} } else {

       fprintf(stderr, "%s:  ERROR: No running copy\n", appname);

exit(1); } /* signal successfully sent */ exit(0);

}  800

B.3 proto.c

/*

* $Id: proto.c,v 1.3 1997/01/08 04:56:52 marthag Exp $ *

* DEBUG: section 17 Neighbor Selection

* AUTHOR: Harvest Derived *

* SQUID Internet Object Cache http://squid.nlanr.net/Squid/

* −−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

*  10

* Squid is the result of efforts by numerous individuals from the

* Internet community. Development is led by Duane Wessels of the

* National Laboratory for Applied Network Research and funded by

* the National Science Foundation. * * This program is free software; you can redistribute it and/or modify

* it under the terms of the GNU General Public License as published by

* the Free Software Foundation; either version 2 of the License, or

* (at your option) any later version.

*  20

* This program is distributed in the hope that it will be useful,

* but WITHOUT ANY WARRANTY; without even the implied warranty of

* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. *

* You should have received a copy of the GNU General Public License

* along with this program; if not, write to the Free Software

* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. *

*/  30

/*

* Copyright (c) 1994, 1995. All rights reserved. *

* The Harvest software was developed by the Internet Research Task

* Force Research Group on Resource Discovery (IRTF−RD): *

* Mic Bowman of Transarc Corporation.

* Peter Danzig of the University of Southern California.

* Darren R. Hardy of the University of Colorado at Boulder. 40

* Udi Manber of the University of Arizona.

* Michael F. Schwartz of the University of Colorado at Boulder.

* Duane Wessels of the University of Colorado at Boulder. *

* This copyright notice applies to software in the Harvest

* “src/” directory only. Users should consult the individual

* copyright notices in the “components/” subdirectories for

* copyright information about other software bundled with the

* Harvest source code distribution.

*  50

* TERMS OF USE *

* The Harvest software may be used and re−distributed without

* charge, provided that the software origin and research team are

* cited in any use of the system. Most commonly this is

* accomplished by including a link to the Harvest Home Page

* (http://harvest.cs.colorado.edu/) from the query page of any

* Broker you deploy, as well as in the query result pages. These

* links are generated automatically by the standard Broker

* software distribution.  60

*

* The Harvest software is provided “as is”, without express or * implied warranty, and with no support nor obligation to assist

* in its use, correction, modification or enhancement. We assume

* no liability with respect to the infringement of copyrights,

* trade secrets, or any patents, and are not responsible for

* consequential damages. Proper use of the Harvest software is

* entirely the responsibility of the user. *

* DERIVATIVE WORKS  70

*

* Users may make derivative works from the Harvest software, subject

* to the following constraints: *

* − You must include the above copyright notice and these

* accompanying paragraphs in all forms of derivative works,

* and any documentation and other materials related to such

* distribution and use acknowledge that the software was

* developed at the above institutions.

*  80

* − You must notify IRTF−RD regarding your distribution of

* the derivative work. *

* − You must clearly notify users that your are distributing

* a modified version and not the original Harvest software. *

* − Any derivative product is also subject to these copyright

* and use restrictions. *

* Note that the Harvest software is NOT in the public domain. We  90

* retain copyright, as specified above. *

* HISTORY OF FREE SOFTWARE STATUS *

* Originally we required sites to license the software in cases

* where they were going to build commercial products/services

* around Harvest. In June 1995 we changed this policy. We now

* allow people to use the core Harvest software (the code found in

* the Harvest “src/” directory) for free. We made this change

* in the interest of encouraging the widest possible deployment of  100

* the technology. The Harvest software is really a reference

* implementation of a set of protocols and formats, some of which

* we intend to standardize. We encourage commercial

* re−implementations of code complying to this set of standards. */

#include "squid.h"

static int matchLocalDomain PARAMS((const char *));  110

static int protoCantFetchObject PARAMS((int, StoreEntry *, char *)); static int protoNotImplemented PARAMS((int, const char *, StoreEntry *)); static int protoDNSError PARAMS((int, StoreEntry *)); static void protoDataFree PARAMS((int, protodispatch data *)); static void protoDispatchDNSHandle PARAMS((int, const ipcache addrs *, void *));

#define OUTSIDE FIREWALL 0 #define INSIDE FIREWALL 1 #define NO FIREWALL 2

120

/* for debugging */ static char *firewall desc str[] = {

"OUTSIDE_FIREWALL",
"INSIDE_FIREWALL",
"NO_FIREWALL"

};

char *IcpOpcodeStr[] =

{  130

"ICP_INVALID",
"ICP_QUERY",
"ICP_HIT",
"ICP_MISS",
"ICP_ERR",
"ICP_SEND",
"ICP_SENDA",
"ICP_DATABEG",
"ICP_DATA",

"ICP_DATAEND",  140

"ICP_SECHO",
"ICP_DECHO",
"ICP_OP_UNUSED0",
"ICP_OP_UNUSED1",
"ICP_OP_UNUSED2",
"ICP_OP_UNUSED3",
"ICP_OP_UNUSED4",
"ICP_OP_UNUSED5",
"ICP_OP_UNUSED6",

"ICP_OP_UNUSED7",  150

"ICP_OP_UNUSED8",

"ICP_RELOADING", /* access denied while store is reloading */

"ICP_DENIED",
"ICP_HIT_OBJ",
"ICP_END"

}; #if DELAY HACK extern int delay fetch;

#endif  160

static void protoDataFree(int fdunused, protodispatch data * protoData) {

requestUnlink(protoData−>request); safe free(protoData);

}

/* called when DNS lookup is done by ipcache. */

static void  170

protoDispatchDNSHandle(int unused1, const ipcache addrs * ia, void *data) {

edge *e = NULL; struct in addr srv addr; protodispatch data *protoData = (protodispatch data *) data; StoreEntry *entry = protoData−>entry; request t *req = protoData−>request;

/* NOTE: We get here after a DNS lookup, whether or not the

* lookup was successful. Even if the URL hostname is bad,  180

* we might still ping the hierarchy */

BIT RESET(entry−>flag, IP LOOKUP PENDING);

if (protoData−>direct fetch == DIRECT YES) {

if (ia == NULL) { protoDNSError(protoData−>fd, entry); return;

}

hierarchyNote(req, HIER DIRECT, 0, req−>host);  190

protoStart(protoData−>fd, entry, NULL, req);

return; } if (protoData−>direct fetch == DIRECT MAYBE && (Config.local ip list || Config.firewall ip list)) {

if (ia == NULL) { debug(17, 3, "Unknown host: %s\n", req−>host); protoData−>direct fetch = DIRECT NO;

} else if (Config.firewall ip list) { srv addr = ia−>in addrs[ia−>cur];

if (ip access check(srv addr, Config.firewall ip list) == IP DENY) {  200

hierarchyNote(req, HIER LOCAL IP DIRECT, 0, req−>host); protoStart(protoData−>fd, entry, NULL, req); return; } else {

protoData−>direct fetch = DIRECT NO; }

} else if (Config.local ip list) { srv addr = ia−>in addrs[ia−>cur]; if (ip access check(srv addr, Config.local ip list) == IP DENY) {

hierarchyNote(req, HIER LOCAL IP DIRECT, 0, req−>host);  210

protoStart(protoData−>fd, entry, NULL, req);

return; }

} } if ((e = protoData−>single parent) &&

(Config.singleParentBypass || protoData−>direct fetch == DIRECT NO)) { /* Only one parent for this host, and okay to skip pinging stuff */ hierarchyNote(req, HIER SINGLE PARENT, 0, e−>host);

protoStart(protoData−>fd, entry, e, req);  220

return; } if (protoData−>n edges == 0 && protoData−>direct fetch == DIRECT NO) {

if ((e = protoData−>default parent)) { hierarchyNote(req, HIER DEFAULT PARENT, 0, e−>host); protoStart(protoData−>fd, entry, e, req);

} else { hierarchyNote(req, HIER NO DIRECT FAIL, 0, req−>host);

   protoCantFetchObject(protoData−>fd, entry, "No neighbors or parents to query and the host is beyond your firewall.");

}  230

return; } if (!neighbors do private keys && !protoData−>query neighbors &&

(e = getFirstUpParent(req))) { /* for private objects we should just fetch directly (because

* icpHandleUdp() won’t properly deal with the ICP replies). */ hierarchyNote(req, HIER FIRSTUP PARENT, 0, e−>host); protoStart(protoData−>fd, entry, e, req); return;

} else if (protoData−>direct fetch == DIRECT MAYBE && ia  240

&& netdbHops(ia−>in addrs[ia−>cur]) <= Config.minDirectHops) { hierarchyNote(req, HIER DIRECT, 0, req−>host); protoStart(protoData−>fd, entry, NULL, req); return;

} else if (neighborsUdpPing(protoData)) { /* call neighborUdpPing and start timeout routine */ if (entry−>ping status != PING NONE)

   fatal dump("protoDispatchDNSHandle:  bad ping_status");

if (entry−>store status != STORE PENDING)

   fatal dump("protoDispatchDNSHandle:  bad store_status");  250

if (entry−>swap status != NO SWAP)

        fatal dump("protoDispatchDNSHandle:  bad swap_status");

entry−>ping status = PING WAITING;

commSetSelect(protoData−>fd, COMM SELECT TIMEOUT, (PF) getFromDefaultSource, (void *) entry, Config.neighborTimeout);

#ifdef DELAY HACK

if (protoData−>delay fetch && entry−>mem obj)  260

entry−>mem obj−>e pings n pings++;

#endif

return; } if ((e = protoData−>default parent)) {

hierarchyNote(req, HIER DEFAULT PARENT, protoData−>fd, e−>host); protoStart(protoData−>fd, entry, e, req);

} else if (protoData−>direct fetch == DIRECT NO) { hierarchyNote(req, HIER NO DIRECT FAIL, 0, req−>host);

protoCantFetchObject(protoData−>fd, entry,  270

        "No neighbors or parents were queried and the host is beyond your firewall.");

} else if (ia == NULL) {

protoDNSError(protoData−>fd, entry); } else {

hierarchyNote(req, HIER DIRECT, 0, req−>host); protoStart(protoData−>fd, entry, NULL, req);

} }

int  280

protoDispatch(int fd, char *url, StoreEntry * entry, request t * request) {

protodispatch data *protoData = NULL; const char *method; char *request hdr;

method = RequestMethodStr[request−>method]; request hdr = entry−>mem obj−>mime hdr;

debug(17, 5, "protoDispatch:  %s URL: %s\n", method, url);  290

debug(17, 10, "request_hdr: %s\n", request hdr);

if (request−>protocol == PROTO CACHEOBJ)

return protoStart(fd, entry, NULL, request); if (request−>protocol == PROTO WAIS)

return protoStart(fd, entry, NULL, request); protoData = xcalloc(1, sizeof(protodispatch data)); protoData−>fd = fd;

protoData−>url = url;  300

protoData−>entry = entry; protoData−>request = requestLink(request); entry−>mem obj−>request = requestLink(request); comm add close handler(fd,

(PF) protoDataFree, (void *) protoData);

protoData−>inside firewall = matchInsideFirewall(request−>host); protoData−>query neighbors = BIT TEST(entry−>flag, HIERARCHICAL);

/* begin DH changes */  310

if (!opt dynamic hierarchy) { protoData−>single parent = getSingleParent(request); protoData−>default parent = getDefaultParent(request); protoData−>n edges = neighborsCount(request); } else { struct edge * dhparent = dhGetParent(url); protoData−>single parent = dhparent; protoData−>default parent = dhparent;

protoData−>n edges = dhNeighborsCount(dhparent);  320

} /* end DH changes */

#ifdef DELAY HACK

protoData−>delay fetch = delay fetch; #endif

debug(17, 2, "protoDispatch:  inside_firewall = %d (%s)\n",

protoData−>inside firewall,

firewall desc str[protoData−>inside firewall]); debug(17, 2, "protoDispatch: query_neighbors = %d\n", protoData−>query neighbors);

330

debug(17, 2, "protoDispatch: n_edges = %d\n", protoData−>n edges);

debug(17, 2, "protoDispatch:      single_parent = %s\n",

protoData−>single parent ? protoData−>single parent−>host : "N/A");

debug(17, 2, "protoDispatch:    default_parent = %s\n",

protoData−>default parent ? protoData−>default parent−>host : "N/A");

if (Config.firewall ip list) { /* Have to look up the url address so we can compare it */ protoData−>source ping = Config.sourcePing;

protoData−>direct fetch = DIRECT MAYBE;  340

BIT SET(entry−>flag, IP LOOKUP PENDING);

ipcache nbgethostbyname(request−>host, fd, protoDispatchDNSHandle,

(void *) protoData);

} else if (!protoData−>inside firewall) { /* There are firewall restrictsions, and this host is outside. */ /* No DNS lookups, call protoDispatchDNSHandle() directly */ protoData−>source ping = 0;

protoData−>direct fetch = DIRECT NO;  350

protoDispatchDNSHandle(fd, NULL, (void *) protoData);

} else if (matchLocalDomain(request−>host) || !protoData−>query neighbors) { /* will fetch from source */ protoData−>direct fetch = DIRECT YES; BIT SET(entry−>flag, IP LOOKUP PENDING); ipcache nbgethostbyname(request−>host,

fd,

protoDispatchDNSHandle,  360

(void *) protoData);

} else if (protoData−>n edges == 0) { /* will fetch from source */ protoData−>direct fetch = DIRECT YES; BIT SET(entry−>flag, IP LOOKUP PENDING); ipcache nbgethostbyname(request−>host,

fd,

protoDispatchDNSHandle,

(void *) protoData);

} else if (Config.local ip list) {  370

/* Have to look up the url address so we can compare it */ protoData−>source ping = Config.sourcePing; protoData−>direct fetch = DIRECT MAYBE; BIT SET(entry−>flag, IP LOOKUP PENDING); ipcache nbgethostbyname(request−>host,

fd,

protoDispatchDNSHandle,

(void *) protoData);

} else if (protoData−>single parent && Config.singleParentBypass &&

!(protoData−>source ping = Config.sourcePing)) {  380

/* will fetch from single parent */ protoData−>direct fetch = DIRECT MAYBE; protoDispatchDNSHandle(fd,

NULL,

(void *) protoData);

} else { /* will use ping resolution */ protoData−>source ping = Config.sourcePing; protoData−>direct fetch = DIRECT MAYBE;

BIT SET(entry−>flag, IP LOOKUP PENDING);  390

ipcache nbgethostbyname(request−>host, fd, protoDispatchDNSHandle, (void *) protoData);

} return 0;

}

int protoUnregister(int fd, StoreEntry * entry, request t * request, struct in addr src addr)

400

{ char *url = entry ? entry−>url : NULL; char *host = request ? request−>host : NULL; protocol t proto = request ? request−>protocol : PROTO NONE;

debug(17, 5, "protoUnregister FD %d '%s'\n", fd, url ? url : "NULL");

if (proto == PROTO CACHEOBJ)

return 0; if (url)

redirectUnregister(url, fd);

if (src addr.s addr != inaddr none)  410

fqdncacheUnregister(src addr, fd); if (host)

ipcache unregister(host, fd); if (entry == NULL)

return 0; if (BIT TEST(entry−>flag, ENTRY DISPATCHED))

return 0; if (entry−>mem status != NOT IN MEMORY)

return 0;

if (entry−>store status != STORE PENDING)  420

return 0; protoCancelTimeout(fd, entry); squid error entry(entry, ERR CLIENT ABORT, NULL); return 1;

}

void protoCancelTimeout(int fd, StoreEntry * entry) {

/* If fd = 0 then this thread was called from neighborsUdpAck and  430

* we must look up the FD in the pending list. */ if (!fd)

fd = storeFirstClientFD(entry−>mem obj); if (fd < 1) {

     debug(17, 1, "protoCancelTimeout:  No client for '%s'\n", entry−>url);

return; }

debug(17, 2, "protoCancelTimeout:  FD %d '%s'\n", fd, entry−>url);

if (fdstatGetType(fd) != FD SOCKET) {

     debug trap("protoCancelTimeout:  called on non-socket");  440

return; } /* cancel the timeout handler */ commSetSelect(fd,

COMM SELECT TIMEOUT,

NULL, NULL, 0);

}

450

/*

* Called from comm select() if neighbor pings timeout

* or from neighborsUdpAck() if all neighbors miss. */ int getFromDefaultSource(int fd, StoreEntry * entry) {

edge *e = NULL; char *url = NULL;

request t *request = entry−>mem obj−>request;  460

url = entry−>url;

/* if fd != 0 then we were called from comm select() because the

* timeout occured. Otherwise we were called from neighborsUdpAck(). */

if (fd) { entry−>ping status = PING TIMEOUT;

     debug(17, 5, "getFromDefaultSource:  Timeout occured pinging for '%s'\n",

url);  470

} /* Check if someone forgot to disable the read timer */ if (BIT TEST(entry−>flag, ENTRY DISPATCHED))

     fatal dump("getFromDefaultSource:  object already being fetched");

if ((e = entry−>mem obj−>e pings first miss)) { hierarchyNote(request, HIER FIRST PARENT MISS, fd, e−>host); return protoStart(fd, entry, e, request);

} if (matchInsideFirewall(request−>host)) {

if (ipcache gethostbyname(request−>host, 0) == NULL)  480

return protoDNSError(fd, entry); hierarchyNote(request, HIER DIRECT, fd, request−>host); return protoStart(fd, entry, NULL, request);

} if ((e = getDefaultParent(request))) { hierarchyNote(request, HIER DEFAULT PARENT, fd, e−>host); return protoStart(fd, entry, e, request);

} if ((e = getSingleParent(request))) {

hierarchyNote(request, HIER SINGLE PARENT, fd, e−>host);  490

return protoStart(fd, entry, e, request); } if ((e = getFirstUpParent(request))) {

hierarchyNote(request, HIER FIRSTUP PARENT, fd, e−>host);

return protoStart(fd, entry, e, request); } hierarchyNote(request, HIER NO DIRECT FAIL, fd, request−>host); protoCancelTimeout(fd, entry); protoCantFetchObject(fd, entry,

     "No ICP replies received and the host is beyond the firewall."); 500

return 0; }

int protoStart(int fd, StoreEntry * entry, edge * e, request t * request) {

char *url = entry−>url; char *request hdr = entry−>mem obj−>mime hdr; int request hdr sz = entry−>mem obj−>mime hdr sz;

debug(17, 5, "protoStart:  FD %d:  Fetching '%s %s' from %s\n",  510

fd,

RequestMethodStr[request−>method],

entry−>url,

e ? e−>host : "source"); if (BIT TEST(entry−>flag, ENTRY DISPATCHED))

     fatal dump("protoStart:  object already being fetched");

BIT SET(entry−>flag, ENTRY DISPATCHED); protoCancelTimeout(fd, entry); netdbPingSite(request−>host);

if (e) {  520

e−>stats.fetches++;

return proxyhttpStart(url, request, entry, e); } else if (request−>protocol == PROTO HTTP) {

return httpStart(url, request, request hdr, request hdr sz, entry); } else if (request−>protocol == PROTO GOPHER) {

return gopherStart(fd, url, entry); } else if (request−>protocol == PROTO FTP) {

return ftpStart(fd, url, request, entry); } else if (request−>protocol == PROTO WAIS) {

return waisStart(fd, url, request−>method, request hdr, entry);  530

} else if (request−>protocol == PROTO CACHEOBJ) { return objcacheStart(fd, url, entry); } else if (request−>method == METHOD CONNECT) {

     fatal dump("protoStart() should not be handling CONNECT");

return 0; } else {

return protoNotImplemented(fd, url, entry); } /* NOTREACHED */

}  540

static int protoNotImplemented(int fd, const char *url, StoreEntry * entry) {

LOCAL ARRAY(char, buf, 256);

debug(17, 1, "protoNotImplemented:  Cannot retrieve '%s'\n", url);

buf[0] = '\0';  550

if (httpd accel mode)

     strcpy(buf, "cached is running in HTTPD accelerator mode, so it does not allow the normal URL syntax.");

else

     sprintf(buf, "Your URL may be incorrect:  '%s'\n", url);

squid error entry(entry, ERR NOT IMPLEMENTED, NULL); return 0;

}

static int  560

protoCantFetchObject(int fd, StoreEntry * entry, char *reason) {

LOCAL ARRAY(char, buf, 2048);

debug(17, 1, "protoCantFetchObject:  FD %d %s\n", fd, reason);

debug(17, 1, "--> '%s'\n", entry−>url);

buf[0] = '\0';

sprintf(buf, "%s\n\nThe cache administrator may need to double-check the cache configuration.",

reason);  570

squid error entry(entry, ERR CANNOT FETCH, buf); return 0;

}

static int protoDNSError(int fd, StoreEntry * entry) {

debug(17, 2, "protoDNSError: FD %d '%s'\n", fd, entry−>url); protoCancelTimeout(fd, entry);

squid error entry(entry, ERR DNS FAIL, dns error message);  580

return 0; }

/*

* return 0 if the host is outside the firewall (no domains matched), and

* return 1 if the host is inside the firewall or no domains at all. */ int matchInsideFirewall(const char *host)

{  590

const wordlist *s = Config.inside firewall list; const char *key = NULL; int result = NO FIREWALL; struct in addr addr; if (!s)

/* no domains, all hosts are ”inside” the firewall */

return NO FIREWALL; for (; s; s = s−>next) {

key = s−>key;

if (!strcasecmp(key, "none"))  600

/* no domains are inside the firewall, all domains are outside */

return OUTSIDE FIREWALL; if (*key == '!') {

key++;

result = OUTSIDE FIREWALL; } else {

result = INSIDE FIREWALL; } if (matchDomainName(key, host))

return result;  610

} /* Check for dotted−quads */ if (Config.firewall ip list) {

if ((addr.s addr = inet addr(host)) != inaddr none) {

if (ip access check(addr, Config.firewall ip list) == IP DENY)

return INSIDE FIREWALL;

} } /* all through the list and no domains matched, this host must

* not be inside the firewall, it must be outside */  620

return OUTSIDE FIREWALL; }

static int matchLocalDomain(const char *host) { const wordlist *s = NULL; for (s = Config.local domain list; s; s = s−>next) {

if (matchDomainName(s−>key, host))

return 1;  630

} return 0;

}

References

[1] Bowman, C., Peter B. Danzig, Udi Manber and Michael F. Schwartz. Scalable Internet Resource Discovery: Research Problems and Approaches. Communications of the ACM, 37(8), pp. 98-107, August 1994.

[2] Chankhunthod, Anawat, Peter B. Danzig, Chuck Neerdaels, Michael F. Schwartz and Kurt J. Worrell. A Hierarchical Internet Object Cache. Technical Report 95-611, Computer Science Department, University of Southern California, Los Angeles, California, March 1995.

[3] Hardy, Darren R., Michael F. Schwartz, Duane Wessels. Harvest User’s Manual. Available at

http://harvest.transarc.com/afs/transarc.com/public/trg/Harvest/user-manual/

[4] Karger, David R., et al, Relieving Hot Spots on the World Wide Web. Available at

http://theory.lcs.mit.edu/~karger/Papers/web.ps.gz

[5] Wessels, Duane. A Distributed Testbed for National Information Provisioning. Available at

http://www.nlanr.net/Cache/

[6] Wessels, Duane. Intelligent Caching for World-Wide Web Objects. Interdisciplinary Telecommunications Program, University of Colorado

- Boulder, 1995. M.S. Thesis.

[7] Wessels, Duane. Internet Cache Protocol (ICP) version 2. Available at

http://www.nlanr.net/Cache/ICP/ICP-id.txt

[8] Wessels, Duane. Squid Internet Object Cache. Available at

http://www.nlanr.net/Squid/