venti: 32-bit extensions to data structures

4 files changed, 168 insertions, 72 deletions

diff --git a/src/libventi/cache.c b/src/libventi/cache.c
index 636a6ea7..030efb0a 100644
--- a/src/libventi/cache.c
+++ b/src/libventi/cache.c
@@ -32,7 +32,6 @@ struct VtCache
 {
 	QLock	lk;
 	VtConn	*z;
-	u32int	blocksize;
 	u32int	now;		/* ticks for usage time stamps */
 	VtBlock	**hash;	/* hash table for finding addresses */
 	int		nhash;
@@ -40,41 +39,45 @@ struct VtCache
 	int		nheap;
 	VtBlock	*block;	/* all allocated blocks */
 	int		nblock;
-	uchar	*mem;	/* memory for all blocks and data */
 	int		(*write)(VtConn*, uchar[VtScoreSize], uint, uchar*, int);
+	VtBlock	*dead;	/* blocks we don't have memory for */
+	ulong	mem;
+	ulong	maxmem;
 };
 
 static void cachecheck(VtCache*);
 
 VtCache*
-vtcachealloc(VtConn *z, int blocksize, ulong nblock)
+vtcachealloc(VtConn *z, ulong maxmem)
 {
-	uchar *p;
 	VtCache *c;
 	int i;
+	int nblock;
 	VtBlock *b;
+	ulong maxmem0;
 
+	maxmem0 = maxmem;
 	c = vtmallocz(sizeof(VtCache));
-
+	nblock = maxmem/100/(sizeof(VtBlock)+2*sizeof(VtBlock*));
 	c->z = z;
-	c->blocksize = (blocksize + 127) & ~127;
 	c->nblock = nblock;
 	c->nhash = nblock;
 	c->hash = vtmallocz(nblock*sizeof(VtBlock*));
 	c->heap = vtmallocz(nblock*sizeof(VtBlock*));
 	c->block = vtmallocz(nblock*sizeof(VtBlock));
-	c->mem = vtmallocz(nblock*c->blocksize);
 	c->write = vtwrite;
+	maxmem -= nblock*(sizeof(VtBlock) + 2*sizeof(VtBlock*));
+	maxmem -= sizeof(VtCache);
+	if((long)maxmem < 0)
+		sysfatal("cache size far too small: %lud", maxmem0);
+	c->mem = maxmem;
 
-	p = c->mem;
 	for(i=0; i<nblock; i++){
 		b = &c->block[i];
 		b->addr = NilBlock;
 		b->c = c;
-		b->data = p;
 		b->heap = i;
 		c->heap[i] = b;
-		p += c->blocksize;
 	}
 	c->nheap = nblock;
 	cachecheck(c);
@@ -102,13 +105,14 @@ vtcachefree(VtCache *c)
 	qlock(&c->lk);
 
 	cachecheck(c);
-	for(i=0; i<c->nblock; i++)
+	for(i=0; i<c->nblock; i++) {
 		assert(c->block[i].ref == 0);
+		vtfree(c->block[i].data);
+	}
 
 	vtfree(c->hash);
 	vtfree(c->heap);
 	vtfree(c->block);
-	vtfree(c->mem);
 	vtfree(c);
 }
 
@@ -128,11 +132,10 @@ vtcachedump(VtCache *c)
 static void
 cachecheck(VtCache *c)
 {
-	u32int size, now;
+	u32int now;
 	int i, k, refed;
 	VtBlock *b;
 
-	size = c->blocksize;
 	now = c->now;
 
 	for(i = 0; i < c->nheap; i++){
@@ -151,8 +154,6 @@ cachecheck(VtCache *c)
 	refed = 0;
 	for(i = 0; i < c->nblock; i++){
 		b = &c->block[i];
-		if(b->data != &c->mem[i * size])
-			sysfatal("mis-blocked at %d", i);
 		if(b->ref && b->heap == BadHeap)
 			refed++;
 		else if(b->addr != NilBlock)
@@ -299,6 +300,57 @@ if(0)fprint(2, "droping %x:%V\n", b->addr, b->score);
 }
 
 /*
+ * evict blocks until there is enough memory for size bytes.
+ */
+static VtBlock*
+vtcacheevict(VtCache *c, ulong size)
+{
+	VtBlock *b;
+	
+	/*
+	 * If we were out of memory and put some blocks
+	 * to the side but now we have memory, grab one.
+	 */
+	if(c->mem >= size && c->dead) {
+		b = c->dead;
+		c->dead = b->next;
+		b->next = nil;
+		goto alloc;
+	}
+	
+	/*
+	 * Otherwise, evict until we have memory.
+	 */
+	for(;;) {
+		b = vtcachebumpblock(c);
+		if(c->mem+b->size >= size)
+			break;
+		/*
+		 * chain b onto dead list
+		 */
+		free(b->data);
+		b->data = nil;
+		c->mem += b->size;
+		b->size = 0;
+		b->next = c->dead;
+		c->dead = b;
+	}
+
+	/*
+	 * Allocate memory for block.
+	 */
+alloc:
+	if(size > b->size || size <= b->size/2) {
+		free(b->data);
+		c->mem += b->size;
+		c->mem -= size;
+		b->size = size;
+		b->data = vtmalloc(size);
+	}
+	return b;
+}
+
+/*
  * fetch a local block from the memory cache.
  * if it's not there, load it, bumping some other Block.
  * if we're out of free blocks, we're screwed.
@@ -332,16 +384,16 @@ vtcachelocal(VtCache *c, u32int addr, int type)
 }
 
 VtBlock*
-vtcacheallocblock(VtCache *c, int type)
+vtcacheallocblock(VtCache *c, int type, ulong size)
 {
 	VtBlock *b;
 
 	qlock(&c->lk);
-	b = vtcachebumpblock(c);
+	b = vtcacheevict(c, size);
 	b->iostate = BioLocal;
 	b->type = type;
 	b->addr = (b - c->block)+1;
-	vtzeroextend(type, b->data, 0, c->blocksize);
+	vtzeroextend(type, b->data, 0, size);
 	vtlocaltoglobal(b->addr, b->score);
 	qunlock(&c->lk);
 
@@ -356,7 +408,7 @@ vtcacheallocblock(VtCache *c, int type)
  * if it's not there, load it, bumping some other block.
  */
 VtBlock*
-vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
+vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type, ulong size)
 {
 	VtBlock *b;
 	ulong h;
@@ -409,7 +461,7 @@ vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
 	/*
 	 * not found
 	 */
-	b = vtcachebumpblock(c);
+	b = vtcacheevict(c, size);
 	b->addr = NilBlock;
 	b->type = type;
 	memmove(b->score, score, VtScoreSize);
@@ -435,7 +487,7 @@ vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
 	qunlock(&c->lk);
 
 	vtcachenread++;
-	n = vtread(c->z, score, type, b->data, c->blocksize);
+	n = vtread(c->z, score, type, b->data, size);
 	if(n < 0){
 		if(chattyventi)
 			fprint(2, "read %V: %r\n", score);
@@ -445,7 +497,7 @@ vtcacheglobal(VtCache *c, uchar score[VtScoreSize], int type)
 		vtblockput(b);
 		return nil;
 	}
-	vtzeroextend(type, b->data, n, c->blocksize);
+	vtzeroextend(type, b->data, n, size);
 	b->iostate = BioVenti;
 	b->nlock = 1;
 	if(vttracelevel)
@@ -534,7 +586,7 @@ vtblockwrite(VtBlock *b)
 	}
 
 	c = b->c;
-	n = vtzerotruncate(b->type, b->data, c->blocksize);
+	n = vtzerotruncate(b->type, b->data, b->size);
 	vtcachenwrite++;
 	if(c->write(c->z, score, b->type, b->data, n) < 0)
 		return -1;
@@ -554,24 +606,18 @@ vtblockwrite(VtBlock *b)
 	return 0;
 }
 
-uint
-vtcacheblocksize(VtCache *c)
-{
-	return c->blocksize;
-}
-
 VtBlock*
 vtblockcopy(VtBlock *b)
 {
 	VtBlock *bb;
 
 	vtcachencopy++;
-	bb = vtcacheallocblock(b->c, b->type);
+	bb = vtcacheallocblock(b->c, b->type, b->size);
 	if(bb == nil){
 		vtblockput(b);
 		return nil;
 	}
-	memmove(bb->data, b->data, b->c->blocksize);
+	memmove(bb->data, b->data, b->size);
 	vtblockput(b);
 	bb->pc = getcallerpc(&b);
 	return bb;
diff --git a/src/libventi/entry.c b/src/libventi/entry.c
index aeb8dada..6485714a 100644
--- a/src/libventi/entry.c
+++ b/src/libventi/entry.c
@@ -6,13 +6,37 @@
 static int
 checksize(int n)
 {
-	if(n < 256 || n > VtMaxLumpSize) {
+	if(n < 256) {
 		werrstr("bad block size %#ux", n);
 		return -1;
 	}
 	return 0;
 }
 
+// _VtEntryBig integer format is floating-point:
+// (n>>5) << (n&31).
+// Convert this number; must be exact or return -1.
+int
+vttobig(ulong n)
+{
+	int shift;
+	ulong n0;
+	
+	n0 = n;
+	shift = 0;
+	while(n >= (1<<(16 - 5))) {
+		if(n & 1)
+			return -1;
+		shift++;
+		n >>= 1;
+	}
+	
+	n = (n<<5) | shift;
+	if(((n>>5)<<(n&31)) != n0)
+		sysfatal("vttobig %#lux => %#lux failed", n0, n);
+	return n;
+}
+
 void
 vtentrypack(VtEntry *e, uchar *p, int index)
 {
@@ -20,21 +44,31 @@ vtentrypack(VtEntry *e, uchar *p, int index)
 	int flags;
 	uchar *op;
 	int depth;
+	int psize, dsize;
 
 	p += index * VtEntrySize;
 	op = p;
 
-	U32PUT(p, e->gen);
-	p += 4;
-	U16PUT(p, e->psize);
-	p += 2;
-	U16PUT(p, e->dsize);
-	p += 2;
 	depth = e->type&VtTypeDepthMask;
 	flags = (e->flags&~(_VtEntryDir|_VtEntryDepthMask));
 	flags |= depth << _VtEntryDepthShift;
 	if(e->type - depth == VtDirType)
 		flags |= _VtEntryDir;
+	U32PUT(p, e->gen);
+	p += 4;
+	psize = e->psize;
+	dsize = e->dsize;
+	if(psize >= (1<<16) || dsize >= (1<<16)) {
+		flags |= _VtEntryBig;
+		psize = vttobig(psize);
+		dsize = vttobig(dsize);
+		if(psize < 0 || dsize < 0)
+			sysfatal("invalid entry psize/dsize: %d/%d", e->psize, e->dsize);
+	}
+	U16PUT(p, psize);
+	p += 2;
+	U16PUT(p, dsize);
+	p += 2;
 	U8PUT(p, flags);
 	p++;
 	memset(p, 0, 5);
@@ -62,10 +96,14 @@ vtentryunpack(VtEntry *e, uchar *p, int index)
 	e->dsize = U16GET(p);
 	p += 2;
 	e->flags = U8GET(p);
+	p++;
+	if(e->flags & _VtEntryBig) {
+		e->psize = (e->psize>>5)<<(e->psize & 31);
+		e->dsize = (e->dsize>>5)<<(e->dsize & 31);
+	}
 	e->type = (e->flags&_VtEntryDir) ? VtDirType : VtDataType;
 	e->type += (e->flags & _VtEntryDepthMask) >> _VtEntryDepthShift;
-	e->flags &= ~(_VtEntryDir|_VtEntryDepthMask);
-	p++;
+	e->flags &= ~(_VtEntryDir|_VtEntryDepthMask|_VtEntryBig);
 	p += 5;
 	e->size = U48GET(p);
 	p += 6;
diff --git a/src/libventi/file.c b/src/libventi/file.c
index 1573a155..ebd71998 100644
--- a/src/libventi/file.c
+++ b/src/libventi/file.c
@@ -36,7 +36,6 @@ static VtFile *
 vtfilealloc(VtCache *c, VtBlock *b, VtFile *p, u32int offset, int mode)
 {
 	int epb;
-	u32int size;
 	VtEntry e;
 	VtFile *r;
 
@@ -74,15 +73,9 @@ vtfilealloc(VtCache *c, VtBlock *b, VtFile *p, u32int offset, int mode)
 		return nil;
 	}
 
-	size = vtcacheblocksize(c);
-	if(e.dsize > size || e.psize > size){
-		werrstr("block sizes %ud, %ud bigger than cache block size %ud",
-			e.psize, e.dsize, size);
-		return nil;
-	}
-
 	r = vtmallocz(sizeof(VtFile));
 	r->c = c;
+	r->bsize = b->size;
 	r->mode = mode;
 	r->dsize = e.dsize;
 	r->psize = e.psize;
@@ -126,7 +119,7 @@ vtfileopenroot(VtCache *c, VtEntry *e)
 	VtBlock *b;
 	VtFile *f;
 
-	b = vtcacheallocblock(c, VtDirType);
+	b = vtcacheallocblock(c, VtDirType, VtEntrySize);
 	if(b == nil)
 		return nil;
 
@@ -191,8 +184,6 @@ _vtfilecreate(VtFile *r, int o, int psize, int dsize, int type)
 	u32int offset;
 	
 	assert(ISLOCKED(r));
-	assert(psize <= VtMaxLumpSize);
-	assert(dsize <= VtMaxLumpSize);
 	assert(type == VtDirType || type == VtDataType);
 
 	if(!r->dir){
@@ -325,12 +316,12 @@ vtfilegetsize(VtFile *r)
 static int
 shrinksize(VtFile *r, VtEntry *e, uvlong size)
 {
-	int i, depth, type, isdir, ppb;
+	int i, depth, bsiz, type, isdir, ppb;
 	uvlong ptrsz;
 	uchar score[VtScoreSize];
 	VtBlock *b;
 
-	b = vtcacheglobal(r->c, e->score, e->type);
+	b = vtcacheglobal(r->c, e->score, e->type, r->dsize);
 	if(b == nil)
 		return -1;
 
@@ -369,7 +360,11 @@ shrinksize(VtFile *r, VtEntry *e, uvlong size)
 		type--;
 		memmove(score, b->data+i*VtScoreSize, VtScoreSize);
 		vtblockput(b);
-		b = vtcacheglobal(r->c, score, type);
+		if(type == VtDataType || type == VtDirType)
+			bsiz = r->dsize;
+		else
+			bsiz = r->psize;
+		b = vtcacheglobal(r->c, score, type, bsiz);
 		if(b == nil)
 			return -1;
 	}
@@ -498,10 +493,10 @@ vtfilesetentry(VtFile *r, VtEntry *e)
 }
 
 static VtBlock *
-blockwalk(VtBlock *p, int index, VtCache *c, int mode, VtEntry *e)
+blockwalk(VtFile *r, VtBlock *p, int index, VtCache *c, int mode, VtEntry *e)
 {
 	VtBlock *b;
-	int type;
+	int type, size;
 	uchar *score;
 	VtEntry oe;
 
@@ -519,12 +514,16 @@ blockwalk(VtBlock *p, int index, VtCache *c, int mode, VtEntry *e)
 	}
 /*print("walk from %V/%d ty %d to %V ty %d\n", p->score, index, p->type, score, type); */
 
+	if(type == VtDirType || type == VtDataType)
+		size = r->dsize;
+	else
+		size = r->psize;
 	if(mode == VtOWRITE && vtglobaltolocal(score) == NilBlock){
-		b = vtcacheallocblock(c, type);
+		b = vtcacheallocblock(c, type, size);
 		if(b)
 			goto HaveCopy;
 	}else
-		b = vtcacheglobal(c, score, type);
+		b = vtcacheglobal(c, score, type, size);
 
 	if(b == nil || mode == VtOREAD)
 		return b;
@@ -566,7 +565,7 @@ growdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 	assert(ISLOCKED(r));
 	assert(depth <= VtPointerDepth);
 
-	b = vtcacheglobal(r->c, e->score, e->type);
+	b = vtcacheglobal(r->c, e->score, e->type, r->dsize);
 	if(b == nil)
 		return -1;
 
@@ -577,7 +576,7 @@ growdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 	 * or an error occurs.
 	 */
 	while(DEPTH(e->type) < depth){
-		bb = vtcacheallocblock(r->c, e->type+1);
+		bb = vtcacheallocblock(r->c, e->type+1, r->psize);
 		if(bb == nil)
 			break;
 		memmove(bb->data, b->score, VtScoreSize);
@@ -605,7 +604,7 @@ shrinkdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 	assert(ISLOCKED(r));
 	assert(depth <= VtPointerDepth);
 
-	rb = vtcacheglobal(r->c, e->score, e->type);
+	rb = vtcacheglobal(r->c, e->score, e->type, r->psize);
 	if(rb == nil)
 		return -1;
 
@@ -618,7 +617,7 @@ shrinkdepth(VtFile *r, VtBlock *p, VtEntry *e, int depth)
 	ob = nil;
 	b = rb;
 	for(; DEPTH(e->type) > depth; e->type--){
-		nb = vtcacheglobal(r->c, b->data, e->type-1);
+		nb = vtcacheglobal(r->c, b->data, e->type-1, r->psize);
 		if(nb == nil)
 			break;
 		if(ob!=nil && ob!=rb)
@@ -720,7 +719,7 @@ assert(b->type == VtDirType);
 		m = VtORDWR;
 
 	for(i=DEPTH(e.type); i>=0; i--){
-		bb = blockwalk(b, index[i], r->c, i==0 ? mode : m, &e);
+		bb = blockwalk(r, b, index[i], r->c, i==0 ? mode : m, &e);
 		if(bb == nil)
 			goto Err;
 		vtblockput(b);
@@ -768,7 +767,7 @@ vtfileblockscore(VtFile *r, u32int bn, uchar score[VtScoreSize])
 	index[DEPTH(e.type)] = r->offset % r->epb;
 
 	for(i=DEPTH(e.type); i>=1; i--){
-		bb = blockwalk(b, index[i], r->c, VtOREAD, &e);
+		bb = blockwalk(r, b, index[i], r->c, VtOREAD, &e);
 		if(bb == nil)
 			goto Err;
 		vtblockput(b);
@@ -837,7 +836,7 @@ fileloadblock(VtFile *r, int mode)
 	case VtORDWR:
 		assert(r->mode == VtORDWR);
 		if(r->local == 1){
-			b = vtcacheglobal(r->c, r->score, VtDirType);
+			b = vtcacheglobal(r->c, r->score, VtDirType, r->bsize);
 			if(b == nil)
 				return nil;
 			b->pc = getcallerpc(&r);
@@ -861,7 +860,7 @@ fileloadblock(VtFile *r, int mode)
 		}
 		addr = vtglobaltolocal(r->score);
 		if(addr == NilBlock)
-			return vtcacheglobal(r->c, r->score, VtDirType);
+			return vtcacheglobal(r->c, r->score, VtDirType, r->bsize);
 
 		b = vtcachelocal(r->c, addr, VtDirType);
 		if(b)
@@ -1220,7 +1219,7 @@ vtfileflushbefore(VtFile *r, u64int offset)
 	 */
 	index[depth] = r->offset % r->epb;
 	for(i=depth; i>=0; i--){
-		bb = blockwalk(b, index[i], r->c, VtORDWR, &e);
+		bb = blockwalk(r, b, index[i], r->c, VtORDWR, &e);
 		if(bb == nil)
 			goto Err;
 		bi[i] = bb;
diff --git a/src/libventi/root.c b/src/libventi/root.c
index 5b4ccac6..b1a153d5 100644
--- a/src/libventi/root.c
+++ b/src/libventi/root.c
@@ -6,19 +6,30 @@
 static int
 checksize(int n)
 {
-	if(n < 256 || n > VtMaxLumpSize) {
+	if(n < 256) {
 		werrstr("bad block size");
 		return -1;
 	}
 	return 0;
 }
 
+extern int vttobig(ulong);
+
 void
 vtrootpack(VtRoot *r, uchar *p)
 {
 	uchar *op = p;
+	int vers, bsize;
 
-	U16PUT(p, VtRootVersion);
+	vers = VtRootVersion;
+	bsize = r->blocksize;
+	if(bsize >= (1<<16)) {
+		vers |= _VtRootVersionBig;
+		bsize = vttobig(bsize);
+		if(bsize < 0)
+			sysfatal("invalid root blocksize: %#x", r->blocksize);
+	}
+	U16PUT(p, vers);
 	p += 2;
 	memmove(p, r->name, sizeof(r->name));
 	p += sizeof(r->name);
@@ -26,7 +37,7 @@ vtrootpack(VtRoot *r, uchar *p)
 	p += sizeof(r->type);
 	memmove(p, r->score, VtScoreSize);
 	p +=  VtScoreSize;
-	U16PUT(p, r->blocksize);
+	U16PUT(p, bsize);
 	p += 2;
 	memmove(p, r->prev, VtScoreSize);
 	p += VtScoreSize;
@@ -42,7 +53,7 @@ vtrootunpack(VtRoot *r, uchar *p)
 	memset(r, 0, sizeof(*r));
 
 	vers = U16GET(p);
-	if(vers != VtRootVersion) {
+	if((vers&~_VtRootVersionBig) != VtRootVersion) {
 		werrstr("unknown root version");
 		return -1;
 	}
@@ -56,6 +67,8 @@ vtrootunpack(VtRoot *r, uchar *p)
 	memmove(r->score, p, VtScoreSize);
 	p +=  VtScoreSize;
 	r->blocksize = U16GET(p);
+	if(vers & _VtRootVersionBig)
+		r->blocksize = (r->blocksize >> 5) << (r->blocksize & 31);
 	if(checksize(r->blocksize) < 0)
 		return -1;
 	p += 2;