cache.c

这是一个同样来自贝尔实验室的和UNIX有着渊源的操作系统, 其简洁的设计和实现易于我们学习和理解

#include "stdinc.h"
#include "vac.h"
#include "dat.h"
#include "fns.h"

typedef struct Label Label;

enum {
	BadHeap = ~0,
};

/*
 * the plan is to store data to the cache in c->size blocks
 * with the block zero extended to fill it out.  When writing to
 * venti, the block will be zero truncated.  The walker will also check
 * that the block fits within psize or dsize as the case may be.
 */

struct Cache
{
	VtLock	*lk;
	VtSession *z;
	u32int	now;			/* ticks for usage timestamps */
	int	size;			/* max. size of any block; allocated to each block */
	Lump	**heads;		/* hash table for finding address */
	int	nheap;			/* number of available victims */
	Lump	**heap;			/* heap for locating victims */
	long	nblocks;		/* number of blocks allocated */
	Lump	*blocks;		/* array of block descriptors */
	u8int	*mem;			/* memory for all block descriptors */
	Lump	*free;			/* free list of lumps */

	long hashSize;
};

/*
 * the tag for a block is hash(index, parent tag)
 */

struct Label {
	uchar gen[4];
	uchar state;
	uchar type;		/* top bit indicates it is part of a directory */
	uchar tag[4];		/* tag of file it is in */
};


static char ENoDir[] = "directory entry is not allocated";

static void fixHeap(int si, Lump *b);
static int upHeap(int i, Lump *b);
static int downHeap(int i, Lump *b);
static char	*lumpState(int);
static void	lumpSetState(Lump *u, int state);

Cache *
cacheAlloc(VtSession *z, int blockSize, long nblocks)
{
	int i;
	Cache *c;
	Lump *b;

	c = vtMemAllocZ(sizeof(Cache));
	
	c->lk = vtLockAlloc();
	c->z = z;
	c->size = blockSize;
	c->nblocks = nblocks;
	c->hashSize = nblocks;
	c->heads = vtMemAllocZ(c->hashSize*sizeof(Lump*));
	c->heap = vtMemAllocZ(nblocks*sizeof(Lump*));
	c->blocks = vtMemAllocZ(nblocks*sizeof(Lump));
	c->mem = vtMemAllocZ(nblocks * blockSize);
	for(i = 0; i < nblocks; i++){
		b = &c->blocks[i];
		b->lk = vtLockAlloc();
		b->c = c;
		b->data = &c->mem[i * blockSize];
		b->addr = i+1;
		b->state = LumpFree;
		b->heap = BadHeap;
		b->next = c->free;
		c->free = b;
	}
	c->nheap = 0;

	return c;
}

long
cacheGetSize(Cache *c)
{
	return c->nblocks;
}

int
cacheGetBlockSize(Cache *c)
{
	return c->size;
}

int
cacheSetSize(Cache *c, long nblocks)
{
	USED(c);
	USED(nblocks);
	return 0;
}

void
cacheFree(Cache *c)
{
	int i;

	for(i = 0; i < c->nblocks; i++){
		assert(c->blocks[i].ref == 0);
		vtLockFree(c->blocks[i].lk);
	}
	vtMemFree(c->heads);
	vtMemFree(c->blocks);
	vtMemFree(c->mem);
	vtMemFree(c);
}

static u32int
hash(Cache *c, uchar score[VtScoreSize], int type)
{
	u32int h;
	uchar *p = score + VtScoreSize-4;

	h = (p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3];
	h += type;
	return h % c->hashSize;
}

static void
findLump(Cache *c, Lump *bb)
{
	Lump *b, *last;
	int h;

	last = nil;
	h = hash(c, bb->score, bb->type);
	for(b = c->heads[h]; b != nil; b = b->next){
		if(last != b->prev)
			vtFatal("bad prev link");
		if(b == bb)
			return;
		last = b;
	}
	vtFatal("block missing from hash table");
}

void
cacheCheck(Cache *c)
{
	u32int size, now;
	int i, k, refed, free;
	static uchar zero[VtScoreSize];
	Lump *p;

	size = c->size;
	now = c->now;

	free = 0;
	for(p=c->free; p; p=p->next)
		free++;
	for(i = 0; i < c->nheap; i++){
		if(c->heap[i]->heap != i)
			vtFatal("mis-heaped at %d: %d", i, c->heap[i]->heap);
		if(i > 0 && c->heap[(i - 1) >> 1]->used2 - now > c->heap[i]->used2 - now)
			vtFatal("bad heap ordering");
		k = (i << 1) + 1;
		if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now)
			vtFatal("bad heap ordering");
		k++;
		if(k < c->nheap && c->heap[i]->used2 - now > c->heap[k]->used2 - now)
			vtFatal("bad heap ordering");
	}

	refed = 0;
	for(i = 0; i < c->nblocks; i++){
		if(c->blocks[i].data != &c->mem[i * size])
			vtFatal("mis-blocked at %d", i);
		if(c->blocks[i].ref && c->blocks[i].heap == BadHeap){
			refed++;
		}
		if(memcmp(zero, c->blocks[i].score, VtScoreSize))
			findLump(c, &c->blocks[i]);
	}
if(refed > 0)fprint(2, "cacheCheck: nheap %d refed %d free %d\n", c->nheap, refed, free);
	assert(c->nheap + refed + free == c->nblocks);
	refed = 0;
	for(i = 0; i < c->nblocks; i++){
		if(c->blocks[i].ref) {
if(1)fprint(2, "%d %V %d %s\n", c->blocks[i].type, c->blocks[i].score, c->blocks[i].ref, lumpState(c->blocks[i].state));
			refed++;
		}
	}
if(refed > 0)fprint(2, "cacheCheck: in used %d\n", refed);
}

/*
 * delete an arbitrary block from the heap
 */
static void
delHeap(Lump *db)
{
	fixHeap(db->heap, db->c->heap[--db->c->nheap]);
	db->heap = BadHeap;
}

static void
fixHeap(int si, Lump *b)
{
	int i;

	i = upHeap(si, b);
	if(i == si)
		downHeap(i, b);
}

static int
upHeap(int i, Lump *b)
{
	Lump *bb;
	u32int now;
	int p;
	Cache *c;
	
	c = b->c;
	now = c->now;
	for(; i != 0; i = p){
		p = (i - 1) >> 1;
		bb = c->heap[p];
		if(b->used2 - now >= bb->used2 - now)
			break;
		c->heap[i] = bb;
		bb->heap = i;
	}
	c->heap[i] = b;
	b->heap = i;

	return i;
}

static int
downHeap(int i, Lump *b)
{
	Lump *bb;
	u32int now;
	int k;
	Cache *c;
	
	c = b->c;
	now = c->now;
	for(; ; i = k){
		k = (i << 1) + 1;
		if(k >= c->nheap)
			break;
		if(k + 1 < c->nheap && c->heap[k]->used2 - now > c->heap[k + 1]->used2 - now)
			k++;
		bb = c->heap[k];
		if(b->used2 - now <= bb->used2 - now)
			break;
		c->heap[i] = bb;
		bb->heap = i;
	}
	c->heap[i] = b;
	b->heap = i;
	return i;
}


/* called with c->lk held */
Lump *
cacheBumpLump(Cache *c)
{
	Lump *b;

	/*
	 * missed: locate the block with the oldest second to last use.
	 * remove it from the heap, and fix up the heap.
	 */
	if(c->free) {
		b = c->free;
		c->free = b->next;
	} else {
		for(;;){
			if(c->nheap == 0) {
				cacheCheck(c);
				assert(0);
				return nil;
			}
			b = c->heap[0];
			delHeap(b);
			if(b->ref == 0)
				break;
		}

		/*
		 * unchain the block from hash chain
		 */
		if(b->prev == nil)
			c->heads[hash(c, b->score, b->type)] = b->next;
		else
			b->prev->next = b->next;
		if(b->next != nil)
			b->next->prev = b->prev;

	}

	/*
	 * the new block has no last use, so assume it happens sometime in the middle
	 */
	b->used = (b->used2 + c->now) / 2;
	b->asize = 0;

	return b;
}

Lump *
cacheAllocLump(Cache *c, int type, int size, int dir)
{
	Lump *b;
	ulong h;

	assert(size <= c->size);

again:
	vtLock(c->lk);
	b = cacheBumpLump(c);
	if(b == nil) {
		vtUnlock(c->lk);
fprint(2, "cache is full\n");
		/* XXX should be better */
		sleep(100);
		goto again;
	}

	vtLock(b->lk);

	assert(b->ref == 0);
	b->ref++;
	b->used2 = b->used;
	b->used = c->now++;

	/* convert addr into score */
	memset(b->score, 0, VtScoreSize-4);
	b->score[VtScoreSize-4] = b->addr>>24;
	b->score[VtScoreSize-3] = b->addr>>16;
	b->score[VtScoreSize-2] = b->addr>>8;
	b->score[VtScoreSize-1] = b->addr;
	
	b->dir = dir;
	b->type = type;
	b->gen = 0;
	b->asize = size;
	b->state = LumpFree;

	h = hash(c, b->score, b->type);

	/* chain onto correct hash */
	b->next = c->heads[h];
	c->heads[h] = b;
	if(b->next != nil)
		b->next->prev = b;
	b->prev = nil;

	vtUnlock(c->lk);

	vtZeroExtend(type, b->data, 0, size);
	lumpSetState(b, LumpActive);

	return b;
}

int
scoreIsLocal(uchar score[VtScoreSize])
{
	static uchar zero[VtScoreSize];
	
	return memcmp(score, zero, VtScoreSize-4) == 0;
}

Lump *
cacheGetLump(Cache *c, uchar score[VtScoreSize], int type, int size)
{
	Lump *b;
	ulong h;
	int n;
	static uchar zero[VtScoreSize];

	assert(size <= c->size);

	h = hash(c, score, type);

again:
	/*
	 * look for the block in the cache
	 */
	vtLock(c->lk);
	for(b = c->heads[h]; b != nil; b = b->next){
		if(memcmp(b->score, score, VtScoreSize) == 0 && b->type == type)
			goto found;
	}

	/* should not be looking for a temp block */
	if(scoreIsLocal(score)) {
		if(memcmp(score, zero, VtScoreSize) == 0)
			vtSetError("looking for zero score");
		else
			vtSetError("missing local block");
		vtUnlock(c->lk);
		return nil;
	}

	b = cacheBumpLump(c);
	if(b == nil) {
		vtUnlock(c->lk);
		sleep(100);
		goto again;
	}

	/* chain onto correct hash */
	b->next = c->heads[h];
	c->heads[h] = b;
	if(b->next != nil)
		b->next->prev = b;
	b->prev = nil;

	memmove(b->score, score, VtScoreSize);	
	b->type = type;
	b->state = LumpFree;

found:
	b->ref++;
	b->used2 = b->used;
	b->used = c->now++;