htcache.c

Open VXI. This is a open source.

/*							       	    HTCache.c
**	CACHE WRITER
**
**	(c) COPYRIGHT MIT 1995.
**	Please first read the full copyright statement in the file COPYRIGH.
**	@(#) $Id: HTCache.c,v 2.73 2000/12/18 17:00:56 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;