vac.c

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

#include "stdinc.h"

typedef struct MetaChunk MetaChunk;

struct MetaChunk {
	ushort offset;
	ushort size;
	ushort index;
};

static int stringUnpack(char **s, uchar **p, int *n);
static int meCmp(MetaEntry*, char *s);
static int meCmpOld(MetaEntry*, char *s);



static char EBadMeta[] = "corrupted meta data";
static char ENoFile[] = "file does not exist";

/*
 * integer conversion routines
 */
#define	U8GET(p)	((p)[0])
#define	U16GET(p)	(((p)[0]<<8)|(p)[1])
#define	U32GET(p)	(((p)[0]<<24)|((p)[1]<<16)|((p)[2]<<8)|(p)[3])
#define	U48GET(p)	(((uvlong)U16GET(p)<<32)|(uvlong)U32GET((p)+2))
#define	U64GET(p)	(((uvlong)U32GET(p)<<32)|(uvlong)U32GET((p)+4))

#define	U8PUT(p,v)	(p)[0]=(v)
#define	U16PUT(p,v)	(p)[0]=(v)>>8;(p)[1]=(v)
#define	U32PUT(p,v)	(p)[0]=(v)>>24;(p)[1]=(v)>>16;(p)[2]=(v)>>8;(p)[3]=(v)
#define	U48PUT(p,v,t32)	t32=(v)>>32;U16PUT(p,t32);t32=(v);U32PUT((p)+2,t32)
#define	U64PUT(p,v,t32)	t32=(v)>>32;U32PUT(p,t32);t32=(v);U32PUT((p)+4,t32)

static int
stringUnpack(char **s, uchar **p, int *n)
{
	int nn;

	if(*n < 2)
		return 0;

	nn = U16GET(*p);
	*p += 2;
	*n -= 2;
	if(nn > *n)
		return 0;
	*s = vtMemAlloc(nn+1);
	memmove(*s, *p, nn);
	(*s)[nn] = 0;
	*p += nn;
	*n -= nn;
	return 1;
}

static int
stringPack(char *s, uchar *p)
{
	int n;

	n = strlen(s);
	U16PUT(p, n);
	memmove(p+2, s, n);
	return n+2;
}

int
mbSearch(MetaBlock *mb, char *elem, int *ri, MetaEntry *me)
{
	int i;
	int b, t, x;
if(0)fprint(2, "mbSearch %s\n", elem);

	/* binary search within block */
	b = 0;
	t = mb->nindex;
	while(b < t){
		i = (b+t)>>1;
		meUnpack(me, mb, i);

		if(mb->botch)
			x = meCmpOld(me, elem);
		else
			x = meCmp(me, elem);

		if(x == 0){
			*ri = i;
			return 1;
		}

		if(x < 0)
			b = i+1;
		else /* x > 0 */
			t = i;
	}

	assert(b == t);

	*ri = b;	/* b is the index to insert this entry */
	memset(me, 0, sizeof(*me));

	vtSetError(ENoFile);
	return 0;
}

void
mbInit(MetaBlock *mb, uchar *p, int n, int ne)
{
	memset(p, 0, n);
	mb->maxsize = n;
	mb->maxindex = ne;
	mb->nindex = 0;
	mb->free = 0;
	mb->size = MetaHeaderSize + ne*MetaIndexSize;
	mb->buf = p;
	mb->botch = 0;
}

int
mbUnpack(MetaBlock *mb, uchar *p, int n)
{
	u32int magic;
	int i;
	int eo, en, omin;
	uchar *q;

	mb->maxsize = n;
	mb->buf = p;

	if(n == 0){
		memset(mb, 0, sizeof(MetaBlock));
		return 1;
	}

	magic = U32GET(p);
	if(magic != MetaMagic && magic != MetaMagic-1)
		goto Err;
	mb->size = U16GET(p+4);
	mb->free = U16GET(p+6);
	mb->maxindex = U16GET(p+8);
	mb->nindex = U16GET(p+10);
	mb->botch = magic != MetaMagic;
	if(mb->size > n)
		goto Err;

	omin = MetaHeaderSize + mb->maxindex*MetaIndexSize;
	if(n < omin)
		goto Err;


	p += MetaHeaderSize;

	/* check the index table - ensures that meUnpack and meCmp never fail */
	for(i=0; i<mb->nindex; i++){
		eo = U16GET(p);
		en = U16GET(p+2);
		if(eo < omin || eo+en > mb->size || en < 8)
			goto Err;
		q = mb->buf + eo;
		if(U32GET(q) != DirMagic)
			goto Err;
		p += 4;
	}

	return 1;
Err:
	vtSetError(EBadMeta);
	return 0;
}


void
mbPack(MetaBlock *mb)
{
	uchar *p;

	p = mb->buf;

	assert(!mb->botch);

	U32PUT(p, MetaMagic);
	U16PUT(p+4, mb->size);
	U16PUT(p+6, mb->free);
	U16PUT(p+8, mb->maxindex);
	U16PUT(p+10, mb->nindex);
}


void
mbDelete(MetaBlock *mb, int i)
{
	uchar *p;
	int n;
	MetaEntry me;

	assert(i < mb->nindex);
	meUnpack(&me, mb, i);
	memset(me.p, 0, me.size);

	if(me.p - mb->buf + me.size == mb->size)
		mb->size -= me.size;
	else
		mb->free += me.size;

	p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
	n = (mb->nindex-i-1)*MetaIndexSize;
	memmove(p, p+MetaIndexSize, n);
	memset(p+n, 0, MetaIndexSize);
	mb->nindex--;
}

void
mbInsert(MetaBlock *mb, int i, MetaEntry *me)
{
	uchar *p;
	int o, n;

	assert(mb->nindex < mb->maxindex);

	o = me->p - mb->buf;
	n = me->size;
	if(o+n > mb->size){
		mb->free -= mb->size - o;
		mb->size = o + n;
	}else
		mb->free -= n;

	p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
	n = (mb->nindex-i)*MetaIndexSize;
	memmove(p+MetaIndexSize, p, n);
	U16PUT(p, me->p - mb->buf);
	U16PUT(p+2, me->size);
	mb->nindex++;
}

int
mbResize(MetaBlock *mb, MetaEntry *me, int n)
{
	uchar *p, *ep;

	/* easy case */
	if(n <= me->size){
		me->size = n;
		return 1;
	}

	/* try and expand entry */

	p = me->p + me->size;
	ep = mb->buf + mb->maxsize;
	while(p < ep && *p == 0)
		p++;
	if(n <= p - me->p){
		me->size = n;
		return 1;
	}

	p = mbAlloc(mb, n);
	if(p != nil){
		me->p = p;
		me->size = n;
		return 1;
	}

	return 0;
}

void
meUnpack(MetaEntry *me, MetaBlock *mb, int i)
{
	uchar *p;
	int eo, en;

	assert(i >= 0 && i < mb->nindex);

	p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
	eo = U16GET(p);
	en = U16GET(p+2);

	me->p = mb->buf + eo;
	me->size = en;

	/* checked by mbUnpack */
	assert(me->size >= 8);
}

/* assumes a small amount of checking has been done in mbEntry */
static int
meCmp(MetaEntry *me, char *s)
{
	int n;
	uchar *p;

	p = me->p;

	/* skip magic & version */
	p += 6;
	n = U16GET(p);
	p += 2;

	if(n > me->size - 8)
		n = me->size - 8;

	while(n > 0){
		if(*s == 0)
			return 1;
		if(*p < (uchar)*s)
			return -1;
		if(*p > (uchar)*s)
			return 1;
		p++;
		s++;
		n--;
	}
	return -(*s != 0);
}

/*
 * This is the old and broken meCmp.
 * This cmp routine reverse the sense of the comparison
 * when one string is a prefix of the other.
 * In other words, it put "ab" after "abc" rather
 * than before.  This behaviour is ok; binary search
 * and sort still work.  However, it is goes against
 * the usual convention.
 */
static int
meCmpOld(MetaEntry *me, char *s)
{
	int n;
	uchar *p;

	p = me->p;

	/* skip magic & version */
	p += 6;
	n = U16GET(p);
	p += 2;

	if(n > me->size - 8)
		n = me->size - 8;

	while(n > 0){
		if(*s == 0)
			return -1;
		if(*p < (uchar)*s)
			return -1;
		if(*p > (uchar)*s)
			return 1;
		p++;
		s++;
		n--;
	}
	return *s != 0;
}

static int
offsetCmp(void *s0, void *s1)
{
	MetaChunk *mc0, *mc1;

	mc0 = s0;
	mc1 = s1;
	if(mc0->offset < mc1->offset)
		return -1;
	if(mc0->offset > mc1->offset)
		return 1;
	return 0;
}

static MetaChunk *
metaChunks(MetaBlock *mb)
{
	MetaChunk *mc;
	int oo, o, n, i;
	uchar *p;

	mc = vtMemAlloc(mb->nindex*sizeof(MetaChunk));
	p = mb->buf + MetaHeaderSize;
	for(i = 0; i<mb->nindex; i++){
		mc[i].offset = U16GET(p);
		mc[i].size = U16GET(p+2);
		mc[i].index = i;
		p += MetaIndexSize;
	}

	qsort(mc, mb->nindex, sizeof(MetaChunk), offsetCmp);

	/* check block looks ok */
	oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
	o = oo;
	n = 0;
	for(i=0; i<mb->nindex; i++){
		o = mc[i].offset;
		n = mc[i].size;
		if(o < oo)
			goto Err;
		oo += n;
	}
	if(o+n > mb->size)
		goto Err;
	if(mb->size - oo != mb->free)
		goto Err;

	return mc;
Err:
fprint(2, "metaChunks failed!\n");
oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
for(i=0; i<mb->nindex; i++){
fprint(2, "\t%d: %d %d\n", i, mc[i].offset, mc[i].offset + mc[i].size);
oo += mc[i].size;
}
fprint(2, "\tused=%d size=%d free=%d free2=%d\n", oo, mb->size, mb->free, mb->size - oo);
	vtSetError(EBadMeta);
	vtMemFree(mc);
	return nil;
}

static void
mbCompact(MetaBlock *mb, MetaChunk *mc)
{
	int oo, o, n, i;

	oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;

	for(i=0; i<mb->nindex; i++){
		o = mc[i].offset;
		n = mc[i].size;
		if(o != oo){
			memmove(mb->buf + oo, mb->buf + o, n);
			U16PUT(mb->buf + MetaHeaderSize + mc[i].index*MetaIndexSize, oo);
		}
		oo += n;
	}

	mb->size = oo;
	mb->free = 0;
}

uchar *
mbAlloc(MetaBlock *mb, int n)
{
	int i, o;
	MetaChunk *mc;

	/* off the end */
	if(mb->maxsize - mb->size >= n)
		return mb->buf + mb->size;

	/* check if possible */
	if(mb->maxsize - mb->size + mb->free < n)
		return nil;

	mc = metaChunks(mb);
	if(mc == nil){
fprint(2, "mbAlloc: metaChunks failed: %r\n");
		return nil;
	}

	/* look for hole */
	o = MetaHeaderSize + mb->maxindex*MetaIndexSize;
	for(i=0; i<mb->nindex; i++){
		if(mc[i].offset - o >= n){
			vtMemFree(mc);
			return mb->buf + o;
		}
		o = mc[i].offset + mc[i].size;
	}

	if(mb->maxsize - o >= n){
		vtMemFree(mc);
		return mb->buf + o;
	}

	/* compact and return off the end */
	mbCompact(mb, mc);
	vtMemFree(mc);

	if(mb->maxsize - mb->size < n){
		vtSetError(EBadMeta);
		return nil;
	}
	return mb->buf + mb->size;
}

int
deSize(DirEntry *dir)
{
	int n;

	/* constant part */

	n = 	4 +	/* magic */
		2 + 	/* version */
		4 +	/* entry */
		4 + 	/* guid */
		4 + 	/* mentry */
		4 + 	/* mgen */
		8 +	/* qid */
		4 + 	/* mtime */
		4 + 	/* mcount */
		4 + 	/* ctime */
		4 + 	/* atime */
		4 +	/* mode */
		0;

	/* strings */
	n += 2 + strlen(dir->elem);
	n += 2 + strlen(dir->uid);
	n += 2 + strlen(dir->gid);
	n += 2 + strlen(dir->mid);

	/* optional sections */
	if(dir->qidSpace){
		n += 	3 + 	/* option header */
			8 + 	/* qidOffset */
			8;	/* qid Max */
	}

	return n;
}

void
dePack(DirEntry *dir, MetaEntry *me)
{
	uchar *p;
	ulong t32;

	p = me->p;

	U32PUT(p, DirMagic);
	U16PUT(p+4, 9);		/* version */
	p += 6;

	p += stringPack(dir->elem, p);

	U32PUT(p, dir->entry);
	U32PUT(p+4, dir->gen);
	U32PUT(p+8, dir->mentry);
	U32PUT(p+12, dir->mgen);
	U64PUT(p+16, dir->qid, t32);
	p += 24;

	p += stringPack(dir->uid, p);
	p += stringPack(dir->gid, p);
	p += stringPack(dir->mid, p);

	U32PUT(p, dir->mtime);
	U32PUT(p+4, dir->mcount);
	U32PUT(p+8, dir->ctime);
	U32PUT(p+12, dir->atime);
	U32PUT(p+16, dir->mode);
	p += 5*4;

	if(dir->qidSpace){
		U8PUT(p, DeQidSpace);
		U16PUT(p+1, 2*8);
		p += 3;
		U64PUT(p, dir->qidOffset, t32);
		U64PUT(p+8, dir->qidMax, t32);
		p += 16;
	}

	assert(p == me->p + me->size);
}


int
deUnpack(DirEntry *dir, MetaEntry *me)
{
	int t, nn, n, version;
	uchar *p;

	p = me->p;
	n = me->size;

	memset(dir, 0, sizeof(DirEntry));

if(0)print("deUnpack\n");
	/* magic */
	if(n < 4 || U32GET(p) != DirMagic)
		goto Err;
	p += 4;
	n -= 4;

if(0)print("deUnpack: got magic\n");
	/* version */
	if(n < 2)
		goto Err;
	version = U16GET(p);
	if(version < 7 || version > 9)
		goto Err;
	p += 2;
	n -= 2;

if(0)print("deUnpack: got version\n");

	/* elem */
	if(!stringUnpack(&dir->elem, &p, &n))
		goto Err;

if(0)print("deUnpack: got elem\n");

	/* entry  */
	if(n < 4)
		goto Err;
	dir->entry = U32GET(p);
	p += 4;
	n -= 4;

if(0)print("deUnpack: got entry\n");

	if(version < 9){
		dir->gen = 0;
		dir->mentry = dir->entry+1;
		dir->mgen = 0;
	}else{
		if(n < 3*4)
			goto Err;
		dir->gen = U32GET(p);
		dir->mentry = U32GET(p+4);
		dir->mgen = U32GET(p+8);
		p += 3*4;
		n -= 3*4;
	}

if(0)print("deUnpack: got gen etc\n");

	/* size is gotten from VtEntry */
	dir->size = 0;

	/* qid */
	if(n < 8)
		goto Err;
	dir->qid = U64GET(p);
	p += 8;
	n -= 8;

if(0)print("deUnpack: got qid\n");
	/* skip replacement */
	if(version == 7){
		if(n < VtScoreSize)
			goto Err;
		p += VtScoreSize;
		n -= VtScoreSize;
	}

	/* uid */
	if(!stringUnpack(&dir->uid, &p, &n))
		goto Err;

	/* gid */
	if(!stringUnpack(&dir->gid, &p, &n))
		goto Err;

	/* mid */
	if(!stringUnpack(&dir->mid, &p, &n))
		goto Err;

if(0)print("deUnpack: got ids\n");
	if(n < 5*4)
		goto Err;
	dir->mtime = U32GET(p);
	dir->mcount = U32GET(p+4);
	dir->ctime = U32GET(p+8);
	dir->atime = U32GET(p+12);
	dir->mode = U32GET(p+16);
	p += 5*4;
	n -= 5*4;

if(0)print("deUnpack: got times\n");
	/* optional meta data */
	while(n > 0){
		if(n < 3)
			goto Err;
		t = p[0];
		nn = U16GET(p+1);
		p += 3;
		n -= 3;
		if(n < nn)
			goto Err;
		switch(t){
		case DePlan9:
			/* not valid in version >= 9 */
			if(version >= 9)
				break;
			if(dir->plan9 || nn != 12)
				goto Err;
			dir->plan9 = 1;
			dir->p9path = U64GET(p);
			dir->p9version = U32GET(p+8);
			if(dir->mcount == 0)
				dir->mcount = dir->p9version;
			break;
		case DeGen:
			/* not valid in version >= 9 */
			if(version >= 9)
				break;
			break;
		case DeQidSpace:
			if(dir->qidSpace || nn != 16)
				goto Err;
			dir->qidSpace = 1;
			dir->qidOffset = U64GET(p);
			dir->qidMax = U64GET(p+8);
			break;
		}
		p += nn;
		n -= nn;
	}
if(0)print("deUnpack: got options\n");

	if(p != me->p + me->size)
		goto Err;

if(0)print("deUnpack: correct size\n");
	return 1;
Err:
if(0)print("deUnpack: XXXXXXXXXXXX EBadMeta\n");
	vtSetError(EBadMeta);
	deCleanup(dir);
	return 0;
}

void
deCleanup(DirEntry *dir)
{
	vtMemFree(dir->elem);
	dir->elem = nil;
	vtMemFree(dir->uid);
	dir->uid = nil;
	vtMemFree(dir->gid);
	dir->gid = nil;
	vtMemFree(dir->mid);
	dir->mid = nil;
}

void
deCopy(DirEntry *dst, DirEntry *src)
{
	*dst = *src;
	dst->elem = vtStrDup(src->elem);
	dst->uid = vtStrDup(src->uid);
	dst->gid = vtStrDup(src->gid);
	dst->mid = vtStrDup(src->mid);
}