1 #include "stdinc.h" 2 #include "dat.h" 3 #include "fns.h" 4 5 typedef struct MetaChunk MetaChunk; 6 7 struct MetaChunk { 8 ushort offset; 9 ushort size; 10 ushort index; 11 }; 12 13 static void usage(void); 14 static void setBit(uchar *bmap, ulong addr); 15 static int getBit(uchar *bmap, ulong addr); 16 static int readLabel(Label *l, u32int addr); 17 static void error(char*, ...); 18 static void warn(char *fmt, ...); 19 static void chkEpoch(u32int epoch); 20 static void chkFree(void); 21 static int readLabel(Label *l, u32int addr); 22 static void chkDir(char *name, Source *source, Source *meta); 23 24 #pragma varargck argpos error 1 25 #pragma varargck argpos warn 1 26 27 uchar *amap; /* bitmap: has been visited at all */ 28 uchar *emap; /* bitmap: see condition (ii) below */ 29 uchar *vmap; /* bitmap: has been visited in this epoch */ 30 uchar *xmap; /* bitmap: see condition (iii) below */ 31 32 Fs *fs; 33 Cache *cache; 34 int nblocks; 35 int bsize; 36 int badactive; 37 int dumpblocks; /* write lost blocks into /tmp/lost */ 38 int fast; /* don't check that all the venti blocks are there */ 39 u32int hint; /* a guess at where chkEpoch might look to find the next root */ 40 41 void 42 main(int argc, char *argv[]) 43 { 44 int csize = 1000; 45 VtSession *z; 46 char *host = nil; 47 u32int e; 48 Source *r, *mr; 49 Block *b; 50 Super super; 51 52 ARGBEGIN{ 53 default: 54 usage(); 55 case 'c': 56 csize = atoi(ARGF()); 57 if(csize <= 0) 58 usage(); 59 break; 60 case 'd': 61 dumpblocks = 1; 62 break; 63 case 'f': 64 fast = 1; 65 break; 66 case 'h': 67 host = ARGF(); 68 break; 69 }ARGEND; 70 71 if(argc != 1) 72 usage(); 73 74 vtAttach(); 75 76 fmtinstall('L', labelFmt); 77 fmtinstall('V', scoreFmt); 78 fmtinstall('R', vtErrFmt); 79 80 /* 81 * Connect to Venti. 82 */ 83 z = vtDial(host, 0); 84 if(z == nil){ 85 if(!fast) 86 vtFatal("could not connect to server: %s", vtGetError()); 87 }else if(!vtConnect(z, 0)) 88 vtFatal("vtConnect: %s", vtGetError()); 89 90 /* 91 * Initialize file system. 92 */ 93 fs = fsOpen(argv[0], z, csize, OReadOnly); 94 if(fs == nil) 95 vtFatal("could not open file system: %R"); 96 cache = fs->cache; 97 nblocks = cacheLocalSize(cache, PartData); 98 bsize = fs->blockSize; 99 100 b = superGet(cache, &super); 101 if(b == nil) 102 vtFatal("could not load super block: %R"); 103 blockPut(b); 104 105 hint = super.active; 106 107 /* 108 * Run checks. 109 */ 110 amap = vtMemAllocZ(nblocks/8 + 1); 111 emap = vtMemAllocZ(nblocks/8 + 1); 112 vmap = vtMemAllocZ(nblocks/8 + 1); 113 xmap = vtMemAllocZ(nblocks/8 + 1); 114 for(e=fs->ehi; e >= fs->elo; e--){ 115 memset(emap, 0, nblocks/8+1); 116 memset(xmap, 0, nblocks/8+1); 117 chkEpoch(e); 118 } 119 chkFree(); 120 vtMemFree(amap); 121 vtMemFree(emap); 122 vtMemFree(vmap); 123 vtMemFree(xmap); 124 125 sourceLock(fs->source, OReadOnly); 126 r = sourceOpen(fs->source, 0, OReadOnly); 127 mr = sourceOpen(fs->source, 1, OReadOnly); 128 sourceUnlock(fs->source); 129 chkDir("", r, mr); 130 131 sourceClose(r); 132 sourceClose(mr); 133 134 fsClose(fs); 135 136 exits(0); 137 } 138 139 static void 140 usage(void) 141 { 142 fprint(2, "usage: %s [-c cachesize] [-h host] file\n", argv0); 143 exits("usage"); 144 } 145 146 /* 147 * When b points at bb, need to check: 148 * 149 * (i) b.e in [bb.e, bb.eClose) 150 * (ii) if b.e==bb.e, then no other b' in e points at bb. 151 * (iii) if !(b.state&Copied) and b.e==bb.e then no other b' points at bb. 152 * (iv) if b is active then no other active b' points at bb. 153 * (v) if b is a past life of b' then only one of b and b' is active (too hard to check) 154 * 155 * Does not walk onto Venti. 156 */ 157 158 static int 159 walk(Block *b, uchar score[VtScoreSize], int type, u32int tag, u32int epoch) 160 { 161 Block *bb; 162 u32int addr; 163 int i, ret; 164 u32int ep; 165 Entry e; 166 167 if(fast && globalToLocal(score) == NilBlock) 168 return 1; 169 170 bb = cacheGlobal(cache, score, type, tag, OReadOnly); 171 if(bb == nil){ 172 error("could not load block %V type %d tag %ux: %R", score, type, tag); 173 return 0; 174 } 175 176 ret = 0; 177 addr = globalToLocal(score); 178 if(addr == NilBlock){ 179 ret = 1; 180 goto Exit; 181 } 182 183 /* (i) */ 184 if(b->l.epoch < bb->l.epoch || bb->l.epochClose <= b->l.epoch){ 185 error("walk: block %#ux [%ud, %ud) points at %#ux [%ud, %ud)\n", 186 b->addr, b->l.epoch, b->l.epochClose, 187 bb->addr, bb->l.epoch, bb->l.epochClose); 188 goto Exit; 189 } 190 191 /* (ii) */ 192 if(b->l.epoch == epoch && bb->l.epoch == epoch){ 193 if(getBit(emap, addr)){ 194 error("walk: epoch join detected: addr %#ux %L\n", bb->addr, &bb->l); 195 goto Exit; 196 } 197 setBit(emap, addr); 198 } 199 200 /* (iii) */ 201 if(!(b->l.state&BsCopied) && b->l.epoch == bb->l.epoch){ 202 if(getBit(xmap, addr)){ 203 error("walk: copy join detected; addr %#ux %L\n", bb->addr, &bb->l); 204 goto Exit; 205 } 206 setBit(xmap, addr); 207 } 208 209 /* (iv) */ 210 if(epoch == fs->ehi){ 211 /* since epoch==fs->ehi is first, amap is same as ``have seen active'' */ 212 if(getBit(amap, addr)){ 213 error("walk: active join detected: addr %#ux %L\n", bb->addr, &bb->l); 214 goto Exit; 215 } 216 } 217 218 if(getBit(vmap, addr)){ 219 ret = 1; 220 goto Exit; 221 } 222 223 setBit(vmap, addr); 224 setBit(amap, addr); 225 226 b = nil; /* make sure no more refs to parent */ 227 USED(b); 228 229 switch(type){ 230 default: 231 /* pointer block */ 232 for(i=0; i<bsize/VtScoreSize; i++) 233 if(!walk(bb, bb->data + i*VtScoreSize, type-1, tag, epoch)) 234 print("# clrp %#ux %d\n", bb->addr, i); 235 break; 236 case BtData: 237 break; 238 case BtDir: 239 for(i=0; i<bsize/VtEntrySize; i++){ 240 if(!entryUnpack(&e, bb->data, i)){ 241 error("walk: could not unpack entry: %ux[%d]: %R", addr, i); 242 print("# clre %#ux %d\n", bb->addr, i); 243 continue; 244 } 245 if(!(e.flags & VtEntryActive)) 246 continue; 247 //fprint(2, "%x[%d] tag=%x snap=%d score=%V\n", addr, i, e.tag, e.snap, e.score); 248 ep = epoch; 249 if(e.snap != 0){ 250 if(e.snap >= epoch){ 251 error("bad snap in entry: %ux[%d] snap = %ud: epoch = %ud", 252 addr, i, e.snap, epoch); 253 print("# clre %#ux %d\n", bb->addr, i); 254 continue; 255 } 256 continue; 257 } 258 if(e.flags & VtEntryLocal){ 259 if(e.tag < UserTag) 260 if(e.tag != RootTag || tag != RootTag || i != 1){ 261 error("bad tag in entry: %ux[%d] tag = %ux", addr, i, e.tag); 262 print("# clre %#ux %d\n", bb->addr, i); 263 continue; 264 } 265 }else{ 266 if(e.tag != 0){ 267 error("bad tag in entry: %ux[%d] tag = %ux", addr, i, e.tag); 268 print("# clre %#ux %d\n", bb->addr, i); 269 continue; 270 } 271 } 272 if(!walk(bb, e.score, entryType(&e), e.tag, ep)) 273 print("# clre %#ux %d\n", bb->addr, i); 274 } 275 break; 276 } 277 278 ret = 1; 279 280 Exit: 281 blockPut(bb); 282 return ret; 283 } 284 285 static void 286 chkEpoch(u32int epoch) 287 { 288 u32int a; 289 Label l; 290 Entry e; 291 Block *b; 292 293 print("chkEpoch %ud\n", epoch); 294 295 /* find root block */ 296 for(a=0; a<nblocks; a++){ 297 if(!readLabel(&l, (a+hint)%nblocks)){ 298 error("could not read label: addr %ux %d %ux %ux: %R", a, l.type, l.state, l.state); 299 continue; 300 } 301 if(l.tag == RootTag && l.epoch == epoch) 302 break; 303 } 304 305 if(a == nblocks){ 306 print("chkEpoch: could not find root block for epoch: %ud\n", epoch); 307 return; 308 } 309 310 a = (a+hint)%nblocks; 311 b = cacheLocalData(cache, a, BtDir, RootTag, OReadOnly, 0); 312 if(b == nil){ 313 error("could not read root block %ux: %R\n", a); 314 return; 315 } 316 317 /* no one should point at the root blocks */ 318 setBit(amap, a); 319 setBit(emap, a); 320 setBit(vmap, a); 321 setBit(xmap, a); 322 323 /* 324 * First entry is the rest of the file system. 325 * Second entry is link to previous epoch root, 326 * just a convenience to help the search. 327 */ 328 if(!entryUnpack(&e, b->data, 0)){ 329 error("could not unpack root block %ux: %R", a); 330 blockPut(b); 331 return; 332 } 333 walk(b, e.score, BtDir, e.tag, epoch); 334 if(entryUnpack(&e, b->data, 1)) 335 hint = globalToLocal(e.score); 336 blockPut(b); 337 } 338 339 /* 340 * We've just walked the whole write buffer. Notice blocks that 341 * aren't marked available but that we didn't visit. They are lost. 342 */ 343 static void 344 chkFree(void) 345 { 346 char buf[64]; 347 int fd; 348 u32int a; 349 Block *b; 350 Label l; 351 u32int nfree; 352 u32int nlost; 353 354 nfree = 0; 355 nlost = 0; 356 /* find root block */ 357 for(a=0; a<nblocks; a++){ 358 if(!readLabel(&l, a)){ 359 error("could not read label: addr %ux %d %d: %R", 360 a, l.type, l.state); 361 continue; 362 } 363 if(getBit(amap, a)) 364 continue; 365 if(l.state == BsFree || l.epochClose <= fs->elo){ 366 nfree++; 367 setBit(amap, a); 368 continue; 369 } 370 nlost++; 371 warn("unreachable block: addr %ux type %d tag %ux state %s epoch %ud close %ud", 372 a, l.type, l.tag, bsStr(l.state), l.epoch, l.epochClose); 373 print("# bfree %#ux\n", a); 374 if(dumpblocks){ 375 sprint(buf, "/tmp/lost.%ux", a); 376 if((fd = create(buf, OWRITE, 0666)) < 0){ 377 fprint(2, "create %s: %r\n", buf); 378 goto nodump; 379 } 380 if((b = cacheLocal(cache, PartData, a, OReadOnly)) == nil){ 381 close(fd); 382 fprint(2, "load block %ux: %R\n", a); 383 goto nodump; 384 } 385 if(write(fd, b->data, bsize) != bsize) 386 fprint(2, "writiting %s: %r\n", buf); 387 close(fd); 388 blockPut(b); 389 } 390 nodump: 391 setBit(amap, a); 392 } 393 fprint(2, "\tused=%ud free space = %ud(%f%%) lost=%ud\n", 394 nblocks-nfree-nlost, nblocks, 100.*nfree/nblocks, nlost); 395 } 396 397 static Source * 398 openSource(Source *s, char *name, uchar *bm, u32int offset, u32int gen, int dir) 399 { 400 Source *r; 401 402 if(getBit(bm, offset)){ 403 warn("multiple references to source: %s -> %d", name, offset); 404 print("# clri %s\n", name); 405 return nil; 406 } 407 setBit(bm, offset); 408 409 r = sourceOpen(s, offset, OReadOnly); 410 if(r == nil){ 411 warn("could not open source: %s -> %d: %R", name, offset); 412 print("# clri %s\n", name); 413 return nil; 414 } 415 416 if(r->gen != gen){ 417 warn("source has been removed: %s -> %d", name, offset); 418 print("# clri %s\n", name); 419 goto Err; 420 } 421 422 if(r->dir != dir){ 423 warn("dir mismatch: %s -> %d", name, offset); 424 print("# clri %s\n", name); 425 goto Err; 426 } 427 return r; 428 Err: 429 sourceClose(r); 430 return nil; 431 } 432 433 static int 434 offsetCmp(void *s0, void *s1) 435 { 436 MetaChunk *mc0, *mc1; 437 438 mc0 = s0; 439 mc1 = s1; 440 if(mc0->offset < mc1->offset) 441 return -1; 442 if(mc0->offset > mc1->offset) 443 return 1; 444 return 0; 445 } 446 447 /* 448 * Check that MetaBlock has reasonable header, sorted entries, 449 */ 450 int 451 chkMetaBlock(MetaBlock *mb) 452 { 453 MetaChunk *mc; 454 int oo, o, n, i; 455 uchar *p; 456 457 mc = vtMemAlloc(mb->nindex*sizeof(MetaChunk)); 458 p = mb->buf + MetaHeaderSize; 459 for(i = 0; i<mb->nindex; i++){ 460 mc[i].offset = (p[0]<<8) | p[1]; 461 mc[i].size = (p[2]<<8) | p[3]; 462 mc[i].index = i; 463 p += MetaIndexSize; 464 } 465 466 qsort(mc, mb->nindex, sizeof(MetaChunk), offsetCmp); 467 468 /* check block looks ok */ 469 oo = MetaHeaderSize + mb->maxindex*MetaIndexSize; 470 o = oo; 471 n = 0; 472 for(i=0; i<mb->nindex; i++){ 473 o = mc[i].offset; 474 n = mc[i].size; 475 if(o < oo) 476 goto Err; 477 oo += n; 478 } 479 if(o+n > mb->size) 480 goto Err; 481 if(mb->size - oo != mb->free) 482 goto Err; 483 484 vtMemFree(mc); 485 return 1; 486 Err: 487 fprint(2, "metaChunks failed!\n"); 488 oo = MetaHeaderSize + mb->maxindex*MetaIndexSize; 489 for(i=0; i<mb->nindex; i++){ 490 fprint(2, "\t%d: %d %d\n", i, mc[i].offset, mc[i].offset + mc[i].size); 491 oo += mc[i].size; 492 } 493 fprint(2, "\tused=%d size=%d free=%d free2=%d\n", oo, mb->size, mb->free, mb->size - oo); 494 vtMemFree(mc); 495 return 0; 496 } 497 498 /* 499 * Walk the source tree making sure that the BtData 500 * sources containing directory entries are okay. 501 * 502 * Walks onto Venti, so takes a long time. 503 */ 504 static void 505 chkDir(char *name, Source *source, Source *meta) 506 { 507 uchar *bm; 508 Block *b, *bb; 509 u32int nb, o; 510 MetaBlock mb; 511 DirEntry de; 512 MetaEntry me; 513 int i; 514 char *s, *nn; 515 Source *r, *mr; 516 517 if(fast && globalToLocal(source->score)==NilBlock && globalToLocal(meta->score)==NilBlock) 518 return; 519 520 if(!sourceLock2(source, meta, OReadOnly)){ 521 warn("could not lock sources for %s: %R", name); 522 return; 523 } 524 525 bm = vtMemAllocZ(sourceGetDirSize(source)/8 + 1); 526 527 nb = (sourceGetSize(meta) + meta->dsize - 1)/meta->dsize; 528 for(o=0; o<nb; o++){ 529 b = sourceBlock(meta, o, OReadOnly); 530 if(0)fprint(2, "source %V:%d block %d addr %d\n", source->score, source->offset, o, b->addr); 531 if(b == nil){ 532 error("could not read block in meta file: %s[%ud]: %R", name, o); 533 continue; 534 } 535 if(!mbUnpack(&mb, b->data, meta->dsize)){ 536 error("could not unpack meta block: %s[%ud]: %R", name, o); 537 blockPut(b); 538 continue; 539 } 540 if(!chkMetaBlock(&mb)){ 541 error("bad meta block: %s[%ud]: %R", name, o); 542 blockPut(b); 543 continue; 544 } 545 s = vtStrDup(""); 546 for(i=0; i<mb.nindex; i++){ 547 meUnpack(&me, &mb, i); 548 if(!deUnpack(&de, &me)){ 549 error("cound not unpack dir entry: %s[%ud][%d]: %R", name, o, i); 550 continue; 551 } 552 if(strcmp(s, de.elem) >= 0) 553 error("dir entry out of order: %s[%ud][%d] = %s last = %s", name, o, i, 554 de.elem, s); 555 vtMemFree(s); 556 s = vtStrDup(de.elem); 557 nn = smprint("%s/%s", name, de.elem); 558 if(!(de.mode & ModeDir)){ 559 r = openSource(source, nn, bm, de.entry, de.gen, 0); 560 if(r != nil) 561 sourceClose(r); 562 deCleanup(&de); 563 free(nn); 564 continue; 565 } 566 567 r = openSource(source, nn, bm, de.entry, de.gen, 1); 568 if(r == nil){ 569 deCleanup(&de); 570 free(nn); 571 continue; 572 } 573 574 mr = openSource(source, nn, bm, de.mentry, de.mgen, 0); 575 if(mr == nil){ 576 sourceClose(r); 577 deCleanup(&de); 578 free(nn); 579 continue; 580 } 581 582 chkDir(nn, r, mr); 583 584 sourceClose(mr); 585 sourceClose(r); 586 deCleanup(&de); 587 free(nn); 588 deCleanup(&de); 589 590 } 591 vtMemFree(s); 592 blockPut(b); 593 } 594 595 nb = sourceGetDirSize(source); 596 for(o=0; o<nb; o++){ 597 if(getBit(bm, o)) 598 continue; 599 r = sourceOpen(source, o, OReadOnly); 600 if(r == nil) 601 continue; 602 warn("non referenced entry in source %s[%d]", name, o); 603 if((bb = sourceBlock(source, o/(source->dsize/VtEntrySize), OReadOnly)) != nil){ 604 if(bb->addr != NilBlock) 605 print("# clre %#ux %d\n", bb->addr, o%(source->dsize/VtEntrySize)); 606 blockPut(bb); 607 } 608 sourceClose(r); 609 } 610 611 sourceUnlock(source); 612 sourceUnlock(meta); 613 vtMemFree(bm); 614 } 615 616 617 static void 618 setBit(uchar *bmap, ulong addr) 619 { 620 bmap[addr>>3] |= 1 << (addr & 7); 621 } 622 623 static int 624 getBit(uchar *bmap, ulong addr) 625 { 626 return (bmap[addr>>3] >> (addr & 7)) & 1; 627 } 628 629 static int 630 readLabel(Label *l, u32int addr) 631 { 632 int lpb; 633 Block *b; 634 u32int a; 635 636 lpb = bsize / LabelSize; 637 a = addr / lpb; 638 b = cacheLocal(cache, PartLabel, a, OReadOnly); 639 if(b == nil){ 640 blockPut(b); 641 return 0; 642 } 643 644 if(!labelUnpack(l, b->data, addr%lpb)){ 645 print("labelUnpack %ux failed\n", addr); 646 blockPut(b); 647 return 0; 648 } 649 blockPut(b); 650 return 1; 651 } 652 653 static void 654 error(char *fmt, ...) 655 { 656 static nerr; 657 va_list arg; 658 char buf[128]; 659 660 661 va_start(arg, fmt); 662 vseprint(buf, buf+sizeof(buf), fmt, arg); 663 va_end(arg); 664 665 print("error: %s\n", buf); 666 667 // if(nerr++ > 20) 668 // vtFatal("too many errors"); 669 } 670 671 static void 672 warn(char *fmt, ...) 673 { 674 static nerr; 675 va_list arg; 676 char buf[128]; 677 678 679 va_start(arg, fmt); 680 vseprint(buf, buf+sizeof(buf), fmt, arg); 681 va_end(arg); 682 683 print("warn: %s\n", buf); 684 } 685