pack.c (11976B)
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 %#08ux", 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 }