tvac.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
tvac.c (12502B)
---
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 }