Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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, 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 
}