Subversion Repositories planix.SVN

#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);

}