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