1 /* 2 * Copyright (c) 1980, 1986, 1993 3 * The Regents of the University of California. All rights reserved. 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 REGENTS 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 REGENTS 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 * @(#)pass1.c 8.6 (Berkeley) 4/28/95 30 * $FreeBSD: src/sbin/fsck/pass1.c,v 1.16.2.5 2002/06/23 22:34:58 iedowse Exp $ 31 */ 32 33 #include <sys/param.h> 34 35 #include <vfs/ufs/dinode.h> 36 #include <vfs/ufs/dir.h> 37 #include <vfs/ufs/fs.h> 38 39 #include <err.h> 40 #include <string.h> 41 42 #include "fsck.h" 43 44 static ufs_daddr_t badblk; 45 static ufs_daddr_t dupblk; 46 static ufs1_ino_t lastino; /* last inode in use */ 47 48 static void checkinode(ufs1_ino_t inumber, struct inodesc *); 49 50 void 51 pass1(void) 52 { 53 u_int8_t *cp; 54 ufs1_ino_t inumber; 55 int c, i, cgd, inosused; 56 struct inostat *info; 57 struct inodesc idesc; 58 59 /* 60 * Set file system reserved blocks in used block map. 61 */ 62 for (c = 0; c < sblock.fs_ncg; c++) { 63 cgd = cgdmin(&sblock, c); 64 if (c == 0) { 65 i = cgbase(&sblock, c); 66 } else 67 i = cgsblock(&sblock, c); 68 for (; i < cgd; i++) 69 setbmap(i); 70 } 71 i = sblock.fs_csaddr; 72 cgd = i+ howmany(sblock.fs_cssize, sblock.fs_fsize); 73 for (; i < cgd; i++) 74 setbmap(i); 75 /* 76 * Find all allocated blocks. 77 */ 78 memset(&idesc, 0, sizeof(struct inodesc)); 79 idesc.id_type = ADDR; 80 idesc.id_func = pass1check; 81 n_files = n_blks = 0; 82 for (c = 0; c < sblock.fs_ncg; c++) { 83 inumber = c * sblock.fs_ipg; 84 setinodebuf(inumber); 85 inosused = sblock.fs_ipg; 86 if (got_siginfo) { 87 printf("%s: phase 1: cyl group %d of %d (%d%%)\n", 88 cdevname, c, sblock.fs_ncg, 89 c * 100 / sblock.fs_ncg); 90 got_siginfo = 0; 91 } 92 /* 93 * If we are using soft updates, then we can trust the 94 * cylinder group inode allocation maps to tell us which 95 * inodes are allocated. We will scan the used inode map 96 * to find the inodes that are really in use, and then 97 * read only those inodes in from disk. 98 */ 99 if (preen && usedsoftdep) { 100 getblk(&cgblk, cgtod(&sblock, c), sblock.fs_cgsize); 101 if (!cg_chkmagic(&cgrp)) 102 pfatal("CG %d: BAD MAGIC NUMBER\n", c); 103 cp = &cg_inosused(&cgrp)[(sblock.fs_ipg - 1) / NBBY]; 104 for ( ; inosused > 0; inosused -= NBBY, cp--) { 105 if (*cp == 0) 106 continue; 107 for (i = 1 << (NBBY - 1); i > 0; i >>= 1) { 108 if (*cp & i) 109 break; 110 inosused--; 111 } 112 break; 113 } 114 if (inosused < 0) 115 inosused = 0; 116 } 117 /* 118 * Allocate inoinfo structures for the allocated inodes. 119 */ 120 inostathead[c].il_numalloced = inosused; 121 if (inosused == 0) { 122 inostathead[c].il_stat = 0; 123 continue; 124 } 125 info = calloc((unsigned)inosused, sizeof(struct inostat)); 126 if (info == NULL) 127 pfatal("cannot alloc %u bytes for inoinfo\n", 128 (unsigned)(sizeof(struct inostat) * inosused)); 129 inostathead[c].il_stat = info; 130 /* 131 * Scan the allocated inodes. 132 */ 133 for (i = 0; i < inosused; i++, inumber++) { 134 if (inumber < ROOTINO) { 135 getnextinode(inumber); 136 continue; 137 } 138 checkinode(inumber, &idesc); 139 } 140 lastino += 1; 141 if (inosused < sblock.fs_ipg || inumber == lastino) 142 continue; 143 /* 144 * If we were not able to determine in advance which inodes 145 * were in use, then reduce the size of the inoinfo structure 146 * to the size necessary to describe the inodes that we 147 * really found. 148 */ 149 inosused = lastino - (c * sblock.fs_ipg); 150 if (inosused < 0) 151 inosused = 0; 152 inostathead[c].il_numalloced = inosused; 153 if (inosused == 0) { 154 free(inostathead[c].il_stat); 155 inostathead[c].il_stat = 0; 156 continue; 157 } 158 info = calloc((unsigned)inosused, sizeof(struct inostat)); 159 if (info == NULL) 160 pfatal("cannot alloc %u bytes for inoinfo\n", 161 (unsigned)(sizeof(struct inostat) * inosused)); 162 memmove(info, inostathead[c].il_stat, inosused * sizeof(*info)); 163 free(inostathead[c].il_stat); 164 inostathead[c].il_stat = info; 165 } 166 freeinodebuf(); 167 } 168 169 static void 170 checkinode(ufs1_ino_t inumber, struct inodesc *idesc) 171 { 172 struct ufs1_dinode *dp; 173 struct zlncnt *zlnp; 174 u_int64_t kernmaxfilesize; 175 ufs_daddr_t ndb, j; 176 mode_t mode; 177 char *symbuf; 178 179 dp = getnextinode(inumber); 180 mode = dp->di_mode & IFMT; 181 if (mode == 0) { 182 if (memcmp(dp->di_db, zino.di_db, 183 NDADDR * sizeof(ufs_daddr_t)) || 184 memcmp(dp->di_ib, zino.di_ib, 185 NIADDR * sizeof(ufs_daddr_t)) || 186 dp->di_mode || dp->di_size) { 187 pfatal("PARTIALLY ALLOCATED INODE I=%u", inumber); 188 if (reply("CLEAR") == 1) { 189 dp = ginode(inumber); 190 clearinode(dp); 191 inodirty(); 192 } 193 } 194 inoinfo(inumber)->ino_state = USTATE; 195 return; 196 } 197 lastino = inumber; 198 /* This should match the file size limit in ffs_mountfs(). */ 199 kernmaxfilesize = (u_int64_t)0x40000000 * sblock.fs_bsize - 1; 200 if (kernmaxfilesize > (u_int64_t)0x80000000u * PAGE_SIZE - 1) 201 kernmaxfilesize = (u_int64_t)0x80000000u * PAGE_SIZE - 1; 202 if (dp->di_size > kernmaxfilesize || 203 dp->di_size > sblock.fs_maxfilesize || 204 (mode == IFDIR && dp->di_size > MAXDIRSIZE)) { 205 if (debug) 206 printf("bad size %ju:", (uintmax_t)dp->di_size); 207 goto unknown; 208 } 209 if (!preen && mode == IFMT && reply("HOLD BAD BLOCK") == 1) { 210 dp = ginode(inumber); 211 dp->di_size = sblock.fs_fsize; 212 dp->di_mode = IFREG|0600; 213 inodirty(); 214 } 215 if ((mode == IFBLK || mode == IFCHR || mode == IFIFO || 216 mode == IFSOCK) && dp->di_size != 0) { 217 if (debug) 218 printf("bad special-file size %ju:", (uintmax_t)dp->di_size); 219 goto unknown; 220 } 221 ndb = howmany(dp->di_size, sblock.fs_bsize); 222 if (ndb < 0) { 223 if (debug) 224 printf("bad size %ju ndb %d:", 225 (uintmax_t)dp->di_size, ndb); 226 goto unknown; 227 } 228 if (mode == IFBLK || mode == IFCHR) 229 ndb++; 230 if (mode == IFLNK) { 231 if (doinglevel2 && 232 dp->di_size > 0 && dp->di_size < MAXSYMLINKLEN && 233 dp->di_blocks != 0) { 234 symbuf = alloca(secsize); 235 if (bread(fsreadfd, symbuf, 236 fsbtodb(&sblock, dp->di_db[0]), 237 (long)secsize) != 0) 238 errx(EEXIT, "cannot read symlink"); 239 if (debug) { 240 symbuf[dp->di_size] = 0; 241 printf("convert symlink %lu(%s) of size %ld\n", 242 (u_long)inumber, symbuf, (long)dp->di_size); 243 } 244 dp = ginode(inumber); 245 memmove(dp->di_shortlink, symbuf, (long)dp->di_size); 246 dp->di_blocks = 0; 247 inodirty(); 248 } 249 /* 250 * Fake ndb value so direct/indirect block checks below 251 * will detect any garbage after symlink string. 252 */ 253 if (dp->di_size < sblock.fs_maxsymlinklen) { 254 ndb = howmany(dp->di_size, sizeof(ufs_daddr_t)); 255 if (ndb > NDADDR) { 256 j = ndb - NDADDR; 257 for (ndb = 1; j > 1; j--) 258 ndb *= NINDIR(&sblock); 259 ndb += NDADDR; 260 } 261 } 262 } 263 for (j = ndb; j < NDADDR; j++) 264 if (dp->di_db[j] != 0) { 265 if (debug) 266 printf("bad direct addr: %ld\n", 267 (long)dp->di_db[j]); 268 goto unknown; 269 } 270 for (j = 0, ndb -= NDADDR; ndb > 0; j++) 271 ndb /= NINDIR(&sblock); 272 for (; j < NIADDR; j++) 273 if (dp->di_ib[j] != 0) { 274 if (debug) 275 printf("bad indirect addr: %ld\n", 276 (long)dp->di_ib[j]); 277 goto unknown; 278 } 279 if (ftypeok(dp) == 0) 280 goto unknown; 281 n_files++; 282 inoinfo(inumber)->ino_linkcnt = dp->di_nlink; 283 if (dp->di_nlink <= 0) { 284 zlnp = (struct zlncnt *)malloc(sizeof *zlnp); 285 if (zlnp == NULL) { 286 pfatal("LINK COUNT TABLE OVERFLOW"); 287 if (reply("CONTINUE") == 0) { 288 ckfini(0); 289 exit(EEXIT); 290 } 291 } else { 292 zlnp->zlncnt = inumber; 293 zlnp->next = zlnhead; 294 zlnhead = zlnp; 295 } 296 } 297 if (mode == IFDIR) { 298 if (dp->di_size == 0) 299 inoinfo(inumber)->ino_state = DCLEAR; 300 else 301 inoinfo(inumber)->ino_state = DSTATE; 302 cacheino(dp, inumber); 303 countdirs++; 304 } else 305 inoinfo(inumber)->ino_state = FSTATE; 306 inoinfo(inumber)->ino_type = IFTODT(mode); 307 if (doinglevel2 && 308 (dp->di_ouid != (u_short)-1 || dp->di_ogid != (u_short)-1)) { 309 dp = ginode(inumber); 310 dp->di_uid = dp->di_ouid; 311 dp->di_ouid = -1; 312 dp->di_gid = dp->di_ogid; 313 dp->di_ogid = -1; 314 inodirty(); 315 } 316 badblk = dupblk = 0; 317 idesc->id_number = inumber; 318 ckinode(dp, idesc); 319 idesc->id_entryno *= btodb(sblock.fs_fsize); 320 if (dp->di_blocks != idesc->id_entryno) { 321 pwarn("INCORRECT BLOCK COUNT I=%u (%d should be %d)", 322 inumber, dp->di_blocks, idesc->id_entryno); 323 if (preen) 324 printf(" (CORRECTED)\n"); 325 else if (reply("CORRECT") == 0) 326 return; 327 dp = ginode(inumber); 328 dp->di_blocks = idesc->id_entryno; 329 inodirty(); 330 } 331 return; 332 unknown: 333 pfatal("UNKNOWN FILE TYPE I=%u", inumber); 334 inoinfo(inumber)->ino_state = FCLEAR; 335 if (reply("CLEAR") == 1) { 336 inoinfo(inumber)->ino_state = USTATE; 337 dp = ginode(inumber); 338 clearinode(dp); 339 inodirty(); 340 } 341 } 342 343 int 344 pass1check(struct inodesc *idesc) 345 { 346 int res = KEEPON; 347 int anyout, nfrags; 348 ufs_daddr_t blkno = idesc->id_blkno; 349 struct dups *dlp; 350 struct dups *new; 351 352 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 353 blkerror(idesc->id_number, "BAD", blkno); 354 if (badblk++ >= MAXBAD) { 355 pwarn("EXCESSIVE BAD BLKS I=%u", 356 idesc->id_number); 357 if (preen) 358 printf(" (SKIPPING)\n"); 359 else if (reply("CONTINUE") == 0) { 360 ckfini(0); 361 exit(EEXIT); 362 } 363 return (STOP); 364 } 365 } 366 for (nfrags = idesc->id_numfrags; nfrags > 0; blkno++, nfrags--) { 367 if (anyout && chkrange(blkno, 1)) { 368 res = SKIP; 369 } else if (!testbmap(blkno)) { 370 n_blks++; 371 setbmap(blkno); 372 } else { 373 blkerror(idesc->id_number, "DUP", blkno); 374 if (dupblk++ >= MAXDUP) { 375 pwarn("EXCESSIVE DUP BLKS I=%u", 376 idesc->id_number); 377 if (preen) 378 printf(" (SKIPPING)\n"); 379 else if (reply("CONTINUE") == 0) { 380 ckfini(0); 381 exit(EEXIT); 382 } 383 return (STOP); 384 } 385 new = (struct dups *)malloc(sizeof(struct dups)); 386 if (new == NULL) { 387 pfatal("DUP TABLE OVERFLOW."); 388 if (reply("CONTINUE") == 0) { 389 ckfini(0); 390 exit(EEXIT); 391 } 392 return (STOP); 393 } 394 new->dup = blkno; 395 if (muldup == 0) { 396 duplist = muldup = new; 397 new->next = 0; 398 } else { 399 new->next = muldup->next; 400 muldup->next = new; 401 } 402 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 403 if (dlp->dup == blkno) 404 break; 405 if (dlp == muldup && dlp->dup != blkno) 406 muldup = new; 407 } 408 /* 409 * count the number of blocks found in id_entryno 410 */ 411 idesc->id_entryno++; 412 } 413 return (res); 414 } 415