1 /* $NetBSD: pass1.c,v 1.19 2009/04/06 12:50:37 lukem Exp $ */ 2 3 /* 4 * Copyright (c) 1980, 1986, 1993 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. Neither the name of the University nor the names of its contributors 16 * may be used to endorse or promote products derived from this software 17 * without specific prior written permission. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32 /* 33 * Copyright (c) 1997 Manuel Bouyer. 34 * 35 * Redistribution and use in source and binary forms, with or without 36 * modification, are permitted provided that the following conditions 37 * are met: 38 * 1. Redistributions of source code must retain the above copyright 39 * notice, this list of conditions and the following disclaimer. 40 * 2. Redistributions in binary form must reproduce the above copyright 41 * notice, this list of conditions and the following disclaimer in the 42 * documentation and/or other materials provided with the distribution. 43 * 3. All advertising materials mentioning features or use of this software 44 * must display the following acknowledgement: 45 * This product includes software developed by Manuel Bouyer. 46 * 4. The name of the author may not be used to endorse or promote products 47 * derived from this software without specific prior written permission. 48 * 49 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 50 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 51 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 52 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 53 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 54 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 55 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 56 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 57 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 58 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 59 */ 60 61 #include <sys/cdefs.h> 62 #ifndef lint 63 #if 0 64 static char sccsid[] = "@(#)pass1.c 8.1 (Berkeley) 6/5/93"; 65 #else 66 __RCSID("$NetBSD: pass1.c,v 1.19 2009/04/06 12:50:37 lukem Exp $"); 67 #endif 68 #endif /* not lint */ 69 70 #include <sys/param.h> 71 #include <sys/time.h> 72 #include <ufs/ext2fs/ext2fs_dinode.h> 73 #include <ufs/ext2fs/ext2fs_dir.h> 74 #include <ufs/ext2fs/ext2fs.h> 75 76 #include <ufs/ufs/dinode.h> /* for IFMT & friends */ 77 78 #include <stdio.h> 79 #include <stdlib.h> 80 #include <string.h> 81 #include <time.h> 82 83 #include "fsck.h" 84 #include "extern.h" 85 #include "fsutil.h" 86 #include "exitvalues.h" 87 88 static daddr_t badblk; 89 static daddr_t dupblk; 90 static void checkinode(ino_t, struct inodesc *); 91 92 void 93 pass1(void) 94 { 95 ino_t inumber; 96 int c, i; 97 size_t j; 98 daddr_t dbase; 99 struct inodesc idesc; 100 101 /* 102 * Set file system reserved blocks in used block map. 103 */ 104 for (c = 0; c < sblock.e2fs_ncg; c++) { 105 dbase = c * sblock.e2fs.e2fs_bpg + 106 sblock.e2fs.e2fs_first_dblock; 107 /* Mark the blocks used for the inode table */ 108 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_i_tables) >= dbase) { 109 for (i = 0; i < sblock.e2fs_itpg; i++) 110 setbmap( 111 fs2h32(sblock.e2fs_gd[c].ext2bgd_i_tables) 112 + i); 113 } 114 /* Mark the blocks used for the block bitmap */ 115 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_b_bitmap) >= dbase) 116 setbmap(fs2h32(sblock.e2fs_gd[c].ext2bgd_b_bitmap)); 117 /* Mark the blocks used for the inode bitmap */ 118 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_i_bitmap) >= dbase) 119 setbmap(fs2h32(sblock.e2fs_gd[c].ext2bgd_i_bitmap)); 120 121 if (sblock.e2fs.e2fs_rev == E2FS_REV0 || 122 (sblock.e2fs.e2fs_features_rocompat & 123 EXT2F_ROCOMPAT_SPARSESUPER) == 0 || 124 cg_has_sb(c)) { 125 /* Mark copuy of SB and descriptors */ 126 setbmap(dbase); 127 for (i = 1; i <= sblock.e2fs_ngdb; i++) 128 setbmap(dbase+i); 129 } 130 131 132 if (c == 0) { 133 for(i = 0; i < dbase; i++) 134 setbmap(i); 135 } 136 } 137 138 /* 139 * Find all allocated blocks. 140 */ 141 memset(&idesc, 0, sizeof(struct inodesc)); 142 idesc.id_type = ADDR; 143 idesc.id_func = pass1check; 144 inumber = 1; 145 n_files = n_blks = 0; 146 resetinodebuf(); 147 for (c = 0; c < sblock.e2fs_ncg; c++) { 148 for (j = 0; 149 j < sblock.e2fs.e2fs_ipg && inumber <= sblock.e2fs.e2fs_icount; 150 j++, inumber++) { 151 if (inumber < EXT2_ROOTINO) /* XXX */ 152 continue; 153 checkinode(inumber, &idesc); 154 } 155 } 156 freeinodebuf(); 157 } 158 159 static void 160 checkinode(ino_t inumber, struct inodesc *idesc) 161 { 162 struct ext2fs_dinode *dp; 163 struct zlncnt *zlnp; 164 int ndb, j; 165 mode_t mode; 166 167 dp = getnextinode(inumber); 168 if (inumber < EXT2_FIRSTINO && 169 inumber != EXT2_ROOTINO && 170 !(inumber == EXT2_RESIZEINO && 171 (sblock.e2fs.e2fs_features_compat & EXT2F_COMPAT_RESIZE) != 0)) 172 return; 173 174 mode = fs2h16(dp->e2di_mode) & IFMT; 175 if (mode == 0 || (dp->e2di_dtime != 0 && dp->e2di_nlink == 0)) { 176 if (mode == 0 && ( 177 memcmp(dp->e2di_blocks, zino.e2di_blocks, 178 (NDADDR + NIADDR) * sizeof(u_int32_t)) || 179 dp->e2di_mode || inosize(dp))) { 180 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 181 (unsigned long long)inumber); 182 if (reply("CLEAR") == 1) { 183 dp = ginode(inumber); 184 clearinode(dp); 185 inodirty(); 186 } 187 } 188 #ifdef notyet /* it seems that dtime == 0 is valid for a unallocated inode */ 189 if (dp->e2di_dtime == 0) { 190 pwarn("DELETED INODE I=%llu HAS A NULL DTIME", 191 (unsigned long long)inumber); 192 if (preen) { 193 printf(" (CORRECTED)\n"); 194 } 195 if (preen || reply("CORRECT")) { 196 time_t t; 197 time(&t); 198 dp->e2di_dtime = h2fs32(t); 199 dp = ginode(inumber); 200 inodirty(); 201 } 202 } 203 #endif 204 statemap[inumber] = USTATE; 205 return; 206 } 207 lastino = inumber; 208 if (dp->e2di_dtime != 0) { 209 time_t t = fs2h32(dp->e2di_dtime); 210 char *p = ctime(&t); 211 pwarn("INODE I=%llu HAS DTIME=%12.12s %4.4s", 212 (unsigned long long)inumber, &p[4], &p[20]); 213 if (preen) { 214 printf(" (CORRECTED)\n"); 215 } 216 if (preen || reply("CORRECT")) { 217 dp = ginode(inumber); 218 dp->e2di_dtime = 0; 219 inodirty(); 220 } 221 } 222 if (inosize(dp) + sblock.e2fs_bsize - 1 < inosize(dp)) { 223 if (debug) 224 printf("bad size %llu:", (unsigned long long)inosize(dp)); 225 goto unknown; 226 } 227 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 228 dp = ginode(inumber); 229 dp->e2di_mode = h2fs16(IFREG|0600); 230 inossize(dp, sblock.e2fs_bsize); 231 inodirty(); 232 } 233 ndb = howmany(inosize(dp), sblock.e2fs_bsize); 234 if (ndb < 0) { 235 if (debug) 236 printf("bad size %llu ndb %d:", 237 (unsigned long long)inosize(dp), ndb); 238 goto unknown; 239 } 240 if (mode == IFBLK || mode == IFCHR) 241 ndb++; 242 if (mode == IFLNK) { 243 /* 244 * Fake ndb value so direct/indirect block checks below 245 * will detect any garbage after symlink string. 246 */ 247 if (inosize(dp) < EXT2_MAXSYMLINKLEN || 248 (EXT2_MAXSYMLINKLEN == 0 && dp->e2di_blocks == 0)) { 249 ndb = howmany(inosize(dp), sizeof(u_int32_t)); 250 if (ndb > NDADDR) { 251 j = ndb - NDADDR; 252 for (ndb = 1; j > 1; j--) 253 ndb *= NINDIR(&sblock); 254 ndb += NDADDR; 255 } 256 } 257 } 258 /* Linux puts things in blocks for FIFO, so skip this check */ 259 if (mode != IFIFO) { 260 for (j = ndb; j < NDADDR; j++) 261 if (dp->e2di_blocks[j] != 0) { 262 if (debug) 263 printf("bad direct addr: %d\n", 264 fs2h32(dp->e2di_blocks[j])); 265 goto unknown; 266 } 267 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 268 ndb /= NINDIR(&sblock); 269 for (; j < NIADDR; j++) { 270 if (dp->e2di_blocks[j+NDADDR] != 0) { 271 if (debug) 272 printf("bad indirect addr: %d\n", 273 fs2h32(dp->e2di_blocks[j+NDADDR])); 274 goto unknown; 275 } 276 } 277 } 278 if (ftypeok(dp) == 0) 279 goto unknown; 280 if (inumber >= EXT2_FIRSTINO || inumber == EXT2_ROOTINO) { 281 /* Don't count reserved inodes except root */ 282 n_files++; 283 } 284 lncntp[inumber] = fs2h16(dp->e2di_nlink); 285 if (dp->e2di_nlink == 0) { 286 zlnp = malloc(sizeof *zlnp); 287 if (zlnp == NULL) { 288 pfatal("LINK COUNT TABLE OVERFLOW"); 289 if (reply("CONTINUE") == 0) 290 exit(FSCK_EXIT_CHECK_FAILED); 291 } else { 292 zlnp->zlncnt = inumber; 293 zlnp->next = zlnhead; 294 zlnhead = zlnp; 295 } 296 } 297 if (mode == IFDIR) { 298 if (inosize(dp) == 0) 299 statemap[inumber] = DCLEAR; 300 else 301 statemap[inumber] = DSTATE; 302 cacheino(dp, inumber); 303 } else { 304 statemap[inumber] = FSTATE; 305 } 306 typemap[inumber] = E2IFTODT(mode); 307 badblk = dupblk = 0; 308 idesc->id_number = inumber; 309 (void)ckinode(dp, idesc); 310 idesc->id_entryno *= btodb(sblock.e2fs_bsize); 311 if (fs2h32(dp->e2di_nblock) != (uint32_t)idesc->id_entryno) { 312 pwarn("INCORRECT BLOCK COUNT I=%llu (%d should be %d)", 313 (unsigned long long)inumber, fs2h32(dp->e2di_nblock), 314 idesc->id_entryno); 315 if (preen) 316 printf(" (CORRECTED)\n"); 317 else if (reply("CORRECT") == 0) 318 return; 319 dp = ginode(inumber); 320 dp->e2di_nblock = h2fs32(idesc->id_entryno); 321 inodirty(); 322 } 323 return; 324 unknown: 325 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 326 statemap[inumber] = FCLEAR; 327 if (reply("CLEAR") == 1) { 328 statemap[inumber] = USTATE; 329 dp = ginode(inumber); 330 clearinode(dp); 331 inodirty(); 332 } 333 } 334 335 int 336 pass1check(struct inodesc *idesc) 337 { 338 int res = KEEPON; 339 int anyout, nfrags; 340 daddr_t blkno = idesc->id_blkno; 341 struct dups *dlp; 342 struct dups *new; 343 344 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 345 blkerror(idesc->id_number, "BAD", blkno); 346 if (badblk++ >= MAXBAD) { 347 pwarn("EXCESSIVE BAD BLKS I=%llu", 348 (unsigned long long)idesc->id_number); 349 if (preen) 350 printf(" (SKIPPING)\n"); 351 else if (reply("CONTINUE") == 0) 352 exit(FSCK_EXIT_CHECK_FAILED); 353 return (STOP); 354 } 355 } 356 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 357 if (anyout && chkrange(blkno, 1)) { 358 res = SKIP; 359 } else if (!testbmap(blkno)) { 360 n_blks++; 361 setbmap(blkno); 362 } else { 363 blkerror(idesc->id_number, "DUP", blkno); 364 if (dupblk++ >= MAXDUP) { 365 pwarn("EXCESSIVE DUP BLKS I=%llu", 366 (unsigned long long)idesc->id_number); 367 if (preen) 368 printf(" (SKIPPING)\n"); 369 else if (reply("CONTINUE") == 0) 370 exit(FSCK_EXIT_CHECK_FAILED); 371 return (STOP); 372 } 373 new = malloc(sizeof(struct dups)); 374 if (new == NULL) { 375 pfatal("DUP TABLE OVERFLOW."); 376 if (reply("CONTINUE") == 0) 377 exit(FSCK_EXIT_CHECK_FAILED); 378 return (STOP); 379 } 380 new->dup = blkno; 381 if (muldup == 0) { 382 duplist = muldup = new; 383 new->next = 0; 384 } else { 385 new->next = muldup->next; 386 muldup->next = new; 387 } 388 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 389 if (dlp->dup == blkno) 390 break; 391 if (dlp == muldup && dlp->dup != blkno) 392 muldup = new; 393 } 394 /* 395 * count the number of blocks found in id_entryno 396 */ 397 idesc->id_entryno++; 398 } 399 return (res); 400 } 401