1 /* $NetBSD: pass1.c,v 1.45 2015/10/03 08:30:13 dholland 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 #include <sys/param.h> 33 #include <sys/time.h> 34 #include <sys/mount.h> 35 #include <sys/buf.h> 36 37 #define vnode uvnode 38 #include <ufs/lfs/lfs.h> 39 #include <ufs/lfs/lfs_accessors.h> 40 #include <ufs/lfs/lfs_inode.h> 41 #undef vnode 42 43 #include <err.h> 44 #include <stdio.h> 45 #include <stdlib.h> 46 #include <string.h> 47 #include <signal.h> 48 #include <util.h> 49 50 #include "bufcache.h" 51 #include "vnode.h" 52 #include "lfs_user.h" 53 54 #include "fsck.h" 55 #include "extern.h" 56 #include "fsutil.h" 57 58 blkcnt_t badblkcount; 59 static blkcnt_t dupblkcount; 60 static int i_d_cmp(const void *, const void *); 61 62 struct ino_daddr { 63 ino_t ino; 64 daddr_t daddr; 65 }; 66 67 static int 68 i_d_cmp(const void *va, const void *vb) 69 { 70 const struct ino_daddr *a, *b; 71 72 a = *((const struct ino_daddr *const *) va); 73 b = *((const struct ino_daddr *const *) vb); 74 75 if (a->daddr == b->daddr) { 76 return (a->ino - b->ino); 77 } 78 if (a->daddr > b->daddr) { 79 return 1; 80 } 81 return -1; 82 } 83 84 void 85 pass1(void) 86 { 87 ino_t inumber; 88 int i; 89 struct inodesc idesc; 90 union lfs_dinode *tinode; 91 IFILE *ifp; 92 struct ubuf *bp; 93 struct ino_daddr **dins; 94 95 /* 96 * Find all allocated blocks, initialize numdirs. 97 */ 98 memset(&idesc, 0, sizeof(struct inodesc)); 99 idesc.id_type = ADDR; 100 idesc.id_func = pass1check; 101 idesc.id_lblkno = 0; 102 inumber = 0; 103 n_files = n_blks = 0; 104 105 if (debug) 106 printf("creating sorted inode address table...\n"); 107 /* Sort by daddr */ 108 dins = ecalloc(maxino, sizeof(*dins)); 109 for (i = 0; i < maxino; i++) { 110 dins[i] = emalloc(sizeof(**dins)); 111 dins[i]->ino = i; 112 if (i == LFS_IFILE_INUM) 113 dins[i]->daddr = lfs_sb_getidaddr(fs); 114 else { 115 LFS_IENTRY(ifp, fs, i, bp); 116 dins[i]->daddr = lfs_if_getdaddr(fs, ifp); 117 brelse(bp, 0); 118 } 119 } 120 qsort(dins, maxino, sizeof(*dins), i_d_cmp); 121 122 /* find a value for numdirs, fill in din_table */ 123 if (debug) 124 printf("counting dirs...\n"); 125 numdirs = 0; 126 for (i = 0; i < maxino; i++) { 127 inumber = dins[i]->ino; 128 if (inumber == 0 || dins[i]->daddr == 0) 129 continue; 130 tinode = ginode(inumber); 131 if (tinode && (lfs_dino_getmode(fs, tinode) & LFS_IFMT) == LFS_IFDIR) 132 numdirs++; 133 } 134 135 /* from setup.c */ 136 inplast = 0; 137 listmax = numdirs + 10; 138 inpsort = ecalloc(listmax, sizeof(struct inoinfo *)); 139 inphead = ecalloc(numdirs, sizeof(struct inoinfo *)); 140 if (debug) 141 printf("counting blocks...\n"); 142 143 for (i = 0; i < maxino; i++) { 144 inumber = dins[i]->ino; 145 if (inumber == 0 || dins[i]->daddr == 0) { 146 statemap[inumber] = USTATE; 147 continue; 148 } 149 if (dins[i]->daddr != LFS_UNUSED_DADDR) { 150 checkinode(inumber, &idesc); 151 } else { 152 statemap[inumber] = USTATE; 153 } 154 free(dins[i]); 155 } 156 free(dins); 157 } 158 159 static int 160 nonzero_db(union lfs_dinode *dip) 161 { 162 unsigned i; 163 164 for (i=0; i<ULFS_NDADDR; i++) { 165 if (lfs_dino_getdb(fs, dip, i) != 0) { 166 return 1; 167 } 168 } 169 return 0; 170 } 171 172 static int 173 nonzero_ib(union lfs_dinode *dip) 174 { 175 unsigned i; 176 177 for (i=0; i<ULFS_NIADDR; i++) { 178 if (lfs_dino_getib(fs, dip, i) != 0) { 179 return 1; 180 } 181 } 182 return 0; 183 } 184 185 void 186 checkinode(ino_t inumber, struct inodesc * idesc) 187 { 188 union lfs_dinode *dp; 189 struct uvnode *vp; 190 struct zlncnt *zlnp; 191 struct ubuf *bp; 192 IFILE *ifp; 193 int64_t ndb, j; 194 mode_t mode; 195 196 vp = vget(fs, inumber); 197 if (vp) 198 dp = VTOD(vp); 199 else 200 dp = NULL; 201 202 if (dp == NULL) { 203 statemap[inumber] = USTATE; 204 return; 205 } 206 mode = lfs_dino_getmode(fs, dp) & LFS_IFMT; 207 208 /* XXX - LFS doesn't have this particular problem (?) */ 209 if (mode == 0) { 210 if (nonzero_db(dp) || nonzero_ib(dp) || 211 lfs_dino_getmode(fs, dp) || lfs_dino_getsize(fs, dp)) { 212 pwarn("mode=o%o, ifmt=o%o\n", lfs_dino_getmode(fs, dp), mode); 213 pfatal("PARTIALLY ALLOCATED INODE I=%llu", 214 (unsigned long long)inumber); 215 if (reply("CLEAR") == 1) { 216 vp = vget(fs, inumber); 217 clearinode(inumber); 218 vnode_destroy(vp); 219 } 220 } 221 statemap[inumber] = USTATE; 222 return; 223 } 224 lastino = inumber; 225 if (/* lfs_dino_getsize(fs, dp) < 0 || */ 226 lfs_dino_getsize(fs, dp) + lfs_sb_getbsize(fs) - 1 < lfs_dino_getsize(fs, dp)) { 227 if (debug) 228 printf("bad size %ju:", 229 (uintmax_t)lfs_dino_getsize(fs, dp)); 230 goto unknown; 231 } 232 if (!preen && mode == LFS_IFMT && reply("HOLD BAD BLOCK") == 1) { 233 vp = vget(fs, inumber); 234 dp = VTOD(vp); 235 lfs_dino_setsize(fs, dp, lfs_sb_getfsize(fs)); 236 lfs_dino_setmode(fs, dp, LFS_IFREG | 0600); 237 inodirty(VTOI(vp)); 238 } 239 ndb = howmany(lfs_dino_getsize(fs, dp), lfs_sb_getbsize(fs)); 240 if (ndb < 0) { 241 if (debug) 242 printf("bad size %ju ndb %jd:", 243 (uintmax_t)lfs_dino_getsize(fs, dp), (intmax_t)ndb); 244 goto unknown; 245 } 246 if (mode == LFS_IFBLK || mode == LFS_IFCHR) 247 ndb++; 248 if (mode == LFS_IFLNK) { 249 /* 250 * Fake ndb value so direct/indirect block checks below 251 * will detect any garbage after symlink string. 252 */ 253 if (lfs_dino_getsize(fs, dp) < lfs_sb_getmaxsymlinklen(fs) || 254 (lfs_sb_getmaxsymlinklen(fs) == 0 && lfs_dino_getblocks(fs, dp) == 0)) { 255 ndb = howmany(lfs_dino_getsize(fs, dp), LFS_BLKPTRSIZE(fs)); 256 if (ndb > ULFS_NDADDR) { 257 j = ndb - ULFS_NDADDR; 258 for (ndb = 1; j > 1; j--) 259 ndb *= LFS_NINDIR(fs); 260 ndb += ULFS_NDADDR; 261 } 262 } 263 } 264 for (j = ndb; j < ULFS_NDADDR; j++) 265 if (lfs_dino_getdb(fs, dp, j) != 0) { 266 if (debug) 267 printf("bad direct addr for size %ju lbn %jd: 0x%jx\n", 268 (uintmax_t)lfs_dino_getsize(fs, dp), 269 (intmax_t)j, 270 (intmax_t)lfs_dino_getdb(fs, dp, j)); 271 goto unknown; 272 } 273 for (j = 0, ndb -= ULFS_NDADDR; ndb > 0; j++) 274 ndb /= LFS_NINDIR(fs); 275 for (; j < ULFS_NIADDR; j++) 276 if (lfs_dino_getib(fs, dp, j) != 0) { 277 if (debug) 278 printf("bad indirect addr for size %ju # %jd: 0x%jx\n", 279 (uintmax_t)lfs_dino_getsize(fs, dp), 280 (intmax_t)j, 281 (intmax_t)lfs_dino_getib(fs, dp, j)); 282 goto unknown; 283 } 284 if (ftypeok(dp) == 0) 285 goto unknown; 286 n_files++; 287 lncntp[inumber] = lfs_dino_getnlink(fs, dp); 288 if (lfs_dino_getnlink(fs, dp) <= 0) { 289 zlnp = emalloc(sizeof *zlnp); 290 zlnp->zlncnt = inumber; 291 zlnp->next = zlnhead; 292 zlnhead = zlnp; 293 } 294 if (mode == LFS_IFDIR) { 295 if (lfs_dino_getsize(fs, dp) == 0) 296 statemap[inumber] = DCLEAR; 297 else 298 statemap[inumber] = DSTATE; 299 cacheino(dp, inumber); 300 } else 301 statemap[inumber] = FSTATE; 302 303 /* 304 * Check for an orphaned file. These happen when the cleaner has 305 * to rewrite blocks from a file whose directory operation (removal) 306 * is in progress. 307 */ 308 if (lfs_dino_getnlink(fs, dp) <= 0) { 309 LFS_IENTRY(ifp, fs, inumber, bp); 310 if (lfs_if_getnextfree(fs, ifp) == LFS_ORPHAN_NEXTFREE) { 311 statemap[inumber] = (mode == LFS_IFDIR ? DCLEAR : FCLEAR); 312 /* Add this to our list of orphans */ 313 zlnp = emalloc(sizeof *zlnp); 314 zlnp->zlncnt = inumber; 315 zlnp->next = orphead; 316 orphead = zlnp; 317 } 318 brelse(bp, 0); 319 } 320 321 /* XXX: why VTOD(vp) instead of dp here? */ 322 323 typemap[inumber] = LFS_IFTODT(mode); 324 badblkcount = dupblkcount = 0; 325 idesc->id_number = inumber; 326 (void) ckinode(VTOD(vp), idesc); 327 if (lfs_dino_getblocks(fs, dp) != idesc->id_entryno) { 328 pwarn("INCORRECT BLOCK COUNT I=%llu (%ju SHOULD BE %lld)", 329 (unsigned long long)inumber, lfs_dino_getblocks(fs, dp), 330 idesc->id_entryno); 331 if (preen) 332 printf(" (CORRECTED)\n"); 333 else if (reply("CORRECT") == 0) 334 return; 335 lfs_dino_setblocks(fs, VTOD(vp), idesc->id_entryno); 336 inodirty(VTOI(vp)); 337 } 338 return; 339 unknown: 340 pfatal("UNKNOWN FILE TYPE I=%llu", (unsigned long long)inumber); 341 statemap[inumber] = FCLEAR; 342 if (reply("CLEAR") == 1) { 343 statemap[inumber] = USTATE; 344 vp = vget(fs, inumber); 345 clearinode(inumber); 346 vnode_destroy(vp); 347 } 348 } 349 350 int 351 pass1check(struct inodesc *idesc) 352 { 353 int res = KEEPON; 354 int anyout, ndblks; 355 daddr_t blkno = idesc->id_blkno; 356 struct dups *dlp; 357 struct dups *new; 358 359 if ((anyout = chkrange(blkno, idesc->id_numfrags)) != 0) { 360 blkerror(idesc->id_number, "BAD", blkno); 361 if (badblkcount++ >= MAXBAD) { 362 pwarn("EXCESSIVE BAD BLKS I=%llu", 363 (unsigned long long)idesc->id_number); 364 if (preen) 365 printf(" (SKIPPING)\n"); 366 else if (reply("CONTINUE") == 0) 367 err(EEXIT, "%s", ""); 368 return (STOP); 369 } 370 } else if (!testbmap(blkno)) { 371 seg_table[lfs_dtosn(fs, blkno)].su_nbytes += idesc->id_numfrags * lfs_sb_getfsize(fs); 372 } 373 for (ndblks = idesc->id_numfrags; ndblks > 0; blkno++, ndblks--) { 374 if (anyout && chkrange(blkno, 1)) { 375 res = SKIP; 376 } else if (!testbmap(blkno)) { 377 n_blks++; 378 #ifndef VERBOSE_BLOCKMAP 379 setbmap(blkno); 380 #else 381 setbmap(blkno, idesc->id_number); 382 #endif 383 } else { 384 blkerror(idesc->id_number, "DUP", blkno); 385 #ifdef VERBOSE_BLOCKMAP 386 pwarn("(lbn %lld: Holder is %lld)\n", 387 (long long)idesc->id_lblkno, 388 (long long)testbmap(blkno)); 389 #endif 390 if (dupblkcount++ >= MAXDUP) { 391 pwarn("EXCESSIVE DUP BLKS I=%llu", 392 (unsigned long long)idesc->id_number); 393 if (preen) 394 printf(" (SKIPPING)\n"); 395 else if (reply("CONTINUE") == 0) 396 err(EEXIT, "%s", ""); 397 return (STOP); 398 } 399 new = emalloc(sizeof(struct dups)); 400 new->dup = blkno; 401 if (muldup == 0) { 402 duplist = muldup = new; 403 new->next = 0; 404 } else { 405 new->next = muldup->next; 406 muldup->next = new; 407 } 408 for (dlp = duplist; dlp != muldup; dlp = dlp->next) 409 if (dlp->dup == blkno) 410 break; 411 if (dlp == muldup && dlp->dup != blkno) 412 muldup = new; 413 } 414 /* 415 * count the number of blocks found in id_entryno 416 */ 417 idesc->id_entryno++; 418 } 419 return (res); 420 } 421