sys/src/cmd/vac/pack.c

   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 }