cache.c

Win9x下文件系统驱动的例子(EXT2)源代码。

#include "vxd.h"

#include "shared\vxddebug.h"
#include "cache.h"



/*
 * This module implements a cache mechansism used for directory
 * entries and diskblocks.
 *
 * There are two flavours of the Cache:
 *	1.	dir. entry caches: Stores the inode number of dir. entries
 *		It is a two-level cache to prevent flushing when reading
 *		"uninterresting" items. An item is lifted from level 1 to 2
 *		after a cache-hit. The Cache allocates the space to store
 *		the cached inode numbers itself.
 *		Also, each object is looked by Id (actually two Ids: the 
 *		MediumId and the ObjectId) and by name. 
 *
 *	2.	diskblock caches: The cache will not store copies of
 *		disk blocks but, instead, it stores the pointers only.
 *		This implies that a client of such a TCache object is
 *		responsible for allocating space for the object.
 *		When a disk block is successfully looked up, the 
 *		pointer to the disk block's buffer is returned; also
 *		the cache object itself is removed from the cache.
 *		This is a _must_ because when other cache objects are
 *		added, stored cache objects are removed (last recently 
 *		used first). If so, the data (i.e., the disk block's 
 *		buffer) is freed. 
 *		Diskblock caches only have one level and they lookup
 *		a block by Id only (again, actually two IDs)
 *
 * TCache objects are thread-safe as they use a Mutex to
 * synchronise update to internal data structures.
 *
 */

#define HASH_QUEUE_SIZE 4
#define LEVEL1 '\1'
#define LEVEL2 '\2'

#define MAX_CACHE_NAME		16
#define MAX_OBJECT_NAME		16

/**********************************
 *
 * PRIVATE TYPEDEFS
 *
 **********************************/


typedef struct _CacheObject
{
	unsigned long		MediumId;
	unsigned long		ObjectId;
	char				ObjectName[MAX_OBJECT_NAME];
	unsigned			NameLen;

	void				*ObjectData;

	unsigned short		HashIndex;
	unsigned char		Level;

	struct _CacheObject *LruNext;
	struct _CacheObject *LruPrev;
	struct _CacheObject	*HashNext;
	struct _CacheObject	*HashPrev;
} TCacheObject;


typedef struct _Cache
{
	TCacheObject		**HashQueue;
	TCacheObject		*LruHead[2];
	TCacheObject		*CacheObjectList;
	
	void				*ObjectDataSpace;
	
	UINT				HashSize;
	UINT				nrObjects;
	UINT				ObjectDataSize;

	char				Name[MAX_CACHE_NAME];
	ULONG				nrLookups;
	ULONG				nrHits;

	MUTEXHANDLE			Mutex;
} TCache;


/**********************************
 *
 * GLOBAL DATA
 *
 **********************************/

// none


/**********************************
 *
 * STATIC DATA
 *
 **********************************/

// none


/************************************************
 *
 * STATIC HELPERS
 *
 * All static helpers assume that access to the
 * Cache's internal datastructures is protected
 * by a synchronisation object
 *
 *************************************************/


/*
 * Simple hash function
 */
static __inline unsigned short HashFunction(unsigned MediumId, unsigned long ObjectId, const char *ObjectName, unsigned NameLen, unsigned HashSize)
{
	return 	(ObjectName) ?
		//(unsigned short) (MediumId ^ ObjectId ^ ( ((unsigned long) NameLen) * *((unsigned char *) ObjectName))
		(unsigned short) ((MediumId ^ ObjectId ^ ((unsigned long) NameLen))
			% (unsigned long) HashSize)
		:
		(unsigned short) ((MediumId ^ ObjectId) % (unsigned long) HashSize);
}



static void LruRemove(TCache *Cache, TCacheObject *Object)
{
	TCacheObject **Lru = &(Cache->LruHead[Object->Level-1]);
	
		/*
		 *  remove object, special care if were are the LruHead
		 */
	if (Object == (*Lru))
		(*Lru) = (*Lru)->LruNext;
	Object->LruPrev->LruNext = Object->LruNext;
	Object->LruNext->LruPrev = Object->LruPrev;
}


static void LruPutBefore(TCacheObject *Object1, TCacheObject *Object2)
{

		/*
		 * insert Object1 before Object2
		 */
	Object1->LruNext = Object2;
	Object1->LruPrev = Object2->LruPrev;
	Object2->LruPrev->LruNext = Object1;
	Object2->LruPrev = Object1;
}


static void HashRemove(TCacheObject **HashQueue, TCacheObject *Object)
{
		/*
		 * First see if we are hashed
		 */
	if (Object->HashIndex == 0xFFFFu)
		return;

	if (Object->HashNext == Object)
	{

			/* 
			 * removal of last object 
			 */
		HashQueue[Object->HashIndex] = 0;
	}
	else
	{
		Object->HashNext->HashPrev = Object->HashPrev;
		Object->HashPrev->HashNext = Object->HashNext;

			/* 
			 * ensure that that queue points to something 
			 */
		HashQueue[Object->HashIndex] = Object->HashNext;
	}
	Object->HashNext = 0;
	Object->HashPrev = 0;
	Object->HashIndex = 0xFFFFu;
}


static void HashAdd(TCacheObject **HashQueue, TCacheObject *Object)
{
	TCacheObject	*HashFirst;
	

		/*
		 * Get beginning of hash queue
		 */
	HashFirst = HashQueue[Object->HashIndex];

	if (HashFirst)
	{
			/*
			 * For non-empty list position us as the first item
			 */
		Object->HashNext = HashFirst;
		Object->HashPrev = HashFirst->HashPrev;
		HashFirst->HashPrev->HashNext = Object;
		HashFirst->HashPrev = Object;
	}
	else
	{
			/*
			 * We are the only item
			 */
		Object->HashNext = Object;
		Object->HashPrev = Object;
	}

	HashQueue[Object->HashIndex] = Object;
}



static void CacheUpdate(TCache *Cache, TCacheObject *Object)
{

		/*
		 * We have an object, put it last in the list (ie the most recent one)
		 */
	LruRemove(Cache, Object);
	LruPutBefore(Object, Cache->LruHead[Object->Level-1]);
}


static void CacheLiftLevel(TCache *Cache, TCacheObject *Object)
{
	TCacheObject 	*LruHead2 = Cache->LruHead[1];

		/*
		 * We replace 'object' from level 1 with the lastest used object from level2
		 * because we made 'object' the most recent in level 1, the level2_object
		 * will now be the most recent object in level 1 (seems fair enough)
		 *
		 * Finally we mark 'object' in level 2 as the most recent one
		 */

		/*
		 * first remove them
		 */
	LruRemove(Cache, LruHead2);
	LruRemove(Cache, Object);

		/*
		 * switch level
		 */
	LruHead2->Level = LEVEL1;
	Object->Level = LEVEL2;

		/*
		 * put them in the right position, that is, most recently used
		 */
	LruPutBefore(LruHead2, Cache->LruHead[0]);
	LruPutBefore(Object, Cache->LruHead[1]);
}



/*
 * Lookup item by Id and possibly by name
 *
 */
static BOOL CacheLookupByNameOrId(TCache *Cache, unsigned long MediumId, unsigned long ObjectId, const char *ObjectName, unsigned NameLen, void *ObjectData)
{
	TCacheObject		*CacheObject, *HashFirst;
	unsigned short		HashIndex;

	VxdDebugPrint(D_CACHE, "CacheLookup: cache=%s, medium=%lu, id=%lu, len=%u", 
			Cache->Name, 
			MediumId, 
			ObjectId,
			NameLen);

	Cache->nrLookups++;

		/*
		 * Find the object in the hash_queue, if the list is
		 * empty, the item is not there
		 */
	HashIndex = HashFunction(MediumId, ObjectId, ObjectName, NameLen, Cache->HashSize);

	HashFirst = Cache->HashQueue[HashIndex];
	if (!HashFirst)
	{
		VxdDebugPrint(D_CACHE, "CacheLookup: miss, hash chain empty");
		return FALSE;
	}

		/*
		 * itterate over the list to see if it's there
		 */
	CacheObject = HashFirst;
	do
	{
			/*
			 * Let's see if we match.
			 * first, MediumId and ObjectId must match
			 * next, if we looking on ObjectName as well, compare the object's name
			 */
		if (! ((CacheObject->MediumId == MediumId) && (CacheObject->ObjectId == ObjectId)))
			continue;
		if (ObjectName)
			if (! ((CacheObject->NameLen==NameLen) && (memcmp(ObjectName, CacheObject->ObjectName, CacheObject->NameLen)==0))) 
				continue;
			
			/*
			 * Match found !
			 */
		VxdDebugPrint(D_CACHE, "CacheLookup: done, lookup hit");
		Cache->nrHits++;
		
			/*
			 * For the block cache we remove the item.
			 * For the dir. entry cache we levellift id needed
			 * and mark the item the most recent one.
			 */
		if (Cache->ObjectDataSize)
		{
				/*
				 * if the item is in level 1 cache, lift it to level 2
				 * otherwise, make it the most recent one
				 */
			if (CacheObject->Level == LEVEL1)
				CacheLiftLevel(Cache, CacheObject);
			else
				CacheUpdate(Cache, CacheObject);
			memcpy(ObjectData, CacheObject->ObjectData, Cache->ObjectDataSize);
		}
		else
		{
				/*
				 * Remove the item from the hash list (it will
				 * never be found again)
				 * Also, make this the least recently used (it
				 * will be the first one reused when a new item 
				 * is added to the cache is full)
				 */
			HashRemove(Cache->HashQueue, CacheObject);
			CacheUpdate(Cache, CacheObject);		// at the end
			Cache->LruHead[0] = CacheObject;		// at the beginning
			* ((char **) ObjectData) = (char *) CacheObject->ObjectData;
			CacheObject->ObjectData = 0;
		}

		return TRUE;

	} while ((CacheObject = CacheObject->HashNext) != HashFirst);

	VxdDebugPrint(D_CACHE, "CacheLookup: done, lookup miss");

	return FALSE;
}


/*
 * Add an item to the cache, replacing the least recently used.
 * It is made the most recent in level 1.
 *
 * PRE CONDITION:
 *	NameLen <= MAX_OBJECT_NAME
 */
static void CacheAddByNameOrId(TCache *Cache, unsigned long MediumId, unsigned long ObjectId, char *ObjectName, unsigned NameLen, void *ObjectData)
{
	unsigned short		NewHashIndex;
	TCacheObject*		CacheObject;

	VxdDebugPrint(D_CACHE, "CacheAdd: cache=%s, medium=%u, id=%u, namelen=%u", 
		Cache->Name, 
		MediumId, 
		ObjectId, 
		NameLen);

		/*
		 * Get the least recently used
		 */
	CacheObject = Cache->LruHead[0];
	
		/*
		 * Set the new memebers
		 */
	CacheObject->MediumId = MediumId;
	CacheObject->ObjectId = ObjectId;
	if (ObjectName)
	{
		memcpy(CacheObject->ObjectName, ObjectName, NameLen);
		CacheObject->NameLen = NameLen;
	}

		/*
		 * If the new object has a different hash value than the object
		 * we are replacing, update the hash links
		 */
	NewHashIndex = 	HashFunction(MediumId, ObjectId, ObjectName, NameLen, Cache->HashSize);
	if (NewHashIndex != CacheObject->HashIndex)
	{
		HashRemove(Cache->HashQueue, CacheObject);
		CacheObject->HashIndex = NewHashIndex;
		HashAdd(Cache->HashQueue, CacheObject);
	}

		/*
		 * Make the new object the most recent one, by pointing
		 * the head of the list to the next item (so the object
		 * is now at the end of the list.
		 */
	Cache->LruHead[0] = CacheObject->LruNext;
	
		/*
		 * If we are a diskblock cache, check if
		 * the object we are removing must be deleted.
		 */
	if (Cache->ObjectDataSize == 0)
	{
		if (CacheObject->ObjectData)
		{
			VxdDebugPrint(D_CACHE, "CacheAddByNameOrId: flushing %X", CacheObject->ObjectData);
			free(CacheObject->ObjectData);
		}
		CacheObject->ObjectData = ObjectData;
		VxdDebugPrint(D_CACHE, "CacheAddByNameOrId: adding %X", CacheObject->ObjectData);
	}
	else
		memcpy(CacheObject->ObjectData, ObjectData, Cache->ObjectDataSize);

	VxdDebugPrint(D_CACHE, "CacheAdd: done");
}





/**********************************
 *
 * INTERFACE ROUTINES
 *
 **********************************/



/* 
 * Create a TCache object. The Cache can either be a dir. entry
 * cache or a diskblock cache. Cache object can be stored 
 * by either object Id or by object Id and Object Name. 
 * In both ways, a Medium id on which the object resides can be 
 * specified. For dir. entry caches, the cache allocates the 
 * memory to store the copies of the objects. For diskblock
 * caches, the client is responsible for the object's data memory.
 *
 * PRE CONDITIONS
 *	<none>
 * POST CONDITIONS
 *	Cache object created and initialised. If cache is a dir. entry
 *	cache, space for these objects is allocated.
 *
 * IN
 *	CacheName:	A descriptive name, used in debug messages (only 
 *				first 16 charecters are used)
 *	NrObjects:	Number of Objects to store in the cache
 *	DataSize:	If the cache should only conain dir. entrys,
 *				specify the size, the cache will allocate the space
 *				for all objects at once. Specify 0 if the cache
 *				contains diskblocks.
 * OUT:
 *	<none>
 *
 * RETURN VALUE:
 *	On success a valid pointer to an TCache object, otherwise 0
 */ 
TCache* CacheCreate(const char *CacheName, unsigned NrObjects, unsigned ObjectDataSize)
{
	TCache				*Cache;
	TCacheObject		*CacheObject;
	unsigned			i, HalfWay;


	VxdDebugPrint(D_SYSTEM, "CacheCreate: cache=%s, nr=%u, size=%u", CacheName, NrObjects, ObjectDataSize);