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");
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)
376 {
377 	int n;
378 	
379 	/* constant part */
380 
381 	n = 	4 +	/* magic */
382 		2 + 	/* version */
383 		4 +	/* entry */
384 		4 + 	/* guid */
385 		4 + 	/* mentry */
386 		4 + 	/* mgen */
387 		8 +	/* qid */
388 		4 + 	/* mtime */
389 		4 + 	/* mcount */
390 		4 + 	/* ctime */
391 		4 + 	/* atime */
392 		4 +	/* mode */
393 		0;
394 
395 	/* strings */
396 	n += 2 + strlen(dir->elem);
397 	n += 2 + strlen(dir->uid);
398 	n += 2 + strlen(dir->gid);
399 	n += 2 + strlen(dir->mid);
400 
401 	/* optional sections */
402 	if(dir->qidspace) {
403 		n += 	3 + 	/* option header */
404 			8 + 	/* qid offset */
405 			8;	/* qid max */
406 	}
407 
408 	return n;
409 }
410 
411 void
412 vdpack(VacDir *dir, MetaEntry *me)
413 {
414 	uchar *p;
415 	ulong t32;
416 
417 	p = me->p;
418 	
419 	U32PUT(p, DirMagic);
420 	U16PUT(p+4, 9);		/* version */
421 	p += 6;
422 
423 	p += stringpack(dir->elem, p);
424 
425 	U32PUT(p, dir->entry);
426 	U32PUT(p+4, dir->gen);
427 	U32PUT(p+8, dir->mentry);
428 	U32PUT(p+12, dir->mgen);
429 	U64PUT(p+16, dir->qid, t32);
430 	p += 24;
431 
432 	p += stringpack(dir->uid, p);
433 	p += stringpack(dir->gid, p);
434 	p += stringpack(dir->mid, p);
435 	
436 	U32PUT(p, dir->mtime);
437 	U32PUT(p+4, dir->mcount);
438 	U32PUT(p+8, dir->ctime);
439 	U32PUT(p+12, dir->atime);
440 	U32PUT(p+16, dir->mode);
441 	p += 5*4;
442 
443 	if(dir->qidspace) {
444 		U8PUT(p, DirQidSpaceEntry);
445 		U16PUT(p+1, 2*8);
446 		p += 3;
447 		U64PUT(p, dir->qidoffset, t32);
448 		U64PUT(p+8, dir->qidmax, t32);
449 	}
450 
451 	assert(p == me->p + me->size);
452 }
453 
454 
455 int
456 vdunpack(VacDir *dir, MetaEntry *me)
457 {
458 	int t, nn, n, version;
459 	uchar *p;
460 	
461 	p = me->p;
462 	n = me->size;
463 
464 	memset(dir, 0, sizeof(VacDir));
465 
466 if(0)print("vdUnpack\n");
467 	/* magic */
468 	if(n < 4 || U32GET(p) != DirMagic)
469 		goto Err;
470 	p += 4;
471 	n -= 4;
472 
473 if(0)print("vdUnpack: got magic\n");
474 	/* version */
475 	if(n < 2)
476 		goto Err;
477 	version = U16GET(p);
478 	if(version < 7 || version > 9)
479 		goto Err;
480 	p += 2;
481 	n -= 2;	
482 
483 if(0)print("vdUnpack: got version\n");
484 
485 	/* elem */
486 	if(stringunpack(&dir->elem, &p, &n) < 0)
487 		goto Err;
488 
489 if(0)print("vdUnpack: got elem\n");
490 
491 	/* entry  */
492 	if(n < 4)
493 		goto Err;
494 	dir->entry = U32GET(p);
495 	p += 4;
496 	n -= 4;
497 
498 if(0)print("vdUnpack: got entry\n");
499 
500 	if(version < 9) {
501 		dir->gen = 0;
502 		dir->mentry = dir->entry+1;
503 		dir->mgen = 0;
504 	} else {
505 		if(n < 3*4)
506 			goto Err;
507 		dir->gen = U32GET(p);
508 		dir->mentry = U32GET(p+4);
509 		dir->mgen = U32GET(p+8);
510 		p += 3*4;
511 		n -= 3*4;
512 	}
513 
514 if(0)print("vdUnpack: got gen etc\n");
515 
516 	/* size is gotten from DirEntry */
517 
518 	/* qid */
519 	if(n < 8)
520 		goto Err;
521 	dir->qid = U64GET(p);
522 	p += 8;
523 	n -= 8;
524 
525 if(0)print("vdUnpack: got qid\n");
526 	/* skip replacement */
527 	if(version == 7) {
528 		if(n < VtScoreSize)
529 			goto Err;
530 		p += VtScoreSize;
531 		n -= VtScoreSize;
532 	}
533 	
534 	/* uid */
535 	if(stringunpack(&dir->uid, &p, &n) < 0)
536 		goto Err;
537 
538 	/* gid */
539 	if(stringunpack(&dir->gid, &p, &n) < 0)
540 		goto Err;
541 
542 	/* mid */
543 	if(stringunpack(&dir->mid, &p, &n) < 0)
544 		goto Err;
545 
546 if(0)print("vdUnpack: got ids\n");
547 	if(n < 5*4)
548 		goto Err;
549 	dir->mtime = U32GET(p);
550 	dir->mcount = U32GET(p+4);
551 	dir->ctime = U32GET(p+8);
552 	dir->atime = U32GET(p+12);
553 	dir->mode = U32GET(p+16);
554 	p += 5*4;
555 	n -= 5*4;
556 
557 if(0)print("vdUnpack: got times\n");
558 	/* optional meta data */
559 	while(n > 0) {
560 		if(n < 3)
561 			goto Err;
562 		t = p[0];
563 		nn = U16GET(p+1);
564 		p += 3;
565 		n -= 3;
566 		if(n < nn)
567 			goto Err;
568 		switch(t) {
569 		case DirPlan9Entry:
570 			/* not valid in version >= 9 */
571 			if(version >= 9)
572 				break;
573 			if(dir->plan9 || nn != 12)
574 				goto Err;
575 			dir->plan9 = 1;
576 			dir->p9path = U64GET(p);
577 			dir->p9version = U32GET(p+8);
578 			if(dir->mcount == 0)
579 				dir->mcount = dir->p9version;
580 			break;
581 		case DirGenEntry:
582 			/* not valid in version >= 9 */
583 			if(version >= 9)
584 				break;
585 			break;
586 		case DirQidSpaceEntry:
587 			if(dir->qidspace || nn != 16)
588 				goto Err;
589 			dir->qidspace = 1;
590 			dir->qidoffset = U64GET(p);
591 			dir->qidmax = U64GET(p+8);
592 			break;
593 		}
594 		p += nn;
595 		n -= nn;
596 	}
597 if(0)print("vdUnpack: got options\n");
598 
599 	if(p != me->p + me->size)
600 		goto Err;
601 
602 if(0)print("vdUnpack: correct size\n");
603 	return 0;
604 Err:
605 if(0)print("vdUnpack: XXXXXXXXXXXX EbadMeta\n");
606 	werrstr(EBadMeta);
607 	vdcleanup(dir);
608 	return -1;
609 }
610 
611 void
612 vdcleanup(VacDir *dir)
613 {
614 	vtfree(dir->elem);
615 	dir->elem = nil;
616 	vtfree(dir->uid);
617 	dir->uid = nil;
618 	vtfree(dir->gid);
619 	dir->gid = nil;
620 	vtfree(dir->mid);
621 	dir->mid = nil;
622 }
623 
624 void
625 vdcopy(VacDir *dst, VacDir *src)
626 {
627 	*dst = *src;
628 	dst->elem = vtstrdup(dst->elem);
629 	dst->uid = vtstrdup(dst->uid);
630 	dst->gid = vtstrdup(dst->gid);
631 	dst->mid = vtstrdup(dst->mid);
632 }
633 
634 int
635 mbsearch(MetaBlock *mb, char *elem, int *ri, MetaEntry *me)
636 {
637 	int i;
638 	int b, t, x;
639 
640 	/* binary search within block */
641 	b = 0;
642 	t = mb->nindex;
643 	while(b < t) {
644 		i = (b+t)>>1;
645 		if(meunpack(me, mb, i) < 0)
646 			return 0;
647 		if(mb->unbotch)
648 			x = mecmpnew(me, elem);
649 		else
650 			x = mecmp(me, elem);
651 
652 		if(x == 0) {
653 			*ri = i;
654 			return 1;
655 		}
656 	
657 		if(x < 0)
658 			b = i+1;
659 		else /* x > 0 */
660 			t = i;
661 	}
662 
663 	assert(b == t);
664 	
665 	*ri = b;	/* b is the index to insert this entry */
666 	memset(me, 0, sizeof(*me));
667 
668 	return -1;
669 }
670 
671 void
672 mbinit(MetaBlock *mb, uchar *p, int n)
673 {
674 	memset(mb, 0, sizeof(MetaBlock));
675 	mb->maxsize = n;
676 	mb->buf = p;
677 	mb->maxindex = n/100;
678 	mb->size = MetaHeaderSize + mb->maxindex*MetaIndexSize;
679 }
680 
681 int
682 mbresize(MetaBlock *mb, MetaEntry *me, int n)
683 {
684 	uchar *p, *ep;
685 
686 	/* easy case */
687 	if(n <= me->size){
688 		me->size = n;
689 		return 0;
690 	}
691 
692 	/* try and expand entry */
693 
694 	p = me->p + me->size;
695 	ep = mb->buf + mb->maxsize;
696 	while(p < ep && *p == 0)
697 		p++;
698 	if(n <= p - me->p){
699 		me->size = n;
700 		return 0;
701 	}
702 
703 	p = mballoc(mb, n);
704 	if(p != nil){
705 		me->p = p;
706 		me->size = n;
707 		return 0;
708 	}
709 
710 	return -1;
711 }