1 #include "all.h"
2
3 /* augmented Dentry */
4 typedef struct {
5 Dentry *d;
6 Off qpath;
7 int ns;
8 } Extdentry;
9
10 static char* abits;
11 static long sizabits;
12 static char* qbits;
13 static long sizqbits;
14
15 static char* name;
16 static long sizname;
17
18 static Off fstart;
19 static Off fsize;
20 static Off nfiles;
21 static Off maxq;
22 static Device* dev;
23 static Off ndup;
24 static Off nused;
25 static Off nfdup;
26 static Off nqbad;
27 static Off nfree;
28 static Off nbad;
29 static int mod;
30 static int flags;
31 static int ronly;
32 static int cwflag;
33 static Devsize sbaddr;
34 static Devsize oldblock;
35
36 static int depth;
37 static int maxdepth;
38 static uchar *lowstack, *startstack;
39
40 /* local prototypes */
41 static int amark(Off);
42 static void* chkalloc(ulong);
43 static void ckfreelist(Superb*);
44 static int fmark(Off);
45 static int fsck(Dentry*);
46 static int ftest(Off);
47 static Dentry* maked(Off, int, Off);
48 static void missing(void);
49 static void mkfreelist(Superb*);
50 static void modd(Off, int, Dentry*);
51 static void qmark(Off);
52 static void trfreelist(Superb*);
53 static void xaddfree(Device*, Off, Superb*, Iobuf*);
54 static void xflush(Device*, Superb*, Iobuf*);
55 static void xread(Off, Off);
56 static Iobuf* xtag(Off, int, Off);
57
58 static void *
chkalloc(ulong n)59 chkalloc(ulong n)
60 {
61 char *p = mallocz(n, 1);
62
63 if (p == nil)
64 panic("chkalloc: out of memory");
65 return p;
66 }
67
68 void
chkfree(void * p)69 chkfree(void *p)
70 {
71 free(p);
72 }
73
74 /*
75 * check flags
76 */
77 enum
78 {
79 Crdall = (1<<0), /* read all files */
80 Ctag = (1<<1), /* rebuild tags */
81 Cpfile = (1<<2), /* print files */
82 Cpdir = (1<<3), /* print directories */
83 Cfree = (1<<4), /* rebuild free list */
84 // Csetqid = (1<<5), /* resequence qids */
85 Cream = (1<<6), /* clear all bad tags */
86 Cbad = (1<<7), /* clear all bad blocks */
87 Ctouch = (1<<8), /* touch old dir and indir */
88 Ctrim = (1<<9), /* trim fsize back to fit when checking free list */
89 };
90
91 static struct {
92 char* option;
93 long flag;
94 } ckoption[] = {
95 "rdall", Crdall,
96 "tag", Ctag,
97 "pfile", Cpfile,
98 "pdir", Cpdir,
99 "free", Cfree,
100 // "setqid", Csetqid,
101 "ream", Cream,
102 "bad", Cbad,
103 "touch", Ctouch,
104 "trim", Ctrim,
105 0,
106 };
107
108 void
cmd_check(int argc,char * argv[])109 cmd_check(int argc, char *argv[])
110 {
111 long f, i, flag;
112 Off raddr;
113 Filsys *fs;
114 Iobuf *p;
115 Superb *sb;
116 Dentry *d;
117
118 flag = 0;
119 for(i=1; i<argc; i++) {
120 for(f=0; ckoption[f].option; f++)
121 if(strcmp(argv[i], ckoption[f].option) == 0)
122 goto found;
123 print("unknown check option %s\n", argv[i]);
124 for(f=0; ckoption[f].option; f++)
125 print("\t%s\n", ckoption[f].option);
126 return;
127 found:
128 flag |= ckoption[f].flag;
129 }
130 fs = cons.curfs;
131
132 dev = fs->dev;
133 ronly = (dev->type == Devro);
134 cwflag = (dev->type == Devcw) | (dev->type == Devro);
135 if(!ronly)
136 wlock(&mainlock); /* check */
137 flags = flag;
138
139 name = abits = qbits = nil; /* in case of goto */
140 sbaddr = superaddr(dev);
141 raddr = getraddr(dev);
142 p = xtag(sbaddr, Tsuper, QPSUPER);
143 if(!p)
144 goto out;
145 sb = (Superb*)p->iobuf;
146 fstart = 2;
147 cons.noage = 1;
148
149 /* 200 is slop since qidgen is likely to be a little bit low */
150 sizqbits = (sb->qidgen+200 + 7) / 8;
151 qbits = chkalloc(sizqbits);
152
153 fsize = sb->fsize;
154 sizabits = (fsize-fstart + 7)/8;
155 abits = chkalloc(sizabits);
156
157 sizname = 4000;
158 name = chkalloc(sizname);
159 sizname -= NAMELEN+10; /* for safety */
160
161 mod = 0;
162 nfree = 0;
163 nfdup = 0;
164 nused = 0;
165 nbad = 0;
166 ndup = 0;
167 nqbad = 0;
168 depth = 0;
169 maxdepth = 0;
170
171 if(flags & Ctouch) {
172 /* round fsize down to start of current side */
173 int s;
174 Devsize dsize;
175
176 oldblock = 0;
177 for (s = 0; dsize = wormsizeside(dev, s),
178 dsize > 0 && oldblock + dsize < fsize; s++)
179 oldblock += dsize;
180 print("oldblock = %lld\n", (Wideoff)oldblock);
181 }
182 amark(sbaddr);
183 if(cwflag) {
184 amark(sb->roraddr);
185 amark(sb->next);
186 }
187
188 print("checking filsys: %s\n", fs->name);
189 nfiles = 0;
190 maxq = 0;
191
192 d = maked(raddr, 0, QPROOT);
193 if(d) {
194 amark(raddr);
195 if(fsck(d))
196 modd(raddr, 0, d);
197 chkfree(d);
198 depth--;
199 if(depth)
200 print("depth not zero on return\n");
201 }
202
203 if(flags & Cfree)
204 if(cwflag)
205 trfreelist(sb);
206 else
207 mkfreelist(sb);
208
209 if(sb->qidgen < maxq)
210 print("qid generator low path=%lld maxq=%lld\n",
211 (Wideoff)sb->qidgen, (Wideoff)maxq);
212 if(!(flags & Cfree))
213 ckfreelist(sb);
214 if(mod) {
215 sb->qidgen = maxq;
216 print("file system was modified\n");
217 settag(p, Tsuper, QPNONE);
218 }
219
220 print("nfiles = %lld\n", (Wideoff)nfiles);
221 print("fsize = %lld\n", (Wideoff)fsize);
222 print("nused = %lld\n", (Wideoff)nused);
223 print("ndup = %lld\n", (Wideoff)ndup);
224 print("nfree = %lld\n", (Wideoff)nfree);
225 print("tfree = %lld\n", (Wideoff)sb->tfree);
226 print("nfdup = %lld\n", (Wideoff)nfdup);
227 print("nmiss = %lld\n", (Wideoff)fsize-fstart-nused-nfree);
228 print("nbad = %lld\n", (Wideoff)nbad);
229 print("nqbad = %lld\n", (Wideoff)nqbad);
230 print("maxq = %lld\n", (Wideoff)maxq);
231 print("base stack=%llud\n", (vlong)startstack);
232 /* high-water mark of stack usage */
233 print("high stack=%llud\n", (vlong)lowstack);
234 print("deepest recursion=%d\n", maxdepth-1); /* one-origin */
235 if(!cwflag)
236 missing();
237
238 out:
239 cons.noage = 0;
240 putbuf(p);
241 chkfree(name);
242 chkfree(abits);
243 chkfree(qbits);
244 name = abits = qbits = nil;
245 if(!ronly)
246 wunlock(&mainlock);
247 }
248
249 /*
250 * if *blkp is already allocated and Cbad is set, zero it.
251 * returns *blkp if it's free, else 0.
252 */
253 static Off
blkck(Off * blkp,int * flgp)254 blkck(Off *blkp, int *flgp)
255 {
256 Off a = *blkp;
257
258 if(amark(a)) {
259 if(flags & Cbad) {
260 *blkp = 0;
261 *flgp |= Bmod;
262 }
263 a = 0;
264 }
265 return a;
266 }
267
268 /*
269 * if a block address within a Dentry, *blkp, is already allocated
270 * and Cbad is set, zero it.
271 * stores 0 into *resp if already allocated, else stores *blkp.
272 * returns dmod count.
273 */
274 static int
daddrck(Off * blkp,Off * resp)275 daddrck(Off *blkp, Off *resp)
276 {
277 int dmod = 0;
278
279 if(amark(*blkp)) {
280 if(flags & Cbad) {
281 *blkp = 0;
282 dmod++;
283 }
284 *resp = 0;
285 } else
286 *resp = *blkp;
287 return dmod;
288 }
289
290 /*
291 * under Ctouch, read block `a' if it's in range.
292 * returns dmod count.
293 */
294 static int
touch(Off a)295 touch(Off a)
296 {
297 if((flags&Ctouch) && a < oldblock) {
298 Iobuf *pd = getbuf(dev, a, Brd|Bmod);
299
300 if(pd)
301 putbuf(pd);
302 return 1;
303 }
304 return 0;
305 }
306
307 /*
308 * if d is a directory, touch it and check all its entries in block a.
309 * if not, under Crdall, read a.
310 * returns dmod count.
311 */
312 static int
dirck(Extdentry * ed,Off a)313 dirck(Extdentry *ed, Off a)
314 {
315 int k, dmod = 0;
316
317 if(ed->d->mode & DDIR) {
318 dmod += touch(a);
319 for(k=0; k<DIRPERBUF; k++) {
320 Dentry *nd = maked(a, k, ed->qpath);
321
322 if(nd == nil)
323 break;
324 if(fsck(nd)) {
325 modd(a, k, nd);
326 dmod++;
327 }
328 chkfree(nd);
329 depth--;
330 name[ed->ns] = 0;
331 }
332 } else if(flags & Crdall)
333 xread(a, ed->qpath);
334 return dmod;
335 }
336
337 /*
338 * touch a, check a's tag for Tind1, Tind2, etc.
339 * if the tag is right, validate each block number in the indirect block,
340 * and check each block (mostly in case we are reading a huge directory).
341 */
342 static int
indirck(Extdentry * ed,Off a,int tag)343 indirck(Extdentry *ed, Off a, int tag)
344 {
345 int i, dmod = 0;
346 Iobuf *p1;
347
348 if (a == 0)
349 return dmod;
350 dmod = touch(a);
351 if (p1 = xtag(a, tag, ed->qpath)) {
352 for(i=0; i<INDPERBUF; i++) {
353 a = blkck(&((Off *)p1->iobuf)[i], &p1->flags);
354 if (a)
355 /*
356 * check each block named in this
357 * indirect(^n) block (a).
358 */
359 if (tag == Tind1)
360 dmod += dirck(ed, a);
361 else
362 dmod += indirck(ed, a, tag-1);
363 }
364 putbuf(p1);
365 }
366 return dmod;
367 }
368
369 static int
indiraddrck(Extdentry * ed,Off * indirp,int tag)370 indiraddrck(Extdentry *ed, Off *indirp, int tag)
371 {
372 int dmod;
373 Off a;
374
375 dmod = daddrck(indirp, &a);
376 return dmod + indirck(ed, a, tag);
377 }
378
379 /* if result is true, *d was modified */
380 static int
fsck(Dentry * d)381 fsck(Dentry *d)
382 {
383 int i, dmod;
384 Extdentry edent;
385
386 depth++;
387 if(depth >= maxdepth)
388 maxdepth = depth;
389 if (lowstack == nil)
390 startstack = lowstack = (uchar *)&edent;
391 /* more precise check, assumes downward-growing stack */
392 if ((uchar *)&edent < lowstack)
393 lowstack = (uchar *)&edent;
394
395 /* check that entry is allocated */
396 if(!(d->mode & DALLOC))
397 return 0;
398 nfiles++;
399
400 /* we stash qpath & ns in an Extdentry for eventual use by dirck() */
401 memset(&edent, 0, sizeof edent);
402 edent.d = d;
403
404 /* check name */
405 edent.ns = strlen(name);
406 i = strlen(d->name);
407 if(i >= NAMELEN) {
408 d->name[NAMELEN-1] = 0;
409 print("%s->name (%s) not terminated\n", name, d->name);
410 return 0;
411 }
412 edent.ns += i;
413 if(edent.ns >= sizname) {
414 print("%s->name (%s) name too large\n", name, d->name);
415 return 0;
416 }
417 strcat(name, d->name);
418
419 if(d->mode & DDIR) {
420 if(edent.ns > 1) {
421 strcat(name, "/");
422 edent.ns++;
423 }
424 if(flags & Cpdir) {
425 print("%s\n", name);
426 prflush();
427 }
428 } else if(flags & Cpfile) {
429 print("%s\n", name);
430 prflush();
431 }
432
433 /* check qid */
434 edent.qpath = d->qid.path & ~QPDIR;
435 qmark(edent.qpath);
436 if(edent.qpath > maxq)
437 maxq = edent.qpath;
438
439 /* check direct blocks (the common case) */
440 dmod = 0;
441 {
442 Off a;
443
444 for(i=0; i<NDBLOCK; i++) {
445 dmod += daddrck(&d->dblock[i], &a);
446 if (a)
447 dmod += dirck(&edent, a);
448 }
449 }
450 /* check indirect^n blocks, if any */
451 for (i = 0; i < NIBLOCK; i++)
452 dmod += indiraddrck(&edent, &d->iblocks[i], Tind1+i);
453 return dmod;
454 }
455
456 enum { XFEN = FEPERBUF + 6 };
457
458 typedef struct {
459 int flag;
460 int count;
461 int next;
462 Off addr[XFEN];
463 } Xfree;
464
465 static void
xaddfree(Device * dev,Off a,Superb * sb,Iobuf * p)466 xaddfree(Device *dev, Off a, Superb *sb, Iobuf *p)
467 {
468 Xfree *x;
469
470 x = (Xfree*)p->iobuf;
471 if(x->count < XFEN) {
472 x->addr[x->count] = a;
473 x->count++;
474 return;
475 }
476 if(!x->flag) {
477 memset(&sb->fbuf, 0, sizeof(sb->fbuf));
478 sb->fbuf.free[0] = 0L;
479 sb->fbuf.nfree = 1;
480 sb->tfree = 0;
481 x->flag = 1;
482 }
483 addfree(dev, a, sb);
484 }
485
486 static void
xflush(Device * dev,Superb * sb,Iobuf * p)487 xflush(Device *dev, Superb *sb, Iobuf *p)
488 {
489 int i;
490 Xfree *x;
491
492 x = (Xfree*)p->iobuf;
493 if(!x->flag) {
494 memset(&sb->fbuf, 0, sizeof(sb->fbuf));
495 sb->fbuf.free[0] = 0L;
496 sb->fbuf.nfree = 1;
497 sb->tfree = 0;
498 }
499 for(i=0; i<x->count; i++)
500 addfree(dev, x->addr[i], sb);
501 }
502
503 /*
504 * make freelist
505 * from existing freelist
506 * (cw devices)
507 */
508 static void
trfreelist(Superb * sb)509 trfreelist(Superb *sb)
510 {
511 Off a, n;
512 int i;
513 Iobuf *p, *xp;
514 Fbuf *fb;
515
516
517 xp = getbuf(devnone, Cckbuf, 0);
518 memset(xp->iobuf, 0, BUFSIZE);
519 fb = &sb->fbuf;
520 p = 0;
521 for(;;) {
522 n = fb->nfree;
523 if(n < 0 || n > FEPERBUF)
524 break;
525 for(i=1; i<n; i++) {
526 a = fb->free[i];
527 if(a && !ftest(a))
528 xaddfree(dev, a, sb, xp);
529 }
530 a = fb->free[0];
531 if(!a)
532 break;
533 if(ftest(a))
534 break;
535 xaddfree(dev, a, sb, xp);
536 if(p)
537 putbuf(p);
538 p = xtag(a, Tfree, QPNONE);
539 if(!p)
540 break;
541 fb = (Fbuf*)p->iobuf;
542 }
543 if(p)
544 putbuf(p);
545 xflush(dev, sb, xp);
546 putbuf(xp);
547 mod++;
548 print("%lld blocks free\n", (Wideoff)sb->tfree);
549 }
550
551 static void
ckfreelist(Superb * sb)552 ckfreelist(Superb *sb)
553 {
554 Off a, lo, hi;
555 int n, i;
556 Iobuf *p;
557 Fbuf *fb;
558
559 strcpy(name, "free list");
560 print("check %s\n", name);
561 fb = &sb->fbuf;
562 a = sbaddr;
563 p = 0;
564 lo = 0;
565 hi = 0;
566 for(;;) {
567 n = fb->nfree;
568 if(n < 0 || n > FEPERBUF) {
569 print("check: nfree bad %lld\n", (Wideoff)a);
570 break;
571 }
572 for(i=1; i<n; i++) {
573 a = fb->free[i];
574 if(a && !fmark(a)) {
575 if(!lo || lo > a)
576 lo = a;
577 if(!hi || hi < a)
578 hi = a;
579 }
580 }
581 a = fb->free[0];
582 if(!a)
583 break;
584 if(fmark(a))
585 break;
586 if(!lo || lo > a)
587 lo = a;
588 if(!hi || hi < a)
589 hi = a;
590 if(p)
591 putbuf(p);
592 p = xtag(a, Tfree, QPNONE);
593 if(!p)
594 break;
595 fb = (Fbuf*)p->iobuf;
596 }
597 if(p)
598 putbuf(p);
599 if (flags & Ctrim) {
600 fsize = hi--; /* fsize = hi + 1 */
601 sb->fsize = fsize;
602 mod++;
603 print("set fsize to %lld\n", (Wideoff)fsize);
604 }
605 print("lo = %lld; hi = %lld\n", (Wideoff)lo, (Wideoff)hi);
606 }
607
608 /*
609 * make freelist from scratch
610 */
611 static void
mkfreelist(Superb * sb)612 mkfreelist(Superb *sb)
613 {
614 Off a;
615 int i, b;
616
617 if(ronly) {
618 print("cant make freelist on ronly device\n");
619 return;
620 }
621 strcpy(name, "free list");
622 memset(&sb->fbuf, 0, sizeof(sb->fbuf));
623 sb->fbuf.free[0] = 0L;
624 sb->fbuf.nfree = 1;
625 sb->tfree = 0;
626 for(a=fsize-fstart-1; a >= 0; a--) {
627 i = a/8;
628 if(i < 0 || i >= sizabits)
629 continue;
630 b = 1 << (a&7);
631 if(abits[i] & b)
632 continue;
633 addfree(dev, fstart+a, sb);
634 }
635 print("%lld blocks free\n", (Wideoff)sb->tfree);
636 mod++;
637 }
638
639 static Dentry*
maked(Off a,int s,Off qpath)640 maked(Off a, int s, Off qpath)
641 {
642 Iobuf *p;
643 Dentry *d, *d1;
644
645 p = xtag(a, Tdir, qpath);
646 if(!p)
647 return 0;
648 d = getdir(p, s);
649 d1 = chkalloc(sizeof(Dentry));
650 memmove(d1, d, sizeof(Dentry));
651 putbuf(p);
652 return d1;
653 }
654
655 static void
modd(Off a,int s,Dentry * d1)656 modd(Off a, int s, Dentry *d1)
657 {
658 Iobuf *p;
659 Dentry *d;
660
661 if(!(flags & Cbad))
662 return;
663 p = getbuf(dev, a, Brd);
664 d = getdir(p, s);
665 if(!d) {
666 if(p)
667 putbuf(p);
668 return;
669 }
670 memmove(d, d1, sizeof(Dentry));
671 p->flags |= Bmod;
672 putbuf(p);
673 }
674
675 static void
xread(Off a,Off qpath)676 xread(Off a, Off qpath)
677 {
678 Iobuf *p;
679
680 p = xtag(a, Tfile, qpath);
681 if(p)
682 putbuf(p);
683 }
684
685 static Iobuf*
xtag(Off a,int tag,Off qpath)686 xtag(Off a, int tag, Off qpath)
687 {
688 Iobuf *p;
689
690 if(a == 0)
691 return 0;
692 p = getbuf(dev, a, Brd);
693 if(!p) {
694 print("check: \"%s\": xtag: p null\n", name);
695 if(flags & (Cream|Ctag)) {
696 p = getbuf(dev, a, Bmod);
697 if(p) {
698 memset(p->iobuf, 0, RBUFSIZE);
699 settag(p, tag, qpath);
700 mod++;
701 return p;
702 }
703 }
704 return 0;
705 }
706 if(checktag(p, tag, qpath)) {
707 print("check: \"%s\": xtag: checktag\n", name);
708 if(flags & (Cream|Ctag)) {
709 if(flags & Cream)
710 memset(p->iobuf, 0, RBUFSIZE);
711 settag(p, tag, qpath);
712 mod++;
713 return p;
714 }
715 return p;
716 }
717 return p;
718 }
719
720 static int
amark(Off a)721 amark(Off a)
722 {
723 Off i;
724 int b;
725
726 if(a < fstart || a >= fsize) {
727 if(a == 0)
728 return 0;
729 print("check: \"%s\": range %lld\n",
730 name, (Wideoff)a);
731 nbad++;
732 return 1;
733 }
734 a -= fstart;
735 i = a/8;
736 b = 1 << (a&7);
737 if(abits[i] & b) {
738 if(!ronly)
739 if(ndup < 10)
740 print("check: \"%s\": address dup %lld\n",
741 name, (Wideoff)fstart+a);
742 else if(ndup == 10)
743 print("...");
744 ndup++;
745 return 1;
746 }
747 abits[i] |= b;
748 nused++;
749 return 0;
750 }
751
752 static int
fmark(Off a)753 fmark(Off a)
754 {
755 Off i;
756 int b;
757
758 if(a < fstart || a >= fsize) {
759 print("check: \"%s\": range %lld\n",
760 name, (Wideoff)a);
761 nbad++;
762 return 1;
763 }
764 a -= fstart;
765 i = a/8;
766 b = 1 << (a&7);
767 if(abits[i] & b) {
768 print("check: \"%s\": address dup %lld\n",
769 name, (Wideoff)fstart+a);
770 nfdup++;
771 return 1;
772 }
773 abits[i] |= b;
774 nfree++;
775 return 0;
776 }
777
778 static int
ftest(Off a)779 ftest(Off a)
780 {
781 Off i;
782 int b;
783
784 if(a < fstart || a >= fsize)
785 return 1;
786 a -= fstart;
787 i = a/8;
788 b = 1 << (a&7);
789 if(abits[i] & b)
790 return 1;
791 abits[i] |= b;
792 return 0;
793 }
794
795 static void
missing(void)796 missing(void)
797 {
798 Off a, i;
799 int b, n;
800
801 n = 0;
802 for(a=fsize-fstart-1; a>=0; a--) {
803 i = a/8;
804 b = 1 << (a&7);
805 if(!(abits[i] & b)) {
806 print("missing: %lld\n", (Wideoff)fstart+a);
807 n++;
808 }
809 if(n > 10) {
810 print(" ...\n");
811 break;
812 }
813 }
814 }
815
816 static void
qmark(Off qpath)817 qmark(Off qpath)
818 {
819 int b;
820 Off i;
821
822 i = qpath/8;
823 b = 1 << (qpath&7);
824 if(i < 0 || i >= sizqbits) {
825 nqbad++;
826 if(nqbad < 20)
827 print("check: \"%s\": qid out of range %llux\n",
828 name, (Wideoff)qpath);
829 return;
830 }
831 if((qbits[i] & b) && !ronly) {
832 nqbad++;
833 if(nqbad < 20)
834 print("check: \"%s\": qid dup %llux\n", name,
835 (Wideoff)qpath);
836 }
837 qbits[i] |= b;
838 }
839