/*							       	    HTCache.c**	CACHE WRITER****	(c) COPYRIGHT MIT 1995.**	Please first read the full copyright statement in the file COPYRIGH.**	@(#) $Id: HTCache.c,v 2.76 2001/08/30 13:49:24 kahan Exp $****	This modules manages the cache****      History:**         HFN: spawned from HTFwrite**         HWL: converted the caching scheme to be hierachical by taking**              AL code from Deamon***//* Library include files */#include "wwwsys.h"#include "WWWUtil.h"#include "WWWCore.h"#include "WWWTrans.h"#include "WWWApp.h"#include "HTCache.h"					 /* Implemented here *//* This is the default cache directory: */#define HT_CACHE_LOC	"/tmp/"#define HT_CACHE_ROOT	"w3c-cache/"#define HT_CACHE_INDEX	".index"#define HT_CACHE_LOCK	".lock"#define HT_CACHE_META	".meta"#define HT_CACHE_EMPTY_ETAG	"@w3c@"/* Default heuristics cache expirations - thanks to Jeff Mogul for good comments! */#define NO_LM_EXPIRATION	24*3600		/* 24 hours */#define MAX_LM_EXPIRATION	48*3600		/* Max expiration from LM *//***  If using LM to find the expiration then take 10% and no more than**  MAX_LM_EXPIRATION.*/#ifndef LM_EXPIRATION#define LM_EXPIRATION(t)	(HTMIN((MAX_LM_EXPIRATION), (t) / 10))#endif#define WARN_HEURISTICS		24*3600		  /* When to issue a warning */#define DUMP_FREQUENCY	10			 /* Dump index every x loads */#define MEGA			0x100000L#define HT_CACHE_TOTAL_SIZE	20		/* Default cache size is 20M */#define HT_CACHE_FOLDER_PCT	10    /* 10% of cache size for metainfo etc. */#define HT_CACHE_GC_PCT		10        /* 10% of cache size free after GC */#define HT_MIN_CACHE_TOTAL_SIZE	 5			/* 5M Min cache size */#define HT_MAX_CACHE_ENTRY_SIZE	 3     /* 3M Max sixe of single cached entry *//* Final states have negative value */typedef enum _CacheState {    CL_ERROR		= -3,    CL_NO_DATA		= -2,    CL_GOT_DATA		= -1,    CL_BEGIN		= 0,    CL_NEED_BODY,    CL_NEED_OPEN_FILE,    CL_NEED_CONTENT} CacheState;/* This is the context structure for the this module */typedef struct _cache_info {    CacheState		state;		  /* Current state of the connection */    char *		local;		/* Local representation of file name */    struct stat		stat_info;	      /* Contains actual file chosen */    HTNet *		net;    HTTimer *		timer;} cache_info;struct _HTCache {    /* Location */    int 		hash;    char *		url;    char *		cachename;    /* GC parameters */    char *		etag;    BOOL		range;	      /* Is this the full part or a subpart? */    BOOL		must_revalidate;    int			hits;				       /* Hit counts */    long		size;		       /* Size of cached entity body */    time_t		lm;				    /* Last modified */    time_t		expires;    time_t		freshness_lifetime;    time_t		response_time;    time_t		corrected_initial_age;    HTRequest *		lock;};struct _HTStream {    const HTStreamClass *	isa;    FILE *			fp;    long			bytes_written;	  /* Number of bytes written */    HTCache *			cache;    HTRequest *			request;    HTResponse *		response;    HTChunk *			buffer;			/* For index reading */    HTEOLState			EOLstate;    BOOL			append;		   /* Creating or appending? */};struct _HTInputStream {    const HTInputStreamClass *	isa;};/* Cache parameters */ PRIVATE BOOL		HTCacheEnable = NO;	      /* Disabled by default */PRIVATE BOOL		HTCacheInitialized = NO;PRIVATE BOOL		HTCacheProtected = YES;PRIVATE char *		HTCacheRoot = NULL;   /* Local Destination for cache */PRIVATE HTExpiresMode	HTExpMode = HT_EXPIRES_IGNORE;PRIVATE HTDisconnectedMode DisconnectedMode = HT_DISCONNECT_NONE;/* Heuristic expiration parameters */PRIVATE int DefaultExpiration = NO_LM_EXPIRATION;/* List of cache entries */PRIVATE HTList ** 	CacheTable = NULL;/* Cache size variables */PRIVATE long		HTCacheTotalSize = HT_CACHE_TOTAL_SIZE*MEGA;PRIVATE long		HTCacheFolderSize = (HT_CACHE_TOTAL_SIZE*MEGA)/HT_CACHE_FOLDER_PCT;PRIVATE long		HTCacheGCBuffer = (HT_CACHE_TOTAL_SIZE*MEGA)/HT_CACHE_GC_PCT;PRIVATE long		HTCacheContentSize = 0L;PRIVATE long		HTCacheMaxEntrySize = HT_MAX_CACHE_ENTRY_SIZE*MEGA;PRIVATE int		new_entries = 0;	   /* Number of new entries */PRIVATE HTNetBefore	HTCacheFilter;PRIVATE HTNetAfter	HTCacheUpdateFilter;PRIVATE HTNetAfter	HTCacheCheckFilter;/* ------------------------------------------------------------------------- *//*  			     CACHE GARBAGE COLLECTOR			     *//* ------------------------------------------------------------------------- */PRIVATE BOOL stopGC (void){    return (HTCacheContentSize + HTCacheFolderSize < HTCacheTotalSize - HTCacheGCBuffer);}PRIVATE BOOL startGC (void){    return (HTCacheContentSize + HTCacheFolderSize > HTCacheTotalSize);}PRIVATE BOOL HTCacheGarbage (void){    long old_size = HTCacheContentSize;    HTTRACE(CACHE_TRACE, "Cache....... Garbage collecting\n");    if (CacheTable) {	time_t cur_time = time(NULL);	HTList * cur;	int cnt;	int hits;	/*	**  Tell the user that we're gc'ing.	*/	{	    HTAlertCallback * cbf = HTAlert_find(HT_PROG_OTHER);	    if (cbf) (*cbf)(NULL, HT_PROG_OTHER, HT_MSG_NULL,NULL, NULL, NULL);	}	/*	**  Walk through and delete all the expired entries. If this is not	**  sufficient then take the fresh ones which have the lowest cache	**  hit count. This algorithm could be made a lot fancier by including	**  the size and also the pain it took to get the document in the first	**  case. It could also include max_stale.	*/	HTTRACE(CACHE_TRACE, "Cache....... Collecting Stale entries\n");	for (cnt=0; cnt<HT_XL_HASH_SIZE; cnt++) {	    if ((cur = CacheTable[cnt])) { 		HTList * old_cur = cur;		HTCache * pres;		while ((pres = (HTCache *) HTList_nextObject(cur)) != NULL) {		    time_t resident_time = cur_time - pres->response_time;		    time_t current_age = pres->corrected_initial_age +			resident_time;		    /* 2000-08-08 Jens Meggers: HTCache_remove doesn't		       remove a cache entry if it's locked. To avoid		       an endless loop, we check the return value of 		       HTCache_remove before skipping the entry. */		    if ((pres->freshness_lifetime < current_age)			&& HTCache_remove(pres)) {			cur = old_cur;		    } else {			old_cur = cur;		    }		    if (stopGC()) break;		}	    }	}	/*	**  We must at least free the min buffer size so that we don't	**  dead lock ourselves. We start from the bottom up by taking	**  all the documents with 0 hits, 1 hits, 2 hits, etc.	*/	HTTRACE(CACHE_TRACE, "Cache....... Collecting least used entries\n");	hits = 0;	while (startGC()) {	    BOOL removed = NO;	    HTTRACE(CACHE_TRACE, "Cache....... Collecting entries with %d hits\n" _ hits);	    for (cnt=0; cnt<HT_XL_HASH_SIZE; cnt++) {		if ((cur = CacheTable[cnt])) { 		    HTList * old_cur = cur;		    HTCache * pres;		    while ((pres = (HTCache *) HTList_nextObject(cur))) {			/* 2000-08-08 Jens Meggers: HTCache_remove doesn't			   remove a cache entry if it's locked. To avoid			   going into an endless loop, we check the return			   value of  HTCache_remove before marking the			   object as removed. */			if ((pres->size > HTCacheMaxEntrySize 			     || pres->hits <= hits) 			    && HTCache_remove(pres)) {			    cur = old_cur;			    removed = YES;			} else {			    old_cur = cur;			}			if (stopGC()) break;		    }		}	    }	    if (!removed) break;	    hits++;	}	HTTRACE(CACHE_TRACE, "Cache....... Size reduced from %ld to %ld\n" _ 		    old_size _ HTCacheContentSize);	/*	**  Dump the new content to the index file	*/	HTCacheIndex_write(HTCacheRoot);	new_entries = 0;	return YES;    }    return NO;}/* ------------------------------------------------------------------------- *//*  			      CACHE INDEX				     *//* ------------------------------------------------------------------------- */PRIVATE char * cache_index_name (const char * cache_root){    if (cache_root) {	char * location = NULL;	if ((location = (char *)	     HT_MALLOC(strlen(cache_root) + strlen(HT_CACHE_INDEX) + 1)) == NULL)	    HT_OUTOFMEM("cache_index_name");	strcpy(location, cache_root);	strcat(location, HT_CACHE_INDEX);	return location;    }    return NULL;}/***  Remove the cache index file*/PUBLIC BOOL HTCacheIndex_delete (const char * cache_root){    if (cache_root) {	char * index = cache_index_name(cache_root);	REMOVE(index);	HT_FREE(index);	return YES;    }    return NO;}/***	Walk through the list of cached objects and save them to disk.**	We override any existing version but that is normally OK as we have**	already read its contents.*/PUBLIC BOOL HTCacheIndex_write (const char * cache_root){    if (cache_root && CacheTable) {	char * index = cache_index_name(cache_root);	FILE * fp = NULL;	HTTRACE(CACHE_TRACE, "Cache Index. Writing index `%s\'\n" _ index);	/*	**  Open the file for writing. Note - we don't take a backup!	**  This should probably be fixed!	*/	if (!index) return NO;	if ((fp = fopen(index, "wb")) == NULL) {	    HTTRACE(CACHE_TRACE, "Cache Index. Can't open `%s\' for writing\n" _ index);	    HT_FREE(index);	    return NO;	}	/*	**  Walk through the list and write it out. The format is really	**  simple as we keep it all in ASCII.	*/	{	    HTList * cur;	    int cnt;	    for (cnt=0; cnt<HT_XL_HASH_SIZE; cnt++) {		if ((cur = CacheTable[cnt])) { 		    HTCache * pres;		    while ((pres = (HTCache *) HTList_nextObject(cur))) {			if (fprintf(fp, "%s %s %s %ld %ld %ld %c %d %d %ld %ld %ld %c\r\n",				    pres->url,				    pres->cachename,				    pres->etag ? pres->etag : HT_CACHE_EMPTY_ETAG,				    (long) (pres->lm),				    (long) (pres->expires),				    pres->size,				    pres->range+0x30,				    pres->hash,				    pres->hits,				    (long) (pres->freshness_lifetime),				    (long) (pres->response_time),				    (long) (pres->corrected_initial_age),				    pres->must_revalidate+0x30) < 0) {			    HTTRACE(CACHE_TRACE, "Cache Index. Error writing cache index\n");			    return NO;			}		    }		}	    }	}	/* Done writing */	fclose(fp);	HT_FREE(index);    }    return NO;}/***	Load one line of index file**	Returns YES if line OK, else NO*/PRIVATE BOOL HTCacheIndex_parseLine (char * line){    HTCache * cache = NULL;    if (line) {	char validate;	char range;	if ((cache = (HTCache *) HT_CALLOC(1, sizeof(HTCache))) == NULL)	    HT_OUTOFMEM("HTCacheIndex_parseLine");	/*	**  Read the line and create the cache object	*/	{	    char * url = HTNextField(&line);	    char * cachename = HTNextField(&line);	    char * etag = HTNextField(&line);	    StrAllocCopy(cache->url, url);	    StrAllocCopy(cache->cachename, cachename);	    if (strcmp(etag, HT_CACHE_EMPTY_ETAG)) StrAllocCopy(cache->etag, etag);	}#ifdef HAVE_LONG_TIME_T	/*	**  On some 64 bit machines (alpha) time_t is of type int and not long.	**  This means that we have to adjust sscanf accordingly so that we	**  know what we are looking for. Otherwise er may get unalignment	**  problems.	*/	if (sscanf(line, "%ld %ld %ld %c %d %d %ld %ld %ld %c",#else	if (sscanf(line, "%d %d %ld %c %d %d %d %d %d %c",#endif		   &cache->lm,		   &cache->expires,		   &cache->size,		   &range,		   &cache->hash,		   &cache->hits,		   &cache->freshness_lifetime,		   &cache->response_time,		   &cache->corrected_initial_age,		   &validate) < 0) {	    HTTRACE(CACHE_TRACE, "Cache Index. Error reading cache index\n");	    return NO;	}	cache->range = range-0x30;	cache->must_revalidate = validate-0x30;	/*	**  Create the new anchor and fill in the expire information we have read	**  in the index.	*/	if (cache) {	    HTAnchor * anchor = HTAnchor_findAddress(cache->url);	    HTParentAnchor * parent = HTAnchor_parent(anchor);	    HTAnchor_setExpires(parent, cache->expires);	    	    HTAnchor_setLastModified(parent, cache->lm);	    if (cache->etag) HTAnchor_setEtag(parent, cache->etag);	}	/*	**  Create the cache table if not already existent and add the new	**  entry. Also check that the hash is still within bounds	*/	if (!CacheTable) {	    if ((CacheTable = (HTList **) HT_CALLOC(HT_XL_HASH_SIZE,						    sizeof(HTList *))) == NULL)		HT_OUTOFMEM("HTCache_parseLine");	}	if (cache->hash >= 0 && cache->hash < HT_XL_HASH_SIZE) {	    int hash = cache->hash;	    if (!CacheTable[hash]) CacheTable[hash] = HTList_new();	    HTList_addObject(CacheTable[hash], (void *) cache);	}	/* Update the total cache size */	HTCacheContentSize += cache->size;	return YES;    }    return NO;}/***	Folding is either of CF LWS, LF LWS, CRLF LWS*/PRIVATE int HTCacheIndex_put_block (HTStream * me, const char * b, int l){    while (l > 0) {	if (me->EOLstate == EOL_FCR) {	    if (*b == LF)				   	     /* CRLF */		me->EOLstate = EOL_FLF;	    else if (isspace((int) *b))				   /* Folding: CR SP */		me->EOLstate = EOL_DOT;	    else {						 /* New line */		HTCacheIndex_parseLine(HTChunk_data(me->buffer));		me->EOLstate = EOL_BEGIN;		HTChunk_clear(me->buffer);		continue;	    }	} else if (me->EOLstate == EOL_FLF) {	    if (isspace((int) *b))		       /* Folding: LF SP or CR LF SP */		me->EOLstate = EOL_DOT;	    else {						/* New line */		HTCacheIndex_parseLine(HTChunk_data(me->buffer));		me->EOLstate = EOL_BEGIN;		HTChunk_clear(me->buffer);		continue;	    }	} else if (me->EOLstate == EOL_DOT) {	    if (isspace((int) *b)) {		me->EOLstate = EOL_BEGIN;		HTChunk_putc(me->buffer, ' ');	    } else {		HTCacheIndex_parseLine(HTChunk_data(me->buffer));		me->EOLstate = EOL_BEGIN;