op public repos

Blob

Date:: Sun Nov 23 17:55:34 2003 UTC
Message:: start thinking about vac -- doesn't build yet
Actions:: History | Blame | Raw File
1 #include <u.h>
2 #include <libc.h>
3 #include <venti.h>
4 
5 int bsize;
6 char *host;
7 VtConn *z;
8 
9 void
10 usage(void)
11 {
12 	fprint(2, "usage: vac [-b blocksize] [-h host] file\n");
13 }
14 
15 void
16 main(int argc, char *argv[])
17 {
18 	ARGBEGIN{
19 	default:
20 		usage();
21 	case 'b':
22 		bsize = unittoull(EARGF(usage()));
23 		break;
24 	case 'h':
25 		host = EARGF(usage());
26 		break;
27 	}ARGEND
28 
29 	if(bsize < 512)
30 		bsize = 512;
31 	if(bsize > VtMaxLumpSize)
32 		bsize = VtMaxLumpSize;
33 	maxbsize = bsize;
34 
35 	vtAttach();
36 
37 	fmtinstall('V', vtScoreFmt);
38 	fmtinstall('R', vtErrFmt);
39 
40 	z = vtDial(host, 0);
41 	if(z == nil)
42 		vtFatal("could not connect to server: %R");
43 
44 	if(!vtConnect(z, 0))
45 		vtFatal("vtConnect: %R");
46 
47 	qsort(exclude, nexclude, sizeof(char*), strpCmp);
48 
49 	vac(z, argv);
50 	if(!vtSync(z))
51 		fprint(2, "warning: could not ask server to flush pending writes: %R\n");
52 
53 	if(statsFlag)
54 		fprint(2, "files %ld:%ld data %ld:%ld:%ld meta %ld\n", stats.file, stats.sfile,
55 			stats.data, stats.skip, stats.sdata, stats.meta);
56 //packetStats();
57 	vtClose(z);
58 	vtDetach();
59 
60 	exits(0);
61 }
62 
63 static int
64 vac(VtSession *z, char *argv[])
65 {
66 	DirSink *dsink, *ds;
67 	MetaSink *ms;
68 	VtRoot root;
69 	uchar score[VtScoreSize], buf[VtRootSize];
70 	char cwd[2048];
71 	int cd, i;
72 	char *cp2, *cp;
73 	VacFS *fs;
74 	VacFile *vff;
75 	int fd;
76 	Dir *dir;
77 	VacDir vd;
78 
79 	if(getwd(cwd, sizeof(cwd)) == 0)
80 		sysfatal("can't find current directory: %r\n");
81 
82 	dsink = dirSinkAlloc(z, bsize, bsize);
83 
84 	fs = nil;
85 	if(dfile != nil) {
86 		fs = vfsOpen(z, dfile, 1, 10000);
87 		if(fs == nil)
88 			fprint(2, "could not open diff: %s: %s\n", dfile, vtGetError());
89 	}
90 		
91 
92 	if(oname != nil) {
93 		fd = create(oname, OWRITE, 0666);
94 		if(fd < 0)
95 			sysfatal("could not create file: %s: %r", oname);
96 	} else 
97 		fd = 1;
98 
99 	dir = dirfstat(fd);
100 	if(dir == nil)
101 		sysfatal("dirfstat failed: %r");
102 
103 	for(; *argv; argv++) {
104 		cp2 = *argv;
105 		cd = 0;
106 		for (cp = *argv; *cp; cp++)
107 			if (*cp == '/')
108 				cp2 = cp;
109 		if (cp2 != *argv) {
110 			*cp2 = '\0';
111 			chdir(*argv);
112 			*cp2 = '/';
113 			cp2++;
114 			cd = 1;
115 		}
116 		vff = nil;
117 		if(fs)
118 			vff = vfOpen(fs, cp2);
119 		vacFile(dsink, argv[0], cp2, vff);
120 		if(vff)
121 			vfDecRef(vff);
122 		if(cd && chdir(cwd) < 0)
123 			sysfatal("can't cd back to %s: %r\n", cwd);
124 	}
125 	
126 	if(isi) {
127 		vff = nil;
128 		if(fs)
129 			vff = vfOpen(fs, isi);
130 		vacStdin(dsink, isi, vff);
131 		if(vff)
132 			vfDecRef(vff);
133 	}
134 
135 	dirSinkClose(dsink);
136 
137 	/* build meta information for the root */
138 	ms = metaSinkAlloc(z, bsize, bsize);
139 	/* fake into a directory */
140 	dir->mode |= (dir->mode&0444)>>2;
141 	dir->qid.type |= QTDIR;
142 	dir->mode |= DMDIR;
143 	plan9ToVacDir(&vd, dir, 0, fileid++);
144 	if(strcmp(vd.elem, "/") == 0){
145 		vtMemFree(vd.elem);
146 		vd.elem = vtStrDup("root");
147 	}
148 	metaSinkWriteDir(ms, &vd);
149 	vdCleanup(&vd);
150 	metaSinkClose(ms);
151 	
152 	ds = dirSinkAlloc(z, bsize, bsize);
153 	dirSinkWriteSink(ds, dsink->sink);
154 	dirSinkWriteSink(ds, dsink->msink->sink);
155 	dirSinkWriteSink(ds, ms->sink);
156 	dirSinkClose(ds);
157 
158 	memset(&root, 0, sizeof(root));		
159 	root.version = VtRootVersion;
160 	strncpy(root.name, dir->name, sizeof(root.name));
161 	root.name[sizeof(root.name)-1] = 0;
162 	free(dir);
163 	sprint(root.type, "vac");
164 	memmove(root.score, ds->sink->dir.score, VtScoreSize);
165 	root.blockSize = maxbsize;
166 	if(fs != nil)
167 		vfsGetScore(fs, root.prev);
168 
169 	metaSinkFree(ms);
170 	dirSinkFree(ds);
171 	dirSinkFree(dsink);
172 	if(fs != nil)
173 		vfsClose(fs);
174 	
175 	vtRootPack(&root, buf);
176 	if(!vacWrite(z, score, VtRootType, buf, VtRootSize))
177 		vtFatal("vacWrite failed: %s", vtGetError());
178 
179 	fprint(fd, "vac:");
180 	for(i=0; i<VtScoreSize; i++)
181 		fprint(fd, "%.2x", score[i]);
182 	fprint(fd, "\n");
183 	
184 	/* avoid remove at cleanup */
185 	oname = nil;
186 	return 1;
187 }
188 
189 static int
190 isExcluded(char *name)
191 {
192 	int bot, top, i, x;
193 
194 	bot = 0;	
195 	top = nexclude;
196 	while(bot < top) {
197 		i = (bot+top)>>1;
198 		x = strcmp(exclude[i], name);
199 		if(x == 0)
200 			return 1;
201 		if(x < 0)
202 			bot = i + 1;
203 		else /* x > 0 */
204 			top = i;
205 	}
206 	return 0;
207 }
208 
209 static void
210 vacFile(DirSink *dsink, char *lname, char *sname, VacFile *vf)
211 {
212 	int fd;
213 	Dir *dir;
214 	VacDir vd;
215 	ulong entry;
216 
217 	if(isExcluded(lname)) {
218 		warn("excluding: %s", lname);
219 		return;
220 	}
221 
222 	if(merge && vacMerge(dsink, lname, sname))
223 		return;
224 
225 	fd = open(sname, OREAD);
226 	if(fd < 0) {
227 		warn("could not open file: %s: %s", lname, vtOSError());
228 		return;
229 	}
230 
231 	if(verbose)
232 		fprint(2, "%s\n", lname);
233 
234 	dir = dirfstat(fd);
235 	if(dir == nil) {
236 		warn("can't stat %s: %r", lname);
237 		close(fd);
238 		return;
239 	}
240 
241 	entry = dsink->nentry;
242 
243 	if(dir->mode & DMDIR) 
244 		vacDir(dsink, fd, lname, sname, vf);
245 	else
246 		vacData(dsink, fd, lname, vf, dir);
247 
248 	plan9ToVacDir(&vd, dir, entry, fileid++);
249 	metaSinkWriteDir(dsink->msink, &vd);
250 	vdCleanup(&vd);
251 
252 	free(dir);
253 	close(fd);
254 }
255 
256 static void
257 vacStdin(DirSink *dsink, char *name, VacFile *vf)
258 {
259 	Dir *dir;
260 	VacDir vd;
261 	ulong entry;
262 
263 	if(verbose)
264 		fprint(2, "%s\n", "<stdio>");
265 
266 	dir = dirfstat(0);
267 	if(dir == nil) {
268 		warn("can't stat <stdio>: %r");
269 		return;
270 	}
271 
272 	entry = dsink->nentry;
273 
274 	vacData(dsink, 0, "<stdin>", vf, dir);
275 
276 	plan9ToVacDir(&vd, dir, entry, fileid++);
277 	vd.elem = vtStrDup(name);
278 	metaSinkWriteDir(dsink->msink, &vd);
279 	vdCleanup(&vd);
280 
281 	free(dir);
282 }
283 
284 static ulong
285 vacDataSkip(Sink *sink, VacFile *vf, int fd, ulong blocks, uchar *buf, char *lname)
286 {
287 	int n;
288 	ulong i;
289 	uchar score[VtScoreSize];
290 
291 	/* skip blocks for append only files */
292 	if(seek(fd, (blocks-1)*bsize, 0) != (blocks-1)*bsize) {
293 		warn("error seeking: %s", lname);
294 		goto Err;
295 	}
296 	n = readBlock(fd, buf, bsize);
297 	if(n < bsize) {
298 		warn("error checking append only file: %s", lname);
299 		goto Err;
300 	}
301 	if(!vfGetBlockScore(vf, blocks-1, score) || !vtSha1Check(score, buf, n)) {
302 		warn("last block of append file did not match: %s", lname);
303 		goto Err;
304 	}
305 
306 	for(i=0; i<blocks; i++) {
307 		if(!vfGetBlockScore(vf, i, score)) {
308 			warn("could not get score: %s: %lud", lname, i);
309 			seek(fd, i*bsize, 0);
310 			return i;
311 		}
312 		stats.skip++;
313 		sinkWriteScore(sink, score, bsize);
314 	}
315 
316 	return i;
317 Err:
318 	seek(fd, 0, 0);
319 	return 0;
320 }
321 
322 static void
323 vacData(DirSink *dsink, int fd, char *lname, VacFile *vf, Dir *dir)
324 {
325 	uchar *buf;
326 	Sink *sink;
327 	int n;
328 	uchar score[VtScoreSize];
329 	ulong block, same;
330 	VacDir vd;
331 	ulong vfblocks;
332 
333 	vfblocks = 0;
334 	if(vf != nil && qdiff) {
335 		vfGetDir(vf, &vd);
336 		if(vd.mtime == dir->mtime)
337 		if(vd.size == dir->length)
338 		if(!vd.plan9 || /* vd.p9path == dir->qid.path && */ vd.p9version == dir->qid.vers)
339 		if(dirSinkWriteFile(dsink, vf)) {
340 			stats.sfile++;
341 			vdCleanup(&vd);
342 			return;
343 		}
344 
345 		/* look for an append only file */
346 		if((dir->mode&DMAPPEND) != 0)
347 		if(vd.size < dir->length)
348 		if(vd.plan9)
349 		if(vd.p9path == dir->qid.path)
350 			vfblocks = vd.size/bsize;
351 
352 		vdCleanup(&vd);
353 	}
354 	stats.file++;
355 
356 	buf = vtMemAlloc(bsize);
357 	sink = sinkAlloc(dsink->sink->z, bsize, bsize);
358 	block = 0;
359 	same = stats.sdata+stats.skip;
360 
361 	if(vfblocks > 1)
362 		block += vacDataSkip(sink, vf, fd, vfblocks, buf, lname);
363 
364 if(0) fprint(2, "vacData: %s: %ld\n", lname, block);
365 	for(;;) {
366 		n = readBlock(fd, buf, bsize);
367 		if(0 && n < 0)
368 			warn("file truncated due to read error: %s: %s", lname, vtOSError());
369 		if(n <= 0)
370 			break;
371 		if(vf != nil && vfGetBlockScore(vf, block, score) && vtSha1Check(score, buf, n)) {
372 			stats.sdata++;
373 			sinkWriteScore(sink, score, n);
374 		} else
375 			sinkWrite(sink, buf, n);
376 		block++;
377 	}
378 	same = stats.sdata+stats.skip - same;
379 
380 	if(same && (dir->mode&DMAPPEND) != 0)
381 		if(0)fprint(2, "%s: total %lud same %lud:%lud diff %lud\n",
382 			lname, block, same, vfblocks, block-same);
383 
384 	sinkClose(sink);
385 	dirSinkWriteSink(dsink, sink);
386 	sinkFree(sink);
387 	free(buf);
388 }
389 
390 
391 static void
392 vacDir(DirSink *dsink, int fd, char *lname, char *sname, VacFile *vf)
393 {
394 	Dir *dirs;
395 	char *ln, *sn;
396 	int i, nd;
397 	DirSink *ds;
398 	VacFile *vvf;
399 	char *name;
400 
401 	ds = dirSinkAlloc(dsink->sink->z, bsize, bsize);
402 	while((nd = dirread(fd, &dirs)) > 0){
403 		for(i = 0; i < nd; i++){
404 			name = dirs[i].name;
405 			/* check for bad file names */
406 			if(name[0] == 0 || strcmp(name, ".") == 0 || strcmp(name, "..") == 0)
407 				continue;
408 			ln = vtMemAlloc(strlen(lname) + strlen(name) + 2);
409 			sn = vtMemAlloc(strlen(sname) + strlen(name) + 2);
410 			sprint(ln, "%s/%s", lname, name);
411 			sprint(sn, "%s/%s", sname, name);
412 			if(vf != nil)
413 				vvf = vfWalk(vf, name);
414 			else
415 				vvf = nil;
416 			vacFile(ds, ln, sn, vvf);
417 			if(vvf != nil)
418 				vfDecRef(vvf);
419 			vtMemFree(ln);
420 			vtMemFree(sn);
421 		}
422 		free(dirs);
423 	}
424 	dirSinkClose(ds);
425 	dirSinkWriteSink(dsink, ds->sink);
426 	dirSinkWriteSink(dsink, ds->msink->sink);
427 	dirSinkFree(ds);
428 }
429 
430 static int
431 vacMergeFile(DirSink *dsink, VacFile *vf, VacDir *dir, uvlong offset, uvlong *max)
432 {
433 	uchar buf[VtEntrySize];
434 	VtEntry dd, md;
435 	int e;
436 
437 	if(vfRead(vf, buf, VtEntrySize, (uvlong)dir->entry*VtEntrySize) != VtEntrySize) {
438 		warn("could not read venti dir entry: %s\n", dir->elem);
439 		return 0;
440 	}
441 	vtEntryUnpack(&dd, buf, 0);
442 
443 	if(dir->mode & ModeDir)	{
444 		e = dir->mentry;
445 		if(e == 0)
446 			e = dir->entry + 1;
447 		
448 		if(vfRead(vf, buf, VtEntrySize, e*VtEntrySize) != VtEntrySize) {
449 			warn("could not read venti dir entry: %s\n", dir->elem);
450 			return 0;
451 		}
452 		vtEntryUnpack(&md, buf, 0);
453 	}
454 
455 	/* max might incorrect in some old dumps */
456 	if(dir->qid >= *max) {
457 		warn("qid out of range: %s", dir->elem);
458 		*max = dir->qid;
459 	}
460 
461 	dir->qid += offset;
462 	dir->entry = dsink->nentry;
463 
464 	if(dir->qidSpace) {
465 		dir->qidOffset += offset;
466 	} else {
467 		dir->qidSpace = 1;
468 		dir->qidOffset = offset;
469 		dir->qidMax = *max;
470 	}
471 
472 	dirSinkWrite(dsink, &dd);
473 	if(dir->mode & ModeDir)	
474 		dirSinkWrite(dsink, &md);
475 	metaSinkWriteDir(dsink->msink, dir);
476 	
477 	return 1;
478 }
479 
480 static int
481 vacMerge(DirSink *dsink, char *lname, char *sname)
482 {
483 	char *p;
484 	VacFS *fs;
485 	VacFile *vf;
486 	VacDirEnum *d;
487 	VacDir dir;
488 	uvlong max;
489 
490 	p = strrchr(sname, '.');
491 	if(p == 0 || strcmp(p, ".vac"))
492 		return 0;
493 
494 	d = nil;
495 	fs = vfsOpen(dsink->sink->z, sname, 1, 100);
496 	if(fs == nil)
497 		return 0;
498 
499 	vf = vfOpen(fs, "/");
500 	if(vf == nil)
501 		goto Done;
502 	max = vfGetId(vf);
503 	d = vdeOpen(fs, "/");
504 	if(d == nil)
505 		goto Done;
506 
507 	if(verbose)
508 		fprint(2, "merging: %s\n", lname);
509 
510 	if(maxbsize < vfsGetBlockSize(fs))
511 		maxbsize = vfsGetBlockSize(fs);
512 
513 	for(;;) {
514 		if(vdeRead(d, &dir, 1) < 1)
515 			break;
516 		vacMergeFile(dsink, vf, &dir, fileid, &max);
517 		vdCleanup(&dir);	
518 	}
519 	fileid += max;
520 
521 Done:
522 	if(d != nil)
523 		vdeFree(d);
524 	if(vf != nil)
525 		vfDecRef(vf);
526 	vfsClose(fs);
527 	return 1;
528 }
529 
530 Sink *
531 sinkAlloc(VtSession *z, int psize, int dsize)
532 {
533 	Sink *k;
534 	int i;
535 
536 	if(psize < 512 || psize > VtMaxLumpSize)
537 		vtFatal("sinkAlloc: bad psize");
538 	if(dsize < 512 || dsize > VtMaxLumpSize)
539 		vtFatal("sinkAlloc: bad psize");
540 
541 	psize = VtScoreSize*(psize/VtScoreSize);
542 
543 	k = vtMemAllocZ(sizeof(Sink));
544 	k->z = z;
545 	k->dir.flags = VtEntryActive;
546 	k->dir.psize = psize;
547 	k->dir.dsize = dsize;
548 	k->buf = vtMemAllocZ(VtPointerDepth*k->dir.psize + VtScoreSize);
549 	for(i=0; i<=VtPointerDepth; i++)
550 		k->pbuf[i] = k->buf + i*k->dir.psize;
551 	return k;
552 }
553 
554 void
555 sinkWriteScore(Sink *k, uchar score[VtScoreSize], int n)
556 {
557 	int i;
558 	uchar *p;
559 	VtEntry *d;
560 
561 	memmove(k->pbuf[0], score, VtScoreSize);
562 
563 	d = &k->dir;
564 
565 	for(i=0; i<VtPointerDepth; i++) {
566 		k->pbuf[i] += VtScoreSize;
567 		if(k->pbuf[i] < k->buf + d->psize*(i+1))
568 			break;
569 		if(i == VtPointerDepth-1)
570 			vtFatal("file too big");
571 		p = k->buf+i*d->psize;
572 		stats.meta++;
573 		if(!vacWrite(k->z, k->pbuf[i+1], VtPointerType0+i, p, d->psize))
574 			vtFatal("vacWrite failed: %s", vtGetError());
575 		k->pbuf[i] = p;
576 	}
577 
578 	/* round size up to multiple of dsize */
579 	d->size = d->dsize * ((d->size + d->dsize-1)/d->dsize);
580 	
581 	d->size += n;
582 }
583 
584 void
585 sinkWrite(Sink *k, uchar *p, int n)
586 {
587 	int type;
588 	uchar score[VtScoreSize];
589 
590 	if(n > k->dir.dsize)
591 		vtFatal("sinkWrite: size too big");
592 
593 	if(k->dir.flags & VtEntryDir) {
594 		type = VtDirType;
595 		stats.meta++;
596 	} else {
597 		type = VtDataType;
598 		stats.data++;
599 	}
600 	if(!vacWrite(k->z, score, type, p, n))
601 		vtFatal("vacWrite failed: %s", vtGetError());
602 
603 	sinkWriteScore(k, score, n);
604 }
605 
606 static int
607 sizeToDepth(uvlong s, int psize, int dsize)
608 {
609 	int np;
610 	int d;
611 	
612 	/* determine pointer depth */
613 	np = psize/VtScoreSize;
614 	s = (s + dsize - 1)/dsize;
615 	for(d = 0; s > 1; d++)
616 		s = (s + np - 1)/np;
617 	return d;
618 }
619 
620 void
621 sinkClose(Sink *k)
622 {
623 	int i, n;
624 	uchar *p;
625 	VtEntry *kd;
626 
627 	kd = &k->dir;
628 
629 	/* empty */
630 	if(kd->size == 0) {
631 		memmove(kd->score, vtZeroScore, VtScoreSize);
632 		return;
633 	}
634 
635 	for(n=VtPointerDepth-1; n>0; n--)
636 		if(k->pbuf[n] > k->buf + kd->psize*n)
637 			break;
638 
639 	kd->depth = sizeToDepth(kd->size, kd->psize, kd->dsize);
640 
641 	/* skip full part of tree */
642 	for(i=0; i<n && k->pbuf[i] == k->buf + kd->psize*i; i++)
643 		;
644 
645 	/* is the tree completely full */
646 	if(i == n && k->pbuf[n] == k->buf + kd->psize*n + VtScoreSize) {
647 		memmove(kd->score, k->pbuf[n] - VtScoreSize, VtScoreSize);
648 		return;
649 	}
650 	n++;
651 
652 	/* clean up the edge */
653 	for(; i<n; i++) {
654 		p = k->buf+i*kd->psize;
655 		stats.meta++;
656 		if(!vacWrite(k->z, k->pbuf[i+1], VtPointerType0+i, p, k->pbuf[i]-p))
657 			vtFatal("vacWrite failed: %s", vtGetError());
658 		k->pbuf[i+1] += VtScoreSize;
659 	}
660 	memmove(kd->score, k->pbuf[i] - VtScoreSize, VtScoreSize);
661 }
662 
663 void
664 sinkFree(Sink *k)
665 {
666 	vtMemFree(k->buf);
667 	vtMemFree(k);
668 }
669 
670 DirSink *
671 dirSinkAlloc(VtSession *z, int psize, int dsize)
672 {
673 	DirSink *k;
674 	int ds;
675 
676 	ds = VtEntrySize*(dsize/VtEntrySize);
677 
678 	k = vtMemAllocZ(sizeof(DirSink));
679 	k->sink = sinkAlloc(z, psize, ds);
680 	k->sink->dir.flags |= VtEntryDir;
681 	k->msink = metaSinkAlloc(z, psize, dsize);
682 	k->buf = vtMemAlloc(ds);
683 	k->p = k->buf;
684 	k->ep = k->buf + ds;
685 	return k;
686 }
687 
688 void
689 dirSinkWrite(DirSink *k, VtEntry *dir)
690 {
691 	if(k->p + VtEntrySize > k->ep) {
692 		sinkWrite(k->sink, k->buf, k->p - k->buf);
693 		k->p = k->buf;
694 	}
695 	vtEntryPack(dir, k->p, 0);
696 	k->nentry++;
697 	k->p += VtEntrySize;
698 }
699 
700 void
701 dirSinkWriteSink(DirSink *k, Sink *sink)
702 {
703 	dirSinkWrite(k, &sink->dir);
704 }
705 
706 int
707 dirSinkWriteFile(DirSink *k, VacFile *vf)
708 {
709 	VtEntry dir;
710 
711 	if(!vfGetVtEntry(vf, &dir))
712 		return 0;
713 	dirSinkWrite(k, &dir);
714 	return 1;
715 }
716 
717 void
718 dirSinkClose(DirSink *k)
719 {
720 	metaSinkClose(k->msink);
721 	if(k->p != k->buf)
722 		sinkWrite(k->sink, k->buf, k->p - k->buf);
723 	sinkClose(k->sink);
724 }
725 
726 void
727 dirSinkFree(DirSink *k)
728 {
729 	sinkFree(k->sink);
730 	metaSinkFree(k->msink);
731 	vtMemFree(k->buf);
732 	vtMemFree(k);
733 }
734 
735 MetaSink *
736 metaSinkAlloc(VtSession *z, int psize, int dsize)
737 {
738 	MetaSink *k;
739 
740 	k = vtMemAllocZ(sizeof(MetaSink));
741 	k->sink = sinkAlloc(z, psize, dsize);
742 	k->buf = vtMemAlloc(dsize);
743 	k->maxindex = dsize/100;	/* 100 byte entries seems reasonable */
744 	if(k->maxindex < 1)
745 		k->maxindex = 1;
746 	k->rp = k->p = k->buf + MetaHeaderSize + k->maxindex*MetaIndexSize;
747 	k->ep = k->buf + dsize;
748 	return k;
749 }
750 
751 /* hack to get base to compare routine - not reentrant */
752 uchar *blockBase;
753 
754 int
755 dirCmp(void *p0, void *p1)
756 {
757 	uchar *q0, *q1;
758 	int n0, n1, r;
759 
760 	/* name is first element of entry */
761 	q0 = p0;
762 	q0 = blockBase + (q0[0]<<8) + q0[1];
763 	n0 = (q0[6]<<8) + q0[7];
764 	q0 += 8;
765 
766 	q1 = p1;
767 	q1 = blockBase + (q1[0]<<8) + q1[1];
768 	n1 = (q1[6]<<8) + q1[7];
769 	q1 += 8;
770 
771 	if(n0 == n1)
772 		return memcmp(q0, q1, n0);
773 	else if (n0 < n1) {
774 		r = memcmp(q0, q1, n0);
775 		return (r==0)?1:r;
776 	} else  {
777 		r = memcmp(q0, q1, n1);
778 		return (r==0)?-1:r;
779 	}
780 }
781 
782 void
783 metaSinkFlush(MetaSink *k)
784 {
785 	uchar *p;
786 	int n;
787 	MetaBlock mb;
788 
789 	if(k->nindex == 0)
790 		return;
791 	assert(k->nindex <= k->maxindex);
792 
793 	p = k->buf;
794 	n = k->rp - p;
795 
796 	mb.size = n;
797 	mb.free = 0;
798 	mb.nindex = k->nindex;
799 	mb.maxindex = k->maxindex;
800 	mb.buf = p;
801 	mbPack(&mb);
802 	
803 	p += MetaHeaderSize;
804 
805 	/* XXX this is not reentrant! */
806 	blockBase = k->buf;
807 	qsort(p, k->nindex, MetaIndexSize, dirCmp);
808 	p += k->nindex*MetaIndexSize;
809 	
810 	memset(p, 0, (k->maxindex-k->nindex)*MetaIndexSize);
811 	p += (k->maxindex-k->nindex)*MetaIndexSize;
812 
813 	sinkWrite(k->sink, k->buf, n);
814 
815 	/* move down partial entry */
816 	n = k->p - k->rp;
817 	memmove(p, k->rp, n);
818 	k->rp = p;
819 	k->p = p + n;
820 	k->nindex = 0;
821 }
822 
823 void
824 metaSinkPutc(MetaSink *k, int c)
825 {
826 	if(k->p+1 > k->ep)
827 		metaSinkFlush(k);
828 	if(k->p+1 > k->ep)
829 		vtFatal("directory entry too large");
830 	k->p[0] = c;
831 	k->p++;
832 }
833 
834 void
835 metaSinkPutString(MetaSink *k, char *s)
836 {
837 	int n = strlen(s);
838 	metaSinkPutc(k, n>>8);
839 	metaSinkPutc(k, n);
840 	metaSinkWrite(k, (uchar*)s, n);
841 }
842 
843 void
844 metaSinkPutUint32(MetaSink *k, ulong x)
845 {
846 	metaSinkPutc(k, x>>24);
847 	metaSinkPutc(k, x>>16);
848 	metaSinkPutc(k, x>>8);
849 	metaSinkPutc(k, x);
850 }
851 
852 void
853 metaSinkPutUint64(MetaSink *k, uvlong x)
854 {
855 	metaSinkPutUint32(k, x>>32);
856 	metaSinkPutUint32(k, x);
857 }
858 
859 void
860 metaSinkWrite(MetaSink *k, uchar *data, int n)
861 {
862 	if(k->p + n > k->ep)
863 		metaSinkFlush(k);
864 	if(k->p + n > k->ep)
865 		vtFatal("directory entry too large");
866 	
867 	memmove(k->p, data, n);
868 	k->p += n;
869 }
870 
871 void
872 metaSinkWriteDir(MetaSink *ms, VacDir *dir)
873 {
874 	metaSinkPutUint32(ms, DirMagic);
875 	metaSinkPutc(ms, Version>>8);
876 	metaSinkPutc(ms, Version);		
877 	metaSinkPutString(ms, dir->elem);
878 	metaSinkPutUint32(ms, dir->entry);
879 	metaSinkPutUint64(ms, dir->qid);
880 	metaSinkPutString(ms, dir->uid);
881 	metaSinkPutString(ms, dir->gid);
882 	metaSinkPutString(ms, dir->mid);
883 	metaSinkPutUint32(ms, dir->mtime);
884 	metaSinkPutUint32(ms, dir->mcount);
885 	metaSinkPutUint32(ms, dir->ctime);
886 	metaSinkPutUint32(ms, dir->atime);
887 	metaSinkPutUint32(ms, dir->mode);
888 
889 	if(dir->plan9) {
890 		metaSinkPutc(ms, DirPlan9Entry);	/* plan9 extra info */
891 		metaSinkPutc(ms, 0);			/* plan9 extra size */
892 		metaSinkPutc(ms, 12);			/* plan9 extra size */
893 		metaSinkPutUint64(ms, dir->p9path);
894 		metaSinkPutUint32(ms, dir->p9version);
895 	}
896 
897 	if(dir->qidSpace != 0) {
898 		metaSinkPutc(ms, DirQidSpaceEntry);
899 		metaSinkPutc(ms, 0);
900 		metaSinkPutc(ms, 16);
901 		metaSinkPutUint64(ms, dir->qidOffset);
902 		metaSinkPutUint64(ms, dir->qidMax);
903 	}
904 
905 	if(dir->gen != 0) {
906 		metaSinkPutc(ms, DirGenEntry);
907 		metaSinkPutc(ms, 0);
908 		metaSinkPutc(ms, 4);
909 		metaSinkPutUint32(ms, dir->gen);
910 	}
911 
912 	metaSinkEOR(ms);
913 }
914 
915 
916 void
917 plan9ToVacDir(VacDir *vd, Dir *dir, ulong entry, uvlong qid)
918 {
919 	memset(vd, 0, sizeof(VacDir));
920 
921 	vd->elem = vtStrDup(dir->name);
922 	vd->entry = entry;
923 	vd->qid = qid;
924 	vd->uid = vtStrDup(dir->uid);
925 	vd->gid = vtStrDup(dir->gid);
926 	vd->mid = vtStrDup(dir->muid);
927 	vd->mtime = dir->mtime;
928 	vd->mcount = 0;
929 	vd->ctime = dir->mtime;		/* ctime: not available on plan 9 */
930 	vd->atime = dir->atime;
931 
932 	vd->mode = dir->mode & 0777;
933 	if(dir->mode & DMDIR)
934 		vd->mode |= ModeDir;
935 	if(dir->mode & DMAPPEND)
936 		vd->mode |= ModeAppend;
937 	if(dir->mode & DMEXCL)
938 		vd->mode |= ModeExclusive;
939 
940 	vd->plan9 = 1;
941 	vd->p9path = dir->qid.path;
942 	vd->p9version = dir->qid.vers;
943 }
944 
945 
946 void
947 metaSinkEOR(MetaSink *k)
948 {
949 	uchar *p;
950 	int o, n;
951 
952 	p = k->buf + MetaHeaderSize;
953 	p += k->nindex * MetaIndexSize;
954 	o = k->rp-k->buf; 	/* offset from start of block */
955 	n = k->p-k->rp;		/* size of entry */
956 	p[0] = o >> 8;
957 	p[1] = o;
958 	p[2] = n >> 8;
959 	p[3] = n;
960 	k->rp = k->p;
961 	k->nindex++;
962 	if(k->nindex == k->maxindex)
963 		metaSinkFlush(k);
964 }
965 
966 void
967 metaSinkClose(MetaSink *k)
968 {
969 	metaSinkFlush(k);
970 	sinkClose(k->sink);
971 }
972 
973 void
974 metaSinkFree(MetaSink *k)
975 {
976 	sinkFree(k->sink);
977 	vtMemFree(k->buf);
978 	vtMemFree(k);
979 }
980 
981 static void
982 warn(char *fmt, ...)
983 {
984 	va_list arg;
985 
986 	va_start(arg, fmt);
987 	fprint(2, "%s: ", argv0);
988 	vfprint(2, fmt, arg);
989 	fprint(2, "\n");
990 	va_end(arg);
991 }
992 
993 static void
994 cleanup(void)
995 {
996 	if(oname != nil)
997 		remove(oname);
998 }
999 
1000 #define TWID64	((u64int)~(u64int)0)
1001 
1002 static u64int
1003 unittoull(char *s)
1004 {
1005 	char *es;
1006 	u64int n;
1007 
1008 	if(s == nil)
1009 		return TWID64;
1010 	n = strtoul(s, &es, 0);
1011 	if(*es == 'k' || *es == 'K'){
1012 		n *= 1024;
1013 		es++;
1014 	}else if(*es == 'm' || *es == 'M'){
1015 		n *= 1024*1024;
1016 		es++;
1017 	}else if(*es == 'g' || *es == 'G'){
1018 		n *= 1024*1024*1024;
1019 		es++;
1020 	}
1021 	if(*es != '\0')
1022 		return TWID64;
1023 	return n;
1024 }