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