1 /* $NetBSD: pass1.c,v 1.12 2004/03/22 19:46:53 bouyer 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.12 2004/03/22 19:46:53 bouyer 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 87 static daddr_t badblk; 88 static daddr_t dupblk; 89 static void checkinode __P((ino_t, struct inodesc *)); 90 91 void 92 pass1() 93 { 94 ino_t inumber; 95 int c, i; 96 daddr_t dbase; 97 struct inodesc idesc; 98 99 /* 100 * Set file system reserved blocks in used block map. 101 */ 102 for (c = 0; c < sblock.e2fs_ncg; c++) { 103 dbase = c * sblock.e2fs.e2fs_bpg + 104 sblock.e2fs.e2fs_first_dblock; 105 /* Mark the blocks used for the inode table */ 106 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_i_tables) >= dbase) { 107 for (i = 0; i < sblock.e2fs_itpg; i++) 108 setbmap( 109 fs2h32(sblock.e2fs_gd[c].ext2bgd_i_tables) 110 + i); 111 } 112 /* Mark the blocks used for the block bitmap */ 113 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_b_bitmap) >= dbase) 114 setbmap(fs2h32(sblock.e2fs_gd[c].ext2bgd_b_bitmap)); 115 /* Mark the blocks used for the inode bitmap */ 116 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_i_bitmap) >= dbase) 117 setbmap(fs2h32(sblock.e2fs_gd[c].ext2bgd_i_bitmap)); 118 119 if (sblock.e2fs.e2fs_rev == E2FS_REV0 || 120 (sblock.e2fs.e2fs_features_rocompat & 121 EXT2F_ROCOMPAT_SPARSESUPER) == 0 || 122 cg_has_sb(c)) { 123 /* Mark copuy of SB and descriptors */ 124 setbmap(dbase); 125 for (i = 1; i <= sblock.e2fs_ngdb; i++) 126 setbmap(dbase+i); 127 } 128 129 130 if (c == 0) { 131 for(i = 0; i < dbase; i++) 132 setbmap(i); 133 } 134 } 135 136 /* 137 * Find all allocated blocks. 138 */ 139 memset(&idesc, 0, sizeof(struct inodesc)); 140 idesc.id_type = ADDR; 141 idesc.id_func = pass1check; 142 inumber = 1; 143 n_files = n_blks = 0; 144 resetinodebuf(); 145 for (c = 0; c < sblock.e2fs_ncg; c++) { 146 for (i = 0; 147 i < sblock.e2fs.e2fs_ipg && inumber <= sblock.e2fs.e2fs_icount; 148 i++, inumber++) { 149 if (inumber < EXT2_ROOTINO) /* XXX */ 150 continue; 151 checkinode(inumber, &idesc); 152 } 153 } 154 freeinodebuf(); 155 } 156 157 static void 158 checkinode(inumber, idesc) 159 ino_t inumber; 160 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 && inumber != EXT2_ROOTINO) 169 return; 170 171 mode = fs2h16(dp->e2di_mode) & IFMT; 172 if (mode == 0 || (dp->e2di_dtime != 0 && dp->e2di_nlink == 0)) { 173 if (mode == 0 && ( 174 memcmp(dp->e2di_blocks, zino.e2di_blocks, 175 (NDADDR + NIADDR) * sizeof(u_int32_t)) || 176 dp->e2di_mode || dp->e2di_size)) { 177 pfatal("PARTIALLY ALLOCATED INODE I=%u", inumber); 178 if (reply("CLEAR") == 1) { 179 dp = ginode(inumber); 180 clearinode(dp); 181 inodirty(); 182 } 183 } 184 #ifdef notyet /* it seems that dtime == 0 is valid for a unallocated inode */ 185 if (dp->e2di_dtime == 0) { 186 pwarn("DELETED INODE I=%u HAS A NULL DTIME", inumber); 187 if (preen) { 188 printf(" (CORRECTED)\n"); 189 } 190 if (preen || reply("CORRECT")) { 191 time_t t; 192 time(&t); 193 dp->e2di_dtime = h2fs32(t); 194 dp = ginode(inumber); 195 inodirty(); 196 } 197 } 198 #endif 199 statemap[inumber] = USTATE; 200 return; 201 } 202 lastino = inumber; 203 if (dp->e2di_dtime != 0) { 204 time_t t = fs2h32(dp->e2di_dtime); 205 char *p = ctime(&t); 206 pwarn("INODE I=%u HAS DTIME=%12.12s %4.4s", inumber, &p[4], &p[20]); 207 if (preen) { 208 printf(" (CORRECTED)\n"); 209 } 210 if (preen || reply("CORRECT")) { 211 dp = ginode(inumber); 212 dp->e2di_dtime = 0; 213 inodirty(); 214 } 215 } 216 if (/* dp->di_size < 0 || */ 217 fs2h32(dp->e2di_size) + sblock.e2fs_bsize - 1 < 218 fs2h32(dp->e2di_size)) { 219 if (debug) 220 printf("bad size %lu:", (u_long)fs2h32(dp->e2di_size)); 221 goto unknown; 222 } 223 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 224 dp = ginode(inumber); 225 dp->e2di_size = h2fs32(sblock.e2fs_bsize); 226 dp->e2di_mode = h2fs16(IFREG|0600); 227 inodirty(); 228 } 229 ndb = howmany(fs2h32(dp->e2di_size), sblock.e2fs_bsize); 230 if (ndb < 0) { 231 if (debug) 232 printf("bad size %lu ndb %d:", 233 (u_long)fs2h32(dp->e2di_size), ndb); 234 goto unknown; 235 } 236 if (mode == IFBLK || mode == IFCHR) 237 ndb++; 238 if (mode == IFLNK) { 239 /* 240 * Fake ndb value so direct/indirect block checks below 241 * will detect any garbage after symlink string. 242 */ 243 if (fs2h32(dp->e2di_size) < EXT2_MAXSYMLINKLEN || 244 (EXT2_MAXSYMLINKLEN == 0 && dp->e2di_blocks == 0)) { 245 ndb = howmany(fs2h32(dp->e2di_size), sizeof(u_int32_t)); 246 if (ndb > NDADDR) { 247 j = ndb - NDADDR; 248 for (ndb = 1; j > 1; j--) 249 ndb *= NINDIR(&sblock); 250 ndb += NDADDR; 251 } 252 } 253 } 254 /* Linux puts things in blocks for FIFO, so skip this check */ 255 if (mode != IFIFO) { 256 for (j = ndb; j < NDADDR; j++) 257 if (dp->e2di_blocks[j] != 0) { 258 if (debug) 259 printf("bad direct addr: %d\n", 260 fs2h32(dp->e2di_blocks[j])); 261 goto unknown; 262 } 263 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 264 ndb /= NINDIR(&sblock); 265 for (; j < NIADDR; j++) { 266 if (dp->e2di_blocks[j+NDADDR] != 0) { 267 if (debug) 268 printf("bad indirect addr: %d\n", 269 fs2h32(dp->e2di_blocks[j+NDADDR])); 270 goto unknown; 271 } 272 } 273 } 274 if (ftypeok(dp) == 0) 275 goto unknown; 276 n_files++; 277 lncntp[inumber] = fs2h16(dp->e2di_nlink); 278 if (dp->e2di_nlink == 0) { 279 zlnp = (struct zlncnt *)malloc(sizeof *zlnp); 280 if (zlnp == NULL) { 281 pfatal("LINK COUNT TABLE OVERFLOW"); 282 if (reply("CONTINUE") == 0) 283 errexit("%s\n", ""); 284 } else { 285 zlnp->zlncnt = inumber; 286 zlnp->next = zlnhead; 287 zlnhead = zlnp; 288 } 289 } 290 if (mode == IFDIR) { 291 if (dp->e2di_size == 0) 292 statemap[inumber] = DCLEAR; 293 else 294 statemap[inumber] = DSTATE; 295 cacheino(dp, inumber); 296 } else { 297 statemap[inumber] = FSTATE; 298 } 299 typemap[inumber] = E2IFTODT(mode); 300 badblk = dupblk = 0; 301 idesc->id_number = inumber; 302 (void)ckinode(dp, idesc); 303 idesc->id_entryno *= btodb(sblock.e2fs_bsize); 304 if (fs2h32(dp->e2di_nblock) != idesc->id_entryno) { 305 pwarn("INCORRECT BLOCK COUNT I=%u (%d should be %d)", 306 inumber, fs2h32(dp->e2di_nblock), idesc->id_entryno); 307 if (preen) 308 printf(" (CORRECTED)\n"); 309 else if (reply("CORRECT") == 0) 310 return; 311 dp = ginode(inumber); 312 dp->e2di_nblock = h2fs32(idesc->id_entryno); 313 inodirty(); 314 } 315 return; 316 unknown: 317 pfatal("UNKNOWN FILE TYPE I=%u", inumber); 318 statemap[inumber] = FCLEAR; 319 if (reply("CLEAR") == 1) { 320 statemap[inumber] = USTATE; 321 dp = ginode(inumber); 322 clearinode(dp); 323 inodirty(); 324 } 325 } 326 327 int 328 pass1check(idesc) 329 struct inodesc *idesc; 330 { 331 int res = KEEPON; 332 int anyout, nfrags; 333 daddr_t blkno = idesc->id_blkno; 334 struct dups *dlp; 335 struct dups *new; 336 337 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 338 blkerror(idesc->id_number, "BAD", blkno); 339 if (badblk++ >= MAXBAD) { 340 pwarn("EXCESSIVE BAD BLKS I=%u", 341 idesc->id_number); 342 if (preen) 343 printf(" (SKIPPING)\n"); 344 else if (reply("CONTINUE") == 0) 345 errexit("%s\n", ""); 346 return (STOP); 347 } 348 } 349 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 350 if (anyout && chkrange(blkno, 1)) { 351 res = SKIP; 352 } else if (!testbmap(blkno)) { 353 n_blks++; 354 setbmap(blkno); 355 } else { 356 blkerror(idesc->id_number, "DUP", blkno); 357 if (dupblk++ >= MAXDUP) { 358 pwarn("EXCESSIVE DUP BLKS I=%u", 359 idesc->id_number); 360 if (preen) 361 printf(" (SKIPPING)\n"); 362 else if (reply("CONTINUE") == 0) 363 errexit("%s\n", ""); 364 return (STOP); 365 } 366 new = (struct dups *)malloc(sizeof(struct dups)); 367 if (new == NULL) { 368 pfatal("DUP TABLE OVERFLOW."); 369 if (reply("CONTINUE") == 0) 370 errexit("%s\n", ""); 371 return (STOP); 372 } 373 new->dup = blkno; 374 if (muldup == 0) { 375 duplist = muldup = new; 376 new->next = 0; 377 } else { 378 new->next = muldup->next; 379 muldup->next = new; 380 } 381 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 382 if (dlp->dup == blkno) 383 break; 384 if (dlp == muldup && dlp->dup != blkno) 385 muldup = new; 386 } 387 /* 388 * count the number of blocks found in id_entryno 389 */ 390 idesc->id_entryno++; 391 } 392 return (res); 393 } 394