xref: /plan9/sys/src/cmd/venti/srv/lumpcache.c (revision 23566e0c4b9b5ce80121325d240a2f6e83a70a8f)

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

/* #define CHECK(x)	x */
#define CHECK(x)

typedef struct LumpCache	LumpCache;

enum
{
	HashLog		= 9,
	HashSize	= 1<<HashLog,
	HashMask	= HashSize - 1,
};

struct LumpCache
{
	QLock		lock;
	Rendez		full;
	Lump		*free;			/* list of available lumps */
	u32int		allowed;		/* total allowable space for packets */
	u32int		avail;			/* remaining space for packets */
	u32int		now;			/* ticks for usage timestamps */
	Lump		**heads;		/* hash table for finding address */
	int		nheap;			/* number of available victims */
	Lump		**heap;			/* heap for locating victims */
	int		nblocks;		/* number of blocks allocated */
	Lump		*blocks;		/* array of block descriptors */
};

static LumpCache	lumpcache;

static void	delheap(Lump *db);
static int	downheap(int i, Lump *b);
static void	fixheap(int i, Lump *b);
static int	upheap(int i, Lump *b);
static Lump	*bumplump(void);

void
initlumpcache(u32int size, u32int nblocks)
{
	Lump *last, *b;
	int i;

	lumpcache.full.l = &lumpcache.lock;
	lumpcache.nblocks = nblocks;
	lumpcache.allowed = size;
	lumpcache.avail = size;
	lumpcache.heads = MKNZ(Lump*, HashSize);
	lumpcache.heap = MKNZ(Lump*, nblocks);
	lumpcache.blocks = MKNZ(Lump, nblocks);
	setstat(StatLcacheSize, lumpcache.nblocks);

	last = nil;
	for(i = 0; i < nblocks; i++){
		b = &lumpcache.blocks[i];
		b->type = TWID8;
		b->heap = TWID32;
		b->next = last;
		last = b;
	}
	lumpcache.free = last;
	lumpcache.nheap = 0;
}

Lump*
lookuplump(u8int *score, int type)
{
	uint ms;
	Lump *b;
	u32int h;

	ms = 0;
	trace(TraceLump, "lookuplump enter");

	h = hashbits(score, HashLog);

	/*
	 * look for the block in the cache
	 */
	qlock(&lumpcache.lock);
	CHECK(checklumpcache());
again:
	for(b = lumpcache.heads[h]; b != nil; b = b->next){
		if(scorecmp(score, b->score)==0 && type == b->type){
			addstat(StatLcacheHit, 1);
			trace(TraceLump, "lookuplump hit");
			goto found;
		}
	}

	trace(TraceLump, "lookuplump miss");

	/*
	 * missed: locate the block with the oldest second to last use.
	 * remove it from the heap, and fix up the heap.
	 */
	while(lumpcache.free == nil){
		trace(TraceLump, "lookuplump bump");
		CHECK(checklumpcache());
		if(bumplump() == nil){
			CHECK(checklumpcache());
			logerr(EAdmin, "all lump cache blocks in use");
			addstat(StatLcacheStall, 1);
			CHECK(checklumpcache());
			rsleep(&lumpcache.full);
			CHECK(checklumpcache());
			addstat(StatLcacheStall, -1);
			goto again;
		}
		CHECK(checklumpcache());
	}

	/* start timer on cache miss to avoid system call on cache hit */
	ms = msec();

	addstat(StatLcacheMiss, 1);
	b = lumpcache.free;
	lumpcache.free = b->next;

	/*
	 * the new block has no last use, so assume it happens sometime in the middle
ZZZ this is not reasonable
	 */
	b->used = (b->used2 + lumpcache.now) / 2;

	/*
	 * rechain the block on the correct hash chain
	 */
	b->next = lumpcache.heads[h];
	lumpcache.heads[h] = b;
	if(b->next != nil)
		b->next->prev = b;
	b->prev = nil;

	scorecp(b->score, score);
	b->type = type;
	b->size = 0;
	b->data = nil;

found:
	b->ref++;
	b->used2 = b->used;
	b->used = lumpcache.now++;
	if(b->heap != TWID32)
		fixheap(b->heap, b);
	CHECK(checklumpcache());
	qunlock(&lumpcache.lock);


	addstat(StatLumpStall, 1);
	qlock(&b->lock);
	addstat(StatLumpStall, -1);

	trace(TraceLump, "lookuplump exit");
	addstat2(StatLcacheRead, 1, StatLcacheReadTime, ms ? msec()-ms : 0);
	return b;
}

void
insertlump(Lump *b, Packet *p)
{
	u32int size;

	/*
	 * look for the block in the cache
	 */
	trace(TraceLump, "insertlump enter");
	qlock(&lumpcache.lock);
	CHECK(checklumpcache());
again:

	addstat(StatLcacheWrite, 1);

	/*
	 * missed: locate the block with the oldest second to last use.
	 * remove it from the heap, and fix up the heap.
	 */
	size = packetasize(p);
	while(lumpcache.avail < size){
		trace(TraceLump, "insertlump bump");
		CHECK(checklumpcache());
		if(bumplump() == nil){
			logerr(EAdmin, "all lump cache blocks in use");
			addstat(StatLcacheStall, 1);
			CHECK(checklumpcache());
			rsleep(&lumpcache.full);
			CHECK(checklumpcache());
			addstat(StatLcacheStall, -1);
			goto again;
		}
		CHECK(checklumpcache());
	}
	b->data = p;
	b->size = size;
	lumpcache.avail -= size;
	CHECK(checklumpcache());
	qunlock(&lumpcache.lock);
	trace(TraceLump, "insertlump exit");
}

void
putlump(Lump *b)
{
	if(b == nil)
		return;

	trace(TraceLump, "putlump");
	qunlock(&b->lock);
	qlock(&lumpcache.lock);
	CHECK(checklumpcache());
	if(--b->ref == 0){
		if(b->heap == TWID32)
			upheap(lumpcache.nheap++, b);
		trace(TraceLump, "putlump wakeup");
		rwakeupall(&lumpcache.full);
	}
	CHECK(checklumpcache());
	qunlock(&lumpcache.lock);
}

/*
 * remove some lump from use and update the free list and counters
 */
static Lump*
bumplump(void)
{
	Lump *b;
	u32int h;

	/*
	 * remove blocks until we find one that is unused
	 * referenced blocks are left in the heap even though
	 * they can't be scavenged; this is simple a speed optimization
	 */
	CHECK(checklumpcache());
	for(;;){
		if(lumpcache.nheap == 0){
			trace(TraceLump, "bumplump emptyheap");
			return nil;
		}
		b = lumpcache.heap[0];
		delheap(b);
		if(!b->ref){
			trace(TraceLump, "bumplump wakeup");
			rwakeupall(&lumpcache.full);
			break;
		}
	}

	/*
	 * unchain the block
	 */
	trace(TraceLump, "bumplump unchain");
	if(b->prev == nil){
		h = hashbits(b->score, HashLog);
		if(lumpcache.heads[h] != b)
			sysfatal("bad hash chains in lump cache");
		lumpcache.heads[h] = b->next;
	}else
		b->prev->next = b->next;
	if(b->next != nil)
		b->next->prev = b->prev;

	if(b->data != nil){
		packetfree(b->data);
		b->data = nil;
		lumpcache.avail += b->size;
		b->size = 0;
	}
	b->type = TWID8;

	b->next = lumpcache.free;
	lumpcache.free = b;

	CHECK(checklumpcache());
	trace(TraceLump, "bumplump exit");
	return b;
}

void
emptylumpcache(void)
{
	qlock(&lumpcache.lock);
	while(bumplump())
		;
	qunlock(&lumpcache.lock);
}

/*
 * delete an arbitrary block from the heap
 */
static void
delheap(Lump *db)
{
	fixheap(db->heap, lumpcache.heap[--lumpcache.nheap]);
	db->heap = TWID32;
}

/*
 * push an element up or down to it's correct new location
 */
static void
fixheap(int i, Lump *b)
{
	if(upheap(i, b) == i)
		downheap(i, b);
}

static int
upheap(int i, Lump *b)
{
	Lump *bb;
	u32int now;
	int p;

	now = lumpcache.now;
	for(; i != 0; i = p){
		p = (i - 1) >> 1;
		bb = lumpcache.heap[p];
		if(b->used2 - now >= bb->used2 - now)
			break;
		lumpcache.heap[i] = bb;
		bb->heap = i;
	}

	lumpcache.heap[i] = b;
	b->heap = i;
	return i;
}

static int
downheap(int i, Lump *b)
{
	Lump *bb;
	u32int now;
	int k;

	now = lumpcache.now;
	for(; ; i = k){
		k = (i << 1) + 1;
		if(k >= lumpcache.nheap)
			break;
		if(k + 1 < lumpcache.nheap && lumpcache.heap[k]->used2 - now > lumpcache.heap[k + 1]->used2 - now)
			k++;
		bb = lumpcache.heap[k];
		if(b->used2 - now <= bb->used2 - now)
			break;
		lumpcache.heap[i] = bb;
		bb->heap = i;
	}

	lumpcache.heap[i] = b;
	b->heap = i;
	return i;
}

static void
findblock(Lump *bb)
{
	Lump *b, *last;
	int h;

	last = nil;
	h = hashbits(bb->score, HashLog);
	for(b = lumpcache.heads[h]; b != nil; b = b->next){
		if(last != b->prev)
			sysfatal("bad prev link");
		if(b == bb)
			return;
		last = b;
	}
	sysfatal("block score=%V type=%#x missing from hash table", bb->score, bb->type);
}

void
checklumpcache(void)
{
	Lump *b;
	u32int size, now, nfree;
	int i, k, refed;

	now = lumpcache.now;
	for(i = 0; i < lumpcache.nheap; i++){
		if(lumpcache.heap[i]->heap != i)
			sysfatal("lc: mis-heaped at %d: %d", i, lumpcache.heap[i]->heap);
		if(i > 0 && lumpcache.heap[(i - 1) >> 1]->used2 - now > lumpcache.heap[i]->used2 - now)
			sysfatal("lc: bad heap ordering");
		k = (i << 1) + 1;
		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
			sysfatal("lc: bad heap ordering");
		k++;
		if(k < lumpcache.nheap && lumpcache.heap[i]->used2 - now > lumpcache.heap[k]->used2 - now)
			sysfatal("lc: bad heap ordering");
	}

	refed = 0;
	size = 0;
	for(i = 0; i < lumpcache.nblocks; i++){
		b = &lumpcache.blocks[i];
		if(b->data == nil && b->size != 0)
			sysfatal("bad size: %d data=%p", b->size, b->data);
		if(b->ref && b->heap == TWID32)
			refed++;
		if(b->type != TWID8){
			findblock(b);
			size += b->size;
		}
		if(b->heap != TWID32
		&& lumpcache.heap[b->heap] != b)
			sysfatal("lc: spurious heap value");
	}
	if(lumpcache.avail != lumpcache.allowed - size){
		fprint(2, "mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
		*(int*)0=0;
	}

	nfree = 0;
	for(b = lumpcache.free; b != nil; b = b->next){
		if(b->type != TWID8 || b->heap != TWID32)
			sysfatal("lc: bad free list");
		nfree++;
	}

	if(lumpcache.nheap + nfree + refed != lumpcache.nblocks)
		sysfatal("lc: missing blocks: %d %d %d %d", lumpcache.nheap, refed, nfree, lumpcache.nblocks);
}