From 7a4ee46d253e291044bba2d0c54b818b67ac013c Mon Sep 17 00:00:00 2001
From: rsc <devnull@localhost>
Date: Sun, 23 Nov 2003 17:54:58 +0000
Subject: Initial stab at Venti.

---
 src/cmd/venti/lumpcache.c | 380 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 380 insertions(+)
 create mode 100644 src/cmd/venti/lumpcache.c

(limited to 'src/cmd/venti/lumpcache.c')

diff --git a/src/cmd/venti/lumpcache.c b/src/cmd/venti/lumpcache.c
new file mode 100644
index 00000000..979271af
--- /dev/null
+++ b/src/cmd/venti/lumpcache.c
@@ -0,0 +1,380 @@
+#include "stdinc.h"
+#include "dat.h"
+#include "fns.h"
+
+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);
+
+	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)
+{
+	Lump *b;
+	u32int h;
+
+	h = hashbits(score, HashLog);
+
+	/*
+	 * look for the block in the cache
+	 */
+//checklumpcache();
+	qlock(&lumpcache.lock);
+again:
+	for(b = lumpcache.heads[h]; b != nil; b = b->next){
+		if(scorecmp(score, b->score)==0 && type == b->type){
+			qlock(&stats.lock);
+			stats.lumphit++;
+			qunlock(&stats.lock);
+			goto found;
+		}
+	}
+
+	/*
+	 * 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){
+		if(bumplump() == nil){
+			logerr(EAdmin, "all lump cache blocks in use");
+			rsleep(&lumpcache.full);
+			goto again;
+		}
+	}
+	qlock(&stats.lock);
+	stats.lumpmiss++;
+	qunlock(&stats.lock);
+
+	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);
+	qunlock(&lumpcache.lock);
+
+//checklumpcache();
+
+	qlock(&b->lock);
+
+	return b;
+}
+
+void
+insertlump(Lump *b, Packet *p)
+{
+	u32int size;
+
+	/*
+	 * look for the block in the cache
+	 */
+//checklumpcache();
+	qlock(&lumpcache.lock);
+again:
+
+	/*
+	 * missed: locate the block with the oldest second to last use.
+	 * remove it from the heap, and fix up the heap.
+	 */
+	size = packetasize(p);
+//ZZZ
+	while(lumpcache.avail < size){
+		if(bumplump() == nil){
+			logerr(EAdmin, "all lump cache blocks in use");
+			rsleep(&lumpcache.full);
+			goto again;
+		}
+	}
+	b->data = p;
+	b->size = size;
+	lumpcache.avail -= size;
+
+	qunlock(&lumpcache.lock);
+//checklumpcache();
+}
+
+void
+putlump(Lump *b)
+{
+	if(b == nil)
+		return;
+
+	qunlock(&b->lock);
+//checklumpcache();
+	qlock(&lumpcache.lock);
+	if(--b->ref == 0){
+		if(b->heap == TWID32)
+			upheap(lumpcache.nheap++, b);
+		rwakeup(&lumpcache.full);
+	}
+
+	qunlock(&lumpcache.lock);
+//checklumpcache();
+}
+
+/*
+ * 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
+	 */
+	for(;;){
+		if(lumpcache.nheap == 0)
+			return nil;
+		b = lumpcache.heap[0];
+		delheap(b);
+		if(!b->ref){
+			rwakeup(&lumpcache.full);
+			break;
+		}
+	}
+
+	/*
+	 * unchain the block
+	 */
+	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;
+
+	return b;
+}
+
+/*
+ * 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;
+
+	qlock(&lumpcache.lock);
+	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)
+		sysfatal("mismatched available=%d and allowed=%d - used=%d space", lumpcache.avail, lumpcache.allowed, size);
+
+	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);
+	qunlock(&lumpcache.lock);
+}
-- 
cgit v1.2.3