plan9port

fork of plan9port with libvec, libstr and libsdb
Log | Files | Refs | README | LICENSE

vac.c (12502B)

      1 #include "stdinc.h"
      2 
      3 typedef struct MetaChunk MetaChunk;
      4 
      5 struct MetaChunk {
      6 	ushort offset;
      7 	ushort size;
      8 	ushort index;
      9 };
     10 
     11 static int stringUnpack(char **s, uchar **p, int *n);
     12 static int meCmp(MetaEntry*, char *s);
     13 static int meCmpOld(MetaEntry*, char *s);
     14 
     15 
     16 
     17 static char EBadMeta[] = "corrupted meta data";
     18 static char ENoFile[] = "file does not exist";
     19 
     20 /*
     21  * integer conversion routines
     22  */
     23 #define	U8GET(p)	((p)[0])
     24 #define	U16GET(p)	(((p)[0]<<8)|(p)[1])
     25 #define	U32GET(p)	(((p)[0]<<24)|((p)[1]<<16)|((p)[2]<<8)|(p)[3])
     26 #define	U48GET(p)	(((uvlong)U16GET(p)<<32)|(uvlong)U32GET((p)+2))
     27 #define	U64GET(p)	(((uvlong)U32GET(p)<<32)|(uvlong)U32GET((p)+4))
     28 
     29 #define	U8PUT(p,v)	(p)[0]=(v)
     30 #define	U16PUT(p,v)	(p)[0]=(v)>>8;(p)[1]=(v)
     31 #define	U32PUT(p,v)	(p)[0]=((v)>>24)&0xFF;(p)[1]=((v)>>16)&0xFF;(p)[2]=((v)>>8)&0xFF;(p)[3]=(v)&0xFF
     32 #define	U48PUT(p,v,t32)	t32=(v)>>32;U16PUT(p,t32);t32=(v);U32PUT((p)+2,t32)
     33 #define	U64PUT(p,v,t32)	t32=(v)>>32;U32PUT(p,t32);t32=(v);U32PUT((p)+4,t32)
     34 
     35 static int
     36 stringUnpack(char **s, uchar **p, int *n)
     37 {
     38 	int nn;
     39 
     40 	if(*n < 2)
     41 		return 0;
     42 
     43 	nn = U16GET(*p);
     44 	*p += 2;
     45 	*n -= 2;
     46 	if(nn > *n)
     47 		return 0;
     48 	*s = vtmalloc(nn+1);
     49 	memmove(*s, *p, nn);
     50 	(*s)[nn] = 0;
     51 	*p += nn;
     52 	*n -= nn;
     53 	return 1;
     54 }
     55 
     56 static int
     57 stringPack(char *s, uchar *p)
     58 {
     59 	int n;
     60 
     61 	n = strlen(s);
     62 	U16PUT(p, n);
     63 	memmove(p+2, s, n);
     64 	return n+2;
     65 }
     66 
     67 int
     68 mbSearch(MetaBlock *mb, char *elem, int *ri, MetaEntry *me)
     69 {
     70 	int i;
     71 	int b, t, x;
     72 if(0)fprint(2, "mbSearch %s\n", elem);
     73 
     74 	/* binary search within block */
     75 	b = 0;
     76 	t = mb->nindex;
     77 	while(b < t){
     78 		i = (b+t)>>1;
     79 		meUnpack(me, mb, i);
     80 
     81 		if(mb->botch)
     82 			x = meCmpOld(me, elem);
     83 		else
     84 			x = meCmp(me, elem);
     85 
     86 		if(x == 0){
     87 			*ri = i;
     88 			return 1;
     89 		}
     90 
     91 		if(x < 0)
     92 			b = i+1;
     93 		else /* x > 0 */
     94 			t = i;
     95 	}
     96 
     97 	assert(b == t);
     98 
     99 	*ri = b;	/* b is the index to insert this entry */
    100 	memset(me, 0, sizeof(*me));
    101 
    102 	werrstr(ENoFile);
    103 	return 0;
    104 }
    105 
    106 void
    107 mbInit(MetaBlock *mb, uchar *p, int n, int ne)
    108 {
    109 	memset(p, 0, n);
    110 	mb->maxsize = n;
    111 	mb->maxindex = ne;
    112 	mb->nindex = 0;
    113 	mb->free = 0;
    114 	mb->size = MetaHeaderSize + ne*MetaIndexSize;
    115 	mb->buf = p;
    116 	mb->botch = 0;
    117 }
    118 
    119 int
    120 mbUnpack(MetaBlock *mb, uchar *p, int n)
    121 {
    122 	u32int magic;
    123 	int i;
    124 	int eo, en, omin;
    125 	uchar *q;
    126 
    127 	mb->maxsize = n;
    128 	mb->buf = p;
    129 
    130 	if(n == 0){
    131 		memset(mb, 0, sizeof(MetaBlock));
    132 		return 1;
    133 	}
    134 
    135 	magic = U32GET(p);
    136 	if(magic != MetaMagic && magic != MetaMagic-1)
    137 		goto Err;
    138 	mb->size = U16GET(p+4);
    139 	mb->free = U16GET(p+6);
    140 	mb->maxindex = U16GET(p+8);
    141 	mb->nindex = U16GET(p+10);
    142 	mb->botch = magic != MetaMagic;
    143 	if(mb->size > n)
    144 		goto Err;
    145 
    146 	omin = MetaHeaderSize + mb->maxindex*MetaIndexSize;
    147 	if(n < omin)
    148 		goto Err;
    149 
    150 
    151 	p += MetaHeaderSize;
    152 
    153 	/* check the index table - ensures that meUnpack and meCmp never fail */
    154 	for(i=0; i<mb->nindex; i++){
    155 		eo = U16GET(p);
    156 		en = U16GET(p+2);
    157 		if(eo < omin || eo+en > mb->size || en < 8)
    158 			goto Err;
    159 		q = mb->buf + eo;
    160 		if(U32GET(q) != DirMagic)
    161 			goto Err;
    162 		p += 4;
    163 	}
    164 
    165 	return 1;
    166 Err:
    167 	werrstr(EBadMeta);
    168 	return 0;
    169 }
    170 
    171 
    172 void
    173 mbPack(MetaBlock *mb)
    174 {
    175 	uchar *p;
    176 
    177 	p = mb->buf;
    178 
    179 	assert(!mb->botch);
    180 
    181 	U32PUT(p, MetaMagic);
    182 	U16PUT(p+4, mb->size);
    183 	U16PUT(p+6, mb->free);
    184 	U16PUT(p+8, mb->maxindex);
    185 	U16PUT(p+10, mb->nindex);
    186 }
    187 
    188 
    189 void
    190 mbDelete(MetaBlock *mb, int i)
    191 {
    192 	uchar *p;
    193 	int n;
    194 	MetaEntry me;
    195 
    196 	assert(i < mb->nindex);
    197 	meUnpack(&me, mb, i);
    198 	memset(me.p, 0, me.size);
    199 
    200 	if(me.p - mb->buf + me.size == mb->size)
    201 		mb->size -= me.size;
    202 	else
    203 		mb->free += me.size;
    204 
    205 	p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
    206 	n = (mb->nindex-i-1)*MetaIndexSize;
    207 	memmove(p, p+MetaIndexSize, n);
    208 	memset(p+n, 0, MetaIndexSize);
    209 	mb->nindex--;
    210 }
    211 
    212 void
    213 mbInsert(MetaBlock *mb, int i, MetaEntry *me)
    214 {
    215 	uchar *p;
    216 	int o, n;
    217 
    218 	assert(mb->nindex < mb->maxindex);
    219 
    220 	o = me->p - mb->buf;
    221 	n = me->size;
    222 	if(o+n > mb->size){
    223 		mb->free -= mb->size - o;
    224 		mb->size = o + n;
    225 	}else
    226 		mb->free -= n;
    227 
    228 	p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
    229 	n = (mb->nindex-i)*MetaIndexSize;
    230 	memmove(p+MetaIndexSize, p, n);
    231 	U16PUT(p, me->p - mb->buf);
    232 	U16PUT(p+2, me->size);
    233 	mb->nindex++;
    234 }
    235 
    236 int
    237 mbResize(MetaBlock *mb, MetaEntry *me, int n)
    238 {
    239 	uchar *p, *ep;
    240 
    241 	/* easy case */
    242 	if(n <= me->size){
    243 		me->size = n;
    244 		return 1;
    245 	}
    246 
    247 	/* try and expand entry */
    248 
    249 	p = me->p + me->size;
    250 	ep = mb->buf + mb->maxsize;
    251 	while(p < ep && *p == 0)
    252 		p++;
    253 	if(n <= p - me->p){
    254 		me->size = n;
    255 		return 1;
    256 	}
    257 
    258 	p = mbAlloc(mb, n);
    259 	if(p != nil){
    260 		me->p = p;
    261 		me->size = n;
    262 		return 1;
    263 	}
    264 
    265 	return 0;
    266 }
    267 
    268 void
    269 meUnpack(MetaEntry *me, MetaBlock *mb, int i)
    270 {
    271 	uchar *p;
    272 	int eo, en;
    273 
    274 	assert(i >= 0 && i < mb->nindex);
    275 
    276 	p = mb->buf + MetaHeaderSize + i*MetaIndexSize;
    277 	eo = U16GET(p);
    278 	en = U16GET(p+2);
    279 
    280 	me->p = mb->buf + eo;
    281 	me->size = en;
    282 
    283 	/* checked by mbUnpack */
    284 	assert(me->size >= 8);
    285 }
    286 
    287 /* assumes a small amount of checking has been done in mbEntry */
    288 static int
    289 meCmp(MetaEntry *me, char *s)
    290 {
    291 	int n;
    292 	uchar *p;
    293 
    294 	p = me->p;
    295 
    296 	/* skip magic & version */
    297 	p += 6;
    298 	n = U16GET(p);
    299 	p += 2;
    300 
    301 	if(n > me->size - 8)
    302 		n = me->size - 8;
    303 
    304 	while(n > 0){
    305 		if(*s == 0)
    306 			return 1;
    307 		if(*p < (uchar)*s)
    308 			return -1;
    309 		if(*p > (uchar)*s)
    310 			return 1;
    311 		p++;
    312 		s++;
    313 		n--;
    314 	}
    315 	return -(*s != 0);
    316 }
    317 
    318 /*
    319  * This is the old and broken meCmp.
    320  * This cmp routine reverse the sense of the comparison
    321  * when one string is a prefix of the other.
    322  * In other words, it put "ab" after "abc" rather
    323  * than before.  This behaviour is ok; binary search
    324  * and sort still work.  However, it is goes against
    325  * the usual convention.
    326  */
    327 static int
    328 meCmpOld(MetaEntry *me, char *s)
    329 {
    330 	int n;
    331 	uchar *p;
    332 
    333 	p = me->p;
    334 
    335 	/* skip magic & version */
    336 	p += 6;
    337 	n = U16GET(p);
    338 	p += 2;
    339 
    340 	if(n > me->size - 8)
    341 		n = me->size - 8;
    342 
    343 	while(n > 0){
    344 		if(*s == 0)
    345 			return -1;
    346 		if(*p < (uchar)*s)
    347 			return -1;
    348 		if(*p > (uchar)*s)
    349 			return 1;
    350 		p++;
    351 		s++;
    352 		n--;
    353 	}
    354 	return *s != 0;
    355 }
    356 
    357 static int
    358 offsetCmp(const void *s0, const void *s1)
    359 {
    360 	MetaChunk *mc0, *mc1;
    361 
    362 	mc0 = (MetaChunk*)s0;
    363 	mc1 = (MetaChunk*)s1;
    364 	if(mc0->offset < mc1->offset)
    365 		return -1;
    366 	if(mc0->offset > mc1->offset)
    367 		return 1;
    368 	return 0;
    369 }
    370 
    371 static MetaChunk *
    372 metaChunks(MetaBlock *mb)
    373 {
    374 	MetaChunk *mc;
    375 	int oo, o, n, i;
    376 	uchar *p;
    377 
    378 	mc = vtmalloc(mb->nindex*sizeof(MetaChunk));
    379 	p = mb->buf + MetaHeaderSize;
    380 	for(i = 0; i<mb->nindex; i++){
    381 		mc[i].offset = U16GET(p);
    382 		mc[i].size = U16GET(p+2);
    383 		mc[i].index = i;
    384 		p += MetaIndexSize;
    385 	}
    386 
    387 	qsort(mc, mb->nindex, sizeof(MetaChunk), offsetCmp);
    388 
    389 	/* check block looks ok */
    390 	oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
    391 	o = oo;
    392 	n = 0;
    393 	for(i=0; i<mb->nindex; i++){
    394 		o = mc[i].offset;
    395 		n = mc[i].size;
    396 		if(o < oo)
    397 			goto Err;
    398 		oo += n;
    399 	}
    400 	if(o+n > mb->size)
    401 		goto Err;
    402 	if(mb->size - oo != mb->free)
    403 		goto Err;
    404 
    405 	return mc;
    406 Err:
    407 fprint(2, "metaChunks failed!\n");
    408 oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
    409 for(i=0; i<mb->nindex; i++){
    410 fprint(2, "\t%d: %d %d\n", i, mc[i].offset, mc[i].offset + mc[i].size);
    411 oo += mc[i].size;
    412 }
    413 fprint(2, "\tused=%d size=%d free=%d free2=%d\n", oo, mb->size, mb->free, mb->size - oo);
    414 	werrstr(EBadMeta);
    415 	vtfree(mc);
    416 	return nil;
    417 }
    418 
    419 static void
    420 mbCompact(MetaBlock *mb, MetaChunk *mc)
    421 {
    422 	int oo, o, n, i;
    423 
    424 	oo = MetaHeaderSize + mb->maxindex*MetaIndexSize;
    425 
    426 	for(i=0; i<mb->nindex; i++){
    427 		o = mc[i].offset;
    428 		n = mc[i].size;
    429 		if(o != oo){
    430 			memmove(mb->buf + oo, mb->buf + o, n);
    431 			U16PUT(mb->buf + MetaHeaderSize + mc[i].index*MetaIndexSize, oo);
    432 		}
    433 		oo += n;
    434 	}
    435 
    436 	mb->size = oo;
    437 	mb->free = 0;
    438 }
    439 
    440 uchar *
    441 mbAlloc(MetaBlock *mb, int n)
    442 {
    443 	int i, o;
    444 	MetaChunk *mc;
    445 
    446 	/* off the end */
    447 	if(mb->maxsize - mb->size >= n)
    448 		return mb->buf + mb->size;
    449 
    450 	/* check if possible */
    451 	if(mb->maxsize - mb->size + mb->free < n)
    452 		return nil;
    453 
    454 	mc = metaChunks(mb);
    455 	if(mc == nil){
    456 fprint(2, "mbAlloc: metaChunks failed: %r\n");
    457 		return nil;
    458 	}
    459 
    460 	/* look for hole */
    461 	o = MetaHeaderSize + mb->maxindex*MetaIndexSize;
    462 	for(i=0; i<mb->nindex; i++){
    463 		if(mc[i].offset - o >= n){
    464 			vtfree(mc);
    465 			return mb->buf + o;
    466 		}
    467 		o = mc[i].offset + mc[i].size;
    468 	}
    469 
    470 	if(mb->maxsize - o >= n){
    471 		vtfree(mc);
    472 		return mb->buf + o;
    473 	}
    474 
    475 	/* compact and return off the end */
    476 	mbCompact(mb, mc);
    477 	vtfree(mc);
    478 
    479 	if(mb->maxsize - mb->size < n){
    480 		werrstr(EBadMeta);
    481 		return nil;
    482 	}
    483 	return mb->buf + mb->size;
    484 }
    485 
    486 int
    487 deSize(DirEntry *dir)
    488 {
    489 	int n;
    490 
    491 	/* constant part */
    492 
    493 	n = 	4 +	/* magic */
    494 		2 + 	/* version */
    495 		4 +	/* entry */
    496 		4 + 	/* guid */
    497 		4 + 	/* mentry */
    498 		4 + 	/* mgen */
    499 		8 +	/* qid */
    500 		4 + 	/* mtime */
    501 		4 + 	/* mcount */
    502 		4 + 	/* ctime */
    503 		4 + 	/* atime */
    504 		4 +	/* mode */
    505 		0;
    506 
    507 	/* strings */
    508 	n += 2 + strlen(dir->elem);
    509 	n += 2 + strlen(dir->uid);
    510 	n += 2 + strlen(dir->gid);
    511 	n += 2 + strlen(dir->mid);
    512 
    513 	/* optional sections */
    514 	if(dir->qidSpace){
    515 		n += 	3 + 	/* option header */
    516 			8 + 	/* qidOffset */
    517 			8;	/* qid Max */
    518 	}
    519 
    520 	return n;
    521 }
    522 
    523 void
    524 dePack(DirEntry *dir, MetaEntry *me)
    525 {
    526 	uchar *p;
    527 	ulong t32;
    528 
    529 	p = me->p;
    530 
    531 	U32PUT(p, DirMagic);
    532 	U16PUT(p+4, 9);		/* version */
    533 	p += 6;
    534 
    535 	p += stringPack(dir->elem, p);
    536 
    537 	U32PUT(p, dir->entry);
    538 	U32PUT(p+4, dir->gen);
    539 	U32PUT(p+8, dir->mentry);
    540 	U32PUT(p+12, dir->mgen);
    541 	U64PUT(p+16, dir->qid, t32);
    542 	p += 24;
    543 
    544 	p += stringPack(dir->uid, p);
    545 	p += stringPack(dir->gid, p);
    546 	p += stringPack(dir->mid, p);
    547 
    548 	U32PUT(p, dir->mtime);
    549 	U32PUT(p+4, dir->mcount);
    550 	U32PUT(p+8, dir->ctime);
    551 	U32PUT(p+12, dir->atime);
    552 	U32PUT(p+16, dir->mode);
    553 	p += 5*4;
    554 
    555 	if(dir->qidSpace){
    556 		U8PUT(p, DeQidSpace);
    557 		U16PUT(p+1, 2*8);
    558 		p += 3;
    559 		U64PUT(p, dir->qidOffset, t32);
    560 		U64PUT(p+8, dir->qidMax, t32);
    561 		p += 16;
    562 	}
    563 
    564 	assert(p == me->p + me->size);
    565 }
    566 
    567 
    568 int
    569 deUnpack(DirEntry *dir, MetaEntry *me)
    570 {
    571 	int t, nn, n, version;
    572 	uchar *p;
    573 
    574 	p = me->p;
    575 	n = me->size;
    576 
    577 	memset(dir, 0, sizeof(DirEntry));
    578 
    579 if(0)print("deUnpack\n");
    580 	/* magic */
    581 	if(n < 4 || U32GET(p) != DirMagic)
    582 		goto Err;
    583 	p += 4;
    584 	n -= 4;
    585 
    586 if(0)print("deUnpack: got magic\n");
    587 	/* version */
    588 	if(n < 2)
    589 		goto Err;
    590 	version = U16GET(p);
    591 	if(version < 7 || version > 9)
    592 		goto Err;
    593 	p += 2;
    594 	n -= 2;
    595 
    596 if(0)print("deUnpack: got version\n");
    597 
    598 	/* elem */
    599 	if(!stringUnpack(&dir->elem, &p, &n))
    600 		goto Err;
    601 
    602 if(0)print("deUnpack: got elem\n");
    603 
    604 	/* entry  */
    605 	if(n < 4)
    606 		goto Err;
    607 	dir->entry = U32GET(p);
    608 	p += 4;
    609 	n -= 4;
    610 
    611 if(0)print("deUnpack: got entry\n");
    612 
    613 	if(version < 9){
    614 		dir->gen = 0;
    615 		dir->mentry = dir->entry+1;
    616 		dir->mgen = 0;
    617 	}else{
    618 		if(n < 3*4)
    619 			goto Err;
    620 		dir->gen = U32GET(p);
    621 		dir->mentry = U32GET(p+4);
    622 		dir->mgen = U32GET(p+8);
    623 		p += 3*4;
    624 		n -= 3*4;
    625 	}
    626 
    627 if(0)print("deUnpack: got gen etc\n");
    628 
    629 	/* size is gotten from VtEntry */
    630 	dir->size = 0;
    631 
    632 	/* qid */
    633 	if(n < 8)
    634 		goto Err;
    635 	dir->qid = U64GET(p);
    636 	p += 8;
    637 	n -= 8;
    638 
    639 if(0)print("deUnpack: got qid\n");
    640 	/* skip replacement */
    641 	if(version == 7){
    642 		if(n < VtScoreSize)
    643 			goto Err;
    644 		p += VtScoreSize;
    645 		n -= VtScoreSize;
    646 	}
    647 
    648 	/* uid */
    649 	if(!stringUnpack(&dir->uid, &p, &n))
    650 		goto Err;
    651 
    652 	/* gid */
    653 	if(!stringUnpack(&dir->gid, &p, &n))
    654 		goto Err;
    655 
    656 	/* mid */
    657 	if(!stringUnpack(&dir->mid, &p, &n))
    658 		goto Err;
    659 
    660 if(0)print("deUnpack: got ids\n");
    661 	if(n < 5*4)
    662 		goto Err;
    663 	dir->mtime = U32GET(p);
    664 	dir->mcount = U32GET(p+4);
    665 	dir->ctime = U32GET(p+8);
    666 	dir->atime = U32GET(p+12);
    667 	dir->mode = U32GET(p+16);
    668 	p += 5*4;
    669 	n -= 5*4;
    670 
    671 if(0)print("deUnpack: got times\n");
    672 	/* optional meta data */
    673 	while(n > 0){
    674 		if(n < 3)
    675 			goto Err;
    676 		t = p[0];
    677 		nn = U16GET(p+1);
    678 		p += 3;
    679 		n -= 3;
    680 		if(n < nn)
    681 			goto Err;
    682 		switch(t){
    683 		case DePlan9:
    684 			/* not valid in version >= 9 */
    685 			if(version >= 9)
    686 				break;
    687 			if(dir->plan9 || nn != 12)
    688 				goto Err;
    689 			dir->plan9 = 1;
    690 			dir->p9path = U64GET(p);
    691 			dir->p9version = U32GET(p+8);
    692 			if(dir->mcount == 0)
    693 				dir->mcount = dir->p9version;
    694 			break;
    695 		case DeGen:
    696 			/* not valid in version >= 9 */
    697 			if(version >= 9)
    698 				break;
    699 			break;
    700 		case DeQidSpace:
    701 			if(dir->qidSpace || nn != 16)
    702 				goto Err;
    703 			dir->qidSpace = 1;
    704 			dir->qidOffset = U64GET(p);
    705 			dir->qidMax = U64GET(p+8);
    706 			break;
    707 		}
    708 		p += nn;
    709 		n -= nn;
    710 	}
    711 if(0)print("deUnpack: got options\n");
    712 
    713 	if(p != me->p + me->size)
    714 		goto Err;
    715 
    716 if(0)print("deUnpack: correct size\n");
    717 	return 1;
    718 Err:
    719 if(0)print("deUnpack: XXXXXXXXXXXX EBadMeta\n");
    720 	werrstr(EBadMeta);
    721 	deCleanup(dir);
    722 	return 0;
    723 }
    724 
    725 void
    726 deCleanup(DirEntry *dir)
    727 {
    728 	vtfree(dir->elem);
    729 	dir->elem = nil;
    730 	vtfree(dir->uid);
    731 	dir->uid = nil;
    732 	vtfree(dir->gid);
    733 	dir->gid = nil;
    734 	vtfree(dir->mid);
    735 	dir->mid = nil;
    736 }
    737 
    738 void
    739 deCopy(DirEntry *dst, DirEntry *src)
    740 {
    741 	*dst = *src;
    742 	dst->elem = vtstrdup(src->elem);
    743 	dst->uid = vtstrdup(src->uid);
    744 	dst->gid = vtstrdup(src->gid);
    745 	dst->mid = vtstrdup(src->mid);
    746 }