/* [<][>][^][v][top][bottom][index][help] */
DEFINITIONS
This source file includes following definitions.
- setbadness
- swapsb
- swapinode
- swapdir
- swapindir
- swapbits
- domalloc
- bitmap_init
- blockusagestr
- bitmap_mark
- countbits
- reportbits
- check_bitmap
- addmemory
- remember_dir
- observe_filelink
- adjust_filelinks
- checknullstring
- checkbadstring
- check_sb
- check_indirect_block
- check_inode_blocks
- ibmap
- dobmap
- dirread
- dirwrite
- dirsortfunc
- qsort
- sortdir
- dir_tryadd
- check_dir_entry
- check_dir
- check_root_dir
- main
1 /*
2 * Copyright (c) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2009
3 * The President and Fellows of Harvard College.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE UNIVERSITY AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE UNIVERSITY OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30 #include <sys/types.h>
31 #include <assert.h>
32 #include <limits.h>
33 #include <stdint.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37 #include <err.h>
38
39 #include "support.h"
40 #include "kern/sfs.h"
41
42 #ifdef HOST
43 #include <netinet/in.h> // for arpa/inet.h
44 #include <arpa/inet.h> // for ntohl
45 #include "hostcompat.h"
46 #define SWAPL(x) ntohl(x)
47 #define SWAPS(x) ntohs(x)
48
49 #else
50
51 #define SWAPL(x) (x)
52 #define SWAPS(x) (x)
53 #define NO_REALLOC
54 #define NO_QSORT
55
56 #endif
57
58 #include "disk.h"
59
60
61 #define EXIT_USAGE 4
62 #define EXIT_FATAL 3
63 #define EXIT_UNRECOV 2
64 #define EXIT_RECOV 1
65 #define EXIT_CLEAN 0
66
67 static int badness=0;
68
69 static
70 void
71 setbadness(int code)
72 {
73 if (badness < code) {
74 badness = code;
75 }
76 }
77
78 ////////////////////////////////////////////////////////////
79
80 static
81 void
82 swapsb(struct sfs_super *sp)
83 {
84 sp->sp_magic = SWAPL(sp->sp_magic);
85 sp->sp_nblocks = SWAPL(sp->sp_nblocks);
86 }
87
88 static
89 void
90 swapinode(struct sfs_inode *sfi)
91 {
92 int i;
93
94 sfi->sfi_size = SWAPL(sfi->sfi_size);
95 sfi->sfi_type = SWAPS(sfi->sfi_type);
96 sfi->sfi_linkcount = SWAPS(sfi->sfi_linkcount);
97
98 for (i=0; i<SFS_NDIRECT; i++) {
99 sfi->sfi_direct[i] = SWAPL(sfi->sfi_direct[i]);
100 }
101
102 #ifdef SFS_NIDIRECT
103 for (i=0; i<SFS_NIDIRECT; i++) {
104 sfi->sfi_indirect[i] = SWAPL(sfi->sfi_indirect[i]);
105 }
106 #else
107 sfi->sfi_indirect = SWAPL(sfi->sfi_indirect);
108 #endif
109
110 #ifdef SFS_NDIDIRECT
111 for (i=0; i<SFS_NDIDIRECT; i++) {
112 sfi->sfi_dindirect[i] = SWAPL(sfi->sfi_dindirect[i]);
113 }
114 #else
115 #ifdef HAS_DIDIRECT
116 sfi->sfi_dindirect = SWAPL(sfi->sfi_dindirect);
117 #endif
118 #endif
119
120 #ifdef SFS_NTIDIRECT
121 for (i=0; i<SFS_NTIDIRECT; i++) {
122 sfi->sfi_tindirect[i] = SWAPL(sfi->sfi_tindirect[i]);
123 }
124 #else
125 #ifdef HAS_TIDIRECT
126 sfi->sfi_tindirect = SWAPL(sfi->sfi_tindirect);
127 #endif
128 #endif
129 }
130
131 static
132 void
133 swapdir(struct sfs_dir *sfd)
134 {
135 sfd->sfd_ino = SWAPL(sfd->sfd_ino);
136 }
137
138 static
139 void
140 swapindir(uint32_t *entries)
141 {
142 int i;
143 for (i=0; i<SFS_DBPERIDB; i++) {
144 entries[i] = SWAPL(entries[i]);
145 }
146 }
147
148 static
149 void
150 swapbits(uint8_t *bits)
151 {
152 /* nothing to do */
153 (void)bits;
154 }
155
156 ////////////////////////////////////////////////////////////
157
158 static
159 void *
160 domalloc(size_t len)
161 {
162 void *x;
163 x = malloc(len);
164 if (x==NULL) {
165 errx(EXIT_FATAL, "Out of memory");
166 }
167 return x;
168 }
169
170 ////////////////////////////////////////////////////////////
171
172 typedef enum {
173 B_SUPERBLOCK, /* Block that is the superblock */
174 B_BITBLOCK, /* Block used by free-block bitmap */
175 B_INODE, /* Block that is an inode */
176 B_IBLOCK, /* Indirect (or doubly-indirect etc.) block */
177 B_DIRDATA, /* Data block of a directory */
178 B_DATA, /* Data block */
179 B_TOFREE, /* Block that was used but we are releasing */
180 B_PASTEND, /* Block off the end of the fs */
181 } blockusage_t;
182
183 static uint32_t nblocks, bitblocks;
184 static uint32_t uniquecounter = 1;
185
186 static unsigned long count_blocks=0, count_dirs=0, count_files=0;
187
188 ////////////////////////////////////////////////////////////
189
190 static uint8_t *bitmapdata;
191 static uint8_t *tofreedata;
192
193 static
194 void
195 bitmap_init(uint32_t bitblocks)
196 {
197 size_t i, mapsize = bitblocks * SFS_BLOCKSIZE;
198 bitmapdata = domalloc(mapsize * sizeof(uint8_t));
199 tofreedata = domalloc(mapsize * sizeof(uint8_t));
200 for (i=0; i<mapsize; i++) {
201 bitmapdata[i] = tofreedata[i] = 0;
202 }
203 }
204
205 static
206 const char *
207 blockusagestr(blockusage_t how, uint32_t howdesc)
208 {
209 static char rv[256];
210 switch (how) {
211 case B_SUPERBLOCK: return "superblock";
212 case B_BITBLOCK: return "bitmap block";
213 case B_INODE: return "inode";
214 case B_IBLOCK:
215 snprintf(rv, sizeof(rv), "indirect block of inode %lu",
216 (unsigned long) howdesc);
217 break;
218 case B_DIRDATA:
219 snprintf(rv, sizeof(rv), "directory data from inode %lu",
220 (unsigned long) howdesc);
221 break;
222 case B_DATA:
223 snprintf(rv, sizeof(rv), "file data from inode %lu",
224 (unsigned long) howdesc);
225 break;
226 case B_TOFREE:
227 assert(0);
228 break;
229 case B_PASTEND:
230 return "past the end of the fs";
231 }
232 return rv;
233 }
234
235 static
236 void
237 bitmap_mark(uint32_t block, blockusage_t how, uint32_t howdesc)
238 {
239 unsigned index = block/8;
240 uint8_t mask = ((uint8_t)1)<<(block%8);
241
242 if (how == B_TOFREE) {
243 if (tofreedata[index] & mask) {
244 /* already marked to free once, ignore */
245 return;
246 }
247 if (bitmapdata[index] & mask) {
248 /* block is used elsewhere, ignore */
249 return;
250 }
251 tofreedata[index] |= mask;
252 return;
253 }
254
255 if (tofreedata[index] & mask) {
256 /* really using the block, don't free it */
257 tofreedata[index] &= ~mask;
258 }
259
260 if (bitmapdata[index] & mask) {
261 warnx("Block %lu (used as %s) already in use! (NOT FIXED)",
262 (unsigned long) block, blockusagestr(how, howdesc));
263 setbadness(EXIT_UNRECOV);
264 }
265
266 bitmapdata[index] |= mask;
267
268 if (how != B_PASTEND) {
269 count_blocks++;
270 }
271 }
272
273 static
274 int
275 countbits(uint8_t val)
276 {
277 uint8_t x;
278 int ct=0;
279
280 for (x=1; x; x<<=1) {
281 if (val & x) ct++;
282 }
283 return ct;
284 }
285
286 static
287 void
288 reportbits(uint32_t bitblock, uint32_t byte, uint8_t val, const char *what)
289 {
290 uint8_t x, y;
291 uint32_t blocknum;
292
293 for (x=1, y=0; x; x<<=1, y++) {
294 if (val & x) {
295 blocknum = bitblock*SFS_BLOCKBITS + byte*CHAR_BIT + y;
296 warnx("Block %lu erroneously shown %s in bitmap",
297 (unsigned long) blocknum, what);
298 }
299 }
300 }
301
302 static
303 void
304 check_bitmap(void)
305 {
306 uint8_t bits[SFS_BLOCKSIZE], *found, *tofree, tmp;
307 uint32_t alloccount=0, freecount=0, i, j;
308 int bchanged;
309
310 for (i=0; i<bitblocks; i++) {
311 diskread(bits, SFS_MAP_LOCATION+i);
312 swapbits(bits);
313 found = bitmapdata + i*SFS_BLOCKSIZE;
314 tofree = tofreedata + i*SFS_BLOCKSIZE;
315 bchanged = 0;
316
317 for (j=0; j<SFS_BLOCKSIZE; j++) {
318 /* we shouldn't have blocks marked both ways */
319 assert((found[j] & tofree[j])==0);
320
321 if (bits[j]==found[j]) {
322 continue;
323 }
324
325 if (bits[j]==(found[j] | tofree[j])) {
326 bits[j] = found[j];
327 bchanged = 1;
328 continue;
329 }
330
331 /* free the ones we're freeing */
332 bits[j] &= ~tofree[j];
333
334 /* are we short any? */
335 if ((bits[j] & found[j]) != found[j]) {
336 tmp = found[j] & ~bits[j];
337 alloccount += countbits(tmp);
338 if (tmp != 0) {
339 reportbits(i, j, tmp, "free");
340 }
341 }
342
343 /* do we have any extra? */
344 if ((bits[j] & found[j]) != bits[j]) {
345 tmp = bits[j] & ~found[j];
346 freecount += countbits(tmp);
347 if (tmp != 0) {
348 reportbits(i, j, tmp, "allocated");
349 }
350 }
351
352 bits[j] = found[j];
353 bchanged = 1;
354 }
355
356 if (bchanged) {
357 swapbits(bits);
358 diskwrite(bits, SFS_MAP_LOCATION+i);
359 }
360 }
361
362 if (alloccount > 0) {
363 warnx("%lu blocks erroneously shown free in bitmap (fixed)",
364 (unsigned long) alloccount);
365 setbadness(EXIT_RECOV);
366 }
367 if (freecount > 0) {
368 warnx("%lu blocks erroneously shown used in bitmap (fixed)",
369 (unsigned long) freecount);
370 setbadness(EXIT_RECOV);
371 }
372 }
373
374 ////////////////////////////////////////////////////////////
375
376 struct inodememory {
377 uint32_t ino;
378 uint32_t linkcount; /* files only; 0 for dirs */
379 };
380
381 static struct inodememory *inodes = NULL;
382 static int ninodes=0, maxinodes=0;
383
384 static
385 void
386 addmemory(uint32_t ino, uint32_t linkcount)
387 {
388 assert(ninodes <= maxinodes);
389 if (ninodes == maxinodes) {
390 #ifdef NO_REALLOC
391 int newmax = (maxinodes+1)*2;
392 void *p = domalloc(newmax * sizeof(struct inodememory));
393 if (inodes) {
394 memcpy(p, inodes, ninodes);
395 free(inodes);
396 }
397 inodes = p;
398 #else
399 maxinodes = (maxinodes+1)*2;
400 inodes = realloc(inodes, maxinodes * sizeof(uint32_t));
401 if (inodes==NULL) {
402 errx(EXIT_FATAL, "Out of memory");
403 }
404 #endif
405 }
406 inodes[ninodes].ino = ino;
407 inodes[ninodes].linkcount = linkcount;
408 }
409
410 /* returns nonzero if directory already remembered */
411 static
412 int
413 remember_dir(uint32_t ino, const char *pathsofar)
414 {
415 int i;
416
417 /* don't use this for now */
418 (void)pathsofar;
419
420 for (i=0; i<ninodes; i++) {
421 if (inodes[i].ino==ino) {
422 assert(inodes[i].linkcount==0);
423 return 1;
424 }
425 }
426
427 addmemory(ino, 0);
428
429 return 0;
430 }
431
432 static
433 void
434 observe_filelink(uint32_t ino)
435 {
436 int i;
437 for (i=0; i<ninodes; i++) {
438 if (inodes[i].ino==ino) {
439 assert(inodes[i].linkcount>0);
440 inodes[i].linkcount++;
441 return;
442 }
443 }
444 bitmap_mark(ino, B_INODE, ino);
445 addmemory(ino, 1);
446 }
447
448 static
449 void
450 adjust_filelinks(void)
451 {
452 struct sfs_inode sfi;
453 int i;
454
455 for (i=0; i<ninodes; i++) {
456 if (inodes[i].linkcount==0) {
457 /* directory */
458 continue;
459 }
460 diskread(&sfi, inodes[i].ino);
461 swapinode(&sfi);
462 assert(sfi.sfi_type == SFS_TYPE_FILE);
463 if (sfi.sfi_linkcount != inodes[i].linkcount) {
464 warnx("File %lu link count %lu should be %lu (fixed)",
465 (unsigned long) inodes[i].ino,
466 (unsigned long) sfi.sfi_linkcount,
467 (unsigned long) inodes[i].linkcount);
468 sfi.sfi_linkcount = inodes[i].linkcount;
469 setbadness(EXIT_RECOV);
470 swapinode(&sfi);
471 diskwrite(&sfi, inodes[i].ino);
472 }
473 count_files++;
474 }
475 }
476
477 ////////////////////////////////////////////////////////////
478
479 static
480 int
481 checknullstring(char *buf, size_t maxlen)
482 {
483 size_t i;
484 for (i=0; i<maxlen; i++) {
485 if (buf[i]==0) {
486 return 0;
487 }
488 }
489 buf[maxlen-1] = 0;
490 return 1;
491 }
492
493 static
494 int
495 checkbadstring(char *buf)
496 {
497 size_t i;
498 int rv=0;
499
500 for (i=0; buf[i]; i++) {
501 if (buf[i]==':' || buf[i]=='/') {
502 buf[i] = '_';
503 rv = 1;
504 }
505 }
506 return rv;
507 }
508
509 ////////////////////////////////////////////////////////////
510
511 static
512 void
513 check_sb(void)
514 {
515 struct sfs_super sp;
516 uint32_t i;
517 int schanged=0;
518
519 diskread(&sp, SFS_SB_LOCATION);
520 swapsb(&sp);
521 if (sp.sp_magic != SFS_MAGIC) {
522 errx(EXIT_UNRECOV, "Not an sfs filesystem");
523 }
524
525 assert(nblocks==0);
526 assert(bitblocks==0);
527 nblocks = sp.sp_nblocks;
528 bitblocks = SFS_BITBLOCKS(nblocks);
529 assert(nblocks>0);
530 assert(bitblocks>0);
531
532 bitmap_init(bitblocks);
533 for (i=nblocks; i<bitblocks*SFS_BLOCKBITS; i++) {
534 bitmap_mark(i, B_PASTEND, 0);
535 }
536
537 if (checknullstring(sp.sp_volname, sizeof(sp.sp_volname))) {
538 warnx("Volume name not null-terminated (fixed)");
539 setbadness(EXIT_RECOV);
540 schanged = 1;
541 }
542 if (checkbadstring(sp.sp_volname)) {
543 warnx("Volume name contains illegal characters (fixed)");
544 setbadness(EXIT_RECOV);
545 schanged = 1;
546 }
547
548 if (schanged) {
549 swapsb(&sp);
550 diskwrite(&sp, SFS_SB_LOCATION);
551 }
552
553 bitmap_mark(SFS_SB_LOCATION, B_SUPERBLOCK, 0);
554 for (i=0; i<bitblocks; i++) {
555 bitmap_mark(SFS_MAP_LOCATION+i, B_BITBLOCK, i);
556 }
557 }
558
559 ////////////////////////////////////////////////////////////
560
561 static
562 void
563 check_indirect_block(uint32_t ino, uint32_t *ientry, uint32_t *blockp,
564 uint32_t nblocks, uint32_t *badcountp,
565 int isdir, int indirection)
566 {
567 uint32_t entries[SFS_DBPERIDB];
568 uint32_t i, ct;
569
570 if (*ientry !=0) {
571 diskread(entries, *ientry);
572 swapindir(entries);
573 bitmap_mark(*ientry, B_IBLOCK, ino);
574 }
575 else {
576 for (i=0; i<SFS_DBPERIDB; i++) {
577 entries[i] = 0;
578 }
579 }
580
581 if (indirection > 1) {
582 for (i=0; i<SFS_DBPERIDB; i++) {
583 check_indirect_block(ino, &entries[i],
584 blockp, nblocks,
585 badcountp,
586 isdir,
587 indirection-1);
588 }
589 }
590 else {
591 assert(indirection==1);
592
593 for (i=0; i<SFS_DBPERIDB; i++) {
594 if (*blockp < nblocks) {
595 if (entries[i] != 0) {
596 bitmap_mark(entries[i],
597 isdir ? B_DIRDATA : B_DATA,
598 ino);
599 }
600 }
601 else {
602 if (entries[i] != 0) {
603 (*badcountp)++;
604 bitmap_mark(entries[i],
605 isdir ? B_DIRDATA : B_DATA,
606 ino);
607 entries[i] = 0;
608 }
609 }
610 (*blockp)++;
611 }
612 }
613
614 ct=0;
615 for (i=ct=0; i<SFS_DBPERIDB; i++) {
616 if (entries[i]!=0) ct++;
617 }
618 if (ct==0) {
619 if (*ientry != 0) {
620 (*badcountp)++;
621 bitmap_mark(*ientry, B_TOFREE, 0);
622 *ientry = 0;
623 }
624 }
625 else {
626 assert(*ientry != 0);
627 if (*badcountp > 0) {
628 swapindir(entries);
629 diskwrite(entries, *ientry);
630 }
631 }
632 }
633
634 /* returns nonzero if inode modified */
635 static
636 int
637 check_inode_blocks(uint32_t ino, struct sfs_inode *sfi, int isdir)
638 {
639 uint32_t size, block, nblocks, badcount;
640
641 badcount = 0;
642
643 size = SFS_ROUNDUP(sfi->sfi_size, SFS_BLOCKSIZE);
644 nblocks = size/SFS_BLOCKSIZE;
645
646 for (block=0; block<SFS_NDIRECT; block++) {
647 if (block < nblocks) {
648 if (sfi->sfi_direct[block] != 0) {
649 bitmap_mark(sfi->sfi_direct[block],
650 isdir ? B_DIRDATA : B_DATA, ino);
651 }
652 }
653 else {
654 if (sfi->sfi_direct[block] != 0) {
655 badcount++;
656 bitmap_mark(sfi->sfi_direct[block],
657 B_TOFREE, 0);
658 }
659 }
660 }
661
662 #ifdef SFS_NIDIRECT
663 for (i=0; i<SFS_NIDIRECT; i++) {
664 check_indirect_block(ino, &sfi->sfi_indirect[i],
665 &block, nblocks, &badcount, isdir, 1);
666 }
667 #else
668 check_indirect_block(ino, &sfi->sfi_indirect,
669 &block, nblocks, &badcount, isdir, 1);
670 #endif
671
672 #ifdef SFS_NDIDIRECT
673 for (i=0; i<SFS_NDIDIRECT; i++) {
674 check_indirect_block(ino, &sfi->sfi_dindirect[i],
675 &block, nblocks, &badcount, isdir, 2);
676 }
677 #else
678 #ifdef HAS_DIDIRECT
679 check_indirect_block(ino, &sfi->sfi_dindirect,
680 &block, nblocks, &badcount, isdir, 2);
681 #endif
682 #endif
683
684 #ifdef SFS_NTIDIRECT
685 for (i=0; i<SFS_NTIDIRECT; i++) {
686 check_indirect_block(ino, &sfi->sfi_tindirect[i],
687 &block, nblocks, &badcount, isdir, 3);
688 }
689 #else
690 #ifdef HAS_TIDIRECT
691 check_indirect_block(ino, &sfi->sfi_tindirect,
692 &block, nblocks, &badcount, isdir, 3);
693 #endif
694 #endif
695
696 if (badcount > 0) {
697 warnx("Inode %lu: %lu blocks after EOF (freed)",
698 (unsigned long) ino, (unsigned long) badcount);
699 setbadness(EXIT_RECOV);
700 return 1;
701 }
702
703 return 0;
704 }
705
706 ////////////////////////////////////////////////////////////
707
708 static
709 uint32_t
710 ibmap(uint32_t iblock, uint32_t offset, uint32_t entrysize)
711 {
712 uint32_t entries[SFS_DBPERIDB];
713
714 if (iblock == 0) {
715 return 0;
716 }
717
718 diskread(entries, iblock);
719 swapindir(entries);
720
721 if (entrysize > 1) {
722 uint32_t index = offset / entrysize;
723 offset %= entrysize;
724 return ibmap(entries[index], offset, entrysize/SFS_DBPERIDB);
725 }
726 else {
727 assert(offset < SFS_DBPERIDB);
728 return entries[offset];
729 }
730 }
731
732 #define BMAP_ND SFS_NDIRECT
733 #define BMAP_D(sfi, x) ((sfi)->sfi_direct[(x)])
734
735 #ifdef SFS_NIDIRECT
736 #define BMAP_NI SFS_NIDIRECT
737 #define BMAP_I(sfi, x) ((sfi)->sfi_indirect[(x)])
738 #else
739 #define BMAP_NI 1
740 #define BMAP_I(sfi, x) ((void)(x), (sfi)->sfi_indirect)
741 #endif
742
743 #ifdef SFS_NDIDIRECT
744 #define BMAP_NII SFS_NDIDIRECT
745 #define BMAP_II(sfi, x) ((sfi)->sfi_dindirect[(x)])
746 #else
747 #ifdef HAS_DIDIRECT
748 #define BMAP_NII 1
749 #define BMAP_II(sfi, x) ((void)(x), (sfi)->sfi_dindirect)
750 #else
751 #define BMAP_NII 0
752 #define BMAP_II(sfi, x) ((void)(x), (void)(sfi), 0)
753 #endif
754 #endif
755
756 #ifdef SFS_NTIDIRECT
757 #define BMAP_NIII SFS_NTIDIRECT
758 #define BMAP_III(sfi, x) ((sfi)->sfi_tindirect[(x)])
759 #else
760 #ifdef HAS_TIDIRECT
761 #define BMAP_NIII 1
762 #define BMAP_III(sfi, x) ((void)(x), (sfi)->sfi_tindirect)
763 #else
764 #define BMAP_NIII 0
765 #define BMAP_III(sfi, x) ((void)(x), (void)(sfi), 0)
766 #endif
767 #endif
768
769 #define BMAP_DMAX BMAP_ND
770 #define BMAP_IMAX (BMAP_DMAX+SFS_DBPERIDB*BMAP_NI)
771 #define BMAP_IIMAX (BMAP_IMAX+SFS_DBPERIDB*BMAP_NII)
772 #define BMAP_IIIMAX (BMAP_IIMAX+SFS_DBPERIDB*BMAP_NIII)
773
774 #define BMAP_DSIZE 1
775 #define BMAP_ISIZE (BMAP_DSIZE*SFS_DBPERIDB)
776 #define BMAP_IISIZE (BMAP_ISIZE*SFS_DBPERIDB)
777 #define BMAP_IIISIZE (BMAP_IISIZE*SFS_DBPERIDB)
778
779 static
780 uint32_t
781 dobmap(const struct sfs_inode *sfi, uint32_t fileblock)
782 {
783 uint32_t iblock, offset;
784
785 if (fileblock < BMAP_DMAX) {
786 return BMAP_D(sfi, fileblock);
787 }
788 else if (fileblock < BMAP_IMAX) {
789 iblock = (fileblock - BMAP_DMAX)/BMAP_ISIZE;
790 offset = (fileblock - BMAP_DMAX)%BMAP_ISIZE;
791 return ibmap(BMAP_I(sfi, iblock), offset, BMAP_DSIZE);
792 }
793 else if (fileblock < BMAP_IIMAX) {
794 iblock = (fileblock - BMAP_IMAX)/BMAP_IISIZE;
795 offset = (fileblock - BMAP_IMAX)%BMAP_IISIZE;
796 return ibmap(BMAP_II(sfi, iblock), offset, BMAP_ISIZE);
797 }
798 else if (fileblock < BMAP_IIIMAX) {
799 iblock = (fileblock - BMAP_IIMAX)/BMAP_IIISIZE;
800 offset = (fileblock - BMAP_IIMAX)%BMAP_IIISIZE;
801 return ibmap(BMAP_III(sfi, iblock), offset, BMAP_IISIZE);
802 }
803 return 0;
804 }
805
806 static
807 void
808 dirread(struct sfs_inode *sfi, struct sfs_dir *d, unsigned nd)
809 {
810 const unsigned atonce = SFS_BLOCKSIZE/sizeof(struct sfs_dir);
811 unsigned nblocks = SFS_ROUNDUP(nd, atonce) / atonce;
812 unsigned i, j;
813
814 for (i=0; i<nblocks; i++) {
815 uint32_t block = dobmap(sfi, i);
816 if (block!=0) {
817 diskread(d + i*atonce, block);
818 for (j=0; j<atonce; j++) {
819 swapdir(&d[i*atonce+j]);
820 }
821 }
822 else {
823 warnx("Warning: sparse directory found");
824 bzero(d + i*atonce, SFS_BLOCKSIZE);
825 }
826 }
827 }
828
829 static
830 void
831 dirwrite(const struct sfs_inode *sfi, struct sfs_dir *d, int nd)
832 {
833 const unsigned atonce = SFS_BLOCKSIZE/sizeof(struct sfs_dir);
834 unsigned nblocks = SFS_ROUNDUP(nd, atonce) / atonce;
835 unsigned i, j, bad;
836
837 for (i=0; i<nblocks; i++) {
838 uint32_t block = dobmap(sfi, i);
839 if (block!=0) {
840 for (j=0; j<atonce; j++) {
841 swapdir(&d[i*atonce+j]);
842 }
843 diskwrite(d + i*atonce, block);
844 }
845 else {
846 for (j=bad=0; j<atonce; j++) {
847 if (d[i*atonce+j].sfd_ino != SFS_NOINO ||
848 d[i*atonce+j].sfd_name[0] != 0) {
849 bad = 1;
850 }
851 }
852 if (bad) {
853 warnx("Cannot write to missing block in "
854 "sparse directory (ERROR)");
855 setbadness(EXIT_UNRECOV);
856 }
857 }
858 }
859 }
860
861 ////////////////////////////////////////////////////////////
862
863 static struct sfs_dir *global_sortdirs;
864 static
865 int
866 dirsortfunc(const void *aa, const void *bb)
867 {
868 const int *a = (const int *)aa;
869 const int *b = (const int *)bb;
870 const struct sfs_dir *ad = &global_sortdirs[*a];
871 const struct sfs_dir *bd = &global_sortdirs[*b];
872 return strcmp(ad->sfd_name, bd->sfd_name);
873 }
874
875 #ifdef NO_QSORT
876 static
877 void
878 qsort(int *data, int num, size_t size, int (*f)(const void *, const void *))
879 {
880 int i, j;
881 (void)size;
882
883 /* because I'm lazy, bubble sort */
884 for (i=0; i<num-1; i++) {
885 for (j=i+1; j<num; j++) {
886 if (f(&data[i], &data[j]) < 0) {
887 int tmp = data[i];
888 data[i] = data[j];
889 data[j] = tmp;
890 }
891 }
892 }
893 }
894 #endif
895
896 static
897 void
898 sortdir(int *vector, struct sfs_dir *d, int nd)
899 {
900 global_sortdirs = d;
901 qsort(vector, nd, sizeof(int), dirsortfunc);
902 }
903
904 /* tries to add a directory entry; returns 0 on success */
905 static
906 int
907 dir_tryadd(struct sfs_dir *d, int nd, const char *name, uint32_t ino)
908 {
909 int i;
910 for (i=0; i<nd; i++) {
911 if (d[i].sfd_ino==SFS_NOINO) {
912 d[i].sfd_ino = ino;
913 assert(strlen(name) < sizeof(d[i].sfd_name));
914 strcpy(d[i].sfd_name, name);
915 return 0;
916 }
917 }
918 return -1;
919 }
920
921 static
922 int
923 check_dir_entry(const char *pathsofar, uint32_t index, struct sfs_dir *sfd)
924 {
925 int dchanged = 0;
926
927 if (sfd->sfd_ino == SFS_NOINO) {
928 if (sfd->sfd_name[0] != 0) {
929 setbadness(EXIT_RECOV);
930 warnx("Directory /%s entry %lu has name but no file",
931 pathsofar, (unsigned long) index);
932 sfd->sfd_name[0] = 0;
933 dchanged = 1;
934 }
935 }
936 else {
937 if (sfd->sfd_name[0] == 0) {
938 snprintf(sfd->sfd_name, sizeof(sfd->sfd_name),
939 "FSCK.%lu.%lu",
940 (unsigned long) sfd->sfd_ino,
941 (unsigned long) uniquecounter++);
942 setbadness(EXIT_RECOV);
943 warnx("Directory /%s entry %lu has file but "
944 "no name (fixed: %s)",
945 pathsofar, (unsigned long) index,
946 sfd->sfd_name);
947 dchanged = 1;
948 }
949 if (checknullstring(sfd->sfd_name, sizeof(sfd->sfd_name))) {
950 setbadness(EXIT_RECOV);
951 warnx("Directory /%s entry %lu not "
952 "null-terminated (fixed)",
953 pathsofar, (unsigned long) index);
954 dchanged = 1;
955 }
956 if (checkbadstring(sfd->sfd_name)) {
957 setbadness(EXIT_RECOV);
958 warnx("Directory /%s entry %lu contains invalid "
959 "characters (fixed)",
960 pathsofar, (unsigned long) index);
961 dchanged = 1;
962 }
963 }
964 return dchanged;
965 }
966
967 ////////////////////////////////////////////////////////////
968
969 static
970 int
971 check_dir(uint32_t ino, uint32_t parentino, const char *pathsofar)
972 {
973 struct sfs_inode sfi;
974 struct sfs_dir *direntries;
975 int *sortvector;
976 uint32_t dirsize, ndirentries, maxdirentries, subdircount, i;
977 int ichanged=0, dchanged=0, dotseen=0, dotdotseen=0;
978
979 diskread(&sfi, ino);
980 swapinode(&sfi);
981
982 if (remember_dir(ino, pathsofar)) {
983 /* crosslinked dir */
984 return 1;
985 }
986
987 bitmap_mark(ino, B_INODE, ino);
988 count_dirs++;
989
990 if (sfi.sfi_size % sizeof(struct sfs_dir) != 0) {
991 setbadness(EXIT_RECOV);
992 warnx("Directory /%s has illegal size %lu (fixed)",
993 pathsofar, (unsigned long) sfi.sfi_size);
994 sfi.sfi_size = SFS_ROUNDUP(sfi.sfi_size,
995 sizeof(struct sfs_dir));
996 ichanged = 1;
997 }
998
999 if (check_inode_blocks(ino, &sfi, 1)) {
1000 ichanged = 1;
1001 }
1002
1003 ndirentries = sfi.sfi_size/sizeof(struct sfs_dir);
1004 maxdirentries = SFS_ROUNDUP(ndirentries,
1005 SFS_BLOCKSIZE/sizeof(struct sfs_dir));
1006 dirsize = maxdirentries * sizeof(struct sfs_dir);
1007 direntries = domalloc(dirsize);
1008 sortvector = domalloc(ndirentries * sizeof(int));
1009
1010 dirread(&sfi, direntries, ndirentries);
1011 for (i=ndirentries; i<maxdirentries; i++) {
1012 direntries[i].sfd_ino = SFS_NOINO;
1013 bzero(direntries[i].sfd_name, sizeof(direntries[i].sfd_name));
1014 }
1015
1016 for (i=0; i<ndirentries; i++) {
1017 if (check_dir_entry(pathsofar, i, &direntries[i])) {
1018 dchanged = 1;
1019 }
1020 sortvector[i] = i;
1021 }
1022
1023 sortdir(sortvector, direntries, ndirentries);
1024
1025 /* don't use ndirentries-1 here in case ndirentries == 0 */
1026 for (i=0; i+1<ndirentries; i++) {
1027 struct sfs_dir *d1 = &direntries[sortvector[i]];
1028 struct sfs_dir *d2 = &direntries[sortvector[i+1]];
1029 assert(d1 != d2);
1030
1031 if (d1->sfd_ino == SFS_NOINO) {
1032 continue;
1033 }
1034
1035 if (!strcmp(d1->sfd_name, d2->sfd_name)) {
1036 if (d1->sfd_ino == d2->sfd_ino) {
1037 setbadness(EXIT_RECOV);
1038 warnx("Directory /%s: Duplicate entries for "
1039 "%s (merged)",
1040 pathsofar, d1->sfd_name);
1041 d1->sfd_ino = SFS_NOINO;
1042 d1->sfd_name[0] = 0;
1043 }
1044 else {
1045 snprintf(d1->sfd_name, sizeof(d1->sfd_name),
1046 "FSCK.%lu.%lu",
1047 (unsigned long) d1->sfd_ino,
1048 (unsigned long) uniquecounter++);
1049 setbadness(EXIT_RECOV);
1050 warnx("Directory /%s: Duplicate names %s "
1051 "(one renamed: %s)",
1052 pathsofar, d2->sfd_name, d1->sfd_name);
1053 }
1054 dchanged = 1;
1055 }
1056 }
1057
1058 for (i=0; i<ndirentries; i++) {
1059 if (!strcmp(direntries[i].sfd_name, ".")) {
1060 if (direntries[i].sfd_ino != ino) {
1061 setbadness(EXIT_RECOV);
1062 warnx("Directory /%s: Incorrect `.' entry "
1063 "(fixed)", pathsofar);
1064 direntries[i].sfd_ino = ino;
1065 dchanged = 1;
1066 }
1067 assert(dotseen==0); /* due to duplicate checking */
1068 dotseen = 1;
1069 }
1070 else if (!strcmp(direntries[i].sfd_name, "..")) {
1071 if (direntries[i].sfd_ino != parentino) {
1072 setbadness(EXIT_RECOV);
1073 warnx("Directory /%s: Incorrect `..' entry "
1074 "(fixed)", pathsofar);
1075 direntries[i].sfd_ino = parentino;
1076 dchanged = 1;
1077 }
1078 assert(dotdotseen==0); /* due to duplicate checking */
1079 dotdotseen = 1;
1080 }
1081 }
1082
1083 if (!dotseen) {
1084 if (dir_tryadd(direntries, ndirentries, ".", ino)==0) {
1085 setbadness(EXIT_RECOV);
1086 warnx("Directory /%s: No `.' entry (added)",
1087 pathsofar);
1088 dchanged = 1;
1089 }
1090 else if (dir_tryadd(direntries, maxdirentries, ".", ino)==0) {
1091 setbadness(EXIT_RECOV);
1092 warnx("Directory /%s: No `.' entry (added)",
1093 pathsofar);
1094 ndirentries++;
1095 dchanged = 1;
1096 sfi.sfi_size += sizeof(struct sfs_dir);
1097 ichanged = 1;
1098 }
1099 else {
1100 setbadness(EXIT_UNRECOV);
1101 warnx("Directory /%s: No `.' entry (NOT FIXED)",
1102 pathsofar);
1103 }
1104 }
1105
1106 if (!dotdotseen) {
1107 if (dir_tryadd(direntries, ndirentries, "..", parentino)==0) {
1108 setbadness(EXIT_RECOV);
1109 warnx("Directory /%s: No `..' entry (added)",
1110 pathsofar);
1111 dchanged = 1;
1112 }
1113 else if (dir_tryadd(direntries, maxdirentries, "..",
1114 parentino)==0) {
1115 setbadness(EXIT_RECOV);
1116 warnx("Directory /%s: No `..' entry (added)",
1117 pathsofar);
1118 ndirentries++;
1119 dchanged = 1;
1120 sfi.sfi_size += sizeof(struct sfs_dir);
1121 ichanged = 1;
1122 }
1123 else {
1124 setbadness(EXIT_UNRECOV);
1125 warnx("Directory /%s: No `..' entry (NOT FIXED)",
1126 pathsofar);
1127 }
1128 }
1129
1130 subdircount=0;
1131 for (i=0; i<ndirentries; i++) {
1132 if (!strcmp(direntries[i].sfd_name, ".")) {
1133 /* nothing */
1134 }
1135 else if (!strcmp(direntries[i].sfd_name, "..")) {
1136 /* nothing */
1137 }
1138 else if (direntries[i].sfd_ino == SFS_NOINO) {
1139 /* nothing */
1140 }
1141 else {
1142 char path[strlen(pathsofar)+SFS_NAMELEN+1];
1143 struct sfs_inode subsfi;
1144
1145 diskread(&subsfi, direntries[i].sfd_ino);
1146 swapinode(&subsfi);
1147 snprintf(path, sizeof(path), "%s/%s",
1148 pathsofar, direntries[i].sfd_name);
1149
1150 switch (subsfi.sfi_type) {
1151 case SFS_TYPE_FILE:
1152 if (check_inode_blocks(direntries[i].sfd_ino,
1153 &subsfi, 0)) {
1154 swapinode(&subsfi);
1155 diskwrite(&subsfi,
1156 direntries[i].sfd_ino);
1157 }
1158 observe_filelink(direntries[i].sfd_ino);
1159 break;
1160 case SFS_TYPE_DIR:
1161 if (check_dir(direntries[i].sfd_ino,
1162 ino,
1163 path)) {
1164 setbadness(EXIT_RECOV);
1165 warnx("Directory /%s: Crosslink to "
1166 "other directory (removed)",
1167 path);
1168 direntries[i].sfd_ino = SFS_NOINO;
1169 direntries[i].sfd_name[0] = 0;
1170 dchanged = 1;
1171 }
1172 else {
1173 subdircount++;
1174 }
1175 break;
1176 default:
1177 setbadness(EXIT_RECOV);
1178 warnx("Object /%s: Invalid inode type "
1179 "(removed)", path);
1180 direntries[i].sfd_ino = SFS_NOINO;
1181 direntries[i].sfd_name[0] = 0;
1182 dchanged = 1;
1183 break;
1184 }
1185 }
1186 }
1187
1188 if (sfi.sfi_linkcount != subdircount+2) {
1189 setbadness(EXIT_RECOV);
1190 warnx("Directory /%s: Link count %lu should be %lu (fixed)",
1191 pathsofar, (unsigned long) sfi.sfi_linkcount,
1192 (unsigned long) subdircount+2);
1193 sfi.sfi_linkcount = subdircount+2;
1194 ichanged = 1;
1195 }
1196
1197 if (dchanged) {
1198 dirwrite(&sfi, direntries, ndirentries);
1199 }
1200
1201 if (ichanged) {
1202 swapinode(&sfi);
1203 diskwrite(&sfi, ino);
1204 }
1205
1206 free(direntries);
1207 free(sortvector);
1208
1209 return 0;
1210 }
1211
1212
1213 static
1214 void
1215 check_root_dir(void)
1216 {
1217 struct sfs_inode sfi;
1218 diskread(&sfi, SFS_ROOT_LOCATION);
1219 swapinode(&sfi);
1220
1221 switch (sfi.sfi_type) {
1222 case SFS_TYPE_DIR:
1223 break;
1224 case SFS_TYPE_FILE:
1225 warnx("Root directory inode is a regular file (fixed)");
1226 goto fix;
1227 default:
1228 warnx("Root directory inode has invalid type %lu (fixed)",
1229 (unsigned long) sfi.sfi_type);
1230 fix:
1231 setbadness(EXIT_RECOV);
1232 sfi.sfi_type = SFS_TYPE_DIR;
1233 swapinode(&sfi);
1234 diskwrite(&sfi, SFS_ROOT_LOCATION);
1235 break;
1236 }
1237
1238 check_dir(SFS_ROOT_LOCATION, SFS_ROOT_LOCATION, "");
1239 }
1240
1241 ////////////////////////////////////////////////////////////
1242
1243 int
1244 main(int argc, char **argv)
1245 {
1246 #ifdef HOST
1247 hostcompat_init(argc, argv);
1248 #endif
1249
1250 if (argc!=2) {
1251 errx(EXIT_USAGE, "Usage: sfsck device/diskfile");
1252 }
1253
1254 assert(sizeof(struct sfs_super)==SFS_BLOCKSIZE);
1255 assert(sizeof(struct sfs_inode)==SFS_BLOCKSIZE);
1256 assert(SFS_BLOCKSIZE % sizeof(struct sfs_dir) == 0);
1257
1258 opendisk(argv[1]);
1259
1260 check_sb();
1261 check_root_dir();
1262 check_bitmap();
1263 adjust_filelinks();
1264
1265 closedisk();
1266
1267 warnx("%lu blocks used (of %lu); %lu directories; %lu files",
1268 count_blocks, (unsigned long) nblocks, count_dirs, count_files);
1269
1270 switch (badness) {
1271 case EXIT_USAGE:
1272 case EXIT_FATAL:
1273 default:
1274 /* not supposed to happen here */
1275 assert(0);
1276 break;
1277 case EXIT_UNRECOV:
1278 warnx("WARNING - unrecoverable errors. Maybe try again?");
1279 break;
1280 case EXIT_RECOV:
1281 warnx("Caution - filesystem modified. Run again for luck.");
1282 break;
1283 case EXIT_CLEAN:
1284 break;
1285 }
1286
1287 return badness;
1288 }