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 }