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
stringunpack(char ** s,uchar ** p,int * n)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
stringpack(char * s,uchar * p)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
mbunpack(MetaBlock * mb,uchar * p,int n)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
mbpack(MetaBlock * mb)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
mbdelete(MetaBlock * mb,int i,MetaEntry * me)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
mbinsert(MetaBlock * mb,int i,MetaEntry * me)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
meunpack(MetaEntry * me,MetaBlock * mb,int i)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
mecmp(MetaEntry * me,char * s)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
mecmpnew(MetaEntry * me,char * s)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
offsetcmp(const void * s0,const void * s1)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 *
metachunks(MetaBlock * mb)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
mbcompact(MetaBlock * mb,MetaChunk * mc)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 *
mballoc(MetaBlock * mb,int n)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
vdsize(VacDir * dir,int version)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
vdpack(VacDir * dir,MetaEntry * me,int version)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
vdunpack(VacDir * dir,MetaEntry * me)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
vdcleanup(VacDir * dir)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
vdcopy(VacDir * dst,VacDir * src)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
mbsearch(MetaBlock * mb,char * elem,int * ri,MetaEntry * me)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
mbinit(MetaBlock * mb,uchar * p,int n,int entries)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
mbresize(MetaBlock * mb,MetaEntry * me,int n)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 }
737