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