1/* $NetBSD: pass1.c,v 1.20 2009/10/19 18:41:08 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 * 44 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 45 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 46 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 47 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 48 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 49 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 50 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 51 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 52 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 53 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 54 */ 55 56#include <sys/cdefs.h> 57#ifndef lint 58#if 0 59static char sccsid[] = "@(#)pass1.c 8.1 (Berkeley) 6/5/93"; 60#else 61__RCSID("$NetBSD: pass1.c,v 1.20 2009/10/19 18:41:08 bouyer Exp $"); 62#endif 63#endif /* not lint */ 64 65#include <sys/param.h> 66#include <sys/time.h> 67#include <ufs/ext2fs/ext2fs_dinode.h> 68#include <ufs/ext2fs/ext2fs_dir.h> 69#include <ufs/ext2fs/ext2fs.h> 70 71#include <ufs/ufs/dinode.h> /* for IFMT & friends */ 72 73#include <stdio.h> 74#include <stdlib.h> 75#include <string.h> 76#include <time.h> 77 78#include "fsck.h" 79#include "extern.h" 80#include "fsutil.h" 81#include "exitvalues.h" 82 83static daddr_t badblk; 84static daddr_t dupblk; 85static void checkinode(ino_t, struct inodesc *); 86 87void 88pass1(void) 89{ 90 ino_t inumber; 91 int c, i; 92 size_t j; 93 daddr_t dbase; 94 struct inodesc idesc; 95 96 /* 97 * Set file system reserved blocks in used block map. 98 */ 99 for (c = 0; c < sblock.e2fs_ncg; c++) { 100 dbase = c * sblock.e2fs.e2fs_bpg + 101 sblock.e2fs.e2fs_first_dblock; 102 /* Mark the blocks used for the inode table */ 103 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_i_tables) >= dbase) { 104 for (i = 0; i < sblock.e2fs_itpg; i++) 105 setbmap( 106 fs2h32(sblock.e2fs_gd[c].ext2bgd_i_tables) 107 + i); 108 } 109 /* Mark the blocks used for the block bitmap */ 110 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_b_bitmap) >= dbase) 111 setbmap(fs2h32(sblock.e2fs_gd[c].ext2bgd_b_bitmap)); 112 /* Mark the blocks used for the inode bitmap */ 113 if (fs2h32(sblock.e2fs_gd[c].ext2bgd_i_bitmap) >= dbase) 114 setbmap(fs2h32(sblock.e2fs_gd[c].ext2bgd_i_bitmap)); 115 116 if (sblock.e2fs.e2fs_rev == E2FS_REV0 || 117 (sblock.e2fs.e2fs_features_rocompat & 118 EXT2F_ROCOMPAT_SPARSESUPER) == 0 || 119 cg_has_sb(c)) { 120 /* Mark copuy of SB and descriptors */ 121 setbmap(dbase); 122 for (i = 1; i <= sblock.e2fs_ngdb; i++) 123 setbmap(dbase+i); 124 } 125 126 127 if (c == 0) { 128 for(i = 0; i < dbase; i++) 129 setbmap(i); 130 } 131 } 132 133 /* 134 * Find all allocated blocks. 135 */ 136 memset(&idesc, 0, sizeof(struct inodesc)); 137 idesc.id_type = ADDR; 138 idesc.id_func = pass1check; 139 inumber = 1; 140 n_files = n_blks = 0; 141 resetinodebuf(); 142 for (c = 0; c < sblock.e2fs_ncg; c++) { 143 for (j = 0; 144 j < sblock.e2fs.e2fs_ipg && inumber <= sblock.e2fs.e2fs_icount; 145 j++, inumber++) { 146 if (inumber < EXT2_ROOTINO) /* XXX */ 147 continue; 148 checkinode(inumber, &idesc); 149 } 150 } 151 freeinodebuf(); 152} 153 154static void 155checkinode(ino_t inumber, struct inodesc *idesc) 156{ 157 struct ext2fs_dinode *dp; 158 struct zlncnt *zlnp; 159 int ndb, j; 160 mode_t mode; 161 162 dp = getnextinode(inumber); 163 if (inumber < EXT2_FIRSTINO && 164 inumber != EXT2_ROOTINO && 165 !(inumber == EXT2_RESIZEINO && 166 (sblock.e2fs.e2fs_features_compat & EXT2F_COMPAT_RESIZE) != 0)) 167 return; 168 169 mode = fs2h16(dp->e2di_mode) & IFMT; 170 if (mode == 0 || (dp->e2di_dtime != 0 && dp->e2di_nlink == 0)) { 171 if (mode == 0 && ( 172 memcmp(dp->e2di_blocks, zino.e2di_blocks, 173 (NDADDR + NIADDR) * sizeof(u_int32_t)) || 174 dp->e2di_mode || inosize(dp))) { 175 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 176 (unsigned long long)inumber); 177 if (reply("CLEAR") == 1) { 178 dp = ginode(inumber); 179 clearinode(dp); 180 inodirty(); 181 } 182 } 183#ifdef notyet /* it seems that dtime == 0 is valid for a unallocated inode */ 184 if (dp->e2di_dtime == 0) { 185 pwarn("DELETED INODE I=%llu HAS A NULL DTIME", 186 (unsigned long long)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 pwarn("INODE I=%llu HAS DTIME=%s", 205 (unsigned long long)inumber, 206 print_mtime(fs2h32(dp->e2di_dtime))); 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 (inosize(dp) + sblock.e2fs_bsize - 1 < inosize(dp)) { 217 if (debug) 218 printf("bad size %llu:", (unsigned long long)inosize(dp)); 219 goto unknown; 220 } 221 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 222 dp = ginode(inumber); 223 dp->e2di_mode = h2fs16(IFREG|0600); 224 inossize(dp, sblock.e2fs_bsize); 225 inodirty(); 226 } 227 ndb = howmany(inosize(dp), sblock.e2fs_bsize); 228 if (ndb < 0) { 229 if (debug) 230 printf("bad size %llu ndb %d:", 231 (unsigned long long)inosize(dp), ndb); 232 goto unknown; 233 } 234 if (mode == IFBLK || mode == IFCHR) 235 ndb++; 236 if (mode == IFLNK) { 237 /* 238 * Fake ndb value so direct/indirect block checks below 239 * will detect any garbage after symlink string. 240 */ 241 if (inosize(dp) < EXT2_MAXSYMLINKLEN || 242 (EXT2_MAXSYMLINKLEN == 0 && dp->e2di_blocks == 0)) { 243 ndb = howmany(inosize(dp), sizeof(u_int32_t)); 244 if (ndb > NDADDR) { 245 j = ndb - NDADDR; 246 for (ndb = 1; j > 1; j--) 247 ndb *= NINDIR(&sblock); 248 ndb += NDADDR; 249 } 250 } 251 } 252 /* Linux puts things in blocks for FIFO, so skip this check */ 253 if (mode != IFIFO) { 254 for (j = ndb; j < NDADDR; j++) 255 if (dp->e2di_blocks[j] != 0) { 256 if (debug) 257 printf("bad direct addr: %d\n", 258 fs2h32(dp->e2di_blocks[j])); 259 goto unknown; 260 } 261 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 262 ndb /= NINDIR(&sblock); 263 for (; j < NIADDR; j++) { 264 if (dp->e2di_blocks[j+NDADDR] != 0) { 265 if (debug) 266 printf("bad indirect addr: %d\n", 267 fs2h32(dp->e2di_blocks[j+NDADDR])); 268 goto unknown; 269 } 270 } 271 } 272 if (ftypeok(dp) == 0) 273 goto unknown; 274 if (inumber >= EXT2_FIRSTINO || inumber == EXT2_ROOTINO) { 275 /* Don't count reserved inodes except root */ 276 n_files++; 277 } 278 lncntp[inumber] = fs2h16(dp->e2di_nlink); 279 if (dp->e2di_nlink == 0) { 280 zlnp = malloc(sizeof *zlnp); 281 if (zlnp == NULL) { 282 pfatal("LINK COUNT TABLE OVERFLOW"); 283 if (reply("CONTINUE") == 0) 284 exit(FSCK_EXIT_CHECK_FAILED); 285 } else { 286 zlnp->zlncnt = inumber; 287 zlnp->next = zlnhead; 288 zlnhead = zlnp; 289 } 290 } 291 if (mode == IFDIR) { 292 if (inosize(dp) == 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) != (uint32_t)idesc->id_entryno) { 306 pwarn("INCORRECT BLOCK COUNT I=%llu (%d should be %d)", 307 (unsigned long long)inumber, fs2h32(dp->e2di_nblock), 308 idesc->id_entryno); 309 if (preen) 310 printf(" (CORRECTED)\n"); 311 else if (reply("CORRECT") == 0) 312 return; 313 dp = ginode(inumber); 314 dp->e2di_nblock = h2fs32(idesc->id_entryno); 315 inodirty(); 316 } 317 return; 318unknown: 319 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 320 statemap[inumber] = FCLEAR; 321 if (reply("CLEAR") == 1) { 322 statemap[inumber] = USTATE; 323 dp = ginode(inumber); 324 clearinode(dp); 325 inodirty(); 326 } 327} 328 329int 330pass1check(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=%llu", 342 (unsigned long long)idesc->id_number); 343 if (preen) 344 printf(" (SKIPPING)\n"); 345 else if (reply("CONTINUE") == 0) 346 exit(FSCK_EXIT_CHECK_FAILED); 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=%llu", 360 (unsigned long long)idesc->id_number); 361 if (preen) 362 printf(" (SKIPPING)\n"); 363 else if (reply("CONTINUE") == 0) 364 exit(FSCK_EXIT_CHECK_FAILED); 365 return (STOP); 366 } 367 new = malloc(sizeof(struct dups)); 368 if (new == NULL) { 369 pfatal("DUP TABLE OVERFLOW."); 370 if (reply("CONTINUE") == 0) 371 exit(FSCK_EXIT_CHECK_FAILED); 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